LDPC codes#

LDPC coding: systematic encoder and min-sum decoder (decision D5).

Same vectorization philosophy as the convolutional module (D4): the decoder state lives in (batch, n_edges) arrays, message-passing updates are segmented numpy reductions (ufunc.reduceat) over the edges of the Tanner graph, and the only Python loop is over decoding iterations.

class LDPCEncoder(H: ndarray, *, name: str = 'ldpc_encoder')[source]#

Systematic encoder for an LDPC code given its parity-check matrix.

Signal Model#

The codeword \(c \in \{0,1\}^n\) satisfies \(H c = 0\) over GF(2). Bringing \(H\) to reduced row echelon form partitions the columns into \(r\) pivot (parity) positions and \(k = n - r\) free (information) positions; the information bits \(u\) are copied to the free positions and each parity is

\[c_{p_i} = \bigoplus_{j \in \mathrm{free}} \tilde{H}_{ij} \, u_j\]

where \(\tilde{H}\) is the reduced matrix. Linearly dependent rows of \(H\) are detected and ignored, so \(k\) can exceed the design dimension \(n - m\).

Axes: axis -1 – information bits on the last axis, broadcast over the rest; (..., k) maps to (..., n).

param H:: Parity-check matrix of shape (m, n) (entries 0/1); must match the decoder.
type H:: np.ndarray
param name:: Name of the processor. Default "ldpc_encoder".
type name:: str, keyword-only

References

T. Richardson, R. Urbanke, Modern Coding Theory, Cambridge University Press, 2008, Section 3.2 (encoding via echelon form).

Examples

>>> H = np.array([[1, 1, 0, 1, 1, 0, 0],
...               [1, 0, 1, 1, 0, 1, 0],
...               [0, 1, 1, 1, 0, 0, 1]])   # (7, 4) Hamming code
>>> encoder = LDPCEncoder(H)
>>> c = encoder(np.array([1, 0, 1, 1]))
>>> print(c)
[0 0 1 0 0 1 1]
>>> print(H @ c % 2)
[0 0 0]

property rate: float#: Code rate \(k / n\) (true rank, not design rate).

class LDPCDecoder(H: ndarray, *, n_iter: int = 25, alpha: float = 1.0, output: Literal['info', 'codeword'] = 'info', name: str = 'ldpc_decoder')[source]#

Min-sum belief-propagation decoder for an LDPC code.

Signal Model#

Messages flow on the edges of the Tanner graph of \(H\). With channel log-likelihood ratios \(L_j = \log P(c_j{=}0)/P(c_j{=}1)\) (the SymbolDemapper(soft=True) convention), the min-sum check update for the message from check \(i\) to variable \(j\) is

\[m_{i \to j} = \alpha \prod_{j' \in N(i) \setminus j} \mathrm{sign}(m_{j' \to i}) \min_{j' \in N(i) \setminus j} |m_{j' \to i}|\]

and the variable update is \(m_{j \to i} = L_j + \sum_{i' \in N(j) \setminus i} m_{i' \to j}\). Iterations stop early when the hard decision satisfies every parity check. All messages live in (batch, n_edges) arrays; the check and variable updates are segmented reductions over edges sorted by check and by variable (decision D5) – the only Python loop is over iterations.

Axes: axis -1 – channel LLRs on the last axis, broadcast over the rest; (..., n) maps to (..., k) (output="info") or (..., n) (output="codeword").

param H:: Parity-check matrix of shape (m, n); must match the encoder. Every row and column must contain at least one 1.
type H:: np.ndarray
param n_iter:: Maximum number of message-passing iterations. Default 25.
type n_iter:: int, keyword-only
param alpha:: Normalization factor of the check update (normalized min-sum). Default 1.0 (plain min-sum); 0.75 is a common choice that recovers most of the sum-product gap.
type alpha:: float, keyword-only
param output:: Return the information bits at the systematic positions (default) or the full hard-decision codeword.
type output:: {“info”, “codeword”}, keyword-only
param name:: Name of the processor. Default "ldpc_decoder".
type name:: str, keyword-only
raises ShapeError:: If the last axis of the input does not match the code length.

References

R. G. Gallager, “Low-density parity-check codes,” IRE Trans. Inf. Theory 8(1), 1962; J. Chen, M. Fossorier, “Near optimum universal belief propagation based decoding of low-density parity check codes,” IEEE Trans. Commun. 50(3), 2002 (normalized min-sum).

Examples

>>> H = np.array([[1, 1, 0, 1, 1, 0, 0],
...               [1, 0, 1, 1, 0, 1, 0],
...               [0, 1, 1, 1, 0, 0, 1]])   # (7, 4) Hamming code
>>> c = LDPCEncoder(H)(np.array([1, 0, 1, 1]))
>>> llr = 4.0 * (1.0 - 2.0 * c)   # log P(0)/P(1), positive = bit 0
>>> llr[1] = -1.0                 # one weak channel error
>>> decoder = LDPCDecoder(H)
>>> print(decoder(llr))
[1 0 1 1]

make_gallager_parity_check(n: int, d_v: int = 3, d_c: int = 6, seed: int | None = None) → ndarray[source]#

Regular parity-check matrix from the Gallager ensemble.

Signal Model#

The \((d_v, d_c)\)-regular matrix stacks \(d_v\) bands of \(n / d_c\) rows. The first band places its ones in consecutive groups of \(d_c\) columns; every other band is a random column permutation of it, so each column has weight \(d_v\) and each row weight \(d_c\). The design rate is \(R = 1 - d_v / d_c\) (the true rate is slightly higher when the stacked rows are linearly dependent, which the encoder detects).

param n:: Code length (number of columns). Must be a multiple of d_c.
type n:: int
param d_v:: Column (variable node) weight. Default 3.
type d_v:: int, optional
param d_c:: Row (check node) weight. Default 6.
type d_c:: int, optional
param seed:: Seed for the band permutations.
type seed:: int, optional
returns:: np.ndarray – Parity-check matrix of shape (n d_v / d_c, n), dtype uint8.

References

R. G. Gallager, “Low-density parity-check codes,” IRE Trans. Inf. Theory 8(1), 1962.

Examples

>>> H = make_gallager_parity_check(12, d_v=3, d_c=6, seed=0)
>>> print(H.shape, int(H.sum(axis=0)[0]), int(H.sum(axis=1)[0]))
(6, 12) 3 6