信息論與編碼基礎(chǔ)-教學(xué)課件

信息論與編碼基礎(chǔ)_教學(xué)課件第一頁，共68頁。編碼器信息序列碼元序列信息論與編碼基礎(chǔ)線性分組碼第二頁，共68頁。例（7，3）線性分組碼信息組碼字定義二進(jìn)制(n,k)線性分組碼，是GF(2)域上的n維線性空間Vn中的一個(gè)k維子空間Vn,k。定理一個(gè)(n,k)線性分組碼中非零碼字的最小重量等于[C]中的最小距離d0。信息論與編碼基礎(chǔ)線性分組碼第三頁，共68頁。信息論與編碼基礎(chǔ)線性分組碼第四頁，共68頁。典型矩陣+++++信息論與編碼基礎(chǔ)線性分組碼第五頁，共68頁。=生成矩陣信息論與編碼基礎(chǔ)線性分組碼第六頁，共68頁。一致校驗(yàn)矩陣信息論與編碼基礎(chǔ)線性分組碼第七頁，共68頁?；蛞恢滦ｒ?yàn)矩陣信息論與編碼基礎(chǔ)線性分組碼第八頁，共68頁。信息論與編碼基礎(chǔ)線性分組碼練習(xí)1）n=?，k=?2）求出該碼的全部碼字；3）求出該碼的一致校驗(yàn)矩陣H0。第九頁，共68頁。信息論與編碼基礎(chǔ)線性分組碼如果把(n,k)碼的一致校驗(yàn)矩陣看成是(n,r)碼的生成矩陣，將(n,k)碼的生成矩陣看成是(n,r)碼的一致校驗(yàn)矩陣，則這兩種碼互為對(duì)偶。任何對(duì)偶碼的碼字相乘為0嗎？對(duì)偶碼第十頁，共68頁。思考題：設(shè)C為數(shù)域F3={0,1,2}中的一個(gè)線性分組碼：請(qǐng)給出該碼的所有碼字，并給出一個(gè)校驗(yàn)矩陣。信息論與編碼基礎(chǔ)線性分組碼第十一頁，共68頁。線性分組碼基本概念對(duì)偶碼信息論與編碼基礎(chǔ)線性分組碼本課小結(jié)生成矩陣和一致校驗(yàn)矩陣第十二頁，共68頁。基本思想錯(cuò)誤圖樣信息論與編碼基礎(chǔ)線性分組碼第十三頁，共68頁。信息論與編碼基礎(chǔ)線性分組碼標(biāo)準(zhǔn)陣列譯碼第十四頁，共68頁。碼字禁用碼字(00…0)陪集陪集首標(biāo)準(zhǔn)陣列譯碼信息論與編碼基礎(chǔ)線性分組碼第十五頁，共68頁。例1：（4，2）線性分組碼標(biāo)準(zhǔn)陣列譯碼譯碼表：禁用碼組100011110010010101000011111010010001011010111100信息論與編碼基礎(chǔ)線性分組碼第十六頁，共68頁。標(biāo)準(zhǔn)陣列的特點(diǎn)：同一行中任意兩個(gè)碼矢量之和為[C]中碼字。標(biāo)準(zhǔn)陣列的同一行中沒有兩個(gè)n重矢量相同，每個(gè)n重矢量在且僅在一行出現(xiàn)。標(biāo)準(zhǔn)陣列譯碼信息論與編碼基礎(chǔ)線性分組碼第十七頁，共68頁。伴隨式譯碼伴隨式S信息論與編碼基礎(chǔ)線性分組碼第十八頁，共68頁。伴隨式譯碼信息論與編碼基礎(chǔ)線性分組碼第十九頁，共68頁。定理每個(gè)陪集全部個(gè)矢量都有相同的伴隨式而不同陪集有不同的伴隨式。信息論與編碼基礎(chǔ)線性分組碼伴隨式譯碼第二十頁，共68頁。例2：（4，2）碼的伴隨式譯碼

000000100010010011000101ESStep1：由R求SS=RHtStep2：由S求E令E＝(e3e2e1e0)，Step3：糾錯(cuò)

C=R+E信息論與編碼基礎(chǔ)線性分組碼伴隨式譯碼第二十一頁，共68頁。S0R=(r3r2r1r0)r0r1r2r3伴隨式計(jì)算伴隨式譯碼S1c0c1c2c3e0e2e3串行輸出錯(cuò)型產(chǎn)生C=R+E^000000100010010011000101ES信息論與編碼基礎(chǔ)線性分組碼第二十二頁，共68頁。r0r1rn-1s0s1sr-1e0e1en-1c0c1cn-1（n，k）線性分組碼一般譯碼電路S=RHtS=EHt^C=R+E接收矢量緩存器伴隨式計(jì)算電路錯(cuò)誤圖樣產(chǎn)生器n級(jí)移位寄存器輸出伴隨式譯碼信息論與編碼基礎(chǔ)線性分組碼第二十三頁，共68頁。思考題1：設(shè)C為數(shù)域F3={0,1,2}中的一個(gè)線性分組碼：利用伴隨式譯碼對(duì)(1122),(2110),(2222)碼字進(jìn)行譯碼。000000100022010012000101ES001111100120101002020021001010信息論與編碼基礎(chǔ)線性分組碼第二十四頁，共68頁。思考題2：信息論與編碼基礎(chǔ)線性分組碼考慮碼率為1/2的（n,n/2）的線性分組碼C，其生成矩陣為G。證明：如果則碼C是自對(duì)偶碼。你能構(gòu)造出符合該條件的碼嗎？第二十五頁，共68頁。標(biāo)準(zhǔn)陣列譯碼（陪集、譯碼步驟）伴隨式譯碼（伴隨式、譯碼過程）信息論與編碼基礎(chǔ)線性分組碼本課小結(jié)第二十六頁，共68頁。例（7，3）碼信息論與編碼基礎(chǔ)線性分組碼第二十七頁，共68頁。定理任一(n,k)線性分組碼若要糾正小于等于t個(gè)錯(cuò)誤，其充要條件是H矩陣中任何2t列線性無關(guān)。定理(n,k)線性分組碼最小距離等于的充要條件是H矩陣中任何列線性無關(guān)。結(jié)論：1、上述定理是構(gòu)造距離為d的任何類型線性分組碼的基礎(chǔ)2、H矩陣列排序不同，碼集不同，但糾錯(cuò)能力不變3、d0≤n–k+1信息論與編碼基礎(chǔ)線性分組碼第二十八頁，共68頁。定理若[C]是k維n重二元碼，當(dāng)已知k時(shí)，要使[C]能糾正t個(gè)錯(cuò)，則必須有不少于r個(gè)校驗(yàn)位，且使r滿足完備碼信息論與編碼基礎(chǔ)線性分組碼第二十九頁，共68頁。信息論與編碼基礎(chǔ)線性分組碼一、線性分組碼的基本原理二、循環(huán)碼的基本原理1、基本概念2、生成矩陣和一致校驗(yàn)矩陣3、線性分組碼的譯碼及糾錯(cuò)能力4、漢明碼簡(jiǎn)介第三十頁，共68頁。1、漢明碼的結(jié)構(gòu)碼長(zhǎng)信息位數(shù)監(jiān)督碼位最小碼距糾錯(cuò)能力信息論與編碼基礎(chǔ)線性分組碼第三十一頁，共68頁。信息論與編碼基礎(chǔ)2、擴(kuò)展?jié)h明碼(7,4)漢明碼(8,4)擴(kuò)展?jié)h明碼線性分組碼第三十二頁，共68頁。信息論與編碼基礎(chǔ)3、從已知線性分組碼來構(gòu)造新的線性分組碼2）鑿孔碼將線性分組碼中所有碼字的某些校驗(yàn)位刪除。3）除刪碼將線性分組碼中一部分碼字刪除。4）增廣碼與除刪碼對(duì)應(yīng)。5）延長(zhǎng)碼原碼增廣擴(kuò)展。線性分組碼1）縮短碼縮短線性分組碼的信息位。第三十三頁，共68頁。信息論與編碼基礎(chǔ)擴(kuò)展?jié)h明碼(2r,2r-1-r,4)偶重量碼字構(gòu)成的子碼(2r-1,2r-2-r,4)漢明碼(2r-1,2r-1-r,3)通過增加全校驗(yàn)位來擴(kuò)展在全校驗(yàn)位上鑿孔延長(zhǎng)縮短除刪丟棄奇重碼字通過加入全“1”分量來增廣線性分組碼3、從已知線性分組碼來構(gòu)造新的線性分組碼第三十四頁，共68頁。信息論與編碼基礎(chǔ)線性分組碼的糾錯(cuò)能力（d0

與H的關(guān)系）漢明碼（完備性，碼結(jié)構(gòu)）本課小結(jié)構(gòu)造新的線性分組碼的方法線性分組碼第三十五頁，共68頁。信息論與編碼基礎(chǔ)線性分組碼一、線性分組碼的基本原理二、循環(huán)碼的基本原理1、基本概念2、循環(huán)碼的編碼3、循環(huán)碼的一般譯碼方法4、循環(huán)漢明碼及其派生碼第三十六頁，共68頁。多項(xiàng)式零多項(xiàng)式:各次系數(shù)均為0的多項(xiàng)式首一多項(xiàng)式：最高次系數(shù)為1的多項(xiàng)式信息論與編碼基礎(chǔ)線性分組碼第三十七頁，共68頁。漢明碼(7,4)漢明碼碼字(0000000)(0001011)(0010110)(0100111)(1000101)(0011101)(0101100)(1001110)(0110001)(1010011)(1100010)(0111010)(1011000)(1110100)(1101001)(1111111)(0000000)(0001011)(0010110)(0100111)(1000101)(0011101)(0101100)(1001110)(0110001)(1010011)(1100010)(0111010)(1011000)(1110100)(1101001)(1111111)信息論與編碼基礎(chǔ)線性分組碼第三十八頁，共68頁。信息論與編碼基礎(chǔ)10001010100111循環(huán)漢明碼信息論與編碼基礎(chǔ)線性分組碼第三十九頁，共68頁。碼多項(xiàng)式信息論與編碼基礎(chǔ)線性分組碼第四十頁，共68頁。生成多項(xiàng)式定理一個(gè)二進(jìn)制(n,k)循環(huán)碼中有唯一的非零最低次多項(xiàng)式，且常數(shù)項(xiàng)為1。定理生成多項(xiàng)式信息論與編碼基礎(chǔ)線性分組碼第四十一頁，共68頁。例子例GF(2)上多項(xiàng)式構(gòu)造一個(gè)（7，3）循環(huán)碼。碼多項(xiàng)式碼字（0010111）（0101110）（1011100）（0111001）（1110010）（1100101）（1001011）（0000000）只要知道了xn+1的因式分解，用它的各個(gè)因式的乘積，便能得到很多個(gè)不同的循環(huán)碼。第四十二頁，共68頁。生成矩陣和一致校驗(yàn)矩陣…………………信息論與編碼基礎(chǔ)線性分組碼第四十三頁，共68頁。校驗(yàn)矩陣校驗(yàn)矩陣……………第四十四頁，共68頁。例子例第四十五頁，共68頁。系統(tǒng)碼情況信息論與編碼基礎(chǔ)線性分組碼第四十六頁，共68頁。例

已知（7，4）系統(tǒng)碼的生成多項(xiàng)式為求生成矩陣。信息論與編碼基礎(chǔ)線性分組碼第四十七頁，共68頁。碼多項(xiàng)式、生成多項(xiàng)式生成矩陣和一致校驗(yàn)矩陣信息論與編碼基礎(chǔ)線性分組碼本課小結(jié)循環(huán)碼的特點(diǎn)第四十八頁，共68頁。信息論與編碼基礎(chǔ)線性分組碼一、線性分組碼的基本原理二、循環(huán)碼的基本原理1、基本概念2、循環(huán)碼的編碼3、循環(huán)碼的一般譯碼方法4、循環(huán)漢明碼及其派生碼第四十九頁，共68頁。信息論與編碼基礎(chǔ)多項(xiàng)式除法電路線性分組碼第五十頁，共68頁。信息論與編碼基礎(chǔ)例線性分組碼D0D1D2++x3x1第五十一頁，共68頁。循環(huán)碼編碼電路信息論與編碼基礎(chǔ)1、n-k級(jí)編碼器2、

k級(jí)編碼器k個(gè)信元校驗(yàn)位線性分組碼第五十二頁，共68頁。例生成多項(xiàng)式的二進(jìn)制（7，4）漢明碼節(jié)拍信息位輸出碼字0000111110200011300111411011500116000170000第五十三頁，共68頁。Cn-kCn-k+1Cn-2Cn-1h0h1hk-2hk-1信息論與編碼基礎(chǔ)循環(huán)碼的k級(jí)編碼器線性分組碼第五十四頁，共68頁。信息論與編碼基礎(chǔ)線性分組碼一、線性分組碼的基本原理二、循環(huán)碼的基本原理1、基本概念2、循環(huán)碼的編碼3、循環(huán)碼的一般譯碼方法4、循環(huán)漢明碼及其派生碼第五十五頁，共68頁。信息論與編碼基礎(chǔ)伴隨式計(jì)算和錯(cuò)誤的檢測(cè)線性分組碼第五十六頁，共68頁。伴隨式計(jì)算第五十七頁，共68頁。信息論與編碼基礎(chǔ)伴隨式計(jì)算電路性質(zhì)及一般譯碼器伴隨式特點(diǎn)定理若

是

的伴隨式，則

循環(huán)移位

（在模運(yùn)算下）的伴隨式，是在伴隨式計(jì)算電路中無輸入時(shí)（自發(fā)運(yùn)算）右移一位的結(jié)果，即線性分組碼第五十八頁，共68頁。定理的伴隨式而任意多項(xiàng)式乘所對(duì)應(yīng)的伴隨式伴隨式計(jì)算電路性質(zhì)及一般譯碼器伴隨式特點(diǎn)信息論與編碼基礎(chǔ)線性分組碼第五十九頁，共68頁。例子例二進(jìn)制（7，4）循環(huán)漢明碼，輸入緩存譯碼000110000100001011000111011101110000111111011010011000第六十頁，共68頁。信息論與編碼基礎(chǔ)(7,4)碼完整譯碼器線性分組碼第六十一頁，共68頁。信息論與編碼基礎(chǔ)循環(huán)碼的通用譯碼器門k級(jí)緩存