信号与编码的第6章.ppt

信道编码 第6章 2 6 1纠错编译码的基本原理与分析方法6 2线性分组码6 3卷积码 内容 3 信源编码提高数字信号有效性将信源的模拟信号转变为数字信号降低数码率 压缩传输频带 数据压缩 信道编码提高数字通信可靠性数字信号在信道的传输过程中 由于实际信道的传输特性不理想以及存在加性噪声 在接收端往往会产生误码 编码 4 6 1纠错编译码的基本原理与分析方法 5 6 1 1差错和差错控制系统分类 差错率是衡量传输质量的重要指标之一 它有几种不同的定义 码元差错率 符号差错率指在传输的码元总数中发生差错的码元数所占的比例 平均值 简称误码率 是指信号差错概率比特差错率 比特误码率 在传输的比特总数中发生差错的比特数所占比例是指信息差错概率对二进制传输系统 符号差错等效于比特差错 对多进制系统 一个符号差错对应多少比特差错却难以确定 6 差错率 根据不同的应用场合对差错率有不同的要求 在电报传送时 允许的比特差错率约为 10 4 10 5 计算机数据传输 一般要求比特差错率小于 10 8 10 9 在遥控指令和武器系统的指令系统中 要求有更小的误比特率或码组差错率 7 差错图样 为定量地描述信号的差错 定义差错图样EE C R 模M 最常用的二进制码可当作特例来研究 其差错图样等于收码与发码的模2加 即E C R或C R E设发送的码字C1111111111接收的码字R1001001111差错的图样E0110110000差错图样中的 1 既是符号差错也是比特差错 差错的个数叫汉明距离 0 传输中无错1 传输中有错 8 差错图样 随机差错 差错是相互独立的 不相关存在这种差错的信道是无记忆信道或随机信道突发差错 指成串出现的错误 错误与错误间有相关性 一个差错往往要影响到后面一串字E 0010010000001001110000000 突发长度 4 突发长度 6 9 纠错码分类 从功能角度讲 差错码分为检错码和纠错码检错码 用于发现差错纠错码 能自动纠正差错纠错码与检错码在理论上没有本质区别 只是应用场合不同 而侧重的性能参数也不同 10 纠错码分类 按照对信息序列的处理方法 有分组码和卷积码分组码 将k个信息码元分成一组 由这k个码元按照一定规则产生r个监督码元 组成长度n k r的码字 卷积码 先将信息序列分组 不同的是编解码运算不仅与本组信息有关 而且还与前面若干组有关 k k 010101010001110 010 xxxx101xxxx010 xxxx r n r 11 纠错码分类 按照码元与原始信息位的关系 分为线性码 所有码元均是原始信息元的线性组合 编码器不带反馈回路 非线性码 码元并不都是信息元的线性组合 可能还与前面已编的码元有关 编码器可能含反馈回路 由于非线性码的分析比较困难 早期实用的纠错码多为线性码 但当今发现的很多好码恰恰是非线性码 12 纠错码分类 按照适用的差错类型 分成 纠随机差错码 用于随机差错信道 其纠错能力用码组内允许的独立差错的个数来衡量 纠突发差错码 针对突发差错而设计 其纠错能力主要用可纠突发差错的最大长度来衡量 13 差错控制系统分类 前向纠错 FEC 发送端的信道编码器将信息码组编成具有一定纠错能力的码 接收端信道译码器对接收码字进行译码 若传输中产生的差错数目在码的纠错能力之内时 译码器对差错进行定位并加以纠正 14 差错控制系统分类 自动请求重发 ARQ 发端发送检错码 收端译码器判断当前码字传输是否出错 当有错时按某种协议通过一个反向信道请求发送端重传已发送的码字 全部或部分 15 差错控制系统分类 混合纠错 HEC 是FEC与ARQ方式的结合 发端发送同时具有自动纠错和检测能力的码组 收端收到码组后 检查差错情况 如果差错在码的纠错能力以内 则自动进行纠正 如果信道干扰很严重 错误很多 超过了码的纠错能力 但能检测出来 则经反馈信道请求发端重发这组数据 信息反馈 IRQ 收端把收到的数据 原封不动地通过反馈信道送回到发端 发端比较发的数据与反馈来的数据 从而发现错误 并且把错误的消息再次传送 直到发端没有发现错误为止 16 检错与纠错原理 0 晴 1 雨若1 0 0 1 收端无法发现错误 00晴 10 01 11 00 11雨 能发现一个错误 禁用码组 插入1位监督码后具有检出1位错码的能力 但不能予以纠正 17 检错与纠错原理 000晴 010 001 111 000 111雨 晴 在只有1位错码的情况下 可以判决哪位是错码并予以纠正 可以检出2位或2位以下的错码 100 011 101 110 雨 18 检错与纠错原理 最大似然译码 将接收到的码字译码为与它差别最小的许用码字 并且认为这个许用码字就是它所对应的发送码字 从而在码字的纠错能力内实现自动纠错 纠错编码之所以具有检错 纠错能力 是因为在信息码元之外加入了监督码 监督码不载信息 只是用来监督信息码在传输中有无差错 纠错编码所提高的可靠性 是以牺牲信道利用率为代价换取的 监督码引入越多 检错 纠错能力越强 但信道的传输效率下降也越多 19 信道编码在被传输信息中附加一些冗余码 即监督码元 利用附加码元与信息码元间的约束关系加以校验 以检测和纠正错误 信源编码减少了冗余度冗余度是随机的 无规律的信道编码增加了冗余度冗余度是特定的 有规律的 故可利用其在接收端进行检错和纠错 信道编码 20 传输冗余比特必然要动用冗余的资源 时间 比如一个比特重复发几次 或一段消息重复发几遍 或根据收端的反馈重发受损信息组 频带 插入冗余比特后传输效率下降 若要保持有用信息的速率不变 方法之一是增大符号传递速率 波特率 结果就占用了更大的带宽 功率 采用多进制符号 用8进制ASK符号代替4进制ASK符号来传送2比特信息 可腾出位置另传1冗余比特 8进制ASK符号的平均功率肯定比4进制时要大 这就是动用冗余的功率资源来传输冗余比特 设备复杂度 加大码长 采用网格编码调制 是在功率 带宽受限信道中实施纠错编码的有效方法 代价是算法复杂度的提高 需动用设备资源 21 信道编码的基本思想 信道编码按一定规则给数字序列m增加一些多余的码元 使不具有规律性的信息序列m变换为具有某种规律性的数码序列C 码序列中的信息序列码元与多余码元之间是相关的 信道译码器利用这种预知的编码规则译码 检验接收到的数字序列R是否符合既定的规则 从而发现R中是否有错 或者纠正其中的差错 根据相关性来检测 发现和纠正传输过程中产生的差错就是信道编码的基本思想 22 码距与检错 纠错能力 纠错编码的检错纠错能力 要取决于码组的码距码距越大 检错 纠错能力越强 汉明距离 二个码组对应码位码元不同的个数 最小码距dmin 一个码组的集合中任意二个码组间的最小汉明距离 码重W 码组中非0的数目 23 码距与检错 纠错能力 定理 若纠错码的最小距离为dmin 可以检测出任意小于等于l dmin 1个差错 可以纠正任意小于等于个差错 可以检测出任意小于等于l同时纠正小于等于t个差错 其中l t满足 l t dmin 1t l 24 编码效率 编码效率 一个组中信息所占的比重 k 信息码元的数目n 编码组码元的总数目n k rr 监督码元的数目 25 检错码 奇偶校验码 n n 1 k 1 k 偶校验码字 26 2 偶 或奇 校验方法一个奇偶校验位p为偶校验位m0 m1 m2 mk 1 p 0 mod2 则C m0 m1 m2 mk 1 p 为一个偶校验码字 C中一定有偶数个 1 所有可能的C的全体称为一个码率为k k 1 的 k 1 k 偶校验码 确定校验位p的编码方程为p m0 m1 m2 mk 1当差错图案E中有奇数个 1 即R中有奇数个位有错时 可以通过校验方程是否为0判断有无可能传输差错 校验方程为1表明一定有奇数个差错 校验方程为0表明可能有偶数个差错 27 多个奇偶校验位一个校验位可以由信息位的部分或全部按校验方程产生 例如C是一个对阵列消息进行垂直与水平校验以及总校验的码字 其码率为 当校验位数增加时 可以检测到差错图案种类数也增加 同时码率减小 28 3 重复消息位方法n重复码 码率为1 n 仅有两个码字C0和C1 传送1比特 k 1 消息 C0 00 0 C1 11 1 n重复码可以检测出任意小于n 2个差错的错误图案BSC信道 pb 1 2 n比特传输中发生差错数目越少 概率越大 1 pb n pb 1 pb n 1 pbt 1 pb n t pbn总认为发生差错的图案是差错数目较少的图案 当接收到重复码的接收序列R中 1 的个数少于一半时 认为发送的是C0 否则认为是C1 图6 1 7所示纠1个任意差错的3重复码 29 6 1 3检错与纠错原理 30 4 等重码 定比码设计码字中的非0符号个数恒为常数 即C由全体重量恒等于m的n重向量组成 5中取3等重码可以检测出全部奇数位差错 对某些码字的传输则可以检测出部分偶数位差错 31 2 最大似然译码译码过程由图6 1 2可见 译码器接收到一个接收码字R后 按编码规则对R进行译码后输出信息码组的估值m 信息码组与码字C之间是有固定规则的 这相当于信道译码器能给出码字C的估值C 当C C时就出现了译码错误 因为只有当C C时 m m 32 最大后验概率译码准则当译码器收到某一个接收码字R后 根据最大后验概率p C R 进行译码判决 一定是译码错误概率最小 根据贝叶斯原理似然函数 p R C 33 设每个码字长为n 若接收码字R与码字C的距离为d R C 则条件概率p R C 可表示为最大化p R C 等价于最小化d R C 所以使差错概率最小的译码是使接收向量R与输出码字C 距离最小的译码