伯利坎普-韦尔奇算法

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

演算法

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

錯誤辨認多項式

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