信息論與編碼基礎-教學課件

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

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

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

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

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

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

是

的伴隨式，則

循環(huán)移位

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