Ferkans — Interactive Telecom Tutor

From Partition to Mapping: Turning Geometry into Bits

In §Set Partitioning of Signal Constellations we saw that an Ungerboeck partition of a $2^m$ -point constellation produces $m+1$ levels of cosets, each level at least doubling the intra-subset MSED. That is a property of the geometry. To build a coded-modulation scheme we need a mapping from binary sequences to constellation points — a rule that tells the encoder which point to transmit given the output of the convolutional code.

The punchline is this: if we label each constellation point with a binary address $b_{m-1} \cdots b_0$ such that the first $i$ bits identify the level- $i$ coset, then a convolutional code acting on the low-order bits (the coset-selecting bits) automatically enjoys a large intra-sequence Euclidean distance, because flipping a low-order bit moves us between points of the same coset at a high partition level. The high-order bits (uncoded) pick a specific point inside the coset.

This is the entire recipe: partition → label → separate coded from uncoded bits → push the code to the bits that select the smallest coset. The rest of the chapter spells out the consequences.

Definition:
Trellis-Coded Modulation (TCM)

A trellis-coded modulation (TCM) scheme transmits $m$ information bits per channel use from a constellation $\mathcal{X}$ of size $2^{m+1}$ (one redundancy bit per symbol) according to the following encoder:

Of the $m$ information bits per symbol, $\tilde{m} \leq m$ are fed into a rate- $\tilde{m}/(\tilde{m}+1)$ convolutional encoder whose $(\tilde{m}+1)$ -bit output selects a level- $(\tilde{m}+1)$ coset of an Ungerboeck partition.
The remaining $m - \tilde{m}$ uncoded information bits select one of the $2^{m - \tilde{m}}$ points inside the chosen coset.

The free Euclidean distance of the TCM scheme is the minimum Euclidean distance between any two distinct code sequences it can produce.

The spectral efficiency is $m$ bits/symbol — same as an uncoded $2^m$ -point constellation. The constellation has been doubled to $2^{m+1}$ , but no additional bandwidth is used. This is the "coding gain without bandwidth expansion" feature Ungerboeck emphasized.

,

Definition:
Parallel Transitions

In the TCM trellis, two edges between the same pair of states that differ only in the uncoded bits are called parallel transitions. They correspond to distinct constellation points lying in the same level- $(\tilde{m}+1)$ coset.

The contribution of parallel transitions to the free Euclidean distance is at least $\Delta_{\tilde{m}+1}$ , because two parallel-transition sequences differ in exactly one symbol and the two competing symbols lie in the same coset at level $\tilde{m}+1$ .

Parallel transitions exist only when $\tilde{m} < m$ , i.e., when at least one information bit is left uncoded. They can dominate the free distance when the convolutional code is strong enough that non-parallel error events are farther away — more on this in s03.

,

Definition:
Subset Decoding (Within-Coset Nearest-Point Rule)

Given a received sample $y \in \mathbb{C}$ and a coset $D$ , the subset decoder outputs

$\hat{x}_D = \operatorname*{arg\,min}_{x \in D} \|y - x\|^2.$

In TCM, subset decoding is performed as a preprocessing step for every coset at every time step: the Viterbi algorithm then operates on a trellis whose branch metric at each transition is the squared Euclidean distance to the subset-decoded point of the corresponding coset.

Subset decoding decouples the uncoded-bit decision from the trellis search, reducing the effective branch-metric computation to "find nearest point in coset" ( $2^{m - \tilde{m}}$ candidates) followed by Viterbi over the much smaller coset trellis.

,

Definition:
Free Euclidean Distance

The free (squared) Euclidean distance $d_{\rm free}^2$ of a TCM scheme is the minimum squared Euclidean distance between any two distinct infinite code sequences $\mathbf{x} = (x_0, x_1, x_2, \ldots)$ and $\mathbf{x}' = (x_0', x_1', x_2', \ldots)$ produced by the encoder:

$d_{\rm free}^2 \;\triangleq\; \min_{\mathbf{x} \neq \mathbf{x}'} \sum_{k \geq 0} \|x_k - x_k'\|^2.$

Since the TCM trellis is linear in the state transitions (not in the symbol values), $d_{\rm free}^2$ can be computed by examining all finite-length error events — paths that diverge from a common state at time $k_1$ and first remerge at time $k_2 > k_1$ .

The free distance plays the role the minimum Hamming distance $d_{\rm free}^{(H)}$ plays in classical convolutional codes — it governs the asymptotic error performance on AWGN via the union bound. The bit-error probability at high SNR is approximately $P_e \approx N_{\rm free}\,Q\!\left(\sqrt{d_{\rm free}^2 / (2N_0)}\right)$ , where $N_{\rm free}$ is the number of error events achieving $d_{\rm free}^2$ (the "error coefficient").

,

Parallel Transitions

Two or more trellis edges connecting the same pair of states. In TCM they are labeled with distinct points from the same level- $(\tilde{m}+1)$ coset, and the distance between parallel edges equals the intra-subset MSED at that level. Parallel transitions bound the free distance from above: $d_{\rm free}^2 \leq \Delta_{\tilde{m}+1}^2$ .

Subset Decoding

The preprocessing step in TCM where, for each coset and each received sample, the nearest point within that coset is found and its squared distance to the received sample is used as the branch metric in the Viterbi decoder. Reduces decoding complexity from $|\mathcal{X}|$ to $2^{\tilde{m}+1}$ branches per time step, times the in-coset search cost.

Free (Euclidean) Distance

The minimum squared Euclidean distance between any two distinct code sequences in a TCM scheme. Analogue of free Hamming distance for binary convolutional codes. On AWGN, $d_{\rm free}^2$ determines the asymptotic coding gain via $\gamma_c = d_{\rm free}^2 / d_{\rm uncoded}^2$ .

Related: Free Euclidean Distance

Theorem: Lower Bound on Free Euclidean Distance via Partition Levels

Consider a TCM scheme built from a rate- $\tilde{m}/(\tilde{m}+1)$ convolutional code driving an Ungerboeck partition of a $2^{m+1}$ -point constellation. Let $\Delta_i^2$ denote the intra-subset MSED at level $i$ of the partition and let $d_{\rm free}^{(H)}$ be the minimum Hamming distance of the convolutional code when its output labels are read as binary addresses of the $2^{\tilde{m}+1}$ level- $(\tilde{m}+1)$ cosets. Then

$d_{\rm free}^2 \;\geq\; \min\!\left\{\,\Delta_{\tilde{m}+1}^2,\;\; \Delta_1^2 \cdot d_{\rm free}^{(H)}\,\right\}.$

The first term bounds error events that traverse parallel transitions (single-symbol errors within a coset); the second bounds error events that stay on distinct coset sequences for at least $d_{\rm free}^{(H)}$ time steps.

Two error mechanisms compete. Parallel transitions give an error at minimum-distance $\Delta_{\tilde{m}+1}$ . Coset-sequence errors accumulate Euclidean distance along each time step where the two coset sequences differ — each such time step contributes at least $\Delta_1^2$ (the distance between the two level-1 cosets) and the two sequences differ in at least $d_{\rm free}^{(H)}$ time steps by the Hamming-distance property of the convolutional code. The free Euclidean distance is then the minimum of the two mechanisms. A good Ungerboeck design balances them: pick $\tilde{m}$ and the convolutional code so that $\Delta_{\tilde{m}+1}^2 \approx \Delta_1^2 \cdot d_{\rm free}^{(H)}$ .

Show Hint

Split the analysis into two cases: error events of length 1 (single-symbol errors) and error events of length $\geq 2$ .

For length-1 events, the two competing symbols must lie in the same coset, so their distance is $\geq \Delta_{\tilde{m}+1}$ .

For longer events, at every time step at which the two coset sequences differ, the Euclidean displacement is at least $\Delta_1$ .

Proof

Case 1 — single-symbol error events

Suppose two code sequences $\mathbf{x}$ and $\mathbf{x}'$ differ in exactly one symbol, say at time $k$ , and are identical elsewhere. Identical state transitions at time $k$ mean the coset index is the same for both sequences at time $k$ : the only way they can differ at $k$ is via the uncoded bits, i.e., they take parallel transitions. The two transmitted points lie in the same level- $(\tilde{m}+1)$ coset, so $\sum_n \|x_n - x_n'\|^2 = \|x_k - x_k'\|^2 \;\geq\; \Delta_{\tilde{m}+1}^2.$

Case 2 — multi-symbol error events

Now suppose $\mathbf{x}$ and $\mathbf{x}'$ differ at two or more time steps, in a contiguous block $[k_1, k_2]$ (the error event). The coset sequences $\mathbf{c}$ and $\mathbf{c}'$ must therefore differ at at least one time step inside $[k_1, k_2]$ — otherwise the state trajectories would coincide and so would the (otherwise identical uncoded-bit decisions). Because the convolutional code has minimum Hamming distance $d_{\rm free}^{(H)}$ , the binary-label sequences of $\mathbf{c}$ and $\mathbf{c}'$ differ in at least $d_{\rm free}^{(H)}$ time steps (bit-by-bit equivalent of symbol index difference). At every such time step, $x_n$ and $x_n'$ lie in different level-1 cosets (they differ in the highest-order coset bit), so $\|x_n - x_n'\|^2 \geq \Delta_1^2$ .

Case 2 — accumulated distance

Summing over the at-least- $d_{\rm free}^{(H)}$ differing time steps, $\sum_n \|x_n - x_n'\|^2 \;\geq\; d_{\rm free}^{(H)} \cdot \Delta_1^2.$ The non-differing coset time steps contribute $\geq 0$ (they may still differ in uncoded bits inside a coset, but never less than zero).

Combine the two cases

The free Euclidean distance is the minimum over all non-zero error events, which is at most the minimum of the two case bounds: $d_{\rm free}^2 \;\geq\; \min\!\left\{\Delta_{\tilde{m}+1}^2,\; d_{\rm free}^{(H)} \cdot \Delta_1^2\right\}. \qquad \blacksquare$ When the bound is tight, which it is for all of Ungerboeck's tabulated TCM codes, the design problem reduces to balancing the two terms by the choice of $\tilde{m}$ and the convolutional code.

,

BER of Ungerboeck 8-PSK TCM vs. Uncoded QPSK

Bit-error rate of Ungerboeck's 8-PSK TCM family at various numbers of trellis states ( $N_s \in \{4, 8, 16, 32, 64\}$ ) compared to uncoded QPSK (same 2 bit/symbol spectral efficiency) on AWGN. Select the number of states to highlight. Observe that adding states (longer memory) improves coding gain, but with diminishing returns: 4-state gives ~3 dB, 8-state ~3.6 dB, 16-state ~4.1 dB, 64-state ~4.6 dB. The gap to the ultimate coding-gain ceiling ( $\sim 6$ dB, set by the partition geometry) is never closed by trellis memory alone.

Parameters

Highlighted trellis states

Example: Free Euclidean Distance of the 4-State 8-PSK TCM

Consider Ungerboeck's canonical 4-state 8-PSK TCM: $m = 2$ information bits per symbol, $\tilde{m} = 1$ coded bit, rate- $1/2$ convolutional code with generator polynomials $(g_0, g_1) = (5, 2)_{\rm oct}$ (in systematic feedback form — the encoder has 2 memory cells, so $\nu = 2$ and $N_s = 4$ ). The code output selects a level-2 coset of the 8-PSK partition (4 cosets of 2 points each, with $\Delta_2^2 = 2$ ). The 1 uncoded bit selects a point inside the coset, with $\Delta_3^2 = 4$ distance to its coset partner.

Compute a lower bound on $d_{\rm free}^2$ using TLower Bound on Free Euclidean Distance via Partition Levels, then state the actual value from Ungerboeck's Table I (1982).

Solution

Read off the partition distances

For unit-energy 8-PSK, we computed in TMSED Doubling Along the 8-PSK Ungerboeck Partition: $\Delta_0^2 = 2 - \sqrt{2}, \qquad \Delta_1^2 = 2, \qquad \Delta_2^2 = 4.$ The coset-selection bit chooses between a level-1 coset (since $\tilde{m} = 1$ , a rate- $1/2$ code produces a 2-bit output that indexes one of 4 level-2 cosets — but the first output bit indexes the level-1 coset, which is what the level-1 distance $\Delta_1^2 = 2$ refers to). The parallel-transition distance is $\Delta_{\tilde{m}+1}^2 = \Delta_2^2 = 4$ .

Wait — we must be careful. The rate- $1/2$ convolutional code has two output bits per symbol; together they specify 4 level-2 cosets. When two code paths diverge, their output-bit sequences differ; the Hamming distance of those sequences is what the convolutional code's $d_{\rm free}^{(H)}$ measures. But within any one time step the two output labels may differ in either the level-1 bit or the level-2 bit (or both). The minimum Euclidean distance at a single differing time step is therefore $\Delta_1^2 = 2$ (the smaller of $\Delta_1^2$ and $\Delta_2^2$ ).

Compute $d_{\rm free}^{(H)}$ for the rate-1/2, $K=3$ convolutional code

The rate- $1/2$ convolutional code with $(g_0, g_1) = (5, 2)_{\rm oct} = (101, 010)_2$ has constraint length $K = 3$ and free Hamming distance $d_{\rm free}^{(H)} = 3$ .

(More precisely: one derives this from the code's state-transition diagram or from standard tables — see $1/2$ $1/2$ Convolutional Codes over BPSK" data-ref-type="interactive_plot">📊BER of Rate- $1/2$ Convolutional Codes over BPSK. A length-3 error event is dominant.)

Lower bound

Applying TLower Bound on Free Euclidean Distance via Partition Levels, $d_{\rm free}^2 \;\geq\; \min\!\left\{\Delta_2^2,\; d_{\rm free}^{(H)} \cdot \Delta_1^2\right\} = \min\{4,\; 3 \cdot 2\} = \min\{4, 6\} = 4.$ Parallel transitions dominate: a single-symbol error between two parallel edges gives $d^2 = \Delta_2^2 = 4$ , which is smaller than the accumulated distance of any coset-sequence error event.

Actual value from Ungerboeck's Table I

Ungerboeck (1982, Table I) tabulates $d_{\rm free}^2 = 4$ for the 4-state 8-PSK TCM — confirming that parallel transitions indeed achieve the minimum free Euclidean distance. Since the uncoded QPSK baseline has $d_{\rm uncoded}^2 = 2$ (unit energy), the asymptotic coding gain is $\gamma_c = d_{\rm free}^2 / d_{\rm uncoded}^2 = 4/2 = 2 \;\;\longleftrightarrow\;\; 3.0 \text{ dB}.$ This is the famous "3 dB from the simplest TCM" figure. Larger trellises (8, 16, 64 states) break the tie by designing the code so that $d_{\rm free}^{(H)} \cdot \Delta_1^2 > \Delta_2^2$ — parallel transitions no longer dominate, and the gain rises toward 6 dB.

,

BER of Rate- $1/2$ Convolutional Codes over BPSK

Bit-error rate (coded) of rate- $1/2$ binary convolutional codes of constraint length $K \in \{3, 4, 5, 6, 7\}$ over BPSK/AWGN. This is the workhorse building block of TCM: the convolutional code drives the coset-selection bits. Notice how quickly adding constraint length pays off — adding one memory cell roughly doubles the decoder complexity but gains $\sim 0.3$ dB.

This plot is the binary precursor to the TCM BER plot in this section: combining one of these convolutional codes with an Ungerboeck 8-PSK partition yields the corresponding row of Ungerboeck's Table I.

Parameters

Constraint length

K

Common Mistake: Hamming Distance and Euclidean Distance Are Not the Same Currency

Mistake:

Confusing the free Hamming distance $d_{\rm free}^{(H)}$ of the underlying convolutional code with the free Euclidean distance $d_{\rm free}^2$ of the TCM scheme.

Correction:

$d_{\rm free}^{(H)}$ measures how many bit positions two distinct coset sequences must differ in — a property of the convolutional code alone.
$d_{\rm free}^2$ measures squared Euclidean distance in the signal space — a property of the convolutional code and the partition together.

These two scale differently with code memory: doubling the states of a binary convolutional code roughly adds $1$ to $d_{\rm free}^{(H)}$ ; doubling the states of a TCM code typically adds $\Delta_1^2$ to $d_{\rm free}^2$ (about 3 dB worth), but only until parallel transitions become the bottleneck. Once they do, increasing state count buys nothing until $\tilde{m}$ is also increased.

Common Mistake: Mixing Up Coded and Uncoded Bits in the TCM Encoder

Mistake:

Believing that all $m$ information bits must go through the convolutional encoder.

Correction:

Only $\tilde{m} \leq m$ of the bits are coded. The remaining $m - \tilde{m}$ ride uncoded through the encoder — they select a specific point within the coset chosen by the code. This is the whole point of the partition trick: high-order uncoded bits live in a large intra-subset MSED, so they do not need protection. Forcing all bits through the code wastes trellis resources on bits that are already geometrically robust.

Quick Check

In the 4-state 8-PSK TCM of EFree Euclidean Distance of the 4-State 8-PSK TCM, the free Euclidean distance is $d_{\rm free}^2 = 4$ . Which type of error event achieves this minimum?

A long error event with $d_{\rm free}^{(H)} = 3$ differing coset positions.

A single-symbol error along parallel transitions (within one coset).

An uncoded-bit-only error in the rightmost flat region of the trellis.

A catastrophic error event from a poorly chosen generator polynomial.

Correction:

A single-symbol error along parallel transitions (within one coset).

From the lower bound $d_{\rm free}^2 \geq \min\{\Delta_2^2,\, d_{\rm free}^{(H)} \cdot \Delta_1^2\} = \min\{4, 6\} = 4$ , the minimum is achieved by parallel transitions (which give exactly $\Delta_2^2 = 4$ ). The longer error event would give $6 > 4$ , so it is not the dominant error mechanism. This is a sign that the 4-state code is parallel-transition-limited: to improve $d_{\rm free}^2$ further one must either go to a level-3 partition (splitting each antipodal pair) or increase the trellis memory and the code's $d_{\rm free}^{(H)}$ .

Quick Check

A TCM scheme transmits 3 bits/symbol at baud rate $1/T_s$ . The constellation size is doubled to 16-QAM, and $\tilde{m} = 2$ of the 3 information bits are coded by a rate- $2/3$ convolutional code. What is the spectral efficiency and what is the rate of bandwidth expansion compared to uncoded 8-PSK at the same bit rate?

3 bit/symbol, bandwidth expansion factor $1$ (no expansion).

3 bit/symbol, bandwidth expansion factor $3/2$ .

2 bit/symbol, bandwidth expansion factor $1$ .

4 bit/symbol, bandwidth expansion factor $4/3$ .

Correction:

3 bit/symbol, bandwidth expansion factor

1

(no expansion).

Spectral efficiency is $m = 3$ bits/symbol — the added redundancy is absorbed by enlarging the constellation from 8 to 16 points at the same baud rate. This is exactly Ungerboeck's signature feature: coding gain without bandwidth expansion. Compared to uncoded 8-PSK at the same bit rate, the bandwidth is identical; only the constellation is denser.

Hamming Distance (binary codes) vs. Euclidean Distance (TCM)

Property	Binary convolutional code	TCM
Distance currency	Hamming ( $d_H$ )	Squared Euclidean ( $d^2$ )
Relevant minimum distance	$d_{\rm free}^{(H)}$	$d_{\rm free}^2$
Code operates on	Bits	Signal points (via coset indices)
Soft-decision gain over hard	$\sim 2$ dB	Built-in (decoder is inherently soft)
Spectral efficiency	Reduced by rate $R$	Unchanged — constellation expanded instead
Dominant error mechanism	Always a $d_{\rm free}^{(H)}$ -length event	Either parallel transitions or long events — whichever is smaller

Key Takeaway

A good TCM design balances parallel transitions against longer error events. The free distance is $d_{\rm free}^2 = \min\{\Delta_{\tilde{m}+1}^2,\; d_{\rm free}^{(H)} \cdot \Delta_1^2\}$ . A design with a very strong code but small $\tilde{m}$ (few coded bits) is parallel-transition-limited — the geometry, not the code, sets the ceiling. A design with a weak code but many coded bits is Hamming-distance-limited. Ungerboeck's tables pick $(\tilde{m}, \nu, g_0, g_1)$ so that the two terms are close to equal at each state count.

Mapping by Set Partitioning and Distance Maximization

From Partition to Mapping: Turning Geometry into Bits

Definition: Trellis-Coded Modulation (TCM)

Definition: Parallel Transitions

Definition: Subset Decoding (Within-Coset Nearest-Point Rule)

Definition: Free Euclidean Distance

Parallel Transitions

Subset Decoding

Free (Euclidean) Distance

Theorem: Lower Bound on Free Euclidean Distance via Partition Levels

Case 1 — single-symbol error events

Case 2 — multi-symbol error events

Case 2 — accumulated distance

Combine the two cases

BER of Ungerboeck 8-PSK TCM vs. Uncoded QPSK

Parameters

Example: Free Euclidean Distance of the 4-State 8-PSK TCM

Read off the partition distances

Compute $d_{\rm free}^{(H)}$ for the rate-1/2, $K=3$ convolutional code

Lower bound

Actual value from Ungerboeck's Table I

BER of Rate-1/21/21/2 Convolutional Codes over BPSK

Parameters

Common Mistake: Hamming Distance and Euclidean Distance Are Not the Same Currency

Common Mistake: Mixing Up Coded and Uncoded Bits in the TCM Encoder

Quick Check

Quick Check

Hamming Distance (binary codes) vs. Euclidean Distance (TCM)

Key Takeaway

Definition:
Trellis-Coded Modulation (TCM)

Definition:
Parallel Transitions

Definition:
Subset Decoding (Within-Coset Nearest-Point Rule)

Definition:
Free Euclidean Distance

BER of Rate- $1/2$ Convolutional Codes over BPSK