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

第6章信道编码信道编码是以信息在信道上的正确传输为目标的编码，可分为两个层次上的问题：如何正确接收载有信息的信号－－线路编码如何避免少量差错信号对信息内容的影响－－纠错编码本章内容有扰离散信道的编码定理纠错编译码的基本原理与分析方法线性分组码卷积码编码与调制的结合－－TCM码运用级联、分集与信息迭代概念的纠错码6.1有扰离散信道的编码定理差错和差错控制系统分类矢量空间与码空间随机编码信道编码定理差错类型差错符号：由符号发生差错引起，也叫信号差错，信号差错概率用误码元率表示差错比特：由信息比特发生差错引起，也叫信息差错，信息差错概率用误比特率表示对于二进制传输系统，符号差错等效于比特差错；对于多进制系统，一个符号差错到底对应多少比特差错却难以确定。因为一个符号由多个比特组成。差错图样（errorpattern）定量地描述信号的差错，收、发码之“差”：差错图样E＝发码C－收码R（模M）例：8进制(M=8)码元，若发码C=（0,2,5,4,7,5,2）收码变为R=（0,1,5,4,7,5,4）差错图样E=C－R=（0,1,0,0,0,0,6）（模8）二进制码：E=CR或C=RE，差错图样中的“１”既是符号差错也是比特差错，差错的个数叫汉明距离。差错图样类型随机差错：若差错图样上各码位的取值既与前后位置无关又与时间无关，即差错始终以相等的概率独立发生于各码字、各码元、各比特；突发差错：前后相关、成堆出现。突发差错总是以差错码元开头、以差错码元结尾，头尾之间并不是每个码元都错，而是码元差错概率超过了某个额定值。纠错码分类从功能角度：检错码、纠错码对信息序列的处理方法：分组码、卷积码码元与原始信息位的关系：线性码、非线性码差错类型：纠随机差错码、纠突发差错码、介于中间的纠随机/突发差错码。构码理论：代数码、几何码、算术码、组合码等差错控制系统分类前向纠错（FEC）：发端信息经纠错编码后传送，收端通过纠错译码自动纠正传递过程中的差错反馈重发（ARQ）：收端通过检测接收码是否符合编码规律来判断，如判定码组有错，则通过反向信道通知发端重发该码混合纠错（HEC）：前向纠错和反馈重发的结合，发端发送的码兼有检错和纠错两种能力6.1.2矢量空间与码空间F表示码元所在的数域，对于二进制码，F代表二元域{0,1}设n重有序元素的集合V={Vi},若满足条件：V中矢量元素在矢量加运算下构成加群；V中矢量元素与数域F元素的标乘封闭在V中；分配律、结合律成立，则称集合V是数域F上的n维矢量空间，或称n维线性空间，n维矢量又称n重(n-tuples)。01(1)(,,,,,),iiiijinijVVVVVVF矢量空间中矢量的关系对于域F上的若干矢量线性组合：线性相关：其中任一矢量可表示为其它矢量的线性组合线性无关或线性独立：一组矢量中的任意一个都不可能用其它矢量的线性组合来代替。12,,,ikVVVV及1122,()kiiiVaVaVaVaF11220,()iiiaVaVaVaF且不全为零矢量空间与基底一组线性无关的矢量，线性组合的集合就构成了一个矢量空间V，这组矢量就是这个矢量空间的基底。n维矢量空间应包含n个基底基底不是唯一的，例：线性无关的两个矢量（1,0）和（0,1）以及（-1,0）和（0,-1）可张成同一个两维空间。12,,,nVVV二元域GF(2)上三重矢量空间以（100）为基底可张成一维三重子空间V1，含21=2个元素，即以(010)(001)为基底可张成二维三重子空间V2，含22=4个元素，即以(100)(010)(001)为基底可张成三维三重空间V,含23=8个元素，V1和V2都是V的子空间。1{(000),(100)}V2{(000),(001),(010),(011)}V矢量空间每个矢量空间或子空间中必然包含零矢量两个矢量正交：V1V2＝0两个矢量空间正交：某矢量空间中的任意元素与另一矢量空间中的任意元素正交正交的两个子空间V1、V2互为对偶空间(DualSpace)，其中一个空间是另一个空间的零空间（nullspace，也称零化空间）。码空间消息k长(n,k)码字n长qk种分组编码器qn种k维k重矢量n维n重矢量通常qnqk，分组编码的任务是要在n维n重矢量空间的qn种可能组合中选择其中的qk个构成一个码空间，其元素就是许用码的码集。分组编码的任务选择一个ｋ维n重子空间作为码空间。确定由k维k重信息空间到ｋ维n重码空间的映射方法。码空间的不同选择方法，以及信息组与码组的不同映射算法，就构成了不同的分组码。6.1.3随机编码运用概率统计方法在特定信道条件下对编码信号的性能作出统计分析，求出差错概率的上下限边界，其中最优码所能达到的差错概率上界称作随机码界。用这种方法不能得知最优码是如何具体编出来的，却能得知最优码可以好到什么程度，并进而推导出有扰离散信道的编码定理，对指导编码技术具有特别重要的理论价值。6.1.3随机编码在(N,K)分组编码器中随机选定的码集有qNM种第m个码集(记作{c}m)被随机选中的概率是设与这种选择相对应的条件差错概率是Pe({c}m)全部码集的平均差错概率是()({})NMmPqc11({})({})({})NMNMqqNMeemmemmmPPPqPccc6.1.3随机编码必定存在某些码集某些码集若，就必然存在一批码集即差错概率趋于零的好码一定存在11({})({})({})NMNMqqNMeemmemmmPPPqPccc({})emePPc({})emePPc0eP({})0emPc6.1.3随机编码码集点数M=qK占N维矢量空间总点数qN的比例是F=qK/qN=q-(N-K)当K和N的差值拉大即冗余的空间点数增加时，平均而言码字的分布将变得稀疏，码字间的平均距离将变大，平均差错概率将变小。当F0即(N-K)时，能否让平均差错概率？Gallager在1965年推导了的上边界，并证明这个上边界是按指数规律收敛的。eP0ePE(R)为可靠性函数，也叫误差指数码率：R=(lbM)/NM是可能的信息组合数，M=qKN是每码字的码元数，R表示每码元携带的信息量，单位是每符号比特（bit/symbol）6.1.4信道编码定理()NERePeR在[0,R0]区间时E(R)~R曲线是斜率为-1（-45）的直线，E(R)反比于R；而当R=C时E(R)=0即可靠性为零。E(R)CR0R0-45E(R)和R的关系曲线6.1.4信道编码定理正定理：只要传信率R小于信道容量C，总存在一种信道码（及解码器），可以以所要求的任意小的差错概率实现可靠的通信。逆定理：信道容量C是可靠通信系统传信率R的上边界，如果RC，就不可能有任何一种编码能使差错概率任意小。6.1.4信道编码定理6.2纠错编译码的基本原理与分析纠错编码的基本思路译码方法－最优译码与最大似然译码6.2.1纠错编码的基本思路R不变，信道容量大者其可靠性函数E(R)也大；C不变，码率减小时其可靠性函数E(R)增大E(R)R0R1R2C1C2增大E(R)的途径()NERePe6.2.1纠错编码的基本思路增大信道容量C扩展带宽加大功率降低噪声减小码率RQ、N不变而减小KQ、K不变而增大NN、K不变而减小Q增大码长N6.2.2最优译码与最大似然译码译码器的任务是从受损的信息序列中尽可能正确地恢复出原信息。译码算法的已知条件是：实际接收到的码字序列{r},r=(r1,r2,…,rN)发端所采用的编码算法和该算法产生的码集XN,满足信道模型及信道参数。12(,,,)NiiiiNccccX最佳译码，也叫最大后验概率译码(MAP)最大似然译码(MLD)6.2.2最优译码与最大似然译码消息组mi码字ci接收码r估值消息ˆicˆim编码器信道译码消息还原ˆmax(/)iiPccrˆmax(/)iiPcrc如果构成码集的2K个码字以相同概率发送，满足P(ci)=1/2K，i=1,2,…,2KP(r)对于任何r都有相同的值，满足P(r)=1/2K则P(ci/r)最大等效于P(r/ci)的最大，在此前提下最佳译码等效于最大似然译码。6.2.2最优译码与最大似然译码()(/)(/),1,2,,2()KiiiPPPiPcrccrr对于无记忆信道，例：BSC信道的最大似然译码可以简化为最小汉明距离译码。汉明距离译码是一种硬判决译码。由于BSC信道是对称的，只要发送的码字独立、等概，汉明距离译码也就是最佳译码。6.2.2最优译码与最大似然译码1(/)(/)NijijjMaxPMaxPrcrc6.3线性分组码消息m(n,k)码字cm=(mk-1,…,m1,m0)分组编码器c=(cn-1,…,c1,c0)qkqn构造线性分组码的方法就是构造子空间的方法,即在n维n重矢量空间的n个基底中选取k个基底张成一个k维n重子空间空间构成n维n重空间有相互正交的n个基底选择k个基底构成码空间C选择另外的(n-k)个基底构成空间HC和H是对偶的CHT＝0,GHT=0n维n重空间Vk维k重k维n重信息组码空间空间mC6.3.1生成矩阵和校验矩阵码空间的所有元素（即码字）都可以写成k个基底的线性组合c=mk-1gk-1+…+m1g1+m0g0=mG当信息元确定后，码字仅由G矩阵决定，因此我们称这k×n矩阵G为该(n,k)线性分组码的生成矩阵。系统形式的生成矩阵(n,k)码的任何生成矩阵都可以通过行运算（以及列置换）简化成“系统形式”。G=[IkP]=Ik是k×k单位矩阵，P是k×(n-k)矩阵。(1)(1)(1)1(1)01(1)11100(1)01001000100001knkkknknkppppppppp生成的码字C前k位由单位矩阵Ik决定，等于把信息组m原封不动搬到码字的前k位；其余的n-k位叫冗余位或一致校验位，是前k个信息位的线性组合。这样生成的（n,k）码叫做系统码。若生成矩阵G不具备系统形式，则生成的码叫做非系统码。系统化不改变码集，只是改变了映射规则。校验矩阵将H空间的n-k个基底排列起来可构成一个(n-k)×n矩阵，称为校验矩阵H。用来校验接收到的码字是否是正确的；G是(n,k)码的生成矩阵，H是它的校验矩阵；H是(n,n-k)对偶码的生成矩阵，它的每一行是一个基底。G则是它的校验矩阵。GHT=0，H＝[－PTIn-k]，二进制时，负号可省略。例6-2(6,3)线性分组码，其生成矩阵是G=求：(1)计算码集，列出信息组与码字的映射关系。(2)将该码系统化处理后，计算系统码码集并列出映射关系。(3)计算系统码的校验矩阵H。若收码r=[100110],检验它是否码字？(4)根据系统码生成矩阵画出编码器电原理图。111010①110001②011101③例6-2码集与映射关系信息码字系统码字000000000000000001011101001011010110001010110011101100011101100111010100111101100111101100110001011110001111010110111010例6-2二元(6,3)线性分组码编码器m0m1m2输入输出c0c1c26.3.2伴随式与标准阵列译码mC=(cn-1,…,c1,c0)R=(rn-1,…,r1,r0)(n,k)信道定义差错图案EE＝(en－1,…,e1,e0)＝R－C＝(rn-1－cn-1,…,r1－c1,r0－c0)二进制码中模2加与模2减是等同的，因此有E=R＋C及R=C＋E伴随式S的定义因为CHT=0所以RHT＝(C＋E)HT＝CHT＋EHT=EHT如果收码无误：必有R＝C即E＝0，则EHT=0RHT=0。如果收码有