西工大通信原理(期末復(fù)習(xí)、考研、求職必備)-第9章 差錯控制編碼

1、第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-51通通 信信 原原 理理 電電 子子 教教 案案第第9 9章章 差錯控制編碼差錯控制編碼 西西 北北 工工 業(yè)業(yè) 大大 學(xué)學(xué) （2008.3）第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-52研究的問題研究的問題 9.1 9.1 引言引言 9.2 9.2 糾錯編碼的基本原理糾錯編碼的基本原理 9.3 9.3 常用的簡單編碼常用的簡單編碼 9.3 9.3 線性分組碼線性分組碼 9.4 9.4 循環(huán)碼循環(huán)碼 9.5 9.5 卷積碼卷積碼 9.6 9.6 網(wǎng)格編碼調(diào)制網(wǎng)格編碼調(diào)制 第第9 9章章 差錯控制

2、編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-53干擾干擾乘性：均衡乘性：均衡加性：調(diào)制解調(diào)體制、發(fā)送功率、最佳接收加性：調(diào)制解調(diào)體制、發(fā)送功率、最佳接收9.1 9.1 引言引言一、編碼問題的提出一、編碼問題的提出 由于數(shù)字信號在傳輸過程中必不可免的受到干擾的影響，使由于數(shù)字信號在傳輸過程中必不可免的受到干擾的影響，使碼元波形變壞，故傳輸?shù)浇邮斩撕罂赡馨l(fā)生錯判。碼元波形變壞，故傳輸?shù)浇邮斩撕罂赡馨l(fā)生錯判。信道信道譯碼譯碼檢檢/糾錯編碼糾錯編碼若還不行，則需差錯控制編碼。若還不行，則需差錯控制編碼。目的：目的：在數(shù)字通信系統(tǒng)中，為了提高數(shù)字信號傳輸?shù)挠行г跀?shù)字通信系統(tǒng)中，為了提高數(shù)字信號傳輸?shù)挠?/p>

3、效性而采取的編碼稱為性而采取的編碼稱為信源編碼信源編碼；為了提高數(shù)字通信的可靠；為了提高數(shù)字通信的可靠性而采取的編碼稱為性而采取的編碼稱為信道編碼信道編碼。差錯可控差錯可控第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-54二、錯誤的類型二、錯誤的類型隨機(jī)性錯誤隨機(jī)性錯誤 （白噪聲引起）（白噪聲引起）特點：特點：單個錯，錯誤之間不相關(guān)。主要出現(xiàn)在無記憶信道。單個錯，錯誤之間不相關(guān)。主要出現(xiàn)在無記憶信道。2. 2. 突發(fā)性錯誤突發(fā)性錯誤 ( (脈沖干擾引起）脈沖干擾引起）特點：特點：成串錯，錯誤之間有相關(guān)性成串錯，錯誤之間有相關(guān)性。主要出現(xiàn)在有記憶信。主要出現(xiàn)在有記憶信道。

4、錯誤傳播。道。錯誤傳播。3. 3. 混合性錯誤混合性錯誤第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-55三、差錯控制的方式三、差錯控制的方式1. 檢錯重發(fā)檢錯重發(fā)(ARQ)收收發(fā)發(fā)可檢錯的碼可檢錯的碼: : 1）雙向通道）雙向通道 2）通信效率低）通信效率低 3）不適于實時通信）不適于實時通信 4）編、譯碼設(shè)備簡單）編、譯碼設(shè)備簡單 5）編碼效率高）編碼效率高總碼元總碼元 (n bit)= 信元信元 (k bit)+ 督元督元 (r bit )。kRn只檢不糾，有錯自只檢不糾，有錯自動要求重發(fā)。動要求重發(fā)。第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理202

5、2-5-562. 2. 前向糾錯前向糾錯 (FEC)(FEC)收收發(fā)發(fā)可糾錯的碼可糾錯的碼 1）只需單向信道）只需單向信道省信道！省信道！ 2）通信效率高；）通信效率高； 3）適于實時傳輸；）適于實時傳輸； 4) 譯碼設(shè)備復(fù)雜。譯碼設(shè)備復(fù)雜。檢錯并糾錯檢錯并糾錯第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-573. 3. 反饋檢驗法反饋檢驗法收收發(fā)發(fā)原理：原理：收端將信碼原封不動地轉(zhuǎn)發(fā)回發(fā)端，并與原發(fā)送信收端將信碼原封不動地轉(zhuǎn)發(fā)回發(fā)端，并與原發(fā)送信碼相比較：發(fā)現(xiàn)錯重發(fā)；否則：碼相比較：發(fā)現(xiàn)錯重發(fā)；否則：PASSPASS特點特點: : 需要雙向通道；需要雙向通道；收發(fā)設(shè)備

6、簡單；收發(fā)設(shè)備簡單；傳輸效率低（最低）。傳輸效率低（最低）。第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-589.2 9.2 糾錯編碼的基本原理糾錯編碼的基本原理一一. . 基本思想基本思想信元信元督元督元信元信元督元督元信元和督元有一的函數(shù)關(guān)系，插入督元的過程就是一種編碼的信元和督元有一的函數(shù)關(guān)系，插入督元的過程就是一種編碼的過程，接收端可檢錯糾錯。顯然，過程，接收端可檢錯糾錯。顯然，傳輸效率傳輸效率（引入冗余碼）（引入冗余碼）例：例：天氣預(yù)報天氣預(yù)報 信元信元 督元督元 0 0 0 晴晴 0 1 1 云云 1 0 1 陰陰 1 1 0 雨雨三位碼元有三位碼元有23=

7、8 8種組合，實際使種組合，實際使用了用了2 22 2=4=4種種許用碼組。許用碼組。其余其余 001，010，100，111 為為禁禁用碼組用碼組。檢錯能力：檢錯能力：可檢錯奇數(shù)個錯；可檢錯奇數(shù)個錯；糾錯能力：糾錯能力：無。無。第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-59例：例：天氣預(yù)報，可預(yù)報天晴天氣預(yù)報，可預(yù)報天晴信元信元 督元督元 0 0 0 1 1 1冗余量加大，禁用碼組比例提高。冗余量加大，禁用碼組比例提高。檢錯能力：檢錯能力：檢檢2；糾錯能力：糾錯能力：糾糾1 1。許用碼組許用碼組2個，禁用碼組個，禁用碼組6個個晴晴陰陰第第9 9章章 差錯控制編碼差

8、錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-510二二. . 糾錯編碼的分類糾錯編碼的分類線性碼線性碼和非線性碼和非線性碼分組碼分組碼、卷積碼和循環(huán)碼、卷積碼和循環(huán)碼系統(tǒng)碼系統(tǒng)碼和非系統(tǒng)碼和非系統(tǒng)碼三三. . 分組碼分組碼定義定義: :將信息碼將信息碼分組分組，為每信息碼附加若干個監(jiān)督碼編碼，稱，為每信息碼附加若干個監(jiān)督碼編碼，稱為分組碼。為分組碼。特點特點: : 在分組碼中，監(jiān)督碼元僅監(jiān)督本碼組中的信息碼元。在分組碼中，監(jiān)督碼元僅監(jiān)督本碼組中的信息碼元。符號符號: : ( n , k ) , r = n k碼字碼字: :結(jié)構(gòu)結(jié)構(gòu): :an-1an-2 arar-1a0k個信元個信元r個督元個督元

9、碼長碼長n1210nnrrAaaa aa第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-511碼組的重量和碼距及糾錯能力碼組的重量和碼距及糾錯能力1. 1. 重量重量 碼組中非碼組中非0元素的個數(shù)元素的個數(shù) 例例: : A= ( 10110 ) 碼重碼重 = 32. 2. 碼距碼距 兩兩碼組對應(yīng)位上數(shù)值不同的個數(shù)，記為兩兩碼組對應(yīng)位上數(shù)值不同的個數(shù)，記為d。最小碼距最小碼距: : 某種編碼中各個碼組間距離某種編碼中各個碼組間距離 的最小值，記做的最小值，記做d0 d0=dmin碼距的幾何意義碼距的幾何意義: : (n=3) 各頂點各頂點沿立方體各邊行走的幾何距離。沿立方體

10、各邊行走的幾何距離。碼元值：碼元值：每一碼組的三個碼元值，每一碼組的三個碼元值，就是此立方體各頂點的座標(biāo)（就是此立方體各頂點的座標(biāo)（a2a1a0）最小碼距最小碼距: : 1第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-512前例中：前例中：天氣預(yù)報天氣預(yù)報 信元信元 督元督元 0 0 0 晴晴 0 1 1 云云 1 0 1 陰陰 1 1 0 雨雨四個許用碼組之間的距離均為四個許用碼組之間的距離均為2。Why?擯棄擯棄d=1的碼禁用碼組。的碼禁用碼組。許用碼組最小碼距愈大，抗干擾許用碼組最小碼距愈大，抗干擾能力愈強(qiáng)！能力愈強(qiáng)！確定最小碼距的目的：確定最小碼距的目的：決定編

11、碼的檢糾錯能力。決定編碼的檢糾錯能力。第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-5133. d0與糾檢錯能力與糾檢錯能力若要求檢測若要求檢測e個錯個錯,則則 d0e+1 若要求糾正若要求糾正t個錯個錯,則則 d02t+1 若要檢測若要檢測e糾正糾正t 個錯個錯(同時同時),則則 d0e+t+1, 且且et碼距與檢錯和糾錯能力的關(guān)系如圖：碼距與檢錯和糾錯能力的關(guān)系如圖：第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-514d0圖圖9-4第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-5159.3 9.3 常用的簡單編碼常用的

12、簡單編碼屬于分組碼一類。簡單、實用。屬于分組碼一類。簡單、實用。一一. . 奇偶監(jiān)督碼奇偶監(jiān)督碼滿足滿足: 1231010nnnaaaaa 督元信元奇數(shù)監(jiān)督碼偶數(shù)監(jiān)督碼偶監(jiān)督碼：偶監(jiān)督碼：碼組中碼組中1的個數(shù)為偶數(shù)；的個數(shù)為偶數(shù)；奇監(jiān)督碼：奇監(jiān)督碼：碼組中碼組中1的個數(shù)為奇數(shù)。的個數(shù)為奇數(shù)。檢錯能力檢錯能力: : 所有奇數(shù)個錯。所有奇數(shù)個錯。一半！應(yīng)用非常多。一半！應(yīng)用非常多。編碼效率編碼效率: :1,!,knRnnnk高碼長信元數(shù)第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-516二維奇偶監(jiān)督碼二維奇偶監(jiān)督碼進(jìn)行橫、縱向監(jiān)督進(jìn)行橫、縱向監(jiān)督例例: : 0 0 0 0

13、1 1 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 0 0 0 0 0 1 1 0 1 0 1 1 0 1 0 1 0橫橫向向監(jiān)監(jiān)督督糾檢錯能力糾檢錯能力: : 仍可檢錯奇數(shù)個錯仍可檢錯奇數(shù)個錯 還可檢錯偶數(shù)個錯還可檢錯偶數(shù)個錯 可糾正一些錯碼可糾正一些錯碼 適于檢測突發(fā)性錯誤適于檢測突發(fā)性錯誤第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-517例例: 碼重為碼重為3許用碼組許用碼組: 禁用碼組禁用碼組: 可檢測所有奇數(shù)個碼元的錯可檢測所有奇數(shù)個碼元的錯 和部分偶和部分偶數(shù)個碼元的錯數(shù)個碼元的錯,但但 不能檢測碼組中不能檢測碼組中“1”變?yōu)樽優(yōu)椤?” 與

14、與“0”變?yōu)樽優(yōu)椤?”的錯碼數(shù)目相同的那些偶數(shù)錯碼的錯碼數(shù)目相同的那些偶數(shù)錯碼325log0.66CRn第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-518例：例： n=10 , 則則 k=5信元碼信元碼 監(jiān)督碼監(jiān)督碼 合成碼合成碼 校驗碼校驗碼1 0 1 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 01 0 0 0 1 0 1 1 1 0 1 1 1 1 1 0 0 0 0 0 接受端的檢測接受端的檢測信息位監(jiān)督位合成碼組編碼規(guī)則編碼規(guī)則:信息位信息位(n/2)中有中有數(shù)個數(shù)個“1”,則監(jiān)督位與信息位則監(jiān)督位與信息位 信息位信息位(n/2)中有中有

15、數(shù)個數(shù)個“1”,則監(jiān)督位是信息位的則監(jiān)督位是信息位的第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-5199.4 9.4 線性分組碼線性分組碼定義：定義：若分組碼（若分組碼（n,k）,督元與信元的關(guān)系可用一線性方程組督元與信元的關(guān)系可用一線性方程組來描述，則該分組碼（來描述，則該分組碼（n,k）稱為線性分組碼。）稱為線性分組碼。一、漢明碼一、漢明碼 能糾一位錯的線性分組碼。能糾一位錯的線性分組碼。定義：定義：是一種是一種能糾正一位錯能糾正一位錯碼，且編碼效率較高的線性分組碼，且編碼效率較高的線性分組碼。碼。最小碼距：最小碼距：d0=31. 構(gòu)造原理構(gòu)造原理考察：考察：定義

16、一個監(jiān)督方程（監(jiān)督關(guān)系式、偶監(jiān)督）：定義一個監(jiān)督方程（監(jiān)督關(guān)系式、偶監(jiān)督）：1231001nnnaaaaaS 校正子督元信元無錯有錯由于一位由于一位校正子校正子只有兩種取值，故只能表示有錯或無錯，不只有兩種取值，故只能表示有錯或無錯，不能指出錯碼的位置。能指出錯碼的位置。第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-520推想推想: :如果監(jiān)督位增加一位（即變成兩位），則可增加一個類似如果監(jiān)督位增加一位（即變成兩位），則可增加一個類似于上式的監(jiān)督關(guān)系，即可獲得兩個校正子，于是可有于上式的監(jiān)督關(guān)系，即可獲得兩個校正子，于是可有0 00 1 0 11 1無錯無錯可指示一個錯

17、碼可能出現(xiàn)的可指示一個錯碼可能出現(xiàn)的位置，共有位置，共有22-1=3 個位置。個位置。1231001nnnaaaaaS 校正子督元信元無錯有錯第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-521再推廣再推廣: :0 0 . 00 0 . 11 1 .1 1無錯無錯2r-1 個錯的個錯的可能位置可能位置顯然：顯然：要求要求 2r-1n（n=k+r），則可指示（僅一位錯時），則可指示（僅一位錯時）任一錯碼的位置包括信元、督元。任一錯碼的位置包括信元、督元?；颍夯颍?2rk+r+1112rSrrrSSS 對應(yīng)對應(yīng)對應(yīng)對應(yīng)一個督元一個監(jiān)督方程一個校正子:個督元個監(jiān)督方程個校正子

18、: 、 、可指示一個錯碼可能出現(xiàn)的可指示一個錯碼可能出現(xiàn)的2r-1個位置。個位置。第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-5222. 2. 例例: : 構(gòu)造構(gòu)造k=4 k=4 的漢明碼的漢明碼（1）確定）確定 r由由 2r k+r+1 得得 r = 3，則，則 n= k+r=7 ( 7,4 ) 分組碼分組碼6543210Aa a a aa a a 信元督元第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-523（2）寫出校正子的編碼表）寫出校正子的編碼表 r = 3 共有共有3個校正子個校正子S1 S2 S3 錯碼位置錯碼位置 S1 S2 S3

19、 錯碼位置錯碼位置0 0 1 a0 1 0 1 a4 0 1 0 a1 1 1 0 a51 0 0 a2 1 1 1 a6 0 1 1 a3 0 0 0 無錯無錯（3） 由校正子編碼表得由校正子編碼表得監(jiān)督方程組監(jiān)督方程組校正子和哪些碼元構(gòu)成偶校正子和哪些碼元構(gòu)成偶監(jiān)督關(guān)系監(jiān)督關(guān)系124562135630346SaaaaSaaaaSaaaa若若 S1S2S3 = 000 時時, 即無錯得即無錯得校驗方程校驗方程:偶監(jiān)督關(guān)系第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-524得得校驗方程校驗方程: :654265316430000aaaaaaaaaaaa即實際上確定了即實

20、際上確定了督元和信元之間的關(guān)系督元和信元之間的關(guān)系:265416530643aaaaaaaaaaaa校驗方程督信關(guān)系有了校正子編碼表，督元不是隨便選的！有了校正子編碼表，督元不是隨便選的！（4） 給定了信元給定了信元a6a5a4a3,可由可由“督信關(guān)系”確定督元確定督元全部全部( 7,4 ) 碼組。碼組。第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-525（4） 給定了信元給定了信元a6a5a4a3,可確定督元全部可確定督元全部( 7,4 ) 碼組碼組265416530643aaaaaaaaaaaa第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-5

21、26二二. . 線性分組碼線性分組碼1. 1. 線性方程組和監(jiān)督方程線性方程組和監(jiān)督方程654321065432106543210111010001101010011110110aaaaaaaaaaaaaaaaaaaaa 寫成矩陣式寫成矩陣式:1 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 a6a5a4a3a2a1a0 00000TTTHAA H記為或第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-527:0HA 其中碼組的行距陣零矩陣監(jiān)督矩陣可見：可見：H一旦確定，督元和信元之間的關(guān)系也就確定了。一旦確定，督元和信元之間的關(guān)系也就確定

22、了。若若:H1rrkrrP則稱則稱H為為典型陣典型陣，一般，一般，H總可以化為典型陣?？偪梢曰癁榈湫完嚒? 1 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 a6a5a4a3a2a1a0 00000TTTHAA H記為或第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-5282. 2. 生成矩陣生成矩陣265416530643aaaaaaaaaaaa督信關(guān)系矩陣形式矩陣形式: 經(jīng)由生成矩陣生由信元生成：成線性碼組從督信方程入手從督信方程入手由由6251403111011011011aaaaPaaa 第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通

23、信系統(tǒng)原理2022-5-529寫成行陣形式寫成行陣形式:21065436543111110101011aa aaaaaaaaaQQ 其中其中 Q = PT。上式表明：上式表明：信息位給定后，就產(chǎn)生了監(jiān)督位！信息位給定后，就產(chǎn)生了監(jiān)督位！進(jìn)一步，令進(jìn)一步，令生成矩陣生成矩陣 G = Ik Q 則，碼組行陣則，碼組行陣 A = a6a5a4a3 G 6251403111011011011aaaaPaaa 第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-530例：例：生成矩陣生成矩陣討論：討論：由具有由具有 Ik Q 形式的生成矩陣稱為形式的生成矩陣稱為典型生成陣典型生成陣。由

24、典型生成矩陣得出的碼組由典型生成矩陣得出的碼組A中，信息位不變，監(jiān)督位附中，信息位不變，監(jiān)督位附加其后這種碼稱為加其后這種碼稱為系統(tǒng)碼系統(tǒng)碼。21065436543111110101011a a aa a a aa a a a Q1 0 0 0 1 1 10 1 0 0 1 1 00 0 1 0 1 0 10 0 0 1 0 1 1kGI Q6543654365436546536431 0 0 0 1 1 10 1 0 0 1 1 00 0 1 0 1 0 10 0 0 1 0 1 1Aa a a aGa a a aaaaaaaaaaaaaa 信息位不變督位附后， ， ，碼組行陣：碼組行陣：第

25、第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-531一般形式一般形式: : A = an-1an-2ar G 3. G 和和 H 的關(guān)系的關(guān)系由由 Q = PT 或或 P = QT 則則 : H = P Ir G = Ik Q 綜上：綜上：線性分組碼的編碼，就是根據(jù)其監(jiān)督陣線性分組碼的編碼，就是根據(jù)其監(jiān)督陣H或生成陣或生成陣G將將長為長為k的信息碼編成長為的信息碼編成長為n的碼組。的碼組。第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-5324. 4. 線性分組碼的糾錯譯碼過程線性分組碼的糾錯譯碼過程怎樣由含有錯誤的接收碼組中的接收碼組中恢復(fù)正確。怎

26、樣由含有錯誤的接收碼組中的接收碼組中恢復(fù)正確。 （1 1）錯誤圖樣）錯誤圖樣設(shè)：設(shè)：發(fā)碼組為發(fā)碼組為A , 接受碼組為接受碼組為B 則則 B A = E ( 模模 2 )錯誤行陣或錯誤行陣或錯誤圖樣錯誤圖樣： E= en-1en-2e0 例例: : A = 1 1 1 1 1 1 1 B = 1 0 0 1 1 0 1 則則 E = 0 1 1 0 0 1 0 0,1,iiiiibaeba，說明無錯，說明有錯第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-533（2 2）校正子（或稱譯碼伴隨式）校正子（或稱譯碼伴隨式）0)TTBAAHBHS 零矩陣無錯（非零矩陣有錯 代入

27、上式，得代入上式，得0TTTTTBHAE HAHEHEHS結(jié)論：結(jié)論：校正子校正子S僅于錯誤圖案有關(guān)，與發(fā)送碼組無關(guān)。僅于錯誤圖案有關(guān)，與發(fā)送碼組無關(guān)。第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-534由收到的碼組由收到的碼組B，按式：，按式：BHT=SS由由 S=ET E按按B+E=A A由由A 原始信息原始信息（3 3）糾錯譯碼過程）糾錯譯碼過程 第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-5355. 5. 線性分組碼的重要性線性分組碼的重要性（1 1）封閉性）封閉性 設(shè)：設(shè)： A1、A2 分別為一線性分組碼的任意兩個許用碼組。分別為一線

28、性分組碼的任意兩個許用碼組。 則：則：A1+A2 仍為該線性分組碼的許用碼組。仍為該線性分組碼的許用碼組。證：證：由假設(shè)知由假設(shè)知A1HT=0、A2HT=0 所以所以A1HT+A2HT=（A1+A2）HT0 即即A1+A2也是一個碼組。也是一個碼組。結(jié)論：結(jié)論：線性碼組中任意兩個碼字之和，仍為該線性碼組之碼字。線性碼組中任意兩個碼字之和，仍為該線性碼組之碼字。（2 2）線性分組碼的最小碼距）線性分組碼的最小碼距即為該碼的最小重量即為該碼的最小重量:d0=Wmin（除全（除全0碼組）碼組）證：證：由封閉性得，兩個碼組之間的距離（之差），必是另一碼由封閉性得，兩個碼組之間的距離（之差），必是另一碼

29、組的重量。故最小碼距即是碼的最小重量！組的重量。故最小碼距即是碼的最小重量！第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-5369.5 9.5 循環(huán)碼循環(huán)碼 仍屬于線性分組碼仍屬于線性分組碼特點特點: : 編譯碼設(shè)備簡單，檢糾錯能力強(qiáng)。編譯碼設(shè)備簡單，檢糾錯能力強(qiáng)。9.5.1 9.5.1 循環(huán)碼的原理循環(huán)碼的原理具有線性分組碼的所有性質(zhì)之外，還具有循環(huán)性：具有線性分組碼的所有性質(zhì)之外，還具有循環(huán)性：循環(huán)碼中任循環(huán)碼中任一許用碼組經(jīng)過循環(huán)移位后，所得到的碼組仍然是許用碼組。一許用碼組經(jīng)過循環(huán)移位后，所得到的碼組仍然是許用碼組。第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通

30、信系統(tǒng)原理2022-5-537碼多項式碼多項式 T(x)（1）定義）定義為了利用代數(shù)理論研究循環(huán)碼，可以將碼組用代數(shù)多項是為了利用代數(shù)理論研究循環(huán)碼，可以將碼組用代數(shù)多項是來表示，這個多項式被稱為碼多項式。來表示，這個多項式被稱為碼多項式。設(shè)：設(shè)：許用循環(huán)碼許用循環(huán)碼A=(an-1 an-2 a1 a0)，則：則：它的碼多項式表示為：它的碼多項式表示為： 121210nnnnT xaxaxa xa其中：其中：x僅是碼元位置的標(biāo)記。僅是碼元位置的標(biāo)記。第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-538例例: : 設(shè)設(shè) ( 7,3 ) 循環(huán)碼組為循環(huán)碼組為 ( 0 1 1

31、 1 0 0 1 )則相應(yīng)則相應(yīng)碼多項式為：碼多項式為： 654320654321065432054301110011T xa xa xa xa xa xa xa xxxxxxxxxxx反之，由碼多項式易得出碼組：反之，由碼多項式易得出碼組：( 0 1 1 1 0 0 1 )可由碼組直接寫出?？捎纱a組直接寫出。第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-539（2 2）碼多項式的按模運算）碼多項式的按模運算1）整數(shù)的按模運算）整數(shù)的按模運算若一個整數(shù)若一個整數(shù)m可以表示為可以表示為:)2(1521225按按模模 ,mpQpnQnn是整數(shù)則在模則在模n運算下，有運算下，

32、有mp（模（模n）。）。例：例：同樣對于多項式而言，也有類似按模運算。同樣對于多項式而言，也有類似按模運算。第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-540 TxR xQxNxNxTxR x其中：其中：商商Q(x)為多項式，余數(shù)為多項式，余數(shù)R(x)的冪次低于的冪次低于N(x)的冪次。的冪次。例例: : 求求 x4+x2+1 按模按模 x3+1 運算的余式運算的余式 R(x)2 2）碼多項式的按模運算）碼多項式的按模運算若若則則4223342231111111xxxxxxxxxxxx +（模）第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-54

33、1 3 3）循環(huán)性）循環(huán)性在循環(huán)碼中，若在循環(huán)碼中，若T(x) 是一個長為是一個長為n的許用碼組，則的許用碼組，則xiT(x) 在按在按模模xn+1運算下運算下，亦是，亦是一個許用碼組。即一個許用碼組。即設(shè)：設(shè)： T(x) 是長為是長為n的許用碼組多項式的許用碼組多項式( )( )x1)inx T xTx(模則：則： 仍為該碼組中的一個碼多項式。仍為該碼組中的一個碼多項式。3985398535322773532( )()11( )0101110 x T xxxxxxxxxxxxxxxxxx T xxxxx （7，3）碼）碼T(x) = x6+x5+x2+1 ( )前碼組循環(huán)左移前碼組循環(huán)左移3

34、位！位！第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-542由此類推由此類推( )( )x( )( )iix T xT xiT xT xi左 移 位右 移 位可見：可見：一個長為一個長為n的循環(huán)碼，必為按模（的循環(huán)碼，必為按模（xn+1）運算的一個余）運算的一個余式。式。( )( )x1)inx T xT x(模第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-5432. 生成多項式生成多項式g(x)（1 1）存在性）存在性 ( n，k ) 循環(huán)碼中循環(huán)碼中有且僅有有且僅有一個一個g(x) g(x)=xn-k+1特點特點: : 最高的次數(shù)最高的次數(shù):

35、 n-k=r； 最高最高次項和次項和常數(shù)常數(shù)項系數(shù)必為項系數(shù)必為1 。 11-110-1000 11nrrrkrrkaaaaa a 個在循環(huán)碼中，除了全在循環(huán)碼中，除了全0碼組碼組外，再也沒有連續(xù)外，再也沒有連續(xù)k位均為位均為0的碼組。即連的碼組。即連0長度最多長度最多為為k-1位！位！這唯一的這唯一的n-k次多項式稱為次多項式稱為生成多項式生成多項式，記為，記為g(x)！第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-544（2） g(x) 與生成矩陣與生成矩陣 G(x) 的關(guān)系的關(guān)系12( )( )( )( )( )kkxg xxg xG xxg xg xA = an

36、-1ar GG = Ik Q 生成矩陣生成矩陣G的每一行都的每一行都是一個碼組；是一個碼組；G是是k行行n列列矩陣，矩陣，只要找到只要找到k個已知碼組，個已知碼組，就能構(gòu)成生成矩陣就能構(gòu)成生成矩陣G！生成多項式確定后，則生成多項式確定后，則g(x)、x g(x)、 xk-1 g(x)都是碼組，都是碼組，且這且這k個碼組信息無關(guān)，因此可以用來構(gòu)成生成矩陣。個碼組信息無關(guān)，因此可以用來構(gòu)成生成矩陣。g(x)確定了確定了G(x)也就確定了也就確定了整個碼組即確定！整個碼組即確定！第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-545例例: : ( 7，3 )循環(huán)碼，循環(huán)碼， g

37、(x) = x4+x2+x+1 求求 典型生成矩陣典型生成矩陣解解:6643225532420( )1011100( )010 1110( )001 01111xxxxxx g xxGxg xxxxxg xxxxx(x)典型陣典型陣: :100 1011010 1110001 0111kGI Q可方便地直接寫成碼組形式可方便地直接寫成碼組形式第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-546（3） g(x) 與與 T(x) 的關(guān)系的關(guān)系（7，3）26546542654( )( ) ( )( )( )( )( ) ( )x g xT xa a a G xa a axg

38、xg xa xa xag xh x g x12( )( )( )( )( )kkxg xxg xG xxg xg x表明：表明：所有所有T(x)都可以被都可以被g(x)整除，而且任一次數(shù)不大于整除，而且任一次數(shù)不大于(k-1)的的多項式乘以多項式乘以g(x)都是碼多項式。都是碼多項式。第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-547依據(jù)依據(jù): : g(x)是是xn+1的一個的一個(n-k)次的因子，且常數(shù)項不為零。次的因子，且常數(shù)項不為零。證：證：任一循環(huán)多項式任一循環(huán)多項式T(x)都是都是g(x)的倍式，即的倍式，即( )( ) ( )T xh x g x( )(

39、 )T xg x( )( )ix T xTx而生成而生成多項式多項式g(x)本身也是一個碼組，即有本身也是一個碼組，即有由于碼組由于碼組T(x)為一為一（n-k）次多項式，故次多項式，故xkT(x) 為一為一n次多次多項式。由項式。由知，知，xkT(x)在模在模（xn+1）的運算下，亦的運算下，亦為一碼組，故可寫成為一碼組，故可寫成 11knnx TxT xQ xxx（4） 如何尋找如何尋找g(x)第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-548上式左端分子和分母都是上式左端分子和分母都是n次多項式，故商次多項式，故商Q(x)1，因此上，因此上式可化成即式可化成即(

40、 )(1)( )knx T xxT x1( )( )nkxg x xh x 將將T(x)=h(x)T(x)=h(x)g(x)、 T(x)=g(x)代入，并化簡，得代入，并化簡，得 11knnx TxT xQ xxx表明表明: : g(x)應(yīng)該是應(yīng)該是xn+1的一個因式！的一個因式！結(jié)論結(jié)論: : g(x)是是xn+1的一個的一個(n-k)次的因子，且常數(shù)項不為零。次的因子，且常數(shù)項不為零。第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-549（4） 如何尋找如何尋找g(x)依據(jù)依據(jù): : g(x)是是xn+1的一個的一個(n-k)次的因子，且常數(shù)項不為零。次的因子，且常數(shù)項不為零。如如 第第9 9章章 差錯控制編碼差錯控制編碼現(xiàn)代通信系統(tǒng)原理2022-5-550 （7，3）循環(huán)碼有多項式如下，找出（循環(huán)碼有多項式如下，找出（7，3）碼的生成）碼的生成多項式多項式g(x)。 （1） x4+x3+x （2） x3+x2+1 （3） x+1 （4） x4+x2+x+1 （5） x4+x+1