通信原理--第9章 差錯控制編碼

1、1歡迎各位同學(xué)光臨歡迎各位同學(xué)光臨通信原理通信原理課程課程禹思敏禹思敏2第第9章章 差錯控制編碼差錯控制編碼信道編碼信道編碼, 糾錯碼糾錯碼,差錯控制編碼差錯控制編碼提高了可靠性提高了可靠性, 但降低了有效性但降低了有效性39.1 概述概述9.1.1 差錯控制編碼的概念差錯控制編碼的概念是一種有效的方法信道編碼技術(shù)降低誤碼率提高信噪比加大發(fā)射功率提高可靠性的方法提高可靠性加入的碼元稱監(jiān)督碼元按一定規(guī)則加入多余度信道編碼提高有效性去掉信源的多余度信源編碼編碼,),(:,:49.1.2 差錯控制方式差錯控制方式 1、檢錯重發(fā)式：發(fā)送端發(fā)出能檢錯的碼，接收端收、檢錯重發(fā)式：發(fā)送端發(fā)出能檢錯的碼，接收

2、端收到后，首先進行檢測，當發(fā)現(xiàn)錯誤時到后，首先進行檢測，當發(fā)現(xiàn)錯誤時,通知發(fā)送端重發(fā)通知發(fā)送端重發(fā)一次，直到正確。如奇偶校驗等。一次，直到正確。如奇偶校驗等。特點：譯碼簡單，實時性差，雙向傳輸。特點：譯碼簡單，實時性差，雙向傳輸。 2、前向糾錯：發(fā)送能自動糾錯的碼、前向糾錯：發(fā)送能自動糾錯的碼,在接收端能自動在接收端能自動糾錯。特點：實時性好，單向傳輸。糾錯。特點：實時性好，單向傳輸。 3、混合方式：上述兩者的組合。在接收端若能自動、混合方式：上述兩者的組合。在接收端若能自動糾正，則不必重發(fā)，若超出自動糾錯的范圍，則通知糾正，則不必重發(fā)，若超出自動糾錯的范圍，則通知對方重發(fā)，取各自的優(yōu)點。對方

3、重發(fā)，取各自的優(yōu)點。59.1.3 糾錯碼的分類糾錯碼的分類 1、線性碼：監(jiān)督碼與信息碼之間的關(guān)系是線性的、線性碼：監(jiān)督碼與信息碼之間的關(guān)系是線性的 2、非線性碼：監(jiān)督碼與信息碼間的關(guān)系是非線性的、非線性碼：監(jiān)督碼與信息碼間的關(guān)系是非線性的 3、分組碼：屬于線性碼的一種、分組碼：屬于線性碼的一種 4、循環(huán)碼：屬于線性碼的一種、循環(huán)碼：屬于線性碼的一種 5、卷積碼：屬于非線性碼的一種、卷積碼：屬于非線性碼的一種 6、其它類型的糾錯碼、其它類型的糾錯碼69.1.4 糾錯碼的基本原理糾錯碼的基本原理一、分組碼：把信息碼按一、分組碼：把信息碼按 k 個碼元一組，并按一定的規(guī)個碼元一組，并按一定的規(guī)律編碼

4、，產(chǎn)生律編碼，產(chǎn)生 r 個監(jiān)督碼元，形成長度為個監(jiān)督碼元，形成長度為 n=k+r 組碼，組碼，稱為碼字，用稱為碼字，用(n,k)表示，其特點是：表示，其特點是： 1、共有、共有2k 個不同的碼字，稱為許用碼組；個不同的碼字，稱為許用碼組； 2、共有、共有2n-2k個碼字未用，稱為禁用碼組。個碼字未用，稱為禁用碼組。 正是存在禁用碼組，使得正是存在禁用碼組，使得(n,k)碼具有糾錯能力，禁碼具有糾錯能力，禁用碼越多，糾錯能力越強。用碼越多，糾錯能力越強。7 2、漢明距離、漢明距離d0的概念的概念:（1）兩個碼字）兩個碼字A,B之間的距離定義為之間的距離定義為:3),(: 0111 1011110

5、0:),(,),(nnnnbaBAdBAmBAdmBAbaBAd得例則其距離為個碼元不同之間有即若兩個碼字81,)(,)3(12,)2(1,) 1 (:,)3(1110 101 010 000 :,)2(00000etdteettdtededdDCBA則要求隨機錯誤個同時檢測個糾則要求個隨機錯誤糾則要求個隨機錯誤檢測有如下結(jié)論可以證明能力越強越大距離有關(guān)檢錯與糾錯能力與漢明檢錯與糾錯能力如離最小距離定義為漢明距則碼字之間的的情況設(shè)一個集中有多個碼字9., 01, 10.,10 ) 1 , 1 (),( ,) 1 (:. 5/)(. 4無任何糾檢錯能力沒有監(jiān)督碼時因此碼組出錯后的碼組仍為許用或原

6、因是無法糾正故出錯時由于沒有禁用碼組雨晴沒有監(jiān)督碼時只有信息碼雨和晴用二進碼表示例題編碼效率有效性的一種指標編碼效率knnkR10可檢出一個隨機錯誤錯誤可檢出這個故在接收端組范圍由于它們不屬于許用碼或收到的碼組變?yōu)楫a(chǎn)生了錯誤在傳輸過程中許用碼組的漢明距離雨晴禁用碼組許用碼組種位編碼共有后監(jiān)督碼加上一位重復(fù)碼,),0 , 1 () 1 , 0(,2:10110100 11,10,01,00:42) 1 , 2(),( ,)()2(001daakn11)6(110,101,100,011,010,001:3111000: )2(111,110,101,100,011,010,001,000:) 1

7、 , 3(),( ,)3(0012012個共禁用碼組許用碼組的漢明距離為雨晴個共許用碼組全部碼字為加上兩位監(jiān)督碼元daaaaaakn1230d000111001010100011101110由(000)錯一位的結(jié)果由(111)錯一位的結(jié)果由上圖可知,若傳輸過程中錯一位,能夠?qū)⑵浼m正139.2 常用的幾種簡單的分組碼常用的幾種簡單的分組碼9.2.1 奇偶監(jiān)督碼奇偶監(jiān)督碼一、二進制運算規(guī)則一、二進制運算規(guī)則對于二進制的按位運算來說對于二進制的按位運算來說, 加法加法, 減法減法, 異或異或三種運算的結(jié)果相同三種運算的結(jié)果相同,這三個符號可視為相同即, , 011111100000011001100

8、1100101111110000000AAAAAAAAAAAAAAAAAAAA141210121001210121,0,1. 1,) 1,(),(.aaaaaaaaaaaaaaaaAnnnnnnnnnn 之間的關(guān)系為與信息碼得監(jiān)督碼元有的個數(shù)為偶數(shù)滿足偶監(jiān)督碼設(shè)碼字碼奇偶監(jiān)督碼奇偶校驗二監(jiān)督碼信息碼15a7a6a5a4a3a2a1a7a6a5a4a3a2a1a0信道信道a7a6a5a4a3a2a1a0輸出輸出S應(yīng)答信號應(yīng)答信號校正子電路校正子電路發(fā)送端發(fā)送端接收端接收端16只能用于檢錯重發(fā)方式不能糾錯只能檢錯但無法檢測偶數(shù)個錯個錯奇偶監(jiān)督碼可檢測奇數(shù)小結(jié)需要重發(fā)有錯若不要重發(fā)無錯若端作為應(yīng)答信

9、號通知發(fā)送利用有錯無錯滿足又稱為校正子應(yīng)答信號在糾錯碼中)3(;,)2(;,) 1 (:., 1, 0:10:,01234567SSSaaaaaaaaSS179.2.2 行列監(jiān)督碼行列監(jiān)督碼 對水平方向的碼元和垂直方向的碼元同時實施對水平方向的碼元和垂直方向的碼元同時實施奇偶監(jiān)督，在一般情況下有：奇偶監(jiān)督，在一般情況下有： LM 個信息碼元加個信息碼元加L+M+1個監(jiān)督元，組成個監(jiān)督元，組成LM+(L+M+1), LM行行列監(jiān)督碼的一個碼字（列監(jiān)督碼的一個碼字（L+1行行,M+1列）。列）。 現(xiàn)以現(xiàn)以(n,k)=(66,50)為例加以說明。為例加以說明。18110010100000100001

10、101001111000011100111000001010101010111000111100水平方向偶校驗垂直方向偶校驗19有關(guān)差錯的分類有關(guān)差錯的分類: 1、隨機差錯：、隨機差錯：由加性高斯噪聲等引起，特點：一般只錯由加性高斯噪聲等引起，特點：一般只錯一位的可能最大，但哪位出錯則是隨機的，經(jīng)計算得：一位的可能最大，但哪位出錯則是隨機的，經(jīng)計算得： （1）錯一位的概率為：）錯一位的概率為：Pe(1) = 710-3 （2）錯二位的概率為：）錯二位的概率為：Pe(2) = 2.110-5 （3）錯三位的概率為：）錯三位的概率為：Pe(3) = 3.510-8 由上述結(jié)果可見，出一位錯的可能性

11、最大。由上述結(jié)果可見，出一位錯的可能性最大。 2、突發(fā)差錯：、突發(fā)差錯：連續(xù)的一串碼元出現(xiàn)錯誤，出錯的長度稱連續(xù)的一串碼元出現(xiàn)錯誤，出錯的長度稱為突發(fā)長度。如磁盤上磁粉失落或劃傷后，對其讀寫會出為突發(fā)長度。如磁盤上磁粉失落或劃傷后，對其讀寫會出突發(fā)錯。突發(fā)錯。209.3 線性分組碼線性分組碼.,)3(.,)2(,) 1 (:100:,012101210121似之處譯碼電路與偶校驗有類線性分組碼的編碼既可檢錯又可糾錯較多碼元而線性分組碼由于監(jiān)督不能糾錯偶校驗只能檢錯督碼元線性分組碼則有多個監(jiān)元偶校驗只有一個監(jiān)督碼別與偶校驗碼的聯(lián)系及區(qū)本節(jié)討論的線性分組碼分組碼中來上述方法可推廣到線性表示有錯表示

12、無錯校正子系之間滿足如下的編碼關(guān)與監(jiān)督碼信息碼在偶校驗碼中aaaaSaaaaaaaannnnnn219.3.1 基本概念基本概念個禁用碼字為個許用碼字為許用碼組與禁用碼組設(shè)碼字為點來說明線性分組碼的特分組碼為例現(xiàn)以監(jiān)督碼元信息碼元11222162:) 1 (:)4 , 7(4743460356145620123456aaaaaaaaaaaaaaaaaaaA a6 a5 a4 a3 a2 a1 a0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 1 0 0 1 1 1 1 0 0 1 0 0 1 1 0 0 1 0 1 1 0 1 0 1 1 0 0 1 1 0

13、 1 1 1 0 0 0 1 0 0 0 1 1 1 1 0 0 1 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 0 1 1 1 0 0 0 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 1 1 1 1 1 1 122)( 112:)3(3, 3 ,0, :)4 , 7()2(00能糾一位錯糾錯能力故得最小碼重為碼外除全由于該碼具有封閉性碼的漢明距離的求法ttdd239.3.2 監(jiān)督矩陣監(jiān)督矩陣H和生成矩陣和生成矩陣G（1）監(jiān)督矩陣）監(jiān)督矩陣H及其物理意義及其物理意義 )( | 001 1011010 1101100 1110,:0 0 00001011001

14、1101010111010000001234560123456034613562456346035614562標準監(jiān)督矩陣可表為為監(jiān)督矩陣為碼字式中IPHHaaaaaaaAAHHAHAaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaTTTTT單位矩陣單位矩陣線性分組碼的編碼規(guī)則！線性分組碼的編碼規(guī)則！24監(jiān)督矩陣監(jiān)督矩陣H的物理意義：的物理意義： 1）在發(fā)送端，可利用監(jiān)督）在發(fā)送端，可利用監(jiān)督 H來進行編碼，因此來進行編碼，因此 H 實際上是一種編碼規(guī)則。利用這種編碼規(guī)實際上是一種編碼規(guī)則。利用這種編碼規(guī) 則，使得則，使得H和碼字和碼字A滿足滿足AHT=0或或HAT=0 2）在接

15、收端，可利用）在接收端，可利用 H，對經(jīng)信道傳送過來的，對經(jīng)信道傳送過來的 碼字碼字 A進行監(jiān)督或檢測，判斷其正確性，若進行監(jiān)督或檢測，判斷其正確性，若 正確，必滿足正確，必滿足AHT=0或或HAT=0，若不正確，若不正確， 則則AHT不為不為0或或HAT不為不為0。 3）下文中將要講述的校正子正是根據(jù)這一原理）下文中將要講述的校正子正是根據(jù)這一原理 來判斷接收碼字來判斷接收碼字 A的正確性并進行糾錯的。的正確性并進行糾錯的。25GaaaaAaaaaGAaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaTT345634563456012345

16、63460356145623344556634603561456233445566:1011110111100001001001001000 :轉(zhuǎn)置即如下形式前面的式子還可表示為物理意義：由生物理意義：由生成矩陣成矩陣G 和信息和信息碼產(chǎn)生一個碼字碼產(chǎn)生一個碼字（2）生成矩陣）生成矩陣G及其物理意義及其物理意義增加的增加的原來的原來的26.,)(|001 1011010 1101100 1110)(|011 0001101 0010110 0100111 1000HGGHPQQPGHIPHQIGTT求或由求可由由此可見或的關(guān)系為和生成矩陣監(jiān)督矩陣顯然標準監(jiān)督矩陣矩陣為由前面得到的標準監(jiān)督標準生

17、成矩陣（3）生成矩陣）生成矩陣G和監(jiān)督矩陣和監(jiān)督矩陣H的關(guān)系的關(guān)系279.3.3 一種編碼電路介紹：根據(jù)一種編碼電路介紹：根據(jù) 得編碼電路：得編碼電路：6a5a4a3a2a1a0a346035614562aaaaaaaaaaaa28例題：例題：設(shè)（設(shè)（7,3）線性分組碼的監(jiān)督矩陣為）線性分組碼的監(jiān)督矩陣為 1 0 0 0 1 1 00 1 0 0 0 1 10 0 1 0 1 1 10 0 1 1 0 1 0 0123456Haaaaaaa 監(jiān)督碼元信息碼元試求：試求：（1）監(jiān)督碼元與信息碼元之間的關(guān)系表達式；）監(jiān)督碼元與信息碼元之間的關(guān)系表達式；（2）列出所有的許用碼組）列出所有的許用碼組（

18、必須自己完成）（必須自己完成）；（3）求漢明距離；能糾幾位錯？）求漢明距離；能糾幾位錯？（自己完成）（自己完成）；（4）畫出編碼器電路。）畫出編碼器電路。需要用初等變換將其需要用初等變換將其化成標準單位矩陣化成標準單位矩陣29解：解：由于由于H矩陣不是標準矩陣矩陣不是標準矩陣,需經(jīng)初等變換后變換成需經(jīng)初等變換后變換成 標準矩陣。得變換后的標準矩陣為：標準矩陣。得變換后的標準矩陣為：1 0 0 0 1 1 00 1 0 0 0 1 10 0 1 0 1 1 10 0 0 1 1 0 1H從而得監(jiān)督碼元與信息碼元之間的關(guān)系表達式為從而得監(jiān)督碼元與信息碼元之間的關(guān)系表達式為 450561456246

19、3aaaaaaaaaaaaa30進一步可畫出編碼器電路如下：進一步可畫出編碼器電路如下：6a5a4a3a2a1a0a319.3.4 S校正子（伴隨式）校正子（伴隨式）時當時當并且有其中或即也稱為誤差矢量誤圖樣定義收發(fā)碼字之差為錯接收碼字變?yōu)榭赡軙l(fā)生錯誤由于傳輸過程中設(shè)發(fā)送碼字為工作原理來討論其校正子的基本為例我們?nèi)匀灰跃€性分組碼iiiiiiinnnnnnabababeeeeeEEABABEEbbbbBaaaaAaaaaaaaaaaaa10,:,., 01210121012134603561456232., 0, 0, 0, 0:0:0:. 對接收的碼進行糾錯利用這一關(guān)系對應(yīng)關(guān)系之間有確定的樣

20、正子與錯誤圖樣由上式知表明有錯若不為表明無錯若等于故有由發(fā)送端的編碼規(guī)則知校正子為則令接收端的若發(fā)送端的編碼規(guī)則為發(fā)送端編碼規(guī)則應(yīng)相同注意接收端解碼規(guī)則與ESEEEHSAHEHAHHEABHSSAHSTTTTTTT33:710317,000000., )4 , 7(034601356124562034613562456034613562456346035614562346035614562的結(jié)果如下表可得書中由上式法來說明校正子的產(chǎn)生方為例碼現(xiàn)以以Peeeeseeeeseeeeseeeeeeeeeeeeaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa34., 0, 0,

21、)2(., 0, 0,) 1 (:01201234560120123456034601356124562需校正表明傳輸不正確則若誤差不需校正表明傳輸正確則若誤差說明校正子公式sssseeeeeeeesssseeeeeeeeeeeeseeeeseeees35.,128) 3(2:可代表不同的錯誤圖樣即校正子的不同輸出種有錯以及無錯種形式分別表示碼字校正子的由此表可知rrArS369.3.5 一種（一種（7,4）碼（又稱為漢明碼）的譯碼電路）碼（又稱為漢明碼）的譯碼電路1、復(fù)習(xí)數(shù)字電路中的、復(fù)習(xí)數(shù)字電路中的3-8譯碼器譯碼器 3-8譯碼器有三個輸入，八個輸出，其邏輯電路圖譯碼器有三個輸入，八個輸出

22、，其邏輯電路圖為為6Z3-83-8譯譯碼碼器器0S1S2S5Z4Z7Z3Z2Z1Z0Z372、根據(jù)、根據(jù)3-8譯碼器的工作原理，得其真值表為：譯碼器的工作原理，得其真值表為：382. 進一步得譯碼電路為（只需校正信息碼進一步得譯碼電路為（只需校正信息碼b3b4b5b6）6b5b4b3b2b1b0b6Z3-83-8譯譯碼碼器器0S1S2S5Z4Z7Z3Z2Z1Z0Z或或門門出錯出錯指示指示6b5b4b3b糾錯電路糾錯電路異或運算異或運算399.4 循環(huán)碼循環(huán)碼循環(huán)碼的循環(huán)特性：循環(huán)碼的循環(huán)特性：（1）是線性碼。）是線性碼。（2）具有循環(huán)性。即碼組中的任一碼字循環(huán)）具有循環(huán)性。即碼組中的任一碼字循

23、環(huán) 移位所得碼字仍是該碼組中的一個碼字。移位所得碼字仍是該碼組中的一個碼字。（3）封閉性。對任意二個碼字的（異或）運）封閉性。對任意二個碼字的（異或）運 算所得碼字仍屬于該碼組中的一個碼字。算所得碼字仍屬于該碼組中的一個碼字。（4）(n,k)循環(huán)碼的碼字可用多項式表示：循環(huán)碼的碼字可用多項式表示：1)(:)(:4)(4652364012211xxxxAxxxxxAaxaxaxaxAnnnn同理有的碼多項式可表為如右表中碼字40本節(jié)的主要內(nèi)容：本節(jié)的主要內(nèi)容：一、在線性分組碼中，我們求出了生成矩陣一、在線性分組碼中，我們求出了生成矩陣 G 和監(jiān)督矩陣和監(jiān)督矩陣 H。同樣，我們在這里首。同樣，我們

24、在這里首 先求循環(huán)碼的生成矩陣先求循環(huán)碼的生成矩陣 G和監(jiān)督矩陣和監(jiān)督矩陣 H二、循環(huán)碼的編碼規(guī)則與編碼方法二、循環(huán)碼的編碼規(guī)則與編碼方法三、循環(huán)碼的編碼電路三、循環(huán)碼的編碼電路四、循環(huán)碼的譯碼以及譯碼電路的組成四、循環(huán)碼的譯碼以及譯碼電路的組成41.)(,)(:)(. 1)()(1 . 4 . 9為該碼的生成多項式則稱的倍式項式都是某個多項式若一種碼的所有碼字多的定義生成多項式及生成矩陣生成多項式xgxgxgxGxg由此可見，生成多項式對于循環(huán)碼來說十分重要！由此可見，生成多項式對于循環(huán)碼來說十分重要！42的一個因式生成多項式是督碼元位數(shù)為監(jiān)為信息碼的位數(shù)碼長為次多項式的是常數(shù)項為生成多項式

25、多項式就是生成多項式次數(shù)最低的碼外除全在循環(huán)碼組中可以證明的獲取及性質(zhì)生成多項式1)3( ,: ),(1)()2()( ,0,) 1 ()(. 2nxrkrknknrxgxgxg（非常重要?。ǚ浅Ｖ匾。?310) 1 , 2, 1()(1)()()()()()( : )(. 31221121或的取值為中的各個系數(shù)其中形式來表示可用多項式的循環(huán)碼的生成矩陣rrigxgxgxgxgxxgxgxxgxgxxgxxGxGirrrrrkk44標準生成矩陣其生成多項式為循環(huán)碼對于前述的例如變成標準陣經(jīng)初等變換101 1 0010111 0101101 100101 1 001010 1 011100 0

26、 1111)()()()(1)(:,) 3 , 7(,23434524562234GxxxxxxxxxxxxgxxgxgxxGxxxxgk-1, k=34546【例題】 設(shè)（7,3）循環(huán)碼的生成多項式為1)(24xxxxg，試根據(jù)（9-25）式列出所有的許用碼字。 解 首先應(yīng)得出標準生成矩陣： 0111 0011110 0101011 1000111 0011110 0101100 1011)()()()(2423523462GGxxxxxxxxxxxxgxxgxgxxG標準生成矩陣 47其次，根據(jù)（9-25）式，得 00000000111 0011110 0101011 1000000T 0

27、0101110111 0011110 0101011 1000011T 01011100111 0011110 0101011 1000102T 01110010111 0011110 0101011 1000113T 10010110111 0011110 0101011 1001004T 10111000111 0011110 0101011 1001015T 11001010111 0011110 0101011 1001106T 11100100111 0011110 0101011 1001117T 最后得表 9-5 所示的（7,3）循環(huán)碼的所有許用碼字表。 481)(24xxxxg

28、產(chǎn)生循環(huán)碼對應(yīng)的許用碼字表 序號 循環(huán)碼碼字 （7,3）碼 信息碼 監(jiān)督碼 456aaa 0123aaaa 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 1 1 1 0 0 1 1 1 0 0 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 1 1 0 0 1 0 1 1 1 1 0 0 1 0 4911)(11)(1)(1)(,)3 , 7( ,)(,)(),(,1)()()(. 211)(1)()(. 1)()()( 2 . 4 . 932213*1, 01223237234*12211*12211*21xxxhxhxxhx

29、hxhxxxxgxxhxxxxgxhxhxhxhxhxhxxhxhxhkxhxhxhxxgxxhxhxHxhxhhhkkkkkkkkkn已知循環(huán)碼例如就可求出的系數(shù)利用只要求出了因此的逆多項式次多項式的它是常數(shù)項為的定義監(jiān)督多項式以及監(jiān)督矩陣及逆多項式監(jiān)督多項式系數(shù)對稱交換法系數(shù)對稱交換法g(x)的最高次為的最高次為r50)( 00010110010110010110010110001)()()()()()()3 , 7(,)()()()()()3(324235346*2*3*1監(jiān)督矩陣為循環(huán)碼的可求得根據(jù)的上面的結(jié)果例如監(jiān)督矩陣HxxxxxxxxxxxxhxxhxhxxhxxHxHxhxxh

30、xhxxHxHkn51HGGHPQQPGHQIGGIPHHTT求或由求可由況是一致的這與線性分組碼中的情或的關(guān)系為和進一步得標準生成矩陣由前面推導(dǎo)的結(jié)果標準監(jiān)督矩陣變成標準陣經(jīng)初等變換變成標準陣經(jīng)初等變換,:,|101 1 0010111 0101101 100101 1 001010 1 011100 0 111|0001 0110010 1100100 1111000 1011011 0000110 0011100 0101000 101（4）循環(huán)碼中監(jiān)督矩陣）循環(huán)碼中監(jiān)督矩陣H與生成矩陣與生成矩陣G關(guān)系關(guān)系52.,) 1 , 2, 1(01) 1 , 2, 1(:,)(1)(. 13 .

31、 4 . 912211為異或電路為位移寄存器開關(guān)斷開開關(guān)接通圖中除法電路如下圖對輸入作除法運算用生成多項式設(shè)生成多項式為除法電路的一般形式編碼方法與編碼電路rriDrrigxgxgxgxgxxgiirrrrr1rg0D輸入輸出1D2D2rD1rD2rg3g2g1g10g1rg它是內(nèi)環(huán)式，并解釋其構(gòu)成規(guī)律。它是內(nèi)環(huán)式，并解釋其構(gòu)成規(guī)律。53:, 1)(:,:)(:2340電路為對輸入信號作除法運算例如最低位存于存于寄存器單元余數(shù)商輸出輸出被除數(shù)的輸入輸入即為除數(shù)各個部分的功能xxxxgDDxgi0D輸入輸入輸出輸出1D2D3D54:1)(:24的電路為對輸入信號作除法運算再如xxxxg0D輸入輸

32、入輸出輸出1D2D3D55)()()()()(: ,)4()()()()(:)()(),()()3()(),)()2(. 1 ),(,) 1 ()7(, ,)3 , 7( :. 24,01233,456xRxmxxQxgxAxRxQxgxmxxRxQxmxxgxmxrxmxkxmrknaaaaaaaArrrrrrk碼多項式為故最后可求得循環(huán)碼的的倍式循環(huán)碼都是生成多項式前面提及即和余式得商式除用得位相當于左移乘用其最高次數(shù)為可求得其碼多項式根據(jù)給定的信息碼設(shè)碼字為循環(huán)碼為例以除法電路為其核心電路循環(huán)碼的編碼規(guī)則監(jiān)督碼信息碼 56. ,),()(),0(, ),()(,)( ,)(,)6(. ,

33、)()(,)5(錯的位進行糾錯出最后利用余數(shù)的特征對表明有錯則表明余數(shù)不為若不能除盡表明沒有出錯則若能除盡除收到的碼字同的首先用與發(fā)送端相后在收到碼字在接收端則這就是循環(huán)碼的編碼規(guī)除盡能夠被循環(huán)碼的碼多項式很顯然xBxAxBxAxgxBxgxA570D1D2D3D輸入信息碼輸出碼字1K2K12. )()()()()(, ) 3(.,.0 , ,2,)2(.4 , ,1)1 (2121編碼的循環(huán)碼是按編碼規(guī)則由上述分析知息碼才能重新輸入下一個信部輸出完后注意要等到四位余數(shù)全全部為寄存器的狀態(tài)也后當四位余數(shù)全部輸出完完成循環(huán)碼編碼息碼的后面接著輸出寄存器中余數(shù)跟在信斷開接位置此時除法運算也已完成碼

34、輸入完成后個移位寄存器中余數(shù)保存在碼作除法運算除法電路對輸入信息另一方面將信息碼直接輸出一方面接通時接位置xRxmxxQxgxAKKKKr3.編碼電路的組成與工作原理編碼電路的組成與工作原理58編碼電路工作原理分析編碼電路工作原理分析根據(jù)（9-34）式，若輸入信息碼456aaam ，用生成多項式1)(24xxxxg除)(4xmx ，得余多項式)(/ )()(4xgxmxxR，余數(shù)R與信息碼m的對應(yīng)關(guān)系如表 9-6 所示。 表 9-6 輸入信息碼m與余數(shù)R的對應(yīng)關(guān)系 456aaam 0123aaaaR 0 0 0 0 0 0 0 0 0 1 0 1 1 1 0 1 0 1 1 1 0 0 1 1

35、 1 0 0 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 1 1 0 0 1 0 1 1 1 1 0 0 1 0 59根據(jù)圖 9-10 所示的電路， 設(shè)寄存器3333DDDD對應(yīng)的當前狀態(tài)為nnnnQQQQ1234，次態(tài)為11121314nnnnQQQQ，則它們之間滿足如下狀態(tài)方程 mQQmQQQmQQQQQnnnnnnnnnn41114122413314 由上式， 進一步得寄存器中的余數(shù)與輸入信息碼之間的邏輯關(guān)系如表 9-7 所示。由此可知，表 9-6 與表 9-7 的結(jié)果是一致的。 60表 9-7 寄存器中的余數(shù)與輸入信息碼之間的邏輯關(guān)系 nnnnQQQQm12341112

36、1314nnnnQQQQ0 0 0 0 00 0 0 00 0 0 0 00 0 0 0 00 0 0 00 0 0 06a5a4a3a2a1a0annnnQQQQm123411121314nnnnQQQQ1 0 0 0 00 1 1 11 0 1 1 10 1 0 0 11 0 0 10 1 0 16a5a4a3a2a1a0annnnQQQQm123411121314nnnnQQQQ0 0 0 0 00 0 0 00 0 0 0 01 0 0 0 00 0 0 00 1 1 16a5a4a3a2a1a0annnnQQQQm123411121314nnnnQQQQ1 0 0 0 00 1 1

37、11 0 1 1 11 1 0 0 11 0 0 10 0 1 06a5a4a3a2a1a0annnnQQQQm123411121314nnnnQQQQ1 0 0 0 00 1 1 10 0 1 1 10 1 1 1 01 1 1 01 0 1 16a5a4a3a2a1a0annnnQQQQm123411121314nnnnQQQQ1 0 0 0 00 1 1 10 0 1 1 11 1 1 1 01 1 1 01 1 0 06a5a4a3a2a1a0annnnQQQQm123411121314nnnnQQQQ0 0 0 0 00 0 0 01 0 0 0 00 0 1 1 10 1 1 11

38、 1 1 06a5a4a3a2a1a0annnnQQQQm123411121314nnnnQQQQ0 0 0 0 00 0 0 01 0 0 0 01 0 1 1 10 1 1 11 0 0 16a5a4a3a2a1a0a 614、循環(huán)碼譯碼電路的組成與工作原理、循環(huán)碼譯碼電路的組成與工作原理 1循環(huán)碼的譯碼電路 對應(yīng)圖 9-10 的譯碼電路如圖 9-11 所示。 該電路接收到的碼多項式為)(xT， 二進制形式為0123456aaaaaaaT ， 對應(yīng)多項式為00112233445566)(xaxaxaxaxaxaxaxT。碼字最高位對應(yīng)6a，最低位對應(yīng)0a，按高位先到低位后到的順序輸入緩存器

39、。整個循環(huán)碼譯碼電路由 7 級緩存器、除法電路、切換開關(guān) K、反饋移位寄存器及輸出和校正信號產(chǎn)生器、校正電路（即異或器）五大部分組成。 621R2R3R4RK&S校正校正信號輸出信號輸出譯碼譯碼輸出輸出)(xT7級緩存器(延時器)7級緩存器(延時器)除法運算器除法運算器余數(shù)最低位余數(shù)最低位余數(shù)余數(shù)余數(shù)最高位余數(shù)最高位余數(shù)余數(shù)異或器異或器1R2R3R4R反饋移位寄存器及輸出和S校正信號產(chǎn)生器反饋移位寄存器及輸出和S校正信號產(chǎn)生器4T3T2T1T6T5T6a5a4a3a2a1a0a0TnQ4nQ3nQ2nQ163譯碼電路中各個部分的工作原理及功能如下： （1）7 級緩存器（延時器） 。它起

40、到延時的作用，能使校正信號正好對準所需校正的碼元，由于有 7 位碼0123456aaaaaaa，故需要有 7 個緩存器（延時器） 。 （2）譯碼器中的除法電路。它與發(fā)送端編碼器的除法電路一致，用于檢查收到的碼字是否正確，若收到的碼字能夠被除法器除盡，余數(shù)為 0，表明無錯，若除不盡，余數(shù)不為 0，表明有錯，除法電路獲取的余數(shù)送入反饋移位寄存器。作除法運算時需注意以下兩點： 64 將收到碼字)(xT乘以rx之后，再除以)(xg。具體而言，為得到正確的余多項式，應(yīng)作運算)(/ )(4xgxTx， 余數(shù)最高位放在寄存器4R中，余數(shù)最低位放在寄存器1R中。 在一般情況下，余數(shù)的位數(shù)應(yīng)與寄存器的個數(shù)相等。

41、對于圖 9-11，有四個寄存器，故余數(shù)應(yīng)為四位。 例如， 若求得余多項式為12x，則對應(yīng)的余數(shù)應(yīng)為 0101，若寄存器是三個,則作余數(shù)應(yīng)為三位，等等。 65（3）切換開關(guān) K。在圖 9-11 中，碼字長度為 7，隨著一個碼字的 7 個碼元全部移進緩存器后， 除法電路也就完成了對這個碼字的除法運算， 余數(shù)存放在四個寄存器4R、3R、2R、1R中。一旦對整個碼字的除法運算結(jié)束，開關(guān) K 就接通，將余數(shù)送入反饋移位寄存器，緊接著開關(guān) K 又斷開，并將除法電路中所有寄存器都清零（清零電路在圖中未畫出） ，再對下一個碼字作除法運算，運算結(jié)束后，K 再次接通，所有寄存器再次清零，依此重復(fù)下去。 66 （4

42、）反饋移位寄存器及輸出和校正信號產(chǎn)生器。它利用除法電路送來的余數(shù)來產(chǎn)生 S 校正信號，主要由反饋移位寄存器、反饋移位寄存器的輸出和與門三個部分組成。反饋移位寄存器的輸出信號為nnnnQQQQ1234，通過非門和與門產(chǎn)生校正信號nnnnQQQQS1234。反饋移位寄存器是核心部件，下面將對其進行詳細分析。 （5）校正電路。它由一個異或器組成。若 S=1，表明所收到的對應(yīng)的碼元有錯，可利用異或器對其校正，若 S=0，表明無錯，異或的結(jié)果，則保持原碼元不變。 67 2反饋移位寄存器的狀態(tài)方程、狀態(tài)轉(zhuǎn)換表和狀態(tài)轉(zhuǎn)換圖 根據(jù)譯碼電路，得反饋移位寄存器的狀態(tài)方程為 nnnnnnnnnnQQQQQQQQQQ

43、41114122413314 進一步得反饋移位寄存器的狀態(tài)轉(zhuǎn)換表如下表所示。 68nnnnQQQQ1234 11121314nnnnQQQQ 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 0 1 1 0 0 1 0 0 1 0 0 0 0 1 0 1 1 0 1 0 0 1 1 0 1 1 0 0 0 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 0 0 1 0 1 0 1 1 0 1 0 0 0 1 1 1 0 1 1 0 0 0 1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1

44、 0 1 0 1 1 1 1 1 1 1 0 0 1 69由狀態(tài)轉(zhuǎn)換表，得狀態(tài)轉(zhuǎn)換圖：由狀態(tài)轉(zhuǎn)換表，得狀態(tài)轉(zhuǎn)換圖：0100001000010111101111101000主循環(huán)nnnnQQQQ1234110100001100011000111001101001011111基準錯余數(shù)6a錯余數(shù)5a錯余數(shù)4a錯余數(shù)3a錯余數(shù)2a錯余數(shù)1a錯余數(shù)0a70虛框所示部分的循環(huán)用于糾錯。當碼元6a出錯時，對應(yīng)反饋移位寄存器產(chǎn)生的輸出信號為10001234nnnnQQQQ。當碼元5a出 錯 時 ， 對 應(yīng) 反 饋 移 位 寄 存 器 產(chǎn) 生 的 輸 出 信 號 為,01001234nnnnQQQQ，當碼元0

45、a出錯時，對應(yīng)反饋移位寄存器產(chǎn)生的輸出信號為01111234nnnnQQQQ。 將余數(shù)nnnnQQQQ1234通過非門和與門后，產(chǎn)生校正信號nnnnQQQQS1234。最后利用反饋移位寄存器的移位操作，將校正信號 S 正好對準緩存器的輸出碼元，從而使得這兩路信號同時到達異或器，對相應(yīng)的錯誤碼元校正。 71 3譯碼和糾錯原理分析 圖 9-10 所示編碼電路的生成多項式為1)(24xxxxg， 得所有的許用碼字如表 9-6 所示。發(fā)送端與接收端按同一規(guī)則進行編譯碼，譯碼電路如圖 9-11 所示。分析結(jié)果如下： （1）經(jīng)傳輸后收到的碼字)(xT如果沒有誤碼，則能被除法電路除盡，余數(shù)為 0，除法電路中

46、的四個寄存器4R、3R、2R、1R也都為0，當 K 閉合后，反饋移位寄存器中的4R、3R、2R、1R也都為 0，校正信號 S=0，不需校正。 （ 2 ） 在 錯 1 位 的 情 況 下 ， 以 表 9-6 中 的 碼 多 項 式1)(36xxxxT為例來說明糾錯原理， 其余碼多項式錯 1 位的情況類似，讀者不難驗證。 72 若6a有錯，) 1/() 1(2434xxxxxx的余多項式為3x，它對應(yīng)的四位碼為10001234nnnnQQQQ，根據(jù)圖9-12，不需移位，得11234nnnnQQQQS， 立即對6a糾錯。 若5a有錯，) 1/() 1(243564xxxxxxxx的余多項式2x，對應(yīng)

47、四位碼01001234nnnnQQQQ，根據(jù)圖9-12，移位一次后，得11234nnnnQQQQS，對5a糾錯。 73 若4a有錯，) 1/() 1(243464xxxxxxxx余多項式x，它對應(yīng)四位碼為00101234nnnnQQQQ，根據(jù)圖 9-12， 移位二次后， 得11234nnnnQQQQS， 對4a糾錯。 若3a有錯，) 1/() 1(2464xxxxxx的余多項式為1，它所對應(yīng)的四位碼為00011234nnnnQQQQ， 根據(jù)圖9-12，移位三次后，得11234nnnnQQQQS，對3a糾錯。 74 若2a有錯，) 1/() 1(242364xxxxxxxx余多項式為13 xx，

48、對應(yīng)四位碼為10111234nnnnQQQQ，根據(jù)圖 9-12， 移位四次后， 得11234nnnnQQQQS，對2a糾錯。 若1a有錯，) 1/() 1(24364xxxxxx余多項式為xxx23，它所對應(yīng)的四位碼為11101234nnnnQQQQ，根據(jù)圖 9-12，移位五次后，得11234nnnnQQQQS，對1a糾錯。 若0a有錯，) 1/()(24364xxxxxxx余多項式為12 xx， 它所對應(yīng)的四位碼為01111234nnnnQQQQ， 根據(jù)圖9-12，移位六次后，得11234nnnnQQQQS，對0a糾錯。 75【 例 題 】 已 知 （ 7,3 ） 循 環(huán) 碼 的 生 成 多

49、 項 式 為1)(234xxxxg，試設(shè)計其編碼電路和譯碼電路。已知發(fā)送端發(fā)送的正確碼字為11101000123456aaaaaaaT，若6a有錯，利用它來設(shè)計譯碼器中的校正電路（即反饋移位寄存器的哪些輸出應(yīng)串接非門） 。并分析當碼字中的5a、4a、3a、2a、1a、0a分別出錯時，譯碼器能否正確糾錯？從而論證該譯碼器的設(shè)計是否正確。 76解：編碼電路為解：編碼電路為0D1D2D3D輸入信息碼輸出碼字1K2K1277（2）譯碼電路的設(shè)計結(jié)果如圖例 9-6 圖（b）所示。 其中反饋移位寄存器的哪些輸出端要加非門可由碼元6a發(fā)生錯誤來確定。6a出錯， 碼字變成 0110100，對應(yīng)的碼多項式為24

50、5)(xxxxT， 余數(shù)的計算與前面敘述的方法相同，得余多項式為10003x，故應(yīng)分別在1R、2R、3R的輸出端口串入一個非門。 784T3T2T1T1R4RK&S 校正信號輸出譯碼輸出)(xT7級緩存器(延時器)除法運算器余數(shù)最高位異或器6T5T反饋移位寄存器及輸出和S校正信號產(chǎn)生器余數(shù)最低位6a5a4a3a2a1a0a0T2R3R余數(shù)余數(shù)1R4R2R3RnQ4nQ3nQ2nQ179反饋移位寄存器的狀態(tài)方程為 nnnnnnnnnnQQQQQQQQQQ41114122413314 80狀態(tài)轉(zhuǎn)換表為：狀態(tài)轉(zhuǎn)換表為：nnnnQQQQ1234 11121314nnnnQQQQ 0 0 0 0

51、 0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 1 0 1 1 0 0 1 0 0 1 0 0 0 0 1 0 1 1 0 1 0 0 1 1 0 1 1 0 0 0 1 1 1 1 1 1 0 1 0 0 0 1 1 0 1 1 0 0 1 1 1 1 1 1 0 1 0 1 0 0 1 1 0 1 1 1 0 1 1 1 1 0 0 0 1 0 1 1 1 0 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 1 1 81狀態(tài)轉(zhuǎn)換圖為：狀態(tài)轉(zhuǎn)換圖為：0100001000011101111001111000主循環(huán)nnnn

52、QQQQ1234101100000011111110011100101001010110基準錯余數(shù)6a錯余數(shù)5a錯余數(shù)4a錯余數(shù)3a錯余數(shù)2a錯余數(shù)1a錯余數(shù)0a82（4）糾錯的工作原理分析 當6a有錯時，余多項式3x，對應(yīng)余數(shù) 1000，不需移位，立即對6a糾錯。 當5a有錯時，余多項式2x，對應(yīng)余數(shù)為 0100，移位一次，可對5a糾錯。 當4a有錯時，余多項式x，對應(yīng)余數(shù)為 0010，移位二次，可對4a糾錯。 83 當3a有錯時，余多項式1，對應(yīng)余數(shù)為0001，移位三次，可對3a糾錯。 當2a有錯時，余多項式xxx23，對應(yīng)余數(shù)為 1110，移位四次，可對2a糾錯。 當1a有錯時，余多項式

53、12 xx，對應(yīng)余數(shù)為 0111，移位五次，可對1a糾錯。 當0a有錯時，余多項式123 xx，對應(yīng)余數(shù)為 1101，移位六次，可對0a糾錯。 84*（5）最后用時序邏輯電路的分析方法來驗證上面各個余數(shù)的正確性。根據(jù)例 9-6 圖（b） ，得譯碼器中除法運算器的狀態(tài)方程為 nnnnnnnnnnQmQQQQQmQQQmQ41111224133414 根據(jù)上述狀態(tài)方程，可得狀態(tài)轉(zhuǎn)換表如例 9-6 表（b）所示， 進一步得接收碼字與余數(shù)之間的關(guān)系如例 9-6 表 （c）所示。由此可見，用兩者的分析結(jié)果是一致的。 85例 9-6 表（b） nnnnQQQmQ1234 nnnnQQQmQ1234 111

54、21314nnnnQQQQ 11121314nnnnQQQQ 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 0 0 1 0 0 1 0 1 1 1 1 0 0 0 1 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 1 1 1 0 0 1 1 0 1 1 0 1 0 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 0 0 1 0 1 0 0 1 0 1 1 0 1 0 1 1 0 1 0 0 1 1 1 0 0 1 1 0 1 0 1 1 0 1 1 0 0 0 0 0 1 0 0 1 1 1 1 0 1 1

55、 1 1 1 1 0 0 0 1 1 0 1 0 0 0 1 1 0 0 0 1 1 0 1 0 0 0 0 0 1 0 0 1 1 1 0 0 1 1 1 1 1 0 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 0 1 0 1 0 0 0 1 0 1 1 1 1 0 1 1 1 0 1 1 0 1 1 0 0 1 1 0 0 1 1 1 0 0 0 1 0 1 1 0 0 0 0 1 1 0 1 1 1 1 0 1 0 1 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 1 1 1

56、 1 1 0 86例 9-6 表（c） nnnnQQQQm123411121314nnnnQQQQ0 0 0 0 00 0 0 01 0 0 0 01 1 1 0 11 1 0 11 0 1 06a5a4a3a2a1a0a0 1 0 1 01 0 0 11 1 0 0 10 0 1 00 0 0 1 00 1 0 00 0 1 0 01 0 0 03a2a1a0annnnQQQQm123411121314nnnnQQQQ1 0 0 0 01 1 0 11 1 1 0 11 1 0 1 01 0 1 00 1 0 06a5a4a3a2a1a0a0 0 1 0 01 0 0 01 1 0 0 00

57、 0 0 00 0 0 0 00 0 0 00 0 0 0 00 0 0 03a2a1a0a （a）接收碼字無錯的余數(shù) （b）接收碼字6a錯的余數(shù) nnnnQQQQm123411121314nnnnQQQQ1 0 0 0 01 1 0 10 1 1 0 11 0 1 1 10 1 1 10 0 1 16a5a4a3a2a1a0a0 0 0 1 10 1 1 01 0 1 1 00 0 0 10 0 0 0 10 0 1 00 0 0 1 00 1 0 03a2a1a0annnnQQQQm123411121314nnnnQQQQ1 0 0 0 01 1 0 11 1 1 0 10 1 0 1 0

58、1 0 1 01 0 0 16a5a4a3a2a1a0a0 1 0 0 11 1 1 11 1 1 1 11 1 1 00 1 1 1 00 0 0 10 0 0 0 10 0 1 03a2a1a0a （c）接收碼字5a錯的余數(shù) （d）接收碼字4a錯的余數(shù) 87nnnnQQQQm123411121314nnnnQQQQ1 0 0 0 01 1 0 11 1 1 0 11 1 0 1 01 0 1 00 1 0 06a5a4a3a2a1a0a1 0 1 0 00 1 0 11 0 1 0 10 1 1 10 0 1 1 11 1 1 00 1 1 1 00 0 0 13a2a1a0annnnQQ

59、QQm123411121314nnnnQQQQ1 0 0 0 01 1 0 11 1 1 0 11 1 0 1 01 0 1 00 1 0 06a5a4a3a2a1a0a0 0 1 0 01 0 0 00 1 0 0 01 1 0 10 1 1 0 10 1 1 10 0 1 1 11 1 1 03a2a1a0a （e）接收碼字3a錯的余數(shù) （f）接收碼字2a錯的余數(shù) nnnnQQQQm123411121314nnnnQQQQ1 0 0 0 01 1 0 11 1 1 0 11 1 0 1 01 0 1 00 1 0 06a5a4a3a2a1a0a0 0 1 0 01 0 0 01 1 0 0

60、 00 0 0 01 0 0 0 01 1 0 10 1 1 0 10 1 1 13a2a1a0annnnQQQQm123411121314nnnnQQQQ1 0 0 0 01 1 0 11 1 1 0 11 1 0 1 01 0 1 00 1 0 06a5a4a3a2a1a0a0 0 1 0 01 0 0 01 1 0 0 00 0 0 00 0 0 0 00 0 0 01 0 0 0 01 1 0 13a2a1a0a （g）接收碼字1a錯的余數(shù) （h）接收碼字0a錯的余數(shù) 889.5 卷積碼簡介卷積碼簡介9.5.1 卷積碼的基本概念卷積碼的基本概念 卷積碼由伊利亞斯卷積碼由伊利亞斯(P. Llias)于于