1、第九章 信道的糾錯編碼第九章第九章 信道的糾錯碼信道的糾錯碼內容提要目前，幾乎所有得到實際應用的糾錯碼都是線性的。本章首先介紹有關糾錯碼的基本概念，然后重點論述線性分組碼的定義及其編譯碼理論。在此基礎上，介紹了一種典型的線性分組碼：漢明碼。 糾錯碼的基本概念糾錯碼的基本概念 信道糾錯編碼信道糾錯編碼 l信源編碼的目的是壓縮冗余度，提高信息的傳輸速率。l信道編碼的目的是提高信息傳輸時的抗干擾能力以增加信息傳輸的可靠性。香農第二定理指出，當信息傳輸速率低于信道容量時，通過某種編譯碼方法，就能使錯誤概率為任意小。目前已有了許多有效的編譯碼方法，并形成了一門新的技術糾錯編碼技術。這里所講的糾錯編碼即信

2、道編碼，與信源編碼一樣都是一種編碼，但兩者的作用是完全不同的。差錯類型差錯類型 討論碼字序列c通過離散信道時發生的情況，信道分為無記憶信道和有記憶信道。 l在無記憶信道中，噪聲對傳輸碼元的影響是相互獨立的，即每一個差錯的出現與其前后是否有錯無關,如圖。在無記憶信道中，錯誤是隨機產生的，因此被稱作隨機錯誤，無記憶信道也被稱為隨機信道（random channel）。 二進制對稱信道 l有記憶信道中，各種干擾所造成的錯誤往往不是單個地，而是成群、成串地出現，表現出錯誤之間有相關性。下圖就是這種信道的一個模型。 有記憶信道模型 就實際信道而言，由于其干擾的復雜性，往往是兩種錯誤并存。隨機錯誤與突發錯

3、誤并存的信道，稱為組合信道或復合信道。 差錯控制系統模型及分類差錯控制系統模型及分類 為了方便研究，將信息傳輸系統模型簡化成下圖所示的簡化模型簡化的信息傳輸系統模型 模型突出了以控制差錯為目的的糾錯碼編碼器和譯碼器，因此也稱為差錯控制系統。在差錯控制系統中使用的碼按其糾錯能力的不同可分為兩種：檢錯碼檢錯碼和糾錯碼糾錯碼。 能發現錯誤但不能糾正錯誤的碼稱為檢錯碼 ； 不僅能發現錯誤而且還能糾正錯誤的碼稱為糾錯碼。（）前向糾錯前向糾錯(FEC)方式方式 ： FEC (Forward Error Control) 方式是發端發送有糾錯能力的碼（糾錯碼），接收端收到這些碼后，通過糾錯譯碼器自動地糾正傳

4、輸中的錯誤。 差錯控制系統大致可分為前向糾錯、反饋重發和混合糾錯等三種方式。l優點是不需要反饋信道；能進行一個用戶對多個用戶的同時通信，特別適合于移動通信；譯碼實時性較好，控制電路也比較簡單。 l缺點是譯碼設備較復雜；編碼效率較低。（）反饋重發反饋重發(ARQ)方式方式: ARQ (Automatic Repeat Request) 方式是：發端發出能夠發現錯誤的碼（檢錯碼），收端譯碼器收到后，判斷在傳輸中有無錯誤產生，并通過反饋信道把撿測結果告訴發端。發端把收端認為有錯的消息再次傳送，直到收端認為正確接收為止。 l優點是譯碼設備簡單，在多余度一定的情況下，碼的檢錯能力比糾錯能力要高得多，因而

5、整個系統能獲得極低的誤碼率。l應用ARQ方式必須有一條從收端至發端的反饋信道。并要求信源產生信息的速率可以進行控制，收、發兩端必須互相配合，其控制電路比較復雜，傳輸信息的連貫性和實時性也較差。（）混合糾錯混合糾錯(HEC)方式：方式： HEC (Hybrid Error Control) 方式是上述兩種方式的結合。發端發送的碼既能檢錯、又有一定的糾錯能力。收端譯碼時若發現錯誤個數在碼的糾錯能力以內，則自動進行糾錯；若錯誤個數超過了碼的糾錯能力，但能檢測出來，則通過反饋信道告知發方重發。這種方式在一定程度上避免了 FEC方式譯碼設備復雜和 ARQ方式信息連貫性差的缺點。 在設計差錯控制系統時，選

6、擇何種實現方式，應綜合考慮各方面的因素。主要有： 滿足用戶對誤碼率的要求； 有盡可能高的信息傳輸速率； (4)可接受的成本。 有盡可能簡單的編譯碼算法且易于實現；糾錯碼的分類糾錯碼的分類 按信息位與校驗位的關系，可將編碼分成以下兩大類：按信息位與校驗位的關系，可將編碼分成以下兩大類：（1）線性碼校驗位與信息位呈線性關系（即可用一次方程描述）。（2）非線性碼校驗位與信息位不呈線性關系。按信息位與校驗位之間的約束關系，可分為：按信息位與校驗位之間的約束關系，可分為：（1）分組碼將信息符號分成k位一組，每組增加r位校驗位，這r位校驗位僅與本組的k位信息位有關，與其他的信息位無關。 循環碼除全零碼字外

7、，其余碼字都可由另一碼字的碼符循 環移位得到； 非循環碼某個碼字的循環移位不一定還是該碼的碼字。（2）卷積碼將信息符號分成k位一組，每組增加r位校驗位，這r位校驗位不僅與本組的k位信息位有關，還與前面m組的信息位有關。線性分組碼的編碼線性分組碼的編碼過程分為兩步：過程分為兩步：p把信息序列按一定長度分成若干信息碼組，每組由 k 位組成；p編碼器按照預定的線性規則(可由線性方程組規定)，把信息碼組變換成 n 重 (nk) 碼字，其中 (nk) 個附加碼元是由信息碼元的線性運算產生的。信息碼組長信息碼組長 k 位，有位，有 2k 個不同的信息碼組，則應該有個不同的信息碼組，則應該有 2k 個個碼字

8、與它們一一對應。碼字與它們一一對應。 線性分組碼線性分組碼線性分組碼線性分組碼：通過預定的線性運算將長為：通過預定的線性運算將長為 k 位的信息碼組位的信息碼組變換成變換成 n位的碼字位的碼字 (nk)。由。由 M=2k 個信息碼組所編成的個信息碼組所編成的 2k個碼字集合，稱為個碼字集合，稱為線性分組碼線性分組碼。碼矢碼矢：一個：一個 n 重的碼字可以用矢量來表示重的碼字可以用矢量來表示C=(Cn1,Cn1,C1,C0 )所以碼字又稱為碼矢。(n,k) 線性碼線性碼：信息位長為：信息位長為 k，碼長為，碼長為 n 的線性碼。的線性碼。碼率碼率/信道的傳信率：信道的傳信率：R=logM/n=k

9、 /n。它表示信道編碼后每。它表示信道編碼后每個碼符號攜帶的信息量，說明了信道的利用效率，個碼符號攜帶的信息量，說明了信道的利用效率，R是衡量是衡量編碼性能的一個重要參數編碼性能的一個重要參數。一致監督方程：一致監督方程：編碼就是給已知信息碼組按預定規則添加監督碼元，以編碼就是給已知信息碼組按預定規則添加監督碼元，以構成碼字。構成碼字。在在 k 個信息碼元之后附加個信息碼元之后附加 r(r=nk) 個監督碼元，使每個監督碼元，使每個監督元是其中某些信息元的模個監督元是其中某些信息元的模2和。和。一致監督方程一致監督方程/一致校驗方程：確定信息元得到監督元規一致校驗方程：確定信息元得到監督元規則

10、的一組方程稱為監督方程則的一組方程稱為監督方程/校驗方程。由于校驗方程。由于所有碼字都所有碼字都按同一規則確定按同一規則確定，又稱為一致監督方程，又稱為一致監督方程/一致校驗方程。一致校驗方程。由于一致監督方程是線性的，即監督元和信息元之間是由于一致監督方程是線性的，即監督元和信息元之間是線性運算關系，所以由線性監督方程所確定的分組碼是線性運算關系，所以由線性監督方程所確定的分組碼是線性分組碼線性分組碼。例例k=3, r=4構成構成 (7,3) 線性分組碼。設碼字為線性分組碼。設碼字為p(C6,C5,C4,C3,C2,C1,C0)pC6,C5,C4為信息元，C3,C2,C1,C0為監督元，每個

11、碼元取“0”或“1”p監督元可按下面方程組計算4505614562463CCCCCCCCCCCCC信息碼組信息碼組 (101)，即，即C6=1, C5=0, C4=1由線性方程組得：由線性方程組得： C3=0, C2=0, C1=1, C0=1即信息碼組即信息碼組 (101) 編出的碼字為編出的碼字為 (1010011)。其它。其它7個碼字如個碼字如表。表。(7,3)分組碼編碼表 信息組 對應碼字 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 1 0 1 1 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 1 0

12、 1 0 1 1 0 1 0 0 1 1 1 1 0 1 1 0 1 0 0 1 1 1 1 1 1 1 0 1 0 0 4505614562463CCCCCCCCCCCCC00000000000000000000451562456346CCCCCCCCCCCCC一致監督矩陣：一致監督矩陣：將監督方程寫成矩陣形將監督方程寫成矩陣形式，得：式，得： HH C CT=0 0T或或 C C HHT=0 0 C CT、HHT、0 0T分別表示分別表示C C、HH、0 0的轉置矩陣。的轉置矩陣。1000110010001100101110001101H 00000C0000100011001000110

13、010111000110101234560123456CCCCCCCCCCCCCC令系數矩陣系數矩陣 H H 的后四列組成一個的后四列組成一個 (44) 階單位子陣，用階單位子陣，用 I I4 表示，表示，H H 的其余部分用的其余部分用 P P 表示表示43437434IPH1000010000100001I110011111101P),(所以推廣到一般情況：對推廣到一般情況：對 (n,k) 線性分組碼，每個碼字中的線性分組碼，每個碼字中的 r(r=nk) 個監督元與信息元之間的關系可由下面的線性個監督元與信息元之間的關系可由下面的線性方程組確定方程組確定000022110222212101

14、212111ChChChChChChChChChrnnrnrnnnnnn令系數矩陣為令系數矩陣為 HH，碼字行陣列為，碼字行陣列為 C C一致監督方程和一致監督矩陣一致監督方程和一致監督矩陣11121212221211201111HCHC0CH0H( , )nnr nrrrnnnnTTTr nnrnn rrhhhhhhhhhCCCn k則：或稱 為線性分組碼的一致監督 矩陣。一致監督矩陣特性一致監督矩陣特性:對對H H 各行實行初等變換，將后面各行實行初等變換，將后面 r 列化為單位子陣，于是列化為單位子陣，于是得到下面矩陣得到下面矩陣(行變換所得方程組與原方程組同解行變換所得方程組與原方程組

15、同解)。監督矩陣監督矩陣H H 的標準形式的標準形式：后面：后面 r 列是一單位子陣的監督矩列是一單位子陣的監督矩陣陣HH。H H 陣的每一行都代表一個監督方程，它表示與該行中陣的每一行都代表一個監督方程，它表示與該行中“1”相對應的碼元的模相對應的碼元的模2和為和為0。100010001H212222111211rnrrkknrpppppppppH H 的標準形式還說明了相應的監督元是由哪些信息元決定的標準形式還說明了相應的監督元是由哪些信息元決定的。例如的。例如 (7,3) 碼的碼的H H 陣的第一行為陣的第一行為 (1011000)，說明此碼的，說明此碼的第一個監督元等于第一個和第三個信

16、息元的模第一個監督元等于第一個和第三個信息元的模2和，依此類和，依此類推。推。 H H 陣的陣的 r 行代表了行代表了 r 個監督方程，也表示個監督方程，也表示由由H H 所確定的碼所確定的碼字有字有 r 個監督元個監督元。為了得到確定的碼，為了得到確定的碼，r 個監督方程（或個監督方程（或H H 陣的陣的r 行）必須是行）必須是線性無關線性無關的，這要求的，這要求H H 陣的秩為陣的秩為 r。若把若把H H 陣化成標準形式，只要檢查單位子陣的秩，就能方陣化成標準形式，只要檢查單位子陣的秩，就能方便地確定便地確定H H 陣本身的秩。陣本身的秩。線性碼的封閉性線性碼的封閉性:線性碼的封閉性線性碼

17、的封閉性：線性碼任意兩個碼字之和仍是一個碼字。：線性碼任意兩個碼字之和仍是一個碼字。證明證明：若：若 U U 和和 V V 為線性碼的任意兩個碼字，故有為線性碼的任意兩個碼字，故有HUT=0T，HVT=0T那么 H(U+V)T=H(UT+VT)=HUT+HVT=0T即 U+V 滿足監督方程，所以 U+V 一定是一個碼字。一個長為一個長為 n 的二元序列可以看作是的二元序列可以看作是GFGF(2)(二元域二元域)上的上的 n 維維線性空間中的一點。長為線性空間中的一點。長為 n 的所有的所有 2n 個矢量集合構成了個矢量集合構成了GFGF(2)上的上的 n 維線性空間維線性空間V Vn。把線性碼

18、放入線性空間中進。把線性碼放入線性空間中進行研究，將使許多問題簡化而比較容易解決。行研究，將使許多問題簡化而比較容易解決。(n,k) 線性碼是線性碼是 n 維線性空間維線性空間V Vn中的一個中的一個 k 維子空間維子空間 V Vk。線性分組碼的生成矩陣線性分組碼的生成矩陣線性分組碼的生成矩陣線性分組碼的生成矩陣:在由在由 (n,k) 線性碼構成的線性空間線性碼構成的線性空間 V Vn 的的 k 維子空間中，一維子空間中，一定存在定存在 k 個線性無關的碼字：個線性無關的碼字：g1,g2, gk,。碼。碼 C CI 中其它任中其它任何碼字何碼字C C都可表示為這都可表示為這 k 個碼字的線性組

19、合，即個碼字的線性組合，即階矩陣。是一個是待編碼的信息組。寫成矩陣形式得其中：nkmmmmmmkimmmmkknkkkkknikkkGmGmgggC1, 1 , 0),2(GFgggC021121021102211GG中每一行中每一行 gi=(gi1,gi2, gin ) 都是一個碼字；都是一個碼字；對每一個信息組對每一個信息組mm，由矩陣，由矩陣GG都可以求得都可以求得 (n,k) 線性碼對應線性碼對應的碼字。的碼字。生成矩陣生成矩陣：由于矩陣：由于矩陣 G G 生成了生成了 (n,k) 線性碼，稱矩陣線性碼，稱矩陣 G G 為為 (n,k) 線性碼的生成矩陣。線性碼的生成矩陣。(n,k)

20、線性碼的每一個碼字都是生成矩陣線性碼的每一個碼字都是生成矩陣 G G 的行矢量的線性的行矢量的線性組合，所以它的組合，所以它的 2k 個碼字構成了由個碼字構成了由 G G 的行張成的的行張成的 n 維空間維空間V Vn的一個的一個 k 維子空間維子空間 V Vk。knkknnknkggggggggg21222211121121gggG顯然：線性系統分組碼線性系統分組碼: 通過行初等變換，將通過行初等變換，將 G G 化為前化為前 k 列是單位子陣的列是單位子陣的標準形式標準形式 knjqmqmqmCkimC,mmmCCCqqqqqqqqqkjjkjkjknikinnkkknnnrkkknkkk

21、knknnk, 2 , 1, 2 , 1G),(),(CQI100010001G02211)(0210211)(21)(22221)( 11211得將上式代入線性系統分組碼線性系統分組碼：用標準生成矩陣：用標準生成矩陣 GGkn 編成的碼字，前面編成的碼字，前面 k 位為信息數字，后面位為信息數字，后面 r=nk 位為校驗字，這種信息數字位為校驗字，這種信息數字在前校驗數字在后的線性分組碼稱為線性系統分組碼。在前校驗數字在后的線性分組碼稱為線性系統分組碼。當生成矩陣當生成矩陣 G G 確定之后，確定之后，(n,k) 線性碼也就完全被確定了，線性碼也就完全被確定了，只要找到碼的生成矩陣，編碼問題

22、也同樣解決了。只要找到碼的生成矩陣，編碼問題也同樣解決了。系統碼的碼字結構信息數字校驗數字例例: (7,4) 線性碼的生成矩陣為線性碼的生成矩陣為)1010011(11010000110100111001010100010101GmC)1010(m1101000011010011100101010001G7441714174，則若 rTrkSrkkSkrTrkTkrrkrkrkTkrrTkrrkkTrkrrkkTSSrkrSrkkSI)Q(HQIGP)Q()P(Q0Q)P(I)P(QIIPQIHGIPHQIG或所以，生成矩陣與一致監督矩陣的關系生成矩陣與一致監督矩陣的關系:由于生成矩陣由于生成

23、矩陣GG的每一行都是一個碼字，所以的每一行都是一個碼字，所以G G 的每行都的每行都滿足滿足HHrnC CTn1=0 0Tr1，則有，則有HHrnGGTnk=0 0Trk 或或 GGknHHTnr=0 0kr線性系統碼的監督矩陣線性系統碼的監督矩陣 H H 和生成矩陣和生成矩陣 G G 之間可以直接互之間可以直接互換換。例例: 已知已知(7,4)線性系統碼的監督矩陣為線性系統碼的監督矩陣為1101000011010011100101010001G100101101011100010111H)4,7()4,7(陣可直接寫出它的生成矩對偶碼對偶碼：一個：一個(n,k)線性碼線性碼 C CI，如果以

24、，如果以G G 作監督矩陣，而以作監督矩陣，而以H H 作生成矩陣，可構造另一個作生成矩陣，可構造另一個 (n,nk)線性碼線性碼C CId ，稱碼，稱碼C CId為原碼的對偶碼。為原碼的對偶碼。(7,3)碼的監督矩陣碼的監督矩陣HH(7,3)是是(7,4)碼的生成矩陣碼的生成矩陣GG(7,4) (7,4) 碼的監督矩陣碼的監督矩陣 HH(7,4)是是(7,3) 碼的生成矩陣碼的生成矩陣 GG(7,3)(7,4)(7,3)1 1 1 0 1 0 01 0 0 1 1 1 0H0 1 1 1 0 1 00 1 0 0 1 1 1G1 1 0 1 0 0 10 0 1 1 1 0 1 標準形式（行

25、初等變換）(7,4)(7,3)1000101101100001001111110100GH0010110110001000010110110001 標準形式(行初等變換)(n,k) 線性碼的編碼就是根據線性碼的監督矩陣或生成矩陣線性碼的編碼就是根據線性碼的監督矩陣或生成矩陣將將長為長為 k 的信息組變換成長為的信息組變換成長為 n(nk) 的碼字的碼字。利用監督矩陣構造利用監督矩陣構造 (7,3) 線性分組碼的編碼電路：線性分組碼的編碼電路：p設碼字矢量為C=(C6 C5C4C3C2C1C0)p碼的監督矩陣為線性分組碼的編碼線性分組碼的編碼4505614562463)3 ,7(10001100

26、10001100101110001101CCCCCCCCCCCCCTT得由0HCH根據方程組可直接畫出根據方程組可直接畫出 (7,3) 碼的并行和串行編碼電路。碼的并行和串行編碼電路。m0m1m2C6C5C4C3C2C1C0C0C1C2C3C4C5C6mC(a)并行編碼電路 （b）串行編碼電路 (7,3)線性編碼電路漢明距離、漢明重量和漢明球漢明距離、漢明重量和漢明球漢明距離漢明距離：在：在 (n,k)線性碼中，兩個碼字線性碼中，兩個碼字 UU、V V 之間對應碼元位上符號之間對應碼元位上符號取值不同的個數，稱為碼字取值不同的個數，稱為碼字 UU、V V 的漢明距離。的漢明距離。p例：(7,3

27、) 碼的兩個碼字 U=0011101,V=0100111之間第2、3、4和6位不同。因此，碼字 U 和 V 的距離為4。線性分組碼的一個碼字對應于線性分組碼的一個碼字對應于 n 維線性空間中的一點，碼字間的距離維線性空間中的一點，碼字間的距離即為空間中兩即為空間中兩對應點的距離。因此，碼字間的距離滿足一般距離公理：對應點的距離。因此，碼字間的距離滿足一般距離公理：10)(),(niiivudVU線性分組碼的最小距離、檢錯和糾錯能力線性分組碼的最小距離、檢錯和糾錯能力三角不等式對稱性非負性)W,U()W,V()V,U()U,V()V,U(0)V,U(dddddd最小距離最小距離dmin：在：在

28、(n,k) 線性碼的碼字集合中，任意兩個不同線性碼的碼字集合中，任意兩個不同碼字間距離的最小值，叫做碼的最小距離。若碼字間距離的最小值，叫做碼的最小距離。若C C(i)和和C C(j) 是任是任意兩個碼字，則碼的最小距離表示為意兩個碼字，則碼的最小距離表示為 碼的最小距離是衡量碼的抗干擾能力（檢、糾錯能力）的重碼的最小距離是衡量碼的抗干擾能力（檢、糾錯能力）的重要參數。碼的最小距離越大，碼的抗干擾能力就越強。要參數。碼的最小距離越大，碼的抗干擾能力就越強。漢明球漢明球：以碼字：以碼字C C為中心，半徑為為中心，半徑為 t 的漢明球是與的漢明球是與 C C 的漢明的漢明距離距離 t 的向量全體集

29、合的向量全體集合 S SC C(t) 任意兩個漢明球不相交最大程度取決于任意兩個碼字之間的任意兩個漢明球不相交最大程度取決于任意兩個碼字之間的最小漢明距離最小漢明距離dmin。12 , 1 , 0,),(min)()(minkjijijiddCCtdt),()(RCRSC tVUdmindmin=5,碼距和糾錯能力關系示意圖漢明重量漢明重量W：碼字中非：碼字中非0碼元符號的個數，稱為該碼字的漢碼元符號的個數，稱為該碼字的漢明重量。明重量。p在二元線性碼中，碼字重量就是碼字中“1”的個數。p最小重量Wmin ：線性分組碼CI中，非0碼字重量的最小值，叫做碼CI的最小重量：Wmin =minW(V

30、 V),V VC CI ,V V0 0最小距離與最小重量的關系：線性分組碼的最小距離等于最小距離與最小重量的關系：線性分組碼的最小距離等于它的最小重量。它的最小重量。 證明證明：設線性碼：設線性碼C CI，且，且UUC CI, V VC CI，又設，又設UUV V=Z Z，由線性碼的封閉性知，由線性碼的封閉性知，Z ZC CI 。因此，。因此，d(UU,V V)=W(Z Z)，由此，由此可推知，線性分組碼的最小距離必等于非可推知，線性分組碼的最小距離必等于非0 0碼字的最小重量。碼字的最小重量。最小距離與檢、糾錯能力：最小距離與檢、糾錯能力：一般地說，線性碼的最小距離越大，意味著任意碼一般地說

31、，線性碼的最小距離越大，意味著任意碼字間的差別越大，則碼的檢、糾錯能力越強。字間的差別越大，則碼的檢、糾錯能力越強。檢錯能力檢錯能力：一個線性碼能檢出長度：一個線性碼能檢出長度l 個碼元的任何個碼元的任何錯誤圖樣，稱碼的檢錯能力為錯誤圖樣，稱碼的檢錯能力為 l。糾錯能力糾錯能力：線性碼能糾正長度：線性碼能糾正長度t 個碼元的任意錯誤個碼元的任意錯誤圖樣，稱碼的糾錯能力為圖樣，稱碼的糾錯能力為 t。最小距離與糾錯能力最小距離與糾錯能力：(n,k) 線性碼能糾線性碼能糾 t 個錯誤的充要條件個錯誤的充要條件是碼的最小距離為是碼的最小距離為 證明證明： 設發送的碼字為設發送的碼字為V V；接收的碼字

32、為；接收的碼字為R R；UU為任意其它碼字；為任意其它碼字； 則矢量則矢量V V、R R、UU間滿足距離的三角不等式，間滿足距離的三角不等式， d(R R,V V)+d(R R,UU)d(UU,V V) 又設信道干擾使碼字中碼元發生錯誤的實際個數為又設信道干擾使碼字中碼元發生錯誤的實際個數為 t，且，且tt d(R R,V V)tt 由于由于d(UU,V V)dmin=2t+1，代入上式得：，代入上式得： d(R R,UU) d(UU,V V)d(R R,V V)= 2t+1tt 的最大整數表示取實數其中或XXdttd2112minmin 上式表明上式表明：如果接收碼字：如果接收碼字 R R

33、中錯誤個數中錯誤個數 tt，那么接收碼，那么接收碼字字 R R 和發送碼字和發送碼字 V V 間距離間距離t ，而與其它任何碼字間距離，而與其它任何碼字間距離都大于都大于 t，按最小距離譯碼把，按最小距離譯碼把R R譯為譯為V V。此時譯碼正確，碼。此時譯碼正確，碼字中的錯誤被糾正。字中的錯誤被糾正。 tVUdmin dmin=5,碼距和糾錯能力關系示意圖最小距離與檢錯能力最小距離與檢錯能力：(n,k) 線性碼能夠發現線性碼能夠發現 l 個錯誤的充要個錯誤的充要條件是碼的最小距離為條件是碼的最小距離為 dmin=l+1 或或 l=dmin1 證明證明： 設發送的碼字為設發送的碼字為 V V；接

34、收的碼字為；接收的碼字為 R R；U U 為任意其它碼字；為任意其它碼字； 則矢量則矢量V V、R R、UU間滿足距離的三角不等式，間滿足距離的三角不等式， d(R R,V V)+d(R R,UU)d(UU,V V) 又設信道干擾使碼字中碼元發生錯誤的實際個數為又設信道干擾使碼字中碼元發生錯誤的實際個數為 l，且，且ll d(R R,V V)ll 由于由于d(UU,V V)dmin=l+1，代入上式得：，代入上式得： d(R R,UU) d(UU,V V)d(R R,V V)=l+1l0 上式表明上式表明：由于接收碼字：由于接收碼字 R R 與其它任何碼字與其它任何碼字 U U 的距離都大的距

35、離都大于于0，則說明接收字，則說明接收字 R R 不會因發生不會因發生 l 個錯誤變為其它碼字，個錯誤變為其它碼字，因而必能發現錯誤。因而必能發現錯誤。 lVUdmindmin=4,碼距和檢錯能力關系示意圖最小距離與檢、糾錯能力最小距離與檢、糾錯能力：(n,k) 線性碼能糾線性碼能糾 t 個錯誤，并個錯誤，并能發現能發現 l 個錯誤個錯誤 (lt) 的充要條件是碼的最小距離為的充要條件是碼的最小距離為 dmin=t+l+1 或或 t+l=dmin1 證明證明： 因為因為dmin2t+1，根據，根據最小距離與糾錯能力最小距離與糾錯能力定理，該碼定理，該碼可糾可糾 t 個錯誤。個錯誤。 又因為又因

36、為dminl+1，根據，根據最小距離與檢錯能力最小距離與檢錯能力定理，該碼定理，該碼有檢有檢 l 個錯誤的能力。個錯誤的能力。 糾錯和檢錯不會發生混淆：設發送碼字為糾錯和檢錯不會發生混淆：設發送碼字為 V V，接收字，接收字為為 R R，實際錯誤數為，實際錯誤數為 l，且，且 tt+1t 因而不會把因而不會把 R R 誤糾為誤糾為 UU。 幾何意義幾何意義：ldmindmin=5,t=1,l=3時碼距和檢錯能力關系示意圖tVUdminldmintdmintl最小碼距與檢糾錯能力l當當 (n,k) 線性碼的最小線性碼的最小距離距離 dmin 給定后，可給定后，可按實際需要靈活安排按實際需要靈活安

37、排糾錯的數目。例如，糾錯的數目。例如，對對 dmin=8 的碼，可用的碼，可用來糾來糾3檢檢4錯，或糾錯，或糾2檢檢5錯，或糾錯，或糾1檢檢6錯，或錯，或者只用于檢者只用于檢7個錯誤。個錯誤。伴隨式和錯誤檢測：伴隨式和錯誤檢測：用監督矩陣譯碼用監督矩陣譯碼：接收到一個碼字：接收到一個碼字 R R 后，檢驗后，檢驗 HH R RT=0 0T 是是否成立：否成立：pHRT =0T是否成立是檢驗碼字出錯與否的依據。p若關系成立，則認為 R 是一個碼字；p否則判為碼字在傳輸中發生了錯誤；伴隨式伴隨式/監督子監督子/校驗子校驗子：S S=R R HHT或或S ST=HH R RT。如何糾錯？如何糾錯？p

38、設發送碼矢 C=(Cn1,Cn2,C0)p信道錯誤圖樣為 E=(En1,En2,E0) ，其中其中Ei=0，表示第，表示第i位無錯；位無錯；Ei=1，表示第，表示第i位有錯。位有錯。i=n1,n2,0。線性分組碼的伴隨式線性分組碼的伴隨式接收碼字接收碼字 R R =(Rn1,Rn2,R0)=C C+E E =(Cn1+En1, Cn2+En2, , C0 +E0)求接收碼字的伴隨式（接收碼字用監督矩陣進行檢驗）求接收碼字的伴隨式（接收碼字用監督矩陣進行檢驗） S ST=HH R RT=HH (C C+E E)T=HH C CT+HH E ET由于由于HH C CT=0 0T，所以，所以 S S

39、T=HH E ET=HH R RT設設HH=(h h1,h h2,h hn)，其中，其中h hi表示表示HH的列。代入上式得到的列。代入上式得到02211EEEnnnThhhS 總結：總結：伴隨式僅與錯誤圖樣有關，而與發送的具體碼字無關，即伴隨式僅與錯誤圖樣有關，而與發送的具體碼字無關，即伴隨式僅由錯誤圖樣決定；伴隨式僅由錯誤圖樣決定；伴隨式是錯誤的判別式：伴隨式是錯誤的判別式：p若S=0，則判為沒有出錯，接收碼字是一個碼字；p若S0，則判為有錯。不同的錯誤圖樣具有不同的伴隨式，它們是一一對應的。不同的錯誤圖樣具有不同的伴隨式，它們是一一對應的。對二元碼，伴隨式對二元碼，伴隨式S是是H H 陣

40、中與錯誤碼元對應列之和陣中與錯誤碼元對應列之和。10110001110100H11000100110001SHR0TTT例例： (7,3)碼接收矢量碼接收矢量 R R 的伴隨式計算的伴隨式計算設發送碼矢設發送碼矢C C=1010011，接收碼字，接收碼字R R1010011，R R與與C C相相同。同。但接收端譯碼器并不知道就是發送的碼字，根據接收字但接收端譯碼器并不知道就是發送的碼字，根據接收字R計算伴隨式，把計算伴隨式，把H和和R代入得到：代入得到：因此因此 譯碼器判接收字無錯。譯碼器判接收字無錯。正確。錯能力相符，所以譯碼中錯誤碼元數與碼的糾由于接收字的第二位是錯的。因此判定接收字的第二

41、列，等于且碼是糾單個錯誤的碼，譯碼器判為有錯。由于伴隨式為接收碼字發送碼矢RRHS)3 , 7(, 0S111011001111000110010001100101110001101RHS,1110011R,1010011CTTTT若接收碼字中有一位錯誤若接收碼字中有一位錯誤C1010011,R0011011,:001 0 1 1 0 0 0011 1 1 0 1 0 01SH R11 1 0 0 0 1 0100 1 1 0 0 0 1011S0TTT 發送碼矢接收碼字伴隨式為由于是第一列和第四列之和，也是第二列和第七列之和，不等于 ，無法判定錯誤出在哪些位上，只是發現有錯。當碼元錯誤多于當

42、碼元錯誤多于1個時個時伴隨式計算電路：伴隨式計算電路：伴隨式的計算可用電路來實現。伴隨式的計算可用電路來實現。以以(7,3)碼為例：設接收字為碼為例：設接收字為R R=(R6R5R4R3R2R1R0)，伴隨式，伴隨式為為根據上式可畫出伴隨式計算電路，見下頁。根據上式可畫出伴隨式計算電路，見下頁。0123045156245634601234561000110010001100101110001101RHSSSSSRRRRRRRRRRRRRRRRRRRRTTR0R1R2R3R4R5R6輸入S0 (7,3)碼伴隨式計算電路S3S2S1輸出 最佳譯碼準則（最大后驗概率譯碼最佳譯碼準則（最大后驗概率譯碼

43、MAP）通信是一個統計過程，糾、檢錯能力最終要反映到差錯概率通信是一個統計過程，糾、檢錯能力最終要反映到差錯概率上。上。對于對于FEC方式，采用糾錯碼后的碼字差錯概率為方式，采用糾錯碼后的碼字差錯概率為pwe，pp(C)：發送碼字C 的先驗概率pp(C/R)：后驗概率若碼字數為若碼字數為 2k，對充分隨機的消息源有，對充分隨機的消息源有p(C C)=1/ 2k，所以最小，所以最小化化pwe等價為最小化等價為最小化p(C CC CR R )，又等價為最大化，又等價為最大化p(C C=C CR R)；)()(RCCCpppwe線性分組碼的譯碼線性分組碼的譯碼由貝葉斯公式：由貝葉斯公式：對于對于 B

44、SC 信道：最大化后驗概率信道：最大化后驗概率p(C C=C CR R) 等價于最大化等價于最大化似然函數似然函數p(R RC C) 最大化最大化p(R RC C) 又等價于最小化又等價于最小化 d(R R,C C)，所以使差錯概率最，所以使差錯概率最小的譯碼是使接收向量小的譯碼是使接收向量 R R 與輸出碼字與輸出碼字 C C 距離最小的譯碼。距離最小的譯碼。) ,(),(min: CRCRCCddiip p( (R R) )p p( (R R/ /C C) )p p( (C C) )p p( (C C/ /R R) ) 標準陣列譯碼標準陣列譯碼碼矢參數碼矢參數p發送碼矢：取自于 2k 個碼

45、字集合C；p接收矢量：可以是 2n 個 n 重中任一個矢量。譯碼方法譯碼方法p把 2n 個 n 重矢量劃分為 2k 個互不相交的子集 ，使得在每個子集中僅含一個碼矢；p根據碼矢和子集間一一對應關系，若接收矢量 Rl 落在子集 Dl中，就把 Rl 譯為子集 Dl 含有的碼字 Cl；p當接收矢量 R 與實際發送碼矢在同一子集中時，譯碼就是正確的。標準陣列標準陣列：是對給定的：是對給定的 (n,k) 線性碼，將線性碼，將 2n 個個 n 重重劃分為劃分為 2k 個子集的一種方法。個子集的一種方法。k221,DDD標準陣列構造方法標準陣列構造方法p先將 2k 個碼矢排成一行，作為標準陣列的第一行，并將

46、全0碼矢C1=(000)放在最左面的位置上；p然后在剩下的 (2n2k) 個 n 重中選取一個重量最輕的 n 重 E2 放在全0碼矢 C1 下面，再將 E2 分別和碼矢 相加，放在對應碼矢下面，構成陣列第二行；p在第二次剩下的 n 重中，選取重量最輕的 n 重 E3，放在 E2 下面，并將 E3 分別加到第一行各碼矢上，得到第三行；p，繼續這樣做下去，直到全部 n 重用完為止。得到下頁表格所示的 (n,k) 線性碼的標準陣列。k232,CCCk2C22ECk32ECkknk22ECkni2ECkn22ECkn2E標準陣列的特性：標準陣列的特性：在標準陣列的同一行中沒有相同的矢量，而且在標準陣列

47、的同一行中沒有相同的矢量，而且 2n 個個 n 重重中任一個中任一個 n 重在陣列中出現一次且僅出現一次。重在陣列中出現一次且僅出現一次。 證明證明：L因為陣列中任一行都是由所選出某一 n 重矢量分別與 2k 個碼矢相加構成的，而 2k 個碼矢互不相同，它們與所選矢量的和也不可能相同，所以在同一行中沒有相同的矢量；L在構造標準陣列時，是用完全部 n 重為止，因而每個 n 重必出現一次；L接下頁L每個n重只能出現一次。 假定某一 n 重 X 出現在第 l 行第 i 列，那么 XEl+Ci， 又假設 X 出現在第 m 行第 j 列，那么 XEm+Cj，ll)的第的第 一個元素，一個元素， 而按陣列

48、構造規則，后面行的第一個元素而按陣列構造規則，后面行的第一個元素是前面行中未曾出現過的元素，這就和陣列構造規則相矛盾。是前面行中未曾出現過的元素，這就和陣列構造規則相矛盾。線性碼糾錯極限定理：二元線性碼糾錯極限定理：二元 (n,k) 線性碼能糾線性碼能糾 2nk 個錯誤圖個錯誤圖樣。這樣。這 2nk 個可糾的錯誤圖樣，包括個可糾的錯誤圖樣，包括0 0矢量在內，即把無錯矢量在內，即把無錯的情況也看成一個可糾的錯誤圖樣。的情況也看成一個可糾的錯誤圖樣。 證明：L(n,k) 線性碼的標準陣列有 2k 列（和碼矢量相等），2n/2k= 2nk行，且任何兩列和兩行都沒有相同的元素。L陪集：標準陣列的每一

49、行叫做碼的一個陪集。L陪集首：每個陪集的第一個元素叫做陪集首。L每一列包含 2nk 個元素，最上面的是一個碼矢，其它元素是陪集首和該碼矢之和，例如第 j 列為L接下頁),(232jjjjjknCECECECDL若發送碼矢為若發送碼矢為 C Cj，信道干擾的錯誤圖樣是陪集首，信道干擾的錯誤圖樣是陪集首，則接收矢量則接收矢量 R R 必在必在 D Dj 中；中；L若錯誤圖樣不是陪集首，則接收矢量若錯誤圖樣不是陪集首，則接收矢量 R R不在不在 D Dj 中，中，則譯成其它碼字，造成錯誤譯碼；則譯成其它碼字，造成錯誤譯碼；L當且僅當錯誤圖樣為陪集首時，譯碼才是正確的。當且僅當錯誤圖樣為陪集首時，譯碼

50、才是正確的。L可糾正的錯誤圖樣可糾正的錯誤圖樣：這：這 2nk 個陪集首稱為可糾正的個陪集首稱為可糾正的錯誤圖樣。錯誤圖樣。線性碼糾錯能力與監督元數目的關系：一個可糾線性碼糾錯能力與監督元數目的關系：一個可糾 t 個錯誤的個錯誤的線性碼必須滿足線性碼必須滿足此條件為漢明限。此條件為漢明限。 漢明限等號成立時的線性碼稱為漢明限等號成立時的線性碼稱為完備碼完備碼。即。即tiknintnnn02112tiknin02標準陣列譯碼標準陣列譯碼=最小距離譯碼法最小距離譯碼法=最佳譯碼法最佳譯碼法l 陪集首是可糾正的錯誤圖樣，為了使譯碼錯誤概率最小，應陪集首是可糾正的錯誤圖樣，為了使譯碼錯誤概率最小，應選

51、取出現概率最大的錯誤圖樣作陪集首；選取出現概率最大的錯誤圖樣作陪集首；l 重量較輕的錯誤圖樣出現概率較大，所以在構造標準陣列時重量較輕的錯誤圖樣出現概率較大，所以在構造標準陣列時是選取重量最輕的是選取重量最輕的 n 重作陪集首；重作陪集首；l 這樣，當錯誤圖樣為陪集首時（可糾的錯誤圖樣），接收矢這樣，當錯誤圖樣為陪集首時（可糾的錯誤圖樣），接收矢量與原發送碼矢間的距離（等于陪集首）最??；量與原發送碼矢間的距離（等于陪集首）最?。籰 因此，選擇重量最輕的元素作陪集首，按標準陣列譯碼就是因此，選擇重量最輕的元素作陪集首，按標準陣列譯碼就是按最小距離譯碼；按最小距離譯碼；l 所以標準陣列譯碼法也是最

52、佳譯碼法。所以標準陣列譯碼法也是最佳譯碼法。在標準陣列中，一個陪集的所有在標準陣列中，一個陪集的所有 2k 個個 n 重有相同的伴隨式，重有相同的伴隨式，不同的陪集伴隨式互不相同。不同的陪集伴隨式互不相同。 證明證明：p設 H 為給定 (n,k) 線性碼的監督矩陣，在陪集首為 El 的陪集中的任意矢量 R 為 R=El+Ci, i=1,2,2kp其伴隨式為 S=RHT=(El+Ci)HT=ElHT+CiHT =ElHTp上式表明：陪集中任意矢量的伴隨式等于陪集首的伴隨式。即同一陪集中所有伴隨式相同。p不同陪集中，由于陪集首不同，所以伴隨式不同。結論：結論：任意任意 n 重的伴隨式決定于它在標準

53、陣列中所在陪集的陪集首。重的伴隨式決定于它在標準陣列中所在陪集的陪集首。標準陣列的陪集首和伴隨式是一一對應的，因而碼的可糾錯標準陣列的陪集首和伴隨式是一一對應的，因而碼的可糾錯誤圖樣和伴隨式是一一對應的，應用此對應關系可以構成比誤圖樣和伴隨式是一一對應的，應用此對應關系可以構成比標準陣列簡單得多的譯碼表，從而得到標準陣列簡單得多的譯碼表，從而得到 (n,k) 線性碼的一般線性碼的一般譯碼步驟：譯碼步驟：p計算接收矢量 R 的伴隨式 ST=HRT ；p根據伴隨式和錯誤圖樣一一對應的關系，利用伴隨式譯碼表，由伴隨式譯出 R 的錯誤圖樣 E；p將接收碼字減錯誤圖樣，得發送碼矢的估值 C=RE 。 上

54、述譯碼法稱為伴隨式譯碼法或查表譯碼法。線性分組碼一般譯碼器結構：線性分組碼一般譯碼器結構： 這種查表譯碼法具有最小的譯碼延遲和最小的譯碼錯這種查表譯碼法具有最小的譯碼延遲和最小的譯碼錯誤概率，原則上可用于任何誤概率，原則上可用于任何 (n,k) 線性碼。線性碼。伴隨式計算電路SE組合邏輯電路糾錯(RE)電路輸入輸出 線性分組碼一般譯碼器常見的線性分組碼奇偶監督碼奇偶監督碼漢明碼漢明碼BCH碼碼RS碼碼CRC碼碼奇偶監督碼采用奇偶校驗原理。采用奇偶校驗原理。只能檢錯，不能糾錯。只能檢錯，不能糾錯。只能檢查出某一分組的單個錯誤或奇數個錯誤，而不能發只能檢查出某一分組的單個錯誤或奇數個錯誤，而不能發

55、現偶數個錯誤?，F偶數個錯誤。最小碼距為最小碼距為2。水平奇偶監督碼水平奇偶監督碼水平垂直奇偶監督碼。水平垂直奇偶監督碼。 漢明碼是漢明于漢明碼是漢明于1950年提出的糾一個錯誤的線性碼。由于年提出的糾一個錯誤的線性碼。由于它編碼簡單，因而在通信系統和數據存儲系統中得到廣泛它編碼簡單，因而在通信系統和數據存儲系統中得到廣泛應用。應用。漢明碼的結構：漢明碼的結構：p糾一個錯誤的線性碼，其最小距離 dmin=3 ；監督矩陣任意兩列線性無關；沒有全0的列。p監督元個數 nk=r；H 陣中每列有 r個元素，至多可構成 2r1種互不相同的非0列。p對于任意正整數 r3，漢明碼的結構參數為碼長：碼長： n=2r1信息位數：信息位數： k=2rr1監督位數：監督位數： nk=r碼的最小距離：碼的最小距離：dmin=3(t=1)漢明碼（Hamming碼）漢明碼監督矩陣構成的兩種方式漢明碼監督矩陣構成的兩種方式p構成 H 陣的標準形式，H=Q Im，其中 Im 為 m 階單位子陣，子陣 Q 是構造 Im 后剩下的列任意排列。用這種形式的 H