Exercises
ex-ch14-01
EasyState the ARQ-DMT formula of El Gamal-Caire-Damen 2006 in closed form and verify the boundary conditions at and .
Use the formula .
Static DMT: at integer corners, piecewise-linear between.
Formula
, where is the static Zheng-Tse DMT. Domain: , .
Boundary at $L = 1$
β the static DMT of Ch. 12. Consistent with "no ARQ = one round".
Boundary as $L \to \infty$
For any fixed : . Hence . This is the ergodic-capacity regime.
ex-ch14-02
EasyOn a i.i.d. Rayleigh channel with ARQ rounds, compute the ARQ-DMT diversity at the following long-term effective rates: . Compare with the static DMT.
.
On : , , , linear between.
Compute $d^{*}(r/2)$
For : . On segment : . On segment : . Values: .
Wait β for , , giving . For , , giving . For , , giving .
Compute ARQ-DMT
. Values: .
Static DMT for comparison
at : (zero beyond ).
Interpretation
ARQ-DMT is strictly greater than the static DMT for all where both are defined, and it extends the domain beyond (the static DMT is for ; the ARQ-DMT extends to ).
ex-ch14-03
EasyExplain operationally why Chase combining achieves at most diversity while incremental redundancy achieves . Why is IR strictly better?
CC retransmits the same codeword; IR transmits fresh parity each round.
CC has per-round rate ; IR has per-round rate (for the same long-term effective rate ).
The static DMT is decreasing: .
CC operating point
CC sends the same rate- codeword at every round. Each round contributes exponent , and the rounds are independent, so the total exponent is .
IR operating point
IR uses a mother code of rate (spread across rounds with fresh parity each round). The effective per-round rate seen by the decoder is , contributing exponent per round. Total: .
Why IR wins
is non-increasing: with equality iff (i.e., ) or iff is constant on (only at ). Hence IR's exponent exceeds CC's for all with .
Operationally: IR lowers the per-round rate to a regime where the static DMT is steeper β more diversity per round β and still collects independent fading looks. CC keeps the per-round rate high (steep regime unused) and only collects the looks.
ex-ch14-04
MediumProve that the function is non-decreasing in for any fixed .
Use the monotonicity and convexity of .
Equivalently: show grows with .
The function is the epigraph-upper-envelope of at scaled by .
Rewrite
.
$d^{*}(r)/r$ is non-increasing on $(0, r_\max)$
Claim: is non-increasing on (0, r_\max] for the piecewise-linear Zheng-Tse DMT. At any interior point (integer), the right derivative of jumps down (the curve gets flatter going right), so decreases as grows. More directly: at integer is a decreasing function of ; dividing by only accelerates the decrease.
Conclude $L \mapsto L \cdot d^{*}(r/L)$ is non-decreasing
As grows, decreases, so non-decreases (by the step above). Multiplying by : non-decreases in .
ex-ch14-05
MediumShow that the ARQ-DMT curve on a channel is strictly above the static DMT curve for all , and sketch both curves.
Static DMT: piecewise-linear through .
ARQ-DMT: on .
Static DMT values on integer corners
, , , . Piecewise-linear: slope on , slope on , slope on .
ARQ-DMT at $L = 2$
. Evaluate at : at , multiplied by 2: .
Comparison at shared $r \in (0, 3]$
at : . at : . The ARQ-DMT is strictly above the static DMT for every in the common domain.
Sketch
On a plot with on the horizontal axis and on the vertical axis: the static DMT goes from down to . The ARQ-DMT goes from down to β it is a scaled-and-stretched copy of the static DMT with both axes scaled by .
ex-ch14-06
MediumFor the channel with rounds at long-term rate , estimate how many decades of SNR the IR-HARQ scheme "wins" over the CC-HARQ scheme at target BLER . Assume both schemes are asymptotically DMT-optimal in their class.
IR: .
CC: .
To reach BLER at slope : .
IR SNR for $10^{-6}$ BLER
decades, i.e., (linear). In dB: dB.
CC SNR for $10^{-6}$ BLER
decades, i.e., (linear). In dB: dB.
SNR gap
CC needs dB more SNR than IR to hit the same BLER. This is the ARQ-DMT payoff at the asymptote; at moderate SNR the gap shrinks because of finite-SNR coding-gain offsets and sub-asymptotic slopes (the empirical diversity is at 15 dB). But the order-of-magnitude is clear: IR provides a dB advantage over CC on with at .
ex-ch14-07
MediumA MIMO 5G NR link uses HARQ rounds. The UE is moving at km/h on a carrier of GHz. HARQ RTT is ms. Does the UE get the full ARQ-DMT gain, or is the diversity compromised by channel coherence?
Coherence time: where is the Doppler shift.
Compare to : if , rounds are correlated.
Doppler shift
km/h m/s. Hz.
Coherence time
ms (loose estimate; tighter bounds give ms).
HARQ RTT vs coherence
ms ms. Consecutive HARQ rounds fall inside the coherence time β they see nearly-identical channel realisations.
Effective diversity
Without frequency hopping, the rounds are correlated and the effective number of independent realisations is . The ARQ-DMT gain is roughly β essentially the static DMT with no ARQ benefit.
Remedy
5G NR per-round frequency hopping (Β§5, Def. DPer-Round Frequency Hopping in 5G NR) deliberately hops the PRB allocation across retransmissions. If the frequency offset exceeds the coherence bandwidth (typically a few MHz in indoor scenarios), the rounds become approximately independent again, restoring the full ARQ-DMT diversity. Frequency hopping is the de facto enabler of ARQ-DMT at low mobility.
ex-ch14-08
MediumIn a 5G NR URLLC link with ms, numerology (slot length ms), and HARQ RTT ms, what is the maximum feasible ? How does the reliability compare to a MIMO eMBB link at , for the same target rate ?
Latency: .
URLLC: , eMBB: .
ARQ-DMT: .
URLLC max $L$
rounds at most.
URLLC ARQ-DMT on $4 \times 4$
Assuming MIMO: ... let me redo this. On : , , , , . Linear on : slope ; on : slope ; etc. . So .
eMBB ARQ-DMT on $4 \times 4$ with $L = 4$
.
Comparison
URLLC: ; eMBB: . The URLLC latency budget costs units of diversity exponent β a reduction. In SNR terms at target BLER : URLLC needs dB of margin above the outage threshold; eMBB needs dB. The dB difference is the "URLLC latency tax". In practice URLLC compensates with low-rate coding ( instead of ), larger antenna arrays, and PDCP duplication β all of which restore the reliability budget at the cost of air-time / equipment.
ex-ch14-09
HardProve the converse of the ARQ-DMT theorem: for any -round ARQ protocol on i.i.d. Rayleigh MIMO at long-term effective multiplexing , the block error probability is bounded below by up to a polynomial prefactor.
Bound .
Compute the exponent of via the Wishart large-deviations argument applied to i.i.d. channels.
Show the LP decomposes into independent Zheng-Tse LPs at rate each.
Fano-style lower bound
For any ARQ protocol carrying message with information across rounds, Fano's inequality says , where is the -round cumulative mutual information. Rearranging, at large block length.
Outage exponent via Wishart LD
The -round outage is where . By the Wishart large-deviations argument of Ch. 12 applied to each independent round, the outage event factorises into independent eigenvalue-exponent LPs.
LP decomposition
Reparametrise per round . The outage constraint becomes . By symmetry / convexity of the static LP's objective (weight vector ), the joint LP attains its minimum when all rounds share the same per-round multiplexing , i.e., for each . The per-round LP value is .
Wait β reconcile with $L \cdot d^{*}(r/L)$
The above gives , but the theorem claims . The discrepancy is the rate convention (see β The Rate Convention: Per-Round vs Long-Term). If denotes the per-round multiplexing gain, then . If denotes the long-term effective multiplexing (the convention of El Gamal-Caire-Damen), then the per-round rate is and the exponent is . Both statements are correct; only the parametrisation differs.
Converse inequality
With the long-term convention: . This matches the upper bound achieved by random Gaussian codes (Thm. TARQ-DMT (El Gamal-Caire-Damen 2006) achievability), so the ARQ-DMT is tight.
ex-ch14-10
HardShow that IR-LAST codes (Def. DIncremental-Redundancy Lattice Space-Time (IR-LAST) Codes) achieve the ARQ-DMT. Sketch the three key ingredients: (i) CDA nonvanishing determinant, (ii) MMSE-GDFE decoder, (iii) common random dither.
Use the per-round PEP bound for CDA codes (Elia et al. 2006).
The MMSE-GDFE lattice decoder achieves the DMT exponent (El Gamal-Caire-Damen 2004).
Common dither matches the codeword distribution to the Gaussian ensemble for an average PEP argument.
CDA NVD per round
Using the CDA-generator construction, the codeword-difference matrix in round satisfies uniformly in SNR. Substituting into the Chernoff PEP bound gives per-round exponent in the ARQ-DMT rate convention.
MMSE-GDFE exponent
By Thm. 2 of El Gamal-Caire-Damen 2004 (Ch. 17), the MMSE-GDFE lattice decoder achieves the same DMT exponent as the joint ML decoder. Hence the per-round IR-LAST exponent matches the Gaussian-random-code exponent .
Cross-round product
With common random dither, the -round PEP averages over the dither and factorises into independent per-round PEPs (via independence of ). The joint exponent is the sum: .
Combine
matches the ARQ-DMT upper bound, so IR-LAST achieves it.
ex-ch14-11
MediumA BLER-vs-SNR curve for a 5G NR LDPC-IR-HARQ link on MIMO shows a slope of at BLER with retransmissions. The long-term effective rate is . Is the scheme operating near the ARQ-DMT asymptote? What is the finite-SNR gap?
Theoretical ARQ-DMT: on .
.
Theoretical slope: .
Compute theoretical slope
on : interpolate and at : . .
Compare to empirical slope
Empirical slope ; theoretical slope . The ratio is .
Interpretation
The empirical slope is of the asymptotic slope β a sizable finite-SNR gap. Typical for BLER in the range on at moderate SNR. The remaining 46% of asymptotic diversity materialises only above β dB (the BLER curve steepens as SNR grows, approaching slope 13 in the deep tail).
Design takeaway
For a BLER target of (URLLC) at this operating point, the system needs β dB of SNR margin, but the empirical slope tells us we must budget on the shallower slope at the target BLER, not the asymptotic slope. Link-level simulation (not just the ARQ-DMT formula) is essential for design sizing.
ex-ch14-12
HardDerive the effective throughput of an IR-HARQ scheme at per-round rate and rounds. Express it in terms of the per-round outage probabilities .
Let be the event that decoding succeeds for the first time at round .
.
.
Success and failure events
"first success at round " , where . .
Total success probability
(success occurs iff the -round outage does not).
Expected rounds used
(if all rounds fail, still rounds used). Using the identity (Abel summation):
Effective throughput
Information bits per block: (if decoded). Channel uses per block: . Effective rate: At high SNR, all so . At low SNR, so .
ex-ch14-13
MediumThe static DMT in Ch. 12 required block length . What is the analogous condition for the per-round block length in the ARQ-DMT?
Each ARQ round is itself a static DMT problem with block length .
For the per-round DMT to match Zheng-Tse, we need .
Per-round static DMT requirement
Each ARQ round uses channel uses. The per-round outage exponent is the static DMT , which requires the per-round block length (by Thm. 9.1 of Tse-Viswanath 2005, equivalently the Zheng-Tse theorem's block- length condition).
What breaks if $N < n_t + n_r - 1$
The per-round outage exponent truncates: at integer corners (Ch. 12 Β§5). The ARQ-DMT formula becomes , which is strictly less than whenever at the operating .
Operational consequence
In high-mobility mmWave scenarios, per-round block length can be as short as 1β2 OFDM symbols. This truncates both the static and ARQ-DMT curves. A system running HARQ rounds with on MIMO achieves much less than at ; more like β a factor of 4 loss from block-length truncation.
ex-ch14-14
MediumWhy does CC-HARQ degenerate to a single-shot scheme at SNR linear (not dB)? Sketch the mutual-information curve of a CC-HARQ round as a function of SNR.
CC-HARQ mutual information: the combined channel has effective SNR .
Above capacity, additional SNR wastes.
Combined CC SNR
After rounds of CC, the effective SNR is (SNR combining on a single symbol replicated times).
Capacity ceiling
The single-round capacity at effective SNR is at high . The per-round rate is typically chosen at , so the "extra" margin is wasted β the decoder could already decode at round 1 with high probability.
Degenerate regime
At very high SNR, and the ACK is emitted on round 1. CC never transmits further rounds; it degenerates to a single-shot scheme with rate . The diversity benefit of CC over single-shot is thus only at moderate SNR where round 1 fails with non-negligible probability.
Contrast with IR
IR is different: its per-round rate is , so even at very high SNR the cumulative rate after rounds is β exactly the target. IR "uses up" the available SNR productively across rounds; CC doesn't.
ex-ch14-15
HardConsider a MIMO system running IR-HARQ at rounds, , and per-round block length . Compute the expected latency (rounds used) at SNR levels dB, given the empirical outage probabilities (at dB as a baseline).
Expected rounds = β from Ex. 12.
Use the baseline probabilities scaled by the DMT exponents at each SNR (slope ).
Baseline at 5 dB
at . Expected rounds .
Extrapolation at 10 dB (5 dB higher)
Each . On : , , , . Diversity exponents per round: . Per-5-dB decay factors: , i.e., . Scaled: . Expected rounds .
Continue for higher SNR
At 15 dB (10 dB above baseline): outages decay further by factor . Round 1 dominates at these SNRs; expected rounds . At 20 dB: round 1 outage ; expected rounds .
Latency summary
SNR: 5 dB 2.1 rounds (16 ms); 10 dB 1.19 rounds (10 ms); 15 dB 1.02 rounds (8.2 ms); 20 dB 1.006 rounds (~8 ms). The expected latency collapses rapidly above the outage threshold; this is exactly why the scheme is called "hybrid ARQ" β at high SNR it behaves like a one-shot code, at low SNR like an -shot code.
ex-ch14-16
MediumExplain why common random dithering is essential for IR-LAST to achieve the ARQ-DMT. What would go wrong without it?
Structured algebraic codes have worst-case codeword differences.
The PEP bound involves the determinant of a specific difference matrix.
Dithering averages over a uniform distribution on the Voronoi region.
Deterministic codes have worst-case PEP
Without dithering, a CDA lattice code transmits a deterministic codeword given the information bits. The PEP for a specific codeword pair depends on the algebraic determinant of their difference. For the worst-case pair, this determinant is the NVD constant β a lower bound, but not tight at finite SNR.
Random code averages over the ensemble
The Gaussian random-code ensemble has a distribution over codewords, and the ensemble-average PEP matches the Gallager-exponent formula. This is the achievability argument of Β§2.
Dithering emulates the ensemble
The common random dither makes the transmitted codeword uniformly distributed over the Voronoi region of the shaping lattice. The average PEP over the dither matches (asymptotically) the Gaussian-ensemble PEP, restoring the random-coding achievability.
What breaks without dither
Without the dither, the IR-LAST PEP is bounded by the worst-case codeword-pair's bound, which does not quite match the Gaussian-random-code bound at every SNR. The asymptotic exponent is still correct (the NVD constant dominates), but the coding gain is worse and the finite-SNR performance degrades. Moreover, the joint PEP across rounds no longer factorises cleanly, so the accounting can fail at non-integer rates.
ex-ch14-17
HardProve that the -round outage event is convex in the joint eigenvalue-exponent space , where .
Write the outage event as a linear constraint in .
The function is convex (a piecewise linear max).
Sum of convex functions is convex.
Outage constraint
, i.e., the sublevel set of the convex function below level .
Convexity of $(1 - \alpha)^+$
is convex in (max of two linear functions). The sum over is convex.
Outage event is convex
The sublevel set of a convex function is convex. Hence is a convex subset of .
Implication
The LP over a convex set with linear objective has a vertex-optimal solution, which is attained at corners β the per-round equal-allocation vertices. This is exactly the achievability argument we used to derive .
ex-ch14-18
MediumA 5G NR URLLC link at (mini-slot HARQ with RTT ms) targets reliability at latency budget ms. What is the maximum , and what diversity gain is feasible?
Max : .
Compute for the feasible on a channel at .
Max feasible $L$
rounds.
Diversity for $L = 2, r = 0.5$ on $4 \times 4$
on : (continuous formula); actually, piecewise interpolation between and gives . .
SNR for $10^{-6}$ BLER
decades dB.
Interpretation
On a URLLC link at with rounds, the system needs only dB of SNR margin above the outage threshold to hit reliability β a very modest requirement. The ARQ-DMT formula gives a slope of 28.5, which is very steep; even a half-round HARQ budget is enormously valuable. This is why 5G NR URLLC relies heavily on spatial diversity (large antenna arrays) β to get the static DMT exponent as large as possible, so that even or yields adequate reliability.
ex-ch14-19
MediumCompute the long-term effective rate of the effective-throughput formula from Ex. 12 in the limit (i) (ii) . Interpret.
at high SNR for any .
at low SNR for .
High SNR limit
for all . Numerator: . Denominator: . Hence β the system behaves as if it transmits successfully at the first round every time, and the per-block throughput is the cumulative rate across the full block.
Low SNR limit
for all . Numerator: . Denominator: . Hence β at low SNR, the system spends all rounds per block and still fails, so the throughput collapses.
Transition regime
Between the two limits, has a sigmoid-like rise vs SNR. The steepness of the rise is governed by the ARQ-DMT exponent: high and high give steeper transitions. Interactive plot π5G NR HARQ-IR Throughput Envelope illustrates this.
ex-ch14-20
EasyDescribe briefly, in your own words, why the El Gamal-Caire-Damen 2006 paper is considered a landmark in MIMO information theory. What new dimension did it add to the DMT picture?
Compare to the Zheng-Tse 2003 paper.
Think about what real systems actually do (retransmit) vs what Ch. 12 analyses (one-shot).
Pre-2006 state of the art
Zheng-Tse (2003) gave the static DMT for a single- shot MIMO channel. Retransmission / ARQ was studied as a throughput mechanism (Wozencraft-Jacobs tradition, Caire-Tuninetti 2001 for AWGN) but not as a resource that reshapes the fundamental tradeoff curve.
What the paper added
El Gamal, Caire, and Damen introduced the delay dimension as a third axis of the DMT. Their theorem showed that ARQ is not just a throughput trick but a genuine information-theoretic resource that multiplies the diversity exponent at fixed rate. They also constructed the first explicit ARQ-DMT-optimal codes (IR-LAST).
Operational impact
The ARQ-DMT theorem underpins HARQ design in every modern cellular standard. LTE Rel-8 (2009) and 5G NR Rel-15 (2018) both use LDPC + circular-buffer rate matching + redundancy versions β the engineering realisation of the information- theoretic IR-HARQ analysed by El Gamal-Caire-Damen. The paper is a textbook example of how a clean theorem shapes standards a decade later.