第十章 差錯(cuò)控制

1、10.8 關(guān)于幀或分組順序的差錯(cuò)控制關(guān)于幀或分組順序的差錯(cuò)控制（10.4 卷積碼卷積碼10.3 循環(huán)碼循環(huán)碼10.1 差錯(cuò)控制編碼的基本概念差錯(cuò)控制編碼的基本概念第十章第十章 差錯(cuò)控制差錯(cuò)控制學(xué)習(xí)目錄學(xué)習(xí)目錄10.2 線性分組碼線性分組碼10.7 不用編碼的差錯(cuò)控制不用編碼的差錯(cuò)控制10.5 網(wǎng)格編碼調(diào)制（網(wǎng)格編碼調(diào)制（TCM）（）（略略）10.6 Turbo碼碼10.9 差錯(cuò)控制編碼對(duì)系統(tǒng)性能的改善差錯(cuò)控制編碼對(duì)系統(tǒng)性能的改善10.1 10.1 差錯(cuò)控制編碼的基本概念差錯(cuò)控制編碼的基本概念下一頁(yè)上一頁(yè) 按照噪聲或干擾的變化規(guī)律，可把按照噪聲或干擾的變化規(guī)律，可把信道分為三類信道分為三類： 隨

2、機(jī)信道隨機(jī)信道：恒參高斯白噪聲信道是典型的隨機(jī)信：恒參高斯白噪聲信道是典型的隨機(jī)信道，其中差錯(cuò)的出現(xiàn)是隨機(jī)的，而且錯(cuò)誤之間是道，其中差錯(cuò)的出現(xiàn)是隨機(jī)的，而且錯(cuò)誤之間是統(tǒng)計(jì)獨(dú)立的。統(tǒng)計(jì)獨(dú)立的。 突發(fā)信道突發(fā)信道：具有脈沖干擾的信道，是典型的突發(fā)：具有脈沖干擾的信道，是典型的突發(fā)信道。錯(cuò)誤是成串成群出現(xiàn)的，即在短時(shí)間內(nèi)出信道。錯(cuò)誤是成串成群出現(xiàn)的，即在短時(shí)間內(nèi)出現(xiàn)大量錯(cuò)誤?，F(xiàn)大量錯(cuò)誤。 混合信道混合信道10.1 10.1 差錯(cuò)控制編碼的基本概念差錯(cuò)控制編碼的基本概念下一頁(yè)上一頁(yè)1. 差錯(cuò)控制的工作方式差錯(cuò)控制的工作方式 差錯(cuò)控制的基本工作方式有差錯(cuò)控制的基本工作方式有4種：種： 前向糾錯(cuò)前向糾錯(cuò)

3、檢錯(cuò)重發(fā)檢錯(cuò)重發(fā) 混合糾錯(cuò)混合糾錯(cuò) 反饋校驗(yàn)。反饋校驗(yàn)。10.1 10.1 差錯(cuò)控制編碼的基本概念差錯(cuò)控制編碼的基本概念下一頁(yè)上一頁(yè)（1） 前向糾錯(cuò)方式前向糾錯(cuò)方式(Forward Error Correction，F(xiàn)EC)發(fā)發(fā)收收可以糾正錯(cuò)誤的碼可以糾正錯(cuò)誤的碼（Auto ReQuest Repeat，ARQ)發(fā)發(fā)收收能夠發(fā)現(xiàn)錯(cuò)誤的碼能夠發(fā)現(xiàn)錯(cuò)誤的碼應(yīng)答信號(hào)應(yīng)答信號(hào) 在具體實(shí)現(xiàn)檢錯(cuò)重發(fā)系統(tǒng)時(shí)，通常有三種在具體實(shí)現(xiàn)檢錯(cuò)重發(fā)系統(tǒng)時(shí)，通常有三種形式，即形式，即停發(fā)等候重發(fā)，返回重發(fā)停發(fā)等候重發(fā)，返回重發(fā)和和選擇重發(fā)選擇重發(fā)。10.1 10.1 差錯(cuò)控制編碼的基本概念差錯(cuò)控制編碼的基本概念下一頁(yè)上一

4、頁(yè)（3） 混合糾錯(cuò)方式混合糾錯(cuò)方式(Hybrid Error Correction ,HEC)發(fā)發(fā)收收可以糾正和發(fā)現(xiàn)錯(cuò)誤的碼可以糾正和發(fā)現(xiàn)錯(cuò)誤的碼（4） 信息反饋方式（信息反饋方式（Information Feedback, IF）發(fā)發(fā)收收數(shù)據(jù)信息數(shù)據(jù)信息數(shù)據(jù)信息數(shù)據(jù)信息回程校驗(yàn)回程校驗(yàn):發(fā)端將反饋信息和原發(fā)送信發(fā)端將反饋信息和原發(fā)送信息進(jìn)行比較，發(fā)現(xiàn)錯(cuò)誤進(jìn)行重發(fā)。息進(jìn)行比較，發(fā)現(xiàn)錯(cuò)誤進(jìn)行重發(fā)。下一頁(yè)上一頁(yè)10.1 10.1 差錯(cuò)控制編碼的基本概念差錯(cuò)控制編碼的基本概念2. 差錯(cuò)控制編碼的分類差錯(cuò)控制編碼的分類按照差錯(cuò)控制編碼的用途：檢錯(cuò)碼、糾錯(cuò)碼和糾刪碼。按照差錯(cuò)控制編碼的用途：檢錯(cuò)碼、糾錯(cuò)

5、碼和糾刪碼。按照信息碼元和監(jiān)督碼元之間的函數(shù)關(guān)系：線性碼和非線性按照信息碼元和監(jiān)督碼元之間的函數(shù)關(guān)系：線性碼和非線性碼。碼。按照對(duì)信息元處理方式的：分組碼和卷積碼。按照對(duì)信息元處理方式的：分組碼和卷積碼。按照碼組中信息碼元在編碼前后是否相同：系統(tǒng)碼和非系統(tǒng)按照碼組中信息碼元在編碼前后是否相同：系統(tǒng)碼和非系統(tǒng)碼。碼。按照糾（檢）錯(cuò)誤的類型：糾（檢）隨機(jī)錯(cuò)誤碼、糾（檢）按照糾（檢）錯(cuò)誤的類型：糾（檢）隨機(jī)錯(cuò)誤碼、糾（檢）突發(fā)錯(cuò)誤碼和既能糾（檢）隨機(jī)錯(cuò)誤同時(shí)又能糾（檢）突發(fā)突發(fā)錯(cuò)誤碼和既能糾（檢）隨機(jī)錯(cuò)誤同時(shí)又能糾（檢）突發(fā)錯(cuò)誤碼。錯(cuò)誤碼。按照每個(gè)碼元的取值：二進(jìn)碼和多進(jìn)碼。按照每個(gè)碼元的取值：二進(jìn)

6、碼和多進(jìn)碼。10.1 10.1 差錯(cuò)控制編碼的基本概念差錯(cuò)控制編碼的基本概念 差錯(cuò)編碼的基本思想是在被傳輸信息中增加一差錯(cuò)編碼的基本思想是在被傳輸信息中增加一些冗余碼，利用附加碼元和信息碼元之間的約束關(guān)些冗余碼，利用附加碼元和信息碼元之間的約束關(guān)系加以校驗(yàn)，以檢測(cè)和糾正錯(cuò)誤，增加冗余碼的個(gè)系加以校驗(yàn)，以檢測(cè)和糾正錯(cuò)誤，增加冗余碼的個(gè)數(shù)可增加糾檢錯(cuò)能力。數(shù)可增加糾檢錯(cuò)能力。3. 差錯(cuò)控制編碼的基本原理差錯(cuò)控制編碼的基本原理下一頁(yè)上一頁(yè)下一頁(yè)上一頁(yè)10.1 10.1 差錯(cuò)控制編碼的基本概念差錯(cuò)控制編碼的基本概念 編碼碼組的碼元總位數(shù)稱為碼組的長(zhǎng)度，簡(jiǎn)稱編碼碼組的碼元總位數(shù)稱為碼組的長(zhǎng)度，簡(jiǎn)稱碼長(zhǎng)碼

7、長(zhǎng)。 碼組中，碼組中，“1”碼元的數(shù)目稱為碼組的重量，簡(jiǎn)稱碼元的數(shù)目稱為碼組的重量，簡(jiǎn)稱碼重碼重。兩個(gè)等長(zhǎng)碼組之間對(duì)應(yīng)位上碼元不同的數(shù)目稱為這兩個(gè)碼組兩個(gè)等長(zhǎng)碼組之間對(duì)應(yīng)位上碼元不同的數(shù)目稱為這兩個(gè)碼組的距離，簡(jiǎn)稱的距離，簡(jiǎn)稱碼距碼距。（1） 碼長(zhǎng)、碼重、碼距碼長(zhǎng)、碼重、碼距（000）（110）（100）（010）（111）（101）（011）（001）A1A2A3下一頁(yè)上一頁(yè)2） 檢錯(cuò)和糾錯(cuò)能力檢錯(cuò)和糾錯(cuò)能力10.1 10.1 差錯(cuò)控制編碼的基本概念差錯(cuò)控制編碼的基本概念 檢測(cè)檢測(cè)e個(gè)隨機(jī)錯(cuò)誤，則要求最小碼距個(gè)隨機(jī)錯(cuò)誤，則要求最小碼距dmine+1；c1e-11dminc21下一頁(yè)上一頁(yè)10

8、.1 10.1 差錯(cuò)控制編碼的基本概念差錯(cuò)控制編碼的基本概念 糾正糾正t個(gè)隨機(jī)錯(cuò)誤，則要求最小碼距個(gè)隨機(jī)錯(cuò)誤，則要求最小碼距dmin2t+1；c1t1dminc2t下一頁(yè)上一頁(yè)10.1 10.1 差錯(cuò)控制編碼的基本概念差錯(cuò)控制編碼的基本概念 糾正糾正t個(gè)同時(shí)檢測(cè)個(gè)同時(shí)檢測(cè)e（e t）個(gè)隨機(jī)錯(cuò)誤，則要求）個(gè)隨機(jī)錯(cuò)誤，則要求最小碼距最小碼距dmint+e+1。t1dminc2tc1e下一頁(yè)上一頁(yè)10.1 10.1 差錯(cuò)控制編碼的基本概念差錯(cuò)控制編碼的基本概念（3） 編碼效率編碼效率 用差錯(cuò)控制編碼提高通信系統(tǒng)的的可靠性，用差錯(cuò)控制編碼提高通信系統(tǒng)的的可靠性，是以降低有效性為代價(jià)換來的。定義編碼效率

9、是以降低有效性為代價(jià)換來的。定義編碼效率來來衡量有效性：衡量有效性： =k/n=k/(k+r) 其中，其中，k是信息元的個(gè)數(shù)，是信息元的個(gè)數(shù)，n為碼長(zhǎng)，為碼長(zhǎng)， r為校驗(yàn)碼為校驗(yàn)碼個(gè)數(shù)個(gè)數(shù) 。下一頁(yè)上一頁(yè)10.1 10.1 差錯(cuò)控制編碼的基本概念差錯(cuò)控制編碼的基本概念4. 常用的幾種簡(jiǎn)單編碼常用的幾種簡(jiǎn)單編碼（1） 奇偶監(jiān)督碼奇偶監(jiān)督碼 奇偶監(jiān)督碼是在原信息碼后面附加一個(gè)監(jiān)督奇偶監(jiān)督碼是在原信息碼后面附加一個(gè)監(jiān)督元，使得碼組中元，使得碼組中“1”的個(gè)數(shù)是奇數(shù)或偶數(shù)，或者的個(gè)數(shù)是奇數(shù)或偶數(shù)，或者說，它是含一個(gè)監(jiān)督元，碼重為奇數(shù)或偶數(shù)的（說，它是含一個(gè)監(jiān)督元，碼重為奇數(shù)或偶數(shù)的（n，n-1）系統(tǒng)分

10、組碼。奇偶監(jiān)督碼又分為奇監(jiān)督碼和）系統(tǒng)分組碼。奇偶監(jiān)督碼又分為奇監(jiān)督碼和偶監(jiān)督碼。偶監(jiān)督碼。下一頁(yè)上一頁(yè)10.1 10.1 差錯(cuò)控制編碼的基本概念差錯(cuò)控制編碼的基本概念（2） 行列監(jiān)督碼（水平奇偶監(jiān)督碼）行列監(jiān)督碼（水平奇偶監(jiān)督碼） 奇偶監(jiān)督碼不能發(fā)現(xiàn)偶數(shù)個(gè)錯(cuò)誤。此引入行列監(jiān)督奇偶監(jiān)督碼不能發(fā)現(xiàn)偶數(shù)個(gè)錯(cuò)誤。此引入行列監(jiān)督碼：將經(jīng)過奇偶監(jiān)督碼的碼元序列排成方陣，每行為碼：將經(jīng)過奇偶監(jiān)督碼的碼元序列排成方陣，每行為一組再做奇偶監(jiān)督編碼，發(fā)送時(shí)則按列的順序傳輸。一組再做奇偶監(jiān)督編碼，發(fā)送時(shí)則按列的順序傳輸。一維奇偶監(jiān)督碼一維奇偶監(jiān)督碼信息碼監(jiān)督碼元 1 1 1 0 0 1 0 1 0 0 1 0 0

11、 1 0 1 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0 1 1 0 1 01001下一頁(yè)上一頁(yè)信息碼監(jiān)督碼元 1 1 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 1 1 0 0 1 0 0 0 1 1 0 0 0 0 1 1 0 1 01001監(jiān)督碼元 0 0 1 1 0 0 1 1 00二維奇偶監(jiān)督碼二維奇偶監(jiān)督碼10.1 10.1 差錯(cuò)控制編碼的基本概念差錯(cuò)控制編碼的基本概念10.1 10.1 差錯(cuò)控制編碼的基本概念差錯(cuò)控制編碼的基本概念下一頁(yè)上一頁(yè)（3） 漢明漢明(Hamming)奇偶監(jiān)督碼奇偶監(jiān)督碼漢明校驗(yàn)是分組奇偶校驗(yàn)。漢明校驗(yàn)是分組奇偶校驗(yàn)。校驗(yàn)位

12、校驗(yàn)位Pn的權(quán)值為的權(quán)值為2n-1例例: 傳送信息傳送信息: 1000101 編碼編碼: P1P21P3000P4101 組組P1P21P3000P41011234分組分組下一頁(yè)上一頁(yè)10.1 10.1 差錯(cuò)控制編碼的基本概念差錯(cuò)控制編碼的基本概念編碼，設(shè)發(fā)送與接收雙方均采用奇校驗(yàn)，則編碼，設(shè)發(fā)送與接收雙方均采用奇校驗(yàn)，則 P1 = 0，P2 = 1，P3 = 1，P4 = 1發(fā)送端發(fā)送的比特流為發(fā)送端發(fā)送的比特流為01110001101接收端接收到的比特流為接收端接收到的比特流為01100001101（能否糾檢錯(cuò)（能否糾檢錯(cuò)？）組組P1P21P3000P41011234下一頁(yè)上一頁(yè)10.1

13、10.1 差錯(cuò)控制編碼的基本概念差錯(cuò)控制編碼的基本概念（3） 重復(fù)碼重復(fù)碼 重復(fù)碼是在每位碼元之后，用簡(jiǎn)單重復(fù)多次的方重復(fù)碼是在每位碼元之后，用簡(jiǎn)單重復(fù)多次的方法編碼。例如重復(fù)兩次，用法編碼。例如重復(fù)兩次，用111傳輸傳輸1碼，用碼，用000傳輸傳輸0碼。碼。（4） 恒比碼恒比碼 碼字中碼字中1的數(shù)目與的數(shù)目與0的的數(shù)目保持恒定比例數(shù)目保持恒定比例的碼稱為的碼稱為恒恒比碼比碼。由于恒比碼中，每個(gè)碼組均含有相同數(shù)目的。由于恒比碼中，每個(gè)碼組均含有相同數(shù)目的1和和0，因此恒比碼又稱因此恒比碼又稱等重碼，定等重碼，定1碼碼。這種碼在檢測(cè)時(shí)，只。這種碼在檢測(cè)時(shí)，只要計(jì)算接收碼元中要計(jì)算接收碼元中1的個(gè)

14、數(shù)是否與規(guī)定的相同，就可判的個(gè)數(shù)是否與規(guī)定的相同，就可判斷有無錯(cuò)誤。斷有無錯(cuò)誤。10.1 10.1 差錯(cuò)控制編碼的基本概念差錯(cuò)控制編碼的基本概念（5） 群計(jì)數(shù)碼群計(jì)數(shù)碼 群計(jì)數(shù)碼是將信息碼元分組后，計(jì)算每組碼元群計(jì)數(shù)碼是將信息碼元分組后，計(jì)算每組碼元中中“1”的個(gè)數(shù)，然后將這個(gè)數(shù)目的二進(jìn)制表示作為的個(gè)數(shù)，然后將這個(gè)數(shù)目的二進(jìn)制表示作為監(jiān)督碼元，一起送往發(fā)送端。監(jiān)督碼元，一起送往發(fā)送端。返回結(jié)束下一頁(yè)上一頁(yè)10.2 10.2 1. 線性分組碼的定義和特點(diǎn)線性分組碼的定義和特點(diǎn) 線性分組碼，是指信息碼元與監(jiān)督碼元之間的關(guān)線性分組碼，是指信息碼元與監(jiān)督碼元之間的關(guān)系可以用系可以用一組線性方程一組線性

15、方程來表示的分組碼，即在（來表示的分組碼，即在（n，k）分組碼中，每一個(gè)監(jiān)督碼元都是碼組中某些信息碼元分組碼中，每一個(gè)監(jiān)督碼元都是碼組中某些信息碼元按模按模2和而得到的。和而得到的。 線性分組碼是一類重要的糾錯(cuò)碼，應(yīng)用很廣。線性分組碼是一類重要的糾錯(cuò)碼，應(yīng)用很廣。下一頁(yè)上一頁(yè)（1） 生成矩陣生成矩陣 設(shè)分組碼的碼組由設(shè)分組碼的碼組由n位碼組成，即位碼組成，即c1,c2cn ；信息碼組；信息碼組由由k位碼組成，即位碼組成，即d1, d2, dk 。以上碼組記為（。以上碼組記為（n，k）碼，）碼，碼組和信息碼組用行矩陣表示：碼組和信息碼組用行矩陣表示： C = c1, c2, cn D = d1,

16、 d2, dk 系統(tǒng)分組碼用聯(lián)立方程可表示為系統(tǒng)分組碼用聯(lián)立方程可表示為 c1= d1 ck= dk ck+1= h11d1 h12d2 h1kdk cn= hn-k,1d1 hn-k,2d2 hn-k,kdk+10.2 10.2 下一頁(yè)上一頁(yè)10.2 10.2 將碼組將碼組C寫成矩陣形式：寫成矩陣形式： C=DG其中矩陣其中矩陣 G 稱為生成矩陣稱為生成矩陣 P,IhhhhhhhhhGkk ,knkk,kn,kn 212221212111100010001下一頁(yè)上一頁(yè)10.2 10.2 由生成矩陣由生成矩陣G和信息組就可以產(chǎn)生全部碼字。和信息組就可以產(chǎn)生全部碼字。G為為kn 階矩陣，各行也是

17、線性無關(guān)的。階矩陣，各行也是線性無關(guān)的。 數(shù)學(xué)上已經(jīng)證明，數(shù)學(xué)上已經(jīng)證明，線性碼的最小碼距線性碼的最小碼距dmin正好等正好等于非零碼的最小碼重于非零碼的最小碼重。例：已知（例：已知（6，3）碼的生成矩陣為：）碼的生成矩陣為： 011100110010101001G下一頁(yè)上一頁(yè)10.2 10.2 試求：（試求：（1）編碼碼組和各個(gè)碼組的碼重；）編碼碼組和各個(gè)碼組的碼重； （2）最小碼距和該碼的差錯(cuò)控制能力。）最小碼距和該碼的差錯(cuò)控制能力。解：由解：由3位碼組成的信息碼組矩陣為位碼組成的信息碼組矩陣為 111011101001110010100000D下一頁(yè)上一頁(yè)10.2 10.2 碼組矩陣為碼

18、組矩陣為 011100110010101001111011101001110010100000GDC下一頁(yè)上一頁(yè)10.2 10.2 000111011011110101101001101110110010011100000000下一頁(yè)上一頁(yè)10.2 10.2 信息碼組、編碼碼組及碼重如下表所示。信息碼組、編碼碼組及碼重如下表所示。信息碼組信息碼組編碼碼組編碼碼組碼重碼重0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 10 0 0 0 0 00 0 1 1 1 00 1 0 0 1 10 1 1 1 0 11 0 0 1 0 11 0 1 0 1 11 1 0 1

19、1 01 1 1 0 0 003343443下一頁(yè)上一頁(yè)10.2 10.2 由上表可知，非零碼的最小碼重由上表可知，非零碼的最小碼重 Wmin=3因此，因此， 檢測(cè)檢測(cè)e個(gè)隨機(jī)錯(cuò)誤，則要求最小碼距個(gè)隨機(jī)錯(cuò)誤，則要求最小碼距dmin e+1； 糾正糾正t個(gè)隨機(jī)錯(cuò)誤，則要求最小碼距個(gè)隨機(jī)錯(cuò)誤，則要求最小碼距dmin 2t+1； 糾正糾正t個(gè)同時(shí)檢測(cè)個(gè)同時(shí)檢測(cè)e（et）個(gè)隨機(jī)錯(cuò)誤，則要求）個(gè)隨機(jī)錯(cuò)誤，則要求最小碼距最小碼距dmint+e+1?？芍?，該碼有檢可知，該碼有檢2錯(cuò)，或糾錯(cuò)，或糾1錯(cuò)，或糾錯(cuò)，或糾1錯(cuò)同時(shí)檢錯(cuò)同時(shí)檢1錯(cuò)錯(cuò)的能力。的能力。下一頁(yè)上一頁(yè)10.2 10.2 碼組碼組C又又寫成矩陣形

20、式：寫成矩陣形式： C=DG=D Ik,P= D Ik, D P= D, Cm于是有于是有 D P = Cm （m=n-k） D P Cm =0寫成矩陣形式寫成矩陣形式 0 mmIPCD+下一頁(yè)上一頁(yè)10.2 10.2 令令 mTIPH mTIPH 或或有有0 TCH我們把我們把 H 稱為稱為監(jiān)督矩陣監(jiān)督矩陣，或稱，或稱一致校驗(yàn)矩陣一致校驗(yàn)矩陣，一旦，一旦H給定，信息位和監(jiān)督位之間的關(guān)系也就確定了。給定，信息位和監(jiān)督位之間的關(guān)系也就確定了。H為為 mn階矩陣，階矩陣，H矩陣每行之間是彼此線性無關(guān)的。矩陣每行之間是彼此線性無關(guān)的。H矩陣矩陣可分成兩部分，其中可分成兩部分，其中P為為km階矩陣，階

21、矩陣，Im為為mm階單位陣。階單位陣。能寫成能寫成H=PT Im形式的矩陣稱為形式的矩陣稱為典型監(jiān)督矩陣典型監(jiān)督矩陣。 下一頁(yè)上一頁(yè)10.2 10.2 設(shè)接收組碼為設(shè)接收組碼為R，它是，它是n位碼組成的行矢量。如果接收位碼組成的行矢量。如果接收組碼有錯(cuò)，組碼可分解為正確組碼組碼有錯(cuò)，組碼可分解為正確組碼C與錯(cuò)誤組碼與錯(cuò)誤組碼E之和，即之和，即ECR 定義伴隨式或校正子為定義伴隨式或校正子為 S=RHT。 S=RHT=（C+E）HT=EHT由此可見，伴隨式由此可見，伴隨式S與錯(cuò)誤圖樣與錯(cuò)誤圖樣E之間有確定的線性變換關(guān)系，與發(fā)送碼之間有確定的線性變換關(guān)系，與發(fā)送碼組組C無關(guān)。接收端譯碼器的任務(wù)就是

22、從伴無關(guān)。接收端譯碼器的任務(wù)就是從伴隨式確定錯(cuò)誤圖樣，然后從接收到的碼隨式確定錯(cuò)誤圖樣，然后從接收到的碼字中減去錯(cuò)誤圖樣。字中減去錯(cuò)誤圖樣。下一頁(yè)上一頁(yè)10.2 10.2 當(dāng)碼組出現(xiàn)錯(cuò)誤時(shí)，由當(dāng)碼組出現(xiàn)錯(cuò)誤時(shí)，由 S=EHT解出解出E矢量。由矢量。由ECR 得得 C=R E+如何解方程如何解方程 S=EHT ？ S為零矢量時(shí)，為零矢量時(shí)，E=0？10.2 10.2 下一頁(yè)上一頁(yè) S=EHT的解不唯一（的解不唯一（n個(gè)變量，個(gè)變量，m（=n-k）個(gè)方）個(gè)方程組）。程組）。 S為零矢量時(shí)，為零矢量時(shí)，E 不一定為不一定為 0。 為了選擇正確的結(jié)果，要使用最大似然比準(zhǔn)則，為了選擇正確的結(jié)果，要使用最

23、大似然比準(zhǔn)則，選擇與選擇與R最相似的最相似的C。從幾何意義上來說，就是選擇。從幾何意義上來說，就是選擇與與R距離最小的碼組。當(dāng)距離最小的碼組。當(dāng)R與與C之間距離最近時(shí)意味之間距離最近時(shí)意味著差錯(cuò)矢量著差錯(cuò)矢量E是是1碼最少的矢量。碼最少的矢量。下一頁(yè)上一頁(yè)10.2 10.2 例：已知（例：已知（6，3）碼的生成矩陣為）碼的生成矩陣為 011100110010101001G試列出試列出S與與R的對(duì)照表。當(dāng)收到碼組的對(duì)照表。當(dāng)收到碼組R=1 1 1 0 1 1時(shí)，解出對(duì)應(yīng)的信息碼組時(shí)，解出對(duì)應(yīng)的信息碼組D。下一頁(yè)上一頁(yè)10.2 10.2 解：生成矩陣解：生成矩陣監(jiān)督矩陣轉(zhuǎn)置監(jiān)督矩陣轉(zhuǎn)置101011

24、110100010001TmPHI100101010011001110kGIP下一頁(yè)上一頁(yè)10.2 10.2 S=EHT共有共有23種形式，相對(duì)的碼重最小的種形式，相對(duì)的碼重最小的E矢量有矢量有8種，種，對(duì)應(yīng)關(guān)系如下表。對(duì)應(yīng)關(guān)系如下表。ES0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 01 0 10 1 11 1 01 0 00 1 00 0 11 1 1下一頁(yè)上一頁(yè)10.2 10.2 將接收的碼組矢量將接收的碼組矢量R=1 1 1 0 1

25、1代入代入S=EHT，得，得 110100010001011110101110111 TRHS由上表可找到差錯(cuò)矢量由上表可找到差錯(cuò)矢量E為為 E =0 1 0 0 0 0下一頁(yè)上一頁(yè)10.2 10.2 正確的碼組為正確的碼組為 C=R E= 1 1 1 0 1 1 0 1 0 0 0 0 = 1 0 1 0 1 1 +所以信息碼組為所以信息碼組為 D = 1 0 1從以上分析可以得出線性分組碼譯碼的基本步驟：從以上分析可以得出線性分組碼譯碼的基本步驟： 計(jì)算接收碼組計(jì)算接收碼組R的伴隨式的伴隨式S； 根據(jù)根據(jù)S找出錯(cuò)誤圖樣找出錯(cuò)誤圖樣E，判定誤碼位置；，判定誤碼位置； 根據(jù)根據(jù)E糾正錯(cuò)誤，得到

26、正確的碼組。糾正錯(cuò)誤，得到正確的碼組。+下一頁(yè)上一頁(yè)10.2 10.2 4. 漢明碼漢明碼 漢明碼漢明碼(1950)是一類常見的線性分組碼，是一種能是一類常見的線性分組碼，是一種能夠糾正單個(gè)錯(cuò)誤的完備碼。要糾正碼組中的單個(gè)錯(cuò)誤，夠糾正單個(gè)錯(cuò)誤的完備碼。要糾正碼組中的單個(gè)錯(cuò)誤，則要求與單個(gè)錯(cuò)誤圖樣對(duì)應(yīng)的伴隨式各不相同，且不能則要求與單個(gè)錯(cuò)誤圖樣對(duì)應(yīng)的伴隨式各不相同，且不能為全零。若碼長(zhǎng)為為全零。若碼長(zhǎng)為n，監(jiān)督碼元的個(gè)數(shù)為，監(jiān)督碼元的個(gè)數(shù)為m，則要求，則要求 2m-1n 碼組為漢明碼時(shí)取等號(hào)。即用來糾正單個(gè)錯(cuò)誤時(shí)，碼組為漢明碼時(shí)取等號(hào)。即用來糾正單個(gè)錯(cuò)誤時(shí)，漢明碼所用的監(jiān)督碼元個(gè)數(shù)最少，效率最高

27、。漢明碼所用的監(jiān)督碼元個(gè)數(shù)最少，效率最高。下一頁(yè)上一頁(yè)10.2 10.2 漢明碼的特點(diǎn)如下：漢明碼的特點(diǎn)如下：（1） 監(jiān)督碼元的個(gè)數(shù)監(jiān)督碼元的個(gè)數(shù)m=n-k，碼長(zhǎng)滿足，碼長(zhǎng)滿足n=2m-1，k = n-m。m2。（2） 無論碼長(zhǎng)無論碼長(zhǎng)n為多少，漢明碼最小碼距為多少，漢明碼最小碼距dmin=3。（3） 其編碼效率為其編碼效率為 =k/n=(2m-1-m)/(2m-1)=1-m/n。10.2 10.2 下一頁(yè)上一頁(yè)例例1.已知：信息碼為已知：信息碼為 “0010”。漢明碼的監(jiān)督關(guān)系式為：。漢明碼的監(jiān)督關(guān)系式為：S2=a2+a4+a5+a6S1=a1+a3+a5+a6S0=a0+a3+a4+a6求

28、：漢明碼碼字。求：漢明碼碼字。 解：解：1) 由監(jiān)督關(guān)系式知冗余碼為由監(jiān)督關(guān)系式知冗余碼為a2a1a0。2) 冗余碼與信息碼合成的漢明碼是冗余碼與信息碼合成的漢明碼是 0010a2a1a010.2 10.2 下一頁(yè)上一頁(yè)設(shè)設(shè)S2=S1=S0=0,由監(jiān)督關(guān)系式得：由監(jiān)督關(guān)系式得：a2=a4+a5+a6=1a1=a3+a5+a6=0a0=a3+a4+a6=1因此，漢明碼碼字為：因此，漢明碼碼字為：0010101 漢明碼是線性碼，其生成矩陣？漢明碼是線性碼，其生成矩陣？10.2 10.2 下一頁(yè)上一頁(yè)例例2.已知：漢明碼的監(jiān)督關(guān)系式為：已知：漢明碼的監(jiān)督關(guān)系式為：S2=a2+a4+a5+a6S1=a

29、1+a3+a5+a6S0=a0+a3+a4+a6 接收碼字為：接收碼字為：0011101(n=7) 求：發(fā)送端的信息碼。求：發(fā)送端的信息碼。解：解：1)由漢明碼的監(jiān)督關(guān)系式計(jì)算得由漢明碼的監(jiān)督關(guān)系式計(jì)算得S2S1S0=011。2)由監(jiān)督關(guān)系式可構(gòu)造出下面錯(cuò)碼位置關(guān)系表：由監(jiān)督關(guān)系式可構(gòu)造出下面錯(cuò)碼位置關(guān)系表： S2S1S0 000 001 010 100 011 101 110 111 錯(cuò)碼位置錯(cuò)碼位置 無錯(cuò)無錯(cuò) a0 a1 a2 a3 a4 a5 a6 3)由由S2S1S0=011查表得知錯(cuò)碼位置是查表得知錯(cuò)碼位置是a3。4)糾錯(cuò)糾錯(cuò)-對(duì)碼字的對(duì)碼字的a3位取反得正確碼字：位取反得正確碼字：

30、0 0 1 0 1 0 15)把冗余碼把冗余碼a2a1a0刪除得發(fā)送端的信息碼：刪除得發(fā)送端的信息碼：0010 10.2 10.2 下一頁(yè)上一頁(yè)下一頁(yè)上一頁(yè)10.2 10.2 對(duì)一般線性分組碼的討論對(duì)一般線性分組碼的討論 1）在線性碼中信息位和監(jiān)督位滿足一組線性方程，）在線性碼中信息位和監(jiān)督位滿足一組線性方程，或者說信息位和監(jiān)督位之間有某種線性變換關(guān)系或者說信息位和監(jiān)督位之間有某種線性變換關(guān)系,該線性該線性方程規(guī)定了信息碼元與監(jiān)督碼元間的相互制約的關(guān)系方程規(guī)定了信息碼元與監(jiān)督碼元間的相互制約的關(guān)系, 這這個(gè)方程組（線性變換）叫做個(gè)方程組（線性變換）叫做碼組的一致監(jiān)督方程或制約方碼組的一致監(jiān)督方

31、程或制約方程程； 2）利用矩陣）利用矩陣H可以表征碼字的特性，為此把可以表征碼字的特性，為此把H稱為線稱為線性碼的一致監(jiān)督矩陣性碼的一致監(jiān)督矩陣,只要監(jiān)督矩陣只要監(jiān)督矩陣H給定，編碼時(shí)監(jiān)督位給定，編碼時(shí)監(jiān)督位和信息位的關(guān)系就完全被確定了；和信息位的關(guān)系就完全被確定了； 3）線性碼具有封閉性，這是它的一個(gè)重要性質(zhì)；）線性碼具有封閉性，這是它的一個(gè)重要性質(zhì)；10.2 10.2 4） H的行數(shù)就是監(jiān)督關(guān)系式的數(shù)目。它等于監(jiān)的行數(shù)就是監(jiān)督關(guān)系式的數(shù)目。它等于監(jiān)督位的數(shù)目督位的數(shù)目m。H每行中的每行中的“1”的位置表示相應(yīng)碼元的位置表示相應(yīng)碼元之間存在的關(guān)系式之間存在的關(guān)系式 5）信息位給定后，用信息位

32、的行矩陣乘矩陣）信息位給定后，用信息位的行矩陣乘矩陣G就就產(chǎn)生出監(jiān)督位；產(chǎn)生出監(jiān)督位； 6）如果找到了碼的生成矩陣）如果找到了碼的生成矩陣G，則編碼的方法就，則編碼的方法就完全確定了；完全確定了； 7）在線性碼中，碼組中的監(jiān)督碼元并不固定監(jiān)）在線性碼中，碼組中的監(jiān)督碼元并不固定監(jiān)督某位或某幾位信息碼元，而是碼組中的所有監(jiān)督碼督某位或某幾位信息碼元，而是碼組中的所有監(jiān)督碼元共同監(jiān)督碼組中所有的信息碼元和監(jiān)督碼元。元共同監(jiān)督碼組中所有的信息碼元和監(jiān)督碼元。返回結(jié)束下一頁(yè)上一頁(yè)10.3 10.3 循環(huán)碼是另一類重要的線性分組碼，它除了具循環(huán)碼是另一類重要的線性分組碼，它除了具有線性碼的一般性質(zhì)外，還

33、具有循環(huán)性，即循環(huán)碼有線性碼的一般性質(zhì)外，還具有循環(huán)性，即循環(huán)碼組中任一碼組循環(huán)移位所得的碼組仍為該循環(huán)碼中組中任一碼組循環(huán)移位所得的碼組仍為該循環(huán)碼中的一許用碼組。的一許用碼組。 在代數(shù)理論中，為了便于計(jì)算，常用碼多項(xiàng)式在代數(shù)理論中，為了便于計(jì)算，常用碼多項(xiàng)式表示碼字。（表示碼字。（n，k）循環(huán)碼的碼字）循環(huán)碼的碼字 C = 其碼多項(xiàng)式（以降冪順序排列）為其碼多項(xiàng)式（以降冪順序排列）為下一頁(yè)上一頁(yè) 碼組碼組C移位移位1次得到次得到C(1)仍是碼組，相應(yīng)的碼多項(xiàng)式仍是碼組，相應(yīng)的碼多項(xiàng)式c(1)(x)為為 c(1)(x) 上式正好是上式正好是 c (x)c (x) = = (c(1)(x)c

34、(x)= (c(1)(x)10.3 10.3 10.3 10.3 下一頁(yè)上一頁(yè) 碼組碼組C移位移位2次得到次得到C(2)仍是碼組，相應(yīng)的碼多項(xiàng)式仍是碼組，相應(yīng)的碼多項(xiàng)式c(2)(x)為為 c(2)(x) 上式正好是上式正好是 c(1)(x)移位移位1次而得到，因此利用前面結(jié)次而得到，因此利用前面結(jié)果，有果，有c(1) (x)= (c(2)(x)c (x)= (c(2)(x)c (x)( x (1c(2)(x)即即c(2)(x)正好是正好是 c (x)10.3 10.3 下一頁(yè)上一頁(yè)c(i)(x)c (x)c (x)下一頁(yè)上一頁(yè) 循環(huán)碼的編碼過程也同樣可用多項(xiàng)式描述。一個(gè)循環(huán)碼的編碼過程也同樣可

35、用多項(xiàng)式描述。一個(gè)k位的信息碼組位的信息碼組 D=d1, d2, dk 可用信息多項(xiàng)式可用信息多項(xiàng)式 d (x) 表表示，有示，有 10.3 10.3 下一頁(yè)上一頁(yè) c (x) = d(g (x) c (x) = g (x)g (x)g (x) 上式說明上式說明c(x)是一個(gè)不大于是一個(gè)不大于n-1次多項(xiàng)式。將式次多項(xiàng)式。將式 c (x) = d(g (x)表示的碼多項(xiàng)式表示的碼多項(xiàng)式 c(x) 提高提高 1 次，得次，得 x c (x) = x d(g (x)上式是上式是g(x)的倍式。的倍式。10.3 10.3 下一頁(yè)上一頁(yè)另一方面，由前面分析，有另一方面，由前面分析，有c (x) = =

36、 (c(1)(x)因?yàn)榍懊嬉呀?jīng)設(shè)定因?yàn)榍懊嬉呀?jīng)設(shè)定 ( 是是 g(x) 的倍式。所以的倍式。所以 c(1)(x)也是也是 g(x) 的倍式。可以表達(dá)為的倍式?？梢员磉_(dá)為 c(1)(x) = Q(g (x)式中式中Q(x)對(duì)應(yīng)于某個(gè)信息碼組。對(duì)應(yīng)于某個(gè)信息碼組。 10.3 10.3 下一頁(yè)上一頁(yè) 以上分析過程說明用式以上分析過程說明用式 c (x) = d(g (x) 產(chǎn)生的產(chǎn)生的碼組一定是循環(huán)碼。碼組一定是循環(huán)碼。 換言之，循環(huán)碼完全由其碼組長(zhǎng)度換言之，循環(huán)碼完全由其碼組長(zhǎng)度n及生成多及生成多項(xiàng)式項(xiàng)式g(x)所決定，由于所決定，由于g(x)是一個(gè)能除盡是一個(gè)能除盡 ( 的的n-k次多項(xiàng)式，所以

37、對(duì)次多項(xiàng)式，所以對(duì) ( 進(jìn)行因式分解，便可進(jìn)行因式分解，便可得到相應(yīng)的得到相應(yīng)的 g(x)。10.3 10.3 下一頁(yè)上一頁(yè)例：例： 求求 (7,4) 循環(huán)碼的生成多項(xiàng)式循環(huán)碼的生成多項(xiàng)式 g(x)。當(dāng)信息碼組。當(dāng)信息碼組D= 1 0 1 0 時(shí)，求輸出碼組時(shí)，求輸出碼組C。解解:(1) 由條件可知由條件可知n=7, k=4, m=n-k=3，g(x)應(yīng)為應(yīng)為 ( 的的3次因式。對(duì)次因式。對(duì)( 分解因式，有分解因式，有 (得到得到2個(gè)生成多項(xiàng)式：個(gè)生成多項(xiàng)式：10.3 10.3 下一頁(yè)上一頁(yè) (2) 由式由式 c (x) = d(g (x) 可計(jì)算輸出碼組可計(jì)算輸出碼組C。由于有。由于有2個(gè)生

38、成多項(xiàng)式，經(jīng)計(jì)算可得到個(gè)生成多項(xiàng)式，經(jīng)計(jì)算可得到2個(gè)碼多項(xiàng)式和個(gè)碼多項(xiàng)式和2個(gè)碼組，個(gè)碼組，計(jì)算過程如下：計(jì)算過程如下： c (x) = d(g (x) = ()()= C = 1 0 0 1 1 1 0 c (x) = d(g (x) = ()() = C = 1 1 1 0 0 1 0 1 1 0 0 1 0 110.3 10.3 下一頁(yè)上一頁(yè) 通常，由信息碼組通常，由信息碼組D和生成多項(xiàng)式和生成多項(xiàng)式g(x)直接求出的碼直接求出的碼組不是系統(tǒng)碼。在上例的結(jié)果中，碼組的前組不是系統(tǒng)碼。在上例的結(jié)果中，碼組的前4位碼不是位碼不是1 0 1 0。為了得到系統(tǒng)循環(huán)碼，必須按照系統(tǒng)碼的規(guī)則表。為了

39、得到系統(tǒng)循環(huán)碼，必須按照系統(tǒng)碼的規(guī)則表示碼組。根據(jù)系統(tǒng)碼的定義，碼組示碼組。根據(jù)系統(tǒng)碼的定義，碼組C的前的前k位是信息碼元，位是信息碼元，后后m位是校驗(yàn)碼元，用多項(xiàng)式可表示為位是校驗(yàn)碼元，用多項(xiàng)式可表示為 c (x) = xd(r (x)d(xd(r (x)10.3 10.3 下一頁(yè)上一頁(yè) 用用Q(x)代表某一個(gè)信息多項(xiàng)式，將碼組多項(xiàng)式表示為代表某一個(gè)信息多項(xiàng)式，將碼組多項(xiàng)式表示為 c (x) = Q (g (x) Q (是不大于是不大于k-1次多項(xiàng)式，次多項(xiàng)式， g (x)是不大于是不大于m-1次的生次的生成多項(xiàng)式。與式成多項(xiàng)式。與式 c (x) = xd(r (x) 對(duì)照后可得對(duì)照后可得

40、xd(r(x) = Q (g (x) 移項(xiàng)后為移項(xiàng)后為 xd(= Q (g (x) r (x) 10.3 10.3 下一頁(yè)上一頁(yè)xd(= Q (g (x) r (x) 即即)()()()()(xgxrxQxgxdxkn 10.3 10.3 由上式可知，由上式可知，r(x)是是 xd( 除以除以g(x)得到的余式，表示為得到的余式，表示為 )()(rem)(xgxdxxrkn下一頁(yè)上一頁(yè)例：例： 用上例的生成多項(xiàng)式求系統(tǒng)循環(huán)碼的碼組，已知用上例的生成多項(xiàng)式求系統(tǒng)循環(huán)碼的碼組，已知 D= 1 0 1 0 。解：當(dāng)解：當(dāng) 時(shí)，信息多項(xiàng)式和升位后的多項(xiàng)式時(shí)，信息多項(xiàng)式和升位后的多項(xiàng)式分別為分別為 d(

41、= () = 10.3 10.3 下一頁(yè)上一頁(yè)求余式求余式r(x)的豎式為的豎式為 ) ( 1 1 1) ( 1 3334646313xrxxxxxxxxxxxxQx 10.3 10.3 下一頁(yè)上一頁(yè)余式和碼組多項(xiàng)式分別為余式和碼組多項(xiàng)式分別為 c (x) = Q (g (x) = ()() = 或或 c 1(x) = xd(r (x) = x ( = x可得系統(tǒng)循環(huán)碼碼組為可得系統(tǒng)循環(huán)碼碼組為 C = 1 0 1 0 0 1 1 10.3 10.3 下一頁(yè)上一頁(yè)當(dāng)當(dāng) 時(shí)，同樣方法可得時(shí)，同樣方法可得 c (x) = C = 1 0 1 0 0 0 1 由以上結(jié)果可以看出，用不同的生成多項(xiàng)式，

42、由以上結(jié)果可以看出，用不同的生成多項(xiàng)式，都可以得到系統(tǒng)循環(huán)碼。都可以得到系統(tǒng)循環(huán)碼。1 1 0 1 0 0 0 10.3 10.3 下一頁(yè)上一頁(yè)（2） 循環(huán)碼的譯碼循環(huán)碼的譯碼 由由 c (x) = Q (g (x) 可知，發(fā)送碼組多項(xiàng)式可知，發(fā)送碼組多項(xiàng)式c(x)是是生成多項(xiàng)式生成多項(xiàng)式g(x)的倍式。如果經(jīng)信道傳輸后發(fā)生錯(cuò)誤，的倍式。如果經(jīng)信道傳輸后發(fā)生錯(cuò)誤，接收碼組多項(xiàng)式接收碼組多項(xiàng)式 R(x) 不再是不再是 g(x)的倍式，可表示為的倍式，可表示為 或者寫成或者寫成 其中其中s(x)是是R(x)除以除以g (x)后的余式，是不大于后的余式，是不大于m-1次的碼次的碼組多項(xiàng)式，稱為組多項(xiàng)

43、式，稱為伴隨多項(xiàng)式伴隨多項(xiàng)式或或校正子多項(xiàng)式校正子多項(xiàng)式。 )()()()()(1xgxsxmxgxR )()(rem)(xgxRxs10.3 10.3 下一頁(yè)上一頁(yè) 接收碼組多項(xiàng)式接收碼組多項(xiàng)式R(x)可表示為發(fā)送碼組多項(xiàng)式與差錯(cuò)多項(xiàng)可表示為發(fā)送碼組多項(xiàng)式與差錯(cuò)多項(xiàng)式之和，即式之和，即 代入上式，得代入上式，得 由由s(x)就可進(jìn)一步確定就可進(jìn)一步確定E(x)。對(duì)于一個(gè)。對(duì)于一個(gè)s(x)， E(x)可能有可能有多種形式。由多種形式。由s(x)確定確定E(x)時(shí)同樣使用最大似然比準(zhǔn)則。時(shí)同樣使用最大似然比準(zhǔn)則。)()()(xExcxR )()(rem)()()(rem)()(rem)(xgxE

44、xgxExcxgxRxs10.3 10.3 下一頁(yè)上一頁(yè)對(duì)最小碼重的差錯(cuò)多項(xiàng)式對(duì)最小碼重的差錯(cuò)多項(xiàng)式E(x) ，由，由 求出對(duì)應(yīng)的伴隨多項(xiàng)式求出對(duì)應(yīng)的伴隨多項(xiàng)式s(x)，將，將E(x)與與s(x)的對(duì)應(yīng)關(guān)系列成的對(duì)應(yīng)關(guān)系列成譯碼表。當(dāng)收到任一碼組譯碼表。當(dāng)收到任一碼組R(x)后，利用式后，利用式求出求出s(x)，對(duì)照譯碼表找到，對(duì)照譯碼表找到E(x) ，再用式，再用式 求求c(x)，即，即 )()/(rem)(xgxExs )()/(rem)(xgxRxs )()()(xExcxR )()()(xExRxc 10.3 10.3 下一頁(yè)上一頁(yè) 原則上糾錯(cuò)可按下述步驟進(jìn)行：原則上糾錯(cuò)可按下述步驟進(jìn)

45、行： 用生成多項(xiàng)式用生成多項(xiàng)式 g（x）去除接收碼組）去除接收碼組 R（x）=c（x）+E（x），得出余式），得出余式 s（x）；）； 按余式按余式 s（x）用查表的方法或通過某種）用查表的方法或通過某種運(yùn)算得到錯(cuò)誤圖樣運(yùn)算得到錯(cuò)誤圖樣 E（x），就可以確定錯(cuò)碼位），就可以確定錯(cuò)碼位置。置。 從從 R（x）中減去）中減去 E（x），便得到已糾），便得到已糾正錯(cuò)誤的原發(fā)送碼組正錯(cuò)誤的原發(fā)送碼組 c（x）。）。10.3 10.3 下一頁(yè)上一頁(yè)例：已知糾單錯(cuò)例：已知糾單錯(cuò)(7,4)系統(tǒng)循環(huán)碼的生成多項(xiàng)式為系統(tǒng)循環(huán)碼的生成多項(xiàng)式為 ，試構(gòu)成譯碼表。，試構(gòu)成譯碼表。若接收碼組若接收碼組R= 1 0 0

46、0 1 0 1，求發(fā)送碼組。，求發(fā)送碼組。解解： 對(duì)碼重為對(duì)碼重為1的差錯(cuò)多項(xiàng)式的差錯(cuò)多項(xiàng)式 E(x) ，求出相應(yīng)的伴隨，求出相應(yīng)的伴隨多項(xiàng)式多項(xiàng)式s(x)，將其對(duì)應(yīng)結(jié)果表成譯碼表，如下表所示。，將其對(duì)應(yīng)結(jié)果表成譯碼表，如下表所示。 E(x)1110.3 10.3 下一頁(yè)上一頁(yè)當(dāng)接收碼組無錯(cuò)誤時(shí)，當(dāng)接收碼組無錯(cuò)誤時(shí)，E(x)=0，則，則s(x)=0。本題給出的接。本題給出的接收碼組為收碼組為 R= 1 0 0 0 1 0 1由此可寫出接收碼組多項(xiàng)式由此可寫出接收碼組多項(xiàng)式 對(duì)應(yīng)的伴隨多項(xiàng)式為對(duì)應(yīng)的伴隨多項(xiàng)式為 111rem)()/(rem)(2326 xxxxxxgxRxs10.3 10.3

47、下一頁(yè)上一頁(yè)查表得到查表得到 由由R(x)和和E(x)可得到譯碼碼組多項(xiàng)式可得到譯碼碼組多項(xiàng)式相應(yīng)的碼組為相應(yīng)的碼組為 C= 1 1 0 0 1 0 1由于是系統(tǒng)循環(huán)碼，所以信息碼組為由于是系統(tǒng)循環(huán)碼，所以信息碼組為 D= 1 1 0 0 1)()()(256 xxxxExRxc10.3 10.3 下一頁(yè)上一頁(yè)10.4 10.4 卷積碼又稱卷積碼又稱連環(huán)碼連環(huán)碼，是，是1955年提出來的一種糾年提出來的一種糾錯(cuò)碼，它和分組碼有明顯的區(qū)別，屬于非分組碼。錯(cuò)碼，它和分組碼有明顯的區(qū)別，屬于非分組碼。1. 基本概念基本概念 卷積碼編碼器在任何一段規(guī)定時(shí)間內(nèi)產(chǎn)生的卷積碼編碼器在任何一段規(guī)定時(shí)間內(nèi)產(chǎn)生的

48、n個(gè)個(gè)碼元，不僅取決于這段時(shí)間中碼元，不僅取決于這段時(shí)間中k個(gè)信息位，而且還取個(gè)信息位，而且還取決于前決于前N-1段規(guī)定時(shí)間內(nèi)的信息位。監(jiān)督位監(jiān)督著這段規(guī)定時(shí)間內(nèi)的信息位。監(jiān)督位監(jiān)督著這N段時(shí)間內(nèi)的信息。這段時(shí)間內(nèi)的信息。這N段時(shí)間內(nèi)的碼元數(shù)目段時(shí)間內(nèi)的碼元數(shù)目nN稱為稱為這種碼的約束長(zhǎng)度。卷積碼常用符號(hào)（這種碼的約束長(zhǎng)度。卷積碼常用符號(hào)（n，k，N）表）表示。其編碼效率為：示。其編碼效率為： =k/n下一頁(yè)上一頁(yè)10.4 10.4 簡(jiǎn)單例子：下圖為一個(gè)簡(jiǎn)單例子：下圖為一個(gè)卷積碼的編碼器。卷積碼的編碼器。6 5 4 3 2 1+輸入輸入b bi i移位寄存器移位寄存器輸出輸出b bi ic c

49、i ib b1 1b b1 1c c1 1b b2 2c c2 2b b3 3c c3 3b b4 4c c4 4b b5 5c c5 5b b6 6c c6 6b b2 2b b3 3b b4 4b b5 5b b6 6輸入輸入輸出輸出卷積碼的參量：卷積碼的參量：k=1, n=2, N=6。下一頁(yè)上一頁(yè)10.4 10.4 現(xiàn)討論卷積碼的解碼問題，這里介紹門限解碼?，F(xiàn)討論卷積碼的解碼問題，這里介紹門限解碼。 一般說來，卷積碼的譯碼可分為一般說來，卷積碼的譯碼可分為代數(shù)譯碼（利用編碼本代數(shù)譯碼（利用編碼本身的代數(shù)結(jié)構(gòu)進(jìn)行解碼）身的代數(shù)結(jié)構(gòu)進(jìn)行解碼）和和概率譯碼（解碼時(shí)要用到信道的概率譯碼（解碼時(shí)

50、要用到信道的統(tǒng)計(jì)特性）統(tǒng)計(jì)特性）兩大類。兩大類。 門限解碼門限解碼是一種二進(jìn)制碼的擇多邏輯解碼法，屬于代數(shù)解是一種二進(jìn)制碼的擇多邏輯解碼法，屬于代數(shù)解碼。它利用一組正交校驗(yàn)方程進(jìn)行計(jì)算。碼。它利用一組正交校驗(yàn)方程進(jìn)行計(jì)算?！罢徽弧笔侵杆馐侵杆獾男畔⑽?，作為校驗(yàn)方程的一個(gè)元素，出現(xiàn)在這一方程組的的信息位，作為校驗(yàn)方程的一個(gè)元素，出現(xiàn)在這一方程組的每一方程中，而其他的信息位至多在一個(gè)方程中出現(xiàn)。這樣每一方程中，而其他的信息位至多在一個(gè)方程中出現(xiàn)。這樣一來，就可以根據(jù)被錯(cuò)碼破壞了的方程組中方程數(shù)目在方程一來，就可以根據(jù)被錯(cuò)碼破壞了的方程組中方程數(shù)目在方程組中是否占多數(shù)來判斷所待解的信息位是否

51、錯(cuò)了。組中是否占多數(shù)來判斷所待解的信息位是否錯(cuò)了。下一頁(yè)上一頁(yè)對(duì)應(yīng)以上例子的對(duì)應(yīng)以上例子的門限解碼器如下圖門限解碼器如下圖。b b6 6b b5 5b b4 4b b3 3b b2 2b b1 1+輸入輸入一級(jí)移位寄存器一級(jí)移位寄存器輸出輸出信息移位寄存器信息移位寄存器S S6 6S S5 5S S4 4S S3 3S S2 2S S1 1+接收監(jiān)督位接收監(jiān)督位重算監(jiān)督位重算監(jiān)督位門限電路門限電路校正子移位寄存器校正子移位寄存器+“1 1”的個(gè)數(shù)的個(gè)數(shù) 3 3下一頁(yè)上一頁(yè)10.4 10.4 由上圖可以看出，當(dāng)傳輸?shù)拇a發(fā)生第一個(gè)位錯(cuò)時(shí)由上圖可以看出，當(dāng)傳輸?shù)拇a發(fā)生第一個(gè)位錯(cuò)時(shí)（且只有一位錯(cuò)誤）：

52、（且只有一位錯(cuò)誤）：1）若錯(cuò)碼為信息位，則僅當(dāng)它位于信息移存器中第）若錯(cuò)碼為信息位，則僅當(dāng)它位于信息移存器中第 6，3，2，1 級(jí)時(shí)才使校正子等于級(jí)時(shí)才使校正子等于“1”，因此，這時(shí)的校，因此，這時(shí)的校正子序列為正子序列為100111；2）若錯(cuò)碼為監(jiān)督位，校正子序列為）若錯(cuò)碼為監(jiān)督位，校正子序列為100000。 可見，當(dāng)校正子序列中出現(xiàn)第一個(gè)可見，當(dāng)校正子序列中出現(xiàn)第一個(gè)“1”時(shí)，則表時(shí)，則表示已檢出一個(gè)錯(cuò)碼。后面幾個(gè)校正子則指出是信息位示已檢出一個(gè)錯(cuò)碼。后面幾個(gè)校正子則指出是信息位錯(cuò)了還是監(jiān)督位錯(cuò)了。錯(cuò)了還是監(jiān)督位錯(cuò)了。下一頁(yè)上一頁(yè)10.4 10.4 按上圖電路連線，假定按上圖電路連線，假定

53、 b1以前各碼均未發(fā)生錯(cuò)誤，則以前各碼均未發(fā)生錯(cuò)誤，則校正子移存器各級(jí)中寄存的校正子值校正子移存器各級(jí)中寄存的校正子值S可用下列邏輯方程可用下列邏輯方程組表示。組表示。 )()()()()()()()()()()()()()()()()()(321666215551444333222111bEbEbEcEbESbEbEcEbESbEcEbEScEbEScEbEScEbES下一頁(yè)上一頁(yè)10.4 10.4 其中其中 為錯(cuò)碼時(shí)為錯(cuò)碼時(shí)當(dāng)當(dāng)為非錯(cuò)碼時(shí)為非錯(cuò)碼時(shí)當(dāng)當(dāng)xxxE10)(上式經(jīng)過簡(jiǎn)單線性變換，可以改寫為上式經(jīng)過簡(jiǎn)單線性變換，可以改寫為 )()()()()()()()()()()()()()(3

54、216662215551444111bEcEbEcEbESSbEbEcEbESbEcEbEScEbES 這是一組正交于這是一組正交于E(b1)的正交校驗(yàn)方程。因的正交校驗(yàn)方程。因?yàn)槊總€(gè)方程中均有一項(xiàng)為每個(gè)方程中均有一項(xiàng)E(b1)，而所有其它，而所有其它E(bi)和和E(ci)項(xiàng)，在整個(gè)方程組中至多出現(xiàn)一次。項(xiàng)，在整個(gè)方程組中至多出現(xiàn)一次。下一頁(yè)上一頁(yè)10.4 10.4 在所考查的在所考查的12個(gè)碼元（個(gè)碼元（ b1至至b6 ， c1至至c6 ）中，在）中，在錯(cuò)誤不多于錯(cuò)誤不多于2個(gè)的條件下，僅當(dāng)個(gè)的條件下，僅當(dāng) E(b1) =1，即，即b1出錯(cuò)時(shí)，出錯(cuò)時(shí)，上述方程組才可能有上述方程組才可能有3

55、個(gè)以上方程等于個(gè)以上方程等于1。 將代表上式的將代表上式的4個(gè)方程的電壓送到一個(gè)門限電路累個(gè)方程的電壓送到一個(gè)門限電路累計(jì)計(jì)“1”的個(gè)數(shù)，當(dāng)結(jié)果大于等于的個(gè)數(shù)，當(dāng)結(jié)果大于等于3時(shí)，門限電路輸出時(shí)，門限電路輸出“1”。門限電路的這一輸出除了送到解碼器輸出端的一。門限電路的這一輸出除了送到解碼器輸出端的一級(jí)移存器糾正輸出碼元級(jí)移存器糾正輸出碼元b1的錯(cuò)誤外，同時(shí)送到受的錯(cuò)誤外，同時(shí)送到受E(b1) 影響的各級(jí)校正子移存器糾正其中錯(cuò)誤。影響的各級(jí)校正子移存器糾正其中錯(cuò)誤。下一頁(yè)上一頁(yè)10.4 10.4 卷積碼常用符號(hào)（卷積碼常用符號(hào)（n，k，N）表示。其中，）表示。其中，n為為碼長(zhǎng)，碼長(zhǎng)，k為碼組中

56、信息碼元的個(gè)數(shù)，為碼組中信息碼元的個(gè)數(shù)，N為相互關(guān)聯(lián)的碼為相互關(guān)聯(lián)的碼組的個(gè)數(shù)。組的個(gè)數(shù)。卷積碼同樣也可以用矩陣的方法描述，但較抽象。卷積碼同樣也可以用矩陣的方法描述，但較抽象。因此，采用圖解的方法直觀描述其編碼過程。常用的圖因此，采用圖解的方法直觀描述其編碼過程。常用的圖解法有解法有3種：樹圖、狀態(tài)圖和格圖。種：樹圖、狀態(tài)圖和格圖。下一頁(yè)上一頁(yè)10.4 10.4 （1） 樹圖樹圖 樹圖描述的是在任何數(shù)據(jù)序列輸入時(shí)，碼字所有可能樹圖描述的是在任何數(shù)據(jù)序列輸入時(shí)，碼字所有可能的輸出。下圖所示是一種（的輸出。下圖所示是一種（2，1，3）卷積碼的編碼器。）卷積碼的編碼器。b3b2b1c1c210.4

57、 10.4 下一頁(yè)上一頁(yè)圖中，圖中，m1與與m2為移位寄存器，它們的初態(tài)均為為移位寄存器，它們的初態(tài)均為0，即，即b1 b2 b3 為為 0 0 0。 c1 ， c2與與 b1 ， b2 ， b3 的關(guān)系如下：的關(guān)系如下： c1= b1 b2 b3 c2= b1 b3b1代表當(dāng)前輸入信息位代表當(dāng)前輸入信息位,而移位寄存器狀態(tài)而移位寄存器狀態(tài)b3b2存儲(chǔ)以前信息位存儲(chǔ)以前信息位(當(dāng)前當(dāng)前寄存器寄存器m1=b1,m2=b2)。下表舉例示出此編碼器的狀態(tài)。下表舉例示出此編碼器的狀態(tài)。+b111010000b3 b2c1 c2狀態(tài)狀態(tài)0011a0101b1101d1000c0110b1011c0000

58、a0000a下一頁(yè)上一頁(yè)10.4 10.4 當(dāng)?shù)诋?dāng)?shù)?位信息為位信息為 1 時(shí)，即時(shí)，即 b1=1，因，因 b3b2 = 00，故輸出，故輸出碼元碼元 c1c2=11；第；第 2 位信息為位信息為 1，這時(shí)，這時(shí) b1 =1， b3b2 =01， c1c2 =01，依此類推。為保證輸入的全部信息位，依此類推。為保證輸入的全部信息位11010都能通過移存器，還必須在信息位加都能通過移存器，還必須在信息位加3個(gè)零。個(gè)零。 現(xiàn)在我們來分析卷積碼的樹狀圖?，F(xiàn)在我們來分析卷積碼的樹狀圖。 (下例以下例以b1=0, b3b2 =00 為起點(diǎn)為起點(diǎn))下一頁(yè)上一頁(yè)卷積碼的樹圖上圖對(duì)應(yīng)的上圖對(duì)應(yīng)的（2,1,3）

59、卷積碼）卷積碼的樹圖如下圖所示的樹圖如下圖所示0000111110100101111100000101101000001111101001011111000001011010aa= 0 0b3b2b= 0 1c= 1 0d= 1 1狀狀態(tài)態(tài) 0000000000001111101001011111000001011010010110101111起起點(diǎn)點(diǎn) 0 01 11111abc1c2abcdabcdabcdabcdabcdabcdabcd輸出碼元序列為輸出碼元序列為11010100下一頁(yè)上一頁(yè)10.4 10.4 上圖中，當(dāng)?shù)谏蠄D中，當(dāng)?shù)?位信息位信息b1=1時(shí)，碼元時(shí)，碼元c1c2為為11，

60、則狀態(tài)從，則狀態(tài)從起點(diǎn)起點(diǎn)a通過下支路到達(dá)狀態(tài)通過下支路到達(dá)狀態(tài)b；當(dāng)?shù)?；?dāng)?shù)?位信息位信息b1=0時(shí)，碼元時(shí)，碼元c1c2為為00，則狀態(tài)從起點(diǎn)，則狀態(tài)從起點(diǎn)a通過上支路到達(dá)狀態(tài)通過上支路到達(dá)狀態(tài)a。依此類。依此類推可求得整個(gè)碼樹狀圖。由該圖可以看出，從第推可求得整個(gè)碼樹狀圖。由該圖可以看出，從第4條支路條支路開始，碼樹呈現(xiàn)出重復(fù)性，即圖中標(biāo)明的上半部與下半開始，碼樹呈現(xiàn)出重復(fù)性，即圖中標(biāo)明的上半部與下半部完全相同。這就意味著從部完全相同。這就意味著從第第4位信息開始，輸出碼元已位信息開始，輸出碼元已與第與第1位信息無關(guān)位信息無關(guān)。這正說明前一圖所示的編碼器的編碼。這正說明前一圖所示的編碼器