伯利坎普－韋爾奇算法(伯利坎普－韋爾奇算法)

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

基本介紹

• 中文名：伯利坎普－韋爾奇算法
• 外文名：Berlekamp-Welch algorithm

算法

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

錯誤辨認多項式

伯利坎普－韋爾奇算法引入了錯誤辨認多項式的概念，也即多項式 ，其中 的值為所有 個錯誤傳輸的點的 值（均未知）。由於 若且唯若 對應一個錯誤傳輸的點，可以看出對於所有值，，其中對於所有i均為已知常量。令 ，可以看出左側為一個 次的多項式，右側為一個 次的多項式，但其最高次係數為1。因此，整個線性系統有個方程式與 個未知數，可以用線性代數的方法解出，並可以由 解出原始的編碼多項式並讀出編碼值 。