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

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

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

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

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

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

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

是

的伴隨式，則

循環(huán)移位

（在模運算下）的伴隨式，是在伴隨式計算電路中無輸入時（自發(fā)運算）右移一位的結果，即線性分組碼定理的伴隨式而任意多項式乘所對應的伴隨式伴隨式計算電路性質(zhì)及一般譯碼器伴隨式特點信息論與編碼基礎線性分組碼例子例二進制（7，4）循環(huán)漢明碼，輸入緩存譯碼000110000100001011000111011101110000111111011010011000信息論與編碼基礎(7,4)碼完整譯碼器線性分組碼信息論與編碼基礎循環(huán)碼的通用譯碼器門k級緩存器伴隨式計算電路1伴隨式計算電路2組合邏輯電路—輸入R(x)輸出糾錯信號線性分組碼信息論與編碼基礎線性分組碼一、線性分組碼的基本原理二、循環(huán)碼的基本原理1、基本概念2、循環(huán)碼的編碼3、循環(huán)碼的一般譯碼方法4、循環(huán)漢明碼及其派生碼信息論與編碼基礎循環(huán)漢明碼線性分組碼既約多項式：如果多項式f(x)除了常數(shù)和它本身以外，不能再被GF(q)的其他多項式除盡，則稱f(x)是GF(q)上的既約多項式。本原多項式：若m次既約多項式f(x)除盡xn+1的最小正整數(shù)n滿足n=2m-1，則稱該多項式為本原多項式。由m次本原多項式g(x)生成的長度2m-1(m≥3)的循環(huán)碼是(2m-1,2m-1-m)漢明碼。0000000000101100101100011101010110001