引入

Recap：通信系统基本模型

一个基本的数字通信系统框图如下

其中：

信源编码：其目的为压缩信息，提高效率。它对原始信息进行压缩，使其占用更少的比特。典型的算法如霍夫曼码、LZ码、JPEG、MP3、MPEG等
信道编码：其目的为增加冗余，纠正传输错误。它在在压缩后的数据中加入冗余信息（如校验位）。常见的有块码（包含Hamming码、CRC码）、卷积码、Turbo码等等。

Recap：香农信道容量

香农信道容量是可实现的信道容量的极限。香农表明如果合适地将信息编码，可以实现很高的通信速率与很低的错误率，这对应有一个最高的信息传输速率称为信道容量（可靠通信的极限）。如果超过这个速率，则无法实现低错误率的通信。

$C=B\log_2(1+S/N)$

其中：

B为信道带宽（Hz）
S为信号功率（W）
N为噪声功率（W）

章节目标：

本章节将：

介绍信源、信息量、熵等概念。
介绍前缀码、霍夫曼、LZ码几种信源编码。
最后简略介绍信道容量的相关内容，其包含香农信道容量、互信息、AWGN与衰落信道中的容量。

信源与熵

信源

信源产生的数据应当在接收端看起来应该是随机的，如果信源产生的数据已经被准确地预测，则无需进行通信。

（老师的例子：这种感觉就像是你谈了个男朋友，你问他今天吃什么，他每天都给你一个小惊喜，所以你每天都要问问他今天吃啥。如果你们每天都吃一样的，那你不需要跟他说话你就知道他是个什么b样了）

离散无记忆信源（Discrete Memoryless Source, DMS）

离散无记忆信源：离散表示信源输出的符号来自于有限的集合（例如0和1），无记忆表明每个符号产生是独立的，不依赖与过去或未来的符号。因此DMS表示信源输出的每个符号都是独立且服从固定概率分布的离散随机变量。

例如：二进制信源输出序列 1010101001110，每个比特都是独立生成的。

例如：英语就不是无记忆信源，如果我说了B和O，那么最后一个可能是X来组成BOX，也可能是Y来组成BOY。但是不可能是Z，因此最后一个字母依赖于前两个。

信息的不确定性，信息量和熵

信息量

如果信息$S=s_k$出现的概率为$p_k$，则定义其信息量$I$为：

$I(s_k)=log_n(\frac{1}{p_k})=-log_n(p_k)$

其中$n$表示离散信源的集合元素个数。例如二进制信源只有0和1两种情况，因此$n=2$，其算出的信息量大小也以bit为单位。

如果$S=s_k$出现概率$p_k$为1，则$I(s_k)=0$。确定事件不包含任何信息。同时，通过这个公式也不难看出，当$S=s_k$的出现概率越小，其包含的信息量越大，反之越小。

假设现有两个信息$s_k$和$s_l$，他们两出现是相互独立的。则这两个信息的总信息量$I(s_ks_l)$为：

$I(s_ks_l)=I(s_k)+I(s_l)$

熵（Entropy）

熵是信源信息量的期望值：

$H(\psi)=E[I(s_k)]=\sum^{K-1}_{K=0}p_kI(s_k)$

从离散的视角来看，就是对$信源每种信息情况的信息量 \times 这种情况出现的概率$进行求和。

例子：假设一个信源，其输出的符号集合为${s_0,s_1,s_2}$，他们的概率分别为${p_0=1/4, p_1=1/4, p_2=1/2}$.

则该信源产生的信息的熵（以bit为单位）为：

$H(\psi)=\frac{1}{4}log_2(4)+\frac{1}{4}log_2(4)+\frac{1}{2}log_2(2)=1.5bits$

对于二进制离散无记忆信源，其信息熵满足：

$1\leq H(\psi)\leq \log_2K$

其中K是信源产生的符号集合元素个数。

例子：考虑一个二进制无记忆信源，0出现的概率为$P_0$, 1出现的概率为$P_1=1-P_0$。求这个信源的熵

$H(\psi)=p_0\times[-\log_2p_0]+(1-p_0)\times[-\log_2(1-p_0)]$

对于不同的$p_0$，熵如下图。可以看出当符号0和1等概率分布时，信息熵最大，为1bit。

信源编码及其效率

信源编码是对原始数据的再表达，以此来减少数据量。其基本思想是：如果已知原始信息的统计数据，如果原始信息的统计数据表明某些符号比其他的更频繁地出现，那么则可以将这些符号编码成更简短的代码，以此来达到压缩。当然，也有诸如JPEG这样的有损压缩，其基于的是人眼对图像中的细节高频信号不明显。

编码效率（Coding Efficiency）

信源编码的编码效率$\eta$定义为$编码后的理论最小长度(L_{min})/信息的平均长度{\overline L}$。

$\eta=\frac{L_{min}}{\overline L}$

对于$\overline L$，假设信息$s_k$出现的概率为$p_k$，而编码将信息$s_k$编码为长度$l_k$的二进制串，则其平均长度计算为：

$\overline L=\sum^{K-1}_{k=0}p_kl_k$

对于$L_{min}$，香农编码定理（Shannon source-coding theorem）给定：对于任何离散无记忆信源，其熵为$H(\psi)$，那么它的平均变编码长度$\overline L \geq H(\psi)$。因此

$L_{min}=H(\psi)$

现在有非常多的无损压缩技术，例如jpeg中使用的霍夫曼编码这样的无损压缩（JPEG在执行霍夫曼编码之前时有损的），zip压缩等等。他们可以通过计算来简化标记文件中的重复信息。但是，熵代表了表达某一信号的最短比特，使用无损压缩技术仍只能逼近信息熵，而无法超越它。熵是无法超越的信息最短长度，编码效率永远小于等于100%。

编码方式

霍夫曼码（Huffman Code）

引入：前缀码

前缀码是指编码集合里面没有任何一个码字是另一个码字的前缀的编码。也就是说，在这个集合中，任何一个码字都不会“开头部分”与另一个码字重叠。

例如集合{A=0, B=10, C=110, D=111}就是前缀码，因为表达ABCD的码字没有任何一个前缀包含了另一个码字；而集合{A=0, B=01, C=011}就不是前缀码，因为B的01包含了A的0作为前缀，C的011包含了B的01作为前缀。

前缀码可以进行即时解码，即可以在不需要查看后续码字的情况下立即解码当前码字。对于前缀码，常使用决策树来对其进行解码。如下图${s_0=0, s_1=10, s_2=110, s_3=111}$的例子

前缀码的每一个码字是唯一可解码的。

前缀码必须满足Kraft-McMillan不等式（但是满足该不等式不一定是前缀码）：

$\sum_{k=0}^{K-1} 2^{-l_k} \leq 1$

其中$l_k$表示第k个码字的长度。

以${s_0=0, s_1=10, s_2=110, s_3=111}$为例：

$\sum_{k=0}^{K-1} 2^{-l_k} =2^{-1}+2^{-2}+2^{-3}+2^{-3}=1$

其是前缀码，所以满足K-M不等式。

霍夫曼码

霍夫曼码是一种无损压缩的前缀码，它根据统统计信息来分配码字。使得更频繁出现的信息有更短的码字，而不频繁出现的信息则占用更长的码字。以此实现无损压缩。

霍夫曼码编码过程

考虑这个例子，现在有$s_0-s_4$5个符号，他们出现的概率分别是：

符号	$s_0$	$s_1$	$s_2$	$s_3$	$s_4$
概率	0.4	0.2	0.2	0.1	0.1

第一步：将符号从上到下按照概率从大到小排列，将概率写在stage1

第二步：将概率最小的两项加起来，在stage2重新从排列。如果加起来的概率与其他概率相等，则将其放在最前面。

第三步：重复步骤2，写出stage3

第四步：重复步骤2，写出stage4。此时只剩两项，可以停止。

ee7691088638cb5d41ecea519ead186c

第五步：给每一个分支上侧分配0，下侧分配1（也可以上1下0）。

第六步：根据每一个箭头，逆序写出每一层的码。以stage4到stage3为例：在stage4 0.6被分配了0，0.4被分配了1，那么stage3就需要把他们拿过来。stage3的第二个0.4需要先写stage4的0，再添上它自己的0；stage3的0.2需要先写stage4的0，再添上它自己的1。第一个0.4被分配了1，且其不是通过加合得到的，因此直接把1写到stage3就行。

第七步：重复第六步直到第一层。即可获得每个symbol的霍夫曼编码

由于霍夫曼编码过程不唯一，这门课考试时请遵循如上过程！

霍夫曼码的编码效率计算例子

在上面的例子中，我们获得了${s_0=00, s_1=10, s_2=11, s_3=010, s_4=011}$的霍夫曼码。根据前面介绍的编码效率计算：

它的平均编码长度为：

$\overline L=0.4\times2+0.2\times2+0.2+0.2\times2+0.1\times3+0.1\times3=2.2bits$

这个信息的理论最短编码（信息熵）为：

$L_{min}=-0.4\times\log_2(0.4)-0.2\times\log_2(0.2)-0.2\times\log_2(0.2)-0.1\times\log_2(0.1)-0.1\times\log_2(0.1)=2.12193bits$

因此对于$s_0-s_4$，采用霍夫曼编码的编码效率为：

$\eta=\frac{L_{min}}{\overline L}=\frac{2.12193}{2.2}=96.451\%$

Lempel-Ziv 码

纵然霍夫曼编码可以通过统计信息来分配码字，实现了非常科学的无损压缩，但是数据的统计信息并不是一直可知的。因此无需统计信息的LZ码或许是另一种选择。

L-Z码不像霍夫曼码，需要根据概率分布来分配码字。L-Z码是一种定长字典码，常用于ZIP、PNG等文件进行无损压缩。

本课介绍的LZ码通过维护一个字典，以将特定码字映射到字典内的条目来实现编码。就像是利用0010来代替1011010101010这一串这样的感觉。

LZ码有数种变体，较为经典的是LZ77,LZ78,LZW等。下方的编码是这门课中讲的，它实际为LZ78编码的非标准变体，我不知道为什么老师选择了这个变体而不直接讲LZ78编码，这个变体使得数据压缩的过程变得非常非常抽象。在本节附录中，会详细拓展LZ77,LZ78,LZW的三种标准编码方式。

编码步骤

以比特流000101110010100101为例。假设字典内已经存入了1和0，此时的字典长这样：
| Index | Dictionary Location | Contents | Code Word |
| :—-: | :————————-: | :———: | :———-: |
| 1 | 1（1） | 0 | 0 |
| 2 | 10（2） | 1 | 1 |

index代表该元素在字典中的序号，Dictionary Location是Index的二进制形式。Contents是原文字符，Code Word是映射到字典后的编码。

从比特流的最左边开始：000101110010100101的第一位是0，字典内已经有0了，因此继续往后看一位，下一位是0，因此此时是00。字典内没有00，将其添加到字典中。它的index就是3，Dictionary Location就是3对应的二进制数；code word 需要把1的Dictionary location搞过来，再在后面补上content的最后一位，1的Dictionary location是1，10的最后一位是0，因此得到code word为10：

Index	Dictionary Location	Contents	Code Word
1	1（1）	0	0
2	10（2）	1	1
3	11（3）	00	10

10已被编入字典，因此可以将其删去，比特流剩余为000101110010100101。此时第一位为0，已编入；往下再看一位，是01。因为字典内没有01，所以需要将其添加进去。它的index是4，code word是（0的Dictionary location）+（01的LSB）=01。因此得到：

Index	Dictionary Location	Contents	Code Word
1	1（1）	0	0
2	10（2）	1	1
3	11（3）	00	10
4	100（4）	01	01

比特流剩余为~~0001~~01110010100101。重复上面的操作，遇到已经编入的字符就往后再读一位，最终得到下表：

*注意：当编入100时，10已经编入，所以它的code word是10的dic. location + 100的LSB；字典的最后一个数无需写出Dictionary Location，因为此时字符已经被完全编码，无需写出Location供下面的生成码字使用。*

Index	Dictionary Location	Contents	Code Word
1	1（1）	0	0
2	10（2）	1	1
3	11（3）	00	10
4	100（4）	01	01
5	101（5）	011	1001
6	110（6）	10	100
7	111（7）	010	1000
8	1000（8）	100	1100
9		101	1101

L-Z码是定长编码，因此现在需要根据最长的code word，将所有较短的code word前面补0，使其具有同样的长度：
| Index | Dictionary Location | Contents | Code Word |
| :—-: | :————————-: | :———: | :———-: |
| 1 | 1（1） | 0 | 0000 |
| 2 | 10（2） | 1 | 0001 |
| 3 | 11（3） | 00 | 0010 |
| 4 | 100（4） | 01 | 0001 |
| 5 | 101（5） | 011 | 1001 |
| 6 | 110（6） | 10 | 0100 |
| 7 | 111（7） | 010 | 1000 |
| 8 | 1000（8） | 100 | 1100 |
| 9 | | 101 | 1101 |

此时就完成了L-Z码的编码，000101110010100101编码后变成 0010 0001 1001 0100 1000 1100 1101。这里编码后反而更冗杂，是因为这个比特流太短了，重复信息很少。

解码过程

收到以L-Z码编码的比特流0010 0011 1001 0100 1000 1100 1101，已知初始字典为001->0，010->1，解码比特流。L-Z码的解码过程是一边解码一边重建字典。

初始字典如下：
| Index | Dictionary Location | Contents | Code Word |
| :—-: | :————————-: | :———: | :———-: |
| 1 | 001（1） | 0 | |
| 2 | 010（2） | 1 | |

第一个码为0010，0010中的0001来自于001，因此它的content为0拼上0010的LSB（0），为00。更新字典如下，解码出的比特流为00。

Index	Dictionary Location	Contents	Code Word
1	001（1）	0
2	010（2）	1
3	011（3）	00	0010

第二个码为0011，其为0+1，故content为01，已解码比特流为0001，更新字典如下：

Index	Dictionary Location	Contents	Code Word
1	001（1）	0
2	010（2）	1
3	011（3）	00	0010
4	100（4）	01	0011

重复上述步骤，最终获得字典如下，解码比特流为：000101110010100101

Index	Dictionary Location	Contents	Code Word
1	001（1）	0
2	010（2）	1
3	011（3）	00	0010
4	100（4）	01	0001
5	101（5）	011	1001
6	110（6）	10	0100
7	111（7）	010	1000
8	1000（8）	100	1100
9		101	1101

信道容量（简要介绍）

信道容量是人为定义的，由香农于1948年在信息论中提出。信道容量在特定SNR下进行地错误率的通信的极限。如果尝试以超过信道容量的速率进行通信，则不可能将通信错误率降到0。

概念：离散无记忆信道（Discrete Memoryless Channels, DMC）

香农在信息论中对建立了一个离散无记忆信道模型。它的发送和接收是两个离散集合，且当前输出只于当前输入有关，如下图所示。使用$p(y_k|x_j)$来表达在发送$x_j$时收到$y_k$的概率。

如果算出发送-接收的所有条件概率，则可以表明这个信道的特征。所有的概率可以使用矩阵来表示，其被称为信道矩阵（Channel Matrix）或转移矩阵（Transition Matrix）

$\mathbf{P} = \left[ \begin{array}{cccc} p(y_0 \mid x_0) & p(y_1 \mid x_0) & \cdots & p(y_{K-1} \mid x_0) \\ p(y_0 \mid x_1) & p(y_1 \mid x_1) & \cdots & p(y_{K-1} \mid x_1) \\ \vdots & \vdots & \ddots & \vdots \\ p(y_0 \mid x_{J-1}) & p(y_1 \mid x_{J-1}) & \cdots & p(y_{K-1} \mid x_{J-1}) \end{array} \right]$

使用矩阵内的条件概率可以算联合概率$p(x_j,j_k)$，即，$P(X=x_j,Y=y_k)$的概率

$p(x_j,y_k)=p(y_k|x_j)p(x_j)$

DMC的例子：二元对称信道（Binary Symmetric Channel）

二元对称信道（Binary Symmetric Channel，BSC）是这是信息论中最经典的离散记忆无信道模型之一，常用于分析误码率和信道容量。

BSC假设信道传输的只有两种符号：0和1。信道是对称的，即，信号在传输时从0翻转到1与从1翻转到0的概率是一样的。

互信息（Mutual Information）

发送的信息X的熵$H(X)$是信息量的期望值，其衡量了传输前的X的不确定性。那么，当已经接收到$Y=y_k$时，来度量对信道输入的X的不确定性就需要条件熵（Conditional Entropy）$H(X|Y=y_k)$。

$H(X|Y=y_k)=\sum_{k=0}^{K-1}H(X|Y=y_k)p(y_k)=\sum_{k=0}^{K-1}\sum_{j=0}^{J-1}p(x_j|y_k)p(y_k)\log_2[\frac{1}{p(x_j|y_k)}]$ $=\sum_{k=0}^{K-1}\sum_{j=0}^{J-1}p(x_j|y_k)\log_2[\frac{1}{p(x_j|y_k)}]$

信道的互信息被定义为：

$I(x;y)=H(X)-H(x|y)$

互信息有以下性质：

对称性：$I(x;y)=I(y;x)$
互信息总大于等于0, $I(x;y)\geq0$
信道的互信息与输入和输出的联合熵有关，$I(x;y)=H(X)+H(Y)-H(X,Y)$，其中$H(X,Y)=\sum_{k=0}^{K-1}\sum_{j=0}^{J-1}p(x_j,y_k)\log_2[\frac{1}{p(x_j,y_k)}]$

离散无记忆信道的容量

离散无记忆信道的信道容量定义为在该信道单次使用中，互信息 $I(X;Y)$的最大值，其中最大化是针对所有可能的输入概率分布 $P(X)$ 进行的。信道容量$C$的单位是每次信道使用的比特数，也可称为每次传输的比特数。

$C=\max_{p(x_j)}I(x;y)$

以二元对称信道为例：

$p(y_0|x_1)=p(y_1|x_0)=p;\ \ \ p(y_0|x_0)=p(y_1|x_1)=1-p$

则该信道的容量为：

$C=1+p\log_2p+(1-p)\log_2(1-p)$

基于这一堆我也看不懂的东西和一堆我也看不懂的推导，香农最终得到了香农信道公式：

$C_{(bps)}=B\log_2(1+SNR)$

香农推导的这一切都是在有线的情况下推导的。对于现在有各种衰落的无线信号，我们仍不知道它的理论信道容量。目前我们仅能通过接收端估计信道的衰落水平。

EE6111-5G-Communication-and-Beyond-P1-2:熵与编码

引入