Ferkans — Interactive Telecom Tutor

Why Partition a Constellation?

Here is the point of this chapter in one sentence: at equal transmit power, we can buy 3 to 6 dB of coding gain over the uncoded signal by splitting each symbol decision into two steps — first pick a subset of the constellation using a convolutional code, then pick a point inside that subset using the remaining uncoded bits — provided the subsets are chosen so that the minimum distance inside each subset is much larger than the minimum distance of the parent constellation.

The procedure that achieves this is called set partitioning. It was introduced by Ungerboeck in 1982 and it revolutionized modem design overnight — the V.32 (9.6 kbps) and V.34 (33.6 kbps) dial-up modems were direct instantiations of his idea. Before attacking the machinery, let us look at the geometric picture: each split of a constellation doubles the minimum squared Euclidean distance inside the resulting subsets, and the coding gain is essentially the number of levels of splitting times 3 dB (a bit less, in practice, because the final convolutional code imposes its own structure).

The coded-modulation insight from §Why Separate Coding and Modulation Is Suboptimal said: do not code in the binary label space, code in the signal space. Set partitioning is the constructive answer — it tells us which binary labels to use so that a convolutional code acting on the subset index maximizes free Euclidean distance in the underlying signal space.

Definition:
Coded Modulation

A coded modulation scheme jointly designs channel coding and modulation so that the code lives in the signal space itself: each encoder output is a point in a constellation $\mathcal{X} \subset \mathbb{C}$ , not a binary symbol in $\{0,1\}$ . The design objective is to maximize the minimum Euclidean distance between distinct code sequences, not the Hamming distance between distinct binary codewords.

The contrast is with the classical "coding then modulation" pipeline (a binary encoder whose output is passed through a separate constellation mapper), which is generally suboptimal at moderate-to-high spectral efficiencies — as we argued in §Why Separate Coding and Modulation Is Suboptimal.

,

Definition:
Set Partition (Ungerboeck Chain)

Let $\mathcal{X}$ be a signal constellation with $|\mathcal{X}| = 2^m$ points and minimum squared distance $\Delta_0^2$ . A set partition (or Ungerboeck chain) is a sequence of successive binary splits

$\mathcal{X} = D_0 \;\to\; \{D_1^{(0)}, D_1^{(1)}\} \;\to\; \{D_2^{(0)}, D_2^{(1)}, D_2^{(2)}, D_2^{(3)}\} \;\to\; \cdots \;\to\; \{D_m^{(0)}, \ldots, D_m^{(2^m-1)}\},$

where at level $i$ the parent set $D_{i-1}$ is split into two disjoint equal-size children, and $\Delta_i^2$ denotes the minimum squared Euclidean distance within any child at level $i$ (the intra-subset minimum squared Euclidean distance, or MSED).

A set partition is Ungerboeck-optimal if at every level $i$ the split is chosen so that $\Delta_i^2$ is as large as possible.

Equivalently, level $i$ labels a point by the first $i$ bits of a binary address; points sharing an $i$ -bit prefix lie in the same subset $D_i^{(k)}$ . At level $m$ every subset contains a single point and $\Delta_m^2 = \infty$ by convention.

Definition:
Intra-Subset Minimum Squared Euclidean Distance

For a subset $D \subseteq \mathcal{X}$ with $|D| \geq 2$ , the intra-subset MSED is

$\Delta^2(D) \;\triangleq\; \min_{\substack{x, x' \in D \\ x \neq x'}} \|x - x'\|^2.$

For a full partition level $i$ , $\Delta_i^2$ denotes the smallest $\Delta^2(D)$ taken over all subsets $D$ at that level.

Intra-subset MSED is the only constellation property that matters for Ungerboeck's design: the convolutional code only picks which subset to transmit from, so the relevant distance between any two competing TCM sequences is governed by the intra-subset MSEDs along the two paths.

Definition:
Coset (Subset) of a Partition

A coset (or subset) at level $i$ of an Ungerboeck partition is one of the $2^i$ disjoint sets $D_i^{(k)}$ , $k = 0, \ldots, 2^i - 1$ , produced by $i$ successive binary splits. Each coset has $|\mathcal{X}|/2^i = 2^{m-i}$ points and intra-subset MSED $\Delta_i^2$ .

The word "coset" is borrowed from lattice terminology: Forney's lattice-theoretic reinterpretation of TCM (Chapter 4) shows that an Ungerboeck partition is, for 2D QAM constellations, literally a chain of sublattice cosets of $\mathbb{Z}^2$ . For now, "coset" and "subset" are synonymous.

Definition:
Mapping by Set Partitioning (Ungerboeck Labeling)

A binary labeling $b_{m-1} b_{m-2} \cdots b_0 \mapsto x \in \mathcal{X}$ is a mapping by set partitioning if the bit $b_{m-1}$ (highest-order) selects the first split, $b_{m-2}$ selects the second split given the first, and so on — i.e., the prefix $b_{m-1} \cdots b_{m-i}$ identifies the coset $D_i^{(k)}$ containing $x$ .

Under this labeling, flipping a low-order bit $b_j$ moves the point to a different representative inside the same level- $(j+1)$ subset, so the resulting Euclidean displacement is $\geq \Delta_{j+1}$ .

Set Partition

A sequence of successive binary splits of a signal constellation in which each split is chosen to maximize the minimum Euclidean distance inside the resulting children. Introduced by Ungerboeck (1982), the set partition is the constellation half of a TCM design; the convolutional code is the sequencing half.

Intra-Subset Minimum Distance

The minimum Euclidean distance between any two points in a given subset of a partition. For Ungerboeck's partition of 8-PSK: level 1 gives $\Delta_1^2 = 2$ , level 2 gives $\Delta_2^2 = 4$ (diametrically opposite pairs), so the MSED doubles at each level.

Coset (in Set Partitioning)

A subset of a constellation that arises at some level of an Ungerboeck partition. For a partition of $\mathcal{X}$ with $|\mathcal{X}|=2^m$ into $2^i$ cosets at level $i$ , each coset has $2^{m-i}$ points. The terminology matches Forney's lattice-theoretic reinterpretation (Chapter 4) in which cosets of sublattices are the Ungerboeck subsets for QAM constellations.

Theorem: MSED Doubling Along the 8-PSK Ungerboeck Partition

Consider the 8-PSK constellation $\mathcal{X} = \{e^{j 2\pi k/8} : k = 0, \ldots, 7\}$ (unit-energy, $E_s = 1$ ) with minimum squared distance $\Delta_0^2 = 2(1 - \cos(\pi/4)) = 2 - \sqrt{2}$ . Partition $\mathcal{X}$ in three levels by successively taking every other point. Then

$\Delta_0^2 = 2 - \sqrt{2} \approx 0.586, \qquad \Delta_1^2 = 2, \qquad \Delta_2^2 = 4,$

so $\Delta_1^2 / \Delta_0^2 = 2 + \sqrt{2} \approx 3.414$ and $\Delta_2^2 / \Delta_1^2 = 2$ . Equivalently, at each level the intra-subset MSED at least doubles (in fact the first split more than triples it).

The 8-PSK points are the 8th roots of unity. Taking every other one gives a rotated QPSK (4 points on the unit circle, $90^\circ$ apart, so $\Delta_1^2 = 2$ ). Taking every other point of the QPSK gives a BPSK (2 diametrically opposite points, $\Delta_2^2 = 4$ ). Each split discards the nearest neighbours and keeps the farthest ones.

Show Hint

Use the chord-length formula: for points $e^{j\alpha}$ and $e^{j\beta}$ on the unit circle, $\|e^{j\alpha} - e^{j\beta}\|^2 = 2 - 2\cos(\alpha - \beta)$ .

Level-0 nearest neighbours differ by $\pi/4$ ; level-1 nearest neighbours by $\pi/2$ ; level-2 nearest neighbours by $\pi$ .

Proof

Level 0 — full 8-PSK

Two distinct 8-PSK points are $e^{j 2\pi k/8}$ and $e^{j 2\pi k'/8}$ . Their squared Euclidean distance is $\|e^{j 2\pi k/8} - e^{j 2\pi k'/8}\|^2 = 2 - 2\cos\!\left(\tfrac{2\pi(k - k')}{8}\right).$ The minimum over $k \neq k'$ is attained at $|k - k'| = 1$ , giving $\Delta_0^2 = 2 - 2\cos(\pi/4) = 2 - \sqrt{2}$ .

Level 1 — two cosets of 4 points each

Split $\mathcal{X}$ by parity of $k$ : $D_1^{(0)} = \{e^{j 2\pi k/8} : k \text{ even}\}$ and $D_1^{(1)} = \{e^{j 2\pi k/8} : k \text{ odd}\}$ . Inside each coset, adjacent points differ by $\pi/2$ , so $\Delta_1^2 = 2 - 2\cos(\pi/2) = 2.$ Each coset is a (rotated) QPSK of 4 points. Notice that $\Delta_1^2 / \Delta_0^2 = 2/(2-\sqrt{2}) = 2 + \sqrt{2} \approx 3.414$ — the first split more than triples the squared distance.

Level 2 — four cosets of 2 points each

Split each QPSK coset by parity of $k/2$ . Inside each level-2 coset, the two surviving points are antipodal: their angular separation is $\pi$ , so $\Delta_2^2 = 2 - 2\cos(\pi) = 4.$ Each level-2 coset is a BPSK pair. We have $\Delta_2^2 / \Delta_1^2 = 2$ exactly — the second split doubles the squared distance.

Level 3 — eight singleton cosets

Split each antipodal pair into singletons. There are no pairs inside a single-element set, so $\Delta_3^2 = \infty$ by convention. This completes the Ungerboeck chain $\Delta_0^2 \approx 0.586 \;\to\; \Delta_1^2 = 2 \;\to\; \Delta_2^2 = 4 \;\to\; \Delta_3^2 = \infty,$ monotonically increasing as required. $\blacksquare$

,

Ungerboeck Set-Partition Tree for 8-PSK

Animated construction of the 2-4-8 partition tree. At each level the 8-PSK constellation is split into two equal halves, and the intra-subset minimum squared distance

\Delta_i^2

is displayed. Watch

\Delta_i^2

double (in fact more than double at the first step) as

i

increases.

At each split, the nearest-neighbour pairs are discarded — the intra-subset MSED grows from

\Delta_0^2 \approx 0.586

to

\Delta_1^2 = 2

to

\Delta_2^2 = 4

.

Intra-Subset MSED at Each Partition Level

For each level $i$ of the Ungerboeck partition of a chosen constellation, plot the intra-subset minimum squared Euclidean distance $\Delta_i^2$ . Try 8-PSK, 16-QAM, and 16-PSK and observe the geometry: for 2D QAM the ratios $\Delta_{i+1}^2/\Delta_i^2 = 2$ hold essentially throughout, while for $M$ -PSK the first split is asymmetric because adjacent and antipodal pairs are geometrically different.

Parameters

Constellation

Example: Ungerboeck Partition of 16-QAM

Let $\mathcal{X}$ be the standard 16-QAM constellation $\{a + j b : a, b \in \{\pm 1, \pm 3\}\}$ with minimum inter-point distance $d_0 = 2$ (so $\Delta_0^2 = 4$ ). Construct the four-level Ungerboeck partition and report $\Delta_0^2, \Delta_1^2, \Delta_2^2, \Delta_3^2$ .

Solution

Level 0 — full 16-QAM

The minimum distance is attained by adjacent horizontal or vertical neighbours, so $\Delta_0^2 = 4$ .

Level 1 — two cosets of 8 points (rotated QPSK $\times$ 2)

Split by the parity of $a + b$ (checkerboard coloring). Each coset is an 8-point subset on a sublattice rotated by $45^\circ$ and scaled: inside the coset, nearest neighbours differ by $(\pm 2, \pm 2)$ , so $\Delta_1^2 = 2^2 + 2^2 = 8.$ We have $\Delta_1^2 / \Delta_0^2 = 2$ exactly.

Level 2 — four cosets of 4 points

Further split each level-1 coset by parity of $a$ (or equivalently $b$ ). Inside a level-2 coset, nearest neighbours differ by $(\pm 4, 0)$ or $(0, \pm 4)$ , so $\Delta_2^2 = 16.$ Again $\Delta_2^2 / \Delta_1^2 = 2$ .

Level 3 — eight cosets of 2 points

Split each level-2 coset into an antipodal pair. Inside a pair, the two points differ by $(\pm 4, \pm 4)$ , so $\Delta_3^2 = 32.$ Once more $\Delta_3^2 / \Delta_2^2 = 2$ . The full chain $4 \to 8 \to 16 \to 32$ exhibits clean doubling — a consequence of the 2D lattice structure of QAM. This is exactly Forney's lattice interpretation: each level is a sublattice of index 2 in the previous.

,

Historical Note: Ungerboeck 1982 — The Paper That Changed Modem Design

1982–1994

Gottfried Ungerboeck (IBM Zürich, later Broadcom Fellow) published "Channel Coding with Multilevel/Phase Signals" in IEEE Transactions on Information Theory in January 1982. The paper was met with initial skepticism — the prevailing view was that coding gain on AWGN was essentially capped at the 2–3 dB obtainable from short binary block codes, and that any further gain required expensive bandwidth expansion.

Ungerboeck's insight was geometric rather than algebraic: instead of coding in the binary message space, code in the signal space by labeling constellation points via a partition tree. His central claim — 3 to 6 dB of coding gain without any bandwidth expansion (the same symbol rate, the same constellation size chosen to compensate for the rate penalty of the code) — was verified experimentally almost immediately. By 1984 the V.32 modem standard (9.6 kbps over a 3 kHz telephone line) had adopted an 8-state 32-CROSS TCM; by 1994 the V.34 modem (33.6 kbps) used a 4D 16-state TCM with shell-mapping shaping. The V.34 modem was, for a decade, the most sophisticated digital communications system in consumer use.

Two follow-up papers in IEEE Communications Magazine (1987) made the ideas accessible to a much broader audience and are the most-cited Ungerboeck works today.

, ,

Common Mistake: A Constellation Admits Many Set Partitions — Not All Are Optimal

Mistake:

Assuming that any binary labeling of a constellation yields an Ungerboeck-optimal partition.

Correction:

A partition is Ungerboeck-optimal only if at every level the split maximizes the intra-subset MSED. For 8-PSK, the parity-by-angle split is optimal; splitting by "top half vs. bottom half" is not — it yields $\Delta_1^2 = 2 - \sqrt{2}$ , no better than the parent. For 16-QAM, the checkerboard (parity of $a+b$ ) is optimal; splitting by $a \geq 0$ vs. $a < 0$ is not. In practice, construct the partition by always discarding nearest neighbours at each level; this gives the unique Ungerboeck chain up to symmetry.

Quick Check

For the Ungerboeck partition of unit-energy 8-PSK, what is the ratio $\Delta_2^2 / \Delta_0^2$ ?

$2$

$4$

$4/(2 - \sqrt{2}) \approx 6.83$

$8$

Correction:

4/(2 - \sqrt{2}) \approx 6.83

From TMSED Doubling Along the 8-PSK Ungerboeck Partition, $\Delta_0^2 = 2 - \sqrt{2}$ and $\Delta_2^2 = 4$ , so the ratio is $4/(2 - \sqrt{2}) = 2(2 + \sqrt{2}) \approx 6.83$ , about $8.3$ dB. Two levels of Ungerboeck partitioning buy you roughly an $8$ dB MSED increase — a strong upper bound on what any 8-PSK TCM with 2-bit-per-symbol coset selection can deliver.

Quick Check

Which of the following binary labelings of QPSK is an Ungerboeck labeling (mapping by set partitioning) rather than a Gray labeling?

$(00,01,11,10) \leftrightarrow (1, j, -1, -j)$

$(00,10,11,01) \leftrightarrow (1, j, -1, -j)$

$(00,11,01,10) \leftrightarrow (1, j, -1, -j)$

$(01,10,00,11) \leftrightarrow (1, j, -1, -j)$

Correction:

(00,10,11,01) \leftrightarrow (1, j, -1, -j)

Ungerboeck labeling uses the highest-order bit to choose the level-1 coset (antipodal pair): $b_1 = 0 \mapsto \{1, -1\}$ , $b_1 = 1 \mapsto \{j, -j\}$ . Then $b_0$ selects the specific point within the coset. So the label sequence going around the circle is $00, 10, 11, 01$ , not the Gray sequence $00, 01, 11, 10$ . In Ungerboeck labeling, diametrically opposite points differ by 1 bit (flipping $b_0$ ); in Gray labeling, adjacent points differ by 1 bit.

Key Takeaway

The partition doubles the MSED. Each level of an Ungerboeck partition at least doubles (and in the first 8-PSK level more than triples) the intra-subset minimum squared distance. A TCM scheme that uses a rate- $\tilde{m}/(\tilde{m}+1)$ convolutional code to select a level- $(\tilde{m}+1)$ coset inherits this distance amplification: the free Euclidean distance of the code is at worst $\Delta_{\tilde{m}+1}$ , regardless of how bad the convolutional code is. The coding gain is bought entirely by the partition geometry, not by the code.

Set Partitioning of Signal Constellations

Why Partition a Constellation?

Definition: Coded Modulation

Definition: Set Partition (Ungerboeck Chain)

Definition: Intra-Subset Minimum Squared Euclidean Distance

Definition: Coset (Subset) of a Partition

Definition: Mapping by Set Partitioning (Ungerboeck Labeling)

Set Partition

Intra-Subset Minimum Distance

Coset (in Set Partitioning)

Theorem: MSED Doubling Along the 8-PSK Ungerboeck Partition

Level 0 — full 8-PSK

Level 1 — two cosets of 4 points each

Level 2 — four cosets of 2 points each

Level 3 — eight singleton cosets

Ungerboeck Set-Partition Tree for 8-PSK

Intra-Subset MSED at Each Partition Level

Parameters

Example: Ungerboeck Partition of 16-QAM

Level 0 — full 16-QAM

Level 1 — two cosets of 8 points (rotated QPSK $\times$ 2)

Level 2 — four cosets of 4 points

Level 3 — eight cosets of 2 points

Historical Note: Ungerboeck 1982 — The Paper That Changed Modem Design

Common Mistake: A Constellation Admits Many Set Partitions — Not All Are Optimal

Quick Check

Quick Check

Key Takeaway

Definition:
Coded Modulation

Definition:
Set Partition (Ungerboeck Chain)

Definition:
Intra-Subset Minimum Squared Euclidean Distance

Definition:
Coset (Subset) of a Partition

Definition:
Mapping by Set Partitioning (Ungerboeck Labeling)