Prerequisites & Notation

Before You Begin

This chapter introduces multiuser source coding, where multiple encoders compress correlated sources separately and a single decoder reconstructs them jointly. The key tool is random binning, which is to source coding what random coding is to channel coding. We assume familiarity with typicality (Chapter 3), lossless source coding (Chapter 5), and rate-distortion theory (Chapter 6).

Strong typicality and joint typicality (Chapter 3)(Review ch03)
Self-check: Can you state the covering lemma and the packing lemma, and explain when each is used?
Lossless source coding theorem and entropy rate (Chapter 5)(Review ch05)
Self-check: Can you explain why $H(X)$ bits per symbol are both necessary and sufficient for lossless compression?
Rate-distortion function and the Wyner-Ziv problem (Chapter 6)(Review ch06)
Self-check: Can you write the rate-distortion function $R$ and explain the covering lemma proof of achievability?
Random coding arguments and union bounds(Review ch03)
Self-check: Can you outline the random coding argument for the channel coding theorem?
Fano's inequality for converse proofs(Review ch01)
Self-check: Can you state Fano's inequality and explain how it converts small error probability into an entropy bound?

Notation for This Chapter

Symbols used throughout this chapter. All logarithms are base 2 unless stated otherwise. We use the notation conventions from Chapters 1-6.

Symbol	Meaning	Introduced
$X, Y$	Correlated discrete sources with joint PMF $P_{XY}$	s01
$R_X, R_Y$	Encoding rates for sources $X$ and $Y$ (bits per symbol)	s01
$H(X\|Y)$	Conditional entropy of $X$ given $Y$	s01
$\mathcal{B}_X, \mathcal{B}_Y$	Bin indices for Slepian-Wolf random binning	s01
$I(X;Y)$	Mutual information between $X$ and $Y$	s01
$\hat{X}, \hat{Y}$	Reconstructions of sources $X$ and $Y$	s02
$d(x, \hat{x})$	Distortion measure between source symbol and reconstruction	s02
$R$	Rate-distortion function	s02
$U, V$	Auxiliary random variables in achievability arguments	s02
$C$	Channel capacity	s04
$\log$	Logarithm base 2 (bits) unless noted otherwise	s01

← Ch 6 Slepian-Wolf Coding