通信原理課件-第十章

第10章差錯(cuò)控制編碼7.1概述7.2常用的幾種簡(jiǎn)單分組碼7.3線性分組碼7.4循環(huán)碼1第10章差錯(cuò)控制編碼7.1概述1

10.1概述

在數(shù)字信號(hào)傳輸中，由于信道不理想以及加性噪聲的影響，被傳輸?shù)男盘?hào)碼元波形會(huì)變壞，造成接收端錯(cuò)誤判決。為了盡量減小數(shù)字通信中信息碼元的差錯(cuò)概率，應(yīng)合理設(shè)計(jì)基帶信號(hào)并采用均衡技術(shù)以減小信道線性畸變引起的碼間干擾；對(duì)于由信道噪聲引起的加性干擾，應(yīng)考慮采取加大發(fā)送功率、適當(dāng)選擇調(diào)制解調(diào)方式等措施。但是隨著現(xiàn)代數(shù)字通信技術(shù)的不斷發(fā)展，以及傳輸速率的不斷提高，對(duì)信息碼元的差錯(cuò)概率Pe的要求也在提高，例如計(jì)算機(jī)間的數(shù)據(jù)傳輸，要求Pe低于10-9，并且信道帶寬和發(fā)送功率受到限制，此時(shí)就需要采用信道編碼，又稱為差錯(cuò)控制編碼。2

10.1概述2

信道編碼理論建立在香農(nóng)信息論的基礎(chǔ)上，其實(shí)質(zhì)是給信息碼元增加冗余度，即增加一定數(shù)量的多余碼元(稱為監(jiān)督碼元或校驗(yàn)碼元)，由信息碼元和監(jiān)督碼元共同組成一個(gè)碼字，兩者間滿足一定的約束關(guān)系。如果在傳輸過程中受到干擾，某位碼元發(fā)生了變化，就破壞了它們之間的約束關(guān)系。接收端通過檢驗(yàn)約束關(guān)系是否成立，完成識(shí)別錯(cuò)誤或者進(jìn)一步判定錯(cuò)誤位置并糾正錯(cuò)誤，從而提高通信的可靠性。3信道編碼理論建立在香農(nóng)信息論的基礎(chǔ)上

10.2差錯(cuò)控制編碼的基本概念

10.2.1差錯(cuò)控制方式

在差錯(cuò)控制系統(tǒng)中，差錯(cuò)控制方式主要有三種。

1.前向糾錯(cuò)控制方式(FEC)

又稱自動(dòng)糾錯(cuò)，是指發(fā)送端發(fā)出的可以糾正錯(cuò)誤碼元的編碼序列，接收端的譯碼器能自動(dòng)糾正傳輸中的錯(cuò)碼，系統(tǒng)框圖如圖10.2.1(a)所示。這種方式的優(yōu)點(diǎn)是不需要反饋信道，譯碼實(shí)時(shí)性好，具有恒定的信息傳輸速率。缺點(diǎn)是為了要獲得比較低的誤碼率，必須以最壞的信道條件來設(shè)計(jì)糾錯(cuò)碼，故需要附加較多的監(jiān)督碼元，這樣既增加了譯碼算法選擇的難度，也降低了系統(tǒng)的傳輸效率，所以不適宜應(yīng)用在傳輸條件惡化的信道。

4

10.2差錯(cuò)控制編碼的基本概念10.

2.反饋重發(fā)糾錯(cuò)方式(ARQ)

發(fā)送端發(fā)出的是能夠檢測(cè)錯(cuò)誤的編碼序列，接收端譯碼器根據(jù)編碼規(guī)則進(jìn)行判決，并通過反饋信道把判決結(jié)果回傳，無錯(cuò)認(rèn)可(ACK)，有錯(cuò)時(shí)否認(rèn)(NAK)。發(fā)送端根據(jù)回傳指令，將有錯(cuò)的碼組重發(fā)，直到接收端認(rèn)為正確接收為止，系統(tǒng)框圖如圖10.2.1(b)所示。

優(yōu)點(diǎn)：檢錯(cuò)碼構(gòu)造簡(jiǎn)單，不需要復(fù)雜的編譯碼設(shè)備，在冗余度一定的條件下，檢錯(cuò)碼的檢錯(cuò)能力比糾錯(cuò)碼的糾錯(cuò)能力強(qiáng)得多，故整個(gè)系統(tǒng)的誤碼率可以保持在極低的數(shù)量級(jí)上。

缺點(diǎn)：需要反饋信道，并要求發(fā)送端有大容量的信源存儲(chǔ)器，且為保證收、發(fā)兩端互相配合，控制電路較為復(fù)雜。另外，當(dāng)信道干擾很頻繁時(shí)，系統(tǒng)經(jīng)常處于重發(fā)消息的狀態(tài)，使傳送信息的實(shí)時(shí)性變差。55

3．混合糾錯(cuò)方式(HEC)

該方式是上述兩種方式的結(jié)合，即在ARQ系統(tǒng)中包含一個(gè)FEC子系統(tǒng)，系統(tǒng)框圖如圖10.2.1(c)所示。發(fā)送端發(fā)出的是具有一定糾錯(cuò)能力和較強(qiáng)檢錯(cuò)能力的碼，所以經(jīng)信道編碼而附加的監(jiān)督碼元并不多。接收端檢測(cè)數(shù)據(jù)碼流，發(fā)現(xiàn)錯(cuò)誤先由FEC子系統(tǒng)自動(dòng)糾錯(cuò)，僅當(dāng)錯(cuò)誤較多超出糾錯(cuò)能力時(shí)，再發(fā)反饋信息要求重發(fā)，因此大大減少了重發(fā)次數(shù)。HEC在一定程度上彌補(bǔ)了反饋重發(fā)和前向糾錯(cuò)兩種方式的缺點(diǎn)，充分發(fā)揮了碼的檢、糾錯(cuò)能力，在較強(qiáng)干擾的信道中仍可獲得較低誤碼率，是實(shí)際通信中應(yīng)用較多的糾錯(cuò)方式。63．混合糾錯(cuò)方式(HEC)677

10.2.2差錯(cuò)控制編碼的分類

用不同的方法可以對(duì)差錯(cuò)控制編碼進(jìn)行不同的分類。1.根據(jù)已編碼組中信息碼元與監(jiān)督碼元之間的函數(shù)關(guān)系，可分為線性碼及非線性碼。若信息碼元與監(jiān)督碼元之間的關(guān)系呈線性，即滿足一組線性方程式，則稱為線性碼。否則稱為非線性碼。

810.2.2差錯(cuò)控制編碼的分類8

2.根據(jù)信息碼元和監(jiān)督碼元之間的約束方式不同，可分為分組碼和卷積碼。分組碼的監(jiān)督碼元僅與本碼組的信息碼元有關(guān)，卷積碼的監(jiān)督碼元不僅與本組信息碼元有關(guān)，而且與前面若干碼組的信息碼元有約束關(guān)系。

3.根據(jù)編碼后信息碼元是否保持原來的形式，可分為系統(tǒng)碼和非系統(tǒng)碼。在系統(tǒng)碼中，編碼后的信息碼元保持原樣，而非系統(tǒng)碼中的信息碼元?jiǎng)t改變了原來的信號(hào)形式。92.根據(jù)信息碼元和監(jiān)督碼元之間的約

4.根據(jù)編碼的不同功能，可分為檢錯(cuò)碼、糾錯(cuò)碼和糾刪碼。檢錯(cuò)碼只能夠發(fā)現(xiàn)錯(cuò)誤，但不能糾正錯(cuò)誤；糾錯(cuò)碼能夠糾正錯(cuò)誤；糾刪碼即可以檢錯(cuò)又可以糾錯(cuò)，但糾錯(cuò)能力有限，當(dāng)有不能糾正的錯(cuò)誤時(shí)將發(fā)出錯(cuò)誤指示或刪除不可糾正的錯(cuò)誤段落。

5.根據(jù)糾正、檢驗(yàn)錯(cuò)誤的類型不同，可分為糾正、檢驗(yàn)隨機(jī)性錯(cuò)誤的碼和糾正、檢驗(yàn)突發(fā)性錯(cuò)誤的碼。

6.根據(jù)碼元取值的不同，可分為二進(jìn)制碼和多進(jìn)制碼。這里只介紹二進(jìn)制糾、檢錯(cuò)編碼。104.根據(jù)編碼的不同功能，可分為檢錯(cuò)碼

10.2.3檢錯(cuò)和糾錯(cuò)的基本原理差錯(cuò)控制編碼的基本思想是在被傳輸?shù)男畔⒋a元中附加一些監(jiān)督碼元，并且使它們之間確定某一種關(guān)系，根據(jù)傳輸過程中這種關(guān)系是否被破壞來發(fā)現(xiàn)或糾正錯(cuò)誤?？梢娺@種差錯(cuò)控制能力是用增加信息量的冗余度來換取的。

設(shè)編碼后的碼組長度、碼組中所含信息碼元個(gè)數(shù)以及監(jiān)督碼元個(gè)數(shù)分別為n、k和r，三者間滿足n=k+r，定義編碼效率為R=k/n=1-r/n?？梢姶a組長度一定時(shí)，所加入的監(jiān)督碼元個(gè)數(shù)越多，編碼效率越低。1110.2.3檢錯(cuò)和糾錯(cuò)的基本原理

香農(nóng)的信道編碼定理指出:對(duì)于一個(gè)給定的有擾信道，若信道容量為C，只要發(fā)送端以低于C的速率R發(fā)送信息（R為編碼器的輸入二進(jìn)制碼元速率），則一定存在一種編碼方法，使編碼錯(cuò)誤概率P隨著碼長n的增加，按指數(shù)下降到任意小的值。可以表示為其中E(R)稱為誤差指數(shù)，它與R和C的關(guān)系如圖10.2.2所示。(10.2.1)12香農(nóng)的信道編碼定理指出:(10.21313

由定理有如下結(jié)論:1.在碼長及發(fā)送信息速率一定的情況下，為減小P可以增大信道容量。由圖10.2.2可知，E(R)隨信道容量的增加而增大。由式(10.2.1)可知，錯(cuò)誤概率隨E(R)的增大而指數(shù)下降。2.在信道容量及發(fā)送信息速率一定的條件下，增加碼長，可以使錯(cuò)誤概率指數(shù)下降。對(duì)于實(shí)際應(yīng)用來說，此時(shí)的設(shè)備復(fù)雜性和譯碼延時(shí)也隨之增加。14由定理有如下結(jié)論:14

香農(nóng)的信道編碼定理為信道編碼奠定了理論基礎(chǔ)，雖然定理本身并沒有給出具體的差錯(cuò)控制編碼方法和糾錯(cuò)碼的結(jié)構(gòu)，但它從理論上為信道編碼的發(fā)展指出了努力方向。

我們用3位二進(jìn)制碼組來說明檢錯(cuò)糾錯(cuò)的基本原理。3位二進(jìn)制碼元共有8種可能的組合:000、001、010、011、100、101、110、111。如果這8種碼組都可傳遞消息，若在傳輸過程中發(fā)生一個(gè)誤碼，則一種碼組會(huì)錯(cuò)誤地變成另一種碼組。由于每一種碼組都可能出現(xiàn)，沒有多余的信息量，因此接收端不可能發(fā)現(xiàn)錯(cuò)誤，認(rèn)為發(fā)送的就是另一種碼組。15香農(nóng)的信道編碼定理為信道編碼奠定了理

如果選其中000、011、101、110來傳送消息，這相當(dāng)于只傳遞00、01、10、11四種信息，而第3位是附加的。這位附加的監(jiān)督碼元與前面兩位碼元一起，保證碼組中“1”碼的個(gè)數(shù)為偶數(shù)。這4種碼組稱為許用碼組。另外4種碼組不滿足這種校驗(yàn)關(guān)系，稱為禁用碼組，它們?cè)诰幋a后的發(fā)送碼元中不會(huì)出現(xiàn)。接收時(shí)一旦發(fā)現(xiàn)有禁用碼組，就表明傳輸過程中發(fā)生了錯(cuò)誤。用這種簡(jiǎn)單的校驗(yàn)關(guān)系可以發(fā)現(xiàn)1個(gè)或3個(gè)錯(cuò)誤，但不能糾正錯(cuò)誤。因?yàn)楫?dāng)接收到的碼組為禁用碼組時(shí)，比如為010，無法判斷發(fā)送的是哪個(gè)碼組。雖然原發(fā)送碼組為101的可能性很小(因?yàn)?個(gè)誤碼的概率一般很小)，但不能絕對(duì)排除，即使傳輸過程中只發(fā)生一個(gè)誤碼，也有三種可能的發(fā)送碼組即000、011和110。16如果選其中000、011、101、1

假如我們進(jìn)一步將許用碼組限制為二種即000和111，顯然這樣可以發(fā)現(xiàn)所有2位以下的誤碼，若用來糾錯(cuò)，可以用最大似然準(zhǔn)則糾正1位錯(cuò)誤。可以用一個(gè)三維立方體來表示上述3位二進(jìn)制碼組的例子，如圖10.2.3所示。圖中立方體各頂點(diǎn)分別表示8位碼組，3位碼元依次表示x、y、z軸的坐標(biāo)。17假如我們進(jìn)一步將許用碼組限制為二種即1818

這里定義碼組中非零碼元的數(shù)目為碼組的重量，簡(jiǎn)稱碼重。比如100碼組的碼重為1，101碼組的碼重為2。定義兩個(gè)碼組中對(duì)應(yīng)碼位上具有不同二進(jìn)制碼元的位數(shù)為兩碼組的距離，稱為漢明(Hamming)距，簡(jiǎn)稱碼距。在前面3位二進(jìn)制碼組的例子中，當(dāng)8種碼組均為許用碼組時(shí)，兩碼組間的最小距離為1，稱這種編碼的最小碼距為1，一般記為dmin=l；當(dāng)選4種碼組為許用碼組時(shí)，最小碼距dmin

=2；當(dāng)用2種碼組作為許用碼組時(shí)，dmin=3。19這里定義碼組中非零碼元的數(shù)目為碼組的

從圖10.2.3所示的立方體可以看出，碼距就是從一個(gè)頂點(diǎn)沿立方體各邊移到另一個(gè)頂點(diǎn)所經(jīng)過的最少邊數(shù)。圖中粗線表示000與111之間的一條最短路徑。很容易得出前例中各種情況下的碼距。根據(jù)以上分析可知，編碼的最小碼距直接關(guān)系到這種碼的檢錯(cuò)和糾錯(cuò)能力，所以最小碼距是差錯(cuò)控制編碼的一個(gè)重要參數(shù)。對(duì)于分組碼一般有以下結(jié)論:20從圖10.2.3所示的立方體可以看出

1.在一個(gè)碼組內(nèi)檢測(cè)e個(gè)誤碼，要求最小碼距dmin≥e+1(10.2.2)2.在一個(gè)碼組內(nèi)糾正t個(gè)誤碼，要求最小碼距dmin≥2t+1(10.2.3)3.在一個(gè)碼組內(nèi)糾正t個(gè)誤碼，同時(shí)檢測(cè)e(e≥t)個(gè)誤碼，要求最小碼距dmin≥t+e+1(10.2.4)這些結(jié)論可以用圖10.2.4所示的幾何圖形簡(jiǎn)單的給予證明。211.在一個(gè)碼組內(nèi)檢測(cè)e個(gè)誤碼，要求2222

可見dmin體現(xiàn)了碼組的糾、檢錯(cuò)能力。碼組間最小距離越大，說明碼字間最小差別越大，抗干擾能力就越強(qiáng)。

由于編碼系統(tǒng)具有糾錯(cuò)能力，因此在達(dá)到同樣誤碼率要求時(shí)，編碼系統(tǒng)會(huì)使所要求的輸入信噪比低于非編碼系統(tǒng)，為此引入了編碼增益的概念。其定義為，在給定誤碼率下，非編碼系統(tǒng)與編碼系統(tǒng)之間所需信噪比Eb/N0之差(用dB表示)。采用不同的編碼會(huì)得到不同的編碼增益，但編碼增益的提高要以增加系統(tǒng)帶寬或復(fù)雜度來換取。23可見dmin體現(xiàn)了碼組的糾、檢錯(cuò)能

10.2.4常用的簡(jiǎn)單檢錯(cuò)碼

常用檢錯(cuò)碼的結(jié)構(gòu)一般都很簡(jiǎn)單，由于這些碼組具有較強(qiáng)的檢錯(cuò)能力，并且易于實(shí)現(xiàn)，所以在實(shí)際當(dāng)中應(yīng)用很廣泛。

1．奇偶校驗(yàn)碼奇偶校驗(yàn)碼又稱奇偶監(jiān)督碼，它只有一個(gè)監(jiān)督碼元，是一種最簡(jiǎn)單的檢錯(cuò)碼，在計(jì)算機(jī)數(shù)據(jù)傳輸中得到廣泛應(yīng)用。編碼時(shí)，首先將要傳送的信息分組，按每組中“1”碼的個(gè)數(shù)計(jì)算監(jiān)督碼元的值。編碼后，整個(gè)碼組中“1”碼個(gè)數(shù)成為奇數(shù)的稱奇校驗(yàn)，成為偶數(shù)的稱偶校驗(yàn)。2410.2.4常用的簡(jiǎn)單檢錯(cuò)碼

設(shè)碼組長度為n，其中前n-1位(an-1,an-2

,?,a1)是信息碼元，a0是監(jiān)督碼元，二者之間的監(jiān)督關(guān)系可用公式表示。

奇校驗(yàn)滿足

偶校驗(yàn)滿足(10.2.6)(10.2.5)25設(shè)碼組長度為n，其中前n-1位(a

接收端用一個(gè)模2加法器就可以完成檢錯(cuò)工作。當(dāng)錯(cuò)碼為一個(gè)或奇數(shù)個(gè)時(shí)，因打亂了“1”數(shù)目的奇偶性，故能發(fā)現(xiàn)差錯(cuò)。然而，當(dāng)錯(cuò)誤個(gè)數(shù)為偶數(shù)時(shí)，由于未破壞“l(fā)”數(shù)目的奇偶性，所以不能發(fā)現(xiàn)偶數(shù)個(gè)錯(cuò)碼。26接收端用一個(gè)模2加法器就可以完成檢錯(cuò)

2．行列監(jiān)督碼

行列監(jiān)督碼也叫方陣校驗(yàn)碼，編碼原理與簡(jiǎn)單的奇偶監(jiān)督碼相似，不同之處在于每個(gè)碼元都要受到縱、橫兩個(gè)方向的監(jiān)督。以圖10.2.5為例，有28個(gè)待發(fā)送的數(shù)據(jù)碼元，將它們排成4行7列的方陣。方陣中每行是一個(gè)碼組，每行的最后加上一個(gè)監(jiān)督碼元進(jìn)行行監(jiān)督，同樣在每列的最后也加上一個(gè)監(jiān)督碼元進(jìn)行列監(jiān)督，然后按行(或列)發(fā)送。接收端按同樣行列排成方陣，發(fā)現(xiàn)不符合行列監(jiān)督規(guī)則的判為有錯(cuò)。它除了能檢出所有行、列中的奇數(shù)個(gè)錯(cuò)誤外，也能發(fā)現(xiàn)大部分偶數(shù)個(gè)錯(cuò)誤。因?yàn)槿绻龅讲铄e(cuò)個(gè)數(shù)恰為4的倍數(shù)，而且差錯(cuò)位置正好處于矩形四個(gè)角的情況，方陣碼無法發(fā)現(xiàn)錯(cuò)誤。27

2828

行列監(jiān)督碼在某些條件下還能糾錯(cuò)，觀察第3行、第4列出錯(cuò)的情況，假設(shè)在傳輸過程中第3行、第4列的“1”錯(cuò)成“0”，由于此錯(cuò)誤同時(shí)破壞了第3行、第4列的偶監(jiān)督關(guān)系，所以接收端很容易判斷是3行4列交叉位置上的碼元出錯(cuò)，從而給予糾正。

行列監(jiān)督碼也常用于檢查或糾正突發(fā)錯(cuò)誤。它可以檢查出錯(cuò)誤碼元長度小于和等于碼組長度的所有錯(cuò)碼，并糾正某些情況下的突發(fā)差錯(cuò)。

行列監(jiān)督碼實(shí)質(zhì)上是運(yùn)用矩陣變換，把突發(fā)差錯(cuò)變成獨(dú)立差錯(cuò)加以處理。因?yàn)檫@種方法比較簡(jiǎn)單，所以被認(rèn)為是克制突發(fā)差錯(cuò)很有效的手段。29行列監(jiān)督碼在某些條件下還能糾錯(cuò)，觀

3.恒比碼

恒比碼又稱等比碼或等重碼。恒比碼的每個(gè)碼組中，“1”和“0”的個(gè)數(shù)比是恒定的。我國電傳通信中采用的五單位數(shù)字保護(hù)電碼是一種3∶2等比碼，也叫五中取三的恒比碼，即在5單位電傳碼的碼組中(25=32)，取其“1”的數(shù)目恒為3的碼組(C53=10)，代表10個(gè)字符(0～9)，如表10.2.1所示。因?yàn)槊總€(gè)漢字是以四位十進(jìn)制數(shù)表示的，所以提高十進(jìn)制數(shù)字傳輸?shù)目煽啃裕喈?dāng)于提高了漢字傳輸?shù)目煽啃浴?03.恒比碼30

國際電傳電報(bào)上通用的ARQ通信系統(tǒng)中，選用三個(gè)“1”、四個(gè)“0”的3:4碼，即七中取三碼。它有C73=35個(gè)碼組，分別表示26個(gè)字母及其他符號(hào)。

在檢測(cè)恒比碼時(shí)，通過計(jì)算接收碼組中“1”的數(shù)目，判定傳輸有無錯(cuò)誤。除了“1”錯(cuò)成“0”和“0”錯(cuò)成“1”成對(duì)出現(xiàn)的錯(cuò)誤以外，這種碼能發(fā)現(xiàn)其他所有形式的錯(cuò)誤，因此檢錯(cuò)能力很強(qiáng)。實(shí)踐證明，應(yīng)用這種碼，國際電報(bào)通信的誤碼率保持在10-6以下。3131

4.ISBN國際統(tǒng)一圖書編號(hào)

國際統(tǒng)一圖書編號(hào)是一種檢錯(cuò)碼，以防止書號(hào)在通信過程中發(fā)生誤傳。這里以編號(hào)ISBN0-1315-2447-X為例，其中第一位數(shù)字“0”表示該書是美國及其它英語國家的出版物(中國的代號(hào)是數(shù)字“7”)，“1315”代表出版公司，“2447”代表書名編號(hào)，最后一位數(shù)字“X”是校驗(yàn)位(這是10的羅馬字表示)。這里采用的校驗(yàn)方法如圖10.2.6所示。324.ISBN國際統(tǒng)一圖書編號(hào)323333

圖中第1行為ISBN編號(hào)。第2行第1個(gè)數(shù)字與第1行第1個(gè)數(shù)字相同；第2行第2個(gè)數(shù)字則為第1行第2個(gè)數(shù)字與第2行第1個(gè)數(shù)字之和，即1+0=1；第2行第3個(gè)數(shù)字為第1行第3個(gè)數(shù)字與第2行第2個(gè)數(shù)字之和，即3+1=4；依次類推，第2行最后所得的累計(jì)和為37。用同樣方法得到第3行的最后累計(jì)和為132。然后用模11對(duì)132進(jìn)行校驗(yàn)，132(mod11)≡0。

顯然，若通信過程中統(tǒng)一書號(hào)發(fā)生了錯(cuò)誤，則上累計(jì)和就不能被11所整除，從而可校驗(yàn)出來。34圖中第1行為ISBN編號(hào)。第2行第10.3線性分組碼

10.3.1基本概念

一個(gè)長為n的分組碼，碼字由兩部分構(gòu)成，即信息碼元(k位)+監(jiān)督碼元(r位)。監(jiān)督碼元是根據(jù)一定規(guī)則由信息碼元變換得到的，變換規(guī)則不同就構(gòu)成不同的分組碼。如果監(jiān)督位為信息位的線性組合，就稱其為線性分組碼。

要從k個(gè)信息碼元中求出r個(gè)監(jiān)督碼元，必須有r個(gè)獨(dú)立的線性方程。根據(jù)不同的線性方程，可得到不同的(n,k)線性分組碼。3510.3線性分組碼10.3.1基本概念35

例如，已知一個(gè)(7，4)線性分組碼，4個(gè)信息碼元a6、a5、a4、a3和3個(gè)監(jiān)督碼元a2、a1、a0之間符合以下規(guī)則

計(jì)算上式得到此(7，4)線性分組碼的全部碼組，列于表10.3.1中(許用碼組的個(gè)數(shù)等于k個(gè)信息碼元的全部組合數(shù)2k個(gè))。(10.3.1)36例如，已知一個(gè)(7，4)線性分組碼，43737

前面介紹的奇偶監(jiān)督碼是一種最簡(jiǎn)單的線性碼。改寫式(10.2.5)、式(10.2.6)可以得到監(jiān)督碼元a0和信息碼元之間的關(guān)系。

奇校驗(yàn)

偶校驗(yàn)(10.3.2)(10.3.3)38前面介紹的奇偶監(jiān)督碼是一種最簡(jiǎn)單的線

線性碼各許用碼組的集合構(gòu)成了代數(shù)學(xué)中的群，因此又稱群碼。它有如下性質(zhì):

1）任意兩許用碼組之和(按位模2加)仍為一許用碼組，即線性碼具有封閉性；

2）集合中的最小距離等于碼組中非全“0”碼字的最小重量。

在群中只存在一種運(yùn)算，即模2加，通常四則運(yùn)算中的加、減法在這里都是模2加的關(guān)系。所以后面將簡(jiǎn)化運(yùn)算符號(hào)⊕為“+”。

為了說明(n,k)線性分組碼的編碼原理，下面引入監(jiān)督矩陣H和生成矩陣G的概念。39線性

10.3.2監(jiān)督矩陣和生成矩陣

1.監(jiān)督矩陣H

改寫式(10.3.1)所示(7，4)線性分組碼的3個(gè)線性方程式

寫成矩陣形式(10.3.4)(10.3.5)4010.3.2監(jiān)督矩陣和生成矩陣或(10.3.6)41或(10.3.6)41分別記作或

式中

是r×n階矩陣，稱為線性分組碼的一致監(jiān)督矩陣(或校驗(yàn)矩陣)。(10.3.8)(10.3.7)(10.3.9)42分別記作(10.3.8)(10.3.7)(10.3.9)

AT、0T、HT分別是A、0、H矩陣的轉(zhuǎn)置。

對(duì)于碼字A來說，恒有

或

成立，即當(dāng)監(jiān)督矩陣H給定時(shí)，利用式(10.3.7)可以驗(yàn)證接收碼是否正確。

H矩陣可以分成兩部分:43AT、0T、HT分別是A、0、H矩陣

H矩陣可以分成兩部分:

式中P為r×k階矩陣，Ir為r×r階單位方陣，具有[PIr]形式的H矩陣被稱為典型矩陣。線性代數(shù)的基本理論指出，典型形式的監(jiān)督矩陣各行一定是線性無關(guān)的，非典型形式的監(jiān)督矩陣可以經(jīng)過線性變換化為典型形式，除非非典型形式監(jiān)督矩陣的各行不是線性無關(guān)的。(10.3.10)44H矩陣可以分成兩部分:(10.3

2.生成矩陣G

改寫式(10.3.1)為矩陣形式

或者(10.3.11)(10.3.12)452.生成矩陣G(10.3.11)(10.3.

其中Q為k×r階矩陣。該式表明，已知Q矩陣，同樣可以由信息位算出監(jiān)督碼元。不難看出,Q是P的轉(zhuǎn)置，即

如果在Q的左邊加上一個(gè)k×k階單位方陣，就構(gòu)成了生成矩陣(10.3.13)(10.3.14)46其中Q為k×r階矩陣。該式表明，已知

稱G為生成矩陣，是因?yàn)槔盟梢援a(chǎn)生碼組A，即

符合[IkQ]形式的生成矩陣稱為典型形式的生成矩陣，由該矩陣得到的碼組是系統(tǒng)碼。利用此生成矩陣同樣可以得到表10.3.1中給出的(7，4)線性分組碼的全部碼字。

同樣，典型形式的生成矩陣的各行也必定是線性無關(guān)的，每行都是一個(gè)許用碼組，k行許用碼組經(jīng)過行運(yùn)算可以生成2k個(gè)不同的許用碼組。非典型形式的生成矩陣經(jīng)過運(yùn)算也一定可以化為典型形式。

典型監(jiān)督矩陣和典型生成矩陣之間存在關(guān)系

(10.3.15)(10.3.16)47稱G為生成矩陣，是因?yàn)槔盟梢援a(chǎn)生

10.3.3伴隨式（校正子）

發(fā)送碼組A=[an-1an-2

?a0

]在傳輸過程中可能會(huì)發(fā)生誤碼。設(shè)接收到的碼組為B=[bn-1bn-2

?b0]，則收、發(fā)碼組之差為B–A=E

或?qū)懗葿=A+E

式中E=[en-1en-2

?e0]為錯(cuò)誤圖樣。

令

S=BHT

為分組碼的伴隨式(亦稱校正子或校驗(yàn)子)。

利用式(10.3.8)，可以得到S=(A+E)HT=AHT+EHT=EHT

這樣就把校正子S與接收碼組B的關(guān)系轉(zhuǎn)換成了校正子S與錯(cuò)誤圖樣E的關(guān)系。(10.3.17)(10.3.18)(10.3.19)4810.3.3伴隨式（校正子）(10.3.17

在接收機(jī)中只要用式(10.3.18)計(jì)算校正子S，并判斷計(jì)算結(jié)果是否為0，就可完成檢錯(cuò)工作。因?yàn)槿绻钦_接收(E=0)，則B=A+E=A，依照式(10.3.8)有S=BHT=AHT=0

如果接收碼組不等于發(fā)送碼組(B≠A)，則E≠0，故S=EHT≠0。

在討論怎樣利用校正子S完成糾錯(cuò)工作之前，先看一下S與E的關(guān)系。

前面所說的(7，4)線性分組碼[見式(10.3.9)]

49在接收機(jī)中只要用式(10.3.18)計(jì)

設(shè)接收碼組的最高位有錯(cuò)，錯(cuò)誤圖樣E=[1000000]，計(jì)算5050

它的轉(zhuǎn)置

恰好是典型監(jiān)督矩陣H中的第一列。

如果是接收碼組B中的次高位有錯(cuò)，E=[0100000]，那么算出的S=[110]，其轉(zhuǎn)置ST恰好是典型監(jiān)督矩陣H中的第二列。

換言之，在接收碼組只錯(cuò)一位碼元的情況下，計(jì)算出的校正子S總是和典型監(jiān)督矩陣HT中的某一行相同?？梢宰C明，只要不超出線性分組碼的糾錯(cuò)能力，接收機(jī)依據(jù)計(jì)算出的校正子S，可以判斷碼組的錯(cuò)誤位置并予以糾正。這里僅討論糾正一位錯(cuò)誤碼元的情況。51它的轉(zhuǎn)置51

例10.3.1已知前述(7，4)線性分組碼某碼組，在傳輸過程中發(fā)生一位誤碼，設(shè)接收碼組B=[0000101]，試將其恢復(fù)為正確碼組。解:(1)首先確定碼組的糾、檢錯(cuò)能力查表10.3.1，得到最小碼距dmin=3，故此碼組可以糾正一位錯(cuò)碼或檢測(cè)兩位錯(cuò)誤碼元。(2)計(jì)算ST52例10.3.1已知前述(7，4)線已知前述(7,4)線性分組碼的典型監(jiān)督矩陣?yán)镁仃囆再|(zhì)汁算校正子的轉(zhuǎn)置53已知前述(7,4)線性分組碼的典型監(jiān)督矩陣53

(3)恢復(fù)正確碼組因?yàn)榇舜a組具有糾正一位錯(cuò)誤的能力，且計(jì)算結(jié)果ST與H矩陣中的第三列相同，相當(dāng)于得到錯(cuò)誤圖樣E=[0010000]，所以正確碼組為A=B+E

=[0000101]+[0010000]=[0010101]54(3)恢復(fù)正確碼組54

10.3.4漢明碼

漢明碼是一種可以糾正單個(gè)隨機(jī)錯(cuò)誤的線性分組碼。它的最小碼距dmin=3，監(jiān)督碼元位數(shù)r=n–k(r是一個(gè)大于或等于2的正整數(shù))，碼長n=2r-1，信息碼元位數(shù)k=2r-1-r,編碼效率R=k/n=(2r-1-r)/(2r-1)=1-r/(2r-1)。當(dāng)r很大時(shí)，極限趨于1，所以是一種高效碼。

漢明碼的監(jiān)督矩陣H有n列r行，它的n列由不全為0的二進(jìn)制r位碼的不同組合構(gòu)成，即每種組合只在某列中出現(xiàn)一次。55

10.3.4漢明碼55

以r=3為例，它的碼長n=23-1=7，所以前面所說的(7，4)線性分組碼就是漢明碼，并且任意調(diào)換H矩陣中各列的位置，不會(huì)影響碼的糾、檢錯(cuò)能力。例如可以構(gòu)造出與式(10.3.9)不同的監(jiān)督矩陣，即

其相應(yīng)的生成矩陣為(10.3.21)(10.3.20)56以r=3為例，它的碼長n=23-

因此，漢明碼H矩陣中各列的位置還可以有其它多種排列形式。

漢明碼的譯碼方法，可以采用計(jì)算校正子，然后確定錯(cuò)誤圖樣并加以糾正的方法。圖10.3.1中給出式(10.3.20)所示(7，4)漢明碼的編碼器和譯碼器電路圖。57因此，漢明碼H矩陣中各列的位置還可以5858

糾正單個(gè)錯(cuò)誤的漢明碼中，r位校正子碼組與誤碼圖樣一一對(duì)應(yīng)，最充分地利用了監(jiān)督位所能提供的信息，這種碼稱為完備碼。在一般情況下，對(duì)于能糾正t個(gè)錯(cuò)誤的線性分組碼(n，k)，應(yīng)滿足不等式(10.3.22)59糾正單個(gè)錯(cuò)誤的漢明碼中，r位校正子碼組與誤碼圖樣

這里，

為中n取i的組合，其物理意義是n位碼組中有i個(gè)誤碼的錯(cuò)誤圖樣數(shù)目(i≠0)。

式(10.3.22)取等號(hào)時(shí)，校正子與誤碼不超過t個(gè)的所有錯(cuò)誤圖樣一一對(duì)應(yīng)，監(jiān)督碼元得到最充分的利用，這種(n，k)碼即為完備碼。

除了漢明碼外，迄今為止已找到的唯一能糾正多個(gè)錯(cuò)誤的完備碼是(23，12)非本原BCH碼，常稱為戈雷碼。60這里，為中n取i的組合，其物理意10.4循環(huán)碼

循環(huán)碼是線性分組碼中一個(gè)最重要的分支。它的檢、糾錯(cuò)能力較強(qiáng)，編碼和譯碼設(shè)備并不復(fù)雜，所以循環(huán)碼受到人們的高度重視，在前向糾錯(cuò)系統(tǒng)中得到了廣泛應(yīng)用。

循環(huán)碼有嚴(yán)密的代數(shù)理論基礎(chǔ)，是目前研究得最成熟的一類碼。這里對(duì)循環(huán)碼不作嚴(yán)格的數(shù)學(xué)分析，只重點(diǎn)介紹循環(huán)碼在差錯(cuò)控制中的應(yīng)用。6110.4循環(huán)碼循環(huán)碼是線性分組碼中

10.4.1循環(huán)碼的特點(diǎn)

循環(huán)碼有兩個(gè)數(shù)學(xué)特征：

1）線性分組碼的封閉性；

2）循環(huán)性，即任一許用碼組經(jīng)過循環(huán)移位后所得到的碼組仍為該許用碼組集合中的一個(gè)碼組。

表10.4.1列出了某(7，3)循環(huán)碼的全部碼組。6210.4.1循環(huán)碼的特點(diǎn)62

以2號(hào)碼組(0010111)為例，左移循環(huán)一位變成3號(hào)碼組(0101110)，依次左移一位構(gòu)成的狀態(tài)圖如圖10.4.1所示。63以2號(hào)碼組(0010111)為例，左

可見除全零碼組外，不論循環(huán)右移或左移，移多少位，其結(jié)果均在該循環(huán)碼組的集合中(全零碼組自己構(gòu)成獨(dú)立的循環(huán)圈)。

為了用代數(shù)學(xué)理論研究循環(huán)碼，可將碼組用多項(xiàng)式表示，稱為碼多項(xiàng)式。循環(huán)碼組中各碼元分別為多項(xiàng)式的系數(shù)。長度為n的碼組A=(an-1an-2

?a1a0)用碼多項(xiàng)式可表示為(10.4.2)64可見除全零碼組外，不論循環(huán)右移或左移

若左移i位后的碼組A(i)=(an-i-1an-i-2

?an-i+1an-i

)，其碼多項(xiàng)式為A(i)(x)可以用下式由xiA(x)求得:

這里Q(x)是xiA(x)除以(xi

+1)的商式，而A(i)(x)是所得的余式。式(10.4.4)也可表示為(10.4.3)(10.4.4)(10.4.5)65若左移i位后的碼組A(i)=(an

在A(x)的表達(dá)式中，系數(shù)ai=0的項(xiàng)常略去不寫，ai=1的項(xiàng)只寫符號(hào)x及其冪次。

碼多項(xiàng)式之間可以進(jìn)行代數(shù)運(yùn)算，在二元碼中遵循模2運(yùn)算的規(guī)則。根據(jù)線性碼的封閉性，任意兩碼字經(jīng)模運(yùn)算后仍為本碼組中的碼字。

從代數(shù)學(xué)的角度，每個(gè)二進(jìn)制碼組可以看成是只有0和1兩個(gè)元素的二元域中的n重。所有二元n重的集合稱為二元域上的一個(gè)矢量空間。二元域上只有兩種運(yùn)算，即加和乘，所有運(yùn)算結(jié)果也必定在同一個(gè)二元集合中。66在A(x)的表達(dá)式中，系數(shù)ai=0的

在二元域中加和乘的運(yùn)算規(guī)則定義為

一組多項(xiàng)式就構(gòu)成一個(gè)(n,k)循環(huán)碼。也就是說，階數(shù)小于等于n-1能被g(x)除盡的每個(gè)多項(xiàng)式都是該循環(huán)碼的許用碼組。(n,k)循環(huán)碼有2k個(gè)碼組，因?yàn)榭梢詷?gòu)成循環(huán)許用碼組A(x)的信息碼組m(x)有2k個(gè)。67在二元域中加和乘的運(yùn)算規(guī)則定義為67

這里，m(x)為不大于k-1階的多項(xiàng)式。

例如，令n＝7，g(x)＝x4+x3+x2+1是x7+1的一個(gè)因式，共有8個(gè)階次不大于6的多項(xiàng)式是g(x)的倍式，即(10.4.6)68這里，m(x)為不大于k-1階的多

這8個(gè)多項(xiàng)式是一個(gè)(7，3)循環(huán)碼。由于它有8個(gè)碼組，k＝3，因此n-k＝7-3＝4，這必定是生成多項(xiàng)式的階次。

為了尋找生成多項(xiàng)式，必須對(duì)xn

+1進(jìn)行因式分解，這可以用計(jì)算機(jī)來完成。對(duì)于某些n值，xn+1只有很少幾個(gè)因式，因而碼長為這些n值的循環(huán)碼很少。僅對(duì)于很少幾個(gè)n值才有很多因式。69這8個(gè)多項(xiàng)式是一個(gè)(7，3)循環(huán)碼。

對(duì)于任意n值有

若取x+1為生成多項(xiàng)式，這樣構(gòu)成的循環(huán)碼就是簡(jiǎn)單的偶監(jiān)督碼(n，n-1)。由于g(x)為一階多項(xiàng)式，因此只有一位監(jiān)督碼?？梢宰C明，x+1的任何倍式的碼重（即碼組中1的個(gè)數(shù)）必定保持偶數(shù)。這是一種最簡(jiǎn)單的循環(huán)碼，dmin

=2。(10.4.7)70對(duì)于任意n值有(10.4.7)70

另一個(gè)最簡(jiǎn)單的循環(huán)碼是以xn-1

+xn-2

+?+x+1為生成多項(xiàng)式，由于生成多項(xiàng)式是n-1階．故信息碼位為1。只有兩種碼組即全0和全1，因此這種循環(huán)碼是重復(fù)碼(n，1)，dmin=n。

任何(n,k)循環(huán)碼的生成多項(xiàng)式g(x)，用乘上(x+1)后得到生成多項(xiàng)式g(x)·(x+1)所構(gòu)造的循環(huán)碼(n，k-1)，其最小碼距增加1。(n，k-1)碼是(n，k)碼的一個(gè)子集。71另一個(gè)最簡(jiǎn)單的循環(huán)碼是以xn-1+

以因式分解中的本原多項(xiàng)式作為生成多項(xiàng)式，可以構(gòu)造出糾正一個(gè)錯(cuò)誤的循環(huán)漢明碼。

考查表10.4.1，其中n-k=4階的多項(xiàng)式只有編號(hào)為(2)的碼組(0010111)，所以表中所示(7，3)循環(huán)碼組的生成多項(xiàng)式g(x)=x4+x2+x+1，并且該碼組集合中的任何碼多項(xiàng)式A(x)都可由信息位乘以生成多項(xiàng)式得到7272

式中(mk-1

mk-2?m1

m0)為信息碼元。

對(duì)于(7，k)循環(huán)碼，有

表10.4.1中所示(7，3)循環(huán)碼組的g(x)，是由式(10.4.9)中第1、3兩項(xiàng)相乘得到的。

如果令式(10.4.9)中第1、2兩項(xiàng)相乘，也得到一個(gè)4階多項(xiàng)式，由它可以構(gòu)成另一個(gè)(7，3)循環(huán)碼組的集合?？梢娺x擇不同的因式組合會(huì)得到不同的生成多項(xiàng)式，從而構(gòu)成不同的循環(huán)碼組。(10.4.8)(10.4.9)73(10.4.8)(10.4.9)73

由于g(x)為n-k階多項(xiàng)式，以與此相對(duì)應(yīng)的碼組作為生成矩陣中的一行，可以證明g(x)，xg(x)，?，xk-1g(x)等多項(xiàng)式必定是線性無關(guān)的。把這k個(gè)多項(xiàng)式相對(duì)應(yīng)的碼組作為各行構(gòu)成的矩陣即為生成矩陣，由各行的線性組合可以得到2k個(gè)循環(huán)碼碼組。這樣循環(huán)碼的生成矩陣多項(xiàng)式可以寫成(10.4.10)74由于g(x)為n-k階多項(xiàng)式，以與此

以表10.4.1中的生成多項(xiàng)式g(x)構(gòu)造G(x)，相應(yīng)的矩陣形式為

作線性變換，整理成典型形式的生成矩陣(10.4.12)(10.4.11)75以表10.4.1中的生成多項(xiàng)式g(x

信息碼元與式(10.4.12)相乘，得到的就是系統(tǒng)循環(huán)碼。

由式(10.4.10)生成矩陣得到的循環(huán)碼并非系統(tǒng)碼。在系統(tǒng)碼中碼組的最左k位是信息碼元，隨后是n-k位監(jiān)督碼元。這相當(dāng)于碼多項(xiàng)式為76信息碼元與式(10.4.12)相乘，得

這里r(x)=rn-k-1xn-k-1+?+r0為監(jiān)督碼多項(xiàng)式，其相應(yīng)的監(jiān)督碼元為(rn-k-1,?,r0)。由式(10.4.14)可知

可見，構(gòu)造系統(tǒng)循環(huán)碼時(shí)，只需將信息碼多項(xiàng)式升n-k階(即乘上xn-k

)，然后以g(x)為模，即除以g(x)，所得余式r(x)即為監(jiān)督碼元。因此，系統(tǒng)循環(huán)碼的編碼過程就變成用除法求余的問題。

系統(tǒng)碼的生成矩陣為典型形式G=[IkQ]，與單位矩陣Ik每行對(duì)應(yīng)的信息多項(xiàng)式為(10.4.14)(10.4.15)77這里r(x)=rn-k-1xn-k-由式(10.4.15)可得相應(yīng)的監(jiān)督多項(xiàng)式為由此得到生成矩陣中每行的碼多項(xiàng)式為因此系統(tǒng)循環(huán)碼生成矩陣多項(xiàng)式的一般表示為(10.4.18)(10.4.17)(10.4.16)78由式(10.4.15)可得相應(yīng)的監(jiān)督多項(xiàng)式為(10.4.1

10.4.3監(jiān)督多項(xiàng)式與監(jiān)督矩陣

如前所述，在(n,k)循環(huán)碼中，xn

+l可分解成g(x)和其它因式的乘積，記為

由于g(x)是常數(shù)項(xiàng)為1的r次多項(xiàng)式，則h(x)為k次多項(xiàng)式,即h(x)=hkxk+?+h1x+h0,稱h(x)為監(jiān)督多項(xiàng)式。若g(x)=gn-kxn-k

+?+g1x+g0，由式(10.4.19)可知，必定有(10.4.19)7910.4.3監(jiān)督多項(xiàng)式與監(jiān)督矩陣(10.

這樣可以得到循環(huán)碼的監(jiān)督矩陣為

它有n-k行n列，完全由h(x)的系數(shù)確定，可以證明GHT=0。(10.4.20)(10.4.21)80(10.4.20)(10.4.21)80

與式(10.4.10)給出的G(x)相對(duì)應(yīng)，監(jiān)督矩陣多項(xiàng)式可用下式表示

其中h*(x)是h(x)的逆多項(xiàng)式。

典型形式的監(jiān)督矩陣可以由式(10.4.22)作線性變換得到。(10.4.22)81與式(10.4.10)給出的G(x)

例10.4.1已知(7，4)系統(tǒng)碼的生成多項(xiàng)式為g(x)=x3+x2+1，求生成矩陣。解：由式(10.4.16)可得

(10.4.23)82例10.4.1已知(7，4)系統(tǒng)碼的生成因此，生成矩陣多項(xiàng)式表示為由多項(xiàng)式系數(shù)得到的生成矩陣為(10.4.25)(10.4.24)83因此，生成矩陣多項(xiàng)式表示為(10.4.25)(10.4.24

10.4.4系統(tǒng)循環(huán)碼的編譯碼方法

1.系統(tǒng)循環(huán)碼的編碼

對(duì)于碼組前k位是信息碼元的系統(tǒng)碼，用多項(xiàng)式表示則為

式中，m(x)是不大于(k-1)次的多項(xiàng)式，代表信息碼元；r(x)是不大于(r-1)次的多項(xiàng)式，代表監(jiān)督碼元。

若令式(10.4.8)中的信息碼元為m‘(x)，則碼組多項(xiàng)式可寫成(10.4.27)(10.4.26)8410.4.4系統(tǒng)循環(huán)碼的編譯碼方

聯(lián)立式(10.4.26)、式(10.4.27)得

即

這就是循環(huán)碼編碼的數(shù)學(xué)依據(jù)，式中為m‘(x)商，r(x)為余式。(10.4.28)85聯(lián)立式(10.4.26)、式(10.

利用生成多項(xiàng)式g(x)作除法運(yùn)算的循環(huán)碼編碼方法歸納如下:

1）信息多項(xiàng)式m(x)左移n-k位，即相當(dāng)于m(x)乘因子xn-k；

2）以g(x)為除式作模運(yùn)算，得余式r(x)；即

3）余式的系數(shù)作監(jiān)督碼元，附加在信息碼元之后形成系統(tǒng)碼，相當(dāng)于令余式r(x)和已經(jīng)左移n-k位的信息碼多項(xiàng)式作按位模2加運(yùn)算。即(10.4.29)(10.4.30)86利用生成多項(xiàng)式g(x)作除法運(yùn)算的循8787

以上編碼方法的實(shí)現(xiàn)電路并不復(fù)雜，多項(xiàng)式除法可以用帶反饋的線性移位寄存器來實(shí)現(xiàn)。有兩種不同的除法電路即采用“內(nèi)接”的模2和（異或門）電路與采用“外接”的模2和電路。生成多項(xiàng)式為g(x)=x6+x5+x4+x3+1的兩種除法電路如圖10.4.2中(a)、(b)所示，一般多采用內(nèi)接模2和的除法電路。內(nèi)接模2和除法電路的工作過程與采用手算進(jìn)行長除的過程完全一致。88以上編碼方法的實(shí)現(xiàn)電路并不復(fù)雜，多項(xiàng)2.系統(tǒng)循環(huán)碼的譯碼(了解)892.系統(tǒng)循環(huán)碼的譯碼(了解)89TheEnd!90TheEnd!90第10章差錯(cuò)控制編碼7.1概述7.2常用的幾種簡(jiǎn)單分組碼7.3線性分組碼7.4循環(huán)碼91第10章差錯(cuò)控制編碼7.1概述1

10.1概述

在數(shù)字信號(hào)傳輸中，由于信道不理想以及加性噪聲的影響，被傳輸?shù)男盘?hào)碼元波形會(huì)變壞，造成接收端錯(cuò)誤判決。為了盡量減小數(shù)字通信中信息碼元的差錯(cuò)概率，應(yīng)合理設(shè)計(jì)基帶信號(hào)并采用均衡技術(shù)以減小信道線性畸變引起的碼間干擾；對(duì)于由信道噪聲引起的加性干擾，應(yīng)考慮采取加大發(fā)送功率、適當(dāng)選擇調(diào)制解調(diào)方式等措施。但是隨著現(xiàn)代數(shù)字通信技術(shù)的不斷發(fā)展，以及傳輸速率的不斷提高，對(duì)信息碼元的差錯(cuò)概率Pe的要求也在提高，例如計(jì)算機(jī)間的數(shù)據(jù)傳輸，要求Pe低于10-9，并且信道帶寬和發(fā)送功率受到限制，此時(shí)就需要采用信道編碼，又稱為差錯(cuò)控制編碼。92

10.1概述2

信道編碼理論建立在香農(nóng)信息論的基礎(chǔ)上，其實(shí)質(zhì)是給信息碼元增加冗余度，即增加一定數(shù)量的多余碼元(稱為監(jiān)督碼元或校驗(yàn)碼元)，由信息碼元和監(jiān)督碼元共同組成一個(gè)碼字，兩者間滿足一定的約束關(guān)系。如果在傳輸過程中受到干擾，某位碼元發(fā)生了變化，就破壞了它們之間的約束關(guān)系。接收端通過檢驗(yàn)約束關(guān)系是否成立，完成識(shí)別錯(cuò)誤或者進(jìn)一步判定錯(cuò)誤位置并糾正錯(cuò)誤，從而提高通信的可靠性。93信道編碼理論建立在香農(nóng)信息論的基礎(chǔ)上

10.2差錯(cuò)控制編碼的基本概念

10.2.1差錯(cuò)控制方式

在差錯(cuò)控制系統(tǒng)中，差錯(cuò)控制方式主要有三種。

1.前向糾錯(cuò)控制方式(FEC)

又稱自動(dòng)糾錯(cuò)，是指發(fā)送端發(fā)出的可以糾正錯(cuò)誤碼元的編碼序列，接收端的譯碼器能自動(dòng)糾正傳輸中的錯(cuò)碼，系統(tǒng)框圖如圖10.2.1(a)所示。這種方式的優(yōu)點(diǎn)是不需要反饋信道，譯碼實(shí)時(shí)性好，具有恒定的信息傳輸速率。缺點(diǎn)是為了要獲得比較低的誤碼率，必須以最壞的信道條件來設(shè)計(jì)糾錯(cuò)碼，故需要附加較多的監(jiān)督碼元，這樣既增加了譯碼算法選擇的難度，也降低了系統(tǒng)的傳輸效率，所以不適宜應(yīng)用在傳輸條件惡化的信道。

94

10.2差錯(cuò)控制編碼的基本概念10.

2.反饋重發(fā)糾錯(cuò)方式(ARQ)

發(fā)送端發(fā)出的是能夠檢測(cè)錯(cuò)誤的編碼序列，接收端譯碼器根據(jù)編碼規(guī)則進(jìn)行判決，并通過反饋信道把判決結(jié)果回傳，無錯(cuò)認(rèn)可(ACK)，有錯(cuò)時(shí)否認(rèn)(NAK)。發(fā)送端根據(jù)回傳指令，將有錯(cuò)的碼組重發(fā)，直到接收端認(rèn)為正確接收為止，系統(tǒng)框圖如圖10.2.1(b)所示。

優(yōu)點(diǎn)：檢錯(cuò)碼構(gòu)造簡(jiǎn)單，不需要復(fù)雜的編譯碼設(shè)備，在冗余度一定的條件下，檢錯(cuò)碼的檢錯(cuò)能力比糾錯(cuò)碼的糾錯(cuò)能力強(qiáng)得多，故整個(gè)系統(tǒng)的誤碼率可以保持在極低的數(shù)量級(jí)上。

缺點(diǎn)：需要反饋信道，并要求發(fā)送端有大容量的信源存儲(chǔ)器，且為保證收、發(fā)兩端互相配合，控制電路較為復(fù)雜。另外，當(dāng)信道干擾很頻繁時(shí)，系統(tǒng)經(jīng)常處于重發(fā)消息的狀態(tài)，使傳送信息的實(shí)時(shí)性變差。955

3．混合糾錯(cuò)方式(HEC)

該方式是上述兩種方式的結(jié)合，即在ARQ系統(tǒng)中包含一個(gè)FEC子系統(tǒng)，系統(tǒng)框圖如圖10.2.1(c)所示。發(fā)送端發(fā)出的是具有一定糾錯(cuò)能力和較強(qiáng)檢錯(cuò)能力的碼，所以經(jīng)信道編碼而附加的監(jiān)督碼元并不多。接收端檢測(cè)數(shù)據(jù)碼流，發(fā)現(xiàn)錯(cuò)誤先由FEC子系統(tǒng)自動(dòng)糾錯(cuò)，僅當(dāng)錯(cuò)誤較多超出糾錯(cuò)能力時(shí)，再發(fā)反饋信息要求重發(fā)，因此大大減少了重發(fā)次數(shù)。HEC在一定程度上彌補(bǔ)了反饋重發(fā)和前向糾錯(cuò)兩種方式的缺點(diǎn)，充分發(fā)揮了碼的檢、糾錯(cuò)能力，在較強(qiáng)干擾的信道中仍可獲得較低誤碼率，是實(shí)際通信中應(yīng)用較多的糾錯(cuò)方式。963．混合糾錯(cuò)方式(HEC)6977

10.2.2差錯(cuò)控制編碼的分類

用不同的方法可以對(duì)差錯(cuò)控制編碼進(jìn)行不同的分類。1.根據(jù)已編碼組中信息碼元與監(jiān)督碼元之間的函數(shù)關(guān)系，可分為線性碼及非線性碼。若信息碼元與監(jiān)督碼元之間的關(guān)系呈線性，即滿足一組線性方程式，則稱為線性碼。否則稱為非線性碼。

9810.2.2差錯(cuò)控制編碼的分類8

2.根據(jù)信息碼元和監(jiān)督碼元之間的約束方式不同，可分為分組碼和卷積碼。分組碼的監(jiān)督碼元僅與本碼組的信息碼元有關(guān)，卷積碼的監(jiān)督碼元不僅與本組信息碼元有關(guān)，而且與前面若干碼組的信息碼元有約束關(guān)系。

3.根據(jù)編碼后信息碼元是否保持原來的形式，可分為系統(tǒng)碼和非系統(tǒng)碼。在系統(tǒng)碼中，編碼后的信息碼元保持原樣，而非系統(tǒng)碼中的信息碼元?jiǎng)t改變了原來的信號(hào)形式。992.根據(jù)信息碼元和監(jiān)督碼元之間的約

4.根據(jù)編碼的不同功能，可分為檢錯(cuò)碼、糾錯(cuò)碼和糾刪碼。檢錯(cuò)碼只能夠發(fā)現(xiàn)錯(cuò)誤，但不能糾正錯(cuò)誤；糾錯(cuò)碼能夠糾正錯(cuò)誤；糾刪碼即可以檢錯(cuò)又可以糾錯(cuò)，但糾錯(cuò)能力有限，當(dāng)有不能糾正的錯(cuò)誤時(shí)將發(fā)出錯(cuò)誤指示或刪除不可糾正的錯(cuò)誤段落。

5.根據(jù)糾正、檢驗(yàn)錯(cuò)誤的類型不同，可分為糾正、檢驗(yàn)隨機(jī)性錯(cuò)誤的碼和糾正、檢驗(yàn)突發(fā)性錯(cuò)誤的碼。

6.根據(jù)碼元取值的不同，可分為二進(jìn)制碼和多進(jìn)制碼。這里只介紹二進(jìn)制糾、檢錯(cuò)編碼。1004.根據(jù)編碼的不同功能，可分為檢錯(cuò)碼

10.2.3檢錯(cuò)和糾錯(cuò)的基本原理差錯(cuò)控制編碼的基本思想是在被傳輸?shù)男畔⒋a元中附加一些監(jiān)督碼元，并且使它們之間確定某一種關(guān)系，根據(jù)傳輸過程中這種關(guān)系是否被破壞來發(fā)現(xiàn)或糾正錯(cuò)誤?？梢娺@種差錯(cuò)控制能力是用增加信息量的冗余度來換取的。

設(shè)編碼后的碼組長度、碼組中所含信息碼元個(gè)數(shù)以及監(jiān)督碼元個(gè)數(shù)分別為n、k和r，三者間滿足n=k+r，定義編碼效率為R=k/n=1-r/n。可見碼組長度一定時(shí)，所加入的監(jiān)督碼元個(gè)數(shù)越多，編碼效率越低。10110.2.3檢錯(cuò)和糾錯(cuò)的基本原理

香農(nóng)的信道編碼定理指出:對(duì)于一個(gè)給定的有擾信道，若信道容量為C，只要發(fā)送端以低于C的速率R發(fā)送信息（R為編碼器的輸入二進(jìn)制碼元速率），則一定存在一種編碼方法，使編碼錯(cuò)誤概率P隨著碼長n的增加，按指數(shù)下降到任意小的值。可以表示為其中E(R)稱為誤差指數(shù)，它與R和C的關(guān)系如圖10.2.2所示。(10.2.1)102香農(nóng)的信道編碼定理指出:(10.210313

由定理有如下結(jié)論:1.在碼長及發(fā)送信息速率一定的情況下，為減小P可以增大信道容量。由圖10.2.2可知，E(R)隨信道容量的增加而增大。由式(10.2.1)可知，錯(cuò)誤概率隨E(R)的增大而指數(shù)下降。2.在信道容量及發(fā)送信息速率一定的條件下，增加碼長，可以使錯(cuò)誤概率指數(shù)下降。對(duì)于實(shí)際應(yīng)用來說，此時(shí)的設(shè)備復(fù)雜性和譯碼延時(shí)也隨之增加。104由定理有如下結(jié)論:14

香農(nóng)的信道編碼定理為信道編碼奠定了理論基礎(chǔ)，雖然定理本身并沒有給出具體的差錯(cuò)控制編碼方法和糾錯(cuò)碼的結(jié)構(gòu)，但它從理論上為信道編碼的發(fā)展指出了努力方向。

我們用3位二進(jìn)制碼組來說明檢錯(cuò)糾錯(cuò)的基本原理。3位二進(jìn)制碼元共有8種可能的組合:000、001、010、011、100、101、110、111。如果這8種碼組都可傳遞消息，若在傳輸過程中發(fā)生一個(gè)誤碼，則一種碼組會(huì)錯(cuò)誤地變成另一種碼組。由于每一種碼組都可能出現(xiàn)，沒有多余的信息量，因此接收端不可能發(fā)現(xiàn)錯(cuò)誤，認(rèn)為發(fā)送的就是另一種碼組。105香農(nóng)的信道編碼定理為信道編碼奠定了理

如果選其中000、011、101、110來傳送消息，這相當(dāng)于只傳遞00、01、10、11四種信息，而第3位是附加的。這位附加的監(jiān)督碼元與前面兩位碼元一起，保證碼組中“1”碼的個(gè)數(shù)為偶數(shù)。這4種碼組稱為許用碼組。另外4種碼組不滿足這種校驗(yàn)關(guān)系，稱為禁用碼組，它們?cè)诰幋a后的發(fā)送碼元中不會(huì)出現(xiàn)。接收時(shí)一旦發(fā)現(xiàn)有禁用碼組，就表明傳輸過程中發(fā)生了錯(cuò)誤。用這種簡(jiǎn)單的校驗(yàn)關(guān)系可以發(fā)現(xiàn)1個(gè)或3個(gè)錯(cuò)誤，但不能糾正錯(cuò)誤。因?yàn)楫?dāng)接收到的碼組為禁用碼組時(shí)，比如為010，無法判斷發(fā)送的是哪個(gè)碼組。雖然原發(fā)送碼組為101的可能性很小(因?yàn)?個(gè)誤碼的概率一般很小)，但不能絕對(duì)排除，即使傳輸過程中只發(fā)生一個(gè)誤碼，也有三種可能的發(fā)送碼組即000、011和110。106如果選其中000、011、101、1

假如我們進(jìn)一步將許用碼組限制為二種即000和111，顯然這樣可以發(fā)現(xiàn)所有2位以下的誤碼，若用來糾錯(cuò)，可以用最大似然準(zhǔn)則糾正1位錯(cuò)誤?？梢杂靡粋€(gè)三維立方體來表示上述3位二進(jìn)制碼組的例子，如圖10.2.3所示。圖中立方體各頂點(diǎn)分別表示8位碼組，3位碼元依次表示x、y、z軸的坐標(biāo)。107假如我們進(jìn)一步將許用碼組限制為二種即10818

這里定義碼組中非零碼元的數(shù)目為碼組的重量，簡(jiǎn)稱碼重。比如100碼組的碼重為1，101碼組的碼重為2。定義兩個(gè)碼組中對(duì)應(yīng)碼位上具有不同二進(jìn)制碼元的位數(shù)為兩碼組的距離，稱為漢明(Hamming)距，簡(jiǎn)稱碼距。在前面3位二進(jìn)制碼組的例子中，當(dāng)8種碼組均為許用碼組時(shí)，兩碼組間的最小距離為1，稱這種編碼的最小碼距為1，一般記為dmin=l；當(dāng)選4種碼組為許用碼組時(shí)，最小碼距dmin

=2；當(dāng)用2種碼組作為許用碼組時(shí)，dmin=3。109這里定義碼組中非零碼元的數(shù)目為碼組的

從圖10.2.3所示的立方體可以看出，碼距就是從一個(gè)頂點(diǎn)沿立方體各邊移到另一個(gè)頂點(diǎn)所經(jīng)過的最少邊數(shù)。圖中粗線表示000與111之間的一條最短路徑。很容易得出前例中各種情況下的碼距。根據(jù)以上分析可知，編碼的最小碼距直接關(guān)系到這種碼的檢錯(cuò)和糾錯(cuò)能力，所以最小碼距是差錯(cuò)控制編碼的一個(gè)重要參數(shù)。對(duì)于分組碼一般有以下結(jié)論:110從圖10.2.3所示的立方體可以看出

1.在一個(gè)碼組內(nèi)檢測(cè)e個(gè)誤碼，要求最小碼距dmin≥e+1(10.2.2)2.在一個(gè)碼組內(nèi)糾正t個(gè)誤碼，要求最小碼距dmin≥2t+1(10.2.3)3.在一個(gè)碼組內(nèi)糾正t個(gè)誤碼，同時(shí)檢測(cè)e(e≥t)個(gè)誤碼，要求最小碼距dmin≥t+e+1(10.2.4)這些結(jié)論可以用圖10.2.4所示的幾何圖形簡(jiǎn)單的給予證明。1111.在一個(gè)碼組內(nèi)檢測(cè)e個(gè)誤碼，要求11222

可見dmin體現(xiàn)了碼組的糾、檢錯(cuò)能力。碼組間最小距離越大，說明碼字間最小差別越大，抗干擾能力就越強(qiáng)。

由于編碼系統(tǒng)具有糾錯(cuò)能力，因此在達(dá)到同樣誤碼率要求時(shí)，編碼系統(tǒng)會(huì)使所要求的輸入信噪比低于非編碼系統(tǒng)，為此引入了編碼增益的概念。其定義為，在給定誤碼率下，非編碼系統(tǒng)與編碼系統(tǒng)之間所需信噪比Eb/N0之差(用dB表示)。采用不同的編碼會(huì)得到不同的編碼增益，但編碼增益的提高要以增加系統(tǒng)帶寬或復(fù)雜度來換取。113可見dmin體現(xiàn)了碼組的糾、檢錯(cuò)能

10.2.4常用的簡(jiǎn)單檢錯(cuò)碼

常用檢錯(cuò)碼的結(jié)構(gòu)一般都很簡(jiǎn)單，由于這些碼組具有較強(qiáng)的檢錯(cuò)能力，并且易于實(shí)現(xiàn)，所以在實(shí)際當(dāng)中應(yīng)用很廣泛。

1．奇偶校驗(yàn)碼奇偶校驗(yàn)碼又稱奇偶監(jiān)督碼，它只有一個(gè)監(jiān)督碼元，是一種最簡(jiǎn)單的檢錯(cuò)碼，在計(jì)算機(jī)數(shù)據(jù)傳輸中得到廣泛應(yīng)用。編碼時(shí)，首先將要傳送的信息分組，按每組中“1”碼的個(gè)數(shù)計(jì)算監(jiān)督碼元的值。編碼后，整個(gè)碼組中“1”碼個(gè)數(shù)成為奇數(shù)的稱奇校驗(yàn)，成為偶數(shù)的稱偶校驗(yàn)。11410.2.4常用的簡(jiǎn)單檢錯(cuò)碼

設(shè)碼組長度為n，其中前n-1位(an-1,an-2

,?,a1)是信息碼元，a0是監(jiān)督碼元，二者之間的監(jiān)督關(guān)系可用公式表示。

奇校驗(yàn)滿足

偶校驗(yàn)滿足(10.2.6)(10.2.5)115設(shè)碼組長度為n，其中前n-1位(a

接收端用一個(gè)模2加法器就可以完成檢錯(cuò)工作。當(dāng)錯(cuò)碼為一個(gè)或奇數(shù)個(gè)時(shí)，因打亂了“1”數(shù)目的奇偶性，故能發(fā)現(xiàn)差錯(cuò)。然而，當(dāng)錯(cuò)誤個(gè)數(shù)為偶數(shù)時(shí)，由于未破壞“l(fā)”數(shù)目的奇偶性，所以不能發(fā)現(xiàn)偶數(shù)個(gè)錯(cuò)碼。116接收端用一個(gè)模2加法器就可以完成檢錯(cuò)

2．行列監(jiān)督碼

行列監(jiān)督碼也叫方陣校驗(yàn)碼，編碼原理與簡(jiǎn)單的奇偶監(jiān)督碼相似，不同之處在于每個(gè)碼元都要受到縱、橫兩個(gè)方向的監(jiān)督。以圖10.2.5為例，有28個(gè)待發(fā)送的數(shù)據(jù)碼元，將它們排成4行7列的方陣。方陣中每行是一個(gè)碼組，每行的最后加上一個(gè)監(jiān)督碼元進(jìn)行行監(jiān)督，同樣在每列的最后也加上一個(gè)監(jiān)督碼元進(jìn)行列監(jiān)督，然后按行(或列)發(fā)送。接收端按同樣行列排成方陣，發(fā)現(xiàn)不符合行列監(jiān)督規(guī)則的判為有錯(cuò)。它除了能檢出所有行、列中的奇數(shù)個(gè)錯(cuò)誤外，也能發(fā)現(xiàn)大部分偶數(shù)個(gè)錯(cuò)誤。因?yàn)槿绻龅讲铄e(cuò)個(gè)數(shù)恰為4的倍數(shù)，而且差錯(cuò)位置正好處于矩形四個(gè)角的情況，方陣碼無法發(fā)現(xiàn)錯(cuò)誤。117

11828

行列監(jiān)督碼在某些條件下還能糾錯(cuò)，觀察第3行、第4列出錯(cuò)的情況，假設(shè)在傳輸過程中第3行、第4列的“1”錯(cuò)成“0”，由于此錯(cuò)誤同時(shí)破壞了第3行、第4列的偶監(jiān)督關(guān)系，所以接收端很容易判斷是3行4列交叉位置上的碼元出錯(cuò)，從而給予糾正。

行列監(jiān)督碼也常用于檢查或糾正突發(fā)錯(cuò)誤。它可以檢查出錯(cuò)誤碼元長度小于和等于碼組長度的所有錯(cuò)碼，并糾正某些情況下的突發(fā)差錯(cuò)。

行列監(jiān)督碼實(shí)質(zhì)上是運(yùn)用矩陣變換，把突發(fā)差錯(cuò)變成獨(dú)立差錯(cuò)加以處理。因?yàn)檫@種方法比較簡(jiǎn)單，所以被認(rèn)為是克制突發(fā)差錯(cuò)很有效的手段。119行列監(jiān)督碼在某些條件下還能糾錯(cuò)，觀

3.恒比碼

恒比碼又稱等比碼或等重碼。恒比碼的每個(gè)碼組中，“1”和“0”的個(gè)數(shù)比是恒定的。我國電傳通信中采用的五單位數(shù)字保護(hù)電碼是一種3∶2等比碼，也叫五中取三的恒比碼，即在5單位電傳碼的碼組中(25=32)，取其“1”的數(shù)目恒為3的碼組(C53=10)，代表10個(gè)字符(0～9)，如表10.2.1所示。因?yàn)槊總€(gè)漢字是以四位十進(jìn)制數(shù)表示的，所以提高十進(jìn)制數(shù)字傳輸?shù)目煽啃?，相?dāng)于提高了漢字傳輸?shù)目煽啃浴?203.恒比碼30

國際電傳電報(bào)上通用的ARQ通信系統(tǒng)中，選用三個(gè)“1”、四個(gè)“0”的3:4碼，即七中取三碼。它有C73=35個(gè)碼組，分別表示26個(gè)字母及其他符號(hào)。

在檢測(cè)恒比碼時(shí)，通過計(jì)算接收碼組中“1”的數(shù)目，判定傳輸有無錯(cuò)誤。除了“1”錯(cuò)成“0”和“0”錯(cuò)成“1”成對(duì)出現(xiàn)的錯(cuò)誤以外，這種碼能發(fā)現(xiàn)其他所有形式的錯(cuò)誤，因此檢錯(cuò)能力很強(qiáng)。實(shí)踐證明，應(yīng)用這種碼，國際電報(bào)通信的誤碼率保持在10-6以下。12131

4.ISBN國際統(tǒng)一圖書編號(hào)

國際統(tǒng)一圖書編號(hào)是一種檢錯(cuò)碼，以防止書號(hào)在通信過程中發(fā)生誤傳。這里以編號(hào)ISBN0-1315-2447-X為例，其中第一位數(shù)字“0”表示該書是美國及其它英語國家的出版物(中國的代號(hào)是數(shù)字“7”)，“1315”代表出版公司，“2447”代表書名編號(hào)，最后一位數(shù)字“X”是校驗(yàn)位(這是10的羅馬字表示)。這里采用的校驗(yàn)方法如圖10.2.6所示。1224.ISBN國際統(tǒng)一圖書編號(hào)3212333

圖中第1行為ISBN編號(hào)。第2行第1個(gè)數(shù)字與第1行第1個(gè)數(shù)字相同；第2行第2個(gè)數(shù)字則為第1行第2個(gè)數(shù)字與第2行第1個(gè)數(shù)字之和，即1+0=1；第2行第3個(gè)數(shù)字為第1行第3個(gè)數(shù)字與第2行第2個(gè)數(shù)字之和，即3+1=4；依次類推，第2行最后所得的累計(jì)和為37。用同樣方法得到第3行的最后累計(jì)和為132。然后用模11對(duì)132進(jìn)行校驗(yàn)，132(mod11)≡0。

顯然，若通信過程中統(tǒng)一書號(hào)發(fā)生了錯(cuò)誤，則上累計(jì)和就不能被11所整除，從而可校驗(yàn)出來。124圖中第1行為ISBN編號(hào)。第2行第10.3線性分組碼

10.3.1基本概念

一個(gè)長為n的分組碼，碼字由兩部分構(gòu)成，即信息碼元(k位)+監(jiān)督碼元(r位)。監(jiān)督碼元是根據(jù)一定規(guī)則由信息碼元變換得到的，變換規(guī)則不同就構(gòu)成不同的分組碼。如果監(jiān)督位為信息位的線性組合，就稱其為線性分組碼。

要從k個(gè)信息碼元中求出r個(gè)監(jiān)督碼元，必須有r個(gè)獨(dú)立的線性方程。根據(jù)不同的線性方程，可得到不同的(n,k)線性分組碼。12510.3線性分組碼10.3.1基本概念35

例如，已知一個(gè)(7，4)線性分組碼，4個(gè)信息碼元a6、a5、a4、a3和3個(gè)監(jiān)督碼元a2、a1、a0之間符合以下規(guī)則

計(jì)算上式得到此(7