信息论与编码-第6章 信道编码-课件.pdf

第6章信道编码信道编码是以信息在信道上的正确传输为目 标的编码，可分为两个层次上的问题：如何正确接收载有信息的信号-线路编码(Line Coding)如何避免少量差错信号对信息内容的影响-纠错编码(Error Correction Coding)本章内容 有扰离散信道的编码定理 纠错编译码的基本原理与分析方法 线性分组码 卷积码 编码与调制的结合一一TCM码运用级联、分集与信息迭代概念的纠错码6.1.1 差错和差错控制系统分类6.1.2 矢量空间与码空间6.1.3 随机编码6.1.4 信道编码定理差错类型差错符号：由符号发生差错引起，也叫信 号差错，信号差错概率用误码元率表示差错比特：由信息比特发生差错引起，也 叫信息差错，信息差错概率用误比特率表 小对于二进制传输系统，符号差错等效于比 特差错；对于多进制系统，一个符号差错到底对应 多少比特差错却难以确定。因为一个符号 由多个比特组成。差错图样(Error Pattern)-定量地描述信号的差错，收、发码之“差”：差错图样石=发码C收码A(模/)例：8进制(M=8)码元，若发码 C=(0,2,5,4,7,5,2)收码变为 R=(0,154,7,5,4)差错图样 E=C-R=(0,1,0,0,0。6)(模8)二进制码：E=CA 或C=RE,差错图样中的“1”既是符号差错也是比特差错，差错的个，数叫汉明距离差错图样类型 随机差错：若差错图样上各码位的取值既与前后 位置无关又与时间无关，即差错始终以相等的概 率独立发生于各码字、各码元、各比特；一一双 绞线、同轴电缆、光纤、微波、卫星、深空通信突发差错：前后相关、成堆出现。突发差错总是 以差错码元开头、以差错码元结尾，头尾之间并 不是每个码元都错，而是码元差错概率超过了某 个额定值。多由突发噪声引起，雷电、电火花、时变信道的衰落、移动通信中的多径噪声等纠错码分类 从功能角度：检错码、纠错码 对信息序列的处理方法：分组码、卷积码 码元与原始信息位的关系：线性码、非线 性码 差错类型：纠随机差错码、纠突发差错码、介于中间的纠随机/突发差错码。构码理论：代数码（近世代数）、几何码（投影几何）、算术码（数论、高等算数）、组合码（排列组合、数论）等差错控制系统分类 前向纠错（FEC）：发端信息经纠错编码后 传送，收端通过纠错译码自动纠正传递过 程中的差错一一无需反向信道，时延小，但 设备较复杂反馈重发（ARQ）：收端通过检测接收码是 否符合编码规律来判断，如判定码组有错，则通过反向信道通知发端重发该码混合纠错（HEC）：前向纠错和反馈重发的 结合，发端发送的码兼有检错和纠错两种 能力一一移动通信和卫星通信得到应用6.1.2矢量空间与码空间（分组码（BlockCodes:把信息码流分割成左位 符号一组（称为信息组或信息码组），将其编成（心左）个码元组成的码字，所有的码字构成码组（码表）m=（m 他，,mk_y）编码 c=Q,c?cn.）而 1 器 nL码字可以被看成是一个重矢量，个码元对应矢 量的n个元素这样，可以从矢量空间的角度来分析和理解分组码6.1.2矢量空间与码空间尸表示码元所在的数域，对于二进制码，厂代表二元 域 0,1 设重有序元素的集合片匕,匕=（匕。，匕，丁、一%eF若满足条件：V中矢量元素在矢量加运算下构成加群；V中矢量元素与数域/元素的标乘封闭在/中；分配律、结合律成立，则称集合P是数域厂上的重矢量空间。矢量空间中矢量的关系对于域尸上的若干矢量匕,匕 及 线性组合：.匕=%匕+。2匕+GF）线性相关：%匕+匕+L q 尸且不全为零）其中任一矢量可表示为其它矢量的线性组合线性无关（线性独立）：一组矢量中的任意一个 都不可能用其它矢量的线性组合来代替。矢量空间与基底 一组线性无关的矢量匕匕，线性组合 的集合就构成了一个矢量空间匕 这组矢量 就是这个矢量空间的基底。维矢量空间应包含个基底，可以说：n 个基底“张成”维矢量空间。基底不是唯一的，例：线性无关的两个矢 量(1,0)和(0,1)以及(-1,0)和(0,-1)可张成同一个二维空间。二元域GF(2)上三重矢量空间 2(100)为基底可张成一维三重子空间匕，含21=2个 元素，即 jz=(000),(100)以(010),(100)为基底可张成二维三重子空间Z,含22=4 个元素，即匕=(000),(010),(100),(110)以(100),(010),(001)为基底可张成三维三重空间匕含23=8 个元素，匕和%都是/的子空间。101-001,001 oil in/000100/1001维3重空间(2个).000.0101002维3重空间 4个）100000010 0103维3重空间(8个)0矢量空间 每个矢量空间或子空间中必然包含零矢量 两个矢量正交：vvv2=0两个矢量空间正交：某矢量空间中的任意元素与另一矢量空间中的任意元素正交正交的两个子空间匕、匕互为对偶空间(Dual Space),其中一个空间是另一个空间的 零空间(Null Space,也称零化空间)。构成矢量的元素的个数称为“重”数，张成 矢量空间的基底的个数称为“维”数。通常好 不，分组编码的任务是要在 维重矢量空间的砂种可能组合中选择 其中的成个构成一个码空间，其元素（码矢量或码矢）就是许用码字的码集。分组编码的任务 选择一个左维重子空间作为码空间。确定由左维左重信息空间到A维重码空间 的映射方法。码空间的不同选择方法，以及信息组与 码组的不同映射算法，就构成了不同的分 组码。6.1.3随机编码 运用概率统计方法在特定信道条件下对编 码信号的性能作出统计分析，求出差错概 率的上下限边界，其中最优码所能达到的 差错概率上界称作随机码界。用这种方法不能得知最优码是如何具体编 出来的，却能得知最优码可以好到什么程 度，并进而推导出有扰离散信道的编码定 理，对指导编码技术具有特别重要的理论 价值。6.1.3随机编码 在 N,&分组编码器中，K重消息组用逐个、随机地对应N 维矢量空间上的任一点（共有必个点）一个消息组有/种对应选择，两个消息组有qMgN种对应 选择，/个消息组选定的码集有 丫种 令“产 贝必K个消息组随机选定的码集有严/种第加个码集（记作。晨）被随机选中的概率是 P（cm）=q（NM）设与这种选择相对应的条件差错概率是乙（。葭）全部码集的平均差错概率是NM NM_ Q q 夕=2夕（。鼠）刀（。鼠）=夕一皿2金（。口）m=l m=l6.1.3随机编码 必定存在某些码集Pe(cJPe 某些码集Pe(cm)Pe若N-0，就必然存在一批码集o即差错概率趋于零的好码一定存在6.1.3随机编石 码集点数河=/占N维矢量空间总点数qN的比例 是 F=qK/qN=q-（N-K）当K和N的差值拉大即冗余的空间点数增加时，平均而言码字的分布将变得稀疏，码字间的平均 距离将变大，平均差错概率将变小。当F-0即（N-幻一oo时，能否让平均差错概 率 Pe f0?Gallager在1965年推导了1的上边界，并证明这 个上边界是按指数规律收敛的。6.1.4信道编码定理PeeNE(R)（尺）称为可靠性函数，也叫误差指数 码率：R=（加/N M是可能的信息组合数，M=qK N是每码字的码元数，R表示每码元携带的信息量，单位是每符号比 特（bit/symbol）6.1.4信道编码定理 及在 0,4 区间时（尺）尺 曲线是斜率为-1-45。）的 直线，（夫）反比于K；而当火=。时&=0即可 靠性为零。&和R的关系曲线6.L4信道编码定理 正定理：只要传信率及小于信道容量G 总存在一种信道码（及解码器），可以以 所要求的任意小的差错概率实现可靠的通 信。逆定理：信道容量C是可靠通信系统传信 率R的上边界，如果火C,就不可能有任 何一种编码能使差错概率任意小。6.2.1纠错编码的基本思路622译码方法一最优译码与最大似然译码621纠错编码的基本思路Pe )尺不变，信道容量大者 其可靠性函数(&)也 大；。不变，码率减小时其 可靠性函数(尺)增大0 RtR2 G v c2增大E(A)的途径621纠错编码的基本思路-1.增大信道容量c p由Shannon公式 G=题下=/18（1+歹储田块 扩展带宽一一明线对称电缆同轴电缆光纤 加大功率一一提高天线增益全向天线改成定向波束天 线 降低噪声一一采用低噪声器件滤波屏蔽接地 2.减小码率R（R=g髻）0、N不变而减小K一在低信源速率 0、K不变而增大N提高信道输入符号速率 N、K不变而减小。提高信号间的区分电平增大码长N621纠错编码的基本思路纠错能力的获取：利用冗余度；噪声均化利用冗余度：在信息码流中插入冗余比特，利用 冗余比特与信息码流之间的相关性进行检错和纠 错传输这些冗余比特要动用的资源：时间：重复重发(ARQ)频带：提高波特率(速率)功率：四进制变成八进制 设备复杂度：网格编码调制(TCM)621纠错编码的基本思路噪声均化：差错随机化由于噪声干扰的危害大小不但与噪声总量有关，而且还与其分布有关。如（7,4 汉明码纠一位 差错，14码元上有两个差错，不同分布结果不同噪声均化的方法：增加码长N 卷积 交错（交织）621纠错编码的基本思路交错器、7654321一654321出1413121110982 29 22|15|8 1 _14131211109821201918171615信道中5个连续的突发差错.信道21 120；191817161528272625242328-一26一：-23一J35343332313029353432313029去交错器人图6-9 5X7行列交错器工作原理示意图622最优译码与最大似然译码译码器的任务是从受损的信息序列中 尽可能正确地恢复出原信息。译码算法的已知条件是：实际接收到的码字序列/,一（-1/2,八）发端所采用的编码算法和该算法产生的 码集心满足弓=（%.4xN 信道模型及信道参数。上622最优译码与最大似然译码消息组配，-码字9 I接收码，-值值C I消息氾编码器 信道 译码 消息还原最佳译码，也叫最大后验概率译码(MAP)ci-max P(cJ r)最大似然译码(MLD)C=max P(r/cJ622最优译码与最大似然译(/，)=尸（/）=I/P）如果构成码集的2K个码字以相同概率发送，满足尸(q)=l/2K,i=12.,2K。对于任何都有相同的值，满足尸=13 则P(q/r)最大等效于P(1/q)的最大，在此前 提下最佳译码等效于最大似然译码。622最优译码与最大似然译彳3 对于无记忆信道，NMaxP(r/q)=Max%。/qjJ=I例：BSC信道的最大似然译码可以简化为最 小汉明距离译码。汉明距离译码是一种硬判决译码。由于BSC 信道是对称的，只要发送的码字独立、等 概，汉明距离译码也就是最佳译码。63线性分组码消息阳(n,k)码字c旭=(叫i，切o)分组编码器c=(cn_19.9CpC0)qk Rfr=o。如果收码有误：即EwO,贝ijAZT=EZTw Oo在小固定的前提下，仅仅与差错图案 E有关，而与发送码。无关。定义伴随式Ss=应孑.2滓0)=RH1=EIT伴随式S的意义从物理意义上看，伴随式s并不反映发送的码字是 什么，而只是反映信道对码字造成怎样的干扰。|差错图案E是重矢量，共有2个可能的组合，而伴 随式S是（-左）重矢量，只有2孑个可能的组合，因此 不同的差错图案可能有相同的伴随式。接收端收到A后，因为已知，可求出S=M尹；如果能知道对应的E,则通过C=A+E而求得C。RHT=S?C=R+ER-SE-C只要E正确，译出的码也就是正确的。可以通过解线性方程求解E：S n-k-P*丹丹尸石山I-|T(“DS1)1)1 k(nk1)0 =(%1，与勺)：:%(1)一 4o得到线性方程组：力。(I)一%_S-hl=e-/(-hl)Ol)+e/(-hl)l+e0 h(n-k-l)Osi=+.+?0%0+J h。+e()oo差错图案的求解上述方程组中有个未知数分T，气，却只 有-左个方程，可知方程组有多解。在有理数或实数域中，少一个方程就可能导致 有无限多个解，而在二元域中，少一个方程导 致有两个解，少两个方程有四个解，以此类推,少-(n-k)=左个方未呈导致每个未知数有才个解。因此，由上述方程组解出的E可以有2左个解。到底取哪一个作为附加在收码A上的差错图案E 的估值呢？概率译码：把所有2人个解的重量(差错图案E中1 的个数)作比较，选择其中重量最轻者作为E的 估值。该方法概念上很简单但计算效率不高。依据：若BSC信道的差错概率是则长度 的码中错误概率：0个错 1个错 2个错 个错(l-p)n p(T-p)n-，p2(1_py-2 pn由于?讲=(010)=54,确定S4所在行，再 沿着行对码表作一维搜索找到(10101),最后顺着所在列向上找 出码字(101。)。先求出伴随式加=(010)=S4并确定4所对应的陪集首(差错 图案)4=(00010),再将陪集首与收码相加得到码字C=A+七4二(10101)+(00010(10111)o上述三种方法由上而下，查表的时间下降而所需计算量增大,实际使用时可针对不同情况选用O对上例作进一步分析，还可以看到，该(5,2)码的纠错能力是%=INT(3-1)/2=1。因此,译码阵列中 只有前6行具有唯一性、可靠性，真正体现了最大似然译 码准则，而第7、8行的差错图案(00011)和(00110)中包含两 个“1、已超出了片1的纠错能力，译码已不可靠。比如，当收码R=(10100)时，根据码表译出的码字是(10H1),与 收码R的汉明距离是2,然而收码R与全零码字(00000)的汉 明距离也是2,为什么不能译成(00000)呢？事实上，码表 的第7、8行本身就不是唯一的。注意在码表计算过程中，伴随式(0H)所对应的4个差错图案中有两个并列重量最轻,如果当时选的不是(000H)而是(10100),那么码表第7行就 不是现在这样了。633码距、纠错能力、MDC码及重量谱 N重码矢c=（加.12，.。0）可与7维矢量空 间当中的一个点对应，全体许用码字所对 应的点构成矢量空间里的一个子集发码一定在这个子集里，传输无误时的收 码也一定位于该子集当出现差错时，接收的N重矢量：对应到子集外空间某一点对应到该子集，却对应到该子集的另一点上633码距、纠错能力、MDC码及重量谱对大的 不码离 间的间作 是定距 之位字记 离决小 C的码，距者最 4同个距的小为 字不两码G间最之 码元该称g字距称 两码为简4码码，.,卜义，各，性 距位定离 集的特 码应小距 码同的二mmC633码距、纠错能力、MDC码及重量谱 定理6.1任何最小距离加的线性分组码，其检错能力为(%)，纠错能力为工d-71%=INT _ 2 _ 定理6.2线性分组码的最小距离等于码集中非零码字的最 小重量dmin-min w(Cz)CfC 及C产。其中w(G)代表码字G中非零码元的个数(对于二元码即1 的个数)，称为码字的重量，简称码重。因为，线性分 组码具有封闭性，即任何两个码字的和一定是另外一个码 字十。.Q=C,C CGsC j k i)i5 j)k633码距、纠错能力、MDC码及重量谱 定理6.3（水）线性分组码最小距离等于（in 的充要条件是：校验矩阵中有（min）列 线性无关。定理6.4（天）线性分组码的最小距离必定小 于等于（n-k+1）dmin V（孑+1）633码距、纠错能力、MDC码及重量谱例6.3：(7,4)线性码的校验矩阵为1110 10 0H=0111010110 10 0 1各列都不相同，任意2列之和不等于0,任意2 列线性无关；任意2列之和一定等于矩阵中某一列,有3列线性相关。所以该码的最小距离为3,小于 n-k+1=4 633码距、纠错能力、MDC码及重量谱（n,k）线性码最小距离心由的上边界是孑+1。如果 我们设计的 5 k）线性码的达到了次+1，就是 达到了设计性能的极点。因此，dmm=次+1的码称 为极大最小距离码（MDC-Maximized minimum Distance Code o MDC码是凡人确定条件下纠错能力最 强的码 总体的、平均的纠错能力不但与最小距离有关，而 且与其余码距或者说与码字的重量分布特性有关 码距（码重）的分布特性称为距离（重量）谱。当各 码距相差不大（重量谱为窄谱）时性能较好 重量谱通常用多项式来表示 Z x =JAQ+AyX+:4%，i=0任何一个二元5线性分组码都有2-左个伴随式，假如该码的纠错能力是。则对于任何一个重量小 于等于犯勺差错图案，都应有一个伴随式与之对应,也就是说，伴随式的数目满足条件其中W 加 口 W 7=-目，1上面的不等式等号成立时称作汉明限，任何一个 纠两马都应满足上述条件。某二元（,左）线性分组码能使等式成立，即该码的伴随式数目不多不少恰好和不 大于个差错的图案数目相等，相当于在标准译 码阵列中能将所有重量不大于才的差错图案选作 陪集首，而没有一个陪集首的重量大于K这时 的校验位得到最充分的利用。这样的二元（七左）线性分组码称为完备码。汉明码(Hamming Codes)汉明码不是指一个码，而是代表一类码。汉明码的纠错能力片1,既有二进制的，也有非二进制 的。二进制时，汉明码码长和信息位上服从以下规律:(,女)=(2加-1,2w-l-m)其中加=-左，是正整数。当加=3、4、5、6、7、8时,有汉明码(7,4)、(15,11)、(31,26)、(63,57)、(127,120)、(255,247).o汉明码是完备码，因为它满足上述等式。r了=。3 7=1+=1+(2/1)=2=2nk汉明码的校验矩阵以具有特殊的性质，能 使构造方法简化。一个（,左）码的校验矩阵有一 左行和列，二进制时/个码元所能组成的列矢 量总数是2也1,恰好和校验矩阵的列数=2加-1 相等。只要排列所有列，通过列置换将矩阵H 转换成系统形式，就可以进一步得到相应的生 成矩阵G。例6.4(p46)构造一个加=3的二元(7,4)汉明码。解：先利用汉明码的特性构造一个(7,4)汉明码的校验矩阵，再通过列置换将它变为系统形式:“00111 1下!1置换H=0110011 nG 0 1 0 1 0 1 Jri 11 on o(no 111 io i o li i o/oo=产R再得生成矩阵G为r i o o o i o nG=I4:P=0 1001110010110I。0 0 1 0 1 J高莱(Golay)7 是二进制(23,12)线性码,其最小距禺痣加=7，纠错能力，=3。是完备码，因为满足等式223-12=2048=i+t+川 在(23,12)码上添加一位奇偶位即得二进 制线性(24,12)扩展高莱码，其最小 距离乙；“=8。635循环码 循环码是线性码的一个子类；满足下列循环移位特性：码集。中任何一个 码字的循环移位仍是码字。循环码的多项式描述 一般（水）线性分组码的左个基底之间不存在 规则的联系，因此需用左个基底组成生成矩 阵来表示一个码的特征。而循环码的左个基底可以是同一个基底循环左 次得到，因此用一个基底就足以表示一个 码的特征。既然只有一个基底，就无需矩阵，只要用 多项式作为数学工具就足够了。循环码的多项式定义把码字与一个不大于 n-1次的码多项式C(x)对应起来。码多项式C(x)定义为：C(x)=。止 1产+cn_2 xn-2+.+c1x+c0对于二进制码，q01=0,.，n-1 o循环码的循环移位循环移一位：(叫72。1。0)一(，24。0%)循环移一位：C0(x)=cn_xxn-x+cn_2xn-2+.+CyX+c0-q(x)=，2X/+C-3X2+.+C/+CnA比较循环移位的前后，可用如下的多项式运算来表 达循环移位移 1 位：C(x)=xC0(x)mod(x+1)移2位：C2(x)=xCx(x)=x2C0(x)mod(xn+1)移-1 位：Cw l(x)=xC_2(x)=xn-1C0(x)mod(xn+l)码字的组成根据码空间的封闭性，码字的线性组合仍是码 字。C(X)=4Z0C0(X)+6Z1XC0(X)+(22X2C0(X)+.+an_cnxCx)=(aac+4Z2X2+.+Q_IX-I)CO(X)=A(x)C0(x)mod(xn+1)其中g(x)是一个码多项式，而/(x)是次数不大于-1的任意多项式。对于二进制码，01=0,，Z7-1 oC(x)=m(x)g(x)I 码多 信息生成 I 项式 多项式多项式 J 生成多项式不是唯一的；g(x)=xn-k+gn.kAxn-k-x+.+g2x2+g1%+1 岁O女)次的首一码多项式，即(团次项的系数 为1。g(x)一定是(X+1)的因子。校验多项式 多项式W+1可因式分解为炉+1=8。)(工)的形式；如果g(x)代表(，左)循环码的生成多项式，则力(X)代 表该循环码的一致校验多项式，其阶次为展 力。)的校验作用表现在：任何码多项式C(x)与(X)的 模产+1乘积一定等于0,而非码字与/x)的乘积必不 为0。C(x)h(x)=m(x)g(x)h(x)=m(x)(xn+V)=0 mod(xn+l)例6.5研究一个长度=7的循环码的构成方法(1)对(N+1)作分解，找出-人次因式。x7+1=(x+l)(x3+x2+l)(x3+x+1),n-k 因式 g(x)1(x+1)3(x3+x2+l)3(x3+x+l)4(x+l)(x3+x2+l)4(x+l)(x3+x+l)6(x3+x2+1)(x3+x+1)对偶式/z(x)循环码(x3+x2+l)(x3+x+1)(7,6)(x+l)(x3+x+l)(7,4)(x+l)(x3+x2+l)(7,4)(x3+x+l)(7,3)(x3+x2+l)(7,3)(x+D(7,1)例6.5研究一个长度=7的循环码的构成方法构成(7,3)循环码：选g(x)=(x+1)(13+x+1)=(x4+x3+x2+1),贝tlC(x)=m(x)g(x)=(m2x2+m 1x+m0)(x4+x3+x2+1)。当输入信息冽=(011)时，m(x)=(+l),C(x)=(x+l)(x4+x3+x2+1)=x5+x2+N+1,对应码矢C=(0100111)。研究一个长度=7的循环码的构成方法信息矢量朋（加2吗m0）码矢 C(c6c5 c4c3 c2c t C)000 001 010 011 100 101110 1110000000 0011101 0111010 0100111 1110100 11010011001110 1010011系统循环码码字的前左位原封不动照搬信息位而后面(一左)位为校验位：C(x)=xnk m(x)+r(x)产生系统循环码的方法：将信息多项式加(x)预乘产六 即右移(n-k)位;将廿孑m(x)除以g(x)，得余式x);得系统循环码的码多项式：C(x)=xnkm(x)+r(x)o例6.6(7,3)循环码生成多项式是虱工)=、4+%3+%2+1,用式(6-3-35)产生系统循环码。解：先以输入信息M=(on)即加(%)=(1+1)为例，.xnkm(x)=x4(x+1)=x5+x4.(必+%4)除以(短+如+/+),得余式年+工).C(x)=xnk m(x)+r(x)=(x5+x4)+(x3+x),对应码矢(onioio)。依次将(000)(in)代入，可得全部码矢如表6-6。此表与表 6-5对比，可见码集未变而映射规则变了，表6-6满足系统循 环码要求。扩展码如果给每个码字添加一位奇偶校验位。校，构成(+1,k)线性码，称为扩展码。1，()*。-1，1，。0，。校7。校=0在二进制偶校验时：原来码字中I的个数为偶数，则添加校验位0;原来码字中1的个数为奇数，则添加校验位1。如果某码原来的最小重量是奇数，则新的最小距离变为%n+l，检错能力增1。O-O校验矩阵g=H;1 1缩短码 把第一位为1的所有码字舍去，剩下另一半第 一位为0的码字舍去它们的第一位后组成一个 新的（一1,k1 码，称为缩短码。码长-1和信息位长度左一1均缩短了。（一1,左一1 缩短码共包含+2=22个码字。由于原先保留的均是第一位为0的码，舍去它 们的第一位不会改变码的最小重量，因此缩短 码与原码具有同样的人出。称为41/缩短码。例6.7(7,4)码的生成矩阵为1 o0 10 00 00 0 10 10 0 11110 110o 1 o 1 1_ 4X7吗卬2ml mQ2CilCiO0!0 0 0 10 0 0C=mG010 0 1 10 1 1010 1 0 II 1 0=加3加2加i加(J10000 0 0 1 0 110 0 1110 10 1100 0 10 110!0 1 10110 0Oil 0 1on 1 0oil 1 11 0 11 1 11 0 00 0 10 1 0码字中的。6去掉，。6是信息位用 与G的第一列相乘结果，所以G的第 一列应去掉；吗去掉，而吗是与G的 第一行相乘，所以G的第一行也去掉。得到新的生成矩阵为G=10 0 1110 10 1100 0 10 113X6原来的校验矩阵为H=101110 10 01110 1010 10 0 13X7校验时，计算用因，的第一位已没有，故杯的第一行 应去掉，即的第一列去掉。得到新的校验矩阵”为H=110 10 01110 1010 10 0 1d加不变，为3。3X6循环冗余校验 CRC 码数据通信中，统计复用的基本单元（帧，分组，包，信元）通常在尾部预留若干位做差错检验，前面信息位长度可变。信息位上和码长可变，校验位长度孑固定，符合 缩短循环码的特点。以一个选定的（循环码为基础，改变，值，得出 任意信息长度的码字，而纠检错能力保持不变。循环冗余校验码（CRC-Cyclic Redundancy Check）是系统的缩短循环码。例6.8(p.158)某CRC码的生成多项式g(x)=、4+x+l。如果想发送一串信息U0001的前6位并加上CRC校验，发码应 如何安排？收码又如何检验？解：本题信息多项式加(X尸15+14+,即左=6,因此=10,degg(x)=4=n-k o将X次加(X)除以g(x),得余式r(x)=xnk m(x)mod g(x)=x4(x5+x4+l)mod g(x)=(x9+x8+x4)mod g(x)=x3+x2于是发码C(x)=xnk m(x)+r(x)=x9+x8+x4+x3+x2,对应的码字是(HOOOlllOO)o接收端的CRC校验实际上就是做除法。如果收码无误，火(、)除以g(x)应得余式0;反之，如果余式不等于零就说明一 定有差错。6.4 卷积码(Convolutional Codes)卷积码的产生 1955年由麻省理工学院（MIT 的Elias提出.分组码以孤立码块为单位编译码 信息流割裂为孤立块后丧失了分组间的相关信息 分组码长越大越好，但译码运算量随指数上升本节内容 卷积码的基本概念和描述方法 卷积码的最大似然译码维特比算法 卷积码的性能限与距离特点 二6.4.1卷积码的基本概念和描述方法将信息序列分隔成长度为人的一个个分组某一时刻的编码输出不仅取决于本时刻的分组，而且取决于本时刻以前的L个分组称 +1 为约束长度(Constraint Length)最重要的三个参数(n,k,L)（小左L 卷积编码小意第，.分组第11分组第12分组第Z-A分组编码输出C，例6.9(p60)二进制(3,2,1)卷积编码器本时刻配。=(加o。,加1。)=(01),上一时刻加=(加o 加J尸(10)g初发示记忆阵列第左行(仁0,1)第/列(/=0,1)对第个(=0,1,2)码元的影响，共NXKX(+1尸3 X2X2个系数：goo=1，goo：1，goi=，goJ=1，go2=1021=1，gio=。，gio7 用矩阵表示gll=1giJ=，&2=Lg/：。G=goo goi S02gfo g：g；21 00 111G goo goi go2 gio gii Sn1 1 11 0 0例6.9(p.160)二进制(3,2J)卷积编码器 本时刻编码输出：c2 尸 m0G+mlG1ri o ii ri i r1 1/(1。)1 0 oj=(011)+(111)=(100)矩阵表示法 Matrix Approach 上例中的GGi具有一般意义 对于 N,K，卷积码，对应第/个信息码组对第z个 时刻的输出码字。的影响的矩阵G，称为第/个生 成子矩阵，即giO g 1)_g（K1 0 g（K1 1 1/NT 矩阵元素或表示记忆阵列第檎入行，第时延 一 列H第个输出国元的影响，g，（0,l 矩阵表示法 Matrix Approach 设编码器的初始状态为零（记忆阵列全体清0,随着时刻，的递推和左比特信息组（阳。,加,.,mL.阳，+1.）源源不断地输入，码字 O源源不断地输出。在时亥作=0时，（y=wGz=1 时，。1=m1G（）+mG1 i=L 时，CL=MG。+，=+l 时，。+1=mL+xG+mLG1.m1GL矩阵表示法(Matrix Approach)可等效地用半无限矩阵的形式来表示，即G G10 170 G.0 0 Gv G10 0 00 0 00 0-0Gg为卷积码的生成矩阵，由于输入的信息序列是半无限的,所以G0c也应该是半无限的于是任何时刻拍勺输出码字：r “C=m G上式可看成是加与&的卷积,这就是卷积码名称的来历即 mG1G(Q)=GQ+GlD+.+CWg0（。）goi（）八）刍。、一 D）g(K-1)0(。)g(K-1)1(。)/NT)ghX0)=g区+g初 O+g如 Q+.+g初=X gknDl 1+D D +D G(D)=在例6.11中 D 1 1例6.10二元(3,1,2)卷积码的转移函数矩阵G(D)=(l，l+2 1+Q+Q2),根据转移函数矩阵,goo（Q =gOo+goo】。+oo2 U=1goi（D）=goi+goJ。+go/D2=1+Dgo2。尸 02+021+022 02=1+D+D2得 goo=l，goo1=g X 2=0,goi=l，goJ=l，go/=O,g02=l，So2=i W=1状态流图表示法(StateDiagram Approach)卷积码编码器在第，时刻输出的码字不仅取决于本时刻 输入的信息组加，而且还取决于第泮寸刻之前存入记忆 阵列的个信息组，即还取决于记忆阵列的内容一一称 为编码器的状态用函数形式表示o=/（加，加工 F）其中（加，2,二称为本时刻编码器的状态 则下一时刻编码器的状态为SI+1=1 2,）=本时刻信息组加和编码器本时刻状态&就决定了编码 器本时刻的输出。.和记忆阵列的下一个状态S+1状态流图表示法(State-Diagram Approach)由于信息组的组合（花样）和编码器的状态组合是有限数量 的，所以可以用信息组触发的状态转移图来描述卷积码例 6.11(p.l63)(3,l,2)卷积码A号人叫EHm _z-2编码器状态状态加o/m/2S：0110 1 不同状态与输入时输出的码字俞人moz=0moz=1s。000111001110邑011100|S30101011 输出不同状态与输入相下一状态俞入moz=0mJ=150S。S?4S。$2S?S3$3S3状态流图表示法（StateDiagram,更直观的方法是采用编码矩阵和状态流图s。50 r 000C=S,001S2.S3H s?S3-111-110 011 100010 101假如输入信息序列是 iono.,c 1/111 c 0/011 c 1/110 c则输出的码字序列为ni on iio 100010网格图表示法(Trellis Approach)输入信息序列是iono,输出码字是ill,on,no,wo,oio.第一部分：网格图第二部分：编码轨迹（路径）图1/101卷积码的最大似然译码一一维特比(Viterbi)算法 Viterbi译码是1967年由AJViterbi提出的一种概率 译码算法 后来由Forney证明Viterbi译码是一种最大似然译码 特点是速度快、译码器较简单，并且比较充分地 利用了信道的统计特性 理论上和实际应用上都得到了极其迅速的发展不仅广泛地用于各种数字传输系统，而且还广泛 应用于处理多种数字估值问题维特比（Viterbi 译码 卷积码的性能取决于卷积码的距离特性和译码算 法 设C,是同一时刻从同一状态出发的任意两个 不同的二进制码字序列序列距离定义为两序列在对应时刻的码字的汉明 距离之和由线性码的封闭性，Cc（2）=c，则。也是一 个码字序列则有d 仁，。=w(C)=W(CO)=d(C.O)维特比（Viterbi 译码 序列距离还与序列的长度有关 定义：长度/（码字）的任意两序列的最小距离为/阶列 距离，记作（/）,即4/=min卜仁,C。）：C。）w C。）=向口恒:C w 0 当/一 0时，任意两序歹I）的最小距离称为自由距离，记作df,即df=lim /=min卜（。?C 2）:C 1 w C 2 =min/Q:C wo 自-距离就是在网格图上所有路径中，重量最轻（与全零序列距离最近）的那条路径的重量维特比(Viterbi)译码例6.12(p.l66)仍以(3,1,2)卷积码为例。输入信息序列10110分析：0时刻从0状态与全零路径分叉却又回到全零路径的 所有可能的路径如下图所示，其中伴随每个转移所标的数 字是对应码字与全零码的距离。S0S2S So So-limdc(/)=W(lll,011,001,000,000,)=6；/-oo So S2 s3 Si So So limt/c(Z)=W(lll,100,010,001,000,-)=6 o图6-22(3,1.2)卷积码的自由距离4维特比（Viterbi 译码 图中，o时刻分叉后的第一次转移只有一条非零分 支，列距离4 1尸3。第二次转移后（时亥U2T）有2sl和2s3两条路径,重量分别是成（n 1 o 11）,（oooooo）=5 和矶（n 11 oo）,000000 =4,选其中小者为列距离，得4（2）=4。以此类推，可得各阶列距离如图底部所标。比较各值，发现/在 4产范围内列距离不变，即得 自由距离dl=limdO=6I具有该自由距离的路径有两条第6章信道编码复习 6有扰离散信道的编码定理 6.1.1差错和差错控制系统分类|6.1.2矢量空间与码空间 6.1.3随机编码 6.L4信道编码定理 6.2纠错编译码的基本原理与分析方法 621纠错编码的基本思路 6.2.2译码方法一最优译码与最大似然译码第6章信道编码复习 6.3线性分组码 6.3.1线性分组码的生成矩阵和校验矩阵 6.3.2伴随式与标准阵列译码.633码距、纠错能力、MDC码及重量谱 6.3.4完备码 6.3.5循环码 637分组码的扩展、缩短与循环冗余校验CRC 6.4卷积码 6.4.1卷积码的基本概念和描述方法第6章信道编码复习概念：差错符号、差错比特 差错图样：随机差错、突发差错 纠错码分类：检和纠错码、分组码和卷积码、线性码与非线性码、纠随机差错码和纠突发差 错码矢量空间与码空间 维重空间有相互正交的个基底 选择左个基底构成左 维重码空间C 选择另外的（-左）个 基底构成空间H。和H是对偶的，正 交的5=0,GIT=O有扰离散信道的编码定理Pe C,就不可能有任何一种编码能使 差错概率任意小。差错控制的途径 从公式 Pe Eg增大码长N增大可靠性函数（&：加大信道容量C减小码率（传信率）及。从概念上利用冗余度（增强相关性）噪声均化（随机化）最优译码与最大似然译码八 最佳译码q=Max P(cz/r),性能优，实.现难 最大似然译码C=Max P(r/cz),性能次 优，实现容易 最佳译码等同最大似然译码：、码集的码字以相同概率发送接收码等概分布线性分组码线性分组码基本概念 码元、码字、码集 重量、重量分布、恒重码 线性码（封闭性）基底、矢量正交、矢量空间正交、对偶 空间、线性相关、线性无关生成矩阵和校验矩阵 生成矩阵G：C=mG 校验矩阵：5=0系统形式：G=IkP,H=PInk 差错图案后=4-。，伴随式5=7?印=石印 标准阵列译码表码距与纠、