第10章_糾錯編碼

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

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

3、附加一定位數(shù)的監(jiān)督碼元，使其與信息位按某 種規(guī)則相互關(guān)聯(lián)；種規(guī)則相互關(guān)聯(lián)； n 若數(shù)據(jù)在傳輸過程中發(fā)生差錯，關(guān)聯(lián)關(guān)系被破壞，從而可若數(shù)據(jù)在傳輸過程中發(fā)生差錯，關(guān)聯(lián)關(guān)系被破壞，從而可 檢出和檢出和/ /或糾正錯誤?；蚣m正錯誤。 第 10 章 差錯控制編碼 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 章 差錯控制編碼 n ：誤碼的位置隨機（誤碼間無關(guān)聯(lián)），隨機誤碼：誤碼的位置隨機（誤碼間無關(guān)聯(lián)），隨機誤碼 主要由白噪聲引起。主要由白噪聲引起。 n ：誤碼成串出現(xiàn)，主要由強脈沖及雷電等突發(fā)的：誤碼成串出現(xiàn)，主要由強脈沖及雷電等突發(fā)的 強干擾引起。強干擾引起。 n ：以上兩種誤碼及產(chǎn)生原因的組合。：以上兩種誤碼及產(chǎn)生原因的組合。 第 10 章 差錯控制編碼 信道編碼的核心問題信道編碼的核心問題 v 發(fā)現(xiàn)錯誤發(fā)現(xiàn)錯誤 v 糾正錯誤糾正錯誤 第 10 章 差錯控制

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

6、間的距糾錯碼的抗干擾能力完全取決于許用碼字之間的距 離，碼的最小距離越大，說明碼字間的最小差別越離，碼的最小距離越大，說明碼字間的最小差別越 大，抗干擾能力就越強。大，抗干擾能力就越強。 n k 第 10 章 差錯控制編碼 舉例說明：假如要傳送舉例說明：假如要傳送A、B兩個消息兩個消息 編碼一： 消息A-“0”；消息B-“1” 最小碼距1 若傳輸中產(chǎn)生錯碼（“0”錯成“1”或“1” 錯成“0”）收端無法發(fā)現(xiàn)，該編碼無檢錯糾 錯能力。 第 10 章 差錯控制編碼 編碼二： 消息A-“00”；消息B-“11” 最小碼距2 若傳輸中產(chǎn)生一位錯碼，則變成“01”或“10”， 收端判決為有錯（因“01”

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

8、糾正t個錯碼，則要求其最小dmin2t+1 一個碼能糾正t個錯碼，同時能檢測e個錯碼，則要 求其最小碼距 dmine+t+1 (et) （2）最小碼距與檢錯和糾錯能力的關(guān)系）最小碼距與檢錯和糾錯能力的關(guān)系 第 10 章 差錯控制編碼 v 奇偶監(jiān)督碼 v 二維奇偶監(jiān)督碼（略，見附錄） v 恒比碼 10.2 常用的幾種簡單分組碼常用的幾種簡單分組碼 第 10 章 差錯控制編碼 10.2.1 奇偶監(jiān)督碼奇偶監(jiān)督碼 1 2 3k k 1 123kk 1k 1123k 123kk 1k 1123k kaa a .a r1a aaa .aa0aaaa .a aaa .aa1aaaa .a1 對對 位位碼碼

9、元元 校校驗驗位位 偶偶校校驗驗 奇奇校校驗驗 奇偶監(jiān)督碼：在信息碼元后附加一位監(jiān)督位，使 得碼組中奇偶監(jiān)督碼“1”的個數(shù)為偶數(shù)或奇數(shù)。 第 10 章 差錯控制編碼 序 號 碼長為4的奇奇監(jiān)督碼序 號 碼長為4的偶偶監(jiān)督碼 信息碼元 監(jiān)督碼元 信息碼元 監(jiān)督碼元 0000100000 1001010011 2010020101 3011130110 4100041001 5101151010 6110161100 7111071111 表：碼長為4的奇、偶監(jiān)督碼 第 10 章 差錯控制編碼 v只能檢測出單個或奇數(shù)個錯誤，不能檢測偶數(shù)個錯誤 v不能糾錯。 v 應(yīng)用：以隨機錯誤為主的計算機通信系統(tǒng)

10、，難于對 付突發(fā)錯誤 v 編碼效率=k/n=k/(k+1)，是一種高效率碼。 10.2.2二維奇偶監(jiān)督碼見附錄二維奇偶監(jiān)督碼見附錄 第 10 章 差錯控制編碼 表表 10-1 3 2 恒比碼恒比碼 （是一種五中取三碼）（是一種五中取三碼） 10.2.3 恒比碼恒比碼 碼字中碼字中1 1的數(shù)目與的數(shù)目與 0 0的數(shù)目保持恒定比例的數(shù)目保持恒定比例 的碼稱為恒比碼。又的碼稱為恒比碼。又 稱等重碼，定稱等重碼，定1 1碼。碼。 這種碼在檢測時，這種碼在檢測時， 通過計算接收碼元中通過計算接收碼元中1 1 的數(shù)目是否正確，就的數(shù)目是否正確，就 知道有無錯誤。知道有無錯誤。 第 10 章 差錯控制編碼

11、線性分組碼： 先將信息碼分組，然后給每組信碼附加若干監(jiān)督碼 的編碼稱為分組碼。 若附加的監(jiān)督碼和信息碼由一些線性代數(shù)方程相則 稱為線性分組碼。 用符號(n,k)表示，k是信息碼的位數(shù)，n是編碼組總 位數(shù)，又稱為碼長，r=n-k為監(jiān)督位數(shù)。 1、基本概念基本概念 10.3 線性分組碼（重點）線性分組碼（重點） 第 10 章 差錯控制編碼 現(xiàn)以(7,4)分組碼為例來說明線性分組碼的特點。設(shè)其碼字 為A=a6 a5 a4 a3 a2 a1 a0，其中前 4 位是信息元，后 3 位是 監(jiān)督元， 可用下列線性方程組來描述該分組碼，產(chǎn)生監(jiān)督元。 3460 3561 4562 aaaa aaaa aaaa

12、第 10 章 差錯控制編碼 表表 10-2 (7,4)碼的碼字表碼的碼字表 第 10 章 差錯控制編碼 2、線性分組碼的性質(zhì)、線性分組碼的性質(zhì) v任意兩個許用碼組之和（逐位模2和）仍為一 許用碼組，即具有封閉性。 v最小碼距=非零碼的最小碼重（1的個數(shù)）。 第 10 章 差錯控制編碼 10.3.2 監(jiān)督矩陣監(jiān)督矩陣H和生成矩陣和生成矩陣G 第 10 章 差錯控制編碼 其中,P為rk階矩陣，Ir為rr階單位矩陣。可以寫成H= P Ir形式的矩陣稱為典型監(jiān)督矩陣。 HAT=0T，說明H矩陣與碼字的轉(zhuǎn)置乘積必為零，可以用來 作為判斷接收碼字A是否出錯的依據(jù)。 并簡記為 第 10 章 差錯控制編碼 v

13、 rn階矩陣 v 監(jiān)督矩陣H確定了編碼時監(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特點 第 10 章 差錯控制編碼 若把監(jiān)督方程補充為下列方程 第 10 章 差錯控制編碼 可改寫為矩陣形式 第 10 章 差錯控制編碼 1101000 1010100 0110010 1110001 G QIG k T PQ 110 101 011 111 第 10 章 差錯控制編碼 vk n階矩陣 v把具有IkQ形式的G矩陣稱為典型形式的生成

14、 矩陣，其中，Ik為kk階單位方陣，Q為k r 階矩陣 v由典型生成矩陣產(chǎn)生的分組碼一定是系統(tǒng)碼 vG矩陣的各行應(yīng)線性無關(guān)，每行均為許用碼組 生成矩陣G特點 第 10 章 差錯控制編碼 已知（6，3）漢明碼(能糾正單個錯誤的線性分 組碼)的生成矩陣如下， (1)列出所有許用碼組; (2)最小碼距d0; (3)檢錯糾錯能力 (4)編碼效率 100101 G010011 001110 第 10 章 差錯控制編碼 543 AaaaG （1） 信息碼信息碼編碼碼字編碼碼字碼重碼重 0 0 00 0 0 0 0 00 0 0 10 0 1 1 1 03 0 1 00 1 0 0 1 13 0 1 10

15、1 11 0 14 1 0 01 0 0 1 0 13 1 0 11 0 1 0 1 14 1 1 01 1 0 1 1 04 1 1 1 1 1 1 0 0 03 第 10 章 差錯控制編碼 （3） （4） 0 0 0 e=d -1=2 d -1 t=1 2 et1det 21 該該碼碼可可以以檢檢2 2位位錯錯 該該碼碼可可以以糾糾1 1位位錯錯 該該碼碼不不能能同同時時檢檢 位位錯錯與與糾糾 位位錯錯。 k3 50% n6 （2） 0 d3 第 10 章 差錯控制編碼 1101000 1010100 0110010 1110001 設(shè)（設(shè)（7,4）線性碼的生成矩陣）線性碼的生成矩陣G為：

16、為： 當信息位為當信息位為0001時，時， （1）試求其后的監(jiān)督位。）試求其后的監(jiān)督位。 （2）監(jiān)督矩陣）監(jiān)督矩陣H 第 10 章 差錯控制編碼 6543 AaaaaG 解：解： （1） 1000111 0100110 A0 0 0 10 0 0 1 0 1 1 0010101 0001011 第 10 章 差錯控制編碼 （2）監(jiān)督矩陣）監(jiān)督矩陣H 根據(jù)生成矩陣和監(jiān)督矩陣的關(guān)系：根據(jù)生成矩陣和監(jiān)督矩陣的關(guān)系： G= IkQ，H=PIr 其中其中P=QT，可得監(jiān)督矩陣，可得監(jiān)督矩陣H為：為： 1001101 0101011 0010111 第 10 章 差錯控制編碼 v錯誤矩陣/錯誤圖樣E： 設(shè)

17、發(fā)送碼組為A，接收碼組為B， 則錯誤矩陣 n 1n 210 n 1n 210 Aaa. a a Bbb. b b n 1n 210 ii iii ii EBAee. e e 1ba eba 0ba 該該位位有有錯錯 該該位位無無錯錯 10.3.3 伴隨式伴隨式(校正子校正子)S 第 10 章 差錯控制編碼 v接收端計算校正子S，即 S=BHT=(A+E)HT=AHT+EHT=0+ EHT= EHT 校正子只與E有關(guān)，即錯誤圖樣與校正子之間 有確定的關(guān)系. 確定錯誤圖樣與校正子的關(guān)系表。 可從表中找得錯碼位置，加以糾正。 第 10 章 差錯控制編碼 表表 10-3 (7,4)碼碼S與與E的對應(yīng)關(guān)

18、系的對應(yīng)關(guān)系 第 10 章 差錯控制編碼 v以（7，4）漢明碼為例 設(shè)發(fā)送碼組A=（0001011） 接收碼組 B=（0000011） 則收端譯碼過程如下： 計算校正子 T 111 110 101 SBH0 0 0 0 0 1 1011011 100 010 001 查表得b3為錯誤位置，即可糾正（0001011） 第 10 章 差錯控制編碼 10.4 循循 環(huán)環(huán) 碼碼 循環(huán)碼是一種重要的線性分組碼。這種 碼的編碼和解碼設(shè)備都不太復(fù)雜，且有較強 的檢（糾）錯能力。 共n位，通常前k位為信息位，后r位為 監(jiān)督位。 10.4.1 10.4.1 循環(huán)碼的編碼原理循環(huán)碼的編碼原理 第 10 章 差錯控

19、制編碼 循環(huán)碼的特點： v 封閉性； v 循環(huán)性；即碼中任一碼組循環(huán)一位(將最右端 的碼元移到左端或反之）以后，仍為該碼中的 一個碼組。 第 10 章 差錯控制編碼 若(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 章 差錯控制編碼 表一種（表一種（7 7，3 3）循環(huán)碼的全部碼字）循環(huán)碼的全部碼字 序序 號號 碼字碼字 序序 號號 碼字碼字 信息位信息位 a6

20、 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 a0 1 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 1 2 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 0 3 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 1 4 40 0 1 1 1 11 1 0 0 0

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

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

23、)( )()( )() 1()( )(0)( 2 7 3 2 0 xgxxA xgxxA xgxxA xgxA 其它碼多項式都是g(x)的倍式， 即 第 10 章 差錯控制編碼 可以證明生成多項式可以證明生成多項式g(x)具有以下特性：具有以下特性： （1） g(x)是一個常數(shù)項為是一個常數(shù)項為1的的 次次 多項式；多項式； （2） g(x)是是 的一個因式；的一個因式； （3）該循環(huán)碼中其它碼多項式都是該循環(huán)碼中其它碼多項式都是g(x) 的倍式。的倍式。 knr 1 n x 42432 12 (7 3)( ) ( )1;( )1 g x g xxxxgxxxx 對于 ，循環(huán)碼，符合碼生成多項

24、式條件的有兩個 可以構(gòu)造出兩種循環(huán)碼組；它們的d0、檢錯、糾錯能力相同 第 10 章 差錯控制編碼 g(x)， ， xk-1g(x)都是許用碼組，連同g(x)共k 個許用碼組，構(gòu)成碼的生成矩陣G(x) 注：該生成矩陣并不是典型形式的，但可通過 線性變換變換成典型的生成矩陣。 )( )( )( )( )( 2 1 xg xxg xgx xgx XG k k 循環(huán)碼的循環(huán)碼的生成矩陣生成矩陣常用多項式的形式來表示常用多項式的形式來表示 第 10 章 差錯控制編碼 例如(7,3)循環(huán)碼，n=7, k=3, r=4, 其生成多項式及生成矩陣分別為 第 10 章 差錯控制編碼 1111111111010

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

26、項式：即為生成多項式： g(x)=x3+x+1。 生成矩陣為：生成矩陣為： 3643 2532 142 3 x g(x)xxx x g(x)xxx G(x) x g(x)xxx g(x)xx1 10110001000101 01011000100111 00101100010110 00010110001011 第 10 章 差錯控制編碼 10.4.2 監(jiān)督多項式及監(jiān)督矩陣監(jiān)督多項式及監(jiān)督矩陣 1 )( 1 )( 1 1 1 xhxhx xg x xh k k k n 其中g(shù)(x)是常數(shù)項為 1 的r次多項式，是生成多項式；h(x)是 常數(shù)項為 1 的k次多項式，稱為監(jiān)督多項式。同理，可得監(jiān)

27、督矩陣H )(* )(* )(* )( 1 xh xxh xhx xH kn 第 10 章 差錯控制編碼 是h(x)的逆多項式。例如(7，3)循環(huán)碼，g(x)=x4+x3+x2+1，則 其中 1)(* 1 2 2 1 1 xhxhxhxxh k kkk 1)(* 1 )( 1 )( 3 23 7 xxxh xx xg x xh 1 11 ( )1 kk k h xxhxh x 第 10 章 差錯控制編碼 1 )( 3 24 235 346 xx xxx xxx xxx xH 1101000 0110100 0011010 0001101 H 第 10 章 差錯控制編碼 10.4.3 編碼方法和

28、電路編碼方法和電路 思路思路：在編碼時，首先要根據(jù)給定的(n,k)值選定生成多項 式g(x)，即應(yīng)在xn+1的因式中選一r=n-k次,常數(shù)項為1的多項式 作為g(x)。設(shè)編碼前的信息多項式m(x)為 12 321 )( k k xaxaxaaxm 循環(huán)碼的碼多項式可表示為 )()()(xRxmxxA r 用xr乘m(x)，相當于把信息碼后附加上r個“0” 第 10 章 差錯控制編碼 用g(x)除xr m(x)，得到商式Q(x)和余式為R(x) 編出碼組為：A(x)= xr m(x)+ R(x) xg xR xQ xg xmx r 10.4.3 編碼解碼電路（略）編碼解碼電路（略） 第 10 章

29、 差錯控制編碼 1 1 ) 1( 1)( )( 24 2 2 24 56 xxx x xx xxx xx xg xmx kn 即余式即余式r(x)=x2+1 于是，對應(yīng)碼組于是，對應(yīng)碼組A(x)= xn-k m(x)+r(x）= x6+x5+ x2+1 編碼為編碼為1100101 例題例題 設(shè)（設(shè)（7，3）循環(huán)碼的生成多項式為）循環(huán)碼的生成多項式為 g(x)=x4+x2+x+1，待編碼信息位為待編碼信息位為110，求對應(yīng)循，求對應(yīng)循 環(huán)碼碼組。環(huán)碼碼組。 解：解：m(x)=x2+x，xn-k m(x)=x4(x2+x)=x6+x5 第 10 章 差錯控制編碼 10.6 卷卷 積積 碼碼 10.

30、6.1 基本概念基本概念 1、卷積碼：用(n,k,m)表示，每個(n,k) 碼段(字碼)中的n 個碼元不僅與該碼段內(nèi)的k個信息元有關(guān)，而且與前面m 個信息元有關(guān)（有記憶性）。 2、編碼器：由k個輸入，n個輸出，m個移位寄存器和一 些輔助電路(模2加法器及開關(guān)電路)構(gòu)成的有記憶系統(tǒng)。 3、卷積碼編碼過程通常可用樹圖、狀態(tài)圖和格圖來描述 第 10 章 差錯控制編碼 例：例： 卷積碼卷積碼(2,1,2)編碼器（編碼器（P284，圖，圖9-7） m1m2 數(shù)據(jù) 輸入 碼字 輸出 S1S2S3 C1 C2 起始狀態(tài)：各級移位寄存器清零，即S2S3為00。 存儲狀態(tài)：S3S2的4種狀態(tài)00、01、10、1

31、1 S1等于當前輸入數(shù)據(jù) C=C1C2 第 10 章 差錯控制編碼 312 3211 SSC SSSC 當輸入數(shù)據(jù)為11010時，(2,1,2)編碼器的工作過程 輸出碼字C由下式確定： 編碼輸出為：11010100101100 第 10 章 差錯控制編碼 編碼約束度編碼約束度：每：每1位數(shù)據(jù)，將影響位數(shù)據(jù)，將影響(m+1)個輸出字個輸出字 碼，稱碼，稱(m+1)為編碼約束度。例（為編碼約束度。例（2，1，2）編碼）編碼 約束度為約束度為3。 約束長度約束長度：每個子碼有：每個子碼有n個碼元，在卷積碼中有個碼元，在卷積碼中有 約束關(guān)系的最大碼元長度為約束關(guān)系的最大碼元長度為(m+1).n，稱為約

32、束，稱為約束 長度。例（長度。例（2，1，2）約束長度為）約束長度為6。 編碼約束度3 約束長度6 第 10 章 差錯控制編碼 10.6.2 卷積碼的描述（用圖解法）卷積碼的描述（用圖解法） 1. 樹圖樹圖 圖圖 7-6 (2,1,2)碼的樹圖碼的樹圖 a11 00 a b b01 10 c d c00 11 a b d10 01 c d 00 10 a 11 01 b a 00 11 a11 00 a b b01 10 c d c00 11 a b d10 01 c d 11 01 c 00 10 d b 10 01 a 11 00 數(shù)碼起點 狀 態(tài) a00 b01 c10 d11上半部 下

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

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

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

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

37、11100000001 11010011010 10000111011 00010000100 11001110111 水平奇偶監(jiān)督碼水平奇偶監(jiān)督碼 111011100110000.0110110101 第一個 碼元 第二個 碼元 第三個 碼元 第十個 碼元 監(jiān)督碼 元 第 10 章 差錯控制編碼 水平奇偶監(jiān)督碼接收端出現(xiàn)突發(fā)誤碼示例水平奇偶監(jiān)督碼接收端出現(xiàn)突發(fā)誤碼示例 信 息 碼 元監(jiān)督碼元 11100000001 11010011010 10000111011 00010000100 11001110111 1 1 0 1 結(jié)論：結(jié)論：能夠發(fā)現(xiàn)突發(fā)長度不大于方陣能夠發(fā)現(xiàn)突發(fā)長度不大于方陣

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