编码理论基础

1. 码的定义

• 定义一：设 A 是一个有限集合，称之为字母表。A 中元素构成的有限序列称为字或串。一个字中的元素的个数称为字长。
• 定义二：设 A是一个字母表。A 上所有字的集合记为

。

中包含一个长度的零的特殊字，称之为空字，记为ε。对

中的任意两个字 x 和 y，将 y 排在 x 后面得到 xy，xy显然还是

中的一个字，即运算即为字的拼接运算。显然，

对拼接运算为带幺半群，单位元为空字 ε。

• 定义三：设 C 是

的一个子集。如果对任意

，当

时，一定有 m=n，并且

，则称 C 为字母表 A 上的一个码。码 C 中的字称为码字。如果码 C 中的码字长度都相同，则称 C 为定长码；否则称其为变长码。如果 ∣A∣=n，则称 C 为 n 元码。

在编码理论中，字母表 A 一般取为有限域 GF(q)。设

表示 GF(q)上的 n 维向量空间。V(n,q) 中的向量

通常记为

。

• 定义四：V(n,q)中的任意一个非空子集 C 称为一个 q 元分组码。C 中的每一个向量称为一个码字。如果 ∣C∣=M，则称 C 是一个 q 元 (n,M) 码，其中 n 表示码长，M 表示码字个数。

分组码是定长码，一个 q 元 (n,M)码的所有码字长度都是 n。编码理论中主要讨论的就是分组码。

2. 码率的定义

• 定义五：一个 q 元 (n,M) 码的码率定义为

​

3. 汉明距离

性质 显然，汉明距离作为一个距离度量，满足距离度量的三大性质：非负性、对称性以及三角不等式。

• 定义七：设 C 是一个 (n,M)码。码 C 的最小距离定义为 C 中的任意两个不同的码字的汉明距离的最小值，记为 d(C)，即

• 定义八：设

。x 中非零分量的个数称为汉明重量，记为 W(x)。设

，对于

，定义

显然

性质

• 定义九：码

的最小重量定义为 C 中所有非零码字的最小重量，记为 W(C)，即

4. 最近邻译码

• 定义十：设 x 是一个码字，经过信道传输后，在接收端我们收到的向量为 y。由于噪声的干扰，可能

，并且y 可能不是一个码字。将 y 译为与 y 汉明距离最小的码字

是合理的。这种译码策略称为最近邻译码。

• 定义十一：满足下述两个条件的信道称为 qq 元对称信道：
  1. 每个字符在传输过程中发生错误的概率相同，都为 p；
  2. 如果一个字符在传输过程中发生了错误，则它错为其它 q−1个字符中的任意一个的概率都是相同的。

一般地，对于 q 元对称信道而言，最近邻译码就是最大似然译码。

5. 检错和纠错

码的最小距离是刻画码的检错和纠错性能的一个重要参数。一般用 (n,M,d) 表示码长为 n，码字个数为 M，最小距离为 d 的一个码。

• 定理一：码 C 至多可以检查 t 个错误的充分必要条件为

• 定理二：码 C 至多可以纠正 t 个错误的充分必要条件为

。

因此，设 C 是一个码，其最小距离为 d，则码 C 至多可以检查 d−1个错误，至多纠正

个错误。

6. 编码理论的基本问题

一个好的 q 元 (n,M,d) 码应具有如下性质：

1. 为了更快的发送信息，码长 n 应该小；
2. 为了更多的发送信息，码字个数 M 应该大；
3. 为了能纠正更多的错误，最小距离 d 应该大。

7. 完备码

• 定义十三：设 C 是一个 q 元

码，如果汉明界等号成立，即

则称 C 为完备码。

8. 系统码

在代数编码理论中，通常取 M=qkM = q^kM=qk。一个 qqq 元 (n,qk)(n, q^k)(n,qk) 码可以对 V(k,q)V(k, q)V(k,q) 中的全体向量进行编码。

在系统码中，信息位和校验位是截然分开的。但在非系统码中，信息位和校验位无法截然分开。校验位就是冗余位，用于在信道的接收端纠正码字在信道传输过程中发生的错误。

9. 新码的构造

我们可以利用一个已知的码来构造新码：

9.1 延长码

将一个码中每个码字都增加一个或多个分量，称为码的延长。最常用的码的延长方法是对每个码字都增加一个奇偶校验位。

9.2 截短码

码的截短是码的延长的逆过程。将一个码中的每个码字都删去一个或多个分量，称为码的截短。

9.3 扩张码

对一个码增加一个或多个码字后所得到的码称为扩张码。

9.4 删除码

从一个码中去掉一个或多个码字后所得到的码称为删除码。

9.5 加长码

9.6 缩小码

10. 码的等价变换

• 定义十九：关于 q 元 (n,M)码有两种置换。一种是关于码字分量位置集合的置换，称为换位型置换，记为 σ1

另一种是关于字母表

的置换，称为换元型置换，记为 σ2​：

• 定义二十：两个 q 元 (n,M) 码是等价的，如果能够通过一系列下述两种变换将其中一个码变为另一个码：
  1. 换位型置换：将码的坐标位置进行置换；
  2. 换元型置换：将出现在某一个固定坐标位置上的字符进行置换。

附录

• 《编码理论基础》by 陈鲁生