伯利坎普-韦尔奇算法
来自维基百科,自由的百科全书
伯利坎普-韦尔奇算法(英語:Berlekamp-Welch algorithm)是一種用於高效地解碼BCH碼與里德-所羅門碼的演算法,其名取自埃尔温·伯利坎普與勞埃德·韋爾奇。伯利坎普-韦尔奇算法的優點在於這一演算法僅需利用矩陣運算。[1][2]這一演算法的時間複雜度為。[3]
演算法
伯利坎普-韦尔奇算法通常被用於解碼里德-所羅門碼。假使在有限體上有個數字,利用RS碼編為次多項式。如果已知傳輸信道會錯誤傳輸個值,那麼RS碼可以傳輸上的個點。因此,解碼者的問題在於要辨認出哪個點是錯誤的。令解碼者接收到的點值為,可以看出對於且僅對於所有正確傳輸的點,。
伯利坎普-韦尔奇算法引入了錯誤辨認多項式的概念,也即多項式,其中的值為所有個錯誤傳輸的點的值(均未知)。由於當且僅當對應一個錯誤傳輸的點,可以看出對於所有值,,其中對於所有i均為已知常數。令,可以看出左側為一個次的多項式,右側為一個次的多項式,但其最高次係數為1。因此,整個線性系統有個方程式與個未知數,可以用線性代數的方法解出,並可以由解出原始的編碼多項式並讀出編碼值。
註釋
Wikiwand - on
Seamless Wikipedia browsing. On steroids.