数字通信原理8差错控制编码.ppt

2010 Copyright,课件,1,数字通信原理第八章 差错控制编码(线性分组码部分),2010 Copyright,课件,2,1、差错控制编码的基本原理 编码：在信息码组上附加一定位数的监督码元，使其与信息位按某种规则相互关联；检错与纠错：若数据在传输过程中发生差错，关联关系被破坏，从而可检出和/或纠正错误,第八章 差错控制编码,2010 Copyright,课件,3,2、差错控制主要类型 检错重发（ARQ）设备较简单；传输序列中冗余量较小；需要有反向信道支持；出错后重传造成延时较大。前向纠错（FEC）适用于包括没有反向信道的场合；出错时可纠正误码，无需重传，延时小；传输序列中冗余量较大。混合系统 前向纠错（FEC）检错重发（ARQ）出错较少时FEC起作用；出错较多时ARQ起作用,第八章 差错控制编码,2010 Copyright,课件,4,3、差错控制编码的分类 线性码：信息码与监督码之间的关系为线性关系；非线性码：信息码与监督码之间的关系为非线性关系。分组码：信息码与监督码以组为单位建立关系；卷积码：监督码与本组和前面码组中的信息码有关。系统码：编码后码组中信息码保持原图样顺序不变；非系统码：编码后码组中原信息码原图样发生变化。,第八章 差错控制编码,2010 Copyright,课件,5,4、错误的主要形式 随机错误：误码的位置随机（误码间无关联），随机误码主要由白噪声引起；突发错误：误码成串出现，主要由强脉冲及雷电等突发的强干扰引起；混合错误：以上两种误码及产生原因的组合；,第八章 差错控制编码,2010 Copyright,课件,6,5、检错与纠错编码的示例 三位二进制码的三种编码方法。三位二进码共有8种可能 的组合：000，001，010，011，100，101，110，111 a.若8个码组均用于表示不同的信息，任一位或一位以上的错 误都会变成另一码组，所以无法检错和纠错。b.若将8个码组分成许用和禁用(通信过程不会采用)两类：许用码组：000，011，101，110 禁用码组：111，100，010，001 因任何一位误码，都会变成禁用码组，所以可检出一位误码。c.若规定 许用码组：000，111 禁用码组：001，010，011，100，101，110 每个码组可携带1比特信息，码组具有检测出两位及以下 的误码，或纠正一位误码的能力。,第八章 差错控制编码,2010 Copyright,课件,7,6、香农信道编码定理 若信道容量为C，信息传输速率为R，如果 R C，则存在 编码方法，使错误概率 PE e-nEc(R)其中 EC(R)称为误差指数，n 为码组长度。(采用适当的方法增大n，有利于减小PE)。误差指数特性曲线：信道容量C作为曲线的 的参变量（包含了有关 S/N等因素的影响）,第八章 差错控制编码,2010 Copyright,课件,8,7、编码效率和冗余度 假定分组码的长度为n，其中信息位为k，相应的监督位为nk 编码效率定义为：冗余度定义为：通常冗余度越大，码的检错和纠错的能力越强。,第八章 差错控制编码,2010 Copyright,课件,9,8、几种常用的检错编码 奇偶校验码 在信息码组an-1,an-2,a1中加入监督位a0，使编码后码组中“1”的个数为奇数（奇校验）或偶数（偶校验）。偶校验：取a0，使下式成立 an-1an-2 a1 a0 0 a0=an-1an-2 a1 奇校验：取a0，使下式成立 an-1an-2 a1 a0 1 a0=an-1an-2 a1 1,第八章 差错控制编码,2010 Copyright,课件,10,奇偶效验码（续）奇偶效验码码组间最小距离dmin2 证明（以偶效验为例）：因为 an-1an-2 a1 a0 0 所以当码组中任一位aj发生错误时:aj/aj;an-1an-2/aja1 a0 1 至少可检出一位误码，故dmin大于或等于2。当有两位ai，aj发生误码时 an-1an-2/aj/sja1 a0 0 所以不能检出两位误码，故dmin小于或等于2。综上，dmin=2,第八章 差错控制编码,2010 Copyright,课件,11,奇偶效验码(续)编码效率为：k/nk/(k+1)；冗员度：1/(k+1)；k：信息位 奇偶效验码的检错能力：奇偶效验码能够检测出所有奇数个位数的错误；奇偶效验码不能检测出所有的偶数个位数的错误。一般地，若信道接收一个错误比特的概率为p，则n个比特长 的码组发生j个比特错误的概率为：其中 奇偶效验码不能检出的错误的概率为：,第八章 差错控制编码,2010 Copyright,课件,12,8、几种常用的检错编码(续)水平奇偶效验码 m个码组分别以各自码组为单位作奇效验或偶效验，然后以各 码组的最高位、次高位，依次发送：an-1 an-2 a1 a0 an-1 an-2 a1 a0 共m行 an-1 an-2 a1 a0 an-1 an-2 a1 a0 当突发的错误数小于m个时，每个码组中的误码个数小于2个 通过奇偶效验可以检出。,第八章 差错控制编码,2010 Copyright,课件,13,8、几种常用的检错编码(续)水平奇偶效验码（续前）整个方阵作为一个“码组”，长度为原来的m倍，可检出不大于 m个的突发错误;在未增加监督位的条件下，检错能力为原来的m倍，这是香农 信道编码定理应用的一个例子。编解码所付的代价：缓存空间和延时增大。,第八章 差错控制编码,2010 Copyright,课件,14,8、几种常用的检错编码(续)方阵码（水平垂直奇偶效验码）在水平奇偶监督码的基础上增加列的奇偶效验。可检出任一行和任一列的所有奇数个错误，及长度不大于 行数（按列发）或不大于列数（按行发）的突发错误。设原来的信息位构成MN的矩阵，加上监督位后构成（M1）（N1）的矩阵，编码效率为：,第八章 差错控制编码,2010 Copyright,课件,15,8、几种常用的检错编码(续)群计数码 计算码组中信息位“1”的个数，将计算值作为监督位，可检出 除“0”变“1”，“1”变“0”成对出现之外的所有错误。恒比码 从某确定长度的码组中挑选出那些“1”和“0”的比例为恒定值 的码组作为许用码组，当收到违反恒比特性的码组即可判为 误码。,第八章 差错控制编码,2010 Copyright,课件,16,9、线性分组码 基本定义 码重W：码组/码字中非零码元的数目；码距d（汉明(Hamming)距）：两码组/码字中对应码元位置上取值不同的个数称为码组/码字间的距离，简称码距；最小码距dmin：准用码组/码字空间中任两码组间的最小距离。,第八章 差错控制编码,2010 Copyright,课件,17,9、线性分组码 线性分组码的检错能力与码距的关系(1)要在一个码组中检出e个误码，要求 dmin e1 即任一码组产生小于等于e个误码时，都不会变成另一准用码组。图中，Ci和Cj是 两个准用码组,第八章 差错控制编码,2010 Copyright,课件,18,9、线性分组码 线性分组码的纠错能力与码距的关系(2)要在一个码组中能纠正t个误码，要求 dmin 2t1 将以t为半径的“球”内所有的禁用码组均判为球心中的准用 码组，可纠正t个以内的错误。图中，Ci和Cj是 两个准用码组,第八章 差错控制编码,2010 Copyright,课件,19,9、线性分组码 线性分组码的检错纠错能力与码距的关系(3)要在一个码组中能纠正t个误码，同时检出e(e t)个误码，要求 dmin et1 当误码数小于等于t时，可纠正；当误码数大于t小于等于e时，不会落入另一码组的纠错范 围内,第八章 差错控制编码,2010 Copyright,课件,20,9、线性分组码 线性分组码的基本性质(定理)(1)两许用码组之和（逐位模2和）仍为一许用码组（封闭性）；(2)码组间的最小距离等于非零码的最小重量。,第八章 差错控制编码,2010 Copyright,课件,21,9、线性分组码 线性分组码的数学基础(1)群的概念 若G是非空集合，在G中定义了一种代数运算，满足（a）封闭性，对 a、b G，恒有 ab G（b）结合律，对 a、b、c G，恒有（ab）c a（bc）（c）有恒等元e存在，对 a G，有 e G，使 aeeaa（d）对 a G，有逆元 a-1 G，使 aa-1 a-1ae 则称G构成一个群。,第八章 差错控制编码,2010 Copyright,课件,22,9、线性分组码 线性分组码的数学基础(2)矢量空间的概念 在群G中，若 a、b G，恒有 abba，则称G为交换群或阿贝尔群。在阿贝尔群G中定义F域上的数乘、且分配率成立，a、b G，A F，有 A（ab）AaAb则称该群为矢量空间V。,第八章 差错控制编码,2010 Copyright,课件,23,9、线性分组码 线性分组码的数学基础(2)矢量空间的概念(续)矢量子空间 矢量空间V中的一个子集S，若满足：全0矢量（恒等元e）在S中；S中的任意两个矢量的和（运算“”）也在S中（封闭性）；则称S为子空间。,第八章 差错控制编码,2010 Copyright,课件,24,9、线性分组码 线性分组码的数学基础(3)n维线性空间 一个由2n个n维二进制数组组成的集合，定义如下的加乘运算 则该集合构成一n维线性空间Vn。,第八章 差错控制编码,2010 Copyright,课件,25,9、线性分组码 线性分组码的数学基础(4)子空间与线性分组码 在2n个n维二进制数组中可选择2k个数组构成Vn上的子空间，子空间上的元素构成线性分组码。,第八章 差错控制编码,2010 Copyright,课件,26,线性分组码的数学基础(续)(4)子空间与线性分组码 子空间S的选择：a、包含尽可能多的可用码字(组)，编码效率高，冗余度小；b、可用码字(组)间的距离尽可能大，使有较大的容错性能。线性空间Vn和其子空间S的形象表示。,第八章 差错控制编码,2010 Copyright,课件,27,9、线性分组码 线性分组码示例 例1：4维线性空间V4及其子空间S V4的所有元素 V4空间的一个子空间 容易验证它包含“0”元素(0000),且满足按位求和运算 的封闭性。,第八章 差错控制编码,2010 Copyright,课件,28,9、线性分组码 线性分组码示例 例2：（6，3）线性分组码 可以验证：对3位的信息码组采用如下6为的码字集编码，该码字集构成一线性子空间。,第八章 差错控制编码,2010 Copyright,课件,29,9、线性分组码 生成矩阵G的概念 选择线性空间V中k个线性无关(独立)的n元组：V1,V2,V3,Vk 以此为基构成所有2k个线性组合S可以表示为：其中mi0或1。显然，S是V的一个子空间。记 则有 矩阵G称为生成矩阵。,第八章 差错控制编码,2010 Copyright,课件,30,9、线性分组码 生成矩阵G的概念(续)例：利用矩阵G计算（许用）码字，已知生成矩阵 编码前的信息码组为110，生成的码字为：,第八章 差错控制编码,2010 Copyright,课件,31,9、线性分组码 生成矩阵的构建、监督矩阵和伴随式(校正子)例：具有纠正一位误码的分组码 C6C5C4C3 C2C1C0 n=7,k=4,信息位 监督位 r=nk3 传输过程中如果发生某一位错误，如在C3位置出错，则相当于 C6C5C4C3C2C1C0000E3000=C6C5C4(C3E3)C2C1C0 其中：E31 定义一组确定误码位置的参量:校正子/伴随式 S1S2S3,第八章 差错控制编码,2010 Copyright,课件,32,9、线性分组码 生成矩阵的构建、监督矩阵和伴随式(续)设建立1位误码与校正子的对应关系如下（亦可建立其它关系）由表格关系，校正子与误码Ei的关系，如表中的S1，当 E2、E4、E5、E6中有一个为1时，S11；S1E6E5E4E2 同理可得，S2E6E5E3E1 S3E6E4E3E0,第八章 差错控制编码,2010 Copyright,课件,33,9、线性分组码 生成矩阵的构建、监督矩阵和伴随式(续)由此，当出现一位误码时，校正子能够确定误码的位置。当无误码时，显然有 S1E6E5E4E20 S2 E6E5E3E10 S3E6E4E3E00 编码时,通过选择监督位C0C1C2的取值来保证正常情况下：S1C6C5C4C20 S2C6C5C3C10 S3C6C4C3C00 上述方程亦称为监督方程。(*)由监督方程可以解得，监督位C0C1C2的取值分别为：C0 C6C4C3 C1C6C5C3 C2C6C5C4 给出一组信息码C6C5C4C3，可计算出监督位C2C1C0。构成码：C6C5C4C3C2C1C0。注意：信息位与监督位间的关系为线性关系。,第八章 差错控制编码,2010 Copyright,课件,34,9、线性分组码 生成矩阵的构建、监督矩阵和伴随式(续)例（续前）：设信息码组C6C5C4C30101 C2C6C5C4 0101 C1C6C5C3 0110 C0C6C4C3 0011 构成发送码字：C6C5C4C3 C2C1C0 0101101 发送码字01011101，若接收时有一位，如C5，出错：C6(C5E5)C4C3 C2C1C00001101 S1C6(C5E5)C4C200011(C6C5C4C2)E5 S2C6(C5E5)C3C100101(C6C5C3C1)E5 S3C6C4C3C0 00000(C6C4C3C0)根据校正子 S1 S2 S3110，由表，可判断误码发生在C5,第八章 差错控制编码,2010 Copyright,课件,35,9、线性分组码 生成矩阵的构建、监督矩阵和伴随式 前述的监督方程可用矩阵形式表示 其一般形式为：un-1un-2u1u0是发送码字/码组，矩阵H称为监督矩阵。,第八章 差错控制编码,2010 Copyright,课件,36,9、线性分组码 生成矩阵的构建、监督矩阵和伴随式(续)对上例，观察P37（*）式（监督方程），有：S1C6C5C4C20S2C6C5C3C10 S3C6C4C3C00 方程组的矩阵表示形式为：,第八章 差错控制编码,2010 Copyright,课件,37,9、线性分组码 生成矩阵的构建、监督矩阵和伴随式 其中，监督矩阵H为：校正子与误码的位置的关系 由H的列向量反映 监督矩阵的性质：（a）H由码元间的监督关系唯一确定；（b）H的行向量相互独立，当采用系统码结构时，具有形式，其中Ir是rr（rn-k）单位阵。,第八章 差错控制编码,2010 Copyright,课件,38,9、线性分组码 生成矩阵的构建、监督矩阵和伴随式 在上例中，监督位的产生可表示为 一般地，对于线性分组码(n，k)，上述关系可表示为 其中监督位 rnk：,第八章 差错控制编码,2010 Copyright,课件,39,9、线性分组码 生成矩阵的构建、监督矩阵和伴随式 监督位矩阵的转置表达式为：若将信息位排列在码组的前半部，监督排列在码组的后半部，则有：生成矩阵可定义为：其中Ik是kk的单位阵。系统码形式的发送码组可按下式产生,第八章 差错控制编码,2010 Copyright,课件,40,9、线性分组码 生成矩阵的构建、监督矩阵和伴随式 生成矩阵G与监督矩阵H之间的关系 监督位矩阵可表示为：生成矩阵可表示为：其中Ik是kk的单位阵，In-k是(n-k)(n-k)的单位阵 由此得 上述关系说明：生成矩阵的每一行都是一个有效的码字。,第八章 差错控制编码,2010 Copyright,课件,41,9、线性分组码 生成矩阵的构建、监督矩阵和伴随式 伴随式(校正子)的定义 设 发送码字为 接收码字为 错误图样为 则一般地，有 接收码字r的伴随式(校正子)定义为,第八章 差错控制编码,2010 Copyright,课件,42,9、线性分组码 生成矩阵的构建、监督矩阵和伴随式 由前面分析，有 其中H的第i列对应第i位单个错误时的伴随式/校正子 伴随式只与错误图样和监督矩阵有关，与发送的码字无关。上式中e是1n的矩阵，而H是rn的矩阵，所得结果 S是二进制数的1r的矩阵（向量），所有可能组合的个数为 若用伴随式的不同组合表征不同的错误，则最多能够表 征（纠正）2r2n-k个错误。,第八章 差错控制编码,2010 Copyright,课件,43,9、线性分组码 线性分组码的许用码字与可纠正的错误图样 对于线性分组码（n，k）所有许用码字和可纠正 的错误图样及组合可表示为一标准阵：其中U1是许用码字集中的全0码字。第一行为无误码的许用 码字；第一列（除全零元素的向量U1外）为所有可纠正的错 误图样，称为陪集首。每一行称为一个陪集。,第八章 差错控制编码,2010 Copyright,课件,44,9、线性分组码 陪集的伴随式 陪集中的每一个元素均有相同的伴随式。任一陪集可表示为 相应的伴随式为：陪集首中每一种错误图样，对应于一个特定的伴随式。因此，可用伴随式来进行错误定位。,第八章 差错控制编码,2010 Copyright,课件,45,9、线性分组码 纠错码的译码步骤 根据收到的r和H计算接收码字的伴随式：根据S定位错误图样ej 由得到的错误图样ej进行纠错：注：如果出现的错误图样不在陪集首内，则不能正确地 定位错误（超出该种编码方法能够纠错的范围）。,第八章 差错控制编码,2010 Copyright,课件,46,9、线性分组码 线性分组码的纠错示例：例 线性分组码（6，3）标准阵：其伴随式为：查询表：,第八章 差错控制编码,2010 Copyright,课件,47,9、线性分组码 线性分组码的纠错示例：例 线性分组码（6，3）设 发送码字为：101110 接收码字为：001110 伴随式：S001110HT100 根据查询表（或监督矩阵），得 错误图样为：100000 差错恢复计算：Ure001110+100000101110,第八章 差错控制编码,2010 Copyright,课件,48,9、线性分组码 线性分组码的纠错示例：例 线性分组码（6，3）译码器的实现 已知译码器的伴随式为：即有：由此，结合伴随式查询表，可构建相应的译码电路。,第八章 差错控制编码,2010 Copyright,课件,49,9、线性分组码 线性分组码的纠错示例：例 线性分组码（6，3）译码器的译码电路,第八章 差错控制编码,2010 Copyright,课件,50,9、线性分组码 线性分组码具有封闭性：任两码组按位之和仍是一个码组。设任 Ci，Cj C（许用码组集合），G为生成矩阵，则 式中 是码组中的信息码部分。任两码组之和：因为：所以 所以,第八章 差错控制编码,2010 Copyright,课件,51,9、线性分组码 线性分组码的最小距离dmin等于非零码组最小重量W 即若记 Wi为Ci的码重，则 因为按定义 又因为 由线性分组码的封闭性，有 所以显然有：,第八章 差错控制编码,2010 Copyright,课件,52,9、线性分组码 汉明界 线性分组码（n,k）能纠正任意的t个错误的必要条件：陪集数/伴随式个数：不等式的左边为伴随式的总数；不等式的右边为所有可能的小于等于t的错误的总的个数。例 线性分组码（127，106）所需的陪集数(由上式可得),第八章 差错控制编码,2010 Copyright,课件,53,9、线性分组码 完备码 能纠正任意的t个错误的线性分组码（n,k）若满足条件：则称该码为完备码(perfect code),第八章 差错控制编码,2010 Copyright,课件,54,9、线性分组码 普洛特金界 线性分组码（n,k）的最小码距dmin小于某一上界：该界称为普洛特金界。例 a.判断线性分组码（7,2）有无纠正任意2个错误的可能 因 所以不可能。b.判断线性分组码（8,2）有无纠正任意2个错误的可能 因 所以有可能。,第八章 差错控制编码,2010 Copyright,课件,55,9、线性分组码 汉明码 能够纠正1位误码，且满足下列条件 的线性分组码，称为汉明码。例：可验证如下监督矩阵对应的线性分组码是汉明码 或,第八章 差错控制编码,2010 Copyright,课件,56,9、线性分组码 汉明码的特点：码字的最小距离为3，能纠正单个的错误(t=1)；汉明码是一种完备码，因为：而 满足完备性条件：汉明码的编码效率,第八章 差错控制编码,2010 Copyright,课件,57,9、线性分组码 生成矩阵的变换 在线性分组码(n,k)的码字集(子空间)中，如果能够找到k个线性无关的码字，即可构成生成矩阵；简单地由k个线性无关的码字构成的生成矩阵未必是系统码生成矩阵；通过矩阵变换可将非系统码的生成矩阵变换成系统码生成矩阵；生成矩阵的变换并不改变码字集中码字的图样，仅仅改变码字集中码字与信息码组的对应关系。,第八章 差错控制编码,2010 Copyright,课件,58,9、线性分组码 生成矩阵的变换(续)例：已知线性分组(7,4)中4个线性无关的码字：1011000，0010110，0101100，0001011 求关于该码字集的系统码生成矩阵和监督矩阵。解：该3码字构成的生成矩阵可表示为 非 或 形式，所以为非系统码生成矩阵。,第八章 差错控制编码,2010 Copyright,课件,59,9、线性分组码 解(续)：对生成矩阵做线性变化，使其左侧成为标准阵，得到新的生成矩阵,第八章 差错控制编码,2010 Copyright,课件,60,9、线性分组码 解(续)：该码的生成矩阵具有系统码生成矩阵的形式 相应地监督矩阵为,2010 Copyright,课件,61,10、循环码 循环码的基本概念 定义 对线性分组码U，如对任意 Ui U，Ui 循环左移或循 环右移任意位后得到的码组Ui 仍然有Ui U，则称U 为循环码。码多项式 为用代数理论研究循环码，可将码组用多项式表示，多 项式称为码多项式。一般地，长为n的码组Un-1Un-2U1U0，对应码多项式U(X)式中，Xi系数对应码字中第i位，Ui，的取值。,第八章 差错控制编码,2010 Copyright,课件,62,10、循环码 循环码的基本概念（续）例：（7,3）码字：1001110 对应 x6x3x2x 对二进制码组，U(x)的系数只在二元域上取值。二元域上加、乘运算规则如下：加运算：乘运算：减法和除法可由加法和乘法定义。,第八章 差错控制编码,2010 Copyright,课件,63,10、循环码 同余类的概念 在整数除法中，取定除数n，可将所有整数按除以n所得余 数进行分类，余数相同的数称为关于n的同余类。一般地，若（Q为整数，p n）则记为：所有余数为p的整数属于关于模n的一个同余类。,第八章 差错控制编码,2010 Copyright,课件,64,10、循环码 同余类的概念（续前）类似地，可以定义关于多项式N(x)的同余类，若 式中Q(x)为整式，余式R(x)的幂 N(x)的幂。上式可写成：记为：例：在系数为二元域的多项式中，有 因为：从而有上述结论。,第八章 差错控制编码,2010 Copyright,课件,65,10、循环码 循环码的代数结构 定理1 若U(X)是长度为n的循环码中的一个码多项式，则 XiU(X)（i为不等于0的整数）按模 Xn1运算的余 式必为循环码中的另一码多项式。证明：设i1，有,第八章 差错控制编码,2010 Copyright,课件,66,10、循环码循环码的代数结构（续）余式为 对应码组un-1 un-2 u1 u0左循环一位之后的得到的码组：un-2 u1 u0 un-1。若i2,第八章 差错控制编码,2010 Copyright,课件,67,10、循环码 循环码的代数结构（续）显然，余式为对应码组un-1un-2u1u0左循环两位之后的得到的 码组。一般地，对任意i有：余式对应un-1un-2u1u0左循环i位之后的得到的码组。证毕(容易用归纳法严格证明),第八章 差错控制编码,2010 Copyright,课件,68,10、循环码 循环码的代数结构（续）例 已知码组的长度为n4，其中一码字：U1101(高位在右)，求该码字循环移位3位后得到的码字。a.由1101直接(右)循环移3位得：U(3)1011 b.根据多项式关系求解，当i3时，关于X4+1的余式U(3)(X)-1011,第八章 差错控制编码,2010 Copyright,课件,69,10、循环码 循环码的生成多项式g(x)及生成矩阵 一般地，线性分码组可表示为矩阵G中每一行均为一许用码组，如第i行对应第i个信息位为1，其余为0时的信息码生成的码组。由于G中包含一个Ik分块，所以G为k个独立的码组组成的矩阵。即：任一线性分组码码组均可由k个线性无关的码组组合而成。,第八章 差错控制编码,2010 Copyright,课件,70,10、循环码 循环码的生成多项式g(x)及生成矩阵(续)利用上述线性分组码任一线性分组码码组均可由k个线性无关的码组组合而成 这一性质，寻求循环码生成矩阵的构建方法。设存在一个幂次数为nk，且常数项不为0的码多项式g(X)，则由循环码的性质（定理1）g(X)，Xg(X),，Xk-2g(X)，Xk-1g(X)(最高次幂等于n1)也是码多项式，这k个码多项式对应独立的k个码字，由此可构 成循环码生成矩阵G(X)。,第八章 差错控制编码,2010 Copyright,课件,71,10、循环码 循环码的生成多项式g(X)及生成矩阵(续)循环码生成矩阵G(X)：其中，g(X)称为循环码码生成多项式。G(X)对应的系数矩阵G 右侧的子方阵具有主对角线元素均不为0的形式。该子阵行列 式不为0，因而子阵满秩，因而行向量是线性无关的。利用码生成矩阵G(X)，任一码字多项式可以表示为：或：,第八章 差错控制编码,2010 Copyright,课件,72,10、循环码 循环码的生成多项式g(X)及生成矩阵(续)例（7，3）生成多项式 g(X)X4+X3+X2+1 对应生成矩阵GX 矩阵为：因为矩阵G左侧的子方阵满秩，因此容易判断该矩阵中的 行向量是线性无关的。,第八章 差错控制编码,2010 Copyright,课件,73,10、循环码 循环码的生成多项式g(X)及生成矩阵(续)定理 2 在循环码中，nk次的码多项式g(X)有一个且只有 一个。证明：（a）在含k个信息位的循环码中，除全0码外，其它码 组最多只有k-1个连0。否则，经循环移位后前面k个信息码 元为0，而监督码元不全为0的码组，这在线性分组码中是不 可能的。所以一定有一个nk次的多项式。（b）nk次的码多项式g(X)的常数项不能为0，否则 该多项式右移一位就会出现k个连0的情况。,第八章 差错控制编码,2010 Copyright,课件,74,10、循环码 循环码的生成多项式g(X)及生成矩阵(续)（c）nk次的码多项式g(X)只可能有一个，若有两个，两多项式相加后由线性分组码的封闭性仍为码多项式，但 由于nk次项和常数项相消，会产生k1连0的情况，由（a）分析，这是不可能的。综上（a）、（b）和（c），证毕。,第八章 差错控制编码,2010 Copyright,课件,75,循环码的生成多项式g(X)及生成矩阵(续)定理 3 在循环码中，所有的码多项式U(x)都能够被g(X)整除。证明：因为任一码多项式都可由其信息码元和生成矩阵 Gx确定：g(X)为码多项式U(x)的一个因式，所以U(x)可被g(X)整除。证毕,第八章 差错控制编码,2010 Copyright,课件,76,10、循环码 循环码的生成多项式g(X)及生成矩阵(续)推论：次数不大于k1次的任何多项式与g(X)的乘积都是 码多项式。,第八章 差错控制编码,2010 Copyright,课件,77,循环码的生成多项式g(x)及生成矩阵(续)定理 4 循环码（n，k）的生成多项式g(X)是Xn1的一个因式。证明：因为g(X)幂为nk，因而可得 其中R(X)的幂小于n。由定理1，R(X)是码多项式，又由定理3 有R(X)=m(X)g(X)，即有 移项整理得：即g(X)是Xn1的一个因式。证毕,第八章 差错控制编码,2010 Copyright,课件,78,循环码的生成多项式g(x)及生成矩阵(续)称 为循环码的一致效验多项式。对任一码多项式，U(X)m(X)g(X)，有 h(X)U(X)=h(X)m(X)g(X)=h(X)g(X)m(X)=(Xn+1)m(X)即若U(X)是许用码组对应的多项式，其乘积h(X)U(X)一定可 被Xn1整除。生成多项式g(X)的三个性质（充要条件）：（a）g(X)是nk次多项式；（b）g(X)的常数项不等于0；（c）是Xn1的一个因式。,第八章 差错控制编码,2010 Copyright,课件,79,10、循环码循环码的生成多项式g(x)及生成矩阵(续)采用前面定义的循环码生成矩阵：对应的系数矩阵G一般不符合 GIk,Q 形式。编码输出结果相当于m(x)g(x)，所得码组为非系统 码结构，获得信息码需要查对应的码表进行译码。,第八章 差错控制编码,2010 Copyright,课件,80,10、循环码 循环码的生成多项式g(x)及生成矩阵(续)例：线性分组码（7，4）生成多项式 g(x)x3+x2+1 对应 生成矩阵Gx对应的系数矩阵为：为非系统码结构的生成矩阵。,第八章 差错控制编码,2010 Copyright,课件,81,10、循环码 系统码结构循环码的编码方法 a.以Xn-k乘信息多项式m(X)，m(X)Xn-k m(X)(幂 n)b.用g(X)除Xn-k m(X)得余式p(X)(幂 n-k)即 Xn-k m(X)q(X)g(X)+p(X)，q(X)的幂次数小于k 取码多项式 U(X)=Xn-k m(X)+p(X)（*）分析上述编码方式的合理性：U(X)=Xn-k m(X)+p(X)q(X)g(X)+p(X)+p(X)=q(X)g(X)因为q(X)的幂次数小于k，由定理3推论，q(X)g(X)一定是循 环码的码多项式，显然（*）定义的U(X)为一种系统码结构的 循环码。,第八章 差错控制编码,2010 Copyright,课件,82,10、循环码 循环码编码器的电路实现 由系统码结构循环码的编码方法可知 循环码编码器的实现需要用到以生成多项式g(x)为除式的 除法器计算余式p(x):,第八章 差错控制编码,2010 Copyright,课件,83,10、循环码 循环码编码器的电路实现(续)多项式除法 多项式除法可用带反馈的移位寄存器实现。例：除数为 g(X)X6X5X4X31 除法电路 如下图，反馈的接入由g(X)确定 除法运算的实现 先将移位寄存器清“0”；进行n次移位，将被除数全部送入除法器后，在寄存 器内即可得到相应的余式。,第八章 差错控制编码,2010 Copyright,课件,84,10、循环码 循环码编码器的电路实现(续)(接上例)计算C(X)/g(X)，其中C(X)=X13+X11+X10+X7+X4+X3+X+1 得余式：p(x)x4x2（容易通过长除法验证）,第八章 差错控制编码,2010 Copyright,课件,85,10、循环码 循环码编码器的电路实现(续)多项式除法电路的一般形式 被除式：除式：相应实现电路：,第八章 差错控制编码,2010 Copyright,课件,86,10、循环码 循环码编码器的电路实现(续)多项式除法电路的缺点 除法运算在移位进行了n-k-1位后才开始，运算完成后，要将余式移出，还要做n-k-1次移位。速度较慢。,第八章 差错控制编码,2010 Copyright,课件,87,10、循环码 实际应用的循环码编码电路特点：采用“预先乘Xn-k方案”（信号直接到达最后一级），边移位边做除法运算，当k个信息码输入后，同时完成了除法运算。g(X)=X4+X3+X2+1（a）当信息位输入时，开关K1、K2合下，k个信息位经K2逐位输出，同时直接送到最高位做除法，其运算等效为：,第八章 差错控制编码,2010 Copyright,课件,88,10、循环码 实际应用的循环码编码电路特点：采用“预先乘Xn-k方案”（信号直接到达最后一级），边移位边做除法运算，当k个信息码输入后，同时完成了除法运算。g(X)=X4+X3+X2+1（a）当信息位输入时，开关K1、K2合下，k个信息位经K2逐位输出，同时直接送到最高位做除法，其运算等效为：,第八章 差错控制编码,2010 Copyright,课件,89,实际应用的循环码编码电路（b）当信息位全部输入后，相应除法运算完成，开关K1、K2合上，将余数顺序输出。例：设m(X)=X2X1 111，Xn-kX73X4，Xn-km(X)X6X5X4 1110000 商为：100，余数为：0100 上述运算也可看作下列分别运算的结果：商为：110011001 100（按位相加）余数：111001111101 0100,第八章 差错控制编码,2010 Copyright,课件,90,10、循环码 实际应用的循环码编码电路 一般形式的（nk）移位寄存器编码电路，设 则：总的所需的移位次数为n。,第八章 差错控制编码,2010 Copyright,课件,91,10、循环码 循环码译码电路 循环码的译码过程 由收到的多项式r(X)计算伴随式多项式S(X)：S(X)r(X)/g(X)由S(X)确定误码的错误图样E(X)；（无误码时显然有S(x)=0）将E(X)与r(X)相加，纠正错误（若在纠错范围内）。一般地，对矩阵形式的线性分组码，校正子S为：对于循环码，校正子对应的多项式S(x)为：,第八章 差错控制编码,2010 Copyright,课件,92,10、循环码 循环码译码电路(续)纠错译码步骤 a.计算S(X)r(X)/g(X)b.确定错误图样S(X)E(X)c.根据E(X)纠错。,第八章 差错控制编码,2010 Copyright,课件,93,循环码译码电路 除法电路的性质 某码组循环移位i次后所得码组的伴随式等于原码组伴随式在 除法电路中循环移位i次所得的结果。设Si(x)为收到的多项式r(x)循环移位i次后计算得到的伴随式：（1）因为：上式两边乘以Xi，有：对比（1）式，得：上式说明，若r(X)中的错误图样E(X)对应的伴随式为S(X)，则 Xir(X)中错误图样XiE(X)对应的伴随式为XiS(X)mod(g(X)。,第八章 差错控制编码,2010 Copyright,课件,94,循环码译码电路(续)除法电路的性质利用上述性质可得：某个可纠正的错误图样E(x)的i次循环移位 XiE(x)必定也是可以纠正的错误图样，其伴随式为：XiS(X)mod(g(X)(*)从而可把E(x)，XE(x)，XiE(x),规为一类，只要知道E(X)的伴随式S(X)，其余循环移位错误对应的伴随式可由(*)式产生。同样，若已知错误图样XiE(x)对应的伴随式Si(X)，则错误图样 E(x)对应的校正子S(X)经循环移i位后变为Si(X)。因此，只要记住一种伴随式和所对应的错误图样，就能纠正该错误图样及其循环移位所对应的其它错误。,第八章 差错控制编码,2010 Copyright,课件,95,10、循环码 纠正单个错误的译码电路 当用于纠正单个错误时，只需要记住一个错误图样。E(x)识别电路可用简单的逻辑电路来实现。例：已知 线性分组码（7，3）：g(x)x4x3x21 错误图样(H)0000001(L)S：(H)0001(L)在电路中右移1位得 错误图样：0000010 S：0010 0100 错误图样：0000100 S：0100 1000 错误图样：0001000 S：1000 1101 错误图样：0010000 S：1101 0111 错误图样：0100000 S：0111 1110 错误图样：1000000 S：1110 由下往上分析，可得下面的结果：,第八章 差错控制编码,2010 Copyright,