分組碼

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

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

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

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

線性分組碼的編碼和解碼　用Vn表示GF(2)域的n維線性空間，Vκ是Vn的κ維子空間，表示一個(n，κ)線性分組碼。是代表Vκ的一組基底。以這組基底構成的矩陣

稱為該線性碼的生成矩陣。對於給定的消息組，按生成矩陣G，m被編為

這就是線性分組碼的編碼規則。若

之秩為並且滿足僅當n滿足HT =0時，才為κ中的碼字。稱H為線性分組碼κ的均等校驗矩陣，稱HT為矢量的伴隨式。假設v是發送的碼矢量，在接收端獲得一個失真的矢量,式中稱為錯誤型。由此

線性碼的解碼原則便以此為基礎。

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

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

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

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

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

其中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，從而可至少糾正個獨立錯誤。BCH碼解碼的第一步是計算伴隨式。假設為發送碼矢量,為接收矢量，而為錯誤矢量，或記為稱為錯誤多項式。於是伴隨矢量之諸分量Sκ由

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

里德-索洛蒙碼 這是一種特殊的非二進位BCH碼。對於任意選取的正整數s,可構造一個相應的碼長為的q進位BCH碼，其中碼元符號取自有限域GF(q)，其中q為某一素數的冪。當時所建立的碼長為的q進位BCH碼便稱為里德-索洛蒙碼，簡稱為RS碼。當,碼元符號取自域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)為戈帕多項式。

例如，α 是域GF(z2)上的本原元素

則

即為這一戈帕碼的碼字。戈帕碼也有類似於BCH碼的解碼方法。

自50年代分組碼的理論獲得發展以來，分組碼在數字通信系統和數據存儲系統中已被廣泛應用。由於大規模和超大規模集成電路的迅速發展，人們開始從易於實現的循環碼理論研究中解脫出來，更重視研究性能良好的非循環線性分組碼和非線性分組碼。人們在分組碼研究中又引進了頻譜方法，這一研究方向受到了較多的注意。