一類重要的改錯碼,它把信源待發的資訊序列按固定的κ位元一組劃分成消息組,再將每一消息組獨立變換成長為n(n>κ)的二進位數字字組,稱為碼字。如果消息組的數目為M(顯然M≤2κ),由此所獲得的M/span>個碼字的全體便稱為碼長為n、信息數目為M的分組碼,記為[n,M]。把消息組變換成碼字的過程稱為編碼,其逆過程稱為譯碼。
線性分組碼與非線性分組碼 分組碼就其構成方式可分為線性分組碼與非線性分組碼。
線性分組碼是指[n,M]分組碼中的M個碼字之間具有一定的線性約束關系,即這些碼字總體構成瞭n維線性空間的一個κ維子空間。稱此κ維子空間為(n,κ)線性分組碼,n為碼長,κ為信息位。此處M=2κ。
非線性分組碼[n,M]是指M個碼字之間不存在線性約束關系的分組碼。d為M個碼字之間的最小距離。非線性分組碼常記為[n,M,d]。非線性分組碼的優點是:對於給定的最小距離d,可以獲得最大可能的碼字數目。非線性分組碼的編碼和譯碼因碼類不同而異。雖然預料非線性分組碼會比線性分組碼具有更好的特性,但在理論上和實用上尚缺乏深入研究(見非線性碼)。
線性分組碼的編碼和譯碼 用Vn表示 GF(2)域的n維線性空間,Vκ是Vn的κ維子空間,表示一個(n,κ)線性分組碼。Ei=(vi1,vi2…,vin)是代表Vκ的一組基底(i=1,2,…,κ)。以這組基底構成的矩陣
稱為該(n,κ)線性碼的生成矩陣。對於給定的消息組m=(m1,m2,…,mκ),按生成矩陣G,m被編為
mG=m1E1+m2E2+…+mκEκ
這就是線性分組碼的編碼規則。若
之秩為n-κ並且滿足GHT=0,僅當
=( v 1, v 2,…, v n)∈ n滿足 H T =0時,才為 κ中的碼字。稱 H為( n, κ)線性分組碼 κ的均等校驗矩陣,稱 H T為矢量 的伴隨式 。假設 v是發送的碼矢量,在接收端獲得一個失真的矢量 r= v+ E,式中 E=( e 1, e 2,…, e n)稱為錯誤型。由此rHT=(v+e)HT=eHT
線性碼的譯碼原則便以此為基礎。
漢明碼 這是最早提出的一類線性分組碼,已廣泛應用於計算機和通信設備。它是由R.W.漢明於1950年提出的。若碼的均等校驗矩陣H由2r-1個、按任一次序排列且彼此相異的二進制 r維列矢量構成。這樣得到的線性分組碼稱為漢明碼,其分組長為n=2r-1,信息位為κ=n-r =2r-1-r,即為(2r-1,2r-1-r)碼。例如,以矩陣
為均等校驗矩陣的線性分組碼便為(7,4)漢明碼。漢明碼的譯碼十分簡單。例如,假定
=(1001100)為發送的碼字,其第3位有錯,即接收矢量為 r =(1011100)。於是恰為矩陣H的第3 列,因而判定原來發送的碼字為
=(1001100)。這種譯碼方式是一般性的。如果接收矢量 r在第 i位有錯,則其伴隨式 Hr T剛好為矩陣 H的第 i列。漢明碼是可以糾正單個錯誤的線性分組碼。循環碼 具有某種循環特性的線性分組碼,如果(n,κ)線性分組碼Vκ具有如下的性質:對於每一個
=( ɑ 0, ɑ 1,…, )∈ V n,隻要 ∈ V κ,其循環移位( )亦屬於 V κ,則稱 V κ為循環碼。循環碼的優點在於其編碼和譯碼手續比一般線性碼簡單,因而易於在設備上實現。使 V n中的每一個矢量 =( ɑ 0, ɑ 1,…, ),對應於域 G F(2)上的多項式 ɑ( x)= ɑ 0+ ɑ 1 x +…+ x n -1。於是 V n中的全體 n維矢量便與上述多項式之間建立瞭一一對應的關系。基於這種對應,使 V n中除瞭線性運算而外,還建立瞭矢量之間的乘法運算。 A=( ɑ 0, ɑ 1,…, )與 B=( b 0, b 1,…, )的乘積 ab可視為 ɑ( x) b( x)[mod( x n-1)]所對應的矢量。因此,一個( n, κ)循環碼的生成矩陣及均等校驗矩陣可分別由生成多項式及均等校驗多項式 h( x)所代替,從而簡化瞭編碼及譯碼運算。BCH碼 它是一類重要的循環碼,能糾正多個錯誤。假設m是滿足2m≡1(mod n)的最小正整數,β是域GF(2m)的n次單位原根,作循環碼的生成多項式g(x),以d0-1個接續的元素
為根,其中 m 0, d 0均為正整數,且 d 0≥2。於是其中mj(x)代表
的最小多項式。由這個 g( x)所生成的,分組長為 n的循環碼稱為BCH碼。它由R.C.Bose,D.K.Ray-Chaudhuri及A.Hocquenghem三人研究而得名。BCH碼的主要數量指標是:碼長 n,首元指數 m 0,設計距離 d 0,信息位數 ( 表示多項式 g( x)的次數)。BCH碼的重要特性在於:設計距離為 d 0的BCH碼,其最小距離至少為 d 0,從而可至少糾正 個獨立錯誤。BCH碼譯碼的第一步是計算伴隨式。假設 為發送碼矢量, 為接收矢量,而 E=( E 0, E 1,…, E n-1)為錯誤矢量,或記為 稱為錯誤多項式。於是伴隨矢量之諸 S=( S 1, S 2,…, S 2 t)分量 S κ由決定(κ=1,2,…2t;為簡便計,設m0=1,d0=2t+1)。假設有e個錯誤出現(1≤e≤t),則對應於e個錯誤的Ei≠0。如果E 的第j個(從左至右)非零分量是Ei,則稱Xj=βi為這個錯誤Ei的錯位,而稱Yj=Ei為這個錯誤的錯值。稱
為錯位多項式。BCH碼譯碼的關鍵是由諸 s κ( κ=1,2,…, 2 t)求出 ( z)。這可用著名的伯利坎普-梅西迭代算法來完成。這種算法相當於線性移位寄存器的綜合問題。最後一步是求出 ( z)的全部根,可用錢天聞搜索算法完成,從而可以定出接收矢量 r的全部錯位。裡德-索洛蒙碼 這是一種特殊的非二進制BCH碼。對於任意選取的正整數s,可構造一個相應的碼長為n=qs-1的q進制BCH碼,其中碼元符號取自有限域GF(q),其中q為某一素數的冪。當s=1,q>2時所建立的碼長為n=q-1的q進制BCH碼便稱為裡德-索洛蒙碼,簡稱為RS碼。當q=2m(m>1),碼元符號取自域GF(2m)的二進制RS碼可用來糾正成區間出現的突發錯誤。這種碼在短波信道中特別有用。
戈帕碼 這是一種重要的線性分組碼,它不僅包括常見的諸如本原BCH碼等大量的循環碼類,還包括相當多的非循環線性分組碼類,並且後一種碼具有良好的漸近特性。戈帕碼的理論實質在於將每一個碼矢量與一個有理分式相對應。q是某一個素數冪,g(z)是域GF(qm)上的任意多項式,L表示域GF(qm)中所有不為g(z)之根的元素所成之集合,|L|代表L中元素的數目。於是存在一個以GF(q)為符號域,以GF(qm)為位置域的線性分組碼。碼長為|L|,它的各碼元用L中的元素來標志。這種碼可定義為滿足條件
的一切GF(q)上的全體|L|維矢量
的集合,式中 這種碼稱為戈帕碼,稱 g( z)為戈帕多項式。例如,q=2,m=2,g(z)=z+α,α 是域GF(z2)上的本原元素
α2+α+1=0 α3=1
則
L={β1,β2,β3}={0,1,α2}
於是
可驗證,(1,1,1)即為這一戈帕碼的碼字。戈帕碼也有類似於BCH碼的譯碼方法。
自50年代分組碼的理論獲得發展以來,分組碼在數字通信系統和數據存儲系統中已被廣泛應用。由於大規模和超大規模集成電路的迅速發展,人們開始從易於實現的循環碼理論研究中解脫出來,更重視研究性能良好的非循環線性分組碼和非線性分組碼。人們在分組碼研究中又引進瞭頻譜方法,這一研究方向受到瞭較多的註意。