伯利坎普－韦尔奇算法 （英語：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}}
n
−
1
{\displaystyle n-1}
多項式
P
(
i
)
=
m
i
{\displaystyle P(i)=m_{i}}
k
{\displaystyle k}
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)}
常數 。令
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 ^ Highly resilient correctors for polynomials – Peter Gemmel and Madhu Sudan's Exposition. (PDF) . [2011-12-31 ] . （原始内容存档 (PDF) 于2016-10-24）.
