信息论与编码-第8章-第15讲-信道编码-循环码1.ppt

6.3.1 循环码的多项式描述 6.3.2 循环码的生成多项式 6.3.3 系统循环码 6.3.4 多项式运算电路 6.3.5 循环码的编码电路 6.3.6 循环码的译码 6.3.7 循环汉明码 6.3.8 缩短循环码 (1) 循环码的性质 循环码是线性分组码的一个重要子类； 循环码具有优良的代数结构。在结构上，它的循环性使得更容易用数学语言来描述；在性能上，具有明确的纠、检错能力，对于给定的码长n和信息位数k，已提出的各类循环码都有确定的纠、检错能力的理论计算值；在实现上，编码和译码都可以通过简单的反馈移位寄存器来完成,并可使用多种简单而有效的译码方法。 循环码是研究最深入、理论最成熟、应用最广泛的一类线性分组码。 (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) 循环码。 循环码举例 例 分析二进制码组{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, 1101, 0111, 1011, 1110}，它尽管满足循环性但由于不是线性码，故也不是循环码。 (3) 码多项式 码多项式：为了运算的方便，将码矢的各分量作为多项式的系数，把码矢表示成多项式，称为码多项式。其一般表示式为 C(x)=Cn－1xn－1+Cn－2xn－2+…+C0 码多项式 i 次循环移位的表示方法 记码多项式C(x)的一次左移循环为 C(1)(x) ，i 次左移循环为 C(i)(x) 码多项式的模 (xn+1) 运算 0和1两个元素模2运算下构成域。 若 p 为素数，则整数全体在模 p 运算下的剩余类全体 在模 p 下构成域。 以 p=3 为模的剩余类全体 模3运算的规则如下： 码矢 C 循环 i 次所得码矢的码多项式 C(x) 乘以 x，再除以 (xn+1)，得 上式表明：码矢循环一次的码多项式 C(1)(x) 是原码多项式 C(x)乘以 x 除以 (xn+1) 的余式。写作 因此， C(x) 的 i 次循环移位 C(i)(x) 是 C(x) 乘以 xi 除以 (xn+1) 的余式，即 结论：循环码的码矢的 i 次循环移位等效于将码多项式乘 xi 后再模 (xn+1)。 (4) 举例：(7,3) 循环码， 可由任一个码矢，比如 (0011101) 经过循环移位，得到其它6个非0码矢； 也可由相应的码多项式(x4+x3+x2+1)，乘以xi(i=1,2,…,6)，再模(x7+1)运算得到其它6个非0码多项式。移位过程和相应的多项式运算如表6.3.1所示。 (1) 循环码的生成矩阵 根据循环码的循环特性，可由一个码字的循环移位得到其它的非0码字。在 (n,k) 循环码的 2k 个码字中，取前 (k－1) 位皆为0的码字 g(x)（其次数r=n－k），再经 (k－1) 次循环移位，共得到 k 个码字： g(x),xg(x),…,xk－1 g(x) (2) 循环码的生成多项式 码的生成矩阵一旦确定，码就确定了； 这就说明： (n,k) 循环码可由它的一个 (n－k) 次码多项式 g(x) 来确定； 所以说 g(x) 生成了 (n,k) 循环码，因此称 g(x) 为码的生成多项式。 (3) 生成多项式和码多项式的关系 定理6.3.1：在 (n,k) 循环码中，生成多项式 g(x) 是惟一的 (n－k) 次码多项式，且次数是最低的。 [证明]： 先证在 (n,k) 循环码系统中存在 (n－k) 次码多项式。 因为在 2k 个信息组中，有一个信息组为 ，它的对应码多项式的次数为 n－1－(k－1)=n－k (n－k) 次码多项式是