第9章 信道(糾錯(cuò))編碼

第9章信道（糾錯(cuò)）編碼信息傳輸要通過各種物理信道，由于干擾、設(shè)備故障等影響，被傳送的信源符號(hào)可能會(huì)發(fā)生失真，使有用信息遭受損壞，接收信號(hào)造成誤判。這種在接收端錯(cuò)誤地確定所接收的信號(hào)叫做差錯(cuò)。為了提高信息傳輸?shù)臏?zhǔn)確性，使其具有較好的抵抗信道中噪聲干擾的能力，在通信系統(tǒng)中需要采用專門的檢、糾錯(cuò)誤方法，即差錯(cuò)控制。

9.1信道編碼的概念

差錯(cuò)控制的任務(wù)是發(fā)現(xiàn)所產(chǎn)生的錯(cuò)誤、并指出發(fā)生錯(cuò)誤的信號(hào)或者校正錯(cuò)誤，差錯(cuò)控制是采用可靠、有效的信道編碼方法來實(shí)現(xiàn)的。

信道編碼器要對(duì)信源編碼輸出的符號(hào)進(jìn)行變換，使其盡量少受噪聲干擾的影響，減少傳輸差錯(cuò)，提高通信可靠性。進(jìn)行信道編碼是為了提高信號(hào)傳輸?shù)目煽啃?，改善通信系統(tǒng)的傳輸質(zhì)量，研究信道編碼的目標(biāo)是尋找具體構(gòu)造編碼的理論與方法。

與糾錯(cuò)編碼有關(guān)的基本定義：(1)碼長(zhǎng)、碼重和碼距碼字中碼元的個(gè)數(shù)稱為碼字的長(zhǎng)度，簡(jiǎn)稱碼長(zhǎng)，用表示。碼字中非“0”碼元的個(gè)數(shù)稱為碼字的漢明重量(簡(jiǎn)稱碼重，記作)。對(duì)二進(jìn)制碼來說，碼重就是碼字中所含碼元“1”的數(shù)目，例如碼字“110000”，其碼長(zhǎng)碼重兩個(gè)等長(zhǎng)碼字之間對(duì)應(yīng)碼元不相同的數(shù)目稱為這兩個(gè)碼組的漢明距離(簡(jiǎn)稱碼距)。例如碼字“110000”與“100001”，它們的漢明距離。在某一碼書中，任意兩個(gè)碼字之間漢明距離的最小值稱為該碼的最小距離，即：碼組的最小碼距從避免碼字受干擾而出錯(cuò)的角度出發(fā)，總是希望碼字間有盡可能大的距離，因?yàn)樽钚〈a距代表著一個(gè)碼組中最不利的情況，應(yīng)使用最小碼距來分析碼的檢錯(cuò)糾錯(cuò)能力。最小碼距是衡量該碼糾錯(cuò)能力的依據(jù)，是非常重要。檢錯(cuò)與糾錯(cuò)能力：定理：若糾錯(cuò)碼的最小距離為，那么如下三個(gè)結(jié)論的任何一個(gè)結(jié)論獨(dú)立成立：①若要發(fā)現(xiàn)個(gè)獨(dú)立差錯(cuò)，則要求最小碼距②若要糾正個(gè)獨(dú)立差錯(cuò)，則要求最小碼距③若要求發(fā)現(xiàn)e個(gè)同時(shí)又糾正t個(gè)獨(dú)立差錯(cuò)，則；定理說明，碼的最小距離越大，碼的糾(檢)錯(cuò)誤的能力越強(qiáng)。但是，隨著多余碼元的增多，信息傳輸速率會(huì)降低得越多。通常用來表示碼字中信息碼元所占的比例，稱為編碼效率，簡(jiǎn)稱碼率，它是衡量碼性能的又一個(gè)重要參數(shù)。碼率越高，信息傳輸率就越高，但此時(shí)糾錯(cuò)能力要降低，若時(shí)就沒有糾錯(cuò)能力了。可見，碼率與糾錯(cuò)能力之間是有矛盾的。

(2)錯(cuò)誤圖樣差錯(cuò)的形式也可以用二元序列來描述。設(shè)發(fā)送碼字為，接收碼字為，兩者的差別:

稱為錯(cuò)誤圖樣。如錯(cuò)誤圖樣中的第位為“1”()，則表明傳輸過程中第位發(fā)生了錯(cuò)誤。例如：，而，則，可知接收的消息序列中的第“2”位和第“6”位出現(xiàn)了錯(cuò)誤。

9.2信道編碼的分類

有些實(shí)際信道既有獨(dú)立隨機(jī)差錯(cuò)也有突發(fā)性成串的差錯(cuò)，這種信道稱混合差錯(cuò)信道，實(shí)際的移動(dòng)信道屬于此類信道。對(duì)應(yīng)的信道編碼可分為：以糾獨(dú)立隨機(jī)差錯(cuò)為主的信道編碼、以糾突發(fā)差錯(cuò)為主的信道編碼和糾混合差錯(cuò)的信道編碼。從功能上看，信道編碼可分為檢錯(cuò)(可以發(fā)現(xiàn)錯(cuò)誤)碼與糾錯(cuò)(不僅能發(fā)現(xiàn)而且能自動(dòng)糾正)碼兩類，糾錯(cuò)碼一定能檢錯(cuò)，檢錯(cuò)碼不一定能糾錯(cuò)，平常所說的糾錯(cuò)碼是兩者的統(tǒng)稱。

根據(jù)信息碼元與監(jiān)督碼元之間的關(guān)系，糾錯(cuò)碼分為線性碼和非線性碼。線性碼——信息碼元與監(jiān)督碼元之間呈線性關(guān)系，關(guān)系可用一組線性代數(shù)方程聯(lián)系起來。非線性碼——信息碼元與監(jiān)督校元之間非線性關(guān)系。按照對(duì)信息碼元處理的方法的不同，糾錯(cuò)碼分為分組碼和卷積碼。分組碼----把信息序列以每個(gè)碼元分組，然后把每組個(gè)信息元按一定規(guī)律產(chǎn)生個(gè)多余的監(jiān)督碼元，輸出序列每組長(zhǎng)為，則每一碼字的個(gè)校驗(yàn)元只與本碼字的個(gè)信息位有關(guān)，與別的碼字的信息位無關(guān)，通常記分組碼為。

檢錯(cuò)與糾錯(cuò)原理

檢錯(cuò)、糾錯(cuò)的目的是要根據(jù)信道接收端接收到的信息序列來判斷是否就是發(fā)送的序列，如果有錯(cuò)則盡可能糾正其中的錯(cuò)誤。要糾正傳輸差錯(cuò)，首先必須檢測(cè)出錯(cuò)誤。而要檢測(cè)出錯(cuò)誤，常用的方法是將發(fā)送端要傳送的信息序列(常為二進(jìn)制序列)中截取出長(zhǎng)度相等的碼元進(jìn)行分組，每組長(zhǎng)度為k，組成k位碼元信息序列 并根據(jù)某種編碼算法以一定的規(guī)則在每個(gè)信息組的后面產(chǎn)生個(gè)冗余碼元，由冗余碼元和信息碼元一起形成“位編碼序列有，因而糾錯(cuò)編碼是冗余編碼，如圖6.1所示。圖6.1糾錯(cuò)編碼通常，將分組碼規(guī)定為具有如圖6.2所示的結(jié)構(gòu)。圖中前面位()為信息位，后面附加個(gè)()校驗(yàn)位。圖6.2檢錯(cuò)與糾錯(cuò)方式和能力：圖6.3所示為幾種檢錯(cuò)與糾錯(cuò)方式示意圖。

圖6.3ARQ方式：發(fā)送端用編碼器對(duì)發(fā)送數(shù)據(jù)進(jìn)行差錯(cuò)編碼，通過正向信道送到接收端，而接收端經(jīng)譯碼器處理后只是檢測(cè)有無差錯(cuò)，不作自動(dòng)糾正。如檢測(cè)到差錯(cuò)，則利用反向信道反饋，請(qǐng)求發(fā)送端重發(fā)有錯(cuò)的數(shù)據(jù)單元，直到接收端檢測(cè)不到差錯(cuò)為止。FEC方式：發(fā)送端用編碼器對(duì)發(fā)送數(shù)據(jù)進(jìn)行差錯(cuò)編碼，在接收端用譯碼器對(duì)接收到的數(shù)據(jù)進(jìn)行譯碼后檢測(cè)有無差錯(cuò)，如檢測(cè)到差錯(cuò)，則確定差錯(cuò)的具體位置和性質(zhì)，自動(dòng)加以糾正，故稱為“前向糾錯(cuò)”。HEC方式：是檢錯(cuò)重發(fā)和前向糾錯(cuò)兩種方式的混合。發(fā)送端用編碼器對(duì)發(fā)送數(shù)據(jù)進(jìn)行便于檢錯(cuò)和糾錯(cuò)的編碼，通過正向信道送到接收端，接收端對(duì)少量的接收差錯(cuò)進(jìn)行自動(dòng)前向糾正，而對(duì)超出糾正能力的差錯(cuò)則通過反饋重發(fā)方式加以糾正，所以是一種糾檢結(jié)合的混合方式。 前面已述信道編碼的任務(wù)是構(gòu)造出以最小多余度的代價(jià)換取最大抗干擾性的“好“碼。下面，從直觀概念出發(fā)，說明多余度與抗干擾性能的關(guān)系，介紹兩種極端情況：一是高可靠性，低有效性的重復(fù)碼；二是高有效性，低可靠性的奇偶校驗(yàn)碼。重復(fù)碼

構(gòu)成重復(fù)碼的方法是當(dāng)發(fā)送某個(gè)信源符號(hào)時(shí)，不是只發(fā)一個(gè)，而是連續(xù)重發(fā)多個(gè)，連續(xù)重發(fā)的個(gè)數(shù)越多，重復(fù)碼的抗干擾能力就越強(qiáng)，當(dāng)然效率也越低。

9.3檢重復(fù)碼和奇偶校驗(yàn)碼

不重復(fù)時(shí)為(1，1)重復(fù)碼，如圖6.4所示:圖6.4發(fā)送碼元不重復(fù)

對(duì)這種情況可得結(jié)論：不重復(fù)，方法簡(jiǎn)單，但沒有任何抗干擾能力，既不能發(fā)現(xiàn)，更不能糾正錯(cuò)誤。重復(fù)一次時(shí)為(2，1)重復(fù)碼，如圖6.5所示:圖6.5發(fā)送碼元重復(fù)一次

結(jié)論：重發(fā)一次，效率降低一倍，可以發(fā)現(xiàn)一個(gè)錯(cuò)誤(收端能發(fā)現(xiàn)它)，但不能糾正這個(gè)錯(cuò)誤。重復(fù)二次時(shí)為(3，1)重復(fù)碼，(3，1)重復(fù)碼用“000”來代表信息“0”，用“111”來代表信息“1”，顯然，所增加的兩位碼元并不會(huì)增加信息，是多余的，因而使信息傳輸率降低。當(dāng)信道上信噪比足夠大時(shí)，我們可以認(rèn)為碼字中產(chǎn)生的錯(cuò)誤一般不多于一個(gè)碼元，那么，如果接收到“001”、“010”、“100”，我們就可判定實(shí)際傳輸?shù)氖恰?00”；同樣，如接收到“011”、“101”、“110”，則可判定為“111”。因此多余碼元使我們可檢出一個(gè)錯(cuò)，并且還可糾正這個(gè)錯(cuò)誤，這樣就提高了信息傳輸?shù)目煽啃?。結(jié)論：重發(fā)二次，效率降低二倍，但換取了可糾正一個(gè)差錯(cuò)或發(fā)現(xiàn)兩個(gè)差錯(cuò)的性能改善。2)奇偶檢驗(yàn)碼

奇偶校驗(yàn)是一種最基本的校驗(yàn)方法。構(gòu)成奇偶檢驗(yàn)碼的方法是在每個(gè)二進(jìn)制信息位后加上一個(gè)奇(偶)監(jiān)督位(或稱校驗(yàn)位)，使碼長(zhǎng)，同時(shí)使碼中“1”的個(gè)數(shù)恒為奇數(shù)(或偶數(shù))，如圖6.6所示。在奇偶校驗(yàn)碼中，監(jiān)督位，它是一種碼重為奇數(shù)(或偶數(shù))的系統(tǒng)分組碼。如圖6.6奇偶校驗(yàn)又可以分為奇校驗(yàn)和偶校驗(yàn)。其規(guī)則如下：奇校驗(yàn)----如果信息碼元中“1”值的個(gè)數(shù)為奇數(shù)個(gè)，則校驗(yàn)碼元值為“0”；如果信息碼元中“1”值的個(gè)數(shù)為偶數(shù)個(gè)，則校驗(yàn)碼元值為“1”。即所有信息碼元與校驗(yàn)碼元的模二和等于“1”。

偶校驗(yàn)----如果信息碼元中“1”值的個(gè)數(shù)為偶數(shù)個(gè)，則校驗(yàn)碼元值為“0”；如果信息碼元中“1”值的個(gè)數(shù)為奇數(shù)個(gè)，則校驗(yàn)碼元值為“1”。即所有信息碼元與校驗(yàn)碼元的模二和等于“0”。根據(jù)奇偶校驗(yàn)的規(guī)則，校驗(yàn)位值的確定方法如表6.1所示。

表6.1奇偶校驗(yàn)規(guī)則表

校驗(yàn)方式信息位中“1”值的個(gè)數(shù)校驗(yàn)位值奇校驗(yàn)奇數(shù)個(gè)0偶數(shù)個(gè)1偶校驗(yàn)偶數(shù)個(gè)0奇數(shù)個(gè)1例如，在七位信息碼中，字符A的代碼為1000001，其中有兩位碼元值為“1”。若采用奇校驗(yàn)編碼，由于這個(gè)字符的七位代碼中有偶數(shù)個(gè)“1”，所以校驗(yàn)位的值應(yīng)為“l(fā)”，其8位組合代碼為：10000011，前7位是信息位，最右邊的1位是校驗(yàn)位。同理，若采用偶校驗(yàn)，可得奇偶校驗(yàn)位的值為“0”，其8位組合代碼為：10000010。這樣在接收端對(duì)碼字中“1”的個(gè)數(shù)進(jìn)行檢驗(yàn)，如有不符，就可斷定發(fā)生了差錯(cuò)。在接收端進(jìn)行校驗(yàn)時(shí)，如采用奇校驗(yàn)編碼，當(dāng)接收到的字符經(jīng)檢測(cè)其八位代碼“l(fā)”的個(gè)數(shù)為奇?zhèn)€數(shù)時(shí)，則被認(rèn)為傳輸正確；否則就被認(rèn)為傳輸中出現(xiàn)差錯(cuò)。然而，如果在傳輸中有偶數(shù)位出現(xiàn)差錯(cuò)，用此方法就檢測(cè)不出來了。所以，奇偶校驗(yàn)方式只能檢測(cè)出位代碼中出現(xiàn)的任意奇數(shù)個(gè)錯(cuò)誤，如果代碼中錯(cuò)碼數(shù)為偶數(shù)個(gè)，則奇偶校驗(yàn)不能奏效。由于奇偶校驗(yàn)碼容易實(shí)現(xiàn)，所以當(dāng)信道干擾不太嚴(yán)重以及碼長(zhǎng)不很長(zhǎng)時(shí)很有用，特別是在計(jì)算機(jī)通信網(wǎng)的數(shù)據(jù)傳送中經(jīng)常應(yīng)用這種檢錯(cuò)碼。9.3線性分組碼

線性分組碼是糾錯(cuò)碼中非常重要的一類碼，雖然對(duì)于同樣碼長(zhǎng)的非線性碼來說線性碼可用碼字較少，但由于線性碼的編碼和譯碼容易實(shí)現(xiàn)，而且是討論其他各類碼的基礎(chǔ)，至今仍是廣泛應(yīng)用的一類碼。9.3.1線性分組碼的基本概念

定義：對(duì)信源編碼器輸出的二進(jìn)制序列進(jìn)行分組，設(shè)分組長(zhǎng)度為，相應(yīng)的碼字表示為：

信道編碼(糾錯(cuò)編碼)的目的是將信息碼字進(jìn)行變換，使其成為以下形式：

其中：，我們稱全體碼字的集合為分組碼。若由到之間的變換為線性變換，則稱全體碼字的集合為線性分組碼，常用線性分組碼表示全體碼字的集合.例1設(shè)信源編碼器輸出的信息序列為，其中是二進(jìn)制數(shù)。信道編碼器輸出的碼字，其中也是二進(jìn)制數(shù)。若從到的變換規(guī)則為：由于從到的變換是一種線性變換，所以全體的集合構(gòu)成了一種線性分組碼。

由本例可以看出，變換后碼字集合中每一個(gè)碼字的所有碼元之和為：因?yàn)榧僭O(shè)了碼為二進(jìn)制碼，上述碼元的和是模2和。因此，變換后將每一個(gè)碼字的碼元全部加起來，它的模2和為“0”，即每一個(gè)碼字中“1”的個(gè)數(shù)為偶數(shù)個(gè)，所以這種碼為偶校驗(yàn)碼。

6.3.2校驗(yàn)矩陣和生成矩陣?yán)?分組碼，按以下的規(guī)則(校驗(yàn)方程)可得到四個(gè)校驗(yàn)元：式中：是三個(gè)信息碼元，方程中的加運(yùn)算均為模2加。由此可得到分組碼的八個(gè)碼字，列于表6.2中。由校驗(yàn)方程看到，信息碼元與校驗(yàn)碼元滿足線性關(guān)系，因此是線性碼。

生成矩陣:線性分組碼校驗(yàn)方程可寫成矩陣形式。式中G稱線性分組碼的生成矩陣。

表9.2：例2編出的線性碼的碼字與信息碼元的對(duì)應(yīng)關(guān)系

信息碼元碼字00000000000010011101010010011101101110101001001110101101001111011010011111110100一致校驗(yàn)矩陣由校驗(yàn)碼元與信息碼元的關(guān)系，可得：即：易得：

由此關(guān)系可知，

這說明，的第一行就是的第一列，的第二行就是的第二列，……，因此，矩陣一旦確定，則矩陣也就確定，反之亦然。=對(duì)偶碼

我們已經(jīng)討論了線性分組碼的生成矩陣與其對(duì)應(yīng)的一致校驗(yàn)矩陣，如果把碼的一致校驗(yàn)矩陣看成是碼的生成矩陣，將碼的生成矩陣看成是碼的一致校驗(yàn)矩陣，則稱這兩種碼互為對(duì)偶碼。

例3求例2所述碼的對(duì)偶碼。顯然，碼的對(duì)偶碼應(yīng)是碼，由對(duì)偶碼的定義得：碼的矩陣就是碼的矩陣，將其化成標(biāo)準(zhǔn)形式后即可得到碼的對(duì)偶碼碼，如表9.3所示。表9.3信息碼元碼字信息碼元碼字000000000001000100010100010001011100110011100010001011010101010011001100111011011101100001000100111110011000100101010110011011101001011001100011110111010001110111010111111111119.3.3線性分組碼的譯碼

只要找到矩陣或矩陣，便解決了編碼問題。經(jīng)編碼后發(fā)送的碼字，由于信道干擾可能出錯(cuò)，接收方怎樣發(fā)現(xiàn)或糾正錯(cuò)誤呢，這就是譯碼要解決的問題。定義——設(shè)碼的一致校驗(yàn)矩陣為，是發(fā)送碼字為時(shí)接收序列，為接收序列的伴隨式或校正子。伴隨式是一致校驗(yàn)矩陣的線性組合，如果錯(cuò)誤圖樣中有一些分量不為“0”，則在中正好就是中不為“0”的那幾列組合而成。由上面的分析，可得如下結(jié)論：①從式(6.2.7)可知伴隨式僅與錯(cuò)誤圖樣有關(guān)，它充分反映了信道受干擾的情況，而與發(fā)送的是什么碼字無關(guān)。②伴隨式是是否有錯(cuò)的判別式，若，則判沒有出錯(cuò)；若，則判有錯(cuò)。③不同的錯(cuò)誤圖樣具有不同的伴隨式，它們是一一對(duì)應(yīng)的，對(duì)二元碼來說，伴隨式即為矩陣中與錯(cuò)誤圖樣對(duì)應(yīng)的各列之和。注意，如果錯(cuò)誤圖樣本身就是一個(gè)碼字，即，那么計(jì)算伴隨式得到的結(jié)果必為“0”，此時(shí)的錯(cuò)誤不能發(fā)現(xiàn)，也無法糾正，因而這樣的錯(cuò)誤圖樣稱為不可檢錯(cuò)誤圖樣。

例3計(jì)算例2所述碼

一致校驗(yàn)矩陣為：接收（1010011）伴隨式為

因此，譯碼器判別接收序列無錯(cuò)，傳輸中沒有發(fā)生錯(cuò)誤。當(dāng)（1110011）接收時(shí)，接收端譯碼器根據(jù)接收序列計(jì)算的伴隨式為:

由于，所以譯碼器判別接收序列有錯(cuò)，傳輸中有錯(cuò)誤發(fā)生。碼是糾正單個(gè)錯(cuò)誤的碼，觀察即為的第二列，因此可判定接收序列的第二位發(fā)生了錯(cuò)誤。由于接收序列中錯(cuò)誤個(gè)數(shù)與碼的糾錯(cuò)能力相符，所以可正確譯碼，發(fā)送碼字應(yīng)為當(dāng)接收時(shí)，接收端譯碼器根據(jù)接收序列計(jì)算的伴隨式為：，但與的任何一列都不相同，無法判別錯(cuò)誤發(fā)生在哪些位上，此時(shí)只能發(fā)現(xiàn)有錯(cuò)。例題：已知：求H、糾錯(cuò)能力。9.4卷積碼卷積碼由埃利