1、信息論與編碼技術信息論與編碼技術主講：展愛云主講：展愛云信息工程學院信息工程學院6.1差錯控制方式差錯控制方式噪聲噪聲6.1差錯控制方式差錯控制方式解決噪聲解決噪聲的辦法的辦法去除噪聲去除噪聲接受噪聲：積極應接受噪聲：積極應對受影響的問題對受影響的問題6.1差錯控制方式差錯控制方式更換信道更換信道6.1差錯控制方式差錯控制方式信源信宿信道噪聲1011010110110001知錯知錯 6.1差錯控制方式差錯控制方式 改錯改錯6.1差錯控制方式差錯控制方式信源信宿信道噪聲靠自己靠自己求教別人求教別人6.1差錯控制方式差錯控制方式差錯控差錯控制方式制方式反饋重傳（反饋重傳（ARQ）（Automati

2、c Repeat Request）前向糾錯（前向糾錯（FEC）（Forward Error Correction）混合方式（混合方式（HEC）（Hybird Error Correction6.1差錯控制方式差錯控制方式1、前向糾錯（、前向糾錯（FEC）信源信宿信道噪聲101101011011000110110101特點特點單向通道單向通道要求糾錯碼要求糾錯碼實時性好實時性好6.1差錯控制方式差錯控制方式好好1101011110錯了錯了錯了，重發(fā)一遍錯了，重發(fā)一遍11010存儲器存儲器110102、反饋重傳（、反饋重傳（ARQ）雙雙向通道向通道實時性不好實時性不好特點特點只要求只要求檢檢錯碼錯

3、碼發(fā)送端要存儲器發(fā)送端要存儲器3、混合方式（、混合方式（HEC）6.1差錯控制方式差錯控制方式 混合方式具有混合方式具有前向糾錯前向糾錯和和反饋重反饋重傳傳的優(yōu)點，可以達到較低的誤碼率，的優(yōu)點，可以達到較低的誤碼率，適合于適合于高速高速傳輸系統(tǒng)傳輸系統(tǒng)信源發(fā)出的數據直接送入信道信源發(fā)出的數據直接送入信道所以送入信道之前要進行處理6.2信道編碼本質信道編碼本質信道編碼信道編碼信道譯碼信道譯碼噪噪聲聲6.2信道編碼本質信道編碼本質信道編碼信道編碼信道譯碼信道譯碼6.2信道編碼本質信道編碼本質信信宿宿信信源源有有噪噪信信道道信信息息元元監(jiān)監(jiān)督督元元碼碼字字晴晴：11雨：雨：0011100100紅色紅

4、色線出線出現(xiàn)的現(xiàn)的錯誤錯誤可以可以發(fā)現(xiàn)發(fā)現(xiàn)6.2信道編碼本質信道編碼本質 k位信息元位信息元r位監(jiān)督元位監(jiān)督元 n位碼字位碼字k+r=n6.2信道編碼本質信道編碼本質如果是二進制編碼，則相當于從碼字集合中找相應的碼字來替代1、信道編碼的分類按照信息元和按照信息元和監(jiān)督元的關系監(jiān)督元的關系分組碼分組碼卷積碼卷積碼6.2信道編碼本質信道編碼本質1、信道編碼的分類按照信息元和按照信息元和監(jiān)督元位置關系監(jiān)督元位置關系系統(tǒng)碼系統(tǒng)碼非系統(tǒng)碼非系統(tǒng)碼6.2信道編碼本質信道編碼本質1、信道編碼的分類按照信息元和按照信息元和監(jiān)督元的計算關系監(jiān)督元的計算關系線性碼線性碼非線性碼非線性碼6.2信道編碼本質信道編碼本

5、質為什么引入線性碼？1、信道編碼的分類漢明碼循環(huán)碼線性分組碼非線性分組碼分組碼線性卷積碼非線性卷積碼卷積碼信道編碼6.2信道編碼本質信道編碼本質2、信道編碼的發(fā)展6.2信道編碼本質信道編碼本質6.2信道編碼本質信道編碼本質6.2信道編碼本質信道編碼本質6.2信道編碼本質信道編碼本質6.2信道編碼本質信道編碼本質3、基本概念(p193、172) 1）、漢明碼重(hamming weight) 碼字中碼元“1”的個數。 例如： 100110 的碼重是 3 w( 1100110)= ？6.2信道編碼本質信道編碼本質2）、漢明碼距(hamming distance) 兩個碼字相對應位不同的個數。 例如

6、：d(1011,0110)=3 d(0011,1011)=? 思考：碼距和碼重的關系？6.2信道編碼本質信道編碼本質結論：碼距是兩個碼字異或的結果的碼重 例如：d(10101,01011) 1 0 1 0 1 0 1 0 1 1 1 1 1 1 06.2信道編碼本質信道編碼本質3）、最小漢明碼距dmin 在碼組中所有碼字相互之間距離的最小值。 例如：碼組 10010，11010，01100 d(10010,11010)=1 d(10010,01100)=4 d(11010,01100)=3 dmin(10010,11010,01100)=1 6.2信道編碼本質信道編碼本質4、檢糾錯能力(p19

7、4/p174)結論：檢糾能力與最小碼距有關。任一(n, k)分組碼，若要在碼字內： 1）、檢錯能力(e位) d=e+1例如：碼組1001，0110，0101 e=? 6.2信道編碼本質信道編碼本質2）、糾錯能力（t) d=2*t+1例如：碼組100101，000101，100001的糾錯能力？6.2信道編碼本質信道編碼本質3）、糾正t個隨機錯誤，同時同時檢測e (e=t)個錯誤，則要求d=e+t+16.2信道編碼本質信道編碼本質奇偶奇偶校驗校驗一維奇偶校驗一維奇偶校驗二維奇偶校驗二維奇偶校驗6.3簡單的信道編碼方法簡單的信道編碼方法1、奇偶校驗、奇偶校驗一一維維奇偶校驗奇偶校驗信息信息元元監(jiān)督

8、元監(jiān)督元100101011奇校驗奇校驗偶校驗偶校驗在信息元后加上在信息元后加上0或者或者1，使得使得碼字的碼字的1的個數為的個數為奇數個奇數個在信息元后加上在信息元后加上0或者或者1，使得使得碼字的碼字的1的個數為的個數為偶數個偶數個奇校驗奇校驗0碼字碼字100101011010011101101011110110知道錯了知道錯了不知道錯了不知道錯了不能糾正不能糾正不能糾正不能糾正自動反饋重傳的差錯控制方式自動反饋重傳的差錯控制方式一維的奇偶校驗發(fā)現(xiàn)奇數個錯誤一維的奇偶校驗發(fā)現(xiàn)奇數個錯誤6.3簡單的信道編碼方法簡單的信道編碼方法二維奇偶校驗二維奇偶校驗（行列校校驗碼（行列校校驗碼）按照行和列分

9、別給出校驗位按照行和列分別給出校驗位6.3簡單的信道編碼方法簡單的信道編碼方法11 0 0 1 0 1 0 0 00 1 0 0 0 0 1 1 0 10 1 1 1 1 0 0 0 0 110 0 1 1 1 0 0 0 01 0 1 0 1 0 1 0 1 00010111111000100偶偶校校驗驗(66,50)的行列校驗碼的行列校驗碼6.3簡單的信道編碼方法簡單的信道編碼方法信道信道錯誤的位置錯誤的位置可可以以糾糾正正不不可可以以糾糾正正找不到找不到錯誤位置錯誤位置6.3簡單的信道編碼方法簡單的信道編碼方法信道編碼效率信道編碼效率%100nk一維奇偶校驗的編碼效率為一維奇偶校驗的編碼

10、效率為1%100kknk可以看出，奇偶校驗很簡單，因此，可以看出，奇偶校驗很簡單，因此，在很多場合得到了廣泛的使用，如網在很多場合得到了廣泛的使用，如網絡傳輸數據。另外，在內存、硬盤保絡傳輸數據。另外，在內存、硬盤保存數據等方面也得到了廣泛應用。存數據等方面也得到了廣泛應用。6.3簡單的信道編碼方法簡單的信道編碼方法一般在較簡單對差錯率要求不是太高一般在較簡單對差錯率要求不是太高的通信系統(tǒng)中的通信系統(tǒng)中應用。應用。2、定比碼、定比碼6.3簡單的信道編碼方法簡單的信道編碼方法電報大樓的電報大樓的7號柜臺如今是北號柜臺如今是北京唯一一個能發(fā)電報的柜臺京唯一一個能發(fā)電報的柜臺http:/ 信信 卓卓

11、 越越 4508 4837 5531 52296.3簡單的信道編碼方法簡單的信道編碼方法每個漢字用每個漢字用4位的十進制進行編碼位的十進制進行編碼 11010 00111 01101 01110 11010 01110 10110 11100 00111 00111 10110 01011 00111 11001 11001 100116.3簡單的信道編碼方法簡單的信道編碼方法 11010 00111 01101 01110 11010 01110 10110 11100 00111 00111 10110 01011 00111 11001 11001 10011 11010 00111 0

12、1101 01110 11010 01100 10110 11100 00111 00111 10110 01011 00111 11001 11001 10011錯了錯了3、群計數碼、群計數碼6.3簡單的信道編碼方法簡單的信道編碼方法 數信息元中數信息元中“1”的個數，在信息元后的個數，在信息元后加上用二進制表示的加上用二進制表示的“1”的個數。的個數。例如：例如：1100101 的群計數編碼的群計數編碼群計數編碼：群計數編碼：1100101 100思考？思考？群計數編碼：群計數編碼：1100101 0100注意：注意： 群計數編碼的監(jiān)督元的位數群計數編碼的監(jiān)督元的位數 r=logk6.3簡

13、單的信道編碼方法簡單的信道編碼方法 在某些電氣化鐵道運動系統(tǒng)和電報系統(tǒng)中采用。在某些電氣化鐵道運動系統(tǒng)和電報系統(tǒng)中采用。 6.3簡單的信道編碼方法簡單的信道編碼方法4、正反碼、正反碼 編碼方法編碼方法：在信息元后加在信息元后加上信息元的原上信息元的原碼或者反碼碼或者反碼 信息元信息元1的個數為的個數為奇數個奇數個，監(jiān)督元為監(jiān)督元為原碼原碼 信息元信息元1的個數為的個數為偶數個偶數個，監(jiān)督元為監(jiān)督元為反碼反碼例： 信息元10110信息元信息元10100+監(jiān)督元監(jiān)督元 10110 =碼字碼字1011010110 +監(jiān)督元監(jiān)督元 01011 =碼字碼字1010001011 正反碼的編碼效率正反碼的編

14、碼效率2/1%100nk5、模、模p法法6.3簡單的信道編碼方法簡單的信道編碼方法在實際生活中，有時侯在實際生活中，有時侯“1”和和“I”很相似。很相似。 “0” 0 “1” 1 “A” 10 “B” 11 對象：數字對象：數字“0”-“9”和字母和字母“A”-“Z”和空格和空格共共37種符號組成的信源。種符號組成的信源。 p=37(符號的個數）符號的個數） 符號符號 值值符號符號 值值符號符號 值值符號符號 值值符號符號 值值0088G16O24W321199H17P25X3322A10I18Q26Y3433B11J19R27Z3544C12K20S28空格空格 3655D13L21T296

15、6E14M22U3077F15N23V31設有某消息的符號序列為設有某消息的符號序列為X=X1X2X3X4假設要加上的監(jiān)督元假設要加上的監(jiān)督元X56.3簡單的信道編碼方法簡單的信道編碼方法求監(jiān)督元求監(jiān)督元X5消息符號消息符號和和累加和累加和X1X1X1X2X1+X22*X1+X2X3X1+X2+X33*X1+2*X2+X3X4X1+X2+X3+X44*X1+3*X2+2*X3+X4X1+X2+X3+X4+X55*X1+4*X2+3*X3+2*X4+1*X5X5設有某消息的符號序列為設有某消息的符號序列為X=X1X2X3X4假設要加上的監(jiān)督元假設要加上的監(jiān)督元X56.3簡單的信道編碼方法簡單的信

16、道編碼方法整數模）(*1.2*) 1(1*PXnXnXn求得監(jiān)督元求得監(jiān)督元X5例：信息元符號序列例：信息元符號序列AS9R6.3簡單的信道編碼方法簡單的信道編碼方法求得：求得： =16 換算成符號為換算成符號為G整數）37(*1*29*3*4*5PRSA整數37*127*29*328*410*5解：假設要加上的監(jiān)督元為解：假設要加上的監(jiān)督元為，則則n=5碼字為碼字為AS9RG應用：應用：2007年前的年前的ISBN, 10位，最后一位是監(jiān)督元位，最后一位是監(jiān)督元6.3簡單的信道編碼方法簡單的信道編碼方法P=11對象：數字對象：數字“0”-“9”和字母和字母“X 符符號號值值符符號號值值符符號

17、號值值符符號號值值114477X10225588336699例：計算ISBN 7-80112-724-?解：7*10+8*9+0*8+1*7+1*6+2*5+7*4+2*3+4*2=6.3簡單的信道編碼方法簡單的信道編碼方法應用應用（變型的模（變型的模P法）法）2007年后的年后的ISBN, 13位，最后一位是監(jiān)督元位，最后一位是監(jiān)督元P=10方法：方法：奇數位奇數位*1+偶數位偶數位*3+監(jiān)督元監(jiān)督元P(10)=整數整數例子：教材的例子6.4線性碼線性碼1、線性碼的定義群群定義了一種運算的集合定義了一種運算的集合群 運算封閉 有恒等元 有逆元 滿足結合律交換群 滿足交換律的群環(huán)環(huán)定義了兩種運

18、算的集合定義了兩種運算的集合按第一種運算（不妨稱為加法）構成交換群第二種運算（不妨稱為乘法）滿足以下條件 封閉性 結合律 與加法間滿足分配律域域一種特殊的環(huán)一種特殊的環(huán)乘法有恒等元（稱為1元），且除了加法的恒等元（稱為0元）以外有逆的環(huán)除0元外，對乘法構成交換群無限域 有理數、實數和復數都是無限域有限域 信道編碼中用到的是有限域，GF(q) 兩者在空間意義上有很強的可類比性GF(2)定義了兩種元素：0和1GF(2)定義了兩種運算：*和+0*0=00*1=01*0=01*1=10+0=00+1=11+0=11+1=0線性碼：具有運算封閉性的碼組2、譯碼準則、譯碼準則 譯碼器的任務是從受損的信息序

19、列中譯碼器的任務是從受損的信息序列中盡可能正盡可能正確的確的恢復出原信息。恢復出原信息。 作為譯碼器的輸入，譯碼算法的已知條件是：作為譯碼器的輸入，譯碼算法的已知條件是： 1）實際接收到的）實際接收到的碼字碼字序列（序列（R） 2）發(fā)端所采用的編碼算法和該算法產生的碼集）發(fā)端所采用的編碼算法和該算法產生的碼集3）信道模型和）信道模型和信道信道參數參數P(R/C)或者或者P(C/R) 問題：問題： MC R 如何根據接收信號如何根據接收信號R估計發(fā)送序列估計發(fā)送序列C,進而估計信息序列進而估計信息序列M？最基本的準則：譯碼的差錯率最小 RERPREPPRCCPREP幾種基本的譯碼方法RCCMin

20、PREMinPMinPE)1 (RCCPMinRCCMinPRCCMaxP 在已知接受的碼字序列在已知接受的碼字序列R條件下，找出可條件下，找出可能性最大的發(fā)碼能性最大的發(fā)碼Ci作為譯碼估值作為譯碼估值C , C=max p(Ci/R) )()()()(RPCRPCPRPRCPRCPiiiiiiCRMaxPRCMaxP在已知在已知r的條件下的條件下,使先驗概率最大的使先驗概率最大的譯碼算法譯碼算法.c=max p(r / ci) 3、線性碼的構造為了進行差錯控制，我們按線性代數的為了進行差錯控制，我們按線性代數的關系來添加監(jiān)督元序列。這種就叫做線關系來添加監(jiān)督元序列。這種就叫做線性碼。性碼。從

21、線性方程組的角度描述分組碼從線性方程組的角度描述分組碼 k位信息元位信息元r位監(jiān)督元位監(jiān)督元 n位碼字位碼字k+r=n6.2信道編碼本質信道編碼本質個校驗位個信息位knknknkknnncccccc02121knknnnnnknknknnnknnnknknknknknnnknnnknknchchchcchchchcchchchc, 022, 011, 00, 222, 211, 22, 122, 111, 1145604561456245631101001111111011ccccccccccccccccExamples(7，3)線性分組碼就，監(jiān)督方程組線性分組碼就，監(jiān)督方程組信道編碼信道編碼

22、信道編碼信道編碼0*1.*0*00*0.*1*00*0.*0*1021,22,11,021, 222, 211, 2021, 122, 111, 1cccchchchcccchchchcccchchchknknknknrknnnrknnnrknknknknknknnnknnnknknknknknknnnknnnknknknnnnnknknknnnknnnknknknknknnnknnnknknchchchcchchchcchchchc, 022, 011, 00, 222, 211, 22, 122, 111, 11000100010001021)(,011,0,21,2, 11, 1ccch

23、hhhhhnnnknknnknknnknknknnkn列行，校驗矩陣0HTCH為線性碼的為線性碼的監(jiān)督矩陣（校驗矩陣）監(jiān)督矩陣（校驗矩陣）45604561456245631101001111111011cccccccccccccccc信道編碼信道編碼012345601234560123456012345610001100010000100010111000011010cccccccccccccccccccccccccccc010001100010000100010111000011010123456012345601234560123456ccccccccccccccccccccccccccc

24、c000001100011000010111010010110000123456CCCCCCC000001100011000010111010010110000123456CCCCCCCHCT0T1000110010000100101110001101H45604561456245631101001111111011cccccccccccccccc信道編碼信道編碼例：一個（7，3）碼的信息元x1x2x3和監(jiān)督元x4x5x6x7間的監(jiān)督方程組為： 07320621053210431xxxxxxxxxxxxx07320621053210431xxxxxxxxxxxxx073206210532104

25、31xxxxxxxxxxxxx000001100011100010111010010110007654321xxxxxxxHXT信道編碼信道編碼信息元信息元監(jiān)督元監(jiān)督元編成碼字編成碼字0000000000000000111010011101010011101001110111010011101010011101001110101001110100111101001110100111101001110100合法碼字合法碼字信道編碼信道編碼3）由于封閉性，可知兩個碼字的碼距就是另外）由于封閉性，可知兩個碼字的碼距就是另外一個碼字的重量。一個碼字的重量。一組碼字中碼的最小重量一組碼字中碼的最小重量（

26、除全（除全0）就是該碼組的最小碼距）就是該碼組的最小碼距。 線性分組碼的性質線性分組碼的性質(P196-198/p176-177)1)上表中的八個碼字是上表中的八個碼字是許用碼字許用碼字.2)任意兩個碼字逐位模二相加，可以得到另外任意兩個碼字逐位模二相加，可以得到另外一個碼字。這種性質叫做一個碼字。這種性質叫做封閉性封閉性。4）監(jiān)督矩陣由兩部分組成監(jiān)督矩陣由兩部分組成|rknIAIAH其中其中A為為rk矩陣，矩陣，In-k為為r=n-k階單位方陣階單位方陣011110111101A0001001001001000knI5）每個碼字必須滿足監(jiān)督方程。）每個碼字必須滿足監(jiān)督方程。TTC0H例如：檢

27、驗例如：檢驗0011101是否是合法碼字？是否是合法碼字？例如：檢驗0011101是否是合法碼字？00101100011110100111000101011000101THR 0000所以所以0011101是合法碼字是合法碼字0000001010011000110001110001011101001011000THC所以所以0011001不是碼字不是碼字信道編碼信道編碼例如：檢驗0011001是否是合法碼字？所以所以0011001是非法碼字是非法碼字110100+000101 00101100011110100111000100011000101RTH 0010=0000 信道編碼信道編碼6）

28、在線性碼組中，如果有一個碼字的碼重為在線性碼組中，如果有一個碼字的碼重為W，則，在，則，在H中必有與之相應的中必有與之相應的W列相加為列相加為0，故稱，故稱W列線性相關。列線性相關。 如果要求碼組的最小碼距為如果要求碼組的最小碼距為d，則表示，則表示H中至少有中至少有d列相加之和為列相加之和為0。 這就要求在碼的監(jiān)督矩陣中，任意少于這就要求在碼的監(jiān)督矩陣中，任意少于或等于或等于d-1列相加之和均不應等于列相加之和均不應等于0，即任，即任意意d-1列線性無關。（列線性無關。（P198/p177)生成矩陣生成矩陣信道編碼器信道編碼器輸入信息元輸入信息元輸出碼字輸出碼字MCGM*G=C2、生成矩陣生

29、成矩陣0HnkkkrTcccccccIAC.|21321TnkkrkcccIcccA0.21.21設有一個待編碼的消息序列為設有一個待編碼的消息序列為 M=m1m2.mk將它表示為信息元序列將它表示為信息元序列 x1x2xk用矩陣關系可以表示兩者的關系：用矩陣關系可以表示兩者的關系： kkkmmmIccc.2121kknkkmmmAcccAccc.212121信道編碼信道編碼kAknmmmIccc.2121信道編碼信道編碼MGC G為生成矩陣為生成矩陣|TkGIA信道編碼信道編碼07320621053210431xxxxxxxxxxxxx例：一個（例：一個（7 7，3 3）碼的信息元）碼的信息

30、元x1x2x3x1x2x3和和監(jiān)督元監(jiān)督元x4x5x6x7x4x5x6x7間的監(jiān)督方程組為間的監(jiān)督方程組為：信道編碼信道編碼011110111101A110101111110TA信道編碼信道編碼001110101001111001110G設一信息元組為設一信息元組為m1m2m3=101,則則1001110001 010011100111010011101CMG通過這種方法，能夠計算出所有的碼字通過這種方法，能夠計算出所有的碼字1010011001110101001111001110101 MGC系統(tǒng)碼系統(tǒng)碼信道編碼信道編碼結論：生成矩陣的三行實際上均是碼字。結論：生成矩陣的三行實際上均是碼字。

31、 這三個碼字組成的生成矩陣，能夠使得這三個碼字組成的生成矩陣，能夠使得得出的碼字中，信息元在前，監(jiān)督元在后，得出的碼字中，信息元在前，監(jiān)督元在后，即構成系統(tǒng)碼。即構成系統(tǒng)碼。 如選其他的碼字來構成生成矩陣，得如選其他的碼字來構成生成矩陣，得出的碼字中信息元與監(jiān)督元將是交錯排列，出的碼字中信息元與監(jiān)督元將是交錯排列，稱為非系統(tǒng)碼。稱為非系統(tǒng)碼。如果收到碼字R=1001000，怎么譯碼呢步驟一：檢錯步驟二：糾錯計算HRT=0TR為合法為合法0TR為非法為非法信道編碼信道編碼六：線性分組碼的譯碼（六：線性分組碼的譯碼（P199/p177)1、伴隨式、伴隨式 發(fā)送的碼字是發(fā)送的碼字是C，接受的碼字是，

32、接受的碼字是R E=R+C 成為錯誤圖樣或者差錯序列。成為錯誤圖樣或者差錯序列。 當用監(jiān)督矩陣來校驗接收到的碼字，有當用監(jiān)督矩陣來校驗接收到的碼字，有 TTTTHEHCECHHR)(信道編碼信道編碼由于由于C是一個合法碼字，是一個合法碼字， TTHC0TTTHEHRSS被稱為伴隨式或者校驗子被稱為伴隨式或者校驗子，用它來檢查接收碼字，用它來檢查接收碼字中的錯誤。中的錯誤。 S是校驗矩陣是校驗矩陣H中某幾列數據的線性組合中某幾列數據的線性組合 線性分組碼的基本譯碼步驟線性分組碼的基本譯碼步驟 Step1: 由接收到的序列由接收到的序列R，計算，計算伴隨式伴隨式S=RHT； Step2: 若若S=

33、0，正確接收；若，正確接收；若S不不為零，尋找錯誤圖樣；為零，尋找錯誤圖樣； Step3: 由錯誤圖樣解出碼字由錯誤圖樣解出碼字C=R-E。信道編碼信道編碼2、標準矩陣（、標準矩陣（Standard Array) 設有一個（設有一個（n,k)線性碼，它共有線性碼，它共有2k個碼個碼字字c0，c1，c2.c2k-1 將他們排列。將他們排列。 根據許用碼字將禁用碼字進行分類，根據許用碼字將禁用碼字進行分類， 分類的依據是錯誤圖樣。分類的依據是錯誤圖樣。C0C1C2C3C2k-1伴隨式伴隨式SE2C1+E2C2+E2C3+E2 C2k-1+E2S2E3C1+E3C2+E3C3+E3 C2k-1E3

34、S3. E2n-kC1+E2n-kC2+E2n-kC3+E2n-k C2k-1E2n-kS2r信道編碼信道編碼碼字碼字錯誤錯誤圖樣圖樣陪集陪集首首信道編碼信道編碼標準陣列的構造方法： 1）選擇所用的碼字構成第0行。 2）選擇差錯圖樣作為第0 列。 3）陣列中的I行J列元素為Cj+Ei 信道編碼信道編碼例：畫出標準陣列0110001110001011101001011000H解：1）先計算合法碼字信道編碼信道編碼信息元信息元監(jiān)督元監(jiān)督元編成碼字編成碼字0000000000000000111010011101010011101001110111010011101010011101001110101

35、001110100111101001110100111101001110100合法碼字合法碼字00000001101001 11101000011101 0100111 0111010 1001110 1010011將將合法碼字放在第一行，且全合法碼字放在第一行，且全0碼放在第一列碼放在第一列S(0000）解：1）先計算合法碼字 2）根據伴隨式，計算差錯圖樣S1=0001S2=0010S3=0011S4=0100S5=0101S6=0110S7=0111S8=1000S9=1001S10=1010S11=1011S12=1100S13=1101S14=1110S15=1111S1=0001TT

36、SHE123456701011000011101000110001010110001eeeeeee 1000000E1=0000001S2=0010TTSHE123456701011000011101001110001000110001eeeeeee 1E2=0000010S3=0011TTSHE123456701011000011101001110001010110001eeeeeee 1E3=00000111E3=0100100E3=101000000000001101001 11101000011101 0100111 0111010 1001110 1010011將將合法碼字放在第一行

37、，且全合法碼字放在第一行，且全0碼放在第一列碼放在第一列S(0000）0001000000100100000010001100000110100000010001010110011110001001101010111100110111101111000010000001100100000000100011000000001010000101100011000000100100000010000010100100根據伴隨式的結果根據伴隨式的結果S求解對應的差錯圖樣求解對應的差錯圖樣E將對應行和對應列的進行異或運算將對應行和對應列的進行異或運算00000001101001 111010000111

38、01 0100111 0111010 1001110 1010011S(0000）00111000011110000100000010010000001000110000011010000001000101011001111000100110101011110011011110111100001000000110010000000010001100000000101000010110001100000010010000001000001010010000000001101001 11101000011101 0100111 0111010 1001110 1010011S(0000）00111

39、0000111100001000000100100000010001100000110100000010001010110011110001001101010111100110111101111000010000001100100000000100011000000001010000101100011000000100100000010000010100100譯碼失?。鹤g碼器根據接收到的信號無法作出明確判斷譯碼失?。鹤g碼器根據接收到的信號無法作出明確判斷譯碼失?。鹤g碼器根據接收到的信號無法作出明確判斷譯碼失?。鹤g碼器根據接收到的信號無法作出明確判斷譯碼錯誤：譯碼器根據接收到的信號作出錯誤判斷譯

40、碼錯誤：譯碼器根據接收到的信號作出錯誤判斷不完備譯碼不完備譯碼(p199)完備譯碼：根據接收信號，譯碼器一定能作出是哪完備譯碼：根據接收信號，譯碼器一定能作出是哪 一組信息的判斷一組信息的判斷(p200)信道編碼信道編碼 應當指出，當（n,k)碼的碼長n較大時，即使只存儲陪集首及伴隨式，譯碼器所需內存仍然很大。信道編碼信道編碼七、漢明碼(p205) 定義：能夠糾正一位錯誤的一組線性碼。 二元（n,k,d)漢明碼是一種d=3的完備碼，滿足：123, 12mkmnmm校驗矩陣有校驗矩陣有 m行，行，2m-1列，取互不相同列，取互不相同的的m重構成重構成GF(2)上的7,4,3漢明碼，001,010

41、,011,100,101,110,111,000。校驗矩陣為：101010111001101111000H構造漢明碼的標準陣列信道編碼信道編碼八、由已知碼構造新碼的方法（p210)擴展碼擴展碼刪余碼刪余碼增廣碼增廣碼(增信刪余碼增信刪余碼)增余刪信碼增余刪信碼延長碼延長碼1、擴展碼、擴展碼00111*HHn+1,k,d 或或n+1,k,d+1增加一個全校驗位增加一個全校驗位2、刪余碼、刪余碼(打孔打孔)在原碼基礎上刪去一個校驗元。n-1, k3、增廣碼、增廣碼 在原碼基礎上，增加一個信息元，刪去一個校驗元 n,k+1,dGG111*d*=mind, n-max w( c )iC1CC*ki2,

42、 2 , 14、增余刪信碼、增余刪信碼刪去一個信息元，增加一個校驗元 若若 n n, ,k k, ,d d 碼的最小漢明距離碼的最小漢明距離d d為奇數，為奇數，則挑選所有偶數重量的碼字，即可構成則挑選所有偶數重量的碼字，即可構成 n n, ,k k-1,-1,d d+1+1增余刪信碼增余刪信碼5、延長碼、延長碼對增廣碼再填加一個全校驗位。n+1,k+111nkR信道編碼信道編碼九九 循環(huán)碼循環(huán)碼、 特點: 1)碼的結構參數可以用有限域的代數方法來表示、分析和構造。）利用循環(huán)特性，可以用循環(huán)反饋移位寄存器來構造較為簡單方便的編碼器和譯碼器。信道編碼信道編碼、定義（p215)定義定義1：設CH是

43、一個n.k線性分組碼，C1是其中的一個碼字，若C1的左(右)循環(huán)移位得到的n維向量也是CH中的一個碼字，則稱CH是循環(huán)碼。信道編碼信道編碼nknVV,定義定義2：設：設是是n維空間的一個維空間的一個k維子空間，維子空間，若對任一若對任一knnnVaaa,021,v恒有恒有knnnnVaaaa,10321,v則稱則稱Vn,k為循環(huán)子空間或循環(huán)碼為循環(huán)子空間或循環(huán)碼信道編碼信道編碼3、幾個概念）多項式多項式 f f( (x x)=)=f fn nx xn n+ f+ fn n-1-1x xn n-1-1+ + f+ f1 1x+fx+f0 0其中其中piFf i=0,1,n，該多項式稱為域該多項式

44、稱為域Fp上的多項式上的多項式碼字：碼字：c1=110010碼多項式：碼多項式：5432101( )1*1*0*0*1*0*f xxxxxxx碼字：碼字：c1=110010碼多項式：碼多項式：5432101( )1*1*0*0*1*0*c xxxxxxx碼字：碼字：c2=001010碼多項式：碼多項式：5432102( )0*0*1*0*1*0*c xxxxxxx541( )c xxxx32( )c xxx2)2)多項式次數多項式次數 degdegf f( (x x) ) 系數系數不為零的不為零的x x的最高次數稱為多項式的最高次數稱為多項式f f( (x x) )的的次數次數. .541(

45、)c xxxxdegc1(x)=532( )cxxxdegc2(x)=?3)3)首一多項式首一多項式 最高次數的系數為最高次數的系數為1 1的多項式的多項式541( )c xxxx32( )cxxx都是首一多項式都是首一多項式信道編碼信道編碼4) 既約多項式既約多項式 設f(x)是次數大于零的多項式，若除常數和常數與本身的乘積以外，再不能被域Fp上的其他多項式整除，則稱f(x)為域Fp上的既約多項式 多項式的因式分解問題、根的問題323( )1c xxx5)多項式加法（多項式加法（p213）)f(x)=fnxn+ fn-1xn-1+ f1x+f0piFf g g( (x x)=)=g gn n

46、x xn n+ g+ gn n-1-1x xn n-1-1+ + g+ g1 1x+gx+g0 0piFg f(x)+ g(x）=（fn+gn）xn+ （fn-1+ gn-1）xn-1+ （f1+ g1）x+（f0+g0）541( )c xxxx32( )cxxx54312c ( )( )xcxxxx6)多項式多項式相等相等（p213）)f(x)=fnxn+ fn-1xn-1+ f1x+f0piFf g g( (x x)=)=g gn nx xn n+ g+ gn n-1-1x xn n-1-1+ + g+ g1 1x+gx+g0 0若對所有若對所有i, fi=gi, 則則f(x)=g(x）)

47、piFg 7)多項式同余（多項式同余（長除法）長除法）類比：類比：8和和5對對3同余同余數的同余數的同余f1(x)和和f2(x)同處以同處以f3(x),余式相等余式相等f1(x)和和f2(x)對對f3(x)多項式多項式的同余的同余1111735673567xxxxxxxxx上面兩個多項式對上面兩個多項式對x7+1同余同余）剩余類）剩余類(Residue)： 給定給定正整數正整數mm，可將全體整數按余數相同進，可將全體整數按余數相同進行分類，可獲得行分類，可獲得mm個剩余類，分別用個剩余類，分別用1, 1 , 0m ExamplesExamples 1 1、GF(2)GF(2)上的多項式上的多項

48、式 f f( (x x)=)=x x2 2+1+1的剩余類全體的剩余類全體為：為： 1, 1 , 0 xx信道編碼信道編碼問題一如何尋找k維循環(huán)子空間？如何設計n,k循環(huán)碼？ 利用多項式和有限域的概念利用多項式和有限域的概念信道編碼信道編碼問題一轉化為如何從模多項式xn-1的剩余類結合代數中尋找循環(huán)子空間？如何尋找生成多項式g(x)？循環(huán)碼模多項式模多項式x xn n-1-1剩余類線性結合代數中的理剩余類線性結合代數中的理想想生成多項式生成多項式信道編碼信道編碼）生成多項式）生成多項式定理定理1 (p215) :GF(q)(q為素數或素數的冪為素數或素數的冪)上的上的n,k循環(huán)碼中，存在唯一的

49、循環(huán)碼中，存在唯一的n-k次首次首一多項式一多項式g(x)，每一個碼多項式，每一個碼多項式C(x)必是必是g(x)的倍式，每一個小于等于的倍式，每一個小于等于(n-1)次的次的g(x)的倍式一定是碼多項式的倍式一定是碼多項式001011101011101011100G信息元信息元碼字碼字000000000000100101110100101110011011100110010111001011001011110111001011111001010000000，0010111，0101110，0111001,1011100，1001011，1110010，11001010000000，00101

50、11，010111，0111001,1011100，1001011，1110010，1100101001011101011101011100Gg(x)=x4+x2+x+1信道編碼信道編碼定理定理2(p216):GF(q)(q為素數或素數的冪)上n,k循環(huán)碼的生成多項式g(x)一定是xn+1的n-k次因式： xn+1= g(x) h(x)。 反之，若g(x)為n-k次多項式，且xn+1能被g(x)整除，則g(x)一定能生成一個n,k循環(huán)碼信道編碼信道編碼兩個結論 結論結論1:1:找一個找一個 n n, ,k k 循環(huán)碼，即是找一個循環(huán)碼，即是找一個n n- -k k次首一多項式次首一多項式g g

51、( (x x) )，且，且g g( (x x) )必是必是x xn n+1+1的因式的因式。結論結論2:若若C(x)是一個碼多項式，則是一個碼多項式，則 反之，若反之，若則則C(x)必是一個碼多項式必是一個碼多項式 0 )(xgxC 0 )(xgxC信道編碼信道編碼Examples GF(2)上，x7+1=(x+1)(x3+x+1)(x3+x2+1) 試求一個7,4循環(huán)碼。g(x)、 xg(x)、x2 g(x)、 x3g(x)、 011gxgxgxgknknknkn 011hxhxhxhkkkk +1nxg x h xg(x)決定生成矩陣，決定生成矩陣，h(x)決定校驗矩陣決定校驗矩陣、循環(huán)碼

52、的生成矩陣和校驗矩陣、循環(huán)碼的生成矩陣和校驗矩陣 xgxgxxgxkk,21nkknknknknknkngggggggggggggG01210110110000000kkkhxhxhxh110*)( xhxhxxhxknkn*2*1,nknkkkkkkkhhhhhhhhhhhhh12101101100000000H循環(huán)碼的編碼原理循環(huán)碼的編碼原理基本步驟基本步驟(n,k) 1、分解多項式、分解多項式xn-1=g(x)h(x）2、選擇其中的、選擇其中的n-k次多項式次多項式g(x)為生成多項式為生成多項式3、由、由g(x)可得到可得到k個多項式個多項式g(x), xg(x),xk-1g(x)4、

53、取上述、取上述k個多項式的系數即可構成相應的生成矩陣個多項式的系數即可構成相應的生成矩陣信道編碼信道編碼5 系統(tǒng)循環(huán)碼 模模g(x)的除法問題的除法問題K位信息元位信息元K位信息元位信息元r位監(jiān)督元位監(jiān)督元x0 xk-1x0* xrxk-1* xrx0 xr-1m(x)c(x)c(x)=m(x)* xr+r(x)結論結論2:若若C(x)是一個碼多項式，則是一個碼多項式，則 反之，反之， 若若則則C(x)必是一個碼多項式必是一個碼多項式 0 )(xgxC 0 )(xgxCc(x)=m(x)* xr+r(x) 0 )(xgxC xgxrxxmxCknmod0 xgxxmxxmxCxrknknmod

54、m(x)是消息多項式是消息多項式信道編碼信道編碼循環(huán)碼的系統(tǒng)碼構造的步驟為： 1）消息多項式乘x n-k 2) x n-km(x)/g(x)=q(x) +r(x)/g(x) 其中：q(x)是商，r(x)是余式 3）C(x)= x n-km(x)+r(x)信道編碼信道編碼例：信息元m=1101 g(x)=1+x+x3 x n-km(x)=x3(x3+x2+1)信道編碼信道編碼1111233324234235453463563xxxxxxxxxxxxxxxxxxxxxxxxxxr(x)=1C(x)= x x n-kn-km(x)+r(x)m(x)+r(x) =x =x6 6+x+x5 5+x+x3

55、 3+1+1所以，碼字所以，碼字是是11010011101001b0b1b2br-2b1br-1b1br輸出輸出C(x)輸入輸入A(x)a0,a1,ak 乘乘B(x)運算電路運算電路(利用校驗多項式利用校驗多項式h(x)編碼時會用到編碼時會用到)6、多項式的乘法電路（、多項式的乘法電路（p222)b0b1b2br-2b1br-1b1br輸出輸出C(x)輸入輸入A(x)a0,a1,ak乘乘B(x)運算電路運算電路akb0akb1akbr-2akbr-16、多項式的乘法電路（、多項式的乘法電路（p222)h0h1h2hr-2b1hr-1b1hr輸入輸入A(x)a0,a1,ak-g1gr-1輸出商輸

56、出商q(x)-g2-g0-gr-1-gr-1乘乘H(x),除除g(x)運算電路運算電路7、多項式的除法電路（、多項式的除法電路（p225)縮減信源循環(huán)碼（縮減信源循環(huán)碼（n-I,k-I),循環(huán)碼編碼電路g0g1g2gn-k-2b1gn-k-1b1gn-k輸出輸出C(x)輸入輸入m(x)m0,m1,mk乘乘g(x)運算電路運算電路mk-1 gn-k-1mk-1 gn-k輸入輸入m(x)是信息序列，是信息序列，g(x)為生成多項式為生成多項式mk-1 g0mk-1 g1循環(huán)碼編碼電路（循環(huán)碼編碼電路（p225)p225)信道編碼信道編碼十、BCH碼(p230) 能糾正多位錯誤的循環(huán)碼。 碼長：n=

57、2m-1監(jiān)督元位數：n-k=2t+1信道編碼信道編碼十一：卷積碼（Convolutional Code）Encoding：1955，EliasDecoding：Threshold Decoding Massey(1963) List Decoding Wozencraft(1961) Viterbi Decoding Viterbi (1967)信道編碼信道編碼編碼約束度 N=m+1 （m編碼的存儲級數）編碼約束比特長度 NA=n*N編碼速率 k/n k輸入的數據比特，n輸出比特數。1、幾個基本概念、幾個基本概念(p234)信道編碼信道編碼2、編碼電路mipi2pi1輸入輸入D1D2(3,1,

58、2) 卷積編碼器卷積編碼器mi信道編碼信道編碼3、監(jiān)督矩陣監(jiān)督方程組：2211iiiiiimmpmmp信道編碼信道編碼輸入信息元：輸出碼字：Ci，Ci+1等稱為子碼。NoImage.21iiimmmCi.1 , 21 , 222, 11 , 1121iiiiiiiiippmppmppmCi+1Ci+2信道編碼信道編碼各子碼之間的關系：(m+1)*nC2C0C1 C3C2C1 C4C3C2 C5C4C3 C6C5C4 信道編碼信道編碼2211iiiiiimmpmmp轉化為：轉化為：0*0,*1*1*0*0*1*0*0*02 ,12 , 11 , 112 , 21 , 22iiiiiiiiiPPmPPmPPm0*1,*0*1*0*0*0*0*0*12 ,12 , 11 , 112 , 21 , 22iiiiiiiiiPPmPPmPPmCiCiCi信道編碼信道編碼寫成矩陣的形式： TTC0H0100000101