Ferkans — Interactive Telecom Tutor

Putting the Transforms to Work

The ISFFT takes DD-grid data symbols to TF-grid precoded symbols. The SFFT takes received TF symbols back to DD-grid estimates. These two operations are the precoder and decoder, respectively, of the OTFS transceiver. The full modulator chain, to be developed in Chapter 6, sandwiches the ISFFT between a DD-grid symbol mapping (at the transmit side) and a standard OFDM modulator (Heisenberg transform), and the demodulator chain reverses this.

This section works out the ISFFT and SFFT in detail — both the full algebraic structure and the practical FFT-based implementation — so that by the time we reach Chapter 6, the transforms are a familiar tool.

ISFFT via 2D FFT

Complexity:

O(MN(\log M + \log N))

Input:

M \times N

DD-grid matrix

X_{DD}

Output:

N \times M

TF-grid matrix

X_{TF}

1. Compute the

M

-point inverse DFT along the delay axis:

\tilde{X}[\ell, k] = \frac{1}{\sqrt{M}}\sum_{m = 0}^{M-1} X_{DD}[\ell, k]\,e^{+j 2\pi m \ell / M}

(This is actually a forward DFT with sign flip — or an IDFT with normalization.)

2. Compute the

N

-point DFT along the Doppler axis:

X_{TF}[n, m] = \frac{1}{\sqrt{N}}\sum_{k = 0}^{N-1} \tilde{X}[m, k]\,e^{+j 2\pi k n / N}

3. Output

X_{TF}

, indexed by

(n, m)

— symbol

n

, subcarrier

m

.

In Python: X_TF = np.fft.ifft(X_DD, axis=1) * np.sqrt(N) — with careful attention to which axis is delay and which is Doppler, and the normalization convention. Equivalent implementations using NumPy fft2 differ by sign conventions; verify against the explicit ISFFT formula for a small test case.

SFFT via 2D FFT

Complexity:

O(MN(\log M + \log N))

Input:

N \times M

TF-grid matrix

X_{TF}

Output:

M \times N

DD-grid matrix

X_{DD}

1. Compute the

N

-point inverse DFT along the symbol (time) axis:

\tilde{X}[n, m] \to \hat{X}[k, m] = \frac{1}{\sqrt{N}}\sum_{n = 0}^{N-1} X_{TF}[n, m]\,e^{-j 2\pi k n / N}

2. Compute the

M

-point DFT along the subcarrier (frequency) axis:

X_{DD}[\ell, k] = \frac{1}{\sqrt{M}}\sum_{m = 0}^{M-1} \hat{X}[k, m]\,e^{+j 2\pi m \ell / M}

3. Output

X_{DD}

, indexed by

(\ell, k)

— delay

\ell

, Doppler

k

.

ISFFT/SFFT Round-Trip on a Sparse DD Pattern

Start with a sparse DD-grid pattern (a few non-zero entries). Apply the ISFFT to get the corresponding TF-grid image, then the SFFT to recover the DD grid. Numerically the recovery is exact up to floating-point error. Play with the data pattern: a single symbol, a row/column, or a random sparse support.

Parameters

DD pattern

Delay bins

M

16

Doppler bins

N

16

Sparsity (random patterns)0.1

Theorem: PAPR Concentration of ISFFT Output

Let $X_{DD}[\ell, k]$ for $(\ell, k) \in \{0, \ldots, M-1\} \times \{0, \ldots, N-1\}$ be i.i.d. $\mathcal{CN}(0, 1)$ data symbols, and let $X_{TF} = \text{ISFFT}(X_{DD})$ . The TF-grid signal has peak-to-average power ratio (PAPR) bounded by $O(\log(MN))$ with probability approaching 1 as $MN \to \infty$ .

An ISFFT of i.i.d. Gaussian symbols is a sum of $MN$ uncorrelated plane waves. By the central limit theorem, its distribution is approximately Gaussian, and the maximum is logarithmic — the same PAPR behavior as OFDM. This is both good (PAPR is bounded) and bad (no improvement over OFDM). Pulse shaping (Chapter 20) can reduce PAPR further.

Proof

Write the TF signal

$X_{TF}[n, m] = (1/\sqrt{MN})\sum_{\ell, k} X_{DD}[\ell, k]\,e^{j 2\pi(k n / N - m \ell / M)}$ . Each term is independent $\mathcal{CN}$ , so $X_{TF}[n, m] \sim \mathcal{CN}(0, 1)$ .

PAPR is logarithmic

$\text{PAPR}(X_{TF}) = \max_{n, m} |X_{TF}[n, m]|^2 / \mathbb{E}[|X_{TF}[n, m]|^2]$ . The maximum of $MN$ i.i.d. squared- $\mathcal{CN}$ variables is $O(\log(MN))$ by extreme-value theory — the standard OFDM PAPR result. $\blacksquare$

DD and TF Grid Pairing

Quantity	DD grid	TF grid
Grid dimensions	$M \times N$	$N \times M$
First index	$\ell$ = delay (0 to $M-1$ )	$n$ = OFDM symbol (0 to $N-1$ )
Second index	$k$ = Doppler (0 to $N-1$ )	$m$ = subcarrier (0 to $M-1$ )
Axis unit	Delay $\Delta\tau = 1/W$ , Doppler $\Delta\nu = 1/T$	Time $T_s = T/N$ , Frequency $\Delta f = W/M$
Channel action	2D sparse convolution	Time-varying multiplication + ICI
Forward transform	ISFFT (to TF)	— (input to OFDM)
Inverse transform	SFFT (from TF)	— (output of OFDM demod)

OTFS Transceiver Chain — The full OTFS transceiver chain, viewed as a cascade. Transmitter (top): QAM symbols on the DD grid → ISFFT (this chapter) → TF grid → OFDM modulation (Heisenberg transform, Chapter 6) → time-domain waveform. Receiver (bottom): matched filter / Wigner transform (Chapter 6) → TF grid → SFFT (this chapter) → DD grid estimate → DD-domain detector (Chapter 8).

Example: ISFFT of Two DD-Grid Symbols

Let $X_{DD}$ be the $4 \times 4$ DD grid with entries $X_{DD}[0, 0] = 1$ and $X_{DD}[2, 1] = -1$ (both real, BPSK-like), and zeros elsewhere. Compute $X_{TF} = \text{ISFFT}(X_{DD})$ .

Solution

Apply linearity

$X_{TF} = X_{TF}^{(1)} - X_{TF}^{(2)}$ where $X_{TF}^{(i)}$ is the ISFFT of a single-impulse grid.

Single-impulse ISFFTs

From EISFFT of a Single DD-Grid Symbol: $X_{TF}^{(1)}[n, m] = \frac{1}{4}\,e^{j 2\pi (0 \cdot n / 4 - m \cdot 0 / 4)} = \frac{1}{4}$ for all $(n, m)$ . $X_{TF}^{(2)}[n, m] = \frac{1}{4}\,e^{j 2\pi (1 \cdot n / 4 - m \cdot 2 / 4)} = \frac{1}{4}\,e^{j (\pi n / 2 - \pi m)}$ .

Combine

$X_{TF}[n, m] = \frac{1}{4}\left[1 - e^{j(\pi n / 2 - \pi m)}\right]$ . At $(n, m) = (0, 0)$ : $X_{TF} = 0$ . At $(n, m) = (1, 0)$ : $X_{TF} = (1 - j)/4$ . Each TF-grid cell carries a superposition of contributions from all DD-grid symbols. This is the essence of OTFS spreading.

Common Mistake: Sign Convention Traps in ISFFT/SFFT

Mistake:

Different references use different sign conventions for the ISFFT. Raviteja (2018) uses $e^{+j 2\pi (k n / N - m \ell / M)}$ ; Hadani (2017) uses the opposite sign in $m \ell / M$ but the same sign in $k n / N$ . Swapping these leads to a mirror-image DD grid at the receiver.

Correction:

When comparing to any external source, always verify the sign convention at the definition. In this book we adopt the Raviteja–Viterbo convention (widely used in the detection literature): ISFFT uses $e^{+j 2\pi (k n / N - m \ell / M)}$ . The SFFT uses the opposite sign in both terms.

A clean way to avoid confusion: implement the ISFFT/SFFT with explicit loops (not np.fft.fft2) at first, verify against a hand-computed example, then port to FFT routines.

Inverse Symplectic Fourier Finite Transform (ISFFT)

The 2D discrete transform that maps an $M \times N$ DD-grid matrix to an $N \times M$ TF-grid matrix. At the OTFS transmitter, it precedes the standard OFDM modulator. Defined by $X_{TF}[n, m] = \frac{1}{\sqrt{MN}}\sum_{\ell, k} X_{DD}[\ell, k]\,e^{j 2\pi (k n / N - m \ell / M)}$ .

Symplectic Fourier Finite Transform (SFFT)

The 2D discrete transform that maps a TF-grid matrix back to a DD-grid matrix. At the OTFS receiver, it follows the OFDM demodulator. Defined by $X_{DD}[\ell, k] = \frac{1}{\sqrt{MN}}\sum_{n, m} X_{TF}[n, m]\,e^{-j 2\pi (k n / N - m \ell / M)}$ . The SFFT is the exact inverse of the ISFFT.

ISFFT, SFFT, and the OTFS Signal Chain