LDPC Codes
Constructors
An LDPC code is defined by a specific choice of a parity-check matrix for a code. Different parity-check matrices for the same linear code produce different LDPC codes. As such, the LDPCCode constructor does not accept a code, but rather a matrix.
CodingTheory.LDPCCode — TypeLDPCCode(H::fq_nmod_mat)Return the LDPC code defined by the parity-check matrix H.
LDPCCode(C::AbstractLinearCode)Return the LDPC code given by the parity-check matrix of C.
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 1Random regular LDPC codes maybe be constructed via
CodingTheory.regular_LDPC_code — Functionregular_LDPC_code(q::Int, n::Int, l::Int, r::Int [; seed=nothing])Return a random regular LDPC code over GF(q) of length n with column degree l and row degree r.
If a seed is given, i.e. regulardLDPCCode(4, 1200, 3, 6, seed=123), the results are reproducible.
and irregular LDPC codes via
Missing docstring for irregular_LDPC_code. Check Documenter's build log for details.
Attributes
The polynomials $\lambda(x)$ and $\rho(x)$ as well as the degrees of each variable and check nodes are computed upon construction.
CodingTheory.variable_degree_polynomial — Functionvariable_degree_polynomial(C::AbstractLDPCCode)Return the variable degree polynomial of C.
CodingTheory.check_degree_polynomial — Functioncheck_degree_polynomial(C::AbstractLDPCCode)Return the check degree polynomial of C.
CodingTheory.variable_degree_distribution — Functionvariable_degree_distribution(C::AbstractLDPCCode)Return the variable node degree distribution of C.
CodingTheory.check_degree_distribution — Functioncheck_degree_distribution(C::AbstractLDPCCode)Return the check node degree distribution of C.
CodingTheory.degree_distributions — Functiondegree_distributions(C::AbstractLDPCCode)Return the variable and check node degree distributions of C.
A bar graph of the degree distributions is available
CodingTheory.degree_distributions_plot — Functiondegree_distributions_plot(C::AbstractLDPCCode)Return a bar plot of the column and row degree distributions of C.
For convenience, the maximum degrees are also stored.
CodingTheory.column_bound — Functioncolumn_bound(C::AbstractLDPCCode)Return the column bound c of the (c, r)-LDPC code C.
CodingTheory.row_bound — Functionrow_bound(C::AbstractLDPCCode)Return the row bound r of the (c, r)-LDPC code C.
CodingTheory.column_row_bounds — Functioncolumn_row_bounds(C::AbstractLDPCCode)Return the column and row bounds c, r of the (c, r)-LDPC code C.
CodingTheory.limited — Functionlimited(C::AbstractLDPCCode)Return the maximum of the row and column bounds for C.
Hecke.density — Functiondensity(C::AbstractLDPCCode)Return the density of the parity-check matrix of C.
Hecke.is_regular — Functionis_regular(G::SimpleGraph{Int})Return true if G is regular.
is_regular(C::AbstractLDPCCode)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.
The Tanner graph corresponding to the parity-matrix defining the LDPC code can be generated as a SimpleDiGraph and visually in a Figure object.
CodingTheory.Tanner_graph — FunctionTanner_graph(H::Union{fq_nmod_mat, Matrix{Int}})Return the SimpleGraph object repesenting the Tanner graph of the parity-check matrix H along with the indices of the left and right vertices representing the bits and parity checks, respectively.
Tanner_graph(C::AbstractLinearCode)Return the SimpleGraph object repesenting the Tanner graph of C along with the indices of the left and right vertices representing the bits and parity checks, respectively.
Tanner_graph(C::AbstractLDPCCode)Return the Tanner graph of C as a Figure object.
CodingTheory.Tanner_graph_plot — FunctionTanner_graph_plot(H::Union{fq_nmod_mat, Matrix{Int}})Return the Tanner graph of the matrix H as a Figure object.
Methods
Occassionally useful for small examples, the following function produces a Figure of the Tanner graph unrolled to a given level.
CodingTheory.computation_graph — Functioncomputation_graph(C::LDPCCode, lvl::Int, v::Int, v_type::Symbol=:v)Return a figure representing the expansion of the Tanner graph of C to level lvl for node v. If v_type is :v, v is interpreted as a variable node; otherwise, v_type is :c and v is interpreted as a check node.
Oscar.girth — Functiongirth(C::LDPCCode)Return the girth of the Tanner graph of C.
An error is thrown if the maximum number of iterations is reached and $-1$ is returned to represent infinite girth.
To count or explicitly enumerate the short cycles of the Tanner graph, use
CodingTheory.count_short_cycles — Functioncount_short_cycles(C::LDPCCode)Return a bar graph and a dictionary of (length, count) pairs for unique short cycles in the Tanner graph of C. An empty graph and dictionary are returned when there are no cycles.
Note
- Short cycles are defined to be those with lengths between $g$ and $2g - 2$, where $g$ is the girth.
CodingTheory.shortest_cycles — Functionshortest_cycles(C::LDPCCode, v::Int)
shortest_cycles(C::LDPCCode, vs::Vector{Int})
shortest_cycles(C::LDPCCode)Return all the cycles of shortest length in the Tanner graph of C for the vertex v or vertices vs. If no vertices are given, all vertices are computed by default.
Note
- The length of the shortest cycle is not necessarily the same for each vertex.
- To reduce computational complexity, the same cycle may appear under each vertex in the cycle.
Various information about the ACE values of cycles in the Tanner graph may be computed with the following functions.
CodingTheory.ACE_spectrum — FunctionACE_spectrum(C::LDPCCode)Return an interactive figure and data for the ACE spectrum of the Tanner graph of C.
CodingTheory.shortest_cycle_ACE — Functionshortest_cycle_ACE(C::LDPCCode, v::Int)
shortest_cycle_ACE(C::LDPCCode, vs::Vector{Int})
shortest_cycle_ACE(C::LDPCCode)Return a cycle of minimum length and minimum ACE in the Tanner graph of C for the vertex v or vertices vs, in the order (ACEs, cycles). If no vertices are given, all vertices are computed by default. The cycle v1 -- c1 -- ... -- cn -- vn is returned in the format [(v1, c1), (c1, v2), ..., (cn, vn)].
CodingTheory.ACE_distribution — FunctionACE_distribution(C::LDPCCode, v::Int)
ACE_distribution(C::LDPCCode, vs::Vector{Int})
ACE_distribution(C::LDPCCode)Return the ACEs and cycle lengths for vertex v or vertices vs of the Tanner graph of C. If no vertices are given, all vertices are computed by default.
CodingTheory.average_ACE_distribution — Functionaverage_ACE_distribution(C::LDPCCode, v::Int)
average_ACE_distribution(C::LDPCCode, vs::Vector{Int})
average_ACE_distribution(C::LDPCCode)Return the average ACE of the vertex v or vertices vs of the Tanner graph of C. If no vertices are given, all vertices are computed (individually) by default.
CodingTheory.median_ACE_distribution — Functionmedian_ACE_distribution(C::LDPCCode, v::Int)
median_ACE_distribution(C::LDPCCode, vs::Vector{Int})
median_ACE_distribution(C::LDPCCode)Return the median ACE of the vertex v or vertices vs of the Tanner graph of C. If no vertices are given, all vertices are computed (individually) by default.
CodingTheory.mode_ACE_distribution — Functionmode_ACE_distribution(C::LDPCCode, v::Int)
mode_ACE_distribution(C::LDPCCode, vs::Vector{Int})
mode_ACE_distribution(C::LDPCCode)Return the mode ACE of the vertex v or vertices vs of the Tanner graph of C. If no vertices are given, all vertices are computed (individually) by default.
Note
- In case of ties, the smallest tied value is returned.