信道编码（纠错编码）、信源编码⚓︎

差错图样、汉明距离⚓︎

一般而言，我们使用的编码都是二进制编码，因此，对于加法运算，我们一般指模二的加法运算。

定义\(\boldsymbol{C}\)为发送的编码（简称发码），\(\boldsymbol{R}\)为收到的编码（简称收码），那么定义差错图样\(\boldsymbol{E}\)：

这样一来，有差错的位在\(\boldsymbol{E}\)中的体现就是对应位为\(1\).差错图样中\(1\)的数目就称为汉明距离.

线性分组码⚓︎

生成矩阵⚓︎

线性分组码\((n,k)\)是把信息流分割成前后相互独立的长度为\(k\)的信息组，再将每个组映射成长度为\(n\)的码字。一般而言，对于给定的信息流\(\boldsymbol{m}\)，其与\(\boldsymbol{G}\)的矩阵乘积就是码字，这个矩阵\(\boldsymbol{G}\)称为生成矩阵.

生成矩阵\(\boldsymbol{G}\)的一般形式为：

其中，\(\boldsymbol{I}_k\)是\(k\)阶单位阵，\(\boldsymbol{P}\)是\(k\times(n-k)\)阶矩阵。

\(\boldsymbol{m}\times\boldsymbol{G}\)得到的前\(k\)位就是\(\boldsymbol{m}\)的内容，这部分叫做系统码；其余的是冗余信息，称为非系统码。

校验矩阵⚓︎

对于给定的生成矩阵\(\boldsymbol{G}\)，存在一个校验矩阵\(\boldsymbol{H}\)，其结构：

它的转置与\(\boldsymbol{G}\)特殊在于，两者的乘积是零向量，因为：

校验矩阵可以校验接收到的码字\(\boldsymbol{R}\)是否是有错误的码字，由于\(\boldsymbol{R}=\boldsymbol{m}\boldsymbol{G}+\boldsymbol{e}\)，则

这个运算结果又称为伴随式，即\(\boldsymbol{S}=\boldsymbol{e}\boldsymbol{H}^T\).

当接收到的码字与初始码字只有一个汉明距离时，可以从上式中显然看出错误的位(相当于筛选出了\(\boldsymbol{H}^T\)中的某一行)；如果存在多个错误，则所得结果是存在错误的位的对应行向量的线性组合，这时是否可以纠正就不一定了。

码距、检错能力、纠错能力⚓︎

对于任一信息流，其会映射到线性空间的一个子集中。这些码字之间最短的汉明距离称为码空间的最小码距，记作\(d_{\min}\).

对于一种码空间，检错能力表示其能够检查出最多偏移的汉明距离的值，一般而言，检错能力为\(d_{\min}-1\)，因为再多错一位就可能会与码空间中其他码字相重叠，就未必能够检错了。

纠错能力是能够纠错时码字偏移的最大汉明距离。直观上说，纠错能力为\(t=\dfrac{d_{\min}-1}{2}\)，因为此时正好落在两个可能的码字之间，若继续向错误的码字偏移，则无法正确纠错（即使依然能够判断是错误的码字）。

事实上，检错能力与矩阵\(\boldsymbol{H}\)的秩是有关的，因为我们单纯靠伴随式是否为零判断检错能力，而伴随式为零也就意味着各个列向量是线性相关的。当\(\boldsymbol{H}\)满秩时，检错能力达到最大，即

通过这个关系我们可以知道极大最小距离码（MDC）的\(d_{\min}\).

完备码⚓︎

根据前面所述，给定了\(\boldsymbol{G}\)的编码方案，其伴随式共有\(2^{n-k}\)个。而对于纠错能力为\(t\)的编码方案，长度为\(n\)的码字可能产生的错误图样是 \(\displaystyle\sum_{i=1}^{n} \begin{pmatrix} n\\ i \end{pmatrix}\) ，于是应有不等关系：

另一个角度来说，在高维线性空间中，每一个码字\(\boldsymbol{C}_i\)都有一个半径为纠错能力\(t\)的球，其中包含距离\(C_i\)所有汉明距离小于等于\(t\)的收码\(\boldsymbol{R}\).这样在一个球体中所包含的收码数为\(\displaystyle\sum_{i=1}^{n} \begin{pmatrix} n\\ i \end{pmatrix}\), 又由于所有球体内收码数不可能多于线性空间中总的收码数，故而\(2^k\displaystyle\sum_{i=1}^{n} \begin{pmatrix} n\\ i \end{pmatrix}\leqslant 2^n\).从这个意义上也可以理解完备码的要求。

汉明码⚓︎

汉明码是纠错能力\(t=1\)的一类码的统称，其\((n,k)\)满足：

常见的完备码是\((7,4)\)汉明码，它将长度为\(4\)的信息流转化为长度为\(7\)的码字。

汉明码的校验矩阵\(\boldsymbol{H}\)是\(n-k\)行\(n\)列的。\(n-k\)个码元恰好能够构成\(2^{n-k}\)个不同的码字，对于汉明码来说，数量是正好的。因此我们对于\(\boldsymbol{H}\)进行系统化处理后即可作为校验矩阵反推出生成矩阵。

香农编码算法⚓︎

对于符号\(x_i\)而言，若其概率为\(p(x_i)\)，则其至少需要\(-\log p(x_i)\)位表示。于是香农码使用\(\lceil -\log p(x_i)\rceil\)位编码来表示该符号。

首先将各个符号的概率由大至小排列，对于每个符号\(x_i\)，定义累计概率\(g_i=\displaystyle\sum_{n=0}^{i-1} p(x_i)\).取\(g_i\)的小数点后前\(\lceil -\log p(x_i)\rceil\)表示该符号的编码。

评论