Ferkans — Interactive Telecom Tutor

From a Sum to a Matrix

The input-output relation of Section 2 can be written as $\mathbf{y}_{DD} = \mathbf{H}_{DD}\,\mathbf{x}_{DD} + \mathbf{w}_{DD}$ , where $\mathbf{H}_{DD} \in \mathbb{C}^{MN \times MN}$ is the DD channel matrix. This matrix form is what every linear detector (MMSE, ZF, matched filtering) takes as input, so we now write it out explicitly.

The point is that $\mathbf{H}_{DD}$ is not a generic $MN \times MN$ complex matrix — it has two structural properties that detection algorithms exploit: sparsity (at most $P \cdot MN$ nonzero entries, not $M^2 N^2$ ) and block circulant structure (a consequence of the doubly-circular 2D convolution).

Definition:
Vectorized DD Grid

The DD grid matrix $X_{DD}[\ell, k]$ of size $M \times N$ is vectorized column-by-column: $\mathbf{x}_{DD} \;=\; \text{vec}(X_{DD}) \;=\; \left[X_{DD}[0, 0], X_{DD}[1, 0], \ldots, X_{DD}[M-1, N-1]\right]^T \in \mathbb{C}^{MN}.$ Similarly $\mathbf{y}_{DD} = \text{vec}(Y_{DD})$ and $\mathbf{w}_{DD} = \text{vec}(W_{DD})$ . The index mapping is $(\ell, k) \leftrightarrow j = k\,M + \ell$ for $\ell \in \{0, \ldots, M-1\}$ and $k \in \{0, \ldots, N-1\}$ .

Theorem: Structure of the DD Channel Matrix

With the column-major vectorization of the DD grid, the channel matrix $\mathbf{H}_{DD} \in \mathbb{C}^{MN \times MN}$ is a sum of $P$ weighted shift-phase matrices: $\mathbf{H}_{DD} \;=\; \sum_{i=1}^{P} h_i\,(\boldsymbol{\Pi}_N^{k_i}\,\boldsymbol{\Delta}_N^{\ell_i}) \otimes \boldsymbol{\Pi}_M^{\ell_i},$ where $\otimes$ is the Kronecker product, $\boldsymbol{\Pi}_K$ is the $K \times K$ circular-shift (forward) permutation matrix, and $\boldsymbol{\Delta}_N = \text{diag}(1, e^{j 2\pi/N}, \ldots, e^{j 2\pi(N-1)/N})$ is the diagonal modulation matrix encoding the Zak twist.

The matrix is:

Sparse: exactly $P \cdot MN$ non-zero entries out of $M^2 N^2$ .
Block circulant with circulant blocks (for integer-Doppler paths).
Diagonalized by the 2D DFT: $\mathbf{H}_{DD} = (\mathbf{F}_N \otimes \mathbf{F}_M)^H\,\boldsymbol{\Lambda}\,(\mathbf{F}_N \otimes \mathbf{F}_M)$ with $\boldsymbol{\Lambda}$ diagonal — this is the ISFFT/SFFT structure of Chapter 3.

The Kronecker product decomposes $\mathbf{H}_{DD}$ into a "Doppler part" $\boldsymbol{\Pi}_N^{k_i}\boldsymbol{\Delta}_N^{\ell_i}$ acting on the $N$ -dimensional Doppler axis, and a "delay part" $\boldsymbol{\Pi}_M^{\ell_i}$ acting on the $M$ -dimensional delay axis. Each axis is shifted circularly by the path index; the Doppler part also carries the Zak-twist phase because the delay shift crosses block boundaries of length $M$ in the vectorized representation.

Proof

Per-path action

From Theorem TDiscrete DD Input-Output Relation (Integer Doppler), path $i$ maps $X_{DD}[\ell, k] \mapsto h_i\,X_{DD}[(\ell - \ell_i)\bmod M,\,(k - k_i)\bmod N]$ times the Zak-twist phase $e^{j 2\pi \alpha_i(\ell, k)}$ .

Vectorize

The $\ell$ -shift corresponds to multiplying $\text{vec}(X_{DD})$ by the Kronecker matrix $\mathbf{I}_N \otimes \boldsymbol{\Pi}_M^{\ell_i}$ . The $k$ -shift corresponds to multiplying by $\boldsymbol{\Pi}_N^{k_i} \otimes \mathbf{I}_M$ . Combined: $(\boldsymbol{\Pi}_N^{k_i} \otimes \boldsymbol{\Pi}_M^{\ell_i})$ .

Include the Zak twist

The phase $e^{j 2\pi \alpha_i(\ell, k)}$ depends only on whether the delay shift wraps, and across $N$ blocks. It combines into $\boldsymbol{\Delta}_N^{\ell_i}$ acting on the Doppler axis. Final: $\boldsymbol{\Pi}_N^{k_i}\boldsymbol{\Delta}_N^{\ell_i}$ for Doppler, $\boldsymbol{\Pi}_M^{\ell_i}$ for delay.

Sum over paths

$\mathbf{H}_{DD} = \sum_i h_i\,(\boldsymbol{\Pi}_N^{k_i}\boldsymbol{\Delta}_N^{\ell_i}) \otimes \boldsymbol{\Pi}_M^{\ell_i}$ , confirming the claimed form.

Diagonalization

Each Kronecker shift $(\boldsymbol{\Pi}_N^{k_i}\boldsymbol{\Delta}_N^{\ell_i}) \otimes \boldsymbol{\Pi}_M^{\ell_i}$ is diagonalized by the 2D DFT $\mathbf{F}_N \otimes \mathbf{F}_M$ (since each factor is diagonalized by its respective DFT). The sum is therefore also diagonalized — this diagonalization is the ISFFT of Chapter 3. $\blacksquare$

,

Sparsity Pattern of the DD Channel Matrix — Sparsity pattern of $\mathbf{H}_{DD}$ for an $M = 16, N = 16$ grid with $P = 4$ paths. Each path contributes a diagonal band of $MN = 256$ non-zeros, for a total of $P \cdot MN = 1024$ non-zeros out of $(MN)^2 = 65{,}536$ — a density of $P/(MN) = 1.6\%$ . For large frames ( $M = 512, N = 16$ , $P = 8$ ) the density is $\sim 0.1\%$ .

DD Channel Matrix Sparsity vs Channel Parameters

Visualize $|\mathbf{H}_{DD}[j, j']|$ as a heatmap for a random $P$ -tap channel. Observe: (i) the matrix is sparse with $P$ diagonal bands, (ii) the bands correspond to path $(\ell_i, k_i)$ offsets, (iii) sparsity density equals $P / (MN)$ . Vary $P$ and watch the density scale linearly.

Parameters

Delay bins

M

16

Doppler bins

N

8

Number of paths

P

4

l_{\max}

3

k_{\max}

1

Seed7

Example: Explicit $(M, N) = (4, 2)$ Channel Matrix

For $M = 4, N = 2$ (so the DD grid has 8 cells), construct the DD channel matrix for a single path $(h_1, \ell_1, k_1) = (1, 1, 0)$ . Ignore the Zak twist (since $\ell_1 < M$ and no boundary crossing for this simple example).

Solution

Per-axis matrices

$\boldsymbol{\Pi}_M^1$ is the $4 \times 4$ circular shift matrix: $\boldsymbol{\Pi}_4^1 = \begin{pmatrix}0&0&0&1\\1&0&0&0\\0&1&0&0\\0&0&1&0\end{pmatrix}$ . For Doppler, $\boldsymbol{\Pi}_2^0\boldsymbol{\Delta}_2^1 = \boldsymbol{\Delta}_2 = \text{diag}(1, -1)$ .

Kronecker product

$\mathbf{H}_{DD} = h_1 \cdot (\text{diag}(1, -1)) \otimes \boldsymbol{\Pi}_4$ $= 1 \cdot \begin{pmatrix}\boldsymbol{\Pi}_4 & \mathbf{0}\\ \mathbf{0} & -\boldsymbol{\Pi}_4\end{pmatrix}$ . This is an $8 \times 8$ block-diagonal matrix with $\boldsymbol{\Pi}_4$ and $-\boldsymbol{\Pi}_4$ blocks.

Sparsity

$\mathbf{H}_{DD}$ has exactly 8 non-zeros (one per row) out of 64 entries — density $12.5\%$ , matching $P / (MN) = 1/8$ . As $M, N$ grow the density drops quickly.

How Detectors Exploit This Structure

The structured form $\mathbf{H}_{DD} = \sum_i h_i (\boldsymbol{\Pi}_N^{k_i}\boldsymbol{\Delta}_N^{\ell_i}) \otimes \boldsymbol{\Pi}_M^{\ell_i}$ is exactly what enables efficient OTFS detection (Chapter 8):

Matched filter: $\mathbf{H}_{DD}^{H}\,\mathbf{y}$ can be computed as $P$ sparse back-projections, each costing $O(MN)$ — total $O(PMN)$ .
MMSE: $(\mathbf{H}_{DD}^{H}\mathbf{H}_{DD} + \sigma^2\mathbf{I})^{-1}$ is itself block-circulant, diagonalizable by the 2D DFT. The inverse can be computed in $O(MN \log(MN))$ via the SFFT.
Message passing: The factor graph has $O(MN)$ variable nodes and $O(MN)$ factor nodes, with each factor having at most $P$ incident variables. Belief-propagation iterations cost $O(PMN)$ per sweep.

All three scale linearly (up to log factors) with the grid size — a direct consequence of the sparsity. A dense $MN \times MN$ matrix would make OTFS impractical at typical 5G frame sizes ( $MN \sim 10^4$ ); the structure brings it down to realtime.

Key Takeaway

The DD channel matrix is sparse and structured — this is the enabler. Each of the $P$ physical paths contributes a Kronecker product of circular-shift and diagonal-phase matrices. The union is sparse with density $P/(MN) \ll 1$ , block-circulant with circulant blocks, and diagonalized by the 2D DFT. Every practical OTFS detector (matched filter, MMSE, message passing) exploits at least one of these three properties. Without them, detection on an $MN \geq 10^4$ grid would be computationally infeasible.

Computational Complexity: Dense vs Structured DD Matrix

Operation	Dense matrix	Sparse DD structure
Matrix-vector product $\mathbf{H}_{DD}\mathbf{x}$	$O(M^2 N^2)$	$O(P \cdot MN)$
Matched filter $\mathbf{H}_{DD}^{H}\mathbf{y}$	$O(M^2 N^2)$	$O(P \cdot MN)$
Solve $\mathbf{H}_{DD}\mathbf{x} = \mathbf{y}$ (direct)	$O((MN)^3)$	$O(MN \log(MN))$ via 2D FFT
MMSE: $(\mathbf{H}_{DD}^{H}\mathbf{H}_{DD} + \sigma^2\mathbf{I})^{-1}\mathbf{y}$	$O((MN)^3)$	$O(MN \log(MN))$
Storage	$O((MN)^2)$	$O(P)$ parameters

The DD Channel Matrix