《《差错控制编码》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《差错控制编码》PPT课件.ppt（48页珍藏版）》请在金锄头文库上搜索。
1、第八章差错控制编码 2020年3月26日 2 8 1差错控制编码的基本概念 数字通信中 根据不同的目的 编码可分为信源编码和信道编码 信源编码是为了提高数字通信的有效性 以及为了使模拟信号数字化而采取的编码 信道编码是为了降低误码率 提高数字通信的可靠性而采取的编码 数字信号在传输的过程中 加性噪声 码间串扰等都会产生误码 为了提高系统的抗干扰性能 可以加大发射功率 降低接收设备本身的噪声 以及合理选择调制 解调方法等 此外 还可以采用信道编码技术 2020年3月26日 3 差错控制编码的基本思想 在发送端根据要传输的数字序列 信息码元 按一定的规律加入多余码元 使原来不相关的数字序列变为相关
2、 然后把这些多余码元和有关的信息码元一起传送 接收端根据信息码元与多余码元之间的相关规则进行检验 从而发现错误 这时 或者通过反馈信道要求对方重发有错的信息 以进行纠错 或者由接收端的译码器自动把错误纠正 这些多余码元称为校验元或监督元 它的加入不改变信息本身 也就是说 它不传送新的信息 它的作用只是使信道译码器能够检测和纠正差错 从而控制系统差错概率 提高可靠性但这是以系统的有效性为代价的 2020年3月26日 4 8 1 1差错控制方式 2020年3月26日 5 前向纠错方式 前向纠错方式记作FEC ForwordErrorCorrection 发端编码器将数字信息按一定规则附加多余码元
3、组成有纠错能力的码 发端发送能够纠正错误的码 收端译码器按预先规定的规则译码 若发现错误 确定其出错位置并进行纠正 优点 单向传输 只有正向信道 适合于只能提供单向信道的场合 一点发送多点接收的同播方式 译码延迟固定 适用于实时传输系统 缺点 编译码设备复杂 为了纠正较多的错误 需要附加的多余码元较多 因而传输效率较低 2020年3月26日 6 检错重发方式 又称自动请求重传方式 记作ARQ AutomaticRepeatRequest 发端编码器将数字信息按一定规则附加多余码元 使之具有一定的检错能力 收端译码器按一定规则对数据码元组进行错误判决 并把判决结果形成应答信号 通过反馈信道回送到
4、发端 发端根据收到的应答信号 把收端认为有错的那组数据码元再次重传 直到码元组无错为止 优点 只需要少量的多余码元就能获得极低的输出误码率 并且其成本和复杂性均比前向纠错低缺点 缺点 必须提供反向信道 不能进行同播 一点发多点收 收发端应有缓冲存储器和控制器 此外当信道干扰较大时 整个系统可能处在重传循环中 因而通信效率降低 信息传输连贯性差 不适于实时传输系统 主要在计算机通信中应用 常用的检错重发系统有三种 即停发等候重发 返回重发和选择重发 2020年3月26日 8 混合纠错方式 混合纠错方式记作HEC HybridErrorCorrection 发端发送具有自动纠错同时又具有检错能力的
5、码 收端收到码后 检查差错情况 如果错误在码的纠错能力范围以内 则自动纠错 如果超过了码的纠错能力但能检测出来 则经过反馈信道请求发端重发 这种方式具有自动纠错和检错重发的优点 可达到较低的误码率 因此 近年来得到广泛应用 在实际通信系统中 选择那种差错控制方式 要视具体情况而定 可以根据信源的性质 信息传输的特点信道干扰的种类和对误码率的要求而适当选择差错控制方式 2020年3月26日 9 8 1 2差错控制编码的分类 根据信息元和监督元的函数关系 可分为线性码和非线性码 如果函数关系是线性的 即满足一组线性方程式 则称为线性码 否则为非线性码 根据上述关系涉及的范围 可分为分组码和卷积码
6、分组码的各码元仅与本组的信息元有关 卷积码中的码元不仅与本组的信息元有关 而且还与前面若干组的信息元有关 根据码的用途 可分为检错码和纠错码 检错码以检错为目的 不一定能纠错 而纠错码以纠错为目的 一定能检错 2020年3月26日 10 8 1 3几种简单的检错码 1 奇偶监督码 设码字A an 1 an 2 a1 a0 对偶监督码有 an 1 an 2 a1 a0 0 奇监督码情况相似 只是码组中 1 的数目为奇数 即满足条件 an 1 an 2 a1 a0 1 而检错能力与偶监督码相同 2020年3月26日 11 奇偶监督码 编码方法 把信息码元分组 在每组信息码元的后面附加一位监督码元
7、使得码组中1的数目为奇数或偶数即可编码规则 码组长度n 信息位n 1特点 是一种能发现奇数个差错的分组码 n较大 即编码码组较长时 编码效率接近于1 n 1 n 信息码元比码组码元适用于检测随机的零星错码 加性白噪声造成的 2020年3月26日 12 8 1 3几种简单的检错码 2 二维奇偶监督码 6 11 行列监督码 2020年3月26日 13 二维奇偶监督码 编码方法 把码元排成方阵 按行列进行奇偶校验 分别附加一位监督码元特点 不仅可检测每行 每列 中奇数个错误 而且可通过水平监督和垂直监督来确定错码的位置纠正仅一行 一列 出现的奇数个错误通过水平监督和垂直监督的关系可以发现单行中出现的
8、偶数个错误 但不能发现构成矩形的4个错误码元适用于突发差错 由突发干扰 突发脉冲 如 闪电 电火花等 在短时间内错码成串出现 在某一行中出现多个错码 2020年3月26日 14 8 1 3几种简单的检错码 3 重复码在每位信息码元之后 用简单重复多次的方法编码 例 重复两次时 用111传输1码 用000传输0码编码方法 每位信息码元简单重复多次 收端译码采用多数表决法 例 重复2次特点 纠正1个错 检出2个错 2020年3月26日 15 8 1 3几种简单的检错码 4 恒比码 码字中1的数目与0的数目保持恒定比例的码称为恒比码 这种码在检测时 只要计算接收码元中1的数目是否正确 就知道有无错误
9、 2020年3月26日 16 恒比码 例 5中取3恒比码 用于电报电码每个码组长度为5 共有25 32种不同的码组 其中有3个1的码组为可用码组 共有10种 表示10个阿拉伯数字 用它拼成汉字 每4阿拉伯数字组成1个汉字电码 其余的22个为禁用码组 特点 简单 除了1错为0与0错为1成对出现 对换性 差错不能检测外 其它任何奇数个或偶数个错码都可以被检测出来 只适用于传输种类较少且有固定代码的字符 而不适用于表示由信源来的二进制随机 数字序列 2020年3月26日 17 8 1 3几种简单的检错码 4 ISBN国际统一图书编号例ISBN0 471 02977 7 2020年3月26日 18 8
10、 1 4检错和纠错的基本原理 如用三位二进制编码来代表八个字母000A100E001B101F010C110G011D111H不管哪一位发生错误 都会使传输字母错误如用三位字母传四个字母000A011B101C110D发生一位错误 准用码字将变成禁用码字 接收端就能知道出错 但是不能纠错 如果进一步将许用码组限制为两种000A111B 检错和纠错能力是用信息量的冗余度来换取的 2020年3月26日 19 检错和纠错的基本原理 检错和纠错能力是用信息量的冗余度换取的 与码组之间的差别有关 不同的编码方法和形式 检错和纠错能力不同 例 n 3 共有8种组合 都用于传输消息 在传输过程中若发生一个误
11、码 则一种码组就会错误地变成另一种码组 但接收端却不能发现错误 因为任何一个码组都是许用码组 在差错控制编码中 定义码组中非零码元的数目为码字的汉明 Hamming 重量 简称码重 例如 码字10110 码重w 3 定义两个等长码组之间相应位取值不同的数目为这两个码组的汉明 Hamming 距离 简称码距 例如11000与10011之间的距离d 3 码组集中任意两个码字之间距离的最小值称为码的最小距离 用dmin表示 最小码距是码的一个重要参数 它是衡量码检错 纠错能力的依据 2020年3月26日 21 最小码距与检错纠错能力的关系 码组内的距离反映了码组之间的差别 最小距离越大 说明两个码组
12、间的最小差别越大 或者说其中一个码组错为另一个码组的可能性就越小 那么其检错和纠错能力也就越强 因此可以说最小码距是衡量一种纠错编码的检错 纠错能力大小的标准 码的最小距离直接关系着码的检错和纠错能力 任一 n k 分组码 若要在码字内 1 检测e个随机错误 则要求码的最小距离dmin e 1 2 纠正t个随机错误 则要求码的最小距离dmin 2t 1 3 纠正t个同时检测e t 个随机错误 则要求码的最小距离dmin t e 1 t 1 e A B 2020年3月26日 23 用差错控制编码提高通信系统的可靠性 是以降低有效性为代价换来的 我们定义编码效率R来衡量有效性 Rc k n 其中
13、k是信息元的个数 n为码长 对纠错码的基本要求是 检错和纠错能力尽量强 编码效率尽量高 编码规律尽量简单 实际中要根据具体指标要求 保证有一定纠 检错能力和编码效率 并且易于实现 编码效率 2020年3月26日 24 8 2线性分组码 线性分组码的构成将信息序列划分为等长 k位 的序列段共有2k个不同的序列段 在每一信息段之后 附加m位监督元 构成长度n k m的分组码 n k 监督元与信息码元为线性关系 2020年3月26日 25 例 信息元长度k 3共有2k 8个不同的信息组每组信息组加4个监督元 构成一个长度为7的 7 3 线性分组码 设 每组信息元为C1C2C3监督元为C4C5C6C7
14、根据下列线性方程组求监督元C4 C1 C3C5 C1 C2 C3C6 C1 C2C7 C2 C3 2020年3月26日 26 例 7 3 码有8个信息组 信息组按上方程组求得每个信息组的4个监督元 得到 7 3 码的所有8个码字信息组码元00000000000010011101010010011101101110101001001110101101001111011010011111110100重要特性 线性码有封闭性 2020年3月26日 27 8 2线性分组码 设分组码由n位码组构成 记为c1 c2 cn 信息码组由k位码组成 记为d1 d2 dk 则该分组码记为 n k 码 码组和信息码
15、组可用行矩阵C和D表示若为线性分组码 C中的n个元素都是由D中的k个元素经线性组合形成的 可用一联立方程表示为 将码组C写成矩阵形式 矩阵G称为生成矩阵 它是一个k n的矩阵 2020年3月26日 29 生成矩阵G 2020年3月26日 30 生成矩阵G Ik单位矩阵 k行k列 kxk阶 P矩阵 k行m列 kxm阶 编码前k位 编码后有n位 2n 2k 选择P矩阵 可得到有较强检错纠错能力 实现方法尽可能简单 编码效率又高的线性分组码由于线性码具有封闭性 故任何二个码组之间的距离必须与某一个码组中 1 的个数相等 而码组中非零码元的数目 1 的个数为码组的重量 码重 所以线性码任意二个码字之间
16、的距离必须等于码中某一个码字的重量 线性码最小码距正好等于非零码的最小码重估算线性码的差错控制能力 求最小码距 最小码重 2020年3月26日 31 例 已知 6 3 码的生成距阵 求 编码码组 2020年3月26日 32 监督矩阵H 校验矩阵或监督矩阵H mxn阶PT m行k列k m n列 2020年3月26日 33 伴随式 校正子 S 设发送码组C cn 1 cn 2 c1 c0 在传输过程中可能发生误码 接收码组R rn 1 rn 2 r1 r0 则收发码组之差定义为错误图样E 也称为误差矢量 即 E R C en 1 en 2 e1 e0 且 当ri ci 当ri ci 令S RHT 称为伴随式或校正子S RHT CHT EHT EHTS只与错误图形有关 与发送的码组C无关HT nxm阶 E 1xn阶 S 1xm阶 S s1s2 sm 解得误差矢量E 求得纠错后的码组C R E 2020年3月26日 34 检错与纠错 检错 当码组出现错误S为非零矢量纠错 S RHT CHT EHT EHTS与E之间有着确定的线性关系 由H矩阵确定 也就是与G P 矩阵有关 S s1s2 sm
