第六节、信息的无损压缩
约 731 个字 3 张图片 预计阅读时间 2 分钟
一、信息论的信源问题
总体过程：信源\(\rightarrow\)信宿
传输模型：
我们为什么要有这些过程？ 信源遍码：信源是冗余的，所以是压缩编码 信道遍码：信道有噪声，需要在有错误的信道上传输
因此，信息论中的信源问题，即以下的问题， - 构成描述信源的模型：随机变量序列或随机过程 - 计算信源输出的信息量，或者说信源的熵 - 如何有效地表示信源的输出，即信源编码
信源编码的目标： 在代价最小的意义上来最有效地表示一个信源，包括量化、压缩、映射、变换、自然语言翻译等许多具体和抽象的过程。 代价最小： 最少的比特数；即到底用多少个比特可以对一个信源进行编码？ （香农的贡献：提出了极限，并且给出了具体的编码方式，因此理论体系是完备的，即存在上确界/下确界）
我们应该如何压缩编码？
我们举个例子，假设有一种外星人的语言只含有a,b,c,d四种字母，其出现概率如下表。
| a | 0.5 |
|---|---|
| b | 0.25 |
| c | 0.125 |
| d | 0.125 |
| 一般的编码方式： |
| a | 0.5 | 00 |
|---|---|---|
| b | 0.25 | 01 |
| c | 0.125 | 10 |
| d | 0.125 | 11 |
| \(\therefore R=0.5\cdot 2+0.25 \cdot 2+0.125 \cdot 2+0.125 \cdot 2=2 \ bit\) |
实际上，我们可以进行第二种编码：
| a | 0.5 | 0 |
|---|---|---|
| b | 0.25 | 10 |
| c | 0.125 | 110 |
| d | 0.125 | 111 |
| 我们再来计算此时的\(R\): \(0.5\cdot 1+0.25 \cdot 2+0.125 \cdot 3+0.125 \cdot 3=1.75 \ bit\), 显然此时 \(R\) 的值变小了。 |
我们来计算一下\(a,b,c,d\) 这组数据的熵 \(H(X)=-0.5 \log 0.5-0.25 \log 0.25 - 0.125 \log 0.125 - 0.125 \log 0.125 = 1.75 \ bit\) ，
这个例子恰好有\(H=X\)，如果概率的分布没有那么巧合呢？
考虑如下分布：
| a | 0.4 |
|---|---|
| b | 0.4 |
| c | 0.1 |
| d | 0.1 |
| 我们继续使用上面的编码方式，即不等长的编码。此时的\(R\), \(0.4\cdot 1+0.4 \cdot 2+0.1 \cdot 3+0.1 \cdot 3=1.8 \ bit\) |
\(H(X)= - (0.4\log 0.4 + 0.4 \log 0.4 + 0.1 \log 0.1 + 0.1 \log 0.1)=1.72 \ bit\)
我们可以把信源编码按以下简单地分类：
渐进无差错编码(的数学表示)：给定任意的\(\epsilon\)，总存在\(N\),使得\(n>N\)时，使得\(P_e^{(n)}<\epsilon\)
同时，还有一些分类方式：
我们用8bit来表示256色的图片\(\rightarrow\)等长编码 我们上面的方式（霍夫曼编码\(\rightarrow\)不等长编码）
香农将信息的传输建模为方框图：
对于离散无记忆信源（DMS）：
- \(u^L=(u_1,u_2,\cdots, u_L)\) ：长度为L的消息序列（例如：a-z 26个字母）
- \(x^N=(x_1,x_2,\cdots, x_N)\)：长度为N的码字，需要进行发送（例如：若\(L=26\)，则要进行一般的编码，\(N=5\)）
- \(\mathcal C\): 码书，码字的集合（标号的集合）
- \(\mathcal{D}\): 译码器