信道的糾錯編碼詳解課件

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

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

3、型及分類 為了方便研究，將信息傳輸系統(tǒng)模型簡化成下圖所示的簡化模型簡化的信息傳輸系統(tǒng)模型 模型突出了以控制差錯為目的的糾錯碼編碼器和譯碼器，因此也稱為差錯控制系統(tǒng)。在差錯控制系統(tǒng)中使用的碼按其糾錯能力的不同可分為兩種：檢錯碼和糾錯碼。 能發(fā)現(xiàn)錯誤但不能糾正錯誤的碼稱為檢錯碼 ； 不僅能發(fā)現(xiàn)錯誤而且還能糾正錯誤的碼稱為糾錯碼。（）前向糾錯(FEC)方式 ： FEC (Forward Error Control) 方式是發(fā)端發(fā)送有糾錯能力的碼（糾錯碼），接收端收到這些碼后，通過糾錯譯碼器自動地糾正傳輸中的錯誤。 差錯控制系統(tǒng)大致可分為前向糾錯、反饋重發(fā)和混合糾錯等三種方式。l優(yōu)點是不需要反饋信道；

4、能進行一個用戶對多個用戶的同時通信，特別適合于移動通信；譯碼實時性較好，控制電路也比較簡單。 l缺點是譯碼設(shè)備較復(fù)雜；編碼效率較低。（）反饋重發(fā)(ARQ)方式: ARQ (Automatic Repeat Request) 方式是：發(fā)端發(fā)出能夠發(fā)現(xiàn)錯誤的碼（檢錯碼），收端譯碼器收到后，判斷在傳輸中有無錯誤產(chǎn)生，并通過反饋信道把撿測結(jié)果告訴發(fā)端。發(fā)端把收端認(rèn)為有錯的消息再次傳送，直到收端認(rèn)為正確接收為止。 l優(yōu)點是譯碼設(shè)備簡單，在多余度一定的情況下，碼的檢錯能力比糾錯能力要高得多，因而整個系統(tǒng)能獲得極低的誤碼率。l應(yīng)用ARQ方式必須有一條從收端至發(fā)端的反饋信道。并要求信源產(chǎn)生信息的速率可以進行控

5、制，收、發(fā)兩端必須互相配合，其控制電路比較復(fù)雜，傳輸信息的連貫性和實時性也較差。（）混合糾錯(HEC)方式： HEC (Hybrid Error Control) 方式是上述兩種方式的結(jié)合。發(fā)端發(fā)送的碼既能檢錯、又有一定的糾錯能力。收端譯碼時若發(fā)現(xiàn)錯誤個數(shù)在碼的糾錯能力以內(nèi)，則自動進行糾錯；若錯誤個數(shù)超過了碼的糾錯能力，但能檢測出來，則通過反饋信道告知發(fā)方重發(fā)。這種方式在一定程度上避免了 FEC方式譯碼設(shè)備復(fù)雜和 ARQ方式信息連貫性差的缺點。 在設(shè)計差錯控制系統(tǒng)時，選擇何種實現(xiàn)方式，應(yīng)綜合考慮各方面的因素。主要有： 滿足用戶對誤碼率的要求； 有盡可能高的信息傳輸速率； (4)可接受的成本。

6、有盡可能簡單的編譯碼算法且易于實現(xiàn)；糾錯碼的分類 按信息位與校驗位的關(guān)系，可將編碼分成以下兩大類：（1）線性碼校驗位與信息位呈線性關(guān)系（即可用一次方程描述）。（2）非線性碼校驗位與信息位不呈線性關(guān)系。按信息位與校驗位之間的約束關(guān)系，可分為：（1）分組碼將信息符號分成k位一組，每組增加r位校驗位，這r位校驗位僅與本組的k位信息位有關(guān)，與其他的信息位無關(guān)。 循環(huán)碼除全零碼字外，其余碼字都可由另一碼字的碼符循 環(huán)移位得到； 非循環(huán)碼某個碼字的循環(huán)移位不一定還是該碼的碼字。（2）卷積碼將信息符號分成k位一組，每組增加r位校驗位，這r位校驗位不僅與本組的k位信息位有關(guān)，還與前面m組的信息位有關(guān)。線性分組

7、碼的編碼過程分為兩步：把信息序列按一定長度分成若干信息碼組，每組由 k 位組成；編碼器按照預(yù)定的線性規(guī)則(可由線性方程組規(guī)定)，把信息碼組變換成 n 重 (nk) 碼字，其中 (nk) 個附加碼元是由信息碼元的線性運算產(chǎn)生的。信息碼組長 k 位，有 2k 個不同的信息碼組，則應(yīng)該有 2k 個碼字與它們一一對應(yīng)。 線性分組碼線性分組碼：通過預(yù)定的線性運算將長為 k 位的信息碼組變換成 n位的碼字 (nk)。由 M=2k 個信息碼組所編成的 2k個碼字集合，稱為線性分組碼。碼矢：一個 n 重的碼字可以用矢量來表示C=(Cn1,Cn1,C1,C0 )所以碼字又稱為碼矢。(n,k) 線性碼：信息位長為

8、 k，碼長為 n 的線性碼。碼率/信道的傳信率：R=logM/n=k /n。它表示信道編碼后每個碼符號攜帶的信息量，說明了信道的利用效率，R是衡量編碼性能的一個重要參數(shù)。一致監(jiān)督方程：編碼就是給已知信息碼組按預(yù)定規(guī)則添加監(jiān)督碼元，以構(gòu)成碼字。在 k 個信息碼元之后附加 r(r=nk) 個監(jiān)督碼元，使每個監(jiān)督元是其中某些信息元的模2和。一致監(jiān)督方程/一致校驗方程：確定信息元得到監(jiān)督元規(guī)則的一組方程稱為監(jiān)督方程/校驗方程。由于所有碼字都按同一規(guī)則確定，又稱為一致監(jiān)督方程/一致校驗方程。由于一致監(jiān)督方程是線性的，即監(jiān)督元和信息元之間是線性運算關(guān)系，所以由線性監(jiān)督方程所確定的分組碼是線性分組碼。一致監(jiān)

9、督方程和一致監(jiān)督矩陣?yán)齥=3, r=4構(gòu)成 (7,3) 線性分組碼。設(shè)碼字為(C6,C5,C4,C3,C2,C1,C0)C6,C5,C4為信息元，C3,C2,C1,C0為監(jiān)督元，每個碼元取“0”或“1”監(jiān)督元可按下面方程組計算信息碼組 (101)，即C6=1, C5=0, C4=1由線性方程組得： C3=0, C2=0, C1=1, C0=1即信息碼組 (101) 編出的碼字為 (1010011)。其它7個碼字如表。一致監(jiān)督矩陣：將監(jiān)督方程寫成矩陣形式，得： H CT=0T或 C HT=0 CT、HT、0T分別表示C、H、0的轉(zhuǎn)置矩陣。系數(shù)矩陣 H 的后四列組成一個 (44) 階單位子陣，用

10、I4 表示，H 的其余部分用 P 表示推廣到一般情況：對 (n,k) 線性分組碼，每個碼字中的 r(r=nk) 個監(jiān)督元與信息元之間的關(guān)系可由下面的線性方程組確定令系數(shù)矩陣為 H，碼字行陣列為 C一致監(jiān)督方程和一致監(jiān)督矩陣一致監(jiān)督矩陣特性:對H 各行實行初等變換，將后面 r 列化為單位子陣，于是得到下面矩陣(行變換所得方程組與原方程組同解)。監(jiān)督矩陣H 的標(biāo)準(zhǔn)形式：后面 r 列是一單位子陣的監(jiān)督矩陣H。H 陣的每一行都代表一個監(jiān)督方程，它表示與該行中“1”相對應(yīng)的碼元的模2和為0。H 的標(biāo)準(zhǔn)形式還說明了相應(yīng)的監(jiān)督元是由哪些信息元決定的。例如 (7,3) 碼的H 陣的第一行為 (1011000)

11、，說明此碼的第一個監(jiān)督元等于第一個和第三個信息元的模2和，依此類推。 H 陣的 r 行代表了 r 個監(jiān)督方程，也表示由H 所確定的碼字有 r 個監(jiān)督元。為了得到確定的碼，r 個監(jiān)督方程（或H 陣的r 行）必須是線性無關(guān)的，這要求H 陣的秩為 r。若把H 陣化成標(biāo)準(zhǔn)形式，只要檢查單位子陣的秩，就能方便地確定H 陣本身的秩。線性碼的封閉性:線性碼的封閉性：線性碼任意兩個碼字之和仍是一個碼字。證明：若 U 和 V 為線性碼的任意兩個碼字，故有HUT=0T，HVT=0T那么 H(U+V)T=H(UT+VT)=HUT+HVT=0T即 U+V 滿足監(jiān)督方程，所以 U+V 一定是一個碼字。一個長為 n 的二

12、元序列可以看作是GF(2)(二元域)上的 n 維線性空間中的一點。長為 n 的所有 2n 個矢量集合構(gòu)成了GF(2)上的 n 維線性空間Vn。把線性碼放入線性空間中進行研究，將使許多問題簡化而比較容易解決。(n,k) 線性碼是 n 維線性空間Vn中的一個 k 維子空間 Vk。線性分組碼的生成矩陣線性分組碼的生成矩陣:在由 (n,k) 線性碼構(gòu)成的線性空間 Vn 的 k 維子空間中，一定存在 k 個線性無關(guān)的碼字：g1,g2, gk,。碼 CI 中其它任何碼字C都可表示為這 k 個碼字的線性組合，即G中每一行 gi=(gi1,gi2, gin ) 都是一個碼字；對每一個信息組m，由矩陣G都可以求

13、得 (n,k) 線性碼對應(yīng)的碼字。生成矩陣：由于矩陣 G 生成了 (n,k) 線性碼，稱矩陣 G 為 (n,k) 線性碼的生成矩陣。(n,k) 線性碼的每一個碼字都是生成矩陣 G 的行矢量的線性組合，所以它的 2k 個碼字構(gòu)成了由 G 的行張成的 n 維空間Vn的一個 k 維子空間 Vk。線性系統(tǒng)分組碼: 通過行初等變換，將 G 化為前 k 列是單位子陣的標(biāo)準(zhǔn)形式 線性系統(tǒng)分組碼：用標(biāo)準(zhǔn)生成矩陣 Gkn 編成的碼字，前面 k 位為信息數(shù)字，后面 r=nk 位為校驗字，這種信息數(shù)字在前校驗數(shù)字在后的線性分組碼稱為線性系統(tǒng)分組碼。當(dāng)生成矩陣 G 確定之后，(n,k) 線性碼也就完全被確定了，只要找

14、到碼的生成矩陣，編碼問題也同樣解決了。例: (7,4) 線性碼的生成矩陣為生成矩陣與一致監(jiān)督矩陣的關(guān)系:由于生成矩陣G的每一行都是一個碼字，所以G 的每行都滿足HrnCTn1=0Tr1，則有HrnGTnk=0Trk 或 GknHTnr=0kr線性系統(tǒng)碼的監(jiān)督矩陣 H 和生成矩陣 G 之間可以直接互換。例: 已知(7,4)線性系統(tǒng)碼的監(jiān)督矩陣為對偶碼：一個(n,k)線性碼 CI，如果以G 作監(jiān)督矩陣，而以H 作生成矩陣，可構(gòu)造另一個 (n,nk)線性碼CId ，稱碼CId為原碼的對偶碼。(7,3)碼的監(jiān)督矩陣H(7,3)是(7,4)碼的生成矩陣G(7,4) (7,4) 碼的監(jiān)督矩陣 H(7,4)

15、是(7,3) 碼的生成矩陣 G(7,3)(n,k) 線性碼的編碼就是根據(jù)線性碼的監(jiān)督矩陣或生成矩陣將長為 k 的信息組變換成長為 n(nk) 的碼字。利用監(jiān)督矩陣構(gòu)造 (7,3) 線性分組碼的編碼電路：設(shè)碼字矢量為C=(C6 C5C4C3C2C1C0)碼的監(jiān)督矩陣為線性分組碼的編碼根據(jù)方程組可直接畫出 (7,3) 碼的并行和串行編碼電路。漢明距離、漢明重量和漢明球漢明距離：在 (n,k)線性碼中，兩個碼字 U、V 之間對應(yīng)碼元位上符號取值不同的個數(shù)，稱為碼字 U、V 的漢明距離。例：(7,3) 碼的兩個碼字 U=0011101,V=0100111之間第2、3、4和6位不同。因此，碼字 U 和

16、V 的距離為4。線性分組碼的一個碼字對應(yīng)于 n 維線性空間中的一點，碼字間的距離即為空間中兩對應(yīng)點的距離。因此，碼字間的距離滿足一般距離公理：線性分組碼的最小距離、檢錯和糾錯能力最小距離dmin：在 (n,k) 線性碼的碼字集合中，任意兩個不同碼字間距離的最小值，叫做碼的最小距離。若C(i)和C(j) 是任意兩個碼字，則碼的最小距離表示為 碼的最小距離是衡量碼的抗干擾能力（檢、糾錯能力）的重要參數(shù)。碼的最小距離越大，碼的抗干擾能力就越強。漢明球：以碼字C為中心，半徑為 t 的漢明球是與 C 的漢明距離 t 的向量全體集合 SC(t) 任意兩個漢明球不相交最大程度取決于任意兩個碼字之間的最小漢明

17、距離dmin。 漢明重量W：碼字中非0碼元符號的個數(shù)，稱為該碼字的漢明重量。在二元線性碼中，碼字重量就是碼字中“1”的個數(shù)。最小重量Wmin ：線性分組碼CI中，非0碼字重量的最小值，叫做碼CI的最小重量：Wmin =minW(V),VCI ,V0最小距離與最小重量的關(guān)系：線性分組碼的最小距離等于它的最小重量。 證明：設(shè)線性碼CI，且UCI, VCI，又設(shè)UV=Z，由線性碼的封閉性知，ZCI 。因此，d(U,V)=W(Z)，由此可推知，線性分組碼的最小距離必等于非0碼字的最小重量。最小距離與檢、糾錯能力：一般地說，線性碼的最小距離越大，意味著任意碼字間的差別越大，則碼的檢、糾錯能力越強。檢錯能

18、力：一個線性碼能檢出長度l 個碼元的任何錯誤圖樣，稱碼的檢錯能力為 l。糾錯能力：線性碼能糾正長度t 個碼元的任意錯誤圖樣，稱碼的糾錯能力為 t。最小距離與糾錯能力：(n,k) 線性碼能糾 t 個錯誤的充要條件是碼的最小距離為 證明： 設(shè)發(fā)送的碼字為V；接收的碼字為R；U為任意其它碼字； 則矢量V、R、U間滿足距離的三角不等式， d(R,V)+d(R,U)d(U,V) 又設(shè)信道干擾使碼字中碼元發(fā)生錯誤的實際個數(shù)為 t，且tt d(R,V)tt 由于d(U,V)dmin=2t+1，代入上式得： d(R,U) d(U,V)d(R,V)= 2t+1tt 上式表明：如果接收碼字 R 中錯誤個數(shù) tt，

19、那么接收碼字 R 和發(fā)送碼字 V 間距離t ，而與其它任何碼字間距離都大于 t，按最小距離譯碼把R譯為V。此時譯碼正確，碼字中的錯誤被糾正。 最小距離與檢錯能力：(n,k) 線性碼能夠發(fā)現(xiàn) l 個錯誤的充要條件是碼的最小距離為 dmin=l+1 或 l=dmin1 證明： 設(shè)發(fā)送的碼字為 V；接收的碼字為 R；U 為任意其它碼字； 則矢量V、R、U間滿足距離的三角不等式， d(R,V)+d(R,U)d(U,V) 又設(shè)信道干擾使碼字中碼元發(fā)生錯誤的實際個數(shù)為 l，且ll d(R,V)ll 由于d(U,V)dmin=l+1，代入上式得： d(R,U) d(U,V)d(R,V)=l+1l0 上式表明

20、：由于接收碼字 R 與其它任何碼字 U 的距離都大于0，則說明接收字 R 不會因發(fā)生 l 個錯誤變?yōu)槠渌a字，因而必能發(fā)現(xiàn)錯誤。 最小距離與檢、糾錯能力：(n,k) 線性碼能糾 t 個錯誤，并能發(fā)現(xiàn) l 個錯誤 (lt) 的充要條件是碼的最小距離為 dmin=t+l+1 或 t+l=dmin1 證明： 因為dmin2t+1，根據(jù)最小距離與糾錯能力定理，該碼可糾 t 個錯誤。 又因為dminl+1，根據(jù)最小距離與檢錯能力定理，該碼有檢 l 個錯誤的能力。 糾錯和檢錯不會發(fā)生混淆：設(shè)發(fā)送碼字為 V，接收字為 R，實際錯誤數(shù)為 l，且 tt+1t 因而不會把 R 誤糾為 U。 幾何意義：當(dāng) (n,k

21、) 線性碼的最小距離 dmin 給定后，可按實際需要靈活安排糾錯的數(shù)目。例如，對 dmin=8 的碼，可用來糾3檢4錯，或糾2檢5錯，或糾1檢6錯，或者只用于檢7個錯誤。伴隨式和錯誤檢測：用監(jiān)督矩陣譯碼：接收到一個碼字 R 后，檢驗 HRT=0T 是否成立：HRT =0T是否成立是檢驗碼字出錯與否的依據(jù)。若關(guān)系成立，則認(rèn)為 R 是一個碼字；否則判為碼字在傳輸中發(fā)生了錯誤；伴隨式/監(jiān)督子/校驗子：S=RHT或ST=HRT。如何糾錯？設(shè)發(fā)送碼矢 C=(Cn1,Cn2,C0)信道錯誤圖樣為 E=(En1,En2,E0) ，其中Ei=0，表示第i位無錯；Ei=1，表示第i位有錯。i=n1,n2,0。線

22、性分組碼的伴隨式接收碼字 R =(Rn1,Rn2,R0)=C+E =(Cn1+En1, Cn2+En2, , C0 +E0)求接收碼字的伴隨式（接收碼字用監(jiān)督矩陣進行檢驗） ST=HRT=H(C+E)T=HCT+HET由于HCT=0T，所以 ST=HET=HRT設(shè)H=(h1,h2,hn)，其中hi表示H的列。代入上式得到 總結(jié)：伴隨式僅與錯誤圖樣有關(guān)，而與發(fā)送的具體碼字無關(guān)，即伴隨式僅由錯誤圖樣決定；伴隨式是錯誤的判別式：若S=0，則判為沒有出錯，接收碼字是一個碼字；若S0，則判為有錯。不同的錯誤圖樣具有不同的伴隨式，它們是一一對應(yīng)的。對二元碼，伴隨式S是H 陣中與錯誤碼元對應(yīng)列之和。例： (

23、7,3)碼接收矢量 R 的伴隨式計算設(shè)發(fā)送碼矢C=1010011，接收碼字R1010011，R與C相同。但接收端譯碼器并不知道就是發(fā)送的碼字，根據(jù)接收字R計算伴隨式，把H和R代入得到：因此 譯碼器判接收字無錯。若接收碼字中有一位錯誤當(dāng)碼元錯誤多于1個時伴隨式計算電路：伴隨式的計算可用電路來實現(xiàn)。以(7,3)碼為例：設(shè)接收字為R=(R6R5R4R3R2R1R0)，伴隨式為根據(jù)上式可畫出伴隨式計算電路，見下頁。 最佳譯碼準(zhǔn)則（最大后驗概率譯碼MAP）通信是一個統(tǒng)計過程，糾、檢錯能力最終要反映到差錯概率上。對于FEC方式，采用糾錯碼后的碼字差錯概率為pwe，p(C)：發(fā)送碼字C 的先驗概率p(C/R

24、)：后驗概率若碼字?jǐn)?shù)為 2k，對充分隨機的消息源有p(C)=1/ 2k，所以最小化pwe等價為最小化p(CCR )，又等價為最大化p(C=CR)；線性分組碼的譯碼由貝葉斯公式：對于 BSC 信道：最大化后驗概率p(C=CR) 等價于最大化似然函數(shù)p(RC) 最大化p(RC) 又等價于最小化 d(R,C)，所以使差錯概率最小的譯碼是使接收向量 R 與輸出碼字 C 距離最小的譯碼。 標(biāo)準(zhǔn)陣列譯碼碼矢參數(shù)發(fā)送碼矢：取自于 2k 個碼字集合C；接收矢量：可以是 2n 個 n 重中任一個矢量。譯碼方法把 2n 個 n 重矢量劃分為 2k 個互不相交的子集 ，使得在每個子集中僅含一個碼矢；根據(jù)碼矢和子集間

25、一一對應(yīng)關(guān)系，若接收矢量 Rl 落在子集 Dl中，就把 Rl 譯為子集 Dl 含有的碼字 Cl；當(dāng)接收矢量 R 與實際發(fā)送碼矢在同一子集中時，譯碼就是正確的。標(biāo)準(zhǔn)陣列：是對給定的 (n,k) 線性碼，將 2n 個 n 重劃分為 2k 個子集的一種方法。標(biāo)準(zhǔn)陣列構(gòu)造方法先將 2k 個碼矢排成一行，作為標(biāo)準(zhǔn)陣列的第一行，并將全0碼矢C1=(000)放在最左面的位置上；然后在剩下的 (2n2k) 個 n 重中選取一個重量最輕的 n 重 E2 放在全0碼矢 C1 下面，再將 E2 分別和碼矢 相加，放在對應(yīng)碼矢下面，構(gòu)成陣列第二行；在第二次剩下的 n 重中，選取重量最輕的 n 重 E3，放在 E2 下

26、面，并將 E3 分別加到第一行各碼矢上，得到第三行；，繼續(xù)這樣做下去，直到全部 n 重用完為止。得到下頁表格所示的 (n,k) 線性碼的標(biāo)準(zhǔn)陣列。標(biāo)準(zhǔn)陣列的特性：在標(biāo)準(zhǔn)陣列的同一行中沒有相同的矢量，而且 2n 個 n 重中任一個 n 重在陣列中出現(xiàn)一次且僅出現(xiàn)一次。 證明：因為陣列中任一行都是由所選出某一 n 重矢量分別與 2k 個碼矢相加構(gòu)成的，而 2k 個碼矢互不相同，它們與所選矢量的和也不可能相同，所以在同一行中沒有相同的矢量；在構(gòu)造標(biāo)準(zhǔn)陣列時，是用完全部 n 重為止，因而每個 n 重必出現(xiàn)一次；接下頁每個n重只能出現(xiàn)一次。 假定某一 n 重 X 出現(xiàn)在第 l 行第 i 列，那么 XEl

27、+Ci， 又假設(shè) X 出現(xiàn)在第 m 行第 j 列，那么 XEm+Cj，ll)的第 一個元素， 而按陣列構(gòu)造規(guī)則，后面行的第一個元素是前面行中未曾出現(xiàn)過的元素，這就和陣列構(gòu)造規(guī)則相矛盾。線性碼糾錯極限定理：二元 (n,k) 線性碼能糾 2nk 個錯誤圖樣。這 2nk 個可糾的錯誤圖樣，包括0矢量在內(nèi)，即把無錯的情況也看成一個可糾的錯誤圖樣。 證明：(n,k) 線性碼的標(biāo)準(zhǔn)陣列有 2k 列（和碼矢量相等），2n/2k= 2nk行，且任何兩列和兩行都沒有相同的元素。陪集：標(biāo)準(zhǔn)陣列的每一行叫做碼的一個陪集。陪集首：每個陪集的第一個元素叫做陪集首。每一列包含 2nk 個元素，最上面的是一個碼矢，其它元素

28、是陪集首和該碼矢之和，例如第 j 列為接下頁若發(fā)送碼矢為 Cj，信道干擾的錯誤圖樣是陪集首，則接收矢量 R 必在 Dj 中；若錯誤圖樣不是陪集首，則接收矢量 R不在 Dj 中，則譯成其它碼字，造成錯誤譯碼；當(dāng)且僅當(dāng)錯誤圖樣為陪集首時，譯碼才是正確的?？杉m正的錯誤圖樣：這 2nk 個陪集首稱為可糾正的錯誤圖樣。線性碼糾錯能力與監(jiān)督元數(shù)目的關(guān)系：一個可糾 t 個錯誤的線性碼必須滿足此條件為漢明限。 漢明限等號成立時的線性碼稱為完備碼。即標(biāo)準(zhǔn)陣列譯碼=最小距離譯碼法=最佳譯碼法 陪集首是可糾正的錯誤圖樣，為了使譯碼錯誤概率最小，應(yīng)選取出現(xiàn)概率最大的錯誤圖樣作陪集首； 重量較輕的錯誤圖樣出現(xiàn)概率較大，

29、所以在構(gòu)造標(biāo)準(zhǔn)陣列時是選取重量最輕的 n 重作陪集首； 這樣，當(dāng)錯誤圖樣為陪集首時（可糾的錯誤圖樣），接收矢量與原發(fā)送碼矢間的距離（等于陪集首）最小； 因此，選擇重量最輕的元素作陪集首，按標(biāo)準(zhǔn)陣列譯碼就是按最小距離譯碼； 所以標(biāo)準(zhǔn)陣列譯碼法也是最佳譯碼法。在標(biāo)準(zhǔn)陣列中，一個陪集的所有 2k 個 n 重有相同的伴隨式，不同的陪集伴隨式互不相同。 證明：設(shè) H 為給定 (n,k) 線性碼的監(jiān)督矩陣，在陪集首為 El 的陪集中的任意矢量 R 為 R=El+Ci, i=1,2,2k其伴隨式為 S=RHT=(El+Ci)HT=ElHT+CiHT =ElHT上式表明：陪集中任意矢量的伴隨式等于陪集首的伴隨

30、式。即同一陪集中所有伴隨式相同。不同陪集中，由于陪集首不同，所以伴隨式不同。結(jié)論：任意 n 重的伴隨式?jīng)Q定于它在標(biāo)準(zhǔn)陣列中所在陪集的陪集首。標(biāo)準(zhǔn)陣列的陪集首和伴隨式是一一對應(yīng)的，因而碼的可糾錯誤圖樣和伴隨式是一一對應(yīng)的，應(yīng)用此對應(yīng)關(guān)系可以構(gòu)成比標(biāo)準(zhǔn)陣列簡單得多的譯碼表，從而得到 (n,k) 線性碼的一般譯碼步驟：計算接收矢量 R 的伴隨式 ST=HRT ；根據(jù)伴隨式和錯誤圖樣一一對應(yīng)的關(guān)系，利用伴隨式譯碼表，由伴隨式譯出 R 的錯誤圖樣 E；將接收碼字減錯誤圖樣，得發(fā)送碼矢的估值 C=RE 。 上述譯碼法稱為伴隨式譯碼法或查表譯碼法。線性分組碼一般譯碼器結(jié)構(gòu)： 這種查表譯碼法具有最小的譯碼延遲

31、和最小的譯碼錯誤概率，原則上可用于任何 (n,k) 線性碼。常見的線性分組碼奇偶監(jiān)督碼漢明碼BCH碼RS碼CRC碼奇偶監(jiān)督碼采用奇偶校驗原理。只能檢錯，不能糾錯。只能檢查出某一分組的單個錯誤或奇數(shù)個錯誤，而不能發(fā)現(xiàn)偶數(shù)個錯誤。最小碼距為2。水平奇偶監(jiān)督碼水平垂直奇偶監(jiān)督碼。 漢明碼是漢明于1950年提出的糾一個錯誤的線性碼。由于它編碼簡單，因而在通信系統(tǒng)和數(shù)據(jù)存儲系統(tǒng)中得到廣泛應(yīng)用。漢明碼的結(jié)構(gòu)：糾一個錯誤的線性碼，其最小距離 dmin=3 ；監(jiān)督矩陣任意兩列線性無關(guān)；沒有全0的列。監(jiān)督元個數(shù) nk=r；H 陣中每列有 r個元素，至多可構(gòu)成 2r1種互不相同的非0列。對于任意正整數(shù) r3，漢明碼的結(jié)構(gòu)參數(shù)為碼長： n=2r1信息位數(shù)： k=2rr1監(jiān)督位數(shù)： nk=r碼的最小距離：dmin=3(t=1)漢明碼（Hamming碼）漢明碼監(jiān)督矩陣構(gòu)成的兩種方式構(gòu)成 H 陣的標(biāo)準(zhǔn)形式，H=Q Im，其中 Im 為 m 階單位子陣，子陣 Q 是構(gòu)造 Im 后剩下的列任意排列。用這種形式的 H 陣編出的漢明碼是系統(tǒng)碼。按m重表示的二進制順序排列。按這種形式 H 陣編出的碼是非系統(tǒng)碼。當(dāng)發(fā)生可糾的單個錯誤時，伴隨式為 H 陣中對應(yīng)的列，所以伴隨式的二進制數(shù)值就是錯誤位置號，