信息論與編碼第6章信道編碼

1、1糾錯(cuò)碼的分類糾錯(cuò)碼的分類根據(jù)監(jiān)督碼元與信息組之間的關(guān)系分組碼卷積碼信息碼元是否發(fā)生變化 系統(tǒng)碼非系統(tǒng)碼 構(gòu)造編碼的數(shù)學(xué)方法 代數(shù)碼幾何碼算術(shù)碼 根據(jù)監(jiān)督碼元和信息碼元的關(guān)系 線性碼非線性碼 根據(jù)碼的功能檢錯(cuò)碼糾錯(cuò)碼糾刪碼 按糾誤的類型 糾隨機(jī)差錯(cuò)碼糾突發(fā)差錯(cuò)碼糾混合差錯(cuò)碼 按碼字中碼元的取值二元碼多元碼 按對信息元的保護(hù)能力 等保護(hù)糾錯(cuò)碼不等保護(hù)糾錯(cuò)碼 -1-20=(,.,)kkmmmm6.1.2 糾錯(cuò)碼的相關(guān)概念糾錯(cuò)碼的相關(guān)概念-1-210=(,., ,)nnccc cC( , )n k( , , )n k L( )W C-1-210(,., ,)nneee eE,RCE CRE ERC(

2、 , ) 4DAB 10111011A11101101Bknr6.1.3 糾錯(cuò)檢錯(cuò)基本原理糾錯(cuò)檢錯(cuò)基本原理()nE RePeeP( )E RCnR噪聲均化糾錯(cuò)檢錯(cuò)原理 噪聲均化差錯(cuò)均勻分?jǐn)偨o各個(gè)碼字 噪聲的總量、分布共同決定干擾的危害 突發(fā)差錯(cuò)集中的噪聲干擾 隨機(jī)差錯(cuò)分散的噪聲干擾 例如:7個(gè)碼元上產(chǎn)生2個(gè)差錯(cuò)。如果2個(gè)差錯(cuò)集中在前7碼元(同一碼字)上，該碼字將出錯(cuò)。如果差錯(cuò)分散在前后兩個(gè)碼字上，每個(gè)碼字承受一個(gè)差錯(cuò)，則每個(gè)碼字差錯(cuò)的個(gè)數(shù)都沒有超出其糾錯(cuò)能力范圍，這兩個(gè)碼字將全部正確解碼。 pq二元對稱無記憶信道 結(jié) 論：即使同樣的信道，選擇的編碼方法不同，所得到的對碼元的譯碼效果是不同的。(

3、0)113133(0)(1)+=24244EeePPPPP(0)111111(0)(1)+=24244EeePPPPP 在該信道中，要發(fā)送消息符號“0”，連續(xù)發(fā)送三次；同樣，發(fā)送消息“1”也連續(xù)發(fā)送三次 0=000 x7=111x輸出端有8種可能的輸出碼字，其信道矩陣為 01234507322222230222222231yyyyyyyyxpp qp qpqp qpqpqqxpqpqpqp qpqp qp qp 根據(jù)最大似然譯碼規(guī)則，如果輸入等概率，那么譯碼函數(shù)為： 平均錯(cuò)誤概率為 3222222332-41=(+)=+3=2.98 102EPqpqpqpqpqpqpqqqpq00102037

4、40576777()()()()()()()()yf xyf xyf xyf xyf xyf xyf xyf x,(| ),(| )X p y x Yp y xCRCnnX(2 )nRM (2 , )nRn,(|),X p y x YRC(2 , )nRnlog(1)NRCWP PRlog(1)NRCWP P,a bR abR基本概念基本概念: 帶幺環(huán),多項(xiàng)式環(huán)，環(huán)的左（右）零因子，整環(huán) ，環(huán)的理想，真理想 ，主理想；同余類。 ( , )R , ,()a b cR a b cab c , ,()a b cR abca ba c 定義定義：同時(shí)規(guī)定加法和乘法兩種代數(shù)運(yùn)算的集合F，并滿足： (1)

5、 集合F對規(guī)定的加法運(yùn)算構(gòu)成交換群。 (2) 集合F中的全體非零元素對乘法運(yùn)算構(gòu)成交換群； (3) 對加法和乘法運(yùn)算滿足分配律。 有無限個(gè)元素的域稱為無限域無限域，有限個(gè)元素的域稱為有限域有限域，有限域又稱為伽羅華域伽羅華域(Galois Field)，含，含q個(gè)元素的域稱為個(gè)元素的域稱為GF(q)。 基本概念基本概念: :子域，擴(kuò)域，域的特征111( ).nnnnf xa xaxa xa域上多項(xiàng)式集合是有單位元的交換環(huán)( ), ( ) ,( )( ) ,( )( ) f x g xF xf xg xF xf xg xF x F x F x( ),( ) ( )0 f xg xF xg xF

6、x且則( )( )q xr x和( )( )( )( )f xq xg xr x( )0r x ( )( )mod ( )f xg xh xgcd( ( ), ( )f x g x( ( ), ( )LCM f x g x 多項(xiàng)式剩余類環(huán)多項(xiàng)式剩余類環(huán) 用用 或者或者 表示所有這樣多項(xiàng)式表示所有這樣多項(xiàng)式的集合的集合( )( ),deg( ( )1( ) p xf xp xp xx 且在F( )ccp x和( )p x111( ).nnnnf xa xaxa xaiqaF qF x( ) GF q x( ) qf xF x( )f x2 F x2( )1f xx2 F x( )f x0,1,1

7、x x和0,1,1x x和22222223323320:0,1, (1),(1)(1),.1:1, (1) 1, (1),.: ,1,1,.1:1,1,.xx xxxxx xx xxx x xxxxxxxxx xxx其加法和乘法如下012( ) 0,1, ,1f xF xx x1xx01x1x01xx011x1x01x1x1x1x01xx1x01x10000001x1x0 x1001x1x1x(0)n n ( )f xqF( )f x( ) qf xF xnq()nGF q4( )1f xxx2( ) f xF x4(2 )GF3213210a xa xa xadeg( )4f32323232

8、333322221,1,1,1,1,1,1, ,1,0 xxxxxx xxxxxx xxxxxxxx xxxx,0,qaFa qF0,na naqF(, )qF *(, )qF (1)q*(, )qFaqFa1q1qae*qFa*qF1q *qF10qxeaqF( ,1)1k qkaka(1) ( ,1)qk q*5Z5Z2424(1)q,nFqnN qnqFqFnqFnqqFqpFmqFpmZmpq|m nnqFmqmqFrqFnqF|m rmrqqFF|m nnqFqa*nqFnqFnqFa1nq nqF1nq ka(1) ( ,1)nnjqk qnqF(1)nq2nFq121212(),

9、qqqF 11(),nkknqiiiiiqFnN ,nqqF特別地，對有歸一性：k( ) qf xFxnqF( )0frq( )f xk( )f xk2,.qq k,qqFFF FqF( )m xqFFFqF( )m x( )( )qf xF x( )0f( )|( )m xf x( )|()()nnqqm xxxFFqF*,qFFFF是l( , )1q l *modlql在ZmqF在( )m xm21,.,nqqq ( )m xm*FlnqFnqFqFnnqFnqF21( )()()().()nqqqm xxxxxnnqF1nq 21,.nqqq nqFn(0)(1)10,( )fff x4

10、( )1f xxx2222,1,1xxx xxx22,xxx( )f x2243(1)(1)1( )xxxxxxf x 44( )0mod( ),10,1f xf xxxxx 即4*2Fx( )f x1xx33xx542(1)xx xx xxx76323()1xx xx xxxx9823(1)xx xx xxx1110232(1)xx xx xxxxx13123232(1)1xx xx xxxxx15143(1)1xx xx x22xx41xx65232()xx xx xxxx84422(1)1xxxxx10932()1xx xx xxxx1211321xx xxxx1413323(1)1xx

11、 xx xxxx421 15 axka(1) ( ,1)nnqk q15 ( ,15)kkaa4*(2 )GFakaa0a1a2a3a4a5a6a7a(0001)(0010)(0100)(1000)(0011)(0110)(1100)(1001)a2a3a1a2aa32aa31aa8a9a10a11a12a13a14a(0101)(1010)(0111)(1110)(1111)(1101)(1001)21a 3aa21aa32aaa321aaa 321aa31a ka(1) ( ,1)nnjqk q,;,u vVuvVaFuVa uV 則則( ,)V nR( , )V n q或者 ,n qV或

12、者 nV( ) qf xF x矢量的線性組合矢量的線性組合 1,riiivk v,iikF vV矢量的線性相關(guān)與線性無關(guān)矢量的線性相關(guān)與線性無關(guān) SV,v可由可由S中的矢量線性表示中的矢量線性表示 空間空間V由空間由空間S線性生成線性生成 空間的基底空間的基底S，維數(shù)，維數(shù)dimV0u v正交補(bǔ)正交補(bǔ) 12dimdimdimVVV兩個(gè)正交補(bǔ)空間V1和V2滿足kqkn, )n k（標(biāo)記為 數(shù)域?yàn)?，則消息為 ， 較大， ( )GF qkq編碼器存儲容量會很大 k為什么要編碼？線性分組碼線性分組碼 個(gè) 重矢量的集合 構(gòu)成 維線性空間的一個(gè) 維子空間Cnnk01-1)km mmm = (m = (0

13、 1-1=()nc ccC= +n k r0.00,10, -11,01,11, -11,01-11,-1,0-1,1-1, -1=nnnkkk nkkknggggggm mmgggCmGG( , )n knkGkn012=(1001110),=(0100111),=(0011101)ggg100111001001110011101G(2)GF012,)m m m（0 0 0 0 1 1 1 10 0 1 1 0 0 1 10 1 0 1 0 1 0 1TM00000000011101010011101110101001110101001111010011110100CMGMG0,00,10,

14、 - -11,01,11, - -1, -1,0-1,1-1, - -1100001000000n kn kk nk kk n kkkkn kpppppppppGEP一致校驗(yàn)矩陣一致校驗(yàn)矩陣 ,1,TTr nn 0HC或者 1,Tnr n 0CH一致校驗(yàn)矩陣一致校驗(yàn)矩陣H 所對應(yīng)的方程稱為一致校驗(yàn)方程-1,=0=(0-1)=(- -1)iikijj ijcmikcm pkin k,1,1,1,()()TTTTTr nnr nkk nr nk nkmm 0HCHGHG,=TTr nk n0H G,=Tk nr n0GH11001110= 10100111110100G1,1,=nkk nCmG例

15、：二元(7,3)碼的生成矩陣G2如下，計(jì)算生成的(7,3)碼。21001011= 01001110011110G解：生成矩陣是系統(tǒng)陣，按系統(tǒng)陣計(jì)算公式計(jì)算，結(jié)果如下：=3mind000100010001“” “， ， ”111110011101“ ” “， ， ”C( , )n kC( , )n kmindemin1dermin21drr()e ermin1dre Cmind( , )n kH( , )n kHdH1d d( , )n kH()nkn()nk()1dnk()1nkrsCCE()rTsTsTTTT 0CHCE HC HE HE HE H()rTTHCH ETSE HTTSH E1

16、10 1 10 0 01 10 0 10 01 1 10 0 100 1 10 0 0 1H0(0000000)E0(0000)S1(0100000)E111(0111)TSEH2(0110000)E2(0100000)+(0010000)E2(0111)(1011)(mod2)=(1100)S(1110)(0010)(mod2)=(1100)因此，不能確定2個(gè)錯(cuò)誤碼元的位置，只能判斷發(fā)生了2位碼元的錯(cuò)誤。, n k2nn2-1,.,kD， 012 -1,kC CC00ES伴隨式000EC= 陪首集 011ECC= 0jjECC= 021kEC11ES22ES2121n kn kES110EC

17、E=220ECE=21021n kn kECS=11EC21EC211n kEC21n kjEC2121n kkEC2jEC1jEC121kEC221kEC2k10,D D1011101101G構(gòu)造該碼的標(biāo)準(zhǔn)陣列譯碼表。 ( , , )n k d2n k(1) 2td伴隨式的漢明限、完備碼：伴隨式的漢明限、完備碼：0201tn kinnnnit (1)/ 21td213dt 01201tn kinnnni (21,21,3)rrr 3r 000111101100111010101H011110011010101011001H=1000101010011100101100001011G(7,4)

18、C = m G(3)r 121210( )nnnnxaxaxa xaC121210(1)122301( )1211201( )( )( )nnnnnnnnninniinininn ixaxaxa xaxaxaxa xaxaxaxa xaxa CCC(2),iaGF-11(mod 2),-(mod2)iixx( )( )( )(mod(1)iinxxxxCC- -12- -121( )=+1n kn kn kxxxxxgggg( - )n k2-1( ),( ),( ),.,( )kx xx xxxxgggg(+1)nx1210( )( )( )( )( )TkkxxxxxxxxxGggggk-

19、 n k-( ),n kxm x( )xC1011( )kkxmm xmxm-1-2- +1-1-210( )=+n knnn kn kkkxxmxmxm xm xm- -1- -2- -1- -210( )=+n kn kn kn kxrxrxrx rr-( )=( )+ ( )n kxxxxCmr-1-2- +1- -1-1-210- -110 =+nnn kn kn kkkn kmxmxm xm xrxrx r-( )=( )+ ( )0 (mod ( )n kxxxxxCmrg-( )( ) (mod ( )n kxxxxrmg( )xm-n kx( )xg-( ) n kxxm( )

20、xr-( )=( )+ ( )n kxxxxCmr( , )n k-11( )=,km xx-22( )=,kmxx-1( )= ,kmxx( )=1kmx(100)(010)(001)-( )=+ ( ) =1,2,n iiixxxikCr-11-22- +1-1-0( )0( )( )00( )0( )nnn kkn kkxr xxr xxxrxxr xG-+ ( ) n kkxr x( )xg-( )=+ ( ) n kkxxr xg( - )kkn kGI P3( )=+ +1 xxxg=(1101)m=(1101)m32( )=+1xxxm-332653( )=(+1)=+n kxx

21、x xxxxxm32=(+ +1) ( )+1xxxxg-( )1(mod ( )n kxxxmg-653( )=( )+ ( )=+1n kxxxxxxxCmr621( )=+1(mod ( )xxxxrg522( )=+ +1(mod ( )xxxxxrg423( )=+ (mod ( )xxxxxrg34( )=+1(mod ( )xxxxrg1000101010011100101100001011G(7,4)系統(tǒng)漢明碼21( )( )( )n kxxxxCmrn kx-( )xm( ) xg( )n kxxm xQ( )xr( )( )( )( )( )n kxxxxxxmrQgg(

22、)/( )( )( )/( )xxxxxRgQrg( )xg( )xR( )xr( )xE( )xr( )xR( )xE( )xC-1-22( -1)2( -2)2 ( -1)2 ( -2)111nnnnt nt nH( )xg21mn =-/ 2tmt1nq2nkt21dt( , ,)n k N( , ,)(3,1,3)n k N 編碼器的序列描述方法樹狀圖 (3,1,3)1,11ym2,11ym3,11ym2m1,22ym2,22ym3,212ymmjjm1,2,23,12jjjjjjjjjymymmymmm1,2,3,21jjjjjjyyymmmA011001111A 1111100mmmmA 22121220mmmmmmA1111000000A2001111000A1200AAAAGAA231234( )xmm xm x