新第5章差错控制编码.ppt

1 第5章差错控制编码 5 1引言5 2差错控制编码的基本原理5 3常用的简单编码5 4线性分组码5 5循环码 2 5 1引言 数字信号在传输过程中受到干扰的影响 使信号波形变坏 发生误码 可以采用一些方法解决 有效性 信源编码可靠性 信道编码 3 0 复习 模拟信源 在无线广播中 信源一般是一个语音源 话音或音乐 在电视广播中 信源主要是活动图像的视频信号源 这些信源的输出都是模拟信号 所以称之为模拟源 信源编码 将模拟信息源的输出转化为数字信号 即A D转换 信源编码目的 提高通信有效性 减少原消息的冗余度 5 1引言 4 差错出现原因外界噪声传输中码间串扰 解决方法合理地设计基带信号 选择调制 解调方式 采用均衡技术 发送功率等因素 使误比特率降低 差错控制措施 5 1引言 5 差错控制编码属信道编码 要求在满足有效性前提下 尽可能提高数字通信的可靠性 差错控制编码是在信息序列上附加上一些监督码元 利用这些冗余的码元 使原来不规律的或规律性不强的原始数字信号变为有规律的数字信号 例如奇偶校验 差错控制译码则利用这些规律性来鉴别传输过程是否发生错误 或进而纠正错误 5 1引言 6 按功能分 检错码和纠错码按监督码元与信息码元关系分 线性码与非线性码按信息码元与监督码元之间的约束关系不同分 分组码与卷积码按信息码元在编码后是否保持原来的信号形式分 系统码与非系统码按纠正差错的类型分 纠正随机错误的码与纠正突发错误的码按码元的取值分 二进制码与多进制码 1 差错控制编码分类 5 1引言 7 2 误码类型 随机误码 突发误码 错码出现是随机的 错码之间统计独立 由随机噪声引起存在随机误码的信道称为随机信道 无记忆信道 差错在短时间成串出现 而在其间又存在较长的无差错区间 且差错之间相关例如 脉冲噪声 存储系统中磁带的缺陷或读写头接触不良引起 再例如用手机过涵洞 且无发射天线存在这种差错的信道称为突发信道 有记忆信道 5 1引言 3 错误图样 例如 设发送数据序列为 00000000001111111111接收数据序列为 01101001001111001001错误图样 差错序列 发送数据序列与接收序列对应码位的模 和则差错序列为 01101001000000110110可见发生了两个长度分别为 和 的突发差错 其错误图样分别为1101001和11011突发长度 指突发差错首位与末位之间的长度 中间可能有没错的码位 9 说明差错序列或错误图样中的 表示对应码位没错 而 表示有错实际信道很复杂 所出现的差错并不是单一的 往往是随机和突发差错并存 只不过以某种错误为主一般说来 纠正随机差错的编译码方法和设备比较简单 成本较低 效果较显著 而纠正突发差错的编译码方法和设备比较复杂 成本较高 效果也不如前者显著 5 1引言 10 4 信道类型 随机信道 突发信道 混合信道 5 1引言 11 5 差错控制方法 检错重发 ARQ 停发等候重发返回重发选择重发前向纠错 FEC 反馈校验 IRQ 混合方式 HEC 5 1引言 12 1 检错重发法 ARQ AutomaticRepeatreQuest 收端在接收到的信码中发现错码时 就通知发端重发 直到正确接收为止 例如奇偶校验 检错重发方式只用于检测误码 能够在接收单元中发现错误 但不一定知道该错误码的具体位置 需具备双向信道 5 1引言 图5 1 1 b 检错重发 ARQ 判断有无错误 14 停发等候重发 图5 1 2停发等候重发 5 1引言 15 发端在Tw时间内送出一个码组 收端收到后检查 如果未发现错误 则发回一个认可信号 ACK 给发送端 发送端收到ACK信号再发下一个码组若检测到错误 则发回一个否认信号 NAK 发送端收到NAK信号后重发前一码组 并再次等候ACK信号或NAK信号发送两个码组之间有停顿时间TI 影响了传输效率 5 1引言 16 返回重发 图5 2 b 返回重发 其发送端不停地送出一个个连续码组 不再等候收端返回的ACK信号一旦收端发现错误并返回NAK信号 则发端从下一码组开始重发前面的N个码组N的大小取决于信号传递及处理所带来的延时 5 1引言 17 5 1引言 图5 1 3返回重发 18 选择重发 也是连续不断地发送码组 收端检测到错误后发回NAK信号 与返回重发不同的是 发端并不重发错误码组后的所有码组 而只重发有错的那个码组 5 1引言 19 图5 1 4选择重发 5 1引言 20 三者比较选择重发传输效率最高 但成本最贵 控制机制复杂 发端和收端都要有数据缓冲器 返回重发 选择重发需要全双工数据链路 而停发等候重发只要求半双工的数据链路 5 1引言 21 2 前向纠错法 FEC ForwardErrorCorrection 图5 1 5前向纠错 FEC 5 1引言 22 发送端将信息序列编码成能够纠正错误的码 接收端根据编码规则进行检查 如果有错自动纠正不需要反馈信道 特别适合只能提供单向信道场合自动纠错 不要求检错重发 延时小 实时性好纠错码必须与信道的错误特性密切配合若纠错较多 则编 译码设备复杂 传输效率低 5 1引言 23 3 信息反馈校验法 IRQ InformationRepeatreQuest 接收端将接收到的信码原封不动地转发回发端 并与原发送信码相比较 若发现错误 发端再重发 5 1引言 24 收端把收到的数据序列全部经反向信道送回发端 发端比较发出和送回的数据序列 从而发现有否错误 如果有错误 发端将数据序列再次传送 直到发端没有发现错误 不需要纠错 检错的编 译码器 设备简单 需要和正向信道相同的反向信道 实时性差发端需要一定容量的存储器以存储发送码组仅适应于传输速率较低 信道差错率较低 具有双向传输线路及控制简单的系统 5 1引言 25 4 混合纠错检错 HEC HybridErrorCorrection FEC与ARQ的结合发端发出同时具有检错和纠错能力的码 收端收到后 检查错误情况 如果错误在纠错能力之内 则自动纠正 若超出纠错能力 但在检错能力之内 则经反向信道要求重发 在实时性和译码复杂性方面是FEC和ARQ的折衷 5 1引言 26 5 1引言 27 核心问题 发现错误纠正错误 5 1引言 28 5 2差错控制编码的基本原理 在信息码序列中加监督码就称为差错控制编码 也叫纠错编码 不同的编码方法 有不同的检错和纠错能力 增加监督码元越多 检 纠 错能力越强 差错控制编码原则上是降低编码效率来换取可靠性提高 即误码率更小 29 理论依据 Shannon信道编码定理 定理指出 对于一给定的有干扰信道 若其信道容量为C 只要发送端以低于C的速率R发送信息 则一定存在一种编码方法 使编码错误概率P随着码长n的增加 按指数下降到任意小的值 1 纠错编码的理论依据 5 2差错控制编码的基本原理 30 5 2差错控制编码的基本原理 31 2 纠错编码的基本思想 5 2差错控制编码的基本原理 发送端按照某种规则在信息序列上附加监督码元 接收端则按照同一规则检查两者间关系 以牺牲通信的有效性 信息传输速率 来提高可靠性码的检错和纠错能力是用信息量的冗余来换取的 一般说来 添加的冗余越多 码的检错 纠错能力越强 但信道的传输效率下降也越多 32 码长 码字中码元的数目 码距 两个码组之间对应位上码元取值不同的个数 定义为两码字的距离 简称码距 d 对于二进制称作这两个码字的汉明距离 如两码字 10011 与 11010 间码距为2 3 码距与检错和纠错能力的关系 5 2差错控制编码的基本原理 1 几个概念 33 最小码距 在一个码字集合中 任意两个码字间距离的最小值 即码字集合中任意两元素间的最小距离 记为dmin或d0码重 码字中非零码元的数目定义为该码字的重量 简称码重 如 10011 码字的码重为3 纠错码的抗干扰能力完全取决于许用码字之间的距离 码的最小距离越大 说明码字间的最小差别越大 抗干扰能力就越强 5 2差错控制编码的基本原理 34 举例说明 假如要传送A B两个消息 编码一 消息A 0 消息B 1 最小码距1若传输中产生错码 0 错成 1 或 1 错成 0 收端无法发现 该编码无检错纠错能力 5 2差错控制编码的基本原理 35 编码二 消息A 00 消息B 11 最小码距2 00 11 称为许用码组 而 01 10 称为禁用码组若传输中产生一位错码 则变成 01 或 10 收端判决为有错 但无法确定错码位置 不能纠正 该编码具有检出一位错码的能力 这表明增加一位冗余码元后码具有检出一位错码的能力 5 2差错控制编码的基本原理 编码三 消息A 000 消息B 111 最小码距3传输中产生一位即使两位错码 都将变成禁用码组 收端判决传输有错 该编码具有检出两位错码的能力 在产生一位错码 错1位概率远远大于错2位 3位概率 情况下 收端可根据 大数 法则进行正确判决 能够纠正这一位错码 该编码具有纠正一位错码的能力 例如收到110 认为是111 这表明增加两位冗余码元后码具有检出两位错码或纠正一位错码的能力 37 一个码能检测e个错码 则要求其最小码dmin e 1一个码能纠正t个错码 则要求其最小dmin 2t 1一个码能纠正t个错码 同时能检测e个错码 则要求其最小码距dmin e t 1 e t 2 最小码距与检错和纠错能力的关系 5 2差错控制编码的基本原理 38 a 检e个错 图5 2 2 a 码距与检错纠错能力的关系 A B都为许用码 A发生e个错 B不能靠在球面上 否则收到B无法判断是否为错码 dmin e 1 5 2差错控制编码的基本原理 39 1 b 纠正t个错码 图5 2 2 b 码距与检错纠错能力的关系 A B都为许用码 A B都发生t个错 dmin 2t 1 5 2差错控制编码的基本原理 40 c 纠正t个错码 检测e个错码 图5 2 2 c 码距与检错纠错能力的关系 A B都为许用码 当误码数小于等于t时 可纠正误码 当误码数大于t小于等于e时 不会落入另一码组的纠错范围内 dmin e t 1 5 2差错控制编码的基本原理 41 当码长n 7 P 10 3时 则有 假设随机信道中发送 0 码与发送 1 码传错概率相等都为P 且P 1 则在码长为n的码组中发生r个错误的概率为 4 误码率 大概率事件 5 2差错控制编码的基本原理 42 设n k r指一个码组中信息位所占比重 用 表示 k n k k r 其中k为信息码元的数目 n为码长编码效率是衡量纠错性能的一个重要指标 一般情况下 监督位越多 检纠错能力越强 但相应的编码效率也越低 5 编码效率 一次课 5 2差错控制编码的基本原理 43 奇偶监督码二维奇偶监督码恒比码正反码 5 3常用的简单编码 44 1 奇偶监督码 5 3常用的简单编码 奇偶监督码 在信息码元后附加一位监督位 使得码组中 1 的个数为偶数或奇数 45 最小码距dmin 2只能检测出单个或奇数个错误 不能纠错应用 以随机错误为主的计算机通信系统 难于对付突发错误编码效率 k n k k 1 5 3常用的简单编码 46 将经过奇偶监督编码的码元序列按行排成方阵 每行为一组奇偶监督码 但发送时按列的顺序传输接收端将码元排成发送时的方阵形式 再按行进行奇偶校验能够发现某行上所有奇数个错误以及突发长度不大于方阵行数的突发错误编码效率 2 水平奇偶监督码 5 3常用的简单编码 表5 1水平奇偶监督码 表5 2水平奇偶监督码接收端出现突发误码示例 结论 能够发现突发长度不大于方阵行数的突发错误 49 又称为方阵码 行列监督码 二维奇偶监督码 将水平奇偶监督码推广到二维 即在水平监督基础上再对方阵中每一列进行奇偶校验 发送时按列的顺序传输接收端将码元排成发送时的方阵形式 再分别按行 按列进行奇偶校验 3 水平垂直奇偶监督码 5 3常用的简单编码 50 能够发现某行 某列上所有奇数个错误以及突发长度不大于方阵行数或列数的突发错误 有可能检测出偶数个错误 在行上检测不出 但有可能在列上检测出 但当偶数个错误刚好构成矩形时 则检测不出可纠正一些错误 5 3常用的简单编码 表5 3水平垂直奇偶监督码 发送顺序 表5 4水平垂直奇偶监督码接收端纠错示例 例如 当码组中仅在一行有奇数个错误时 能够确定错误位置 并纠正它 表5 5水平垂直奇偶监督码接收端检错示例 0 1 1 构成矩形的偶数个误码检测不出 0 0 表5 6水平垂直奇偶监督码接收端检错示例 0 1 有可能检测出偶数个误码 0 0 1 55 4 ISBN国际图书统一编号InternationalStandardBookNumber 无误码 若不能被11整除 有误码 5 3常用的简单编码 56 5 3常用的简单编码 能被11整除 无误码 57 5 4线性分组码 重点 1 分组码 先将信息码分组 然后给每组信码附加若干监督码的编码称为分组码 用符号 n k 表示 k是信息码的位数 n是编码组总位数 又称为码长 r n k为监督位数 2 代数码 建立在代数学基础上的编码 称为代数码 例如奇偶校验码 1 基本概念 58 3 线性码 线性码中信息位和监督位是按一组线性方程构成的 线性码是一种代数码 奇偶监督码是最简单的线性码 4 线性分组码 信息码分组后 附加的监督码和信息码由一些线性代数方程联系着的编码称为线性分组码 5 4线性分组码 59 2 线性分组码的性质 任意两个许用码组之和 逐位模2和 仍为一许用码组 即具有封闭性 最小码距 非零码的最小码重 1的个数 因为线性分组码中必有一个全0码组 5 4线性分组码 60 以汉明码为例来说明编码原理 汉明码是一种设计用来纠正一位错码且编码效率较高的线性分组码 7 4 汉明码的编码效率为 3 线性分组码的编码原理 5 4线性分组码 61 发送端编码 将一位监督码元附加在信息码元后 使得码元中 1 码元个数为偶数 接收端译码 计数接收码组中 1 码元个数是否为偶数 即计算 S an 1 an 2 a0 模2加 5 4 1 S 0认为没错 S 1认为有错 5 4 1 式称为监督方程 监督关系式 S称为校正子 校验子 伴随式 1 回忆奇偶监督偶校验码 5 4线性分组码 62 监督位增加到2位 有两个监督方程 两个校验子 两个校验子组合有四种 如00表示无错 01 10 11则可表示一位错码的三种可能位置 监督位增加到r位 可指示一位错码的 2r 1 个可能位置对于 n k 分组码 若希望用r n k个监督位构造出的r个监督关系式来指示一位错码的n种可能位置 则要求 可以这样来考虑 2r 1 n即2r k r 1 5 4 2 5 4线性分组码 63 欲纠正一位错码 由 5 4 2 式知r 3 取r 3 则n k r 7设7位码元为 a6a5 a0 三个校正子 S1 S2 S3 可规定S1S2S3的八种组合与一位错码的对应关系 也可规定为另一种对应关系 构造一 n k 分组码 k 4并能纠正一位错码 2 汉明码的构造 5 4线性分组码 64 表5 9S1S2S3的八种组合与一位错码的对应关系 5 4线性分组码 S1 a2 a4 a5 a6S2 a1 a3 a5 a6S3 a0 a3 a4 a6 5 4 3 监督方程 模2加 仅当有一个错码且位置在a2 a4 a5 a6时 S1为1 否则为0 这就意味着这四个码元构成偶数监督关系 即 66 3 发端编码的原则 信息码元a6 a5 a4 a3来源于待编码的信息序列 监督码元a2 a1 a0的取值应根据信息码元按监督关系式来决定 即使前面三式中的S1 S2 S3均为0 000表示无错码 5 4线性分组码 67 a2 a4 a5 a6a1 a3 a5 a6a0 a3 a4 a6 给定信息位后 根据上式算出各监督位 该编码的所有码组如表5 10 5 4 4 a6 a5 a4 a2 0a6 a5 a3 a1 0a6 a4 a3 a0 0 5 4 5 5 4线性分组码 表5 10许用码组 69 该汉明码的编码效率较高R k n 4 7 57 该码的最小码距为3 能纠正一个错码或检测两个错码设收到码组0000011 按监督方程计算可得 S1 0 S2 1 S3 1 再根据校正子组合与一位错码位置的对应关系 可知错码发生在a3位 并加以纠正 0001011 5 4线性分组码 70 4 监督矩阵 沿 7 4 汉明码出发 式 5 4 4 可改写成 1 a6 1 a5 1 a4 0 a3 1 a2 0 a1 0 a0 01 a6 1 a5 0 a4 1 a3 0 a2 1 a1 0 a0 01 a6 0 a5 1 a4 1 a3 0 a2 0 a1 1 a0 0写成矩阵形式 5 4 6 5 4线性分组码 71 H称为线性码监督矩阵 可化简为 H AT 0T或A HT 0 5 4线性分组码 72 r n阶矩阵H确定了编码时监督码元与信息码元的关系把具有 P Ir 形式的H矩阵称为典型形式的监督矩阵 其中P为r k阶矩阵 Ir为r r阶单位方阵当H不是典型阵时 可变换为典型阵 由典型阵构成的码组称为系统码 非典型阵构成的码组称为非系统码H矩阵的各行应线性无关 矩阵若能写成典型形式 则其各行一定线性无关 监督矩阵H特点 5 4线性分组码 73 上式右部前面矩阵就是监督矩阵H中的P矩阵 5 生成矩阵 同样 监督码生成方程 5 4 5 式也可写成矩阵形式 即 5 4 7 5 4线性分组码 74 其中Q PT可见 Q为k r阶矩阵 或写成 5 4线性分组码 75 生成矩阵G 在Q矩阵的左边加上一个k k阶矩阵 即 5 4线性分组码 76 k n阶矩阵编码方法完全由生成矩阵G确定把具有 Ik Q 形式的G矩阵称为典型形式的生成矩阵 其中 Ik为k k阶单位方阵 Q为k r阶矩阵由典型生成矩阵产生的分组码一定是系统码G矩阵的各行应线性无关 每行均为许用码组 生成矩阵G特点 5 4线性分组码 77 例5 2 已知 6 3 汉明码的生成矩阵如下 1 列出所有许用码组 2 最小码距d0 3 检错纠错能力 4 编码效率 5 4线性分组码 1 3 4 2 80 设 7 4 线性码的生成矩阵G为 当信息位为0001时 1 试求其后的监督位 2 监督矩阵H 5 4线性分组码 81 解 1 82 2 监督矩阵H根据生成矩阵和监督矩阵的关系 G Ik Q H P Ir 其中P QT 可得监督矩阵H为 83 错误矩阵 错误图样E 设发送码组为A 接收码组为B 6 校正子与检错 则错误矩阵 5 4线性分组码 84 接收端计算校正子S 即S BHT A E HT AHT EHT 0 EHT EHT可见校正子只与E有关 即错误图样与校正子之间有确定的关系 所以可从错误图样与校正子的关系表中确定错码位置 加以纠正 5 4线性分组码 85 以 7 4 汉明码为例设发送码组A 0001011 接收码组B 0000011 则收端译码过程如下 计算校正子 查表得a3为错误位置 即可纠正 0001011 5 4线性分组码 86 5 4线性分组码 4 7 4 汉明码编译码仿真 汉明码编译码仿真 87 设A1和A2为码中任意两许用码组 则有A1 HT 0A2 HT 0于是A1 HT A2 HT A1 A2 HT 0即 A1 A2 必是该码中一许用码组 例5 3 证明线性分组码的封闭性 略 p319 9 6 作业 5 4线性分组码 88 5 5循环码 循环码是一种重要的线性分组码 这种码的编码和解码设备都不太复杂 且有较强的检 纠 错能力 共n位 通常前k位为信息位 后r位为监督位 5 5 1循环码的编码原理 89 循环码的特点 封闭性 循环性 即码中任一码组循环一位 将最右端的码元移到左端或反之 以后 仍为该码中的一个码组 5 5 1循环码的编码原理 90 若 an 1 an 2 a1 a0 是一 n k 循环码的码组 则 an 2 an 3 a1 a0 an 1 an 3 an 4 a0 an 1 an 2 a0 an 1 an 2 an 3 a2 a1 也都是该循环码的码组 5 5 1循环码的编码原理 91 表5 10一种 7 3 循环码的全部码字 把码长为n的码组中的各码元当作n 1次多项式的系数若码组A an 1 an 2 a1 a0 则其相应的码多项式为 T x an 1xn 1 an 1xn 1 a1x a0对于 7 3 循环码的任意码组可表示为 T x a6x6 a5x5 a4x4 a3x3 a2x2 a1x a0如码组 1100101 对应的码多项式可表示为T7 x 1 x6 1 x5 0 x4 0 x3 1 x2 0 x 1 x6 x5 x2 1 1 码多项式T x 93 码多项式与码组的关系 本质上是一回事 仅是表示方法的不同而已 对于二进制码组 多项式的每个系数不是0就是1 x仅是码元位置的标志 因此 这里并不关心x的取值 0 0 00 1 11 0 11 1 00 0 00 1 01 1 1 5 5 1循环码的编码原理 94 若一个整数m可以表示为 则在模n运算下 有m p 模n 同样对于多项式而言 则可以写为 F x R x 模N x 即一任意多项式F x 被一个n次多项式N x 除 得到商式Q x 和一个次数小于n的余式R x 5 5 1循环码的编码原理 95 例如码组 1100101 对应的码多项式可为 T7 x x6 x5 x2 1其被x3 1除得x6 x5 x2 1 1 模x3 1 5 5 1循环码的编码原理 96 在循环码中 若T x 是一个长为n的许用码组 则xi T x 在按模xn 1运算下 也是一许用码组 即若xi T x Ti x 模xn 1 则Ti x 也是一许用码组 且为A x 码组向左循环移位i次的结果 重要结论 5 5 1循环码的编码原理 97 例如A4 0111001 对应的码多项式为 A4向左循环移1位得A7 1110010 这相当于将A4 x 乘以x 即 A7向左循环移1位得A6 1100101 但若将A7 x 乘以x得到多项式为对于 7 3 循环码的码多项式 其最高次数不能超过6 解决该问题的办法是对上式作模x7 1运算得余作为码多项式 98 例如 其对应的码组为0101110 它正是表5 10中第3码字 结论 一个码长为n的 n k 循环码 它必为按模xn 1运算的一个余式 5 5 1循环码的编码原理 99 循环码完全由其码组长度n和生成多项式g x 所决定问题 寻找构成生成矩阵的k个线性无关的许用码组 2 循环码的生成多项式与生成矩阵 5 5 1循环码的编码原理 100 生成多项式 如果一种码的所有码多项式都是多项式g x 的倍式 则称g x 为该码的生成多项式 在 n k 循环码中任意码多项式A x 都是最低次码多项式的倍式 如 7 3 循环码中 其它码多项式都是g x 的倍式 即 101 n k 循环码中一定能找到这样一个码组 前面的k 1位都是0 而第k位及第n位为1 其它各位gi为0或1 000 01gn k 1gn k 2 g2g11 其对应的码多项式为g x 且g x 一定是码中唯一的一个n k次多项式 这唯一的n k次多项式g x 称为码的生成多项式 5 5 1循环码的编码原理 102 也就是说 最高次方为n k 最后一位为1的多项式即为生成多项式g x 如 7 3 循环码 T x a6x6 a5x5 a4x4 a3x3 a2x2 a1x a0前k 1位为0 即前两位为0 因为k 3 也就是最高次方为n k 4 最后一位a0为1的多项式即为g x 5 5 1循环码的编码原理 103 例如 上表中的编码为 7 3 循环码 n 7 k 3 n k 4 其中唯一的一个 n k 4次码多项式代表的码组是第二码组0010111 与它对应的码多项式即生成多项式为 g x x4 x2 x 1 104 可以证明生成多项式g x 具有以下特性 1 g x 是一个常数项为1的次多项式 2 g x 是的一个因式 3 该循环码中其它码多项式都是g x 的倍式 g x xg x xk 1g x 5 5 1循环码的编码原理 105 g x xk 1g x 都是许用码组 连同g x 共k个许用码组 构成码的生成矩阵G x 注 该生成矩阵并不是典型形式的 但可通过线性变换变换成典型的生成矩阵 5 5 1循环码的编码原理 106 一旦生成多项式g x 确定以后 该循环码的生成矩阵G x 就可以确定 进而该循环码的所有码字就可以确定 生成矩阵G x 的每一行都是一个码组 5 5 1循环码的编码原理 107 例5 4 试求表5 10 7 3 循环码的生成多项式和生成矩阵 解 对 7 3 循环码 n 7 k 3 r 4由上例已知生成多项式为 g x x4 x2 x 1 5 5 1循环码的编码原理 将第1行与第3行模2加作为第1行 则有 为典型生成矩阵 108 接上例 设信息码为101 求整个码组 解 整个码组A 信息码 G 典型的 故A 101 1011100 5 5 1循环码的编码原理 109 例5 5 已知循环码的生成多项式为 当信息位为1000时 写出它的监督位和整个码组 解 由生成多项式可知n k 3 而k 4 所以n 7 110 第1行 第3行 第4行第1行 第2行 第4行第2行 非典型 典型 当信息位为1000时 整个码组为 111 监督位为101 112 已知 7 4 循环码的全部码组为 试写出该循环码的生成多项式g x 和生成矩阵G 并将G化成典型矩阵 5 5 1循环码的编码原理 113 解 n 7 k 4 n k 3上述码组中的 n k 3次码多项式为第2组 它所对应的码多项式g x 即为生成多项式 g x x3 x 1 生成矩阵为 114 5 5 2循环码的编码 解码方法 1 编码方法 1 原理 用码多项式来表示为 A mk 1mk 2 m0ar 1 a1a0 式中M x 是信息码组码多项式 所以只需要确定r x 已知循环码的所有码字都能够被g x 整除 r x 可由下式确定 115 设信息位对应的多项式为m x 用xn k乘m x 相当于把信息码后附加上 n k 个 0 详细解释 用g x 除xn km x 得到余式为r x 编出码组为 T x xn km x r x 2 编码步骤 5 5 2循环码的编码 解码方法 116 例如 信息码为110 它相当于m