第3 章 循环码编码和译码
3.1 循环码概念
循环码是线性分组码中一个重要的分支。它的检、纠错能力较强，编码和译码设备并不复杂，而且性能较好，不仅能纠随机错误，也能纠突发错误。
循环码是目前研究得最成熟的一类码，并且有严密的代数理论基础，故有许多特殊的代数性质，这些性质有助于按所要求的纠错能力系统地构造这类码，且易于实现，所以循环码受到人们的高度重视，在FEC系统中得到了广泛应用。
3.1.1、循环码定义
定义：一个线性分组码，若具有下列特性，则称为循环码。设码字
A?(an?1an?2... (3-1) a1a0)若将码元左移一位，得
A(1)?(an?2an?1...a1a0an?1)A(1)也是一个码字。
注意：循环码并非由一个码字的全部循环移位构成。
3.1.2 循环码的特点
表3-1列出了某（7，4）循环码的全部码组
码组 编号 a6 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 信息位 a5 0 0 0 0 1 1 1 1 a4 0 0 1 1 0 0 1 1 a3 0 1 0 1 0 1 0 1 a2 0 1 1 1 0 1 1 0 监督位 a1 0 0 1 0 1 1 0 0 a0 0 1 1 1 1 0 0 1 码组 编号 a6 9 10 11 12 13 14 15 16 1 1 1 1 1 1 1 1 信息位 a5 0 0 0 0 1 1 1 1 a4 0 0 1 1 0 0 1 1 a3 0 1 0 1 0 1 0 1 a2 1 0 0 1 1 0 0 1 监督位 a1 1 1 0 0 0 0 1 1 (3-2)
a0 0 1 1 0 1 0 0 1
循环码有两个数学特征：
1.线性分组码的封闭型：即如果c1，c2，是与消息m1，m2对应的码字，则c1+c2必定是与m1+m2对应的码字。
2.循环性，即任一许用码组经过循环移位后所得到的码组仍为该许用码组集合中的一个码组。
即若（an-1 an-2 … a1 a0）为一循环码组，则（an-2 an-3 … an an-1）、（an-3 an-2 … an-1 an-2）、……还是许用码组。也就是说，不论是左移还是右移，也不论移多少位，仍然是许用的循环码组。
以3号码组（0010111）为例，左移循环一位变成6号码组（0101110），依次左移一位构成的状态图如图1.1-2所示。
1001011 1100101 1110010 0010111 0101110 1011100 0111001
图3-1 （7，4）循环码中的循环圈
可见除全零码组外，不论循环右移或左移，移多少位，其结果均在该循环码组的集合中（全零码组自己构成独立的循环圈）。
3.2 码多项式
为了用代数理论研究循环码，可将码组用多项式表示，循环码组中各码元分别为多项式的系数。长度为n的码组A?(an?1an?2...a1a0)用码多项式表示则为
A(x)?an?1xn?1?an?2xn?2?...?a1x?a0式中，x的幂次是码元位置的标记。若把一个码组左移i位后的码组记为，
(3-3)
A(i)?(an?1?ian?2?i...an?i?1an?i)其码多项式为
(3-4)
A(i)(x)?an?1?ixn?1?an?i?2xn?2?...?an?1?ix?an?iA(i)(x)可以根据xiA(x)按模xn+1运算得到，即
(3-5)
A(i)(x)?xiA(x)mod(xn? (3-6) 1)或
xiA(x)?Q(x)(xn?1)?A(i)( (3-7) x)
式中，Q(x)为xiA(x)除以xn+1的商式，而xiA(x)等于A(i)(x)被xn+1除得之余式。 以码组0100111为例，若将此码左移两位，则由式（3-7）可得x2(x5+x2+x+1)=Q(x)(x7+1)+A(2)(x)易有其余式为A(2)(x)=x4+x3+x2+x，对应的码组为0011101，它与直接对码组进行循环左移的结果相同。
3.3 生成多项式
（n,k）循环码码组集合中（全“0”码除外）幂次最低的多项式（n-k）阶称为生成多项式g(x)。它是能整除xn+1且常数项为1的多项式，具有唯一性。
下面证明g(x)唯一性：
[证明]令g(x)?g0?g1x?...?gr?1xr?1?xr是（n，k）码中一个次数最低的非零码字多项式。若g(x)不是唯一的，则必然存在另一个次数为r的码字多项式，例如
??g1?x?...?gr??1xr?1?xrg?(x)?g0由于（n，k）是线性的，所以
?)?(g1?g1?)x?...?(gr?1?gr??1)xrg(x)?g?(x)?(g0?g0也是一个码字多项式，显然若g(x)?g?(x)?0，则它必是一个次数低于r的非零码字多项式。这与假设g(x)是次数最低非零码字多项式矛盾，所以g(x)?g?(x)?0，因此
g(x)?g?(x)(3-8)
从而g(x)唯一。
集合中其他码多项式，都是按模(xn+1)运算下g(x)的倍式，即可以由多项式g(x)产生循环码的全部码组。
假设信息码多项式为m(x)，则对应的循环码多项式为
A(x)=m(x)g(x) (3-9)
式中，m(x)为次数不大于k-1的多项式，共有2k个（n,k）循环码组。
考查表3-1，其中n-k=4阶的多项式只有编号为2的码组（0011101），所以表中所示（7，4）循环码组的生成多项式g(x)=x4+x3+x2+1，并且该码组集合中的任何码多项式A(x)都可由信息位乘以生成多项式得到
A(x)=(mk-1+mk-2+…+m1+m0)g(x)mod(xn+1) (3-10)
式中，(mk-1mk-2…m1m0)为信息码元。 对于（7，k）循环码，x7+1的因式分解为
x7+1=(x+1)(x3+x+1)(x3+x2+1) (3-11)
由该式可以构成表3-2所示几种（7，k）循环码。
表3-2 （7，k）循环码的生成多项式
(7,k) (7,1) (7,3) (7,4) (7,6)
g(x) (x+x+1)(x3+x2+1) (x+1)(x3+x+1)或(x+1)(x3+x2+1) x3+x+1或x3+x2+1 x+1 3从表（3-2）中可以看出，即使n,k均已确定，也可能由多种生成多项式供选择，选用的多项式不同，产生出的循环码组也不同。
3.4 生成矩阵
根据各码组集合中生成多项式的唯一性，可以构造生成矩阵G。由于g(x)的次数为n-k，则g(x),xg(x),…,xk-1g(x)都是码多项式，而且线性无关，因此以这k各多项式对应的码组作为k行就能构成该循环码的生成矩阵，因此循环码的生成矩阵多项式可以写成
?xk?1g(x)?
?? ...??
G(x)?...?
?.? xg(x)???g(x)???
(3-12)
以生成多项式g(x)=x4+x3+x2+1构造G(x)，相应的矩阵形式为 65422??x?x?x?x??xg(x)
????543
G(x)??xg(x)???x?x?x?x?
?g(x)??x4?x3?x2?1?
????
(3-13)
则G为g(x)升幂排列时的G为
?1
?
G??0 ?0?110100??111010?011101?? (3-14)
对式（3-14）作线性变换，整理成典型形式的生成矩阵
?1001110??G??0100111????0011101??（3-15）
若信息码元与式（3-15）相乘，得到的就是系统循环码。
3.5 监督多项式与监督矩阵
如前所述，在（n，k）循环码中，由于g(x)能除尽,因此xn+1可分解成g(x)和其他因式的乘积，记为
xn+1=g(x)h(x) (3-16)
即可写成
h(x)=xn+1/g(x) (3-17)
由于g(x)是常数项为1的r次多项式，所以h(x)必为k次多项式。称h(x)为监督多项式或一致校验多项式，与式（3.18）给出的G(x)相对应，监督矩阵多项式可表示为
?xh(x)???...???H(x)??...?*??xh(x)??*??h(x)?r?1*
(3-18)
式中，h*(x)式h(x)的逆多项式。
由式（1.1.14）可知，前述生成多项式的g(x)的一致校验多项式为h(x)x3+x2+1，所以其一致校验矩阵（监督矩阵）为
?1?0H(x)???0??0101000?
110100??
011010?
? （3-19）
001001?