《信息论与编码-第6章课件》由会员分享，可在线阅读，更多相关《信息论与编码-第6章课件（125页珍藏版）》请在金锄头文库上搜索。
1、第第6 6章章 信道编码信道编码 信道编码信道编码是以信息在信道上的正确传输为目是以信息在信道上的正确传输为目 标的编码，可分为两个层次上的问题：标的编码，可分为两个层次上的问题：n n如何正确接收载有信息的信号如何正确接收载有信息的信号 线路编码线路编码(Line Coding)(Line Coding)n n如何避免少量差错信号对信息内容的影响如何避免少量差错信号对信息内容的影响 纠错编码纠错编码(Error Correction Coding)(Error Correction Coding)本章内容本章内容n有扰离散信道的编码定理 n纠错编译码的基本原理与分析方法n线性分组码 n卷积码
2、n编码与调制的结合TCM码n运用级联、分集与信息迭代概念的纠错码6.16.1 有扰离散信道的编码定理有扰离散信道的编码定理 6.1.1 差错和差错控制系统分类 6.1.2 矢量空间与码空间 6.1.3 随机编码 6.1.4 信道编码定理 差错类型差错类型n n差错符号差错符号：由符号发生差错引起，也叫信 号差错，信号差错概率用误码元率表示n n差错比特差错比特：由信息比特发生差错引起，也 叫信息差错，信息差错概率用误比特率表 示n对于二进制传输系统，符号差错等效于比 特差错；n对于多进制系统，一个符号差错到底对应 多少比特差错却难以确定。因为一个符号 由多个比特组成。差错图样（差错图样（Err
3、or PatternError Pattern） n定量地描述信号的差错，收、发码之“差” ： 差错图样E发码C 收码R （模M） n例：8进制(M=8)码元， 若发码 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）n二进制码：E=C R 或 C = R E ，差错图样中 的“”既是符号差错也是比特差错，差错的个数 叫汉明距离 差错图样类型差错图样类型 n n随机差错随机差错：若差错图样上各码位的取值既与前后 位置无关又与时间无关，即差错始终以相等的概 率独立发生于各码字、各码元、各比特；双 绞线、同轴
4、电缆、光纤、微波、卫星、深空通信 等n n突发差错突发差错：前后相关、成堆出现。突发差错总是 以差错码元开头、以差错码元结尾，头尾之间并 不是每个码元都错，而是码元差错概率超过了某 个额定值。多由突发噪声引起，雷电、电火花、 时变信道的衰落、移动通信中的多径噪声等纠错码分类纠错码分类 n n从功能角度从功能角度：检错码 、纠错码 n n对信息序列的处理方法对信息序列的处理方法：分组码、卷积码n n码元与原始信息位的关系码元与原始信息位的关系：线性码、非线 性码 n n差错类型差错类型：纠随机差错码、纠突发差错码 、介于中间的纠随机/突发差错码。n n构码理论构码理论：代数码（近世代数）、几何码
5、 （投影几何）、算术码（数论、高等算数 ）、组合码（排列组合、数论）等 差错控制系统分类差错控制系统分类 n n前向纠错（前向纠错（FECFEC）：发端信息经纠错编码后 传送，收端通过纠错译码自动纠正传递过 程中的差错无需反向信道，时延小，但 设备较复杂 n n反馈重发（反馈重发（ARQARQ）：收端通过检测接收码是 否符合编码规律来判断，如判定码组有错 ，则通过反向信道通知发端重发该码 n n混合纠错（混合纠错（HECHEC）：前向纠错和反馈重发的 结合，发端发送的码兼有检错和纠错两种 能力 移动通信和卫星通信得到应用6.1.2 6.1.2 矢量空间与码空间矢量空间与码空间 n(n,k)分组
6、码（Block Codes): 把信息码流分割成 k 位 符号一组（称为信息组或信息码组），将其编成 n (nk)个码元组成的码字，所有的码字构成码组（ 码表）n码字可以被看成是一个 n 重矢量，n 个码元对应矢 量的 n 个元素n这样，可以从矢量空间的角度来分析和理解分组码编码 器m=(m0, m1, , mk-1 )k位c=(c0, c1, , cn-1 )n位6.1.2 6.1.2 矢量空间与码空间矢量空间与码空间 nF 表示码元所在的数域，对于二进制码，F 代表二元 域0,1n设 n 重有序元素的集合V= Vi , n若满足条件：nV 中矢量元素在矢量加运算下构成加群；nV 中矢量元素
7、与数域 F 元素的标乘封闭在 V 中；n分配律、结合律成立，则称集合 V 是数域 F 上的 n 重矢量空间。矢量空间中矢量的关系矢量空间中矢量的关系 对于域 F 上的若干矢量n n线性组合线性组合：n n线性相关线性相关：其中任一矢量可表示为其它矢量的线性组合n n线性无关（线性独立）线性无关（线性独立）：一组矢量中的任意一个 都不可能用其它矢量的线性组合来代替。矢量空间与基底矢量空间与基底n一组线性无关的矢量 ，线性组合 的集合就构成了一个矢量空间 V，这组矢量 就是这个矢量空间的基底。nn 维矢量空间应包含 n 个基底，可以说：n 个基底“张成” n 维矢量空间。n基底不是唯一的，例：线性
8、无关的两个矢 量（1,0）和（0,1）以及（-1,0）和（0,-1） 可张成同一个二维空间。二元域二元域GFGF(2)(2)上三重矢量空间上三重矢量空间 n以（100）为基底可张成一维三重子空间V1，含21 =2 个 元素，即n以(010),(100)为基底可张成二维三重子空间V2，含 22 =4 个元素，即n以(100),(010),(001)为基底可张成三维三重空间V,含 23 =8 个元素，V1和V2都是V 的子空间。1001000001100111011110100010010103维3重空间(8个)1001000001100100102维3重空间(4个)000 1001001维3重空
9、间(2个)矢量空间矢量空间n每个矢量空间或子空间中必然包含零矢量n两个矢量正交：V1V2 0 n两个矢量空间正交：某矢量空间中的任意元 素与另一矢量空间中的任意元素正交 n正交的两个子空间V1、V2互为对偶空间 (Dual Space)，其中一个空间是另一个空间的零空 间（Null Space，也称零化空间）。n构成矢量的元素的个数称为“重” 数，张成矢 量空间的基底的个数称为“维”数。 码空间码空间消息k长 (n , k) 码字n长 qk 种 分组编码器 qn种k维k重矢量 n维n重矢量 通常qn qk，分组编码的任务是要在 n 维 n 重矢量空间的 qn 种可能组合中选择 其中的 qk 个
10、构成一个码空间，其元素（ 码矢量或码矢）就是许用码字的码集。 分组编码的任务分组编码的任务 n选择一个 k 维 n重子空间作为码空间。n确定由 k 维 k 重信息空间到维 n 重码空间 的映射方法。码空间的不同选择方法，以及信息组与 码组的不同映射算法，就构成了不同的分 组码。6.1.36.1.3随机编码随机编码n运用概率统计方法在特定信道条件下对编 码信号的性能作出统计分析，求出差错概 率的上下限边界，其中最优码所能达到的 差错概率上界称作随机码界。n用这种方法不能得知最优码是如何具体编 出来的，却能得知最优码可以好到什么程 度，并进而推导出有扰离散信道的编码定 理，对指导编码技术具有特别重
11、要的理论 价值。 6.1.36.1.3随机编码随机编码n在(N,K)分组编码器中，K重消息组m逐个、随机地对应N 维矢量空间上的任一点（共有qN个点）n一个消息组有qN种对应选择 ，两个消息组有qN qN种对应 选择， qK个消息组选定的码集有 种 n令M= qK，则qK个消息组随机选定的码集有qNM种 n第m个码集(记作cm )被随机选中的概率是n设与这种选择相对应的条件差错概率是 Pe(cm)n全部码集的平均差错概率是6.1.36.1.3随机编码随机编码n必定存在某些码集n某些码集n若 ，就必然存在一批码集n即差错概率趋于零的好码一定存在 6.1.36.1.3随机编码随机编码n码集点数 M
12、=qK占 N 维矢量空间总点数 qN 的比例 是 F =qK / qN = q-(N-K) n当 K 和 N 的差值拉大即冗余的空间点数增加时， 平均而言码字的分布将变得稀疏，码字间的平均 距离将变大，平均差错概率将变小。 n当 F0 即 (N-K) 时，能否让平均差错概率 ？ nGallager在1965年推导了 的上边界，并证明这 个上边界是按指数规律收敛的。 nE(R) 称为可靠性函数，也叫误差指数 n码率：R =( lbM) / N nM 是可能的信息组合数，M=qKnN 是每码字的码元数，nR 表示每码元携带的信息量，单位是每符号比 特（bit / symbol） 6.1.46.1.
13、4信道编码定理信道编码定理nR在0,R0区间时E(R)R 曲线是斜率为-1(-45)的 直线，E(R)反比于R； 而当R=C时E(R)=0即可 靠性为零。 6.1.46.1.4信道编码定理信道编码定理E(R)C R0 R0 -45 E(R)和R的关系曲线n n正定理正定理：只要传信率 R 小于信道容量 C， 总存在一种信道码（及解码器），可以以 所要求的任意小的差错概率实现可靠的通 信。n n逆定理逆定理：信道容量 C 是可靠通信系统传信 率 R 的上边界，如果 R C ，就不可能有任 何一种编码能使差错概率任意小。 6.1.46.1.4信道编码定理信道编码定理6.2 6.2 纠错编译码的基本
14、原理与分析方法纠错编译码的基本原理与分析方法6.2.1 纠错编码的基本思路 6.2.2 译码方法最优译码与最大似然译码 6.2.16.2.1纠错编码的基本思路纠错编码的基本思路nR不变，信道容量大者 其可靠性函数E(R)也 大；nC不变，码率减小时其 可靠性函数E(R)增大 E(R)R 0 R1 p(1-p)n-1 p2(1-p)n-2 pn出错越少的情况，发生概率越大，E的重量越轻 ，所以该译码方法实际上体现了最小距离译码准则 ，即最大似然译码。标准阵列译码表标准阵列译码表 n上述的概率译码，如每接收一个码R就要 解一次线性方程，那就太麻烦了。n好在伴随式S的数目是有限的2n-k个，如果 n
15、-k不太大，我们可以预先把不同S下的方 程组解出来，把各种情况下的最大概率译 码输出列成一个码表。n这样，在实时译码时就不必再去解方程， 而只要象查字典那样查一下码表就可以了 。这样构造的表格叫做标准阵列译码表。 n表中所列码字是接收到的码序列R；n将没有任何差错时的收码R放在第一行，收码等于发码 R=C(CCi,i =0,1,2k-1), 差错图案为全零E0=(0,00)，伴随式 为全零S0=(0,00)。由于有2k个码字，码表有2k列。n在第2到第n+1的n行中差错图案的所有重量为1 (共n个)。n如果(1+ n)C，就不可能有任何一种编码能使 差错概率任意小。 差错控制的途径差错控制的途径 n从公式 n增大码长Nn增大可靠性函数E(R)：加大信道容量C减小码率(传信率)R。n从概念上n利用冗余度（增强相关性）n噪声均化(随机化) 最优译码与最大似然译码最优译码与最大似然译码 n最佳译码 Max P(ci /r)，性能优，实 现难n最大似然译码 Max P(r / ci)，性能次 优，实现容易n最佳译码等同最大似然译码：n码集的码字以相同概率发送n接收码等概分布线性分组码线性分组码 n线性分组码基本概念 n码元、码字、码集n重量、
