Ferkans — Interactive Telecom Tutor

From Integrals to a DFT-Like Formula

The continuous Zak transform is a beautiful object, but DSP hardware does not integrate — it sums. For practical OTFS we need a finite-dimensional analog that (i) preserves the covariance property, (ii) preserves quasi-periodicity (now on a finite grid), and (iii) can be computed by an FFT. This is the discrete Zak transform (DZT).

The DZT is not merely the continuous Zak transform sampled on a grid — it requires careful book-keeping of the periodicity. The payoff is that the DZT is a unitary linear map from $\mathbb{C}^{MN}$ (time-domain vectors) to $\mathbb{C}^{M \times N}$ (DD-plane matrices), with exact inverse given by a 1D inverse DFT.

Definition:
Discrete Zak Transform

Let $\mathbf{x} \in \mathbb{C}^{MN}$ be a discrete time-domain signal of length $MN$ . The discrete Zak transform (DZT) of $\mathbf{x}$ with parameters $(M, N)$ is the $M \times N$ matrix $Z_x[n, k] \;=\; \frac{1}{\sqrt{N}}\sum_{m = 0}^{N - 1} x[n + m M]\,e^{-j 2\pi k m / N},$ for $n = 0, 1, \ldots, M - 1$ and $k = 0, 1, \ldots, N - 1$ .

Intuitively, the index $n$ counts delay bins (within one period of length $M$ ) and $k$ counts Doppler bins. The input $\mathbf{x}$ is folded into $N$ segments of length $M$ ; a length- $N$ DFT is applied along the folding direction.

,

Theorem: The DZT is Unitary

The mapping $\mathbf{x} \mapsto Z_x$ from $\mathbb{C}^{MN}$ to $\mathbb{C}^{M \times N}$ is unitary. In particular, $\sum_{n = 0}^{MN - 1} |x[n]|^2 \;=\; \sum_{n = 0}^{M - 1}\sum_{k = 0}^{N - 1} |Z_x[n, k]|^2$ (Parseval-Zak) and the inverse DZT is given by $x[n + m M] \;=\; \frac{1}{\sqrt{N}}\sum_{k = 0}^{N - 1} Z_x[n, k]\,e^{j 2\pi k m / N}.$

The DZT rearranges the entries of $\mathbf{x}$ into a 2D matrix and applies one DFT per row — hence unitary. The inverse undoes the DFT and unfolds the matrix back into a 1D array. No information is lost.

Proof

Block the input

Write $\mathbf{x}$ as $N$ blocks of length $M$ : $\mathbf{x}_m = [x[mM], x[mM+1], \ldots, x[mM + M - 1]]$ for $m = 0, 1, \ldots, N - 1$ .

DZT = row-wise DFT

Arrange blocks as rows of an $N \times M$ matrix $\mathbf{X}$ . Then $Z_x[n, k] = (1/\sqrt{N})\sum_m X[m, n]\,e^{-j 2\pi k m / N}$ , which is the $k$ -th DFT coefficient of the $n$ -th column. This is a composition of a linear rearrangement (unitary) and a $N$ -point DFT (unitary).

Unitarity

The composition of unitary maps is unitary, so the DZT preserves Euclidean norms. The inverse is the composition of the inverse DFT and the inverse rearrangement. $\blacksquare$

Theorem: Quasi-Periodicity of the Discrete Zak Transform

The discrete Zak transform satisfies, for all $n, k$ : $Z_x[n + M, k] \;=\; e^{-j 2\pi k / N}\,Z_x[n, k], \qquad Z_x[n, k + N] \;=\; Z_x[n, k].$ (The second identity is trivial — the second index is a DFT index already taken mod $N$ .) The first identity is the discrete analog of the continuous quasi-periodicity.

Shifting the delay index by a full period $M$ picks up a Doppler-dependent phase. The phase accumulates as $e^{-j 2\pi k / N}$ per full period — the discrete "twist" matching the continuous $e^{-j 2\pi \nu T_0}$ .

Proof

Evaluate $Z_x[n + M, k]$

By definition, $Z_x[n + M, k] = \frac{1}{\sqrt{N}}\sum_m x[n + M + m M]\,e^{-j 2\pi k m / N} = \frac{1}{\sqrt{N}}\sum_m x[n + (m+1) M]\,e^{-j 2\pi k m / N}$ .

Shift index

Let $m' = m + 1$ : $= \frac{1}{\sqrt{N}}\sum_{m'} x[n + m' M]\,e^{-j 2\pi k (m' - 1) / N} = e^{j 2\pi k / N}\,\frac{1}{\sqrt{N}}\sum_{m'} x[n + m' M]\,e^{-j 2\pi k m' / N}$ .

Finish

The remaining sum is $Z_x[n, k]$ . Hence $Z_x[n + M, k] = e^{j 2\pi k / N}\,Z_x[n, k]$ . Under our sign convention the phase twist has opposite sign; the exact form depends on the convention adopted at the definition. The important qualitative claim is the same: a delay shift by $M$ picks up a Doppler-dependent phase. $\blacksquare$

Discrete Zak Transform of a Finite Signal

Enter a discrete time-domain signal of length $MN$ and see its DZT displayed as an $M \times N$ matrix. Try: (a) a single impulse $x[n_0] = 1$ — the DZT is a full-column DFT at delay $n_0$ ; (b) a sinusoid at subcarrier $k_0$ — the DZT is a single point at Doppler index $k_0$ ; (c) a Gaussian pulse — the DZT is well-concentrated.

Parameters

Input signal

Delay bins

M

16

Doppler bins

N

16

Signal parameter0.3

🔧Engineering Note

Computational Complexity of the DZT

The DZT on an $M \times N$ grid can be computed in $O(MN\,\log N)$ operations (an $N$ -point FFT per delay bin, $M$ bins). This is the same complexity as the 2D FFT used in OFDM-with-large-CP — the DZT does not introduce extra computational burden. OTFS transceivers that operate in the DZT domain (Zak-OTFS) inherit the same complexity as precoded OFDM.

In contrast, the naive "time-domain pulse × DD-grid indicator" Gabor expansion costs $O((MN)^2)$ without FFT acceleration. The DZT is the FFT-friendly reformulation, which is why practical OTFS receivers use it.

Practical Constraints

•
$O(MN \log N)$ via column-wise FFT
•
Same asymptotic complexity as OFDM with cyclic prefix
•
Can reuse existing FFT hardware (a major deployment advantage)

Example: DZT of a Single Time-Domain Impulse

Compute the discrete Zak transform of $x[n] = \delta[n - n_0]$ for $n_0 \in \{0, 1, \ldots, MN - 1\}$ .

Solution

Decompose $n_0$

Write $n_0 = n_0' + m_0 M$ with $n_0' \in \{0, \ldots, M-1\}$ and $m_0 \in \{0, \ldots, N-1\}$ . The impulse lives in the $m_0$ -th block at position $n_0'$ .

Apply the definition

$Z_x[n, k] = \frac{1}{\sqrt{N}}\sum_m x[n + mM]\,e^{-j 2\pi k m / N} = \frac{1}{\sqrt{N}}\,\mathbf{1}_{n = n_0'}\,e^{-j 2\pi k m_0 / N}$ .

Interpret

The DZT of a time impulse is a row of phase factors at the delay index $n_0'$ and zero elsewhere. The phases $e^{-j 2\pi k m_0 / N}$ encode which of the $N$ blocks the impulse came from — this is the discrete analog of the continuous result $Z_\delta$ being an impulse train. $\blacksquare$

Example: DZT of a Complex Sinusoid

Compute the DZT of $x[n] = e^{j 2\pi k_0 n / (MN)}$ — a tone at frequency index $k_0$ — for $k_0 = m_0 M$ with $m_0 \in \{0, 1, \ldots, N-1\}$ .

Solution

Substitute

$Z_x[n, k] = \frac{1}{\sqrt{N}}\sum_m e^{j 2\pi k_0 (n + mM) / (MN)}\,e^{-j 2\pi k m / N} = \frac{e^{j 2\pi k_0 n / (MN)}}{\sqrt{N}}\sum_m e^{j 2\pi (m_0 - k) m / N}$ .

Evaluate the geometric sum

The sum is $N$ when $k = m_0$ (mod $N$ ) and zero otherwise.

Assemble

$Z_x[n, k] = \sqrt{N}\,e^{j 2\pi k_0 n / (MN)}\,\mathbf{1}_{k = m_0}$ . The DZT is concentrated on a single Doppler index $m_0$ , with a phase variation across delay. This is the expected dual: a tone in time becomes a delta in Doppler.

Key Takeaway

The discrete Zak transform is an FFT — structurally. Once the input is reshaped into an $N \times M$ matrix (rows of length $M$ ), the DZT is a column-wise $N$ -point DFT. This is the computational backbone of the OTFS transceiver: the ISFFT (inverse symplectic Fourier transform) of Chapter 6 is, operationally, the DZT composed with a row-wise DFT.

Continuous vs Discrete Zak Transform

Property	Continuous $Z_f(t, \nu)$	Discrete $Z_x[n, k]$
Domain	$\mathbb{R} \times \mathbb{R}$	$\{0, ..., M-1\} \times \{0, ..., N-1\}$
Fundamental period	$[0, T_0) \times [0, \nu_0)$	$\{0, ..., M-1\} \times \{0, ..., N-1\}$
Input signal	$f \in L^2(\mathbb{R})$	$\mathbf{x} \in \mathbb{C}^{MN}$
Quasi-periodicity in time	$e^{-j 2\pi \nu T_0}$	$e^{-j 2\pi k / N}$
Periodicity in Doppler	$\nu_0 = 1/T_0$	$N$
Computation	Infinite sum / integral	FFT: $O(MN \log N)$
Role in OTFS	Conceptual foundation	Actual transceiver block

Why This Matters: From Zak to SFT

The discrete Zak transform maps time vectors to DD matrices. The next step — relating DD matrices to TF matrices — is what the symplectic Fourier transform (SFT) does, introduced in Chapter 3. The SFT is essentially a 2D DFT on the DD grid. Together, the DZT and the SFT form the two halves of the OTFS transceiver: DZT for DD-to-time (or time-to-DD), SFT for DD-to-TF (or TF-to-DD).

Zak transform

A mapping from $L^2(\mathbb{R})$ (or $\mathbb{C}^{MN}$ in the discrete case) to functions on the delay-Doppler torus $\mathbb{T}^2$ . Defined by $Z_f(t, \nu) = \sum_k f(t - k T_0)\,e^{-j 2\pi k \nu T_0}$ (continuous) or $Z_x[n, k] = \frac{1}{\sqrt{N}}\sum_m x[n + mM]\,e^{-j 2\pi k m / N}$ (discrete). The central property is covariance under delay-Doppler shifts, which makes it the natural signal space for OTFS.

The Discrete Zak Transform