循环码基础知识解析

1.循环码的定义

将GF（q）上的n维矢量c=（c₀，c₁，…，c_n-2，c_n-1）的分量循环右移一位，得到的新的n维矢量c（1）=（c_n-1，c₀，c₁，…，c_n-2）称为矢量c的循环移位。类似地，将矢量c的分量循环右移i位，得到的新的n维矢量是c（i）=（c_n-i，…，c_n-1，c₀，c₁，…，c_n-i-1）。

显然，矢量c循环右移i位等价于矢量c循环左移n-i位。

定义6.59 若q元（n，k，d）线性分组码C的任意码字c=（c₀，c₁，…，c_n-2，c_n-1）的循环右移一位得到的矢量c（1）=（c_n-1，c₀，c₁，…，c_n-2）也是该码的码字，则称C为循环码。

【例6.39】

二元（7，3，4）线性分组码的生成矩阵为

由此得到该码的2³=8个码字是c₀=0000000，c₁=1011100，c₂=0101110，c₃=0010111，c₁+c₂=1110010，c₁+c₃=1001011，c₂+c₃=0111001，c₁+c₂+c₃=1100101。事实上，该码的循环右移一位仍然是该码集中的一个码字。可以验证如下：c₀→c₀，c₁→c₂，c₂→c₃，c₃→c₁+c₃，c₁+c₂→c₂+c₃，c₁+c₃→c₁+c₂+c₃，c₂+c₃→c₁，c₁+c₂+c₃→c₁+c₂。

例6.39、例6.28和例6.29讨论的分组码都是纠错能力相同的（7，3，4）线性分组码，但是，例6.39定义的码具有循环特性，而例6.28和例6.29的码不具有循环特性。

2.循环码的多项式描述

GF（q）上的循环码是具有循环特性的线性分组码，是线性分组码的一个重要子类。循环码类具有很多可以简化实现编码和译码的代数性质。为了用代数理论研究循环码，可以将码字用多项式来表示，其映射关系如下：

式（6.49）建立了码字c和多项式c（x）的一一对应关系，称c（x）为码字c的码多项式。多项式c（x）的系数就是码字c各分量的值，x为任意实变量，x的幂次代表该分量的位置。每个码字与等于或少于n-1次的多项式相对应。若c_n-1≠0，则c（x）的次数是n-1；若c_n-1=0，则c（x）的次数小于n-1。下面将不加区分地使用码字、码矢和码多项式等术语。

由定义6.59知，若c=（c₀，c₁，…，c_n-2，c_n-1）是循环码的一个码字，则c（1）=（c_n-1，c₀，c₁，…，c_n-2）也是该循环码的一个码字，c（1）的码多项式为

将式（6.50）与式（6.49）比较可知

同理，xc^（1）（x）对应的码字c^（2）相当于将码字c^（1）右移一位，亦即c右移两位，由此可得

依此类推，不难得出循环右移i位时，有

可见，xⁱc（x）在模xⁿ-1的余式对应着将码字c右移i位的码字c^（i）。因此有以下定理：

定理6.31 若c（x）是GF（q）上n长循环码C中的一个码多项式，则xⁱc（x）按模xⁿ-1运算的余式必为循环码中另一码多项式。(www.xing528.com)

为了表述简单，在码多项式的表示中不一定写出mod xⁿ-1，而用类似式（6.50）来表示。

观察循环码的所有码多项式，不难发现，除全0码字外，循环码中必存在至少一个最低次多项式。该多项式在循环码的理论分析和应用中具有十分重要的意义。显然，令

是GF（q）上循环码C中最低次数的非0码多项式，则必有g₀≠0，g_r≠0。特别地，对于二元循环码必有g₀=g_r=1。下述几个定理重点描述这个多项式的若干性质：

定理6.32 GF（q）上（n，k，d）循环码C中有唯一的非0最低次首一多项式g（x）。

由定理6.32知，在循环码中，次数最低的非0码首一多项式有如下形式：

考虑多项式g^（1）（x）=xg（x），g^（2）（x）=x²g（x），…，g^（n-r-1）（x）=x^n-r-1g（x），它们的次数分别为r+1，r+2，…，n-1，且由式（6.49）知它们皆是码多项式g（x）的循环移位。因此，它们是C中的码多项式。由于C是线性码，因而g（x），xg（x），…，x^n-r-1g（x）的线性组合

也是码多项式。式中，m_i∈GF（q）（i=0，1，…，n-r-1）。

定理6.33 令g（x）是q元循环码C中次数最低的非0首一码多项式，则次数等于或小于n-1次的GF（q）上的多项式c（x），当且仅当它是g（x）的倍式时才是码多项式。

等于或小于n-1次且是g（x）倍式的GF（q）上的多项式共有q^n-r个。由定理6.33知，这些多项式形成了（n，k，d）循环码C中的所有码多项式。因为C中有q^k个码多项式，所以q^n-r必须等于q^k。结果有r=n-k（即g（x）的次数是n-k）。因此，在（n，k，d）循环码中次数最低的非0首一码多项式有如下形式：

归纳以上结果，得到下面的重要定理：

定理6.34 q元（n，k，d）循环码C中，有且仅有唯一的n-k次首一码多项式g（x），每个码多项式都是g（x）的倍式，且每个是g（x）倍式的、等于或小于n-1次多项式必为码多项式。

3.缩短循环码

在实际工程设计中，循环码的码长n、信息元位数k常与实际需要不一致。为此，常常把（n，k，d）循环码缩短成（n-l，k-l）码，使其适合工程的需要。

定义6.60 在（n，k，d）循环码C中，取其最后l位码元为0的所有码字，并去掉这l位码元，组成一个新的（n-l，k-l）码，称该码为缩短循环码。

q元（n，k，d）循环码的码字有q^k个，其最后l位码元为0的码字有q^k-l个，因此，缩短循环码共有q^k-l个码字。可以证明，缩短循环码是线性分组码，一般该码不具有循环性质。由定理6.30知，缩短循环码的纠错能力至少与导出该码的原码相同。

显然，将（n-l，k-l）缩短循环码的每个码字后面补上l个0码元所组成的码集合，是原（n，k，d）循环码的一个子集。所以，（n-l，k-l）缩短循环码的编码和译码方法与原循环码的编码和译码方法有密切关系。