《通信原理與通信技術(shù)》課件第8章

第8章差錯控制編碼

8.1差錯控制編碼的概念

8.2差錯控制方式

8.3差錯控制編碼分類

8.4檢錯和糾錯原理

8.5幾種常用的檢錯碼

8.6線性分組碼

8.7循環(huán)碼

8.8小資料——香農(nóng)

8.1差錯控制編碼的基本概念

對于模擬信號而言，信號波形會發(fā)生畸變，引起信號失真（即信息失真），并且信號一旦失真就很難糾正過來。因此，在模擬系統(tǒng)中只能采取各種抗干擾、防干擾措施盡量將干擾降到最低程度以保證通信質(zhì)量。而在數(shù)字系統(tǒng)中，盡管干擾同樣會使信號產(chǎn)生變形，但一定程度的信號畸變不會影響對數(shù)字信息的接收，因為我們只關(guān)心數(shù)字信號的電平狀態(tài)（是高電平還是低電平，或者是正電平還是負電平），而不太在乎其波形的失真。也就是說，數(shù)字系統(tǒng)對干擾或信道特性不良的寬容度比模擬系統(tǒng)的大（這就是數(shù)字通信比模擬通信抗干擾能力強的原因之一）。但是，當干擾超過系統(tǒng)的限度時，就會使數(shù)字信號產(chǎn)生誤碼，從而引起信息傳輸錯誤。數(shù)字通信系統(tǒng)除了可以采取與模擬系統(tǒng)同樣的措施以降低干擾和信道不良對信號造成的影響之外，還可以通過對所傳數(shù)字信息進行特殊處理（即差錯控制編碼）對誤碼進行檢錯和糾錯，以進一步將誤碼率降低，從而滿足通信要求。因此，數(shù)字通信系統(tǒng)可以從硬件上的抗干擾措施和軟件上的信道編碼兩個方面對信息傳輸中出現(xiàn)的錯誤進行控制和糾正。

圖8－1兩種通信系統(tǒng)干擾示意圖

在圖1-3中，我們看到數(shù)字通信系統(tǒng)有信源編/譯碼和信道編/譯碼兩對功能模塊。因為信源輸出是攜帶模擬消息的模擬信號，所以，信源編碼模塊的主要任務是把模擬信號轉(zhuǎn)換為數(shù)字信號（比如采用PCM實現(xiàn)A/D轉(zhuǎn)換，形成原始編碼）。若信源輸出為離散消息（則圖1-3也可以看做是一個數(shù)據(jù)通信系統(tǒng)的示意圖），信源編碼模塊的主要任務則是把這些離散消息變成數(shù)字代碼（數(shù)據(jù)），并盡量減少編碼多余度（原始碼元個數(shù)），從而提高編碼效率并降低碼元速率。比如，消息“真”和“假”可以用符號“T”和“F”表示，那么信源編碼就是將消息符號“T”和“F”變換成“0”和“1”、“00”和“11”或其他碼字，顯然，“0”和“1”的編碼效率最高?？梢?，信源編碼就是把信源的消息符號變換成數(shù)據(jù)的過程。信源編碼的主要目的是提高通信的有效性，信源譯碼模塊則完成信源編碼的逆向過程。

信道編碼的目的是提高通信過程的可靠性，其主要任務就是對信源編碼器輸出的數(shù)字基帶信號按一定的規(guī)律加入一些冗余碼元，使之攜帶檢、糾錯信息，以便于收信端利用這些信息檢出或糾正通信過程中出現(xiàn)的錯碼，從而提高信息傳輸?shù)目煽啃?。可見，信道編碼就是使原來沒有規(guī)律性或規(guī)律性不強的原始數(shù)字信號變換成了具有規(guī)律性或規(guī)律性變強的數(shù)字信號，而信道譯碼則是利用這種規(guī)律性來鑒別信號是否發(fā)生錯誤或進而糾正錯誤。香農(nóng)在1848年和1957年發(fā)表的《通信的數(shù)學理論》、《適用于有擾信道的編碼理論某些成果》兩篇論文中提出了關(guān)于有擾信道中信息傳輸?shù)闹匾碚摗戕r(nóng)第二定理。該定理指出：對于一個給定的有擾信道，若該信道容量為C，則只要信道中的信息傳輸速率R小于C，就一定存在一種編碼方式，使編碼后的誤碼率隨著碼長n的增加按指數(shù)下降到任意小的值?；蛘哒f只要R<C，就存在傳輸速率為R的糾錯碼。

該定理雖然沒有明確指出如何對數(shù)據(jù)信息進行糾錯編碼，也沒有給出這種具有糾錯能力通信系統(tǒng)的具體實現(xiàn)方法，但它奠定了信道編碼的理論基礎，并為人們從理論上指出了信道編碼的努力方向。

綜上所述，信道編碼的基本思想就是在數(shù)字信號序列中加入一些冗余碼元。這些冗余碼元不含有通信信息，但與信號序列中的信息碼元有著某種制約關(guān)系，這種關(guān)系在一定程度上可以幫助人們發(fā)現(xiàn)或糾正在信息序列中出現(xiàn)的錯誤（也就是誤碼），從而起到降低誤碼率、提高可靠性的作用。這些冗余碼元被稱為監(jiān)督（或校驗）碼元。所謂信道編碼，就是尋找合適的方法將信息碼元和監(jiān)督碼元編排在一起的過程。

需要說明的是，一種比較流行的說法是“信道編碼就是差錯控制編碼”。但在第6章中，我們知道基帶信號通常需要進行碼型變換，使得數(shù)字信號與信道匹配，以利于在信道中傳輸，從而提高通信的可靠性。顯然，從目的上看，碼型變換和信道編碼是一致的，都是提高通信的可靠性；從通信流程上看，信道編碼和碼型變換緊密相連且都處在信號傳輸階段；另外，碼型變換實際上也是一種編碼。因此，我們認為可以把碼型變換歸為信道編碼的一個分支，或者說，信道編碼應該包含差錯控制編碼和碼型變換兩部分內(nèi)容。差錯控制編碼從解碼角度提高可靠性，而碼型變換從傳輸角度提高可靠性；差錯控制編碼注重數(shù)字信號的內(nèi)在規(guī)律性，而碼型變換強調(diào)數(shù)字信號的外在表現(xiàn)形式。這樣，圖1－3的系統(tǒng)功能才更加準確和完善。至此，我們可以認為：信道編碼是指對信源編碼器輸出的原始信息數(shù)據(jù)碼進行差錯控制編碼以及將其變換成適合信道傳輸?shù)拇a型的全過程。圖8-2信源編碼和信道編碼示意圖

8.2差錯控制方式

前向糾錯（FEC）、檢錯重發(fā)（ARQ）和混合糾錯（HEC）是常用的三種差錯控制方式。圖8-3是這三種方式構(gòu)成的差錯控制系統(tǒng)示意圖。圖8－3常用三種差錯控制系統(tǒng)原理框圖在前向糾錯系統(tǒng)中，發(fā)送端將信息碼經(jīng)信道編碼后變成能夠糾正錯誤的碼組，然后通過信道發(fā)送出去；接收端收到這些碼組后，根據(jù)與發(fā)送端約定好的編碼規(guī)則，通過譯碼能自動發(fā)現(xiàn)并糾正因傳輸帶來的數(shù)據(jù)錯誤。前向糾錯方式只要求單向信道，因此特別適合于只能提供單向信道的場合，同時也適合一點發(fā)送多點接收的廣播方式。因為不需要對發(fā)送端反饋信息，所以接收信號的延時小、實時性好。這種糾錯系統(tǒng)的缺點是設備復雜、成本高，且糾錯能力愈強，編譯碼設備就愈復雜。

檢錯重發(fā)系統(tǒng)的發(fā)送端將信息碼編成能夠檢錯的碼組發(fā)送到信道，接收端收到一個碼組后進行檢驗，將檢驗結(jié)果（有誤碼或者無誤碼）通過反向信道反饋給發(fā)送端作為對發(fā)送端的一個應答信號。發(fā)送端根據(jù)收到的應答信號做出是繼續(xù)發(fā)送新的數(shù)據(jù)還是把出錯的數(shù)據(jù)重發(fā)的判斷。

檢錯重發(fā)系統(tǒng)根據(jù)工作方式不同又可分為三種，即停發(fā)等候重發(fā)系統(tǒng)、返回重發(fā)系統(tǒng)和選擇重發(fā)系統(tǒng)，如圖8－4所示。在圖8－4（a）中，發(fā)送端在t=0時刻將碼組1發(fā)給接收端，然后停止發(fā)送，等待接收端的應答信號。接收端收到該碼組并檢驗后，將應答信號ACK發(fā)回發(fā)送端，發(fā)送端確認碼組1無錯，就將碼組2發(fā)送出來；接收端對碼組2進行檢驗后通過應答信號NAK告訴發(fā)送端有錯誤，發(fā)送端將碼組2重新發(fā)送一次，接收端第二次收到碼組2經(jīng)檢驗后無錯，即可通過ACK信號告訴發(fā)送端無錯，發(fā)送端接著發(fā)送碼組3……從上述過程中可見，發(fā)送端由于要等接收端的應答信號，發(fā)送過程是間歇式的，因此數(shù)據(jù)傳輸效率不高。但由于該系統(tǒng)原理簡單，因此在計算機通信中仍然得到應用。

圖8－4檢錯重發(fā)的三種工作方式返回重發(fā)系統(tǒng)的工作原理如圖8－3（b）所示。在這種系統(tǒng)中發(fā)送端不停頓地發(fā)送信息碼組，不再等候ACK信號，如果接收端發(fā)現(xiàn)錯誤并發(fā)回NAK信號，則發(fā)送端從下一個碼組開始重發(fā)前一段N個碼組。N的大小取決于信號傳輸和處理所造成的延時，也就是發(fā)送端從發(fā)錯誤碼組開始，到收到NAK信號為止所發(fā)出的碼組個數(shù)，圖中N=5。接收端收到碼組2有錯，發(fā)送端在碼組6后重發(fā)碼組2、3、4、5、6，接收端重新接收，發(fā)送端繼續(xù)發(fā)后續(xù)碼組。這種返回重發(fā)系統(tǒng)的傳輸效率比停發(fā)等候系統(tǒng)有很大改進，在很多數(shù)據(jù)傳輸系統(tǒng)中得到了應用。

圖8－4（c）描述了選擇重發(fā)系統(tǒng)的工作過程。這種重發(fā)系統(tǒng)也是連續(xù)不斷地發(fā)送碼組，接收端檢測到錯誤后發(fā)回NAK信號，但是發(fā)送端不是重發(fā)前N個碼組，而是只重發(fā)有錯誤的那一組。圖中顯示發(fā)送端只重發(fā)接收端檢出有錯的碼組2，對其他碼組不再重發(fā)。接收端對已認可的碼組，從緩沖存儲器讀出時重新排序，恢復出正常的碼組序列。顯然，選擇重發(fā)系統(tǒng)傳輸效率最高，但價格也最貴，因為它要求較為復雜的控制，在收、發(fā)兩端都要求有數(shù)據(jù)緩存器。

混合糾錯方式是前向糾錯方式和檢錯重發(fā)方式的結(jié)合。如圖8－3（c）所示，其內(nèi)層采用FEC方式，糾正部分差錯；外層采用ARQ方式，重傳那些雖已檢出但未糾正的差錯?；旌霞m錯方式在實時性和譯碼復雜性方面是前向糾錯和檢錯重發(fā)方式的折中，較適合于環(huán)路延遲大的高速數(shù)據(jù)傳輸系統(tǒng)。

8.3差錯控制編碼的分類

根據(jù)編碼方式和衡量標準的不同，差錯控制編碼有多種形式和類別，其主要分類如下：

（1）檢錯碼、糾錯碼和糾刪碼。根據(jù)編碼功能可分為檢錯碼、糾錯碼和糾刪碼三種類型，只能完成檢錯功能的叫檢錯碼；具有糾錯能力的叫糾錯碼；而糾刪碼既可檢錯也可糾錯。

（2）線性碼和非線性碼。按照信息碼元和附加的監(jiān)督碼元之間的檢驗關(guān)系可以分為線性碼和非線性碼。若信息碼元與監(jiān)督碼元之間的關(guān)系為線性關(guān)系，即監(jiān)督碼元是信息碼元的線性組合，則稱為線性碼。反之，若兩者不存在線性關(guān)系，則稱為非線性碼。（3）按照信息碼元和監(jiān)督碼元之間的約束方式可分為分組碼和卷積碼。在分組碼中，編碼前先把信息序列分為k位一組，然后用一定規(guī)則附加m位監(jiān)督碼元，形成n=k+m位的碼組。監(jiān)督碼元僅與本碼組的信息碼元有關(guān)，而與其他碼組的信息碼元無關(guān)。但在卷積碼中，碼組中的監(jiān)督碼元不但與本組信息碼元有關(guān)，而且與前面碼組的信息碼元也有約束關(guān)系，就像鏈條那樣一環(huán)扣—環(huán)，所以卷積碼又稱連環(huán)碼或鏈碼。

（4）系統(tǒng)碼與非系統(tǒng)碼。所有碼組的k信息位和m監(jiān)督位排列順序一致且互不相混的碼叫系統(tǒng)碼，反之就是非系統(tǒng)碼。

（5）糾正隨機錯誤碼和糾正突發(fā)錯誤碼。顧名思義，前者用于糾正因信道中出現(xiàn)的隨機獨立干擾引起的誤碼，后者主要對付信道中出現(xiàn)的突發(fā)錯誤。

從上述分類中可以看到，一種編碼可以具有多樣性。本章主要介紹糾正隨機錯誤的二進制線性分組碼。

8.4檢錯和糾錯原理

在討論檢錯和糾錯問題之前，我們先介紹一下數(shù)字通信中碼元的兩種錯誤形式：隨機錯誤和突發(fā)錯誤。

（1）隨機錯誤：由隨機噪聲引起的碼元錯誤。其特點是碼元中任意一位或幾位發(fā)生從0變1或從1變0的錯誤是相互獨立的，彼此之間沒有聯(lián)系，一般不會引起成片的碼元錯誤。

圖8-5通信差錯分類及其表示（2）突發(fā)錯誤：由突發(fā)噪聲引起的碼元錯誤，比如閃電、電器開關(guān)的瞬態(tài)、磁帶缺陷等都屬于突發(fā)噪聲。該錯誤的特點是各錯誤碼元之間存在相關(guān)性，因此是成片出現(xiàn)的，也就是說，突發(fā)錯誤是一個錯誤序列，該序列的首部和尾部碼元都是錯的，中間的碼元有錯的也有對的，但錯的碼元相對較多。錯誤序列的長度（包括首和尾在內(nèi)的錯誤所波及的段落長度）稱為突發(fā)長度。

根據(jù)前面給出的基本概念我們知道，必須在信息碼序列中加入監(jiān)督碼元才能完成檢錯和糾錯功能，其前提是監(jiān)督碼元要與信息碼之間有一種特殊的關(guān)系。下面我們從一個簡單的例子出發(fā)，詳細介紹檢錯和糾錯的基本原理。

假設要發(fā)送一組具有四個狀態(tài)的數(shù)據(jù)信息（比如一個電壓信號的四個值，1V、2V、3V、4V）。我們首先要用二進制碼對數(shù)據(jù)信息進行編碼，顯然，用2位二進制碼就可完成，其編碼表如表8－1所示。

表8－1

2位編碼表假設不經(jīng)信道編碼，在信道中直接傳輸按表中編碼規(guī)則得到的0、1數(shù)字序列，則在理想情況下，接收端收到00就認為是1V，收到10就是3V，如此可完全了解發(fā)送端傳過來的信息。而在實際通信中由于干擾（噪聲）的影響，會使信息碼元發(fā)生錯誤從而出現(xiàn)誤碼（比如碼組00變成10、01或11）。從上表可見，任何一組碼不管是一位還是兩位發(fā)生錯誤，都會使該碼組變成另外一組信息碼，從而引起信息傳輸錯誤。因此，以這種編碼形式得到的數(shù)字信號在傳輸過程中不具備檢錯和糾錯的能力，這是我們所不希望的。該例中問題的關(guān)鍵是2位二進制碼的全部組合都是信息碼組或稱許用碼組，任何一位（或兩位）發(fā)生錯誤都會引起歧義。為了克服這一缺點，我們在每組碼后面再加1位碼元，使2位碼組變成3位碼組。這樣，在3位碼組的8種組合中只有4組是許用碼組，而其余4種被稱為禁用碼組，編碼表變成表8－2。

在許用碼組000、011、101、110中，右邊加上的1位碼元就是監(jiān)督碼元，它的加入原則是使碼組中1的個數(shù)為偶數(shù)，這樣監(jiān)督碼元就和前面2位信息碼元發(fā)生了關(guān)系。這種編碼方式稱為偶校驗（EvenParity）；反之，如果加入原則是使碼組中1的個數(shù)為奇數(shù)，則編碼方式稱為奇校驗（OddParity）。現(xiàn)在我們再看一下出現(xiàn)誤碼的情況，假設許用碼組000出現(xiàn)1位誤碼，即變成001、010或100三個碼組中的一個，可見這三個碼組中1的個數(shù)都是奇數(shù)，是禁用碼組。因此，當收信端收到這三個碼組中的任何一個時，就知道是誤碼。用這種方法可以發(fā)現(xiàn)1位或3位出現(xiàn)錯誤的碼組，而無法檢出2位錯誤，因為一個碼組出現(xiàn)2位錯誤，其奇偶性不變。那么，收信端能否從誤碼中判斷哪一位發(fā)生錯誤了呢（即糾正錯誤）？比如對誤碼001而言，如果是1位發(fā)生錯誤，原碼可能是000、101或011；如果3位都錯，原碼就是110，而我們現(xiàn)在無法判斷出原碼到底是哪一組。也就是說，通過增加一位監(jiān)督碼元，我們可以檢出1位或3位錯誤（3位出錯的概率極?。?，但無法糾正錯誤。

我們能否通過增加監(jiān)督碼元的位數(shù)來增加檢錯位數(shù)或?qū)崿F(xiàn)糾錯功能呢？比如我們在表8－2中再加1位監(jiān)督碼元變成4位編碼（見表8－3），看看情況如何。

表8－3

4位編碼表

編碼原則仍然是偶校驗。顯然，檢錯1位和3位沒問題，但檢錯2位還不行（比如0000變成1100，而1100是許用碼組）。設誤碼為1110，則可能的原碼為0110、1010、1100、1111四個（還按1位誤碼考慮），而0110、1010、1100都是許用碼組，所以無法糾錯。必須注意，這里的糾錯是對所有許用碼組而言的，部分許用碼組能夠糾錯還不能稱之為能夠糾錯，比如，誤碼0001的可能原碼有0000、0011、0101、1001，其中0011、0101和1001都是禁用碼組，所以原碼只能是0000，可見對0001可以糾錯，但我們不能說這種編碼方式可以糾正一位錯誤（因為不能對全部許用碼組糾錯）?？梢姡唵蔚卦黾右晃槐O(jiān)督碼元并沒有提高檢錯與糾錯能力。那么，檢錯與糾錯能力到底與什么有關(guān)呢？在回答這個問題之前，我們先介紹兩個新概念——碼元的漢明（Hamming）距離和碼元的漢明重量。

所謂碼元的漢明距離，就是兩個碼組中對應碼位上碼元不同的個數(shù)，簡稱碼距（也稱漢明距）。碼距反映的是碼組之間的差異程度。比如，00和01兩組碼的碼距為1，011和100的碼距為3。那么，多個碼組之間相互比較，可能會有不同的碼距，其中的最小值被稱為最小碼距（用dmin表示）。比如，000、001、110三個碼組相比較，碼距有1和2兩個值，則最小碼距為1；表8－3中的4個許用碼組的最小碼距為2。

有分析表明，一種編碼方式的檢錯和糾錯能力與許用碼組中的最小碼距有關(guān)。比如，表8－3中8個碼組的最小碼距為1，若這8個碼組都作為許用碼組，則沒有檢錯能力，更不用說糾錯了；若我們選取其中四個作為許用碼組，則最小碼距為2，可以檢出1位或3位錯誤；如果只選兩組000和111為許用碼組時，其最小碼距為3，那么就可以發(fā)現(xiàn)所有2位以下的錯誤，若用來糾錯，則可糾正1位錯誤。根據(jù)理論推導，可以得出以下結(jié)論：

(1)在一個碼組內(nèi)要想檢出e位誤碼，要求最小碼距為

（8.4－1）

(2)在一個碼組內(nèi)要想糾正t位誤碼，要求最小碼距為

（8.4－2）

(3)在一個碼組內(nèi)要想糾正t位誤碼，同時檢測出e位誤碼（e＞t），要求最小碼距為

（8.4－3）

假如有碼組0000和1111，其碼距為4。對式（8.4－1）可以這樣理解：若原碼為0000，接收碼為0001、0011或0111，顯然可以斷定接收碼出現(xiàn)1位、2位和3位錯誤，即若只用于檢錯，碼距為4的碼組可檢測出3位錯誤；同樣的情況，用式（8.4－2）可以發(fā)現(xiàn)0001是錯碼，并可認定原碼為0000。但對0011不能糾正，因為無法斷定原碼是0000還是1111。而對0111，只能認定是1位錯誤，原碼為1111。所以，式（8.4－2）只能糾正1位錯誤。所謂能糾正t位誤碼，同時檢測出e位誤碼，是指當錯碼不超過t位時，錯碼能夠自動糾正，當錯碼超過t位時，則不能糾正錯誤，但仍可檢測出e位誤碼，這正是混和檢錯糾錯的控制方式。如上述碼組按式（8.4－3）可知，能夠糾正1位錯誤，若收到0100，則可自動將1變?yōu)?；若收到1100時，則無法糾正，但仍可發(fā)現(xiàn)有2位錯誤，若收到1101，則只能按1位錯誤糾正為1111，而不能判定為3位錯誤糾正為0000。

有了上述結(jié)論，我們就知道表8－2和表8－3中的編碼檢錯和糾錯能力之所以一樣，是因為它們的最小碼距都是2。

顯然，要提高編碼的糾、檢錯能力，不能僅靠簡單地增加監(jiān)督碼元位數(shù)（即冗余度），更重要的是要加大最小碼距（即碼組之間的差異程度）。而最小碼距的大小與編碼的冗余度是有關(guān)的，最小碼距增大，碼元的冗余度就增大，但碼元的冗余度增大，最小碼距不一定增大。因此，一種編碼方式具有檢錯和糾錯能力的必要條件是信息編碼必須有冗余，而充分條件是碼元之間要有一定的碼距。另外，檢錯要求的冗余度比糾錯要低。

在把k位信息碼編制成n位差錯控制碼的過程中，我們把信息碼的位數(shù)k與差錯控制碼的位數(shù)n之比定義為編碼效率，用Rc表示，即

因為k<n，所以Rc<1。顯然，編碼的冗余度越大，編碼效率越低，也就是說，通信系統(tǒng)可靠性的提高，是以降低有效性（即編碼效率）來換取的。差錯控制編碼的關(guān)鍵技術(shù)（也是努力方向）就是尋找一種好的編碼方法，在一定的差錯控制能力要求下，使得編碼效率盡可能地高，同時譯碼方法盡可能地簡單。

碼元的漢明重量簡稱碼重，被定義為一個碼字中非零碼元的個數(shù)。比如，碼字100110的碼重為3，0110的碼重是2。它反映一個碼字中“1”和“0”的“比重”。(8.4-4) 8.5幾種常用的檢錯碼

8.5.1奇偶校驗碼

奇偶校驗碼是數(shù)據(jù)通信中最常見的一種簡單檢錯碼，其編碼規(guī)則是：把信息碼先分組，形成多個許用碼組，在每一個許用碼組最后（最低位）加上一位監(jiān)督碼元即可。加上監(jiān)督碼元后使該碼組中1的數(shù)目為奇數(shù)的編碼稱為奇校驗碼，為偶數(shù)的編碼稱為偶校驗碼。根據(jù)編碼分類，可知奇偶校驗碼屬于一種檢錯、線性、分組系統(tǒng)碼。

奇偶校驗碼的監(jiān)督關(guān)系可以用以下公式進行表述。假設一個碼組的長度為n(在計算機通信中常為一個字節(jié))，表示為an-1an-2an-3…a0，其中前n-1位是信息碼，最后一位a0為校驗位，那么，偶校驗碼必須保證

監(jiān)督碼元a0的取值（0或1）可由下式?jīng)Q定：

對于偶校驗碼必須保證監(jiān)督碼元a0的取值（0或1）可由下式?jīng)Q定：

根據(jù)奇偶校驗的規(guī)則我們可以看到，當碼組中的誤碼為偶數(shù)時，校驗失效。比如有兩位發(fā)生錯誤，則會有這樣幾種情況：00變成11、11變成00、01變成10、10變成01?？梢姡瑹o論哪種情況出現(xiàn)，都不會改變碼組的奇偶性，偶校驗碼中1的個數(shù)仍為偶數(shù)，奇校驗碼中1的個數(shù)仍為奇數(shù)。所以，簡單的奇偶校驗碼只能檢測出奇數(shù)個位發(fā)生錯誤的碼組。

8.5.2水平奇偶校驗碼

為克服上述簡單奇偶校驗碼檢錯能力不高且不能檢測突發(fā)錯誤的缺點，我們可以將經(jīng)過簡單奇偶校驗編碼的碼組按行排列成方陣，每一行是一個碼組，若有n個碼組則方陣就有n。比如，有經(jīng)過奇偶校驗編碼的7個碼組01011011001、01010100100、00110000110、11000111001、00111111110、00010011111、11101100001排成方陣共有7行（見表8－4）。如果傳輸時按碼組逐行傳輸?shù)脑?，則與簡單奇偶校驗碼沒有區(qū)別。但若發(fā)信端按列進行傳輸，即000100110010110010101…1001011（如表中箭頭所示），接收端按列接收后再按行還原成發(fā)送端的方陣，然后按行進行奇偶校驗，則糾錯情況就會發(fā)生變化。觀察該表可見，因為是逐列發(fā)送，在一列中不管出現(xiàn)幾個誤碼（偶數(shù)個或奇數(shù)個），對應在每一行都只是一位誤碼，所以都可以通過水平奇偶校驗檢驗出來；但對于每一行（一個碼組）而言，仍然只能檢出所有奇數(shù)個錯誤。與簡單奇偶校驗編碼相比，這種方法的最大優(yōu)點是可以檢出所有長度小于行數(shù)（碼組數(shù)）的突發(fā)錯誤。

表8－4水平偶校驗碼

8.5.3二維奇偶校驗碼

在上述水平奇偶校驗編碼的基礎上，若再加上垂直奇偶校驗編碼就構(gòu)成二維奇偶校驗碼。比如對表8－4的7個碼組再加上一行就構(gòu)成二維偶校驗碼，如表8－5所示。

二維奇偶校驗碼在發(fā)送時仍按列發(fā)送（如箭頭所示），接收端順序接收后仍還原成表8－5所示的方陣形式。二維奇偶校驗碼比一維奇偶校驗碼多了個列校驗，因此，其檢錯能力有所提高，除了可檢出行中的所有奇數(shù)個誤碼及長度不大于行數(shù)的突發(fā)性錯誤外，還可檢出列中的所有奇數(shù)個誤碼及長度不大于列數(shù)的突發(fā)性錯誤，同時還能檢出碼組中大多數(shù)出現(xiàn)偶數(shù)個錯誤的情況。比如，在碼組1中頭兩位發(fā)生錯誤，從01變成10，則第1列的1就變成3個，第2列的1也變成3個，而兩列的校驗碼元都是0，所以可以查出這兩列有錯誤，也就是說，碼組中出現(xiàn)了2位（偶數(shù)位）誤碼，但具體是哪一個碼組（那一行）出現(xiàn)誤碼還無法判斷。

表8－5二維偶校驗碼

8.5.4群計數(shù)碼

在奇偶校驗碼中，我們通過添加監(jiān)督位將碼組的碼重配成奇數(shù)或偶數(shù)。而群計數(shù)碼的編碼原則是先算出信息碼組的碼重（碼組中“1”的個數(shù)），然后用二進制計數(shù)法將碼重作為監(jiān)督碼元添加到信息碼組的后面。比如表8－4中的7個信息碼組變成群計數(shù)碼后的形式見表8－6。

表8－6群計數(shù)碼

這種碼屬于非線性分組系統(tǒng)碼，其檢錯能力很強，除了能檢出碼組中奇數(shù)個錯誤之外，還能檢出偶數(shù)個0變1或1變0的錯誤，但對1變0和0變1成對出現(xiàn)的誤碼無能為力?？梢则炞C，除了無法檢出1變0和0變1成對出現(xiàn)的誤碼外，這種碼可以檢出其他所有形式的錯誤。

8.5.5恒比碼

恒比碼的編碼原則是從確定碼長的碼字中挑選那些“1”和“0”個數(shù)的比值一樣的碼字作為許用碼字。

這種碼通過計算接收碼組中1的個數(shù)目是否正確，就可檢測出有無錯誤。表8－7是我國郵電部門在國內(nèi)通信中采用的五單位數(shù)字保護電碼，它是一種5中取3的恒比碼。每個碼組的長度為5，其中1的個數(shù)為3，每個許用碼組中1和0個數(shù)的比值恒為3/2。許用碼組的個數(shù)就是5中取3的組合數(shù)，即C35=5!(3!2!)=10，正好可以表示10個阿拉伯數(shù)字。

表8－7五單位保護電碼表

8.6線性分組碼

對于信源輸出的2k個離散消息，信源編碼器可以用k位二進制碼對它們進行編碼，形成2k個具有k位碼元的碼字（碼組），這些碼字被稱為信息碼字，我們用矩陣D表示。

若在每個k位信息碼字后面添加m位碼元，就會形成2k

個n位碼字（n=k+m）。而添加的m個碼元不攜帶將要傳送的信息，這些碼元被稱為監(jiān)督碼元或校驗碼元。因此，把這種對每個信息碼字附加若干位監(jiān)督碼元的編碼方法所得到的碼字集合稱為分組碼，常用矩陣C表示。顯然，如果上述分組碼每個碼字之間沒有關(guān)系的話（彼此獨立或線性無關(guān)），則對于大的k值或n值（信息碼或分組碼的碼長很大），編碼設備會極為復雜，因為編碼設備必須儲存2k個碼長為n的碼字。因此，我們需要構(gòu)造碼字之間有某種關(guān)系的分組碼，以降低編碼的復雜性。線性分組碼就是滿足這一條件的一種分組碼。

如果分組碼中的信息碼元和監(jiān)督碼元滿足一組線性方程的話，則稱其為線性分組碼。否則，即為非線性分組碼。通常，把長度為n，有2k個碼字的線性分組碼稱為線性（n，k）碼或（n，k）線性碼。線性分組碼有兩個重要性質(zhì)：

（1）封閉性。即任意兩個許用碼字之模2加仍為一個許用碼字，這個性質(zhì)隱含著線性分組碼必須包含全零碼字這一結(jié)論。

（2）碼字的最小碼距等于非零碼的最小碼重。利用這一性質(zhì)，我們可以迅速方便地找出一種線性分組碼的最小碼距，從而判斷該碼的檢/糾錯能力。線性分組碼有兩個重要性質(zhì)：

（1）封閉性。即任意兩個許用碼字之模2加仍為一個許用碼字，這個性質(zhì)隱含著線性分組碼必須包含全零碼字這一結(jié)論。

（2）碼字的最小碼距等于非零碼的最小碼重。利用這一性質(zhì)，我們可以迅速方便地找出一種線性分組碼的最小碼距，從而判斷該碼的檢/糾錯能力。

在（n，k）碼中，雖然有2k個碼字，但因為有了線性條件，2k個碼字中只有k個獨立，其余的都可以通過這k個獨立的碼字線性組合而成（模2加），所以，編碼設備不再需要儲存2k個碼長為n的碼字，而只需保存k個線性無關(guān)的碼字即可。

設有一（n，k）線性分組碼，即c1,c2,…，cn；其中信息碼字為d1，d2,…，dk，線性分組碼格式如圖8-6所示。具有這種結(jié)構(gòu)的線性分組碼又叫做線性分組系統(tǒng)碼。圖8－6線性分組碼格式

相應的分組碼碼組行向量和信息碼組行向量為

則一個分組碼組的前k位是信息碼元，后n-k位是監(jiān)督碼元（設監(jiān)督碼元位數(shù)為m，則有m=n-k），每一個分組碼組可以由信息碼元線性組合而成，即（8.6－1）

（8.6－2）

c1=d1

c2=d2

c3=d3

┆

ck=dk

ck+1=h11d1⊕h12d2⊕…⊕h1kdk

ck+2=h21d1⊕h22d2⊕…⊕h2kdk

┆

cn=hm1d1⊕hm2d2⊕…⊕hmkdk

式中hij是二進制常數(shù)，值為0或1；hmidi表示模2乘，也可表示為hm⊙idi。其運算規(guī)則是：1⊙0=0⊙1=0⊙0=0；1⊙1=1?？梢姡诰€性分組碼中，信息碼元和監(jiān)督碼元可以用線性方程聯(lián)系起來。上述各式描述一個分組碼碼組與一個信息碼碼組之間的關(guān)系。

將上述C與D的n個關(guān)系式用矩陣表示為

式中，G稱為生成矩陣，是一個k×n階矩陣，具體形式為

即

C=D·G

（8.6-3）

該矩陣又可分解為兩個子矩陣：

其中，Ik是k×k階單位陣；P為k×m階矩陣，即(8.6-4)這樣，分組碼C又可表示為

C=D[IkP]（8.6-5）

需要說明的是，上述各式中的C和D可以是由一個碼組構(gòu)成的一個行向量，也可以是由2k個行向量構(gòu)成的2k×n階分組碼矩陣或2k×k階信息碼矩陣。

式（8.6－3）說明，（n，k）線性碼完全由生成矩陣G的k行元素決定，即任意一個分組碼碼組都是G的線性組合。而（n，k）線性碼中的任何k個線性無關(guān)的碼組都可用來構(gòu)成生成矩陣，所以，生成矩陣G的各行都線性無關(guān)，如果各行之間有線性相關(guān)的，就不可能由G生成2k個不同的碼組了。其實，G的各行本身就是一個碼組，如果已有k個線性無關(guān)的碼組，則可用其直接構(gòu)成G矩陣，并由此生成其余碼字。

用能夠分塊為Ik和Q的生成矩陣G產(chǎn)生的線性分組碼就是系統(tǒng)碼，其特征是前k位元素與信息碼完全相同。不能分塊的生成矩陣G所產(chǎn)生的線性分組碼就是非系統(tǒng)碼。

系統(tǒng)碼的編碼器只需存儲k×m個元素（非系統(tǒng)碼要存儲k×n個），就可根據(jù)信息向量（矩陣）構(gòu)造出相應的分組碼碼字（或分組碼矩陣），從而降低了編碼的復雜性，并提高了編碼效率。

由于系統(tǒng)碼的編/譯碼器比較簡單，且檢、糾錯性能與非系統(tǒng)碼相同，因此，以下只討論系統(tǒng)碼的相關(guān)問題。例題8－1

給定一個（7，4）線性分組碼的生成矩陣

若信息碼D=［1101］，求該信息碼的線性分組編碼C。解根據(jù)式（8.6－3）可得

即對信息碼［1101］的線性分組編碼為［1101000］。注意在矩陣乘法中，是模2乘和模2加。

上式也可寫成

由以上討論可知，編碼前的信息碼組共有2k種組合，而編碼后的碼組在k位信息碼元之外還附加了m位校驗碼元，共有2n種組合，顯然，2n>2k，這就是說C與D的關(guān)系不唯一。因此，選擇適當?shù)木仃嘝，就可得到既具有較強的檢錯或糾錯能力，實現(xiàn)方法又比較簡單且編碼效率較高的一種線性分組碼。目前已經(jīng)找到不少性能較好的矩陣P。

例題8－2已知線性（6，3）碼的生成矩陣為

求兩組線性分組碼及差錯控制能力。

解因為k=3，所以信息碼碼組矩陣（8×3階）為則由式（8-6）可得出分組碼碼字矩陣分別為下面我們簡要介紹譯碼原理。

從式（8.6－4）可得

C=D[IkP]=[DDP]=[DCm]（8.6-6）

Cm=DQ

（8.6-7）式中，Cm是k×m階監(jiān)督碼元矩陣。式（8.6-7）兩邊模2加Cm，可得DQ⊕Cm=0，該式可變?yōu)榫仃囅喑诵问?，即?.6－8）

令其中QT是m×k階矩陣，可用P表示，即則有（8.6－9）

（8.6－10）

通常，把H稱為一致校驗矩陣或一致監(jiān)督矩陣。具有[P

Im]形式的H矩陣稱為典型形式的監(jiān)督矩陣。由典型形式的監(jiān)督矩陣及信息碼元很容易算出各監(jiān)督碼元。CHT=0 （8.6-11）

該式說明任何碼組和校驗矩陣H的轉(zhuǎn)置相乘，其結(jié)果為m位零向量，因此，用校驗矩陣檢查二元序列是不是碼組非常方便，“校驗”之名由此而來?？梢酝茖С鲂ｒ灳仃嘓與生成矩陣G滿足

GHT=HGT=0（8.6－12）

將式（8.6-6）和HT代入式（8.6-8）可得

設行向量R=[r1，r2，…，rn]是收信端通過信道收到的碼組。由于信道干擾會產(chǎn)生誤碼，接收向量R和發(fā)送向量C就會有差別，我們用向量E=[e1，e2，…，en]表示這種差別。由此定義三者之間的關(guān)系為：

E=R+C （8.6-13）

這里的“+”號仍為模2加。若R中的某一位ri與C中的相同位ci一樣時，E中的ei=0；若不同（即出現(xiàn)誤碼），則ei=1?？梢娤蛄縀能夠反映誤碼狀況，因此，稱之為錯誤向量或錯誤圖樣。比如，發(fā)送向量C=[11011001]，而接收向量R=[10001011]，顯然，R中有3個錯誤，由式（8.6-10）可得錯誤圖樣E=[01010010]?？梢?，E的碼重就是誤碼的個數(shù)，因此E的碼重越小越好。

式（8.6－13）也可寫為

R=E+C

（8.6－14）

定義矩陣S為伴隨式

S=RHT

（8.6－15）

則由式（8.6－8）、（8.6－11）和（8.6－12）得

S=（E+C）HT=EHT+CHT=EHT

（8.6－16）

圖8-7線性分組碼編碼與譯碼示意圖 8.7循環(huán)碼

循環(huán)碼是線性分組碼的一個重要分支。循環(huán)碼有許多特殊的代數(shù)性質(zhì)，基于這些性質(zhì)，循環(huán)碼有較強的糾錯能力，而且其編碼和譯碼電路很容易用移位寄存器實現(xiàn)，因而在FEC系統(tǒng)中得到了廣泛的應用。

循環(huán)碼可定義為：對于一個（n，k）線性碼C，若其中的任一碼組向左或向右循環(huán)移動任意位后仍是C中的一個碼組，則稱C是一個循環(huán)碼。循環(huán)碼是一種分組碼，前k位為信息碼元，后r位為監(jiān)督碼元。它除了具有線性分組碼的封閉性之外，還具有一個獨特的性質(zhì)即循環(huán)性。循環(huán)性指的是任一許用碼組經(jīng)過循環(huán)移位后所得到的碼組仍為一許用碼組。若C=[c1，c2，…，cn]是一個循環(huán)碼組，對它左循環(huán)移位一次，得到C（1）=[c2，c3，…，cn，c1]也是許用碼組，移位i次得到C(i)=[ci+1，ci+2，…，cn，c1，ci]也是許用碼組。不論右移或左移，移位位數(shù)多少，其結(jié)果均為循環(huán)碼組。

在代數(shù)編碼理論中，可以把循環(huán)碼組中各碼元當作一個多項式的系數(shù)，即把一個長為n的碼組表示為

c(x)=c1xn-1+c2xn-2+…+cn

式中，c(x)稱為碼多項式；變量x稱為元素，其冪次對應元素的位置，它的系數(shù)即為元數(shù)的取值（我們不關(guān)心x本身的取值），系數(shù)之間的加法和乘法仍服從模2規(guī)則。比如一個（7，3）循環(huán)碼（見表8－9）中第7個碼組為（1100101），則該碼組可表示為

c7(x)=1·x6+1·x5+0·x4+0·x3+1·x2+0·x+1

=x6+x5+x2+1表8－8（7，3）循環(huán)碼的全部碼組

表8－9（7，4）循環(huán)碼碼組

從表8－9中可見，對于16組信息，系統(tǒng)碼和非系統(tǒng)碼都具有16個相同的編碼碼組，但與信息碼的對應（映射）關(guān)系不一樣。系統(tǒng)碼的前4位對應的都是信息碼，而后3位都是監(jiān)督碼元，二者涇渭分明。而非系統(tǒng)碼從第5組開始就“亂”了，雖然每組信息碼仍有一個確定的編碼碼組與之對應，但已經(jīng)沒有了系統(tǒng)碼那種涇渭分明的結(jié)構(gòu)。由于一般我們只研究系統(tǒng)碼，因此有些書上直接說循環(huán)碼是一種系統(tǒng)碼。另外，還需說明的是，對于一個（n，k）線性碼C，根據(jù)不同的方法（生成矩陣）可以有多種編碼形式，其中包含系統(tǒng)碼和非系統(tǒng)碼，但系統(tǒng)碼是唯一的，其余的都是非系統(tǒng)碼。

通過上述介紹，我們簡要地了解了數(shù)字（數(shù)據(jù)）通信中信道編碼的基本概念和常用的檢錯、糾錯編碼，但限于篇幅，還有很多內(nèi)容沒有涉及。為了使讀者對編碼有一個全面、系統(tǒng)的認識，我們給出編碼所研究的以下主要問題：

（1）根據(jù)實際通信系統(tǒng)對糾錯能力的要求，尋找合適的碼型（通常是一種長碼型）。要求該碼型可以在數(shù)學上證明具有滿足要求的糾錯能力，并具有數(shù)學結(jié)構(gòu)，且能夠根據(jù)此結(jié)構(gòu)用一些設備實現(xiàn)編碼和譯碼。

（2）尋找實用的編碼方法，盡量提高編碼效率。

（3）尋找實用的譯碼方法