Ferkans — Interactive Telecom Tutor

From the Continuum to the Grid

The continuous 2D convolution is elegant but does not tell a receiver what to compute. Practical OTFS works on the discrete DD grid $(M, N)$ defined in Chapter 3. In this section we project the continuous input-output relation onto that grid and obtain the discrete OTFS input-output equation that every detector in the literature targets.

The key quantity we will derive is the integer-Doppler input-output relation: $Y_{DD}[\ell, k] \;=\; \sum_{i=1}^{P} h_i\,X_{DD}[(\ell - \ell_i) \bmod M, (k - k_i) \bmod N] \;+\; W_{DD}[\ell, k].$ This is a sparse 2D circular convolution — $P$ taps acting on a data grid. The equation sets the stage for the channel matrix of Section 3 and for the detectors of Chapters 7-8.

Definition:
Discrete Path Indices

Given a continuous path with delay $\tau_i$ and Doppler $\nu_i$ , its discrete indices on the $(M, N)$ DD grid are $\ell_i \;=\; \tau_i \cdot W, \qquad k_i \;=\; \nu_i \cdot T,$ where $W = M\Delta f$ is the bandwidth and $T = N T_s$ is the frame duration. We assume throughout this section that $\ell_i, k_i$ are integers — the integer-delay, integer-Doppler case. Fractional offsets are postponed to Chapter 10.

The maximum indices over the channel are $l_{\max} = \lceil \tau_{\max} W \rceil, \qquad k_{\max} = \lceil f_D T \rceil.$ Both are bounded, and for realistic systems $l_{\max} \ll M$ and $k_{\max} \ll N$ — this is where the channel's sparsity comes from.

Theorem: Discrete DD Input-Output Relation (Integer Doppler)

Assume integer delay-Doppler paths $\ell_i, k_i \in \mathbb{Z}$ . Let $X_{DD}[\ell, k]$ be the QAM data grid of size $M \times N$ , and let $Y_{DD}[\ell, k]$ be the received DD grid after OTFS demodulation (Chapter 6). Then $Y_{DD}[\ell, k] \;=\; \sum_{i=1}^{P} h_i\,e^{j 2\pi \alpha_i(\ell, k)}\,X_{DD}\!\left[(\ell - \ell_i) \bmod M,\,(k - k_i) \bmod N\right] \;+\; W_{DD}[\ell, k],$ where the per-path phase is $\alpha_i(\ell, k) = (\ell - \ell_i)\,k_i / (MN) - k k_i / (MN)$ (or an equivalent grid-dependent phase from the Zak twist at block boundaries). The noise $W_{DD}$ is an i.i.d. $\mathcal{CN}(0, \sigma^2)$ field.

In matrix form, $\mathbf{y}_{DD} \;=\; \mathbf{H}_{DD}\,\mathbf{x}_{DD} \;+\; \mathbf{w}_{DD},$ where $\mathbf{x}_{DD} = \text{vec}(X_{DD}) \in \mathbb{C}^{MN}$ and $\mathbf{H}_{DD}$ is the $MN \times MN$ DD channel matrix developed in Section 3.

Each physical path takes a copy of the transmit DD grid, shifts it by $(\ell_i, k_i)$ (circularly on the torus), scales it by $h_i$ , and adds a Zak-twist phase $\alpha_i(\ell, k)$ that accounts for the quasi-periodicity when the shift wraps. The receiver observes the sum of $P$ such shifted-and-phased copies plus noise.

Notice that the equation has exactly $P$ terms — not $MN$ , not $M$ , not $N$ . The physical number of paths determines the effective order of the DD channel, and this is typically $P \leq 20$ . This is the concrete meaning of "sparse" for the discrete grid.

Proof

Discretize the continuous relation

Starting from Theorem TContinuous DD Input-Output Relation, $y_{DD}(\tau, \nu) = \sum_i h_i\,x_{DD}(\tau - \tau_i, \nu - \nu_i) + \mathbf{w}$ . Sample at the DD grid points $\tau = \ell \Delta\tau$ , $\nu = k \Delta\nu$ . The translated input becomes $x_{DD}(\ell \Delta\tau - \ell_i \Delta\tau, k \Delta\nu - k_i \Delta\nu) = X_{DD}[\ell - \ell_i, k - k_i]$ (sampling at integer multiples of the resolution $\Delta\tau, \Delta\nu$ ).

Enforce toroidal index arithmetic

The DD signal lives on the fundamental domain $\mathbb{T}^2$ with periodicities $T$ (delay) and $1/T_s$ (Doppler). Translations beyond $[0, M) \times [0, N)$ wrap by quasi-periodicity. In the integer-Doppler case this gives $(\ell - \ell_i) \bmod M$ and $(k - k_i) \bmod N$ .

Account for the Zak twist

Crossing the $M$ -period in delay picks up a phase $e^{-j 2\pi k/N}$ per wrap (by Theorem TQuasi-Periodicity of the Discrete Zak Transform). The crossing happens only when $\ell - \ell_i < 0$ , so the phase factor $e^{j 2\pi \alpha_i(\ell, k)}$ is non-trivial only for paths whose shift crosses the delay boundary at grid position $\ell$ . This is the origin of the "within-block" vs "cross-block" bookkeeping in the Raviteja–Viterbo formulation.

Collect

The sum over paths with the explicit shift, phase, and noise term gives the stated equation. In vector form, the map $\mathbf{x}_{DD} \mapsto \mathbf{H}_{DD}\,\mathbf{x}_{DD}$ is linear with a sparse block-circulant matrix $\mathbf{H}_{DD}$ . The matrix is developed explicitly in Section 3. $\blacksquare$

,

Cyclic Prefix Is Required for the Circular Form

The circular (toroidal) form of the discrete input-output relation requires a cyclic prefix of length at least $l_{\max} = \tau_{\max} W$ . Without the CP, the delay-axis convolution is linear rather than circular, and boundary effects corrupt the first few delay bins of each frame. OTFS frames with insufficient CP still work (the corruption is small), but the clean doubly-circular structure that enables FFT-based detection requires adequate CP.

The standard choice in 5G NR is CP length $\geq 5.2\,\mu\text{s}$ for extended CP, covering $\tau_{\max}$ up to roughly this value at 15 kHz subcarrier spacing. For OTFS with larger $\tau_{\max}$ (e.g., LEO satellite), longer CPs are needed or alternative reduced-CP schemes (see Chapter 20) must be employed.

Example: $(M, N) = (4, 4)$ Input-Output for a Two-Path Channel

An OTFS frame with $M = N = 4$ transmits the DD grid $X_{DD}$ where $X_{DD}[0, 0] = 1$ and $X_{DD}[1, 2] = 1$ , zero elsewhere. The channel has two integer-index paths: $(h_1, \ell_1, k_1) = (1, 1, 0)$ and $(h_2, \ell_2, k_2) = (0.5, 2, 1)$ . Compute $Y_{DD}$ , ignoring the Zak-twist phase for simplicity (equivalent to no block-boundary crossings in this example).

Solution

Apply path 1 to $X_{DD}$

$h_1 = 1$ , shift $(\ell_1, k_1) = (1, 0)$ : this shifts each non-zero of $X_{DD}$ by 1 in delay. Contribution: $Y_1[\ell, k] = X_{DD}[(\ell - 1) \bmod 4, k]$ . $Y_1[1, 0] = 1$ (from $X[0, 0]$ ); $Y_1[2, 2] = 1$ (from $X[1, 2]$ ).

Apply path 2 to $X_{DD}$

$h_2 = 0.5$ , shift $(\ell_2, k_2) = (2, 1)$ : shifts by 2 in delay and 1 in Doppler. $Y_2[2, 1] = 0.5$ (from $X[0, 0]$ ); $Y_2[3, 3] = 0.5$ (from $X[1, 2]$ ).

Sum

$Y_{DD} = Y_1 + Y_2 + W$ . Non-zero entries (before noise): $Y[1, 0] = 1$ , $Y[2, 1] = 0.5$ , $Y[2, 2] = 1$ , $Y[3, 3] = 0.5$ . Four impulses, confirming the $P \cdot |\text{supp}(X)|$ cardinality.

Discrete DD Input-Output for a Random OTFS Frame

Generate an $M \times N$ OTFS frame with random QPSK symbols and pass it through a $P$ -tap DD channel. Display the transmit grid, the channel's DD impulse response, and the received grid (with AWGN). Vary $P$ and SNR to see the sparsity advantage: even at low SNR, the support pattern of the channel is visible as a multi-spike response to each input symbol.

Parameters

Delay bins

M

16

Doppler bins

N

16

Number of paths

P

4

SNR (dB)15

l_{\max}

3

k_{\max}

2

Seed1

Forward Pass Through the DD Channel (FFT Implementation)

Complexity:

O(MN \log(MN))

Input:

M \times N

transmit grid

X_{DD}

, path parameters

\{(h_i, \ell_i, k_i)\}_{i=1}^P

, AWGN variance

\sigma^2

Output: Received grid

Y_{DD}

of size

M \times N

1. Initialize

Y_{DD} \leftarrow 0

.

2. for each path

i = 1, \ldots, P

do

3.

\quad

Compute the shifted grid

X_i[\ell, k] \leftarrow X_{DD}[(\ell - \ell_i) \bmod M,\,(k - k_i) \bmod N]

.

4.

\quad

Apply Zak-twist phase:

X_i[\ell, k] \leftarrow X_i[\ell, k]\,e^{j 2\pi \alpha_i(\ell, k)}

.

5.

\quad

Accumulate:

Y_{DD} \leftarrow Y_{DD} + h_i\,X_i

.

6. end for

7. Add noise:

Y_{DD} \leftarrow Y_{DD} + W

with

W[\ell, k] \sim \mathcal{CN}(0, \sigma^2)

.

8. return

Y_{DD}

The per-path shift is $O(MN)$ and the total is $O(P MN)$ . For realistic $P \leq 20$ , this is linear in the grid size — significantly cheaper than a dense $MN \times MN$ matrix-vector multiply $O(M^2N^2)$ . Alternatively, computing $Y_{DD}$ via the SFFT of the time-domain channel action costs $O(MN \log(MN))$ , giving the same asymptotic cost.

🚨Critical Engineering Note

Integer vs Fractional Doppler

The entire derivation in this section assumes integer delay and Doppler indices. Real channels have $\tau_i$ and $\nu_i$ that are arbitrary real numbers — they seldom land exactly on the DD grid. When a path has, say, $\nu_i = k_i / T + \epsilon$ with $|\epsilon| < 1/(2T)$ , the discretized relation acquires additional off-diagonal terms (inter-Doppler interference) that couple neighboring grid cells.

Integer Doppler is a convenient fiction. In practice:

Fractional delay is usually not a problem — narrow pulses and large bandwidth oversample the delay axis, making $\Delta\tau$ fine.
Fractional Doppler is a problem — the Doppler resolution $1/T$ is coarse because $T$ is short, and typical paths have $\nu_i$ that are not grid-aligned.

Chapter 10 develops the full fractional-Doppler model and the detection modifications it requires. For this chapter, and for the detection analysis of Chapters 7-9, we follow the literature convention of assuming integer indices and treating fractional effects as perturbations.

Practical Constraints

•
Fractional Doppler offset $\epsilon$ creates leakage into $\pm 1, \pm 2, \ldots$ Doppler bins
•
Leakage power $\sim |\text{sinc}(\epsilon - k)|^2$ for nearest-neighbor coupling
•
Practical OTFS uses $N \geq 16$ to keep fractional effects manageable

📋 Ref: Raviteja–Viterbo (2018), §IV

Common Mistake: Circular vs Linear Convolution Confusion

Mistake:

Treating the DD channel action as a linear 2D convolution (as on $\mathbb{R}^2$ ), rather than the circular one required on the DD torus. This leads to incorrect boundary behavior and wrong detector output at the first $l_{\max}$ delay cells of each OTFS frame.

Correction:

The DD-grid convolution is doubly circular: delay index wraps modulo $M$ , Doppler index wraps modulo $N$ (with a Zak-twist phase on the delay wrap). This is enforced by the cyclic prefix (for delay) and by the inherent periodicity of the Doppler axis (from the quasi-periodic Zak structure, Chapter 2). Always compute using modular arithmetic on the indices; FFT-based implementations handle this automatically.

Discrete DD Input-Output Relation