Generalized LDPC and Tanner Codes

A Tanner code generalizes an LDPC code by replacing each single parity check with a short local code imposed on the edges incident to that check vertex. Taking the local code to be a single parity check recovers an ordinary LDPC code, while stronger local codes buy better distance at the same degree.

The spectral functions here are what make these codes tractable to reason about: the Sipser-Spielman bound turns the spectral gap of the underlying graph into a distance guarantee, so an expander graph yields a code with provably good distance.

CodingTheory.TannerCode — Method

TannerCode(
    G::Graphs.SimpleGraphs.SimpleGraph{Int64},
    C::AbstractLinearCode
) -> TannerCode

Return the Tanner code obtained by applying the local code C to the edges of G.

source

CodingTheory.TannerCode — Method

TannerCode(
    G::Graphs.SimpleGraphs.SimpleGraph{Int64},
    left::Vector{Int64},
    right::Vector{Int64},
    C::AbstractLinearCode
) -> TannerCode

Return the Tanner code obtained by applying the local code C to the vertices right in the bipartition of G and treating the vertices of left as bits.

source

CodingTheory.TannerCode — Method

TannerCode(
    G::Graphs.SimpleGraphs.SimpleGraph{Int64},
    left::Vector{Int64},
    right1::Vector{Int64},
    right2::Vector{Int64},
    C1::AbstractLinearCode,
    C2::AbstractLinearCode
) -> TannerCode

Return the Tanner code obtained by applying the local codes C1 and C2 to the vertices right1 and right2 in the bipartition of G and treating the vertices of left as bits.

source

CodingTheory.TannerCode — Method

TannerCode(
    EVI::SparseArrays.SparseMatrixCSC{Int64, Int64},
    C::AbstractLinearCode
) -> TannerCode

Return the Tanner code obtained by applying the local code C to the edges of the graph with edge-vertex incidence matrix EVI.

source

CodingTheory.Sipser_Spielman_bound — Method

Sipser_Spielman_bound(C::TannerCode) -> Int64

Return the Sipser-Spielman spectral lower bound on the minimum distance of the Tanner code.

source

CodingTheory.Tanner_graph — Method

Tanner_graph(C::AbstractLinearCode) -> Any

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.

source

CodingTheory.Tanner_graph — Method

Tanner_graph(
    H::Union{Nemo.FqMatrix, Nemo.fpMatrix, Hecke.SMat, SparseArrays.SparseMatrixCSC, Matrix{Int64}}
) -> Tuple{Any, Vector{Int64}, Vector{Int64}}

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.

source

CodingTheory.Tanner_graph_plot — Function

Tanner_graph_plot(H::Union{CTMatrixTypes, Matrix{Int}})

Return the Tanner graph of the matrix H as a Makie Figure object.

Note

Run using Makie to activate this extension.

source

CodingTheory.graph_eigenvalues — Method

graph_eigenvalues(C::TannerCode) -> Any

Return the eigenvalues of the base graph used to construct the Tanner code. Computes lazily and caches the result.

source

CodingTheory.spectral_gap — Method

spectral_gap(C::TannerCode) -> Any

Return the second-largest eigenvalue (in absolute value) of the base graph, often denoted λ.

source