LDPC Codes

An LDPC code is defined by a specific choice of parity-check matrix for a code. Different parity-check matrices for the same linear code produce different LDPC codes, so the LDPCCode constructor does not accept a code but rather a matrix.

julia> H = matrix(GF(2), 6, 9, [
          1 0 1 0 1 0 0 0 1;
          0 1 1 0 1 1 1 0 0;
          0 0 0 1 0 1 0 0 0;
          0 0 0 1 1 0 1 1 0;
          0 1 1 1 0 1 0 0 1;
          1 1 0 0 0 0 1 1 1]);

julia> L = LDPCCode(H)
[9, 3, 3]_2 irregular 5-limited LDPC code with density 0.46296296296296297.

Variable degree polynomial:
        21//25*x^2 + 4//25*x
Check degree polynomial:
        3//5*x^4 + 8//25*x^3 + 2//25*x
Parity-check matrix: 6 × 9
        1 0 1 0 1 0 0 0 1
        0 1 1 0 1 1 1 0 0
        0 0 0 1 0 1 0 0 0
        0 0 0 1 1 0 1 1 0
        0 1 1 1 0 1 0 0 1
        1 1 0 0 0 0 1 1 1

The degree polynomials $\lambda(x)$ and $\rho(x)$, the degrees of the individual variable and check nodes, and the maximum degrees are all computed at construction. A bar graph of the degree distributions is available through degree_distributions_plot, which requires a Makie backend to be loaded.

The Tanner graph of the defining parity-check matrix can be produced as a SimpleDiGraph or drawn into a Figure, and computation_graph draws the graph unrolled to a given level, which is occasionally useful for small examples. Cycle structure, girth, and ACE data have their own page; see Cycles and ACE.

CodingTheory.LDPCCode — Method
LDPCCode(C::AbstractLinearCode) -> LDPCCode

Return the LDPC code given by the parity-check matrix of C.

source
CodingTheory.LDPCCode — Method
LDPCCode(
    H::Union{Nemo.FqMatrix, Nemo.fpMatrix, Hecke.SMat, SparseArrays.SparseMatrixCSC}
) -> LDPCCode

Return the LDPC code defined by the parity-check matrix H.

source
CodingTheory.design_rate — Method
design_rate(C::LDPCCode) -> Float64

Return the design rate of C, given by its design dimension divided by its block length.

source
CodingTheory.parity_check_matrix — Method
parity_check_matrix(C::AbstractLDPCCode) -> Any

Retrieve the parity-check matrix H. Checks the cache first, then falls back to the struct field, throwing an error if neither exists.

source
CodingTheory.regular_LDPC_code — Method
regular_LDPC_code(
    q::Int64,
    n::Int64,
    l::Int64,
    r::Int64;
    seed
)

Return a random regular LDPC code over GF(q) of length n with column degree l and row degree r.

source
Hecke.density — Method
density(C::LDPCCode) -> Any

Return the density of the parity-check matrix of C.

source
Hecke.dimension — Method
dimension(C::LDPCCode) -> Union{Missing, Int64}

Return the exact rank-adjusted dimension k of the LDPC code C.

Notes

  • If not previously computed, this runs the O(n^3) rank computation, caches the result in C.k, and returns it.
source
Hecke.is_regular — Method
is_regular(C::LDPCCode) -> Bool

Return true if the C is a regular LDPC code.

Notes

  • An LDPC is regular if all the column degrees and equal and all the row degrees are equal.
source

The following is not exported but may be useful.

Hecke.density — Function
density(C::LDPCCode) -> Any

Return the density of the parity-check matrix of C.

source

Construction algorithms

Beyond random regular codes, the library provides the progressive-edge-growth family, which greedily adds edges so as to maximize the local girth, and several named algebraic and pseudorandom families: Gallager's original construction, MacKay-Neal codes, spatially coupled codes, and codes from Euclidean and projective geometries.

CodingTheory.EuclideanGeometryCode — Method
EuclideanGeometryCode(m::Int64, p::Int64)

Return the Euclidean-geometry LDPC code from point-line incidence in $\operatorname{EG}(m, p)$.

Here m is the dimension, and p is the prime field order expected by the construction. Columns of the parity-check matrix represent points and rows represent affine lines.

source
CodingTheory.GallagerCode — Method
GallagerCode(n::Int64, wc::Int64, wr::Int64)

Return a random regular LDPC code from Gallager's block-permutation construction.

For the regular construction, wr must divide n. The parity-check matrix then has n columns, column weight wc, and row weight wr. Its first row block has disjoint consecutive supports, and each remaining block is an independent random column permutation of that block.

source
CodingTheory.Mackay_Neal — Method
Mackay_Neal(
    n::Int64,
    m::Int64,
    deg_v::Vector{Int64};
    max_retries
)

Return a random LDPC code generated by the MacKay-Neal edge-placement algorithm.

The code has n variable nodes, m check nodes, and variable-node degrees given by deg_v. Edge placement balances check degrees while excluding parallel edges and 4-cycles. At most max_retries attempts are made for each column.

source
CodingTheory.ProjectiveGeometryCode — Method
ProjectiveGeometryCode(m::Int64, p::Int64)

Return the projective-geometry LDPC code from point-line incidence in $\operatorname{PG}(m, p)$.

Here m is the projective dimension, and p is the prime field order expected by the construction. Columns of the parity-check matrix represent projective points and rows represent projective lines.

source
CodingTheory.SC_LDPCCode — Method
SC_LDPCCode(B_components::Vector{Matrix{Int64}}, L::Int64)

Return the terminated spatially coupled LDPC code formed from B_components.

The equally sized component matrices are placed along a diagonal coupling window for L variable-block positions. If there are $w + 1$ components of size $m_b \times n_b$, the parity-check matrix has size $(L + w)m_b \times Ln_b$.

source
CodingTheory.progressive_edge_growth — Method
progressive_edge_growth(
    n::Int64,
    m::Int64,
    deg_v::Vector{Int64}
) -> SparseArrays.SparseMatrixCSC{Int64, Int64}

Return a parity-check matrix built with the progressive-edge-growth (PEG) algorithm and approximate-cycle-EMD (ACE) maximization.

Arguments

  • n::Int: Number of variable nodes (columns).
  • m::Int: Number of check nodes (rows).
  • deg_v::Vector{Int}: Target degree for each variable node.
source
CodingTheory.progressive_edge_growth_QC — Method
progressive_edge_growth_QC(
    B::Matrix{Int64},
    Z::Int64
) -> Matrix{Int64}

Return a quasi-cyclic shift matrix built with the QC-PEG algorithm to increase the lifted graph's girth while preserving a block-circulant structure.

Arguments

  • B::Matrix{Int}: The base matrix (protograph/macro-graph) where 1 indicates an edge exists, and 0 indicates no edge.
  • Z::Int: The lifting factor (circulant size).

Returns

  • A matrix of the same size as B containing the selected circulant shifts p ∈ [0, Z-1]. Null edges are represented as -1.
source
CodingTheory.progressive_edge_growth_protograph — Method
progressive_edge_growth_protograph(
    B::Matrix{Int64},
    Q::Int64
) -> SparseArrays.SparseMatrixCSC{Int64, Int64}

Return a parity-check matrix lifted from a protograph base matrix with the PEG algorithm, which selects permutation edges to increase girth.

Arguments

  • B::Matrix{Int}: The protograph base matrix. B[i, j] represents the number of parallel edges.
  • Q::Int: The lifting factor (number of replicas).
source