信息论第五章

1、信息论课件第五章第1页，共28页，2022年，5月20日，1点22分，星期一(1) 循环码的性质循环码是线性分组码的一个重要子类；由于循环码具有优良的代数结构，使得可用简单的反馈移位寄存器实现编码和伴随式计算，并可使用多种简单而有效的译码方法；循环码是研究最深入、理论最成熟、应用最广泛的一类线性分组码。第2页，共28页，2022年，5月20日，1点22分，星期一(2) 循环码的定义循环码：如果 (n,k) 线性分组码的任意码矢C=(Cn1,Cn2,C0) 的 i 次循环移位，所得矢量C(i)=(Cn1i,Cn2i,C0,Cn1,Cni) 仍是一个码矢，则称此线性码为 (n,k) 循环码。第3页

2、，共28页，2022年，5月20日，1点22分，星期一(3) 码多项式码多项式：为了运算的方便，将码矢的各分量作为多项式的系数，把码矢表示成多项式，称为码多项式。其一般表示式为C(x)=Cn1xn1+Cn2xn2+C0)码多项式 i 次循环移位的表示方法 记码多项式C(x)的一次左移循环为 C(1)(x) ，i 次左移循环为 C(i)(x)第4页，共28页，2022年，5月20日，1点22分，星期一码多项式的模 (xn+1) 运算0和1两个元素模2运算下构成域。第5页，共28页，2022年，5月20日，1点22分，星期一码矢 C 循环 i 次所得码矢的码多项式 C(x) 乘以 x，再除以 (x

3、n+1)，得第6页，共28页，2022年，5月20日，1点22分，星期一上式表明：码矢循环一次的码多项式 C(1)(x) 是原码多项式 C(x)乘以 x 除以 (xn+1) 的余式。写作因此， C(x) 的 i 次循环移位 C(i)(x) 是 C(x) 乘以 xi 除以 (xn+1) 的余式，即结论：循环码的码矢的 i 次循环移位等效于将码多项式乘 xi 后再模 (xn+1)。第7页，共28页，2022年，5月20日，1点22分，星期一(4) 举例：(7,3) 循环码可由任一个码矢，比如 (0011101) 经过循环移位，得到其它6个非0码矢；也可由相应的码多项式(x4+x3+x2+1)，乘以

4、xi(i=1,2,6)，再模(x7+1)运算得到其它6个非0码多项式。移位过程和相应的多项式运算如表6.3.1所示。第8页，共28页，2022年，5月20日，1点22分，星期一第9页，共28页，2022年，5月20日，1点22分，星期一(1) 循环码的生成矩阵根据循环码的循环特性，可由一个码字的循环移位得到其它的非0码字。在 (n,k) 循环码的 2k 个码字中，取前 (k1) 位皆为0的码字 g(x)（其次数r=nk），再经 (k1) 次循环移位，共得到 k 个码字:g(x),xg(x),xk1 g(x) 这 k 个码字显然是相互独立的，可作为码生成矩阵的 k 行，于是得到循环码的生成矩阵

5、G(x)第10页，共28页，2022年，5月20日，1点22分，星期一(2) 循环码的生成多项式码的生成矩阵一旦确定，码就确定了；这就说明： (n,k) 循环码可由它的一个 (nk) 次码多项式 g(x) 来确定；所以说 g(x) 生成了 (n,k) 循环码，因此称 g(x) 为码的生成多项式。第11页，共28页，2022年，5月20日，1点22分，星期一(3) 生成多项式和码多项式的关系定理：在 (n,k) 循环码中，生成多项式 g(x) 是惟一的 (nk) 次码多项式，且次数是最低的。定理：在 (n,k) 循环码中，每个码多项式 C(x) 都是 g(x) 的倍式；而每个为 g(x) 倍式且

6、次数小于或等于 (n1) 的多项式，必是一个码多项式。 第12页，共28页，2022年，5月20日，1点22分，星期一(定理6.3.2的逆定理)：在一个 (n,k) 线性码中，如果全部码多项式都是最低次的 (nk) 次码多项式的倍式，则此线性码为一个 (n,k) 循环码。 注：一般说来，这种循环码仍具有把 (n,k) 线性码码中任一非0码矢循环移位必为一码矢的循环特性，但从一个非0码矢出发，进行循环移位，就未必能得到码的所有非0码矢了。所以称这种循环码为推广循环码。第13页，共28页，2022年，5月20日，1点22分，星期一码字循环关系图单纯循环码的码字循环图：(7,3)循环码第14页，共2

7、8页，2022年，5月20日，1点22分，星期一推广循环码的码字循环图：(6,3)循环码第15页，共28页，2022年，5月20日，1点22分，星期一(4) 如何寻找一个合适的生成多项式由下面式子可知：循环码的多项式等于信息多项式乘以生成多项式。 这说明：对一个循环码只要生成多项式一旦确定，码就确定了，编码问题就解决了。 所以：作一循环码的关键，就在于寻找一个适当的生成多项式。第16页，共28页，2022年，5月20日，1点22分，星期一定理： (n,k) 循环码的生成多项式 g(x) 是 (xn+1)的因式，即 xn+1=h(x)g(x)。定理：若 g(x) 是一个 (nk) 次 多项式，且

8、为(xn+1) 的因式，则 g(x) 生成一个 (n,k) 循环码。结论：当求作一个(n,k)循环码时，只要分解多项式(xn+1) ，从中取出(nk)次因式作生成多项式即可。第17页，共28页，2022年，5月20日，1点22分，星期一举例：求 (7,3) 循环码的生成多项式。解：分解多项式 xn+1，取其4次因式作生成多项式x7+1= (x+1) (x3+x2+1) (x3+x+1)可将一次和任一个三次因式的乘积作为生成多项式，因而可取 g1(x)= (x+1) (x3+x2+1) = x4+x2+x+1 或 g2(x)= (x+1) (x3+x+1) = x4+x3+x2+1第18页，共2

9、8页，2022年，5月20日，1点22分，星期一(5) 循环码的监督多项式和监督矩阵循环码的监督多项式：设 g(x) 为 (n,k) 循环码的生成多项式，必为 (xn+1) 的因式，则有 xn+1=h(x)g(x)，式中h(x) 为 k 次多项式，称为 (n,k) 循环码的监督多项式。(n,k) 循环码也可由其监督多项式完全确定。举例： (7,3) 循环码 x7+1= (x3+x+1)(x4+x2+x+1)4次多项式为生成多项式g(x)=x4+x2+x+1=g4x4+g3x3+g2x2+g1x+g03次多项式是监督多项式h(x)=x3+x+1=h3x3+h2x2+h1x+h0第19页，共28页

10、，2022年，5月20日，1点22分，星期一循环码的监督矩阵由等式 x7+1= h(x)g(x) 两端同次项系数相等得将上面的方程组 写成矩阵形式第20页，共28页，2022年，5月20日，1点22分，星期一上式中，列阵的元素是生成多项式 g(x) 的系数，是一个码字，那么第一个矩阵则为(7,3)循环码的监督矩阵，即第21页，共28页，2022年，5月20日，1点22分，星期一循环码监督矩阵的构成由式 (6.3.2) 可见，监督矩阵的第一行是码的监督多项式 h(x) 的系数的反序排列，第二、三、四行是第一行的移位；可用监督多项式的系数来构成监督矩阵第22页，共28页，2022年，5月20日，1

11、点22分，星期一(n,k) 循环码的监督矩阵对偶问题如果 xn+1=h(x)g(x)，其中 g(x) 为 (nk) 次多项式，以 g(x)为生成多项式，则生成一个 (n,k) 循环码；以 h(x) 为生成多项式，则生成 (n,nk) 循环码；这两个循环码互为对偶码。第23页，共28页，2022年，5月20日，1点22分，星期一线性码的译码是根据接收字多项式的伴随式和可纠的错误图样间的一一对应关系，由伴随式得到错误图样；循环码是线性码的一个特殊子类，循环码的译码与线性码的译码步骤基本一致。不过由于循环码的循环特性，使它的译码更加简单易行；循环码的译码过程仍包括三个步骤：接收多项式的伴随式计算；求伴随式对应的错误图样；用错误图样纠错。6.3.6 循环码的译码第24页，共28页，2022年，5月20日，1点22分，星期一(1) 根据伴随式定义 ST=HRT 计算伴随式S设设第25页，共28页，2022年，5月20日，1点22分，星期一这是前面介绍过的由接收矢量相应分量直接求和计算伴随式的方法，对所有线性码都适用。第26页，共28页，2022年，5月20日，1点22分，星期一第27页，共28页，2022年，5月20日，1点22分，星期一(4) 接收字循环移位的伴随式与伴随式循环移位的关系：设 S(x) 为接收矢量 R(x) 的伴随式，则 R(x) 的循环移位 xR(x) (mod (xn