第一章 引言与回顾 —— 熵、互信息、典型序列与信道容量

第一章是整门课的数学语言基础。熵与互信息的定义、链式法则、四个不等式（IT/Jensen/Fano/数据处理）、典型序列与AEP、信道容量的定义与计算——这些是后续所有章节证明推导的通用工具箱。

1.1 熵（Entropy）

定义

基本性质与证明

性质1 — 非负性（离散）：$H(X) \geq 0$

证：$0 \leq P(x) \leq 1 \implies \log(1/P(x)) \geq 0 \implies H(X) = E[\log(1/P(X))] \geq 0$。等号当 $X$ 为确定性变量。

性质2 — 上界：$H(X) \leq \log|\mathcal{X}|$

证：令 $u(x) = 1/|\mathcal{X}|$ 为均匀分布。

故 $H(X) \leq \log|\mathcal{X}|$。等号当且仅当 $P(x) = u(x)$ 即均匀分布。

性质3 — 凹性：$H(X)$ 是 $P(x)$ 的凹函数（∩）

含义：$H(\lambda P_1 + (1-\lambda)P_2) \geq \lambda H(P_1) + (1-\lambda)H(P_2)$。这是 $-x\log x$ 凹性的直接结果。

联合熵与条件熵

公式 名称 含义
$H(X,Y) = -\sum_{x,y} P(x,y)\log P(x,y)$ 联合熵 $X,Y$ 总不确定度
$H(X\vert Y) = -\sum_{x,y} P(x,y)\log P(x\vert y)$ 条件熵 已知 $Y$ 后 $X$ 剩余的不确定度
$H(X,Y) = H(X) + H(Y\vert X) = H(Y) + H(X\vert Y)$ 链式法则（2变量） 联合熵的分解

性质4 — 条件不增熵：$H(X|Y) \leq H(X)$

证：$H(X) - H(X|Y) = I(X;Y) \geq 0$（由 $D(P_{XY}|P_X P_Y) \geq 0$）。等号当 $X \perp Y$。

性质5 — 链式法则（$N$ 变量）：

性质6 — 独立界：，等号当 相互独立。

微分熵（连续随机变量）

注意：微分熵可正可负，不具有绝对参考意义，通常以差值形式出现（如互信息）。

性质7 — 给定方差下的最大微分熵：

等号当且仅当 $X \sim \mathcal{N}(\mu, \sigma^2)$。

证：令 $f$ 为 $X$ 的密度，$\phi$ 为 $\mathcal{N}(0,\sigma^2)$ 的密度。

性质8 — 向量情形的最大微分熵：

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

1.2 相对熵（KL 散度）

定义

性质与证明

性质9 — 非负性（信息不等式）：$D(P|Q) \geq 0$

证（Jensen）：

其中 $\log(\cdot)$ 是凹函数，由 Jensen：$E[\log Z] \leq \log E[Z]$，取 $Z = Q(x)/P(x)$。
等号当且仅当 $\frac{Q(x)}{P(x)} \equiv 1$ 即 $P = Q$。

性质10 — 不对称性：$D(P|Q) \neq D(Q|P)$（一般情况）。

性质11 — 对 $(P,Q)$ 联合凸。

性质12 — 链式法则：

1.3 互信息（Mutual Information）

定义

等价形式

理解：已知 $X$ 使 $Y$ 的不确定度减少了多少。

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

情形 公式
离散-离散 $I(X;Y) = H(Y) - H(Y\vert X) = H(X) - H(X\vert Y)$
连续-连续 $I(X;Y) = h(Y) - h(Y\vert X) = h(X) - h(X\vert Y)$
混合（$X$离散，$Y\vert X$连续） $I(X;Y) = h(Y) - h(Y\vert X) = H(X) - H(X\vert Y)$

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

熵与互信息的 Venn 图关系

1
2
3
4
5
6
7
8
9
10
      H(X,Y) 全集
┌─────────────────────────┐
│  ┌─────────┐  ┌───────┐ │
│  │ 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(X,Y) = H(X|Y) + I(X;Y) + H(Y|X)$

条件互信息

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

性质与证明

性质13 — 非负性：$I(X;Y) \geq 0$

证：$I(X;Y) = D(P(x,y)|P(x)P(y)) \geq 0$（由 KL 散度的非负性）。

性质14 — 对称性：$I(X;Y) = I(Y;X)$

性质15 — 上界（离散）：$I(X;Y) \leq \min{H(X), H(Y)}$

证：$I(X;Y) = H(X) - H(X|Y) \leq H(X)$（因 $H(X|Y) \geq 0$）。

性质16 — 链式法则：

性质17 — 凸性：

  • 固定 $P(y|x)$，$I(X;Y)$ 是 $P(x)$ 的凹函数（∩） — 保证容量优化是凸问题
  • 固定 $P(x)$，$I(X;Y)$ 是 $P(y|x)$ 的凸函数（∪） — 保证率失真优化是凸问题

1.4 四个核心不等式（证明工具箱）

(1) IT 不等式

证：令 $f(r) = \ln r - (r-1)$，$f’(r) = 1/r - 1$，$f$ 在 $r=1$ 取最大值 $f(1)=0$。
变体：$\log_2 r \leq (r-1)\log_2 e$。

(2) Jensen 不等式

在信息论中的核心用法：$\log(\cdot)$ 为凹函数 → $E[\log X] \leq \log E[X]$。这是证明 $D(P|Q) \geq 0$ 和 $H(X) \leq \log|\mathcal{X}|$ 的基础。

(3) 数据处理不等式（Data Processing Inequality）

若 $X \to Y \to Z$ 构成 Markov 链，则 $I(X;Z) \leq I(X;Y)$。

证：

其中 $I(X;Z|Y) = 0$ 由 Markov 性 $X \to Y \to Z$ 保证。

推论：$I(X; g(Y)) \leq I(X; Y)$——对数据的任何后处理都不会增加信息量。这指导了现代通信系统采用软判决而非硬判决的设计。

(4) Fano 不等式

其中 $P_e = \Pr(\hat{X} \neq X)$。

证：定义错误指示变量 $E = 1_{ {\hat{X} \neq X} }$。

弱化版（更常用）：$H(X|Y) \leq 1 + P_e \log|\mathcal{X}|$，或 $P_e \geq \frac{H(X|Y) - 1}{\log|\mathcal{X}|}$。

Fano 不等式在逆定理中的应用模式（贯穿全书）：

然后用链式法则展开 $I(M; Y^n)$，逐步单字母化。

(5) 熵功率不等式（EPI）

标量 EPI：若 $X \perp Z$，则 $2^{2h(X+Z)} \geq 2^{2h(X)} + 2^{2h(Z)}$。等号当 $X,Z$ 为高斯且方差成比例。

向量 EPI：$2^{\frac{2}{n}h(X^n+Z^n)} \geq 2^{\frac{2}{n}h(X^n)} + 2^{\frac{2}{n}h(Z^n)}$。

条件 EPI（用于高斯 BC 逆定理）：

1.5 典型序列与 AEP

弱典型（熵-典型）序列

由弱大数定律（WLLN）应用于 $\log\frac{1}{P(X_i)}$（期望为 $H(X)$），得 AEP：

典型集：$T_\varepsilon^{(n)} = {x^n : \left|-\frac{1}{n}\log P(x^n) - H(X)\right| \leq \varepsilon }$

典型集的三个核心性质

性质 数学表达
(a) 近似等概 $2^{-n[H(X)+\varepsilon]} \leq P(x^n) \leq 2^{-n[H(X)-\varepsilon]}$
(b) 高概率 $P(X^n \in T_\varepsilon^{(n)}) \to 1$（$n \to \infty$）
(c) 数量极少 $(1-\varepsilon)2^{n[H(X)-\varepsilon]} \leq \vert T_\varepsilon^{(n)}\vert \leq 2^{n[H(X)+\varepsilon]}$

核心洞察：总共 $|\mathcal{X}|^n$ 种序列中，典型集大小仅约 $2^{nH(X)}$——数量极少但概率几乎为 1。

联合典型与联合 AEP

联合典型集：$(x^n, y^n)$ 同时满足 $x^n$ 关于 $X$ 典型、$y^n$ 关于 $Y$ 典型、$(x^n,y^n)$ 关于 $(X,Y)$ 联合典型。

定理 1.2.1（联合 AEP）：$(X^n, Y^n)$ i.i.d. 从 $P(x,y)$ 抽取时，

  1. $P((X^n, Y^n) \in T_\varepsilon^{(n)}) \to 1$
  2. $|T_\varepsilon^{(n)}| \leq 2^{n[H(X,Y)+\varepsilon]}$

定理 1.2.2（独立抽取的联合典型概率）：
若 $\tilde{X}^n$ 与 $\tilde{Y}^n$ 分别独立地从 $P(x)$ 和 $P(y)$ 抽取，则

证：

这是信道编码定理证明中最关键的界。含义：两个独立产生的序列”碰巧联合典型”的概率以 $I(X;Y)$ 的指数衰减。

强典型序列

要求每种符号的经验频率都接近真实概率（仅适用于离散变量）：

对比 弱典型 强典型
条件 $-\frac{1}{n}\log P(x^n) \approx H(X)$ 每种符号频率 $\approx$ 真实概率
适用范围 离散 + 连续 仅离散
互相关系 强典型 ⇒ 弱典型 弱典型 ⇏ 强典型

1.6 信源编码

无损信源编码定理

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

Kraft 不等式（前缀码的充要条件）

其中 $D$ 为编码字母表大小，$l_i$ 为第 $i$ 个码字长度。满前缀码以等式满足。

最优码长

理论最优：，期望码长 。

前缀信源编码定理

编码 构造方法 特点
Shannon 码 $l_i = \lceil -\log_D P_i \rceil$ 在 1 比特内达到最优
Huffman 码 贪心合并最小概率符号 单符号级别最优前缀码

1.7 信道容量

DMC 定义

无记忆性：$P(\mathbf{y}|\mathbf{x}) = \prod_{i=1}^{n} P(y_i|x_i)$。

容量的双重定义

概念 定义
信息容量 $C = \max_{P(X)} I(X;Y)$
操作容量 所有可达速率的上确界
可达速率 $R$ 存在 $(2^{nR}, n)$ 码使 $P_e^{(n)} \to 0$

噪声信道编码定理

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

可达性证明框架（随机编码 + 联合典型译码）

  1. 随机码本生成：固定 $P(x)$，独立生成 $2^{nR}$ 个码字 $\sim \prod P(x_i)$
  2. 编码：发送消息 $w$ 对应的 $X^n(w)$
  3. 联合典型译码：收到 $Y^n$，找唯一 $\hat{w}$ 使 $(X^n(\hat{w}), Y^n) \in T_\varepsilon^{(n)}$
  4. 错误分析（发送 $w=1$）：
  • $E_1$：正确码字不典型 → AEP → $\to 0$
  • $E_w$（$w \neq 1$）：错误码字碰巧与 $Y^n$ 联合典型
  1. 结论：平均错误概率 → 0，存在好码。对 $P(x)$ 取 max 得 $C$。

逆定理框架（Fano + 链式法则——通用模板）

典型信道的容量公式

BSC（二元对称信道，交叉概率 $\varepsilon$）：

最优输入：等概 $P(0)=P(1)=1/2$。

BEC（二元擦除信道，擦除概率 $\alpha$）：

推导：

反馈容量

对于 DMC，反馈不增加容量：$C{FB} = C = \max{P(x)} I(X;Y)$。

高斯信道

推导：

最优输入：$X \sim \mathcal{N}(0, P)$。

Shannon-Hartley 定理（限带 AWGN）：$C = W\log_2(1 + \text{SNR})$ bits/s。

信源-信道分离定理

可靠通信可做到当且仅当 $H(V) < C$。信源编码与信道编码可以分开独立设计。

1.8 MIMO 信道

系统模型

功率约束：$E[|\mathbf{x}|^2] = \text{tr}(\mathbf{K}_x) \leq P$，其中 $\mathbf{K}_x = E[\mathbf{x}\mathbf{x}^H]$。

SVD 分解——将 MIMO 化为并行标量信道

  • $\boldsymbol{\Lambda}$：非负实对角矩阵（奇异值 $\sqrt{\lambda_i}$）
  • $\mathbf{U}, \mathbf{V}$：酉矩阵

等效变换：$\tilde{\mathbf{y}} = \boldsymbol{\Lambda}\tilde{\mathbf{x}} + \tilde{\mathbf{n}}$，展开为 $m = \min(M,N)$ 个并行子信道：

MIMO 容量一般表达式

利用 $\det(\mathbf{I}_m + \mathbf{A}\mathbf{B}) = \det(\mathbf{I}_n + \mathbf{B}\mathbf{A})$ 可得等价形式。

注水算法（发射端已知信道 CSIT）

将 SVD 代入容量公式，得功率分配问题：

最优解——注水功率分配：

注水容量：

条件 策略
CSIT + CSIR 注水功率分配
无 CSIT（ZMSW 信道） 等功率分配 $\mathbf{K}_x = \frac{P}{N}\mathbf{I}_N$

1.9 第一章核心公式速查

名称 公式
熵 $H(X) = -\sum_x P(x)\log P(x)$
联合熵链式法则
微分熵 $h(X) = -\int f(x)\log f(x)dx$
最大微分熵（标量） $h(X) \leq \frac{1}{2}\log(2\pi e\sigma^2)$
最大微分熵（向量） $h(\mathbf{X}) \leq \frac{1}{2}\log[(2\pi e)^n\vert K\vert]$
KL 散度
互信息
互信息链式法则
IT 不等式 $\ln r \leq r - 1$
Jensen $E[f(X)] \geq f(E[X])$（$f$ 凹）
数据处理不等式 $X \to Y \to Z \implies I(X;Z) \leq I(X;Y)$
Fano 不等式 $H(P_e) + P_e\log(\vert \mathcal{X}\vert-1) \geq H(X\vert Y)$
AEP $-\frac{1}{n}\log P(X^n) \to H(X)$
联合典型概率界 $P((\tilde{x}^n,\tilde{y}^n) \in T_\varepsilon) \leq 2^{-n[I(X;Y)-3\varepsilon]}$
Kraft 不等式 $\sum_i D^{-l_i} \leq 1$
BSC 容量 $C = 1 - H_2(\varepsilon)$
BEC 容量 $C = 1 - \alpha$
高斯信道容量 $C = \frac{1}{2}\log(1 + \text{SNR})$
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)$
注水功率分配 $P_i = (\mu - N_0/\lambda_i)^+$

第二章 多址接入信道（MAC）

2.1 系统模型与核心特征

关键特征：发端独立（$X_1 \perp X_2$，不可协作编码）、收端合作（联合译码）。

2.2 MAC 容量定理

定理 2.2.1：容量区域 = 所有满足以下条件的 $(R_1, R_2)$ 的凸壳的闭包：

其中 $P(x_1, x_2) = P(x_1)P(x_2)$。

容量区域形状（五边形）

1
2
3
4
5
6
7
8
9
10
11
12
R₂
^
| A(0, I(X₂;Y))
|  |＼
|  |   ＼  B(I(X₁;Y), I(X₂;Y|X₁))
|  |      ＼
|  |  C(I(X₁;Y|X₂), I(X₂;Y))
|  |       ／
|  |    ／
|  | ／
|  D(I(X₁;Y), 0)
+-----------------------> R₁
  • 上边界 $R_1+R_2 = I(X_1,X_2;Y)$（和速率上界）
  • 角点 B/D 用 SIC 可达，非角点用时间共享

2.3 可达性证明——同时译码 + 四类错误事件分析

编码：固定 $P(x_1)P(x_2)$，独立生成 $2^{nR_1}$ 个 $X_1^n(i)$ 和 $2^{nR_2}$ 个 $X_2^n(j)$。

同时译码规则：找唯一的 $(i,j)$ 使 。

错误概率（假设发送 $(1,1)$）：

四类错误的详细分析

① $E_{1,1}^c$（正确码字对不典型）：由联合 AEP，$\to 0$，无条件。

② $E_{i,1}$ ($i \neq 1$)（用户1错，用户2对）：

$X_1^n(i)$ 独立于 $(X_2^n(1), Y^n)$（后者从联合分布抽取）。

关键恒等式：

最后一步因 $X_1 \perp X_2$，$I(X_1;X_2)=0$。

③ $E_{1,j}$ ($j \neq 1$)（用户1对，用户2错）：对称地

④ $E_{i,j}$ ($i,j \neq 1$)（两用户都错）：

$X_1^n(i), X_2^n(j), Y^n$ 三者相互独立。

关键恒等式（利用 $X_1 \perp X_2$ 故 $H(X_1)+H(X_2) = H(X_1,X_2)$）：

总错误概率上界

当三个不等式满足时，$P_e^{(n)} \to 0$。平均错误概率可任意小 → 存在好码。

2.4 时间共享与凸壳

由于 $R_p$ 区域（对特定 $P(x_1)P(x_2)$）不一定凸，需取凸壳。引入时间共享变量 $Q$：

凸壳形式：

$|\mathcal{Q}| \leq 2$（Carathéodory 定理在二维的推论）。

2.5 逐次干扰消除（SIC）译码

达到角点 B $(I(X_1;Y), I(X_2;Y|X_1))$ 的步骤：

方法 特点
同时译码 一步找联合典型码字对
SIC + 时间共享 可达到整个容量区域

对 DM-MAC，同时译码不比 SIC + 时间共享更好。

2.6 高斯 MAC 容量区域

其中 $C(x) = \frac{1}{2}\log(1+x)$。无需时间共享——单个 $R(X_1,X_2)$ 即为凸。

$R_1$ 约束推导：

2.7 速率分裂（Rate-Splitting）

将用户1分裂为 ，。

译码顺序：

即 ——通过调整 在容量边界上滑动。

2.8 第二章核心公式速查

名称 公式
MAC 容量区域 $R_1 < I(X_1;Y\vert X_2),\; R_2 < I(X_2;Y\vert X_1),\; R_1+R_2 < I(X_1,X_2;Y)$
MAC 容量（凸壳形式） 同上，条件于 $Q$（$\vert Q\vert \leq 2$）
高斯 MAC 容量 $R_j \leq C(P_j/\sigma^2),\; R_1+R_2 \leq C((P_1+P_2)/\sigma^2)$
$E_{i,j}$ 错误概率界 $P(E_{i,j}) \leq 2^{-n[I(X_1,X_2;Y)-2\varepsilon]}$
$E_{i,1}$ 错误概率界 $P(E_{i,1}) \leq 2^{-n[I(X_1;Y\vert X_2)-3\varepsilon]}$

第三章 广播信道（BC）

3.1 系统模型

BC 的容量区域在一般情况下未知。已知最佳内界：Marton (1979)；最佳外界：Nair-El Gamal (2007)。

3.2 叠加编码内界（Cover 1972）

核心思想：云中心 $U$（对两用户均可见） + 卫星码字 $X$（仅好用户可分辨）。

定理：$(R_1, R_2)$ 可达，若存在 $p(u,x)$ 满足：

3.3 退化 BC 容量定理

退化定义：$X \to Y_1 \to Y_2$（$Y_2$ 是 $Y_1$ 的物理/随机退化版）。

定理（Cover 1972, Bergmans 1973, Gallager 1974）：

其中 $|\mathcal{U}| \leq \min{|\mathcal{X}|, |\mathcal{Y}_1|, |\mathcal{Y}_2|} + 1$。

Gallager 逆定理证明（考试核心）

关键技巧：识别辅助变量 $U_i = (M_2, Y_1^{i-1})$

约束 $R_1$ 的推导：

约束 $R_2$ 的推导（利用退化性）：

引入时间共享变量：$Q \sim \text{Unif}[1:n]$，$U = (Q, U_Q)$，得单字母表达式。

3.4 高斯 BC 容量区域与 EPI 逆定理

设 $|g_1| \geq |g_2|$（用户1信道更好），$Z_j \sim \mathcal{N}(0, N_j)$。

定理：对某个 $\alpha \in [0,1]$：

其中 $S_j = g_j^2 P/N_j$，$\bar{\alpha} = 1-\alpha$。

可达性

取 $U \sim \mathcal{N}(0, \bar{\alpha}P)$，$V \sim \mathcal{N}(0, \alpha P)$，$U \perp V$，$X = U + V$。

  • 用户2：将 $V$ 视为噪声 → $R_2 = I(U;Y_2) = C(\bar{\alpha}S_2/(\alpha S_2 + 1))$
  • 用户1：SIC——先译 $U$，消除后再译 $V$ → $R_1 = I(V;Y_1|U) = C(\alpha S_1)$

逆定理（EPI 的应用）概要

  1. 由 Fano：$nR_2 \leq I(M_2; Y_2^n)$
  2. $I(M_2; Y_2^n) \leq \frac{n}{2}\log(2\pi e(P+N_2)) - h(Y_2^n|M_2)$
  3. 由连续性，存在 $\alpha$ 使 $h(Y_2^n|M_2) = \frac{n}{2}\log(2\pi e(\alpha P + N_2))$
  4. 得 $R_2 \leq C(\bar{\alpha}S_2/(\alpha S_2 + 1))$
  5. 利用条件 EPI 处理 $R_1$：$2^{\frac{2}{n}h(Y_2^n|M_2)} \geq 2^{\frac{2}{n}h(Y_1^n|M_2)} + 2\pi e(N_2-N_1)$
  6. 导出 $R_1 \leq C(\alpha S_1)$

3.5 Less Noisy 与 More Capable BC

条件 定义 关系
Less Noisy $I(U;Y_1) \geq I(U;Y_2)$ 对所有 $p(u,x)$ 退化 ⇒ Less Noisy ⇒ More Capable
More Capable $I(X;Y_1) \geq I(X;Y_2)$ 对所有 $p(x)$ 容量区域已知（SC + 和速率约束）

3.6 Marton 编码方案

对于非退化的一般 BC，在叠加编码基础上引入binning（分箱）。

核心问题

如何从独立消息 $M_1, M_2$ 生成相关的 $U_1^n, U_2^n$？答案：分箱 + 联合典型匹配。

码本构造

  • 随机独立生成 $2^{n(R_1+r_1)}$ 个 $U_1^n$ 和 $2^{n(R_2+r_2)}$ 个 $U_2^n$
  • 分为 $2^{nR_1}$ 和 $2^{nR_2}$ 个箱
  • 编码：在箱 $\mathcal{B}_1(m_1) \times \mathcal{B}_2(m_2)$ 中找联合典型的 $(U_1^n, U_2^n)$

箱中存在联合典型对的条件：$r_1 + r_2 \geq I(U_1; U_2)$（Mutual Covering Lemma）

Marton 内界定理

通过 Fourier-Motzkin 消元：译 $U_1$ 需 $R_1+r_1 \leq I(U_1;Y_1)$，译 $U_2$ 需 $R_2+r_2 \leq I(U_2;Y_2)$，联合典型存在需 $r_1+r_2 \geq I(U_1;U_2)$。

3.7 Gelfand-Pinsker 问题与污纸编码（DPC）

问题设定

GP 定理

可达性——Binning 编码

  1. 码本生成：每消息 $m$ 对应子码本 $\mathcal{C}(m)$ 含 $2^{nR’}$ 个 $U^n$（$\tilde{R} = R+R’$）
  2. 编码：给定 $(m, S^n)$，在 $\mathcal{C}(m)$ 中找与 $S^n$ 联合典型的 $U^n$，发 $X^n = f(U^n, S^n)$
    • 条件：$R’ \geq I(U;S)$（Covering Lemma）
  3. 译码：找唯一 $(\hat{m},\hat{\ell})$ 使 $(U^n, Y^n) \in T_\varepsilon^{(n)}$
    • 条件：$R+R’ \leq I(U;Y)$（Packing Lemma）
  4. 联合：$R \leq I(U;Y) - I(U;S)$

DPC 推导（Costa 1983）——核心考点

取 $U = X + \alpha S$（$X \perp S$）：

对 $\alpha$ 求导，得最优值：

代入得： —— 完美抵消状态影响，达到无状态容量！

DPC 的 MMSE 理解（更直观）

当 $\alpha = \alpha^*$ 时：

$\alpha^* = \frac{P}{P+1}$ 正是 $X$ 关于 $Y=X+Z$ 的 L-MMSE 估计系数：

状态信息情景 AWGN 容量
收发均不知 $S$ $C(P/(1+Q))$（状态视为噪声）
仅译码端知 $S$ $C(P)$（直接减去 $S$）
仅编码端知 $S$（DPC） $C(P)$（完美抵消）

3.8 第三章核心公式速查

名称 公式
叠加编码内界 $R_1 \leq I(X;Y_1\vert U),\; R_2 \leq I(U;Y_2),\; R_1+R_2 \leq I(X;Y_1)$
退化 BC 容量 $R_1 \leq I(X;Y_1\vert U),\; R_2 \leq I(U;Y_2)$
高斯 BC 容量 $R_1 \leq C(\alpha S_1),\; R_2 \leq C(\bar{\alpha}S_2/(\alpha S_2+1))$
Marton 内界 $R_j \leq I(U_j;Y_j),\; R_1+R_2 \leq I(U_1;Y_1)+I(U_2;Y_2)-I(U_1;U_2)$
GP 容量 $C^{\text{SI-E}} = \max[I(U;Y) - I(U;S)]$
DPC 最优参数 $\alpha^* = P/(P+1)$，容量 $= C(P)$

第四章 相关信源的编码

4.1 Slepian-Wolf 定理

模型

两个编码器不通信，但联合译码器需要同时恢复 $U^n$ 和 $V^n$。

定理

核心发现（Slepian-Wolf 奇迹）：即使编码器不通信，和速率 $H(U,V)$ 仍然可达——与两编码器能协作时完全一样！

逆定理证明

证 $R_1 \geq H(U|V)$：

证 $R_1+R_2 \geq H(U,V)$：

可达性——随机 Binning + 联合典型译码（四类错误）

对每个 $u^n$ 随机分配 bin $m_1 \in [1:2^{nR_1}]$，对每个 $v^n$ 随机分配 bin $m_2 \in [1:2^{nR_2}]$。

译码：在 $\mathcal{B}_1(m_1) \times \mathcal{B}_2(m_2)$ 中找唯一的联合典型对。

事件 定义 概率 → 0 的条件
$E_1$ $(U^n,V^n)$ 不典型 无条件（LLN）
$E_2$ $\exists \tilde{u}^n \neq U^n \in \mathcal{B}_1(m_1)$ 与 $V^n$ 联合典型 $R_1 > H(U\vert V)$
$E_3$ $\exists \tilde{v}^n \neq V^n \in \mathcal{B}_2(m_2)$ 与 $U^n$ 联合典型 $R_2 > H(V\vert U)$
$E_4$ 两者都错但联合典型 $R_1+R_2 > H(U,V)$

$E_2$ 的定量分析：

$k$ 源扩展

4.2 有 Helper 的无损压缩（Ahlswede-Körner-Wyner）

定理：

对某个 $p(u|y)$，$|\mathcal{U}| \leq |\mathcal{Y}| + 1$，Markov 链 $U \to Y \to X$。

4.3 率失真理论

有损信源编码定理（Shannon 1959）

Bernoulli 信源 + Hamming 失真：$R(D) = \max{H_2(p) - H_2(D), 0}$

高斯信源 + 平方误差：$R(D) = \frac{1}{2}\log^+(P/D)$

逆定理概要

最后一步用 $R(D)$ 的凸性。

4.4 Wyner-Ziv 定理

模型

定理

可达性——Compress-Bin 方案（三步法）

码本生成：生成 $2^{n\tilde{R}}$ 个 $U^n(l)$，均分为 $2^{nR}$ 个 bin。

编码：找 $l$ 使 $(X^n, U^n(l)) \in T_{\varepsilon’}^{(n)}$，发送 bin 索引 $m$。

  • $\tilde{R} > I(X;U)$（Covering——码本够大以覆盖 $X^n$）

译码：在 $\mathcal{B}(m)$ 中找唯一 $\hat{l}$ 使 $(U^n(\hat{l}), Y^n) \in T_\varepsilon^{(n)}$。

  • $\tilde{R} - R < I(Y;U)$（Packing——每 bin 够小以避免混淆）

联合：$R > I(X;U) - I(Y;U) = I(X;U|Y)$

Wyner-Ziv 与 Gelfand-Pinsker 的对偶

维度 Wyner-Ziv（信源编码） Gelfand-Pinsker（信道编码）
公式 $\min[I(X;U) - I(Y;U)]$ $\max[I(U;Y) - I(U;S)]$
优化 最小化 最大化
编码工具 Covering Binning（匹配状态）
译码工具 Packing 联合典型译码

4.5 第四章核心公式速查

名称 公式
Slepian-Wolf 区域 $R_1 \geq H(U\vert V),\; R_2 \geq H(V\vert U),\; R_1+R_2 \geq H(U,V)$
$k$-源 Slepian-Wolf $\sum_{j \in S} R_j \geq H(\mathbf{X}(S) \vert \mathbf{X}(S^c))$
Ahlswede-Körner-Wyner $R_1 \geq H(X\vert U),\; R_2 \geq I(Y;U)$，$U \to Y \to X$
率失真函数 $R(D) = \min_{p(\hat{x}\vert x): E[d] \leq D} I(X;\hat{X})$
Bernoulli + Hamming $R(D) = \max{H_2(p) - H_2(D), 0}$
高斯 + 平方误差 $R(D) = \frac{1}{2}\log^+(P/D)$
Wyner-Ziv $R^{\text{SI-D}} = \min[I(X;U) - I(Y;U)] = \min I(X;U\vert Y)$

第五章 中继信道（Relay Channels）

5.1 系统模型

中继信道容量在一般情况下未知。

5.2 割集上界

定理（Cover-El Gamal 1979）：

两个割的物理含义

割1的逆定理证明

关键 Markov 性：（由信道无记忆保证）。

5.3 直接传输下界

中继不扮演主动角色（$X_2$ 固定或独立）。对反向退化 RC 是紧的。

5.4 多跳下界

可达性——分组 Markov 编码：$b$ 个传输块发送 $b-1$ 个消息，中继在块 $j$ 中转发块 $j-1$ 中译出的消息。

1
2
消息:  m₁    m₂    m₃   ...  m_{b-1}   1
块:    1     2     3    ...   b-1      b

5.5 协作多跳下界

源和中继通过条件码本 实现相干协作。

5.6 译码转发（DF）

定理（Cover-El Gamal 1979）：

项 物理含义
$I(X_1; Y_2\vert X_2)$ 中继译码条件——中继能可靠译出源消息的速率
$I(X_1, X_2; Y_3)$ 目的译码条件——源+中继协作时目的的可靠速率

可达性——后向译码（Backward Decoding）

  • 中继译码（前向）：块 $j$ 结束后，找 $\tilde{m}_j$ 满足联合典型条件 → $R < I(X_1; Y_2|X_2)$
  • 目的译码（后向）：从块 $b$ 往前，已译出 后，利用 译

紧条件

对物理退化 RC（$X_1 \to (Y_2, X_2) \to Y_3$），DF 下界 = 割集上界，容量已知。

DF 的局限

当中继比目的节点弱时（$I(X_1;Y_2|X_2) < I(X_1;Y_3|X_2=x_2)$），DF 甚至不如直接传输。

解决：部分 DF（只译码部分消息）或压缩转发（不译码，只量化转发）。

5.7 部分译码转发

将 $M = (M’, M’’)$：$M’$ 由中继译码并协作转发，$M’’$ 直接传输。

紧于半确定 RC 和正交发送分量 RC。

5.8 压缩转发（CF）

中继不译码——而是将 $Y_2$ 量化/压缩后转发（利用 Wyner-Ziv 编码）。

定理（El Gamal-Mohseni-Zahedi 2006）：

项 物理含义
$I(X_1; \hat{Y}_2, Y_3\vert X_2)$ 源到”增强目的”的速率
$I(Y_2; \hat{Y}_2\vert X_1,X_2,Y_3)$ 压缩代价（Wyner-Ziv 速率损失）

策略选择指南

1
2
3
4
中继比目的强？
  ├── 是 → DF 或部分 DF
  └── 否 → CF（压缩转发）
            └── 中继极弱 → 直接传输

5.9 第五章核心公式

名称 公式
割集上界 $C \leq \max \min{I(X_1,X_2;Y_3),\; I(X_1;Y_2,Y_3\vert X_2)}$
直接传输下界 $C \geq \max I(X_1; Y_3 \vert X_2)$
多跳下界 $C \geq \max \min{I(X_1;Y_2),\; I(X_2;Y_3\vert X_1)}$
协作多跳下界 $C \geq \max \min{I(X_2;Y_3),\; I(X_1;Y_2\vert X_2)}$
DF 下界 $C \geq \max \min{I(X_1,X_2;Y_3),\; I(X_1;Y_2\vert X_2)}$
部分 DF 下界 $C \geq \max \min{I(X_1,X_2;Y_3),\; I(U;Y_2\vert X_2)+I(X_1;Y_3\vert X_2,U)}$
CF 下界 $C \geq \max \min{I(X_1,X_2;Y_3)-I(Y_2;\hat{Y}_2\vert X_1,X_2,Y_3),\; I(X_1;\hat{Y}_2,Y_3\vert X_2)}$

第六章 干扰信道（IC）

6.1 系统模型

IC 的容量区域在一般情况下未知。

6.2 三种点对点编码策略

所有策略使用相同的随机码本（独立生成 $X_1^n, X_2^n$，带时间共享 $Q$）。

(1) 将干扰视为噪声（IAN）

译码器忽略另一个用户的码字，只译自己的消息。适用于弱干扰。

(2) 同时译码（SD）

每个译码器试图同时译出两个消息。适用于强干扰。

(3) 同时非唯一译码（SND）

译码器 1 只需唯一确定 $\hat{m}_1$，允许 $m_2$ 不唯一确定（只要求存在某个 $m_2$ 使联合典型条件成立）。

SND 恒包含 SD 区域——因 SD 额外要求 $R_2 < I(X_2;Y_1|X_1,Q)$。

6.3 强干扰与极强干扰

定义对比

条件 定义 物理含义
极强干扰 $I(X_1;Y_1\vert X_2) \leq I(X_1;Y_2)$ 且对称（对所有 $p(x_1)p(x_2)$） 干扰链路比期望链路更好
强干扰 $I(X_1;Y_1\vert X_2) \leq I(X_1;Y_2\vert X_2)$ 且对称 已知自己输入时，干扰链路提供更多信息

极强 ⇒ 强，逆一般不成立。

强干扰容量区域（Costa-El Gamal 1987）

$\vert \mathcal{Q}\vert \leq 4$。可达性：SND，强干扰条件下 SD 的额外约束自动满足。逆定理：利用 $I(X_1^n;Y_1^n|X_2^n) \leq I(X_1^n;Y_2^n|X_2^n)$（强干扰条件对任意 $n$ 成立）。

极强干扰容量区域

$\vert \mathcal{Q}\vert \leq 2$。无和速率约束——干扰完全不损害通信。可达方法：SC 译码（先译干扰、消除后再译自己的消息）。

高斯 IC 的 SNR/INR 判据（Sato 1981）

条件 SNR/INR 条件 容量
强干扰 $I_2 \geq S_1$ 且 $I_1 \geq S_2$ SND 区域
极强干扰 $S_2 \leq I_1/(1+S_1)$ 且 $S_1 \leq I_2/(1+S_2)$ $R_j < C(S_j)$（无干扰容量）

6.4 Han-Kobayashi 编码方案

速率分裂思想

消息 译码器1 译码器2
$M_{10}$（用户1公共） 译码 译码
$M_{11}$（用户1私密） 译码 视为噪声
$M_{20}$（用户2公共） 译码 译码
$M_{22}$（用户2私密） 视为噪声 译码

H-K 内界定理（7个不等式）

$(R_1, R_2)$ 可达，若存在 $p(q)p(u_1,x_1|q)p(u_2,x_2|q)$ 满足：

$\vert \mathcal{U}_1\vert \leq \vert \mathcal{X}_1\vert +4$，$\vert \mathcal{U}_2\vert \leq \vert \mathcal{X}_2\vert +4$，$\vert \mathcal{Q}\vert \leq 7$。

7 个不等式来源于对 4 个中间速率变量 的 Fourier-Motzkin 消元。

译码器1错误分析表（8种情形）

情形 $m_{10}$ $m_{20}$ $m_{11}$ 联合分布 Packing 条件
1 ✓ ✓ ✓ $p(u_1,x_1)p(u_2)p(y_1\vert x_1,u_2)$ 参考（正确）
2 ✓ ✗ ✓ $p(u_1,x_1)p(u_2)p(y_1\vert u_1,u_2)$ $R_{20} < I(U_2;Y_1\vert U_1,X_1)$
3 ✗ ✓ ✗ $p(u_1,x_1)p(u_2)p(y_1\vert u_2)$
4 ✗ ✓ ✓ 同情形3 同情形3
5 ✓ ✗ ✗ $p(u_1,x_1)p(u_2)p(y_1\vert u_1)$
6 ✗ ✗ ✓ $p(u_1,x_1)p(u_2)p(y_1)$
7 ✗ ✗ ✗ 同情形6 同情形6
8 ✓ ✗ ✓ $p(u_1,x_1)p(u_2)p(y_1\vert x_1)$ 不造成错误

6.5 高斯 IC 的半比特定理（Etkin-Tse-Wang 2008）

若 $(R_1, R_2)$ 属于高斯 IC 的外界 $\mathcal{R}_o$，则

H-K 内界距离容量区域至多 1/2 bit/维。

证明关键

将高斯 IC 表示为注入式半确定性 IC：

需要证明 。取 ：

方差至多 2 → $h(T_j-U_j) - h(Z_j) \leq \frac{1}{2}\log 2 = \frac{1}{2}$

6.6 第六章核心公式

名称 公式
IAN 内界 $R_j < I(X_j; Y_j \vert Q)$
SND 内界 $R_j < I(X_j; Y_j \vert X_k, Q),\; R_1+R_2 < \min{I(X_1,X_2;Y_1\vert Q), I(X_1,X_2;Y_2\vert Q)}$
强干扰容量 SND 区域（$\vert \mathcal{Q}\vert \leq 4$）
极强干扰容量 $R_j < I(X_j; Y_j \vert X_k, Q)$（$\vert \mathcal{Q}\vert \leq 2$），无和速率约束
H-K 内界 7 个不等式（Fourier-Motzkin 消元结果）
高斯 IAN $R_j < C(S_j/(1+I_j))$
半比特定理

附录

A.1 不等式缩放

技巧 使用场景
Union Bound 总错误概率 ≤ 各错误事件概率之和
Jensen 的证明
Fano 不等式 逆定理的起点：$nR \leq I(M;Y^n) + n\epsilon_n$
IT 不等式 的另一种证明方法
数据处理不等式 Markov 链中的信息降级
EPI 高斯信道的逆定理

A.2 单字母化的标准模板

1
2
3
4
5
6
1. Fano: nR ≤ I(M; Y^n) + nε_n
2. 链式展开: = Σ_i I(M; Y_i | Y^{i-1})
3. 识别辅助变量: U_i = (M, Y^{i-1}) 或变体
4. 验证 Markov 链: U_i → X_i → Y_i
5. 引入时间共享变量: Q ~ Unif[1:n]
6. 取 n→∞: R ≤ I(X; Y|U)

A.3 各章考点

考点 章节 证明核心
Ch1 Jensen 不等式
$H(X) \leq \log\vert \mathcal{X}\vert$ Ch1 KL散度非负性
数据处理不等式 Ch1 链式法则 + Markov性
Fano 不等式 Ch1 条件熵展开 + 错误事件
联合典型概率界 $2^{-nI}$ Ch1 典型集大小 + 概率界
MAC 四类错误 Ch2 Union Bound + 联合典型界
退化 BC 逆定理（$U_i$ 构造） Ch3 Fano + 链式法则 + 退化性
高斯 BC 逆定理（EPI） Ch3 Fano + 条件 EPI + 连续性
DPC $\alpha^* = P/(P+1)$ Ch3 MMSE 正交性
GP 定理 $I(U;Y)-I(U;S)$ Ch3 Covering + Packing 联合
Slepian-Wolf 四类错误 Ch4 随机 Binning + 联合典型
Wyner-Ziv Compress-Bin Ch4 Covering + Packing + FM 消元
割集上界（两个割） Ch5 Fano + 链式法则 + Markov性
DF 后向译码 Ch5 条件码本 + $b$ 块分组 Markov
CF 压缩转发 Ch5 Wyner-Ziv + 分组 Markov
强干扰容量（SND） Ch6 SND 译码 + Packing Lemma
H-K 8 种错误情形 Ch6 联合分布推导 + Packing Lemma
半比特定理 Ch6 $I(X_j;T_j\vert U_j) \leq 1/2$

A.4 备考策略

  1. Ch1——Fano、$D(P|Q) \geq 0$、数据处理不等式、AEP、联合典型界，这些是解所有证明题的”基本语言”。

  2. 证明题：MAC 可达性（四类错误）、退化 BC 逆定理（$U_i$ 构造）、Slepian-Wolf 证明（四类错误）、割集上界——这四者最高频。

  3. DPC：$\alpha^* = P/(P+1)$ 的推导和 MMSE 正交性理解。

  4. H-K 7 不等式不需死记：理解公共/私密消息分裂逻辑和 8 种错误情形的联合分布推导即可。

  5. 高斯信道重在理解：容量公式会默写，EPI 用法理解即可。

  6. 工具链要烂熟：Fano → 链式法则 → Markov 性 → 单字母化，这条链在逆定理中反复出现。