Exercises

$\sigma^2 = \int_{-1/2}^{1/2} x^2 dx = \frac{x^3}{3}\Big|_{-1/2}^{1/2} = \frac{1}{12}$.

$\text{Vol}(\Lambda)^{2/n} = 1^{2/1} = 1$. $G = \sigma^2/\text{Vol}^{2/n} = 1/12 \approx 0.0833$.

Compare with the optimal $1/(2\pi e) \approx 0.0585$. The 1D lattice has a shaping loss of $10\log_{10}((1/12)/(1/(2\pi e))) = 1.53$ dB.

$K = \lfloor 256 \times 0.6 \rfloor = 153$ information bits. Frozen bits: $N - K = 256 - 153 = 103$. Code rate: $R = 153/256 \approx 0.598$.

Coding gain $= 9.6 - 0.2 = 9.4$ dB.

The Shannon limit for rate 1/2 is $E_b/N_0 = (2^{2R}-1)/(2R) = 1/1 = 0$ dB, which is $-0.0$ dB. So the code is 0.2 dB from the Shannon limit.

The shaping gap is independent of constellation size at high SNR: $\gamma_s = 10\log_{10}(\pi e/6) = 10\log_{10}(1.4257) \approx 1.53$ dB.

At moderate SNR, the actual gap may be smaller because the discreteness of the constellation is less significant.

$I(W^-) + I(W^+) = I(U_1; Y_1, Y_2) + I(U_2; Y_1, Y_2, U_1)$.

By the chain rule for mutual information: $I(U_1, U_2; Y_1, Y_2) = I(U_1; Y_1, Y_2) + I(U_2; Y_1, Y_2 | U_1)$.

Since knowing $U_1$ does not reduce the information in $(Y_1, Y_2)$ about $U_2$ beyond what is already captured: $I(U_2; Y_1, Y_2, U_1) = I(U_2; Y_1, Y_2 | U_1)$ (because $U_1$ and $U_2$ are independent).

$I(U_1, U_2; Y_1, Y_2) = I(X_1; Y_1) + I(X_2; Y_2) = 2I(W)$

where the first equality uses the fact that the encoding $(X_1, X_2) = (U_1 \oplus U_2, U_2)$ is a bijection, so mutual information is preserved.

$U_1$ can be recovered from $Y_1 \oplus Y_2$ (when both are not erased). $U_1$ is erased iff $Y_1$ is erased OR $Y_2$ is erased. $\epsilon^- = 1 - (1-\epsilon)^2 = 2\epsilon - \epsilon^2$.

Given $U_1$, we need $U_2 = X_2$, so $U_2$ is recovered from $Y_2$ (directly) or from $Y_1 \oplus U_1$ (indirectly). $U_2$ is erased iff both $Y_1$ AND $Y_2$ are erased. $\epsilon^+ = \epsilon^2$.

$\epsilon^- + \epsilon^+ = 2\epsilon - \epsilon^2 + \epsilon^2 = 2\epsilon$. But the capacity is $1 - \epsilon$, so the total capacity is $(1-\epsilon^-) + (1-\epsilon^+) = 2 - 2\epsilon = 2(1-\epsilon) = 2I(W)$. $\checkmark$

$\eta = R \times \log_2 M = 0.75 \times 6 = 4.5$ bits/s/Hz.

$E_b/N_0|_{\min} = (2^{4.5}-1)/4.5 = (22.63 - 1)/4.5 = 4.81$. In dB: $10\log_{10}(4.81) \approx 6.82$ dB.

Gap $= 7.5 - 6.82 = 0.68$ dB.

Modern LDPC codes have a coding gap of about $0.1$–$0.3$ dB at this rate. The shaping loss is approximately $0.68 - 0.2 = 0.48$ dB, which is less than the theoretical maximum of 1.53 dB because the high rate and finite constellation size reduce the effective shaping penalty.

16-QAM is $\{(a, b) : a, b \in \{-3, -1, 1, 3\}\}$, which is a subset of $2\mathbb{Z} + 1$ (odd integers) in each dimension. After scaling, this is $\Lambda = \mathbb{Z}^2$ intersected with the square $[-4, 4)^2$.

The hexagonal lattice $A_2$ has $G(A_2) \approx 0.0802$ vs. $G(\mathbb{Z}^2) = 1/12 \approx 0.0833$. The power efficiency improvement is $10\log_{10}(0.0833/0.0802) \approx 0.16$ dB.

This is the basis for hexagonal constellations, which provide a small but measurable improvement over square QAM.

$I_0 = I(W)$. At step $m$, the path $B_m$ determines which bit-channel we are at. At step $m+1$, we go to either $(B_m, 0)$ (applying $W^-$) or $(B_m, 1)$ (applying $W^+$), each with probability 1/2.

$\mathbb{E}[I_{m+1} | I_m = c] = \frac{1}{2}I(W_c^-) + \frac{1}{2}I(W_c^+) = \frac{1}{2} \cdot 2c = c = I_m$.

(Using $I(W^-) + I(W^+) = 2I(W)$.)

$I_m$ is a bounded martingale ($0 \leq I_m \leq 1$), so by the martingale convergence theorem, $I_m \to I_\infty$ a.s. Since the variance $\text{Var}(I_{m+1} | I_m)$ is strictly positive unless $I_m \in \{0, 1\}$, the only possible limits are 0 and 1. The fraction converging to 1 equals $\mathbb{E}[I_0] = I(W)$.

Standard 16-QAM has 4 points at $|x|^2 = 2$ (inner ring), 8 points at $|x|^2 = 10$ (middle ring), and 4 points at $|x|^2 = 18$ (outer ring).

$P(x) = \frac{e^{-\lambda|x|^2}}{Z}$ where $Z = 4e^{-2\lambda} + 8e^{-10\lambda} + 4e^{-18\lambda}$.

For $\lambda = 0$: uniform, $\mathbb{E}[|X|^2] = 10$, $H = 4$ bits. For $\lambda = 0.05$: $\mathbb{E}[|X|^2] \approx 8.2$, $H \approx 3.7$ bits. For $\lambda = 0.12$: $\mathbb{E}[|X|^2] \approx 5.6$, $H \approx 3.0$ bits.

The optimal $\lambda^* \approx 0.12$ achieves the minimum 3-bit rate with a power reduction of about $10\log_{10}(10/5.6) \approx 2.5$ dB. Of this, 1.53 dB is shaping gain; the rest comes from reducing the effective rate from 4 to 3 bits/symbol.

Nearest-neighbor decoding fails when the noise vector $Z^{n}$ leaves the Voronoi region. For reliable decoding, we need $\text{Vol}(\mathcal{V})^{2/n} \gg (2\pi e N)^{n/2 \times 2/n} = 2\pi e N$. Hence $\mu = \text{Vol}(\Lambda)^{2/n}/(2\pi e N) > 1$.

With a spherical shaping region of power $P$ and volume $\text{Vol}(\mathcal{S})^{2/n} = 2\pi e P/(n^{1/n}) \approx 2\pi e P$:

$R = \frac{1}{2}\log\frac{\text{Vol}(\mathcal{S})^{2/n}}{\text{Vol}(\Lambda)^{2/n}} = \frac{1}{2}\log\frac{2\pi e P}{2\pi e N \cdot G(\Lambda) \cdot 2\pi e} \to \frac{1}{2}\log\frac{P}{N}$

as $G(\Lambda) \to 1/(2\pi e)$. More precisely: $R = \frac{1}{2}\log(P/N) + \frac{1}{2}\log(1/(2\pi e G(\Lambda)))$. As $G \to 1/(2\pi e)$, the second term vanishes.

For BPSK over AWGN at SNR = 1 (0 dB): $m_0 = 2\text{SNR} = 2$.

$m^+ = 2 \times 2 = 4$ (good channel). $m^- = \phi^{-1}(1-(1-\phi(2))^2)$ where $\phi(m) = 1 - \frac{1}{\sqrt{4\pi m}}\int e^{-(t-m)^2/(4m)}dt$. Numerically, $\phi(2) \approx 0.3799$, $m^- \approx 0.963$.

From $m = 4$: $m_3^+ = 8$, $m_3^- \approx 2.53$. From $m = 0.963$: $m_1^+ = 1.926$, $m_1^- \approx 0.384$.

Ordering: bit 4 ($m=8$, best) > bit 3 ($m=2.53$) > bit 2 ($m=1.926$) > bit 1 ($m=0.384$, worst).

For rate 1/2: freeze bits 1 and 2 (worst), use bits 3 and 4.

• Turbo (rate 1/2, 8-state): $E_b/N_0 \approx 1.5$ dB (gap: 1.3 dB)
• LDPC (optimized irregular, BP): $E_b/N_0 \approx 1.2$ dB (gap: 1.0 dB)
• Polar (CA-SCL, $L=32$): $E_b/N_0 \approx 1.3$ dB (gap: 1.1 dB)

At this moderate block length, all three perform within about 1.0–1.5 dB of the Shannon limit. LDPC has a slight edge, but the differences are small and depend strongly on the specific code design and decoder implementation. At longer block lengths ($n \geq 4096$), all three approach within 0.3 dB of the limit.

$N = K/R = 8448/(2/3) = 8448 \times 3/2 = 12672$ bits.

In 5G NR, this would be transmitted using rate matching to fit the allocated resource blocks.

Starting from $\epsilon = 0.5$: at each level, each channel with erasure $e$ splits into $e^- = 2e - e^2$ and $e^+ = e^2$.

The recursion has fixed points at $e = 0$ and $e = 1$. For $0 < e < 1$: $e^+ = e^2 < e$ and $e^- = 2e - e^2 > e$. The "good" children get better, the "bad" children get worse.

By the martingale argument, as $m \to \infty$, the fraction of channels with $e < \delta$ (capacity $> 1 - \delta$) approaches $1 - \epsilon = 0.5$, and the fraction with $e > 1 - \delta$ (capacity $< \delta$) also approaches 0.5.