ch7線性分組糾錯編碼

第七章線性分組糾錯編碼本章主要內(nèi)容信道編碼的基本概念、原理線性分組（糾錯）碼的一般概念線性分組（糾錯）碼的生成矩陣和校驗矩陣線性分組（糾錯）碼的編碼線性分組（糾錯）碼的譯碼二元Hamming碼從一個已知線性分組碼來構(gòu)造一個新的線性分組碼信道編碼的基本概念信道編碼的目的提高信息傳輸?shù)目煽啃裕尤哂喽龋；舅枷?/p>

根據(jù)一定規(guī)律在待發(fā)的信息中加入一些多余的碼元（監(jiān)督碼元），以保證傳輸質(zhì)量。研究內(nèi)容

怎樣構(gòu)造最小冗余度、最大抗干擾性能的“好碼”。檢錯碼糾錯碼線性碼非線性碼循環(huán)碼非循環(huán)碼糾隨機(jī)錯誤碼糾突發(fā)錯誤碼糾混合錯誤碼糾同步錯誤碼系統(tǒng)碼非系統(tǒng)碼二元碼多元碼分組碼卷積碼信道編碼分類信道編碼的基本原理香農(nóng)信道編碼定理：R<C，無差錯傳輸。

對于一個給定的有干擾信道，如果信道容量為C，只要發(fā)送端以低于C的速率R發(fā)送信息(R為編碼器輸入的二元碼元速率)，則一定存在一種編碼方法，使編碼錯誤概率p隨著碼長n的增加，按指數(shù)下降到任意小的值?；驹?/p>

在被傳輸?shù)男畔⑿蛄猩细郊右恍┐a元(稱為監(jiān)督碼元)，這些多余的碼元與信息(數(shù)據(jù))碼元之間以某種確定的規(guī)則相互關(guān)聯(lián)著。接收端根據(jù)既定的規(guī)則檢驗信息元與監(jiān)督元之間的這種關(guān)系，如傳輸過程中發(fā)生差錯，則信息元與監(jiān)督元之間的這一關(guān)系將受到破壞，從而使接收端可以發(fā)現(xiàn)傳輸中的錯誤，乃至糾正錯誤。檢錯和糾錯“好”——0“壞”——1

無檢錯糾錯能力“好”——00“壞”——11

接收：00011011

譯出：好？？壞檢1位錯碼，無糾錯能力“好”——000“壞”——111

接收：000001010011100101110111

譯出：好？？？？？？壞譯出：好好好壞好壞壞壞檢至少2位錯碼，或檢1位錯碼并糾正“好”——0000“壞”——1111

接收：00000001001000110100010101100111

譯出：好好好？好？？壞接收：10001001101010111100110111101111

譯出：好？？壞？壞壞壞檢2位錯碼，并能糾正1位錯碼線性分組碼的基本概念(n,k)線性分組碼分組

k個信息元一組變換

n個碼元線性監(jiān)督元與信息元之間呈線性關(guān)系分組編碼器信源可發(fā)出種不同的消息組。

(n,k)分組碼共個碼字（許用碼字），其中只有k個是線性獨立的。R=k/n

編碼速率/碼率

R越小，冗余度就越大，檢錯和糾錯的能力越強(qiáng)；但也降低了傳輸信息的實際速率。R越大，碼的效率也就越高或傳信率越高。分組編碼器

系統(tǒng)碼結(jié)構(gòu)示意圖(r=n-k)kbit信息位（n-k）bit監(jiān)督位分組編碼器例：(7，3)線性分組碼

設(shè)該碼的碼字為c6c5c4c3c2c1c0，其中c6、c5、c4為信息元；c3、c2、c1、c0為監(jiān)督元，每個碼元取值為“0”或“1”，即ci∈GF(2)。監(jiān)督元可按下式計算：碼重：在信道編碼中，定義碼字中非零碼元的數(shù)目為碼字的漢明（Hamming)重量，簡稱碼重。例如“010”碼字的碼重為1，記為。“011”碼字的碼重為2，記為碼距：把兩個碼字之間對應(yīng)碼位上具有不同二元碼元的位數(shù)定義為兩碼字的漢明距離，簡稱碼距。例如dH(010,011)=1

最小漢明距離：碼字集合中任意兩碼字間的最小距離，稱為這一編碼的最小漢明距離，以dmin表示；在非零碼字中，重量最小者稱為該碼的最小漢明重量，它等于dmin

。漢明距離三個性質(zhì)：(1)對稱性：d(C1，C2)＝d(C2，C1)；(2)非負(fù)性：d(C1，C2)≥0；

(3)滿足距離三角不等式：

d(C1，C2)≤d(C1，C3)＋d(C3，C2)。（n，k，dmin）：表示最小距離為dmin，碼率為R＝k／n的線性分組碼，dmin表示了碼的糾錯能力。

糾錯碼的基本任務(wù)：構(gòu)造出R一定且dmin盡可能大的碼，或dmin一定且R盡可能大的碼。

MDS碼：(n，k，d)線性分組碼的最小距離dmin≤n－k＋1。若系統(tǒng)碼的最小距離

dmin＝n－k＋1，則稱此碼為極大最小距離可分碼，簡稱MDS碼。線性分組碼的檢錯和糾錯能力結(jié)論1.檢測e個錯碼，則要求最小碼距

dmin≥e＋1。2.糾正t個錯碼，則要求最小碼距

dmin≥2t＋1。3.糾正t個錯碼，同時能檢測e（e>t）個錯碼，則要求最小碼距

dmin≥e＋t＋1。線性分組碼的性質(zhì)

(1)兩個屬于該碼組碼字的和仍是一個屬于該碼組的碼字。

(2)全零碼字總是碼組中的一個碼字。

(3)一個線性碼組中兩個碼字之間的最小距離等于任何非零碼字的最小重量。例：已知碼組C=｛0000,1010,0101,1111｝是一個分組長度n=4的線性分組碼。觀察碼字之間所有十種可能的和：0000+0000=0000,0000+1010=1010,0000+0101=0101,0000+1111=1111,1010+1010=0000,1010+0101=1111,1010+1111=0101,0101+0101=0000,0101+1111=1010,1111+1111=0000它們都在C中，全零碼字也在C中。該碼組的最小距離為dmin=2。(線性分組碼的3個性質(zhì))線性分組碼的生成矩陣消息碼字若，則稱G為(n,k)線性分組碼的生成矩陣生成矩陣G與線性分組碼是一一對應(yīng)的。線性分組碼的生成矩陣系統(tǒng)碼－－碼字的前k位與消息完全相同系統(tǒng)碼生成矩陣－－例：(7，3)線性分組碼

設(shè)該碼的碼字為c6c5c4c3c2c1c0，其中c6、c5、c4為信息元；c3、c2、c1、c0為監(jiān)督元，每個碼元取值為“0”或“1”，即ci∈GF(2)。監(jiān)督元按下式計算，求生成矩陣。已知GF(2)中碼生成矩陣分別為：求：G1和G2分別對應(yīng)的碼字空間？線性分組碼的監(jiān)督矩陣在線性分組碼（n，k）中，每個碼字中r（r＝n－k）個監(jiān)督元和信息元之間的關(guān)系為

H陣的r行代表了r個監(jiān)督方程，即：

H陣的標(biāo)準(zhǔn)形式

例：(7，3)線性分組碼

設(shè)該碼的碼字為c6c5c4c3c2c1c0，其中c6、c5、c4為信息元；c3、c2、c1、c0為監(jiān)督元，每個碼元取值為“0”或“1”，即ci∈GF(2)。監(jiān)督元按下式計算，求監(jiān)督矩陣。生成矩陣和監(jiān)督矩陣的關(guān)系線性碼的生成矩陣G和監(jiān)督矩陣H的行矢量彼此正交。對系統(tǒng)碼來說結(jié)論：系統(tǒng)碼的生成矩陣G和監(jiān)督矩陣H可以互化。對偶碼原碼CI

（n，k）對偶碼CJ

（n，r）生成矩陣

GH監(jiān)督矩陣

HG原碼CI

與對偶碼CJ的碼字彼此正交。定理兩個k×n矩陣,若一個可以由另一個通過一系列下述變換得到，則它們生成的GF(p)上的(n，k)線性碼等價：

（1）對行置換；

（2）對行乘以一個非零常量；

（3）把一行乘以一個常量然后加到另一行上；

（4）對列置換；

（5）對任意列乘以一個非零常量。

G（7，3）編出的（7，3）碼H（7，4）編出的（7，4）碼小結(jié)信道編碼的目的信道編碼定理線性分組碼的生成矩陣線性分組碼的監(jiān)督矩陣生成矩陣與監(jiān)督矩陣的關(guān)系對偶碼Galois域加法：1.F在加法下封閉，即若a,b2.滿足結(jié)合律，即若3.滿足交換律，即a+b=b+a。4.F中含有一個加法恒元0，滿足a+0=a。5.

集合中每個元素a都有一個加法逆元–a，滿足a+(–a)=0Galois域乘法：集合F*在乘法下封閉。F*為F除去加法恒元0，記作F*=F-{0}。滿足交換律。滿足結(jié)合律。滿足乘加分配律，即(a+b)*c=a*c+b*cF中含有單位元１，對F中任意元素a滿足a*1=a。F中任一非零元素a有乘法逆元a–1，滿足a*a–1=1。域中元素個數(shù)q有限，就稱為Galois域，記為GF(q)。Galois域例｛０,1｝就構(gòu)成了最簡單的有限域GF(2)

+01001110*01000101線性分組碼的編碼(n，k)線性碼的編碼就是根據(jù)線性碼的監(jiān)督矩陣或生成矩陣將長為k的信息組變換成長為n(n>k)的碼字,即先求出信息元和碼元之間的關(guān)系,再利用此關(guān)系構(gòu)造編碼電路。

下面利用監(jiān)督矩陣來構(gòu)造(7，3)線性分組碼的編碼電路。設(shè)二元碼字為碼的監(jiān)督矩陣為C＝[c6c5c4c3c2c1c0]線性分組碼的編碼線性分組碼的編碼++++線性分組碼的譯碼—標(biāo)準(zhǔn)陣列譯碼線性分組碼的譯碼—標(biāo)準(zhǔn)陣列譯碼定理假設(shè)C是ＧＦ(p)上的一個(n，k)碼，則(1)任意長為n的向量b都屬于C的某個陪集；

(2)每個陪集恰好包含pk個向量；

(3)兩個陪集或者不相交或者完全重合；

(4)若a+C是C的一個陪集，且b∈(a+C)，則b+C=a+C。例:設(shè)C為一個二元(3，2)碼，其生成矩陣：

碼字C=｛000,010,101,111｝。C的標(biāo)準(zhǔn)陣列為：標(biāo)準(zhǔn)陣列譯碼若接收碼字R位于標(biāo)準(zhǔn)陣列的第i行第j列，則將接收碼字R譯碼為cj

，此時的錯誤圖樣為陪集首。當(dāng)且僅當(dāng)錯誤圖樣為陪集首時，譯碼才是正確的。所以，這2n－k個陪集首稱為可糾正的錯誤圖樣。標(biāo)準(zhǔn)陣列譯碼例：已知二元(4,2)線性分組碼生成矩陣為

(1)求系統(tǒng)的標(biāo)準(zhǔn)陣列。(2)若接收碼字R=［1010］,錯誤圖樣E=［0100］,求對應(yīng)的碼字,并判斷譯碼有無錯誤。(3)若接收碼字R=［1010］,錯誤圖樣E=［0110］,求對應(yīng)的碼字,并判斷譯碼有無錯誤。標(biāo)準(zhǔn)陣列譯碼(1)由生成矩陣可得，系統(tǒng)碼組為0000,0111,1001，1110。標(biāo)準(zhǔn)陣列如下：(2)當(dāng)接收字R＝［1010］時，把R譯成碼字C＝［1110］。位于第3行的陪集首［0100］是錯誤圖樣E，因此譯碼正確。(3)當(dāng)接收字R＝［1010］時，把R譯成碼字C＝［1110］。位于第3行的陪集首［0100］不是錯誤圖樣E=［0110］，因此譯碼不正確。設(shè)二元(6，3）碼的生成矩陣為(1)若接收碼字R=［111011］，錯誤圖樣E=［010000］，求對應(yīng)的碼字，并判斷譯碼有無錯誤。(2)若接收碼字R=［100111］，錯誤圖樣E=［001100］，求對應(yīng)的碼字，并判斷譯碼有無錯誤。線性分組碼的譯碼—伴隨式譯碼伴隨式定義把S＝RH

T或S

T＝HR

T，稱為接收碼字R的伴隨式(或監(jiān)督子，或校驗子)。錯誤圖樣

若ei＝0，表示第i位無錯，若ei＝1，則表示第i位有錯。伴隨式性質(zhì)①伴隨式與發(fā)送碼字無關(guān)，僅與錯誤圖樣有關(guān)。②伴隨式S≠0，表示接收碼字有錯。如果沒有錯誤出現(xiàn)，則伴隨式S＝0。③不同的錯誤圖樣有不同的伴隨式，即錯誤圖樣與伴隨式一一對應(yīng)。線性分組碼的譯碼—伴隨式譯碼伴隨式譯碼步驟1.計算接收碼字的伴隨式：；2.由伴隨式譯出接收碼字的錯誤圖樣；3.譯碼：。例：已知（7，3）碼一致監(jiān)督矩陣為試對接收碼字1010011，1110011，0011011

分別進(jìn)行譯碼。線性分組碼的譯碼—伴隨式譯碼對1010011的譯碼為1010011對1110011的譯碼為1010011對0011011的不能正確譯碼，只能發(fā)現(xiàn)有錯。漢明碼是1950年由漢明提出的一種能糾正全部單個錯誤的線性分組碼。漢明碼是一種特殊的(n,k,d)線性分組碼碼長信息位數(shù)監(jiān)督位數(shù)最小距離漢明碼二進(jìn)制漢明碼參數(shù)碼長信息位數(shù)監(jiān)督位數(shù)最小距離碼率【例】構(gòu)造一個二元的（7，4，3）漢明