Convolutional codes

Convolutional coding: encoder and Viterbi decoder (decision D4).

Batch-vectorized implementations: the only Python loop is over time (the trellis recursion is irreducible); everything across batch and states is numpy. Branch metrics are computed inside the time loop, so memory stays bounded (architecture document, section 8).

class ConvolutionalEncoder(g: tuple[int, ...] = (91, 121), *, terminated: bool = True, name: str = 'conv_encoder')

Rate \(1/n\) convolutional encoder.

Signal Model

With input bits \(x[m]\) and generator polynomials \(g_0, \dots, g_{n-1}\) of constraint length \(K\), the coded stream interleaves the \(n\) parity outputs:

\[y[nm + i] = \bigoplus_{l=0}^{K-1} g_{i}[l] \, x[m - l], \qquad i = 0, \dots, n-1\]

The default generators \((133, 171)_8\) with \(K = 7\) are the standard NASA/Voyager code (free distance 10). When terminated is True, \(K - 1\) zero tail bits flush the register so the decoder can end in the all-zero state.

Axes: axis -1 – bits on the last axis, broadcast over the rest; (..., N) maps to (..., n (N + K - 1)) when terminated.

param g:

Generator polynomials \(g_i\) in octal (MSB = current input tap). Default (0o133, 0o171).

type g:

tuple of int

param terminated:

Append \(K - 1\) zero tail bits. Default True.

type terminated:

bool, keyword-only

param name:

Name of the processor. Default "conv_encoder".

type name:

str, keyword-only

References

J. G. Proakis, M. Salehi, Digital Communications, 5th ed., McGraw-Hill, 2008, Section 8.2.

Examples

>>> encoder = ConvolutionalEncoder((0o5, 0o7))  # K=3, rate 1/2
>>> bits = np.array([1, 0, 1, 1])
>>> print(encoder(bits))
[1 1 0 1 0 0 1 0 1 0 1 1]

property rate: float

Code rate \(1/n\) (tail bits not counted).

class ViterbiDecoder(g: tuple[int, ...] = (91, 121), *, soft: bool = False, terminated: bool = True, name: str = 'viterbi')

Maximum-likelihood decoder for a rate \(1/n\) convolutional code.

Signal Model

The decoder finds the information sequence \(\hat{x}\) whose coded sequence \(c(\hat{x})\) minimizes the path metric

\[\hat{x} = \arg\min_{x} \sum_{m, i} d\big(r[nm+i],\, c_i[m]\big)\]

where \(d\) is the Hamming distance for hard decisions (soft=False, input bits in \(\{0, 1\}\)) and the max-log metric \(d(r, c) = r \, c\) for soft decisions (soft=True, input log-likelihood ratios \(r = \log P(0)/P(1)\), as produced by SymbolDemapper(..., soft=True)).

Axes: axis -1 – coded samples on the last axis, batch-vectorized Viterbi recursion with a Python loop over time only (decision D4); (..., n (N + K - 1)) maps back to (..., N) when terminated.

param g:

Generator polynomials \(g_i\) in octal; must match the encoder. Default (0o133, 0o171).

type g:

tuple of int

param soft:

Interpret the input as LLRs instead of hard bits. Default False.

type soft:

bool, keyword-only

param terminated:

Assume \(K - 1\) zero tail bits (decoding ends in state 0). Default True.

type terminated:

bool, keyword-only

param name:

Name of the processor. Default "viterbi".

type name:

str, keyword-only

raises ShapeError:

If the coded length is not a multiple of \(n\), or shorter than the tail.

References

A. J. Viterbi, “Error bounds for convolutional codes and an asymptotically optimum decoding algorithm,” IEEE Trans. Inf. Theory 13(2), 1967; Proakis & Salehi, 5th ed., Section 8.2.

Examples

>>> encoder = ConvolutionalEncoder((0o5, 0o7))
>>> decoder = ViterbiDecoder((0o5, 0o7))
>>> coded = encoder(np.array([1, 0, 1, 1]))
>>> coded[2] ^= 1  # one channel error
>>> print(decoder(coded))
[1 0 1 1]