11 群与编码（TBD）
编码
信息（Message）
有限的 0 和 1 序列。
码字（Word）
长度为 m 的 0 和 1 序列。
群
集合 B 是在模 2 加运算下的群。
- \(B^m=B \times B \times B \times \dots \times B\) 是定义了运算 \(\oplus\) 的群：\((x_1,x_2,\dots,x_m)\oplus(y_1,y_2,\dots,y_m)=(x_1+y_1,x_2+y_2,\dots,x_m+y_m)\)
- \(B^m\) 可以简写成 \(b_1b_2\dots b_m\)
编码函数
定义双射（一一对应）的编码函数 \(e:B^m \rightarrow B^n\)，如果 \(b \in B^m\)，则 \(e(b)\) 称为 \(b\) 的码字（Word）
差错检测
如果 \(x = e(b)\) 在传输过程中出现了 \(h\) 个错误 \((1 \leq h \leq k )\)，称为发生了小于等于 \(k\) 个错误，则 \(x_t\) 不是一个码字。
权值
对于 \(x \in B^n\)，\(x\) 中 1 的个数称为权值，用 \(|x|\) 表示。
奇偶校验码
例如 \(e(010)=0101\)、\(e(110)=1100\)。
海明距离（Hamming）
对于 \(x,y \in B^m\)，它俩的海明距离 \(\delta(x,y)=|x\oplus y|\)。
例如 \(x=110110,y=000101\)，则 \(x\oplus y=110011\)，那么 \(\delta(x,y)=4\)。
- \(\delta(x,y)=\delta(y,x)\)
- \(\delta(x,y) \geq 0\)
- \(\delta(x,y) = 0\text{ iff } x = y\)
- \(\delta(x,y) \leq \delta(x,z) + \delta(z,y)\)
最小距离
最小距离是所有不同码字中距离最小的那一个。 $$ \min{\delta[e(x),e(y)] ~ | x,y \in B^m} $$
例如，我们选择以下编码方案：
- 00 → 000
- 01 → 011
- 10 → 101
- 11 → 110
我们来计算这个编码方案的最小距离：
- 000 和 011 之间的海明距离是 2
- 000 和 101 之间的海明距离是 2
- 000 和 110 之间的海明距离是 2
- 011 和 101 之间的海明距离是 3
- 011 和 110 之间的海明距离是 1
- 101 和 110 之间的海明距离是 1
在这些距离中，最小的距离是 1。因此，这个编码方案的最小距离是 1。
定理
-
如果一个 \(B^m→B^n\) 的编码函数可以检测 \(k\) 的错误，则当且仅当它的最小距离最少是 \(k+1\)。
-
如果一个 \(B^m→B^n\) 的译码函数可以检测 \(t\) 的错误，则当且仅当它的最小距离最少是 \(2t+1\)。
群码
如果存在一个 \(B^m \rightarrow B^n\) 的编码函数 \(e\)，并且 \(e(B^m)=\{e(b)~|~e(b) \in B^n\}\)，则 \(e\) 是 \(B^n\) 的子群。
回顾子群的条件（N 是 \(B^n\) 的子群）：
- \(B^n\) 的单位元在 \(N\) 里
- 如果 \(x,y \in N\)，那么 \(x\oplus y \in N\)
- 如果 \(x\in N\)，它的逆元也在 \(N\) 里
定理一
如果一个编码函数 \(e\) 是群码，则它的最小距离是其中最小非零码字的权值。
译码
TODO