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

伯利坎普－韋爾奇算法（Berlekamp-Welch algorithm）是一種用于高效地解碼BCH碼與里德-所羅門碼的算法，其名取自埃爾溫·伯利坎普與勞埃德·韋爾奇。伯利坎普－韋爾奇算法的優(yōu)點(diǎn)在于這一算法僅需利用矩陣運(yùn)算。1

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

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

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

李航 - 副教授 - 西南大學(xué)