第四章相关信源的编码（Coding of Correlated Sources）

课程: 网络信息论（Network Information Theory）
教材: A. El Gamal and Y.-H. Kim, Network Information Theory, Cambridge University Press, 2011
整理说明: 本章系统介绍相关信源的分布式压缩理论——从无损压缩（Slepian-Wolf 编码、有 Helper 的编码）到有损压缩（率失真函数、Wyner-Ziv 编码），揭示 Covering Lemma 与 Packing Lemma 的对偶关系。
免责声明：本笔记内容来源于课程讲义和PPT，经AI辅助汇总完成，仅供学习参考。如有错误或遗漏，请以原始课程资料为准。

1. 点对点无损压缩回顾

1.1 经典模型

离散无记忆信源（DMS）$(\mathcal{X}, p(x))$ 产生 i.i.d. 序列 $X^n$。

    graph LR
    XN["X<sup>n</sup>"] --> ENC["编码器<br/>m(X<sup>n</sup>)"]
    ENC -->|"M ∈ [1:2<sup>nR</sup>]"| DEC["译码器<br/>X̂<sup>n</sup>(M)"]
    DEC --> XHAT["X̂<sup>n</sup>"]

概念	定义
$(2^{nR}, n)$ 码	编码器 $m: \mathcal{X}^n \to [1:2^{nR}]$，译码器 $\hat{x}^n: [1:2^{nR}] \to \mathcal{X}^n$
错误概率	$P_e^{(n)} = P{\hat{X}^n \neq X^n}$
可达速率 $R$	$\exists (2^{nR}, n)$ 码使 $\lim_n P_e^{(n)} \to 0$
最优压缩速率 $R^*$	所有可达速率的下确界

1.2 无损信源编码定理（Shannon 1948）

$\boxed{R^* = H(X)}$

可达性（基于典型集）:

$|T\epsilon^{(n)}| \approx 2^{nH(X)}$，$P{X^n \in T\epsilon^{(n)}} \geq 1 - \epsilon$
给典型序列分配不同索引，非典型序列映射到固定索引
$Pe \leq P{X^n \notin T\epsilon^{(n)}} \to 0$

逆定理: Fano 不等式。

1.3 随机 Binning 编码方案

这是理解 Slepian-Wolf 编码的关键前导。

    graph TB
    subgraph 随机Binning
        direction LR
        SEQ["所有 X<sup>n</sup> 序列"] -->|"随机分配索引"| B1["Bin 1"]
        SEQ --> B2["Bin 2"]
        SEQ --> B3["..."]
        SEQ --> BR["Bin 2<sup>nR</sup>"]
    end

步骤	操作
码本生成	对每个 $x^n \in \mathcal{X}^n$ 随机分配一个索引 $m(x^n) \in [1:2^{nR}]$；具有相同索引的序列构成一个箱（Bin）$\mathcal{B}(m)$
编码	观察到 $x^n \in \mathcal{B}(m)$，发送箱索引 $m$
译码	在 $\mathcal{B}(m)$ 中寻找唯一的典型序列 $\hat{x}^n$；否则宣布错误

错误概率分析（对随机 bin 分配取平均）:

令 $M$ 为 $X^n$ 的随机 bin 索引。注意 $M \sim \text{Unif}[1:2^{nR}]$，且与 $X^n$ 独立。

错误事件	定义	概率
$E_1$	$X^n \notin T_\epsilon^{(n)}$	$\to 0$（LLN）
$E_2$	$\exists \tilde{x}^n \neq X^n, \tilde{x}^n \in T_\epsilon^{(n)}, \tilde{x}^n \in \mathcal{B}(M)$	关键分析

$P(E_2)$ 的分析（假设 $X^n \in \mathcal{B}(1)$）:

$\begin{aligned} P(E_2) &= \sum_{x^n} P(X^n = x^n | x^n \in \mathcal{B}(1)) \cdot P(\exists \tilde{x}^n \neq x^n, \tilde{x}^n \in T_\epsilon^{(n)}, \tilde{x}^n \in \mathcal{B}(1)) \\\\ &\leq \sum_{x^n} p(x^n) \sum_{\tilde{x}^n \in T_\epsilon^{(n)}, \neq x^n} \underbrace{P(\tilde{x}^n \in \mathcal{B}(1))}_{= 2^{-nR}} \\\\ &\leq |T_\epsilon^{(n)}| \cdot 2^{-nR} \\\\ &\leq 2^{n(H(X)+\delta)} \cdot 2^{-nR} \to 0 \quad \text{当 } R > H(X) \end{aligned}$

🔑 关键洞察: 随机 binning 中，一个”错误”的典型序列落入同一 bin 的概率仅为 $2^{-nR}$。这就是 binning 技术的核心机制——通过随机分箱来”隔离”不同的典型序列。

2. 相关信源的分布式无损压缩——Slepian-Wolf

2.1 问题模型

两个相关的 DMS 分量 $(U, V) \sim p(u, v)$。两个编码器分别观测 $U^n$ 和 $V^n$，不能互相通信；一个联合译码器同时恢复两者。

    graph TB
    U["U<sup>n</sup>"] --> ENC1["编码器 1<br/>m₁(U<sup>n</sup>)"]
    V["V<sup>n</sup>"] --> ENC2["编码器 2<br/>m₂(V<sup>n</sup>)"]
    ENC1 -->|"M₁ ∈ [1:2<sup>nR₁</sup>]"| DEC["联合译码器"]
    ENC2 -->|"M₂ ∈ [1:2<sup>nR₂</sup>]"| DEC
    DEC --> UHAT["Û<sup>n</sup>"]
    DEC --> VHAT["V̂<sup>n</sup>"]

2.2 速率区域的初步分析

内界（独立编码）:

$R_1 \geq H(U), \quad R_2 \geq H(V)$

外界（联合编码）:

$R_1 + R_2 \geq H(U, V), \quad R_1 \geq H(U|V), \quad R_2 \geq H(V|U)$

    graph LR
    subgraph Slepian-Wolf速率区域
        direction TB
        A2["H(V)"]
        C2["H(V|U)"]
        D2["H(U|V)"]
        B2["H(U)"]
        SUM["H(U,V)"]
    end

2.3 Slepian-Wolf 定理（1973）⭐

定理: 最优速率区域 $R^*$ 是满足以下条件的所有 $(R_1, R_2)$ 的集合：
$\boxed{\begin{aligned} R_1 &\geq H(U | V) \\\\ R_2 &\geq H(V | U) \\\\ R_1 + R_2 &\geq H(U, V) \end{aligned}}$

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

以坐标图展示：

R₂
^
| H(V) ●──────────┐
|      │＼          │
|      │  ＼  可达   │
|H(V|U)●     ＼     │
|      │  区域  ＼   │
|      │         ＼  │
|      └──────────●──●──> R₁
|    H(U|V)       H(U)

2.4 逆定理证明

利用 Markov 链 $(U^n, V^n) \to (M_1, M_2) \to (\hat{U}^n, \hat{V}^n)$。

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

$\begin{aligned} nR_1 &\geq H(M_1) \geq H(M_1 | M_2) \\\\ &= H(M_1 | M_2) - H(M_1 | M_2, U^n) \quad (\text{因为 } H(M_1|M_2,U^n) \geq 0)\\\\ &= I(M_1; U^n | M_2) \\\\ &= H(U^n | M_2) - H(U^n | M_2, M_1) \\\\ &\geq H(U^n | V^n, M_2) - H(U^n | \hat{U}^n) \quad (\text{由 Markov 性})\\\\ &= H(U^n | V^n) - n\epsilon_n \quad (\text{Fano: } H(U^n|\hat{U}^n) \leq n\epsilon_n)\\\\ &= n H(U|V) - n\epsilon_n \end{aligned}$

证 $R_1 + R_2 \geq H(U, V)$（类似思路）:

$\begin{aligned} n(R_1 + R_2) &\geq H(M_1, M_2) \\\\ &= I(M_1, M_2; U^n, V^n) \\\\ &= H(U^n, V^n) - H(U^n, V^n | M_1, M_2) \\\\ &\geq H(U^n, V^n) - H(U^n, V^n | \hat{U}^n, \hat{V}^n) \\\\ &= n H(U, V) - n\epsilon_n \end{aligned}$

2.5 可达性证明（Cover 1975）——随机 Binning

对称编码方案（与 §1.3 的随机 binning 完全对偶）:

步骤	用户 1 ($U$)	用户 2 ($V$)
码本生成	随机将每个 $u^n$ 分配索引 $m_1 \in [1:2^{nR_1}]$	随机将每个 $v^n$ 分配索引 $m_2 \in [1:2^{nR_2}]$
编码	观察到 $u^n \in \mathcal{B}_1(m_1)$，发送 $m_1$	观察到 $v^n \in \mathcal{B}_2(m_2)$，发送 $m_2$
译码	联合译码：在 $\mathcal{B}_1(m_1) \times \mathcal{B}_2(m_2)$ 中找唯一的联合典型对 $(\hat{u}^n, \hat{v}^n)$	-

错误事件分析（对随机 bin 分配取平均）:

假设真实序列为 $(U^n, V^n)$，bin 索引为 $(M_1, M_2)$。

事件	定义	概率 → 0 的条件
$E_1$	$(U^n, V^n) \notin T_\epsilon^{(n)}$	无条件（LLN）
$E_2$	$\exists \tilde{u}^n \neq U^n, \tilde{u}^n \in \mathcal{B}_1(M_1), (\tilde{u}^n, V^n) \in T_\epsilon^{(n)}$	$R_1 \geq H(U\vert V)$
$E_3$	$\exists \tilde{v}^n \neq V^n, \tilde{v}^n \in \mathcal{B}_2(M_2), (U^n, \tilde{v}^n) \in T_\epsilon^{(n)}$	$R_2 \geq H(V\vert U)$
$E_4$	$\exists \tilde{u}^n \neq U^n \in \mathcal{B}_1(M_1), \tilde{v}^n \neq V^n \in \mathcal{B}_2(M_2), (\tilde{u}^n, \tilde{v}^n) \in T_\epsilon^{(n)}$	$R_1+R_2 \geq H(U,V)$

$E_2$ 的详细分析:

$\begin{aligned} P(E_2) &\leq \sum_{u^n \in T_\epsilon^{(n)}(U|V), \neq U^n} P(\tilde{u}^n \in \mathcal{B}_1(M_1)) \\\\ &\leq |T_\epsilon^{(n)}(U|V)| \cdot 2^{-nR_1} \\\\ &\approx 2^{nH(U|V)} \cdot 2^{-nR_1} \to 0 \quad \text{当 } R_1 > H(U|V) \end{aligned}$

$E_4$ 的详细分析:

$\begin{aligned} P(E_4) &\leq \sum_{(\tilde{u}^n, \tilde{v}^n) \in T_\epsilon^{(n)}(U,V), \neq (U^n,V^n)} P(\tilde{u}^n \in \mathcal{B}_1(M_1)) \cdot P(\tilde{v}^n \in \mathcal{B}_2(M_2)) \\\\ &\leq 2^{nH(U,V)} \cdot 2^{-nR_1} \cdot 2^{-nR_2} \to 0 \quad \text{当 } R_1+R_2 > H(U,V) \end{aligned}$

📌 Packing Lemma 在此的作用: 保证在 bin 中不存在另一个与接收到的 $V^n$（或联合接收信息）联合典型的序列——这是”packing”的体现：将典型序列”打包”进不同的 bin 中以防止混淆。

2.6 扩展到 k 个信源

定理: $k$-DMS $(X_1, \ldots, X_k)$ 的最优速率区域是所有满足以下条件的 $(R_1, \ldots, R_k)$ 的集合：
$\sum_{j \in S} R_j \geq H(\mathbf{X}(S) | \mathbf{X}(S^c)), \quad \forall S \subseteq [1:k]$
即任意子集的速率之和至少为该子集在已知其他信源条件下的条件熵。

2.7 另一种可达性方案（Slepian-Wolf 1973 原证）

考虑角点 $(H(U|V), H(V))$:

编码器 2：$R_2 \geq H(V)$（常规信源编码）
编码器 1：无法观测 $V^n$，如何实现 $R_1 \geq H(U|V)$？

巧妙方案: 将 $[U \to V] \sim p(v|u)$ 视为虚拟信道。利用信道编码，存在码 $\mathcal{C}$ 含 $2^{nI(U;V)}$ 个输入 $u^n$ 和一个译码器使错误概率 $< \epsilon$。

生成 $K = \frac{2^{nH(U)}}{2^{nI(U;V)}} = 2^{nH(U|V)}$ 个这样的信道码 $\mathcal{C}_1, \ldots, \mathcal{C}_K$

编码器 1 将 $u^n$ 编码为包含它的第一个码 $\mathcal{C}_i$ 的索引 $i$

译码器利用 $m_2$ 恢复的 $\hat{v}^n$ 和 $i$，在码 $\mathcal{C}_i$ 中译码出 $\hat{u}^n$

这就是信源-信道对偶性的经典实例——将分布式信源编码问题转化为信道编码问题。

3. 有 Helper 的无损压缩——Ahlswede-Körner-Wyner

3.1 问题模型

2 分量 DMS $(X, Y) \sim p(x, y)$。目标是无损压缩 $X$，编码器 2（Helper）可以观测 $Y$ 并发送信息来帮助译码 $X$。

    graph TB
    X["X<sup>n</sup>"] --> ENC1["编码器 1<br/>m₁(X<sup>n</sup>)"]
    Y["Y<sup>n</sup>"] --> ENC2["编码器 2 (Helper)<br/>m₂(Y<sup>n</sup>)"]
    ENC1 -->|"M₁"| DEC["译码器<br/>X̂<sup>n</sup>(M₁,M₂)"]
    ENC2 -->|"M₂"| DEC

3.2 特殊情形

情形	条件	所需速率
无 Helper	$R_2 = 0$	$R_1 \geq H(X)$
无损 Helper	$R_2 \geq H(Y)$	$R_1 \geq H(X\vert Y)$（退化为 Slepian-Wolf）

3.3 内界与外界

内界:

$R_1 \geq H(X|Y), \quad H(Y) \cdot R_1 + I(X;Y) \cdot R_2 \geq H(X) \cdot H(Y)$

外界:

$R_1 \geq H(X|Y)$

3.4 定理（Ahlswede-Körner 1975, Wyner 1975）

定理: 最优速率区域是所有满足以下条件的 $(R_1, R_2)$ 的集合：
$\boxed{\begin{aligned} R_1 &\geq H(X | U) \\\\ R_2 &\geq I(Y; U) \end{aligned}}$
对某个 $p(u|y)$，$|\mathcal{U}| \leq |\mathcal{Y}| + 1$，且 Markov 链 $U \to Y \to X$ 成立。

3.5 可达性概要

    graph TB
    subgraph 编码器2 (Helper)
        YN["Y<sup>n</sup>"] --> FIND["找 U<sup>n</sup>(m₂)<br/>与 Y<sup>n</sup> 联合典型"]
        FIND --> SEND2["发送 m₂"]
    end
    subgraph 编码器1
        XN["X<sup>n</sup>"] --> BIN["随机 Binning:<br/>X<sup>n</sup> → B(m₁)"]
        BIN --> SEND1["发送 m₁"]
    end
    subgraph 译码器
        M1["m₁"] --> DECODE
        M2["m₂"] --> DECODE["在 B(m₁) 中找 Û<sup>n</sup><br/>与 U<sup>n</sup>(m₂) 联合典型"]
    end

步骤	内容	速率条件
码本生成	对每个 $m_2$ 随机生成 $U^n(m_2) \sim \prod p_U$；随机将 $X^n$ 分配到 bin $\mathcal{B}(m_1)$	—
编码器 1	$X^n$ 所在 bin 索引 $m_1$	—
编码器 2	找 $U^n(m_2)$ 与 $Y^n$ 联合典型，发送 $m_2$	$R_2 \geq I(Y; U)$
译码	在 $\mathcal{B}(m_1)$ 中找唯一 $\hat{X}^n$ 与 $U^n(m_2)$ 联合典型	$R_1 \geq H(X\vert U)$

3.6 逆定理概要

识别辅助变量 $U_i = (M_2, Y^{i-1}, X^{i-1})$，满足 $U_i \to Y_i \to X_i$。

使用下凸包络（Lower Convex Envelope）方法（参见 slides p.24）:

$n(\mu R_1 + R_2) \geq \mu H(M_1) + H(M_2) \approx \sum_i H(Y_i) + \mathcal{C}[\mu H(X) - H(Y)](Y_i)$

其中 $\mathcal{C}[f]$ 表示 $f$ 的下凸包络。当 $\mu \leq 1$ 时，$\mu R_1 + R_2 \geq \mu H(X)$。

4. 点对点有损压缩——率失真理论

4.1 基本模型

    graph LR
    XN["X<sup>n</sup>"] --> ENC["编码器<br/>m(X<sup>n</sup>)"]
    ENC -->|"M ∈ [1:2<sup>nR</sup>]"| DEC["译码器<br/>X̂<sup>n</sup>(M)"]
    DEC --> XHAT["X̂<sup>n</sup>"]

概念	定义
失真度量	$d: \mathcal{X} \times \hat{\mathcal{X}} \to [0, \infty)$；Hamming 失真：$d(x,\hat{x}) = 1_{x \neq \hat{x}}$
平均每符号失真	$d(x^n, \hat{x}^n) = \frac{1}{n}\sum_i d(x_i, \hat{x}_i)$
期望失真	$E[d(X^n, \hat{X}^n)] = \frac{1}{n}\sum_i E[d(X_i, \hat{X}_i)]$
$(R, D)$ 可达	$\exists (2^{nR}, n)$ 码使 $\limsup_n E[d(X^n, \hat{X}^n)] \leq D$
率失真函数	$R(D) = \inf{R : (R, D) \text{ 可达}}$

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

定理:
$\boxed{R(D) = \min_{p(\hat{x}|x):\; E[d(X,\hat{X})] \leq D} I(X; \hat{X})}$
对 $D \geq D_{\min} = \min_{\hat{x}(x)} E[d(X, \hat{x}(X))]$ 成立。

    graph LR
    subgraph R(D) 曲线
        direction TB
        HX["R(0) = H(X)"]
        RD["R(D)"]
        DMAX["D<sub>max</sub>"]
    end

典型曲线: 当 $D = 0$ 时，$R(0) = H(X)$（退化为无损压缩）；当 $D \geq D_{\max}$ 时，$R(D) = 0$（无需传输）。

4.3 实例：Bernoulli 信源 + Hamming 失真

$X \sim \text{Bern}(p)$，$0 \leq p \leq 1/2$，Hamming 失真：

$R(D) = \max\{H_2(p) - H_2(D), 0\}$

最优反向测试信道（反向 BSC）:

    graph LR
    XHAT["X̂ ~ Bern(p-D)/(1-2D)"] -->|"BSC(D)"| X["X ~ Bern(p)"]
    Z["Z ~ Bern(D)"] --> X

理解: 将压缩看作通过”反向信道”$p(\hat{x}|x)$ 将 $\hat{X}$ 变为 $X$。等价的”正向测试信道”为 $p(x|\hat{x})$——最优分布恰好是 BSC($D$)。

4.4 逆定理证明概要

对任意 $(2^{nR}, n)$ 码序列满足 $\limsup E[d] \leq D$：

$\begin{aligned} nR &\geq H(M) \geq I(M; X^n) \geq I(\hat{X}^n; X^n) \\\\ &= \sum_i I(\hat{X}^n; X_i | X^{i-1}) \\\\ &= \sum_i I(\hat{X}^n, X^{i-1}; X_i) \quad (\text{无记忆性})\\\\ &\geq \sum_i I(\hat{X}_i; X_i) \geq \sum_i R(E[d(X_i, \hat{X}_i)]) \\\\ &\geq n R\!\left(\frac{1}{n}\sum_i E[d(X_i, \hat{X}_i)]\right) = n R(E[d(X^n, \hat{X}^n)]) \end{aligned}$

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

4.5 二次高斯信源编码

$X \sim \mathcal{N}(0, P)$，平方误差失真 $d(x, \hat{x}) = (x - \hat{x})^2$：

$R(D) = \min_{p(\hat{x}|x): E[(X-\hat{X})^2] \leq D} I(X; \hat{X}) = \frac{1}{2}\log^+\!\left(\frac{P}{D}\right)$

最优反向测试信道:

    graph LR
    XHAT["X̂ ~ N(0, P-D)"] -->|"+"| X["X ~ N(0, P)"]
    Z["Z ~ N(0, D)"] --> X

最优策略：$\hat{X} \sim \mathcal{N}(0, P-D)$，$Z \sim \mathcal{N}(0, D)$，$\hat{X} \perp Z$，$X = \hat{X} + Z$（此即反向高斯测试信道）。

4.6 可达性——随机编码 + 联合典型编码

步骤	操作
码本生成	固定达到 $R(D/(1+\epsilon))$ 的 $p(\hat{x}\vert x)$；独立生成 $2^{nR}$ 个 $\hat{X}^n(m) \sim \prod p_{\hat{X}}$
编码	观察到 $x^n$，找索引 $m$ 使得 $(x^n, \hat{x}^n(m)) \in T_\epsilon^{(n)}$；若多个则选最小；若无则选 $m=1$
译码	收到 $m$，重构 $\hat{x}^n = \hat{x}^n(m)$

关键误差事件:

事件	定义	控制条件
$E_1$	$X^n \notin T_\epsilon^{(n)}$	LLN $\to 0$
$E_2$	$\forall m, (X^n, \hat{X}^n(m)) \notin T_\epsilon^{(n)}$	$R > I(X; \hat{X})$（Covering Lemma）

Covering Lemma 的作用: 保证码本中存在一个码字与信源序列联合典型——这需要 $R$ 足够大（大于 $I(X;\hat{X})$）。Covering 与 Packing 形成对偶。

5. 有边信息的有损压缩——Wyner-Ziv

5.1 问题模型

信源 $(X, Y)$ 为 2-DMS。编码器观测 $X^n$（不能观测 $Y^n$），译码器已知 $Y^n$（边信息/side information）。目标是在失真 $D$ 下重建 $\hat{X}^n$。

    graph TB
    X["X<sup>n</sup>"] --> ENC["编码器<br/>m(X<sup>n</sup>)"]
    ENC -->|"M ∈ [1:2<sup>nR</sup>]"| DEC["译码器<br/>X̂<sup>n</sup>(M, Y<sup>n</sup>)"]
    Y["Y<sup>n</sup> (边信息)"] --> DEC
    DEC --> XHAT["X̂<sup>n</sup>"]

5.2 不同边信息情形的率失真函数对比

情形	条件	率失真函数
无边信息	$(m(x^n), \hat{x}^n(m))$	$R(D) = \min_{p(\hat{x}\vert x)} I(X; \hat{X})$
仅编码端有 SI	$(m(x^n, y^n), \hat{x}^n(m))$	$R^{\text{SI-E}}(D) = R(D)$（SI 不降低速率需求）
编译码端均有 SI	$(m(x^n, y^n), \hat{x}^n(m, y^n))$	$R^{\text{SI-ED}}(D) = \min_{p(\hat{x}\vert x,y)} I(X; \hat{X}\vert Y)$
仅译码端有 SI	$(m(x^n), \hat{x}^n(m, y^n))$	$R^{\text{SI-D}}(D)$ — Wyner-Ziv 问题

对 Hamming 失真且 $D = 0$：$R^* = H(X|Y)$（设置 $U = X$），与编译码端均知 $Y$ 相同——退化为 Slepian-Wolf。

5.3 Wyner-Ziv 定理（1976）⭐

定理: 仅译码端有边信息时的率失真函数为：
$\boxed{R^{\text{SI-D}}(D) = \min_{p(u|x),\; \hat{x}(u,y):\; E[d(X,\hat{X})] \leq D} \big[I(X; U) - I(Y; U)\big] = \min I(X; U | Y)}$
其中 $U$ 为辅助随机变量，满足 $U \to X \to Y$。

Wyner-Ziv 公式的关键结构: $I(X; U) - I(Y; U) = I(X; U|Y)$——条件互信息。

5.4 可达性 —— Compress-Bin 方案

这是理解 Wyner-Ziv 编码的核心。

    graph TB
    subgraph 编码端
        XN["X<sup>n</sup>"] --> COVER["Covering:<br/>找 l 使 (X<sup>n</sup>, U<sup>n</sup>(l)) ∈ T<sub>ε'</sub>"]
        COVER --> BIN["Binning:<br/>l ∈ B(m)，发送 m"]
    end
    subgraph 译码端
        M["m"] --> DECODE
        YN["Y<sup>n</sup>"] --> DECODE["Packing:<br/>在 B(m) 中找唯一 U<sup>n</sup>(l̂)<br/>使 (U<sup>n</sup>(l̂), Y<sup>n</sup>) ∈ T<sub>ε</sub>"]
        DECODE --> RECON["重建 X̂<sup>n</sup> = x̂(U<sup>n</sup>(l̂), Y<sup>n</sup>)"]
    end

码本生成:

步骤	操作
1	固定达到 $R^{\text{SI-D}}(D/(1+\epsilon))$ 的 $p(u\vert x)$ 和 $\hat{x}(u, y)$
2	独立生成 $2^{n\tilde{R}}$ 个 $U^n(l) \sim \prod p_U(u_i)$，$l \in [1:2^{n\tilde{R}}]$
3	将 $l$ 的索引空间均分为 $2^{nR}$ 个 bin：$\mathcal{B}(m) = [(m-1)2^{n(\tilde{R}-R)}+1 : m2^{n(\tilde{R}-R)}]$

编码（Covering）: 观察到 $x^n$，找 $l$ 使 $(x^n, u^n(l)) \in T_{\epsilon’}^{(n)}$，发送 $l$ 所在 bin 的索引 $m$。

译码（Packing）: 收到 $m$ 和已知 $y^n$，在 $\mathcal{B}(m)$ 中找唯一的 $\hat{l}$ 使 $(u^n(\hat{l}), y^n) \in T_\epsilon^{(n)}$，重构 $\hat{x}_i = \hat{x}(u_i(\hat{l}), y_i)$。

5.5 错误概率与失真分析

令 $(L, M)$ 为编码端选择的索引，$\hat{L}$ 为译码端的估计。

事件	定义	控制条件	所用工具
$E_1$	$\forall l, (U^n(l), X^n) \notin T_{\epsilon’}^{(n)}$	$\tilde{R} > I(X; U)$	Covering Lemma
$E_2$	$(U^n(L), X^n, Y^n) \notin T_\epsilon^{(n)}$	—	条件典型引理
$E_3$	$\exists \tilde{l} \neq L \in \mathcal{B}(M), (U^n(\tilde{l}), Y^n) \in T_\epsilon^{(n)}$	$\tilde{R} - R < I(Y; U)$	Packing Lemma

🔑 Compress-Bin 的精髓:

Covering: $\tilde{R} > I(X; U)$——码本要足够大，以”覆盖”每个 $x^n$（找到与之联合典型的 $U^n$）

Packing: $\tilde{R} - R < I(Y; U)$——每个 bin 要足够小，以”打包”不混淆

联合可得: $R > I(X; U) - I(Y; U) = I(X; U|Y)$ ✨

5.6 Covering Lemma 与 Packing Lemma 的对偶

    graph TB
    subgraph 编码 (Covering)
        C1["生成 2<sup>nR̃</sup> 个 U<sup>n</sup>"]
        C2["要求: R̃ > I(X;U)"]
        C3["目标: 存在 l 使 (X<sup>n</sup>, U<sup>n</sup>(l)) 联合典型"]
    end
    subgraph 译码 (Packing)
        P1["每个 Bin 有 2<sup>n(R̃-R)</sup> 个 U<sup>n</sup>"]
        P2["要求: R̃-R < I(Y;U)"]
        P3["目标: Bin 中至多一个 U<sup>n</sup> 与 Y<sup>n</sup> 联合典型"]
    end

6. Wyner-Ziv 与 Gelfand-Pinsker 的对偶性

本章最后一页幻灯片揭示了两大经典问题之间的深刻对偶关系：

维度	Wyner-Ziv（信源编码）	Gelfand-Pinsker（信道编码）
问题	仅译码端有边信息的有损压缩	仅编码端有状态的信道编码
公式	$R^{\text{SI-D}} = \min[I(X;U) - I(Y;U)]$	$C^{\text{SI-E}} = \max[I(U;Y) - I(U;S)]$
优化方向	最小化压缩速率	最大化传输速率
编码工具	Covering（覆盖）	Packing（打包）
译码工具	Packing（打包）	Covering（覆盖）
编码端	Covering: 找与 $X^n$ 联合典型的 $U^n$	Binning: 找与 $S^n$ 联合典型的 $U^n$
译码端	Packing: 在 bin 中找与 $Y^n$ 匹配的 $U^n$	Covering: $U^n$ 与 $Y^n$ 联合典型

    graph LR
    subgraph Wyner-Ziv
        WZX["X<sup>n</sup>"] -->|"Covering<br/>I(X;U)"| WZU["U<sup>n</sup>"]
        WZU -->|"Binning<br/>I(X;U)-I(Y;U)"| WZM["M"]
        WZM -->|"Packing<br/>I(Y;U)"| WZXHAT["X̂<sup>n</sup>"]
    end
    subgraph Gelfand-Pinsker
        GPM["M"] -->|"Binning<br/>I(U;S)"| GPU["U<sup>n</sup>"]
        GPU -->|"Covering<br/>I(U;Y)-I(U;S)"| GPY["Y<sup>n</sup>"]
        GPS["S<sup>n</sup>"] --> GPU
    end

根本的对偶关系:

率失真 $R(D) = \min I(X; \hat{X})$ vs 信道容量 $C = \max I(X; Y)$——一个是最小化，一个是最大化

信源编码：优化信道给定信源；信道编码：优化信源给定信道

信源编码用联合典型编码（Covering）；信道编码用联合典型译码（Packing）

Wyner-Ziv：Covering 速率 $-$ Packing 速率；GP：Packing 速率 $-$ Covering 速率

7. 考试重点速查表

7.1 核心公式

名称	公式
无损信源编码	$R^* = H(X)$
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)),\; \forall S \subseteq [1:k]$
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)$
编译码均有 SI	$R^{\text{SI-ED}}(D) = \min_{p(\hat{x}\vert x,y)} I(X; \hat{X}\vert Y)$
Wyner-Ziv	$R^{\text{SI-D}}(D) = \min[I(X;U) - I(Y;U)] = \min I(X;U\vert Y)$
Gelfand-Pinsker	$C^{\text{SI-E}} = \max[I(U;Y) - I(U;S)]$

7.2 关键概念对比

概念	Covering Lemma	Packing Lemma
作用	保证码本中存在一个码字满足条件	保证 bin 中至多一个码字满足条件
条件	码本大小足够大：$R > I(X; U)$	bin 大小足够小：$R < I(Y; U)$
应用	信源编码（编码器找联合典型）	信道编码（译码器排除混淆）
在 WZ 中	编码端：$\tilde{R} > I(X;U)$	译码端：$\tilde{R}-R < I(Y;U)$

信源编码问题	边信息位置	速率条件
无损点对点	无	$R \geq H(X)$
Slepian-Wolf	译码端（两个编码器间无协作）	$R_1 \geq H(U\vert V)$
有 Helper 无损	译码端 + Helper 编码 $Y$	$R_1 \geq H(X\vert U), R_2 \geq I(Y;U)$
有损点对点	无	$R \geq \min I(X;\hat{X})$
Wyner-Ziv	仅译码端	$R \geq \min[I(X;U)-I(Y;U)]$
有损编译码端均有 SI	编译码端	$R \geq \min I(X;\hat{X}\vert Y)$

7.3 Slepian-Wolf 错误事件速查表

事件	定义	速率条件
$E_1$	$(U^n, V^n)$ 不典型	无条件
$E_2$	$U$ 错 + $V$ 对	$R_1 \geq H(U\vert V)$
$E_3$	$U$ 对 + $V$ 错	$R_2 \geq H(V\vert U)$
$E_4$	两者都错	$R_1+R_2 \geq H(U,V)$

7.4 Wyner-Ziv 错误事件速查表

事件	定义	控制条件	工具
$E_1$	$\forall l, (U^n(l), X^n) \notin T_{\epsilon’}^{(n)}$	$\tilde{R} > I(X;U)$	Covering Lemma
$E_2$	$(U^n(L), X^n, Y^n) \notin T_\epsilon^{(n)}$	无条件（条件典型引理）	—
$E_3$	Bin 中有混淆	$\tilde{R}-R < I(Y;U)$	Packing Lemma

复习建议:

Slepian-Wolf（§2）是分布式信源编码的基石——必须理解为什么 $H(U,V)$ 的和速率在编码器无协作时仍可达（随机 binning + 联合典型译码）。四个错误事件的分析方法要能默写。

Binning 技术（§§1.3, 2.5, 3.5, 5.4）贯穿全章——从随机 binning 的基本机制（错误典型序列落入同一 bin 的概率为 $2^{-nR}$）出发，理解 Slepian-Wolf、有 Helper 和无损压缩、Wyner-Ziv 中 binning 的不同用法。

率失真理论（§4）的核心是 $R(D) = \min I(X;\hat{X})$——理解 Covering Lemma 在编码端的作用（保证码本中存在与信源联合典型的码字）。

Wyner-Ziv（§5）的 Compress-Bin 方案是整章的高潮——Covering（编码）+ Packing（译码）的分工，以及 $R > I(X;U) - I(Y;U)$ 的推导。

WZ ↔ GP 对偶性（§6）是网络信息论最漂亮的结构之一——信源编码 vs 信道编码、最小化 vs 最大化、Covering vs Packing 的角色互换。