摘要

本报告根据《信息论与编码》第 6 章中线性分组码、伴随式和标准阵列译码的内容，选取课件例 6-3 的二元 (5,2) 系统线性分组码作为仿真对象，使用 Python 编写程序实现码字生成、校验矩阵求解、伴随式计算、标准阵列构造以及接收码译码。程序默认使用课件中的生成矩阵，并对接收码 R=10101 进行验证，得到伴随式 S=010、差错图案 E=00010，最终译出码字 C=10111，与课件计算结果一致。

关键词：线性分组码；标准阵列；伴随式；校验矩阵；Python

 

1. 选题背景

 

信道传输过程中，接收端收到的码字可能因为噪声产生错误。线性分组码通过增加冗余位，使接收端能够检测甚至纠正一部分错误。第 6 章课件中给出了 (n,k) 线性分组码的基本结构，并介绍了用伴随式和标准阵列进行译码的方法。

 

本次程序选题为“(n,k) 线性分组码的标准译码表构造”。为了和课件内容对应，程序默认采用课件例 6-3 中的 (5,2) 线性分组码，并实现接收码的自动译码。

 

2. 基本原理

 

2.1 生成矩阵与码字

对于二元 (n,k) 线性分组码，信息组 m 是 k 位二元向量，生成矩阵 G 是 k×n 矩阵。码字 C 可由下面公式生成：

C = mG

其中运算均在 GF(2) 上进行，即加法使用模 2 加法。

本程序默认使用课件例 6-3 的生成矩阵：

G =

10111

01101

 

因此 4 个信息组生成的码字为：

m C

00 00000

01 01101

10 10111

11 11010

 

2.2 校验矩阵与伴随式

校验矩阵 H 用于判断接收码是否满足线性分组码的校验关系。正确码字 C 应满足：

C * H^T = 0

若接收码为 R，差错图案为 E，则：

R = C + E

因此：S = R * H^T = (C + E) * H^T = E * H^T

伴随式 S 与发送的具体码字 C 无关，只与差错图案 E 有关。所以译码时可以先求接收码 R 的伴随式 S，再根据 S 查表得到最可能的差错图案 E，最后用：

C = R + E

恢复发送码字。

程序根据 G 自动求得校验矩阵：

 

H =

11100

10010

11001

 

3. 标准阵列译码表构造

标准阵列的第一行是所有合法码字，第一列是各个陪集首，也就是每个伴随式对应的最小重量差错图案。课件例 6-3 中共有：

2^k = 4 个码字

2^(n-k) = 8 个伴随式

 

程序中使用的伴随式表如下：

S E

000 00000

111 10000

101 01000

100 00100

010 00010

001 00001

011 00011

110 00110

其中 `00000` 表示无差错，重量为 1 的差错图案表示单比特错误。对于后两个重量为 2 的差错图案，课件中也说明可能存在并列最轻的情况，选择并不唯一。本程序为了和课件例题对应，固定选择 `00011` 和 `00110` 作为对应陪集首。

构造出的标准阵列如下：

S E 00000 01101 10111 11010

000 00000 00000 01101 10111 11010

111 10000 10000 11101 00111 01010

101 01000 01000 00101 11111 10010

100 00100 00100 01001 10011 11110

010 00010 00010 01111 10101 11000

001 00001 00001 01100 10110 11011

011 00011 00011 01110 10100 11001

110 00110 00110 01011 10001 11100

 

4. 程序设计

 

程序文件为：

ppt_standard_array_decoder.py

 

程序主要函数如下：

str_to_bits() 将输入字符串转为二元向量

gf2_rref() 对矩阵进行 GF(2) 行化简

parity_check_matrix() 根据生成矩阵求校验矩阵 H

encode() 根据 C=mG 生成码字

make_codebook() 枚举全部信息组和码字

syndrome() 计算伴随式 S=R*H^T

build_syndrome_leaders() 自动寻找各伴随式的最小重量差错图案

build_standard_array() 构造标准阵列译码表

decode() 根据 S 查 E，再计算 C=R+E

 

程序默认使用课件例 6-3 的 (5,2) 码，也支持用户手动输入其他 n、k 和生成矩阵 G。

 

5. 运行结果

 

程序运行后直接按回车，可使用默认课件例题。程序首先输出生成矩阵 G、由 G 求出的校验矩阵 H、全部合法码字、伴随式表以及标准阵列译码表。这样可以比较直观地看到：第一行是合法码字，第一列是不同伴随式对应的差错图案。

 

                                                     运行图1 程序生成码表和标准阵列

 

随后输入课件中的接收码 `10101` 进行译码，程序输出结果为：

 

S = R * H^T : 010

E from table: 00010

C = R + E : 10111

m : 10

 

                                                              运行图2 接收码10101的译码结果

 

计算过程说明：

 

1. 接收码为 R=10101。

2. 由 S=R*H^T 求得伴随式 S=010。

3. 查伴随式表得差错图案 E=00010，表示第 4 位发生错误。

4. 用 C=R+E 得到译出码字 C=10111。

5. 查码表可知 C=10111 对应的信息组为 m=10。

 

该结果与课件中“R=10101 译出 C=10111”的结果一致。

 

6. 结果分析

 

由码字集合可得该线性分组码的最小距离：

 

d_min = 3

 

因此其纠错能力为：

 

t = floor((d_min - 1) / 2) = 1

 

这说明该码可以可靠纠正 1 位随机错误。当错误位数超过 1 位时，标准阵列仍然可以给出一个译码结果，但该结果不一定唯一，也不一定可靠。课件中也指出，后面包含两个“1”的差错图案已经超过 t=1 的纠错能力，因此只能作为最大似然意义下的一种选择。

 

从程序结果可以看出，标准阵列译码的核心优点是译码过程简单：接收端只需计算伴随式，再查表得到差错图案。缺点是当 n 较大时，标准阵列表会迅速变大，存储和构造成本都会增加。

 

结合运行图可以看到，程序不是直接把课件结果写死输出，而是先通过生成矩阵计算出码字集合和校验矩阵，再用伴随式确定差错图案。这样既能复现实例，也方便更换其他 (n,k) 线性分组码进行测试。

 

7. 总结

本次程序实现了二元线性分组码的标准阵列译码过程，重点体现了课件第 6 章中的三个公式：

C = mG

S = R * H^T

C = R + E

通过 Python 程序可以自动生成码字、校验矩阵、伴随式表和标准阵列，并完成接收码译码。以课件例 6-3 为测试对象时，程序输出结果与课堂计算一致。通过本次实现，我对线性分组码中“伴随式只反映差错图案，而不反映发送码字”的含义有了更直观的理解。

 

参考资料

 

1. 《信息论与编码》第 6 章课件：线性分组码、伴随式与标准阵列译码。

2. 曹雪虹等，《信息论与编码（第4版）》，相关章节：线性分组码、校验矩阵、伴随式译码。