伯利坎普-韋爾奇演算法

伯利坎普－韋爾奇演算法（英語：Berlekamp-Welch algorithm）是一種用於高效地解碼BCH碼與里德-所羅門碼的演算法，其名取自埃爾溫·伯利坎普與勞埃德·韋爾奇。伯利坎普－韋爾奇演算法的優點在於這一演算法僅需利用矩陣運算。^[1][2]這一演算法的時間複雜度為${\displaystyle O(N^{3})}$。^[3]

演算法

伯利坎普－韋爾奇演算法通常被用於解碼里德-所羅門碼。假使在有限體${\displaystyle GF(q)}$上有${\displaystyle n}$個數字${\displaystyle m_{1},\dots ,m_{n}}$，利用RS碼編為${\displaystyle n-1}$次多項式${\displaystyle P(i)=m_{i}}$。如果已知傳輸信道會錯誤傳輸${\displaystyle k}$個值，那麼RS碼可以傳輸${\displaystyle P(i)}$上的${\displaystyle n+2k}$個點${\displaystyle (i,P(i))}$。因此，解碼者的問題在於要辨認出哪${\displaystyle k}$個點是錯誤的。令解碼者接收到的點值為${\displaystyle R(i)}$，可以看出對於且僅對於所有正確傳輸的點${\displaystyle i}$，${\displaystyle P(i)=R(i)}$。

錯誤辨認多項式

伯利坎普－韋爾奇演算法引入了錯誤辨認多項式的概念，也即多項式${\displaystyle E(i)=(i-e_{1})(i-e_{2})\dots (i-e_{k})}$，其中${\displaystyle e}$的值為所有${\displaystyle k}$個錯誤傳輸的點的${\displaystyle i}$值（均未知）。由於${\displaystyle E(i)=0}$若且唯若${\displaystyle i}$對應一個錯誤傳輸的點，可以看出對於所有${\displaystyle i}$值，${\displaystyle P(i)E(i)=R(i)E(i)}$，其中${\displaystyle R(i)}$對於所有i均為已知常數。令${\displaystyle Q(i)=R(i)E(i)}$，可以看出左側為一個${\displaystyle n+k-1}$次的多項式，右側為一個${\displaystyle k}$次的多項式，但其最高次系數為1。因此，整個線性系統有${\displaystyle n+2k}$個方程式與${\displaystyle n+2k}$個未知數，可以用線性代數的方法解出，並可以由${\displaystyle P(i)=Q(i)/E(i)}$解出原始的編碼多項式並讀出編碼值${\displaystyle m_{1},\dots ,m_{n}}$。

註釋

1. Berlekamp, Elwyn R., Nonbinary BCH decoding, International Symposium on Information Theory, San Remo, Italy, 1967
2. Berlekamp, Elwyn R., Algebraic Coding Theory Revised, Laguna Hills, CA: Aegean Park Press, 1984 [1968], ISBN 0894120638. Previous publisher McGraw–Hill, New York, NY.
3. Highly resilient correctors for polynomials – Peter Gemmel and Madhu Sudan's Exposition. (PDF). [2011-12-31]. （原始內容存檔 (PDF)於2016-10-24）.