数字通信原理8差错控制编码课件

数字通信原理第八章差错控制编码

(线性分组码部分)2010Copyright1课件1、差错控制编码的基本原理

编码：在信息码组上附加一定位数的监督码元，使其与信息位按某种规则相互关联；

检错与纠错：若数据在传输过程中发生差错，关联关系被破坏，从而可检出和/或纠正错误第八章差错控制编码2010Copyright2课件2、差错控制主要类型

检错重发（ARQ）

设备较简单；传输序列中冗余量较小；需要有反向信道支持；出错后重传造成延时较大。前向纠错（FEC）

适用于包括没有反向信道的场合；出错时可纠正误码，无需重传，延时小；传输序列中冗余量较大。混合系统

前向纠错（FEC）＋检错重发（ARQ）

出错较少时FEC起作用；出错较多时ARQ起作用第八章差错控制编码2010Copyright3课件4、错误的主要形式

随机错误：误码的位置随机（误码间无关联），随机误码主要由白噪声引起；

突发错误：误码成串出现，主要由强脉冲及雷电等突发的强干扰引起；

混合错误：以上两种误码及产生原因的组合；第八章差错控制编码2010Copyright5课件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比特信息，码组具有检测出两位及以下的误码，或纠正一位误码的能力。第八章差错控制编码2010Copyright6课件6、香农信道编码定理

若信道容量为C，信息传输速率为R，如果R<C，则存在编码方法，使错误概率

PE

e-nEc(R)

其中EC(R)称为误差指数，n为码组长度。(采用适当的方法增大n，有利于减小PE)。误差指数特性曲线：信道容量C作为曲线的的参变量（包含了有关

S/N等因素的影响）第八章差错控制编码2010Copyright7课件8、几种常用的检错编码

奇偶校验码在信息码组an-1,an-2,…,a1中加入监督位a0，使编码后码组中“1”的个数为奇数（奇校验）或偶数（偶校验）。

偶校验：取a0，使下式成立

an-1an-2…a1a0＝0a0=an-1an-2…a1

奇校验：取a0，使下式成立an-1an-2…a1a0＝1a0=an-1an-2…a11第八章差错控制编码2010Copyright9课件奇偶效验码（续）奇偶效验码码组间最小距离dmin＝2

证明（以偶效验为例）：因为an-1an-2…a1a0＝0

所以当码组中任一位aj发生错误时:aj

/aj;an-1an-2…/aj…a1a0＝1

至少可检出一位误码，故dmin大于或等于2。当有两位ai，aj发生误码时

an-1an-2…/aj…/sj…a1a0＝0

所以不能检出两位误码，故dmin小于或等于2。综上，dmin=2

第八章差错控制编码2010Copyright10课件奇偶效验码(续)编码效率为：k/n＝k/(k+1)；冗员度：1/(k+1)；k：信息位

奇偶效验码的检错能力：

奇偶效验码能够检测出所有奇数个位数的错误；奇偶效验码不能检测出所有的偶数个位数的错误。一般地，若信道接收一个错误比特的概率为p，则n个比特长的码组发生j个比特错误的概率为：其中

奇偶效验码不能检出的错误的概率为：第八章差错控制编码2010Copyright11课件8、几种常用的检错编码(续)

水平奇偶效验码（续前）

整个方阵作为一个“码组”，长度为原来的m倍，可检出不大于m个的突发错误;在未增加监督位的条件下，检错能力为原来的m倍，这是香农信道编码定理应用的一个例子。编解码所付的代价：缓存空间和延时增大。第八章差错控制编码2010Copyright13课件8、几种常用的检错编码(续)

方阵码（水平垂直奇偶效验码）在水平奇偶监督码的基础上增加列的奇偶效验。可检出任一行和任一列的所有奇数个错误，及长度不大于行数（按列发）或不大于列数（按行发）的突发错误。

设原来的信息位构成M×N的矩阵，加上监督位后构成（M＋1）×（N＋1）的矩阵，编码效率为：第八章差错控制编码2010Copyright14课件8、几种常用的检错编码(续)

群计数码计算码组中信息位“1”的个数，将计算值作为监督位，可检出除“0”变“1”，“1”变“0”成对出现之外的所有错误。

恒比码从某确定长度的码组中挑选出那些“1”和“0”的比例为恒定值的码组作为许用码组，当收到违反恒比特性的码组即可判为误码。第八章差错控制编码2010Copyright15课件9、线性分组码

线性分组码的检错能力与码距的关系(1)要在一个码组中检出e个误码，要求

dmin

e＋1

即任一码组产生小于等于e个误码时，都不会变成另一准用码组。图中，Ci和Cj是两个准用码组第八章差错控制编码2010Copyright17课件9、线性分组码线性分组码的纠错能力与码距的关系(2)要在一个码组中能纠正t个误码，要求

dmin

2t＋1

将以t为半径的“球”内所有的禁用码组均判为球心中的准用码组，可纠正t个以内的错误。图中，Ci和Cj是两个准用码组第八章差错控制编码2010Copyright18课件9、线性分组码线性分组码的检错纠错能力与码距的关系(3)要在一个码组中能纠正t个误码，同时检出e(et)个误码，要求

dmin

e＋t＋1

当误码数小于等于t时，可纠正；当误码数大于t小于等于e时，不会落入另一码组的纠错范围内第八章差错控制编码2010Copyright19课件9、线性分组码

线性分组码的数学基础(1)群的概念若G是非空集合，在G中定义了一种代数运算＋，满足（a）封闭性，对

a、bG，恒有a＋bG（b）结合律，对

a、b、cG，恒有（a＋b）＋c＝a＋（b＋c）（c）有恒等元e存在，对

aG，有eG，使

a＋e＝e＋a＝a（d）对

aG，有逆元a-1

G，使

a＋a-1

＝a-1＋a＝e

则称G构成一个群。第八章差错控制编码2010Copyright21课件9、线性分组码

线性分组码的数学基础(2)矢量空间的概念在群G中，若

a、bG，恒有a＋b＝b＋a，则称G为交换群或阿贝尔群。在阿贝尔群G中定义F域上的数乘、且分配率成立，

a、bG，

AF，有

A（a＋b）＝Aa＋Ab则称该群为矢量空间V。第八章差错控制编码2010Copyright22课件9、线性分组码

线性分组码的数学基础(2)矢量空间的概念(续)

矢量子空间矢量空间V中的一个子集S，若满足：全0矢量（恒等元e）在S中；

S中的任意两个矢量的和（运算“＋”）也在S中（封闭性）；

则称S为子空间。第八章差错控制编码2010Copyright23课件9、线性分组码

线性分组码的数学基础(4)子空间与线性分组码

在2n个n维二进制数组中可选择2k个数组构成Vn上的子空间，子空间上的元素构成线性分组码。第八章差错控制编码2010Copyright25课件线性分组码的数学基础(续)(4)子空间与线性分组码

子空间S的选择：

a、包含尽可能多的可用码字(组)，编码效率高，冗余度小；

b、可用码字(组)间的距离尽可能大，使有较大的容错性能。线性空间Vn和其子空间S的形象表示。第八章差错控制编码2010Copyright26课件9、线性分组码生成矩阵G的概念

选择线性空间V中k个线性无关(独立)的n元组：

V1,V2,V3,…,Vk以此为基构成所有2k个线性组合S可以表示为：

其中mi＝0或1。显然，S是V的一个子空间。记

则有

矩阵G称为生成矩阵。第八章差错控制编码2010Copyright29课件9、线性分组码生成矩阵G的概念(续)例：利用矩阵G计算（许用）码字，已知生成矩阵编码前的信息码组为110，生成的码字为：第八章差错控制编码2010Copyright30课件9、线性分组码

生成矩阵的构建、监督矩阵和伴随式(校正子)

例：具有纠正一位误码的分组码

C6C5C4C3C2C1C0n=7,k=4,

信息位监督位r=n－k＝3

传输过程中如果发生某一位错误，如在C3位置出错，则相当于C6C5C4C3C2C1C0＋000E3000=C6C5C4(C3E3)C2C1C0

其中：E3＝1

定义一组确定误码位置的参量:校正子/伴随式S1S2S3

第八章差错控制编码2010Copyright31课件9、线性分组码

生成矩阵的构建、监督矩阵和伴随式(续)设建立1位误码与校正子的对应关系如下（亦可建立其它关系）

由表格关系，校正子与误码Ei的关系，如表中的S1，当

E2、E4、E5、E6中有一个为1时，S1＝1；S1＝E6E5E4E2同理可得，S2＝E6E5E3E1S3＝E6E4E3E0

S1S2S3误码位置S1S2S3误码位置001101010110100111011000

无误第八章差错控制编码2010Copyright32课件9、线性分组码生成矩阵的构建、监督矩阵和伴随式(续)由此，当出现一位误码时，校正子能够确定误码的位置。

当无误码时，显然有

S1＝E6E5E4E2＝0

S2＝E6E5E3E1＝0

S3＝E6E4E3E0＝0

编码时,通过选择监督位C0C1C2的取值来保证正常情况下：

S1＝C6C5C4C2＝0

S2＝C6C5C3C1＝0

S3＝C6C4C3C0＝0

上述方程亦称为监督方程。(*)

由监督方程可以解得，监督位C0C1C2的取值分别为：

C0＝C6C4C3C1＝C6C5C3C2＝C6C5C4

给出一组信息码C6C5C4C3，可计算出监督位C2C1C0。构成码：

C6C5C4C3C2C1C0。注意：信息位与监督位间的关系为线性关系。第八章差错控制编码2010Copyright33课件9、线性分组码生成矩阵的构建、监督矩阵和伴随式(续)例（续前）：

设信息码组C6C5C4C3＝0101C2＝C6C5C4＝010＝1

C1＝C6C5C3＝011＝0

C0＝C6C4C3＝001＝1构成发送码字：C6C5C4C3C2C1C0＝发送码字，若接收时有一位，如C5，出错：C6(C5E5)C4C3C2C1C0＝0001101S1＝C6(C5E5)C4C2＝0001＝1＝(C6C5C4C2)E5

S2＝C6(C5E5)C3C1＝0010＝1＝(C6C5C3C1)E5

S3＝C6C4C3C0＝0000＝0＝(C6C4C3C0)

根据校正子S1S2S3＝110，由表，可判断误码发生在C5第八章差错控制编码2010Copyright34课件9、线性分组码生成矩阵的构建、监督矩阵和伴随式前述的监督方程可用矩阵形式表示

其一般形式为：

un-1un-2……u1u0是发送码字/码组，矩阵H称为监督矩阵。

第八章差错控制编码2010Copyright35课件9、线性分组码生成矩阵的构建、监督矩阵和伴随式(续)对上例，观察P37（*）式（监督方程），有： S1＝C6C5C4C2＝0 S2＝C6C5C3C1＝0

S3＝C6C4C3C0＝0

方程组的矩阵表示形式为：第八章差错控制编码2010Copyright36课件9、线性分组码生成矩阵的构建、监督矩阵和伴随式其中，监督矩阵H为：校正子与误码的位置的关系由H的列向量反映

监督矩阵的性质：（a）H由码元间的监督关系唯一确定；（b）H的行向量相互独立，当采用系统码结构时，具有形式

，其中Ir是r×r（r＝n-k）单位阵。第八章差错控制编码2010Copyright37课件9、线性分组码生成矩阵的构建、监督矩阵和伴随式

在上例中，监督位的产生可表示为一般地，对于线性分组码(n，k)，上述关系可表示为其中监督位r＝n－k：第八章差错控制编码2010Copyright38课件9、线性分组码生成矩阵的构建、监督矩阵和伴随式

监督位矩阵的转置表达式为：若将信息位排列在码组的前半部，监督排列在码组的后半部，则有：

生成矩阵可定义为：

其中Ik是k×k的单位阵。系统码形式的发送码组可按下式产生第八章差错控制编码2010Copyright39课件9、线性分组码生成矩阵的构建、监督矩阵和伴随式生成矩阵G与监督矩阵H之间的关系

监督位矩阵可表示为：

生成矩阵可表示为：

其中Ik是k×k的单位阵，In-k是(n-k)×(n-k)的单位阵由此得上述关系说明：生成矩阵的每一行都是一个有效的码字。第八章差错控制编码2010Copyright40课件9、线性分组码生成矩阵的构建、监督矩阵和伴随式

伴随式(校正子)的定义

设发送码字为接收码字为错误图样为则一般地，有

接收码字r的伴随式(校正子)定义为第八章差错控制编码2010Copyright41课件9、线性分组码生成矩阵的构建、监督矩阵和伴随式由前面分析，有其中H的第i列对应第i位单个错误时的伴随式/校正子

伴随式只与错误图样和监督矩阵有关，与发送的码字无关。

上式中e是1×n的矩阵，而H是r×n的矩阵，所得结果

S是二进制数的1×r的矩阵（向量），所有可能组合的个数为若用伴随式的不同组合表征不同的错误，则最多能够表征（纠正）2r＝2n-k个错误。第八章差错控制编码2010Copyright42课件9、线性分组码线性分组码的许用码字与可纠正的错误图样对于线性分组码（n，k）所有许用码字和可纠正的错误图样及组合可表示为一标准阵：其中U1是许用码字集中的全0码字。第一行为无误码的许用码字；第一列（除全零元素的向量U1外）为所有可纠正的错误图样，称为陪集首。每一行称为一个陪集。第八章差错控制编码2010Copyright43课件9、线性分组码陪集的伴随式

陪集中的每一个元素均有相同的伴随式。任一陪集可表示为

相应的伴随式为：陪集首中每一种错误图样，对应于一个特定的伴随式。因此，可用伴随式来进行错误定位。

第八章差错控制编码2010Copyright44课件9、线性分组码

纠错码的译码步骤

根据收到的r和H计算接收码字的伴随式：

根据S定位错误图样ej

由得到的错误图样ej进行纠错：

注：如果出现的错误图样不在陪集首内，则不能正确地定位错误（超出该种编码方法能够纠错的范围）。第八章差错控制编码2010Copyright45课件9、线性分组码

线性分组码的纠错示例：例线性分组码（6，3）

标准阵：

其伴随式为：查询表：第八章差错控制编码2010Copyright46课件9、线性分组码

线性分组码的纠错示例：例线性分组码（6，3）

设发送码字为：101110

接收码字为：001110

伴随式：S＝[001110]HT＝[100]

根据查询表（或监督矩阵），得错误图样为：[100000]

差错恢复计算：

U＝r＋e＝[001110]+[100000]＝[101110]第八章差错控制编码2010Copyright47课件9、线性分组码

线性分组码的纠错示例：例线性分组码（6，3）

译码器的实现

已知译码器的伴随式为：

即有：由此，结合伴随式查询表，可构建相应的译码电路。第八章差错控制编码2010Copyright48课件9、线性分组码

线性分组码的纠错示例：例线性分组码（6，3）

译码器的译码电路第八章差错控制编码2010Copyright49课件9、线性分组码

线性分组码具有封闭性：任两码组按位之和仍是一个码组。设任Ci，Cj

C（许用码组集合），G为生成矩阵，则式中是码组中的信息码部分。任两码组之和：因为：所以所以第八章差错控制编码2010Copyright50课件9、线性分组码线性分组码的最小距离dmin等于非零码组最小重量W

即若记Wi为Ci的码重，则因为按定义又因为由线性分组码的封闭性，有所以显然有：第八章差错控制编码2010Copyright51课件9、线性分组码

汉明界

线性分组码（n,k）能纠正任意的t个错误的必要条件：陪集数/伴随式个数：不等式的左边为伴随式的总数；不等式的右边为所有可能的小于等于t的错误的总的个数。例线性分组码（127，106）所需的陪集数(由上式可得)第八章差错控制编码2010Copyright52课件9、线性分组码

完备码

能纠正任意的t个错误的线性分组码（n,k）若满足条件：

则称该码为完备码(perfectcode)第八章差错控制编码2010Copyright53课件9、线性分组码

普洛特金界

线性分组码（n,k）的最小码距dmin小于某一上界：

该界称为普洛特金界。例a.判断线性分组码（7,2）有无纠正任意2个错误的可能因所以不可能。

b.判断线性分组码（8,2）有无纠正任意2个错误的可能因所以有可能。第八章差错控制编码2010Copyright54课件9、线性分组码

汉明码

能够纠正1位误码，且满足下列条件的线性分组码，称为汉明码。例：可验证如下监督矩阵对应的线性分组码是汉明码或第八章差错控制编码2010Copyright55课件

9、线性分组码

汉明码的特点：码字的最小距离为3，能纠正单个的错误(t=1)；汉明码是一种完备码，因为：而满足完备性条件：汉明码的编码效率第八章差错控制编码2010Copyright56课件9、线性分组码

生成矩阵的变换

在线性分组码(n,k)的码字集(子空间)中，如果能够找到k个线性无关的码字，即可构成生成矩阵；简单地由k个线性无关的码字构成的生成矩阵未必是系统码生成矩阵；通过矩阵变换可将非系统码的生成矩阵变换成系统码生成矩阵；生成矩阵的变换并不改变码字集中码字的图样，仅仅改变码字集中码字与信息码组的对应关系。

第八章差错控制编码2010Copyright57课件9、线性分组码

生成矩阵的变换(续)

例：已知线性分组(7,4)中4个线性无关的码字：1011000，，，

求关于该码字集的系统码生成矩阵和监督矩阵。解：该3码字构成的生成矩阵可表示为非或形式，所以为非系统码生成矩阵。

第八章差错控制编码2010Copyright58课件9、线性分组码解(续)：对生成矩阵做线性变化，使其左侧成为标准阵，得到新的生成矩阵

第八章差错控制编码2010Copyright59课件9、线性分组码解(续)：该码的生成矩阵具有系统码生成矩阵的形式

相应地监督矩阵为

2010Copyright60课件

10、循环码

循环码的基本概念

定义对线性分组码U，如对任意Ui

U，Ui

循环左移或循环右移任意位后得到的码组Ui’仍然有Ui’U，则称U

为循环码。

码多项式

为用代数理论研究循环码，可将码组用多项式表示，多项式称为码多项式。一般地，长为n的码组Un-1Un-2…U1U0，对应码多项式U(X)

式中，Xi系数对应码字中第i位，Ui，的取值。第八章差错控制编码2010Copyright61课件10、循环码

循环码的基本概念（续）

例：（7,3）码字：1001110对应x6＋x3＋x2＋x

对二进制码组，U(x)的系数只在二元域上取值。二元域上加、乘运算规则如下：

加运算：

乘运算：减法和除法可由加法和乘法定义。第八章差错控制编码2010Copyright62课件10、循环码同余类的概念

在整数除法中，取定除数n，可将所有整数按除以n所得余数进行分类，余数相同的数称为关于n的同余类。一般地，若

（Q为整数，p<n）则记为：

所有余数为p的整数属于关于模n的一个同余类。第八章差错控制编码2010Copyright63课件10、循环码同余类的概念（续前）

类似地，可以定义关于多项式N(x)的同余类，若

式中Q(x)为整式，余式R(x)的幂<N(x)的幂。上式可写成：记为：

例：在系数为二元域的多项式中，有因为：从而有上述结论。第八章差错控制编码2010Copyright64课件10、循环码循环码的代数结构

定理1

若U(X)是长度为n的循环码中的一个码多项式，则

XiU(X)（i为不等于0的整数）按模Xn＋1运算的余式必为循环码中的另一码多项式。证明：设i＝1，有第八章差错控制编码2010Copyright65课件10、循环码循环码的代数结构（续）余式为对应码组un-1un-2…u1u0左循环一位之后的得到的码组：

un-2…u1u0un-1。

若i＝2第八章差错控制编码2010Copyright66课件10、循环码循环码的代数结构（续）

显然，余式为对应码组un-1un-2…u1u0左循环两位之后的得到的码组。一般地，对任意i有：

余式对应un-1un-2…u1u0左循环i位之后的得到的码组。证毕(容易用归纳法严格证明)第八章差错控制编码2010Copyright67课件10、循环码循环码的代数结构（续）例已知码组的长度为n＝4，其中一码字：U＝1101(高位在右)，求该码字循环移位3位后得到的码字。

a.由1101直接(右)循环移3位得：U(3)＝1011b.根据多项式关系求解，当i＝3时，关于X4+1的余式U(3)(X)-1011第八章差错控制编码2010Copyright68课件10、循环码循环码的生成多项式g(x)及生成矩阵

一般地，线性分码组可表示为矩阵G中每一行均为一许用码组，如第i行对应第i个信息位为1，其余为0时的信息码生成的码组。由于G中包含一个Ik分块，所以G为k个独立的码组组成的矩阵。即：

任一线性分组码码组均可由k个线性无关的码组组合而成。

第八章差错控制编码2010Copyright69课件10、循环码

循环码的生成多项式g(x)及生成矩阵(续)

利用上述线性分组码

任一线性分组码码组均可由k个线性无关的码组组合而成这一性质，寻求循环码生成矩阵的构建方法。

设存在一个幂次数为n－k，且常数项不为0的码多项式g(X)，则由循环码的性质（定理1）

g(X)，Xg(X),……，Xk-2g(X)，Xk-1g(X)(最高次幂等于n－1)

也是码多项式，这k个码多项式对应独立的k个码字，由此可构成循环码生成矩阵G(X)。第八章差错控制编码2010Copyright70课件10、循环码循环码的生成多项式g(X)及生成矩阵(续)

循环码生成矩阵G(X)：

其中，g(X)称为循环码码生成多项式。G(X)对应的系数矩阵G

右侧的子方阵具有主对角线元素均不为0的形式。该子阵行列式不为0，因而子阵满秩，因而行向量是线性无关的。利用码生成矩阵G(X)，任一码字多项式可以表示为：

或：第八章差错控制编码2010Copyright71课件10、循环码循环码的生成多项式g(X)及生成矩阵(续)

例（7，3）生成多项式g(X)＝X4+X3+X2+1对应生成矩阵G[X]

矩阵为：

因为矩阵G左侧的子方阵满秩，因此容易判断该矩阵中的行向量是线性无关的。第八章差错控制编码2010Copyright72课件10、循环码循环码的生成多项式g(X)及生成矩阵(续)

定理2在循环码中，n－k次的码多项式g(X)有一个且只有一个。证明：（a）在含k个信息位的循环码中，除全0码外，其它码组最多只有k-1个连0。否则，经循环移位后前面k个信息码元为0，而监督码元不全为0的码组，这在线性分组码中是不可能的。所以一定有一个n－k次的多项式。（b）n－k次的码多项式g(X)的常数项不能为0，否则该多项式右移一位就会出现k个连0的情况。第八章差错控制编码2010Copyright73课件10、循环码循环码的生成多项式g(X)及生成矩阵(续)

（c）n－k次的码多项式g(X)只可能有一个，若有两个，两多项式相加后由线性分组码的封闭性仍为码多项式，但由于n－k次项和常数项相消，会产生k＋1连0的情况，由（a）分析，这是不可能的。综上（a）、（b）和（c），证毕。第八章差错控制编码2010Copyright74课件循环码的生成多项式g(X)及生成矩阵(续)

定理3

在循环码中，所有的码多项式U(x)都能够被g(X)整除。证明：因为任一码多项式都可由其信息码元和生成矩阵

G[x]确定：

g(X)为码多项式U(x)的一个因式，所以U(x)可被g(X)整除。

证毕第八章差错控制编码2010Copyright75课件10、循环码循环码的生成多项式g(X)及生成矩阵(续)

推论：次数不大于k－1次的任何多项式与g(X)的乘积都是码多项式。第八章差错控制编码2010Copyright76课件循环码的生成多项式g(x)及生成矩阵(续)定理4循环码（n，k）的生成多项式g(X)是Xn＋1的一个因式。证明：因为g(X)幂为n－k，因而可得其中R(X)的幂小于n。由定理1，R(X)是码多项式，又由定理3

有R(X)=m(X)g(X)，即有移项整理得：即g(X)是Xn＋1的一个因式。证毕第八章差错控制编码2010Copyright77课件循环码的生成多项式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)一定可被Xn＋1整除。生成多项式g(X)的三个性质（充要条件）：（a）g(X)是n－k次多项式；（b）g(X)的常数项不等于0；

（c）是Xn＋1的一个因式。第八章差错控制编码2010Copyright78课件10、循环码循环码的生成多项式g(x)及生成矩阵(续)采用前面定义的循环码生成矩阵：

对应的系数矩阵G一般不符合

G＝[Ik,Q]

形式。编码输出结果相当于m(x)g(x)，所得码组为非系统码结构，获得信息码需要查对应的码表进行译码。

第八章差错控制编码2010Copyright79课件10、循环码循环码的生成多项式g(x)及生成矩阵(续)例：线性分组码（7，4）生成多项式g(x)＝x3+x2+1对应生成矩阵G[x]对应的系数矩阵为：为非系统码结构的生成矩阵。第八章差错控制编码2010Copyright80课件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)为一种系统码结构的循环码。第八章差错控制编码2010Copyright81课件10、循环码循环码编码器的电路实现

由系统码结构循环码的编码方法可知循环码编码器的实现需要用到以生成多项式g(x)为除式的除法器计算余式p(x):第八章差错控制编码2010Copyright82课件10、循环码循环码编码器的电路实现(续)

多项式除法多项式除法可用带反馈的移位寄存器实现。

例：除数为g(X)＝X6＋X5＋X4＋X3＋1除法电路如下图，反馈的接入由g(X)确定

除法运算的实现先将移位寄存器清“0”；进行n次移位，将被除数全部送入除法器后，在寄存器内即可得到相应的余式。第八章差错控制编码2010Copyright83课件10、循环码循环码编码器的电路实现(续)

(接上例)计算C(X)/g(X)，其中C(X)=X13+X11+X10+X7+X4+X3+X+1

得余式：

p(x)＝x4＋x2

（容易通过长除法验证）移位序号输入移位寄存器内容输出商反馈信号01234567891011121314010110010011011

L000000H100000010000101000110100011011001101000001100111110100111010111101111001011011001010余数000000111001110000000000000000000000000000000000000000000100111100111100111000000000000100111100111100111

第八章差错控制编码2010Copyright84课件10、循环码循环码编码器的电路实现(续)

多项式除法电路的一般形式

被除式：除式：相应实现电路：第八章差错控制编码2010Copyright85课件10、循环码循环码编码器的电路实现(续)

多项式除法电路的缺点除法运算在移位进行了n-k-1位后才开始，运算完成后，要将余式移出，还要做n-k-1次移位。速度较慢。第八章差错控制编码2010Copyright86课件10、循环码实际应用的循环码编码电路特点：采用“预先乘Xn-k方案”（信号直接到达最后一级），边移位边做除法运算，当k个信息码输入后，同时完成了除法运算。

g(X)=X4+X3+X2+1

（a）当信息位输入时，开关K1、K2合下，k个信息位经K2逐位输出，同时直接送到最高位做除法，其运算等效为：第八章差错控制编码2010Copyright87课件10、循环码实际应用的循环码编码电路特点：采用“预先乘Xn-k方案”（信号直接到达最后一级），边移位边做除法运算，当k个信息码输入后，同时完成了除法运算。

g(X)=X4+X3+X2+1

（a）当信息位输入时，开关K1、K2合下，k个信息位经K2逐位输出，同时直接送到最高位做除法，其运算等效为：第八章差错控制编码2010Copyright88课件实际应用的循环码编码电路（b）当信息位全部输入后，相应除法运算完成，开关K1、K2合上，将余数顺序输出。例：设m(X)=X2＋X＋1111，Xn-k＝X7－3＝X4，

Xn-km(X)＝X6＋X5＋X4

1110000

商为：100，余数为：0100

上述运算也可看作下列分别运算的结果：商为：110＋011＋001100（按位相加）余数：1110＋0111＋11010100第八章差错控制编码2010Copyright89课件10、循环码实际应用的循环码编码电路一般形式的（n－k）移位寄存器编码电路，设则：总的所需的移位次数为n。第八章差错控制编码2010Copyright90课件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)为：第八章差错控制编码2010Copyright91课件10、循环码循环码译码电路(续)

纠错译码步骤

a.计算S(X)＝r(X)/g(X)b.确定错误图样S(X)E(X)c.根据E(X)纠错。

第八章差错控制编码2010Copyright92课件循环码译码电路

除法电路的性质

某码组循环移位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))。第八章差错控制编码2010Copyright93课件