通信工程 / 系统课时

用生成矩阵编码线性分组码

用生成矩阵编码线性分组码

给定一段 4 位二进制信息,怎样把它转换为 7 位合法码字?本课使用一个系统形(7,4)线性分组码,先通过生成矩阵手算编码结果,再用 Python 枚举全部码字,检查码长、信息位数、码率及编码结果是否正确。

学习目标

  • 理解生成矩阵 GG 的行列含义,以及码长 nn、信息位数 kk 和码率 RR 的关系。
  • 使用模二矩阵乘法,把 4 位信息编码为 7 位合法码字。
  • 编写 Python 程序验证编码结果、系统形结构和合法码字数量。

从生成矩阵确定编码参数

线性分组码将固定长度的 kk 位信息映射为 nn 位码字,其中 n>kn>k。多出的 n−kn-k 位提供冗余,使接收端能够根据码的结构检测或纠正一定范围内的错误。

设信息向量为 uu,生成矩阵为 GG,码字为 cc。它们的维度分别是 1×k1\times k、k×nk\times n 和 1×n1\times n,编码公式为:

c=uG(mod2)c=uG\pmod 2

这里的运算发生在二元域 GF(2) 中。乘法遵循普通的 0、1 乘法规则,加法则等价于异或,例如 1⊕1=01\oplus1=0,所以矩阵乘法得到的每个结果都必须对 2 取模。

本例采用以下 4 行 7 列生成矩阵:

G=[1000110010010100100110001111]G=\begin{bmatrix} 1&0&0&0&1&1&0\\ 0&1&0&0&1&0&1\\ 0&0&1&0&0&1&1\\ 0&0&0&1&1&1&1 \end{bmatrix}

矩阵前 4 列组成单位阵 I4I_4,所以它是系统形生成矩阵,可以写成 G=[I4∣P]G=[I_4\mid P]。编码后,码字前 4 位直接保留原始信息,最后 3 位由信息位计算得到。

根据矩阵尺寸,可以立即确定:

  • 信息位数:k=4k=4。
  • 码长:n=7n=7。
  • 冗余位数:n−k=3n-k=3。
  • 码率:R=kn=47≈0.5714R=\frac{k}{n}=\frac47\approx0.5714。

码率表示每个传输码字中有效信息位所占的比例。这里每传输 7 位,承载 4 位原始信息;码率约为 57.14%,不代表误码率为 42.86%。

手算一组信息位的编码结果

选取信息向量 u=[1,0,1,1]u=[1,0,1,1]。矩阵乘法可以理解为:信息位为 1,就选中生成矩阵对应的行;信息位为 0,该行不参与;最后将选中的行逐位异或。

本例选中 GG 的第 1、3、4 行,第 2 行不参与。前三个以外的信息位位置由单位阵直接保证,输出的前 4 位仍然是 1011。

最后 3 位的计算分别为:

  • 第 5 位:p1=1⊕0⊕1=0p_1=1\oplus0\oplus1=0。
  • 第 6 位:p2=1⊕1⊕1=1p_2=1\oplus1\oplus1=1。
  • 第 7 位:p3=0⊕1⊕1=0p_3=0\oplus1\oplus1=0。

因此得到合法码字:

c=[1,0,1,1,0,1,0]c=[1,0,1,1,0,1,0]

写成连续比特串就是 1011010。读者可以用相同方法验证 u=[0,0,0,0]u=[0,0,0,0] 必然生成全零码字,因为所有矩阵行都没有被选中。

系统形生成矩阵将四位信息编码为七位码字的模二运算关系

用 Python 编码并验证结果

下面使用 Python 3.8 或更新版本实现模二矩阵乘法,不需要安装第三方库。程序不仅计算指定信息向量,还会穷举全部 16 种 4 位输入,检查是否得到 16 个互不相同的码字。

将代码保存为 channel_code.py,使用 python channel_code.py 运行。

python
# 系统形生成矩阵:前4列保留信息位,后3列产生校验位
G = [
    [1, 0, 0, 0, 1, 1, 0],
    [0, 1, 0, 0, 1, 0, 1],
    [0, 0, 1, 0, 0, 1, 1],
    [0, 0, 0, 1, 1, 1, 1],
]


def encode(u):
    k, n = len(G), len(G[0])
    if len(u) != k or any(bit not in (0, 1) for bit in u):
        raise ValueError("信息位必须由 4 个 0/1 组成")

    # 对每一列做点积并模2取余,得到对应的码字位
    return [
        sum(u[i] * G[i][j] for i in range(k)) % 2
        for j in range(n)
    ]


def bitstr(bits):
    return "".join(str(bit) for bit in bits)


if __name__ == "__main__":
    u = [1, 0, 1, 1]
    c = encode(u)

    # 穷举所有4位输入,检测不同输入是否生成重复码字
    codebook = {
        bitstr(encode([(v >> s) & 1 for s in (3, 2, 1, 0)]))
        for v in range(16)
    }

    assert c[:4] == u
    assert len(codebook) == 16

    print(f"信息位 u: {bitstr(u)}")
    print(f"码字 c: {bitstr(c)}")
    print(f"码长 n: {len(c)},信息位 k: {len(u)}")
    print(f"码率 R: {len(u)}/{len(c)} = {len(u) / len(c):.4f}")
    print(f"合法码字数: {len(codebook)}")

预期输出:

text
信息位 u: 1011
码字 c: 1011010
码长 n: 7,信息位 k: 4
码率 R: 4/7 = 0.5714
合法码字数: 16

代码中的列表 G[i][j] 表示矩阵第 i+1i+1 行、第 j+1j+1 列的元素。内层求和计算指定列的点积,% 2 将整数结果变为 GF(2) 中的单个比特。

两个断言分别验证系统形矩阵保留原始信息位,以及 16 种输入产生 16 个不同码字。如果修改矩阵时破坏了相应性质,程序就可能触发 AssertionError。但这两个断言并不能代替对任意生成矩阵的完整结构检查。

判断生成矩阵是否有效

对于一个二元 (n,k)(n,k) 线性分组码,生成矩阵必须具有 kk 行、nn 列,并且在 GF(2) 上的行秩为 kk。只有满足行线性无关,才能保证全部 2k2^k 个输入映射到互不相同的码字。

本例前 4 列恰好是单位阵,所以 4 行一定线性无关,矩阵秩为 4。由此可知合法码字共有 24=162^4=16 个。对于这个较小的示例,穷举全部输入很方便;当 kk 达到几十甚至几百时,应使用 GF(2) 高斯消元检查矩阵秩,而不是枚举全部 2k2^k 个输入。

实际实现中还应避免以下问题:

  • 漏掉模二运算:普通整数点积可能产生 2 或 3,而合法二元码字的每一位只能是 0 或 1。必须在求和后执行 % 2。
  • 把码长和信息位数写反:对于 4 行 7 列的 GG,输入必须是 4 位,输出必须是 7 位;矩阵行数决定 kk,列数决定 nn。
  • 认为所有生成矩阵都是系统形:只有类似 [Ik∣P][I_k\mid P] 的系统形矩阵才保证前 kk 位直接等于输入;一般满行秩生成矩阵也能有效编码,但信息位不一定原样出现在码字开头。
  • 把生成码字等同于完成纠错:矩阵乘法负责生成合法码字,不能仅凭编码结果判断接收数据哪里出错。错误检测与定位还需要分析码的最小距离,以及使用校验矩阵计算伴随式等方法。

可以把示例的输入改为 u = [1, 1, 1, 1] 再运行,手算四行异或应得到码字 1111111;同时码长仍为 7、码率仍为 4/7、合法码字总数仍为 16。这说明改变信息内容只改变具体码字,不改变生成矩阵决定的编码参数。

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

目录与阅读设置

阅读设置

17

记录一个想法

用生成矩阵编码线性分组码

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

登录哪都通