【正文】 01 0001 0000000 0000 C m 3 線性分組碼 ?C m H 線性分組碼的糾、檢錯能力 對于一個二進制對稱信道，當輸入為 2k個等可能的 n長碼字，則最大后驗概率準則等效于最小漢明距離譯碼準則。 3 線性分組碼 1( | ) ( | )kknD n Dj i j ikp p y x p p ?????yx關于碼的最小距離與糾、檢錯能力的關系有以下結(jié)論：對于 （ n， k） 線性分組碼，設 為碼的最小距離則 （１）這組碼有糾正 u 個錯誤的充要條件是 mind12m i n ?? udu u 2u+1 3 線性分組碼 l l l+1 （２）具有檢測 l個錯誤的充要條件是 1m in ?? ld3 線性分組碼 u l u+l+1 （３）具有糾正 u 個錯誤，同時可以發(fā)現(xiàn) l個錯誤的充分必要條件為 m in 1d u l? ? ?3 線性分組碼 碼的糾錯能力 u與碼字的 長度 n和 消息數(shù) M滿足以下關系： 02uinniMC???3 線性分組碼 校驗矩陣與碼的最小距離的關系 對于 （ n， k） 線性分組碼： 校驗矩陣 H中的任意 t列線性無關 而 t+1列線 性相關 ， 則碼的最小距離 (碼字的最小重量 ) 為 t+1。 反過來說 ， 若碼的最小距離 (碼字的最小重量 ) 為 t+1則 H 的任意 t列線性無關而 t+1列線性相關 。 3 線性分組碼 1 0 1 1 0 0 01 1 1 0 1 0 01 1 0 0 0 1 00 1 1 0 0 0 1?????????H1 1 1 0 1 0 01 1 11 1 0 1 0 0 11 1 01 0 1 0 0 1 11 0 11 0 0 1 1 1 01 0 00 1 1 1 0 1 00 1 10 1 0 0 1 1 10 1 00 0 1 1 1 0 10 0 10 0 0 0 0 0 00 0 0Cm 線性分組碼的伴隨式 0CH ?TR=C+E E=[e1 e2 … en] TTTTT EHCHEHHCERHS ?????? )(1) ，說明 R 是一個碼字 。 2) ，說明 R 不是碼字，傳輸過程產(chǎn)生了誤碼。 0?S0?STTS = H R3 線性分組碼 TTS = H E例：某（ 5,2）系統(tǒng)線性碼的生成矩陣是 設收碼是 ，問它是否是碼字。 )1010 1(?R???????1011011101G3 線性分組碼 令 ? ?12121nTTn i iinee=ee????????????????S H E H H H H? ?12 n= e e eE ? ?12 n=H H H HiH H 則 （其中 表示 的列向量） 3 線性分組碼 結(jié)論： 1) 當傳輸過程沒有錯誤時 ，即 ， 2)當發(fā)生一位錯誤時， 是校驗矩陣的某一列。 3)當發(fā)生多個錯誤時， 為校驗矩陣對應列的模 2和。 ? ?0 0 0=E T 0?STSTS例 ： 設 (7,3)線性分組碼的校驗矩陣為 1 0 1 1 0 0 01 1 1 0 1 0 01 1 0 0 0 1 00 1 1 0 0 0 1?????????H3 線性分組碼 m in 31d ??（ 1）接收碼字 R=(1010011)， TT101 0 1 1 0 0 0 011 1 1 0 1 0 0 001 1 0 0 0 1 0 000 1 1 0 0 0 1 011??????? ? ? ???? ? ? ???? ? ? ?????? ? ? ???? ? ? ???? ? ? ???????S = H R傳輸過程中沒有誤碼， ?=CR?3 線性分組碼 （ 2）接收碼字 R=(1110011)， TT111 0 1 1 0 0 0 011 1 1 0 1 0 0 101 1 0 0 0 1 0 100 1 1 0 0 0 1 111??????? ? ? ???? ? ? ???? ? ? ?????? ? ? ???? ? ? ???? ? ? ???????S = H R ，第 2位出錯， ? = ( 1 0 1 0 0 1 1 )=+C R E? T 2?SH?( 0 1 0 0 0 0 0 )=E3 線性分組碼 （ 3）接收碼字 R=(0011011)， TT001 0 1 1 0 0 0 011 1 1 0 1 0 0 111 1 0 0 0 1 0 100 1 1 0 0 0 1 011??????? ? ? ???? ? ? ???? ? ? ?????? ? ? ???? ? ? ???? ? ? ???????S = H R與 中的任一列都不相同， ? TS HT 1 4 2 7 5 6? ? ? ? ? ?S H H H H H H不能確定到底是哪兩位出錯，不能正確譯碼。 3 線性分組碼 ?????????????????????niiinnnnTTeeeeeee122112121][HHHHHHHHES???線性分組碼的伴隨式譯碼 ERCEEHS ????? ?T3 線性分組碼 編碼C = m G計算Em輸出CER0RH ?T? ??C R E?Cnoyes輸出 R3 線性分組碼 02uinniMC???若（ n， k）線性分組碼能夠糾正 u 個錯誤，則其校驗位的數(shù)目必須滿足 ??? ?uiinkn C024 漢明碼 上式等號成立則稱為 完備碼 如果是能糾正一位錯誤的完備碼則 21r n??完備碼具有下述特性： （ 1）以每個發(fā)送碼字為球心，以 u為半徑畫一個球，那么每一個接收碼字都落在其中一個球中，因此接收碼字與發(fā)送碼字的距離至多為 u （ 2）所有差錯數(shù)小于等于 u的接收碼字都能得到糾正； （ 3）差錯數(shù)大于等于 u+1的接收碼字，因為落在另一個球內(nèi)被糾正為其他的發(fā)送碼字。 完備碼并不多見，我們知道的有 u=1的漢明碼、 u=3的高萊碼，以及 (n,1)中 n為奇數(shù)的重復碼等。 4 漢明碼 完備碼 非完備碼 000 111 000 001 010 100 111 110 101 011 02 22n un k inkiC???? ?m in 3d ?00000 01101 00000 00001 00010 00100 01000 10000 00011 10011 01101 01100 01111 01001 00101 11101 01110 11100 10111 10111 . . . 11010 11010 . . . 4 漢明碼 l漢明碼是一種能夠糾正單個錯誤的完備碼。 ?漢明碼最小碼距 ?設監(jiān)督碼共有 r 位，對于漢明碼必然有 。 ?通常漢明碼可以表示成 。 21rn ??( 2 1 , 2 1 )rr r? ? ?m in 3d ?4 漢明碼 在同樣的糾錯能力下，漢明碼的碼率是最高的 21 12 1 2 1rrrrrR ??? ? ???l漢明碼監(jiān)督矩陣構成的兩種方式： ?按 r 位的二進制數(shù)的 自然 順序從左到右排列（不包括全 0列）。當發(fā)生可糾的單個錯誤時，伴隨式為 H 陣中對應的列，譯碼比較方便。 ?構成 H 陣的標準形式， 。非標準形式的監(jiān)督矩陣可以通過列置換變成標準形式的監(jiān)督矩陣，糾錯能力保持不變。 ? ?H = Q I4 漢明碼 例：構造一個 r=3的二元（ 7,4）漢明碼 解： r=3的漢明碼， = 2 1 7rn ??=4k n r??0 0 0 1 1 1 10 1 1 0 0 1 11 0 1 0 1 0 1???????H列置換 ? ?1 1 1 0 1 0 00 1 1 1 0 1 01 1 0 1 0 0 1???? ???QI4 漢明碼 ? ?1 0 0 0 1 0 10 1 0 0 1 1 10 0 1 0 1 1 00 0 0 1 0 1 1?????????G = I P1 1 1 00 1 1 11 1 0 1?????????Q ?1 0 11111 1 00 1 1?????????????TP = Q4 漢明碼 信息 比特 碼字 （循環(huán) 1） 信息 比特 碼字 （循環(huán) 2） 信息 比特 碼字 0001 0010 0101 0110 1000 1011 1100 0001011 0010110 0101100 0110001 1000101 1011000 1100010 0011 0100 0111 1001 1010 1101 1110 0011101 0100111 0111010 1001110 1010011 1101001 1110100 0000 1111 0000000 1111111 4 漢明碼 l如果給漢明碼添加一位奇偶校驗位，可得到擴展?jié)h明碼： ? 信息位保持不變，監(jiān)督位增加一位。 ? 最小碼距 ， 可糾正 一位 錯誤，同時發(fā)現(xiàn) 兩位 錯誤。 m in 4d ?39。00 1 1 1 1 0 0 001 0 1 1 0 1 0 01 1 0 1 0 0 1 001 1 1 1 1 1 1 11 1 1??????????????????????????H Hm i n 4 1 2 1d ? ? ? ?l擴展?jié)h明碼的監(jiān)督方程： 4 漢明碼 復習 一個碼字的漢明重量就是一個碼字 中非零碼元的個數(shù) ,記為 W(c)。 W(1010101)=4。 定理：設 (n,k)為線性分組碼 ,則它的所有非零碼字的重量的最小值 wmin,稱為最小重量 ,等于最小距離 , 即 wmin=dmin。 什么是線性分組碼 ? 同時具有分組特性和線性特性的糾錯碼。 線性分組碼的 G,H,E 設線性分組碼 (n,k)的系統(tǒng)碼的生成矩陣為 ,n=k+r。校驗矩陣 H為 r n矩陣 ,滿足:cHT=0 或 HcT=0. 其中 c=(c1,c2,c3,c4,c5,c6)為碼字 , ,Q為 r k矩陣。 nkk PEG ?? ) ,() ,( rEQH ?因為 G的每行都是碼字 ,故 GHT=0 或 HGT=0,從而 ? ? 0 T ?????????EQPE 有 QT+P=0 故 P=QT 或 Q=PT 校驗矩陣 H的性質(zhì) : ? (1) H與生成矩陣 G可以相互轉(zhuǎn)化。 ? (2) 利用 H和式 cHT=0判別是否碼字。 ? (3) H中列的線性相關性與糾錯能力有關系。 m4 m3 m2 m1 ci7 ci6 ci5 0001101 輸入 編碼器用 4級移位寄存器和 74=3個模 2加法器組成 ,加法器生成校驗位后按順序暫存在另一個長度為 74的