通信工程 / 系统课时
用多项式表示循环码的码字
用多项式表示循环码的码字
七位比特不仅能表示成向量,也能表示成系数为 0 或 1 的多项式。这里用一个 (7,4) 循环码的实际码字,解释比特与幂次如何对应、模二运算为何可以实现循环移位,并用 Python 验证移位前后的码字合法性。
学习目标
- 按固定的位序把七位比特转换为多项式。
- 用模二加法和多项式取余解释循环移位。
- 通过生成多项式验证原码字和移位码字。
用系数下标对应多项式幂次
取码长 ,约定比特从左到右依次写作 ,其中 是 的系数。序列 [1,1,0,0,1,0,1] 因而对应 。这里按低次幂到高次幂排列,不是通常把最高有效位放在左侧的二进制写法。
在 中,每个系数只能是 0 或 1,加减法都是异或,例如 。取生成多项式 和消息多项式 ,相乘后 项出现两次、相互抵消,得到 。因此该序列确实属于由 生成的 (7,4) 循环码。
用乘以 x 解释循环移位
长度为 7 的循环码以 为模;在 中减法等于加法,所以也可以写成 。将码字多项式乘以 后对它取余,超出第六次幂的项便回到常数项。
本例先得到 ,再将 替换成 ,得到 。对应系数从 [1,1,0,0,1,0,1] 变为 [1,1,1,0,0,1,0]:原来的 回绕到新序列首位,其余比特右移一格。

同一规则还适用于码字相加:相同位置逐位异或即可。本例 ,因为常数项和一次项各出现两次,被模二运算抵消。
用 Python 验证生成与移位
下面的 Python 3 程序用整数的第 个二进制位保存 的系数。^ 执行模二加法,移位操作模拟乘 ,多项式长除法判断是否被生成多项式整除。
n = 7
g = 0b1011 # g(x) = 1 + x + x^3
m = 0b1001 # m(x) = 1 + x^3
def multiply_gf2(a, b):
result = 0
while b:
if b & 1:
result ^= a # 同次项按模二相加
a <<= 1
b >>= 1
return result
def remainder_gf2(poly, divisor):
while poly.bit_length() >= divisor.bit_length():
poly ^= divisor << (poly.bit_length() - divisor.bit_length())
return poly
def coefficients(poly):
return [(poly >> i) & 1 for i in range(n)]
c = multiply_gf2(g, m)
# 乘以 x 后,将第七次幂的系数折回常数项
shifted = ((c << 1) & ((1 << n) - 1)) | (c >> (n - 1))
print("c:", coefficients(c))
print("shift:", coefficients(shifted))
print("XOR:", coefficients(c ^ shifted))
print("remainders:", remainder_gf2(c, g), remainder_gf2(shifted, g))
print("g divides x^7+1:", remainder_gf2((1 << n) | 1, g) == 0)预期输出:
c: [1, 1, 0, 0, 1, 0, 1]
shift: [1, 1, 1, 0, 0, 1, 0]
XOR: [0, 0, 1, 0, 1, 1, 1]
remainders: 0 0
g divides x^7+1: True区分位序、移位与合法码字
脚本中整数 0b1010011 按惯例从高位到低位显示;但 coefficients 返回的是从 到 的系数。混用这两种方向,会把同一组比特解释为不同的多项式。核对时先注明 在哪一端,再讨论左移或右移。
另外,任何七位串都能表示成多项式,却未必是这个循环码的合法码字。本例的 整除 ,且原码字与移位码字除以 的余数都为 0;若验出非零余数,应先检查系数顺序、生成多项式和最高位回绕是否正确。