伯利坎普-韋爾奇算法(種用於高效地解碼BCH碼與里德-所羅門碼的算法)

本詞條是多義詞,共2個義項
更多義項 ▼ 收起列表 ▲

伯利坎普-韋爾奇算法(英語:Berlekamp-Welch algorithm)是一種用於高效地解碼BCH碼與里德-所羅門碼的算法

基本介紹

簡介,算法,錯誤辨認多項式,

簡介

伯利坎普-韋爾奇算法(英語:Berlekamp-Welch algorithm)是一種用於高效地解碼BCH碼與里德-所羅門碼的算法,其名取自埃爾溫·伯利坎普與勞埃德·韋爾奇。伯利坎普-韋爾奇算法的優點在於這一算法僅需利用矩陣運算。這一算法的時間複雜度

算法

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

錯誤辨認多項式

伯利坎普-韋爾奇算法引入了錯誤辨認多項式的概念,也即多項式
,其中e的值為所有k個錯誤傳輸的點的i值(均未知)。由於E(i)=0若且唯若i對應一個錯誤傳輸的點,可以看出對於所有i值,
,其中R(i)對於所有i均為已知常量。令Q(i)=R(i)E(i),可以看出左側為一個n+k-1次的多項式,右側為一個k次的多項式,但其最高次係數為1。因此,整個線性系統有n+2k個方程式與n+2k個未知數,可以用線性代數的方法解出,並可以由P(i)=Q(i)/E(i)解出原始的編碼多項式並讀出編碼值

相關詞條

熱門詞條

聯絡我們