本专栏蕴含信息论与编码的外围常识，按知识点组织，可作为教学或学习的参考。markdown 版本已归档至【Github 仓库：https://github.com/timerring/information-theory】或者公众号【AIShareLab】回复 信息论 获取。
线性分组码
基本概念
线性分组码数学定义: 编码前信息码元空间 $U^{k}$ , 经映射 $f$ , 编码后码字空间 $C^{n}$ , 即 $f: U^{k} \rightarrow C^{n}$ , 其中 $n>k$。若 $f$ 进一步满足线性关系:
$$
f\left(\alpha \mathbf{u} \oplus \beta \mathbf{u}^{\prime}\right)=\alpha f(\mathbf{u}) \oplus \beta f\left(\mathbf{u}^{\prime}\right)
$$
其中 $\alpha, \beta \in G F(2)=\{0,1\}, \mathbf{u} 与 \mathbf{u}^{\prime} \in \mathbf{U}^{k}$ 则称 $f$ 为线性编码映射，进一步若 f 为一一对应映射，则 f 为惟一可译线性编码。由 f 编写成的码 c 称为线性分组码。
线性分组码是一类奇偶校验码，它由（n，k）模式示意。编码器将一个 k 比特信息分组（信息矢量）转变成一个更长的由给定符号集组成的 n 比特编码分组（编码矢量）。当这个符号集蕴含 2 个元素 (0 and1）时 , 称为二进制编码。
kbit 信息造成 $2^k$ 不同的信息序列 , 称为 k 元组。nbit 能够造成 $2^n$ 个不同序列，称为 n 元组。（n, k）分组码输入的长度为 n 的序列称为码字。所有这些码字的汇合称为该线性分组码的码组。
定义: 如果分组码中任意两个码字的线性组合仍是分组码的一个码字，那么该分组码是线性的。对于二进制码，如果 $c_i$ 和 $c_j$ 是码字，$c_i$+$c_j$ 也是码字。其中 + 示意按位模 2 加 (就是逐位相加)。
例:(7,3)线性分组码
$d_{\min}=4$ . $c_{i}+c_{j}$ 仍为码字
疾速计算方法：看除全零码以外，最小的码重就是它的码距。
编码 - 生成矩阵
编码和生成矩阵
（n，k）线性分组码的结构——根据给定的 k 个信息码元，设计满足编码条件（最小码距、码率）的 n- k 个监督码元。
例: 二元 (7,3) 线性分组码, n=7, k=3, r=7-3=4 ,
$$
\mathbf{u}=\left(u_{2}, u_{1}, u_{0}\right) \rightarrow \mathbf{c}=\left(c_{6}, c_{5}, c_{4}, c_{3}, c_{2}, c_{1}, c_{0}\right)
$$
结构:
编码位 高位间接对应信息位;
编码位 低位由信息位组合而成。.
$$
\begin{array}{ll}
c_{6}=u_{2} & c_{3}=u_{2} \bigoplus u_{0}=c_{6} \oplus c_{4} \\
c_{5}=u_{1} & c_{2}=u_{2} \bigoplus u_{1} \oplus u_{0}=c_{6} \oplus c_{5} \oplus c_{4} \\
c_{4}=u_{0} & c_{1}=u_{2} \bigoplus u_{1}=c_{6} \oplus c_{5} \\
& c_{0}=u_{1} \oplus u_{0}=c_{5} \oplus c_{4}
\end{array}
$$
写成矩阵模式，为
即 : $\mathbf{C}=\mathbf{u} \mathbf{G}$
设信息码元序列为 $\mathbf{u}$ , 长度为 k , 由 $\mathbf{C}=\mathbf{u G}$ 能够失去一个 n 位的码组, 也即由 k 个信息位通过一个线性变换矩阵 $\mathbf{G}$ 产生。
$\mathbf{G}$- 生成矩阵
$$
\mathbf{G}=\left(\begin{array}{c}
\mathbf{g}_{1} \\
\mathbf{g}_{2} \\
\vdots \\
\mathbf{g}_{k}
\end{array}\right)=\left(\begin{array}{ccc}
g_{11} & \ldots & g_{1 n} \\
\vdots & \vdots & \vdots \\
g_{k 1} & \ldots & g_{k n}
\end{array}\right) k \times n \text {阶}
$$
线性分组码的编码: $\mathrm{C}=\mathbf{u G} $
该 (7,3) 码的生成矩阵为
如：若输出的信息为 [011], 由 $\mathrm{C}=\mathrm{uG}$ , 得 $\mathrm{C}=[0111010]$, 和码表中的码字统一。
例 生成矩阵如图矩阵。
若信息为 $\mu=\left(\begin{array}{lll}1 & 1 & 1\end{array}\right)$，则编码出的码字是什么? 1110100$$
G=\left[\begin{array}{lllllll}
1 & 0 & 0 & 1 & 1 & 1 & 0 \\
0 & 1 & 0 & 0 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 & 1 & 0 & 1
\end{array}\right]
$$
零碎码与非零碎码
若生成矩阵能够分解成两个子块,
$$
\boldsymbol{G}=[\boldsymbol{I} \vdots \boldsymbol{Q}] \text {或} \boldsymbol{G}=[\boldsymbol{Q} \vdots \boldsymbol{I}]
$$
其中 $\mathrm{I}$ 为 $\boldsymbol{k}$ 阶单位矩阵, $\mathrm{Q}$ 为 $\boldsymbol{k} *(\boldsymbol{n}-\boldsymbol{k})$ 阶矩阵, 则 C 为零碎码，又称为组织码, G 为零碎码的生成矩阵 (典型生成矩阵)。
若信息分组以不变的模式呈现在线性分组码的任意 k 位 (个别为前 k 位，或后 k 位），则称此码组为零碎码，否则称为非零碎码。(如果编码器输入的比特流中原样蕴含了信息比特，叫零碎码。 编码输入中的这些原始信息位也叫零碎位。)
生成矩阵的个性
a. 生成矩阵 $\mathbf{G}$ 肯定是 $\boldsymbol{k}$ 行 $\boldsymbol{n}$ 列的 $\boldsymbol{k} \times \boldsymbol{n}$ 阶矩阵, $\mathrm{G}$ 的每行形成一行矢量, 共有 $\boldsymbol{k}$ 个矢量。
b. 线性分组码的每个码字是生成矩阵 $\mathbf{G}$ 各行矢量的线性组合。
$$
\begin{array}{r}
\mathbf{C}=\mathbf{u G}=\left(u_{k-1}, \ldots, u_{1}, u_{0}\right)\left(\begin{array}{c}
\boldsymbol{g}_{1} \\
\boldsymbol{g}_{2} \\
\vdots \\
\boldsymbol{g}_{k}
\end{array}\right) \\
=u_{k-1} \boldsymbol{g}_{1}+u_{k-2} \boldsymbol{g}_{2}+\ldots+u_{1} \boldsymbol{g}_{k-1}+u_{0} \boldsymbol{g}_{k}
\end{array}
$$
c. G 的每一行是一个码字。
d. 生成矩阵 G 的 各行线性无关。思考: 已知码字汇合，如何结构生成矩阵?
e. 对 非零碎码的生成矩阵 ，总能够通过高等 行变换 及列替换 结构成另一等价的 零碎码的生成矩阵 并且这两个线性分组码检、纠错性能雷同。
求非零碎 (7,4) 线性分组码的等价零碎码生成矩阵。
$$
\mathrm{G}=\left[\begin{array}{lllllll}
0 & 1 & 0 & 1 & 0 & 1 & 0 \\
0 & 1 & 1 & 1 & 0 & 0 & 1 \\
1 & 1 & 1 & 0 & 0 & 1 & 0 \\
1 & 0 & 1 & 0 & 1 & 0 & 1
\end{array}\right]
$$列的替换和高等行变换不扭转矩阵的秩，变换后矩阵的 各行矢量仍线性无关。
任何一个线性分组 (n, k)码都可等价于一个零碎码。（纠错能力、编码构造)
思考: 由非零碎型生成矩阵变换成零碎型生成矩阵，答案惟一吗?
已知某 (7，4) 分组码的码表如下，请问最小汉明距是多少? 请写出该码的典型生成矩阵。
最小汉明距：3
生成矩阵:
$$
G=\left[\begin{array}{lllllll}
1 & 0 & 0 & 0 & 1 & 1 & 1 \\
0 & 1 & 0 & 0 & 1 & 1 & 0 \\
0 & 0 & 1 & 0 & 1 & 0 & 1 \\
0 & 0 & 0 & 1 & 0 & 1 & 1
\end{array}\right]
$$
检错 - 监督矩阵
由分组码的生成矩阵可失去其监督矩阵。
$$
\mathbf{H C}^{T}=\mathbf{0}^{T},[\mathbf{P}: \mathbf{I}] \mathbf{C}^{T}=\mathbf{0}^{T}
$$
个别状况下, 一个 (n, k) 线性分组码的 H 矩阵中的（n-k）行对应（n-k）个线性监督方程组, 以确定（n-k）个监督码元。
$\mathbf{H}$——线性分组码的监督矩阵，是 $（n-k）\times \mathbf{n}$ 阶的。
若 H=[P：I], 其中 I 是 (n-k）阶方阵, 则 H 为典型监督矩阵。
监督矩阵
$$
H \cdot C^{T}=H \cdot G^{T} \mu^{T}=0^{T}
$$
或者 $\mathbf{G}$ 每一行及其线性组合都是 (n, k) 码的码字, 故 $H \cdot G^{T}=0^{T} \Rightarrow G \cdot H^{T}=0$ .
$$
\begin{array}{c}
G \cdot H^{T}=\left[\begin{array}{ll}
I & Q
\end{array}\left[\begin{array}{c}
P^{T} \\
I
\end{array}\right]=P^{T}+Q=0\right. \\
\therefore Q=P^{T} \text {或} P=Q^{T}
\end{array}
$$
请思考：已知 $\mathbf{G}=[I: Q] \Rightarrow \mathbf{H}=[\mathrm{P}: I]$ 若 $G=[Q: I]$，则 $H= [I:P]$
监督方程
由
$$
\begin{aligned}
H \cdot C^{T} & =H \cdot G^{T} \mu^{T}=0^{T} \\
& \Rightarrow C H^{T}=0
\end{aligned}
$$
可知，若
$$
\widetilde{\boldsymbol{C}} \boldsymbol{H}^{T} \neq \mathbf{0}
$$
则 $\widetilde{\boldsymbol{C}}$ 不是无效码字, 从而检测出谬误。故：
$$
\boldsymbol{C H}^{T}=0
$$
称为线性分组码的监督方程。
监督矩阵的个性
- 由 H 矩阵能够建设线性分组码的线性方程组, H 矩阵共有 n-k 行, 其中每行代表一个线性方程的系数, 示意求一个监督位的线性方程;
- H 矩阵的每行与码集中的一个码字的内积为 0 ;
- 任何一个 $ (\boldsymbol{n}-\boldsymbol{k})$ 线性分组码的 $\mathrm{H}$ 矩阵有 $ (\boldsymbol{n}-\boldsymbol{k})$ 行, 且每行线性无关;
- 一个 $(\boldsymbol{n}, \boldsymbol{k}, d)$ 线性分组码, 如要纠正小于等于 t 个谬误, 则其充要条件是 H 矩阵中任何 2t 列线性无关, 因为最小间隔 d=2t+1 , 所以也相当于要求 H 矩阵中任意 (d-1) 列线性无关。
- 零碎码的典型生成矩阵 $\mathbf{G}$ 能够不便的失去典型监督矩阵 $\mathbf{H}$。
已知一 (6,3) 线性分组码的生成矩阵 G 如下，求其监督矩阵 $\mathbf{H}$。
$$
\begin{array}{l}
\boldsymbol{G}=\left[\begin{array}{llllll}
1 & 0 & 0 & 1 & 1 & 0 \\
0 & 1 & 0 & 1 & 0 & 1 \\
0 & 0 & 1 & 0 & 1 & 1
\end{array}\right] \\
\end{array}
$$
参考文献：
- Proakis, John G., et al. Communication systems engineering. Vol. 2. New Jersey: Prentice Hall, 1994.
- Proakis, John G., et al. SOLUTIONS MANUAL Communication Systems Engineering. Vol. 2. New Jersey: Prentice Hall, 1994.
- 周炯槃. 通信原理（第 3 版）[M]. 北京：北京邮电大学出版社, 2008.
- 樊昌信, 曹丽娜. 通信原理（第 7 版）[M]. 北京：国防工业出版社, 2012.