演算法
伯利坎普-韦尔奇算法通常被用於解碼里德-所羅門碼。假使在有限體
上有
個數字
,利用RS碼編為
次多項式
。如果已知傳輸信道會錯誤傳輸
個值,那麼RS碼可以傳輸
上的
個點
。因此,解碼者的問題在於要辨認出哪
個點是錯誤的。令解碼者接收到的點值為
,可以看出對於且僅對於所有正確傳輸的點
,
。
錯誤辨認多項式
伯利坎普-韦尔奇算法引入了錯誤辨認多項式的概念,也即多項式
,其中
的值為所有
個錯誤傳輸的點的
值(均未知)。由於
當且僅當
對應一個錯誤傳輸的點,可以看出對於所有
值,
,其中
對於所有i均為已知常數。令
,可以看出左側為一個
次的多項式,右側為一個
次的多項式,但其最高次係數為1。因此,整個線性系統有
個方程式與
個未知數,可以用線性代數的方法解出,並可以由
解出原始的編碼多項式並讀出編碼值
。
註釋