《信息论与编码第8章第15讲信道编码循环码课件》由会员分享，可在线阅读，更多相关《信息论与编码第8章第15讲信道编码循环码课件（57页珍藏版）》请在金锄头文库上搜索。
1、2020/9/18,1,我始终努力保持自己思想的自由，我可以放弃任何假说，无论是如何心爱的，只要事实证明它是不符。 -达尔文（英国）,2020/9/18,2,6.3.1 循环码的多项式描述 6.3.2 循环码的生成多项式 6.3.3 系统循环码 6.3.4 多项式运算电路 6.3.5 循环码的编码电路 6.3.6 循环码的译码 6.3.7 循环汉明码 6.3.8 缩短循环码,6.3 循环码,2020/9/18,3,(1) 循环码的性质 循环码是线性分组码的一个重要子类； 循环码具有优良的代数结构。在结构上，它的循环性使得更容易用数学语言来描述；在性能上，具有明确的纠、检错能力，对于给定的码长n
2、和信息位数k，已提出的各类循环码都有确定的纠、检错能力的理论计算值；在实现上，编码和译码都可以通过简单的反馈移位寄存器来完成,并可使用多种简单而有效的译码方法。 循环码是研究最深入、理论最成熟、应用最广泛的一类线性分组码。,6.3.1 循环码的多项式描述,6.3循环码,2020/9/18,4,(2) 循环码的定义 循环码：如果 (n,k) 线性分组码的任意码矢 C=(Cn1,Cn2,C0) 的 i 次循环移位，所得矢量 C(i)=(Cn1i,Cn2i,C0,Cn1,Cni) 仍是一个码矢，则称此线性码为 (n,k) 循环码。,6.3.1 循环码的多项式描述,6.3循环码,2020/9/18,5
3、,循环码举例 例 分析二进制码组000, 110, 101, 011, 00000, 01111, 10100, 11011, 0000, 1101, 0111, 1011, 1110是不是循环码。 解 看码组符不符合线性和循环的条件。 对于码组000, 110, 101, 011，它既是线性码又是循环码。事实上，它是对00, 01, 10, 11进行偶校验得到的码，是(3, 2)循环码。 对于码组00000, 01111, 10100, 11011，它是线性码但不是循环码。事实上，它是对消息序列00, 01, 10, 11进行编码得到的线性分组码(5, 2) 码。 对于码组0000, 110
4、1, 0111, 1011, 1110，它尽管满足循环性但由于不是线性码，故也不是循环码。,6.3.1 循环码的多项式描述,6.3循环码,2020/9/18,6,(3) 码多项式 码多项式：为了运算的方便，将码矢的各分量作为多项式的系数，把码矢表示成多项式，称为码多项式。其一般表示式为 C(x)=Cn1xn1+Cn2xn2+C0 码多项式 i 次循环移位的表示方法 记码多项式C(x)的一次左移循环为 C(1)(x) ，i 次左移循环为 C(i)(x),6.3.1 循环码的多项式描述,6.3循环码,2020/9/18,7,码多项式的模 (xn+1) 运算 0和1两个元素模2运算下构成域。,6.3
5、.1 循环码的多项式描述,6.3循环码,2020/9/18,8,若 p 为素数，则整数全体在模 p 运算下的剩余类全体 在模 p 下构成域。 以 p=3 为模的剩余类全体 模3运算的规则如下：,6.3.1 循环码的多项式描述,6.3循环码,2020/9/18,9,码矢 C 循环 i 次所得码矢的码多项式 C(x) 乘以 x，再除以 (xn+1)，得,6.3.1 循环码的多项式描述,6.3循环码,2020/9/18,10,上式表明：码矢循环一次的码多项式 C(1)(x) 是原码多项式 C(x)乘以 x 除以 (xn+1) 的余式。写作 因此， C(x) 的 i 次循环移位 C(i)(x) 是 C
6、(x) 乘以 xi 除以 (xn+1) 的余式，即 结论：循环码的码矢的 i 次循环移位等效于将码多项式乘 xi 后再模 (xn+1)。,6.3.1 循环码的多项式描述,6.3循环码,2020/9/18,11,(4) 举例：(7,3) 循环码， 可由任一个码矢，比如 (0011101) 经过循环移位，得到其它6个非0码矢； 也可由相应的码多项式(x4+x3+x2+1)，乘以xi(i=1,2,6)，再模(x7+1)运算得到其它6个非0码多项式。移位过程和相应的多项式运算如表6.3.1所示。,6.3.1 循环码的多项式描述,6.3循环码,2020/9/18,12,6.3.1 循环码的多项式描述,6
7、.3循环码,2020/9/18,13,(1) 循环码的生成矩阵 根据循环码的循环特性，可由一个码字的循环移位得到其它的非0码字。在 (n,k) 循环码的 2k 个码字中，取前 (k1) 位皆为0的码字 g(x)（其次数r=nk），再经 (k1) 次循环移位，共得到 k 个码字： g(x),xg(x),xk1 g(x),6.3.2 循环码的生成多项式,6.3循环码,这 k 个码字显然是相互独立的，可作为码生成矩阵的 k 行，于是得到循环码的生成矩阵 G(x),2020/9/18,14,(2) 循环码的生成多项式 码的生成矩阵一旦确定，码就确定了； 这就说明： (n,k) 循环码可由它的一个 (n
8、k) 次码多项式 g(x) 来确定； 所以说 g(x) 生成了 (n,k) 循环码，因此称 g(x) 为码的生成多项式。,6.3.2 循环码的生成多项式,6.3循环码,2020/9/18,15,(3) 生成多项式和码多项式的关系 定理6.3.1：在 (n,k) 循环码中，生成多项式 g(x) 是惟一的 (nk) 次码多项式，且次数是最低的。 证明： 先证在 (n,k) 循环码系统中存在 (nk) 次码多项式。 因为在 2k 个信息组中，有一个信息组为 ，它的对应码多项式的次数为 n1(k1)=nk (nk) 次码多项式是最低次码多项式。 若 g(x) 不是最低次码多项式，那么设更低次的码多项式
9、为g(x) ，其次数为 (nk1)。 g(x) 的前面 k 位为0，即 k个信息位全为0，而监督位不为0，这对线性码来说是不可能的，因此 g(x) 是最低次的码多项式，即 gnk 必为1。,6.3.2 循环码的生成多项式,6.3循环码,2020/9/18,16,g0=1，否则经 (n1) 次左移循环后将得到低于 (nk) 次的码多项式。 g(x) 是惟一的 (nk) 次多项式。 如果存在另一个 (nk) 次码多项式，设为 g(x) ，根据线性码的封闭性，则 g(x) + g(x) 也必为一个码多项式。由于 g(x)和 g(x) 的次数相同，它们的和式的 (nk) 次项系数为0，那么 g(x)
10、+ g(x) 是一个次数低于 (nk) 次的码多项式，前面已证明 g(x) 的次数是最低的，因此 g(x) 不能存在，所以 g(x) 是惟一的 (nk) 次码多项式。,6.3.2 循环码的生成多项式,6.3循环码,2020/9/18,17,令 是(n, k)循环码C中最低次数的非零码多项式，则常数项g0必为1。 证明 设g0=0 则 将g (x)循环右移1位或循环左移n 1位，记为 有 它是一个次数小于r的非零码多项式，与g (x)是最低次数的非零码多项式的假设相矛盾，故g0必为1。因此 证毕。 （实质上是论证了生成多项式必有常数项）,6.3.2 循环码的生成多项式,6.3循环码,2020/9
11、/18,18,定理6.3.2：在 (n,k) 循环码中，每个码多项式 C(x) 都是 g(x) 的倍式；而每个为 g(x) 倍式且次数小于或等于 (n1) 的多项式，必是一个码多项式。 证明： 设 m=(mk1,mk2,m0) 为任一信息组，G(x) 为该 (n,k) 循环码的生成矩阵，则相应的码多项式为,6.3.2 循环码的生成多项式,6.3循环码,2020/9/18,19,上式表明：循环码的任一码多项式为 g(x) 的倍式。 显然，凡是为 g(x) 的倍式且次数小于或等于 (n1) 的多项式，一定能分解成上式的形式，因而它就是信息多项式 m(x)=(mk1xk1+mk2 xk2+m0) 并
12、由生成矩阵 G(x) 所生成的码多项式。 定理6.3.3(定理6.3.2的逆定理)：在一个 (n,k) 线性码中，如果全部码多项式都是最低次的 (nk) 次码多项式的倍式，则此线性码为一个 (n,k) 循环码。 注：一般说来，这种循环码仍具有把 (n,k) 线性码码中任一非0码矢循环移位必为一码矢的循环特性，但从一个非0码矢出发，进行循环移位，就未必能得到码的所有非0码矢了。所以称这种循环码为推广循环码。,6.3.2 循环码的生成多项式,6.3循环码,2020/9/18,20,码字循环关系图 单纯循环码的码字循环图：(7,3)循环码,6.3.2 循环码的生成多项式,6.3循环码,2020/9/
13、18,21,推广循环码的码字循环图：(6,3)循环码,6.3.2 循环码的生成多项式,6.3循环码,2020/9/18,22,(4) 如何寻找一个合适的生成多项式 由下面式子可知：循环码的多项式等于信息多项式乘以生成多项式。 这说明：对一个循环码只要生成多项式一旦确定，码就确定了，编码问题就解决了。 所以：作一循环码的关键，就在于寻找一个适当的生成多项式。,6.3.2 循环码的生成多项式,6.3循环码,2020/9/18,23,定理6.3.4： (n,k) 循环码的生成多项式 g(x) 是 (xn+1)的因式，即 xn+1=h(x)g(x)。 证明： 由于 xk g(x) 是 n 次多项式，可
14、表示为 xk g(x)=1(xn+1)+ g(k)(x) (6.3.1) 式中 g(k)(x) 是码多项式 g(x) 乘以 xk 除以 (xn+1) 的余式。 根据循环码的移位关系，它是 g(x) 循环移位 k 次所得到的码多项式，因而 g(k)(x) 是 g(x) 的倍式。 设 g(k)(x)=m(x)g(x) 代入式(6.3.1)得 (xn+1)=xk+m(x)g(x) 上式表明： g(x) 是 (xn+1) 的因式。,6.3.2 循环码的生成多项式,6.3循环码,2020/9/18,24,定理6.3.5：若 g(x) 是一个 (nk) 次 多项式，且为(xn+1) 的因式，则 g(x)
15、生成一个 (n,k) 循环码。 证明： 由于 g(x) 是一个 (nk) 次多项式，且为 (xn+1) 的因式，所以 g(x), xg(x), xk1 g(x) 是 k 个次数小于 n，并且彼此独立的多项式；,6.3.2 循环码的生成多项式,6.3循环码,将此多项式用作码的生成矩阵的 k 行，得到 (n,k) 线性码的生成矩阵；,2020/9/18,25,设信息组 m=(mk1,mk2,m0)，则相应的码字为 C(x)=mG(x)=(mk1xk1+mk2 1xk2+m0)g(x)= m(x)g(x) C(x)n1； m(x) 是 2k 个信息多项式的表示式； 所以 C(x) 即为相应 2k 个
16、码多项式的表示式。 因此，g(x) 生成一个 (n,k) 线性码。 C(x) 是 (nk) 次多项式 g(x) 的倍式，所以 g(x) 生成一个 (n,k)循环码。 结论：当求作一个(n,k)循环码时，只要分解多项式(xn+1) ，从中取出(nk)次因式作生成多项式即可。,6.3.2 循环码的生成多项式,6.3循环码,2020/9/18,26,举例：求 (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,6.3.
