信息論課件chap檢錯(cuò)與糾錯(cuò)方式和能力

華僑大學(xué)通信工程 ： : 上次上次碼重最小距離錯(cuò)誤圖樣定理4.4.1若糾錯(cuò)碼的最小距離為dmin，那么如下三個(gè)結(jié)的任何一個(gè)結(jié)論獨(dú)立成若要發(fā)現(xiàn)e個(gè)獨(dú)立差錯(cuò)，則要求最dmine1；若要糾正t個(gè)獨(dú)立差dmin2t③若要求發(fā)現(xiàn)e個(gè)同時(shí)又糾正t個(gè)獨(dú)立差錯(cuò)dminet1(et)3 信息 監(jiān)督表示：（n,k）分組碼。n：分組長度k/n：編碼效率分類：線性碼：信息位與校驗(yàn)位之間為線非線性碼：信息與校驗(yàn)位之間不 性關(guān)4r個(gè)

n=r+ ：信息元個(gè)r：校驗(yàn)元個(gè)編碼是在信道輸入端2n個(gè)n長的二元序列中找一組2k個(gè)碼字，使碼字的r(=n-k)個(gè)校驗(yàn)元與其k個(gè)信息元之間滿足一定譯碼常采用最大似然譯碼準(zhǔn)則( ：最小漢明距離譯碼準(zhǔn)則)最大似然準(zhǔn)則(ML)：若P{Y|xk}是所有P{Y|xi}中最大的一個(gè)，則判斷端發(fā)的是 [例4.2.1]設(shè)將信源 輸出的二進(jìn)制序列進(jìn)行分組，分長度為k=1，相應(yīng)的碼字表Mcn這樣的碼字共有兩個(gè):“1”和“0”現(xiàn)將M進(jìn)行變換，變換規(guī)

因此，形成的糾錯(cuò)碼具有以下形C 由于m1只取“0”或“l(fā)”，所以C的全體碼字只有兩個(gè)長為n的全“0”或全“l(fā)”即經(jīng)過上述變換，得到了(n,1)重復(fù)碼6[例4.2.2]設(shè)信源 輸出的信息序列為M其中mi(1ik)是二進(jìn)制數(shù)

m2m1)信道 輸出的碼字為C c2c1)，其中ci(1in,nk)也是二進(jìn)制數(shù)。若從M到 c 由于從M到 的變換是一種線性變換，所以全體C的集構(gòu)成了一種(n,n-1)線性分組本例變換后碼字集合中每一個(gè)碼字的 cnc1(m1m2 mk)c1因?yàn)榧僭O(shè)了碼為二進(jìn)制碼，上述碼元的和是模2和 7[例 (7,3)分組碼。按以下的規(guī)則(校驗(yàn)方程)可得到四校驗(yàn)

c3c2c1

c5

c4m3 ccmm c2m3c mm3

m1是信息碼元，方程中的加運(yùn)算為模2由方程得到(7,3)分組碼的八個(gè)碼八個(gè)信源序列與八個(gè)碼字的對(duì)應(yīng)關(guān)系列于表4.2.1中8 00000000000010011101010010011101101110101001001110101101001111011010011111110100 c c4m3 cmm c2m3c m 9對(duì)于線性分組碼有一個(gè)非常重要的結(jié)論：一個(gè)(n,k)組碼中非零碼字的最小重量等于該碼的最小距離dmin 因 性分組碼的討論中就有了生成矩陣和一致校驗(yàn)矩陣的概念生成4.2.的(7300100001001011110101110 c5c4m3

c7c6c5c4c3c2c1m3m2m1cm c2m3

Cccm

稱矩陣G為線性分組合，而3個(gè)信息碼元構(gòu)成的信息位只有88可見，在本例中，線性分組碼的碼書是選取了128合之中的8種（合法碼字）3的７３因素是生成矩陣生成規(guī)則 G 1 。4.2.3pp1,n0100p1,k2,k01k,kpk,np2,n1 1

G

定義4.2.2若信息組以不變的形式，在碼字的任意k現(xiàn)，則該碼稱為系統(tǒng)碼。否則，稱為非目前常用的有兩種形式的

GIk一種是把信息組排在碼字(cn ,c2,c1)的最左邊k位,cn,cnk式(4.2.另一種是把信息組安置在碼字(cn ,c2,c1)的最右邊k位,c,1 1

GP

kG

能夠產(chǎn)生系統(tǒng)碼的生成矩陣為典型矩陣(或稱標(biāo)準(zhǔn)統(tǒng)型陣不具有元和特別如果生成矩陣G為非的，可經(jīng)過行初等變換變成標(biāo)一致校驗(yàn)從前面的討論我們知道，編碼問題就是在給定的dmin下如何利用已知的k個(gè)信息碼元求得r=n-k個(gè) c7 c5

c4c7

c7c5c4cccc m

c

cc cmm

c

cc

m3 m

c70110001100110101000111000C

06

HCT 0c5 c 0

4

or c c 1 c2 HCT CHT該式表明C中各碼元是滿足由矩陣H所確定的r個(gè)線性方程的解C是碼書C中的一個(gè)碼字，由C的全體就構(gòu)成反之，若某碼元序列滿足由H所確定的r個(gè)線性方程，則該元序列一定是碼書C中的一 由于(n,k)碼的 字均按H所確定的規(guī)則求出，故H為一致校驗(yàn)矩陣一致校驗(yàn)矩陣H有如下特點(diǎn)①Ｈ矩陣的每一行代表一個(gè)線性方程的系數(shù)，它對(duì)應(yīng) 元的線性方程②Ｈ矩陣每一列代表此碼元與哪幾個(gè)校驗(yàn)方③由該Ｈ矩陣得到的(n,k)分組碼的 字C都滿足由矩陣的行所確(n,k)碼需有r 元，故需有r個(gè)獨(dú)立的線性方程因此，H矩陣必須有r行，且各行之間線性無⑤生成矩陣G中的每一行及其線性組合都是(n,k)碼中的個(gè)碼字，故

c7cc7c5c4

06

1HGT1

cccc

c 100011100 1000111000 GHT c

04 1c3 ccc

c

2 HQIr式中Q是一個(gè)rk階矩陣。我們稱這種形式的H矩陣為典型矩陣(或標(biāo)準(zhǔn)陣)，同樣，采型矩陣形式的H矩陣更

Ik HGT

QIr

QIrPT

Q Q PH0H01100110101000111000Q

Gk|11G01000110111111010線性分組碼的[例4.2.4]設(shè)二元碼字為Cc7c6c5c4c3c2c1碼的一致校驗(yàn)矩陣H 0 0 H1 1

0T

c4c7 cc c

c4c7 cc c

按照該線性方程組，可直接畫出(7,3)線性分組碼的行編碼電路和(a)并行編碼電 (b)串行編碼電例4.2.5（P85）考慮一個(gè)(7,4)分組線性碼，其生成00000010100110101100101GG00對(duì)于信息序

畫出該(7,4)分組線性碼 原理圖

R ，檢驗(yàn)它是否為 對(duì)偶碼和縮矩陣H(n,k)碼的一致校驗(yàn)矩陣看成是(n,r)碼的生成則稱這兩種碼互為對(duì)偶碼[例4.2.6]求例4.2.3(7,3)碼的G矩陣就是(7,3)碼的H矩陣，將其化成標(biāo)準(zhǔn)形式后即可(7,3)(7,4)碼，如表所示。011000110000010110100行初等變 1001110001(7,4 010111100000101 在有些情況下，如果對(duì)某一給定長度的信息碼元找不適碼長的碼，則可將某一(n,k)碼縮短以滿足要 000000000001001111010010011011011100100100110101101001110110101111111010信息碼碼 000000010111101011111100縮短碼的G矩陣和H矩陣也可由原(n,k)碼的G和H推導(dǎo)而。i,ki,i行和前i列即可，而H7,36,2H

G

H6,2 1 對(duì)偶碼和對(duì)偶碼和縮短碼的糾錯(cuò)能力與原碼的糾錯(cuò)性能線性分組碼的CECE R 1)RCriciRHC CHTEHRHC CHTEHT T則認(rèn)為R有錯(cuò) 定義4.2.3設(shè)(n,k)碼的一致校驗(yàn)矩陣為H，R是發(fā)送碼字為時(shí)的接收序列，則 SRHTEH為接收序列R的伴隨式或校正子

EE

SSHHhh2,1nhh1rhrhSHETnhh 1n1 enhenhnen1hn1若S0那么計(jì)算伴隨式S得到的結(jié)果必為“0”，此時(shí)的錯(cuò)誤不能發(fā)現(xiàn)，也無法糾正，因而這樣的錯(cuò)誤圖樣稱為不可檢錯(cuò)圖樣SSTeh e [例4.2.7]計(jì)算例4.2.3所述(7,3)碼接收R1 解：(7,3)碼的一致校驗(yàn)矩陣為H

01101100110101000111000(7,3)00R1

接收端

0 0

STHRT 0

0 當(dāng)接收R2 )時(shí)，接收端 根據(jù)接收序列計(jì)算

0 0 STHRT 0 0 1 1由于S0，所以 判定接收序列R2碼，即發(fā)送碼字應(yīng)為( )。

0 0 STHRT 1 0 1 1S0與H實(shí)現(xiàn)伴隨式計(jì)算的電路：如前所述的(7,3)碼，設(shè)接收序列(7654321

r06

rr

4s s4sr

STHRT

05

r5r33

04

rr s

r

rr

2

1圖4.2.3線性分由前可知，線性分組碼的糾錯(cuò)能力t和碼字的最小距離dmin 進(jìn)一步研究dmin和碼字結(jié)構(gòu)的關(guān)系。定的，知H矩陣，該碼的結(jié)構(gòu)也就知道了，實(shí)際上所謂校驗(yàn)就是利用H矩陣去鑒別接收矢量R的結(jié)構(gòu)。那么從研究碼的糾錯(cuò)能力角度來看dmin與H有什么關(guān)系呢？定理 (n,k)線性分組碼最小碼距等于dmin的充要條件H矩陣中任何dmin1列線性無定理4.1.2是構(gòu)造任何類型線性分組碼的基礎(chǔ)。由定理可出以下三個(gè)結(jié)論為了構(gòu)造最小距離dmine1(可檢測e個(gè)錯(cuò)誤)或dmin2t1(中任意dmin1列線性無關(guān)。列H無全“”任一線性分組碼的最小距離(或最小重量dmin均滿足dminnkdminnk1的線性分組碼稱為極大最小距離碼。在同樣的n,k之下，由于dmin最大，因此糾錯(cuò)能力更強(qiáng)，所以設(shè)計(jì)這種碼，是編碼理論中人們感的一個(gè)課題。根據(jù)定理4.2.1，我們可以由H碼的糾錯(cuò)、檢錯(cuò)能力在已知信息位k的條件下，如何去確定校驗(yàn)位r=n-k的位數(shù)t若C是(n,k)二元碼，當(dāng)巳知k時(shí)，要使C能糾正t個(gè)錯(cuò)t必須有不少于r個(gè)校驗(yàn)位，且r

2r1

CnC。漢明 漢明碼有許多很好的性質(zhì)，它可以用一種簡潔的方法進(jìn)行譯1明碼參對(duì)于任意正整數(shù)m>=3，存在具有下列參數(shù)的漢碼長：n=2m-信息位數(shù)：k=2m-m-校驗(yàn)位數(shù)：r=n-最小碼（：m=3，n=7，k=4

（7,4）漢明（15,11）漢明22以最