第四章相关信源的编码（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)}, \quad P\{X^n \in T_\epsilon^{(n)}\} \geq 1 - \epsilon$
给典型序列分配不同索引，非典型序列映射到固定索引
$P_e \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 技术的核心机制——通过随机分箱来”隔离”不同的典型序列。

1.4 随机 Binning 的两种视角：哈希与线性 Binning

视角一：哈希函数类比。随机 binning 的本质与哈希函数非常相似：为每个源序列随机分配一个大索引，等价于选取一个随机哈希函数。只要典型序列集合足够小（或等价地，哈希函数的值域 $2^{nR}$ 足够大），高概率下不同的典型序列就会落入不同的索引。binning 的错误事件 $E_2$ 正是”哈希碰撞”。

视角二：随机线性 binning。对伯努利信源，取

$w(x^n) = x^n H$

其中 $H$ 为 $n \times nR$ 的随机二进制矩阵，元素 i.i.d. $\sim \text{Bern}(1/2)$。可以证明该方案的错误概率与随机 binning 相当。这正是线性信道编码的对偶：信道编码用生成矩阵把消息”展开”成码字，而 binning 用校验矩阵（奇偶校验、伴随式）把序列”压缩”成索引——每个 bin 恰为一个线性码的陪集（coset）。这一代数结构正是后续分布式信源编码（乃至网络编码）实用化构造的基础。

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 TB
    C1["R₁ ≥ H(U|V)"] --> REG["最优速率区域 R*<br/>（三条约束的交集）"]
    C2["R₂ ≥ H(V|U)"] --> REG
    C3["R₁ + R₂ ≥ H(U,V)"] --> REG

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_1 + R_2 \geq H(U, V)$ 即使两个编码器都能观测到两个源的输出也不改变——这并不意味着给编码器提供另一源的边信息毫无用处：边信息不能降低可达速率，却能显著降低编译码器的复杂度（例如编码器 1 若知道 $V^n$，就无需使用本章的分布式方案）。

以坐标图展示：

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) \\\\ &\geq H(M_1 | M_2) - H(M_1 | M_2, U^n) \quad (\text{减去非负项})\\\\ &= 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{条件不增熵; } \hat{U}^n \text{ 是 } (M_1, M_2) \text{ 的函数})\\\\ &= H(U^n | V^n) - H(U^n | \hat{U}^n) \quad (M_2 \text{ 是 } V^n \text{ 的函数})\\\\ &= n H(U|V) - n\epsilon_n \quad (\text{Fano: } H(U^n|\hat{U}^n) \leq 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) \\\\ &= H(M_1, M_2) - H(M_1, M_2 | U^n, V^n) \quad (M_1, M_2 \text{ 由 } (U^n, V^n) \text{ 确定})\\\\ &= 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) \quad ((\hat{U}^n, \hat{V}^n) \text{ 是 } (M_1, M_2) \text{ 的函数})\\\\ &= n H(U, V) - n\epsilon_n \quad (\text{Fano}) \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$ 的详细分析（给定 $V^n$ 的条件典型集 $T_\epsilon^{(n)}(U|V^n)$ 大小约为 $2^{nH(U|V)}$）:

$\begin{aligned} P(E_2) &\leq \sum_{\tilde{u}^n \neq U^n:\; (\tilde{u}^n, V^n) \in T_\epsilon^{(n)}} P(\tilde{u}^n \in \mathcal{B}_1(M_1)) \\\\ &\leq |T_\epsilon^{(n)}(U|V^n)| \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 实例：双对称二进制信源 DSBS(p)

定义: $(X_1, X_2)$ 为双对称二进制信源（doubly symmetric binary source, DSBS(p)），若

$p_{X_1,X_2}(0,0) = p_{X_1,X_2}(1,1) = \frac{1-p}{2}, \quad p_{X_1,X_2}(0,1) = p_{X_1,X_2}(1,0) = \frac{p}{2}, \quad p \in [0, 1/2]$

性质:

性质	内容
边缘分布	$X_1 \sim \text{Bern}(1/2)$，$X_2 \sim \text{Bern}(1/2)$
模二和	$Z = X_1 \oplus X_2 \sim \text{Bern}(p)$，且与 $X_1$、$X_2$ 均独立
信道视角	$X_2 = X_1 \oplus Z$：$X_2$ 是以 $X_1$ 为输入的 BSC(p) 的输出，反之亦然

    graph LR
    X1["X₁ ~ Bern(1/2)"] -->|"⊕"| X2["X₂ ~ Bern(1/2)"]
    Z["Z ~ Bern(p), Z ⊥ X₁"] -->|"⊕"| X2

Slepian-Wolf 速率区域: 由 $H(X_1|X_2) = H(X_2|X_1) = H(p)$，$H(X_1, X_2) = 1 + H(p)$，得

$\boxed{R_1 \geq H(p), \quad R_2 \geq H(p), \quad R_1 + R_2 \geq 1 + H(p)}$

数值实例: 取 $p = 0.01$，两源高度相关：

方案	所需速率
独立压缩	2 bits/符号对
Slepian-Wolf	$H(X_1) + H(X_2 \vert X_1) = H(1/2) + H(0.01) = 1 + 0.0808 = 1.0808$ bits/符号对

💡 相关性越强（$p$ 越小），Slepian-Wolf 编码相对独立压缩的节省越显著——这正是分布式压缩的核心价值所在。

2.7 扩展到 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]$
即任意子集的速率之和至少为该子集在已知其他信源条件下的条件熵。

📌 多对一 vs 一对多: 分布式无损信源编码（多对一通信）与多址接入信道（MAC）一样，对任意数量的发送端都有单字母刻画；而其对偶的一对多通信——广播信道（BC，即使只有两个接收端）——容量区域一般未知（见第三章）。多对一问题”好解”、一对多问题”难解”，是网络信息论中反复出现的现象。

2.8 另一种可达性方案（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$——这 $2^{nI(U;V)}$ 个码字恰好是”可以在 $V$ 端分辨”的序列集合。

生成 $K = \frac{2^{nH(U)}}{2^{nI(U;V)}} = 2^{nH(U|V)}$ 个这样的信道码 $\mathcal{C}_1, \ldots, \mathcal{C}_K$：每个码本含 $2^{nI(U;V)}$ 个码字，$K$ 个码本恰好渐近覆盖全部约 $2^{nH(U)}$ 个典型序列

编码器 1 将 $u^n$ 编码为包含它的第一个码 $\mathcal{C}_i$ 的索引 $i$（速率 $\log K = H(U|V)$）

译码器利用 $m_2$ 恢复的 $\hat{v}^n$ 和 $i$，在码 $\mathcal{C}_i$ 中译码出 $\hat{u}^n$（信道译码：错误概率 $< \epsilon$）

由此达到角点 $(H(U|V), H(V))$；对称地可得角点 $(H(U), H(V|U))$，整个速率区域由时分共享（time-sharing）取凸包得到。

这就是信源-信道对偶性的经典实例——将分布式信源编码问题转化为信道编码问题。注意该方案是非对称的（一个编码器做常规信源编码），与 §2.5 中 Cover 1975 的对称 binning 方案互为补充。

3. 有 Helper 的无损压缩

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 内界与外界

内界的构造——时分共享（time-sharing）: §3.2 的两个特殊情形给出两个角点：$(H(X), 0)$（无 Helper）与 $(H(X|Y), H(Y))$（Helper 无损传输 $Y$）。对这两个方案做时分共享并利用区域的凸性，可得连接两角点的线段：对任意 $R_2 \in [0, H(Y)]$，

$R_1 \geq H(X) - \frac{I(X;Y)}{H(Y)} \cdot R_2$

整理为 PPT 中的形式（代入两端点均满足等号）：

$\boxed{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)$

以坐标图表示：

R₂
^
| H(Y) ●────────┐
|      │ 时分共享 │
|      │   内界   │
|      └────────●──────> R₁
|    H(X|Y)   H(X)

⚠️ 两个界都不紧: 一般情形下时分共享内界与平凡外界之间存在间隙——这正是为什么需要下面的 Ahlswede-Körner-Wyner 定理给出精确刻画。

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$ 成立。

区域的几何含义: 每个可行的辅助变量 $U$ 对应一个”矩形” ${R_1 \geq H(X|U),\; R_2 \geq I(Y;U)}$ 的右上角点 $(H(X|U), I(Y;U))$；最优速率区域即所有这样的矩形（角点）之并的闭包。直观上：

$U$ 是 Helper 对 $Y$ 的压缩描述：Helper 以速率 $I(Y;U)$ 传输 $U$，译码端把 $U$ 当作”部分边信息”，主编码器只需以 $H(X|U)$ 的速率传输即可恢复 $X$
$U$ 的压缩程度可调：$U$ 越”精细”（$R_2$ 大），$R_1$ 越小，两端点在 $R_1$-$R_2$ 平面上形成一条折中曲线

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$（多个则取最小，没有则取 $m_2=1$）	$R_2 \geq I(Y; U)$
译码	在 $\mathcal{B}(m_1)$ 中找唯一 $\hat{X}^n$ 与 $U^n(m_2)$ 联合典型	$R_1 \geq H(X\vert U)$

错误概率分析: 译码错误仅当以下任一事件发生，故

$P(E) \leq P(E_1) + P(E_1^c \cap E_2) + P(E_3 | X^n \in \mathcal{B}(1))$

事件	定义	控制条件	所用工具
$E_1$	$\forall m_2,\; (U^n(m_2), Y^n) \notin T_{\epsilon'}^{(n)}$	$R_2 > I(Y;U) + \delta(\epsilon’)$	Covering Lemma
$E_2$	$(X^n, U^n(M_2)) \notin T_\epsilon^{(n)}$	无条件	条件典型引理
$E_3$	$\exists \tilde{x}^n \neq X^n \in \mathcal{B}(M_1),\; (\tilde{x}^n, U^n(M_2)) \in T_\epsilon^{(n)}$	$R_1 > H(X\vert U) + \delta(\epsilon)$	Binning 分析（同 §1.3）

🔑 结构洞察: 本方案与 §5 的 Wyner-Ziv（Compress-Bin）同构——Helper 用联合典型编码把 $Y$ “压缩”为辅助变量 $U$（Covering），译码端以 $U$ 为边信息、借助主编码器的 binning 恢复 $X$（Packing）。区别仅在于这里是无损恢复，而 Wyner-Ziv 允许失真。

3.6 逆定理（标准证明，NIT §10.4.2）

讲义 p.24 提示”identification (check book)”——即识别辅助变量

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

由 DMS 无记忆性（给定 $Y_i$ 时 $X_i$ 与 $(M_2, Y^{i-1}, X^{i-1})$ 独立），有 Markov 链 $U_i \to Y_i \to X_i$。

$R_2$ 方向:

$\begin{aligned} nR_2 &\geq H(M_2) \geq I(M_2; Y^n) \\\\ &= \sum_{i=1}^{n} I(M_2; Y_i | Y^{i-1}) \\\\ &= \sum_{i=1}^{n} I(M_2, Y^{i-1}; Y_i) \quad (I(Y^{i-1};Y_i)=0)\\\\ &\overset{(a)}{=} \sum_{i=1}^{n} I(M_2, Y^{i-1}, X^{i-1}; Y_i) = \sum_{i=1}^{n} I(U_i; Y_i) \end{aligned}$

其中 (a) 利用了 Markov 链 $X^{i-1} \to (M_2, Y^{i-1}) \to Y_i$ ，由 $(X^{i-1}, Y^{i-1}) \perp (Y_i, Y_{i+1}^n)$ 且 $M_2 = m_2(Y^n)$ 推出。

$R_1$ 方向:

$\begin{aligned} nR_1 &\geq H(M_1) \geq H(M_1 | M_2) \\\\ &= H(M_1 | M_2) + H(X^n | M_1, M_2) - H(X^n | M_1, M_2) \\\\ &\geq H(M_1, X^n | M_2) - n\epsilon_n \quad (\text{Fano: } H(X^n|M_1,M_2) \leq n\epsilon_n)\\\\ &= H(X^n | M_2) - n\epsilon_n \quad (M_1 = m_1(X^n))\\\\ &= \sum_{i=1}^{n} H(X_i | M_2, X^{i-1}) - n\epsilon_n \\\\ &\geq \sum_{i=1}^{n} H(X_i | M_2, X^{i-1}, Y^{i-1}) - n\epsilon_n \quad (\text{条件不增熵})\\\\ &= \sum_{i=1}^{n} H(X_i | U_i) - n\epsilon_n \end{aligned}$

单字母化: 引入时分共享变量 $Q \sim \text{Unif}[1:n]$，与 $(X^n, Y^n, U^n)$ 独立。则

$R_1 \geq H(X_Q | U_Q, Q), \qquad R_2 \geq I(Y_Q; U_Q | Q) = I(Y_Q; U_Q, Q) \quad (Q \perp Y_Q)$

定义 $X = X_Q$，$Y = Y_Q$，$U = (Q, U_Q)$，令 $n \to \infty$，即得 $R_1 \geq H(X|U)$，$R_2 \geq I(Y;U)$，且 $U \to Y \to X$。基数界 $|\mathcal{U}| \leq |\mathcal{Y}| + 1$ 由凸覆盖方法（convex cover method，教材附录 C）给出。

3.7 另一种逆定理思路：下凸包络（讲义 p.24）

讲义给出的替代证明思路基于下凸包络（Lower Convex Envelope）方法：对任意 $\mu \geq 1$ 的支撑超平面，

$\begin{aligned} n(\mu R_1 + R_2) &\geq \mu H(M_1) + H(M_2) \\\\ &\geq \mu H(M_1|M_2) + I(M_2; Y^n) \\\\ &\geq \mu H(X^n|M_2) - \mu H(X^n|M_1, M_2) + I(M_2; Y^n) \\\\ &= \mu H(X^n|M_2) - \mu n\epsilon_n + I(M_2; Y^n) \\\\ &\approx H(Y^n) - H(Y^n|M_2) + \mu H(X^n|M_2) \\\\ &\overset{?}{\geq} \sum_i H(Y_i) + \mathcal{C}[\mu H(X) - H(Y)](Y_i) \end{aligned}$

其中 $\mathcal{C}[f]$ 表示 $f$ 的下凸包络（把 $p(x|y)$ 视为信道）。讲义在最后一步标注 “?”，即该步的严格论证需要额外技术处理。当 $\mu \leq 1$ 时，由 $n(R_1+R_2) \geq I(M_1,M_2; X^n) \geq nH(X) - n\epsilon_n$ 知 $\mu R_1 + R_2 \geq \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))]$ 成立。

两个特征失真值:

记号	定义	含义
$D_{\min}$	$\min_{\hat{x}(x)} E[d(X, \hat{x}(X))]$	无速率约束下可达的最小失真；$R(D_{\min}) = H(X)$（无损极限）
$D_{\max}$	$\min_{\hat{x} \in \hat{\mathcal{X}}} E[d(X, \hat{x})]$	零速率可达的最小失真；$D \geq D_{\max}$ 时 $R(D) = 0$（取常数重构 $\hat{x}^* = \arg\min$，无需传输）

    graph LR
    A["D = 0（设 D<sub>min</sub> = 0）<br/>R(0) = H(X)"] -->|"D 增大<br/>R(D) 单调递减"| B["0 < D < D<sub>max</sub><br/>R(D) 凸下降"]
    B -->|"D 继续增大"| C["D ≥ D<sub>max</sub><br/>R(D) = 0"]

典型曲线: 当 $D = 0$ 时（假设 $D_{\min} = 0$ ，如 Hamming 失真）， $R(0) = H(X)$ ，退化为无损压缩；当 $D \geq D_{\max}$ 时， $R(D) = 0$ ，无需传输。 $R(D)$ 在 $[D_{\min}, D_{\max}]$ 上是 $D$ 的非增凸函数（凸性是逆定理最后一步的关键）。

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\}$

其中 $D_{\max} = p$（取 $\hat{x} \equiv 0$）。当 $D \leq p$ 时，验证：最优测试信道 $p(\hat{x}|x)$ 使 $I(X; \hat{X}) = H(X) - H(X|\hat{X}) = H_2(p) - H_2(D)$，其中 $H(X|\hat{X}) = H_2(D)$ 对应”反向 BSC”结构。

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

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

理解: 将压缩看作通过”反向信道”$p(\hat{x}|x)$ 将 $\hat{X}$ 变为 $X$——反向信道刻画的是”$\hat{X}$ 加上多少噪声才成为 $X$”。等价的”正向测试信道”为 $p(x|\hat{x})$——最优分布恰好是 BSC($D$)：$X = \hat{X} \oplus Z$。

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}) + \delta(\epsilon)$（Covering Lemma）

失真分析（对码本取平均）: 令 $E = {(X^n, \hat{X}^n(M)) \notin T_\epsilon^{(n)}}$ 为”编码错误”事件，$P(E) \leq P(E_1) + P(E_2) \to 0$。由全期望公式与典型平均引理（typical average lemma，联合典型的序列对每符号失真接近期望）:

$\begin{aligned} E[d(X^n; \hat{X}^n)] &= P(E)\, E[d(X^n, \hat{X}^n) | E] + P(E^c)\, E[d(X^n, \hat{X}^n) | E^c] \\\\ &\leq P(E)\, d_{\max} + P(E^c)\, (1+\epsilon)\, E[d(X, \hat{X})] \end{aligned}$

由于 $p(\hat{x}|x)$ 达到 $R(D/(1+\epsilon))$，即 $E[d(X, \hat{X})] \leq D/(1+\epsilon)$，故 $E[d(X^n, \hat{X}^n)] \leq P(E)d_{\max} + D \to D$。这说明速率 $R = R(D/(1+\epsilon)) + \delta(\epsilon)$ 可达失真 $D$；令 $\epsilon \to 0$，由 $R(D)$ 的连续性得 $R(D)$ 可达。

Covering Lemma 的作用: 保证码本中存在一个码字与信源序列联合典型——这需要 $R$ 足够大（大于 $I(X;\hat{X})$）。Covering 与 Packing 形成对偶。若失真测度为 Hamming 失真且 $D = 0$，本方案即退化为 §1.2 的无损压缩（NIT 3.6.4）。

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。

⚠️ Wyner-Ziv 速率损失: 一般而言 $R^{\text{SI-D}}(D) \geq R^{\text{SI-ED}}(D)$，且可以严格大于——编码端不知道边信息是有代价的，称为 Wyner-Ziv 速率损失（rate loss）。一个重要的例外是联合高斯信源 + 平方误差失真：此时无速率损失，
$R^{\text{SI-D}}(D) = R^{\text{SI-ED}}(D) = \frac{1}{2}\log^{+}\!\left(\frac{\sigma_{X|Y}^2}{D}\right)$
其中 $\sigma_{X|Y}^2$ 为 $X$ 在已知 $Y$ 条件下的均方误差（条件方差）。

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]}$
其中 $U$ 为辅助随机变量，满足 Markov 链 $U \to X \to Y$（由 $p(u|x)$ 保证），基数 $|\mathcal{U}| \leq |\mathcal{X}| + 1$。

Wyner-Ziv 公式的关键结构: 由 Markov 链 $U \to X \to Y$ 有 $I(X; U) - I(Y; U) = I(X; U | Y)$——条件互信息。因此目标函数也可等价地写为

$R^{\text{SI-D}}(D) = \min_{p(u|x),\; \hat{x}(u,y):\; E[d(X,\hat{X})] \leq D} I(X; U | Y)$

与编译码端均有边信息时的 $\min I(X; \hat{X}|Y)$ 相比，Wyner-Ziv 用辅助变量 $U$（编码端对 $X$ 的压缩描述）替代了直接的重构 $\hat{X}$——这正是编码端”不知道” $Y$ 的体现。

5.4 逆定理概要（NIT §11.3.2）

逆定理的关键是识别辅助变量

$U_i = (M, Y^{i-1}, Y_{i+1}^n)$

注意到重构 $\hat{X}_i$ 是 $(M, Y^n) = (U_i, Y_i)$ 的函数，且由 DMS 无记忆性有 Markov 链 $U_i \to X_i \to Y_i$。于是

$\begin{aligned} nR &\geq H(M) \geq H(M | Y^n) \\\\ &= H(M | Y^n) - H(M | X^n, Y^n) \quad (M = m(X^n))\\\\ &= I(X^n; M | Y^n) \\\\ &= \sum_{i=1}^{n} I(X_i; M | Y^n, X^{i-1}) \\\\ &\overset{(a)}{=} \sum_{i=1}^{n} I(X_i; M, Y^{i-1}, Y_{i+1}^n, X^{i-1} | Y_i) \\\\ &\geq \sum_{i=1}^{n} I(X_i; U_i | Y_i) \\\\ &\geq \sum_{i=1}^{n} R^{\text{SI-D}}\big(E[d(X_i, \hat{X}_i)]\big) \quad (\text{每一时隙构成一个单字母 Wyner-Ziv 实例})\\\\ &\overset{(b)}{\geq} n\, R^{\text{SI-D}}\!\left(\frac{1}{n}\sum_{i=1}^{n} E[d(X_i, \hat{X}_i)]\right) \end{aligned}$

其中 (a) 利用了 $(X_i, Y_i) \perp (Y^{i-1}, Y_{i+1}^n, X^{i-1})$ （DMS 无记忆性），(b) 是 $R^{\text{SI-D}}(D)$ 的凸性。由假设 $\limsup_n \frac{1}{n}\sum_i E[d(X_i, \hat{X}_i)] \leq D$ 及 $R^{\text{SI-D}}(D)$ 的非增性，得 $R \geq R^{\text{SI-D}}(D)$。基数界 $|\mathcal{U}| \leq |\mathcal{X}| + 1$ 由凸覆盖方法给出。

💡 与 §3.6 的 AKW 逆定理对比：两个证明都是”识别辅助变量 + 单字母化”的套路，只是 Markov 链方向相反（WZ 中 $U \to X \to Y$，AKW 中 $U \to Y \to X$），这正是 §6 对偶性的另一面。

5.5 可达性 —— Compress-Bin 方案

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

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

    style ENC fill:#e3f2fd,stroke:#1565c0
    style DEC fill:#e8f5e9,stroke:#2e7d32
    style COVER fill:#bbdefb
    style DECODE fill:#c8e6c9

码本生成:

步骤	操作
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.6 错误概率与失真分析

令 $(L, M)$ 为编码端选择的索引，$\hat{L}$ 为译码端的估计。最终失真事件被以下并界控制：

$P(E) \leq P\{(U^n(\hat{L}), X^n, Y^n) \notin T_\epsilon^{(n)}\} \leq P(E_1) + P(E_1^c \cap E_2) + P(E_3)$

事件	定义	控制条件	所用工具
$E_1$	$\forall l, (U^n(l), X^n) \notin T_{\epsilon’}^{(n)}$	$\tilde{R} > I(X; U) + \delta(\epsilon’)$	Covering Lemma
$E_2$	$(U^n(L), X^n, Y^n) \notin T_\epsilon^{(n)}$	—（在 $E_1^c$ 下）	条件典型引理
$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

失真分析: 与 §4.6 相同，由全期望公式与典型平均引理，$E[d(X^n, \hat{X}^n)] \leq P(E)d_{\max} + P(E^c)(1+\epsilon)\, E[d(X,\hat{X})] \to D$（因 $p(u|x)$、$\hat{x}(u,y)$ 达到 $R^{\text{SI-D}}(D/(1+\epsilon))$）；再由 $R(D)$ 的连续性完成证明。

🔑 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.7 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：找与 $X^n$ 联合典型的 $U^n$（速率 $I(X;U)$），再 Binning 发送 bin 索引	Covering：找与 $S^n$ 联合典型的 $U^n$（速率 $I(U;S)$），再 Binning 发送 bin 索引
译码端	Packing：在 bin 中找与 $Y^n$ 联合典型的唯一 $U^n$	Packing：在 bin 中找与 $Y^n$ 联合典型的唯一 $U^n$
速率结构	覆盖速率 − 打包速率 = $I(X;U) - I(Y;U)$	打包速率 − 覆盖速率 = $I(U;Y) - I(U;S)$

    graph LR
    subgraph WZ["Wyner-Ziv (信源编码)"]
        WZX["X^n"] -->|"Covering<br/>I(X;U)"| WZU["U^n"]
        WZU -->|"Binning<br/>R = I(X;U)-I(Y;U)"| WZM["M"]
        WZY["Y^n (边信息)"] -->|"Packing<br/>I(Y;U)"| WZXHAT["X̂^n"]
        WZM --> WZXHAT
    end
    subgraph GP["Gelfand-Pinsker (信道编码)"]
        GPM["M"] -->|"Binning<br/>R = I(U;Y)-I(U;S)"| GPU["U^n"]
        GPS["S^n (状态)"] -->|"Covering<br/>I(U;S)"| GPU
        GPU -->|"信道 p(y|x,s)"| GPY["Y^n"]
        GPY -->|"Packing<br/>I(U;Y)"| GPMHAT["M̂"]
    end

    style WZ fill:#e3f2fd,stroke:#1565c0
    style GP fill:#fff3e0,stroke:#e65100

根本的对偶关系:

率失真 $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]$
DSBS(p) 的 SW 区域	$R_1 \geq H(p),\; R_2 \geq H(p),\; R_1+R_2 \geq 1+H(p)$
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)$
Wyner-Ziv（高斯）	$R^{\text{SI-D}}(D) = \frac{1}{2}\log^+(\sigma_{X\vert Y}^2/D)$（无速率损失）
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