通信原理-第十一章-差错控制编码

11.1概述

11.2纠错编码的基本原理

11.4简单的实用编码

11.5线性分组码

11.6循环码

11.7卷积码

第十一章差错控制编码本章内容简介11.1概述一.差错的产生二.差错控制方法噪声与干扰■

检错重发法■

前向纠错法■

反馈校验法随机噪声与干扰突发噪声与干扰混合噪声与干扰随机信道突发信道混合信道噪声与干扰是通信出现差错的基本原因。不同的噪声与干扰信道，应采用不同的差错控制策略。检错重发法：双向信道工作。接收信息方具有检错能力，收到信息无误，回发肯定应答；有误则不发应答或发否定应答。前向纠错法：单向信道工作。接收信息方具有纠错能力，发现收到信息有误时，确定误码的位置并按规则予以纠正。反馈校验法：双向信道工作。接收信息方简单地将收到信息回传给发送方，由发送方判断前次发送是否无误。第十一章差错控制编码11.1概述三.

自动要求重发(ARQ)系统第十一章差错控制编码接收码组ACKACKNAKACKACKNAKACKt1233455发送码组12334556t有错码组有错码组数据按分组发送。每发送一组数据后发送端等待接收端的确认(ACK)答复，然后再发送下一组数据。图中的第3组接收数据有误，接收端发回一个否认(NAK)答复。这时，发送端将重发第3组数据。系统是工作在半双工状态，时间没有得到充分利用，传输效率较低。停止等待ARQ系统11.1概述三.

自动要求重发(ARQ)系统第十一章差错控制编码拉后ARQ系统接收数据有错码组有错码组91011101112214365798576ACK1NAK5NAK9ACK5发送数据57695214367981011101112重发码组重发码组发送端连续发送数据组，接收端对于每个接收到的数据组都发回确认(ACK)或否认(NAK)答复。例如，图中第5组接收数据有误，则在发送端收到第5组接收的否认答复后，从第5组开始重发数据组。在这种系统中需要对发送的数据组和答复进行编号，以便识别。显然，这种系统需要双工信道。11.1概述三.

自动要求重发(ARQ)系统第十一章差错控制编码选择重发ARQ系统接收数据有错码组有错码组921436575981011131412发送数据995852143671011131412重发码组重发码组NAK9ACK1NAK5ACK5ACK9它只重发出错的数据组，因此进一步提高了传输效率。11.1概述三.

自动要求重发(ARQ)系统图11-1典型ARQ系统组成框图

发送信源终端接收信宿终端编码器、缓冲存储重发控制解码器指令产生输出缓存双向信道正确输出错误删除■ARQ系统主要优点:1.

只需少量多余码元；

2.适应不同差错特性；

3.检错方法简单。■ARQ系统主要缺点:1.

需要双向信道；

2.出错率高时，重发降低信道效率；

3.信息传输实时性差。第十一章差错控制编码11.1概述四.差错控制编码在信息码元序列中加入一定数目的监督码元就称为差错控制编码。■差错控制编码的检纠错能力■差错控制编码的编码效率（码率）一般说来，差错控制编码的检纠错能力取决于：●在信息码元序列中加入的监督码元的多少。对于一定长度的信息码元序列,加入的监督码元越多，检纠错能力越强。●不同的编码规则与方法（有不同的检错或纠错能力）。在一定长度信息码元序列中加入监督码元的数目越多,差错控制编码的编码效率越低。如信息码长为k，监督码长为r,则编码效率为k/(k+r)=k/n。监督码元数r和信息码元数k之比r/k

=(n-k)/k

称为冗余度。第十一章差错控制编码11.2纠错编码的基本原理第十一章差错控制编码

分组码基本原理：举例说明如下。设有一种由3位二进制数字构成的码组，它共有8种不同的可能组合。若将其全部用来表示天气，则可以表示8种不同天气， 例如：“000”（晴），“001”（云）， “010”（阴），“011”（雨）， “100”（雪），“101”（霜）， “110”（雾），“111”（雹）。其中任一码组在传输中若发生一个或多个错码，则将变成另一个信息码组。这时，接收端将无法发现错误。11.2纠错编码的基本原理第十一章差错控制编码若在上述8种码组中只准许使用4种来传送天气，例如：“000”＝晴“011”＝云“101”＝阴“110”＝雨这时，虽然只能传送4种不同的天气，但是接收端却有可能发现码组中的一个错码。例如，若“000”（晴）中错了一位，则接收码组将变成“100”或“010”或“001”。这3种码组都是不准使用的，称为禁用码组。接收端在收到禁用码组时，就认为发现了错码。当发生3个错码时，“000”变成了“111”，它也是禁用码组，故这种编码也能检测3个错码。但是这种码不能发现一个码组中的两个错码，因为发生两个错码后产生的是许用码组。11.2纠错编码的基本原理第十一章差错控制编码检错和纠错上面这种编码只能检测错码，不能纠正错码。例如，当接收码组为禁用码组“100”时，接收端将无法判断是哪一位码发生了错误，因为晴、阴、雨三者错了一位都可以变成“100”。要能够纠正错误，还要增加多余度。例如，若规定许用码组只有两个：“000”（晴），“111”（雨），其他都是禁用码组，则能够检测两个以下错码，或能够纠正一个错码。例如，当收到禁用码组“100”时，若当作仅有一个错码，则可以判断此错码发生在“1”位，从而纠正为“000”（晴）。因为“111”（雨）发生任何一位错码时都不会变成“100”这种形式。但是，这时若假定错码数不超过两个，则存在两种可能性：“000”错一位和“111”错两位都可能变成“100”，因而只能检测出存在错码而无法纠正错码。11.2纠错编码的基本原理表11-1差错控制编码举例

消息信息位监督位晴000

云011

阴101

雨110两位信息位后加入一个监督位,使每码组中“1”的个数为偶数,能够检测出码组中所有单数个误码。为每组信息码后附加若干个监督位构成的码组集合,称为分组码。分组码用符号(n,k)表示,k是信息位的数目,n是码组总长度,n-k=r是监督位数目。an-1an-2……ar

ar-1……a1a0k个信息位r个监督位码组总长度n=k+r图11-2(n,k)分组码的结构第十一章差错控制编码11.2纠错编码的基本原理■

码重与码距概念●

一条码组中“1”的个数称为该码组的码重。●

两码组中不同位的数目称为该两码组的码距。■

最小码重与最小码距●

某码组集合中含“1”个数最少的码组的码重,称该码组集合的最小码重。●某码组集合中不同位数最少的两码组的码距,称该码组集合的最小码距。码组集合①1001001②0011011③1011100④0111011⑤0100011⑥1000100码重w=3w=4w=4w=5w=3w=2最小码重w0=2码重与码距概念举例码距d12=3d13=3d14=4d15=3d16=3┇d24=1┇最小码距d0=1第十一章差错控制编码11.2纠错编码的基本原理■

码距(汉明Hamming距离)概念图11-3码距的几何意义a0a1a2(0,0,0)(0,0,1)(1,0,1)(1,0,0)(1,1,0)(0,1,0)(0,1,1)(1,1,1)■

如果使用全部8个三位的码组分别表示8种不同信息，由于最小码距d0=1,说明某码组的任何一位错误，都可能变为其他合法码组,无检错或纠错能力。■

如果使用其中4个三位的码组分别表示4种不同信息，由于最小码距d0=2,说明某码组的任何一位错误，都不可能变为其他合法码组,能够检测出单个误码。最小码距d0

是衡量差错控制编码系统检错及纠错能力的决定性参数。第十一章差错控制编码11.2纠错编码的基本原理■

最小码距d0与检错纠错能力关系（1）只检模式为检测e个误码，要求最小码距

d0≧e+1(11.2-2)AB0123ed0图11-4码距与检错纠错能力的关系（a）只检模式第十一章差错控制编码11.2纠错编码的基本原理■

最小码距d0与检错纠错能力关系（2）只纠模式为纠正t个误码，要求最小码距

d0≧2t+1(11.2-3)

图11-4码距与检错纠错能力的关系（b）只纠模式AB0123td0t4567第十一章差错控制编码11.2纠错编码的基本原理■

最小码距d0与检错纠错能力关系（3）先纠后检，纠检结合模式为纠正t个误码,同时能检出

e个误码,要求最小码距

d0≧e+t+1(e>t)(11.2-4)

图11-4码距与检错纠错能力的关系（c）纠检结合模式ABtet1d0第十一章差错控制编码11.2纠错编码的基本原理■

最小码距d0与检错纠错能力关系(1)只检模式由d0≧e+1,可知系统的检错能力：最多可检出6位误码。(2)只纠模式由d0≧2t+1,可知系统的纠错能力：最多可检出3位误码。(3)纠检结合模式由d0≧t+e+1(e>t),可知:►若先纠正1位误码，则还可以检出5位以下的误码。[举例]

某差错控制编码系统，码组集合的最小码距d0=7,试求该编码系统的检纠错能力。ABe≦6t≦3t=1e≦5t=2e≦4►若先纠正2位误码，则还可以检出4位以下的误码。第十一章差错控制编码11.2纠错编码的基本原理■差错控制(纠错)编码的效用AB错2位错5位错3位错4位错1位错6位假设在随机信道中发送“0”和“1”时的出错概率相同，都等于Pe（

Pe<<1），则容易证明，在长度为n的码组中恰好发生r个误码的概率为(11.2-5)例如，当码长n=7，Pe

=10-3

时

P7(1)≈7×10-3P7(2)≈2.1×10-5P7(3)≈3.5×10-8采用差错控制编码,即使仅能够检出或纠正1—2个误码，也能使误码率降低几个数量级。第十一章差错控制编码11.4常用的简单编码1.奇偶监督码■

偶监督码

信息位附加监督位后，码组中“1”的个数为偶数,即满足

an-1⊕

an-2⊕

……⊕

a1⊕

a0=0

(11.4-1)由k=n-1个信息位an-1an-2……a1和r=1个监督位a0构成的总长度为n=k+1的(k+1,k)分组码。■

奇监督码

信息位附加监督位后，码组中“1”的个数为奇数,即满足

an-1⊕

an-2⊕

……⊕

a1⊕

a0=1

(11.4-2)监督关系式偶监督码由已知信息位获得监督位的表示式为

a0=an-1⊕

an-2⊕

……⊕

a1奇监督码由已知信息位获得监督位的表示式为

a0=an-1⊕

an-2⊕

……⊕

a1⊕1奇偶监督码的编码效率η=(n-1)/n第十一章差错控制编码11.4常用的简单编码2.二维奇偶监督码■二维奇偶监督码有可能检测出偶数个错误,甚至可能纠正一些错误。■二维奇偶监督码特别适合于检测突发性错误。■二维奇偶监督码的编码效率低于一维奇偶监督码。上例中，η=m(n-1)/n(m+1)二维奇偶监督码又称为方阵码。它是将上述的m条偶或奇监督码排成一个方阵，然后沿垂直方向加上垂直监督位构成。a1n-1a1n-2……

a11a10a2n-1a2n-2……

a21a20amn-1amn-2……

am1am0cn-1cn-2……

c1c0信息位m×(n-1)水平监督位m×1垂直监督位

1×n第十一章差错控制编码信息位100110100101101011101110001001000010001110010101100000111.4常用的简单编码2.二维奇偶监督码

0水平监督位垂直监督位

0

1

1

1

0

11

0[举例]本例中，信息位k=7×7=49位，监督位r=7+8=15位，编码效率η=49/(49+15)=49/64第十一章差错控制编码11.4常用的简单编码3.恒比码(等重码)在全部码组集合中，每条码组中包含“1”的数目相同。表11-2我国电传机数字代码字符保护电码字符保护电码

001101500111101011610101211001711100310110801110411010910011

恒比码中无法清晰地将信息位与监督位分开。因此一般只适用与传输电传机或键盘设备输入信息编码。恒比码不适合信源随机信息的编码。4.正反码

正反码中信息位数目和监督位数目相同。当信息位中“1”为奇数时，监督位与信息位相同;当信息位中“1”为偶数时，监督位与信息位相反。正反码的编码效率η=1/2,是具有纠错能力的编码。详见教材（略）第十一章差错控制编码11.5

线性分组码前述的偶监督码，n-1个信息位附加1个监督位，构成整个码组中“1”的个数为偶数,唯一的监督关系满足

an-1⊕

an-2⊕

……⊕

a1⊕

a0=0在接收端，由收到整个码组an-1an-2……

a1a0，计算校正子SS=an-1⊕

an-2⊕

……⊕

a1⊕

a0(11.5-1)单个校正子S的取值只有两种可能，“0”或“1”。若S=0,表示“无错”,S=1,表示“有错”。无法确定误码的位置进行纠正。增加监督位的数量，可以建立监督位和信息位关系（监督关系）的多个监督关系式。在接收端，由收到整个码组an-1an-2……

a1a0，计算多个校正子S1、S2、……

Sr

。组合取值有2r

种可能，一种表示“无错”,其他2r

-1种可以用来确定误码的位置以进行纠正。第十一章差错控制编码11.5

线性分组码若由信息位和监督位构成的整个码组的总长度n满足

n≦2r

–1或2r≧n+1=k+r+1(11.5-2)则除一种状态表示“无错”外，校正子S1、S2、……

Sr

组合的其他2r

-1种状态,至少可以确定长度为n的码组中，一个单个误码的位置。若码组的总长度n满足

n=

2r

–1或2r=n+1这时r个校正子组合的2r

种状态,恰好可以表示出“无错”和n位码组当中的1位误码位置。作为能够纠正1位误码的一种编码，其编码效率是最高的,称为汉明(Hamming)码。能够纠正1位误码的(7,4)、(15,11)、(31,26)、(63,57)、…….，其编码效率在同码长的编码中都是最高的,都是汉明码。第十一章差错控制编码11.5

线性分组码现在通过（7,4）分组码例子说明汉明码的监督关系式构造。信息位(k=4):a6a5a4a3

监督位(r=3):a2a1a0

表11-3校正子与误码位置的对应关系S1S2S3

误码位置S1S2S3

误码位置

000无错011a3001a0101a4010a1110a5100a2111a6可以看出，仅当1位误码位置在a2、a4、a5或a6时，校正子S1为1；否则S1为0。这意味着a2、a4、a5、a64个码元构成偶监督关系

S1=a6⊕

a5⊕

a4⊕

a2

(11.5-3)第十一章差错控制编码同理可得到关于S2、S3的偶监督关系，有

S1=a6⊕

a5⊕

a4⊕

a2

(11.5-3)S2=a6⊕

a5⊕

a3⊕

a1

(11.5-4)S3=a6⊕

a4⊕

a3⊕

a0

(11.5-5)11.5

线性分组码表11-3校正子与误码位置的对应关系S1S2S3

误码位置S1S2S3

误码位置

000无错011a3001a0101a4010a1110a5100a2111a6编码时，给信息位加入监督位应使得S1=S2=

S3=0，即满足

a6⊕

a5⊕

a4⊕

a2

=0

a6⊕

a5⊕

a3⊕

a1

=0(11.5-6)

a6⊕

a4⊕

a3⊕

a0

=0第十一章差错控制编码11.5

线性分组码由监督关系式（方程组）

a6⊕

a5⊕

a4⊕

a2

=0

a6⊕

a5⊕

a3⊕

a1

=0(11.5-6)

a6⊕

a4⊕

a3⊕

a0

=0整理可得到已知信息位求监督位的关系式

a2

=a6⊕

a5⊕

a4a1

=a6⊕

a5⊕

a3(11.5-7)a0

=a6⊕

a4⊕

a3对于信息位k=4情况，共有24=16种信息码组合，由式(11.5-7)求出每种信息组合所附加的监督位，进而得到全部24=16条完整码组，如表11-4所示（教材P337）。第十一章差错控制编码例如：接收到码组“0000011”,该码组确实是表11-4中某码组传输中产生了1位误码所致。由式(11.5-3)、(11.5-4)和(11.5-5)分别计算3个校正子，有

S1=a6⊕

a5⊕

a4⊕

a2=0

⊕0

⊕0

⊕0=0S2=a6⊕

a5⊕

a3⊕

a1=0

⊕0

⊕0

⊕1=1S3=a6⊕

a4⊕

a3⊕

a0=0

⊕0

⊕0

⊕1=1根据表11-3校正子与误码位置对应关系，可以确定1位误码的位置在a3处，正确的码组应该为“0001011”，它就是表11-4中的第2条码组。11.5

线性分组码

表11-3校正子与误码位置对应关系S1S2S3

误码位置S1S2S3

误码位置

000无错011a3001a0101a4010a1110a5100a2111a6如果1条码组在传输过程中确实产生了1位错误，前述的(7,4)汉明码就能无误地指出误码位置以进行纠正。第十一章差错控制编码11.5

线性分组码从表11-4(7,4)汉明码的全部码组可以看到，这种码的最小码距(数值上和非全零码的最小码重相等)d0=3，用于检错可检测出e=2

位以下的误码，用于纠错只可纠正t=1

位误码。这种码的编码效率η=k/n=4/7。汉明码能够纠正1位误码，其编码效率在同码长的编码中是最高的。具有1位误码纠正能力的(7,4)、(15,11)、(31,26)、(63,57)、…….都是汉明码。汉明码的编码效率随着码组总长n的增加而增加。因为码组越长，信息位所占比例越大，监督位所占比例越小。

当码长n很大时，编码效率接近于1。汉明码2r=n+1第十一章差错控制编码11.5

线性分组码改写监督关系式（方程组）

a6⊕

a5⊕

a4⊕

a2

=0

a6⊕

a5⊕

a3⊕

a1

=0(11.5-6)

a6⊕

a4⊕

a3⊕

a0

=0为

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=0

(11.5-8)1·a6+

0·a5+

1·a4+

1·a3+

0·a2

+0·a1+

1·a0

=0为简化将“⊕”改写为“+”,均表示模2加。并可表示为矩阵形式

111010011010101011001a6a5a4a3a2

a1a0000(11.5-9)简记为H•AT=OT

或A

•HT=O(11.5-10)r×n监督矩阵[a6a5a4a3a2

a1a0]1×n码组向量[

000]1×r零向量第十一章差错控制编码11.5

线性分组码式(11.5-9)中的监督矩阵是一个

r行×n列的矩阵，内容可以分为两部分其中P为

r×k阶矩阵，Ir为

r×r

阶单位矩阵。具有[P┊Ir]形式的监督矩阵称为典型监督矩阵。(11.5-11)111010011010101011001P┊Ir

H111010011010101011001式(11.5-7)改写可得到已知信息位a6a5a4a3求监督位a2

a1a0的矩阵关系式a2

a1a0111011011011a6

a5a4a3或(11.5-12)(11.5-13)a2a1a0a6a5a4a3111110101011Pr×k

Qk×r其Q为

k×r

阶,它是P的转置矩阵Q=PT

(11.5-14)第十一章差错控制编码11.5

线性分组码对已知信息位a6a5a4a3求监督位a2

a1a0的关系(11.5-7)扩充，变为已知信息位a6a5a4a3求整个码组a6a5a4a3a2

a1a0的关系式a2=a6⊕

a5⊕

a4a1=a6⊕

a5⊕

a3a0=a6⊕

a4⊕

a3a6=a6a5=a5a4=a4a3

=

a3矩阵形式a6

a5a4a3a6

a5a4a3a2

a1a01000010000100001111011011011简记为A=[a6a5a4a3]·G(11.5-17)G10001110100110001010100010111000111010011000101010001011Ik┊Q(11.5-15)GTk×k

阶单位矩阵Ikk×r阶矩阵Q典型生成矩阵生成矩阵第十一章差错控制编码11.5

线性分组码●线性分组码具有封闭性。它是指一种线性分组码的任意两条合法码组相异或，得到的结果仍然是该线性分组码的一条合法码组。■线性分组码的两个重要性质●线性分组码的最小码重（全零码除外），就是该线性分组码的最小码距。这是因为，任一码组中“1”的个数（码重），都是某两条码组不相同位的数目（码距）。性质1（线性分组码的封闭性）给我们提供了利用某些已知码组获得一些未知码组的一条可能的途径。性质2（最小码距=最小码重）给我们提供了从码组获得最小码距，并判断检错纠错能力的便捷方法。第十一章差错控制编码11.6

循环码

循环码是一种简单、重要、常用的线性分组码。除了具有线性分组码的一般性质外，还具有循环性，即码组集合中任一码组循环左移或右移若干位，得到的结果仍然为该码组集合中的一条合法码组。11.6.1循环码原理表11-6(7,3)循环码举例码组信息位监督位编号a6a5a4a3a2

a1a0

1000000020010111301011104011100151001011610111007110010181110010循环m位循环左移3位循环左移2位本例中，只要知道一条非全零码组,通过移位就可求出全部码组。循环右移3位第十一章差错控制编码11.6

循环码

■

码的多项式表示

对于码组an-1an-2……

a1a0，若将各码元作为多项式系数，则可得到码组的多项式表示

T(x)=an-1xn-1+

an-2xn-2+

……+

a1x

+

a0(11.6-1)对于前例的(7,3)码,任一码组都可表示为

T(x)=a6x6+

a5x5+a4x4+a3x3+a2x2+

a1x

+

a0(11.6-2)而其中的第7条码组“1100101”可表示为多项式

T7(x)=x6+

x5+x2+1(11.6-3)11.6.1循环码原理对于码长为n的码组，码多项式的最高次数为xn-1。多项式系数取值是模2的，即只能是“1”或“0”。第十一章差错控制编码11.6

循环码11.6.1循环码原理1.码多项式的按模运算

■如整数的按模运算

对整数m按模n运算,将整数m除以整数n,商为整数Q,余数为p(p<n),即我们说整数m按模n运算之结果为

m≡p(模n)(11.6-4)(11.6-5)

■多项式的按模运算

对任意多项式F(x)被另一个n次多项式N(x)除，得到一商式Q(x)和一个次数小于n的余式R(x),即

F(x)=N(x)Q(x)+R(x)我们说多项式F(x)按模N(x)运算之结果为

F(x)

≡R(x)

(模N(x))(11.6-6)(11.6-7)第十一章差错控制编码11.6

循环码11.6.1循环码原理1.码多项式的按模运算

■多项式的按模运算[例]●x3按模(x3+1)运算，结果为

x3

≡1(模x3+1)●x4+x2+1按模(x3+1)运算，结果为

x4+x2+1

≡x2+x

+1

(模x3+1)(11.6-6)(11.6-7)x3+1x4+x2+1xx4+xx2+x

+1注意:多项式系数是模2的,取值只能是“1”或“0”,这也是余式为x2+x

+1,而不为x2-x

+1

的原因。重要结论:在循环码中，若T(x)是一个长度为n的码组，则xi

T(x)

在按模xn+1运算下，也是该循环码的一个许用码组。第十一章差错控制编码11.6

循环码11.6.1循环码原理1.码多项式的按模运算重要结论:在循环码中，若T(x)是一个长度为n的码组，则xi

T(x)

在按模xn+1运算下，也是该循环码的一个许用码组。证明详见教材。[举例]

T(x)=x4+x2+x+1

是一个长度为7

的合法码组,可以证明

T´(x)=x3T(x)=x7+x5+x4+

x3

按模x7+1运算,其结果为

T´(x)≡x5+x4+

x3

+1

也是一个长度为7

的合法码组。表11-6(7,3)循环码举例码组信息位监督位编号a6a5a4a3a2

a1a0

1000000020010111301011104011100151001011610111007110010181110010第十一章差错控制编码11.6

循环码11.6.1循环码原理2.循环码生成矩阵和生成多项式生成矩阵G用于由给定信息位生成完整码组，它由k行n列构成，其每一行都是彼此线性无关的合法码组。在循环码中,一个(n,k)码有2k种不同码组。现用g(x)表示前(k-1)位皆为“0”的码组,则g(x)、xg(x)、x2g(x)、…、xk-1g(x)是k个彼此线性无关的合法码组,可用来构成循环码的生成矩阵G(x)g(x)xg(x)xk-1g(x)xk-2g(x)(11.6-15)可以证明,除全零码外,g(x)前(k-1)位皆为“0”是唯一前面连续“0”最多的码组,且常数项一定为“1”,否则经若干次循环移位后会得到一个信息位全零的“非全零”码组，而这是不可能的。第十一章差错控制编码11.6

循环码11.6.1循环码原理2.循环码生成矩阵和生成多项式表11-6(7,3)循环码举例码组信息位监督位编号a6a5a4a3a2

a1a0

1000000020010111301011104011100151001011610111007110010181110010[举例]g(x)

对应前(k-1)位皆为“0”是唯一前面连续“0”最多的码组,因此，除全零码外，g(x)是一个次数最低的码多项式。是一个常数项不为零的(n-k)次多项式。g(x)=x4+x2+x+1

G(x)g(x)xg(x)x2g(x)(11.6-16)G001011101011101011100(11.6-17)非典型阵典型化线性变换G001011101011101001011典型阵G=[Ik┊Q]第十一章差错控制编码11.6

循环码11.6.1循环码原理3.如何寻找(n,k)码的生成多项式生成多项式g(x)

是循环码的最关键因素。由它可容易地获得生成矩阵G,并根据信息位产生全部码组。下面研究的g(x)获得方法。■

由(n,k)循环码的全部条码组寻找g(x)

(7,4)循环码举例码组信息位监督位编号a6a5a4a3a2

a1a0

10000000

20001011

30010110

40011101

50100111

60101100

70110001

80111010码组信息位监督位编号a6a5a4a3a2

a1a0

91000101

101001110

111010011

121011000

131100010

141101001

151110100

161111111前(k-1)位皆为“0”的码组，也是信息位为“0…01”的码组。g(x)=x3+x+11011000010110000101100001011G=第十一章差错控制编码11.6

循环码11.6.1循环码原理3.如何寻找(n,k)码的生成多项式■

由(n,k)循环码的部分码组寻找g(x)1011000010110000101100001011G=

(7,4)循环码举例码组信息位监督位编号a6a5a4a3a2

a1a0

10000000

┇┇00111010100111010110001100010111010┇┇161111111循环左移3位，得到前(k-1)=3位皆为“0”的码组“0001011”，对应

g(x)=x3+x+1线性变换典型化1000101010011100101100001011G=1000101010011100101100001011Ik┊Q第十一章差错控制编码11.6

循环码11.6.1循环码原理3.如何寻找(n,k)码的生成多项式■

由(n,k)循环码的部分码组寻找g(x)

(7,4)循环码举例码组信息位监督位编号a6a5a4a3a2

a1a0

10000000

┇┇001110101001111010011

┇

┇0111010┇┇161111111两条码组模2加后，循环左移1位，得到前(k-1)=3位皆为“0”的码组“0001011”，对应g(x)=x3+x+1如何寻找g(x)

？第十一章差错控制编码1011000010110000101100001011G=线性变换典型化1000101010011100101100001011G=1000101010011100101100001011Ik┊Q11.6

循环码11.6.1循环码原理3.如何寻找(n,k)码的生成多项式■

无已知条件下，求(n,k)循环码的g(x)如何寻找g(x)

？可以证明(见教材)，生成多项式g(x)

是(xn

+1)的一个因式。上述结论告诉我们，可以通过对(xn

+1)分解因式获得g(x)

。(xn

+1)的因式可能有多个，只有那些常数项不为零的n-k次因式才可作为(n,k)循环码的生成多项式g(x)

。例如：为获得(7,4)循环码的生成多项式g(x)

，分解(x7+1)得

(x7+1)=(x+1)(x3+x2

+1)(x3+x+1)g1(x)和g2(x)都可作为(7,4)循环码的生成多项式。g1(x)g2(x)(11.6-24)同理,(7,3)循环码的生成多项式也是分解(x7+1)所得

g2(x)=x4+x3

+x2+

1(11.6-26)g1(x)=x4+x2

+x+

1(11.6-25)(x+1)(x3+x2

+1)(x+1)(x3+x+1)第十一章差错控制编码11.6

循环码11.6.2循环码的编解码方法■编码步骤(1)用信息码多项式m(x)乘以xn-k

，该运算相当于给信息码后加(n-k)个“0”。例如，信息码为“110”,相当于m(x)=x2+x

。当n-k=7-3=4时，xn-k

m(x)=x4(x2+x)=x6+x5，相当于“1100000”。(2)用xn-k

m(x)除以g(x),得到商Q(x)和余式r(x),既

xn-k

m(x)=g(x)Q(x)+R(x)(11.6-27)

若取g(x)=x4+x2+x+1

，对于上例可得相当于

110000010111

10110111=111+(11.6-28)(11.6-29)第十一章差错控制编码11.6

循环码11.6.2循环码的编解码方法■编码步骤(3)编出码组T(x)为

T(x)=xn-k

m(x)+r(x)(11.6-30)

在上例中

T(x)=1100000+101=1100101

正是表11-6中第7条码组。

a

b

c

d⊕⊕⊕

S

e

f

m信息码输入编码输出图11-6(7,3)循环码编码器第十一章差错控制编码11.6

循环码11.6.2循环码的编解码方法■解码步骤(1)用接收码组R(x)=T(x)+E(x)除以生成多项式g(x),得到余式r(x)。(2)根据余式r(x)用查表方法或运算得到错误图样E(x),就可确定误码位置。(3)从R(x)中减去E(x),就可得到已经纠正错误的原始发送码组T(x)。解码信息输出图11-7b(7,3)循环码纠错解码器⊕

a

b

c

d⊕⊕⊕

与门⊕

缓冲移位寄存器接收编码输入第十一章差错控制编码11.6

循环码11.6.3缩短循环码研究表明，并不是任意码组长度n

和信息位k都可以找到满足某纠错能力的循环码。但若将某已知循环码缩短，就可能满足码长n

、信息位长度k和纠错能力要求。给定已知(n,k)循环码集合，使前i(0<i<k)个高阶信息位数字全为“0”,于是得到有2k-i个码组的集合,然后从这些码组中删去这i个零信息位数字，最终得到一组新的(n-i,k-i)线性分组码，就是缩短循环码。例如，若欲构造具有1位误码纠正能力的(13,9)码，则可以由(15,11)汉明码的全部211条码组中，挑选出前两位皆为“0”的码组29

，构成一个新的码组集合。而在传输时，两个零信息位不发送，即发送的是(13,9)缩短循环码。缩短循环码和原始循环码相比，缩短的是信息位，监督位并没减少，因此检错纠错能力不会减少。第十一章差错控制编码11.6

循环码11.6.4BCH(Bose-Chaudhuri-Hocguenghem)码在系统设计中，通常是在给定纠正随机误码的个数条件下寻找码生成多项式g(x)，从而得到满足一定抗干扰性能要求的编码。BCH码就是为解决这一问题研究发展起来的一类纠正多个随机错误的循环码。■

本原BCH码本原BCH码的码长为n=2m-1(m是大于或等于3的整数),其生成多项式g(x)中含有最高次数为m次的本原多项式。■

非本原BCH码本原BCH码的码长n为(2m-1)的一个因子，其生成多项式g(x)中不含有最高次数为m次的本原多项式。可以证明：

对于正整数m(m≧3)和t(t<m/2),必存在“码长n=2m-1，监督位数目r

≦

mt,能够纠正不大于t

个的随机误码”的BCH码。第十一章差错控制编码11.6

循环码11.6.4BCH(Bose-Chaudhuri-Hocguenghem)码表11-8二进制本原BCH码参数——

n、k、t、g(x)n

k

t

g(x)n

k

t

g(x)41136357110313775121247111123453170131772721394166623567532467365103350042317777773061574641653472614524717323260404441212355118101363026512351725163107657115542332512712012116731336504711324156711517777777777多项式系数(八进制)111010001g(x)=x8+x7+x6+x4+1第十一章差错控制编码11.6

循环码11.6.4BCH(Bose-Chaudhuri-Hocguenghem)码11.6

循环码11.6.5里德-索洛蒙(Reed-Solomon)码见讲义（略）表11-9部分非本原BCH码参数nktg(x)17927272112216632312353433322251454121466471334724543073357655321076165404354300067734641717773537多项式系数(八进制)101001100101g(x)=x11+x9+x6+x5+x2+1255=17×152047=23×89第十一章差错控制编码11.7

卷积码(连环码)前述的分组码在编码时，各长度为n的码组进行分别编码。即对于给定的k个信息位，附加上仅仅与这k个信息位有关的r个监督位，形成长度为n的码组。各个码组之间没有任何约束关系，因此在译码时各个码组也是分别独立地进行。卷积码在编码时，长度为n的码组由k个信息位附加上r个监督位，形成长度为n的码组。但是这r个监督位不仅仅与当前的k个信息位有关，还和前面的(N-1)个码组中的信息位有关。这样若干个(N)码组形成一种约束关系。卷积码的约束长度:以码组为单位时为N,以码元为单位时为nN

。码组长度为n,信息位组长度为k,约束长度为N个码组的卷积码记为(n,k,N)卷积码,卷积码的编码效率为Rc=k/n。第十一章差错控制编码11.7

卷积码11.7.1

卷积码的图形表示M3M2M1⊕⊕输入序列m1,m2,…,mj

,…输出序列m1y21y31,m2y22y32,…图