A Sparse graph code is a code which is represented by a sparse graph.

Any linear code can be represented as a graph, where there are two sets of nodes - a set representing the transmitted bits and another set representing the constraints that the transmitted bits have to satisfy. The state of the art classical error-correcting codes are based on sparse graphs, achieving close to the Shannon limit. The archetypal sparse-graph codes are Gallager's low-density parity-check codes.

edit


Stub icon

This article about matrices is a stub. You can help Wikipedia by adding missing information.

📚 Artikel Terkait di Wikipedia

Low-density parity-check code

using a flexible design method that is based on sparse Tanner graphs (specialized bipartite graphs). LDPC code ensembles have also been analyzed using methods

Expander graph

In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander

Sparse matrix

Pareto principle Ragged matrix Single-entry matrix Skyline matrix Sparse graph code Sparse file Harwell-Boeing file format Matrix Market exchange formats

Error correction code

Gallager code, as the archetype for sparse graph codes LT code, which is a near-optimal rateless erasure correcting code (Fountain code) m of n codes Nordstrom-Robinson

List of graph theory topics

Petersen graph Planar graph Dual polyhedron Outerplanar graph Random graph Regular graph Scale-free network Snark (graph theory) Sparse graph Sparse graph code

Adjacency matrix

In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether

Dijkstra's algorithm

) {\textstyle \Theta (|E|+|V|^{2})=\Theta (|V|^{2})} . For sparse graphs, that is, graphs with far fewer than | V | 2 {\displaystyle |V|^{2}} edges, Dijkstra's

Planar graph

this sense, planar graphs are sparse graphs, in that they have only O(v) edges, asymptotically smaller than the maximum O(v2). The graph K3,3, for example