通信原理第12讲差错控制编码.ppt

第十二章差错控制编码 在信源编码的基础上 为了提高传输系统的抗干扰能力 需要在数字调制之前对数字基带信号进行某种前向纠错编码 也就是信道编码 信道编码的目的是提高通信系统纠错能力 因而也称为差错控制编码 为了在接收端获得应用的高质量图像和声音 信道编码需对信源编码后的数据流添加一些符合特定逻辑关系的附加数据 这必将使传输码率增加 信道编码一般有下列要求 1 增加尽可能少的数据率而可获得较强的检错和纠错能力 即编码效率高 抗干扰能力强 2 对数字信号有良好的透明性 也即传输通道对于传输的数字信号内容没有任何限制 3 传输信号的频谱特性与传输信道的通频带有最佳的匹配性 4 编码信号内包含有正确的数据定时信息和帧同步信息 以便接收端准确地解码 5 编码的数字信号具有适当的电平范围 6 发生误码时 误码的扩散蔓延小 其中 最主要的可概括为两点 其一 附加一些数据信息以实现最大的检错纠错能力 这就涉及到差错控制编码原理和特性 其二 数据流的频谱特性适应传输通道的通频带特性 以求信号能量经由通道传输时损失最小 因此有利于载波噪声比 载噪比 C N 高 发生误码的可能性小 解决误码从两个方面着手 1 通过合理选择码型 尽量减少传输信道发生误码的可能2 进行误码控制 既增强信道的纠错能力 差错控制编码原理 为了能判断发送的信息是否有误 可以在发送时增加必要的附加数据 又为了能纠正一定程度的错误 这需要增加更多的附加数据 这些附加数据在不发生误码的情况下 是完全多余的 但若发生误码 便可利用信息数据与附加数据之间特定的关系实现误码检知和误码纠正 换言之 为使信源代码具有检错纠错能力 应按一事实上规则在信源编码所产生数据的基础上增加一些冗余码元 又称监督码或检验码 使监督码元和信息码元之间建立一种确定的关系 发送端完成这项任务的过程就称为差错控制编码 注意 无论检错还是纠错 都有一定的差错识别范围 误码严重而超过识别范围时 将不能实现检错和纠错 甚至越纠越错 差错控制编码的方式 1 反馈重发 ARQ 自动重发请求 方式这种方式中 接收端发现误码后通过反馈信道请求发送端重发数据 因此 接收端需要有误码检测和反馈信道 优点 系统的编解码设备比较简单 纠错能力强 适合于干扰不严重的点对点通信中应用 缺点 当信道质量较差而干扰频繁发生时 经常处于重发信息状态 使信息的连续性和实时性很差 出错 2 前向纠错 FEC 方式 这种方式中 发送端发送的数据内包括信息码元以及供接收端自动发现错误和纠正误码的监督码元 优点 它不需要反馈信道 能进行单点对多点的同步通信 译码实时性较好 缺点 编译码电路稍微复杂些 由于添加的监督码元较多 从而使编码效率较低 3 混合纠错 HEC 方式 这种方式中 发送端发出的信息内包含有给出检错纠错能力的监督码元 误码量少时接收端检知后能自动纠错 误码量超过纠错能力时接收端能通过反馈信道请求发送端重发有关信息 优点 编译码电路的复杂性比FEC方式的简单 又可避免ARQ方式中信息连续性差的缺点 并且能保证较低的接收误码率 纠错码的分类 对具体的纠错码 可以从不同角度将其分类 下图所示即为纠错码的分类情况 图5 6纠错码的分类 检错码 只能检知一定的误码而不能纠错 纠错码 具备检错能力和一定的纠错能力 纠删码 能检错纠错 对超过其纠错能力的误码则将有关信息删除或采取误码隐匿措施将误码加以掩蔽 纠错码按照检错纠错功能的不同 可分为 差错控制编码的几个基本概念 1 信息码元和监督码元n k r k为信息码元 是发送端由信源编码给出的信息数据比特 在二元码情况下 总共有2k个不同的信息码组 r为监督码元 组成一组总码数为n的码组 2 许用码组和禁用码组信道编码后总码长为n的不同码组值可有2n个 其中发送的信息码组有2k个 通常称之为许用码组 其余的为禁用码组 不允许传送 3 编码效率通常 将每个码组内信息码元数k值与总码元数n值之比 k n称为信道编码的编码效率 即 k n k k r 是衡量信道编码性能的一个重要指标 可见 监督码元越多 检错纠错能力越强 但编码效率相应地降低 4 码重 码重 码字的重量 即一个码字中 1 码的个数 通常用W表示 例如 码字10011000的码重W 300000000的码重W 01001111001的码重W 6 5 码距 码距 即码元距离就是两个码组中对应码位上码元不同的个数 也称汉明距 用d表示 码距反映的是码组之间的差异程度 比如 00和01两组码的码距为d 1 011和100的码距为d 3 11000与10011之间的距离为d 3 最小码距 码集中所有码字之间码距的最小值即称为最小码距 用表示 例如 若码集包含的码字有10010 00011 和11000 求最小码距 各码字两两之间的码距分别如下 10010和00011之间 d 210010和11000之间 d 200011和11000之间 d 4因此该码集的最小码距为2 最小码距是衡量码检错 纠错能力的依据 6 d0的大小直接关系着编码的检 纠错能力 为检测e个错码 要求d0 e 1为纠正t个错码 要求d0 2t 1为纠正t个错码 同时检测e个错码 要求d0 e t 1 B d0 B A 1 2 B B 3 4 5 d0 例 1 如果A和B为1个比特 d0 1 则无法检错和纠错 2 如果A和B各增加1个监督码元 组成 2 1 码组 便具有检错能力 如将00和11作为许用码组 01和10作为禁用码组 这时d0 2 码组的检错能力e 1 而纠错能力为0 3 如果再增加1个监督码元 就可实现纠错能力 线性分组码 1 奇偶校验码 它是一种最简单的线性分组检错码 方法 是先将信源编码后的信息数据流分成等长码组 然后在每一信息码组之后加入1位监督码元作为奇偶校验位 使得码组总码长的码重为奇数 奇校验编码 或偶数 偶校验编码 它可以检知奇数个误码 而不能发现偶数个误码 而且没有纠错能力 一般地 若有r个监督码元 就有r个监督方程和r个相应的校验子 可给出2r种状态 对于一位误码来说 非全0的2r 1种状态可指明2r 1个误码位置 线性分组码具有如下性质 1 封闭性 任意两个码组的和还是许用的码组 2 码的最小距离等于非零码的最小码重 如果对于线性分组码 n k 中2r 1 n 就有可能构造出能纠正一位或一位以上误码的线性分组码 2 汉明码 汉明码 HammingCode 是由RichardHamming于1950年提出的 它属于线性分组编码方式 用以纠正单个错误的线性分组码 在软件无线电中应用广泛 其基本原理是 将信息码元与监督码元通过线性方程式联系起来 每一个监督位被编在传输码字的特定比特位置上 系统对于错误的数位无论是原有信息位中的 还是附加监督位中的都能把它分离出来 它有以下特征 码长n 2m 1信息位数k 2m m 1监督码位r n k m最小距离d 3纠错能力t 1这里m为大于等于2的正整数 给定m后 即可构造出具体的 n k 汉明码 假设k为4 要求能纠正一位误码 则根据条件2r 1 n 得r 3 现取3 则构成 7 4 汉明码 7 4 汉明码 用a0 al a2 a3 a4 a5 a6表示这7个码元 用S1 S2 S3表示由三个监督方程式计算得到的校正子 并假设三位S1 S2 S3校正子码组与误码位置的对应关系如下表所示 7 4 码校正子与误码位置 当误码位置在a2 a4 a5 a6时 校正子S1 1 否则S1 0 因此有 S1 a6 a5 a4 a2同理有S2 a6 a5 a3 a1S3 a6 a4 a3 a0 由表可知 在编码时 a6 a5 a4 a3为信息码元 a2 a1 a0为监督码元 则监督码元可由以下监督方程唯一确定 0 a6 a5 a4 a20 a6 a5 a3 a10 a6 a4 a3 a0也即 a2 a6 a5 a4a1 a6 a5 a3a0 a6 a4 a3 由上面方程可得到16个许用码组 在接收端收到每个码组后 计算出S1 S2 S3 如果不全为0 则表示存在错误 可以由下表确定错误位置并予以纠正 例如 收到码组为0000011 可算出S1S2S3 011 由表可知在a3上有一误码 通过观察可以看出 上述 7 4 码的最小码距为dmin 3 它能纠正一个误码或检测两个误码 如果超出纠错能力则反而会因 乱纠 出现新的误码 监督矩阵 0 a6 a5 a4 a20 a6 a5 a3 a10 a6 a4 a3 a0可写成 0 1 a6 1 a5 1 a4 0 a3 1 a2 0 a1 0 a00 1 a6 1 a5 0 a4 1 a3 0 a2 1 a1 0 a00 1 a6 0 a5 1 a4 1 a3 0 a2 0 a1 1 a0用矩阵表示为 111010001101010a6a5a4a3a2a1a0T 010110010简化为 HAT 0T其中H称为监督矩阵 H可以分成两部分 11101001101010 PIr 1011001其中P为信息位矩阵 Ir为rXr阶的单位矩阵生成矩阵G G IkPT 根据生成矩阵和已知的信息码元可产生整个码组 A a6a5a4a3 G 扩展汉明码 汉明码如果再加上一位对所有码元都进行校验的监督位 则监督码元由m增至m 1 信息位不变 码长由2m 1增至2m 通常把这种 2m 2m 1 m 码称为扩展汉明码 扩展汉明码的最小码距增加为4 能纠正l位错误同时检测2位错误 简称纠1检2错码 其实质上是在原汉明码的每个码组后面增加1位偶监督码元 例如 7 4 汉明码可变成 8 4 扩展汉明码 又称增余汉明码 循环码 循环码是一种特殊的线性分组码 它除了具有群码的封闭性外 还有一个特性就是循环性 按模运算 为了用代数理论研究循环码 可将码组用多项式来表示 称为码多项式 设许用码组C cn 1cn 2 clc0 对应的码多项式可表示为C x cn 1xn 1 cn 2xn 2 clx c0其中多项式的系数就是码字各分量的值 x为一个任意实变量 其幂次i代表该分量所在位置 循环码中的几个定理 1 若C x 是n长循环码中的一个码多项式 则xiC x 按模 xn 1 运算的余式必为循环码中另一码多项式 2 一个二进制中 n k 循环码中有惟一的r n k次多项式g x 且其常数项为l 如果一个码的所有码多项式都是多项式g x 的倍式 则称g x 生成该码 且称g x 为该码的生成多项式 所对应的码字成为生成子或生成子序列 3 设g x 是 n k 循环码 C x 中的一个次数最低的多项式 g x 0 则该循环码由g x 生成 并且g x 是 xn 1 的一个因式 从以上讨论中 可得到几个重要结论 在二元或GF 2 上找一个 n k 循环码 就是找一个能除尽xn 1的n k次首1多项式g x 为了寻找生成多项式 必须对xn 1进行因式分解 这可用计算机来完成 对于某些n值 xn 1只有很少的几个因式 因而码长为n的循环码也不多 仅对于很少的几个n值 才有较多的因式 如果C x 是 n k 码的一个码多项式 则g x 一定除尽C x 反之 若g x C x 则次数小于等于n 1的C x 必是码的码多项式 也就是说若C x 是码多项式 则C x 0modg x 例 多项式x7 1 x 1 x3 x 1 x3 x2 1 构造一个 7 3 循环码 要构造一个 7 3 循环码 就是在x7 1中找一个n k 4次的因式g x 作为码的生成多项式 由它的一切倍式就组成了 7 3 循环码 若选g x x3 x 1 x 1 x4 x3 x2 1 该码的八个码字可由g x xg x x2g x 的线性组合产生出来 而且这三个码多项式是线性无关的 它们构成一组基底 所以生成的循环子空间 循环码 是一个三维子空间V7 3 对应于一个 7 3 循环码 若选g x x 1 x3 x2 1 x4 x2 x l 则生成另一个循环码 由此可知 只要知道了xn l的因式分解式 用它的各个因式的乘积 便能得到很多个不同的循环码 循环码的编码方法 1 首先根据给定的 n k 值选定生成多项式g x 1 g x 是一个 n k 次多项式2 g x 的常数项不为03 g x 是xn 1的一个因子 2 冗余码的计算 1 把信息码元多项式m x 乘xn k 得T x 2 用g x 除T x 得到余式r x 3 余式r x 即为循环冗余码 它作为监督码元加于信息码元后面 4 写出码多项式C x T x r x 即 在m x 后面添加n个0 监督位 信息位 例 7 3 循环码m x x2 x g