信息论与编码课件

1、7.3 7.3 循环码循环码 循环码是一种特殊的线性分组码，属于线性分组码的一个重要子类，也是目前研究最为透彻的一类码，大多数有实用价值的纠错码都是循环码。循环码与一般的线性分组码相比具有以下优点：循环码的编码及译码易于用简单的具有反馈连接的移位寄存器来实现。 定义：设有 线性分组码 ，如果它的任意一个码字的每一次循环移位仍然是 中的一个码字，则称 为循环码。也即，如果 是循环码 的一个码字，那么 等也都是 的码字时，则所有这些具有循环特性的码字的全体便构成了循环码。 ( , )n kCCC12 1()nnCc cc c C12 1(),nnCcc c c CC 例如此（7，3）线性分组码就是

2、循环码，如表所示。 信息码元码字0 0 00 0 0 0 0 0 00 0 10 0 1 1 1 0 10 1 00 1 0 0 1 1 10 1 10 1 1 1 0 1 01 0 01 0 0 1 1 1 01 0 11 0 1 0 0 1 11 1 01 1 0 1 0 0 11 1 11 1 1 0 1 0 07654321 ccccccc321 mmm循环码的主要特点是： 理论成熟：可利用成熟的代数结构深入探讨其性质； 实现简单：可利用循环移位特性在工程上进行编、译码； 循环码的描述方式有很多，但在工程上最有用的是采用多项式的描述方法。 由于循环码的以上特点，可以将其用多项式来表示，

3、从而可以借助代数的工具对循环码进行分析，这也是循环码能被广泛应用的原因之一。 6.3.1 循环码的多项式描述循环码的多项式描述 设有循环码字 ，则可以用一个次数不超过 的多项式惟一确定，其相应的多项式可表示为： 即码字 与码多项式 一一对应。 由循环码的特性可知，若 是循环码 的一个码字，则 也是该循环码的一个码字，它的码多项式为： 比较式两式，得：2 1()nCcc c 1n 121( )nnC xc xc xc C( )C x12 1()nnCc cc c (1)12 1()nnCcc c c (1)111( )nnnCxcxc xc1(1)11( )( )111nnnnnnnncxc x

4、cxC xCxccxxx 该式说明，码字循环一次的码多项式 是原码多项式 乘 后再除以 所得的余式，即： 由此可以推知， 的 次循环移位 是原码多项式 乘 后再除以 所得的余式，即： (6.3.3) 式(6.3.3)揭示了 线性码中码多项式与码字循环移位之间的关系，它对循环码的研究起着重要的作用。 (1)( )( )mod(1)nCxxC xx (1)( )Cx( )C xx1nx ( )C xi( )( )iCx( )C xix1nx ( )( )( )mod(1)iinCxx C xx ( , )n k 例如前面所述 循环码可由任一个码字(如“0011101”)经循环移位后，得到其他6个码

5、字；也可由相应的码多项式 乘以 后，再模 得到其他6个非零码多项式。这个移位过程及相应的多项式运算如表6.3.2所示。 (7,3)4321xxx(1,2,6)ix i 71x 表6.3.2 循环码的循环移位 4321xxx4327543(1)mod(1)x xxxxxxxx 243276542(1)mod(1)xxxxxxxxx 34327653(1)mod(1)1xxxxxxxx 4432764(1)mod(1)1xxxxxxxx 5432752(1)mod(1)1xxxxxxxx 64327632(1)mod(1)xxxxxxxxx 循环次数码字码多项式0 0 0 0 0 0 000 0

6、1 1 1 0 110 1 1 1 0 1 021 1 1 0 1 0 031 1 0 1 0 0 141 0 1 0 0 1 150 1 0 0 1 1 161 0 0 1 1 1 06.3.2 循环码的生成矩阵循环码的生成矩阵 根据循环码的循环特性，可由一个码字的循环移位得到其他非“0”码字。在 循环码的码多项式中，每一个能整除 的 次首一多项式(其最高次项系数为“l”)都是该码码的生成多项式的生成多项式，记为 。将 经过 次循环移位，共得到 个码多项式： 、 、 。这 个码多项式显然是相互独立的，可作为码生成矩阵的 行，于是得到 循环码的生成矩阵生成矩阵 ： (6.3.4) ( , )n

7、 k1nx ()nk ( )g x( )g x(1)k k( )g x( )xg x1( )kxg x kk( , )n k( )G x12( )( )( )( )( )kkxg xxg xG xxg xg x 码的生成矩阵一旦确定，码也就确定了。这说明 循环码可由它的一个 (n-k) 次首一多项式 来确定，所以可以说由 生成了 循环码，因此称 为码的生成多项式，即： (6.3.5) 如果某一个码具有生成多项式，则该码一定是循环码。 码的生成多项式具有如下性质： 在 循环码中， 次码多项式是最低次的码多项式。 在 循环码中， 是惟一的 次多项式。 在 循环码中，每个码多项式 都是 的倍式。 任

8、意 循环码的生成多项式 一定整除 。 ( , )n k( )g x( , )n k( )g x10( )n kn kg xgxg xg ( , )n k( , )n k( , )n k( )g x()nk ( , )n k( )C x( )g x( , )n k( )g x1nx 例：求二进制 循环码的生成多项式。 解：分解多项式 ，取其四次首一多项式作为生成多项式： 可将一次和任一个三次多项式的乘积作为生成多项式：或 由于 线性码的生成矩阵 与一致校验矩阵 满足关系： ，而循环码也是线性码，如果设 为 循环码的生成多项式，它必为 的因式，则有： (6.3.6) (7,3)71x 73321(

9、1)(1)(1)xxxxxx 342( )(1)(1)1g xxxxxxx 32432( )(1)(1)1g xxxxxxx ( , )n kGH0TGH ( )g x( , )n k71x 1( ) ( )nxg x h x 因为 是 次多项式，以 为生成多项式，则生成一个 循环码，以 为生成多项式，则生成一个 循环码，这两个循环码互为对偶码。称 为 循环码的校校验多项式验多项式，且： (6.3.7) 显然， 循环码也可由其校验多项式完全确定， 循环码的一致校验矩阵 为 (6.3.8) ( )g x()nk ( )g x( , )n k( )h x( ,)n nk ( )h x( , )n

10、k10( )kkh xh xh xh ( , )n k( , )n kH*2*1*( )( )( )( )( )n kn kh xxh xH xxh xxh x 式中 为 的反多项式： 011011011000000kkkkkkhhhhhhhhHhhhh *( )h x( )h x*1011( )kkkkh xh xh xhxh 6.3.3 系统循环码系统循环码 前面介绍的生成矩阵所产生循环码不是系统码。我们可以通过矩阵的行运算，得到系统循环码的生成矩阵，使之具有 的形式，生成矩阵的行运算实质上就是码字间 个基底间进行线性组合运算。系统循环码的生成矩阵的一致校验矩阵是 。 例6.3.4 以 为

11、生成多项式生成一个 循环码，要求生成的（7，4）循环码是系统的。 解：由例6.3.1得对应给定 的 循环码的一般生成矩阵为： kGIP HTn kPI k3( )(1)g xxx (7,4)( )g x(7,4)1011000 (1)0101100 (2)0010110 (3)0001011 (4)G 对矩阵 的行进行运算，将第、行相加后作为第1行，第、行相加后作为第2行，得： 对应： 这样，就得到系统循环码的生成矩阵和一致校验矩阵。 G01000101 (1)(3)(4)0100111(2)(4)00101100001011G 0111010001110101101001H 6.3.4 多项

12、式运算电路多项式运算电路 由于多项式 表示的是时间序列 ，因而多项式的运算表现为对时间序列的操作。 设有多项式 和 ，则： 与 的相加电路相加电路如图6.3.1所示。若 的阶数 小于 的阶数 ，则将 也扩充为 次多项式，其扩充的幂次项系数为“0”。图6.3.1 多项式相加 ( )nn10g x =g x +.+g x+gn10g =(g .g g )( )g x( )h xg(x)h(x)h(x)mg(x)n( )h xn 多项式的乘法电路乘法电路如图6.3.2所示，按照图6.3.2的乘法电路构成， 与 乘法的般电路如图6.3.3所示。在乘法电路中总假设多项式的低位在前，电路中的所有寄存器初态

13、为“0”。 图6.3.2 多项式乘法电路例 ( )g x( )h x图6.3.3 多项式乘法电路 设 ， ，则用多项式 去除任意多项式 的电路即为 除法电路除法电路，如图6.3.4所示。移位寄存器的初始状态全为“0”，当 输入完毕，移位寄存器( )中的内容即为余式。 图6.3.4 除法电路 10( )kkg xg xg xg 10( )rrh xh xh xh ( )h x( )g x( )h x( )g x011rp pp 例6.3.5 设被除式 与除式 都是系数为二进制的多项式，且： 则完成除以 的电路如图6.3.5所示。完成上述二个多项式相除的算式如下： 这里商为 ，余式为 ，表6.3.

14、3给出了图6.3.5电路的运算过程，经过 次移位后得到商 项的系数， =5次移位后，完成了整个除法运算，在移位寄存器中保存的数(001)代表余式 的系数。 ( )g x( )h x433( )1, ( )1g xxxh xxx( )h x43321(1)(1)xxxxxx 1x2x14r x1k 012()x x x00()p x11()p x22()p x4()x3()x2()x1()x1()x0()x0()x1 1 0 0 1 1 1节拍输入移位寄存器的内容输出000000111000211100300110401111510011余 式商式表6.3.3 例6.3.5的运算过程表 6.3.

15、5 循环码的编码电路循环码的编码电路 利用生成多项式 实现编码是循环码编码电路的常用实现方法。若已知信息位为 位，要求纠错能力为 ，可以按循环码的性质来设计循环码编码电路。 首先可以根据式： ，求出所需要的 和 求出 以后，再从 的因式中找出生成多项式 ，由 生成的码 就是满足要求的循环码。 给定 后，实现编码电路的方法有两种：一种方法采用 的乘法电路；另一种方法是除以 的除法电路。前者主要是利用方程式 进行编码，这样编出的码为非系统码；而后者是系统码编码器中常用的电路，所编出的码为系统码。我们在这里只介绍更常使用的系统码编码电路。( )g xkt121triniC n()rnk n1nx (

16、 )g x( )g xC( )g x( )g x( )g x( )( ) ( )C x =m x g x 设从信源输入编码器的位信息组多项式为： 如果要编出系统码的码字，则： (6.3.9) 从式(6.3.9)知，系统码的编码器就是将信息组 乘上 ，然后用生成多项式 除，求余式 的电路，由此得系统循环码的编码步骤如下： 以 乘以 ； 以 除以 ，得到余式 ； 组合 和 得互码字“ ”。 1110( )kkm xmxm xm ( )( )( )( )( )mod ( )n kn kC xm x xr xr xm x xg x ( )m xn kx ( )g x( )r xn kx ( )m x(

17、 )g xn kx ( )m x( )r x( )m x( )r x( )m x( )r x 实现系统循环码编码的电路如图6.3.6所示。图6.3.6 级系统码编码器 下面以二进制 循环码(汉明码)为例，来说明编码器的工作原理。 当输入信息码元为(1001)，即 ，设循环码的生成多项式 ，由系统码生成规则： 其运算过程为： (7,4)3( )1m xx 3( )1g xxx 7 43632( )(1),mod( )n kxm xxxxxxxg x 33636434422 1( )_ ( )nkxxxxxxxm xxxxxxxxxxr x 则： 由此得二进制循环系统码编码器如图6.3.7所示。电

18、路的编码过程如下： 三级移存器初始状态全为“0”，门1开，门2关。信息组以高位先入的次序送入电路，一方面经或门输出编码的前 个信息码元，另一方面送入 除法电路的右端，这对应于完成用 除 的除法运算。 ( )( )( )nkC xr xxm x 7432632(1)xxxxxxxx 1001110C k( )g x( )g xn kx ( )m x图6.3.7 循环系统码编码器 四次移位后，信息组全部通过或门输出，它就是系统码码字的前四个信息码元，同时它也全部进入除 电路，完成除法运算。此时在移存器 中存的数就是余式 的系数，也就是码字的校验码元 。 门1关闭，门2打开，再经三次移位后，移存器中

19、的校验码元 跟在信息组后面输出，形成一个完整的码字 。 门1打开，门2关闭，送入第二组信息组，重复上述过程。 ( )g x210p p p( )r x3 2 1()c c c3 2 1()c c c74635241321(,)cm cm cm cm c c c 表6.3.4列出了上述编码器的工作过程。设输入信息组为(1001)，七个移位脉冲过后，在输出端得到了已编好的码字(1001110)。 6.3.6 循环码的译码电路循环码的译码电路 若给定循环码的生成多项式 ，为求伴随式多项式 ，有以下定义： 定义6.3.2 循环码的伴随式多项式 是接收码字多项式 或错误图样多项式 除以生成多项式 所得的

20、余式。 若给定循环码的一致校验矩阵 ，则伴随式 式中 为发送端发送的码字， 为信道的错误图样。 循环码的伴随式译码一般包括以下三个步骤： 根据接收码字多项式 计算相应的伴随式多项式： 或 ，它等价于根据接收码字 来计算相应的伴随式 ： 。 ( )g x( )s x( )s x( )r x( )e x( )g xH()TTTSRHCE HEHCE( )r x( )( )mod ( )s xr xg x( )( )mod ( )s xe xg xRSTTS RHEH 根据伴随式 (或伴随式多项式 )求对应的错误图样。 利用错误图样进行纠错，得到对码字的估计(即译码输出)。下面我们用例题来说明循环码

21、伴随式译码的具体过程。 例6.3.6 已知二进制 循环码的生成多项式 ，一致校验矩阵为： 试设计能纠正一个信道错误的伴随式译码电路。 S( )s x(7,4)3( )1g xxx111010001110101101001H 解：由定义6.3.2知伴随式多项式 的计算，实际上是用 做除法并求余，所以伴随式译码器中必须要有除法电路。此外，必须根据所求得的伴随式结果进行正确的解码。 假设信道错误出现在最高位，即 ，对应的错误图样多项式为 ，则我们可以求得相应的伴随式多项式： 即相应的伴随式多项式为 ，对应的伴随式为 。 同样，我们也可以由一致校验矩阵求得伴随式为： 相应的译码电路如图6.3.8所示。

22、 ( )s x( )g x(1000000)E6( ) e xx263( )(1) ( )mod ( )/(1)s xxe xg xxxx2( )(1)s xx(101)S(101)TSEH图6.3.8 (7，4)循环码的伴随式译码器假设接收码字 ，其译码过程如下： 开始译码时，门1打开，7个时钟过后，全部进入七个缓冲器中，同时， 被 除的求余运算也巳进行完毕，除法电路中的三个移位寄存器中存放的是伴随式多项式的系数，其结果为 ，其中最低位对应于 ，最高位对应于 。 (1000000)R( )r x( )g x(101)S0S2S 接收码字输入完毕后，门1关闭。当第八个时钟到来时，开始纠错译码，

23、因为此时从 中出来的“101”数字经过非门后，变成“111”，所以与门的输出为“l”，与 的最高位相加，正好纠正了该位上的错误，因此，第八个时钟过后，在输出端输出的是“l”。此后，与门的输出都为“0”，随着时钟的到来，移位寄存器将后面的码字直接输出。 在纠正最高位上的错误的同时，与门输出的“l”被输入到 左端的加法器上，参加除法器的复位运算，此时除法器中三个移位寄存器被复位到“000”，准备进行下一个码字的译码。 0S2SR0p6.3.7 常用的循环码常用的循环码 循环冗余校验码 在数据通信中，信息都是先划分成小块再组装成帧后(或叫分组、包等，仅名称不同而已)在线路上统计复用传送或存入共同物理

24、介质的，帧尾一般都留有8、12、16或32位用作差错校验。如把一帧视为一个码字，则其校验位长度 不变而信息位 和码长 是可变的，其结构符合 缩短循环码的特点。只要以一个选定的 循环码为基础，改变 的值，就能得到任何信息长度的帧结构，而纠错能力保持不变。这种应用下的缩短循环码称为循环冗余校验码循环冗余校验码(Cyclic Redundancy Check，CRC)。 nkkn(,)n i ki( , )n ki 循环冗余校验码是系统的缩短循环码，码的结构如图6.3.10所示。图6.3.10 循环冗余校验码(CRC)结构 图中，码字用码多项式 表示， 是 除以 后的余式， 为 次多项式，它们之间满

25、足： 。虽然循环冗余校验码指的是整个码字 ，但人们习惯上仅把校验部分称为CRC码。 如果传输过程无差错，则接收码字 应等于发送码字 这时 能被 整除；如果 ，则说明在传输过程中出现了误码。 ( )C x( )r x( )n kxm x( )g x( )g xnk( )( )( )n kC xxm xr x( )C x( )r x( )C x( )r x( )g x( )( )r xC x 例6.3.7 某CRC的生成多项式为 。如果想发送一串信息“110001”的前6位，并加上CRC校验，发送码字 应如何安排，接收码字 又如何校验？解：本题信息码字多项式 ， ，从生成多项式 的阶数得校验位数等

26、于4，因此 。 将 除以 得余式 ： 于是，发送码字多项式 ， 对应的发送码字为(1100011100)。 4( )1g xxx( )C x( )r x54( )1m xxx6k( )g x10n( )n kxm x( )g x( )r x45432( )( )mod ( ) (1)mod ( ) n kr xxm xg xxxxg xxx( )( )( )n kC xxm xr x98432xxxxx 在接收端，CRC校验实际上就是做除法运算：如果传输过程无差错，则 能 被整除，余式为“0”；如果余式不为“0”，则说明一定有差错。 例6.3.8 假设 ，即信息码字为(1011001)， ，求

27、CRC校验码。由题得： ，用 去除 ，有： ( )r x( )g x643( )1m xxxx43( )1g xxx410874( ) x m xxxxx( )g x4( )x m x 经相除后得到的最后余数1010就是冗余校验码 。所以，发送码字为：(10110011010)。 需要注意的是，这里所涉及的运算与前面一样都是模2运算。 如果例子中的发送码字(10110011010)经传输后受噪声的干扰，在接收端变成为(10110011100)。求余式的除法如下： ( )r x 求得余式不为零，相当于在发送码字上加了差错图样“00000000110”。差错图样相应的多项式为 。有差错时，接收端收

28、到的不再是 ，而是 + 。由于： 若 ，则这种差错就能检测出来，若 ，那么由于接收到的码字多项式仍然可被 整除，错误就检测不出来，也即发生了漏检。 理论上可以证明，循环冗余校验码的检错能力如下： 可检测出所有奇数个错； 可检测出所有单比特和双比特的错； 2( ) e xxx( )C x( )Cx( )e x ( )+ ( ) ( ) ( )=+ ( ) ( ) ( )C xe xC xe xg xg xg x( )( )e x0g x ( )( )e x0g x ( )g x 可检测出所有小于、等于校验码长度 的突发错误； 对于 位的突发性错误，查出概率为 ； 对于多于 位的突发性错误，查出概

29、率为 。 由此可以看出，只要选择足够的冗余校验位，可以使得漏检率减到任意小的程度。 循环冗余编码法在数据传输中得到了最广泛的应用。CRC本身具有纠错功能，但网络中一般不用其纠错功能，仅用其强大的检错功能，检出错误后要求重发。 目前广泛使用的CRC码已成国际标准，生成多项式主要有下述四种： nk1nk(1)1 2r1nk1 2r CRC-12，其生成多项式： CRC-16，其生成多项式： CRC-CCITT，其生成多项式： CRC-32，其生成多项式： 循环冗余校验码的编译码过程通常用采用硬件来实现，因为除法运算易于用移位寄存器和模2加法器来实现，可以达到比较高的处理速度。随着集成电路工艺的发展

30、，循环冗余码的产生和校验均有集成电路产品，发送端能够自动生成CRC码，接收端可自动校验，速度大大提高。 121132( )1g xxxxxx16152( )1g xxxx16155( )1g xxxx322623221612111087542( )1g xxxxxxxxxxxxxxx(2) BCH码 BCH码是一类最重要的循环码，能纠正多个随机错误。这种码可以是二进制码，也可以是非二进制码。 BCH码具有纠错能力强，构造方便，编、译码易于实现等一系列优点。二进制本原BCH码具有下列参数： (6.3.10) 式中 和纠错能力 是任意的正整数。BCH码的码长为 或 的因子，通常称前者为本原本原BCH码码，称后者为非本原BCH码。 min2121 mnnkmtdt( 3)m1( 2)mt21mn21mn BCH码的基本特点是其生成多项式 包含 个连续幂次的根，由该 生成的循环码，其纠错能力不小于 。BCH码的出现为通信系统设计者们在纠错能力、码长和码率的灵活设计上提供了很大的选择余地，加上其构码方法带来的译码特点，可以用伯利坎普(Berlekamp)迭代译码等通用、高效的译码算法，所以BCH码从二十世纪七十年代起已成为线性分组码的主流。