电力系统远动原理及技术ppt课件

电力系统远动原理及技术 第四章远动信息的信道编译码 4 1概述 在远动系统中 远动装置采集的信息必须通过通信通道传输到调度控制中心才能使用 上行 调度控制中心下达到各厂站端的命令同样也必须通过通信通道才能传送到各厂站端的远动装置 下行 因此通信信道是远动系统中的重要组成部分 1 信道编码 原因 通信信道各种干扰 使远动信息在传输时 由于干扰而发生差错 从而降低远动信息的可靠性 目的 使要传送的信息有较好的抗干扰能力 信道编码又称为抗干扰编码 措施 在信息进入通信线路之前 对它加以改造 保护形成码字 使码字的内容结构具有一定的规律性和相关性 当信息受到干扰后能根据码字原有的内在规律性和相关性 发现甚至纠正错误 达到恢复原来信息的目的 2 信道编码的方法 信道编码的一般方法 对信源编码得到的序列 按照某种规律 添加一定数量的监督码元 由信息序列和监督码元构成一个有抗干扰能力的码字 添加监督码元的规律或规则不同 就形成了不同的编码方法 远动信息的信道编码常用编码方法有 奇偶加正反校验码 BCH码 等比码 卷积码等 目前主要采用的是BCH码 BCH码 名称由来 三个人的名字 优点 有效纠正多个随机错误 具有循环码的优点 编译码容易实现 结果 国际电工委员会和我国的远动标准都要求用此编码方式进行抗干扰的编码 4 2信道编码的基本原则 4 2 1数字传输系统模型 1 图4 1数字通信系统模型 信源 信源编码 信道编码 调制器 通信 解调器 信道译码 信源译码 信宿 s m c 干扰 r m s 2 信源 信源 信源就是指各种参数 状态和命令 可以是开关的合闸或跳闸状态 也可以是电压 功率等的数值 信源的输出可以是连续变化的模拟信号 也可以是离散的数字信号 3 信源编码 有效性编码 信源编码是将各种形式的信源 经变送器 模数转换电路或其它各种编码电路变成离散的代码 信源编码原则 一是使代表信源s的码元数尽可能少 二是要能能够从信息序列m重构原来的信源s 3 信源编码 例 以信源是4个状态为例 如果信源编码采用两位二进制数的信息序列 则00 01 10 11可分别代表信源的四种状态 其二进制数的个数最少 且能重构原来的四种状态 若采用一位或三位二进制数 就不能同时满足上述两点要求 故信源编码又称有效性编码 4 信道编码的作用 信道编码的作用是根据一定的规则 在信息序列m中添加一些码元 将信息序列m变成较原来长的二进制数字序列c 称为码字 信道编码的目的是提高信息序列m的抗干扰能力 5 调制器的作用 调制器的作用是将用数字序列表示的码字c 变换成适合于传输的信号形式 送入信道 电力系统远动装置中 常采用数字调频或数字调相的方法 将码字c中的每个码字 0 或 1 变成不同的两种载波频率或两种载波相位 6 信道的类型 电力载波微波散射波光纤通道等 7 信道中的干扰源 远动系统中的噪音由雷电 弧光 电火花 天线电台频率干扰 多路通信的跳闸干扰等所引起 任何远动系统环境中 干扰是永远存在的 不同的信道具有不同的干扰源 信道编码就是抗信道干扰的措施之一 7 信道中的干扰 3 码字在信道中穿送时受到干扰的情况 可用错误图样e来表示 如果e中的所有位不全为 0 则按收码字r肯定和发送码字c不完全相同 即信息在信道中受到了干扰 错误图样 有了错误图样与接收码字就可以得到正确的发送码字了吗 错误图样是我们为了研究信道中的干扰而提出的一个物理模型 错误图样并不真正存在于发送过程中 错误图样是我们通过信道译码纠正了干扰后得到的一个序列 而不是通过错误图样进行译码 先后顺序 8 信道译码 信道译码就是根据按收码字r及信道编码规则 检查或纠正按收码字r中的错误码元 产生出发送码字c的估计值c 并从c 中还原出信息序列m的估计值m 9 信源译码 信源译码是根据信源编码规则 将按受到的信息序列m 转变为原信源s的估计值s 并送给显示系统显示或执行对象执行 这里在显示或执行就是我们所说的 信宿 也称为 受信者 11提高信息传输可靠性的措施 提高信息传输可靠性的措施之一 是设计出性能良好的信道编码器和译码器 1提高传输率 2码字的抗干扰能力强 12 数字传输中的干扰 随机干扰 如果干扰对每个码元的影响是独立的 与前后码元无关 这种干扰称为随机干扰 突发干扰 如果干扰一旦发生 不但影响某一个码元 而且同时引起前后某些码元的错误 错误之间具有相关性 这种干扰称为突发干扰 13 实际信道中的干扰 实际干扰类型 随机干扰和突发干扰并存的通道称为复合通道 对应措施 对于复合通道 我们应该对它的干扰所产生的错误进行统计分析 掌握其错误出现的规律 以便采用一种有针对性的信道编码方法 4 2 2最大似然译码 原理性 原理性 并非实际采用的译码方式 研究对象载体 信道中受干扰情况与信道的特性有关 最简单而最典型的信道是二进制对称信道 简称BSC信道 BSC信道的特征 按收码元与发送码元相同的概率 为码元正确按收概率q q 0 5 按收码元与发送码元相反的概率 为码元错误概率p p 0 5 P Q 1 要么正确 要么错误 假设信道对发送码元的影响是独立的 4 2 2最大似然译码 原理 名称理解 最相似 量化就是按位计算条件概率 原理 在按收到码字后 信道译码器对信道编码器可能输出的所有码字c 计算它们的条件概率 若对可能的发送码字条件概率最大 则认为码字就是发送码字 可将收到的译为发送码字 这种译码方案称为最大似然译码 对于一个编码方案来说 所有的码子是一个有限的集合 4 2 2最大似然译码 计算 条件概率可表达如下 4 1 式中 当时 当时 4 2 2最大似然译码 计算公式改写 令为发送码字与接收码字不同的码元位数 则 4 1 式可改写为 4 2 注意 不具有实际操作性 只是原理描述 分析 由于二进制对称信道中P Q 所以条件概率随不同码元个数 D 的增大而减小 所以按条件概率最大来寻找发送码字 等效于寻找与按收码字不同的码元位数最少的发送码字 4 2 2最大似然译码 实质 因此 最大似然译码就是判断发端可能发送的所有码字中 哪个码字与接接收码字最相似 与最相似的码字 两者之间不同的码元位数最小 按 4 2 式算出的条件概率必然最大 例子 4 2 3最小距离译码的检纠错能力 1 汉明距离 汉明距离 码距 是指两个码元位数相同的码字之间 对应码元位不相同码元的数目 计算 按位异或后求和或者是模2加 4 2 3最小距离译码的检纠错能力 2 知道了码距的概念 我们就知道 对于最大似然译码来说 就是找到与接收到的码字距离最小的码字 并认为此码字就是发送端想要发送的码字 关于码距在编码中的一个定义 在一种码的所有码字的集合当中 任意两个码字之间的码距不一定相同 我们将所有可能的码字之间的码距的最小值称为这个码字集合的最小值 记为dmin 4 2 3最小距离译码的检纠错能力 3 汉明重量 汉明重量 码重 码字中非零码元的个数 用w表示 在二进制情况下 它就是码字中1码元的个数 若码字则其码重为 4 4 4 2 3最小距离译码的检纠错能力 4 前提 在一个线性码中任意两个码字v和u相加 得到的码字v u一定在该线性码中 当v和u中对应位上的码元不同时 在v u的码字中对应位上的码元是1 否则为0 由此可得出等式 4 5 该式说明 一个线性码中 任意两个码字之间的汉明距离正好等于这两个码字相加所得到的另一个码字的汉明重量 重量与距离的联系区别 重量是一个码字的运算距离是两个码字的运算联系是公式4 5 关于线性码的一些结论 一个线性码的所有码字中 如果某两个码字之间的码距最小 则它们之间的码距可以代表该线性码的最小距离 同时 这两个码字的和一定为该线性码字中的另一个码字 这个码字的重量一定最小 因此 一个线性码的最小距离等于它的非零码字的最小重量 4 2 3最小距离译码的检纠错能力 7 一种码的最小距离是衡量这种码抗干扰能力 检纠错能力 的重要参数 对最小距离为dmin的码 它能纠正的码字中的错误码元的个数t和能检出的码字中的错误码元个数l满足如下关系式 4 2 3最小距离译码的检纠错能力 8 纠错能力 4 6 检错能力 4 7 同时检错和纠错的能力 4 8 最小码距与码的检 纠错能力之间的关系 可以用图形作几何解释 举例 只传输两个信息 断路器分合闸 保护动作未动作 开关量 直观上讲 可以只用一位长度的码字即可 选取0 1分别表示合闸 跳闸显然 这个编码方式下 码的最小距离为1 即dmin 1 无检错 纠错能力验证 无论哪个码字受到干扰 都将变为另一个码字 因此接收端无法知道是否受到了干扰 如果用两位长度的码字即可 选取00 11分别表示合闸 跳闸显然 这个编码方式下 码的最小距离为2 即dmin 2 可检错1位 无纠错能力验证 检错 发送的码字00 11只受到1位的干扰 即变为01 10 接收端就可以知道此码字受到了干扰 可以检出一位干扰造成的错误 如果受到了2位的干扰 即变为11 00 则接收端无法知道此码字受到了干扰 不能检错 验证 纠错 发送的码字受到1位的干扰 变为01 10 由于受到干扰的码字与发送的码字 00 11 的相似程度相同 因此接收端无法纠正错误 如果用三位长度的码字即可 选取000 111分别表示合闸 跳闸显然 这个编码方式下 码的最小距离为3 即dmin 3 可检错2位 纠错1位验证 检错 受到1位干扰同前 发送的码字000 111受到2位的干扰 接收端就可以知道此码字受到了干扰 可以检出2位干扰造成的错误 如果受到了3位的干扰 即变为111 000 则接收端无法知道此码字受到了干扰 不能检错 验证 纠错 发送的码字受到1位的干扰 如001则可以判断是000码字受到了干扰 纠正错误 译码为000 4 2 3最小距离译码的检纠错能力 17 抗干扰编码就是对信源编码得到的k位信息序列 按照某种规律添加r位新码元 称为监督元 达到增大码的最小距离的目的 经抗干扰编码后得到的码字 其码元位数 称码长 编码效率 4 2 3最小距离译码的检纠错能力 18 添加监督元的规律或规则不同 便形成不同的码元方法 对编码方法的选择原则 一是 要使新选择的编码方法能够检测出或纠正信道中最可能出现的错误图样 前述根据不同的信道选择不同的编码方式 二要 提高编码效率 即在保证可靠性的前提下 尽量减少监督元的数目 有侧重性 三要 使选择的方法易于实现 比如 选择消息序列在前 监督序列在后的编码方式 结论 增加码字的距离可以增加码字的抗干扰能力 即增加检错 纠错的能力 但是增加距离就必须增加监督元 附加信息 会使信息编码的效率降低 矛盾 两者是矛盾的 因此 在实践中应当选取适当的编码方式 适合工程需求 比如 远动应用的4840码4032码等 4 3信道编码的代数基础 码字中的信息元和监督元之间按一定的代数关系互相约束 这种编码属于代数编码 这里只有介绍我们常用到的一些基本的理论 元 集的概念 简单介绍 元 就是元素 可能是数 点 线 面等集 即集合 是一些元素的集体表示 域 一个非空域上的元满足一些特定运算规则 则称此集为域 例如 有理数集中包括的元是所有的有理数 对于加法和乘法运算 结果也在这个集中 则可以说 有理数集对于加法和乘法来说是一个域 有理数域 下面来看伽罗华域 4 3 1伽罗华域及域上多项式 1 设F式一个非空集合 在F中定义加法和乘法两种代数差异 若F对这两种运算满足自封 并满足以下运算规则 4 3 1伽罗华域及域上多项式 2 加法 对任意 有 对任意 有 若F中有易个元素位0 任意 有 对任意 有 4 3 1伽罗华域及域上多项式 3 乘法 对任意 有 对任意 有 存在易元素 具有性质 则 有 4 3 1伽罗华域及域上多项式 4 在加法与乘法间满足分配规律 有 则F对于所规定的加法和乘法运算式是一个域 4 3 1伽罗华域及域上多项式 5 如果域F中的元素个数无限 称F为无限域 元素个数有限 称F为有限域 也称为伽罗华域 具有两个元素0和1 且加法和乘法运算按模2加模2乘法运算的有限域称为二元域 记为GF 2 后面的分析都在这个域上 4 3 1伽罗华域及域上多项式 6 模2加法运算规则是 模2乘法运算规则是1 1 1 0 0 0 0 1 0 1 0 0以后为了书写上的方便 将直接用 和 号表示和 域上多项式的概念 用来表示信息序列 假如一个多项式的所有系数和未知数x是某域上的元素 则称这个多项式是该域上的多项式 域上多项式可表示为 4 9 在GF 2 上的多项式 系数和未知数x的取值只能是0或1 对的单项式为 的单项式为 4 3 1伽罗华域及域上多项式 8 在信道编码中 经常用多项式来代表一个信息序列或码字 这种多项式称为消息多项式 注意 多项式种的x不再有未知数的概念 只代表系数所处的位置 而系数则代表码元的取值 例如二进制序列1101101 可用二元域上的多项式来等效地表示 而11000010111可表示为二元域上的多项式 4 3 2二元域上的矢量空间及矩阵 为何要研究二元域 计算机信息的表示方法 为何要研究其上的矢量空间与矩阵 一种编码中的码字有很多个 每一个码字就是一个序列 序列中的信息是有先后顺序的 我们可以当成一个矢量 研究一个编码就需要研究其中所有码字的集合 4 3 2二元域上的矢量空间及矩阵 1 对于二进制序列 可以是0 也可以是1 取值等于二元域GF 2 中的元素 通常称这个序列为GF 2 上的n重 n位序列可以构成个不同的n重 所有二进制n重的集合称为GF 2 上的矢量空间 记作 其中的任何一个n重 称为矢量 也称为码矢 矢量运算法则 加法 乘法按位 矢量运算法则 一个二进制n重v与GF 2 中任一元素的标乘定义为 由于取值为0或1 则的值只有两种 全0n重 或是原来的n重 正交 如果矢量空间中两个矢量V U 满足 则称两个矢量正交 反之 称为非正交矢量 子空间定义 由矢量空间中的部分矢量构成的集合称为的子集 若子集s中包含全0矢量 并且s中任何两个矢量的和也在s中 则称子集s为矢量空间的子空间 矢量的线性相关性 全是矢量空间中的k个矢量 这k个矢量的线性组合构成另一个矢量 4 10 若只有为全0时 才能得到为全0矢量 则称是线性无关的 反之 则称为线性相关的 举例 线性相关 对于4维的一组矢量 1100 1010 1011 1101 如果取各矢量的系数分别为1 1 1 1 则U 0000 说明这组矢量是线性相关的 举例 线性无关 对于4维的一组矢量 1000 0100 0010 0001 无论取得何种不全为0的系数组合 U都不可能为全零矢量 0000 说明这组矢量是线性无关的 注意 一组矢量要么是相关的 否则必然是无关的 在研究了矢量的相关性之后 我们来看基底 维数的概念 4 3 2二元域上的矢量空间及矩阵 6 前提 是一组线性无关的矢量 保证唯一性 若一个矢量空间中的每一个矢量 都等于一组矢量的线性组合 则称这组矢量张成这个矢量空间 基底 这组张成矢量称为被张成矢量空间的基底维数 而基底中矢量的个数称为被张成矢量空间的维数 拓展到矩阵中 一个k行n列的k n矩阵排列如下 4 11 行空间 位于阵列中带i行和第i列的元素若只取GF 2 中的元素 0或1 则称G为域GF 2 上的一个k n矩阵 矩阵G中每一行是一个二进制n重 每一列是一个二进制k重 若矩阵G的k行是中的k个线性无关的n重 则G的所有行的线性组合构成的一个k维子空间 称它为矩阵G的行空间 零化空间 对于任何具有k个线性无关行的GF 2 上的k n矩阵 总存在一个距阵H 4 12 零化空间 它的n k行也是线性无关的 而且K H矩阵G的任意行与 N K N矩阵H的任意行都正交 即 4 13 引申 矩阵G的行空间中的任意矢量v与矩阵H的行空间中的任意矢量n都是正交的 结论 我们称为G的行空间是H的零化空间 同样 H的行空间也是G的零化空间 结论 前提 由于矩阵G和H之间的这种性质方法 得到了编译码的方法编码 在线性分组码的编码中 用G的行空间中的个n重作为许用码字发送出去 译码 以矩阵H为校验矩阵 检查按收码字是否与H的各行正交 编译码方法提示 由前述 知道寻找到了G就可以解决便宜码的问题 那么G怎么找 由定义知道是找到K个线性无关的N重 问题 是否可以检测出所有的干扰 各个概念之间的关系 N维 矢量空间 K维子空间 基底 矩阵G 张成 线性组合构成 包含 监督码的增加方法有多种多样 不同的方法构成的码的特性各不相同 那么线性分组码的监督元增加的方法是 4 4线性分组码的编译码linealnormedcode 码字个数 若码字中有K位为消息码元 有R位监督码元 则码长n k r K位消息位可能取种不同的取值 因此这样的码的码字数目为个 按照码字监督元的监督范围分类 卷积码 监督范围超出本码字的消息 分组码 监督范围未超出本码字的消息 线性分组码定义 若一个分组码中的个码字 恰好是矢量空间V的一个K维子空间 称分组码为线性分组码 包含全0码 码字加法运算自封 问题转换 寻找线性分组码 寻找K维子空间 寻找行空间矩阵G 寻找K个线性无关的N重 根据线性分组码定义 根据行空间定义 根据G定义 得到线性分组码 与消息位线性组合 注意 如果K个线性无关的N重选择的不同 则生成的线性分组码不同 生成矩阵G的概念 根据式 4 14 选择K个线性无关的n重 以消息码元为函数进行组合 便生成一个 n k 线性分组码 因此有 4 4 2线性分组码的生成矩阵 2 写成分相形式 4 4 2线性分组码的生成矩阵 3 mG 4 15 称G为 n k 线性分组码的生成矩阵 结论 分析4 15 一旦生成矩阵G选定 n k 线性分组码也就唯一地确定了 举例 选取N 6 K 3 因此 在64个6重中选择三个线性无关的6重 如 100110 010011 001101 则按照与8个消息组线性组合 可以得到8个码字 这8个码字构成一个 6 3 线性分组码 系统码定义 生成的码字前k位是消息元 后r n k 位是监督元 这种形式的码称为系统码 满足系统码形式的线性分组码称为系统线性分组码 系统线性分组码生成 由前述知道 G一旦确定 则线性分组码便确定了 很显然 如果要找系统码 则需要找到一个特殊的G 这个特定的G可以生成的具有系统码特征的系统线性分组码 线性分组码 生成矩阵G 唯一确定 特殊生成矩阵G 唯一确定 系统线性分组码 具有特定性质 满足系统码性质 系统线性分组码的生成矩阵 如果生成矩阵G的前部分是k k的单位阵 由它生成的线性分组码为 将其计算展开 验证 前K位 很明显是消息位 后N K位 很明显是监督位 监督位是消息位的线性组合 满足系统线性分组码的定义 举例前述的例子 我们选取生成矩阵为 001101010011100110 单位阵 4 4 2线性分组码的生成矩阵 7 另外 任意一位监督元与消息元之间的关系由下面的一致校验方能确定 4 17 4 4 3线性分组码的一致校验矩阵 1 前述 对任何矩阵G 总存在矩阵H 使得G的行空间中的任意一个矢量和矩阵H的任一行正交 编码 对于某个生成矩阵G 可以得到码字 译码 对于某个码字 若H与码字正交 认为正确 否则认为受到了干扰 结论 对某一个编码来说 需要知道G和H Z这样就可以完成编译码工作了 一致校验矩阵H的确定 因此在确定了G之后 需要确定H 为正确译码提供依据 其关系是 注意G和H的维数 很显然 由G就可以得到H 由生成矩阵G得到一致校验矩阵H 100 p11p12 p1 n k 010 p21p22 p2 n k 00 pn1pn2 pk n k G 4 18 由生成矩阵G得到一致校验矩阵H 4 19 举例 还是 6 3 码 100110010011001101 101100110010011001 GH 4 4 4接收码字的伴随式 由一致校验矩阵H的定义可以知道 码字和H有下式成立 00 0 4 22 定义伴随式 考虑到错误图样 接收码字R为发送码字e和错误图样e的模之和 即 R c e 4 23 我们定义它为接收码字的伴随式S S RHT 4 24 4 4 4接收码字的伴随式 4 若错误图样e 00 0 则R C S RHT CHT 00 0 当E 00 0 时 S RHT c e HT CHT eHT eHT此时 只要错误图样E不等于线性分组码中的码字总有S eHT 00 0 接收码字的伴随式计算结果分析 当错误图样E和发送端的某一发送码字相同时 会使S eHT 0 出现错误判断结果 为什么 按照定义e c所以 eHT cHT 0因此 任何一种编码方法都不可能检测和纠正所有可能的错误 4 5循环码的编译码原理 循环码是线性分组码的一重要子类 在远动装置中被广泛的应用 举例 CDT规约中用的 48 40 码 40 32码 都是循环码 为何多用循环码 循环码有些便于工程实际的性质 循环码是线性分组码的子类 如果一个 N K 线性分组码 它的2K个码字中的任一码字的任何次循环移位 得到的任然是这个线性分组码中的码字 这个线性分组码称为循环码 在工程实际中 移位是很容易实现的 不论怎样的CPU 1 一定有移位指令 软件 2 一定有某个寄存器可以记录溢出位 硬件 4 5 1循环码的基本概念 2 码字C用码多项式表示 如下 4 25 乘以x并除以 xn 1 求其余式 4 5 1循环码的基本概念 3 余式恰是码字c循环移位一次后码字c 1 对应的码多项式c 1 x 可见将循环码的码字c循环左移一位 相当于将该码字的码多项式c x 乘以x并除以 xn 1 后所得的余式 加两个CN 1 4 5 1循环码的基本概念 4 同理可证 将码字c循环左移i次 相当于将码多项式c x 乘以xi并除以 xn 1 后所得余式 该余式为 4 27 由于xn 1 0mod xn 1 或xn 1mod xn 1 所以用xn 1为模作除法的物理意义就是在首尾相连的n级循环移位寄存器中作循环移位 将最高的溢出 次数 n的位 循环反馈至最低位上 为什么工程实际中需要 这些特性使循环码编码的实现伴随式的计算得以简化 译码 1 在一个 n k 循环码中 有一个并且只有一个n k次码的多项式g x 即 4 28 n k 循环码中的每一个码多项式c x 都是g x 的倍式 并且每个为g x 倍式的次数小于或等于 n 1 次的多项式 一定是一个码多项式 充分必要等价命题 性质一代数表示 由这一特性可知 n k 循环码中的每个码多项式c x 都可表示成 4 29 对消息m x 的编码相当于用消息m x 乘以g x 结论 所以多项式g x 确定了由2k个消息生成的2k个码字 我们称多项式g x 为循环码的生成多项式 与线性分组码对比 生成矩阵 生成多项式 校验矩阵 余式 4 5 1循环码的基本概念 7 2 n k 循环码的生成多项式g x 是xn 1的一个因式 即 4 30 3 若g x 是一个n k次多项式 且是xn 1的因式 则g x 生成一个 n k 循环码 性质分析 特性1可以生成一个NK循环码 必须首先找到生成多项式g x 它的次数为n k 特性2给出了寻找g x 的方法 码字生成 最后以这个n k次的因式为生成多项式 用它分别乘以2k个不同的消息 便可得到 n k 循环码的2k个码字 对比一般线性分组码 容易了 例 以 7 4 循环码为例 其生成过程如下 首先分解 找出次的因式 因为 所以要找的生成多项式 对消息多项式 取m3m2m1m0为十六种不同的序列 完成运算运算结果即为 7 4 循环码的十六个码字 N K 循环码的不唯一性 当我们从式子xn 1中分解n k次的因式时 有时分解方法不是唯一的 这时要找的生成多项式也就不是唯一的 如果用不同的生成多项式对2k个消息编码可以得到不同的码字 从而形成码字不同而码长和消息位相同的多个 n k 循环码 仍以 7 4 循环码为例 由于若选择可生成 7 4 循环码 再引入系统性质 循环码分为非系统循环码和系统循环码 实现非系统循环码的编码只要根据码长n和消息位k选定生成多项式g x 再完成m x g x 的乘法运算 便得到消息多项式m x 对应的循环码的码多项式c x 在信道译码时 要从非系统循环码的码字中得到消息位 不十分方便 因此 这种码使用较少 一般多采用系统循环码 其编码方法 n k 系统循环码的编码过程是 首先把消息多项式m x 乘以xn k 得到xn km x 然后以生成多项式g x 去除xn km x 如果商为q x 余式为r x 则xn km x q x g x r x 最后用r x 模2加xn km x 便得到所需的系统循环码码字c x xn km x r x 即系统循环码是一种消息位在前 监督位在后的结构 其编码方法验证 当我们把m x 乘以xn k时 消息多项式的变化是 4 31 对多项式中的消息位mi 原来是xi的系数 乘xn k后变成了xi n k的系数 x增加了n k次 由于消息多项式中x的次数代表消息元的位置 这样做等于把k个消息元的位置往前移动了n k位 且没有改变消息元的取值 同时在消息元的后面空出了n k个零位 以便补充监督元 其编码方法验证 用g x 去除xn km x 时 得到等式 4 32 只要在等式两边同时模2加余式r x 得到 4 33 其编码方法验证 明显看出 式 4 33 左边的多项式是生成多项式g的倍式 且次数小于或等于n 1次 根据前面叙述的循环码的特性1 它一定是 n k 循环码的码多项式 又因为xn km x 的最低次项是m0 xn k 余式r x 的最高次项是rn k 1xn k 1 所以式 4 33 左边的多项式可写成 4 34 4 5 2系统循环码的编译码原理 6 式 4 34 右边的多项式对应的n位序列 mk 1mk 2 m1m0rn k 1 r1r0 前k位是消息位 后 n k 位是余式的系数 于是这n位序列构成系统码结构的码字 因此 我们得到的是一个系统循环码的码字 4 35 译码 用生成多项式去除接收码字 检查余式是否为零 也就是检查接受码字是否是生成多项式的倍式 余式为零 认为接收码字是发送码字 余式不为零 认为接收码字是不发送码字 编码举例 仍以 7 4 码为例 设生成多项式 对消息进行系统循环码的编码 其过程如下 4 5 2系统循环码的编译码原理 9 由得 所以 1111111 当消息取十六种不同的值时 按同样方法生成的十六个系统循环码码字 与循环码相比 编码复杂了些译码简单多了 一致校验 信息提取 4 5 3缩短循环码 1 生成码长为n 消息位为k的循环码 依靠从中分解出一个n k次的因式作生成多项式 如果对于我们要求的码长n 和消息位k 在因式分解式中 不存在n k 的因式 则可用缩短循环码来产生我们需要的 n k 码 48 40 码 就是缩短循环码 由 127 120 码来 127 120 127 119 48 40 增余删信 缩短 为了理解缩短循环码 我们先观察一个 7 4 系统循环码的十六个码字 c m3m2m1m0r2r1r00000 xxx0001xxx0010 xxx0011xxx0100 xxx0101xxx0110 xxx0111xxx 1000 xxx1001xxx1010 xxx1011xxx1100 xxx1101xxx1110 xxx1111xxx 4 5 3缩短循环码 3 在2k 24 16个码字中 有的码字消息最高位m3 0 由于对消息编码时 消息中高位的零在计算中不起作用 所以它不影响余式 如果我们删去这8个码字最高位的零 可以得到8个码长为6的码字 构成一个 6 3 码 1 这个码的监督元位数和原来的 7 4 码相同 2 可以用原来 7 4 码的生成多项式g x 按同样的系统循环码的编码方法来生成 称这个 6 3 码为原来 7 4 系统循环码的缩短循环码 4 5 3缩短循环码 4 同理在16个码字中 有1 4的码字 2k 2 4 前两位消息为零 当删去这4个消息的前两位零时 得到4个码长为5的码字 构成一个 5 2 码 也称为原 7 4 系统循环码的缩短循环码 它的码长和消息位同时减少了二位 是 n 2 k 2 码 一般定义 一般来讲 在任何一个给定的 n k 系统循环码的2k个码字中 一定存在个前 位为零的码字 如果删去这个码字中前面 位零 可得个长为 n 的码字 由他们构成的 n k 线性系统码 称为原 n k 系统循环码的缩短循环码 缩短循环码的实质 由于缩短循环码只取了原系统循环码中的部分码字 并删去了码字前面的零 故缩短循环码的码字不再满足任一码字的任何次循环仍是这个码中的码字 所以它已不是循环码 那为什么还要用缩短循环码 缩短循环码删去的是原系统循环码码字前面的零 它不影响由消息生成码字时的运算过程和运算结果 所以缩短循环码可采用原系统循环码的编码电路 检纠错译码电路及编译码算法 它的检纠错能力不低于原来的 n k 系统循环码 缩短循环码的生成 前面我们要生成的 n k 码 如果在xn 1中不能分解出 n k 次的因式 可以另外找出一个n 使n n 并使其在xn 1中存在 n k 次的因式g x 另n n 我们可以先用g x 生成一个码长为n的码 因为g x 为 n k 次的因式 它生成的码监督元必为n k 位 故消息位 生成 n k 码 不能分解出 n k 次的因式 找不到g 生成 N K 码 N n K k 增加码长 缩短成 n k 码 4 6 1软件表算法一 1 n k 系统循环码对消息多项式m x 的编码就是求m x 的监督元 即求m x 除以g x 所得到的算式 可以表示为 4 36 4 37 4 6 1软件表算法一 2 设消息多项式m x 它对应的消息序列为m 按长度n k将消息序列分段 有m 其中都是长度等于n k的消息段 最后一个消息段位 这时消息多项式可以写成m x 4 38 4 6 1软件表算法一 3 其中为第i段消息的多项式 即必须注意的是每个分段的多项式的次数和原多项式在原消息序列中的多项式的次数相同 4 6 1软件表算法一 4 对m x 编码时 求余式的除法运算是 4 39 4 6 1软件表算法一 5 将 4 39 式各开得到的第一项是 4 40 其中运算为求多项式的次数的运算 4 6 1软件表算法一 6 将 4 39 式展开的第二项是 4 41 4 6 1软件表算法一 7 将 4 40 式中的第二项与 4 41 相加得 4 42 4 6 1软件表算法一 8 以此类推 4 39 式的第i项是 4 43 4 6 1软件表算法一 9 将 4 39 式第 i 1 相中含有余式的相 同 4 43 式相加得 4 44 4 6 1软件表算法一 10 4 39 式第p项与 p 1 项中含有余式的项相加得 4 45 4 6 1软件表算法一 11 可见 4 39 式的展开式之和是 4 6 1软件表算法一 12 4 46 4 6 1软件表算法 13 其中 4 6 1软件表算法一 14 由 4 46 式可以得到 系统循环码编码时 求除以g x 的余式可以采用对消息段分段求余式的方法 求消息段的余式时 除第一消息段直接用乘除以g x