关于信息:系统码的编译码与汉明码

本专栏蕴含信息论与编码的外围常识，按知识点组织，可作为教学或学习的参考。markdown 版本已归档至【Github 仓库：https://github.com/timerring/information-theory】或者公众号【AIShareLab】回复 信息论 获取。

零碎码的编译码

线性分组码的编码器

1. 如图硬件实现。生成矩阵为

$$
G=\left[\begin{array}{l}
1011000 \\
1110100 \\
1100010 \\
0110001
\end{array}\right]
$$

2. 查表。(软件)
3. 矩阵乘法。(软件)

线性分组码的译码器

所有编码合乎监督方程, 监督方程在译码中十分重要。

对二元信道, 传输后 $\mathbf{y}=\mathbf{C}+\mathbf{e}$ , 向量 $\mathrm{e}=\left[e_{n-1}, e_{n-2}, \ldots, e_{i}, \ldots, e_{0}\right]$ 称为谬误图样。$e_{i}=1$ 示意第 i 位谬误。

如果译码器能揣测出谬误图样 e, 那它就能够给出译码后果为

$$
\hat{\mathbf{C}}=\mathbf{y}+\mathbf{e}
$$

随同式校验(Syndrome Testing)

设 $\mathbf{y}=\left[y_{n-1} y_{n-2} \cdots y_{0}\right]$ 是一个接管矢量, 由传输的 $\mathbf{C}=\left[c_{n-1} c_{n-2} \cdots c_{0}\right]$ 产生。能够将 $\mathbf{y}$ 写成 $\mathbf{y}=\mathbf{C}+\mathbf{e}$

其中 $\mathrm{e}=\left[e_{n-1}, e_{n-2}, \ldots, e_{i}, \ldots, e_{0}\right]$ 是由信道引入的谬误矢量（图样）。

在 $2^{n}$ 个 $\mathrm{n}$ 元组空间中存在 $2^{n}-1$ 个非零的潜在谬误图样。（为什么?）

$\mathbf{y}$ 的随同式 (或称校对子) 定义为

$\mathbf{S}=\mathbf{y H}^{\mathbf{T}}$

• 若 $\mathbf{S}=\mathbf{0}, \mathbf{y}$ 是无效码字.
• 若 $ \mathbf{y}$ 蕴含可检测到的谬误，随同式 $\mathbf{S} \neq \mathbf{0}$ ;

• 若 $ \mathbf{y}$ 蕴含能够纠正的谬误, $\mathbf{S}$ 将由非凡的非零值来批示特定的谬误图样。

  线性分组码的一个重要性质是,（可纠正的）谬误图样与随同式一一对应。

$$
\mathbf{S}=\mathbf{y H}^{\mathrm{T}}=(\mathbf{C}+\mathrm{e}) \mathbf{H}^{\mathrm{T}}=\mathbf{C H}^{\mathrm{T}}+\mathrm{eH}^{\mathrm{T}}=\mathrm{eH}^{\mathrm{T}}
$$

(7,4) 循环码校验矩阵如下所示, 设发送码字为 $\mathbf{C}=1000011$ , 接管矢量为 $\mathbf{y}=1100011$
试求随同式矢量 $\mathbf{S}=\mathbf{y H}^{\mathrm{T}}$ 并证实它等于 $ \mathrm{eH}^{\mathrm{T}}$

校验矩阵: $H=\left(\begin{array}{lllllll}0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 1\end{array}\right) $

留神: 监督矩阵必须具备两个性质:

1. H 中没有全 0 列，否则的话，相应码字地位上的谬误就无奈影响随同式，因此无奈检测。
2. H 中的所有列是惟一的，如果 H 有两列雷同，那么对应这两列产生的错码地位将无奈辨认。

例：已知 (7,3) 线性分组码的监督矩阵为

$$
\mathbf{H}=\left(\begin{array}{lllllll}
1 & 0 & 1 & 1 & 0 & 0 & 0 \\
1 & 1 & 1 & 0 & 1 & 0 & 0 \\
1 & 1 & 0 & 0 & 0 & 1 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 & 1
\end{array}\right)
$$

信道输入端的接管矢量为

$$
\mathbf{y}=\left(\begin{array}{lllllll}
1 & 0 & 0 & 1 & 0 & 0 & 1
\end{array}\right)
$$

申请出 $\mathbf{y}$ 的随同式。并预计最有可能的译码后果。

解: $\mathbf{S}=\mathbf{y} \mathbf{H}^{T}=\left(\begin{array}{llll}0 & 1 & 1 & 1\end{array}\right)$
所有可能的谬误图样有（1001001）（1010100) (1110011) (0000111) (0011010) (0100000) (0111101)
取码重最小即可能性最大的谬误图样 (0100000) 为可纠正的谬误图样。译码后果

$$
\begin{array}{l}
\widehat{\mathbf{C}}=\mathbf{y}+\mathbf{e}^{\prime}=\left(\begin{array}{lllllll}
1 & 0 & 0 & 1 & 0 & 0 & 1
\end{array}\right)+ \\
\left(\begin{array}{lllllll}
0 & 1 & 0 & 0 & 0 & 0 & 0
\end{array}\right)=\left(\begin{array}{lllllll}
1 & 1 & 0 & 1 & 0 & 0 & 1
\end{array}\right) \\
\end{array}
$$

纠错

随同式不仅能够检测谬误, 而且能够同时纠正错误, 因 为可纠正的谬误图样与随同式之间一一对应。

在硬裁决译码中, 个别采纳规范阵(standard array) 来实现纠错的设计。

规范阵蕴含了 $2^{\mathrm{n}}$ 个所有的可能接管矢量. 其第一行以全 0 码 字开始，包含了所有码字, 而第一列包含了所有可纠正的谬误图样 (个别选汉明分量最小的元素 )。每行称为一个陪集 (coset), 由第一列的谬误图样 (称为陪集首) 及其烦扰的码字组成。$(\boldsymbol{n} . \boldsymbol{k})$ 码的规范阵如下:

留神：码字 $C_{1}$（全 0 码）起两个作用：既是其中的一个码字, 也是谬误图样 $\mathrm{e}_{1}$ , 代表没有谬误, 即 $\mathbf{y}=\mathbf{C}$ .

译码机制要求将每个有错的矢量用此矢量同列的最顶端的无效码字代替。

假如一个码字 $\mathrm{C}_{\mathrm{i}}$ 通过一个噪声信道, 接管矢量为量将被正确译码为码字 $\mathrm{C}_{\mathrm{i}}$。如果谬误图样不是一个陪集首, 那么将会导致译码谬误。

陪集的随同式

陪集中的每一个元素具备雷同的随同式。随同式用于预计谬误图样。

纠错译码

1. 计算 $\mathbf{y}$ 的随同式 $\mathbf{S}=\mathbf{y H}^{\mathrm{T}}$ .
2. 定位谬误图样 (陪集首) $\mathrm{e}_{\mathrm{j}}$ , 它的随同式与 $\mathrm{yH}^{\mathrm{T}}$ 相等。
3. 假如谬误图样是由信道衰败引起的。
4. 谬误接管的矢量或码字示意为 $\mathrm{C}=\mathbf{y}+\mathrm{e}_{\mathbf{j}}$。通过减去其中已辨认出的谬误来复原正确码字。

Example: (6,3)线性分组码如下表所示，求它的生成矩阵和监督矩阵。

其生成矩阵为

$$
G=\left[\begin{array}{l}
110100 \\
011010 \\
101001
\end{array}\right]
$$

监督矩阵为

$$
H=\left[\begin{array}{l}
100101 \\
010110 \\
001011
\end{array}\right]
$$

(6,3)码的规范阵如下。

依据规范阵，能够失去谬误图样与随同式的一一对应关系，可用来译码，同时实现纠错。

在线性分组码中，[全 0 码]码字肯定是无效码字。

已知接管矢量 y =001110. 请问译码器译码所得是什么?

S = 100，监督矩阵为

$$
H=\left[\begin{array}{l}
100101 \\
010110 \\
001011
\end{array}\right]
$$

S=100

C=101110

U=110

译码办法与译码电路

(1) 在设计阶段:

对每一种可能随同式的取值确定出它所对应的可纠正错误图样，存储为表格。

(2）译码器运行时:

当接收端收到 y 后，计算随同式 S，用 S 查可纠正错误图样表，依据查表后果纠正错误。

“查谬误图样表”这个环节往往能够进行逻辑化简，比方在 (7.4) 码的情景下，“查谬误图样表”是用 3 比特地址查 8 种后果，所有后果除全 0 外，只有 1 个 1。这样的电路相似 38 译码器。

(7,4）码谬误图样与随同式表

汉明码

一能纠正单个随机谬误、编码效率最高的线性分组码

• 主要参数：码长 $n=2^{m}-1$ ;
• 信息位：$k=n-m=2^{m}-1-m$ ;
• 监督位: $n-k=m$ , 且 $m \geq 3 ;(m=3, n=7, k=4)$
• 最小间隔 : $d_{\text {min}}=d_{0}=3$
• 汉明码的非全 0 随同式有 $n=2^{n-k}-1$ 个, 每个随同式对应一种单比特谬误图样, 因而每个随同式就是监督矩阵 $\boldsymbol{H}$ 的一个列, 而 $\boldsymbol{H}$ 的所有列形成了全 0 以外的所有可能的 $n-k$ 比特向量。

如 m=3 , 则能够失去一个 $n=2^{3}-1=7$ 的 (7,4) 汉明码, 其 $\boldsymbol{H}$ 矩阵的列由所有非 0 三重组成:

$$
H=\left(\begin{array}{lllllll}
1 & 0 & 1 & 1 & 1 & 0 & 0 \\
1 & 1 & 1 & 0 & 0 & 1 & 0 \\
0 & 1 & 1 & 1 & 0 & 0 & 1
\end{array}\right)
$$

因为任意两列线性无关 (d=3, t=1) , 故能纠任意单个随机谬误（监督矩阵的个性 d）。$R=k / n=1-m / n$ .

高效率纠错码。广泛应用于 RAM 中。

总结

线性分组码

①编码: 生成矩阵编码

②译码: 校验矩阵，谬误图样，随同式译码，规范阵

③生成矩阵与监督矩阵的关系

④汉明码

参考文献：

1. Proakis, John G., et al. Communication systems engineering. Vol. 2. New Jersey: Prentice Hall, 1994.
2. Proakis, John G., et al. SOLUTIONS MANUAL Communication Systems Engineering. Vol. 2. New Jersey: Prentice Hall, 1994.
3. 周炯槃. 通信原理（第 3 版）[M]. 北京：北京邮电大学出版社, 2008.
4. 樊昌信, 曹丽娜. 通信原理（第 7 版）[M]. 北京：国防工业出版社, 2012.