[科普中國]-伯利坎普-韋爾奇算法

伯利坎普－韋爾奇算法（英語：Berlekamp-Welch algorithm）是一種用于高效地解碼BCH碼與里德-所羅門碼的算法。

簡介伯利坎普－韋爾奇算法（英語：Berlekamp-Welch algorithm）是一種用于高效地解碼BCH碼與里德-所羅門碼的算法，其名取自埃爾溫·伯利坎普與勞埃德·韋爾奇。伯利坎普－韋爾奇算法的優(yōu)點(diǎn)在于這一算法僅需利用矩陣運(yùn)算。12這一算法的時(shí)間復(fù)雜度為。

算法伯利坎普－韋爾奇算法通常被用于解碼里德-所羅門碼。假使在有限體GF(q)上有 n個(gè)數(shù)字，利用RS碼編為n-1次多項(xiàng)式。如果已知傳輸信道會錯誤傳輸 k個(gè)值，那么RS碼可以傳輸 P(i)上的n+2k個(gè)點(diǎn)(i,P(i))。因此，解碼者的問題在于要辨認(rèn)出哪k個(gè)點(diǎn)是錯誤的。令解碼者接收到的點(diǎn)值為R(i)，可以看出對于且僅對于所有正確傳輸?shù)狞c(diǎn)i，P(i)=R(i)。

錯誤辨認(rèn)多項(xiàng)式伯利坎普－韋爾奇算法引入了錯誤辨認(rèn)多項(xiàng)式的概念，也即多項(xiàng)式，其中e的值為所有k個(gè)錯誤傳輸?shù)狞c(diǎn)的i值（均未知）。由于E(i)=0當(dāng)且僅當(dāng)i對應(yīng)一個(gè)錯誤傳輸?shù)狞c(diǎn)，可以看出對于所有i值，，其中R(i)對于所有i均為已知常量。令Q(i)=R(i)E(i)，可以看出左側(cè)為一個(gè)n+k-1次的多項(xiàng)式，右側(cè)為一個(gè)k次的多項(xiàng)式，但其最高次系數(shù)為1。因此，整個(gè)線性系統(tǒng)有n+2k個(gè)方程式與n+2k個(gè)未知數(shù)，可以用線性代數(shù)的方法解出，并可以由P(i)=Q(i)/E(i)解出原始的編碼多項(xiàng)式并讀出編碼值。

本詞條內(nèi)容貢獻(xiàn)者為:

胡啟洲 - 副教授 - 南京理工大學(xué)