新起点
伯利坎普-韦尔奇算法
2020-08-02 20:22:03

伯利坎普-韦尔奇算法(英语:Berlekamp-Welch algorithm)是一种用于高效地解码BCH码与里德-所罗门码的算法,其名取自埃尔温·伯利坎普与劳埃德·韦尔奇。伯利坎普-韦尔奇算法的优点在于这一算法仅需利用矩阵运算。这一算法的时间复杂度为 O ( N 3 ) {\displaystyle O(N^{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}}

网站公告: