第8讲-差错控制编码-NEW..ppt

数字通信原理 PrinciplesofDigitalCommunicationF 中南大学信息科学与工程学院SchoolofInformationScienceandEngineeringCentralSouthUniversity主讲 李敏联系方式 limin csu limin 课件邮箱 txyl csu 第七讲差错控制编码 7 1基本概念7 2纠错编码原理7 3常用的简单编码7 4线性分组码7 5循环码 重点和难点 差错控制的目的和基本原理 差错控制方式及其特点 码重 汉明距离 最小距离的概念和确定 纠错和检错能力分析编码效率汉明码和CRC码 第七讲差错控制编码 7 1基本概念 产生误码的原因 系统特性的不理想 乘性噪声 数字信号波形失真 接收端误判 形成误码信道噪声干扰 加性噪声 数字信号变形 误码 信道分类 按加性噪声引起的错码分布规律 随机信道 白色高斯噪声 误码相互独立 突发信道 存在突发脉冲干扰 误码在短时间内成串出现 并前后有关 混合信道 随机信道 突发信道 7 1基本概念 差错类型 随机差错 独立差错 差错的出现随机 且差错之间是统计独立的由随机噪声引起突发差错 差错在短时间成串出现 而在其间又存在较长的无差错区间 且差错之间相关因脉冲噪声 也可能是由存储系统中磁带的缺陷或读写头接触不良引起 7 1基本概念 提高系统可靠性的途径 加大发送功率 即提高信噪比 虽简单有效 但功率不可无限增加 实际受到一定的限制 匹配滤波接收 可抑制白色噪声 使误码率下降 合理的调制解调方式PePSK PeDPSK PeFSK相干 ASK PeASK PSK非相干差错控制编码 正交编码或纠错编码正交编码 选择抗干扰能力强的信号集合 使受干扰后不容易混淆 常和调制方式结合在一起 纠错编码 使信号受干扰而出错后在译码判决时能自动纠正错误 7 1基本概念 差错控制方式 前向纠错 FEC forwarderrorcorrection 检错重发 ARQ automaticrepeatrequest 混合纠错 HEC hybriderrorcorrection 差错控制编码的基本思想 在发送端被传输的信码序列上附加一些监督码元 冗余码元 使所传输的码字中前后码元产生一定的相关性 具有一定的监督关系 接收端利用这种监督关系来检测 纠正错误 理论依据 Shannon信道编码定理 Shannon信道编码定理 对于一给定的有干扰信道 若其信道容量为C 只要发送端以低于C的速率R发送信息 则一定存在一种编码方法 使编码错误概率P随着码长n的增加 按指数下降到任意小的值 7 1基本概念 按监督码元和信息码元关系不同 线性码 LinearCodes 非线性码 non LinearCodes 按对信息元处理的方法不同 分组码 BlockCodes 卷积码 ConvolutionalCodes 按纠错类型分 纠随机错误的码 纠突发错误的码按功能分 检错码 纠错码 纠删码按码元取值不同 二进制码 多进制码按编码的数字方式不同 代数码 几何码 算术码按编码后是否保持原有形式 系统码 非系统码按码字结构特点 循环码 非循环码 差错控制编码分类 7 2纠错编码原理 检错和纠错 检错 知道在若干码元中有错码 但不一定知道错码的准确位置 纠错 能确定错码的位置 并对其进行纠正 差错控制编码的基本思想 发送端按照某种规则在信息序列上附加监督码元 接收端则按照同一规则检查两者间关系 以牺牲通信的有效性 信息传输速率 来提高可靠性码的检错和纠错能力是用信息量的冗余来换取的 一般说来 添加的冗余越多 码的检错 纠错能力越强 但信道的传输效率下降也越多 举例说明 假如要传送晴天 雨天两个消息 编码一 消息A 0 消息B 1 若传输中产生错码 0 1或1 0 收端无法发现 该编码无检错纠错能力 编码二消息A 00 消息B 11 若传输中产生一位错码 则变成 01 或 10 收端判决为有错 但无法确定错码位置 不能纠正 该编码具有检出一位错码的能力 7 2纠错编码原理 举例说明 假如要传送晴天 雨天两个消息 编码三消息A 000 消息B 111 传输中产生一位即使两位错码 收端都能判决传输有错 该编码具有检出两位错码的能力 在产生一位错码情况下 收端可根据 大数 法则进行正确判决 能够纠正这一位错码 该编码具有纠正一位错码的能力 结论增加冗余 可提高检纠错能力 增加冗余 会降低传输的信息量 编码效率降低 7 2纠错编码原理 7 2纠错编码原理 几个基本概念许用码 用于传输信息的码组 禁用码 在传输信息中不可能出现的码组 监督位 增加的不携带传输信息的 但具有一定约束的码位 分组码 将信息码分组 并为每组信息码附加若干监督码的编码 n k r n为实际传送的码长 k是信息码长 r是监督码长 码距d 接收码Cr与发送码CL之间不同的码元个数的数目 码重W 码字中 1 的个数 最小码距d0 一个码型中任何两个码字之间的最小距离 又称为汉明距离 最小码重W0 一个码型中任意码字的码重的最小值 7 2纠错编码原理 码距与检 纠错能力的关系 最小码距与检错能力的关系一个码能检测e个错码 则要求其最小码距d0 e 1即 若最小码距为d0 则最多能检测d0 1个错码 最小码距和纠错能力的关系一个码能纠正t个错码 则要求其最小码距d0 2t 1即 若最小码距为d0 则最多能纠正 d0 1 2个错码 最小码距和同时检纠错能力的关系一个码能纠正t个错码 同时能检测e个错码 则要求其最小码距d0 e t 1 e t 7 2纠错编码原理 差错控制编码的效果假设随机信道中发送 0 码与发送 1 码传错概率相等为Pe 且Pe 1 则在码长为n的码组中发生r个错误的概率为 Pn r CnrPer 1 Pe n r n r n r Per当码长n 7 Pe 10 3时 则有P7 1 7Pe 7 10 3P7 2 21Pe2 2 1 10 5P7 3 35Pe3 3 5 10 8 7 2纠错编码原理 编码效率指一个码组中信息位所占比重 用 表示 k n 其中k为信息码元的数目 n为码长 可见 若加入的监督位越多 纠错能力越强 编码效率越低 纠错编码的任务是 根据不同干扰特性设计出纠检错能力最强 效率高的纠错码 且译码设备不太复杂 7 3常用的简单编码 奇偶校验码 奇偶监督码 奇监督码 使码字加上1位监督位C0后 码字中 1 的个数为奇数个 偶监督码 使码字加上1为监督位C0后 码字中 1 的个数为偶数个 只能检测出奇数个错误 不能纠错应用 以随机错误为主的计算机通信系统 难于对付突发错误最小码距dmin 2 7 3常用的简单编码 水平奇偶校验码 编码规则 1 对需要传输的数据 进行奇偶校验编码 2 将经过奇偶监督编码的码元序列按行排成方阵 每行为一组奇偶校验编码 3 发送时按照列的顺序传输 4 接收端仍将码元排成发送时的方阵形式 然后按行进行奇偶校验 例 偶校验 0100110001传输时为 0110000011 7 3常用的简单编码 二维奇偶校验码 水平垂直奇偶监督码 将奇偶校验码的若干码组排列成矩阵每一码组写成一行m个码组m行m个监督位构成了一监督位列按列的方向增加第二维校验位n个监督位构成了一监督位行 检错能力 检出所有行和列中的奇数个差错能检出大多数偶数个差错能检出突发长度不大于方阵行数或列数的突发错误 适用于检测突发错误 将使误码减少到原来的1 1 7 3常用的简单编码 二维奇偶校验码 水平垂直奇偶监督码 7 3常用的简单编码 等比码 每个码组中含 1 和 0 的个数的比例恒定 又称等重码 恒比码 定1码 能检测出所有1位错和奇数个错误 并能部分检测出偶数个错误 成对交换错则检测不出 简单 适应于对字母或符号进行编码 常用于电传机传输汉字 以及其他产生固定字符的键盘设备中 例 电传机传输数字时广泛采用的五单位数字保护电码 是一种五中取三的恒比码 共有 种组合 代表10个阿拉伯数字 7 3常用的简单编码 正反码 监督位数与信息位数目相同 且两者相同或相反 取决于信息序列中 1 的个数 编码规则当信息位中有奇数个 1 时 监督位是信息位的简单重复 当信息位中有偶数个 1 时 监督位是信息位的反码 接收端解码先将码组中信息位与监督位按位模2加 得到合成码组 产生校验码组 码组中信息码元有奇数个 1 则校验码组 合成码组 否则校验码组 合成码组的反码按照校验码组中 1 的个数进行检错及纠错 7 3常用的简单编码 正反码 7 3常用的简单编码 正反码 举例 电报通信中常用5单位电码来构造正反码编码若为11001 则码字为1100111001若为10001 则码字为1000101110假设发送码组为1100111001若接收码组为1100111001 判决为无错传输若接收码组为1000111001 合成码组01000 先将码组中信息位与监督位按位模2加 得到合成码组 因码组中信息码元有偶数个 1 则校验码组为10111 说明信息码元中第二位错码 给以纠正若接收码组为1100101001 合成码组10000 因码组中信息码元有奇数个 1 则校验码组为10000 说明监督码元中第一位错码若接收码组为1001111001 合成码组01010 因码组中信息码元有奇数个 1 则校验码组为01010 说明错码多于1个码长为10的正反码能够纠正1位差错 并能检测所有2位及以下的错码 7 4线性分组码 系统码 信息码元编码后 信息码元本身不变 而只在信息码元后加入监督码元 即前半部分为不变的信息码元 后半部分为监督码元的码型 线性码 监督码元和信息码元成线性关系的码型 分组码 监督码元只和本身信息码元有关的码型 线性分组码 利用代数关系 将信息序列划分为等长的k位序列段 在每一信息段后附加r个监督码元 并使监督码元和信息码元成线性关系 这样构成的码型就叫 汉明码 纠单个错的线性分组码 循环码 在严谨的代数基础上构造的 纠错能力强的解编码设备并不复杂的线性分组码 卷积码 监督码元不仅与本身信息码元有关 且跟其它码元有关的一种码型 基本概念 7 4线性分组码 具有封闭性 即任意两许用码组之和仍为一许用码组 码距的最小值等于最小码重 除全 0 码组以外 线性分组码的表示 n k 码长为n 信息码长为k 监督码长r n k 一致校验矩阵 H ParitycheckMatrix 用于说明监督码元与信息码元监督关系的矩阵 线性分组码的特点 举例 7 4 码 设码元表示为 C C6C5C4C3C2C1C0 由 7 4 码可知 n 7 k 4 r 3 假设 中南大学通信原理 7 4线性分组码 写成矩阵形式 一致校验矩阵 H 中南大学通信原理 7 4线性分组码 举例 7 4 码 n k 码的所有码字均按H所确定的规则求出H矩阵的每一行代表一个线性方程的系数 它表示求一个校验元的线性方程 H矩阵每一列代表此码元与哪几个校验方程有关 k r n列 一致校验矩阵 H 的特性 H 是r n阶矩阵 r为监督码元个数 n为码长 H P Ir P是r k阶阵 Ir为r个监督码系数构成的r r阶单位矩阵 此时称 H 为典型形式监督矩阵 各行线性无关 若接收到码字R与 H 的转置乘积为 0 则说明接收到的码字R是正确的 即R H T 0 则R正确 最小码距d0 n k 1 r 1 最小码距的上界 中南大学通信原理 7 4线性分组码 生成矩阵 G 在给定信息位的条件下 确定码字的矩阵 举例 7 4 码 生成矩阵 G 中南大学通信原理 7 4线性分组码 k r n列 生成矩阵 G 的特性 G 是k n阶矩阵 k为信息码元个数 n为码长 G Ik Q Q是r k阶阵 Ir为k个信息码系数构成的k k阶单位矩阵 此时称 G 为典型形式生成矩阵 各行线性无关 G Ik Q H P Ir 所以 Q P T P Q T即 G 和 H 可相互确定 且都唯一确定码字 对偶码 一码型A的 H 是另一码型B的 G 或A码型的 G 是B码型的 H 则称A是B的对偶码 线性分组码的封闭性 即任意n个码字之模2和仍是线性分组码内的许用码字 线性分组码的最小距离等于最小码重d0 Wmin 中南大学通信原理 7 4线性分组码 例题 6 3 码 当 R H T 0 R C 说明正确接收 若传输过程发生误码 设收发码组之差为 E 则 E En 1En 2 E0 R C Ei 1第i位有错 即Ri不等于Ci0第i位没有错 即Ri Ci E 为错误图样 即发送数据序列与接收序列对应码位的模 和 R C E 模2 S R H T E H T 称 S 为校正子或伴随式或校验子 为1 r阶行矩阵 它最多能指出2r 1种错误 中南大学通信原理 7 4线性分组码 线性分组码的译码和校正子设发送的码字为 C Cn 1Cn 2 C0 接收的码字为 R Rn 1Rn 2 R0 则 例题 6 3 码 汉明码能纠正单个错误的高效率线性分组码特点 n k 汉明码 K位信息 监督位有r位 为能指出所有单错位置和无错情况 n k和r间应满足下述关系 取等号 码长n 2r 1 k 2r 1 r最小码距为3 纠错能力为1 编码效率较高 k n 2r 1 r 2r 1 1 r 2r 1 当n增大 r增大 但 也增加 汉明码是一种完备码 能纠正一个错码 能检测两个错码 中南大学通信原理 7 4线性分组码 汉明码 中南大学通信原理 7 4线性分组码 总结 中南大学通信原理 7 4线性分组码 码多项式码长为n的码组中的各码元当作n 1次多项式的系数若码组A an 1 an 2 a1 a0 则其相应的码多项式为 A x an 1xn 1 an 1xn 1 a1x a0如码组 1100101 对应的码多项式可表示为A7 x 1 x6 1 x5 0 x4 0 x3 1 x2 0 x 1 x6 x5 x2 1码多项式与码组的关系 本质上是一回事 仅是表示方法的不同而已 中南大学通信原理 7 5循环码 循环码是一种系统分组码 前k位是信息码 后r位是监督码 不仅具有封闭性 还具有循环性 即一许用码组经循环移位后得到另一个许用码组 中南大学通信原理 7 5循环码 中南大学通信原理 7 5循环码 多项式的模运算示例 定理1 若c x 是n长循环码中的一个码多项式 则xic x 按模xn 1运算的余式必为循环码中的另一个码多项式 即若xi c x ci x 模xn 1 则ci x 也是一许用码组 且为c x 码组向左循环移位i次的结果 中南大学通信原理 7 5循环码 设C cn 1 cn 2 c0 是一个循环码组 则可将之表示为 码组C向左循环移位1次 类似地 码组C经i次移位后 得到的新的码组ci x xi c x ci x 中南大学通信原理 7 5循环码 生成多项式g x 和生成矩阵 G g x 是循环码中前k 1位为0码字的码多项式 即为 n k 阶码多项式 中南大学通信原理 7 5循环码 生成多项式g x 和生成矩阵 G 中南大学通信原理 7 5循环码 生成多项式g x 和生成矩阵 G 定理2 在循环码中 n k 阶码多项式有且仅有一个 定理3 循环码中 所有码多项式都能被g x 整除 推论 次数不大于k 1次的任何多项式与g x 的乘积都是码多项式 定理4 循环码的生成多项式g x 是xn 1的一个因式 中南大学通信原理 7 5循环码 生成多项式g x 和生成矩阵 G 根据循环性 xg x x2g x xk 1g x 都是许用码组 连同g x 共k个许用码组 构成码的生成矩阵G x 注 该生成矩阵并不一定是典型形式的 但可通过线性变换变换成典型的生成矩阵 xi g x i k 1 相当于对g x 向左循环移位i次 中南大学通信原理 7 5循环码 循环码的编码过程 设信息码多项式为m x 1 确定循环码的生成多项式g x 2 信息码元左移r位 得M x xn km x 3 M x 除以g x 求余数R x 4 T x xn km x R x 中南大学通信原理 7 5循环码 典型生成矩阵 G 中南大学通信原理 7 5循环码 由生成矩阵得到许用码字 中南大学通信原理 7 5循环码 由许用码字求生成多项式 中南大学通信原理 7 5循环码 循环码的监督多项式 中南大学通信原理 7 5循环码 循环码的监督矩阵 中南大学通信原理 7 5循环码 循环码的监督矩阵 中南大学通信原理 7 5循环码 循环码的译码过程 循环码的检错能力 能检出全部的单个错误 对应一位错码的错码多项式E x xi 而多于一项的生成多项式g x 1 显然xi除以g x 的余数不会等于0 也即