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

9.1信道編碼的概念

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

信道編碼器要對信源編碼輸出的符號進行變換，使其盡量少受噪聲干擾的影響，減少傳輸差錯，提高通信可靠性。進行信道編碼是為了提高信號傳輸?shù)目煽啃裕纳仆ㄐ畔到y(tǒng)的傳輸質(zhì)量，研究信道編碼的目標是尋找具體構(gòu)造編碼的理論與方法。

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

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

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

9.2信道編碼的分類

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

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

檢錯與糾錯原理

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

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

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

9.3檢重復碼和奇偶校驗碼

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

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

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

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

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

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

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

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

定義：對信源編碼器輸出的二進制序列進行分組，設分組長度為，相應的碼字表示為：

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

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

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

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

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

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

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

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

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

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

例3求例2所述碼的對偶碼。顯然，碼的對偶碼應是碼，由對偶碼的定義得：碼的矩陣就是碼的矩陣，將其化成標準形式后即可得到碼的對偶碼碼，如表9.3所示。表9.3信息碼元碼字信息碼元碼字000000000001000100010100010001011100110011100010001011010101010011001100111011011101100001000100111110011000100101010110011011101001011001100011110111010001110111010111111111119.3.3線性分組碼的譯碼

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

例3計算例2所述碼

一致校驗矩陣為：接收（1010011）伴隨式為

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

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