伯利坎普-韦尔奇算法

伯利坎普-韦尔奇算法(英语: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).