跳转到内容

伯利坎普-韦尔奇算法

本页使用了标题或全文手工转换
维基百科,自由的百科全书

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