第10章_糾錯(cuò)編碼

1、第 10 章 差錯(cuò)控制編碼 第第 10 章章 差錯(cuò)控制編碼差錯(cuò)控制編碼 10.1 概述概述 10.2 常用的幾種簡(jiǎn)單分組碼常用的幾種簡(jiǎn)單分組碼 10.3 線性分組碼線性分組碼 10.4 循環(huán)碼循環(huán)碼 10.5 卷積碼卷積碼第 10 章 差錯(cuò)控制編碼 本章內(nèi)容在數(shù)字通信系統(tǒng)中所處的位置本章內(nèi)容在數(shù)字通信系統(tǒng)中所處的位置第 10 章 差錯(cuò)控制編碼 一、信源編碼和信道編碼一、信源編碼和信道編碼 在數(shù)字通信中，根據(jù)不同的目的，編碼可分在數(shù)字通信中，根據(jù)不同的目的，編碼可分為為信源編碼和信道編碼信源編碼和信道編碼。 信源編碼信源編碼是為了提高數(shù)字通信的有效性以及是為了提高數(shù)字通信的有效性以及使模擬信號(hào)數(shù)

2、字化而采取的編碼技術(shù)。使模擬信號(hào)數(shù)字化而采取的編碼技術(shù)。 信道編碼信道編碼是為了降低誤碼率，提高數(shù)字通信是為了降低誤碼率，提高數(shù)字通信的可靠性而采取的編碼。的可靠性而采取的編碼。 10.1 概概 述述 第 10 章 差錯(cuò)控制編碼 數(shù)字信號(hào)在傳輸過程中受到干擾的影響，使信號(hào)波形變壞，發(fā)生誤碼，可以采用一些方法解決。差錯(cuò)出現(xiàn)原因v 外界噪聲v 傳輸中碼間串?dāng)_解決方法v 合理地設(shè)計(jì)基帶信號(hào)，選擇調(diào)制、解調(diào)方式，采用均衡技術(shù)，提高發(fā)送功率等因素，使誤比特率降低。v 差錯(cuò)控制編碼。第 10 章 差錯(cuò)控制編碼 n 在信息碼上附加一定位數(shù)的監(jiān)督碼元，使其與信息位按某在信息碼上附加一定位數(shù)的監(jiān)督碼元，使其與信

3、息位按某種規(guī)則相互關(guān)聯(lián)；種規(guī)則相互關(guān)聯(lián)；n 若數(shù)據(jù)在傳輸過程中發(fā)生差錯(cuò)，關(guān)聯(lián)關(guān)系被破壞，從而可若數(shù)據(jù)在傳輸過程中發(fā)生差錯(cuò)，關(guān)聯(lián)關(guān)系被破壞，從而可 檢出和檢出和/ /或糾正錯(cuò)誤?；蚣m正錯(cuò)誤。第 10 章 差錯(cuò)控制編碼 n ： 信息碼與監(jiān)督碼之間的關(guān)系為線性關(guān)系；信息碼與監(jiān)督碼之間的關(guān)系為線性關(guān)系； ：信息碼與監(jiān)督碼之間的關(guān)系為非線性關(guān)系。：信息碼與監(jiān)督碼之間的關(guān)系為非線性關(guān)系。n ：監(jiān)督碼只與本組信息碼有系；：監(jiān)督碼只與本組信息碼有系； ：監(jiān)督碼與本組和前面碼組中的信息碼有關(guān)。：監(jiān)督碼與本組和前面碼組中的信息碼有關(guān)。n ： 編碼后碼組中信息碼保持原圖樣順序不變；編碼后碼組中信息碼保持原圖樣順序不

4、變； ：編碼后碼組中原信息碼原圖樣發(fā)生變化。：編碼后碼組中原信息碼原圖樣發(fā)生變化。第 10 章 差錯(cuò)控制編碼 n ：誤碼的位置隨機(jī)（誤碼間無關(guān)聯(lián)），隨機(jī)誤碼：誤碼的位置隨機(jī)（誤碼間無關(guān)聯(lián)），隨機(jī)誤碼 主要由白噪聲引起。主要由白噪聲引起。n ：誤碼成串出現(xiàn)，主要由強(qiáng)脈沖及雷電等突發(fā)的：誤碼成串出現(xiàn)，主要由強(qiáng)脈沖及雷電等突發(fā)的 強(qiáng)干擾引起。強(qiáng)干擾引起。n ：以上兩種誤碼及產(chǎn)生原因的組合。：以上兩種誤碼及產(chǎn)生原因的組合。第 10 章 差錯(cuò)控制編碼 信道編碼的核心問題信道編碼的核心問題v 發(fā)現(xiàn)錯(cuò)誤發(fā)現(xiàn)錯(cuò)誤v 糾正錯(cuò)誤糾正錯(cuò)誤第 10 章 差錯(cuò)控制編碼 v 碼長(zhǎng)：碼字中碼元的個(gè)數(shù)，通常用n表示。v碼重：

5、碼字中非零碼元的個(gè)數(shù)定義為該碼字的重量，簡(jiǎn)稱碼重。如“10011”碼字的碼重為3。v 碼距：兩個(gè)等長(zhǎng)碼字之間對(duì)應(yīng)碼元不同的數(shù)目，通常用d表示。兩個(gè)碼字對(duì)應(yīng)位模2相加得到的新碼組的重量就是這兩個(gè)碼字之間的距離。 niii 1dAB （1）幾個(gè)概念）幾個(gè)概念第 10 章 差錯(cuò)控制編碼 v 編碼效率：信息碼元數(shù)與碼長(zhǎng)之比，通常用 表示，其中k為信息碼元的數(shù)目，n為碼長(zhǎng)。v最小碼距：在一個(gè)碼字集合中，任意兩個(gè)碼字間距離的最小值，即碼字集合中任意兩元素間的最小距離，記為dmin或d0糾錯(cuò)碼的抗干擾能力完全取決于許用碼字之間的距糾錯(cuò)碼的抗干擾能力完全取決于許用碼字之間的距離，碼的最小距離越大，說明碼字間的

6、最小差別越離，碼的最小距離越大，說明碼字間的最小差別越大，抗干擾能力就越強(qiáng)。大，抗干擾能力就越強(qiáng)。nk第 10 章 差錯(cuò)控制編碼 舉例說明：假如要傳送舉例說明：假如要傳送A、B兩個(gè)消息兩個(gè)消息編碼一：消息A-“0”；消息B-“1”最小碼距1若傳輸中產(chǎn)生錯(cuò)碼（“0”錯(cuò)成“1”或“1”錯(cuò)成“0”）收端無法發(fā)現(xiàn)，該編碼無檢錯(cuò)糾錯(cuò)能力。第 10 章 差錯(cuò)控制編碼 編碼二：消息A-“00”；消息B-“11”最小碼距2若傳輸中產(chǎn)生一位錯(cuò)碼，則變成“01”或“10”，收端判決為有錯(cuò)（因“01”“10”為禁用碼組），但無法確定錯(cuò)碼位置，不能糾正，該編碼具有檢出一位錯(cuò)碼的能力。這表明增加一位冗余碼元后碼具有檢出

7、一位錯(cuò)碼的能力第 10 章 差錯(cuò)控制編碼 編碼三：消息A-“000”；消息B-“111”最小碼距3傳輸中產(chǎn)生一位即使兩位錯(cuò)碼，都將變成禁用碼組，收端判決傳輸有錯(cuò)。該編碼具有檢出兩位錯(cuò)碼的能力。在產(chǎn)生一位錯(cuò)碼情況下，收端可根據(jù)“大數(shù)”法則進(jìn)行正確判決，能夠糾正這一位錯(cuò)碼。例如收到110，認(rèn)為是111。這表明增加兩位冗余碼元后碼具有檢出兩位錯(cuò)碼及糾正一位錯(cuò)碼的能力。第 10 章 差錯(cuò)控制編碼 一個(gè)碼能檢測(cè)e個(gè)錯(cuò)碼，則要求其最小碼dmine+1一個(gè)碼能糾正t個(gè)錯(cuò)碼，則要求其最小dmin2t+1一個(gè)碼能糾正t個(gè)錯(cuò)碼，同時(shí)能檢測(cè)e個(gè)錯(cuò)碼，則要求其最小碼距 dmine+t+1 (et)（2）最小碼距與檢錯(cuò)

8、和糾錯(cuò)能力的關(guān)系）最小碼距與檢錯(cuò)和糾錯(cuò)能力的關(guān)系第 10 章 差錯(cuò)控制編碼 v 奇偶監(jiān)督碼v 二維奇偶監(jiān)督碼（略，見附錄）v 恒比碼10.2 常用的幾種簡(jiǎn)單分組碼常用的幾種簡(jiǎn)單分組碼第 10 章 差錯(cuò)控制編碼 10.2.1 奇偶監(jiān)督碼奇偶監(jiān)督碼 1 2 3kk 1123kk 1k 1123k123kk 1k 1123kkaa a .ar1aaaa .aa0aaaa .aaaa .aa1aaaa .a1 對(duì)對(duì) 位位碼碼元元校校驗(yàn)驗(yàn)位位偶偶校校驗(yàn)驗(yàn) 奇奇校校驗(yàn)驗(yàn) 奇偶監(jiān)督碼：在信息碼元后附加一位監(jiān)督位，使得碼組中奇偶監(jiān)督碼“1”的個(gè)數(shù)為偶數(shù)或奇數(shù)。第 10 章 差錯(cuò)控制編碼 序號(hào) 碼長(zhǎng)為4的奇奇監(jiān)

9、督碼序號(hào) 碼長(zhǎng)為4的偶偶監(jiān)督碼 信息碼元 監(jiān)督碼元 信息碼元 監(jiān)督碼元 0000100000 1001010011 2010020101 3011130110 4100041001 5101151010 6110161100 7111071111表：碼長(zhǎng)為4的奇、偶監(jiān)督碼第 10 章 差錯(cuò)控制編碼 v只能檢測(cè)出單個(gè)或奇數(shù)個(gè)錯(cuò)誤，不能檢測(cè)偶數(shù)個(gè)錯(cuò)誤v不能糾錯(cuò)。v 應(yīng)用：以隨機(jī)錯(cuò)誤為主的計(jì)算機(jī)通信系統(tǒng)，難于對(duì)付突發(fā)錯(cuò)誤v 編碼效率=k/n=k/(k+1)，是一種高效率碼。10.2.2二維奇偶監(jiān)督碼見附錄二維奇偶監(jiān)督碼見附錄 第 10 章 差錯(cuò)控制編碼 表表 10-1 3 2 恒比碼恒比碼 （是一種

10、五中取三碼）（是一種五中取三碼）10.2.3 恒比碼恒比碼 碼字中碼字中1 1的數(shù)目與的數(shù)目與0 0的數(shù)目保持恒定比例的數(shù)目保持恒定比例的碼稱為恒比碼。又的碼稱為恒比碼。又稱等重碼，定稱等重碼，定1 1碼。碼。 這種碼在檢測(cè)時(shí)，這種碼在檢測(cè)時(shí)，通過計(jì)算接收碼元中通過計(jì)算接收碼元中1 1的數(shù)目是否正確，就的數(shù)目是否正確，就知道有無錯(cuò)誤。知道有無錯(cuò)誤。第 10 章 差錯(cuò)控制編碼 線性分組碼：先將信息碼分組，然后給每組信碼附加若干監(jiān)督碼的編碼稱為分組碼。若附加的監(jiān)督碼和信息碼由一些線性代數(shù)方程相則稱為線性分組碼。用符號(hào)(n,k)表示，k是信息碼的位數(shù)，n是編碼組總位數(shù)，又稱為碼長(zhǎng)，r=n-k為監(jiān)督位

11、數(shù)。1、基本概念基本概念10.3 線性分組碼（重點(diǎn)）線性分組碼（重點(diǎn)）第 10 章 差錯(cuò)控制編碼 現(xiàn)以(7,4)分組碼為例來說明線性分組碼的特點(diǎn)。設(shè)其碼字為A=a6 a5 a4 a3 a2 a1 a0，其中前 4 位是信息元，后 3 位是監(jiān)督元， 可用下列線性方程組來描述該分組碼，產(chǎn)生監(jiān)督元。 346035614562aaaaaaaaaaaa第 10 章 差錯(cuò)控制編碼 表表 10-2 (7,4)碼的碼字表碼的碼字表 第 10 章 差錯(cuò)控制編碼 2、線性分組碼的性質(zhì)、線性分組碼的性質(zhì)v任意兩個(gè)許用碼組之和（逐位模2和）仍為一許用碼組，即具有封閉性。v最小碼距=非零碼的最小碼重（1的個(gè)數(shù)）。第 1

12、0 章 差錯(cuò)控制編碼 10.3.2 監(jiān)督矩陣監(jiān)督矩陣H和生成矩陣和生成矩陣G 第 10 章 差錯(cuò)控制編碼 其中,P為rk階矩陣，Ir為rr階單位矩陣。可以寫成H=P Ir形式的矩陣稱為典型監(jiān)督矩陣。 HAT=0T，說明H矩陣與碼字的轉(zhuǎn)置乘積必為零，可以用來作為判斷接收碼字A是否出錯(cuò)的依據(jù)。 并簡(jiǎn)記為 第 10 章 差錯(cuò)控制編碼 v rn階矩陣v 監(jiān)督矩陣H確定了編碼時(shí)監(jiān)督碼元與信息碼元的關(guān)系v 把具有PIr形式的H矩陣稱為典型形式的監(jiān)督矩陣，其中P為r k階矩陣, Ir為r r階單位方陣v H矩陣的各行應(yīng)線性無關(guān)。矩陣若能寫成典型形式，則其各行一定線性無關(guān)監(jiān)督矩陣H特點(diǎn)第 10 章 差錯(cuò)控制編

13、碼 若把監(jiān)督方程補(bǔ)充為下列方程 第 10 章 差錯(cuò)控制編碼 可改寫為矩陣形式 第 10 章 差錯(cuò)控制編碼 1101000101010001100101110001GQIGkTPQ110101011111第 10 章 差錯(cuò)控制編碼 vk n階矩陣v把具有IkQ形式的G矩陣稱為典型形式的生成矩陣，其中，Ik為kk階單位方陣，Q為k r階矩陣v由典型生成矩陣產(chǎn)生的分組碼一定是系統(tǒng)碼vG矩陣的各行應(yīng)線性無關(guān)，每行均為許用碼組生成矩陣G特點(diǎn)第 10 章 差錯(cuò)控制編碼 已知（6，3）漢明碼(能糾正單個(gè)錯(cuò)誤的線性分組碼)的生成矩陣如下，(1)列出所有許用碼組;(2)最小碼距d0;(3)檢錯(cuò)糾錯(cuò)能力(4)編碼

14、效率100101G010011001110 第 10 章 差錯(cuò)控制編碼 543AaaaG （1）信息碼信息碼編碼碼字編碼碼字碼重碼重0 0 00 0 0 0 0 000 0 10 0 1 1 1 030 1 00 1 0 0 1 130 1 10 1 11 0 141 0 01 0 0 1 0 131 0 11 0 1 0 1 141 1 01 1 0 1 1 041 1 1 1 1 1 0 0 03第 10 章 差錯(cuò)控制編碼 （3）（4）000e=d -1=2d -1t=12et1det21 該該碼碼可可以以檢檢2 2位位錯(cuò)錯(cuò)該該碼碼可可以以糾糾1 1位位錯(cuò)錯(cuò)該該碼碼不不能能同同時(shí)時(shí)檢檢 位

15、位錯(cuò)錯(cuò)與與糾糾 位位錯(cuò)錯(cuò)。k350%n6 （2）0d3 第 10 章 差錯(cuò)控制編碼 1101000101010001100101110001設(shè)（設(shè)（7,4）線性碼的生成矩陣）線性碼的生成矩陣G為：為：當(dāng)信息位為當(dāng)信息位為0001時(shí)，時(shí)，（1）試求其后的監(jiān)督位。）試求其后的監(jiān)督位。（2）監(jiān)督矩陣）監(jiān)督矩陣H第 10 章 差錯(cuò)控制編碼 6543AaaaaG 解：解：（1） 10001110100110A0 0 0 10 0 0 1 0 1 100101010001011第 10 章 差錯(cuò)控制編碼 （2）監(jiān)督矩陣）監(jiān)督矩陣H根據(jù)生成矩陣和監(jiān)督矩陣的關(guān)系：根據(jù)生成矩陣和監(jiān)督矩陣的關(guān)系：G= IkQ，H

16、=PIr其中其中P=QT，可得監(jiān)督矩陣，可得監(jiān)督矩陣H為：為：100110101010110010111第 10 章 差錯(cuò)控制編碼 v錯(cuò)誤矩陣/錯(cuò)誤圖樣E：設(shè)發(fā)送碼組為A，接收碼組為B，則錯(cuò)誤矩陣 n 1n 210n 1n 210Aaa. a aBbb. b b n 1n 210iiiiiiiEBAee. e e1baeba0ba 該該位位有有錯(cuò)錯(cuò)該該位位無無錯(cuò)錯(cuò)10.3.3 伴隨式伴隨式(校正子校正子)S 第 10 章 差錯(cuò)控制編碼 v接收端計(jì)算校正子S，即S=BHT=(A+E)HT=AHT+EHT=0+ EHT= EHT 校正子只與E有關(guān)，即錯(cuò)誤圖樣與校正子之間有確定的關(guān)系.確定錯(cuò)誤圖樣與

17、校正子的關(guān)系表?？蓮谋碇姓业缅e(cuò)碼位置，加以糾正。第 10 章 差錯(cuò)控制編碼 表表 10-3 (7,4)碼碼S與與E的對(duì)應(yīng)關(guān)系的對(duì)應(yīng)關(guān)系 第 10 章 差錯(cuò)控制編碼 v以（7，4）漢明碼為例設(shè)發(fā)送碼組A=（0001011）接收碼組 B=（0000011）則收端譯碼過程如下：計(jì)算校正子 T111110101SBH0 0 0 0 0 1 1011011100010001 查表得b3為錯(cuò)誤位置，即可糾正（0001011）第 10 章 差錯(cuò)控制編碼 10.4 循循 環(huán)環(huán) 碼碼 循環(huán)碼是一種重要的線性分組碼。這種碼的編碼和解碼設(shè)備都不太復(fù)雜，且有較強(qiáng)的檢（糾）錯(cuò)能力。共n位，通常前k位為信息位，后r位為監(jiān)

18、督位。10.4.1 10.4.1 循環(huán)碼的編碼原理循環(huán)碼的編碼原理第 10 章 差錯(cuò)控制編碼 循環(huán)碼的特點(diǎn)：v 封閉性；v 循環(huán)性；即碼中任一碼組循環(huán)一位(將最右端的碼元移到左端或反之）以后，仍為該碼中的一個(gè)碼組。第 10 章 差錯(cuò)控制編碼 若(an-1,an-2,a1,a0)是一(n,k)循環(huán)碼的碼組，則(an-2 ,an-3 ,a1,a0 ,an-1)(an-3 ,an-4 , , a0 , an-1 ,an-2) ( a0 ,an-1 , an-2 ,an-3 ,a2 ,a1) 也都是該循環(huán)碼的碼組。第 10 章 差錯(cuò)控制編碼 表一種（表一種（7 7，3 3）循環(huán)碼的全部碼字）循環(huán)碼的全

19、部碼字序序號(hào)號(hào)碼字碼字 序序號(hào)號(hào)碼字碼字信息位信息位a6 a5 a4a6 a5 a4監(jiān)督位監(jiān)督位a3 a2 a1 a0a3 a2 a1 a0信息位信息位a6 a5 a4a6 a5 a4監(jiān)督位監(jiān)督位a3 a2 a1 a0a3 a2 a1 a01 10 0 0 0 0 00 0 0 0 0 0 0 05 51 1 0 0 0 01 1 0 0 1 1 1 12 20 0 0 0 1 10 0 1 1 1 1 1 16 61 1 0 0 1 11 1 1 1 0 0 0 03 30 0 1 1 0 01 1 1 1 1 1 0 07 71 1 1 1 0 00 0 1 1 0 0 1 14 40 0

20、 1 1 1 11 1 0 0 0 0 1 18 81 1 1 1 1 10 0 0 0 1 1 0 0第 10 章 差錯(cuò)控制編碼 把碼長(zhǎng)為n的碼組中的各碼元當(dāng)作n-1次多項(xiàng)式的系數(shù)若碼組A=（an-1，an-2，a1，a0)，則其相應(yīng)的碼多項(xiàng)式為(以降冪順序排列以降冪順序排列) ： A(x)= an-1xn-1+ an-1xn-2+ + a1x+ a0對(duì)于（7，3）循環(huán)碼的任意碼組可表示為： A(x)= a6x6+ a5x5+ a4x4 + a3x3 + a2x2 + a1x+ a0如碼組（1100101）對(duì)應(yīng)的碼多項(xiàng)式可表示為A7(x)= 1x6+1 x5+ 0 x4 + 0 x3 + 1

21、 x2 + 0 x+1 = x6 + x5 + x2 +11、碼多項(xiàng)式、碼多項(xiàng)式A(x)第 10 章 差錯(cuò)控制編碼 表表 10-4 (7,3)循環(huán)碼循環(huán)碼 寫出各個(gè)碼寫出各個(gè)碼字多項(xiàng)式？字多項(xiàng)式？最低次多項(xiàng)最低次多項(xiàng)式的次數(shù)是式的次數(shù)是多少？多少？第 10 章 差錯(cuò)控制編碼 10.4.1 生成多項(xiàng)式及生成矩陣生成多項(xiàng)式及生成矩陣 如果一種碼的所有碼多項(xiàng)式都是多項(xiàng)式g(x)的倍式，則稱g(x)為該碼的生成多項(xiàng)式。 在(n,k)循環(huán)碼中任意碼多項(xiàng)式A(x)都是最低次(r次次)碼多項(xiàng)式的倍式。如表 10-4 的(7,3)循環(huán)碼中， 1)()(2341xxxxAxg第 10 章 差錯(cuò)控制編碼 )()(

22、)()()() 1()()(0)(27320 xgxxAxgxxAxgxxAxgxA其它碼多項(xiàng)式都是g(x)的倍式， 即 第 10 章 差錯(cuò)控制編碼 可以證明生成多項(xiàng)式可以證明生成多項(xiàng)式g(x)具有以下特性：具有以下特性： （1） g(x)是一個(gè)常數(shù)項(xiàng)為是一個(gè)常數(shù)項(xiàng)為1的的 次次多項(xiàng)式；多項(xiàng)式； （2） g(x)是是 的一個(gè)因式；的一個(gè)因式； （3）該循環(huán)碼中其它碼多項(xiàng)式都是該循環(huán)碼中其它碼多項(xiàng)式都是g(x)的倍式。的倍式。knr1nx4243212(7 3)( )( )1;( )1g xg xxxxgxxxx對(duì)于 ，循環(huán)碼，符合碼生成多項(xiàng)式條件的有兩個(gè)可以構(gòu)造出兩種循環(huán)碼組；它們的d0、檢錯(cuò)

23、、糾錯(cuò)能力相同第 10 章 差錯(cuò)控制編碼 g(x)， ， xk-1g(x)都是許用碼組，連同g(x)共k個(gè)許用碼組，構(gòu)成碼的生成矩陣G(x)注：該生成矩陣并不是典型形式的，但可通過線性變換變換成典型的生成矩陣。)()()()()(21xgxxgxgxxgxXGkk循環(huán)碼的循環(huán)碼的生成矩陣生成矩陣常用多項(xiàng)式的形式來表示常用多項(xiàng)式的形式來表示 第 10 章 差錯(cuò)控制編碼 例如(7,3)循環(huán)碼，n=7, k=3, r=4, 其生成多項(xiàng)式及生成矩陣分別為 第 10 章 差錯(cuò)控制編碼 111111111101001101001110001010110001010011100111010001010111

24、0100110001010110001001110011101001011000010110000000例：已知（例：已知（7，4）循環(huán)碼的全部碼組為：）循環(huán)碼的全部碼組為：試寫出該循環(huán)碼的生成多項(xiàng)式試寫出該循環(huán)碼的生成多項(xiàng)式g(x)和生成和生成矩陣矩陣G，并將并將G化成典型矩陣?；傻湫途仃?。第 10 章 差錯(cuò)控制編碼 解：解：n=7，k=4，n-k=3上述碼組中的上述碼組中的(n-k)=3次碼多項(xiàng)式為第次碼多項(xiàng)式為第2組，它所組，它所對(duì)應(yīng)的碼多項(xiàng)式對(duì)應(yīng)的碼多項(xiàng)式g(x)即為生成多項(xiàng)式：即為生成多項(xiàng)式：g(x)=x3+x+1。生成矩陣為：生成矩陣為：364325321423x g(x)xxx

25、x g(x)xxxG(x)x g(x)xxxg(x)xx110110001000101010110001001110010110001011000010110001011 第 10 章 差錯(cuò)控制編碼 10.4.2 監(jiān)督多項(xiàng)式及監(jiān)督矩陣監(jiān)督多項(xiàng)式及監(jiān)督矩陣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)式。同理，可得監(jiān)督矩陣H )(*)(*)(*)(1xhxxhxhxxHkn第 10 章 差錯(cuò)控制編碼 是h(x)的逆多項(xiàng)式。例如(7，3)循環(huán)碼，g(x)=x4+x3+x2+1，則 其中 1)(

26、*12211xhxhxhxxhkkkk1)(*1)(1)(3237xxxhxxxgxxh111( )1kkkh xxhxh x第 10 章 差錯(cuò)控制編碼 1)(324235346xxxxxxxxxxxxH1101000011010000110100001101H第 10 章 差錯(cuò)控制編碼 10.4.3 編碼方法和電路編碼方法和電路 思路思路：在編碼時(shí)，首先要根據(jù)給定的(n,k)值選定生成多項(xiàng)式g(x)，即應(yīng)在xn+1的因式中選一r=n-k次,常數(shù)項(xiàng)為1的多項(xiàng)式作為g(x)。設(shè)編碼前的信息多項(xiàng)式m(x)為 12321)(kkxaxaxaaxm循環(huán)碼的碼多項(xiàng)式可表示為 )()()(xRxmxxAr

27、用xr乘m(x)，相當(dāng)于把信息碼后附加上r個(gè)“0”第 10 章 差錯(cuò)控制編碼 用g(x)除xr m(x)，得到商式Q(x)和余式為R(x) 編出碼組為：A(x)= xr m(x)+ R(x) xgxRxQxgxmxr10.4.3 編碼解碼電路（略）編碼解碼電路（略） 第 10 章 差錯(cuò)控制編碼 11) 1(1)()(24222456xxxxxxxxxxxxgxmxkn即余式即余式r(x)=x2+1于是，對(duì)應(yīng)碼組于是，對(duì)應(yīng)碼組A(x)= xn-k m(x)+r(x）= x6+x5+ x2+1 編碼為編碼為1100101例題例題 設(shè)（設(shè)（7，3）循環(huán)碼的生成多項(xiàng)式為）循環(huán)碼的生成多項(xiàng)式為g(x)=

28、x4+x2+x+1，待編碼信息位為待編碼信息位為110，求對(duì)應(yīng)循，求對(duì)應(yīng)循環(huán)碼碼組。環(huán)碼碼組。解：解：m(x)=x2+x，xn-k m(x)=x4(x2+x)=x6+x5第 10 章 差錯(cuò)控制編碼 10.6 卷卷 積積 碼碼 10.6.1 基本概念基本概念 1、卷積碼：用(n,k,m)表示，每個(gè)(n,k) 碼段(字碼)中的n個(gè)碼元不僅與該碼段內(nèi)的k個(gè)信息元有關(guān)，而且與前面m個(gè)信息元有關(guān)（有記憶性）。2、編碼器：由k個(gè)輸入，n個(gè)輸出，m個(gè)移位寄存器和一些輔助電路(模2加法器及開關(guān)電路)構(gòu)成的有記憶系統(tǒng)。3、卷積碼編碼過程通常可用樹圖、狀態(tài)圖和格圖來描述第 10 章 差錯(cuò)控制編碼 例：例： 卷積碼

29、卷積碼(2,1,2)編碼器（編碼器（P284，圖，圖9-7） m1m2數(shù)據(jù)輸入碼字輸出S1S2S3C1C2起始狀態(tài)：各級(jí)移位寄存器清零，即S2S3為00。存儲(chǔ)狀態(tài)：S3S2的4種狀態(tài)00、01、10、11S1等于當(dāng)前輸入數(shù)據(jù)C=C1C2第 10 章 差錯(cuò)控制編碼 3123211SSCSSSC當(dāng)輸入數(shù)據(jù)為11010時(shí)，(2,1,2)編碼器的工作過程 輸出碼字C由下式確定： 編碼輸出為：11010100101100 第 10 章 差錯(cuò)控制編碼 編碼約束度編碼約束度：每：每1位數(shù)據(jù)，將影響位數(shù)據(jù)，將影響(m+1)個(gè)輸出字個(gè)輸出字碼，稱碼，稱(m+1)為編碼約束度。例（為編碼約束度。例（2，1，2）編

30、碼）編碼約束度為約束度為3。約束長(zhǎng)度約束長(zhǎng)度：每個(gè)子碼有：每個(gè)子碼有n個(gè)碼元，在卷積碼中有個(gè)碼元，在卷積碼中有約束關(guān)系的最大碼元長(zhǎng)度為約束關(guān)系的最大碼元長(zhǎng)度為(m+1).n，稱為約束，稱為約束長(zhǎng)度。例（長(zhǎng)度。例（2，1，2）約束長(zhǎng)度為）約束長(zhǎng)度為6。編碼約束度3約束長(zhǎng)度6第 10 章 差錯(cuò)控制編碼 10.6.2 卷積碼的描述（用圖解法）卷積碼的描述（用圖解法） 1. 樹圖樹圖 圖圖 7-6 (2,1,2)碼的樹圖碼的樹圖 a1100abb0110cdc0011abd1001cd0010a1101ba0011a1100abb0110cdc0011abd1001cd1101c0010db1001a

31、1100數(shù)碼起點(diǎn)狀態(tài)a00b01c10d11上半部下半部數(shù)碼110101第 10 章 差錯(cuò)控制編碼 2狀態(tài)圖狀態(tài)圖用狀態(tài)圖來描述。下圖就是該（用狀態(tài)圖來描述。下圖就是該（2，1，2）卷積碼編碼器的）卷積碼編碼器的狀態(tài)圖。狀態(tài)圖。 在圖中有在圖中有4個(gè)節(jié)點(diǎn)個(gè)節(jié)點(diǎn)a、b、c、d，同樣分別表示，同樣分別表示S3S2的的4種可種可能狀態(tài)。每個(gè)節(jié)點(diǎn)有兩條線，實(shí)線表示輸入數(shù)據(jù)為能狀態(tài)。每個(gè)節(jié)點(diǎn)有兩條線，實(shí)線表示輸入數(shù)據(jù)為0，虛線，虛線表示輸入數(shù)據(jù)為表示輸入數(shù)據(jù)為1，線旁的數(shù)字即為輸出碼字。，線旁的數(shù)字即為輸出碼字。圖（圖（2 2，1 1，2 2）卷積碼的狀態(tài)圖）卷積碼的狀態(tài)圖0010第 10 章 差錯(cuò)控制

32、編碼 3 3格圖格圖 格圖也稱網(wǎng)絡(luò)或籬笆圖，它由樹圖在時(shí)間上展開而格圖也稱網(wǎng)絡(luò)或籬笆圖，它由樹圖在時(shí)間上展開而得到，實(shí)線表示數(shù)據(jù)為得到，實(shí)線表示數(shù)據(jù)為0 0，虛線表示數(shù)據(jù)為，虛線表示數(shù)據(jù)為1 1，線旁數(shù)字，線旁數(shù)字為輸出碼字，節(jié)點(diǎn)表示狀態(tài)。為輸出碼字，節(jié)點(diǎn)表示狀態(tài)。 以上的以上的3 3種卷積碼的描述方法，不但有助于求解輸出碼種卷積碼的描述方法，不但有助于求解輸出碼字，了解編碼工作過程，而且對(duì)研究解碼方法也很有用。字，了解編碼工作過程，而且對(duì)研究解碼方法也很有用。圖圖 （2 2，1 1，2 2）卷積碼的格圖）卷積碼的格圖第 10 章 差錯(cuò)控制編碼 三、卷積碼的譯碼（略）三、卷積碼的譯碼（略） 卷

33、積碼的譯碼可分為卷積碼的譯碼可分為代數(shù)代數(shù)譯碼和譯碼和概率概率譯碼兩大類。譯碼兩大類。代數(shù)譯碼目前用的很少代數(shù)譯碼目前用的很少概率譯碼已成為卷積碼最主要的譯碼方概率譯碼已成為卷積碼最主要的譯碼方法法維比特譯碼維比特譯碼序列譯碼序列譯碼第 10 章 差錯(cuò)控制編碼 維比特譯碼：最大似然譯碼把接收的碼字與所有可能所有可能的碼字比較，選擇一種碼距最小的碼字作為解碼輸出對(duì)接收的序列進(jìn)行分段處理，保留碼距最小的路徑，直至譯完整個(gè)序列例：（2，1，2）卷積碼收端收到的序列為010101 101001 其中8條路徑中紅色的這條是碼距最?。?）的一條路徑：對(duì)對(duì)010101譯碼為：譯碼為：110第 10 章 差

34、錯(cuò)控制編碼 本章小結(jié)：1、信源編碼、信道編碼的概念和區(qū)別2、線性分組碼、循環(huán)碼的相關(guān)概念、編碼、譯碼作業(yè)：9-12、9-13、9-19、9-23、9-27第 10 章 差錯(cuò)控制編碼 v 將經(jīng)過奇偶監(jiān)督編碼的碼元序列按行排成方陣，每行為一組奇偶監(jiān)督碼，但發(fā)送時(shí)按列的順序傳輸v 接收端將碼元排成發(fā)送時(shí)的方陣形式，再按行進(jìn)行奇偶校驗(yàn)v 能夠發(fā)現(xiàn)某行上所有奇數(shù)個(gè)錯(cuò)誤以及突發(fā)長(zhǎng)度不大于方陣行數(shù)的突發(fā)錯(cuò)誤v 編碼效率附錄：附錄： 2、水平奇偶監(jiān)督碼、水平奇偶監(jiān)督碼pqpqp(q1) 信信息息碼碼元元共共 行行 列列第 10 章 差錯(cuò)控制編碼 信 息 碼 元監(jiān)督碼元111000000011101001101

35、0100001110110001000010011001110111水平奇偶監(jiān)督碼水平奇偶監(jiān)督碼111011100110000.0110110101第一個(gè)碼元第二個(gè)碼元第三個(gè)碼元第十個(gè)碼元監(jiān)督碼元第 10 章 差錯(cuò)控制編碼 水平奇偶監(jiān)督碼接收端出現(xiàn)突發(fā)誤碼示例水平奇偶監(jiān)督碼接收端出現(xiàn)突發(fā)誤碼示例信 息 碼 元監(jiān)督碼元11100000001110100110101000011101100010000100110011101111101結(jié)論：結(jié)論：能夠發(fā)現(xiàn)突發(fā)長(zhǎng)度不大于方陣能夠發(fā)現(xiàn)突發(fā)長(zhǎng)度不大于方陣行數(shù)的突發(fā)錯(cuò)誤行數(shù)的突發(fā)錯(cuò)誤第 10 章 差錯(cuò)控制編碼 v 又稱為方陣碼、行列監(jiān)督碼、二維奇偶監(jiān)督碼。v 將水平奇偶監(jiān)督碼推廣到二維。即在水平監(jiān)督基礎(chǔ)上再對(duì)方陣中每一列進(jìn)行奇偶校驗(yàn)，發(fā)送時(shí)按列的順序傳輸v 接收端將碼元排成發(fā)送時(shí)的方陣形式，再分別按行、按列進(jìn)行奇偶校驗(yàn)3、水平垂直奇偶監(jiān)督碼、水平垂直奇偶監(jiān)督碼第 10 章 差錯(cuò)控制編碼 v 能夠發(fā)現(xiàn)某行、某列上所有奇數(shù)個(gè)錯(cuò)誤以及突發(fā)長(zhǎng)度不大于方陣行數(shù)或列數(shù)的突發(fā)錯(cuò)誤；v 有可能檢測(cè)出偶數(shù)個(gè)錯(cuò)誤（在行上檢測(cè)不出，但有可能在列上檢測(cè)出），但當(dāng)偶數(shù)個(gè)錯(cuò)誤剛好構(gòu)成矩形時(shí)，則檢測(cè)不出v 可糾正一些錯(cuò)誤mn(m1)(n1) 編編碼碼效效率