第6章信道编码.ppt
《第6章信道编码.ppt》由会员分享,可在线阅读,更多相关《第6章信道编码.ppt(111页珍藏版)》请在三一文库上搜索。
1、1,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,第6章 信道编码,信道编码是以信息在信道上的正确传输为目标的编码,可分为两个层次上的问题: 如何正确接收载有信息的信号 线路编码 如何避免少量差错信号对信息内容的影响 纠错编码,2,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,本章内容,有扰离散信道的编码定理 纠错编译码的基本原理与分析方法 线性分组码 卷积码 编码与调制的结合TCM码 运用级联、分集与信息迭代概念的纠错码,3,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.1 有扰离散信道的编码定理,差错和差错控制系统分类 矢量空间与码空间
2、随机编码 信道编码定理,4,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,差错类型,差错符号:由符号发生差错引起,也叫信号差错,信号差错概率用误码元率表示 差错比特:由信息比特发生差错引起,也叫信息差错,信息差错概率用误比特率表示 对于二进制传输系统,符号差错等效于比特差错; 对于多进制系统,一个符号差错到底对应多少比特差错却难以确定。因为一个符号由多个比特组成。,5,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,差错图样(error pattern),定量地描述信号的差错,收、发码之“差” : 差错图样E发码C 收码R (模M) 例:8进制(M=8)码元, 若
3、发码 C=(0,2,5,4,7,5,2) 收码变为 R=(0,1,5,4,7,5,4) 差错图样 E=CR=(0,1,0,0,0,0,6)(模8) 二进制码:E=C R 或 C = R E ,差错图样中的“”既是符号差错也是比特差错,差错的个数叫汉明距离。,6,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,差错图样类型,随机差错:若差错图样上各码位的取值既与前后位置无关又与时间无关,即差错始终以相等的概率独立发生于各码字、各码元、各比特; 突发差错:前后相关、成堆出现。突发差错总是以差错码元开头、以差错码元结尾,头尾之间并不是每个码元都错,而是码元差错概率超过了某个额定值。,7
4、,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,纠错码分类,从功能角度:检错码 、纠错码 对信息序列的处理方法:分组码、卷积码 码元与原始信息位的关系:线性码、非线性码 差错类型:纠随机差错码、纠突发差错码、介于中间的纠随机/突发差错码。 构码理论:代数码、几何码、算术码、组合码等,8,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,差错控制系统分类,前向纠错(FEC):发端信息经纠错编码后传送,收端通过纠错译码自动纠正传递过程中的差错 反馈重发(ARQ):收端通过检测接收码是否符合编码规律来判断,如判定码组有错,则通过反向信道通知发端重发该码 混合纠错(HEC)
5、:前向纠错和反馈重发的结合,发端发送的码兼有检错和纠错两种能力,9,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.1.2矢量空间与码空间,F表示码元所在的数域,对于二进制码,F代表二元域0,1 设n重有序元素的集合V= Vi , 若满足条件: V中矢量元素在矢量加运算下构成加群; V中矢量元素与数域F元素的标乘封闭在V中; 分配律、结合律成立, 则称集合V是数域F上的n维矢量空间,或称n维线性空间,n维矢量又称n重(n-tuples)。,10,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,矢量空间中矢量的关系,对于域F上的若干矢量 线性组合: 线性相关: 其
6、中任一矢量可表示为其它矢量的线性组合 线性无关或线性独立:一组矢量中的任意一个都不可能用其它矢量的线性组合来代替。,11,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,矢量空间与基底,一组线性无关的矢量 ,线性组合的集合就构成了一个矢量空间V,这组矢量 就是这个矢量空间的基底。 n维矢量空间应包含n个基底 基底不是唯一的,例:线性无关的两个矢量(1,0)和(0,1)以及(-1,0)和(0,-1)可张成同一个两维空间 。,12,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,二元域GF(2)上三重矢量空间,以(100)为基底可张成一维三重子空间V1,含21 =2 个
7、元素,即 以(010)(001)为基底可张成二维三重子空间V2,含 22 =4个元素,即 以(100)(010)(001)为基底可张成三维三重空间V,含 23 =8个元素,V1和V2都是V的子空间。,13,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,矢量空间,每个矢量空间或子空间中必然包含零矢量 两个矢量正交:V1V2 0 两个矢量空间正交:某矢量空间中的任意元素与另一矢量空间中的任意元素正交 正交的两个子空间V1、V2互为对偶空间 (Dual Space),其中一个空间是另一个空间的零空间(null space,也称零化空间)。,14,普通高等教育“十五”国家级规划教材信息
8、论与编码 曹雪虹等编著,码空间,消息k长 (n , k) 码字n长,qk 种 分组编码器 qn种 k维k重矢量 n维n重矢量,通常qn qk,分组编码的任务是要在n维n重矢量空间的qn种可能组合中选择其中的qk个构成一个码空间,其元素就是许用码的码集。,15,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,分组编码的任务,选择一个维n重子空间作为码空间。 确定由k维k重信息空间到维n重码空间的映射方法。 码空间的不同选择方法,以及信息组与码组的不同映射算法,就构成了不同的分组码。,16,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.1.3随机编码,运用概率统计
9、方法在特定信道条件下对编码信号的性能作出统计分析,求出差错概率的上下限边界,其中最优码所能达到的差错概率上界称作随机码界。 用这种方法不能得知最优码是如何具体编出来的,却能得知最优码可以好到什么程度,并进而推导出有扰离散信道的编码定理,对指导编码技术具有特别重要的理论价值。,17,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.1.3随机编码,在(N,K)分组编码器中随机选定的码集有qNM种 第m个码集(记作cm )被随机选中的概率是 设与这种选择相对应的条件差错概率是Pe(cm) 全部码集的平均差错概率是,18,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,
10、6.1.3随机编码,必定存在某些码集 某些码集 若 ,就必然存在一批码集 即差错概率趋于零的好码一定存在,19,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.1.3随机编码,码集点数M=qK占N维矢量空间总点数qN的比例是 F =qK / qN = q-(N-K) 当K和N的差值拉大即冗余的空间点数增加时,平均而言码字的分布将变得稀疏,码字间的平均距离将变大,平均差错概率将变小。 当F0 即(N-K)时,能否让平均差错概率 ? Gallager在1965年推导了 的上边界,并证明这个上边界是按指数规律收敛的。,20,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编
11、著,E(R)为可靠性函数,也叫误差指数 码率:R =( lbM) / N M是可能的信息组合数,M=qK N是每码字的码元数, R表示每码元携带的信息量,单位是每符号比特(bit / symbol),6.1.4信道编码定理,21,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,R在0,R0区间时E(R)R曲线是斜率为-1(-45)的直线,E(R)反比于R;而当R=C时E(R)=0即可靠性为零。,6.1.4信道编码定理,22,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,正定理:只要传信率R小于信道容量C,总存在一种信道码(及解码器),可以以所要求的任意小的差错概率
12、实现可靠的通信。 逆定理:信道容量C是可靠通信系统传信率R的上边界,如果R C,就不可能有任何一种编码能使差错概率任意小。,6.1.4信道编码定理,23,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.2 纠错编译码的基本原理与分析,纠错编码的基本思路 译码方法最优译码与最大似然译码,24,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.2.1纠错编码的基本思路,R不变,信道容量大者其可靠性函数E(R)也大; C不变,码率减小时其可靠性函数E(R)增大,25,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.2.1纠错编码的基本思路,增大信道
13、容量C 扩展带宽 加大功率 降低噪声 减小码率R Q、N不变而减小K Q、K不变而增大N N、K不变而减小Q 增大码长N,26,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.2.2最优译码与最大似然译码,译码器的任务是从受损的信息序列中尽可能正确地恢复出原信息。 译码算法的已知条件是: 实际接收到的码字序列r, r=(r1,r2,rN) 发端所采用的编码算法和该算法产生的码集XN, 满足 信道模型及信道参数。,27,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,最佳译码,也叫最大后验概率译码(MAP) 最大似然译码( MLD),6.2.2最优译码与最大似然译
14、码,消息组mi 码字ci 接收码r 估值 消息,编码器 信道 译码 消息还原,28,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,如果 构成码集的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最优译码与最大似然译码,29,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,对于无记忆信道, 例:BSC信道的最大似然译码可以简化为最小汉明距离译码。 汉明距离译码是一种硬判决译
15、码。由于BSC信道是对称的,只要发送的码字独立、等概,汉明距离译码也就是最佳译码。,6.2.2最优译码与最大似然译码,30,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.3 线性分组码,消息m (n , k) 码字c,m=(mk-1,m1,m0) 分组编码器 c=(cn-1,c1,c0) qk qn,码集C能否构成n维n重矢量空间的一个k维n重子空间? 如何寻找最佳的码空间? qk个信息元组以什么算法一一对应映射到码空间。 码率编码效率:Rc =k/n,31,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.3.1 生成矩阵和校验矩阵,c m G 1n 1k
16、 kn 码字 消息 生成矩阵 Ggk-1g1g0T,有k个(1n)行矢量,如何选择呢?,32,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,线性分组码的形成,c = mk-1 gk-1+ m1 g1+m0 g0 码空间的所有元素(即码字)都可以写成k个基底的线性组合 由于k个基底即G的k个行矢量线性无关,矩阵G的秩一定等于k。 当信息元确定后,码字仅由G矩阵决定,因此我们称这kn 矩阵G为该(n,k)线性分组码的生成矩阵。,33,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,生成矩阵G(kn)的特点,想要保证 (n,k)线性分组码能够构成k维n重子空间,G 的k
17、个行矢量gk-1, g1, g0必须是线性无关的,只有这样才符合作为基底的条件。 由于基底不是唯一的,所以G也就不是唯一的。 不同的基底有可能生成同一码集,但因编码涉及码集和映射两个因素,码集一样而映射方法不同也不能说是同样的码。,34,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,系统形式的生成矩阵,(n,k)码的任何生成矩阵都可以通过行运算(以及列置换)简化成“系统形式” 。 G = Ik P = Ik是kk单位矩阵,P是k(n-k)矩阵。,35,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,生成的码字C,前k位由单位矩阵Ik决定,等于把信息组m原封不动搬到
18、码字的前k位; 其余的n-k位叫冗余位或一致校验位,是前k个信息位的线性组合。 这样生成的(n,k)码叫做系统码。 若生成矩阵G不具备系统形式,则生成的码叫做非系统码。 系统化不改变码集,只是改变了映射规则。,36,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,系统码,若通过行运算和列置换能将两个生成矩阵G互等,则称这两个G等效。 非系统码的G可通过运算转变为系统码的G。 等效的两个G生成的两个(n,k)线性码也是等效的。 因此,每个(n,k)线性码都可以和一个系统的(n,k)线性码等效。,37,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,空间构成,n维n重空
19、间有相互正交的n个基底 选择k个基底构成码空间C 选择另外的(n-k)个基底构成空间H C和H是对偶的 CHT0, GHT=0,38,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,校验矩阵,将H空间的n-k个基底排列起来可构成一个(n-k)n矩阵,称为校验矩阵H。用来校验接收到的码字是否是正确的; G是(n,k)码的生成矩阵,H是它的校验矩阵; H是(n,n-k)对偶码的生成矩阵,它的每一行是一个基底。 G则是它的校验矩阵。 GHT=0 ,H PT In-k ,二进制时,负号可省略。,39,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,例6-2 (6,3)线性分
20、组码,其生成矩阵是 G= 求: (1)计算码集,列出信息组与码字的映射关系。 (2)将该码系统化处理后,计算系统码码集并列出映射关系。 (3)计算系统码的校验矩阵H。若收码r = 100110, 检验它是否码字? (4)根据系统码生成矩阵画出编码器电原理图。,1 1 1 0 1 0 1 1 0 0 0 1 0 1 1 1 0 1 ,40,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,例6-2 码集与映射关系,信息 码字 系统码字 000 000000 000000 001 011101 001011 010 110001 010110 011 101100 011101 100
21、 111010 100111 101 100111 101100 110 001011 110001 111 010110 111010,41,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,例6-2 二元(6,3)线性分组码编码器,m0 m1 m2 输入 输出 c0 c1 c2,42,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,6.3.2 伴随式与标准阵列译码,m C=(cn-1,c1,c0) R=(rn-1,r1,r0) (n,k) 信道 定义差错图案E E(en1,e1,e0) RC (rn-1cn-1,r1c1,r0c0) 二进制码中模2加与模2减是等同
22、的,因此有 E = R C 及 R = C E,43,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,伴随式S的定义,因为CHT = 0 所以RHT(CE)HTCHTEHT= EHT 如果收码无误:必有RC即E0, 则EHT= 0 RHT = 0。 如果收码有误:即E 0, 则RHT = EHT 0。 在HT固定的前提下,RHT仅仅与差错图案E有关,而与发送码C无关。定义伴随式S S = (sn-k-1,s1,s0) = RHT = EHT,44,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,从物理意义上看,伴随式S并不反映发送的码字是什么,而只是反映信道对码字造
23、成怎样的干扰。 差错图案E是n重矢量,共有2n个可能的组合,而伴随式S是(n-k)重矢量,只有2n-k个可能的组合,因此不同的差错图案可能有相同的伴随式。 接收端收到R后,因为已知HT,可求出 SRHT;如果能知道对应的E,则通过C = RE而求得C。 RHT = S ? C = RE R S E C 只要E正确,译出的码也就是正确的。,伴随式S的意义,45,普通高等教育“十五”国家级规划教材信息论与编码 曹雪虹等编著,差错图案E的求解(1),可以通过解线性方程求解E: S = (sn-k-1,s1,s0) = EHT = (en-1, e1,e0) 得到线性方程组: sn-k-1=en-1h
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信道编码
链接地址:https://www.31doc.com/p-2567014.html