通信原理 第五版 第9章 差錯(cuò)控制編碼

1、 第第 九九 章章差錯(cuò)控制編碼差錯(cuò)控制編碼信信源源信信源源編編碼碼信信道道編編碼碼調(diào)調(diào)制制發(fā)發(fā)轉(zhuǎn)轉(zhuǎn)換換器器媒媒質(zhì)質(zhì)收收轉(zhuǎn)轉(zhuǎn)換換器器解解調(diào)調(diào)信信道道譯譯碼碼信信源源譯譯碼碼信信宿宿9.0 引言引言目的：目的：提高通信系統(tǒng)的可靠性提高通信系統(tǒng)的可靠性 降低誤碼率，減少發(fā)射功率，提高接收機(jī)的靈敏度等等。降低誤碼率，減少發(fā)射功率，提高接收機(jī)的靈敏度等等。1. 隨機(jī)性差錯(cuò)：隨機(jī)性差錯(cuò)：差錯(cuò)是隨機(jī)的且相互之間是獨(dú)立出現(xiàn)。通常差錯(cuò)是隨機(jī)的且相互之間是獨(dú)立出現(xiàn)。通常由由高斯白噪聲引起；高斯白噪聲引起；12位錯(cuò)誤。位錯(cuò)誤。2. 突發(fā)性差錯(cuò)：突發(fā)性差錯(cuò)：由脈沖性干擾引起由脈沖性干擾引起, ,在短暫的時(shí)間內(nèi)出現(xiàn)連續(xù)

2、在短暫的時(shí)間內(nèi)出現(xiàn)連續(xù)的差錯(cuò)，而這些短暫時(shí)間之后卻又存在較長的無誤碼區(qū)間。的差錯(cuò)，而這些短暫時(shí)間之后卻又存在較長的無誤碼區(qū)間。一、差錯(cuò)類型一、差錯(cuò)類型9.1 糾錯(cuò)編碼的基本概念糾錯(cuò)編碼的基本概念混合性差錯(cuò)：混合性差錯(cuò)：既存在隨機(jī)差錯(cuò)又有突發(fā)性差錯(cuò)。既存在隨機(jī)差錯(cuò)又有突發(fā)性差錯(cuò)。以上兩種錯(cuò)誤性質(zhì)不同，可采取不同措施處理以上兩種錯(cuò)誤性質(zhì)不同，可采取不同措施處理 ！ 可以用來檢測一位錯(cuò)誤可以用來檢測一位錯(cuò)誤 可糾正一位錯(cuò)誤或檢測兩位錯(cuò)誤可糾正一位錯(cuò)誤或檢測兩位錯(cuò)誤AB 許用碼組許用碼組 禁用碼組禁用碼組 00 01 11 10 采用采用2 2位二進(jìn)制碼位二進(jìn)制碼許用碼組許用碼組 禁用碼組禁用碼組 0

3、00 001 010 100 111 101 110 011采用采用3 3位二進(jìn)制碼位二進(jìn)制碼采用采用1 1位二進(jìn)制碼位二進(jìn)制碼01二、差錯(cuò)控制的基本方法二、差錯(cuò)控制的基本方法 在信息序列之后附加一些監(jiān)督碼元在信息序列之后附加一些監(jiān)督碼元，這些多余的碼元與信，這些多余的碼元與信息碼元之間以某種確定的規(guī)則相互關(guān)聯(lián)，接收端按照既定的規(guī)息碼元之間以某種確定的規(guī)則相互關(guān)聯(lián)，接收端按照既定的規(guī)則檢驗(yàn)出關(guān)聯(lián)關(guān)系，如這種規(guī)則受到破壞，將會發(fā)現(xiàn)錯(cuò)誤，乃則檢驗(yàn)出關(guān)聯(lián)關(guān)系，如這種規(guī)則受到破壞，將會發(fā)現(xiàn)錯(cuò)誤，乃至糾正錯(cuò)誤。至糾正錯(cuò)誤。例：例：三、檢錯(cuò)與糾錯(cuò)能力三、檢錯(cuò)與糾錯(cuò)能力與最小碼距與最小碼距 d0 的關(guān)系的關(guān)

4、系結(jié)論：結(jié)論：最小碼距決最小碼距決定檢錯(cuò)和糾錯(cuò)能力定檢錯(cuò)和糾錯(cuò)能力(c) 為了同時(shí)檢測為了同時(shí)檢測e個(gè)錯(cuò)誤，糾正個(gè)錯(cuò)誤，糾正t個(gè)錯(cuò)誤個(gè)錯(cuò)誤d0 et1(b) 為了糾正為了糾正t個(gè)錯(cuò)誤個(gè)錯(cuò)誤 d0 2t1(a) 為了檢測為了檢測e個(gè)錯(cuò)誤，個(gè)錯(cuò)誤， d0 e1碼距：碼距：兩個(gè)碼組對應(yīng)位上不同的數(shù)目。兩個(gè)碼組對應(yīng)位上不同的數(shù)目。 碼重：碼重：碼組中碼組中“1”的數(shù)目。的數(shù)目。AB0 1 2 3d0e(a)AB0 1 2 3 4 5d0tt(b)ABd0et tt1(c)四、差錯(cuò)控制編碼的效用四、差錯(cuò)控制編碼的效用 假設(shè)在隨機(jī)信道中發(fā)假設(shè)在隨機(jī)信道中發(fā)“0”0”和發(fā)和發(fā)“1”1”的概率相同，在碼長為的

5、概率相同，在碼長為n的碼組中恰好發(fā)生的碼組中恰好發(fā)生 r 個(gè)錯(cuò)誤的概率為：個(gè)錯(cuò)誤的概率為：( p為誤碼率為誤碼率 )rrnrrnnprnrnppCrP)!( !)1 ()(371077) 1 (pP527101 . 221)2(pP837105 . 335) 3(pP310p當(dāng)碼長當(dāng)碼長 n7 ，誤碼率誤碼率 時(shí)時(shí) ，則有：則有：結(jié)論：采用差錯(cuò)控制編碼，即使僅能糾正（或檢測）結(jié)論：采用差錯(cuò)控制編碼，即使僅能糾正（或檢測）12個(gè)錯(cuò)誤，就能使誤碼率下降幾個(gè)數(shù)量級。個(gè)錯(cuò)誤，就能使誤碼率下降幾個(gè)數(shù)量級。 五、糾錯(cuò)碼的五、糾錯(cuò)碼的1. 分組碼與卷積碼分組碼與卷積碼：分組碼：分組碼：將信息碼分組，為每組信

6、息碼后面附加若干位監(jiān)督碼元，且將信息碼分組，為每組信息碼后面附加若干位監(jiān)督碼元，且 監(jiān)督碼元僅監(jiān)督本碼組中的信息位監(jiān)督碼元僅監(jiān)督本碼組中的信息位。1na2nara1ra0a K個(gè)信息位個(gè)信息位r個(gè)監(jiān)督位個(gè)監(jiān)督位碼長碼長 nkr卷積碼：卷積碼：卷積碼也是先將信息序列分組，后面附加監(jiān)督位，但是監(jiān)卷積碼也是先將信息序列分組，后面附加監(jiān)督位，但是監(jiān)督位不但與本碼組的信息位有關(guān)，還與前面碼組的信息位有關(guān)，或督位不但與本碼組的信息位有關(guān)，還與前面碼組的信息位有關(guān)，或者說監(jiān)督位不僅監(jiān)督本碼組的信息位還監(jiān)督其它碼組的信息位者說監(jiān)督位不僅監(jiān)督本碼組的信息位還監(jiān)督其它碼組的信息位。2. 系統(tǒng)碼與非系統(tǒng)碼系統(tǒng)碼與非

7、系統(tǒng)碼系統(tǒng)碼：系統(tǒng)碼：就是信息位在前，監(jiān)督位在后的碼字。就是信息位在前，監(jiān)督位在后的碼字。非系統(tǒng)碼非系統(tǒng)碼: : 信息位與監(jiān)督位之間無特定的位置關(guān)系。信息位與監(jiān)督位之間無特定的位置關(guān)系。9.2 差錯(cuò)控制方式差錯(cuò)控制方式2. 前向糾錯(cuò)前向糾錯(cuò)（FEC） 可以糾正錯(cuò)誤可以糾正錯(cuò)誤 發(fā)發(fā) 收收3. 混和糾錯(cuò)混和糾錯(cuò)（HEC） 可以發(fā)現(xiàn)和糾正錯(cuò)誤可以發(fā)現(xiàn)和糾正錯(cuò)誤 發(fā)發(fā) 收收 應(yīng)答信號應(yīng)答信號 比較：比較：譯碼復(fù)雜性、實(shí)時(shí)性和占用傳輸鏈路譯碼復(fù)雜性、實(shí)時(shí)性和占用傳輸鏈路(單向還是雙向單向還是雙向)1. 檢錯(cuò)重發(fā)（檢錯(cuò)重發(fā)（ARQ） （包括停發(fā)等候重發(fā)、返回重發(fā)和選擇重發(fā)）（包括停發(fā)等候重發(fā)、返回重發(fā)和

8、選擇重發(fā)） 能夠發(fā)現(xiàn)錯(cuò)誤能夠發(fā)現(xiàn)錯(cuò)誤 發(fā)發(fā) 收收 應(yīng)答信號應(yīng)答信號ARQ：自動重復(fù)請求發(fā)送：自動重復(fù)請求發(fā)送1233123ACKNAKACK等待時(shí)間等待時(shí)間發(fā)送端發(fā)送端接收端接收端1 2 3 4 5 6 2 3 4 5 6 7 8 9 10 111 2 3 4 5 6 2 3 4 5 6 7 8 9 10 11從碼組從碼組2 2開始重發(fā)開始重發(fā)NAKACK發(fā)現(xiàn)錯(cuò)誤發(fā)現(xiàn)錯(cuò)誤 停發(fā)等候重發(fā)停發(fā)等候重發(fā) 返回重發(fā)返回重發(fā)1 2 3 4 5 6 2 7 8 9 10 1 12 1 2 3 4 5 6 2 7 8 9 10 1112重發(fā)重發(fā)碼組碼組2 2NAKACK發(fā)現(xiàn)錯(cuò)誤發(fā)現(xiàn)錯(cuò)誤選擇重發(fā)選擇重發(fā)比較反

9、返回重發(fā)和選擇重發(fā)：比較反返回重發(fā)和選擇重發(fā)： 看起來只重傳特定的幀比同時(shí)將未損壞的幀一起傳顯得更有效，看起來只重傳特定的幀比同時(shí)將未損壞的幀一起傳顯得更有效，但是由于接收方進(jìn)行的排序和存儲所需的復(fù)雜度，以及發(fā)送方選擇重但是由于接收方進(jìn)行的排序和存儲所需的復(fù)雜度，以及發(fā)送方選擇重傳所需的額外邏輯，選擇重發(fā)傳所需的額外邏輯，選擇重發(fā)ARQARQ的開銷更大，所以并不常用。的開銷更大，所以并不常用。（1）幀損壞：）幀損壞：接收方發(fā)現(xiàn)錯(cuò)誤，就返回一個(gè)否認(rèn)幀給發(fā)送方，發(fā)送方重發(fā)最后一幀。接收方發(fā)現(xiàn)錯(cuò)誤，就返回一個(gè)否認(rèn)幀給發(fā)送方，發(fā)送方重發(fā)最后一幀。發(fā)送方發(fā)送方接收方接收方數(shù)據(jù)幀數(shù)據(jù)幀0ACK1數(shù)據(jù)幀數(shù)據(jù)

10、幀1ACK0數(shù)據(jù)幀數(shù)據(jù)幀0NAK時(shí)間時(shí)間時(shí)間時(shí)間等待時(shí)間等待時(shí)間等待時(shí)間等待時(shí)間等待時(shí)間等待時(shí)間停等停等ARQ，損壞幀損壞幀數(shù)據(jù)幀數(shù)據(jù)幀0ACK1。正確正確有錯(cuò)誤有錯(cuò)誤停等停等ARQ：（ 2） 幀丟失幀丟失（a）丟失數(shù)據(jù)幀：丟失數(shù)據(jù)幀： 發(fā)送設(shè)備等待發(fā)送設(shè)備等待ACK或或NAK幀直到定時(shí)器超時(shí)幀直到定時(shí)器超時(shí)；（b）確認(rèn)幀丟失確認(rèn)幀丟失: 接收方檢查到達(dá)的新數(shù)據(jù)幀編號。接收方檢查到達(dá)的新數(shù)據(jù)幀編號。如果丟失的是如果丟失的是NAK幀，接收方將接收新的數(shù)據(jù)幀拷貝并返回一個(gè)幀，接收方將接收新的數(shù)據(jù)幀拷貝并返回一個(gè)ACK幀；幀；如果丟失的是如果丟失的是ACK幀，則接收方將新的數(shù)據(jù)幀拷貝視為重復(fù)幀，對它

11、的接幀，則接收方將新的數(shù)據(jù)幀拷貝視為重復(fù)幀，對它的接收進(jìn)行確認(rèn)并等待下一幀的到來收進(jìn)行確認(rèn)并等待下一幀的到來發(fā)送方發(fā)送方接收方接收方數(shù)據(jù)幀數(shù)據(jù)幀0ACK1數(shù)據(jù)幀數(shù)據(jù)幀0ACK1時(shí)間時(shí)間時(shí)間時(shí)間超時(shí)超時(shí)等待時(shí)間等待時(shí)間停等停等ARQ，確認(rèn)幀丟失，確認(rèn)幀丟失。丟失丟失9.3 常用的簡單糾錯(cuò)碼常用的簡單糾錯(cuò)碼1. 奇偶校驗(yàn)奇偶校驗(yàn)偶校驗(yàn)00121 aaaann設(shè)信息位每組長度為設(shè)信息位每組長度為n-1n-1位，增加一位監(jiān)督位，位，增加一位監(jiān)督位，n n位編碼構(gòu)成以下位編碼構(gòu)成以下約束關(guān)系約束關(guān)系 錯(cuò)誤正確100121aaaaSnn接收端計(jì)算校正子接收端計(jì)算校正子奇偶校驗(yàn)可以用來檢測單個(gè)或奇數(shù)個(gè)錯(cuò)誤奇

12、偶校驗(yàn)可以用來檢測單個(gè)或奇數(shù)個(gè)錯(cuò)誤2. . 縱向奇偶校驗(yàn)（縱向奇偶校驗(yàn)（LRC）用于檢測突發(fā)錯(cuò)誤）用于檢測突發(fā)錯(cuò)誤11100111 11011101 00111001 1010100111100111110111010011100110101001縱向排列縱向排列原是數(shù)據(jù)原是數(shù)據(jù)11100111 11011101 00111001 10101001 10101010突發(fā)錯(cuò)誤突發(fā)錯(cuò)誤接收方檢驗(yàn)是否滿足接收方檢驗(yàn)是否滿足LRCLRC 10101010監(jiān)督碼元監(jiān)督碼元交織編碼：交織編碼： 針對突發(fā)性錯(cuò)誤針對突發(fā)性錯(cuò)誤 信信 息息 碼碼 元元 0 1 0 1 1 0 1 1 0 0 0 1 0 1 0

13、 1 0 0 1 0 0 0 1 1 0 0 0 0 1 1 1 1 0 0 0 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 1 0 1 1 0 0 0 0 監(jiān)督碼元監(jiān)督碼元 0 0 1 1 1 0 0 0 0 1 0監(jiān)督碼元監(jiān)督碼元 1 0 0 1 0 1 13. 水平垂直奇偶校驗(yàn)水平垂直奇偶校驗(yàn)它能發(fā)現(xiàn)某一行或某一列上所有奇數(shù)個(gè)錯(cuò)誤以它能發(fā)現(xiàn)某一行或某一列上所有奇數(shù)個(gè)錯(cuò)誤以及長度不大于行數(shù)（或列數(shù)）的突發(fā)錯(cuò)誤及長度不大于行數(shù)（或列數(shù)）的突發(fā)錯(cuò)誤5. 群計(jì)數(shù)碼群計(jì)數(shù)碼111001 100信息位信息位監(jiān)督位監(jiān)督位發(fā)現(xiàn)所有奇數(shù)個(gè)錯(cuò)誤

14、，以及一些偶數(shù)個(gè)錯(cuò)誤，除發(fā)現(xiàn)所有奇數(shù)個(gè)錯(cuò)誤，以及一些偶數(shù)個(gè)錯(cuò)誤，除“0”變變“1”，和，和“1”變變“0”成對出現(xiàn)。成對出現(xiàn)。4. 等重碼（恒比碼）等重碼（恒比碼）數(shù)字?jǐn)?shù)字 電電 碼碼 數(shù)字?jǐn)?shù)字 電電 碼碼 0 0 1 1 0 1 5 0 0 1 1 1 1 0 1 0 1 1 6 1 0 1 0 1 2 1 1 0 0 1 7 1 1 1 0 0 3 1 0 1 1 0 8 0 1 1 1 0 4 1 1 0 1 0 9 1 0 0 1 15中取中取3，或，或7中取中取4作業(yè)：作業(yè)：9-3，9-59.4 線性分組碼線性分組碼定義：定義：信息位和監(jiān)督位之間的關(guān)系是由線性方程組約束的編碼稱信息位

15、和監(jiān)督位之間的關(guān)系是由線性方程組約束的編碼稱作線性分組碼，即監(jiān)督碼元是由信息碼元的線性組合而產(chǎn)生。作線性分組碼，即監(jiān)督碼元是由信息碼元的線性組合而產(chǎn)生。奇偶校驗(yàn)碼就是一種效率很高的線性分組碼奇偶校驗(yàn)碼就是一種效率很高的線性分組碼。0121aaaaSnn 這里這里S稱為校正子，若稱為校正子，若S0，表示無錯(cuò)，表示無錯(cuò)，S1表示有錯(cuò)誤，由表示有錯(cuò)誤，由于只用了一位監(jiān)督位于只用了一位監(jiān)督位a 0 ，因此只能表示有錯(cuò)與無錯(cuò)。，因此只能表示有錯(cuò)與無錯(cuò)。若監(jiān)督位增加到若監(jiān)督位增加到2位，就可增加一個(gè)監(jiān)督方程式，接收時(shí)就可位，就可增加一個(gè)監(jiān)督方程式，接收時(shí)就可計(jì)算計(jì)算2個(gè)校正子個(gè)校正子S1和和 S2 ，共有

16、四種可能，除了，共有四種可能，除了00表示無錯(cuò)以表示無錯(cuò)以外，其余外，其余3種就可以表示一位錯(cuò)碼的的具體位置了種就可以表示一位錯(cuò)碼的的具體位置了。對于二進(jìn)制編碼，知道了錯(cuò)誤的位置，就可以實(shí)現(xiàn)糾錯(cuò)了對于二進(jìn)制編碼，知道了錯(cuò)誤的位置，就可以實(shí)現(xiàn)糾錯(cuò)了一般說來對于，對一般說來對于，對 r r個(gè)監(jiān)督位，可以計(jì)算個(gè)監(jiān)督位，可以計(jì)算r 個(gè)校正子，它可以指個(gè)校正子，它可以指出出 種錯(cuò)誤圖樣，即種錯(cuò)誤圖樣，即 個(gè)錯(cuò)誤位置，因此對于個(gè)錯(cuò)誤位置，因此對于（n，k）碼。要想指出一位錯(cuò)碼的所有可能位置，則要求：碼。要想指出一位錯(cuò)碼的所有可能位置，則要求：2 1r2 1r 設(shè)分組碼中設(shè)分組碼中（n，k）中中k4，為了糾

17、正一位錯(cuò)誤，為了糾正一位錯(cuò)誤，則則 ，取，取r3，則，則n7，用用 表示，用表示，用 表示由表示由3 3個(gè)監(jiān)督方程式計(jì)算得到的校正子，并假設(shè)這個(gè)監(jiān)督方程式計(jì)算得到的校正子，并假設(shè)這3 3個(gè)校正子與誤碼對應(yīng)的關(guān)系如下表所示：個(gè)校正子與誤碼對應(yīng)的關(guān)系如下表所示：3r0123456aaaaaaa123SSStiinrtiinrCC01212或?qū)τ趯τ诩m正糾正t 個(gè)錯(cuò)誤個(gè)錯(cuò)誤一、線性分組碼的構(gòu)成：一、線性分組碼的構(gòu)成：rknCnr112糾正糾正1 1個(gè)錯(cuò)誤個(gè)錯(cuò)誤校正子表校正子表 S1S2S3 誤碼位置誤碼位置 S1S2S3 誤碼位置誤碼位置 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0

18、1 1 1 0 1 1 0 0 0 無錯(cuò)無錯(cuò)0a1a6a5a4a3a2a因此接收端計(jì)算下面因此接收端計(jì)算下面3個(gè)校驗(yàn)關(guān)系，可確定誤碼的位置個(gè)校驗(yàn)關(guān)系，可確定誤碼的位置24561aaaaS13562aaaaS03463aaaaS發(fā)送端構(gòu)成偶校驗(yàn)關(guān)系發(fā)送端構(gòu)成偶校驗(yàn)關(guān)系由此監(jiān)督位可以由信息位的線性組合得到：由此監(jiān)督位可以由信息位的線性組合得到：000034613562456aaaaaaaaaaaa346035614562aaaaaaaaaaaa許用碼組許用碼組信息位信息位 監(jiān)督位監(jiān)督位 信息位信息位 監(jiān)督位監(jiān)督位 0 0 0 0 0 0 0 1 0 0 0 111 0 0 0 1 0 1 1 1

19、0 0 1 100 0 0 1 0 1 0 1 1 0 1 0 010 0 0 1 1 1 1 0 1 0 1 1 001 0 1 0 0 1 1 0 1 1 0 0 001 0 1 0 1 1 0 1 1 1 0 1 010 0 1 1 0 0 1 1 1 1 1 0 100 0 1 1 1 0 0 0 1 1 1 1 1113456aaaa012aaa3456aaaa012aaa 010011010010101100010111012345601234560123456aaaaaaaaaaaaaaaaaaaaa 0001001101010101100101110123456Taaaaaaa

20、線性分組碼的生成和監(jiān)督矩陣線性分組碼的生成和監(jiān)督矩陣監(jiān)督矩陣監(jiān)督矩陣TTHA0 即即 0123456aaaaaaaA 0000 100110101010110010111H其中：其中： 34634565634560123456aaaaaaaaaaaaaaaaaaaa TaaaaaaaaaaaaaaA 01234560123456對于所有的編碼與信息位的關(guān)系：對于所有的編碼與信息位的關(guān)系： , , rIPH 1001101010101100101110krrIrr0HP為為 階矩陣，階矩陣， 為為 階單位陣階單位陣，具有具有 形式稱為典型形式的監(jiān)督矩陣；形式稱為典型形式的監(jiān)督矩陣；線性代數(shù)理論告

21、訴我們，典型形式的監(jiān)督矩陣各行一定是線性無關(guān)的，線性代數(shù)理論告訴我們，典型形式的監(jiān)督矩陣各行一定是線性無關(guān)的，非典型形式的監(jiān)督矩陣可以通過矩陣的初等變換化為典型形式。非典型形式的監(jiān)督矩陣可以通過矩陣的初等變換化為典型形式。 Gaaaaaaaa345634561101000101010001100101110001 QIGk 1101000101010001100101110001其中其中TTaaaaaaaaaaaaaaaaa 345634635645634561111111111111 GaaaaA 3456則則全部碼字由信息位與生成矩陣全部碼字由信息位與生成矩陣G相乘得到相乘得到Q為為K r

22、 階矩陣階矩陣。I k為為k 階單位陣階單位陣具有典型化形式具有典型化形式 的生成矩陣稱為典型生成矩陣的生成矩陣稱為典型生成矩陣 QIGk, , 0它與典型化形式它與典型化形式 的關(guān)系為：的關(guān)系為： rIPH, , 0TTPQQP 或或, ,結(jié)論：結(jié)論： 1). 由典型化的生成矩陣產(chǎn)生的是系統(tǒng)碼組；由典型化的生成矩陣產(chǎn)生的是系統(tǒng)碼組；k 2). 典型化的生成矩陣的各行也必定是線性無關(guān)的，每一行都是典型化的生成矩陣的各行也必定是線性無關(guān)的，每一行都是一個(gè)許用碼組，一個(gè)許用碼組，k行許用碼組進(jìn)過運(yùn)算可以生成行許用碼組進(jìn)過運(yùn)算可以生成 2 個(gè)不同的碼組，個(gè)不同的碼組， 非典型形式的生成矩陣經(jīng)過運(yùn)算也

23、一定可化為典型形式。非典型形式的生成矩陣經(jīng)過運(yùn)算也一定可化為典型形式。 0001101001101001101001101000G例：若線性分組碼的生成矩陣為例：若線性分組碼的生成矩陣為典型陣為典型陣為 00011010010111010001110001100G 1001110010011100111010H監(jiān)督矩陣監(jiān)督矩陣三、線性分組碼的特性：三、線性分組碼的特性：1) 任意兩個(gè)許用碼組之和仍為許用碼組封閉性任意兩個(gè)許用碼組之和仍為許用碼組封閉性2) 碼的最小距離等于非零碼的最小重量碼的最小距離等于非零碼的最小重量。四、四、線性分組碼的伴隨式譯碼線性分組碼的伴隨式譯碼 , ,. . . .

24、 . . . ., , , 021rrrRnn 設(shè)發(fā)送的碼組為設(shè)發(fā)送的碼組為A，接收的碼組為接收的碼組為R， , ,. . . . . . . ., , , 021eeeEnn 設(shè)設(shè)E為傳輸錯(cuò)誤圖樣為傳輸錯(cuò)誤圖樣，則則：RAETTTTTEHEHAHHEARHS ) )( (計(jì)算校正子計(jì)算校正子TTHES 或者或者對于前面（對于前面（7，4）碼的例子，一位錯(cuò)誤圖樣為：）碼的例子，一位錯(cuò)誤圖樣為： (1000000) , (0100000)， (0010000)，(0001000)， (0000100)，(0000001), (0000001)611100000011001101010101100

25、10111HHET 50110000010100110101010110010111H 01001000000100110101010110010111H .例：若接收的碼組為例：若接收的碼組為1001101計(jì)算伴隨式計(jì)算伴隨式 ：002361001011001100110101010110010111HHHHHHESTT 最后一位有錯(cuò)，譯碼得：最后一位有錯(cuò)，譯碼得：1001100校正子校正子S只與只與E有關(guān)，若接收碼字有關(guān)，若接收碼字R中第中第I 位有錯(cuò)，那么導(dǎo)出的伴位有錯(cuò)，那么導(dǎo)出的伴隨式隨式 恰好是矩陣恰好是矩陣H的第的第i 列相同的位置。利用伴隨式不列相同的位置。利用伴隨式不僅可以判決

26、接收碼字中是否有錯(cuò)，而且可以指出差錯(cuò)的位置。僅可以判決接收碼字中是否有錯(cuò)，而且可以指出差錯(cuò)的位置。TTHES 作業(yè)：作業(yè)：9-79.5 循環(huán)碼循環(huán)碼一、特點(diǎn)：一、特點(diǎn)：循環(huán)碼是一種具有循環(huán)移位特性的線性分組碼，這循環(huán)碼是一種具有循環(huán)移位特性的線性分組碼，這類碼除了具有線性分組碼的一般性質(zhì)外，還具有循環(huán)性質(zhì)帶來類碼除了具有線性分組碼的一般性質(zhì)外，還具有循環(huán)性質(zhì)帶來的其它性能和特征，并可以用不太長的碼長來實(shí)現(xiàn)，循環(huán)碼本的其它性能和特征，并可以用不太長的碼長來實(shí)現(xiàn)，循環(huán)碼本身的特性使編譯設(shè)備比較容易實(shí)現(xiàn)。身的特性使編譯設(shè)備比較容易實(shí)現(xiàn)。1. 碼多項(xiàng)式碼多項(xiàng)式：012211cxcxcxcxCnnnn

27、) )( (1012 nnCCCC 0121CCCCCnn 若若 是一個(gè)碼字是一個(gè)碼字1210CCCCnn 則則C的每次的每次循環(huán)移位都是一個(gè)碼字循環(huán)移位都是一個(gè)碼字）模（17x,., 12987xxxxx) 1(2346236xxxxxxxx) 1(23422456xxxxxxxx) 1(1234525xxxxxxx) 1(12343356xxxxxxx1234xxx) 1(234345xxxxxxxx) 1(1234446xxxxxxx序號序號 信息碼信息碼 (7.3)循環(huán)碼循環(huán)碼 移位次數(shù)移位次數(shù) 碼多項(xiàng)式碼多項(xiàng)式0 000 0000000 1 001 0011101 02 011 01

28、11010 13 111 1110100 24 110 1101001 35 101 1010011 46 010 0100111 57 100 1001110 6例例 ：(7，3)循環(huán)碼循環(huán)碼按模運(yùn)算規(guī)則：模按模運(yùn)算規(guī)則：模n運(yùn)算下，一整數(shù)運(yùn)算下，一整數(shù)m等于其被等于其被n除得到的余數(shù)除得到的余數(shù)模運(yùn)算中，模運(yùn)算中，rqnmnrnrqnm或)(一般的講，若一整數(shù)一般的講，若一整數(shù)m可表示為可表示為rm 則：則： （模（模n）)()()()()()()(xgxrxFxrxgxqxF模則2. 按模運(yùn)算按模運(yùn)算)(xC)(xCXi1nx)()(xCxCxii結(jié)論：結(jié)論：可以證明在循環(huán)碼中可以證明在

29、循環(huán)碼中, , 若若 是一個(gè)碼長為是一個(gè)碼長為n的許用碼的許用碼組多項(xiàng)式，則組多項(xiàng)式，則 在模在模 運(yùn)算下亦是許用碼組，運(yùn)算下亦是許用碼組，即若有：即若有：)(xCi則則 也是一個(gè)許用碼組。也是一個(gè)許用碼組。2456xxxx前面的（前面的（7，3）1110100碼多項(xiàng)式碼多項(xiàng)式35672456)(xxxxxxxxx左移一位的多項(xiàng)式左移一位的多項(xiàng)式 1356xxx1110100左移一位的碼組左移一位的碼組1101001對應(yīng)的多項(xiàng)式對應(yīng)的多項(xiàng)式13563567xxxxxxx）（模17x顯然顯然1111356735677xxxxxxxxx多項(xiàng)式除法多項(xiàng)式除法： 二、循環(huán)碼的生成多項(xiàng)式二、循環(huán)碼的生成

30、多項(xiàng)式對于線性分組碼來說只要找到它的生成矩陣就可確定所有的對于線性分組碼來說只要找到它的生成矩陣就可確定所有的編碼碼字，而它的生成矩陣的每一行都是一個(gè)許用碼組，循環(huán)編碼碼字，而它的生成矩陣的每一行都是一個(gè)許用碼組，循環(huán)碼的某一個(gè)碼字循環(huán)移位可得到它的碼字。只要找到這個(gè)碼字碼的某一個(gè)碼字循環(huán)移位可得到它的碼字。只要找到這個(gè)碼字就可以得到生成矩陣。這個(gè)碼字稱為生成多項(xiàng)式（碼字）。就可以得到生成矩陣。這個(gè)碼字稱為生成多項(xiàng)式（碼字）。)()()()()(0121xgxxgxxgxxgxxGk生成矩陣可寫為：生成矩陣可寫為：對于線性分組碼，其生成矩陣由對于線性分組碼，其生成矩陣由K 行線性無關(guān)的碼字組成

31、行線性無關(guān)的碼字組成2. (n，k)循環(huán)碼的生成多項(xiàng)式循環(huán)碼的生成多項(xiàng)式g g (x)(x)是是 的因式的因式1nx定理：定理：1. 在一個(gè)在一個(gè)(n，k)循環(huán)碼中，存在一個(gè)唯一的最低次碼多循環(huán)碼中，存在一個(gè)唯一的最低次碼多項(xiàng)項(xiàng)式，式， 其次數(shù)為其次數(shù)為 r = n - k，且常數(shù)項(xiàng)必須為且常數(shù)項(xiàng)必須為，即生成多項(xiàng)式即生成多項(xiàng)式1)(111xgxgxxgknknkn1nx)(xg)(xg3. 若是一個(gè)若是一個(gè)(nk)次多項(xiàng)式，且是次多項(xiàng)式，且是 的因式，則的因式，則 一定能生成一個(gè)一定能生成一個(gè)(n，k)循環(huán)碼循環(huán)碼)(xg)(xC0)(xC)(xg模4. 所有碼多項(xiàng)式必定能被整除，所有碼多項(xiàng)

32、式必定能被整除，即即)(xg)(xg就是說階數(shù)小于就是說階數(shù)小于(n-1)(n-1)能被能被 整除的每個(gè)多項(xiàng)式都是循環(huán)碼整除的每個(gè)多項(xiàng)式都是循環(huán)碼的許用碼組，或必是的倍式的許用碼組，或必是的倍式 (7.k) 循環(huán)碼循環(huán)碼(n . k) d g( x) h( x ) (7.6) 2(7.4) 3(7.3) 4(7.1) 61) 1)(1(1111) 1)(1() 1)(1(11) 1)(1() 1(32332324234233323323或或或或xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx1nx結(jié)論：結(jié)論：(1) 一個(gè)一個(gè)( (n，k) )循環(huán)碼的每一個(gè)碼多項(xiàng)式也必然是按循環(huán)碼的

33、每一個(gè)碼多項(xiàng)式也必然是按模模 運(yùn)算后某個(gè)余式，即一個(gè)運(yùn)算后某個(gè)余式，即一個(gè)(n，k)循環(huán)碼的所有碼字都循環(huán)碼的所有碼字都可以通過可以通過k 個(gè)許用碼多項(xiàng)式循環(huán)移位得到。個(gè)許用碼多項(xiàng)式循環(huán)移位得到。循環(huán)碼完全由其碼組長度循環(huán)碼完全由其碼組長度n及生成多項(xiàng)式及生成多項(xiàng)式 g (x)決定決定123 xxxg) )( (例：一個(gè)例：一個(gè)(7，4) 循環(huán)碼，則由生成多項(xiàng)式循環(huán)碼，則由生成多項(xiàng)式 000110100110100110100110100012334245356xxxxxxxxxxxxG) )( (構(gòu)成的生成矩陣為構(gòu)成的生成矩陣為典型陣為典型陣為 00011010010111010001110

34、001100G 1001110010011100111010H監(jiān)督矩陣監(jiān)督矩陣三、循環(huán)碼的系統(tǒng)碼的編碼實(shí)現(xiàn)三、循環(huán)碼的系統(tǒng)碼的編碼實(shí)現(xiàn)系統(tǒng)碼組中的最左邊的系統(tǒng)碼組中的最左邊的k k位是信息碼元，隨后是位是信息碼元，隨后是n nk k位的監(jiān)位的監(jiān)督碼元，即碼多項(xiàng)式為：督碼元，即碼多項(xiàng)式為：011011rxrxmxmxrxxmxCknknknnkkn ) )( () )( () )( (）（模（模) )( () )( () )( () )( () )( (xgxxmxcxxmxrknkn 因此因此) )( () )( () )( () )( () )( (xgxrxqxgxmxkn 有：有：m (

35、x) x 除法求余得到除法求余得到r ( x)n - k例例：已知已知 (7，4) 循環(huán)碼的生成多項(xiàng)式為循環(huán)碼的生成多項(xiàng)式為若信息碼為若信息碼為1001 ，求編碼碼字，求編碼碼字123 xxxg) )( (11113633 xxxxxxxC) )( () )( (因此：因此：13 xxm) )( (解：解：112333 xxxxxgxmxkn) )( () )( () )( (11112323 xxrxxxxxx) )( (即編碼碼組為：即編碼碼組為： 1001011 S0 S1輸入輸入m。 S2。K1K2輸出輸出ef輸入輸入 移移 存存 器器 反饋反饋 輸出輸出 m S0 S1 S2 e f

36、 0 0 0 0 0 00 0 0 0 0 0 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 0 1 1 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 反饋反饋 e=S21+m0123 xxxg) )( (作業(yè)作業(yè)：9-1，9-6，9-7，9-8，9-13，9-14 (n ,k) 循環(huán)碼編碼器循環(huán)碼編碼器10 gSn-