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 元对称信道：
- 每个字符在传输过程中发生错误的概率相同，都为 p；
- 如果一个字符在传输过程中发生了错误，则它错为其它 q−1个字符中的任意一个的概率都是相同的。
一般地，对于 q 元对称信道而言，最近邻译码就是最大似然译码。
5. 检错和纠错
码的最小距离是刻画码的检错和纠错性能的一个重要参数。一般用 (n,M,d) 表示码长为 n，码字个数为 M，最小距离为 d 的一个码。
- 定理一：码 C 至多可以检查 t 个错误的充分必要条件为
- 定理二：码 C 至多可以纠正 t 个错误的充分必要条件为
。
因此，设 C 是一个码，其最小距离为 d，则码 C 至多可以检查 d−1个错误，至多纠正
个错误。
6. 编码理论的基本问题
一个好的 q 元 (n,M,d) 码应具有如下性质：
- 为了更快的发送信息，码长 n 应该小；
- 为了更多的发送信息，码字个数 M 应该大；
- 为了能纠正更多的错误，最小距离 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) 码是等价的，如果能够通过一系列下述两种变换将其中一个码变为另一个码：
- 换位型置换：将码的坐标位置进行置换；
- 换元型置换：将出现在某一个固定坐标位置上的字符进行置换。
附录
- 《编码理论基础》by 陈鲁生
