Code analysis

Analytical reference for convolutional codes (decisions D4, D7).

The distance spectrum is enumerated from the trellis of the code itself, never transcribed from a textbook table: the same reg = (b << (K - 1)) | state recursion that ConvolutionalEncoder runs forward is walked breadth-first here, one trellis step per iteration, to collect the error events. The published tables then serve as a cross-check, not as a source – the enumerator returns \(d_{\mathrm{free}} = 10\) for the NASA (133, 171) code because the trellis says so.

That spectrum feeds the union bound, which is the analytical curve a soft-decision Viterbi decoder is measured against (validation/fec_union_bound.py).

class DistanceSpectrum(g: tuple[int, ...], K: int, k: int, rate: float, d_free: int, distances: NDArray[int64], a_d: NDArray[int64], beta_d: NDArray[int64])

Weight enumerator of the error events of a rate \(1/n\) code.

Signal Model

An error event is a trellis path that leaves the all-zero path at time 0 (input bit 1), stays away from the all-zero state, and merges back into it later. Collecting these paths by output weight \(d\) and input weight \(i\) gives the transfer function of the code,

\[T(D, N) = \sum_{d \ge d_{\mathrm{free}}} \sum_{i \ge 1} a_{d,i} \, D^{d} N^{i},\]

of which this object stores the two marginals used by every performance bound:

\[a_d = \sum_i a_{d,i}, \qquad \beta_d = \sum_i i \, a_{d,i} = \left. \frac{\partial T}{\partial N} \right|_{N = 1} \text{, coefficient of } D^d\]

\(a_d\) counts the error events of output weight \(d\); \(\beta_d\) counts the information bit errors they carry, which is what union_bound_ber() weighs.

param g:

Generator polynomials \(g_i\) in octal, as passed to ConvolutionalEncoder.

type g:

tuple of int

param K:

Constraint length \(K\) implied by g.

type K:

int

param k:

Number of information bits per trellis step \(k\); always 1 for the rate \(1/n\) codes this module enumerates.

type k:

int

param rate:

Code rate \(R = k/n\).

type rate:

float

param d_free:

Free distance \(d_{\mathrm{free}}\), the smallest output weight of an error event.

type d_free:

int

param distances:

The weights \(d\) covered, d_free through d_max inclusive (gaps are kept, with a zero coefficient: a code whose events all have even weight must show it).

type distances:

np.ndarray of int

param a_d:

Number of error events \(a_d\), aligned with distances.

type a_d:

np.ndarray of int

param beta_d:

Cumulated information weight \(\beta_d\), aligned with distances.

type beta_d:

np.ndarray of int

References

A. J. Viterbi, “Convolutional codes and their performance in communication systems,” IEEE Trans. Commun. Technol. 19(5), 1971 (transfer function \(T(D, N)\) and its derivative); J. G. Proakis, M. Salehi, Digital Communications, 5th ed., McGraw-Hill, 2008, Section 8.2.

Examples

>>> spectrum = distance_spectrum((0o5, 0o7), n_terms=3)
>>> print(spectrum.d_free, spectrum.rate)
5 0.5
>>> print(spectrum.distances, spectrum.a_d, spectrum.beta_d)
[5 6 7] [1 2 4] [ 1  4 12]

distance_spectrum(g: Sequence[int] = (91, 121), *, n_terms: int = 6, d_max: int | None = None) → DistanceSpectrum

Enumerate the distance spectrum of a rate \(1/n\) convolutional code.

Signal Model

The encoder register content is \(\mathrm{reg} = (b \ll (K-1)) \,|\, s\) for input bit \(b\) in state \(s\), the very recursion run by ConvolutionalEncoder; the branch output weight is \(w(\mathrm{reg}) = \sum_{i} g_i \cdot \mathrm{reg} \bmod 2\). An error event is a path \(0 \to s_1 \to \dots \to s_L \to 0\) with \(b = 1\) on the first branch and \(s_\ell \ne 0\) in between. Because the code is linear, comparing every path pair reduces to comparing every path to the all-zero one, so these events carry the whole error behaviour.

Counting them by output weight \(d\) and input weight yields the coefficients of the transfer function \(T(D, N)\):

\[a_d = \#\{\text{error events of output weight } d\}, \qquad \beta_d = \sum_{\text{events of weight } d} w_{\mathrm{in}}(\text{event})\]

and \(d_{\mathrm{free}} = \min \{d : a_d > 0\}\). The search is a breadth-first walk of the trellis pruned at d_max (one iteration per trellis step); the walk terminates because, absent a zero-weight cycle, every long path eventually exceeds d_max.

Axes: not a signal transform – a pure function of the code parameters, returning arrays indexed by output weight.

param g:

Generator polynomials \(g_i\) in octal (MSB = current input tap), identical to the encoder’s. Default (0o133, 0o171), the NASA/Voyager \(K = 7\) code.

type g:

tuple of int

param n_terms:

Number of non-zero coefficients \(a_d\) wanted; d_max is grown until that many are found. Ignored when d_max is given. Default 6.

type n_terms:

int, optional, keyword-only

param d_max:

Largest output weight \(d\) enumerated. Larger means a tighter union_bound_ber() at low SNR and a longer run.

type d_max:

int, optional, keyword-only

returns:

DistanceSpectrum – The coefficients \(a_d\) and \(\beta_d\) for \(d_{\mathrm{free}} \le d \le d_{\max}\).

raises ValueError:

If g is catastrophic – a zero-output-weight cycle makes \(a_d\) infinite – or if no error event is found below d_max.

References

A. J. Viterbi, “Convolutional codes and their performance in communication systems,” IEEE Trans. Commun. Technol. 19(5), pp. 751-772, 1971 (transfer function of the state diagram); J. G. Proakis, M. Salehi, Digital Communications, 5th ed., McGraw-Hill, 2008, Section 8.2.

Examples

>>> spectrum = distance_spectrum((0o5, 0o7), n_terms=4)
>>> print(spectrum.d_free, spectrum.a_d, spectrum.beta_d)
5 [1 2 4 8] [ 1  4 12 32]
>>> nasa = distance_spectrum(n_terms=3)   # (133, 171), K = 7
>>> print(nasa.d_free, nasa.distances, nasa.a_d)
10 [10 11 12 13 14] [ 11   0  38   0 193]

union_bound_ber(spectrum: DistanceSpectrum, ebn0_dB: ArrayLike) → NDArray[float64]

Union bound on the bit error rate of soft-decision Viterbi decoding over AWGN.

Signal Model

Antipodal signalling over AWGN, \(y[n] = x[n] + b[n]\) with \(x[n] = \pm\sqrt{E_s}\) and \(b[n] \sim \mathcal{N}(0, N_0/2)\), decoded by a maximum-likelihood (soft) Viterbi decoder. Two codewords differing in \(d\) coded bits are confused with probability \(Q(\sqrt{2 d R E_b/N_0})\); summing that pairwise probability over every error event, each weighted by the number \(\beta_d\) of information bits it flips, over-counts the overlapping events and therefore bounds the bit error rate:

\[P_b \le \frac{1}{k} \sum_{d \ge d_{\mathrm{free}}} \beta_d \, Q\!\left(\sqrt{2 d R \frac{E_b}{N_0}}\right), \qquad Q(u) = \frac{1}{\sqrt{2\pi}} \int_u^{\infty} e^{-t^2/2}\, dt\]

Two honest caveats, both visible in validation/fec_union_bound.py: the sum is truncated at the d_max of spectrum, so it is a genuine upper bound only where its tail is negligible; and the full series only converges above the code’s cutoff rate. Below roughly 3 dB the truncated sum keeps growing with d_max and usually exceeds 1 – a value \(> 1\) is not a tight bound, it is no information at all. Above 4 dB the terms fall geometrically, the truncation error is negligible, and the bound is within a small factor of the simulated curve.

Axes: element-wise – a scalar conversion applied pointwise to an array of operating points.

param spectrum:

Weight enumerator of the code, from distance_spectrum(); supplies \(\beta_d\), the weights \(d\), the rate \(R\) and the number of inputs per step \(k\).

type spectrum:

DistanceSpectrum

param ebn0_dB:

Information-bit-energy-to-noise ratio \(E_b/N_0\) in dB (energy per information bit, so the rate loss is already accounted for).

type ebn0_dB:

float or np.ndarray

returns:

np.ndarray – Upper bound on \(P_b\), same shape as ebn0_dB. Values above 1 are returned as computed, not clipped: a bound that exceeds 1 must look useless, because it is.

References

J. G. Proakis, M. Salehi, Digital Communications, 5th ed., McGraw-Hill, 2008, Section 8.2 (union bound for soft-decision decoding, eq. 8.2-22); A. J. Viterbi, “Convolutional codes and their performance in communication systems,” IEEE Trans. Commun. Technol. 19(5), 1971.

Examples

>>> spectrum = distance_spectrum((0o5, 0o7), d_max=26)   # K = 3
>>> print(f"{float(union_bound_ber(spectrum, 5.0)):.3e}")
9.171e-05
>>> print(f"{float(union_bound_ber(distance_spectrum(d_max=30), 5.0)):.3e}")
4.427e-07