信息论与编码-第6章 信道编码-课件.pdf
《信息论与编码-第6章 信道编码-课件.pdf》由会员分享,可在线阅读,更多相关《信息论与编码-第6章 信道编码-课件.pdf(125页珍藏版)》请在咨信网上搜索。
1、第6章信道编码信道编码是以信息在信道上的正确传输为目 标的编码,可分为两个层次上的问题:如何正确接收载有信息的信号-线路编码(Line Coding)如何避免少量差错信号对信息内容的影响-纠错编码(Error Correction Coding)本章内容 有扰离散信道的编码定理 纠错编译码的基本原理与分析方法 线性分组码 卷积码 编码与调制的结合一一TCM码运用级联、分集与信息迭代概念的纠错码6.1.1 差错和差错控制系统分类6.1.2 矢量空间与码空间6.1.3 随机编码6.1.4 信道编码定理差错类型差错符号:由符号发生差错引起,也叫信 号差错,信号差错概率用误码元率表示差错比特:由信息比
2、特发生差错引起,也 叫信息差错,信息差错概率用误比特率表 小对于二进制传输系统,符号差错等效于比 特差错;对于多进制系统,一个符号差错到底对应 多少比特差错却难以确定。因为一个符号 由多个比特组成。差错图样(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”既是符号差错也是比特差错,差错的个,数叫汉明距离差错图样类型 随机差错:若差
3、错图样上各码位的取值既与前后 位置无关又与时间无关,即差错始终以相等的概 率独立发生于各码字、各码元、各比特;一一双 绞线、同轴电缆、光纤、微波、卫星、深空通信突发差错:前后相关、成堆出现。突发差错总是 以差错码元开头、以差错码元结尾,头尾之间并 不是每个码元都错,而是码元差错概率超过了某 个额定值。多由突发噪声引起,雷电、电火花、时变信道的衰落、移动通信中的多径噪声等纠错码分类 从功能角度:检错码、纠错码 对信息序列的处理方法:分组码、卷积码 码元与原始信息位的关系:线性码、非线 性码 差错类型:纠随机差错码、纠突发差错码、介于中间的纠随机/突发差错码。构码理论:代数码(近世代数)、几何码(
4、投影几何)、算术码(数论、高等算数)、组合码(排列组合、数论)等差错控制系统分类 前向纠错(FEC):发端信息经纠错编码后 传送,收端通过纠错译码自动纠正传递过 程中的差错一一无需反向信道,时延小,但 设备较复杂反馈重发(ARQ):收端通过检测接收码是 否符合编码规律来判断,如判定码组有错,则通过反向信道通知发端重发该码混合纠错(HEC):前向纠错和反馈重发的 结合,发端发送的码兼有检错和纠错两种 能力一一移动通信和卫星通信得到应用6.1.2矢量空间与码空间(分组码(BlockCodes:把信息码流分割成左位 符号一组(称为信息组或信息码组),将其编成(心左)个码元组成的码字,所有的码字构成码
5、组(码表)m=(m 他,,mk_y)编码 c=Q,c?cn.)而 1 器 nL码字可以被看成是一个重矢量,个码元对应矢 量的n个元素这样,可以从矢量空间的角度来分析和理解分组码6.1.2矢量空间与码空间尸表示码元所在的数域,对于二进制码,厂代表二元 域 0,1 设重有序元素的集合片匕,匕=(匕。,匕,丁、一%eF若满足条件:V中矢量元素在矢量加运算下构成加群;V中矢量元素与数域/元素的标乘封闭在/中;分配律、结合律成立,则称集合P是数域厂上的重矢量空间。矢量空间中矢量的关系对于域尸上的若干矢量匕,匕 及 线性组合:.匕=%匕+。2匕+GF)线性相关:%匕+匕+L q 尸且不全为零)其中任一矢量
6、可表示为其它矢量的线性组合线性无关(线性独立):一组矢量中的任意一个 都不可能用其它矢量的线性组合来代替。矢量空间与基底 一组线性无关的矢量匕匕,线性组合 的集合就构成了一个矢量空间匕 这组矢量 就是这个矢量空间的基底。维矢量空间应包含个基底,可以说:n 个基底“张成”维矢量空间。基底不是唯一的,例:线性无关的两个矢 量(1,0)和(0,1)以及(-1,0)和(0,-1)可张成同一个二维空间。二元域GF(2)上三重矢量空间 2(100)为基底可张成一维三重子空间匕,含21=2个 元素,即 jz=(000),(100)以(010),(100)为基底可张成二维三重子空间Z,含22=4 个元素,即匕
7、=(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,也称零化空间)。构
8、成矢量的元素的个数称为“重”数,张成 矢量空间的基底的个数称为“维”数。通常好 不,分组编码的任务是要在 维重矢量空间的砂种可能组合中选择 其中的成个构成一个码空间,其元素(码矢量或码矢)就是许用码字的码集。分组编码的任务 选择一个左维重子空间作为码空间。确定由左维左重信息空间到A维重码空间 的映射方法。码空间的不同选择方法,以及信息组与 码组的不同映射算法,就构成了不同的分 组码。6.1.3随机编码 运用概率统计方法在特定信道条件下对编 码信号的性能作出统计分析,求出差错概 率的上下限边界,其中最优码所能达到的 差错概率上界称作随机码界。用这种方法不能得知最优码是如何具体编 出来的,却能得知
9、最优码可以好到什么程 度,并进而推导出有扰离散信道的编码定 理,对指导编码技术具有特别重要的理论 价值。6.1.3随机编码 在 N,&分组编码器中,K重消息组用逐个、随机地对应N 维矢量空间上的任一点(共有必个点)一个消息组有/种对应选择,两个消息组有qMgN种对应 选择,/个消息组选定的码集有 丫种 令“产 贝必K个消息组随机选定的码集有严/种第加个码集(记作。晨)被随机选中的概率是 P(cm)=q(NM)设与这种选择相对应的条件差错概率是乙(。葭)全部码集的平均差错概率是NM NM_ Q q 夕=2夕(。鼠)刀(。鼠)=夕一皿2金(。口)m=l m=l6.1.3随机编码 必定存在某些码集P
10、e(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是每码字的
11、码元数,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 )尺不变,信道容量大者 其可
12、靠性函数(&)也 大;。不变,码率减小时其 可靠性函数(尺)增大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纠错编码的基本思路纠错能力的获取:利用冗余度;噪声均化利用冗余度:在信息码流中插入冗余比特,利用 冗余比特
13、与信息码流之间的相关性进行检错和纠 错传输这些冗余比特要动用的资源:时间:重复重发(ARQ)频带:提高波特率(速率)功率:四进制变成八进制 设备复杂度:网格编码调制(TCM)621纠错编码的基本思路噪声均化:差错随机化由于噪声干扰的危害大小不但与噪声总量有关,而且还与其分布有关。如(7,4 汉明码纠一位 差错,14码元上有两个差错,不同分布结果不同噪声均化的方法:增加码长N 卷积 交错(交织)621纠错编码的基本思路交错器、7654321一654321出1413121110982 29 22|15|8 1 _14131211109821201918171615信道中5个连续的突发差错.信道21
14、 120;191817161528272625242328-一26一:-23一J35343332313029353432313029去交错器人图6-9 5X7行列交错器工作原理示意图622最优译码与最大似然译码译码器的任务是从受损的信息序列中 尽可能正确地恢复出原信息。译码算法的已知条件是:实际接收到的码字序列/,一(-1/2,八)发端所采用的编码算法和该算法产生的 码集心满足弓=(%.4xN 信道模型及信道参数。上622最优译码与最大似然译码消息组配,-码字9 I接收码,-值值C I消息氾编码器 信道 译码 消息还原最佳译码,也叫最大后验概率译码(MAP)ci-max P(cJ r)最大似然
15、译码(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旭=(叫
16、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正确,译出
17、的码也就是正确的。可以通过解线性方程求解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左个解
18、。到底取哪一个作为附加在收码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
19、)+(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行本身
20、就不是唯一的。注意在码表计算过程中,伴随式(0H)所对应的4个差错图案中有两个并列重量最轻,如果当时选的不是(000H)而是(10100),那么码表第7行就 不是现在这样了。633码距、纠错能力、MDC码及重量谱 N重码矢c=(加.12,.。0)可与7维矢量空 间当中的一个点对应,全体许用码字所对 应的点构成矢量空间里的一个子集发码一定在这个子集里,传输无误时的收 码也一定位于该子集当出现差错时,接收的N重矢量:对应到子集外空间某一点对应到该子集,却对应到该子集的另一点上633码距、纠错能力、MDC码及重量谱对大的 不码离 间的间作 是定距 之位字记 离决小 C的码,距者最 4同个距的小为 字
21、不两码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码及
22、重量谱 定理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)线性码的达到了次
23、+1,就是 达到了设计性能的极点。因此,dmm=次+1的码称 为极大最小距离码(MDC-Maximized minimum Distance Code o MDC码是凡人确定条件下纠错能力最 强的码 总体的、平均的纠错能力不但与最小距离有关,而 且与其余码距或者说与码字的重量分布特性有关 码距(码重)的分布特性称为距离(重量)谱。当各 码距相差不大(重量谱为窄谱)时性能较好 重量谱通常用多项式来表示 Z x =JAQ+AyX+:4%,i=0任何一个二元5线性分组码都有2-左个伴随式,假如该码的纠错能力是。则对于任何一个重量小 于等于犯勺差错图案,都应有一个伴随式与之对应,也就是说,伴随式的数目
24、满足条件其中W 加 口 W 7=-目,1上面的不等式等号成立时称作汉明限,任何一个 纠两马都应满足上述条件。某二元(,左)线性分组码能使等式成立,即该码的伴随式数目不多不少恰好和不 大于个差错的图案数目相等,相当于在标准译 码阵列中能将所有重量不大于才的差错图案选作 陪集首,而没有一个陪集首的重量大于K这时 的校验位得到最充分的利用。这样的二元(七左)线性分组码称为完备码。汉明码(Hamming Codes)汉明码不是指一个码,而是代表一类码。汉明码的纠错能力片1,既有二进制的,也有非二进制 的。二进制时,汉明码码长和信息位上服从以下规律:(,女)=(2加-1,2w-l-m)其中加=-左,是正
25、整数。当加=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)汉明
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信息论与编码-第6章 信道编码-课件 信息论 编码 信道编码 课件
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【曲****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【曲****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。