《信息论与编码》曹雪虹

阅读量：

信息论是研究信息处理、编码、传输和解码的数学基础。1948年，香农的《通信的数学理论》奠定了信息论的框架，提出信息率和信道容量的概念。信息论的核心在于通过数学方法优化信息处理过程，确保高效、可靠地传输信息。
信息论的基本概念包括熵、互信息、信道容量等。熵衡量了信息的不确定性，是信息量的期望值。互信息表示信源和信道的效率，信道容量是信道中最大的互信息值。这些概念在通信、数据压缩和密码学等领域有广泛应用。
信息论分为离散和连续部分。离散信源的熵计算基于概率分布，连续信源的熵基于概率密度函数。熵具有非负性、确定性和最大熵定理等性质。这些性质在信源编码定理中被应用，确保编码效率。
信源编码定理分为无失真和限失真两种情况。无失真编码定理要求码字平均长度满足熵的条件，而限失真编码定理允许一定失真，通过优化编码降低信息率需求。这些定理为编码和解码提供了理论基础。
限失真编码定理通过失真函数和信息率失真函数R(D)描述了在允许失真情况下的编码效率。R(D)函数在失真域内是下凸的，且随着失真增加，信息率减小。这些理论为实际应用提供了指导，如图像和音频压缩。
信息论的理论不仅推动了现代通信技术的发展，还影响了数据存储、密码学和生物医学等领域的技术进步。其核心在于通过数学优化，实现高效、可靠的信息处理。

第一章绪论

1.1信息论的形成和发展

通信系统的核心任务就是在噪声干扰下，系统性地研究和解决如何确保信息传输的准确无误，同时在干扰存在的情况下，实现信息的稳定可靠传输。通过编码等技术手段，系统性地研究和解决通信系统中的各种问题。

信息率失真理论是数据压缩的数学基础。

从信息论和控制论的角度来看，在通信和控制系统中信息的传递本质是信息，而信号则是其具体的载体。信息储存在信号之中，信号则是信息的物理体现。当信号到达接收端（信息论中称为信宿）时，经过处理后会转化为文字、声音或图像等形式，供人们提取和利用。在接收端，面对含噪声的信号，通过一系列处理和变换，最终实现有用信息的提取，这一过程被称为信息提取。信息提取的方法主要包括检测和估计两类。那些能够携带、传输、存储和处理信息的信号统称为数据。

1.2 通信系统的模型

信源编码器：将信源输出的消息转换为由二进制码元（多进制码元）构成的代码组，即基带信号。同时，该装置还具有冗余度压缩功能，以提高信息传输效率。（无失真信源编码和限失真编码）
信源译码器：作为信源编码器的逆向工作装置。
信道编码器：在信源编码器输出的代码组中添加用于检错或纠错的监督码元。（调制解调和纠错检错编译码）
信道译码器：作为信道编码器的逆向工作装置。

第二章信源及信息熵

2.1 信源的描述和分类

离散信源：时间与幅度均为离散分布，如文字、数字、数据等。
连续信源：时间与幅度皆为连续分布，如语言、图像、图形等。
离散信源进一步划分为：

2.2 离散信源熵和互信息

自信息量：

底数为2时，单位为bit；底数为e时，单位为nat；底数为10时，单位为det。

随机事件的不确定度（属性）在数值上等于其自信息量的数值表现，两者在单位上一致，但意义各不相同。

联合自信息量：

如果xy独立，则

因此，

如果xy不独立，可用条件自信息量：

熵（平均自信息量的数值、信源的平均不确定性）：单位为bit/symbol

条件熵：
给定yi（已知yi后，X的不确定度）：

给定Y(各个yi)（已知各个yi后，X的不确定度）：

给定X（各个xi）（已知各个xi后，Y的不确定度）：

联合熵（表示XY同时发生的不确定度）：

关系：

互信息（定义为后验概率与先验概率的比值的对数）：

X与yi间的互信息：

平均互信息（收到Y后能获得的X的信息）：

关系：

三个事件 ，xyz：

熵的性质：
1.非负性
2.对称性
3.确定性
4.香农辅助定理

对于两个概论分布pi和qi，如下等式成立：

即，对于任意概率分布π，它对其他概率分布q的自信息量-log q取其数学期望时，一定大于等于π本身的熵。仅当P等于Q时，等号成立。这可以通过差值来判断分布是否相同（相对熵/KL散度 ）。

5.最大熵定理
只有等概率时，熵最大。

6.条件熵 <无条件熵

例题：

2.3 连续信源的熵和互信息

连续信源熵（有相对意义，而不是绝对值）：

此外，

最大熵定理
为了求解连续信源的最大熵定理，需要进行限制。
限峰功率的最大熵定理：（输入符号的幅度限制在区间 $[a,b]$ 内）当输入符号服从均匀分布时，能够达到最大熵值。
限平均功率的最大熵定理：对于具有固定相关性的输入符号 $X$ ，当其服从正态分布时，能够达到最大熵值。
（可以证明，在正态分布情况下，熵（相对熵）仅与方差有关。这也是为什么噪声设计为高斯白噪声 的原因，由于高斯白噪声是信道中噪声功率最大的情况。）

2.4 离散序列信源的熵

通常情况下消息不是单个符号，而是离散序列的形式：

当无记忆时，序列熵变为：

平均每个符号熵为，即每个符号的符号熵等于单个符号信源的符号熵H(X)。

当有记忆时，序列熵变为：

当平稳信源且满足m阶马尔科夫性质时，分析状态转移概率，特别地，关注一步状态转移概率：

满足：

可写为矩阵形式（转移矩阵）：

注意：只有每行和为1，对于列不成立。
对于k步的转移概率为：

放到矩阵上（比较好理解）：

但是求这种信源的熵（马氏链，平稳信源），需要求出稳定分布的概率：

这里的Wj就是经过无数步后达到 j 的稳等概率，可以列方程求解：

为了使马氏链最终达到稳定状态，成为遍历的马氏链过程，需要具备不可约性和非周期性这两个条件。

不可约性定义：对于任意两个状态，都存在一条路径可以连接它们。作为反例，我们可以构造一个可约的马尔可夫链，其中存在两个状态无法相互转移。

非周期性：对于所有状态i，状态i返回自身需要经过n步转移，其中n的取值没有共同的大于1的公约数，从而保证了系统的非周期性。

上图中的S1返回S1的步数依次为2、4、6等，其最大公约数为2，由此可知周期为2。由于呈现周期性特征，该系统无法达到稳定状态，在周期过程中的每一个特定步数都对应着一个稳态。

具有不可约性和非周期性的马氏链：

通过建立方程组即可求解，其稳定分布的概率为{1/2，1/2}，由此可知，该马氏链具有遍历性（无论从哪个状态出发，经过足够多的转移步骤后，转移概率趋于常数，即达到稳态分布）。最终，这种信源的熵值为（平稳的马尔科夫信源）：

也就是上面提及的Wi。

例题：

2.5 冗余度

冗余度（信息冗余度/剩余度），这与信源符号间的相关程度和信源符号分布的不均匀程度有关。当信源输出符号间彼此独立无关且处于等概率分布状态时，信源实际熵达到最大熵H0(X)。

信息效率：（信息的不确定性水平，所需传输的信息量与实际传输的信息量之比，实际传输的信息量必然包含冗余信息，其总量超过所需传输的信息量）

冗余度（肯定性的程度）：

第三章无失真信源编码

无失真地进行信源编码的定理被称为第一极限定理；
信道编码定理，其中涉及离散和连续信道的情况被称为第二极限定理；
限失真地进行信源编码的定理被称为第三极限定理。

信源编码的核心任务在于消除冗余信息 ，因此，主要方法分为两类：一类是减少冗余内容 ，另一类是实现概率均等化 。

3.1 编码的定义

分组码（块码）：符号序列Xi通过固定码表映射至码字Yi。例如，上表中码1、2、3、4均为分组码。定长码与不定长码：上表中的例子均为不定长码。非奇异码：信源符号与码字之间存在一一对应关系。例如，码2、3、4属于非奇异码；反之，码1则属于奇异码（我的理解是会产生歧义）。例如，码1会产生歧义。唯一可译码：码元序列能够被唯一地分割。例如{0,10,11}、码3、4均为唯一可译码。显然，奇异码不是唯一可译码，非奇异码中既有非唯一可译码（如码2），也有唯一可译码（如码3、4）。唯一可译码又可分为：非即时码、即时码（异前缀码）。可以不可以即时译码。例如，码3、4分别对应。

码树：用来表示码字的构成。

r进制编码树中，n级节点的数量为r的n次方。
当指定某个n级节点作为终端节点时，它代表一个信源符号，即，所有从树根到终端节点的路径都是独一无二的，这限制了前缀码的使用，从而形成了即时码。
满树结构，如图(a)，所构造的码为树码，属于定长码。而非满树结构，如图(b)，则生成非定长码。
对于唯一可译码的充分必要条件，各码字长度Ki必须满足克劳夫特不等式（该不等式仅能说明存在这样的码）。

其中，m是进制数，n是信源符号数。
例子：

3.2 定长编码定理

定长编码定理：对于无记忆平稳信源符号序列

每个符号的熵为

，可用KL个符号进行定长编码 ，每个符号有m种可能值，理解为m进制，{0,1，2，…，m-1}。

只要：

当L足够大时，可以使得译码差错降至极小，从而几乎无失真。取等于时，恰好处在临界状态，可能出现有失真或无失真两种情况。

此定义为平均信息率，即每个信源符号所需的平均编码长度。

编码效率：这可以理解为：当码字的信息量超过信源序列的信息量时，传输几乎无失真。条件是当L足够大。

那L多大呢？例子来说明：

而连续信源仅限于进行定长编码。
通常情况下，当编码块长L有限时，传输效率较高的固定长度的编码方案必然引入失真和误码（即无法实现无失真编码），这与变长编码的无失真特性相比较为有限。

3.3 变长编码定理

单个符号变长编码定理：
离散无记忆信源的符号熵为H(X)，每个信源符号用m进制码元进行变长编码，则存在无失真编码方案，其码字平均长度K满足（可以将logm乘过来，转化为H(X)+logm>K* logm≥H(X)，信源信息量与码字信息量之和大于等于码字信息量）：
信源信息量与码字信息量之和大于等于码字信息量。