Exercises

$|\mathcal{X}|^{MN} = 4^{100} = (4^{10})^{10} = (10^6)^{10} = 10^{60}$. Precisely: $10^{60.2}$.

$10^{60}$ candidates per frame. With $10^{18}$ ops/sec (EFLOPS machine), it would take $10^{42}$ seconds per frame — longer than the age of the universe. ML is infeasible.

2D FFT: $O(MN\log(MN)) = 10^4 \cdot 13.3 \approx 1.3 \times 10^5$ ops. Element-wise: $O(MN) = 10^4$ ops. Total: $\sim 2.7 \times 10^5$ ops.

The two 2D FFTs dominate. Element-wise is a tenth of the FFT cost. MMSE is essentially "the cost of two 2D FFTs" — equivalent to the cost of the OTFS demodulator itself.

$\hat{\mathbf{x}} = (\mathbf{H}_{DD}^{H}\mathbf{H}_{DD} + \sigma^2\mathbf{I})^{-1}\mathbf{H}_{DD}^{H}\mathbf{y}$.

$\mathbf{H}_{DD}^{H}\mathbf{H}_{DD} = \mathbf{F}^H|\boldsymbol{\Lambda}|^2\mathbf{F}$. $\mathbf{I} = \mathbf{F}^H\mathbf{F}$. So $\mathbf{H}_{DD}^{H}\mathbf{H}_{DD} + \sigma^2\mathbf{I} = \mathbf{F}^H(|\boldsymbol{\Lambda}|^2 + \sigma^2)\mathbf{F}$.

Its inverse is $\mathbf{F}^H(|\boldsymbol{\Lambda}|^2 + \sigma^2)^{-1}\mathbf{F}$, where the inverse in parentheses is element-wise.

$\hat{\mathbf{x}} = \mathbf{F}^H(|\boldsymbol{\Lambda}|^2 + \sigma^2)^{-1}\mathbf{F} \cdot \mathbf{F}^H\boldsymbol{\Lambda}^H\mathbf{F}\mathbf{y} = \mathbf{F}^H\boldsymbol{\Lambda}^H/(|\boldsymbol{\Lambda}|^2 + \sigma^2) \mathbf{F}\mathbf{y}$. $\blacksquare$

$\mathbf{H}_{DD} = h_1\,\boldsymbol{\Pi}_N^{k_1}\boldsymbol{\Delta}_N^{\ell_1} \otimes \boldsymbol{\Pi}_M^{\ell_1}$ — a permutation-plus-diagonal times $h_1$. Its eigenvalues are $h_1 \cdot (\text{unit roots of unity})$.

$|\boldsymbol{\Lambda}_{n, m}| = |h_1|$ for all $(n, m)$ — constant.

Element-wise multiply by $h_1^*/(|h_1|^2 + \sigma^2/\sigma_x^2)$. Same for all cells.

Single-path channel: all DD cells experience the same SNR. MMSE is uniformly Wiener — BER is the same across cells. Multi-path case has cell-dependent $|\boldsymbol{\Lambda}|$, creating per-cell SINR variability.

2D FFT + iFFT: $2 \cdot MN\log(MN) = 2 \cdot 4096 \cdot 12 = 10^5$ ops. Sparse multiply ($P\,MN$): $10 \cdot 4096 = 4 \times 10^4$ ops. Soft-quantize ($|\mathcal{X}| = 4$, QPSK): $4 MN = 1.6 \times 10^4$ ops. Per iteration: $\sim 1.5 \times 10^5$ ops.

5 iterations: $7.5 \times 10^5$ ops.

MMSE alone: $1.5 \times 10^5$ ops (one "iteration"). LCD (5 iter) = 5× MMSE = $7.5 \times 10^5$ ops. MP (10 iter): $P \cdot MN \cdot 10 = 4 \times 10^5$ ops. LCD and MP are in the same ballpark; MMSE is 3-5× faster. LCD typically chosen for predictable latency.

$\sum_i |h_i|^2 =$ sum of $P$ iid exponential$(P)$ = $\chi^2_{2P}/P$. Mean: $P/P = 1$. Variance of total: $1/P$.

$|\lambda_{n, m}|^2 = |\sum_i h_i\,e^{j\phi_i}|^2$, a sum of $P$ complex $\mathcal{CN}(0, 1/P)$ variables: $\lambda_{n, m} \sim \mathcal{CN}(0, 1)$. $|\lambda|^2 \sim$ exponential with mean 1.

$\mathrm{SINR}_{\text{MMSE}} = |\lambda|^2/(\sigma^2/\sigma_x^2)$. Expected value: $1/\mathrm{SNR}$. Same as single-path — but with Rayleigh fading (diversity 1 regardless of $P$).

MMSE sees an effective single-tap Rayleigh channel, regardless of $P$. The "diversity $P$" advantage of OTFS is entirely in the detector's nonlinear processing (MP or LCD iterations), not in the channel's post-MMSE statistics.

$p(y | \{x_j\}) \propto \exp(-|y - \sum_j h_j x_j|^2/\sigma^2)$.

$\mu_{y \to v_i}(x_i) = \int \prod_{j \neq i} \mu_{v_j \to y}(x_j) \cdot p(y | \{x_j\})\,dx_j$. Each message is Gaussian: $\mu_{v_j \to y}(x_j) = \mathcal{CN}(\bar{\mu}_j, \sigma_j^2)$.

The integrand is Gaussian in $\{x_j\}_{j \neq i}$; integrating gives another Gaussian. The result is $\mu_{y \to v_i}(x_i) \propto \mathcal{CN}(\tilde{\mu}_i, \tilde{\sigma}_i^2)$ with $\tilde{\mu}_i = (y - \sum_{j \neq i} h_j \bar{\mu}_j)/h_i$ $\tilde{\sigma}_i^2 = (\sigma^2 + \sum_{j \neq i} |h_j|^2\sigma_j^2)/|h_i|^2$.

The factor says: "Given the messages from my other $P - 1$ neighbors, the variable $v_i$ should be $\tilde{\mu}_i$ with uncertainty $\tilde{\sigma}_i^2$." The $v_i$ message aggregates this with priors from its other incident factors. $\blacksquare$

At fixed point, $\mu_{v_i \to y_k} = \mu_{v_i \to y_k'}$ for all incident factors. Equivalently, the posterior at each variable equals the product of all factor messages.

The converged update becomes $\mathbf{x}^{(t)} = \mathcal{T}_\tau(\mathbf{z}^{(t)} + \mathbf{H}_{DD}^{T}(\mathbf{y} - \mathbf{H}_{DD}\mathbf{x}^{(t-1)}))$, where $\mathcal{T}_\tau$ is a soft-thresholding (or QAM-mapping) operator and $\mathbf{z}^{(t)}$ is the "Onsager" correction term accounting for self-feedback.

MP is essentially AMP (approximate message passing) specialized to the DD-channel structure. AMP has been extensively studied in compressive sensing and MIMO detection; OTFS detection is a special case with structured (sparse) matrices.

Recognizing this connection gives access to AMP's convergence analysis (state evolution) and its asymptotic optimality results. The OTFS-specific convergence bounds in Raviteja et al. (2018) are AMP results specialized to the DD factor graph.

$\mathrm{BER}(\mathrm{SNR}) \propto 1/\mathrm{SNR}^P$. $\mathrm{BER}(10\,\text{dB})/\mathrm{BER}(15\,\text{dB}) = (10^{1.5}/10)^P = 10^{0.5 P} = 10^{4}$.

$\mathrm{BER}(10\,\text{dB}) = 10^4 \cdot 10^{-4} = 1$ — but BER is bounded by 1/2 for binary symbols, so the extrapolation breaks down.

The simple $1/\mathrm{SNR}^P$ scaling holds in the high-SNR regime. At low SNR, the BER saturates. The real $\mathrm{BER}(10\,\text{dB})$ is probably in the $0.01$–$0.1$ range — detector is noise-limited, not diversity-limited.

Diversity only helps in the high-SNR regime where BER is small. At low SNR, outer coding is essential (not just detector diversity). This is why IDD is the standard for low-SNR operation.

MP's Gaussian messages retain full information. LCD's soft- quantization reduces messages to QAM expected values, losing some uncertainty information between iterations.

At high SNR, both methods converge to ML. Gap $\to 0$. The asymptotic "diversity $P$" is identical for both.

At $\mathrm{SNR} = 15$ dB, MP is typically 0.5 dB better than LCD. Below $10$ dB, gap can be 1-2 dB.

For high-SNR operation (eMBB at 10+ dB), LCD's simpler structure makes it the preferred choice. For low-SNR operation (mMTC at 0 dB), MP offers measurable gains. In practice, both are accompanied by outer LDPC coding which largely closes the gap via iterative decoding.

Pairwise error probability at SNR $\rho$: $\mathrm{PEP}(\rho) = \Pr(\|\mathbf{y} - \mathbf{H}\hat{\mathbf{x}}\|^2 < \|\mathbf{y} - \mathbf{H}\mathbf{x}\|^2)$.

$\mathrm{PEP}|\mathbf{h} = Q(\sqrt{\|\mathbf{H}(\mathbf{x} - \hat{\mathbf{x}})\|^2/(2\sigma^2)})$. Depends on $\|\mathbf{H}\Delta\mathbf{x}\|^2 = \sum_{\ell, k} |\sum_i h_i\,(\text{shift})|^2$, which is $|\boldsymbol{\Lambda}|^2$-weighted in the 2D DFT basis.

For $P$ iid paths, $\mathbb{E}|\mathbf{H}\Delta\mathbf{x}|^2 \propto \sum_i |h_i|^2$ is chi-squared with $2P$ DoF. Averaging $Q(\cdot)$ over this distribution: $\mathrm{PEP} \sim 1/\rho^P$ at large $\rho$.

BER $\leq (|\mathcal{X}|^{MN} - 1) \cdot \mathrm{PEP}$. Since the exponential factor in $\mathrm{PEP}$ dominates for large $\rho$, BER $\sim \rho^{-P}$.

At convergence, MP's decisions match ML's up to tie-breaking effects. Asymptotic BER slope is the same $P$. $\blacksquare$

LCD (3 inner iter): $3 \cdot MN \log(MN) = 3 \cdot 4096 \cdot 12 \approx 1.5 \times 10^5$ ops. LDPC (5 inner iter on a rate-1/2 code): $\sim 2 \cdot MN \cdot 5 = 4 \times 10^4$ ops (per-bit variable-to-check messages). Total per outer iter: $\sim 2 \times 10^5$ ops.

$3 \cdot 2 \times 10^5 = 6 \times 10^5$ ops per frame.

$\sim 10^6$ ops/frame total including the IDD. At 100 frames/sec, $10^8$ ops/sec — well within a modern SoC. IDD is realtime-feasible for 5G NR.

Each DD cell has effective gain $\lambda_{n, m} \sim \mathcal{CN}(0, 1)$ (since total channel power is 1). Per-cell capacity: $\mathbb{E}[\log_2(1 + |\lambda|^2 \mathrm{SNR})]$.

Total frame capacity: $MN \cdot \mathbb{E}[\log_2(1 + |\lambda|^2 \mathrm{SNR})]$. Per-cell, per-DoF: $\mathbb{E}[\log_2(1 + |\lambda|^2 \mathrm{SNR})]$.

Single-tap Rayleigh: same formula. Identical capacity.

OTFS does not improve ergodic capacity over OFDM. Both have the same total rate on the same channel. What OTFS improves is outage capacity — the fraction of realizations with rate above a threshold. For rare deep fades, OTFS's diversity-$P$ reliability wins without changing the average.

$4^{20} = 10^{12}$ candidates.

At $\mathrm{SNR} = 20$ dB, only a small fraction of candidates are within the sphere. Typical reduction: $10^5$–$10^6$ candidates (from empirical simulation).

Sphere decoding is feasible at $MN = 20$ but not $MN = 1000$. For OTFS, it is a niche choice — OTFS frames are larger than the sphere-decoding sweet spot.

$\hat{\mathbf{x}}_{\text{MAP}} = \arg\max_{\mathbf{x}} p(\mathbf{y}|\mathbf{x}) p(\mathbf{x})$. With a data prior $p(\mathbf{x})$ (e.g., encoding constraints), the MAP problem is a constrained ML.

Use $p(\mathbf{x})$ as a prior message at variable nodes. Per-variable message: $\prod_{y \in \mathcal{N}(x)} \mu_{y \to x}(x) \cdot p(x)$. Convergence conditions depend on code structure.

For a rate-1/2 LDPC outer code with MAP detection, BER typically improves by 1-2 dB over LCD at moderate SNR. At low SNR, the MAP benefit is larger ($\sim 3$ dB) because the prior corrects cells that the channel alone cannot resolve.

MAP detection integrated with LDPC decoding is $O(T_{\text{iter}}\,MN\log(MN))$, same as IDD. The difference is that MAP uses the marginal posterior at each bit, while IDD uses the extrinsic LLR — EXIT analysis shows that the two converge to the same fixed point asymptotically.

A fully joint MAP detector-decoder that exploits both the DD channel sparsity AND the LDPC graph structure remains an active research topic. Current implementations use the simpler IDD loop (detector and decoder operate independently with message exchange), which is sub-optimal but close.

Treating each LLR as a noisy observation of the true bit (true bit $= +1/-1$, noise $= 1/\lambda$ per Gaussian approximation): $\lambda^{\text{combined}} = \lambda^{\text{TF}} + \lambda^{\text{DD}}$ (independent observations combine additively in log-likelihood).

If the LLR magnitudes are unreliable (possibly biased), reweight: $\lambda^{\text{combined}} = w_{TF}\lambda^{\text{TF}} + w_{DD}\lambda^{\text{DD}}$ with $w_{TF}/w_{DD} \propto (\sigma^2_{TF})^{-1}/(\sigma^2_{DD})^{-1}$.

Cross-domain combination preserves the information from both detectors, weighted by their reliability. When one domain fails (e.g., TF in a deep fade), its LLR is suppressed by the small weight, and the other domain carries the decision.