西北大学信息科学与技术学院：《信息与编码》课程教学课件（PPT讲稿）第五章（5-3）循环码

循环码 1、循环码的多项式描述 2、循环码的生成多项式 3、系统循环码 4、多项式运算电路 5、循环码的编码电路 6、循环码的译码 7、循环汉明码 8、缩短循环码

1 、循环码的多项式描述 2 、循环码的生成多项式 3 、系统循环码 4 、多项式运算电路 5 、循环码的编码电路 6 、循环码的译码 7 、循环汉明码 8 、缩短循环码 循环码

(1)循环码的性质 循环码是线性分组码的一个重要子类; ■由于循环码具有优良的代数结构,使得可用简 单的反馈移位寄存器实现编码和伴随式计算 并可使用多种简单而有效的译码方法; ■循环码是研究最深入、理论最成熟、应用最广 泛的一类线性分组码

(1) 循环码的性质 ◼ 循环码是线性分组码的一个重要子类； ◼ 由于循环码具有优良的代数结构，使得可用简 单的反馈移位寄存器实现编码和伴随式计算， 并可使用多种简单而有效的译码方法； ◼ 循环码是研究最深入、理论最成熟、应用最广 泛的一类线性分组码

(2)循环码的定义 ■循环码:如果(n,k线性分组码的任意码矢 7-1rn-2r…r0 的j次循环移位,所得矢量 -1-in-2-j…r0,n-1r…rn 仍是一个码矢,则称此线性码为(心)循环码

(2) 循环码的定义 ◼ 循环码：如果 (n,k) 线性分组码的任意码矢 C=(Cn－1 ,Cn－2 ,…,C0 ) 的 i 次循环移位，所得矢量 C(i)=(Cn－1－i ,Cn－2－i ,…,C0 ,Cn－1 ,…,Cn－i ) 仍是一个码矢，则称此线性码为 (n,k) 循环码

(3)码多项式 ■码多项式:为了运算的方便,将码矢的各分量作为多 项式的系数,把码矢表示成多项式,称为码多项式 其一般表示式为 Cx=C-1X-1+C-2X-2+.+co) ■码多项式j次循环移位的表示方法 记码多项式以刈)的一次左移循环为￠1(x),/次左移 循环为c(x) C(r)=Cnx+Cr-2 c n2-1 Co(x)=CLix--+Cn-2- x2-+.+Cox+Cn-I

(3) 码多项式 ◼ 码多项式：为了运算的方便，将码矢的各分量作为多 项式的系数，把码矢表示成多项式，称为码多项式。 其一般表示式为 C(x)=Cn－1x n－1+Cn－2x n－2+…+C0 ) ◼ 码多项式 i 次循环移位的表示方法 记码多项式C(x)的一次左移循环为 C(1)(x) ，i 次左移 循环为 C(i) (x)

码多项式的模(X+1)运算 ■0和1两个元素模2运算下构成域。 0 00 ×0 000 0

◼ 码多项式的模 (x n+1) 运算 ◼ 0和1两个元素模2运算下构成域。 + 0 1 0 0 1 1 1 0 × 0 1 0 0 0 1 0 1

码矢￠循环/次所得码矢的码多项式 a)=C2 2 C()=ChY +C+Cn2+…+C c(x)乘以X,再除以(+1),得 xc(x) "+Cx+.+C x+Cx+C x+1 x"+1 1×C

◼ 码矢 C 循环 i 次所得码矢的码多项式 ◼ C(x) 乘以 x，再除以 (x n+1)，得

上式表明:码矢循环一次的码多项式￠1(x)是原码 多项式c(x)乘以X除以(X+1)的余式。写作 c(x)=x.C(x)(模x"+1 因此,(刈)的/次循环移位c(刈是∝刈乘以ⅹ 除以(x+1)的余式,即 c(x)=x2·C(x)(模x"+1) 结论:循环码的码矢的j次循环移位等效于将码多 项式乘ⅹ后再模(X+1)

上式表明：码矢循环一次的码多项式 C(1)(x) 是原码 多项式 C(x)乘以 x 除以 (x n+1) 的余式。写作 因此， C(x) 的 i 次循环移位 C(i) (x) 是 C(x) 乘以 x i 除以 (x n+1) 的余式，即 ◼ 结论：循环码的码矢的 i 次循环移位等效于将码多 项式乘 x i 后再模 (x n+1)

(4)举例:(73)循环码 ●可由任一个码矢,比如(0011101)经过循环移位, 得到其它6个非0码矢; ●也可由相应的码多项式(X4++2+1),乘以 X(1,2,,6),再模(x+1)运算得到其它6个非0码 多项式。移位过程和相应的多项式运算如表631所 小

(4) 举例：(7,3) 循环码 可由任一个码矢，比如 (0011101) 经过循环移位， 得到其它6个非0码矢； 也可由相应的码多项式(x 4+x 3+x 2+1)，乘以 x i (i=1,2,…,6)，再模(x 7+1)运算得到其它6个非0码 多项式。移位过程和相应的多项式运算如表6.3.1所 示

表6.3.1循环码的循环移位 移位次数码字 码多项式 0011101x4+x3+x2+1 (模x2+1) 0=1=2=3 0111010x(x4+x3+x2+1)=x3+x4+x+x(模x+1) 110100x2(x4+x3+x2+1)=x+x3+x4+x2(模x+1) 11001x2(x4+x2+x2+1)=x9+x2+x+1(模x2+1) 1010011x(x4+x3+x2+1)=x°+x4+x+1(模x2+1) 010011x2(x4+x2+x2+1)=x2+x2+x+1(模x2+1) 1001110x°(x 4+x2+x2+1)=x3+x3+x2+x(模x+1)

表 6.3.1 循环码的循环移位 移位次数 码 字 码多项式 0 0011101 x 4 +x 3 +x 2 +1 (模 x 7 +1) 1 0111010 x(x 4 +x 3 +x 2 +1)≡x 5 +x 4 +x 3 +x (模 x 7 +1) 2 1110100 x 2 (x 4 +x 3 +x 2 +1)≡x 6 +x 5 +x 4 +x 2 (模 x 7 +1) 3 1101001 x 3 (x 4 +x 3 +x 2 +1)≡x 6 +x 5 +x 3 +1 (模 x 7 +1) 4 1010011 x 4 (x 4 +x 3 +x 2 +1)≡x 6 +x 4 +x+1 (模 x 7 +1) 5 0100111 x 5 (x 4 +x 3 +x 2 +1)≡x 5 +x 2 +x+1 (模 x 7 +1) 6 1001110 x 6 (x 4 +x 3 +x 2 +1)≡x 6 +x 3 +x 2 +x (模 x 7 +1)

1)循环码的生成矩阵 ■根据循环码的循环特性,可由一个码字的循环移位得 到其它的非0码字。在()循环码的2K个码字中, 取前(k-1)位皆为0的码字9(x)(其次数广=n-k), 再经(k-1)次循环移位,共得到k个码字 9),g(x),…,x19(x 这k个码字显然是相互独 g(x) 立的,可作为码生成矩阵 g(x) 的k行,于是得到循环码 的生成矩阵Gx) xg(x) g(x)

(1) 循环码的生成矩阵 ◼ 根据循环码的循环特性，可由一个码字的循环移位得 到其它的非0码字。在 (n,k) 循环码的 2 k 个码字中， 取前 (k－1) 位皆为0的码字 g(x)（其次数r=n－k）， 再经 (k－1) 次循环移位，共得到 k 个码字: g(x),xg(x),…,x k－1 g(x) 这 k 个码字显然是相互独 立的，可作为码生成矩阵 的 k 行，于是得到循环码 的生成矩阵 G(x)