本页使用了标题或全文手工转换

伯利坎普-韦尔奇算法

维基百科,自由的百科全书
跳转至: 导航搜索

伯利坎普-韦尔奇算法英语Berlekamp-Welch algorithm)是一種用於高效地解碼BCH碼里德-所羅門碼演算法,其名取自埃尔温·伯利坎普勞埃德·韋爾奇。伯利坎普-韦尔奇算法的優點在於這一演算法僅需利用矩陣運算。[1][2]這一演算法的時間複雜度O(N^3)[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),可以看出對於且僅對於所有正確傳輸的點iP(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

註釋[编辑]

  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.