第一章 引言与回顾

课程: 网络信息论（Network Information Theory）
教材: A. El Gamal and Y.-H. Kim, Network Information Theory, Cambridge University Press, 2011
整理说明: 本文按教材 1.1~1.8 节顺序展开。
免责声明：本笔记内容来源于课程讲义和PPT，经AI辅助汇总完成，仅供学习参考。如有错误或遗漏，请以原始课程资料为准。

目录

  1. 课程概述与信息论基础
  2. 熵与互信息（§1.1）
  3. 典型序列（§1.2）
  4. 信源编码（§1.3）
  5. 信道容量（§1.4）
  6. 关于容量的进一步讨论（§1.5）
  7. 操作性信道容量（§1.6）
  8. 零错误容量（§1.7）
  9. MIMO 信道（§1.8）
  10. 考试重点速查表

1. 课程概述与信息论基础

1.1 信息论的诞生

1948年，Shannon 应用概率统计方法研究数字通信问题，提出了通信系统的数学模型，并建立了下列四个基本定理，由此奠定了点对点数字通信的完整理论基础：

定理 对应核心概念 简要含义
信道编码定理 容量（Capacity） 信道存在一个最大可靠传输速率
无损信源编码定理 熵（Entropy） 信源可以被压缩到其熵为止，不能再低
有损信源编码定理 率失真函数（Rate-Distortion） 允许失真时，所需速率由率失真函数给出
分离定理 标准二进制接口 信源编码与信道编码可以分开设计而不损失性能

此外，数据处理定理（Data Processing Theorem） 告诉我们对接收信号做任何后处理都不会增加信息量，这指导了现代通信系统采用软判决译码而非硬判决的设计原则。

Viterbi (1991) 的名言: “本世纪下半叶数字通信的进步，由信息论的教训所引导，但由固态电子学的进步所推动。”（Advances in digital communication in the latter half of this century were guided by the lessons of information theory but fueled by the progress in solid state electronics.）

1.2 网络信息流与最大流-最小割定理

网络信息论研究的是多节点网络中的信息传输极限。其数学基础之一是图论中的 最大流-最小割定理（Ford-Fulkerson, Elias-Feistein-Shannon, 1956）。

最大流-最小割定理：网络中从源到宿的最大信息流等于所有割集中的最小割容量。

$C(S)$是割 $(S,S^c)$ 的总容量：将所有节点划分为两个子集 $S$ （含源）和 $S^c$ （含宿），割容量等于从$S$指向$S^c$的所有链路的容量之和。$C_{jk}$ 是从节点 $j \in S$ 到节点 $k \in S^c$ 的链路容量。

理解要点: 网络的整体传输能力受限于”瓶颈”割——就像沙漏的腰部决定了流沙的速度，无论其他部分多粗。

1.3 网络信息论的研究要素与历史

与传统点对点通信不同，多用户通信系统引入了三个关键新元素：

元素 含义 典型场景
干扰（Interference） 多个发射机的信号在接收端相互叠加 多址接入、干扰信道
协作（Cooperation） 节点之间可以共享信息、协同传输 中继信道、分布式天线
反馈（Feedback） 接收端可以将信息回传给发送端 双向通信、ARQ

发展历程:

  • 1961年: Shannon 发表第一篇网络信息论论文 “Two-way communication channels”
  • 1970s~1980s: 大量理论研究涌现（多址信道、广播信道、中继信道等）
  • 1990s 中期至今: 无线通信网络的蓬勃发展重新点燃了对网络信息论的研究兴趣

网络信息论的核心目标是回答多用户网络中的基本信息流问题——每个用户最多能以多快的速率可靠通信？

2. 熵与互信息（§1.1）

本节回顾信息论中最基础的几个量：熵、条件熵、相对熵、互信息，以及它们之间的不等式关系。这些是后续所有定理推导的数学语言。

2.1 熵（Entropy）——不确定度的度量

设 $X$ 为离散随机变量，取值于有限字母表 $\mathcal{X}$，概率质量函数 $P(x) = \Pr{X = x}$，$x \in \mathcal{X}$。

物理意义: 熵 $H(X)$ 是对随机变量 $X$ 不确定度（随机性）的度量。一个确定性的事件（$P(x)=1$）的熵为 0；等概分布的熵最大。

联合熵与条件熵

公式 说明
$H(XY) = E[-\log P(x,y)] = -\sum_x\sum_y P(x,y)\log P(x,y)$ 联合熵：同时观察 $X$ 和 $Y$ 的不确定度
$H(X\vert Y) = -\sum_x\sum_y P(x,y)\log P(x\vert y)$ 条件熵：已知 $Y$ 后，$X$ 剩余的不确定度
$H(X\vert Y) \leq H(X)$ 条件作用不会增加不确定度（等号当 $X$ 与 $Y$ 独立）
$H(XY) = H(X) + H(Y\vert X)$ 联合熵的链式法则（2 变量）

链式法则

将两个变量的链式法则推广到 $N$ 个变量：

含义: 一个随机向量所包含的总不确定度，等于逐个观察每个分量时，在已知前面分量的条件下新增的不确定度之和。

离散熵的上界

其中 $|\mathcal{X}|$ 是字母表大小，等号当且仅当 $X$ 服从均匀分布。直觉：当所有可能取值等可能时，最难预测，不确定度最大。

微分熵（连续随机变量）

对于连续随机变量，熵的定义需要从求和变为积分：

注意: 微分熵与离散熵不同，它可以为负值（例如方差很小的均匀分布），且不具有绝对参考意义。在信息论中，微分熵通常以差值的形式出现（如互信息中）。

给定方差下的最大微分熵: 在所有具有相同方差的连续分布中，高斯分布具有最大的微分熵。

向量情形的最大微分熵: 设随机向量 $\mathbf{X} \in \mathbb{R}^n$ 具有协方差矩阵 $K = E[(\mathbf{X}-E(\mathbf{X}))(\mathbf{X}-E(\mathbf{X}))^T]$，则

等式成立当且仅当 $\mathbf{X} \sim \mathcal{N}(0, K)$。这个结论在 MIMO 信道容量推导中非常重要——最优输入分布是高斯分布。

2.2 相对熵（KL 散度）——两个分布的”距离”

其中 $\text{supp}(P) = {x: P(x) > 0}$ 是 $P$ 的支撑集。

注意: $D(P|Q)$ 不是真正意义上的距离（不对称、不满足三角不等式），但 $D(P|Q) \geq 0$ 恒成立（由 Jensen 不等式可证），等号当且仅当 $P=Q$。

相对熵的直观理解: 如果用分布 $Q$ 来近似真实分布 $P$，则在编码时平均每个符号要多花 $D(P|Q)$ 比特。这就是为什么 KL 散度也被称为”信息散度”（Information Divergence）。

2.3 互信息（Mutual Information）——信息共享量

互信息度量一个随机变量包含关于另一个随机变量的信息量。它是信息论中最核心的量之一。

定义解读: 互信息就是联合分布 $P(x,y)$ 与”假设独立时的分布”$P(x)P(y)$ 之间的 KL 散度——它衡量 $X$ 和 $Y$ 偏离独立的程度。

互信息的多种等价形式

理解: $I(X;Y) = H(Y) - H(Y|X)$ 表示”已知 $X$ 使 $Y$ 的不确定度减少了多少”。

三种情形的互信息计算公式

情形 公式
离散-离散: $X,Y$ 均离散 $I(X;Y) = H(Y) - H(Y\vert X) = H(X) - H(X\vert Y)$
连续-连续: $(X,Y) \sim f(x,y)$ $I(X;Y) = h(Y) - h(Y\vert X) = h(X) - h(X\vert Y) = \iint f(x,y)\log\frac{f(x,y)}{f(x)f(y)}dxdy$
混合: $X$ 离散, $Y\vert X=x \sim f(y\vert x)$ 连续 $I(X;Y) = h(Y) - h(Y\vert X) = H(X) - H(X\vert Y) = \sum_x P(x)\int f(y\vert x)\log\frac{f(y\vert x)}{f(y)}dy$

第三种情形在通信系统中最常见：$X$ 是离散的发送符号，$Y$ 是叠加了连续噪声的接收信号。

1
2
3
4
5
6
7
8
9
10
      H(XY) = 全集
┌─────────────────────────┐
│  ┌─────────┐  ┌───────┐ │
│  │ H(X│Y)  │  │H(Y│X) │ │
│  │         │  │       │ │
│  │   ┌─────┴──┴──┐    │ │
│  │   │  I(X;Y)   │    │ │
│  │   └───────────┘    │ │
│  └────────────────────┘ │
└─────────────────────────┘
  • $H(X) = H(X|Y) + I(X;Y)$
  • $H(Y) = H(Y|X) + I(X;Y)$
  • $H(XY) = H(X|Y) + I(X;Y) + H(Y|X)$

条件互信息

含义：在已知 $Z$ 的条件下，$X$ 中包含的关于 $Y$ 的信息。

⚠️ 重要: $I(X;Y|Z)$ 与 $I(X;Y)$ 之间没有普遍的大小关系！条件作用可以增加互信息（例如 $X,Y$ 独立但 $X,Y$ 通过 $Z$ 相关联时），也可以减少互信息（例如 $Z$ 已经包含了 $X$ 和 $Y$ 的共享信息时）。

互信息的链式法则

物理意义: 一串随机变量 $X_1^n$ 整体包含的关于 $Y$ 的信息，等于逐个观察 $X_i$ 时在已知前面变量的条件下新增的信息之和。这与熵的链式法则完全对偶。

2.4 四个重要不等式

这些不等式是信息论证明的核心工具。

不等式 数学表达 条件 / 备注
IT 不等式 $\log r \leq (r-1)\log e$ $r > 0$ 为任意正实数，等号成立 iff $r = 1$；常用对数底为 2 时：$\log_2 r \leq (r-1)\log_2 e$
Jensen 不等式 $E[f(X)] \geq f(E[X])$ $f$ 为凸函数（convex-∪）；若 $f$ 为凹函数则不等号反向
数据处理不等式 $I(X;Z) \geq I(X;Y)$ 若 $X \to Z \to Y$ 构成 Markov 链，则对数据的任何处理都不会增加其中包含的原始信息量
Fano 不等式 $H_2(P_e) + P_e\log(\vert \mathcal{X}\vert-1) \geq H(X\vert Y)$ $P_e = \Pr(\hat{X} \neq X)$ 为根据 $Y$ 猜 $X$ 的错误概率

Fano 不等式的含义: 如果知道了 $Y$ 能很好地推测 $X$（即 $H(X|Y)$ 很小），那么错误概率 $P_e$ 也必须很小。反过来，如果 $H(X|Y)$ 很大（$Y$ 没有消除多少关于 $X$ 的不确定性），那么无论怎么猜，$P_e$ 都不可能太小。

2.5 熵与互信息的凸性

凸性是求解最优化问题（如信道容量 $C = \max_{P(x)} I(X;Y)$）的数学保证。

性质 说明 应用
$H(X)$ 是 $P(x)$ 的凹函数（convex-∩） 对两个分布的混合，熵不小于各自熵的加权平均 —
固定 $P(y\vert x)$，$I(X;Y)$ 是 $P(x)$ 的凹函数 这意味着局部最大值就是全局最大值 容量计算时可以用凸优化算法（如 Blahut-Arimoto）

3. 典型序列（§1.2）

典型序列是 Shannon 证明编码定理的核心工具。其基本思想是：当序列长度 $n$ 很大时，几乎所有出现的序列都”看起来一样”——它们属于一个称为典型集的子集，该子集虽然只占所有可能序列的极小比例，却占据了几乎全部概率。

3.1 基本设定

考虑一个 DMS（离散无记忆信源），它以独立同分布（i.i.d.）方式从有限字母表 $\mathcal{X}$ 中产生符号。令 $X^n = (X_1, X_2, \ldots, X_n)$ 为长度为 $n$ 的序列，$N(a|X^n)$ 表示字母 $a \in \mathcal{X}$ 在 $X^n$ 中出现的次数。

记号约定：$x^n$ 和 $\mathbf{x}$ 在本文中可互换使用，均表示序列 $(x_1, x_2, \ldots, x_n)$。

3.2 型方法（Method of Types）

型方法是分析离散序列的强大组合工具。一个序列的型就是该序列中每个符号出现的经验频率。

型类 $T(P_x)$ 是所有具有相同型 $P_x$ 的长度为 $n$ 的序列的集合：

例: $\mathcal{X} = {1, 2, 3}$，序列 $x = (1,1,3,2,1)$ 即长度 $n=5$。

  • $P_x(1) = 3/5$（1 出现了 3 次）
  • $P_x(2) = 1/5$（2 出现了 1 次）
  • $P_x(3) = 1/5$（3 出现了 1 次）

型类 $T(P_x) = {11123, 11132, 11213, \ldots, 32111}$ 即所有包含 3 个 1、1 个 2、1 个 3 的长度为 5 的序列。（共计 $\frac{5!}{3!\,1!\,1!} = 20$ 个序列）

3.3 弱典型序列（熵-典型序列）

理论根基——弱大数定律（WLLN）:

样本均值依概率收敛到总体均值。

将 WLLN 应用于 $\log\frac{1}{P(X_i)}$（其期望正是 $H(X)$），即得到信息论中最重要的性质——渐近等分性质（AEP）：

即对任意 $\varepsilon > 0$：

AEP 的含义：当 $n$ 充分大时，一个随机产生的序列几乎一定满足 $P(x^n) \approx 2^{-nH(X)}$，即每个典型序列的概率都约等于 $2^{-nH(X)}$。

Shannon 的典型定义: 序列 $x^n$ 相对于 $\varepsilon$ 和 $P(x)$ 是典型的，如果

典型集:

典型集的三个核心性质

这三个性质精确刻画了”典型集虽小但几乎包含所有概率”：

性质 数学表达 直观解释
(a) 近似等概 $2^{-n[H(X)+\varepsilon]} \leq P(x^n) \leq 2^{-n[H(X)-\varepsilon]}$ 典型集中的每个序列有大致相同的概率
(b) 高概率 $P(X^n \in T_\varepsilon) > 1 - \delta \to 1$（当 $n \to \infty$） 随机序列几乎一定落入典型集
(c) 数量极少 $(1-\varepsilon)2^{n[H(X)-\varepsilon]} \leq \vert T_\varepsilon\vert \leq 2^{n[H(X)+\varepsilon]}$ 典型集大小约为 $2^{nH(X)}$
$\frac{\vert T_\varepsilon\vert }{\vert \mathcal{X}^n\vert } \leq 2^{-n[\log\vert \mathcal{X}\vert-H(X)-\varepsilon]} \to 0$ 典型序列占总序列的比例趋于 0

核心洞察: 虽然总共有 $|\mathcal{X}|^n$ 种可能的序列，但典型集的大小只有约 $2^{nH(X)}$ 个。当 $H(X) < \log|\mathcal{X}|$（非均匀分布时），典型序列只是冰山一角——但概率几乎全部集中于此。

3.4 强典型序列（仅适用于离散随机变量）

弱典型的条件只约束了整体对数概率，而强典型要求每种符号的经验频率都接近真实概率。

定义 1（绝对偏差）:

其中令 $N(a|x^n) = 0$ 若 $P_X(a) = 0$。

定义 2（ε-字母-典型，相对偏差）:

弱典型 vs 强典型的区别:

  • 弱典型：只要求 $-\frac{1}{n}\log P(x^n) \approx H(X)$，即整体对数概率接近熵值。
  • 强典型：要求每种符号的出现频率都接近其真实概率。强典型必然弱典型，反之不成立。
  • 适用场景：弱典型可用于连续分布，强典型仅适用于离散分布。信道编码定理的经典证明中二者均可使用。

3.5 联合典型序列

当涉及两个（或多个）相关随机变量时，需要联合典型的概念。设 $(X^n, Y^n)$ 是从联合分布 $P(x,y)$ 中 i.i.d. 抽取的序列对。

联合典型集:

满足：$2^{-n[H(XY)+\varepsilon]} < P(x^n, y^n) < 2^{-n[H(XY)-\varepsilon]}$

条件解读: 联合典型要求三者同时典型——$x^n$ 关于 $X$ 的边际分布典型，$y^n$ 关于 $Y$ 的边际分布典型，且 $(x^n, y^n)$ 关于联合分布典型。

联合 AEP 定理（Theorem 1.2.1）

设 $(X^n, Y^n)$ 从 $P(x,y)$ i.i.d. 抽取，则当 $n \to \infty$ 时：

  1. $P\big((x^n, y^n) \in T_\varepsilon^{(n)}\big) \to 1$ ——联合典型几乎一定发生
  2. $|T_\varepsilon^{(n)}| \leq 2^{n[H(XY)+\varepsilon]}$ ——联合典型集大小的上界

解读: (1) 表明联合典型也是”高概率”事件；(2) 表明联合典型集的大小由联合熵 $H(XY)$ 决定。

定理 1.2.2（独立抽取的联合典型概率）

若 $\tilde{x}^n$ 和 $\tilde{y}^n$ 是分别独立地从 $P(x)$ 和 $P(y)$ 中抽取的（即 $(\tilde{x}^n, \tilde{y}^n) \sim P(x^n)P(y^n)$），则

🔑 这是信道编码定理证明中最关键的界之一！

意义: 两个独立抽取的序列”碰巧看起来像”联合典型的概率随 $n$ 指数衰减，衰减速率正是互信息 $I(X;Y)$。当 $I(X;Y) > 0$ 时，$n$ 稍大后这个概率就几乎为 0。

在编码定理中的应用: 随机生成码本，每个码字是独立地从 $P(x)$ 生成的。译码时，接收端寻找与接收序列 $y^n$ 联合典型的码字。如果发送的是码字 $x^n(1)$，则 $(x^n(1), y^n)$ 以高概率联合典型（定理 1.2.1），而其他所有不相关的码字与 $y^n$ 联合典型的概率以 $2^{-nI(X;Y)}$ 衰减（定理 1.2.2）。只要总码字数 $< 2^{nI(X;Y)}$，由联合界（union bound），错误概率 → 0。

强联合典型集

其中 $N(a,b|x^n,y^n)$ 是序列对 $(x_1,y_1), (x_2,y_2), \ldots, (x_n,y_n)$ 中 $(a,b)$ 同时出现的次数。

4. 信源编码（§1.3）

信源编码研究如何用尽可能少的比特来表示信源输出。这里的理论基础由 Shannon 的无损信源编码定理给出——压缩极限由信源的熵决定。

4.1 离散无记忆信源（DMS）

DMS: 以 i.i.d. 方式从离散有限字母表 $\mathcal{X}$ 中发射符号的设备。每次发射独立于历史，且服从相同的分布 $P(x)$。

信源编码问题的框图（Fig. 1.3）

目标: 在保证 $P(\hat{X}^n \neq X^n) \to 0$（当 $n \to \infty$）的前提下，最小化平均编码速率：

其中 $\ell(X^n)$ 是码字 $C(X^n)$ 的长度（比特数）。

4.2 定长信源编码 —— 基于 AEP 的数据压缩

利用 AEP，可以构造一个非常简单的定长编码方案：

编码步骤:

  1. 将所有典型序列从 1 到 $|T_\varepsilon^{(n)}|$ 编号，需要 $\lceil n[H(X) + \varepsilon] \rceil + 1$ 比特。
  2. 用一个额外的标志比特 ‘0’ 表示”这是典型序列”，后跟编号。
  3. 若输入序列不是典型序列（小概率事件），则发送标志比特 ‘1’，后跟 $n\log|\mathcal{X}| + 1$ 比特直接描述该序列。

期望码长分析:

其中 $\varepsilon’ = \varepsilon + \varepsilon\log|\mathcal{X}| + \frac{2(1+\varepsilon)}{n} \to 0$ 当 $\varepsilon \to 0$ 且 $n$ 充分大。

因此：$R = E[\ell(X^n)]/n \leq H(X) + \varepsilon’$，即任意略高于熵的速率都可达。

无损信源编码定理（Theorem 1.3.1）

  • 若 $R > H(X)$，则存在编码方案使 $P_e \to 0$（$R$ 可达）
  • 若 $R < H(X)$，则任何编码方案的 $P_e$ 都不可能趋于 0（$R$ 不可达）

编码效率: $\eta = H(X)/R \leq 1$。当 $R$ 接近 $H(X)$ 时效率接近 100%。

4.3 变长信源编码

变长编码可以对高频符号用短码字、低频符号用长码字，从而获得比定长编码更高的效率。

前缀码

定义: 前缀码是指任何码字都不是其他码字前缀的编码。前缀码可以即时译码（收到完整的码字即可立即译出对应符号，无需查看后续比特）。

Kraft 不等式

这是判断一组码字长度能否构成前缀码的充要条件：

其中 $D$ 是编码字母表大小（$D=2$ 为二进制编码），$l_i$ 是第 $i$ 个码字的长度。

重要性质: 每个满前缀码（即不能再添加任何码字而不破坏前缀性质的码）以等式满足 Kraft 不等式。

4.4 最优码的构造

最优前缀码是最小化期望码长 $L = \sum_i P_i l_i$ 的前缀码。求解以下优化问题：

拉格朗日乘子法给出理论最优解（忽略整数约束）:

即每个符号的理想码长等于其自信息（以 $D$ 为底）。此时期望码长 $L^* = H_D(X)$。

前缀信源编码定理（Theorem 1.3.2）

对于任意熵为 $H(X)$ 的 DMS，存在 $D$ 元前缀码，使得对长度为 $n$ 的信源分组进行编码时，每符号的平均码长 $\bar{L}_n$ 满足：

解读: 当分组长度 $n \to \infty$ 时，平均码长可以无限逼近熵值 $H(X)/\log D$（以 $D$ 元为单位）。

4.5 Shannon 码与 Huffman 码

编码 构造方法 特点
Shannon 码 $l_i = \lceil -\log_D P_i \rceil$（对理想码长向上取整） 构造简单，在 1 比特内达到最优
Huffman 码 贪心算法：反复合并两个最小概率的信源符号，自底向上构建二叉树 最优前缀码，在单个符号级别达到最小期望码长

5. 信道容量（§1.4）

信道容量是通信系统最核心的极限指标——它给出了在给定信道上实现可靠通信的最高速率。

5.1 离散无记忆信道（DMC）

DMC 的定义: 信道在时刻 $n$ 的输出 $Y_n$ 仅依赖于该时刻的输入 $X_n$，与之前的所有输入输出无关：

无反馈时，$n$ 次使用的联合条件概率简化为乘积：

DMC 由三要素描述: 输入字母表 $\mathcal{X}$、输出字母表 $\mathcal{Y}$、转移概率矩阵 $P(y|x)$。

5.2 容量的双重定义

概念 定义 说明
信息容量 $C = \max_{P(X)} I(X;Y)$ 数学优化问题：找到使互信息最大的输入分布
操作容量 所有可达速率的上确界 工程定义：实际可以可靠通信的最高速率
可达速率 $R$ 存在 $(2^{nR}, n)$ 码序列，使最大（或平均）错误概率 $P_e^{(n)} \to 0$（$n \to \infty$） 存在性定义

噪声信道编码定理（Theorem 1.4.1）

任意低于 $C = \max_{P(X)} I(X;Y)$ 的速率都是可达的。

这一定理的重要意义:

  1. 它建立了操作容量 = 信息容量的等价关系。从此”容量”一词既指 $C = \max I(X;Y)$ 的计算值，也指可达速率的上确界，两者等价。
  2. 它解决了容量的计算问题——将工程上的可达速率问题转化为互信息的最大化问题，这在数学上是可求解的。
  3. 证明方法: Shannon 采用”随机编码 + 典型集译码“的方法：随机生成大量码字，译码时寻找与接收序列联合典型的码字。分析的是码本集合上的平均错误概率，由此推出至少存在一个好的码本使错误概率任意小。

5.3 典型信道的容量计算

(1) 二元对称信道（BSC）

  • 输入和输出均为 ${0, 1}$，交叉概率为 $\varepsilon$（即每个比特以概率 $\varepsilon$ 被翻转）。
  • 最优输入分布：等概（$P(0) = P(1) = 1/2$）。

其中 $H_2(p) = -p\log_2 p - (1-p)\log_2(1-p)$ 为二元熵函数。

  • $\varepsilon = 0$（无噪声）→ $C = 1$ bit/使用
  • $\varepsilon = 0.5$（完全随机）→ $C = 0$（信道无意义）
  • 图像关于 $\varepsilon = 0.5$ 对称

(2) 二元擦除信道（BEC）

  • 输入 ${0,1}$，输出 ${0, e, 1}$，符号以概率 $\alpha$ 被擦除（接收端知道它被擦除了，但不知道原值）。

推导过程：

理解: 当擦除概率为 $\alpha$ 时，$\alpha$ 比例的传输被浪费（知道丢了但不知道丢了什么），剩下 $1-\alpha$ 的传输是完美的（知道收到的是 0 还是 1 就确知原值）。

(3) 一般离散无记忆信道的容量界

这个不等式将序列互信息与单符号互信息联系起来：$n$ 次使用信道获得的总互信息，最多等于每次单独使用的互信息之和（当输入在时间上独立时取等号）。

一般信道的数值计算: 当信道不是对称的，最优输入分布没有闭式解时，使用 Blahut-Arimoto 算法（一种交替优化的迭代算法）来数值计算容量。

5.4 信源-信道分离定理

考虑将一个满足 AEP 的 i.i.d. 信源 $V^n$ 通过 DMC $P(y|x)$ 进行可靠传输。
这可以做到当且仅当 $H(V) < C$。

分离定理的意义: 我们可以独立地设计信源编码（压缩到 $H(V)$）和信道编码（达到 $C$），然后将二者级联。只要 $H(V) < C$，整个系统就可以可靠工作。这极大地简化了通信系统的工程设计——信源编码和信道编码可以作为两个独立模块来优化。

5.5 反馈容量

Theorem 1.4.2: 对于 DMC，反馈不增加容量。

  • 容量不变: 无论有没有从接收端到发送端的完美反馈链路，信道的香农容量都是一样的。
  • 但反馈有价值: 反馈极大地简化了编码方案——有了反馈，可以用简单的重传协议达到接近容量；没有反馈则需要复杂的前向纠错码（如 Turbo 码、LDPC 码、Polar 码）。

5.6 高斯信道

高斯信道是模拟通信系统最基础的模型。接收信号等于输入信号乘以信道增益再加高斯白噪声。

  • $h$: 信道增益（可以固定，也可以随机——对应衰落信道）
  • $Z \sim \mathcal{N}(0, \sigma_z^2)$: 加性高斯白噪声（AWGN）
  • 功率约束：$E[X^2] \leq P$

高斯信道互信息的推导:

当 $X \sim \mathcal{N}(0, P)$ 时，$Y \sim \mathcal{N}(0, h^2P + \sigma_z^2)$。

这就是著名的 Shannon 公式: $C = \frac{1}{2}\log_2(1 + \text{SNR})$ bits/real dimension。

  • $\text{SNR} = h^2P / \sigma_z^2$ 是信噪比。
  • 当 SNR 很高时，$C \approx \frac{1}{2}\log_2(\text{SNR})$——容量随 SNR 的对数增长。
  • 当 SNR 很低时，$C \approx \frac{\text{SNR}}{2\ln 2}$——容量近似与 SNR 成线性关系。

衰落信道

当 $h$ 是与 $X$ 和 $Z$ 独立的随机变量时（分布密度为 $P_h(\cdot)$），信道输出扩充为向量 $Y’ = [hX + Z, h]$（接收端已知 $h$）：

物理含义: 在衰落信道中，容量等于各衰落状态下瞬时容量的统计平均（当发射端不知道信道状态时，这是上界；当发射端知道信道状态并做功率注水时，可达容量可能更大）。

并行高斯信道：注水定理

当多个并行高斯子信道共享总功率约束时，最优功率分配策略是注水（Water-Filling）——将更多的功率分配给增益（或信噪比）较高的子信道，对增益过低的子信道可能不分配功率。具体公式见 §9.5 节的 MIMO 注水算法。

波形信道（限带 AWGN 信道）

其中 $z(t)$ 是高斯随机过程。若 $x(t)$ 仅在 $[-W, W]$ 频率范围有非零分量，则：

这就是 Shannon-Hartley 定理：容量 = 带宽 × 频谱效率上界。增加带宽或增加功率都可以提高容量，但效果不同——功率增加使容量对数增长，带宽增加使容量线性增长（但 SNR 随之下降）。

6. 关于容量的进一步讨论（§1.5）

本节从更精确的数学角度审视”容量”这个概念，澄清一些容易被误解的细节。

6.1 可靠通信的速率上界

将一次传输 $N$ 个符号视为一个整体（超符号），其上界为：

展开互信息：

等号成立条件

式 (1) 取等号要求输出符号在时间上独立。实现此条件的一种方式是使输入符号在时间上独立。

在此条件下优化输入分布 $P(X^N)$ 以最大化 $I(X^N; Y^N)$，等价于在每个时刻独立地选择 $P(X_i)$ 以最大化单符号互信息。因此：

结论: 即使允许任意 $N$ 符号联合编码，能达到的最高速率也不会超过单符号互信息优化的结果 $C$。

6.2 一个重要澄清 ⚠️

问: “式(1.2)取等号”是否意味着不需要编码就能达到容量？

答: 不！这是对容量概念最常见的误解。

  • 上述推导只是”信息”容量的优化结果——它告诉我们 $C = \max I(X;Y)$ 是互信息的上界，但不考虑错误概率。
  • 可靠通信无法恰好以速率 $C$ 实现——$C$ 只是一个上确界（supremum），不是可达速率本身。
  • 对于任意严格小于 $C$ 的速率（无论多接近 $C$），信道编码定理保证存在编码使可靠通信成为可能——此时输出符号几乎独立。
  • 编码的作用是将 $n$ 次信道使用耦合起来，使得在译码端可以”平均掉”噪声的影响（大数定律），代价是引入了时延。

7. 操作性信道容量（§1.6）

为了精确陈述信道编码定理，需要严格定义”可达速率”和”容量”。

7.1 精确定义

术语 定义
$(n, \varepsilon)$-码 对信道 ${Pn : \mathcal{X}^n \to \mathcal{Y}^n}{n=1}^{\infty}$ ，一个长度为 $n$ 的分组码，其最大错误概率 $\leq \varepsilon$
$\varepsilon$-可达速率 $R$ 若对任意 $\delta > 0$ 和所有充分大的 $n$，存在速率 $> R - \delta$ 的 $(n, \varepsilon)$-码
可达速率 $R$ 对所有 $0 < \varepsilon < 1$ 都是 $\varepsilon$-可达的速率
$\varepsilon$-容量 $C_\varepsilon$ 所有 $\varepsilon$-可达速率的上确界
容量 $C$ 所有可达速率的上确界

关键性质: $\lim{\varepsilon \to 0} C\varepsilon = C$ ——当对错误概率的要求越来越严格时， $\varepsilon$-容量趋于（无错误约束下的）容量。

7.2 噪声信道编码定理（正式表述）

对于任意 $0 < \varepsilon < 1$，DMC 的 $\varepsilon$-容量为：

数学意义: 这一表述将”容量”从操作性定义（可达速率的上确界）转化为信息论定义（互信息的最大值），使得信道容量在原则上可以计算到任意精度。这是 Shannon 理论最漂亮的结论之一。

8. 零错误容量（§1.7）

Shannon 于 1956 年提出了一个比普通容量更严格的概念——零错误容量（Zero-Error Capacity）。

8.1 动机与定义

普通容量允许错误概率 $\to 0$（但不是严格为 0）。零错误容量要求严格零错误——译码器永远不会犯错误。

Bhattacharyya 距离: 两个输入符号 $a_i$ 和 $a_j$ 被称为处于”无穷 Bhattacharyya 距离”，若它们的输出分布完全不重叠：

直观: 这意味着接收端从收到的输出符号可以绝对确定发送的是 $a_i$ 还是 $a_j$，两个符号不可能被混淆。

零错误容量的定义: 对每个 $n$，令 $\mathcal{C}^{(n)}$ 是长度为 $n$ 的最大分组码，满足其中任意两个不同的码字 $x^m$ 和 $x^{m’}$ 都有：

（即任意两个码字的输出分布完全不重叠）。令 $M_n = |\mathcal{C}^{(n)}|$，则：

$C_0$ 是使得译码错误概率严格为零的任意分组码的最大可达速率。

8.2 定理 1.7.1 及其证明

定理: 要么 $C_0 = 0$，要么 $C_0 \geq 1$。

证明:

若 $C_0 \neq 0$，则存在某两个输入符号 $a_i$ 和 $a_j$ 满足 $\sum_k \sqrt{P(k|i)P(k|j)} = 0$。

取两个长度为 1 的码字 $x_1 = a_i$ 和 $x_2 = a_j$。译码器从不会混淆这两个码字（因为输出分布不重叠），因此译码错误概率为 0。使用这两个码字，可以以 1 bit/symbol 的速率可靠通信。因此 $C_0 \geq 1$。

📌 复习注意: 零错误容量的具体计算通常非常困难，即使是简单的信道（如五边形信道），其零错误容量至今未知。这是一个著名的开放问题。

9. MIMO 信道（§1.8）

多输入多输出（MIMO）技术是现代无线通信最重要的技术突破之一。通过在收发两端配置多根天线，MIMO 系统可以在不增加带宽和发射功率的前提下显著提高频谱效率。

9.1 系统模型

考虑一个具有 $N$ 根发射天线和 $M$ 根接收天线的单用户 MIMO 系统（记为 $(N, M)$ 系统）。

数学模型

在离散时间基带下，MIMO 信道描述为：

符号 维度 含义
$\mathbf{x}$ $N \times 1$ 发射信号向量（复值）
$\mathbf{y}$ $M \times 1$ 接收信号向量（复值）
$\mathbf{H}$ $M \times N$ 信道矩阵，$h_{ij}$ 表示从发射天线 $j$ 到接收天线 $i$ 的信道增益
$\mathbf{n}$ $M \times 1$ 噪声向量，$\mathbf{n} \sim \mathcal{CN}(0, N_0\mathbf{I}_M)$

功率约束: 总发射功率受限于 $P$，与天线数 $N$ 无关：

其中 $\mathbf{K}_x = E[\mathbf{x}\mathbf{x}^H]$ 是发射信号的协方差矩阵。

归一化: 假设每根接收天线的接收功率等于总发射功率（在确定性 $\mathbf{H}$ 情形下）：

对于随机 $\mathbf{H}$（富散射环境），假设 $\mathbf{H}$ 的各项为 i.i.d. 零均值复高斯变量，每维方差 $1/2$。此时每条接收天线的平均 SNR = $P/N_0$。

9.2 MIMO 信道容量的推导

容量定义（确定性信道，接收端已知 $\mathbf{H}$）:

展开：

已知 $\mathbf{x}$ 和 $\mathbf{H}$ 时，$\mathbf{y} = \mathbf{H}\mathbf{x} + \mathbf{n}$ 的随机性仅来自 $\mathbf{n}$：

这是一个与输入无关的常数。因此最大化 $I(\mathbf{x}; \mathbf{y}|\mathbf{H})$ 等价于最大化 $H(\mathbf{y}|\mathbf{H})$。

关键结论: 在给定协方差矩阵 $\mathbf{K}_y$ 的随机向量中，零均值循环对称复高斯（ZMCSCG） 分布最大化微分熵。这就要求 $\mathbf{x}$ 也是 ZMCSCG 分布——这就是 MIMO 容量达到时的最优输入分布。

代入协方差矩阵 $\mathbf{K}_y = \mathbf{H}\mathbf{K}_x\mathbf{H}^H + N_0\mathbf{I}_M$：

MIMO 容量的一般表达式

利用行列式恒等式 $\det(\mathbf{I}_m + \mathbf{A}\mathbf{B}) = \det(\mathbf{I}_n + \mathbf{B}\mathbf{A})$（$\mathbf{A}$ 为 $m \times n$，$\mathbf{B}$ 为 $n \times m$）：

9.3 情形一：发射端未知信道（No CSIT）

若发射端不知道信道状态信息（CSIT），但接收端知道（CSIR），且信道矩阵 $\mathbf{H}$ 服从零均值空间白化（ZMSW）模型，则最优策略是各天线独立等功率分配：

容量简化为：

其中 $\text{SNR} = P/N_0$。

直观: 发射端不知道信道，无法做定向波束赋形，只能”均匀喷洒”功率。在富散射环境下，这正是最优策略。

9.4 情形二：SVD 并行分解——将 MIMO 化为并行标量信道

MIMO 信道最深刻的结构性质是：通过奇异值分解（SVD），可以将 MIMO 信道转化为若干个并行的独立标量高斯子信道。

SVD 分解

任何 $M \times N$ 复矩阵 $\mathbf{H}$ 可以分解为：

  • $\boldsymbol{\Lambda} \in \mathbb{R}^{M \times N}$: 非负实对角矩阵
  • $\mathbf{U} \in \mathbb{C}^{M \times M}$: 酉矩阵，$\mathbf{U}\mathbf{U}^H = \mathbf{I}_M$
  • $\mathbf{V} \in \mathbb{C}^{N \times N}$: 酉矩阵，$\mathbf{V}\mathbf{V}^H = \mathbf{I}_N$
  • $\boldsymbol{\Lambda}$ 的对角元是 $\mathbf{H}\mathbf{H}^H$ 的特征值的非负平方根（即 $\mathbf{H}$ 的奇异值）

等效变换

代入 (1.8) 到 (1.3)：

令 $\tilde{\mathbf{y}} = \mathbf{U}^H\mathbf{y}$，$\tilde{\mathbf{x}} = \mathbf{V}^H\mathbf{x}$，$\tilde{\mathbf{n}} = \mathbf{U}^H\mathbf{n}$。由于 $\mathbf{U}$ 和 $\mathbf{V}$ 是可逆酉矩阵，$\tilde{\mathbf{n}}$ 与 $\mathbf{n}$ 同分布，且 $E[\tilde{\mathbf{x}}^H\tilde{\mathbf{x}}] = E[\mathbf{x}^H\mathbf{x}]$。于是原信道等价于：

展开为标量形式：

其中 $m = \min(M, N)$，$\lambda_i$ 是 $\mathbf{H}\mathbf{H}^H$（或 $\mathbf{H}^H\mathbf{H}$）的正特征值。

物理含义: SVD 变换揭示 MIMO 信道实际上是由 $m = \min(M, N)$ 个并行的独立标量高斯子信道组成的——这就是 Fig. 1.5 和 Fig. 1.6 的核心内容。

  • 若 $N > M$（发射天线多于接收天线）：最多有 $M$ 个有效的非零增益子信道；多余的发射天线不增加子信道数量，但通过波束赋形可提高每个子信道的增益。
  • 若 $M > N$（接收天线多于发射天线）：最多有 $N$ 个有效的非零增益子信道；多余的接收天线提供分集增益。

特征值与 Wishart 矩阵

令 $\lambda_i$ 为 $\mathbf{H}\mathbf{H}^H$ 的特征值，由 $\mathbf{H}\mathbf{H}^H\mathbf{z} = \lambda\mathbf{z}$（$\mathbf{z} \neq 0$）定义。

Wishart 矩阵:

  • $\mathbf{W}$ 的非零特征值个数 = $\text{rank}(\mathbf{H}) = r \leq m = \min(M, N)$
  • 若信道是满秩的（富散射环境），$r = m$
  • $\sqrt{\lambda_i}$ 也称为 $\mathbf{H}$ 的奇异值

特征值通过解 $\det(\lambda\mathbf{I}_m - \mathbf{W}) = 0$ 求得。

9.5 情形三：发射端已知信道（CSIT + CSIR）——注水算法

当收发两端都已知完美信道信息时，发射端可以对各并行子信道进行最优功率分配。这就是著名的注水（Water-Filling）算法。

将 SVD 代入容量公式 (1.6)，利用酉矩阵的性质化简，得到在并行子信道上的功率分配问题：

这是一个凸优化问题。求解得到最优功率分配：

其中 $a^+ = \max(0, a)$，$\mu$ 为”水位”参数，由总功率约束确定：

注水容量的表达式

容量可达时的输入协方差矩阵为：$\mathbf{K}_x = \mathbf{V}\mathbf{P}\mathbf{V}^H$，其中 $\mathbf{P} = \text{diag}(P_1, P_2, \ldots, P_m, 0, \ldots, 0)$ 为 $N \times N$ 对角阵。

注水的物理解释

将总功率 $P$ 看作”水”，倒入各子信道的”容器”中。每个子信道的底高为 $N_0/\lambda_i$——增益 $\lambda_i$ 越大，底越低，能容纳更多的水（功率）；增益过小的子信道（底高于水位 $\mu$），得不到任何功率分配。

注水算法的迭代步骤

  1. 初始化: 设迭代次数 $p = 1$，假设所有 $m-p+1$ 个子信道都被使用。
  2. 计算水位:
  3. 分配功率:
  4. 检查: 若增益最低的子信道功率 $P{m-p+1} < 0$，则丢弃该子信道（设 $P{m-p+1} = 0$），令 $p \gets p+1$，返回步骤 2。
  5. 终止: 直至所有保留子信道的 $P_i \geq 0$，或 $p = m$（所有子信道都被丢弃）。

计算说明: 在实践中，先对特征值 $\lambda_i$ 从大到小排序，然后依次尝试分配。注水算法通常只需少数几次迭代即可收敛。

注水效果总结

条件 策略
子信道增益高（$\lambda_i$ 大） 分配较多功率
子信道增益低（$\lambda_i$ 小） 分配较少功率
子信道增益极低（$N_0/\lambda_i > \mu$） 不分配功率（弃用）
无 CSIT 所有天线等功率分配 $\mathbf{K}_x = \frac{P}{N}\mathbf{I}_N$

10. 考试重点速查表

10.1 核心公式汇总

名称 公式 页码
熵 $H(X) = -\sum_x P(x)\log P(x)$ §1.1
联合熵链式法则 $H(X1^n) = \sum{i=1}^n H(X_i \vert X_1^{i-1})$ §1.1
微分熵 $h(X) = -\int f(x)\log f(x)dx$ §1.1
最大微分熵（标量） $h(X) \leq \frac{1}{2}\log(2\pi e\sigma^2)$ §1.1
最大微分熵（向量） $h(\mathbf{X}) \leq \frac{1}{2}\log(2\pi e)^n\vert K\vert$ §1.1
KL 散度 $D(P\vert Q) = \sum_x P(x)\log\frac{P(x)}{Q(x)}$ §1.1
互信息 $I(X;Y) = H(Y) - H(Y\vert X) = \sum_{x,y} P(x,y)\log\frac{P(x,y)}{P(x)P(y)}$ §1.1
互信息链式法则 $I(X1^n;Y) = \sum{i=1}^n I(X_i;Y\vert X_1^{i-1})$ §1.1
Jensen 不等式 $E[f(X)] \geq f(E[X])$（$f$ 凸） §1.1
数据处理不等式 $X \to Z \to Y \implies I(X;Z) \geq I(X;Y)$ §1.1
Fano 不等式 $H_2(P_e) + P_e\log(\vert \mathcal{X}\vert-1) \geq H(X\vert Y)$ §1.1
AEP $-\frac{1}{n}\log P(X^n) \to H(X)$ 依概率收敛 §1.2
典型集大小 $\vert T_\varepsilon\vert \approx 2^{nH(X)}$ §1.2
联合典型概率界 $P((\tilde{x}^n,\tilde{y}^n) \in T_\varepsilon^{(n)}) \leq 2^{-n[I(X;Y)-3\varepsilon]}$ §1.2
Kraft 不等式 $\sum_i D^{-l_i} \leq 1$ §1.3
信源编码定理 $H(X)/\log D \leq \bar{L}_n < H(X)/\log D + 1/n$ §1.3
BSC 容量 $C = 1 - H_2(\varepsilon)$ §1.4
BEC 容量 $C = 1 - \alpha$ §1.4
高斯信道容量 $C = \frac{1}{2}\log(1 + \text{SNR})$ §1.4
Shannon-Hartley $C = W\log_2(1 + \text{SNR})$ bits/s §1.4
MIMO 容量（一般） $C = \max_{\text{tr}(\mathbf{K}_x)=P} \log_2\det(\mathbf{I} + \frac{1}{N_0}\mathbf{H}\mathbf{K}_x\mathbf{H}^H)$ §1.8
注水功率分配 $P_i = (\mu - N_0/\lambda_i)^+$ §1.8
注水容量 §1.8

10.2 关键概念对比

维度 弱典型 强典型
条件 $\vert -\frac{1}{n}\log P(x^n) - H(X)\vert \leq \varepsilon$ $\vert \frac{1}{n}N(a\vert x^n) - P_X(a)\vert < \varepsilon P_X(a)$
关注点 整体对数概率 每种符号的经验频率
适用范围 离散 + 连续 仅离散
在证明中 用于信道编码定理（联合典型译码） 用于更精细的分析
维度 无 CSIT 有 CSIT + CSIR
策略 等功率分配 $\mathbf{K}_x = \frac{P}{N}\mathbf{I}_N$ 注水功率分配
容量 $C = \log_2\det(\mathbf{I} + \frac{\text{SNR}}{N}\mathbf{H}\mathbf{H}^H)$ $C_{WF} = \sum \frac{1}{2}\log_2(\mu\lambda_i)^+$
何时最优 ZMSW 信道模型 发射端已知 $\mathbf{H}$

10.3 重要定理速查

定理 核心结论 关键条件
信道编码定理 $R < C$ 可达，$R > C$ 不可达 DMC，$n \to \infty$
信源编码定理 $R > H(X)$ 可达，$R < H(X)$ 不可达 DMS，$n \to \infty$
分离定理 信源编码 + 信道编码可独立设计 $H(V) < C$
反馈容量 $C_{FB} = C$（反馈不增容量但简化编码） DMC
联合 AEP 联合典型高概率出现；独立抽取的联合典型概率指数小 i.i.d. 抽取
零错误容量 $C_0 = 0$ 或 $C_0 \geq 1$ Bhattacharyya 距离无穷大
最大微分熵 给定协方差下高斯分布最优 连续随机向量

复习策略建议:

  1. 熵与互信息（§1.1~§1.2）是整门课的数学语言——必须烂熟于心。重点掌握链式法则、AEP 的陈述和应用、Fano 不等式。
  2. 信源编码（§1.3）与信道容量（§1.4）是 Shannon 理论的两大支柱。理解 Kraft 不等式→信源编码定理的逻辑链，以及 $C = \max I(X;Y)$→信道编码定理的证明思路。
  3. MIMO（§1.8）是网络信息论在物理层的核心应用。SVD 并行分解 + 注水算法是必须掌握的推导。
  4. 考试中的计算题大概率涉及：BSC/BEC 容量计算、高斯信道互信息推导、MIMO 注水功率分配。
  5. 证明题的核心工具：Fano 不等式（下界）、典型集界 + union bound（上界）、链式法则（展开/合并）、Jensen 不等式（凸性分析）。