查看“︁伯利坎普-韦尔奇算法”︁的源代码

{{noteTA
|G1=IT
}}

'''伯利坎普－韦尔奇算法'''（{{lang-en|Berlekamp-Welch algorithm}}）是一種用於高效地解碼[[BCH碼]]與[[里德-所羅門碼]]的[[演算法]]，其名取自[[埃尔温·伯利坎普]]與[[勞埃德·韋爾奇]]。伯利坎普－韦尔奇算法的優點在於這一演算法僅需利用[[矩陣]]運算。<ref name="berlekamp_bch">{{Citation
 |last= Berlekamp
 |first= Elwyn R.
 |authorlink= 埃尔温·伯利坎普
 |title= Nonbinary BCH decoding
 |year= 1967
 |series= International Symposium on Information Theory
 |place= San Remo, Italy}}</ref><ref name="berlekamp_algebraic">{{Citation
 |last= Berlekamp
 |first= Elwyn R.
 |authorlink= 埃尔温·伯利坎普
 |title=Algebraic Coding Theory
 |place=Laguna Hills, CA
 |origyear=1968
 |year=1984
 |edition= Revised
 |publisher=Aegean Park Press
 |isbn= 0894120638}}. Previous publisher McGraw–Hill, New York, NY.</ref>這一演算法的[[時間複雜度]]為<math>O(N^3)</math>。<ref name="gemmel_sudan">{{Cite web |url=http://people.csail.mit.edu/madhu/papers/1992/gemmell.pdf |title=Highly resilient correctors for polynomials – Peter Gemmel and Madhu Sudan's Exposition. |accessdate=2011-12-31 |archive-date=2016-10-24 |archive-url=https://web.archive.org/web/20161024003108/http://people.csail.mit.edu/madhu/papers/1992/gemmell.pdf |dead-url=no }}</ref>

==演算法==
伯利坎普－韦尔奇算法通常被用於解碼[[里德-所羅門碼]]。假使在[[有限體]]<math>GF(q)</math>上有<math>n</math>個數字<math>m_1, \dots , m_n</math>，利用RS碼編為<math>n-1</math>次[[多項式]]<math>P(i)=m_i</math>。如果已知傳輸信道會錯誤傳輸<math>k</math>個值，那麼RS碼可以傳輸<math>P(i)</math>上的<math>n+2k</math>個點<math>(i, P(i))</math>。因此，解碼者的問題在於要辨認出哪<math>k</math>個點是錯誤的。令解碼者接收到的點值為<math>R(i)</math>，可以看出對於且僅對於所有正確傳輸的點<math>i</math>，<math>P(i)=R(i)</math>。

===錯誤辨認多項式===
伯利坎普－韦尔奇算法引入了錯誤辨認多項式的概念，也即多項式<math>E(i)=(i-e_1)(i-e_2)\dots(i-e_k)</math>，其中<math>e</math>的值為所有<math>k</math>個錯誤傳輸的點的<math>i</math>值（均未知）。由於<math>E(i)=0</math>當且僅當<math>i</math>對應一個錯誤傳輸的點，可以看出對於所有<math>i</math>值，<math>P(i)E(i)=R(i)E(i)</math>，其中<math>R(i)</math>對於所有i均為已知[[常數]]。令<math>Q(i)=R(i)E(i)</math>，可以看出左側為一個<math>n+k-1</math>次的多項式，右側為一個<math>k</math>次的多項式，但其最高次[[係數]]為1。因此，整個[[線性系統]]有<math>n+2k</math>個方程式與<math>n+2k</math>個未知數，可以用[[線性代數]]的方法解出，並可以由<math>P(i)=Q(i)/E(i)</math>解出原始的編碼多項式並讀出編碼值<math>m_1,\dots,m_n</math>。

==註釋==
{{reflist}}


[[Category:有限域]]
[[Category:编码理论]]
[[Category:信息论]]
[[Category:错误检测与校正]]