信息论与编码第6信道编码

1学习得来终觉浅，绝知此事要自悟纠错码的分类纠错码的分类根据监督码元与信息组之间的关系分组码卷积码信息码元是否发生变化 系统码非系统码 构造编码的数学方法 代数码几何码算术码 根据监督码元和信息码元的关系 线性码非线性码 根据码的功能检错码纠错码纠删码 按纠误的类型 纠随机差错码纠突发差错码纠混合差错码 按码字中码元的取值二元码多元码 按对信息元的保护能力 等保护纠错码不等保护纠错码-1-20=(,.,)kkmmmm6.1.2 纠错码的相关概念纠错码的相关概念-1-210=(,.,)nnccc cC(,)n k(,)n k L()W C-1-210(,.,)nneee eE,RCE CRE ERC(,)4DAB 10111011A11101101Bknr6.1.3 纠错检错基本原理纠错检错基本原理()nE RePeeP()E RCnR噪声均化纠错检错原理 噪声均化差错均匀分摊给各个码字 噪声的总量、分布共同决定干扰的危害 突发差错集中的噪声干扰 随机差错分散的噪声干扰 例如:7个码元上产生2个差错。如果2个差错集中在前7码元(同一码字)上，该码字将出错。如果差错分散在前后两个码字上，每个码字承受一个差错，则每个码字差错的个数都没有超出其纠错能力范围，这两个码字将全部正确解码。pq二元对称无记忆信道 结 论：即使同样的信道，选择的编码方法不同，所得到的对码元的译码效果是不同的。(0)113133(0)(1)+=24244EeePPPPP(0)111111(0)(1)+=24244EeePPPPP 在该信道中，要发送消息符号“0”，连续发送三次；同样，发送消息“1”也连续发送三次 0=000 x7=111x输出端有8种可能的输出码字，其信道矩阵为 01234507322222230222222231yyyyyyyyxpp qp qpqp qpqpqqxpqpqpqp qpqp qp qp 根据最大似然译码规则，如果输入等概率，那么译码函数为：平均错误概率为 3222222332-41=(+)=+3=2.98 102EPqpqpqpqpqpqpqqqpq0010203740576777()()()()()()()()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基本概念基本概念:带幺环,多项式环，环的左（右）零因子，整环，环的理想，真理想，主理想；同余类。(,)R,()a b cR a b cab c ,()a b cR abca ba c 定义定义：同时规定加法和乘法两种代数运算的集合F，并满足：(1)集合F对规定的加法运算构成交换群。(2)集合F中的全体非零元素对乘法运算构成交换群；(3)对加法和乘法运算满足分配律。有无限个元素的域称为无限域无限域，有限个元素的域称为有限域有限域，有限域又称为伽罗华域伽罗华域(Galois Field)，含，含q个元素的域称为个元素的域称为GF(q)。基本概念基本概念:子域，扩域，域的特征111().nnnnf xa xaxa xa域上多项式集合是有单位元的交换环(),(),()(),()()f x g xF xf xg xF xf xg xF x F x F x(),()()0 f xg xF xg xF 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 多项式剩余类环多项式剩余类环 用用 或者或者 表示所有这样多项式表示所有这样多项式的集合的集合()(),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,1x 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()4f32323232333322221,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(),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()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 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或者 nV()qf xF x矢量的线性组合矢量的线性组合 1,riiivk v,iikF vV矢量的线性相关与线性无关矢量的线性相关与线性无关 SV,v可由可由S中的矢量线性表示中的矢量线性表示 空间空间V由空间由空间S线性生成线性生成 空间的基底空间的基底S，维数，维数dimV0u v正交补正交补 12dimdimdimVVV两个正交补空间V1和V2满足kqkn,)n k（标记为 数域为 ，则消息为 ，较大，()GF qkq编码器存储容量会很大 k为什么要编码？线性分组码线性分组码 个 重矢量的集合 构成 维线性空间的一个 维子空间Cnnk01-1)km mmm=(m=(0 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,-11,01,11,-1,-1,0-1,1-1,-1100001000000n kn kk nk kk n kkkkn kpppppppppGEP一致校验矩阵一致校验矩阵,1,TTr nn 0HC或者 1,Tnr n 0CH一致校验矩阵一致校验矩阵H 所对应的方程称为一致校验方程-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例：二元(7,3)码的生成矩阵G2如下，计算生成的(7,3)码。21001011=01001110011110G解：生成矩阵是系统阵，按系统阵计算公式计算，结果如下：=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 E110 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个错误码元的位置，只能判断发生了2位码元的错误。,n k2nn2-1,.,kD，012-1,kC CC00ES伴随式000EC=陪首集 011ECC=0jjECC=021kEC11ES22ES2121n kn kES110ECE=220ECE=21021n kn kECS=11EC21EC211n kEC21n kjEC2121n kkEC2jEC1jEC121kEC221kEC2k10,D D1011101101G构造该码的标准阵列译码表。(,)n k d2n k(1)2td伴随式的汉明限、完备码：伴随式的汉明限、完备码：0201tn kinnnnit (1)/21td213dt 01201tn kinnnni (21,21,3)rrr 3r 000111101100111010101H011110011010101011001H=1000101010011100101100001011G(7,4)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-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()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 kxxx xxxxxm32=(+1)()+1xxxxg-()1(mod()n kxxxmg-653()=()+()=+1n kxxxxxxxCmr621()=+1(mod()xxxxrg522()=+1(mod()xxxxxrg423()=+(mod()xxxxxrg34()=+1(mod()xxxxrg1000101010011100101100001011G(7,4)系统汉明码21()()()n kxxxxCmrn kx-()xm()xg()n kxxm xQ()xr()()()()()n kxxxxxxmrQgg()/()()()/()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 xm xMx12223()1()1()1xxxxxx ggg11222233()1(100)()1(101)()1(111)xxxxxx gggggg112233()()()()()()()()()Y xM x g xY xM x gxY xM x gx123111112322221233333()(100)()()(101)()()(111)()xg g gxg g gxg g gggg11122233312312312311122233312312312311122233312312312300gggggggggggggggggggggggggggG12312312300GGGGGGGGGG123111112322221233333()()()g g gg g gg g gGGG22()(1,1)xxxxG1)01L=(,L,mm mm011(,)L N=c cc c011(,)L Nr rr r=c10log()log()L NiiiPP r cr carg maxlog)cPcc=(r clog()iiP r c(00,01,10,00,00,00,00)r()(,)()r ts t an t0bEN 11200011()()SSSbiiji vijijEPPsQdSSNijd欧几里德距离 0bEN信噪比221()2txQ xedtmin20()bfEPCQdNmin2fd归一化欧氏距离 min220,U1(,)-(,)2minfbds ts tdtE所有U因此，针对不同的调制方式和映射规则，寻找有最大min2fd的卷积码，是编码与调制结合的一个最关键的问题。2(3)mm 学习得来终觉浅，绝知此事要自悟