第九章差錯(cuò)控制編碼_sxq

1、第第9 9章章差錯(cuò)控制編碼差錯(cuò)控制編碼南京航空航天大學(xué)信息科學(xué)與技術(shù)學(xué)院南京航空航天大學(xué)信息科學(xué)與技術(shù)學(xué)院 通信原理教研組通信原理教研組copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組2引言引言1糾錯(cuò)編碼的基本原理糾錯(cuò)編碼的基本原理2常用的簡單編碼常用的簡單編碼3線性分組碼線性分組碼4循環(huán)碼循環(huán)碼5第第9章章 差錯(cuò)控制編碼差錯(cuò)控制編碼67卷積碼卷積碼網(wǎng)格編碼調(diào)制網(wǎng)格編碼調(diào)制copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組39.1 引言引言信道信道解調(diào)解調(diào)信源信源編碼編碼加密加密調(diào)制調(diào)制解密解密譯碼譯碼信宿信宿噪聲噪聲同步系

2、統(tǒng)同步系統(tǒng)信源編碼信源編碼 信道編碼信道編碼 差錯(cuò)控制差錯(cuò)控制ASKFSKPSKDPSK數(shù)字通信的組成數(shù)字通信的組成A/DA/D數(shù)據(jù)壓縮數(shù)據(jù)壓縮copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組4采用信道編碼采用信道編碼 在通信過程中，會(huì)受到各種外來干擾，如脈沖干擾，隨在通信過程中，會(huì)受到各種外來干擾，如脈沖干擾，隨機(jī)噪聲干擾，人為干擾及通信線路傳輸性能的限制都將使信機(jī)噪聲干擾，人為干擾及通信線路傳輸性能的限制都將使信號失真。由于以上原因，引起數(shù)據(jù)信息序列產(chǎn)生錯(cuò)誤，稱之號失真。由于以上原因，引起數(shù)據(jù)信息序列產(chǎn)生錯(cuò)誤，稱之為為差錯(cuò)差錯(cuò)。 隨機(jī)性錯(cuò)誤：前后出錯(cuò)位之

3、間無一定關(guān)系，隨機(jī)、離散出現(xiàn)。隨機(jī)性錯(cuò)誤：前后出錯(cuò)位之間無一定關(guān)系，隨機(jī)、離散出現(xiàn)。突發(fā)性錯(cuò)誤：差錯(cuò)成串出現(xiàn)，且有一定相關(guān)性。突發(fā)性錯(cuò)誤：差錯(cuò)成串出現(xiàn)，且有一定相關(guān)性。差錯(cuò)的兩大類型：差錯(cuò)的兩大類型： 合理的設(shè)計(jì)基帶信號合理的設(shè)計(jì)基帶信號時(shí)域時(shí)域/頻域均衡頻域均衡 都能有效的提高傳輸可靠性。都能有效的提高傳輸可靠性。發(fā)射功率的提高發(fā)射功率的提高copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組5數(shù)字通信中的編碼數(shù)字通信中的編碼信道編碼：信道編碼：信源編碼：信源編碼： 為為提高信號傳輸?shù)挠行蕴岣咝盘杺鬏數(shù)挠行远扇〉拇胧?。而采取的措施。為為提高信號傳輸?shù)目煽?/p>

4、性提高信號傳輸?shù)目煽啃远扇〉拇胧┒扇〉拇胧? ,亦稱亦稱差錯(cuò)控制編碼。差錯(cuò)控制編碼。 在發(fā)送端利用信道編碼器在數(shù)據(jù)信息中增在發(fā)送端利用信道編碼器在數(shù)據(jù)信息中增加一些監(jiān)督信息，使不帶規(guī)律性或規(guī)律性不加一些監(jiān)督信息，使不帶規(guī)律性或規(guī)律性不強(qiáng)的原始數(shù)字信號變?yōu)閹б?guī)律性或加強(qiáng)了規(guī)強(qiáng)的原始數(shù)字信號變?yōu)閹б?guī)律性或加強(qiáng)了規(guī)律性的數(shù)字信號，律性的數(shù)字信號，信道譯碼器信道譯碼器則利用這些規(guī)則利用這些規(guī)律性來鑒別是否發(fā)生錯(cuò)誤，或進(jìn)行錯(cuò)誤糾正。律性來鑒別是否發(fā)生錯(cuò)誤，或進(jìn)行錯(cuò)誤糾正。差錯(cuò)控制差錯(cuò)控制copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組6 1、差錯(cuò)控制方法、差錯(cuò)控制

5、方法（1）前向糾錯(cuò)法）前向糾錯(cuò)法FEC 所發(fā)碼具有糾錯(cuò)能力，收端接收后自動(dòng)糾所發(fā)碼具有糾錯(cuò)能力，收端接收后自動(dòng)糾錯(cuò)，無需反向信道。實(shí)時(shí)性好，但譯碼設(shè)備錯(cuò)，無需反向信道。實(shí)時(shí)性好，但譯碼設(shè)備復(fù)雜，復(fù)雜，傳輸效率傳輸效率 。信源信源FEC編碼編碼信道信道FEC譯碼譯碼信宿信宿copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組7（2）信息反饋法）信息反饋法IF信息信號信息信號信息信號信息信號發(fā)端收端收端 方法和設(shè)備簡單，無需糾檢錯(cuò)編譯系統(tǒng)。方法和設(shè)備簡單，無需糾檢錯(cuò)編譯系統(tǒng)。但需要但需要雙向信道雙向信道，傳輸效率傳輸效率、實(shí)時(shí)性差、實(shí)時(shí)性差 。copyright 信

6、息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組8(3)檢錯(cuò)重發(fā)法檢錯(cuò)重發(fā)法ARQ 所發(fā)碼具有檢錯(cuò)能力，收端接收后判決是否出錯(cuò)，通所發(fā)碼具有檢錯(cuò)能力，收端接收后判決是否出錯(cuò)，通過反向信道發(fā)送判決結(jié)果，發(fā)端據(jù)此決定是否重發(fā)。過反向信道發(fā)送判決結(jié)果，發(fā)端據(jù)此決定是否重發(fā)。 譯碼設(shè)備簡單，對突發(fā)錯(cuò)誤有效，要求有反饋信道。譯碼設(shè)備簡單，對突發(fā)錯(cuò)誤有效，要求有反饋信道。信源信源編碼器編碼器正向信道正向信道譯碼器譯碼器信宿信宿緩存器緩存器重發(fā)控制器重發(fā)控制器反向信道反向信道重發(fā)判決器重發(fā)判決器工作過程：發(fā)送工作過程：發(fā)送檢測檢測回復(fù)回復(fù)重發(fā)或發(fā)送新的數(shù)據(jù)重發(fā)或發(fā)送新的數(shù)據(jù)copyright

7、信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組9停止等待方式停止等待方式 3221221發(fā)送端發(fā)送端接收端接收端 ARQARQ的三種實(shí)現(xiàn)方式：的三種實(shí)現(xiàn)方式： 特點(diǎn)：半雙工工作，簡單，要求的緩存量小，但等待時(shí)間較長，特點(diǎn)：半雙工工作，簡單，要求的緩存量小，但等待時(shí)間較長，傳輸效率傳輸效率 copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組10 連續(xù)重發(fā)方式 6543254321065432543210退退N N步方式：從出錯(cuò)幀開始重發(fā)步方式：從出錯(cuò)幀開始重發(fā)優(yōu)缺點(diǎn)：傳輸效率優(yōu)缺點(diǎn)：傳輸效率，但重發(fā)的，但重發(fā)的N N幀中，大部分幀中，大部分為正

8、確，所以仍有浪費(fèi)。發(fā)端緩存必須可存為正確，所以仍有浪費(fèi)。發(fā)端緩存必須可存N N幀。幀。 copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組112987654321029876543210 只對出錯(cuò)信息重發(fā)，因此傳輸效率大大提只對出錯(cuò)信息重發(fā)，因此傳輸效率大大提高高 。但收發(fā)兩端都要有足夠的存儲(chǔ)空間。但收發(fā)兩端都要有足夠的存儲(chǔ)空間。 選擇重發(fā)方式 copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組12反饋信道反饋信道ARQFEC編碼器編碼器正向信道正向信道FEC譯碼器譯碼器ARQ 編碼既有糾錯(cuò)能力也有檢錯(cuò)能力，收端收到編碼既有糾

9、錯(cuò)能力也有檢錯(cuò)能力，收端收到信息碼組后在收端進(jìn)行檢測。在糾錯(cuò)范圍內(nèi)：信息碼組后在收端進(jìn)行檢測。在糾錯(cuò)范圍內(nèi)：糾正；超出范圍：通過糾正；超出范圍：通過ARQARQ方式進(jìn)行重發(fā)。方式進(jìn)行重發(fā)。 (4) 混合方式copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組13（1）根據(jù)各碼組信息碼和監(jiān)督碼的關(guān)系分：根據(jù)各碼組信息碼和監(jiān)督碼的關(guān)系分： 線性碼，非線性碼線性碼，非線性碼根據(jù)監(jiān)督碼元是否僅與本組信息元有關(guān)根據(jù)監(jiān)督碼元是否僅與本組信息元有關(guān) 分組碼，卷積碼分組碼，卷積碼（2）根據(jù)糾錯(cuò)碼組中信息元是否隱蔽分：根據(jù)糾錯(cuò)碼組中信息元是否隱蔽分： 系統(tǒng)碼，非系統(tǒng)碼系統(tǒng)碼，非系

10、統(tǒng)碼（3）糾錯(cuò)碼的分類糾錯(cuò)碼的分類copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組14根據(jù)碼的用途分：根據(jù)碼的用途分： 檢錯(cuò)碼檢錯(cuò)碼 ，糾錯(cuò)碼，糾錯(cuò)碼（4）根據(jù)根據(jù)碼元的取值碼元的取值： 二進(jìn)制碼，多進(jìn)制碼二進(jìn)制碼，多進(jìn)制碼（5）根據(jù)根據(jù)構(gòu)造編碼的數(shù)學(xué)方法構(gòu)造編碼的數(shù)學(xué)方法： 代數(shù)碼，幾何碼，算術(shù)碼代數(shù)碼，幾何碼，算術(shù)碼（6）本課程主要討論糾隨機(jī)錯(cuò)誤的二進(jìn)制線性分組碼。本課程主要討論糾隨機(jī)錯(cuò)誤的二進(jìn)制線性分組碼。copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組15糾錯(cuò)碼的發(fā)展概況糾錯(cuò)碼的發(fā)展概況n 通信的數(shù)學(xué)理論，通信的數(shù)

11、學(xué)理論，Shannon(1948)Shannon(1948)n 漢明碼，漢明碼，Hamming (1950)Hamming (1950)n 級連碼，級連碼，F(xiàn)orney(1966)Forney(1966)n 卷積碼及有效譯碼，卷積碼及有效譯碼，(60(60年代年代) )n RS RS碼及有效譯碼，碼及有效譯碼，(60(60年代年代) )n TCM TCM，Ungerboeck(1982),Forney(1984)Ungerboeck(1982),Forney(1984)n Turbo Turbo碼，碼，Berrou(1993) Berrou(1993) n LDPC LDPC 碼，碼，Gall

12、ager(1963),Macky(1996)Gallager(1963),Macky(1996)n 空時(shí)編碼空時(shí)編碼,Tarokh(2000),Tarokh(2000)copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組169.2 糾錯(cuò)編碼的基本原理糾錯(cuò)編碼的基本原理1、 幾個(gè)術(shù)語幾個(gè)術(shù)語碼長：碼長：碼組中碼元的數(shù)目，常用碼組中碼元的數(shù)目，常用n n表示；表示；碼距：碼距：兩等長碼字兩等長碼字C C1 1、C C2 2對應(yīng)位上取值不同的對應(yīng)位上取值不同的數(shù)目，又稱為漢明數(shù)目，又稱為漢明(Hamming)(Hamming)距離，記為距離，記為d(cd(c1 1,c

13、,c2 2) )。碼重碼重：碼組中非零碼元的數(shù)目，記為：碼組中非零碼元的數(shù)目，記為W W；copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組17n=3時(shí)，碼距的幾何說明：時(shí)，碼距的幾何說明：（ a2 a1 a0 ）a2a1a0（ 110） （ 011 ）d=2110011（ 111） （ 000 ）d=3000111最小碼距最小碼距：在分組碼：在分組碼(n,k)(n,k)中，任意兩個(gè)碼字之中，任意兩個(gè)碼字之間漢明距離的最小值，記為間漢明距離的最小值，記為d dminmin。最小碼距的大小關(guān)系到編碼的檢最小碼距的大小關(guān)系到編碼的檢糾糾錯(cuò)能力錯(cuò)能力。0101011

14、00001copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組18發(fā)送序列發(fā)送序列C: (1111011000)接收序列接收序列R: (0110010110)比較比較C和和R，可寫出另一個(gè)序列，可寫出另一個(gè)序列E：1001001110R = C + E 序列序列E定義為錯(cuò)誤圖樣定義為錯(cuò)誤圖樣(Error Pattern)錯(cuò)誤圖樣：錯(cuò)誤圖樣：copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組19A A、B B兩消息，可用一位二進(jìn)制數(shù)表示，兩消息，可用一位二進(jìn)制數(shù)表示，A=1A=1、B=0B=0出錯(cuò)時(shí)出錯(cuò)時(shí)無法判定無法判定 增加一個(gè)

15、監(jiān)督位，取增加一個(gè)監(jiān)督位，取11A11A、00B00B 再增加一個(gè)監(jiān)督位，取再增加一個(gè)監(jiān)督位，取111A111A、000B000B許用碼組：許用碼組：00，11禁用碼組：禁用碼組：01，10若收到若收到0101或或1010時(shí)，時(shí)，可知發(fā)生了錯(cuò)誤，但不能糾正錯(cuò)誤可知發(fā)生了錯(cuò)誤，但不能糾正錯(cuò)誤。許用碼組：000，111禁用碼組：001, 010, 100, 011, 101, 110如一位錯(cuò)如一位錯(cuò)能夠糾正錯(cuò)誤能夠糾正錯(cuò)誤；若兩位錯(cuò)，；若兩位錯(cuò)，則只能發(fā)現(xiàn)不能糾錯(cuò)則只能發(fā)現(xiàn)不能糾錯(cuò)2、糾錯(cuò)或檢錯(cuò)的原理、糾錯(cuò)或檢錯(cuò)的原理copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教

16、研組20因此因此這種（這種（3,13,1）碼，能糾正一個(gè)錯(cuò)，發(fā)現(xiàn)兩個(gè)錯(cuò)。）碼，能糾正一個(gè)錯(cuò)，發(fā)現(xiàn)兩個(gè)錯(cuò)。 但是但是 (3,1)(3,1)碼中，數(shù)據(jù)位僅為碼中，數(shù)據(jù)位僅為1 1位，監(jiān)督位為位，監(jiān)督位為兩位，傳輸效率兩位，傳輸效率 可以看出：差錯(cuò)控制是以可以看出：差錯(cuò)控制是以犧牲傳輸效率犧牲傳輸效率為代價(jià)而為代價(jià)而換取了傳輸質(zhì)量的提高的。糾檢錯(cuò)能力與加入的監(jiān)督換取了傳輸質(zhì)量的提高的。糾檢錯(cuò)能力與加入的監(jiān)督元方式和數(shù)目有關(guān)。元方式和數(shù)目有關(guān)。copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組21分組碼的三個(gè)參數(shù)分組碼的三個(gè)參數(shù)碼長碼長 n，信息位，信息位 k，最小距

17、離，最小距離 d0 ， 用符號用符號 (n,k,d0) 表示表示k個(gè)信息元個(gè)信息元an-1 an-2 ar ar-1 a0 r個(gè)監(jiān)督元個(gè)監(jiān)督元碼長：碼長：n = k+rR=k/n為為編碼效率編碼效率，d0一定一定(糾錯(cuò)能力一定糾錯(cuò)能力一定)時(shí)，時(shí)，k/n大，效率高。大，效率高。 對被傳輸?shù)男畔⑿蛄蟹纸M，每組為對被傳輸?shù)男畔⑿蛄蟹纸M，每組為k k個(gè)信息元，對個(gè)信息元，對每組按某種關(guān)系附加每組按某種關(guān)系附加(n-k) (n-k) 個(gè)監(jiān)督碼元個(gè)監(jiān)督碼元 ( (校驗(yàn)校驗(yàn)) )，形成，形成為為n n位的碼字。這種方法構(gòu)成的碼組稱為位的碼字。這種方法構(gòu)成的碼組稱為分組碼分組碼。3、分組碼、分組碼copyr

18、ight 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組224、分組碼的糾分組碼的糾( (檢檢) )錯(cuò)能力與最小碼距錯(cuò)能力與最小碼距d d0 0的關(guān)系的關(guān)系 任一任一（n n，k k）分組碼，若要在碼字內(nèi)能：分組碼，若要在碼字內(nèi)能： 1/ 1/ 檢測檢測e e個(gè)隨機(jī)錯(cuò)誤，則要求：個(gè)隨機(jī)錯(cuò)誤，則要求： d d0 e+1e+1 2/ 2/ 糾正糾正t t個(gè)隨機(jī)錯(cuò)誤，則要求：個(gè)隨機(jī)錯(cuò)誤，則要求： d d0 0 2 2t+1t+1 3/ 3/ 糾正糾正t t個(gè)同時(shí)檢測個(gè)同時(shí)檢測e e(et)(et)個(gè)隨機(jī)錯(cuò)誤，個(gè)隨機(jī)錯(cuò)誤，則要求：則要求： d d0 0 e+t+1 e+t+1 cop

19、yright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組231 A1 d0eA2（a）A1 A2 d0et（c） A1 d0tA2（b） A2t11copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組24例例9-1一個(gè)碼集，只有兩個(gè)許用碼：一個(gè)碼集，只有兩個(gè)許用碼：00000000、11111111，試求其糾、檢錯(cuò)能力和編碼效率。試求其糾、檢錯(cuò)能力和編碼效率。copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組25解：解：根據(jù)碼距的定義，則該碼集根據(jù)碼距的定義，則該碼集d0 = 4， 1/ 用于檢錯(cuò)，用于檢錯(cuò)

20、，e d d0 0 1=3，即可檢，即可檢3個(gè)錯(cuò)誤；個(gè)錯(cuò)誤；2/ 用于糾錯(cuò)，用于糾錯(cuò)，t (d d0 01)/2=3/2，取整，即可糾，取整，即可糾1個(gè)錯(cuò)誤；個(gè)錯(cuò)誤；3/ 同時(shí)用于糾、檢錯(cuò)，同時(shí)用于糾、檢錯(cuò)， d d0 0 e+t+1 e+t+1 （e et t） ?。喝。篹=2，t=1，則可滿足上式，即可檢，則可滿足上式，即可檢2個(gè)錯(cuò)誤個(gè)錯(cuò)誤 同時(shí)糾一個(gè)錯(cuò)；同時(shí)糾一個(gè)錯(cuò)；R=k/n=1/4copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組26copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組275. 差錯(cuò)控制編碼的效用差錯(cuò)控

21、制編碼的效用 假設(shè)在隨機(jī)信道中，發(fā)送假設(shè)在隨機(jī)信道中，發(fā)送“0 0”和和“1 1”的錯(cuò)的錯(cuò)誤概率相等，都等于誤概率相等，都等于p p，且，且p p1 1，在碼長為，在碼長為n n的碼組中，發(fā)生的碼組中，發(fā)生r r個(gè)錯(cuò)誤的概率為：個(gè)錯(cuò)誤的概率為：!( )(1)!()!rrn rrnnnP rC pppr nrcopyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組28!( )(1)!()!rrn rrnnnP rC pppr nr例如：當(dāng)例如：當(dāng)n=7，p=10-時(shí)，則有：時(shí)，則有：371077) 1 (pP5227101 . 221)!27( ! 2! 7)2(pp

22、P8337105 . 335)!37( ! 3! 7) 3(ppP 由此可見，即使僅能糾正由此可見，即使僅能糾正1-21-2個(gè)錯(cuò)誤，也可使誤碼個(gè)錯(cuò)誤，也可使誤碼率下降幾個(gè)數(shù)量級。所以差錯(cuò)控制編碼具有較大的實(shí)率下降幾個(gè)數(shù)量級。所以差錯(cuò)控制編碼具有較大的實(shí)際應(yīng)用價(jià)值。際應(yīng)用價(jià)值。copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組296. 6. 有擾信道編碼定理（有擾信道編碼定理（ShannonShannon第二定理）第二定理） 對于給定的有擾信道，若信道容量為對于給定的有擾信道，若信道容量為C C，只，只要發(fā)送端以低于要發(fā)送端以低于C C的信息速率的信息速率R R

23、b b發(fā)送信息，則發(fā)送信息，則一定存在一種編碼方法一定存在一種編碼方法，使得譯碼錯(cuò)誤概率，使得譯碼錯(cuò)誤概率P P隨著碼長隨著碼長n n的增加，按指數(shù)下降至任意小的值，的增加，按指數(shù)下降至任意小的值，表示為表示為 P P e e-nE(Rb)-nE(Rb)E(RE(Rb b) )為誤差指數(shù)，為誤差指數(shù)，R Rb bC0)0。 Rbmax=C=Blog2(1+S/N) （bit/s）copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組30 1.碼長碼長n和信息速率和信息速率Rb一定時(shí)，隨一定時(shí)，隨C誤差指數(shù)誤差指數(shù)E(Rb) P隨指數(shù)下降。隨指數(shù)下降。 其中其中 C

24、=Blog2(1+S/N)（bit/s） 2.在在C和和Rb一定時(shí)一定時(shí)(Rb C)，隨碼長，隨碼長n P 隨指數(shù)下降隨指數(shù)下降(P0)。 數(shù)字傳輸系統(tǒng)中，無誤碼傳輸?shù)淖罡咝畔⑺俾蕯?shù)字傳輸系統(tǒng)中，無誤碼傳輸?shù)淖罡咝畔⑺俾?Rbmax=C=Blog2(1+S/N) （bit/s） 兩個(gè)結(jié)論：兩個(gè)結(jié)論：copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組31編碼性能舉例 未采用糾錯(cuò)編碼時(shí)，若接收信噪比等于7dB，編碼前誤碼率約為810-4，圖中A點(diǎn)，在采用糾錯(cuò)編碼后，誤碼率降至約410-5，圖中B點(diǎn)。這樣，增大發(fā)送功率,就能降低誤碼率約一個(gè)半數(shù)量級。10-610-5

25、10-410-310-210-1編碼后PeAB信噪比 (dB)copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組32 由圖還可以看出，若保持由圖還可以看出，若保持誤碼率在誤碼率在1010-5-5，圖中，圖中C C點(diǎn)，點(diǎn)，未采用編碼時(shí)，約需要信未采用編碼時(shí)，約需要信噪比噪比E Eb b / n / n0 0 = 9.5 dB = 9.5 dB。在采用這種編碼時(shí)，約需在采用這種編碼時(shí)，約需要信噪比要信噪比7.5 dB7.5 dB，圖中，圖中D D點(diǎn)。可以節(jié)省功率點(diǎn)?？梢怨?jié)省功率2 dB2 dB。通常稱這通常稱這2 dB2 dB為為編碼增益編碼增益。 上面兩種情況付

26、出的代上面兩種情況付出的代價(jià)是帶寬增大。價(jià)是帶寬增大。10-610-510-410-310-210-1PeCD信噪比 (dB)編碼后copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組33 傳輸速率和傳輸速率和E Eb b/n/n0 0的關(guān)系的關(guān)系對于給定的傳輸系統(tǒng)式對于給定的傳輸系統(tǒng)式中，中，R RB B為碼元速率。為碼元速率。若希望提高傳輸速率，若希望提高傳輸速率，由上式看出勢必使信噪由上式看出勢必使信噪比下降，誤碼率增大。比下降，誤碼率增大。假設(shè)系統(tǒng)原來工作在圖假設(shè)系統(tǒng)原來工作在圖中中C C點(diǎn)，提高速率后由點(diǎn)，提高速率后由C C點(diǎn)升到點(diǎn)升到E E點(diǎn)。但加用

27、糾點(diǎn)。但加用糾錯(cuò)編碼后，仍可將誤碼錯(cuò)編碼后，仍可將誤碼率降到率降到D D點(diǎn)。這時(shí)付出點(diǎn)。這時(shí)付出的代價(jià)仍是帶寬增大。的代價(jià)仍是帶寬增大。10-610-510-410-310-210-1編碼后PeCDE信噪比 (dB)copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組349-3 9-3 常用的簡單編碼常用的簡單編碼1 1、奇偶監(jiān)督碼：、奇偶監(jiān)督碼： k=n-1,r=1k=n-1,r=1的線性碼。的線性碼。特點(diǎn)：特點(diǎn)： 碼組中的碼組中的1 1個(gè)數(shù)是奇數(shù)（奇監(jiān)督碼）個(gè)數(shù)是奇數(shù)（奇監(jiān)督碼） 或偶數(shù)（偶監(jiān)督碼）。或偶數(shù)（偶監(jiān)督碼）。0021aaann偶監(jiān)督時(shí)，要滿足：偶

28、監(jiān)督時(shí)，要滿足：1021aaann奇監(jiān)督時(shí)，要滿足：奇監(jiān)督時(shí)，要滿足：兩者的校驗(yàn)?zāi)芰ο嗤?，均只能檢測出奇數(shù)個(gè)錯(cuò)誤。兩者的校驗(yàn)?zāi)芰ο嗤?，均只能檢測出奇數(shù)個(gè)錯(cuò)誤。R=k/n=n-1/n=1-1/n編碼效率：編碼效率：copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組35 碼長碼長5 5的偶監(jiān)督碼的偶監(jiān)督碼序序 碼碼 字字 序序 碼碼 字字號號 信息碼元信息碼元 監(jiān)督元監(jiān)督元 號號 信息碼元信息碼元 監(jiān)督元監(jiān)督元 a4 a3 a2 a1 a0 a4 a3 a2 a1 a0 0 0 0 0 0 0 8 1 0 0 0 1 1 0 0 0 1 1 9 1 0 0 1 0

29、 2 0 0 1 0 1 10 1 0 1 0 0 3 0 0 1 1 0 11 1 0 1 1 1 4 0 1 0 0 1 12 1 1 0 0 0 5 0 1 0 1 0 13 1 1 0 1 1 6 0 1 1 0 0 14 1 1 1 0 1 7 0 1 1 1 1 15 1 1 1 1 0 copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組36 偶監(jiān)督碼編碼器a4a3a2a1+信息組信息組a0a1a2a3a4碼字碼字12340aaaaacopyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組3701234bbbbbsb3b

30、0b1b2b4+接收碼組BS檢錯(cuò)信號有錯(cuò)無錯(cuò)10偶監(jiān)督碼的檢錯(cuò)偶監(jiān)督碼的檢錯(cuò)電路電路copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組38 例例9-29-2：一數(shù)據(jù)序列：一數(shù)據(jù)序列： 1110011100 1011110111 0110101101 1000110001 1010110101 試對其進(jìn)行（試對其進(jìn)行（6 6，5 5）偶校驗(yàn)編碼，寫出碼序列）偶校驗(yàn)編碼，寫出碼序列并分析其抗干擾能力并分析其抗干擾能力 copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組39一數(shù)據(jù)序列一數(shù)據(jù)序列： 1110011100 1011110

31、111 0110101101 1000110001 1010110101 試對其進(jìn)行（試對其進(jìn)行（6 6，5 5）偶校驗(yàn)編碼，寫出碼序列）偶校驗(yàn)編碼，寫出碼序列并分析其抗干擾能力并分析其抗干擾能力解：解： （6 6，5 5）, ,將數(shù)據(jù)序列每將數(shù)據(jù)序列每5 5碼元分組，碼元分組，123450aaaaaa并作：并作：的運(yùn)算的運(yùn)算可得出編碼數(shù)據(jù)序列：可得出編碼數(shù)據(jù)序列：11100111001110111101110001101011011110001100010010101101011 1 只能檢測出奇數(shù)個(gè)錯(cuò)誤，不能發(fā)現(xiàn)偶數(shù)個(gè)錯(cuò)誤，只能檢測出奇數(shù)個(gè)錯(cuò)誤，不能發(fā)現(xiàn)偶數(shù)個(gè)錯(cuò)誤，也不能糾錯(cuò)。也不能糾錯(cuò)。

32、 copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組402 2、水平垂直奇偶校驗(yàn)、水平垂直奇偶校驗(yàn)碼：碼： 又稱行列監(jiān)督碼或二維奇偶監(jiān)督碼。又稱行列監(jiān)督碼或二維奇偶監(jiān)督碼。特點(diǎn)：特點(diǎn)：對水平方向和垂直方向的碼元同時(shí)實(shí)施奇偶監(jiān)督。對水平方向和垂直方向的碼元同時(shí)實(shí)施奇偶監(jiān)督。 1 1 0 0 1 0 1 0 0 0 00 1 0 0 0 0 1 1 0 1 00 1 1 1 1 0 0 0 0 1 11 0 0 1 1 1 0 0 0 0 01 0 1 0 1 0 1 0 1 0 11 1 0 0 0 1 1 1 1 0 0行行列列監(jiān)監(jiān)督督碼碼copyright

33、信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組41適于監(jiān)測突發(fā)錯(cuò)誤：q逐行傳輸時(shí)，能檢測長度b M+1的突發(fā)錯(cuò)誤;q逐列傳輸時(shí),能檢測長度bL+1的突發(fā)錯(cuò)誤；q還能糾正一些僅在一行中的單個(gè)錯(cuò)誤。1 1 0 0 1 0 1 0 0 0 00 1 0 0 0 0 1 1 0 1 00 1 1 1 1 0 0 0 0 1 11 0 0 1 1 1 0 0 0 0 01 0 1 0 1 0 1 0 1 0 11 1 0 0 0 1 1 1 1 0 0L5，M10的行列監(jiān)督碼的行列監(jiān)督碼其中其中M為列數(shù)，為列數(shù)，L為行數(shù)為行數(shù)copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)

34、與技術(shù)學(xué)院通信原理教研組423 3、恒比碼：、恒比碼： 又稱等重碼或定又稱等重碼或定1 1碼。碼。特點(diǎn)：特點(diǎn)： 碼組中碼組中0 0，1 1的個(gè)數(shù)保持不變。的個(gè)數(shù)保持不變。 若碼長為若碼長為n n，碼重為，碼重為w w，則此碼的碼字個(gè)數(shù)，則此碼的碼字個(gè)數(shù) 為：為：C Cn nw w，禁用碼字個(gè)數(shù)為：，禁用碼字個(gè)數(shù)為：2 2n n - C- Cn nw w碼字的個(gè)數(shù)碼字的個(gè)數(shù)C C5 53 3 =10=10檢錯(cuò)能力較強(qiáng)，可檢出檢錯(cuò)能力較強(qiáng)，可檢出所有奇數(shù)所有奇數(shù)和和部分偶數(shù)部分偶數(shù)錯(cuò)誤。錯(cuò)誤。檢錯(cuò)能力較強(qiáng)，可檢出所有奇數(shù)和部分偶數(shù)錯(cuò)誤。檢錯(cuò)能力較強(qiáng)，可檢出所有奇數(shù)和部分偶數(shù)錯(cuò)誤。適用于傳輸電報(bào)或其

35、他鍵盤設(shè)備產(chǎn)生的字母或符適用于傳輸電報(bào)或其他鍵盤設(shè)備產(chǎn)生的字母或符號，但不適合信源發(fā)出的是二進(jìn)制隨機(jī)數(shù)字序列號，但不適合信源發(fā)出的是二進(jìn)制隨機(jī)數(shù)字序列的場合。的場合。copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組43數(shù)字?jǐn)?shù)字碼碼 字字0 01 12 23 34 45 56 67 78 89 901101011010101101011110011100110110101101101011010001110011110101101011110011100011100111010011100113:2 恒比碼恒比碼如：我國的電報(bào)，每如：我國的電報(bào)，每個(gè)漢字用四個(gè)

36、個(gè)漢字用四個(gè)1010進(jìn)制進(jìn)制數(shù)表示，每位數(shù)表示，每位1010進(jìn)制進(jìn)制數(shù)就采用數(shù)就采用 3 3：2 2 恒比恒比碼構(gòu)成的碼構(gòu)成的5 5位碼組來表位碼組來表示。示。碼字的個(gè)數(shù)碼字的個(gè)數(shù)C C5 53 3 =10=10copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組44作業(yè)：4 4、正反碼：、正反碼： 簡單的可糾錯(cuò)編碼，信元數(shù)等于監(jiān)督元數(shù)簡單的可糾錯(cuò)編碼，信元數(shù)等于監(jiān)督元數(shù)特點(diǎn)：特點(diǎn)： 信息位中，有奇數(shù)個(gè)信息位中，有奇數(shù)個(gè)1 1時(shí)，監(jiān)督位重復(fù)信息位；時(shí)，監(jiān)督位重復(fù)信息位； 信息位中，有偶數(shù)個(gè)信息位中，有偶數(shù)個(gè)1 1時(shí)，監(jiān)督位取信息位的反碼；時(shí)，監(jiān)督位取信息位的反碼

37、；可糾一位、檢測所有兩位錯(cuò)和部分兩位以上的錯(cuò)誤?？杉m一位、檢測所有兩位錯(cuò)和部分兩位以上的錯(cuò)誤。例：例：11001 1100111001 11001110011100110001 1000110001 100010111001110(n,k) (n,k) 其中其中k=n/2 k=n/2 編碼效率：編碼效率： R=k/n=1/2R=k/n=1/2copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組459.4 線性分組碼9.4.1 9.4.1 基本概念基本概念 可用可用線性方程組線性方程組表述碼的規(guī)律性的分表述碼的規(guī)律性的分組碼稱為線性分組碼。線性碼建立在代數(shù)組碼稱為

38、線性分組碼。線性碼建立在代數(shù)學(xué)群論基礎(chǔ)上，線性碼各許用碼的集合構(gòu)學(xué)群論基礎(chǔ)上，線性碼各許用碼的集合構(gòu)成代數(shù)學(xué)中的群，因此，又稱為群碼。成代數(shù)學(xué)中的群，因此，又稱為群碼。copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組46 1. 1. 含有全零碼字。含有全零碼字。 2.2.任意兩個(gè)許用碼字之和仍是一個(gè)許用碼字。任意兩個(gè)許用碼字之和仍是一個(gè)許用碼字。（封閉性封閉性） 3.3.最小碼距最小碼距d d0 0等于非零碼字的最小重量即等于非零碼字的最小重量即d d0 0=W=Wminmin （由此性質(zhì)可以方便的確定出線性分組碼的最（由此性質(zhì)可以方便的確定出線性分組碼的最

39、小碼距，進(jìn)而明確其糾錯(cuò)能力。）小碼距，進(jìn)而明確其糾錯(cuò)能力。） 在群中只有一種運(yùn)算，就是模在群中只有一種運(yùn)算，就是模2 2 和。和。線性分組碼的性質(zhì)線性分組碼的性質(zhì)：copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組47 奇偶監(jiān)督碼是一種最簡單的線性碼，我們曾經(jīng)作了奇偶監(jiān)督碼是一種最簡單的線性碼，我們曾經(jīng)作了偶校驗(yàn)的例子。偶校驗(yàn)的例子。0021aaann稱為稱為監(jiān)督監(jiān)督方程方程。接收時(shí)，為了檢測傳輸時(shí)是否有錯(cuò)，還要做同樣的計(jì)接收時(shí)，為了檢測傳輸時(shí)是否有錯(cuò)，還要做同樣的計(jì)算：算：01234bbbbbs有錯(cuò)無錯(cuò)10s這里這里S S稱為稱為校正子，校正子，上式也稱上式

40、也稱伴隨式伴隨式。奇偶監(jiān)督碼中只有一位監(jiān)督碼，因此只能表示有否錯(cuò)誤。奇偶監(jiān)督碼中只有一位監(jiān)督碼，因此只能表示有否錯(cuò)誤。copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組48當(dāng)監(jiān)督位增加，則監(jiān)督方程增加，校正子增加。當(dāng)監(jiān)督位增加，則監(jiān)督方程增加，校正子增加。r r位監(jiān)督碼除了用全位監(jiān)督碼除了用全“0 0”表示無錯(cuò)外，可表示表示無錯(cuò)外，可表示r21種錯(cuò)誤圖樣。種錯(cuò)誤圖樣。(n,k)碼可糾錯(cuò)的錯(cuò)誤圖樣數(shù)為：碼可糾錯(cuò)的錯(cuò)誤圖樣數(shù)為： 我們把接收碼組我們把接收碼組R R與發(fā)射碼組與發(fā)射碼組C C的差稱為的差稱為錯(cuò)誤圖樣錯(cuò)誤圖樣，用用E E表示：表示：E=C-RE=C-R

41、，或者，或者 C=R+EC=R+E (n,k)中，信息碼為中，信息碼為k位，可傳輸位，可傳輸M=2k種信息，當(dāng)種信息，當(dāng)增加增加r位的監(jiān)督位后，有位的監(jiān)督位后，有2n種狀態(tài)，但只取種狀態(tài)，但只取2k 種為許種為許用狀態(tài)，其他為禁用，用狀態(tài)，其他為禁用，(n,k)碼可檢測的錯(cuò)誤圖樣數(shù)為碼可檢測的錯(cuò)誤圖樣數(shù)為 2n-2k2n-k -1=2r-1不可檢測的錯(cuò)誤圖樣數(shù)為不可檢測的錯(cuò)誤圖樣數(shù)為2k-1copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組491nc2nctnctiinc12 n-k-1 + + =對于能糾正對于能糾正 t 個(gè)錯(cuò)誤的線性分組碼個(gè)錯(cuò)誤的線性分組碼

42、(n,k)應(yīng)滿足：應(yīng)滿足：inc是錯(cuò)是錯(cuò) i 位的個(gè)數(shù)。位的個(gè)數(shù)。如果滿足如果滿足 ，則有可能構(gòu)造出糾正一位或一位，則有可能構(gòu)造出糾正一位或一位以上的線性碼以上的線性碼。i=1時(shí)，時(shí)，1nnc 即對于碼組長度為即對于碼組長度為n n，信息碼元，信息碼元k k位，監(jiān)督元位，監(jiān)督元r r，nr12copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組50 思考：思考： 例例9-39-3設(shè)設(shè)(n(n，k)k)中，中，k=4k=4，要求能糾一位錯(cuò)，取，要求能糾一位錯(cuò)，取r=r=？copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組51 解：

43、解： (n(n，k)k)線性分組碼，線性分組碼，k=4k=4，要求能糾一位錯(cuò)，要求能糾一位錯(cuò)，現(xiàn)取現(xiàn)取r=3r=3，可指示，可指示2 23 3-1=7-1=7種錯(cuò)誤，種錯(cuò)誤， 碼長碼長n=4+3=7n=4+3=7，表示為：表示為： C=CC=C6 6C C5 5C C4 4C C3 3C C2 2C C1 1C C0 0 其中其中C C6 6C C5 5C C4 4C C3 3為信息碼元，為信息碼元，C C2 2C C1 1C C0 0為監(jiān)督元為監(jiān)督元由由r=3r=3，可有三個(gè)監(jiān)督方程和校正子，設(shè)為，可有三個(gè)監(jiān)督方程和校正子，設(shè)為s s1 1s s2 2s s3 321rn 恰好滿足恰好滿足

44、, ,故可糾一位錯(cuò)。故可糾一位錯(cuò)。copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組52設(shè)設(shè)s1s2s3三位校正子與誤三位校正子與誤碼位置的對應(yīng)關(guān)系為：碼位置的對應(yīng)關(guān)系為：0 0 00 0 00 0 10 0 10 1 00 1 01 0 01 0 00 1 10 1 11 0 11 0 11 1 01 1 01 1 11 1 1誤碼位置誤碼位置無錯(cuò)無錯(cuò) C C0 0 C C1 1 C C2 2 C C3 3 C C4 4 C C5 5 C C6 6S S1 1 S S2 2 S S3 3 于是監(jiān)督碼元于是監(jiān)督碼元C C2 2C C1 1C C0 0應(yīng)應(yīng)由以下

45、由以下監(jiān)督方程監(jiān)督方程決定。決定。C C2 2=C=C6 6+C+C5 5+C+C4 4C C1 1=C=C6 6+C+C5 5+C+C3 3C C0 0=C=C6 6+C+C4 4+C+C3 3監(jiān)督元與信息元之間的線性方程組監(jiān)督元與信息元之間的線性方程組s1=C2+C6+C5+C4=0s2=C1+C6+C5+C3=0s3=C0+C6+C4+C3=0copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組53于是得到于是得到(7(7，4)4)線性分組碼如下：線性分組碼如下： 序序 碼碼 字字 號號 信息元信息元 監(jiān)督元監(jiān)督元 8 1 0 0 0 1 1 18 1 0

46、 0 0 1 1 1 9 1 0 0 1 1 0 0 9 1 0 0 1 1 0 0 10 1 0 1 0 0 1 0 10 1 0 1 0 0 1 0 11 1 0 1 1 0 0 1 11 1 0 1 1 0 0 1 12 1 1 0 0 0 0 1 12 1 1 0 0 0 0 1 13 1 1 0 1 0 1 0 13 1 1 0 1 0 1 0 14 1 1 1 0 1 0 0 14 1 1 1 0 1 0 0 15 1 1 1 1 1 1 1 15 1 1 1 1 1 1 1 序序 碼碼 字字 號號 信息元信息元 監(jiān)督元監(jiān)督元 0 0 0 0 0 0 0 00 0 0 0 0 0

47、0 0 1 0 0 0 1 0 1 1 1 0 0 0 1 0 1 1 2 0 0 1 0 1 0 1 2 0 0 1 0 1 0 1 3 0 0 1 1 1 1 0 3 0 0 1 1 1 1 0 4 0 1 0 0 1 1 0 4 0 1 0 0 1 1 0 5 0 1 0 1 1 0 1 5 0 1 0 1 1 0 1 6 0 1 1 0 0 1 1 6 0 1 1 0 0 1 1 7 0 1 1 1 0 0 0 7 0 1 1 1 0 0 0copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組549.4.2 監(jiān)督矩陣0001001101010101100

48、101110123456CCCCCCC 將前面的監(jiān)督方程改寫成矩陣的形式，將前面的監(jiān)督方程改寫成矩陣的形式， C=CC=C6 6C C5 5C C4 4C C3 3C C2 2C C1 1C C0 0 可看成為編碼矢量，于是有：可看成為編碼矢量，于是有：記做：記做：TTHC00TCH監(jiān)督方程監(jiān)督方程copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組55H - H - 監(jiān)督矩陣監(jiān)督矩陣110110110111P 不滿足以上關(guān)系的為非典型矩陣，典型矩陣和不滿足以上關(guān)系的為非典型矩陣，典型矩陣和非典型矩陣之間可以轉(zhuǎn)換。非典型矩陣之間可以轉(zhuǎn)換。2/ 2/ H H矩陣各

49、行是線性無關(guān)的。矩陣各行是線性無關(guān)的。行數(shù)行數(shù)-監(jiān)督元的個(gè)數(shù)監(jiān)督元的個(gè)數(shù)r r列數(shù)列數(shù)-碼組長度碼組長度 n nI Ir r為為r r階單位陣階單位陣1/ 1/ 當(dāng)有當(dāng)有H=P IrH=P Ir時(shí)稱為典型矩陣，時(shí)稱為典型矩陣，100I010001copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組56利用監(jiān)督方程，我們可以對線性碼的利用監(jiān)督方程，我們可以對線性碼的封閉性加以證明封閉性加以證明 即H陣與編碼碼字的轉(zhuǎn)置乘積為0，可用來作為判斷接收碼組是否錯(cuò)的依據(jù)。,/3TTOCHcopyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組57

50、 設(shè)監(jiān)督方程設(shè)監(jiān)督方程A A1 1、A A2 2均為線性碼集合中的許用碼均為線性碼集合中的許用碼組，因此有組，因此有 令兩許用碼組相加令兩許用碼組相加 A A1 1+A+A2 2帶入監(jiān)督方程，有：帶入監(jiān)督方程，有：02THA01THA因此，因此， A A1 1+A+A2 2亦為許用碼組。亦為許用碼組。0)(2121TTTHAHAHAAcopyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組589.4.3 生成矩陣 當(dāng)給出信息組后，如何方便迅速地求出整個(gè)當(dāng)給出信息組后，如何方便迅速地求出整個(gè)編碼碼組，即如何生成編碼矢量編碼碼組，即如何生成編碼矢量？C C2 2=C=C

51、6 6+C+C5 5+C+C4 4C C1 1=C=C6 6+C+C5 5+C+C3 3C C0 0=C=C6 6+C+C4 4+C+C3 3由監(jiān)督元與信息元之間的關(guān)系：由監(jiān)督元與信息元之間的關(guān)系：3456012110110110111CCCCCCCTPCCCCCCC3456012或者可以寫成：或者可以寫成：copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組59QCCCCCCC3456012令令QPT則有：則有：給給Q Q的左邊，加一個(gè)的左邊，加一個(gè)k kk k階的單位矩陣，則構(gòu)成：階的單位矩陣，則構(gòu)成：G=IG=Ik k Q Q稱為稱為生成矩陣生成矩陣，且為

52、典型形式。典型，且為典型形式。典型G G矩陣矩陣行數(shù)行數(shù)- - 信息元的個(gè)數(shù)信息元的個(gè)數(shù)k k列數(shù)列數(shù)- - 碼組長度碼組長度 n n每行本身就是一個(gè)許用碼組每行本身就是一個(gè)許用碼組TTHG00TGH于是有：于是有：矩陣和非典型矩陣之間可以轉(zhuǎn)換。矩陣和非典型矩陣之間可以轉(zhuǎn)換。copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組60碼字的前面碼字的前面 k k 位為信息位，后面位為信息位，后面 位為位為監(jiān)督位監(jiān)督位一般情況，定義線性分組碼的碼字有如下形式：一般情況，定義線性分組碼的碼字有如下形式：信息碼元信息碼元監(jiān)督位監(jiān)督位信息信息位位編碼編碼 碼字碼字kkn k

53、n系統(tǒng)形式的線性分組碼系統(tǒng)形式的線性分組碼1210()nnn kn kCccccc 120()kkMmmm02121mmmccckkknnnkn 0M G編碼編碼 kkn copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組61設(shè)信息組1000111010011000101010001011G生成矩陣生成矩陣編碼碼組編碼碼組CM G6543Mcccccopyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組62. )2階矩陣，各行線性無關(guān)為nkG1）由G和信息組即可產(chǎn)生全部碼字.111110 101011TQP通過典型生成矩陣產(chǎn)生的一定

54、是系統(tǒng)碼。通過典型生成矩陣產(chǎn)生的一定是系統(tǒng)碼。k10000100I00100001G稱為典型生成矩陣。3) kGI Qcopyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組63011010101001110100G （1）試確定試確定(n,k)(n,k)，并求，并求H H ； (2) (2) 寫出監(jiān)督元與信息元的關(guān)系式及寫出監(jiān)督元與信息元的關(guān)系式及 該（該（n,kn,k）碼的全部碼字；）碼的全部碼字； (3) (3) 確定最小碼距及檢錯(cuò)能力。確定最小碼距及檢錯(cuò)能力。例9-4設(shè)已知設(shè)已知copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教

55、研組64110100011010101001解：求H，需確定P，QPT應(yīng)將已知的那個(gè)G轉(zhuǎn)換成典型形式，求出Q，再利用 求出G。011010101001110100G011010110100101001H=P Ir=100101010110001011rTIQcopyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組65 (2) 0THC5432101101000110100101001cccccc設(shè)C= 012345cccccc于是有：110100011010101001345cccGMC監(jiān)督元與信息元的關(guān)系式監(jiān)督元與信息元的關(guān)系式copyright 信息科學(xué)與技術(shù)學(xué)

56、院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組66用三位二進(jìn)制數(shù)的所有用三位二進(jìn)制數(shù)的所有8種狀態(tài)帶入，可得到所有碼字如右表種狀態(tài)帶入，可得到所有碼字如右表。 序號 碼 字 0 0 0 0 0 0 0 1 0 0 1 0 1 1 2 0 1 0 1 1 0 3 0 1 1 1 0 1 4 1 0 0 1 0 1 5 1 0 1 1 1 0 6 1 1 0 0 1 1 7 1 1 1 0 0 0(3) 確定最小碼距及確定最小碼距及 檢錯(cuò)能力檢錯(cuò)能力所以有：所以有：d d0 0=3=3可用于檢兩位錯(cuò)或可用于檢兩位錯(cuò)或糾一位錯(cuò)。糾一位錯(cuò)。利用性質(zhì)知：最小利用性質(zhì)知：最小碼距碼距d0 0等于非零碼等

57、于非零碼字的最小重量即字的最小重量即d0 0=wminmincopyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組679.4.4 校正子S 發(fā)送端經(jīng)過編碼后給出：發(fā)送端經(jīng)過編碼后給出：0121cccccnn接收端收到的碼組為：接收端收到的碼組為：0121rrrrRnn兩者的差記為：兩者的差記為：0121eeeeCREnniiiiicrcre10表示第表示第 i 位無錯(cuò)位無錯(cuò)表示第表示第 i 位有錯(cuò)位有錯(cuò)E稱為錯(cuò)誤圖樣。共有稱為錯(cuò)誤圖樣。共有2n個(gè)錯(cuò)誤圖樣。個(gè)錯(cuò)誤圖樣。當(dāng)當(dāng) E為全零錯(cuò)誤圖樣時(shí)，為全零錯(cuò)誤圖樣時(shí)，R=C 沒有傳輸錯(cuò)誤沒有傳輸錯(cuò)誤;copyright

58、信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組68TTHR0可利用可利用E檢出或糾正錯(cuò)誤；檢出或糾正錯(cuò)誤；TTHR0傳輸中的錯(cuò)誤超出了可糾錯(cuò)的范圍。傳輸中的錯(cuò)誤超出了可糾錯(cuò)的范圍。可能有可能有兩種兩種情況：情況：(n,k)可檢測的錯(cuò)誤圖樣數(shù)為可檢測的錯(cuò)誤圖樣數(shù)為 2n - 2k(n,k)可糾錯(cuò)的錯(cuò)誤圖樣數(shù)為可糾錯(cuò)的錯(cuò)誤圖樣數(shù)為 2n-k - 1這時(shí)的錯(cuò)誤圖樣稱為不可檢測的錯(cuò)誤圖樣這時(shí)的錯(cuò)誤圖樣稱為不可檢測的錯(cuò)誤圖樣一般來講，一般來講，E=0， 則則R=C，可滿足監(jiān)督方程，可滿足監(jiān)督方程E0，則，則RC，不滿足監(jiān)督方程，不滿足監(jiān)督方程檢錯(cuò)：當(dāng)檢錯(cuò)：當(dāng)S=0時(shí)，認(rèn)為時(shí)，認(rèn)為E=0

59、，當(dāng)，當(dāng)S 0時(shí)，認(rèn)為時(shí)，認(rèn)為E 0,校正子校正子 S 的計(jì)算的計(jì)算TTTTTEHEHCHHECRHS)(即校正子只與錯(cuò)誤圖樣即校正子只與錯(cuò)誤圖樣E有關(guān)。有關(guān)。copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組69標(biāo)準(zhǔn)陣列表標(biāo)準(zhǔn)陣列表kknknknknkkkkCECECEECECECEECECECEECCCCDDDD2232222233323322322222321232101E排列方法排列方法第一個(gè)元素。排在零碼字個(gè)碼字排在第一行，全碼的）（02),(11Cknk陪陪集集陪陪集集首首copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原

60、理教研組70kknknknknkkkkCECECEECECECEECECECEECCCCDDDD2232222233323322322222321232101E陪陪集集陪陪集集首首下面構(gòu)成第二行。放在下面，并將放在重作為錯(cuò)誤圖樣重中選擇重量較小的個(gè)剩下的）（iiknCCECEnn212222且希望重量盡可能小。重是前面未出現(xiàn)過的，每行第一個(gè)重。有繼續(xù)以上過程，用完所）（nn3copyright 信息科學(xué)與技術(shù)學(xué)院通信原理教研組信息科學(xué)與技術(shù)學(xué)院通信原理教研組71構(gòu)造標(biāo)準(zhǔn)陣列的一般方法如下：構(gòu)造標(biāo)準(zhǔn)陣列的一般方法如下：1）用概率譯碼確定各伴隨式）用概率譯碼確定各伴隨式S對應(yīng)的差錯(cuò)圖案對應(yīng)的差錯(cuò)圖