通信工程 / 系统课时

用多项式表示循环码的码字

用多项式表示循环码的码字

七位比特不仅能表示成向量,也能表示成系数为 0 或 1 的多项式。这里用一个 (7,4) 循环码的实际码字,解释比特与幂次如何对应、模二运算为何可以实现循环移位,并用 Python 验证移位前后的码字合法性。

学习目标

  • 按固定的位序把七位比特转换为多项式。
  • 用模二加法和多项式取余解释循环移位。
  • 通过生成多项式验证原码字和移位码字。

用系数下标对应多项式幂次

取码长 n=7n=7,约定比特从左到右依次写作 c0,c1,...,c6c_0,c_1,...,c_6,其中 cic_i 是 xix^i 的系数。序列 [1,1,0,0,1,0,1] 因而对应 c(x)=1+x+x4+x6c(x)=1+x+x^4+x^6。这里按低次幂到高次幂排列,不是通常把最高有效位放在左侧的二进制写法。

在 GF(2)GF(2) 中,每个系数只能是 0 或 1,加减法都是异或,例如 1+1=01+1=0。取生成多项式 g(x)=1+x+x3g(x)=1+x+x^3 和消息多项式 m(x)=1+x3m(x)=1+x^3,相乘后 x3x^3 项出现两次、相互抵消,得到 m(x)g(x)=1+x+x4+x6m(x)g(x)=1+x+x^4+x^6。因此该序列确实属于由 g(x)g(x) 生成的 (7,4) 循环码。

用乘以 x 解释循环移位

长度为 7 的循环码以 x7−1x^7-1 为模;在 GF(2)GF(2) 中减法等于加法,所以也可以写成 x7+1x^7+1。将码字多项式乘以 xx 后对它取余,超出第六次幂的项便回到常数项。

本例先得到 xc(x)=x+x2+x5+x7xc(x)=x+x^2+x^5+x^7,再将 x7x^7 替换成 11,得到 c′(x)=1+x+x2+x5c'(x)=1+x+x^2+x^5。对应系数从 [1,1,0,0,1,0,1] 变为 [1,1,1,0,0,1,0]:原来的 c6c_6 回绕到新序列首位,其余比特右移一格。

七位循环码的系数与循环移位对应关系

同一规则还适用于码字相加:相同位置逐位异或即可。本例 c(x)+c′(x)=x2+x4+x5+x6c(x)+c'(x)=x^2+x^4+x^5+x^6,因为常数项和一次项各出现两次,被模二运算抵消。

用 Python 验证生成与移位

下面的 Python 3 程序用整数的第 ii 个二进制位保存 xix^i 的系数。^ 执行模二加法,移位操作模拟乘 xx,多项式长除法判断是否被生成多项式整除。

python
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)

预期输出:

text
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 返回的是从 x0x^0 到 x6x^6 的系数。混用这两种方向,会把同一组比特解释为不同的多项式。核对时先注明 c0c_0 在哪一端,再讨论左移或右移。

另外,任何七位串都能表示成多项式,却未必是这个循环码的合法码字。本例的 g(x)g(x) 整除 x7+1x^7+1,且原码字与移位码字除以 g(x)g(x) 的余数都为 0;若验出非零余数,应先检查系数顺序、生成多项式和最高位回绕是否正确。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用多项式表示循环码的码字

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通