循环码的生成多项式和矩阵

2023-06-27 理论教育版权反馈

【摘要】：此前k-1位为0、末位为1的码字，所对应的码多项式是最高次幂为（n-1）-（k-1）=n-k次的码多项式，而且它是循环码中幂次最低的码多项式，称它为循环码的生成多项式g。这种情况不可能出现，所以在（n，k）循环码中，最高次幂为n-k次的码多项式只有一个，生成多项式g具有惟一性。定理三：循环码（n，k）的生成多项式g是x n+1的一个因式。

从线性分组码的讨论中可知，有了生成矩阵就可以由信息位产生相应的循环码。

定理二：在循环码（n，k）中，n-k次幂的码多项式有一个，且仅有一个，用g（x）表示，称这惟一的n-k次多项式g（x）为循环码的生成多项式，并且g（x）的常数项不为零。

因线性分组码的信息位和监督位之间线性关系，可以由线性方程确定。所以当信息位全0时，监督位必然也全为0。循环码是一种线性分组码，它具有同样的性质，即信息位为全0时循环码必然是全0码。在（n，k）循环码中，除全0码外，不可能出现连续k位均为0的码字。因为如果出现k个连续的0，经过若干次移位后，将变为前k个信息码元全为0而监督码元不全为0的情况，这显然是不可能的。因此在（n，k）循环码的码集中，除全0码外，连续为0的长度最多只能有k-1位。前k-1位为0的码字，其末位必然为“1”。因为，若其末位为0，则经移位后必然出现k个连续的0，这是不可能的。此前k-1位为0、末位为1的码字，所对应的码多项式是最高次幂为（n-1）-（k-1）=n-k次的码多项式，而且它是循环码中幂次最低的码多项式，称它为循环码的生成多项式g（x）。由该码字末位为1可知，g（x）的常数项不为零，这样的码多项式只有一个。因为如果有两个最高次幂为n-k次的码多项式，则由循环码的封闭性可知，把这两个码字相加产生的码字连续前k位都为0。这种情况不可能出现，所以在（n，k）循环码中，最高次幂为n-k次的码多项式只有一个，生成多项式g（x）具有惟一性。

一旦g（x）确定，则该（n，k）循环码就被确定了。g（x）是循环码中幂次最低的码多项式，由它左移就可产生其他码多项式，如xg（x）、x 2g（x）、x 3g（x）等。用k个互相独立的码多项式g（x）、xg（x）、x 2g（x）…x k-1g（x）可以构造出循环码的生成矩阵G（x）为

例如，有一个（7，3）循环码其最高次幂为n-k次的码字为0010111，其生成多项式g（x）=x 4+x 2+x+1。利用式（4-44）可得其生成矩阵G（x）为

将此生成矩阵用系数表示，写成生成矩阵G，则

式（4-46）不符合典型生成矩阵的形式，所以它不是典型生成矩阵，由它编写出的码字不是系统码，但是对此矩阵作线性变化可以得到典型生成矩阵的形式。

设上例中信息码为[C6C5C4]，由生成矩阵多项式可以写出该循环码的码字为

式中 u（x）——信息码[C6C5C4]的多项式。

所以已知信息码U = [uk-1uk-2…u1u0]和g（x）后就可求得循环码的所有多项式为

式中 u（x）——信息位所对应的多项式。

信息位有k位，所以u（x）的最高阶数为（k-1）次幂，此方法求得的码多项式为非系统码。由式（4-47）可看出，所有的码多项式都可以被g（x）整除。

定理三：循环码（n，k）的生成多项式g（x）是x n+1的一个因式。

g（x）是最高次幂为n-k次的码多项式，x kg（x）是最高次幂为n的多项式。利用定理一对x kg（x）作模x n+1运算，得

式中 r（x）——该循环码的一个码多项式。