BCH碼檢視原始碼討論檢視歷史

來自 孔夫子舊書網 的圖片

BCH碼是全國科學技術名詞審定委員會審定、公布的一個科技名詞。

語言文字是一個民族文化的結晶。這個民族過去的文化靠着它來流傳,未來的文化也仗着它來推進，從大約是在公元前14世紀，殷商後期的「甲骨文」被認為是「漢字」的第一種形式，西周後期，漢字發展演變為大篆，後秦始皇統一中國，中國文字才逐漸走上了發展的道路，直至今天。

名詞解釋

BCH碼是一類重要的糾錯碼，它把信源待發的信息序列按固定的κ位一組劃分成消息組，再將每一消息組獨立變換成長為n(n>κ)的二進制數字組，稱為碼字。如果消息組的數目為M(顯然M>=2),由此所獲得的M個碼字的全體便稱為碼長為n、信息數目為M的分組碼，記為n，M。把消息組變換成碼字的過程稱為編碼，其逆過程稱為譯碼。

分組碼就其構成方式可分為線性分組碼與非線性分組碼。

線性分組碼是指[n,M]分組碼中的M個碼字之間具有一定的線性約束關係,即這些碼字總體構成了n維線性空間的一個κ維子空間。稱此κ維子空間為(n，κ)線性分組碼，n為碼長，κ為信息位。此處M=2。

非線性分組碼[n，M]是指M個碼字之間不存在線性約束關係的分組碼。d為M個碼字之間的最小距離。非線性分組碼常記為[n，M，d]。非線性分組碼的優點是：對於給定的最小距離d,可以獲得最大可能的碼字數目。非線性分組碼的編碼和譯碼因碼類不同而異。雖然預料非線性分組碼會比線性分組碼具有更好的特性，但在理論上和實用上尚缺乏深入研究（見非線性碼）。

漢明碼

這是最早提出的一類線性分組碼，已廣泛應用於計算機和通信設備。它是由R.W.漢明於1950年提出的。若碼的均等校驗矩陣H由2-1個、按任一次序排列且彼此相異的二進制r維列矢量構成。這樣得到的線性分組碼稱為漢明碼，其分組長為n=2-1，信息位為κ=n-r=2-1-r，即為(2-1，2-1-r)碼。例如，以矩陣

為均等校驗矩陣的線性分組碼便為(7，4)漢明碼。漢明碼的譯碼十分簡單。例如, 假定=(1001100)為發送的碼字,其第3位有錯，即接收矢量為r=(1011100)。於是

恰為矩陣H的第 3 列，因而判定原來發送的碼字為=(1001100)。這種譯碼方式是一般性的。如果接收矢量r在第i位有錯,則其伴隨式Hr剛好為矩陣H的第i列。漢明碼是可以糾正單個錯誤的線性分組碼。

循環碼

具有某種循環特性的線性分組碼，如果(n，κ)線性分組碼Vκ具有如下的性質:對於每一個=(ɑ0,ɑ1，…，)∈Vn，只要∈Vκ,其循環移位()亦屬於Vκ,則稱Vκ為循環碼。循環碼的優點在於其編碼和譯碼手續比一般線性碼簡單，因而易於在設備上實現。使Vn中的每一個矢量=(ɑ0，ɑ1，…，),對應於域GF(2)上的多項式ɑ(x)=ɑ0+ɑ1x+…+x。於是Vn中的全體n維矢量便與上述多項式之間建立了一一對應的關係。基於這種對應,使Vn中除了線性運算而外，還建立了矢量之間的乘法運算。A=(ɑ0,ɑ1,…,)與B=(b0,b1,…,)的乘積ab可視為ɑ(x)b(x)[mod(x-1)]所對應的矢量。因此,一個(n,κ)循環碼的生成矩陣及均等校驗矩陣可分別由生成多項式及均等校驗多項式h(x)所代替，從而簡化了編碼及譯碼運算。

BCH碼

它是一類重要的循環碼，能糾正多個錯誤。假設m是滿足模n(modn)的最小正整數,β是域GF(2)的n次單位原根,作循環碼的生成多項式g(x),以d0-1個接續的元素為根，其中m0,d0均為正整數，且d0≥2。於是

其中mj(x)代表的最小多項式。由這個g(x)所生成的，分組長為n的循環碼稱為BCH碼。它由R.C.Bose，D.K.Ray-Chaudhuri及A.Hocquenghem三人研究而得名。BCH碼的主要數量指標是：碼長n，首元指數m0，設計距離d0，信息位數（表示多項式g(x)的次數）。BCH碼的重要特性在於：設計距離為d0的BCH碼，其最小距離至少為d0，從而可至少糾正(d0-1)/2個獨立錯誤。BCH碼譯碼的第一步是計算伴隨式。假設 為發送碼矢量,為接收矢量,而E=(E0,E1,…,En-1)為錯誤矢量,或記為錯誤多項式。於是伴隨矢量之諸S=(S1，S2，…,S2t)分量Sκ由

決定（κ=1,2,…2t；為簡便計,設m0=1,d0=2t+1）。假設有e個錯誤出現(1≤e≤t),則對應於e個錯誤的Ei厵0。如果E的第j個（從左至右）非零分量是Ei,則稱Xj=β為這個錯誤Ei的錯位，而稱Yj=Ei為這個錯誤的錯值。稱 為錯位多項式。BCH碼譯碼的關鍵是由諸sκ(κ=1,2，…，2t)求出(z)。這可用著名的伯利坎普－梅西迭代算法來完成。這種算法相當於線性移位寄存器（LFDR寄存器）的綜合問題。最後一步是求出(z)的全部根，可用錢天聞搜索算法完成,從而可以定出接收矢量r的全部錯位。