第9章_差錯(cuò)控制編碼_

1、第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-291通通 信信 原原 理理 電電 子子 教教 案案第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼 陜西科技大學(xué)陜西科技大學(xué)第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-292研究的問(wèn)題研究的問(wèn)題 9.1 9.1 引言引言 9.2 9.2 糾錯(cuò)編碼的基本原理糾錯(cuò)編碼的基本原理 9.3 9.3 常用的簡(jiǎn)單編碼常用的簡(jiǎn)單編碼 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章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代

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

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

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

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

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

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

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

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

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

11、小碼距的目的：決定編碼的檢糾錯(cuò)能力。決定編碼的檢糾錯(cuò)能力。第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-29133. d0與糾檢錯(cuò)能力與糾檢錯(cuò)能力若要求檢測(cè)若要求檢測(cè)e個(gè)錯(cuò)個(gè)錯(cuò),則則 d0e+1 若要求糾正若要求糾正t個(gè)錯(cuò)個(gè)錯(cuò),則則 d02t+1 若要檢測(cè)若要檢測(cè)e糾正糾正t 個(gè)錯(cuò)個(gè)錯(cuò)(同時(shí)同時(shí)),則則 d0e+t+1, 且且et碼距與檢錯(cuò)和糾錯(cuò)能力的關(guān)系如圖：碼距與檢錯(cuò)和糾錯(cuò)能力的關(guān)系如圖：第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-2914d0圖圖9-4第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-29159.

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

13、縱向監(jiān)督例例: : 0 0 0 0 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)督督糾檢錯(cuò)能力糾檢錯(cuò)能力: : 仍可檢錯(cuò)奇數(shù)個(gè)錯(cuò)仍可檢錯(cuò)奇數(shù)個(gè)錯(cuò) 還可檢錯(cuò)偶數(shù)個(gè)錯(cuò)還可檢錯(cuò)偶數(shù)個(gè)錯(cuò) 可糾正一些錯(cuò)碼可糾正一些錯(cuò)碼 適于檢測(cè)突發(fā)性錯(cuò)誤適于檢測(cè)突發(fā)性錯(cuò)誤第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-2917例例: 碼重為碼重為3許用碼組許用碼組: 禁用碼組禁用碼組: 可檢測(cè)所有奇數(shù)個(gè)碼元的錯(cuò)可檢測(cè)所有奇數(shù)個(gè)碼元的錯(cuò) 和部分偶和部分偶數(shù)個(gè)碼元的錯(cuò)數(shù)個(gè)碼元的錯(cuò),但但 不能檢測(cè)碼組

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

15、督位與信息位 信息位信息位(n/2)中有中有數(shù)個(gè)數(shù)個(gè)“1”,則監(jiān)督位是信息位的則監(jiān)督位是信息位的第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-29199.4 9.4 線性分組碼線性分組碼定義：定義：若分組碼（若分組碼（n,k）,督元與信元的關(guān)系可用一線性方程組督元與信元的關(guān)系可用一線性方程組來(lái)描述，則該分組碼（來(lái)描述，則該分組碼（n,k）稱為線性分組碼。）稱為線性分組碼。一、漢明碼一、漢明碼 能糾一位錯(cuò)的線性分組碼。能糾一位錯(cuò)的線性分組碼。定義：定義：是一種是一種能糾正一位錯(cuò)能糾正一位錯(cuò)碼，且編碼效率較高的線性分組碼，且編碼效率較高的線性分組碼。碼。最小碼距：最小碼距

16、：d0=31. 構(gòu)造原理構(gòu)造原理考察：考察：定義一個(gè)監(jiān)督方程（監(jiān)督關(guān)系式、偶監(jiān)督）：定義一個(gè)監(jiān)督方程（監(jiān)督關(guān)系式、偶監(jiān)督）：1231001nnnaaaaaS 校正子督元信元無(wú)錯(cuò)有錯(cuò)由于一位由于一位校正子校正子只有兩種取值，故只能表示有錯(cuò)或無(wú)錯(cuò)，不只有兩種取值，故只能表示有錯(cuò)或無(wú)錯(cuò)，不能指出錯(cuò)碼的位置。能指出錯(cuò)碼的位置。第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-2920推想推想: :如果監(jiān)督位增加一位（即變成兩位），則可增加一個(gè)類似如果監(jiān)督位增加一位（即變成兩位），則可增加一個(gè)類似于上式的監(jiān)督關(guān)系，即可獲得兩個(gè)校正子，于是可有于上式的監(jiān)督關(guān)系，即可獲得兩個(gè)校正子，于

17、是可有0 00 1 0 11 1無(wú)錯(cuò)無(wú)錯(cuò)可指示一個(gè)錯(cuò)碼可能出現(xiàn)的可指示一個(gè)錯(cuò)碼可能出現(xiàn)的位置，共有位置，共有22-1=3 個(gè)位置。個(gè)位置。1231001nnnaaaaaS 校正子督元信元無(wú)錯(cuò)有錯(cuò)第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-2921再推廣再推廣: :0 0 . 00 0 . 11 1 .1 1無(wú)錯(cuò)無(wú)錯(cuò)2r-1 個(gè)錯(cuò)的個(gè)錯(cuò)的可能位置可能位置顯然：顯然：要求要求 2r-1n（n=k+r），則可指示（僅一位錯(cuò)時(shí)），則可指示（僅一位錯(cuò)時(shí)）任一錯(cuò)碼的位置包括信元、督元。任一錯(cuò)碼的位置包括信元、督元。或：或： 2rk+r+1112rSrrrSSS 對(duì)應(yīng)對(duì)應(yīng)對(duì)應(yīng)對(duì)應(yīng)

18、一個(gè)督元一個(gè)監(jiān)督方程一個(gè)校正子:個(gè)督元個(gè)監(jiān)督方程個(gè)校正子: 、 、可指示一個(gè)錯(cuò)碼可能出現(xiàn)的可指示一個(gè)錯(cuò)碼可能出現(xiàn)的2r-1個(gè)位置。個(gè)位置。第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-29222. 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章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-2923（2）寫(xiě)出校正子的編碼表）寫(xiě)出校正子的編碼表 r = 3 共有共有3個(gè)校

19、正子個(gè)校正子S1 S2 S3 錯(cuò)碼位置錯(cuò)碼位置 S1 S2 S3 錯(cuò)碼位置錯(cuò)碼位置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 無(wú)錯(cuò)無(wú)錯(cuò)（3） 由校正子編碼表得由校正子編碼表得監(jiān)督方程組監(jiān)督方程組校正子和哪些碼元構(gòu)成偶校正子和哪些碼元構(gòu)成偶監(jiān)督關(guān)系監(jiān)督關(guān)系124562135630346SaaaaSaaaaSaaaa若若 S1S2S3 = 000 時(shí)時(shí), 即無(wú)錯(cuò)得即無(wú)錯(cuò)得校驗(yàn)方程校驗(yàn)方程:偶監(jiān)督關(guān)系第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-2924得得校驗(yàn)方程校驗(yàn)方程: :65

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

21、第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-2926二二. . 線性分組碼線性分組碼1. 1. 線性方程組和監(jiān)督方程線性方程組和監(jiān)督方程654321065432106543210111010001101010011110110aaaaaaaaaaaaaaaaaaaaa 寫(xiě)成矩陣式寫(xiě)成矩陣式: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章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-2927:0HA 其中碼組的行距陣零矩陣監(jiān)督矩陣可見(jiàn)：可見(jiàn)：H

22、一旦確定，督元和信元之間的關(guān)系也就確定了。一旦確定，督元和信元之間的關(guān)系也就確定了。若若:H1rrkrrP則稱則稱H為為典型陣典型陣，一般，一般，H總可以化為典型陣?？偪梢曰癁榈湫完?。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章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-29282. 2. 生成矩陣生成矩陣265416530643aaaaaaaaaaaa督信關(guān)系矩陣形式矩陣形式: 經(jīng)由生成矩陣生由信元生成：成線性碼組從督信方程入手從督信方程入手由由625140311

23、1011011011aaaaPaaa 第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-2929寫(xiě)成行陣形式寫(xiě)成行陣形式: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章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-2930例：例：生成矩陣生成矩陣討論

24、：討論：由具有由具有 Ik Q 形式的生成矩陣稱為形式的生成矩陣稱為典型生成陣典型生成陣。由典型生成矩陣得出的碼組由典型生成矩陣得出的碼組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 aG

25、a a a aaaaaaaaaaaaaa 信息位不變督位附后， ， ，碼組行陣：碼組行陣：第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-2931一般形式一般形式: : 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將將長(zhǎng)為長(zhǎng)為k的信息碼編成長(zhǎng)為的信息碼編成長(zhǎng)為n的碼組。的碼組。第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-29324. 4.

26、 線性分組碼的糾錯(cuò)譯碼過(guò)程線性分組碼的糾錯(cuò)譯碼過(guò)程怎樣由含有錯(cuò)誤的接收碼組中的接收碼組中恢復(fù)正確。怎樣由含有錯(cuò)誤的接收碼組中的接收碼組中恢復(fù)正確。 （1 1）錯(cuò)誤圖樣）錯(cuò)誤圖樣設(shè)：設(shè)：發(fā)碼組為發(fā)碼組為A , 接受碼組為接受碼組為B 則則 B A = E ( 模模 2 )錯(cuò)誤行陣或錯(cuò)誤行陣或錯(cuò)誤圖樣錯(cuò)誤圖樣： 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，說(shuō)明無(wú)錯(cuò)，說(shuō)明有錯(cuò)第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-2933（2 2

27、）校正子（或稱譯碼伴隨式）校正子（或稱譯碼伴隨式）0)TTBAAHBHS 零矩陣無(wú)錯(cuò)（非零矩陣有錯(cuò) 代入上式，得代入上式，得0TTTTTBHAE HAHEHEHS結(jié)論：結(jié)論：校正子校正子S僅于錯(cuò)誤圖案有關(guān)，與發(fā)送碼組無(wú)關(guān)。僅于錯(cuò)誤圖案有關(guān)，與發(fā)送碼組無(wú)關(guān)。第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-2934由收到的碼組由收到的碼組B，按式：，按式：BHT=SS由由 S=ET E按按B+E=A A由由A 原始信息原始信息（3 3）糾錯(cuò)譯碼過(guò)程）糾錯(cuò)譯碼過(guò)程 第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-29355. 5. 線性分組碼的重要性線

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

29、組）證：證：由封閉性得，兩個(gè)碼組之間的距離（之差），必是另一碼由封閉性得，兩個(gè)碼組之間的距離（之差），必是另一碼組的重量。故最小碼距即是碼的最小重量！組的重量。故最小碼距即是碼的最小重量！第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-29369.5 9.5 循環(huán)碼循環(huán)碼 仍屬于線性分組碼仍屬于線性分組碼特點(diǎn)特點(diǎn): : 編譯碼設(shè)備簡(jiǎn)單，檢糾錯(cuò)能力強(qiáng)。編譯碼設(shè)備簡(jiǎn)單，檢糾錯(cuò)能力強(qiáng)。9.5.1 9.5.1 循環(huán)碼的原理循環(huán)碼的原理具有線性分組碼的所有性質(zhì)之外，還具有循環(huán)性：具有線性分組碼的所有性質(zhì)之外，還具有循環(huán)性：循環(huán)碼中任循環(huán)碼中任一許用碼組經(jīng)過(guò)循環(huán)移位后，所得到的碼組

30、仍然是許用碼組。一許用碼組經(jīng)過(guò)循環(huán)移位后，所得到的碼組仍然是許用碼組。第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-2937碼多項(xiàng)式碼多項(xiàng)式 T(x)（1）定義）定義為了利用代數(shù)理論研究循環(huán)碼，可以將碼組用代數(shù)多項(xiàng)是為了利用代數(shù)理論研究循環(huán)碼，可以將碼組用代數(shù)多項(xiàng)是來(lái)表示，這個(gè)多項(xiàng)式被稱為碼多項(xiàng)式。來(lái)表示，這個(gè)多項(xiàng)式被稱為碼多項(xiàng)式。設(shè)：設(shè)：許用循環(huán)碼許用循環(huán)碼A=(an-1 an-2 a1 a0)，則：則：它的碼多項(xiàng)式表示為：它的碼多項(xiàng)式表示為： 121210nnnnT xaxaxa xa其中：其中：x僅是碼元位置的標(biāo)記。僅是碼元位置的標(biāo)記。第第9 9章章 差錯(cuò)控制編

31、碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-2938例例: : 設(shè)設(shè) ( 7,3 ) 循環(huán)碼組為循環(huán)碼組為 ( 0 1 1 1 0 0 1 )則相應(yīng)則相應(yīng)碼多項(xiàng)式為：碼多項(xiàng)式為： 654320654321065432054301110011T xa xa xa xa xa xa xa xxxxxxxxxxx反之，由碼多項(xiàng)式易得出碼組：反之，由碼多項(xiàng)式易得出碼組：( 0 1 1 1 0 0 1 )可由碼組直接寫(xiě)出?？捎纱a組直接寫(xiě)出。第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-2939（2 2）碼多項(xiàng)式的按模運(yùn)算）碼多項(xiàng)式的按模運(yùn)算1）整數(shù)的按模運(yùn)算）整數(shù)的按模運(yùn)算若

32、一個(gè)整數(shù)若一個(gè)整數(shù)m可以表示為可以表示為:)2(1521225按按模模 ,mpQpnQnn是整數(shù)則在模則在模n運(yùn)算下，有運(yùn)算下，有mp（模（模n）。）。例：例：同樣對(duì)于多項(xiàng)式而言，也有類似按模運(yùn)算。同樣對(duì)于多項(xiàng)式而言，也有類似按模運(yùn)算。第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-2940 TxR xQxNxNxTxR x其中：其中：商商Q(x)為多項(xiàng)式，余數(shù)為多項(xiàng)式，余數(shù)R(x)的冪次低于的冪次低于N(x)的冪次。的冪次。例例: : 求求 x4+x2+1 按模按模 x3+1 運(yùn)算的余式運(yùn)算的余式 R(x)2 2）碼多項(xiàng)式的按模運(yùn)算）碼多項(xiàng)式的按模運(yùn)算若若則則4223

33、342231111111xxxxxxxxxxxx +（模）第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-2941 3 3）循環(huán)性）循環(huán)性在循環(huán)碼中，若在循環(huán)碼中，若T(x) 是一個(gè)長(zhǎng)為是一個(gè)長(zhǎng)為n的許用碼組，則的許用碼組，則xiT(x) 在按在按模模xn+1運(yùn)算下運(yùn)算下，亦是，亦是一個(gè)許用碼組。即一個(gè)許用碼組。即設(shè)：設(shè)： T(x) 是長(zhǎng)為是長(zhǎng)為n的許用碼組多項(xiàng)式的許用碼組多項(xiàng)式( )( )x1)inx T xTx(模則：則： 仍為該碼組中的一個(gè)碼多項(xiàng)式。仍為該碼組中的一個(gè)碼多項(xiàng)式。3985398535322773532( )()11( )0101110 x T xxx

34、xxxxxxxxxxxxxxx T xxxxx （7，3）碼）碼T(x) = x6+x5+x2+1 ( )前碼組循環(huán)左移前碼組循環(huán)左移3位！位！第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-2942由此類推由此類推( )( )x( )( )iix T xT xiT xT xi左 移 位右 移 位可見(jiàn)：可見(jiàn)：一個(gè)長(zhǎng)為一個(gè)長(zhǎng)為n的循環(huán)碼，必為按模（的循環(huán)碼，必為按模（xn+1）運(yùn)算的一個(gè)余）運(yùn)算的一個(gè)余式。式。( )( )x1)inx T xT x(模第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-29432. 生成多項(xiàng)式生成多項(xiàng)式g(x)（1 1

35、）存在性）存在性 ( n，k ) 循環(huán)碼中循環(huán)碼中有且僅有有且僅有一個(gè)一個(gè)g(x) g(x)=xn-k+1特點(diǎn)特點(diǎn): : 最高的次數(shù)最高的次數(shù): n-k=r； 最高最高次項(xiàng)和次項(xiàng)和常數(shù)常數(shù)項(xiàng)系數(shù)必為項(xiàng)系數(shù)必為1 。 11-110-1000 11nrrrkrrkaaaaa a 個(gè)在循環(huán)碼中，除了全在循環(huán)碼中，除了全0碼組碼組外，再也沒(méi)有連續(xù)外，再也沒(méi)有連續(xù)k位均為位均為0的碼組。即連的碼組。即連0長(zhǎng)度最多長(zhǎng)度最多為為k-1位！位！這唯一的這唯一的n-k次多項(xiàng)式稱為次多項(xiàng)式稱為生成多項(xiàng)式生成多項(xiàng)式，記為，記為g(x)！第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-2944

36、（2） g(x) 與生成矩陣與生成矩陣 G(x) 的關(guān)系的關(guān)系12( )( )( )( )( )kkxg xxg xG xxg xg xA = an-1ar GG = Ik Q 生成矩陣生成矩陣G的每一行都的每一行都是一個(gè)碼組；是一個(gè)碼組；G是是k行行n列列矩陣，矩陣，只要找到只要找到k個(gè)已知碼組，個(gè)已知碼組，就能構(gòu)成生成矩陣就能構(gòu)成生成矩陣G！生成多項(xiàng)式確定后，則生成多項(xiàng)式確定后，則g(x)、x g(x)、 xk-1 g(x)都是碼組，都是碼組，且這且這k個(gè)碼組信息無(wú)關(guān)，因此可以用來(lái)構(gòu)成生成矩陣。個(gè)碼組信息無(wú)關(guān)，因此可以用來(lái)構(gòu)成生成矩陣。g(x)確定了確定了G(x)也就確定了也就確定了整個(gè)碼

37、組即確定！整個(gè)碼組即確定！第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-2945例例: : ( 7，3 )循環(huán)碼，循環(huán)碼， g(x) = x4+x2+x+1 求求 典型生成矩陣典型生成矩陣解解:6643225532420( )1011100( )010 1110( )001 01111xxxxxx g xxGxg xxxxxg xxxxx(x)典型陣典型陣: :100 1011010 1110001 0111kGI Q可方便地直接寫(xiě)成碼組形式可方便地直接寫(xiě)成碼組形式第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-2946（3） g(x) 與與

38、T(x) 的關(guān)系的關(guān)系（7，3）26546542654( )( ) ( )( )( )( )( ) ( )x g xT xa a a G xa a axg xg xa xa xag xh x g x12( )( )( )( )( )kkxg xxg xG xxg xg x表明：表明：所有所有T(x)都可以被都可以被g(x)整除，而且任一次數(shù)不大于整除，而且任一次數(shù)不大于(k-1)的的多項(xiàng)式乘以多項(xiàng)式乘以g(x)都是碼多項(xiàng)式。都是碼多項(xiàng)式。第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼現(xiàn)代通信系統(tǒng)原理2021-10-2947依據(jù)依據(jù): : g(x)是是xn+1的一個(gè)的一個(gè)(n-k)次的因子，且常數(shù)項(xiàng)不

39、為零。次的因子，且常數(shù)項(xiàng)不為零。證：證：任一循環(huán)多項(xiàng)式任一循環(huán)多項(xiàng)式T(x)都是都是g(x)的倍式，即的倍式，即( )( ) ( )T xh x g x( )( )T xg x( )( )ix T xTx而生成而生成多項(xiàng)式多項(xiàng)式g(x)本身也是一個(gè)碼組，即有本身也是一個(gè)碼組，即有由于碼組由于碼組T(x)為一為一（n-k）次多項(xiàng)式，故次多項(xiàng)式，故xkT(x) 為一為一n次多次多項(xiàng)式。由項(xiàng)式。由知，知，xkT(x)在模在模（xn+1）的運(yùn)算下，亦的運(yùn)算下，亦為一碼組，故可寫(xiě)成為一碼組，故可寫(xiě)成 11knnx TxT xQ xxx（4） 如何尋找如何尋找g(x)第第9 9章章 差錯(cuò)控制編碼差錯(cuò)控制編

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