1、第十一章 差錯控制編碼和線性分組碼,主要內容和重點,差錯控制編碼的基本概念 線性分組碼 性質、基本原理 校正子 監(jiān)督矩陣 生成矩陣 漢明碼 循環(huán)碼 概念及性質 生成多項式 生成矩陣與監(jiān)督矩陣 編碼器,2.1 引言,什么是差錯控制編碼（信道編碼）？ 為什么要引入差錯控制編碼？ 差錯控制編碼的3種方式？ 信道發(fā)生差錯的幾種模式 差錯控制編碼的基本原理 差錯控制編碼的分類 編碼信道及香農(nóng)編碼定理,2.1 引言,什么是差錯控制編碼 在實際信道上傳輸數(shù)字信號時，由于信道傳輸特性不理想及加性噪聲的影響，接收端所收到的數(shù)字信號不可避免地會發(fā)生錯誤 為了在已知信噪比情況下達到一定的誤比特率指標，應該合理設計基

2、帶信號，選擇調制解調方式，采用時域、頻域均衡，使誤比特率盡可能降低 但若誤比特率仍不能滿足要求，則必須采用信道編碼（即差錯控制編碼），將誤比特率進一步降低,2.1 引言,什么是差錯控制編碼（續(xù)） 差錯控制編碼的基本思路： 在發(fā)送端將被傳輸?shù)男畔⒏缴弦恍┍O(jiān)督碼元，這些多余的碼元與信息碼元之間以某種確定的規(guī)則相互關聯(lián)（約束） 接收端按照既定的規(guī)則校驗信息碼元與監(jiān)督碼元之間的關系，一旦傳輸發(fā)生差錯，則信息碼元與監(jiān)督碼元的關系就受到破壞，從而接收端可以發(fā)現(xiàn)錯誤乃至糾正錯誤 差錯控制編碼所要解決的問題：各種編碼和譯碼方法,2.1 引言,差錯控制的三種方式 檢錯重發(fā)（ARQ） 在接收端根據(jù)編碼規(guī)則進行檢查

3、，如果發(fā)現(xiàn)規(guī)則被破壞，則通過反向信道要求發(fā)送端重新發(fā)送，直到接收端檢查無誤為止 ARQ系統(tǒng)的重發(fā)機制：停發(fā)等候重發(fā)、返回重發(fā)和選擇重發(fā) 需要反饋信道，效率較低，但是性能很好,2.1 引言,差錯控制的三種方式（續(xù)） 前向糾錯（FEC） 發(fā)送端發(fā)送能糾正錯誤的編碼，在接收端根據(jù)接收到的碼和編碼規(guī)則，能自動糾正傳輸中的錯誤 不需要反饋信道，實時性好，但是隨著糾錯能力的提高，編譯碼設備復雜,2.1 引言,差錯控制的三種方式（續(xù)） 混合方式 結合FEC和ARQ：在糾錯能力范圍內，自動糾正錯誤，超出糾錯范圍則要求發(fā)送端重新發(fā)送,2.1 引言,信道發(fā)生差錯的幾種模式 隨機差錯： 差錯的出現(xiàn)是隨機的，差錯出現(xiàn)

4、的位置是隨機分布的 一般由信道的加性隨機噪聲引起 這種信道稱為隨機信道 突發(fā)差錯： 差錯的出現(xiàn)是一連串出現(xiàn)的。這種情況如移動通信中信號在某一段時間內發(fā)生衰落，造成一串差錯；光盤上的一條劃痕等等 這樣的信道稱之為突發(fā)信道 混合差錯： 既有突發(fā)錯誤又有隨機差錯的情況 這種信道稱之為混合信道,2.1 引言,差錯控制編碼的基本原理 以差錯重發(fā)編碼來闡述差錯編碼在相同的信噪比情況下為什么會獲得更好的系統(tǒng)性能？ 例1：假設發(fā)送的信息0、1等概，采用2PSK方式，則最佳接收的系統(tǒng)誤比特率為 ，現(xiàn)假設 如果將信息0編碼成00，信息1編碼成11，則在接收端： 如果發(fā)送00，收到01、10，知道發(fā)生了差錯，要求發(fā)

5、送端重新傳輸，直到傳送正確為止 只有當收到11時，我們才錯誤地認為當前發(fā)送的是1 因此在這種情況下發(fā)生譯碼錯誤的概率是 同理，如果發(fā)送的是11，只有收到00時才可能發(fā)生錯誤譯碼，因此在這種情況下發(fā)生譯碼錯誤的概率是 故采用00、11編碼的系統(tǒng)誤比特率為,2.1 引言,差錯控制編碼的基本原理（續(xù)） 依此類推，可知： 采用000、111編碼的ARQ系統(tǒng)誤比特率是多少？ 采用0000、1111編碼的ARQ系統(tǒng)誤比特率是多少？ 例2，如例1，如果0、1采用00000、11111編碼，在接收端用如下的譯碼方法，每收到5個比特譯碼一次，采用大數(shù)判決，即5個比特中0的個數(shù)大于1的個數(shù)則譯碼成0，反之譯碼成1

6、；不采用ARQ方式。那么，這種編碼方式就變成了糾錯編碼 由于傳輸錯誤當接收端收到11000，10100，10010，10001，01100，01010，01001，00110，00101，00011中的任何一種時，都可以自動糾正成00000 課外題：請計算在這種情況下的系統(tǒng)性能,2.1 引言,差錯控制編碼的基本原理（續(xù)） 例3，2PSK系統(tǒng)中誤比特率與Es/N0有關 上述例1、例2的編碼方式叫重復碼 我們看到，重復碼中假設傳輸時每個符號的Es/N0相等，因此才得到以上的性能分析對比 但是如果我們以Eb/N0的指標進行比較，則我們看到 例1的 例2的 如果要求各系統(tǒng)在Eb/N0相同的情況下進行比

7、較（n重復碼中用了n倍能量來傳輸一個比特，從每個比特能量的角度來看），則可看到這2種系統(tǒng)性能相近（即獲得相近的編碼增益）,2.1 引言,差錯控制編碼的基本原理（續(xù)） 當x1有 2PSK系統(tǒng)： 2重重復碼： 編碼增益=,2.1 引言,差錯控制編碼的分類 根據(jù)差錯控制編碼的功能不同： 檢錯碼、糾錯碼、糾刪碼（兼檢錯、糾錯） 根據(jù)信息位和校驗位的檢驗關系： 線性碼（存在線性關系）和非線性碼 按信息碼元在編碼后是否保持原來的形式 系統(tǒng)碼：保持不變 非系統(tǒng)碼：信息碼元改變了原有的信號形式 按糾正錯誤的類型： 糾正隨機錯誤的碼：用于隨機錯誤的信道 糾正突發(fā)錯誤的碼：用于突發(fā)信道,2.1 引言,差錯控制編碼

8、的分類（續(xù)） 根據(jù)信息碼元和監(jiān)督碼元的約束方式： 分組碼：監(jiān)督碼元僅與本碼組的信息碼元有關 卷積碼：監(jiān)督碼元還與前面碼組的信息碼元有約束關系 分組碼：將k個信息比特編成n個比特的碼字，共有2k個碼字。所有個碼字組成一個分組碼。傳輸時前后碼字之間毫無關系 卷積碼：也是將k個信息比特編成n個比特的碼字，但是前后的N個碼字之間相互關聯(lián) 編碼速率=平均每個碼字所攜帶的信息比特率,2.1 引言,編碼信道 所謂的編碼信道就是將調制解調包括在信道內的一種模型上的等效。 即如果研究編碼和譯碼，完全可以將調制、解調與信道合起來等效成一個等效的信道，這種信道就稱之為編碼信道,2.1 引言,編碼信道（續(xù)） 根據(jù)調制

9、解調的不同輸入和輸出具有不同的類型 離散無記憶對稱二進制輸入二進制輸出信道（BSC） 這種情況相應于2進制調制解調+判決 離散無記憶二進制輸入多進制輸出信道 對應于2進制輸入，量化后輸出的情況，即所謂的軟譯碼 離散無記憶多進制輸入多進制輸出 對應于多進制輸入、量化后輸出 離散無記憶二進制輸入連續(xù)輸出 對應于二進制輸入，模擬輸出（未判決、未量化）,2.1 引言,香農(nóng)有擾離散信道的編碼定理 對于一個給定的有擾信道，若信道的容量為C，只要發(fā)送端以低于C的速率R發(fā)送信息（R為編碼器的輸入二進制碼元速率），則一定存在一種編碼方法，使編碼錯誤概率P隨著碼長n的增加，按指數(shù)下降到任意小的值，表示為 其中E(

10、R)稱為誤差指數(shù) 結論： n和R一定情況下，為減小P，可增大C 在C及R一定的情況下，增加n，可以 使P指數(shù)下降。從實際的角度看，這時 設備復雜性和譯碼延時也隨之增加,E（R） C 0 C1 C2 R,2.2 糾錯編碼的基本原理,主要內容 碼重、碼距 最小碼距 碼的糾錯、檢錯性能,2.2 糾錯編碼的基本原理,分組碼將k個比特編成n個比特一組的碼字（碼組），記為（n，k）碼 由于輸入有 2k種組合，因此（n，k）碼應該有2k個碼字 碼重、碼距 碼重：碼字中1的個數(shù)。如碼字11000的碼重為2 碼距：碼字C1與碼字C2之間不同的比特數(shù)（又稱漢明距）,2.2 糾錯編碼的基本原理,最小碼距 所用碼字中

11、任何兩個碼字之間的碼距的最小值，用 dmin表示 碼的糾錯、檢錯性能：由最小碼距決定 為了檢測e個錯誤，要求最小碼距 為了糾正t個錯誤，要求最小碼距 為了糾正t個錯誤，同時檢測e個錯誤，要求最小碼距,糾錯碼的抗干擾能力完全取決于許用碼字之間的距離，碼的最小距離越大，說明碼字間的最小差別越大，抗干擾能力就越強。,2.3 常用的簡單編碼,奇偶監(jiān)督碼（奇偶校驗） 可以表示成為（n，n-1）。如果是奇監(jiān)督碼，在附加上一個監(jiān)督元以后，碼長為n的碼字中“1”的個數(shù)為奇數(shù)個；如果是偶監(jiān)督碼，在附加上一個監(jiān)督元以后，碼長為n的碼字中“1”的個數(shù)為偶數(shù)個。 設奇偶監(jiān)督碼的碼字表示為： 則偶校驗碼： （即偶數(shù)個1

12、） 奇校驗碼： （即奇數(shù)個1） 可見這種碼的最小碼距為2，只能檢1個錯,奇偶監(jiān)督碼的編碼可以用軟件實現(xiàn)，也可用硬件電路實現(xiàn)。 如果碼組B無錯，BA，則M0；如果碼組B有單個（或奇數(shù)個）錯誤，則M1。,2.3 常用的簡單編碼,二維奇偶監(jiān)督碼 提高奇偶校驗碼對突發(fā)錯誤的檢測能力 將若干奇偶校驗碼排成若干行，然后對每列進行奇偶校驗，放在最后一行。傳輸時按照列順序進行傳輸，在接收端又按照行的順序檢驗是否差錯 由于突發(fā)錯誤是成串發(fā)生的，經(jīng)過傳輸后錯誤被分散（交織編碼+奇偶校驗） 移動通信中的信道衰落造成突發(fā)錯誤，因此傳輸前，先將輸入的信息比特交織，將突發(fā)錯誤盡可能分散成隨機錯誤，然后用其它編碼方式來糾正

13、隨機的錯誤,2.3 常用的簡單編碼,恒比碼 每個碼組中的1的個數(shù)都一樣 電傳機傳輸漢字時每個漢字用4位阿拉伯數(shù)字表示，每個阿拉伯數(shù)字用5個比特的碼字表示。由于阿拉伯數(shù)字只有10個，因此從32中可能的碼字中挑出 =10個1的個數(shù)為3的碼字作為阿拉伯數(shù)字的編碼方式 譯碼可以采用查表方法，檢錯時檢查1的個數(shù)是否為3 一般用在電傳、電報,2.3 常用的簡單編碼,ISBN國際統(tǒng)一圖書編號 國際圖書的發(fā)行中，用編碼的方式來防止書號在通信過程中發(fā)生錯誤 如通信原理的書號是ISBN 7-118-01429-X 其中第一位數(shù)字“7”表示“中國”，“118”表示出版社，“01429”表示書名編號，最后一位“X”表

14、示校驗位（它是羅馬數(shù)字10的表示） 所采用的校驗方式如下所示： 7 1 1 8 0 1 4 2 9 X=10 7 8 9 17 17 18 22 24 33 43 7 15 24 41 58 76 98 122 155 198 198 (模11)=0,2.4 線性分組碼,差錯編碼的重點：各種編碼和譯碼的方法 主要內容 性質 基本原理 校驗矩陣（監(jiān)督矩陣） 生成矩陣 校正子（伴隨式） 漢明碼,2.4 線性分組碼,定義： 將信息碼分組，為每組信息位附加若干監(jiān)督位，且信息位和監(jiān)督位間的關系可由線性方程組表示的編碼 即可用線性方程組表述碼的規(guī)律性的分組碼 線性分組碼（n，k）的性質 許用碼字（組）為2

15、k個 定義線性分組碼的加法為模2加，乘法為二進制乘法。即有 1+1=0、1+0=1、0+1=1、0+0=0 1x1 = 1, 1x 0 =0, 0 x0 =0, 0 x1 =0 且碼字與碼字的運算是各相應比特位上符合上述二進制加法運算規(guī)則,2.4 線性分組碼,線性分組碼（n，k）的性質（續(xù)） 群：集合G上定義了一種加法運算，如果該運算符合以下4條公理，則稱G是該運算的一個群 封閉性：任何a、b屬于G，有a*b屬于G 單位元：G中存在一個元素e滿足e*a=a 有逆元：任何a屬于G，存在b屬于G滿足a*b=e 結合率成立：a*(b*c)=(a*b)*c 線性分組碼的性質： 封閉性。任意兩個許用碼組

16、的和仍是一個許用碼組 最小碼距等于非零碼的最小碼重,2.4 線性分組碼,基本原理 (n, k)碼：碼長n，信息位數(shù)為k，則監(jiān)督位數(shù)r=n-k 校正子（伴隨式）S：為了檢測傳輸過程中是否有錯，將接收到的碼組代入監(jiān)督方程式所得到的結果 以（7，4）線性分組碼為例，說明（n，k）碼的基本原理 7碼元a6a5a4a3a2a1a0，信息碼元a6a5a4a3，監(jiān)督碼元a2a1a0 校正子S1S2S3與信息碼元及監(jiān)督碼元之間的關系為,2.4 線性分組碼,基本原理（續(xù)） 3個校正子可以指示23-1=7種錯誤圖樣，如表所示 可知，（7，4）碼可糾正一位錯誤 在編碼時a2a1a0應根據(jù)監(jiān)督方程確定：,2.4 線性

17、分組碼,基本原理（續(xù)） 由此可得16個許用碼組,2.4 線性分組碼,基本原理（續(xù)） 接收端收到每個碼組后，計算出S1、S2和S3，如不全為0，則查表確定誤碼的位置，予以糾正 如，接收碼組為0000011，可算得S1S2S3011，查表知a3錯 （7，4）碼：dmin=3，能糾正1個誤碼或檢測2個誤碼 (n, k)線性分組碼： r=n-k個監(jiān)督碼元，有r個校正子，可以指示2r-1個誤碼圖樣 當2r-1n（即2rk+r+1）時，就可糾正1位或1位以上的錯誤 編碼效率（編碼速率）：k/n=(2r-r-1)/(2r-1)=1-r/n,2.4 線性分組碼,校驗矩陣（監(jiān)督矩陣） 監(jiān)督碼元與信息碼元之間的關

18、系可表示為監(jiān)督方程形式，上例（7，4）碼的監(jiān)督方程為 簡記為 HAT0T 或 AHT0,2.4 線性分組碼,校驗矩陣（監(jiān)督矩陣）（續(xù)） 稱H為監(jiān)督矩陣 設收到的碼組為B，則校正子SHBT 故可根據(jù)H及誤碼圖樣表構成差錯控制譯碼器 典型形式監(jiān)督矩陣 HP Ir 其中，P為rk階矩陣，Ir為rr階單位方陣 各行線性無關 非典型形式監(jiān)督矩陣可以經(jīng)過行運算化為典型形式 由典型形式監(jiān)督矩陣及信息碼元可算出各監(jiān)督碼元,2.4 線性分組碼,生成矩陣 監(jiān)督碼元與信息碼元之間的關系還可表示為生成方程形式 上述（7，4）碼的生成方程為 稱G為生成矩陣，由生成矩陣G可構造差錯控制編碼器,2.4 線性分組碼,生成矩陣

19、（續(xù)） 典型生成矩陣G GIk Q 其中，QPT為kr階矩陣，Ik為kk階單位方陣 PQT 由典型生成矩陣G可以得到系統(tǒng)碼 各行線性無關 非典型形式生成矩陣可以經(jīng)過行運算化為典型形式,2.4 線性分組碼,校正子（伴隨式） 發(fā)送碼組A在傳輸過程中可能發(fā)生誤碼 設接收到的碼組為Bbn-1 bn-2 b0 則錯誤圖樣 E=B-A，或 B=A+E 其中，E= en-1 en-2 e0 校正子為 S=BHT=(A+E)HT=AHT+EHT=EHT S與E間有確定的關系,2.4 線性分組碼,漢明碼 上述方法構造的糾正單個錯誤的線性分組碼 特點 碼長：n2m1 信息碼位：k=2m-m-1 監(jiān)督碼位：r=n-

20、k=m 最小碼距：d=3 糾錯能力：t=1,2.5 循環(huán)碼,概念、性質和多項式表示 生成多項式 生成矩陣與監(jiān)督矩陣 編碼器,2.5 循環(huán)碼,概念及性質 線性分組碼中最重要的一種子類，比較成熟 特點 代數(shù)結構清晰：有嚴格的代數(shù)理論基礎 性能較好：可糾隨機錯誤和突發(fā)錯誤 編譯碼簡單：特殊的代數(shù)性質有助于按照要求的糾錯能力構造，并且簡化譯碼算法 易于實現(xiàn)：很容易用帶反饋的移位寄存器實現(xiàn) 目前的計算機糾錯系統(tǒng)中廣泛使用的線性分組碼,如 是循環(huán)碼的一許用碼組 則 也是一許用碼組,2.5 循環(huán)碼,概念及性質（續(xù)） 例：設（7，4）漢明碼C的校驗矩陣和生成矩陣為 得到16個碼組是： （1000101）（00

21、01011）（0010110）（0101100） （1011000）（0110001）（1100010） （0100111）（1001110）（0011101）（0111010） （1110100）（1101001）（1010011） （1111111）（0000000） 可以看到：如果Ci是C的碼組，則它的左右移位都是C的碼組，具有這種特性的線性分組碼稱為循環(huán)碼,2.5 循環(huán)碼,概念及性質（續(xù)） 循環(huán)碼的性質： 封閉性 任何許用碼組的線性和還是許用碼組。由此性質可以得到：線性碼都包含全零碼 最小碼重就是最小碼距 循環(huán)性 任何許用的碼組循環(huán)移位后的碼組還是許用碼組,2.5 循環(huán)碼,概念及性質（

22、續(xù)） 多項式表示： 目的：用代數(shù)理論的方法研究循環(huán)碼的特性 定義：碼 的碼多項式如下 其中，D為實變量、其冪次代表移位次數(shù)， GF（2）表示2元域，只有兩種元素0、1，且0、1滿足如下的運算規(guī)則： 0+0=0，0+1=1，1+0=1，1+1=0 （加法） 0 x0=0，0 x1=0，1x0=0，1x1=1。 （乘法） 例如：（1011000）的碼多項式為,左移一位 左移 位,若 是長度為n的循環(huán)碼組，則 在按模 進行運算后，也是一個循環(huán)碼組，也就是 用 多項式除后所得之余式，即為所求的碼組。,2.5 循環(huán)碼,生成多項式 循環(huán)碼完全由其碼長n和生成多項式g（D）構成 其中g（D）是一個能除盡Dn

23、+1的r=n-k階多項式 階數(shù)低于n并能被g（D）除盡的一組碼多項式就構成一個（n，k）循環(huán)碼 即階數(shù)小于或等于n-1且能被g（D）除盡的每個多項式都是循環(huán)碼的許用碼組 信息多項式為M(D),k 位，(k-1)次多項式,2.5 循環(huán)碼,生成多項式（續(xù)） 例如，（7，4）循環(huán)碼的生成多項式 則階數(shù)低于n-1能被g（D）除盡的多項式為 其中 ，i=0，1，2，3 假設 則對應的循環(huán)碼多項式為 故對應的循環(huán)碼組為（1111111）,2.5 循環(huán)碼,生成多項式的構造 循環(huán)碼多項式表示及循環(huán)性質 循環(huán)碼中任何碼組的循環(huán)移位還是許用碼組，可以表示成碼多項式的形式 定理一：碼組 ，經(jīng)過移位i位，得到碼組 則

24、可以證明： 即 證明： 利用多項式的長除法：可以得證,2.5 循環(huán)碼,生成多項式的構造（續(xù)） 循環(huán)碼多項式表示及循環(huán)性質 例：（7，4）循環(huán)碼（1000101）的碼多項式為 移位1位后變成 將它被 除，得到 因此，循環(huán)左移一位的余式為 其相對應的碼組為（0001011），正好是（1000101）循環(huán)左移一位的結果,2.5 循環(huán)碼,生成多項式的構造（續(xù)） 循環(huán)碼多項式的構造 定理二：（n，k）循環(huán)碼的生成多項式g(D)一定是Dn+1的因式，即 反之，如果g(D)是一個n-k次多項式，且除盡Dn+1 ， 則此g(D)一定生成一個（n，k）循環(huán)碼 證明：循環(huán)碼的碼組T（D）是g（D）的倍式，因此 而

25、生成多項式g(D)本身也是一個碼組，該碼組的多項式次數(shù)為n-k次 由定理一，可以知道 也是循環(huán)碼組 而 所以， 即g（D）是Dn+1的因式 因式分解可以通過計算機分解的方式分解，也可以通過查表（已經(jīng)作好的因式分解表）得到,2.5 循環(huán)碼,生成多項式的構造（續(xù)） 循環(huán)碼多項式的構造 例， 因此，（7，4）循環(huán)碼的生成多項式可以選擇 或 而（7，3）循環(huán)碼的生成多項式可以選擇 或 練習：請驗證以下結論 （7，6）循環(huán)碼的生成多項式為D+1，實際上就是簡單的偶校驗碼 （7，1）循環(huán)碼的生成多項式為 ，實際上是7重重復碼,2.5 循環(huán)碼,生成矩陣 根據(jù) 循環(huán)碼的碼組多項式是生成多項式g（D）的倍式 根

26、據(jù)線性碼的生成矩陣的特性，（n，k）碼的生成矩陣實際上可以由（n，k）碼中k個不相關的碼組構成 可以挑選出k個循環(huán)碼組的碼多項式形成 非系統(tǒng)碼的生成矩陣 系統(tǒng)碼的生成矩陣,2.5 循環(huán)碼,生成矩陣 非系統(tǒng)碼的生成矩陣 輸入信息碼元為 時， 相應的循環(huán)碼組多項式為： 由上式得到的碼組不是系統(tǒng)碼,2.5 循環(huán)碼,生成矩陣 非系統(tǒng)碼的生成矩陣（續(xù)） 例：已知（7，4）循環(huán)碼的生成多項式為 求生成矩陣 解： 所以，,2.5 循環(huán)碼,生成矩陣 系統(tǒng)碼的生成矩陣 系統(tǒng)碼定義：（n，k）系統(tǒng)碼的碼組中前k個比特是信息比特，后n-k個比特是監(jiān)督位 問題：已知生成多項式g（D），如何構造系統(tǒng)碼的生成矩陣？ 在系統(tǒng)碼中，碼組應該具備如下的形式： 其中，r（D）的次數(shù)小于等于n-k-1 實際上上式表示了如何生成系統(tǒng)碼，即 將信息碼多項式升n-k次，然后以g（D）為模，求出余式r（D）,2.5 循環(huán)碼,生成矩陣 系統(tǒng)碼的生成矩陣 例： 已知（7，4）系統(tǒng)循環(huán)碼的生成多項式為 求生成矩陣 解：系統(tǒng)碼的生成矩陣形式肯定是 因此選擇信息多項式為 、1 將D3提升n-k=3次，得到D6 ，求D6除以g（D）的余式得到 因此，系統(tǒng)生成矩陣