ch7線性分組糾錯(cuò)編碼

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

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

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

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

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

無檢錯(cuò)糾錯(cuò)能力“好”——00“壞”——11

接收：00011011

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

接收：000001010011100101110111

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

接收：00000001001000110100010101100111

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

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

k個(gè)信息元一組變換

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

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

編碼速率/碼率

R越小，冗余度就越大，檢錯(cuò)和糾錯(cuò)的能力越強(qiáng)；但也降低了傳輸信息的實(shí)際速率。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)督元，每個(gè)碼元取值為“0”或“1”，即ci∈GF(2)。監(jiān)督元可按下式計(jì)算：碼重：在信道編碼中，定義碼字中非零碼元的數(shù)目為碼字的漢明（Hamming)重量，簡稱碼重。例如“010”碼字的碼重為1，記為?！?11”碼字的碼重為2，記為碼距：把兩個(gè)碼字之間對(duì)應(yīng)碼位上具有不同二元碼元的位數(shù)定義為兩碼字的漢明距離，簡稱碼距。例如dH(010,011)=1

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

。漢明距離三個(gè)性質(zhì)：(1)對(duì)稱性：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表示了碼的糾錯(cuò)能力。

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

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

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

dmin≥e＋1。2.糾正t個(gè)錯(cuò)碼，則要求最小碼距

dmin≥2t＋1。3.糾正t個(gè)錯(cuò)碼，同時(shí)能檢測(cè)e（e>t）個(gè)錯(cuò)碼，則要求最小碼距

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

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

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

(3)一個(gè)線性碼組中兩個(gè)碼字之間的最小距離等于任何非零碼字的最小重量。例：已知碼組C=｛0000,1010,0101,1111｝是一個(gè)分組長度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個(gè)性質(zhì))線性分組碼的生成矩陣消息碼字若，則稱G為(n,k)線性分組碼的生成矩陣生成矩陣G與線性分組碼是一一對(duì)應(yīng)的。線性分組碼的生成矩陣系統(tǒng)碼－－碼字的前k位與消息完全相同系統(tǒng)碼生成矩陣－－例：(7，3)線性分組碼

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

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

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

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

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

（n，k）對(duì)偶碼CJ

（n，r）生成矩陣

GH監(jiān)督矩陣

HG原碼CI

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

（1）對(duì)行置換；

（2）對(duì)行乘以一個(gè)非零常量；

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

（4）對(duì)列置換；

（5）對(duì)任意列乘以一個(gè)非零常量。

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

集合中每個(gè)元素a都有一個(gè)加法逆元–a，滿足a+(–a)=0Galois域乘法：集合F*在乘法下封閉。F*為F除去加法恒元0，記作F*=F-{0}。滿足交換律。滿足結(jié)合律。滿足乘加分配律，即(a+b)*c=a*c+b*cF中含有單位元１，對(duì)F中任意元素a滿足a*1=a。F中任一非零元素a有乘法逆元a–1，滿足a*a–1=1。域中元素個(gè)數(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)上的一個(gè)(n，k)碼，則(1)任意長為n的向量b都屬于C的某個(gè)陪集；

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

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

(4)若a+C是C的一個(gè)陪集，且b∈(a+C)，則b+C=a+C。例:設(shè)C為一個(gè)二元(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

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

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

T或S

T＝HR

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

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

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