Chapter 9 差錯(cuò)控制編碼

1、9.1 概述9.2檢錯(cuò)與糾錯(cuò)原理9.3簡單分組碼 9.4線性分組碼9.5循環(huán)碼Chapter9 差錯(cuò)控制編碼1.9.1 概述 9.1.1 信源編碼與信道編碼信源編碼：信道編碼：加入冗余度去掉冗余度提高通信可靠性及模數(shù)轉(zhuǎn)換提高通信有效性2.提高數(shù)字系統(tǒng)的抗干擾性能的途徑：加大發(fā)射功率降低接收設(shè)備本身的噪聲選擇調(diào)制、解調(diào)方法信道編碼9.1.2 差錯(cuò)控制方式 9.1 概述 3.圖 9-1 差錯(cuò)控制方式 9.1 概述 4.1. 前向糾錯(cuò)方式特點(diǎn)：單向傳輸，實(shí)時(shí)性好，譯碼設(shè)備較復(fù)雜2. 檢錯(cuò)重發(fā)方式特點(diǎn)：需要反饋信道，譯碼設(shè)備簡單，對突發(fā)錯(cuò)誤和信道干擾較嚴(yán)重時(shí)有效， 實(shí)時(shí)性差，主要應(yīng)用于計(jì)算機(jī)數(shù)據(jù)通信中

2、9.1 概述 5.3. 混合糾錯(cuò)方式特點(diǎn)：結(jié)合自動(dòng)糾錯(cuò)和檢錯(cuò)重發(fā)的優(yōu)點(diǎn)，可達(dá)到較低的誤碼率4. 幾個(gè)重要概念隨機(jī)信道：差錯(cuò)出現(xiàn)是隨機(jī)的，且錯(cuò)誤之間是統(tǒng)計(jì)獨(dú)立的。例如，恒參高斯白噪聲信道是典型的隨機(jī)信道突發(fā)信道：錯(cuò)誤成串成群出現(xiàn)，在短時(shí)間內(nèi)出現(xiàn)大量錯(cuò)誤。例如，脈沖干擾的信道是典型的突發(fā)信道9.1 概述 6.混合信道：隨機(jī)錯(cuò)誤和成串錯(cuò)誤都占有相當(dāng)比例。例如，短波信道和對流層散射信道。說明：不同類型的信道，應(yīng)采用不同的差錯(cuò)控制方式9.1 概述 7.9.2 檢錯(cuò)與糾錯(cuò)原理 9.2.1 糾錯(cuò)碼的分類1.根據(jù)糾錯(cuò)碼各碼組信息元和監(jiān)督元的關(guān)系線性碼非線性碼2.信息元和監(jiān)督元的關(guān)系涉及的范圍：分組碼卷積碼8.

3、3.根據(jù)碼的用途檢錯(cuò)碼糾錯(cuò)碼9.2.2 檢糾錯(cuò)的基本原理 1. 分組碼(n,k)分組碼：k每組二進(jìn)制信息碼元的數(shù)目n碼組長度，或碼長n-k=r監(jiān)督碼元數(shù)目9.2 檢錯(cuò)與糾錯(cuò)原理 9.重要概念：許用碼組、禁用碼組、碼重（碼字的漢明重量）、碼距、最小碼距問題：許用碼組個(gè)數(shù)？禁用碼組個(gè)數(shù)？2. 檢錯(cuò)和糾錯(cuò)能力 最小碼距是碼的一個(gè)重要參數(shù)， 是衡量碼檢、糾錯(cuò)能力的依據(jù)。關(guān)系如下：9.2 檢錯(cuò)與糾錯(cuò)原理 10.(3) 糾正t個(gè)同時(shí)檢測e(t)個(gè)隨機(jī)錯(cuò)誤，則要求碼的最小距離d0t+e+1。 (1) 檢測e個(gè)隨機(jī)錯(cuò)誤，則要求碼的最小距離d0e+1;(2) 糾正t個(gè)隨機(jī)錯(cuò)誤， 則要求碼的最小距離d02t+1;

4、舉例：重復(fù)碼(2,1)，許用碼組是 00 與 11， d0=2，收端譯碼，出現(xiàn) 01、10 禁用碼組時(shí)，可以發(fā)現(xiàn)傳輸中的一位錯(cuò)誤。9.2 檢錯(cuò)與糾錯(cuò)原理 11.重復(fù)碼(3,1) ，許用碼組 000 與111, d0=3; 當(dāng)收端出現(xiàn)兩個(gè)或三個(gè) 1 時(shí)，判為 1，否則判為 0?？杉m單個(gè)錯(cuò)誤，或者檢兩個(gè)錯(cuò)誤。3. 編碼效率差錯(cuò)控制編碼提高通信系統(tǒng)的可靠性， 以降低有效性為代價(jià)編碼效率：R=k/nk是信息元的個(gè)數(shù)，n為碼長9.2 檢錯(cuò)與糾錯(cuò)原理 12.4. 對糾錯(cuò)碼的要求檢錯(cuò)和糾錯(cuò)能力盡量強(qiáng)編碼效率盡量高編碼規(guī)律盡量簡單9.2 檢錯(cuò)與糾錯(cuò)原理 13.9.3 常用的幾種簡單分組碼9.3.1 奇偶監(jiān)督碼

5、 編碼規(guī)則：在原信息碼后面附加一個(gè)監(jiān)督元， 使得碼組中“1”的個(gè)數(shù)是奇數(shù)或偶數(shù)設(shè)碼字A=an-1,an-2,a1,a0，對偶監(jiān)督碼有： 偶監(jiān)督碼奇監(jiān)督碼14.奇監(jiān)督碼：兩者的檢錯(cuò)能力相同。特點(diǎn)：奇監(jiān)督碼的碼重為奇數(shù)，偶監(jiān)督碼的碼重為偶數(shù)。(n,n-1)系統(tǒng)分組碼編碼效率R為：不能檢測突發(fā)錯(cuò)誤，不能發(fā)現(xiàn)偶數(shù)個(gè)錯(cuò)誤9.3 常用的幾種簡單分組碼15.9.3.2 水平奇偶監(jiān)督碼編碼規(guī)則：將奇偶監(jiān)督的碼元排成方陣，每行為一組奇偶監(jiān)督碼。發(fā)送按列的順序傳輸，接收將碼元序列還原成發(fā)送時(shí)的方陣，并按行進(jìn)行奇偶校驗(yàn)。舉例：信息碼元監(jiān)督碼元1110011000110100110110000111010001000

6、0101100111011101019.3 常用的幾種簡單分組碼16.能夠發(fā)現(xiàn)某行上所有奇數(shù)個(gè)錯(cuò)誤以及突發(fā)長度不大于方陣行數(shù)的突發(fā)錯(cuò)誤 編碼效率：9.3 常用的幾種簡單分組碼17.水平奇偶監(jiān)督碼接收端出現(xiàn)突發(fā)誤碼示例:1101結(jié)論：能夠發(fā)現(xiàn)突發(fā)長度不大于方陣行數(shù)的突發(fā)錯(cuò)誤18.9.3.3 行列監(jiān)督碼編碼規(guī)則：不僅對水平(行)方向的碼元，而且對垂直(列)方向的碼元實(shí)施奇偶監(jiān)督。舉例：圖 9-2 (66,50)行列監(jiān)督碼 9.3 常用的幾種簡單分組碼19. 又稱為方陣碼、行列監(jiān)督碼、二維奇偶監(jiān)督碼。 將水平奇偶監(jiān)督碼推廣到二維。即在水平監(jiān)督基礎(chǔ)上再對方陣中每一列進(jìn)行奇偶校驗(yàn)，發(fā)送時(shí)按列的順序傳輸

7、接收端將碼元排成發(fā)送時(shí)的方陣形式，再分別按行、按列進(jìn)行奇偶校驗(yàn)9.3 常用的幾種簡單分組碼20.水平垂直奇偶監(jiān)督碼接收端糾錯(cuò)示例011例如：當(dāng)碼組中僅在一行有奇數(shù)個(gè)錯(cuò)誤時(shí)，能夠確定錯(cuò)誤位置，并糾正它。21.水平垂直奇偶監(jiān)督碼接收端檢錯(cuò)示例011構(gòu)成矩形的偶數(shù)個(gè)誤碼檢測不出。0022.水平垂直奇偶監(jiān)督碼接收端檢錯(cuò)示例01有可能檢測出偶數(shù)個(gè)誤碼。00123.特點(diǎn)：LM個(gè)信息元附加L+M+1個(gè)監(jiān)督元，組成(LM+L+M+1,LM)行列監(jiān)督碼的一個(gè)碼字(L+1行，M+1列)具有較強(qiáng)的檢測能力，適于檢測突發(fā)錯(cuò)誤，還可用于糾錯(cuò)9.3.4 群計(jì)數(shù)碼編碼規(guī)則：把信息碼元中“1”的個(gè)數(shù)用二進(jìn)制數(shù)字表示，作為監(jiān)督

8、碼元放在信息碼元的后面。特點(diǎn)：具有較強(qiáng)的檢測能力。9.3 常用的幾種簡單分組碼24.9.3.5 恒比碼碼字中 1 的數(shù)目與 0 的數(shù)目保持恒定比例。表 9-1 32 恒比碼 舉例：9.3 常用的幾種簡單分組碼25.9.4 線 性 分 組 碼 9.4.1 基本概念 線性分組碼：在(n,k)分組碼中，若每一個(gè)監(jiān)督元都是碼組中某些信息元按模二和而得到，即監(jiān)督元是按線性關(guān)系相加而得到。舉例：(7,3)線性分組碼設(shè)其碼字為A=a6 a5 a4 a3 a2 a1 a0前 3 位是信息元，后 4位是監(jiān)督元26.表 9-4 (7,3)碼的碼字表 序號(hào)碼元信息元監(jiān)督元0000000010011101201001

9、1130111010410011105101001161101001711101009.4 線 性 分 組 碼 27.9.4.2 漢明碼 漢明碼：用于糾正單個(gè)錯(cuò)誤的線性分組碼。舉例：(7,4)漢明碼設(shè)其碼字為A=a6 a5 a4 a3 a2 a1 a0前 4位是信息元，后 3位是監(jiān)督元s3 s2 s1三個(gè)校正子9.4 線 性 分 組 碼 28.S1S2S3錯(cuò)碼位置S1S2S3錯(cuò)碼位置001010100011a0a1 a2 a3101110111000a4a5 a6無錯(cuò)表 9-5 校正子與錯(cuò)碼位置的對應(yīng)關(guān)系3個(gè)監(jiān)督方程：9.4 線 性 分 組 碼 29.當(dāng)三個(gè)校正子均為0，則有：推導(dǎo)出監(jiān)督元滿足

10、：9.4 線 性 分 組 碼 30.(7,4)漢明碼的許用碼組如下：表 9-6 (7,4)漢明碼的16個(gè)許用碼組 問題：漢明碼的編碼效率為多少？31.9.4.3 監(jiān)督矩陣H以上述(7,4)碼為例：3 個(gè)監(jiān)督方程式可以改寫為：線性方程用矩陣形式表示：9.4 線 性 分 組 碼 32.其中，AT是A的轉(zhuǎn)置，0T是0=0 0 0的轉(zhuǎn)置，HT是H的轉(zhuǎn)置。 簡記為： 監(jiān)督矩陣H為rn階矩陣，H矩陣每行之間是彼此線性無關(guān)的。H矩陣的特點(diǎn)：H矩陣可分成兩部分：9.4 線 性 分 組 碼 33.其中,P為rk階矩陣，Ir為rr階單位矩陣典型監(jiān)督矩陣：可以寫成H=P Ir形式的矩陣。HAT=0T ，H矩陣與碼字

11、的轉(zhuǎn)置乘積必為零，可以用來作為判斷接收碼字A是否出錯(cuò)的依據(jù)9.4.4 生成矩陣G 9.4 線 性 分 組 碼 34.若把監(jiān)督方程補(bǔ)充為下列方程： 仍以上述(7,4)碼為例：改寫為矩陣形式：9.4 線 性 分 組 碼 35.變換為 ：即： 9.4 線 性 分 組 碼 36.其中： 生成矩陣G和信息組就可以產(chǎn)生全部碼字生成矩陣的特點(diǎn)：G為kn階矩陣，各行也是線性無關(guān)的生成矩陣也可以分為兩部分：9.4 線 性 分 組 碼 37.Q為kr階矩陣,Ik為k階單位陣典型生成矩陣：可以寫成式 形式的G矩陣9.4.5 伴隨式(校正子)S和檢錯(cuò) 9.4 線 性 分 組 碼 38.設(shè)發(fā)送碼組： A=an-1,an

12、-2,a1,a0接收碼組：B=bn-1,bn-2,b1,b0傳輸過程中可能發(fā)生誤碼誤差矢量：收發(fā)碼組之差定義為錯(cuò)誤圖樣E。其中E=en-1,en-2,e1,e0，且 當(dāng)bi=ai 當(dāng)biai 9.4 線 性 分 組 碼 39.令S=BHT，稱為伴隨式或校正子。 總結(jié)：伴隨式S與錯(cuò)誤圖樣E之間有確定的線性變換關(guān)系。接收端譯碼器的任務(wù)就是從伴隨式確定錯(cuò)誤圖樣，然后從接收到的碼字中減去錯(cuò)誤圖樣。9.4 線 性 分 組 碼 40.表 9-7 (7,4)碼S與E的對應(yīng)關(guān)系 9.4 線 性 分 組 碼 41.已知（6，3）漢明碼(能糾正單個(gè)錯(cuò)誤的線性分組碼)的生成矩陣如下，(1)列出所有許用碼組;(2)最

13、小碼距d0;(3)檢錯(cuò)糾錯(cuò)能力(4)編碼效率9.4 線 性 分 組 碼 42.（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 0343.（3）（4）（2）9.4 線 性 分 組 碼 44.設(shè)（7,4）線性碼的生成矩陣G為：當(dāng)信息位為0001時(shí)，（1）試求其后的監(jiān)督位。（2）監(jiān)督矩陣H9.4 線 性 分 組 碼 45.解：（1）9.4 線 性 分 組 碼

14、46.（2）監(jiān)督矩陣H根據(jù)生成矩陣和監(jiān)督矩陣的關(guān)系：G= IkQ，H=PIr其中P=QT，可得監(jiān)督矩陣H為：9.4 線 性 分 組 碼 47.9.4.6 線性分組碼的性質(zhì) 有封閉性有零碼有負(fù)元滿足結(jié)合律滿足交換律最小碼距等于線性分組碼中非全零碼組的最小重量9.4 線 性 分 組 碼 48.9.5 循 環(huán) 碼 9.5.1 循環(huán)特性 循環(huán)碼：任一碼字循環(huán)移位所得的碼字仍為該碼組中的一個(gè)碼字，這種具有循環(huán)性的線性分組碼稱為循環(huán)碼。循環(huán)碼的碼字常用碼多項(xiàng)式（以降冪順序排列）表示。49.表 9-8 (7,3)循環(huán)碼的全部碼組 9.5 循 環(huán) 碼 50.9.5.2 生成多項(xiàng)式及生成矩陣 碼的生成多項(xiàng)式：如

15、果一種碼的所有碼多項(xiàng)式都是多項(xiàng)式g(x)的倍式，則稱g(x)為該碼的生成多項(xiàng)式舉例：上述(7,3)循環(huán)碼其它碼多項(xiàng)式都是g(x)的倍式， 即 9.5 循 環(huán) 碼 51.結(jié)論：1）循環(huán)碼中次數(shù)最低的碼多項(xiàng)式(全 0 碼字除外)就是生成多項(xiàng)式g(x)；2）g(x)是常數(shù)項(xiàng)為1 的r=n-k 次多項(xiàng)式， 是xn+1 的一個(gè)因式9.5 循 環(huán) 碼 52.循環(huán)碼的生成矩陣用多項(xiàng)式形式表示： 其中： 9.5 循 環(huán) 碼 53.舉例：(7,3)循環(huán)碼，n=7, k=3, r=4, 其生成多項(xiàng)式及生成矩陣分別為： 9.5 循 環(huán) 碼 54.9.5.3 監(jiān)督多項(xiàng)式及監(jiān)督矩陣監(jiān)督多項(xiàng)式：其中：g(x)是常數(shù)項(xiàng)為

16、1 的r次多項(xiàng)式，是生成多項(xiàng)式；h(x)是常數(shù)項(xiàng)為 1 的k次多項(xiàng)式，稱為監(jiān)督多項(xiàng)式。監(jiān)督矩陣H：9.5 循 環(huán) 碼 55.其中： 是h(x)的逆多項(xiàng)式。9.5 循 環(huán) 碼 56.舉例：(7，3)循環(huán)碼則： 9.5 循 環(huán) 碼 57.即： 9.5.4 編碼方法和電路 9.5 循 環(huán) 碼 58. 思路：在編碼時(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)為: 9.5 循 環(huán) 碼 循環(huán)碼的碼多項(xiàng)式可表示為 :用xr乘m(x)，相當(dāng)于把信息碼后附加上r個(gè)“0”59. 用g(x)除xr m(x)，得到商式Q(x)和余式為R(x)9.5 循 環(huán) 碼 編出碼組為：A(x)= xr m(x)+ R(x)60.即余式r(x)=x2+1于是，對應(yīng)碼組A(x)= xn-k m(x)+r(x）= x6+x5+ x2+1 編碼為1100101例題 設(shè)（7，3）循環(huán)碼的生成多項(xiàng)式為g(x)=x4+x2+x+1，待編碼信息位為110，求對應(yīng)循環(huán)碼碼組。解：m(x)