伯利坎普-韦尔奇算法 (英语:Berlekamp-Welch algorithm )是一种用于高效地解码BCH码 与里德-所罗门码 的算法 ,其名取自埃尔温·伯利坎普 与劳埃德·韦尔奇 。伯利坎普-韦尔奇算法的优点在于这一算法仅需利用矩阵 运算。[ 1] [ 2] 这一算法的时间复杂度 为
O
(
N
3
)
{\displaystyle O(N^{3})}
。[ 3]
算法
伯利坎普-韦尔奇算法通常被用于解码里德-所罗门码 。假使在有限体
G
F
(
q
)
{\displaystyle GF(q)}
上有
n
{\displaystyle n}
个数字
m
1
,
…
,
m
n
{\displaystyle m_{1},\dots ,m_{n}}
,利用RS码编为
n
−
1
{\displaystyle n-1}
次多项式
P
(
i
)
=
m
i
{\displaystyle P(i)=m_{i}}
。如果已知传输信道会错误传输
k
{\displaystyle k}
个值,那么RS码可以传输
P
(
i
)
{\displaystyle P(i)}
上的
n
+
2
k
{\displaystyle n+2k}
个点
(
i
,
P
(
i
)
)
{\displaystyle (i,P(i))}
。因此,解码者的问题在于要辨认出哪
k
{\displaystyle k}
个点是错误的。令解码者接收到的点值为
R
(
i
)
{\displaystyle R(i)}
,可以看出对于且仅对于所有正确传输的点
i
{\displaystyle i}
,
P
(
i
)
=
R
(
i
)
{\displaystyle P(i)=R(i)}
。
错误辨认多项式
伯利坎普-韦尔奇算法引入了错误辨认多项式的概念,也即多项式
E
(
i
)
=
(
i
−
e
1
)
(
i
−
e
2
)
…
(
i
−
e
k
)
{\displaystyle E(i)=(i-e_{1})(i-e_{2})\dots (i-e_{k})}
,其中
e
{\displaystyle e}
的值为所有
k
{\displaystyle k}
个错误传输的点的
i
{\displaystyle i}
值(均未知)。由于
E
(
i
)
=
0
{\displaystyle E(i)=0}
当且仅当
i
{\displaystyle i}
对应一个错误传输的点,可以看出对于所有
i
{\displaystyle i}
值,
P
(
i
)
E
(
i
)
=
R
(
i
)
E
(
i
)
{\displaystyle P(i)E(i)=R(i)E(i)}
,其中
R
(
i
)
{\displaystyle R(i)}
对于所有i均为已知常量 。令
Q
(
i
)
=
R
(
i
)
E
(
i
)
{\displaystyle Q(i)=R(i)E(i)}
,可以看出左侧为一个
n
+
k
−
1
{\displaystyle n+k-1}
次的多项式,右侧为一个
k
{\displaystyle k}
次的多项式,但其最高次系数 为1。因此,整个线性系统 有
n
+
2
k
{\displaystyle n+2k}
个方程式与
n
+
2
k
{\displaystyle n+2k}
个未知数,可以用线性代数 的方法解出,并可以由
P
(
i
)
=
Q
(
i
)
/
E
(
i
)
{\displaystyle P(i)=Q(i)/E(i)}
解出原始的编码多项式并读出编码值
m
1
,
…
,
m
n
{\displaystyle m_{1},\dots ,m_{n}}
。
注释
^ Berlekamp, Elwyn R. , Nonbinary BCH decoding, International Symposium on Information Theory, San Remo, Italy, 1967
^ Berlekamp, Elwyn R. , Algebraic Coding Theory Revised, Laguna Hills, CA: Aegean Park Press, 1984 [1968], ISBN 0894120638 . Previous publisher McGraw–Hill, New York, NY.
^ Highly resilient correctors for polynomials – Peter Gemmel and Madhu Sudan's Exposition. (PDF) . [2011-12-31 ] . (原始内容存档 (PDF) 于2016-10-24).