第三章广播信道（Broadcast Channels）

课程: 网络信息论（Network Information Theory）
教材: A. El Gamal and Y.-H. Kim, Network Information Theory, Cambridge University Press, 2011
整理说明: 本章为广播信道的模型、叠加编码、退化 BC 容量区域及其逆定理证明（Gallager/Nair/EPI）、Marton 编码方案、Gelfand-Pinsker 问题与污纸编码。
免责声明：本笔记内容来源于课程讲义和PPT，经AI辅助汇总完成，仅供学习参考。如有错误或遗漏，请以原始课程资料为准。

1. 广播信道基本概念

1.1 模型描述

广播信道（Broadcast Channel, BC）是通信网络下行链路的基础模型：一个发送端，多个接收端。典型例子：电视广播、无线基站下行、卫星广播、课堂讲授。

    graph TB
    M0["M₀ (公共消息)"] --> ENC
    M1["M₁ (私有消息)"] --> ENC["编码器<br/>X<sup>n</sup>(M₀,M₁,M₂)"]
    M2["M₂ (私有消息)"] --> ENC
    ENC -->|"X<sup>n</sup>"| CH["p(y₁,y₂|x)"]
    CH -->|"Y₁<sup>n</sup>"| DEC1["译码器 1<br/>→ (M̂₀, M̂₁)"]
    CH -->|"Y₂<sup>n</sup>"| DEC2["译码器 2<br/>→ (M̂₀, M̂₂)"]

离散无记忆 BC（DM-BC）: 由 $(\mathcal{X}, p(y_1, y_2|x), \mathcal{Y}_1 \times \mathcal{Y}_2)$ 描述。

无记忆性：

$p(y_1^n, y_2^n | x^n) = \prod_{i=1}^{n} p(y_{1,i}, y_{2,i} | x_i)$

1.2 码的定义与可达性

一个 $(2^{nR_0}, 2^{nR_1}, 2^{nR_2}, n)$ 码包含：

组件	定义
编码器	$f: [2^{nR_0}] \times [2^{nR_1}] \times [2^{nR_2}] \to \mathcal{X}^n$，将三个消息嵌入一个码字
译码器 1	$g_1: \mathcal{Y}_1^n \to [2^{nR_0}] \times [2^{nR_1}]$
译码器 2	$g_2: \mathcal{Y}_2^n \to [2^{nR_0}] \times [2^{nR_2}]$

速率三元组 $(R_0, R_1, R_2)$ 可达，如果存在一列码使 $P_e^{(n)} \to 0$。
容量区域是所有可达速率三元组的闭包。

1.3 重要事实

⚠️ BC 的容量区域在一般情况下是未知的！这与 MAC（已有完整的单字母刻画）形成鲜明对比。

已知最佳内界：Marton (1979) 的内界
已知最佳外界：Nair-El Gamal (2007) 的外界
两者在若干特殊情形下重合

引理: BC 的容量区域仅通过条件边缘分布 $p(y_1|x)$ 和 $p(y_2|x)$ 依赖于 $p(y_1, y_2|x)$，而与 $Y_1$ 和 $Y_2$ 之间的相关性无关。

2. 简单界与实例

2.1 简单界

界	内容
单用户容量	$Rj \leq C_j = \max{p(x)} I(X; Y_j)$，$j = 1, 2$
和速率上界	$R1 + R_2 \leq C{12} = \max_{p(x)} I(X; Y_1, Y_2)$

    graph LR
    subgraph 简单界示意
        direction TB
        A["R₂ = C₂"]
        B["R₁+R₂ = C₁₂"]
        C["R₁ = C₁"]
    end

以坐标图表示：

R₂
^
| C₂ ●──────────┐
|    │ 可达?     │
|    │     TDMA │───┐
|    │    内界    │   外边界 = ?
|    └──────────●── C₁₂
+-----------------------> R₁
                      C₁

2.2 特殊情形

情形	说明	容量区域
仅有公共消息 $(R_1=R_2=0)$	所有人接收相同消息	$C0 = \max{p(x)} \min{I(X;Y_1), I(X;Y_2)}$
对称 BC	可设 $Y_1 = Y_2$ 求得容量区域	退化为点对点
正交分量 BC	$X = (X_1, X_2)$，$Y_1$ 仅依赖 $X_1$，$Y_2$ 仅依赖 $X_2$	容量区域为矩形 $R_1 \leq C_1, R_2 \leq C_2$

2.3 二元对称广播信道（BS-BC）实例

    graph TB
    X["X ∈ {0,1}"] --> BSC1["BSC(p₁)"]
    X --> BSC2["BSC(p₂)"]
    BSC1 --> Y1["Y₁"]
    BSC2 --> Y2["Y₂"]

假设 $p_1 < p_2 < 1/2$。时分（TDMA）内界：

R₂
^
| 1-H(p₂) ●──────────┐
|         │     TDMA  │
|         │     内界   │
|         └──────────●──
+-------------------> R₁
              1-H(p₁)

3. 叠加编码与内界

叠加编码（Superposition Coding, Cover 1972）是 BC 最基础的编码方案。

3.1 核心思想

    graph TB
    subgraph 叠加编码结构
        direction TB
        CLOUD["云中心 U<sup>n</sup>(m₂)<br/>（对两用户均可见）"]
        SAT["卫星码字 X<sup>n</sup>(m₁,m₂)<br/>（仅好用户可分辨）"]
        CLOUD --> SAT
    end

直觉: 发 $2^{nR_2}$ 个”云”（cloud centers），每个云中包含 $2^{nR_1}$ 个”卫星码字”。

用户 2（差用户）只能看到云——译 $U$ 获得 $m_2$

用户 1（好用户）既能看云又能分辨云内的卫星——先译 $U$ 再译 $X$

3.2 BS-BC 的叠加编码实现

码本生成:

$U \sim \text{Bern}(1/2)$，$V \sim \text{Bern}(\alpha)$，$U \perp V$
$X = U \oplus V$（二元异或）
独立生成 $2^{nR_2}$ 个 $U^n(m_2) \sim \prod p_U(u_i)$
独立生成 $2^{nR_1}$ 个 $V^n(m_1) \sim \prod p_V(v_i)$
发送：$X^n(m_1, m_2) = U^n(m_2) \oplus V^n(m_1)$

译码:

译码器 2: 从 $Y_2^n = U^n \oplus (V^n \oplus Z_2^n)$ 中恢复 $m_2$（$V$ 视为噪声） $R_2 \leq I(U; Y_2) = 1 - H(\alpha * p_2)$
译码器 1（逐次干扰消除）:
1. 先从 $Y_1^n$ 恢复 $m_2$：$R_2 \leq I(U; Y_1) = 1 - H(\alpha * p_1)$
2. 再从 $V^n \oplus Z_1^n$ 中恢复 $m_1$：$R_1 \leq I(V; V \oplus Z_1) = H(\alpha * p_1) - H(p_1)$

其中 $a * b = a(1-b) + (1-a)b$ 是二元卷积。

3.3 叠加编码内界定理（Cover 1972, Bergmans 1973）

定理: 速率对 $(R_1, R_2)$ 对 BC $p(y_1, y_2|x)$ 是可达的，如果存在某个联合分布 $p(u, x)$ 满足：
$\boxed{\begin{aligned} R_2 &\leq I(U; Y_2) \\\\ R_1 &\leq I(X; Y_1 | U) \\\\ R_1 + R_2 &\leq I(X; Y_1) \end{aligned}}$

可达性证明（sketch）:

步骤	内容
码本生成	独立生成 $2^{nR2}$ 个 $U^n(m_2) \sim \prod p_U$；对每个 $m_2$，条件独立生成 $2^{nR_1}$ 个 $X^n(m_1, m_2) \sim \prod p{X\vert U}$
编码	发送 $X^n(m_1, m_2)$
译码器 2	找唯一 $m2$ 使得 $(U^n(m_2), Y_2^n) \in T\epsilon^{(n)}$（packing lemma 保证 $R_2 < I(U;Y_2)$ 时 $P_e \to 0$）
译码器 1	同时非唯一译码：找唯一 $m1$ 使得 $(U^n(m_2), X^n(m_1, m_2), Y_1^n) \in T\epsilon^{(n)}$ 对某个 $m_2$ 成立

错误事件分析（假设发送 $(M_1, M_2) = (1,1)$）:

事件	条件	概率 → 0 的条件
$E_{11}$	正确码字不典型	无条件（LLN）
$E_{12}$	$m_1 \neq 1$ 错误	$R_1 < I(X;Y_1\vert U) - \delta(\epsilon)$
$E_{13}$	$m_1 \neq 1, m_2 \neq 1$ 错误	$R_1+R_2 < I(X;Y_1) - \delta(\epsilon)$

Packing Lemma: 若 $X^n(m)$ 条件独立于 $\tilde{Y}^n$ 给定 $\tilde{U}^n$，且 $\vert A\vert \leq 2^{nR}$，则当 $R < I(X;Y|U) - \delta(\epsilon)$ 时，存在某个 $m$ 使 $(\tilde{U}^n, X^n(m), \tilde{Y}^n)$ 联合典型的概率 → 0。

4. 退化广播信道

退化 BC 是一类最重要的 BC，其容量区域已被完全确定。

4.1 退化 BC 的定义

物理退化: $X \to Y_1 \to Y_2$ 构成 Markov 链，即存在一个物理级联：

$p(y_1, y_2 | x) = p(y_1 | x) p(y_2 | y_1)$

    graph LR
    X["X"] -->|"p(y₁|x)"| Y1["Y₁"]
    Y1 -->|"p(y₂|y₁)"| Y2["Y₂<br/>(更差的接收)"]

随机退化（Stochastically Degraded）: 存在一个分布 $p’(y_2 | y_1)$ 使得

$p(y_2 | x) = \sum_{y_1} p(y_1 | x) p'(y_2 | y_1)$

即 $X \to Y_1 \to \tilde{Y}_2$ 且 $\tilde{Y}_2$ 与 $Y_2$ 同分布。这对 BS-BC 尤为重要——$Y_1$ 经过另一个 BSC 即可得到 $Y_2$。

⚠️ 注意: 物理退化 ⇒ 随机退化，但反之不一定。然而容量区域仅依赖于条件边缘分布，因此两者在容量意义上等价。

4.2 退化 BC 容量定理

定理（Cover 1972, Bergmans 1973, Gallager 1974）: 退化 BC $X \to Y_1 \to Y_2$ 的容量区域是满足以下条件的所有 $(R_1, R_2)$ 的集合：
$\boxed{\begin{aligned} R_1 &\leq I(X; Y_1 | U) \\\\ R_2 &\leq I(U; Y_2) \end{aligned}}$
其中 $U$ 为辅助随机变量，$|\mathcal{U}| \leq \min{|\mathcal{X}|, |\mathcal{Y}_1|, |\mathcal{Y}_2|} + 1$。

可达性: 叠加编码（§3.3）。退化性保证 $I(U;Y_2) \leq I(U;Y_1)$，故译码器 1 也能可靠恢复 $U$（进而逐次消除）。

4.3 逆定理 —— Gallager 证明（1974）

这是 BC 容量理论中最经典的证明之一。核心是识别辅助随机变量 $U$。

通过码诱导的联合分布:

$(M_1, M_2, X^n, Y_1^n, Y_2^n) \sim 2^{-n(R_1+R_2)} p(x^n|m_1, m_2) \prod_i p(y_{1i}, y_{2i} | x_i)$

由 Fano 不等式（$\epsilon_n \to 0$）:

$nR_j = H(M_j) \leq I(M_j; Y_j^n) + n\epsilon_n, \quad j = 1, 2$

关键步骤——识别辅助变量:

$U_i = (M_2, Y_1^{i-1})$

验证 $Ui \to X_i \to (Y{1i}, Y_{2i})$ 成立（因为 $X_i = f(M_1, M_2)$ 且信道无记忆）。

约束 $R_1$:

$\begin{aligned} I(M_1; Y_1^n) &\leq I(M_1; Y_1^n | M_2) \quad (\text{因为 } M_1 \perp M_2)\\\\ &= \sum_{i=1}^{n} I(M_1; Y_{1i} | M_2, Y_1^{i-1}) \quad (\text{链式法则})\\\\ &= \sum_{i=1}^{n} I(X_i; Y_{1i} | M_2, Y_1^{i-1}) \\\\ &= \sum_{i=1}^{n} I(X_i; Y_{1i} | U_i) \end{aligned}$

第三步使用了 $Xi = f(M_1, M_2)$ 和 Markov 性 $(Y_1^{i-1}, M_1, M_2) \to X_i \to Y{1i}$。

约束 $R_2$（利用退化性 $X \to Y_1 \to Y_2$）:

$\begin{aligned} I(M_2; Y_2^n) &= \sum_{i=1}^{n} I(M_2; Y_{2i} | Y_2^{i-1}) \\\\ &\leq \sum_{i=1}^{n} I(M_2, Y_2^{i-1}; Y_{2i}) \\\\ &\leq \sum_{i=1}^{n} I(M_2, Y_1^{i-1}; Y_{2i}) \quad (\text{退化性})\\\\ &= \sum_{i=1}^{n} I(U_i; Y_{2i}) \end{aligned}$

引入时间共享变量: $Q \sim \text{Unif}[1:n]$，$Q \perp (M1, M_2, X^n, Y_1^n, Y_2^n)$。令 $U = (Q, U_Q)$，$X = X_Q$，$Y_1 = Y{1Q}$，$Y2 = Y{2Q}$。则：

$nR_1 \leq n I(X; Y_1 | U) + n\epsilon_n, \quad nR_2 \leq n I(U; Y_2) + n\epsilon_n$

两边除以 $n$，令 $n \to \infty$，即得定理的逆方向。

4.4 逆定理 —— Nair (2013) 的替代证明

Nair 提出了一个更简洁的逆定理证明，使用支撑超平面方法。

核心定理: 闭凸集 $\mathcal{C} \subset \mathbb{R}^n$ 由其支撑函数唯一确定：

$S_{\mathcal{C}}(y) = \sup\{y^T x : x \in \mathcal{C}\}, \quad \forall y \in \mathbb{R}^n$

对于退化 BC 的容量区域 $\mathcal{D}$，对 $\lambda > 0$：

$\sup_{(R_1, R_2) \in \mathcal{D}} (R_1 + \lambda R_2) = \sup_{p(u,x)} \left[I(X; Y_1 | U) + \lambda I(U; Y_2)\right]$

通过代数展开并利用 Csiszár 和恒等式，可完成逆定理证明（细节见 slides pp.24-27）。

📐 Csiszár Sum Identity (1978): 对于 $(U, Y^n, Z^n)$，
$\sum_{i=1}^{n} I(Z_{i+1}^n; Y_i | Y^{i-1}, U) = \sum_{i=1}^{n} I(Y^{i-1}; Z_i | Z_{i+1}^n, U)$
这是信息论中处理”过去-未来”对称性的核心工具，广泛应用于多用户信道的逆定理证明。

4.5 BS-BC 退化情形的容量区域

对于 $p_1 < p_2 < 1/2$ 的 BS-BC，其容量区域是所有满足以下条件的 $(R_1, R_2)$ 的并集（$\alpha \in [0, 1]$）:

$R_1 \leq H(\alpha * p_1) - H(p_1), \quad R_2 \leq 1 - H(\alpha * p_2)$

参数 $\alpha$ 的物理意义: $X = U \oplus V$，$U \sim \text{Bern}(1/2)$，$V \sim \text{Bern}(\alpha)$。$\alpha$ 控制着两层信号之间的功率（或信息）分配。

$\alpha \to 0$: $V$ 几乎为常数 0，$X \approx U$ → 几乎全传 $R_2$，$R_1 \to 0$
$\alpha = 1/2$: $U$ 和 $V$ 独立等概，$X$ 为两者之和 → 中间权衡
$\alpha \to 1$: $V$ 几乎等概 → 侧重传 $R_1$

5. 高斯广播信道

5.1 模型

高斯 BC 是连续值 BC 的最重要实例：

$Y_1 = g_1 X + Z_1, \quad Y_2 = g_2 X + Z_2$

$Z_1 \sim \mathcal{N}(0, N_1)$，$Z_2 \sim \mathcal{N}(0, N_2)$
功率约束：$\frac{1}{n} \sum_i x_i^2(m_1, m_2) \leq P$
不失一般性设 $|g_1| \geq |g_2|$（用户 1 比用户 2 的信道更好）

等效物理退化模型: 由于 $|g_1| \geq |g_2|$，高斯 BC 天然是退化的：

    graph LR
    X["X"] --> Y1["Y₁ = X + Z₁<br/>N₁ = 1/g₁²"]
    Y1 -->|"+Z̃₂<br/>N₂-N₁"| Y2["Y₂ = X + Z₂<br/>N₂ = 1/g₂²"]

其中 $Z_1 \sim \mathcal{N}(0, N_1)$，$\tilde{Z}_2 \sim \mathcal{N}(0, N_2 - N_1)$（$N_2 \geq N_1$）。

5.2 高斯 BC 容量区域

定理（Cover 1972, Bergmans 1974）: 高斯 BC 的容量区域是满足以下条件的所有 $(R_1, R_2)$ 的集合（对某个 $\alpha \in [0, 1]$）：
$\boxed{\begin{aligned} R_1 &\leq C(\alpha S_1) = \frac{1}{2}\log\left(1 + \alpha \cdot \frac{g_1^2 P}{N_1}\right) \\\\[4pt] R_2 &\leq C\!\left(\frac{\bar{\alpha} S_2}{\alpha S_2 + 1}\right) = \frac{1}{2}\log\left(1 + \frac{(1-\alpha)g_2^2 P}{\alpha g_2^2 P + N_2}\right) \end{aligned}}$
其中 $S_j = g_j^2 P/N_j$（接收 SNR），$C(x) = \frac{1}{2}\log_2(1+x)$，$\bar{\alpha} = 1 - \alpha$。

5.3 可达性

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

发送 $X^n(m_1, m_2) = V^n(m_1) + U^n(m_2)$
用户 2: $Y_2 = V + U + Z_2$，将 $V$ 视为噪声： $R_2 = I(U; Y_2) = C\!\left(\frac{\bar{\alpha}P}{\alpha P + N_2}\right) = C\!\left(\frac{\bar{\alpha}S_2}{\alpha S_2 + 1}\right)$
用户 1: $Y_1 = V + U + Z_1$，先用 SIC 译 $U$（恢复 $m_2$），消除后再译 $V$（恢复 $m_1$）： $R_1 = I(V; Y_1 | U) = I(V; V + Z_1) = C(\alpha S_1)$

5.4 逆定理（Bergmans 1974）

逆定理依赖于 熵功率不等式（EPI）：

向量 EPI（Shannon 1948, Stam 1959, Blachman 1965）:
若 $X^n \perp Z^n$ 且 $Y^n = X^n + Z^n$，则
$2^{2h(Y^n)/n} \geq 2^{2h(X^n)/n} + 2^{2h(Z^n)/n}$
等号成立当且仅当 $X^n$ 与 $Z^n$ 为高斯且协方差矩阵成比例。

条件 EPI: 若 $X^n \perp Z^n | U$ 且 $Y^n = X^n + Z^n$，则
$2^{2h(Y^n|U)/n} \geq 2^{2h(X^n|U)/n} + 2^{2h(Z^n|U)/n}$

逆定理证明概要（省略趋于零的 $\epsilon_n$ 项）:

由 Fano：$nR_1 \leq I(M_1; Y_1^n | M_2)$，$nR_2 \leq I(M_2; Y_2^n)$。

需要证明存在 $\alpha \in [0,1]$ 使 $R_1 \leq nC(\alpha P/N_1)$ 和 $R_2 \leq nC(\bar{\alpha}P/(\alpha P + N_2))$。

$R_2$ 的处理:

$\begin{aligned} I(M_2; Y_2^n) &= h(Y_2^n) - h(Y_2^n | M_2) \\\\ &\leq \frac{n}{2}\log(2\pi e(P + N_2)) - h(Y_2^n | M_2) \end{aligned}$

噪声熵的下界和上界：$h(Z_2^n) \leq h(Y_2^n | M_2) \leq h(Y_2^n)$

由连续性，存在 $\alpha \in [0,1]$ 使得：

$h(Y_2^n | M_2) = \frac{n}{2}\log(2\pi e(\alpha P + N_2))$

因此 $nR_2 \leq nC(\bar{\alpha}P/(\alpha P + N_2))$。

$R_1$ 的处理:

$\begin{aligned} I(M_1; Y_1^n | M_2) &= h(Y_1^n | M_2) - h(Y_1^n | M_1, M_2, X^n) \\\\ &= h(Y_1^n | M_2) - \frac{n}{2}\log(2\pi e N_1) \end{aligned}$

利用条件 EPI 和 $Y_2^n$ 的表示 $Y_2^n = Y_1^n + \tilde{Z}_2^n$：

$\begin{aligned} 2^{2h(Y_2^n|M_2)/n} &\geq 2^{2h(Y_1^n|M_2)/n} + 2\pi e(N_2 - N_1) \\\\ 2\pi e(\alpha P + N_2) &\geq 2^{2h(Y_1^n|M_2)/n} + 2\pi e(N_2 - N_1) \end{aligned}$

从而 $h(Y_1^n | M_2) \leq \frac{n}{2}\log(2\pi e(\alpha P + N_1))$。因此：

$nR_1 \leq \frac{n}{2}\log(2\pi e(\alpha P + N_1)) - \frac{n}{2}\log(2\pi e N_1) = nC(\alpha P/N_1)$

6. 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)$ 成立	仅需比较无条件互信息

定理（El Gamal 1979）: More Capable BC 的容量区域为
$R_1 \leq I(X; Y_1 | U), \quad R_2 \leq I(U; Y_2), \quad R_1+R_2 \leq I(X; Y_1)$
对某个 $p(u, x)$，$|\mathcal{U}| \leq \min{|\mathcal{X}|, |\mathcal{Y}_1| \cdot |\mathcal{Y}_2|} + 2$。

6.1 BSC + BEC 混合 BC 的层次结构

以 $X$ 同时经过 BSC(p) → $Y_1$ 和 BEC($\epsilon$) → $Y_2$ 为例：

参数范围	信道类别	说明
$0 \leq \epsilon \leq 2p$	退化	$Y_2$ 是 $Y_1$ 的退化版本
$2p < \epsilon \leq 4p(1-p)$	Less Noisy	非退化，但 $Y_2$ 受更强噪声
$4p(1-p) < \epsilon \leq H(p)$	More Capable	非 Less Noisy，但 $Y_1$ 更强
$H(p) < \epsilon \leq 1$	一般 BC	不属于以上三类，叠加编码非最优

7. 带公共消息的广播信道

当存在公共消息 $M_0$（两个用户都需译出）时，叠加编码可以自然扩展：

    graph TB
    M0["M₀ (公共)"] --> ENC
    M1["M₁ (私密)"] --> ENC
    M2["M₂ (私密)"] --> ENC
    ENC --> CH["p(y₁,y₂|x)"]
    CH --> D1["译码器 1<br/>→ (M̂₀, M̂₁)"]
    CH --> D2["译码器 2<br/>→ (M̂₀, M̂₂)"]

定理: 速率三元组 $(R_0, R_1, R_2)$ 对 DM-BC 可达，如果存在 $p(u, x)$ 满足：
$\begin{aligned} R_1 &\leq I(X; Y_1 | U) \\\\ R_0 + R_2 &\leq I(U; Y_2) \\\\ R_0 + R_1 + R_2 &\leq I(X; Y_1) \end{aligned}$
对 More Capable BC 该内界是紧的。

直观: $U$ 承载公共消息 $M_0$ 和差用户的私密消息 $M_2$，好用户在此基础上还能额外译出其私密消息 $M_1$。

8. Marton 编码方案

对于非退化的一般 BC，叠加编码不再是最优的。Marton (1979) 通过在叠加编码基础上引入 binning（分箱）技术，给出了目前已知最佳的内界。

8.1 核心难度

叠加编码中 $U$（给用户 2）和 $X$ 是嵌套的。在非退化 BC 中，两个用户的信号向量可能不是标量嵌套关系，需要允许 $U_1$ 和 $U_2$ 相关才能达到更高的速率对。

问题: 消息 $M_1$ 和 $M_2$ 独立，如何生成相关的 $U_1^n$ 和 $U_2^n$？

解决方案: Binning（分箱）——利用联合典型性来”匹配”独立生成的两个序列。

8.2 Marton 编码的码本构造

    graph TB
    subgraph 用户1码本
        B11["Bin 1: {U₁ⁿ(1,1),...,U₁ⁿ(1,2<sup>nr₁</sup>)}"]
        B12["Bin 2: {U₁ⁿ(2,1),...,U₁ⁿ(2,2<sup>nr₁</sup>)}"]
        B13["..."]
        B1R["Bin 2<sup>nR₁</sup>"]
    end
    subgraph 用户2码本
        B21["Bin 1: {U₂ⁿ(1,1),...,U₂ⁿ(1,2<sup>nr₂</sup>)}"]
        B22["Bin 2: {U₂ⁿ(2,1),...,U₂ⁿ(2,2<sup>nr₂</sup>)}"]
        B23["..."]
        B2R["Bin 2<sup>nR₂</sup>"]
    end

步骤	描述
生成	随机独立生成 $2^{n(R_1+r_1)}$ 个 $U_1^n$ 和 $2^{n(R_2+r_2)}$ 个 $U_2^n$
分箱	将 $U_1^n$ 均分为 $2^{nR_1}$ 个箱（每箱 $2^{nr_1}$ 个）；$U_2^n$ 同理
编码	给定 $(m_1, m_2)$，在箱 $\mathcal{B}_1(m_1) \times \mathcal{B}_2(m_2)$ 中找一对联合典型的 $(U_1^n, U_2^n)$，然后发送 $X^n = f^n(U_1^n, U_2^n)$
译码 1	在 $\mathcal{B}_1$ 中找与 $Y_1^n$ 联合典型的 $U_1^n$
译码 2	在 $\mathcal{B}_2$ 中找与 $Y_2^n$ 联合典型的 $U_2^n$

8.3 联合典型序列的存在性

关键问题: 箱 $\mathcal{B}_1(m_1) \times \mathcal{B}_2(m_2)$ 中能找到一对联合典型的 $(U_1^n, U_2^n)$ 吗？

    graph TB
    subgraph 独立生成的相关性
        A["全部 U₁ⁿ 序列<br/>大小 = 2<sup>nH(U₁)</sup>"]
        B["全部 U₂ⁿ 序列<br/>大小 = 2<sup>nH(U₂)</sup>"]
        JT["联合典型序列<br/>大小 ≈ 2<sup>nH(U₁,U₂)</sup>"]
    end

全部可能的 $(U_1^n, U_2^n)$ 对有 $2^{n[H(U_1)+H(U_2)]}$ 个
联合典型对约有 $2^{nH(U_1, U_2)}$ 个
联合典型的比例：$2^{nH(U_1,U_2)} / 2^{n[H(U_1)+H(U_2)]} = 2^{-nI(U_1;U_2)}$
每箱有 $2^{nr_1} \times 2^{nr_2} = 2^{n(r_1+r_2)}$ 个序列对
期望联合典型对数：$2^{n(r_1+r_2)} \cdot 2^{-nI(U_1;U_2)}$

充分条件: $r_1 + r_2 \geq I(U_1; U_2)$，则每箱中以高概率存在联合典型对。这就是 Mutual Covering Lemma。

8.4 Marton 内界定理

定理（Marton 1979）: $(R_1, R_2)$ 可达如果
$\boxed{\begin{aligned} R_1 &\leq I(U_1; Y_1) \\\\ R_2 &\leq I(U_2; Y_2) \\\\ R_1 + R_2 &\leq I(U_1; Y_1) + I(U_2; Y_2) - I(U_1; U_2) \end{aligned}}$
对某个 $p(u_1, u_2)$ 和函数 $x(u_1, u_2)$ 成立。

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)$
消去 $r_1, r_2$（$r_1, r_2 \geq 0$）得 Marton 区域

注意: Marton 内界一般不是凸的。对于非退化 BC，通常在 Marton 内界基础上还需要取凸壳。

8.5 与 Gelfand-Pinsker 的联系

考虑 Marton 区域的一个角点（$\alpha = 1$）:

$R_1 = I(U_1; Y_1) - I(U_1; U_2), \quad R_2 = I(U_2; Y_2)$

$R_1$ 恰好等于 Gelfand-Pinsker 速率——如果我们将 $U_2^n$ 视为发送端非因果已知的干扰（状态），而接收端未知。

    graph LR
    subgraph Gelfand-Pinsker视角
        M1["M₁"] --> ENC1["编码器<br/>已知 U₂ⁿ"]
        U2["U₂ⁿ<br/>（状态/干扰）"] --> ENC1
        ENC1 -->|"Xⁿ"| CH1["p(y₁|x,u₂)"]
        CH1 -->|"Y₁ⁿ"| DEC1["译码器"]
    end

这正是下一节要深入讨论的内容。

9. Gelfand-Pinsker 问题与污纸编码

Gelfand-Pinsker (GP) 问题研究的是发送端非因果已知信道状态时的信道容量。它是理解 Marton 编码角点和污纸编码（Dirty Paper Coding, DPC）的理论基础。

9.1 问题设定

    graph TB
    M["消息 M"] --> ENC["编码器<br/>（非因果已知 Sⁿ）"]
    S["状态 Sⁿ ~ ∏ p(s)<br/>（DMS）"] --> ENC
    S --> CH["信道<br/>p(y|x,s)"]
    ENC -->|"Xⁿ"| CH
    CH -->|"Yⁿ"| DEC["译码器<br/>（未知 Sⁿ）"]
    DEC --> MHAT["M̂"]

发送端非因果地知道整个状态序列 $S^n$（例如：写在脏纸上的污渍模式在写字前已完全已知）
接收端不知道 $S^n$
信道转移概率 $p(y|x,s)$

9.2 不同状态信息情形的容量对比

情形	容量公式
收发均不知状态	$C = \max_{p(x)} I(X; Y)$
仅译码端知状态	$C^{\text{SI-D}} = \max_{p(x)} I(X; Y\vert S)$
编译码端均知状态	$C^{\text{SI-ED}} = \max_{p(x\vert s)} I(X; Y\vert S)$
仅编码端因果知状态	$C^{\text{CSI-E}} = \max_{p(u), x(u,s), U\perp S} I(U; Y)$
仅编码端非因果知状态	$C^{\text{SI-E}} = \max_{p(u\vert s), f(u,s)} [I(U; Y) - I(U; S)]$

$C \leq C^{\text{SI-D}}, C^{\text{SI-E}}, C^{\text{CSI-E}} \leq C^{\text{SI-ED}}$

9.3 Gelfand-Pinsker 定理

定理（Gelfand-Pinsker 1980）: 仅发送端非因果已知 DM 状态的信道容量为：
$\boxed{C^{\text{SI-E}} = R_{GP} = \max_{p(u|s), f(u,s)} \left[I(U; Y) - I(U; S)\right]}$
其中 $U$ 是辅助随机变量，$|\mathcal{U}| \leq \min{|\mathcal{X}| \cdot |\mathcal{S}|, |\mathcal{Y}| + |\mathcal{S}| - 1}$。

可达性证明——Binning 技术:

    graph TB
    subgraph Binning编码
        B1["Bin 1 (m=1):<br/>{Uⁿ(1,1),..., Uⁿ(1,2<sup>nR'</sup>)}"]
        B2["Bin 2 (m=2):<br/>{Uⁿ(2,1),..., Uⁿ(2,2<sup>nR'</sup>)}"]
        BNR["Bin 2<sup>nR</sup>"]
    end

步骤	内容
码本生成	固定 $p(u\vert s)$ 和 $f(u,s)$；对每个 $m$ 生成子码本 $\mathcal{C}(m)$ 含 $2^{nR’}$ 个 $U^n$ 序列（设 $\tilde{R} = R + R’$）
编码	给定 $m$ 和 $S^n$，在箱 $\mathcal{C}(m)$ 中找与 $S^n$ 联合典型的 $U^n(\ell)$；发送 $X^n = f(U^n(\ell), S^n)$
译码	接收 $Y^n$，找唯一 $(m, \ell)$ 使 $(U^n(m, \ell), Y^n) \in T_\epsilon^{(n)}$

错误分析的关键不等式:

箱中存在与 $S^n$ 联合典型的 $U^n$：$R’ \geq I(U; S)$（状态”选择”合适的 $U$）
译码端恢复 $U$：$R + R’ \leq I(U; Y)$
联合可得：$R \leq I(U; Y) - I(U; S)$ ✨

9.4 AWGN 污纸信道（Costa 1983）——Writing on Dirty Paper

考虑最重要的高斯情形：

$Y = X + S + Z$

$S \sim \mathcal{N}(0, Q)$：状态（干扰/污渍）
$Z \sim \mathcal{N}(0, 1)$：噪声
$S \perp Z$，$E[X^2] \leq P$

四种情形的容量:

情形	容量	说明
收发均不知 $S$	$C = C!\left(\frac{P}{1+Q}\right)$	状态视为噪声
仅译码端知 $S$	$C^{\text{SI-D}} = C(P)$	直接减去 $S$，恢复干净的 AWGN
编译码均知 $S$	$C^{\text{SI-ED}} = C(P)$	同上
仅编码端知 $S$	$C^{\text{SI-E}} = C(P)$	🔑 污纸编码——完美抵消！

🎯 核心结论: 发送端预先知道污渍，可以通过污纸编码（DPC）完全抵消状态的影响，达到和无状态一样的容量 $C(P)$！这就是 “Writing on Dirty Paper” 名称的由来。

最优方案推导

尝试 $U = X + \alpha S$，其中 $X \sim \mathcal{N}(0, P)$，$X \perp S$。

计算 $I(U; Y)$:

$\begin{aligned} I(U; Y) &= h(Y) - h(Y|U) \\\\ &= h(X+S+Z) - h(X+S+Z | X+\alpha S) \\\\ &= h(X+S+Z) + h(X+\alpha S) - h(X+S+Z, X+\alpha S) \\\\ &= \frac{1}{2}\log\frac{(P+Q+1)(P+\alpha^2 Q)}{PQ(1-\alpha)^2 + (P+\alpha^2 Q)} \end{aligned}$

计算 $I(U; S)$:

$I(U; S) = h(U) - h(U|S) = \frac{1}{2}\log\frac{P+\alpha^2 Q}{P}$

可达速率:

$\begin{aligned} R(\alpha) &= I(U; Y) - I(U; S) \\\\ &= \frac{1}{2}\log\frac{P(P+Q+1)}{PQ(1-\alpha)^2 + (P+\alpha^2 Q)} \end{aligned}$

优化 $\alpha$: 令分子最大化，取

$\alpha^* = \frac{P}{P+1}$

代入得：

$R(\alpha^*) = \frac{1}{2}\log(1+P) = C(P)$

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

DPC 的替代理解（更直观的推导）

从 MMSE 性质出发:

$\begin{aligned} I(U; Y) - I(U; S) &= h(U|S) - h(U|Y) \\\\ h(U|S) &= h(X+\alpha S | S) = h(X) \\\\ h(U|Y) &= h(X+\alpha S | X+S+Z) \\\\ &= h(X+\alpha S - \alpha(X+S+Z) | X+S+Z) \quad (\text{减去已知部分})\\\\ &= h(X - \alpha(X+Z) | X+Z) \\\\ &= h(X | X+Z) \quad (\text{因为当 } \alpha = \alpha^* \text{ 时}, X - \alpha(X+Z) \perp X+Z)\\\\ \therefore I(U; Y) - I(U; S) &= h(X) - h(X|X+Z) = I(X; X+Z) = C(P) \end{aligned}$

关键：当 $\alpha = P/(P+1)$ 时，$X - \alpha(X+Z)$ 与 $X+Z$ 在高斯假设下独立（MMSE 估计的正交性原理），进而也与 $Y = (X+Z) + S$ 独立。

9.5 DPC 在 MIMO 广播信道中的应用

Caire & Shamai (2003): 提出将 DPC 应用于 MIMO 高斯广播信道
Weingarten-Steinberg-Shamai (2006): 利用熵功率不等式证明 DPC 达到的速率区域就是多用户 MIMO GBC 的容量区域

这一结果确立了 DPC 作为 MIMO 下行链路（多用户 MIMO）容量可达方案的理论地位。

10. 考试重点速查表

10.1 核心公式

名称	公式
BC 容量区域（一般）	未知；Marton 内界 + Nair-El Gamal 外界
仅公共消息 BC	$C_0 = \max_{p(x)} \min\{I(X;Y_1), I(X;Y_2)\}$
叠加编码内界	$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)$（$\vert U\vert \leq \min{\vert X\vert,\vert Y_1\vert ,\vert Y_2\vert }+1$）
高斯 BC 容量	$R_1 \leq C(\alpha S_1),\; R_2 \leq C(\bar{\alpha}S_2/(\alpha S_2+1))$，$\alpha \in [0,1]$
More Capable BC	SC 内界 + $R_1+R_2 \leq I(X;Y_1)$
带公共消息 BC	$R_1 \leq I(X;Y_1\vert U),\; R_0+R_2 \leq I(U;Y_2),\; R_0+R_1+R_2 \leq I(X;Y_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_{p(u\vert s), f(u,s)} [I(U;Y) - I(U;S)]$
DPC（Costa 1983）	$C^{\text{SI-E}} = C(P)$（完美抵消状态），$\alpha^* = \frac{P}{P+1}$
Packing Lemma	若 $\vert A\vert \leq 2^{nR}$，$R < I(X;Y\vert U)-\delta$，则 $P(\exists m)$ 联合典型 $\to 0$
EPI（向量）	$2^{2h(X+Z)/n} \geq 2^{2h(X)/n} + 2^{2h(Z)/n}$
Csiszár Sum Identity	$\sum_i I(Z_{i+1}^n; Y_i\vert Y^{i-1},U) = \sum_i I(Y^{i-1}; Z_i\vert Z_{i+1}^n, U)$

10.2 关键概念对比

维度	MAC	BC
拓扑	多发一收（上行）	一发多收（下行）
编码约束	发送端独立	发送端协作（同一编码器）
译码约束	接收端协作	接收端独立
容量区域	已知（单字母刻画）	一般未知
可达方法	同时译码 / SC + TS	叠加编码 / Marton binning
凸性	非凸，需取凸壳	SC 内界自凸

退化类型	定义	容量是否已知
退化 BC	$X \to Y_1 \to Y_2$	✅ 已知
Less Noisy	$I(U;Y_1) \geq I(U;Y_2)\; \forall p(u,x)$	✅ 已知（SC）
More Capable	$I(X;Y_1) \geq I(X;Y_2)\; \forall p(x)$	✅ 已知（SC + 和速率约束）
一般 BC	以上都不满足	❌ 未知

10.3 各类信道容量对比

状态信息情景	容量公式	AWGN 特例
收发均不知	$\max I(X;Y)$	$C(P/(1+Q))$
仅译码知	$\max I(X;Y\vert S)$	$C(P)$
编译码均知	$\max I(X;Y\vert S)$	$C(P)$
编码端因果知	$\max I(U;Y), U\perp S$	—
编码端非因果知（GP）	$\max [I(U;Y)-I(U;S)]$	$C(P)$（DPC 完美抵消）

10.4 重要定理与证明方法

定理	可达性方法	逆定理关键工具
退化 BC 容量	叠加编码 + Packing Lemma	Gallager $U_i=(M_2,Y_1^{i-1})$ / Nair 支撑超平面 + Csiszár Sum Identity
高斯 BC 容量	$U,V$ 高斯 + SIC	EPI（条件 EPI）
GP 容量	Binning（分箱编码）	Csiszár Sum Identity / 凹包络
DPC $C(P)$	$U = X + \alpha S$，优化 $\alpha$	MMSE 正交性

复习建议:

叠加编码（§3）是 BC 的基础——必须理解云+卫星的结构、Packing Lemma 的作用、以及译码器 1 的”同时非唯一译码”。

退化 BC（§4）的容量定理及其 Gallager 逆定理证明是核心考点——重点掌握 $U_i = (M_2, Y_1^{i-1})$ 的构造和两个速率约束的推导。

高斯 BC（§5）的 EPI 逆定理是考试难点——理解为什么需要条件 EPI 以及 $\alpha$ 参数如何通过 $h(Y_2^n|M_2)$ 的连续性引入。

Marton 编码（§8）中 binning 的核心思想是从独立消息中生成相关 $U_1, U_2$——理解 $r_1+r_2 \geq I(U_1;U_2)$ 的必要性。

Gelfand-Pinsker（§9）是 BC 角点的理论基础——重点掌握 $I(U;Y)-I(U;S)$ 公式和 DPC 中 $\alpha^* = P/(P+1)$ 的推导。