16.編碼.ppt

1、組合數(shù)學(xué),1,編 碼,目的要求 掌握編碼理論的基本知識(shí) 掌握線(xiàn)性分組碼的基本知識(shí),組合數(shù)學(xué),2,上節(jié)內(nèi)容回顧,定義5-1 如果原有的信息編碼含m位，按照一定的規(guī)則添加nm個(gè)（nm）附加位形成的n位長(zhǎng)字符串稱(chēng)為碼字，n稱(chēng)為碼長(zhǎng)，每一位稱(chēng)為碼元。這樣的編碼稱(chēng)為分組碼。 在分組碼的碼字中，前m位恰是原有的信息，稱(chēng)為信息位，后nm位用來(lái)檢查錯(cuò)誤和糾正錯(cuò)誤，稱(chēng)為校驗(yàn)位。,組合數(shù)學(xué),3,比率mn是編碼的一項(xiàng)重要參數(shù)，稱(chēng)為碼率。 在w后面添加1位校驗(yàn)位，并且如果信息位中有偶數(shù)個(gè)1，則校驗(yàn)位取0；否則校驗(yàn)位取1。這樣產(chǎn)生的編碼稱(chēng)為奇偶校驗(yàn)碼。 如果原有的信息編碼有m位，則在它的后面添加2m位，并且這2m位恰是

2、將信息位重復(fù)兩次。這樣產(chǎn)生的編碼稱(chēng)為三次重復(fù)碼。,組合數(shù)學(xué),4,n位二進(jìn)制數(shù)c、r和e之間有如下關(guān)系 rce，cre，ecr 定義5-2 對(duì)于每個(gè)由n位二進(jìn)制數(shù)構(gòu)成的字符串xx1x2xn，x中1的個(gè)數(shù)稱(chēng)為x的權(quán)，記為w(x)。若yy1y2yn也是n位二進(jìn)制數(shù)構(gòu)成的字符串，則稱(chēng)d(x,y)w(xy)為x與y的漢明(Hamming)距離。,組合數(shù)學(xué),5,定義5-2 對(duì)于每個(gè)由n位二進(jìn)制數(shù)構(gòu)成的字符串xx1x2xn，x中1的個(gè)數(shù)稱(chēng)為x的權(quán)，記為w(x)。若yy1y2yn也是n位二進(jìn)制數(shù)構(gòu)成的字符串，則稱(chēng)d(x,y)w(xy)為x與y的漢明(Hamming)距離。 引理5-1 對(duì)于所有由n位二進(jìn)制數(shù)構(gòu)

3、成的字符串x和y，都有w(xy)w(x)w(y)。,組合數(shù)學(xué),6,定理5-1 對(duì)于所有由n位二進(jìn)制數(shù)構(gòu)成的字符串x和y，都滿(mǎn)足下面的4個(gè)性質(zhì)： （1）d(x,y)0 （2）d(x,y)0 xy （3）d(x,y)d(y,x) （4）d(x,z)d(x,y)d(y,z) 對(duì)于長(zhǎng)度為n的一組編碼，將其碼字間的最小距離記為d。,組合數(shù)學(xué),7,定理5-2 一組編碼可以查出k個(gè)錯(cuò)誤的充分必要條件是這組編碼的碼字間的最小距離至少是k1。 定理5-3 設(shè)一組編碼的任意兩個(gè)碼字間的最小距離至少是2k1，則權(quán)不超過(guò)k的誤差可以得到糾正。,組合數(shù)學(xué),8,線(xiàn)性分組碼,實(shí)例5-1 矩陣 可以用來(lái)定義一個(gè)編碼函數(shù)：E(

4、w)wG，其中w是任意一個(gè)由3位二進(jìn)制數(shù)構(gòu)成的字符串。在這種意義下稱(chēng)G為生成矩陣。例如,組合數(shù)學(xué),9,可以用來(lái)定義一個(gè)編碼函數(shù)：E(w)wG，其中w是任意一個(gè)由3位二進(jìn)制數(shù)構(gòu)成的字符串。在這種意義下稱(chēng)G為生成矩陣。例如,組合數(shù)學(xué),10,由這個(gè)生成矩陣G得到的碼字集合是 C000000,100110,010011,001101, 110101,101011,011110,111000 對(duì)于這個(gè)碼字集合C，可以通過(guò)直接取碼字的前3個(gè)碼元來(lái)重現(xiàn)信息。 注意到，碼字集合C的碼字間的最小距離是3。因此，用這組碼可以查出所有權(quán)2的錯(cuò)誤。,組合數(shù)學(xué),11,對(duì)于所有由3位二進(jìn)制數(shù)構(gòu)成的字符串ww1w2w3，有

5、 w1w2w3(w1w3)(w1w2)(w2w3) 所以有w4w1w3，w5w1w2，w6w2w3。,組合數(shù)學(xué),12,因?yàn)檫@里的運(yùn)算是模2加法，這些方程w4w1w3，w5w1w2，w6w2w3可以改寫(xiě)為 w1 w3w4 0 w1w2 w5 0 w2w3 w60 于是有,組合數(shù)學(xué),13,因此，如果由6位二進(jìn)制數(shù)構(gòu)成的字符串rr1r2r3r4r5r6是一個(gè)碼字當(dāng)且僅當(dāng),組合數(shù)學(xué),14,根據(jù)前面介紹的糾錯(cuò)理論，因?yàn)閷?shí)例5-1中這些碼字間的最小距離是3，所以可以建立一個(gè)譯碼函數(shù)來(lái)糾單錯(cuò)。 假定接收到的字符串是r110110，并希望求出離r最近的碼字c。實(shí)際的做法是檢驗(yàn)HrT，通常稱(chēng)HrT為r的校正子。

6、,組合數(shù)學(xué),15,由于 所以r不是碼字。這就可以斷言，r110110至少有一個(gè)錯(cuò)誤?；仡櫵械拇a字中，只有d(100110, r)1。,組合數(shù)學(xué),16,由 rce100110010000 可以看出，r110110恰好有一個(gè)錯(cuò)誤，并且這個(gè)錯(cuò)誤發(fā)生在r的第2位。,組合數(shù)學(xué),17,細(xì)心的讀者可能已經(jīng)發(fā)現(xiàn)，校正子HrT恰好是H的第2列。這是巧合嗎？不是。這是必然結(jié)果。換句話(huà)說(shuō)，通過(guò)計(jì)算校正子HrT，如果結(jié)果和H的第i列相同，就意味著r恰好有一個(gè)錯(cuò)誤，并且這個(gè)錯(cuò)誤就發(fā)生在第i位。據(jù)此就可以糾錯(cuò)了。,組合數(shù)學(xué),18,線(xiàn)性分組碼的標(biāo)準(zhǔn)校驗(yàn)矩陣H與生成矩陣G是有明確關(guān)系的。為了方便表達(dá)，引用記號(hào)： GmnIm|Am(nm)， H(nm)nB(nm)m|Inm， 則有BAT。更簡(jiǎn)捷的表達(dá)是：若記GIm|A，則HAT|Inm。 實(shí)例5-1的結(jié)果可以推廣到一般。,組合數(shù)學(xué),19,課后作業(yè),1、令C是一個(gè)碼字集合，且下面的各小題中，都給出了c（碼字）、r（接受到的字符串）和e（錯(cuò)誤型式）中的兩項(xiàng)，求第三項(xiàng)。 (1) c1010110，r1011111 (2) c1010110，e0100010 (3) e1000010，r0100111 2、在二元碼中，針對(duì)下列各組