Ferkans — Interactive Telecom Tutor

Why We Need an Algebraic Framework

The Golden code of §1 works beautifully for $n_t = 2$ , but the construction — the golden ratio, the unit $\alpha$ , the factor $j$ in one entry — looks rabbit-from-a-hat until you recognise that every piece is a consequence of one algebraic structure: a cyclic division algebra of degree $2$ over the Gaussian rationals $\mathbb{Q}(j)$ . The point is that once we see the Golden code this way, the path to $n_t = 3, 4, 5, \ldots$ is immediate: take a cyclic division algebra of degree $n_t$ .

This generalisation was pursued in parallel by three groups in the mid-2000s. Sethuraman-Rajan-Shashidhar (2003) showed that cyclic algebras give full-diversity space-time codes. Belfiore-Rekaya- Viterbo (2005) wrote down the $2 \times 2$ Golden code. Oggier- Rekaya-Belfiore-Viterbo (2006) constructed the "Perfect codes" for $n_t = 2, 3, 4, 6$ . And — the subject of the CommIT contribution below — Elia, P. V. Kumar, S. A. Pawar, K. R. Kumar, Hsiao-feng Lu, and Giuseppe Caire (2006) gave the first explicit construction of DMT-optimal codes for every $(n_t, n_r)$ , proving that a CDA with the non-vanishing-determinant property achieves the Zheng-Tse curve in full and — a stronger property that we develop in §4 — achieves the tradeoff curve under any fading distribution, not just i.i.d. Rayleigh.

This section builds the CDA framework from scratch, states the key theorem, and places the Elia-Kumar-Caire 2006 result in context.

,

Definition:
Cyclic Algebra $\mathcal{A}(F, K, \sigma, \gamma)$

Let $F$ be a number field (for MIMO codes, $F = \mathbb{Q}(j)$ ) and let $K/F$ be a cyclic Galois extension of degree $n$ — that is, $\mathrm{Gal}(K/F) = \langle \sigma \rangle$ is a cyclic group of order $n$ generated by the automorphism $\sigma: K \to K$ . Fix a non-zero element $\gamma \in F^*$ . The cyclic algebra $\mathcal{A}(F, K, \sigma, \gamma)$ is the $n^2$ -dimensional $F$ -algebra $\mathcal{A} \;=\; K \oplus eK \oplus e^2 K \oplus \cdots \oplus e^{n-1} K$ where $e$ is a formal symbol satisfying the two rules $e^n = \gamma \qquad \text{and} \qquad x \cdot e = e \cdot \sigma(x) \quad \text{for all } x \in K.$ Multiplication extends $F$ -linearly and non-commutatively using these rules. An element of $\mathcal{A}$ is uniquely written as $a_0 + e a_1 + e^2 a_2 + \cdots + e^{n-1} a_{n-1}$ with $a_i \in K$ .

The rule $x e = e \sigma(x)$ is where cyclic algebras become non-commutative: swapping $x$ and $e$ applies the Galois automorphism $\sigma$ . This is the algebraic counterpart of the rotation between antennas in the space-time code. The element $\gamma$ — called the non-norm element — plays the role of the factor $j$ in the Golden code: it ties together what would otherwise be $n$ independent copies of $K$ .

,

Definition:
Division Algebra and the Non-Norm Condition

A ring $\mathcal{A}$ is a division algebra if every non-zero element has a two-sided multiplicative inverse. The cyclic algebra $\mathcal{A}(F, K, \sigma, \gamma)$ is a division algebra if and only if $\gamma$ satisfies the non-norm condition: $\gamma \notin N_{K/F}(K^*) \;=\; \{N_{K/F}(x) : x \in K, x \neq 0\}$ and furthermore no power $\gamma^k$ for $k = 1, 2, \ldots, n - 1$ lies in $N_{K/F}(K^*)$ either. (For prime $n$ , a single non-norm $\gamma$ suffices.)

The regular representation of $\mathcal{A}$ sends each $a = \sum_{i} e^i a_i \in \mathcal{A}$ to its left-multiplication matrix in the basis $\{1, e, e^2, \ldots, e^{n-1}\}$ : $\lambda(a) = \begin{pmatrix} a_0 & \gamma \sigma(a_{n-1}) & \gamma \sigma^2(a_{n-2}) & \cdots & \gamma \sigma^{n-1}(a_1) \\ a_1 & \sigma(a_0) & \gamma \sigma^2(a_{n-1}) & \cdots & \gamma \sigma^{n-1}(a_2) \\ a_2 & \sigma(a_1) & \sigma^2(a_0) & \cdots & \gamma \sigma^{n-1}(a_3) \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ a_{n-1} & \sigma(a_{n-2}) & \sigma^2(a_{n-3}) & \cdots & \sigma^{n-1}(a_0) \end{pmatrix}.$ This is the codeword matrix of the CDA space-time code. Each row of $\lambda(a)$ is the Galois orbit of a component of $a$ , weighted by $\gamma$ above the diagonal.

,

Theorem: CDA Codewords Are Full Rank

Let $\mathcal{A}(F, K, \sigma, \gamma)$ be a cyclic division algebra of degree $n$ and let $\lambda: \mathcal{A} \to M_n(K)$ be the regular representation. For every non-zero $a \in \mathcal{A}$ , the codeword matrix $\lambda(a)$ has full rank $n$ over $K$ ; equivalently $\det(\lambda(a)) \in F^*$ is non-zero.

In consequence: for any CDA space-time code $\mathcal{C} = \{\lambda(a) : a \in \mathcal{I}\}$ built from a finite subset $\mathcal{I} \subset \mathcal{A}$ closed under subtraction, every non-zero codeword-difference matrix $\boldsymbol{\Delta} = \lambda(a) - \lambda(\hat a) = \lambda(a - \hat a)$ (with $a \neq \hat a$ ) is full rank, so the code achieves full spatial diversity $n_t n_r$ at $r = 0$ .

The non-norm condition on $\gamma$ is precisely what prevents the determinant of $\lambda(a)$ from factoring through a degenerate quotient — it forces the columns of $\lambda(a)$ to be $K$ -linearly independent for every non-zero $a$ . Intuitively, $\lambda(a)$ is the "twisted" cyclic extension matrix, and the twist $\gamma \sigma$ is chosen so that no non-trivial linear combination of the columns can give zero.

Show Hint

In a division algebra, every non-zero element has an inverse. Hence $\lambda(a)$ has a matrix inverse, namely $\lambda(a^{-1})$ .

A matrix with a two-sided inverse has non-zero determinant.

Proof

Step 1 — Division implies invertibility

Since $\mathcal{A}$ is a division algebra, every non-zero $a \in \mathcal{A}$ has a multiplicative inverse $a^{-1}$ . The regular representation is a ring homomorphism: $\lambda(a b) = \lambda(a) \lambda(b)$ and $\lambda(1) = \mathbf{I}_n$ .

Step 2 — Matrix inverse via $\lambda(a^{-1})$

Applying $\lambda$ to $a a^{-1} = 1$ gives $\lambda(a) \lambda(a^{-1}) = \mathbf{I}_n$ . Hence $\lambda(a)$ has a two-sided matrix inverse, namely $\lambda(a^{-1})$ .

Step 3 — Non-zero determinant

An $n \times n$ matrix with a two-sided matrix inverse has non-zero determinant. Hence $\det(\lambda(a)) \neq 0$ . Further, a ring-theoretic consequence of the CDA structure is that $\det(\lambda(a)) \in F$ (the reduced norm lands in the base field) — this is not just non-zero but an element of $F^*$ .

Step 4 — Apply to the code

For any two distinct codewords $\lambda(a), \lambda(\hat a)$ , the difference is $\lambda(a - \hat a) = \lambda(b)$ for $b = a - \hat a \neq 0$ . By steps 1–3, $\det(\lambda(b)) \neq 0$ , i.e. the error matrix $\boldsymbol{\Delta}$ is full rank. Applying the rank criterion (Ch. 11) to the PEP, the code achieves diversity $n_t n_r$ at $r = 0$ . $\blacksquare$

,

Structure of a CDA Codeword Matrix $\lambda(a)$

Heatmap visualisation of the regular-representation matrix $\lambda(a)$ for a CDA of degree $n_t$ . Each row is a Galois orbit of a component of $a = a_0 + e a_1 + \cdots + e^{n_t - 1} a_{n_t - 1}$ , weighted by $\gamma$ above the diagonal. Diagonal cells show $\sigma^i(a_0)$ (the Galois orbit of $a_0$ ); off- diagonal cells show $\gamma \sigma^i(a_j)$ . The structure is the direct generalisation of the Alamouti-like row symmetry to higher dimensions.

Parameters

Number of antennas

n_t

4

🎓CommIT Contribution(2006)

Explicit DMT-Optimal Space-Time Codes via Cyclic Division Algebras

P. Elia, K. R. Kumar, S. A. Pawar, P. V. Kumar, H.-f. Lu, G. Caire — IEEE Trans. Inf. Theory, vol. 52, no. 9, pp. 3869–3884

Petros Elia (USC, later EURECOM), K. Raj Kumar, Sameer A. Pawar, P. Vijay Kumar (USC), Hsiao-feng Lu (National Chiao Tung), and Giuseppe Caire (USC at the time, now TU Berlin) jointly established the first explicit construction of DMT-optimal space-time codes for arbitrary $(n_t, n_r)$ . Before this paper, DMT optimality was known only for a handful of special cases — Alamouti at $r = 0$ , V-BLAST-ML at $r = \min(n_t, n_r)$ , and the Golden code was conjectured (but not yet proved) DMT-optimal for $2 \times 2$ . No explicit construction existed for $n_t \ge 3$ , and no general existence result matched the Zheng-Tse achievability for all $r$ . The paper closed this gap. Its four contributions are the backbone of this chapter.

(i) CDAs with non-vanishing determinant achieve the Zheng-Tse DMT for every $(n_t, n_r)$ . The central theorem: if a cyclic division algebra of degree $n_t$ over $\mathbb{Q}(j)$ admits a lattice representative $\mathcal{I}$ whose minimum codeword-pair determinant $\delta_{\min}$ is bounded below by a positive constant independent of the input QAM size $M$ , then the CDA space-time code $\{\lambda(a) : a \in \mathcal{I}\}$ achieves the full Zheng-Tse DMT curve $d^*(r) = (n_t - r)(n_r - r)$ for all $r \in [0, \min(n_t, n_r)]$ . Explicit families of such "NVD-CDA" codes are exhibited for every $n_t$ . This was a landmark: the first explicit construction of DMT-optimal codes for arbitrary MIMO dimensions.

(ii) Approximate universality: same code, all fadings. The paper proves (building on Tavildar-Viswanath 2006) that NVD-CDA codes are approximately universal — they achieve the Zheng-Tse DMT under every fading distribution satisfying mild regularity (density bounded away from zero near zero), not just i.i.d. Rayleigh. This is the strongest achievability result possible for space-time codes: you do not have to redesign the code for Rician, Nakagami, log-normal, or correlated fading. The same CDA-NVD codewords work — a property that, in retrospect, the classical Gaussian random-coding achievability of Zheng-Tse does not obviously possess. Section 4 of this chapter develops approximate universality in detail.

(iii) A DMT upper bound for linear STBCs. The paper also proves a converse: no linear space-time block code with lattice structure over $\mathbb{Q}(j)$ can achieve a tradeoff curve tighter than Zheng-Tse. Combined with (i), this establishes NVD-CDA codes as the design frontier for linear STBCs — one cannot do better within this rich but structured class. This closed the DMT-optimality question for linear codes.

(iv) Explicit constructions for every $n_t$ . The paper is not an existence proof; it writes down explicit CDAs — including the cases $n_t = 2, 3, 4, 6$ matching the Perfect codes of Oggier et al. and extending to $n_t = 5, 7, 8, \ldots$ via the Selmer group method. Coding gains (the actual $\delta_{\min}$ values, modulo $M$ -independent constants) are tabulated. Together with the sphere-decoder analysis of Hassibi-Vikalo (2005), this gave practitioners a complete toolkit: an explicit code, a proven DMT-optimality guarantee, and a polynomial-in- $M$ decoding algorithm.

Why it redefined the field. Before 2006, the DMT was primarily an information-theoretic benchmark — a curve against which code designers measured their constructions, hoping to approach it. After Elia-Kumar-Caire 2006, the benchmark became a construction recipe: pick a cyclic division algebra of degree $n_t$ ; verify the NVD condition (a finite algebraic check); use the regular representation as the codebook; decode with a sphere decoder. The DMT question was closed for linear STBCs, and the conversation shifted to decoder complexity, finite-SNR coding gains, and the harder problems of compute-and-forward (Ch. 18) and lattice space-time codes (Ch. 17). The paper is the most-cited explicit-code-construction paper in space-time coding, cited in every subsequent survey and in the DVB-NGH standard's space-time-coding section.

cdadmtgolden-codeapproximate-universalityperfect-codesnon-vanishing-determinantView Paper →

Theorem: CDA-NVD Codes Achieve the DMT (Elia-Kumar-Caire 2006)

Let $\mathcal{A}(F, K, \sigma, \gamma)$ be a cyclic division algebra of degree $n_t$ over $F = \mathbb{Q}(j)$ , and let $\mathcal{C}_M = \{\lambda(a) : a \in \mathcal{I}_M\}$ be the CDA space-time code on an input constellation of size $M^{n_t^2}$ (so that each of the $n_t^2$ information symbols drawn from a $\mathbb{Z}[j]$ -QAM has size $M$ ). Suppose $\mathcal{I}_M$ inherits the non-vanishing-determinant property: $\delta_{\min}(\mathcal{C}_M) \;=\; \min_{\lambda(a) \neq \lambda(\hat a)} |\det(\lambda(a - \hat a))|^2 \;\ge\; \delta_0 > 0$ with $\delta_0$ independent of $M$ . Then, on an $n_t \times n_r$ i.i.d. Rayleigh block-fading channel with block length $L = n_t$ , the code $\mathcal{C}_M$ achieves the Zheng-Tse DMT curve $d^*(r) = (n_t - r)(n_r - r)$ for every $r \in [0, \min(n_t, n_r)]$ .

Intuitively, what happens is that the NVD condition controls the pairwise error probability uniformly over the codebook. The PEP bound of Chapter 11 has a prefactor $1/\det(\boldsymbol{\Delta} \boldsymbol{\Delta}^H)^{n_r}$ ; without NVD, this prefactor could grow with $M$ faster than the SNR penalty $\text{SNR}^{-n_t n_r}$ absorbs, breaking DMT optimality at high $r$ . With NVD, the prefactor is bounded by $\delta_0^{-n_r}$ — a constant — and the SNR exponent controls the full decay. Averaging over the fading, the Zheng-Tse curve emerges.

Show Hint

Start from the PEP bound $P(\ntn{X} \to \hat{\ntn{X}}) \le (1 + \tfrac{\text{SNR}}{4 n_t} \delta_{\min})^{-n_r}$ under i.i.d. Rayleigh.

Use the union bound over $|\mathcal{C}_M|^2 \le \text{SNR}^{2 n_t^2 r}$ codeword pairs (at rate $r \log \text{SNR}$ ).

Balance the union bound with the Wishart outage event $\{\lambda_i(\mathbf{H}\mathbf{H}^{H}) \doteq \text{SNR}^{-\alpha_i}\}$ via Laplace's method — the machinery of Ch. 12.

The NVD property ensures the $M$ -dependence of the union bound is absorbed into the $\doteq$ asymptotic.

Proof

Step 1 — PEP under NVD

By the rank criterion (Ch. 11) and the NVD property, the determinant $\det(\boldsymbol{\Delta}\boldsymbol{\Delta}^H) \ge \delta_0^2$ for every non-zero codeword difference. Hence the conditional PEP given $\mathbf{H}$ is bounded by $P(\ntn{X} \to \hat{\ntn{X}} \mid \mathbf{H}) \le \exp(- \tfrac{\text{SNR}}{4 n_t} \cdot \mathrm{tr}(\mathbf{H} \boldsymbol{\Delta} \boldsymbol{\Delta}^H \mathbf{H}^{H}))$ .

Step 2 — Union bound at rate $r \log \ntn{snr}$

The codebook at multiplexing gain $r$ has size $|\mathcal{C}_M| \doteq \text{SNR}^{r n_t}$ ; the number of codeword pairs is $\doteq \text{SNR}^{2 r n_t}$ . Union-bounding over pairs: $P_e \le \sum_{\text{pairs}} \mathbb{E}_{\mathbf{H}}[P(\ntn{X} \to \hat{\ntn{X}} \mid \mathbf{H})].$

Step 3 — Wishart outage analysis

Decompose the fading via the eigenvalues $\text{SNR}^{-\alpha_i}$ of $\mathbf{H}^{H} \mathbf{H}$ as in Ch. 12. The expectation of the conditional PEP exponentiates the Wishart joint density $\prod_i \text{SNR}^{-(n_t + n_r - 2i - 1) \alpha_i} \prod_{i < j}|\text{SNR}^{-\alpha_i} - \text{SNR}^{-\alpha_j}|^2$ , and a Laplace-method evaluation gives the large-deviations exponent $\sum_i (n_t + n_r - 2i - 1)^+ \alpha_i^+$ .

Step 4 — NVD absorbs the $M$-dependence

Without NVD, the PEP would contribute a factor $\delta_{\min}(M)^{-n_r}$ that could grow polynomially in $M$ , i.e. as $\doteq \text{SNR}^{\epsilon n_r}$ for some $\epsilon > 0$ , degrading the exponent by $\epsilon n_r$ . With NVD, $\delta_{\min} \ge \delta_0$ so this factor is a constant and invisible to $\doteq$ . Combined with the Wishart Laplace evaluation of step 3, the resulting exponent is exactly the Zheng-Tse $(n_t - r)(n_r - r)$ .

Step 5 — Matching the Zheng-Tse converse

The Zheng-Tse converse (Ch. 12) gives the upper bound $d^*(r) \le (n_t - r)(n_r - r)$ on every linear STBC. Steps 1–4 give the matching lower bound for the CDA-NVD code. Hence the code achieves the Zheng-Tse curve. $\blacksquare$

,

Common Mistake: CDA Alone Does Not Imply NVD

Mistake:

A common assumption is that any cyclic division algebra automatically yields a DMT-optimal space-time code once you pick a lattice in it. In particular one might hope that just scaling the information constellation preserves DMT optimality.

Correction:

The CDA framework gives full diversity automatically (Theorem TCDA Codewords Are Full Rank) but not NVD. The NVD property requires the lattice $\mathcal{I}$ — the subring of $\mathcal{A}$ from which codewords are drawn — to have integer or algebraic-integer entries, so that $\det(\lambda(a))$ lands in $\mathbb{Z}[j]$ whenever $a$ has entries in the ring of integers $\mathcal{O}_K$ . Scaling by a real factor preserves NVD, but scaling by a non-algebraic real factor (or drawing entries from a non-integer QAM grid) breaks it. Full diversity is purely algebraic; NVD is lattice-theoretic. The Elia-Kumar- Caire 2006 paper's contribution is precisely the explicit lattice choice that makes both hold.

⚠️Engineering Note

Decoding Complexity: Sphere Decoding for CDA Codes

CDA codes achieve the Zheng-Tse DMT curve, but they are not cheap to decode. The ML-decoding complexity — minimising $\|\ntn{Y} - \mathbf{H} \ntn{X}\|_F^2$ over the codebook of size $M^{n_t^2}$ — is $O(M^{n_t^2})$ brute force. For $n_t = 4, M = 64$ , that is $64^{16} \approx 8 \times 10^{28}$ candidates, far out of reach.

The Viterbo-Boutros (1999) and Damen-Chkeif-Belfiore (2000) sphere decoder exploits the lattice structure: it searches only candidates inside a shrinking ball around the received vector. Average complexity is $O(M^{n_t^2 / 2})$ — still exponential in $n_t^2$ but tractable for $n_t \le 4$ at moderate $M$ . For $n_t = 4, M = 16$ the sphere decoder averages $\sim 16^8 \approx 4 \times 10^9$ — feasible on custom hardware; for $n_t = 6$ or large $M$ it becomes impractical.

For a designer, the CDA framework means: once you have a cyclic division algebra of degree $n_t$ , you have a code. No further design effort — just instantiate a CDA that exists in any dimension. But if $n_t \ge 6$ or if you want flexible rate adaptation, you should look instead at lattice space-time (LAST) codes (Ch. 17), which achieve the DMT with lower decoding complexity via MMSE-GDFE pre-processing, or at modern 5G NR designs that abandon full-CDA in favour of low-dimensional Alamouti-style precoding with BICM outer codes.

Practical Constraints

•
ML decoding: $O(M^{n_t^2})$ brute force — impractical beyond $n_t = 2$
•
Sphere decoder average complexity: $O(M^{n_t^2 / 2})$ — tractable for $n_t \le 4$
•
Sphere decoder worst case: still $O(M^{n_t^2})$
•
LAST codes (Ch. 17): polynomial decoding via MMSE-GDFE at the cost of coding-gain loss

📋 Ref: DVB-NGH (2012) adopted Golden code with sphere decoder; 5G NR uses simpler precoding.

, ,

Cyclic Division Algebras and the CDA Framework