1、第八章 線性分組碼第八章第八章 線性分組碼線性分組碼內容提要內容提要目前，幾乎所有得到實際應用的糾錯碼都是線目前，幾乎所有得到實際應用的糾錯碼都是線性的。本章首先介紹有關糾錯碼的基本概念，性的。本章首先介紹有關糾錯碼的基本概念，然后重點論述線性分組碼的定義及其編譯碼理然后重點論述線性分組碼的定義及其編譯碼理論。在此基礎上，介紹了一種典型的線性分組論。在此基礎上，介紹了一種典型的線性分組碼：漢明碼。碼：漢明碼。 8.1 8.1 糾錯碼的基本概念糾錯碼的基本概念 8.1.1 信道糾錯編碼信道糾錯編碼 l l信源編碼的目的是壓縮冗余度，提高信息的傳輸速率。信源編碼的目的是壓縮冗余度，提高信息的傳輸速

2、率。l l信道編碼的目的是提高信息傳輸時的抗干擾能力以增信道編碼的目的是提高信息傳輸時的抗干擾能力以增加信息傳輸的可靠性。加信息傳輸的可靠性。8.1.2 差錯控制系統模型及分類差錯控制系統模型及分類 信息傳輸系統模型簡化成圖信息傳輸系統模型簡化成圖8.1所示的簡化模型所示的簡化模型圖圖8.1 8.1 簡化的信息傳輸系統模型簡化的信息傳輸系統模型 模型突出了以控制差錯為目的的糾錯碼編碼器和譯碼器，模型突出了以控制差錯為目的的糾錯碼編碼器和譯碼器，因此也稱為差錯控制系統。因此也稱為差錯控制系統。在差錯控制系統中使用的碼按其糾錯能力的不同可分為兩在差錯控制系統中使用的碼按其糾錯能力的不同可分為兩種：

3、種：檢錯碼檢錯碼和和糾錯碼糾錯碼。 能發現錯誤但不能糾能發現錯誤但不能糾正錯誤的碼稱為檢錯碼正錯誤的碼稱為檢錯碼 ； 不僅能發不僅能發現錯誤而且還現錯誤而且還能糾正錯誤的能糾正錯誤的碼稱為糾錯碼。碼稱為糾錯碼。（）前向糾錯（）前向糾錯(FEC)方式方式 ： FEC (Forward Error Control) 方式是發端發送有糾錯方式是發端發送有糾錯能力的碼（糾錯碼），接收端收到這些碼后，通過糾錯譯能力的碼（糾錯碼），接收端收到這些碼后，通過糾錯譯碼器自動地糾正傳輸中的錯誤。碼器自動地糾正傳輸中的錯誤。 差錯控制系統大致可分為前向糾錯、重傳反饋和混合糾錯差錯控制系統大致可分為前向糾錯、重傳反

4、饋和混合糾錯等三種方式。等三種方式。l l優點優點: :是不需要反饋是不需要反饋信道；能進行一個用信道；能進行一個用戶對多個用戶的同時戶對多個用戶的同時通信，特別適合于移通信，特別適合于移動通信；譯碼實時性動通信；譯碼實時性較好，控制電路也比較好，控制電路也比較簡單。較簡單。 l l缺點是譯碼設缺點是譯碼設備較復雜；編碼備較復雜；編碼效率較低。效率較低。（）重傳反饋（）重傳反饋(ARQ)方式方式: ARQ (Automatic Repeat Request) 方式是：發端發出方式是：發端發出能夠發現錯誤的碼（檢錯碼），收端譯碼器收到后，判斷能夠發現錯誤的碼（檢錯碼），收端譯碼器收到后，判斷在傳

5、輸中有無錯誤產生，并通過反饋信道把撿測結果告訴在傳輸中有無錯誤產生，并通過反饋信道把撿測結果告訴發端。發端把收端認為有錯的消息再次傳送，直到收端認發端。發端把收端認為有錯的消息再次傳送，直到收端認為正確接收為止。為正確接收為止。 l l優點是譯碼設備簡單，優點是譯碼設備簡單，在多余度一定的情況在多余度一定的情況下，碼的檢錯能力比下，碼的檢錯能力比糾錯能力要高得多，糾錯能力要高得多，因而整個系統能獲得因而整個系統能獲得極低的誤碼率。極低的誤碼率。l l應用應用ARQ方式必須有一條從收端至發端的反饋信道。并要求信方式必須有一條從收端至發端的反饋信道。并要求信源產生信息的速率可以進行控制，收、發兩端

6、必須互相配合，其源產生信息的速率可以進行控制，收、發兩端必須互相配合，其控制電路比較復雜，傳輸信息的連貫性和實時性也較差。控制電路比較復雜，傳輸信息的連貫性和實時性也較差。（）混合糾錯（）混合糾錯(HEC)方式：方式： HEC (Hybrid Error Control) 方式是上述兩種方式的方式是上述兩種方式的結合。發端發送的碼既能檢錯、又有一定的糾錯能力。收結合。發端發送的碼既能檢錯、又有一定的糾錯能力。收端譯碼時若發現錯誤個數在碼的糾錯能力以內，則自動進端譯碼時若發現錯誤個數在碼的糾錯能力以內，則自動進行糾錯；若錯誤個數超過了碼的糾錯能力，但能檢測出來，行糾錯；若錯誤個數超過了碼的糾錯能

7、力，但能檢測出來，則通過反饋信道告知發方重發。這種方式在一定程度上避則通過反饋信道告知發方重發。這種方式在一定程度上避免了免了 FEC方式譯碼設備復雜和方式譯碼設備復雜和 ARQ方式信息連貫性差的方式信息連貫性差的缺點。缺點。 在設計差錯控制系統時，選擇何種實現方式，應綜合考在設計差錯控制系統時，選擇何種實現方式，應綜合考慮各方面的因素。主要有：慮各方面的因素。主要有： 滿足用戶對誤碼率的要求；滿足用戶對誤碼率的要求； 有盡可能高的信息傳輸速率；有盡可能高的信息傳輸速率； (4)可接受的成本。可接受的成本。 有盡可能簡單的編譯碼算法且易于實現；有盡可能簡單的編譯碼算法且易于實現；8.1.3 糾

8、錯碼的分類糾錯碼的分類 常用的糾錯碼按其碼字結構形式和對信息序列處理方式常用的糾錯碼按其碼字結構形式和對信息序列處理方式的不同可分成兩大類：的不同可分成兩大類：分組碼分組碼和和卷積碼卷積碼。 分組碼是把信息序列以每分組碼是把信息序列以每k個碼元分組，編碼器將每個信息組個碼元分組，編碼器將每個信息組按一定規律產生按一定規律產生r個多余的碼元（稱為校驗元），形成一個長個多余的碼元（稱為校驗元），形成一個長為為n = k + r 的碼字。的碼字。卷積碼是把信息序列以每卷積碼是把信息序列以每k個分組，通過編碼器輸出長為個分組，通過編碼器輸出長為n（n k）的一個子碼。但是該子碼的的一個子碼。但是該子碼

9、的nk個校驗元不僅與本子碼的信息元個校驗元不僅與本子碼的信息元有關，而且也與其前有關，而且也與其前m個子碼的信息元有關。個子碼的信息元有關。an 1an 2arar 1a0時 間k個 信 息 位r個 監 督 位碼 長nkr8.1.4 差錯類型差錯類型 討論碼字序列討論碼字序列c通過離散信道時發生的情況，信道分為無記憶信通過離散信道時發生的情況，信道分為無記憶信道和有記憶信道。道和有記憶信道。 l l在無記憶信道中，噪聲對傳輸碼元的影響是相互獨立的，即每一在無記憶信道中，噪聲對傳輸碼元的影響是相互獨立的，即每一個差錯的出現與其前后是否有錯無關個差錯的出現與其前后是否有錯無關, ,如圖如圖8.2。

10、在無記憶信道中，在無記憶信道中，錯誤是錯誤是隨機隨機產生的，因此被稱作隨機錯誤，產生的，因此被稱作隨機錯誤，無記憶信道也被稱為隨無記憶信道也被稱為隨機信道機信道（random channel）。 圖圖8.2 8.2 二進制對稱信道二進制對稱信道 l l有記憶信道中，各種干擾所造成的錯誤往往不是單個地，而是成有記憶信道中，各種干擾所造成的錯誤往往不是單個地，而是成群、成串地出現，表現出錯誤之間有相關性。圖群、成串地出現，表現出錯誤之間有相關性。圖8.3就是這種信道的就是這種信道的一個模型。一個模型。 圖圖8.3 8.3 有記憶信道模型有記憶信道模型 就實際信道而言，由于其干擾的復雜性，往往是兩種

11、錯誤就實際信道而言，由于其干擾的復雜性，往往是兩種錯誤并存。隨機錯誤與突發錯誤并存的信道，稱為并存。隨機錯誤與突發錯誤并存的信道，稱為組合信道或復組合信道或復合信道合信道。 11 p1p21 p2p21pp 表表8.1給出了一個（給出了一個（7，3）線性分組碼的例子。該例）線性分組碼的例子。該例子中，信息組為（子中，信息組為（c6 c5 c4），），碼字為（碼字為（c6 c5 c4 c3 c2 c1 c0）。）。當已知信息組時，按以下規則得到四個校驗元：當已知信息組時，按以下規則得到四個校驗元： （ 83）這組方程稱為校驗方程。這組方程稱為校驗方程。8.2 8.2 線性分組碼的編碼線性分組碼的

12、編碼 8.2.1 生成矩陣生成矩陣 4505614562463ccccccccccccc信息組信息組 碼碼 字字 0000 0 0 0 0 0 0 0010 0 1 1 1 0 1 0100 1 0 0 1 1 1 0110 1 1 1 0 1 0 1001 0 0 1 1 1 0 1011 0 1 0 0 1 1 1101 1 0 1 0 0 1 1111 1 1 0 1 0 0 表表8.1 （7，3）線性分組碼）線性分組碼 （7，3）線性分組碼有）線性分組碼有23個許用碼字或合法碼字，另有個許用碼字或合法碼字，另有2723個禁用碼字。發方發送的是許用碼字，若收方收到的個禁用碼字。發方發送的

13、是許用碼字，若收方收到的是禁用碼字，則說明傳輸中發生了錯誤。是禁用碼字，則說明傳輸中發生了錯誤。 為了深化對線性分組碼的理論分析，與線性空間聯系起為了深化對線性分組碼的理論分析，與線性空間聯系起來。來。 將（將（n，k）線性分組碼的定義如下：線性分組碼的定義如下：定義定義8.1 2k個個n重的集合重的集合C稱為線性分組碼，當且僅當它是稱為線性分組碼，當且僅當它是n維線性空間維線性空間Vn中的一個中的一個k k維子空間。維子空間。 （n，k）線性分組碼的線性分組碼的2k個碼字組成了個碼字組成了n維線性空間維線性空間Vn的一的一個個k維子空間，因此這維子空間，因此這2k個碼字完全可由個碼字完全可由

14、k個線性無關的矢個線性無關的矢量所組成的基底所張成。量所組成的基底所張成。 設此設此k個矢量為個矢量為c1，c2，ck: :c1（g1, ,n-1，g1, ,n-2，g1, ,0）c2（g2, ,n-1，g2, ,n-2，g2.0）ck（gk, ,n-1，gk, ,n-2，gk, ,0）（n，k）碼中的任一碼字碼中的任一碼字ci，均可由這組基底的線性組合生成：均可由這組基底的線性組合生成： (8 (85)5) 0 ,2,1,0 , 22, 21, 20 , 12, 11, 121knknknnnnknnniigggggggggmmmG Gm mc c寫成矩陣形式：寫成矩陣形式： (8 (84)

15、4)0 ,2,1,0 , 22, 21, 20 , 12, 11, 1knknknnnngggggggggk21c cc cc cG G信息組信息組 碼碼 字字 0000 0 0 0 0 0 0 0010 0 1 1 1 0 1 0100 1 0 0 1 1 1 0110 1 1 1 0 1 0 1001 0 0 1 1 1 0 1011 0 1 0 0 1 1 1101 1 0 1 0 0 1 1111 1 1 0 1 0 0 表表8.1 （7，3）線性分組碼）線性分組碼 定義定義8.2 若信息組以不變的形式，在碼字的任意若信息組以不變的形式，在碼字的任意k位中出現位中出現的碼，稱為系統碼；

16、否則，稱為非系統碼。的碼，稱為系統碼；否則，稱為非系統碼。 說明：說明：常見系統碼有兩種形式：常見系統碼有兩種形式： （1 1）、信息組排在碼字的最左邊）、信息組排在碼字的最左邊k k位；（本教材采用）位；（本教材采用） （2 2）、）、信息組排在碼字的最右邊信息組排在碼字的最右邊k位；位； 一個系統碼的生成矩陣一個系統碼的生成矩陣G，其左邊，其左邊k行行k列應是一個列應是一個k階單位方陣階單位方陣Ik 因此生產矩陣因此生產矩陣G表示為：表示為：其中，其中，P是一個是一個 階矩陣。階矩陣。 QIGk)(knkQ為為kr階矩陣階矩陣,Ik為為k階單位陣，稱為階單位陣，稱為典型生成矩陣典型生成矩陣

17、。8.2.2 校驗矩陣校驗矩陣 表表8.1所示所示（7，3）線性分組碼的四個校驗元是由線性分組碼的四個校驗元是由( (83) )式所示的線式所示的線性方程組決定的。把性方程組決定的。把(8(83)3)式移項：式移項：上式寫成矩陣形式得上式寫成矩陣形式得00000451562456346ccccccccccccc000010001100100011001011100011010123456ccccccc這里的四行七列矩陣稱為（這里的四行七列矩陣稱為（7，3）碼的一致校驗矩陣，簡稱）碼的一致校驗矩陣，簡稱校驗矩陣校驗矩陣，用，用H表示：表示： 100011001000110010111000110

18、1H H 由由H矩陣得到的（矩陣得到的（n，k）線性分組碼的每一碼字線性分組碼的每一碼字ci，（i i1 1，2 2，2k），），都必須滿足由都必須滿足由H矩陣各行所確定的線矩陣各行所確定的線性方程組，即性方程組，即 c ci iH H T T0 0 (8 (88)8)或或 H Hc ci iT T0 0T T (8 (89)9) 又，（又，（n n，k k）線性分組碼的生成矩陣線性分組碼的生成矩陣G G中的每一行及其線性組中的每一行及其線性組合都是（合都是（n n，k k）碼的碼字，所以有碼的碼字，所以有 GH GH T T0 0 (8 (810)10)或或 HG T0T (8 (811)1

19、1) 系統碼的校驗矩陣系統碼的校驗矩陣H H具有以下形式：即具有以下形式：即 rIPH 一個系統碼的校驗矩陣一個系統碼的校驗矩陣H，其右邊，其右邊r行行r列應是一個列應是一個r階單位方陣階單位方陣Ir， 而而PT是一個是一個 階矩陣階矩陣： kkn )(TQP 8.2.3 編碼的實現編碼的實現 設碼的設碼的G矩陣為矩陣為0 ,2,1,0 , 22, 21, 20 , 12, 11, 1kknkknkknknknknkpppppppppI IG G當信息組當信息組m（mn- 1mn-2 mn-k）時，相應的碼字時，相應的碼字c是是 c mG（cn-1 cn-2 c1 c0） cj mn-1 p1

20、,j+mn-2 p2,j+mn-k pk,j 0 j nk cjmj nk j n1 其中其中圖8.4 （n，k）線性分組碼編碼電路 編碼實現電路如圖編碼實現電路如圖8.4所示。電路由移位寄存器、模二加法器和模所示。電路由移位寄存器、模二加法器和模二乘法器組成二乘法器組成根據圖根據圖8.4的電路，可畫出的電路，可畫出（7，3）線性分組碼的編碼線性分組碼的編碼器電路，如圖器電路，如圖8.5。 圖圖8.5 8.5 （7, 37, 3）線性分組碼編碼電路）線性分組碼編碼電路 8.3 8.3 伴隨式與譯碼伴隨式與譯碼 8.3.1 碼的距離和重量碼的距離和重量 定義定義8.5 一個碼的最小距離一個碼的最

21、小距離dmin定義為定義為 (8 (813)13) ),(,),(minminknjiddjijic cc cc cc c 定義定義8.4 碼字中碼字中非零碼元的個數，非零碼元的個數，稱為該碼字的漢明稱為該碼字的漢明重量，簡稱重量，重量，簡稱重量，用用w（c）表示。表示。定義定義8.3 兩個兩個碼字碼字之間，對應位取值之間，對應位取值不同的個數，稱為不同的個數，稱為它們之間的它們之間的漢明漢明距距離，簡稱距離，用離，簡稱距離，用d d（c1，c 2）表示。表示。碼的距離和重量滿足以下不等碼的距離和重量滿足以下不等 d d（c 1，c 2） d d（c 1 1，c 3 3）d d（c 3 3，c

22、 2 2） (8 (814)14)w（c 1 1c 2 2） w（c 1 1）w（c 2 2） (8 (815)15) 定理定理8.1 線性分組碼的最小距離等于其非零碼字的最小重線性分組碼的最小距離等于其非零碼字的最小重量。量。 根據定理，要得到碼的最小距離，只要檢查根據定理，要得到碼的最小距離，只要檢查2k1個非零個非零碼字的重量即可。碼字的重量即可。 當當 當生成矩陣給定時，當生成矩陣給定時，線性分組碼有如下性質線性分組碼有如下性質：（1 1）零向量；）零向量； （2 2）任意兩碼字的和仍是一個碼字；）任意兩碼字的和仍是一個碼字；（3 3）任意碼字）任意碼字 是是 的行向量的行向量 的線性

23、組合；的線性組合；（4 4）線性分組碼的最小距離等于最小非零碼字重量。）線性分組碼的最小距離等于最小非零碼字重量。 110,kgggcG信息組信息組 碼碼 字字 0000 0 0 0 0 0 0 0010 0 1 1 1 0 1 0100 1 0 0 1 1 1 0110 1 1 1 0 1 0 1001 0 0 1 1 1 0 1011 0 1 0 0 1 1 1101 1 0 1 0 0 1 1111 1 1 0 1 0 0 表表8.1 （7，3）線性分組碼）線性分組碼 事實上，兩個碼字之間的距離表示了它們之間差別的大小。事實上，兩個碼字之間的距離表示了它們之間差別的大小。因此，一個線性分

24、組碼的最小距離是衡量碼抗干擾能力的因此，一個線性分組碼的最小距離是衡量碼抗干擾能力的重要參數。碼的最小距離愈大，其抗干擾能力愈強。重要參數。碼的最小距離愈大，其抗干擾能力愈強。8.3.2 線性碼的糾檢錯能力線性碼的糾檢錯能力 該定理是糾錯碼理論中最重要的基本定理之一，它說該定理是糾錯碼理論中最重要的基本定理之一，它說明了一個距離為明了一個距離為d的線性分組碼，既可用來糾正的線性分組碼，既可用來糾正個錯誤，又可用來檢測個錯誤，又可用來檢測e d1個錯誤。個錯誤。 21dt定理定理8.2 對于任一個（對于任一個（n，k）線性分組碼，若要在碼字線性分組碼，若要在碼字內內 檢測檢測e個錯誤，則要求碼的

25、最小距離個錯誤，則要求碼的最小距離d e1； 糾正糾正t個錯誤，則要求碼的最小距離個錯誤，則要求碼的最小距離d 2t1； 糾正糾正t個錯誤同時檢測個錯誤同時檢測e（ t）個錯誤，則要求個錯誤，則要求d te1。 定理定理8.3 （n，k）線性分組碼有最小距離為線性分組碼有最小距離為d的充的充要條件，是要條件，是H矩陣中任意矩陣中任意d1列線性無關。列線性無關。 推論推論8.4 （n，k）線性分組碼的最大的，可能線性分組碼的最大的，可能的最小距離等于的最小距離等于n k1。 由此定理可知，所有列相同，但排列位置不同的各種由此定理可知，所有列相同，但排列位置不同的各種H矩陣所對應的不同（矩陣所對應

26、的不同（n，k）線性分組碼，都有相同的線性分組碼，都有相同的最小距離，即它們在糾錯能力和碼率上是完全等價的。最小距離，即它們在糾錯能力和碼率上是完全等價的。 8.3.3 伴隨式伴隨式 由于信道中噪聲的影響，由于信道中噪聲的影響，y序列中的某些碼元可能與序列中的某些碼元可能與c序序列中對應碼元的值不同，有列中對應碼元的值不同，有 yce (8(816)16) 稱稱e為信道的為信道的錯誤圖樣錯誤圖樣。 （n，k）碼的任一碼字，均滿足碼的任一碼字，均滿足(88)式或式或(89)式，因式，因此，可以將接收碼字此，可以將接收碼字y用二式中之任一式進行檢驗：用二式中之任一式進行檢驗： (8(817)17)

27、TTTTTHHHHHe ee ec ce ec cy y)(令令 s s = = y y. .H H T T= =e e. .H H T T (8 (818)18)稱為接收序列的稱為接收序列的伴隨式伴隨式或校正子。或校正子。當當s 0時，譯碼器要做的就是如何從伴隨式時，譯碼器要做的就是如何從伴隨式s中找到錯誤中找到錯誤圖樣，從而譯出發送的碼字。圖樣，從而譯出發送的碼字。得到（得到（n，k）線性分組碼的譯碼步驟如下：線性分組碼的譯碼步驟如下： 若若s = = 0，則認為收到的則認為收到的y沒有錯誤；否則認為沒有錯誤；否則認為有錯，并查譯碼表，由有錯，并查譯碼表，由s找出錯誤圖樣找出錯誤圖樣 ；e

28、 eTH Hy ys s 由接收到的由接收到的y計算伴隨式計算伴隨式 ； 由和由和y計算計算 ， 就作為糾錯后的判決碼就作為糾錯后的判決碼字輸出。字輸出。e ey yc cc c8.3.4 線性分組碼的譯碼線性分組碼的譯碼 8.4 8.4 漢明碼漢明碼 8.4.1 漢明碼的構造漢明碼的構造 定義定義8.6若若H矩陣的列是由非全零且互不相矩陣的列是由非全零且互不相同的所有二進制同的所有二進制r重組成，則由此得到的線性重組成，則由此得到的線性分組碼，稱為分組碼，稱為GF( (2) )上的（上的（2r1，2r1r）漢明碼。漢明碼。 8.4.2 漢明限與完備碼漢明限與完備碼 一個二進制（一個二進制（n，k）線性分組碼，若要糾正線性分組碼，若要糾正t個錯誤，則個錯誤，則應使小于或等于應使小于或等于t個錯誤所組成的所有錯誤圖樣，都必須有不個錯誤所組成的所有錯誤圖樣，都必須有不同的伴隨式與