【通信原理入坑之路】—— 信息论部分线性分组码各种计算的解法

女爷i 2022-12-27 01:55 334阅读 0赞

在开始本文之前，我们先给出下面的几个名词，他们将会在后续的分析中反复出现：  
【1】生成矩阵 【2】监督矩阵 【3】许用码字 【4】最小汉明距离 【5】伴随式 【6】错误图样

我们先重点看看接收端中，上面这些名词的关联：  
![在这里插入图片描述][2020120714090593.png]  
首先，当我们接收到码字 y 时，我们可以通过监督矩阵计算出伴随式 S，通过伴随式，我们又可以得到错误图样，错误图样的意义就是它能够指出接收码字中哪一位出错了。从而去修改对应位置的码字。【**监督矩阵的监督作用可以通过 ： H ⋅ C T = 0 H\\sdot C^T=0 H⋅CT=0表现出来**】

下面我们具体看看如何通过监督矩阵得到所有的伴随式，也就是过程 a：

1.  假设我们现在计算得到了监督矩阵H： H = \[ 1 1 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1 \] H = \\begin\{bmatrix\} 1 & 1&0&1&0&0&0\\\\ 0&1&1&0&1&0&0\\\\ 1&1&1&0&0&1&0\\\\ 1&0&1&0&0&0&1 \\end\{bmatrix\} H=⎣⎢⎢⎡1011111001111000010000100001⎦⎥⎥⎤  
    那么伴随式S就是H 矩阵各列的组合（异或运算）。比如说，我们现在选择H的第1，2列进行异或，就会得到其中一个伴随式： S = \[ 0 1 0 1 \] S = \\begin\{bmatrix\} 0&1&0&1\\end\{bmatrix\} S=\[0101\]；再比如说我们如果只选择H的第6列进行异或，也可以得到另一个伴随式： S = \[ 0 0 1 0 \] S = \\begin\{bmatrix\} 0&0&1&0\\end\{bmatrix\} S=\[0010\]

下面我们具体看看如何通过伴随式求出错误图样，以及如果通过错误图样反推伴随式：

1.  如何通过伴随式求出错误图样？结果可能是不唯一的。由于我们刚刚不是选取了H的第1，2列异或得到了一个伴随式： S = \[ 0 1 0 1 \] S = \\begin\{bmatrix\} 0&1&0&1\\end\{bmatrix\} S=\[0101\]吗，所以上图的 b 过程就是说你伴随式S是选取了H的哪些列计算得到了，那么错误图样 e 就是在对应的位置标记为“1”，否则标记为“0”。所以，这个伴随式对应的错误图样就是  \[ 1 1 0 0 0 0 0 \] \\begin\{bmatrix\} 1&1&0&0&0&0&0\\end\{bmatrix\} \[1100000\]，但是还有一种可能性： S = \[ 0 1 0 1 \] S = \\begin\{bmatrix\} 0&1&0&1\\end\{bmatrix\} S=\[0101\]也可以是H矩阵的第5，7两列的组合。因此，错误图样还可能是： \[ 0 0 0 0 1 0 1 \] \\begin\{bmatrix\} 0&0&0&0&1&0&1\\end\{bmatrix\} \[0000101\]
2.  而反过来通过错误图样找S，结果就是唯一的了。比如说错误图样： \[ 1 1 0 0 0 0 0 \] \\begin\{bmatrix\} 1&1&0&0&0&0&0\\end\{bmatrix\} \[1100000\]，那么对应的伴随矩阵就只能是 S = \[ 0 1 0 1 \] S = \\begin\{bmatrix\} 0&1&0&1\\end\{bmatrix\} S=\[0101\]

**而可纠正的错误图样，指的就是错误最少的那种情况。**

--------------------

说了那么多，那么生成矩阵和监督矩阵到底怎么求呢？我们记住下面的关系： Q = \[ I ∣ P \] Q = \\begin\{bmatrix\} I|P\\end\{bmatrix\} Q=\[I∣P\]  
 H = \[ P T ∣ I \] H = \\begin\{bmatrix\} P^T|I\\end\{bmatrix\} H=\[PT∣I\]

**上述都是系统的生成矩阵和监督矩阵，如果题目给出来的矩阵不是系统的（也就是没有单位矩阵的），那么大部分情况可以通过行的互换得出。**

--------------------

求出了监督矩阵，我们就来看看最小汉明距离  d m i n d\_\{min\} dmin 如何计算。**其实  d m i n d\_\{min\} dmin 就是看H矩阵中最少有多少列是线性相关的**。还是以刚刚的H为例：  
 H = \[ 1 1 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1 \] H = \\begin\{bmatrix\} 1 & 1&0&1&0&0&0\\\\ 0&1&1&0&1&0&0\\\\ 1&1&1&0&0&1&0\\\\ 1&0&1&0&0&0&1 \\end\{bmatrix\} H=⎣⎢⎢⎡1011111001111000010000100001⎦⎥⎥⎤

我们发现，任意的3列都无法表示成线性关系，但是其中第5，6，7列的和恰好等于第3列，也就是说最少4列是可以表示成线性相关的，所以  d m i n = 4 d\_\{min\} = 4 dmin=4

--------------------

我们再来看看许用码字的求法：

**我们通过 (n, k) 码的形式【即：n位的码字里面有k个信息位】那么我们就把k个信息位的所有组合都列出来，然后分别跟生成矩阵相乘，就可以得到许用码字  C C C了。**

其中，我们也可以通过生成矩阵的维度确定 n, k：生成矩阵的维度：(k, n).

--------------------

另外还有一种题型：

> 已知某线性分组码的码长为  10 10 10，如果要想该线性码能够纠正两位随机错误，问需要多少位的监督位？

首先，我们明确这样一个性质：监督位如果有  x x x 位，那么其伴随式就会有： 2 x 2^\{x\} 2x种。下面我们回到题目：题目说想要线性码能够纠正两位随机错误，这个**随机错误其实就是通过错误图样来反应的**。比如一个  ( 7 , 4 ) (7,4) (7,4) 码，如果错误图样是  \[ 0001000 \] \[0 0 0 1 0 0 0\] \[0001000\]，那么就可以判断是第四位出错了。

**接下来我们看一下如果是出现两位错误的时候，错误图样有多少种情况：根据排列组合的知识，从10位里面选出2位作为错误位，那么有： C 10 2 = 45 C\_\{10\}^\{2\} = 45 C102=45种情况。然后只错一位的情况一共有： C 10 1 = 10 C\_\{10\}^1=10 C101=10种。因此，错两位及以下的错误图样一共有： 45 + 10 = 55 45+10=55 45\+10=55种情况。那么因此，我们所选取的监督位就应该使得线性码所产生的错误图样数比55大。由于  2 6 = 64 > 55 > 2 5 = 32 2^6=64>55>2^5=32 26=64>55>25=32，因此，监督位的个数应该是6.**

[2020120714090593.png]: /images/20221120/221c67596a0d47419a066637e6784498.png