伯利坎普-韋爾奇演算法

伯利坎普-韋爾奇演算法(英語:Berlekamp-Welch algorithm)是一種用於高效地解碼BCH碼里德-所羅門碼演算法,其名取自埃爾溫·伯利坎普勞埃德·韋爾奇。伯利坎普-韋爾奇演算法的優點在於這一演算法僅需利用矩陣運算。[1][2]這一演算法的時間複雜度[3]

演算法

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

錯誤辨認多項式

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

註釋

  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).