通信工程 / 系统课时
用生成矩阵编码线性分组码
用生成矩阵编码线性分组码
给定一段 4 位二进制信息,怎样把它转换为 7 位合法码字?本课使用一个系统形(7,4)线性分组码,先通过生成矩阵手算编码结果,再用 Python 枚举全部码字,检查码长、信息位数、码率及编码结果是否正确。
学习目标
- 理解生成矩阵 的行列含义,以及码长 、信息位数 和码率 的关系。
- 使用模二矩阵乘法,把 4 位信息编码为 7 位合法码字。
- 编写 Python 程序验证编码结果、系统形结构和合法码字数量。
从生成矩阵确定编码参数
线性分组码将固定长度的 位信息映射为 位码字,其中 。多出的 位提供冗余,使接收端能够根据码的结构检测或纠正一定范围内的错误。
设信息向量为 ,生成矩阵为 ,码字为 。它们的维度分别是 、 和 ,编码公式为:
这里的运算发生在二元域 GF(2) 中。乘法遵循普通的 0、1 乘法规则,加法则等价于异或,例如 ,所以矩阵乘法得到的每个结果都必须对 2 取模。
本例采用以下 4 行 7 列生成矩阵:
矩阵前 4 列组成单位阵 ,所以它是系统形生成矩阵,可以写成 。编码后,码字前 4 位直接保留原始信息,最后 3 位由信息位计算得到。
根据矩阵尺寸,可以立即确定:
- 信息位数:。
- 码长:。
- 冗余位数:。
- 码率:。
码率表示每个传输码字中有效信息位所占的比例。这里每传输 7 位,承载 4 位原始信息;码率约为 57.14%,不代表误码率为 42.86%。
手算一组信息位的编码结果
选取信息向量 。矩阵乘法可以理解为:信息位为 1,就选中生成矩阵对应的行;信息位为 0,该行不参与;最后将选中的行逐位异或。
本例选中 的第 1、3、4 行,第 2 行不参与。前三个以外的信息位位置由单位阵直接保证,输出的前 4 位仍然是 1011。
最后 3 位的计算分别为:
- 第 5 位:。
- 第 6 位:。
- 第 7 位:。
因此得到合法码字:
写成连续比特串就是 1011010。读者可以用相同方法验证 必然生成全零码字,因为所有矩阵行都没有被选中。

用 Python 编码并验证结果
下面使用 Python 3.8 或更新版本实现模二矩阵乘法,不需要安装第三方库。程序不仅计算指定信息向量,还会穷举全部 16 种 4 位输入,检查是否得到 16 个互不相同的码字。
将代码保存为 channel_code.py,使用 python channel_code.py 运行。
# 系统形生成矩阵:前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)}")预期输出:
信息位 u: 1011
码字 c: 1011010
码长 n: 7,信息位 k: 4
码率 R: 4/7 = 0.5714
合法码字数: 16代码中的列表 G[i][j] 表示矩阵第 行、第 列的元素。内层求和计算指定列的点积,% 2 将整数结果变为 GF(2) 中的单个比特。
两个断言分别验证系统形矩阵保留原始信息位,以及 16 种输入产生 16 个不同码字。如果修改矩阵时破坏了相应性质,程序就可能触发 AssertionError。但这两个断言并不能代替对任意生成矩阵的完整结构检查。
判断生成矩阵是否有效
对于一个二元 线性分组码,生成矩阵必须具有 行、 列,并且在 GF(2) 上的行秩为 。只有满足行线性无关,才能保证全部 个输入映射到互不相同的码字。
本例前 4 列恰好是单位阵,所以 4 行一定线性无关,矩阵秩为 4。由此可知合法码字共有 个。对于这个较小的示例,穷举全部输入很方便;当 达到几十甚至几百时,应使用 GF(2) 高斯消元检查矩阵秩,而不是枚举全部 个输入。
实际实现中还应避免以下问题:
- 漏掉模二运算:普通整数点积可能产生 2 或 3,而合法二元码字的每一位只能是 0 或 1。必须在求和后执行
% 2。 - 把码长和信息位数写反:对于 4 行 7 列的 ,输入必须是 4 位,输出必须是 7 位;矩阵行数决定 ,列数决定 。
- 认为所有生成矩阵都是系统形:只有类似 的系统形矩阵才保证前 位直接等于输入;一般满行秩生成矩阵也能有效编码,但信息位不一定原样出现在码字开头。
- 把生成码字等同于完成纠错:矩阵乘法负责生成合法码字,不能仅凭编码结果判断接收数据哪里出错。错误检测与定位还需要分析码的最小距离,以及使用校验矩阵计算伴随式等方法。
可以把示例的输入改为 u = [1, 1, 1, 1] 再运行,手算四行异或应得到码字 1111111;同时码长仍为 7、码率仍为 4/7、合法码字总数仍为 16。这说明改变信息内容只改变具体码字,不改变生成矩阵决定的编码参数。