1、第第 10 章章 差錯(cuò)控制編碼差錯(cuò)控制編碼 10.1 概述概述 10.2 常用的幾種簡(jiǎn)單分組碼常用的幾種簡(jiǎn)單分組碼 10.3 線性分組碼線性分組碼 10.4 循環(huán)碼循環(huán)碼 10.5 卷積碼卷積碼 *10.6 網(wǎng)格編碼調(diào)制網(wǎng)格編碼調(diào)制 10.1 概概 述述 10.1.1 信道編碼信道編碼 在數(shù)字通信中，根據(jù)不同的目的，編碼可分為信源編碼信源編碼和信道編碼信道編碼。信源編碼是為了提高數(shù)字信號(hào)的有效性有效性以及為了使模擬信號(hào)數(shù)字化而采取的編碼。信道編碼是為了降低誤碼率， 提高數(shù)字通信的可靠性而采取的編碼。 數(shù)字信號(hào)在傳輸過程中，加性噪聲、碼間串?dāng)_等都會(huì)產(chǎn)生誤碼。為了提高系統(tǒng)的抗干擾性能，可以加大發(fā)射

2、功率，降低接收設(shè)備本身的噪聲，以及合理選擇調(diào)制、解調(diào)方法等。此外，還可以采用信道編碼技術(shù)。10.1.2 差錯(cuò)控制方式差錯(cuò)控制方式 圖 10-1 差錯(cuò)控制方式 發(fā)端糾錯(cuò)碼收端前向糾錯(cuò)FEC發(fā)端檢錯(cuò)碼收端檢錯(cuò)重發(fā)ARQ判決信號(hào)發(fā)端檢錯(cuò)和糾錯(cuò)碼收端混合糾錯(cuò)HEC判決信號(hào) 1. 檢錯(cuò)重發(fā)方式檢錯(cuò)重發(fā)方式 檢錯(cuò)重發(fā)又稱自動(dòng)請(qǐng)求重傳自動(dòng)請(qǐng)求重傳方式，記作ARQ(Automatic Repeat Request)。 由發(fā)端送出能夠發(fā)現(xiàn)錯(cuò)誤的碼，由收端判決傳輸中無(wú)錯(cuò)誤產(chǎn)生，如果發(fā)現(xiàn)錯(cuò)誤，則通過反向信道把這一判決結(jié)果反饋給發(fā)端，然后，發(fā)端把收端認(rèn)為錯(cuò)誤的信息再次重發(fā)，從而達(dá)到正確傳輸?shù)哪康?。其特點(diǎn)是需要反饋信道

3、，譯碼設(shè)備簡(jiǎn)單，對(duì)突發(fā)錯(cuò)誤突發(fā)錯(cuò)誤和信道干擾較嚴(yán)信道干擾較嚴(yán)重重時(shí)有效， 但實(shí)時(shí)性差，主要在計(jì)算機(jī)數(shù)據(jù)通信中得到應(yīng)用。 2. 前向糾錯(cuò)方式前向糾錯(cuò)方式 前向糾錯(cuò)方式記作FEC(Forword ErrorCorrection)。發(fā)端發(fā)送能夠糾正錯(cuò)誤的碼，收端收到信碼后自動(dòng)地糾正傳輸中的錯(cuò)誤。其特點(diǎn)是單向傳輸，實(shí)時(shí)性好，但譯碼設(shè)備較復(fù)雜。 3. 混合糾錯(cuò)方式混合糾錯(cuò)方式 混合糾錯(cuò)方式記作HEC(Hybrid ErrorCorrection)是FEC和ARQ方式的結(jié)合。發(fā)端發(fā)送具有自動(dòng)糾錯(cuò)同時(shí)又具有檢錯(cuò)能力的碼。收端收到碼后，檢查差錯(cuò)情況，如果錯(cuò)誤在碼的糾錯(cuò)能力范圍以內(nèi)，則自動(dòng)糾錯(cuò)，如果超過了碼的糾

4、錯(cuò)能力， 但能檢測(cè)出來，則經(jīng)過反饋信道請(qǐng)求發(fā)端重發(fā)。這種方式具有自動(dòng)糾錯(cuò)和檢錯(cuò)重發(fā)的優(yōu)點(diǎn)，可達(dá)到較低的誤碼率，因此， 近年來得到廣泛應(yīng)用。 按照噪聲或干擾的變化規(guī)律，可把信道分為三類：隨隨機(jī)信道機(jī)信道、突發(fā)信道突發(fā)信道和混合信道混合信道。恒參高斯白噪聲信道是典型的隨機(jī)信道，其中差錯(cuò)的出現(xiàn)是隨機(jī)的，而且錯(cuò)誤之間是統(tǒng)計(jì)獨(dú)立的。具有脈沖干擾的信道是典型的突發(fā)信道， 錯(cuò)誤是成串成群出現(xiàn)的，即在短時(shí)間內(nèi)出現(xiàn)大量錯(cuò)誤。短波信道和對(duì)流層散射信道是混合信道的典型例子，隨機(jī)錯(cuò)誤和成串錯(cuò)誤都占有相當(dāng)比例。對(duì)于不同類型的信道，應(yīng)采用不同的差錯(cuò)控制方式。 10.1.3 糾錯(cuò)碼的分類糾錯(cuò)碼的分類 (1) 根據(jù)糾錯(cuò)碼各碼

5、組信息元和監(jiān)督元的函數(shù)關(guān)系，可分為線性碼和非線性碼。如果函數(shù)關(guān)系是線性的，即滿足一組線性方程式，則稱為線性碼線性碼，否則為非線性碼非線性碼。 (2) 根據(jù)信息元和監(jiān)督元的函數(shù)關(guān)系涉及的范圍，可分為分組碼分組碼和卷積碼卷積碼。分組碼的各碼元僅與本組的信息元有關(guān)；卷積碼中的碼元不僅與本組的信息元有關(guān)， 而且還與前面若干組的信息元有關(guān)。 (3) 根據(jù)碼的用途，可分為檢錯(cuò)碼檢錯(cuò)碼和糾錯(cuò)碼糾錯(cuò)碼。檢錯(cuò)碼以檢錯(cuò)為目的，不一定能糾錯(cuò)；而糾錯(cuò)碼以糾錯(cuò)為目的，一定能檢錯(cuò)。 10.2 糾錯(cuò)編碼的基本原理糾錯(cuò)編碼的基本原理 1. 分組碼分組碼- n個(gè)碼元成一組，稱為一個(gè)碼字。 分組碼一般可用(n,k)表示。其中，n

6、是編碼碼組的碼元總位數(shù)，又稱為碼組長(zhǎng)度，簡(jiǎn)稱碼長(zhǎng)碼長(zhǎng), k是每組二進(jìn)制信息碼元的數(shù)目。n-k=r為每個(gè)碼組中的監(jiān)督碼元數(shù)目。簡(jiǎn)單地說，分組碼是對(duì)每段k位長(zhǎng)的信息組以一定的規(guī)則增加r個(gè)監(jiān)督元， 組成長(zhǎng)為n的碼字。在二進(jìn)制情況下，共有 個(gè)不同的信息組，相應(yīng)地可得到 個(gè)不同的碼字，稱為許用碼組。其余 個(gè)碼字未被選用，稱為禁用碼組。 2k2k22nk 在分組碼中，非零碼元的數(shù)目稱為碼字的漢明重量漢明重量， 簡(jiǎn)稱碼重碼重。例如，碼字 10110，碼重w=3。 兩個(gè)等長(zhǎng)碼組之間相應(yīng)位取值不同的數(shù)目稱為這兩個(gè)碼組的漢明漢明(Hamming)距離距離， 簡(jiǎn)稱碼距碼距。例如 11000 與 10011之間的距離

7、d=3。碼組集中任意兩個(gè)碼字之間距離的最小值稱為碼的最小距離碼的最小距離，用d表示。最小碼距最小碼距是碼的一個(gè)重要參數(shù)， 它是衡量碼檢錯(cuò)、糾錯(cuò)能力的依據(jù)。 2. 檢錯(cuò)和糾錯(cuò)能力檢錯(cuò)和糾錯(cuò)能力 例如：重復(fù)碼重復(fù)碼-若分組碼碼字中的監(jiān)督元在信息元之后，而且是信息元的簡(jiǎn)單重復(fù)。 重復(fù)碼是一種簡(jiǎn)單實(shí)用的檢錯(cuò)碼， 并有一定的糾錯(cuò)能力。 (2,1)重復(fù)碼重復(fù)碼，兩個(gè)許用碼組是 00 與 11，d0=2，收端譯碼，出現(xiàn)01、10禁用碼組時(shí)，可以發(fā)現(xiàn)傳輸中的一位錯(cuò)誤。(3,1)重復(fù)碼重復(fù)碼，兩個(gè)許用碼組是 000 與111, d0=3; 當(dāng)收端出現(xiàn)兩個(gè)或三個(gè) 1 時(shí)，判為 1，否則判為 0。此時(shí)，可以糾正單個(gè)

8、錯(cuò)誤，或者該碼可以檢出兩個(gè)錯(cuò)誤。 碼的最小距離d0直接關(guān)系著碼的檢錯(cuò)和糾錯(cuò)能力；任一(n,k)分組碼，若要在碼字內(nèi): (1) 檢測(cè)e個(gè)隨機(jī)錯(cuò)誤，則要求碼的最小距離d0e+1; (2) 糾正t個(gè)隨機(jī)錯(cuò)誤， 則要求碼的最小距離d02t+1; (3) 糾正t個(gè)同時(shí)檢測(cè)e(t)個(gè)隨機(jī)錯(cuò)誤，則要求碼的最小距離d0t+e+1。 3. 編碼效率編碼效率 用差錯(cuò)控制編碼提高通信系統(tǒng)的可靠性， 是以降低有效性為代價(jià)換來的。我們定義編碼效率編碼效率R來衡量有效性:R=k/n其中, k是信息元的個(gè)數(shù)，n為碼長(zhǎng)。 對(duì)糾錯(cuò)碼的基本要求是糾錯(cuò)碼的基本要求是: 檢錯(cuò)和糾錯(cuò)能力盡量強(qiáng)； 編碼效率盡量高；編碼規(guī)律盡量簡(jiǎn)單。 實(shí)

9、際中要根據(jù)具體指標(biāo)要求， 保證有一定糾、檢錯(cuò)能力和編碼效率，并且易于實(shí)現(xiàn)。 10.3 常用的幾種簡(jiǎn)單分組碼常用的幾種簡(jiǎn)單分組碼10.3.1 奇偶監(jiān)督碼奇偶監(jiān)督碼 奇偶監(jiān)督碼是在原信息碼后面附加一個(gè)監(jiān)督元，使得碼組中“1”的個(gè)數(shù)是奇數(shù)或偶數(shù)?；蛘哒f，它是含一個(gè)監(jiān)督元，碼重為奇數(shù)或偶數(shù)的(n,n-1)系統(tǒng)分組碼系統(tǒng)分組碼。奇偶監(jiān)督碼又分為奇監(jiān)督碼和偶監(jiān)督碼。 設(shè)碼字A=an-1,an-2,a1,a0，對(duì)偶監(jiān)督碼有 00121aaaann 奇監(jiān)督碼情況相似， 只是碼組中“1”的數(shù)目為奇數(shù)， 即滿足條件 1021aaann而檢錯(cuò)能力檢錯(cuò)能力與偶監(jiān)督碼相同。 奇偶監(jiān)督碼的編碼效率R為 nnR/ ) 1(

10、 10.3.2 水平奇偶監(jiān)督碼水平奇偶監(jiān)督碼（克服不能檢測(cè)突發(fā)錯(cuò)誤的缺點(diǎn)） 110010100000100001101001111000011100111000001010101010111000111100信息碼元監(jiān)督元10.3.3 行列監(jiān)督碼行列監(jiān)督碼（克服不能發(fā)現(xiàn)偶數(shù)個(gè)錯(cuò)誤的缺點(diǎn)）圖 10-2 (66,50)行列監(jiān)督碼 11001010000010000110100111100001110011100000101010101011100011110010.3.4 群計(jì)數(shù)碼群計(jì)數(shù)碼 將信息碼元中“1”的個(gè)數(shù)用二進(jìn)制表示，放在信息元后面作為監(jiān)督元。如1010111，有5個(gè)1，監(jiān)督元為101，

11、所以群計(jì)數(shù)碼為101011110110.3.5 恒比碼恒比碼 碼字中 1 的數(shù)目與 0 的數(shù)目保持恒定比例的碼稱為恒比碼。 由于恒比碼中，每個(gè)碼組均含有相同數(shù)目的 1 和 0，因此恒比碼又稱等重碼等重碼，定定 1 碼碼。這種碼在檢測(cè)時(shí)，只要計(jì)算接收碼元中 1 的數(shù)目是否正確，就知道有無(wú)錯(cuò)誤。 目前我國(guó)電傳通信中普遍采用 3 2 碼，又稱“5 中取 3”的恒比碼，即每個(gè)碼組的長(zhǎng)度為 5，其中 3 個(gè)“1”。許用碼組恰好可表示 10 個(gè)阿拉伯?dāng)?shù)字，如表 10 - 1 所示。而每個(gè)漢字又是以四位十進(jìn)制數(shù)來代表的。實(shí)踐證明，采用這種碼后，我國(guó)漢字電報(bào)的差錯(cuò)率大為降低。 表表 10-3 3 2 恒比碼恒

12、比碼 10.4 線線 性性 分分 組組 碼碼 線性分組碼：每個(gè)監(jiān)督元都是某些信息元的模二和。如：(7,4)分組碼。設(shè)其碼字為A=a6 a5 a4 a3 a2 a1 a0，其中前 4 位是信息元，后 3 位是監(jiān)督元， 可用下列線性方程組來描述該分組碼，產(chǎn)生監(jiān)督元。 346035614562aaaaaaaaaaaa10.4.1 基本概念基本概念（10-4）表表 10-4 (7,4)碼的碼字表碼的碼字表 10.4.2 漢明碼漢明碼 一種用來糾正單個(gè)錯(cuò)誤的線性分組碼，監(jiān)督元個(gè)數(shù)r與碼字長(zhǎng)度n之間滿足關(guān)系：21rn 10.4.3 監(jiān)督矩陣監(jiān)督矩陣H(10-4) 其中,P為rk階矩陣，Ir為rr階單位矩陣

13、?？梢詫懗蒆=P Ir形式的矩陣稱為典型監(jiān)督矩陣。 HAT=0T，說明H矩陣與碼字的轉(zhuǎn)置乘積必為零，可以用來作為判斷接收碼字A是否出錯(cuò)的依據(jù)。 并簡(jiǎn)記為 將(10-4)補(bǔ)充為下列方程 10.4.4 生成矩陣生成矩陣G 可改寫為矩陣形式 1101000101010001100101110001GQIGkTPQ110101011111典型生成矩陣10.4.5 伴隨式伴隨式(校正子校正子)S和檢錯(cuò)和檢錯(cuò) 設(shè)發(fā)送碼組A=an-1,an-2,a1,a0，在傳輸過程中可能發(fā)生誤碼。接收碼組B=bn-1,bn-2,b1,b0，則收發(fā)碼組之差定義為錯(cuò)誤圖樣錯(cuò)誤圖樣E， 也稱為誤差矢量， 即 ABE其中E=en

14、-1,en-2,e1,e0，且 10ie當(dāng)bi=ai 當(dāng)biai (10 - 23) 式(10 - 23)也可寫作 EAB令S=BHT，稱為伴隨式或校正子。 TTTEHHEABHS)(表表 10-7 (7,4)碼碼S與與E的對(duì)應(yīng)關(guān)系的對(duì)應(yīng)關(guān)系 漢明碼的生成步驟：1.確定k和r2.選擇校正子S和錯(cuò)誤圖樣E的對(duì)應(yīng)關(guān)系3.列出r個(gè)監(jiān)督方程4.求監(jiān)督元（或者生成矩陣）10.5 循循 環(huán)環(huán) 碼碼 表表 10-8 (7,3)循環(huán)碼的全部碼組循環(huán)碼的全部碼組 10.5.1循環(huán)特性循環(huán)特性 在代數(shù)理論中，為了便于計(jì)算，常用碼多項(xiàng)式在代數(shù)理論中，為了便于計(jì)算，常用碼多項(xiàng)式表示碼字。表示碼字。(n,k)循環(huán)碼的碼

15、字，其碼多循環(huán)碼的碼字，其碼多項(xiàng)式項(xiàng)式(以降冪以降冪順序排列順序排列)為為 012211)(axaxaxaxAnnnn10.5.2 生成多項(xiàng)式及生成矩陣生成多項(xiàng)式及生成矩陣 如果一種碼的所有碼多項(xiàng)式都是多項(xiàng)式如果一種碼的所有碼多項(xiàng)式都是多項(xiàng)式g(x)的倍式，則稱的倍式，則稱g(x)為該碼的生成多項(xiàng)式。在為該碼的生成多項(xiàng)式。在(n,k)循環(huán)碼中任意碼多項(xiàng)式循環(huán)碼中任意碼多項(xiàng)式A(x)都是最低次碼多項(xiàng)式的倍式。如表都是最低次碼多項(xiàng)式的倍式。如表 10-4 的的(7,3)循循環(huán)碼中，環(huán)碼中， 1)()(2341xxxxAxg)()()()()() 1()()(0)(27320 xgxxAxgxxAx

16、gxxAxgxA其它碼多項(xiàng)式都是其它碼多項(xiàng)式都是g(x)的倍式，的倍式， 即即 循環(huán)碼的生成矩陣常用多項(xiàng)式的形式來表示循環(huán)碼的生成矩陣常用多項(xiàng)式的形式來表示 1)(111xgxgxxgrrr)()()()()(21xgxxgxgxxgxxGkk例如(7,3)循環(huán)碼，n=7, k=3, r=4, 其生成多項(xiàng)式及生成矩陣分別為 10.4.2 監(jiān)督多項(xiàng)式及監(jiān)督矩陣監(jiān)督多項(xiàng)式及監(jiān)督矩陣 為了便于對(duì)循環(huán)碼編譯碼，通常還定義監(jiān)督多項(xiàng)式， 令 1)(1)(111xhxhxxgxxhkkkn其中g(shù)(x)是常數(shù)項(xiàng)為 1 的r次多項(xiàng)式，是生成多項(xiàng)式；h(x)是常數(shù)項(xiàng)為 1 的k次多項(xiàng)式，稱為監(jiān)督多項(xiàng)式。同理，可得

17、監(jiān)督矩陣H )(*)(*)(*)(1xhxxhxhxxHkn是h(x)的逆多項(xiàng)式。例如(7，3)循環(huán)碼，g(x)=x4+x3+x2+1，則 其中 1)(*12211xhxhxhxxhkkkk1)(*1)(1)(3237xxxhxxxgxxh1)(324235346xxxxxxxxxxxxH1101000011010000110100001101H10.6 卷卷 積積 碼碼 10.6.1 基本概念基本概念 圖 10-7 卷積碼(2,1,2)編碼器 m1m2數(shù)據(jù)輸入碼字輸出S1S2S3C1C2S1等于當(dāng)前輸入數(shù)據(jù)，而等于當(dāng)前輸入數(shù)據(jù)，而移位寄存器狀態(tài)移位寄存器狀態(tài)S2S3存儲(chǔ)以前的數(shù)存儲(chǔ)以前的數(shù)據(jù)

18、，輸出碼字據(jù)，輸出碼字C由下式確定由下式確定 3123211SSCSSSC表 10-6 (2,1,2)編碼器的工作過程 10.5.2 卷積碼的描述卷積碼的描述 1. 樹狀圖樹狀圖 圖圖 10-6 (2,1,2)碼的樹圖碼的樹圖 a1100abb0110cdc0011abd1001cd0010a1101ba0011a1100abb0110cdc0011abd1001cd1101c0010db1001a1100數(shù)碼起點(diǎn)狀態(tài)a00b01c10d11上半部下半部數(shù)碼11012. 狀態(tài)圖狀態(tài)圖 圖 10 -10 (2,1,2)碼的狀態(tài)圖 a00b01c10d11cbad01011111001000103. 格圖格圖 圖 10-8 (2,1,2)碼的格圖 a00起點(diǎn)aaaaaabbbccccbbcbddddd