Sparse graph code

Sparse graph code

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.

External links

* [http://www.inference.phy.cam.ac.uk/mackay/itila/ The on-line textbook: Information Theory, Inference, and Learning Algorithms] , by David J.C. MacKay, discusses sparse-graph codes in Chapters 47-50.
* [http://www.inference.phy.cam.ac.uk/mackay/codes/data.html Encyclopedia of Sparse Graph Codes]


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • Sparse matrix — A sparse matrix obtained when solving a finite element problem in two dimensions. The non zero elements are shown in black. In the subfield of numerical analysis, a sparse matrix is a matrix populated primarily with zeros (Stoer Bulirsch 2002,… …   Wikipedia

  • Low-density parity-check code — In information theory, a low density parity check code (LDPC code) is an error correcting code, a method of transmitting a message over a noisy transmission channel. [David J.C. MacKay (2003) Information theory, inference and learning algorithms …   Wikipedia

  • List of graph theory topics — This is a list of graph theory topics, by Wikipedia page. See glossary of graph theory for basic terminology Contents 1 Examples and types of graphs 2 Graph coloring 3 Paths and cycles 4 …   Wikipedia

  • Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… …   Wikipedia

  • Expander graph — In combinatorics, an expander graph is a sparse graph which has high connectivity properties, quantified using vertex or edge expansion as described below. Expander constructions have spawned research in pure and applied mathematics, with several …   Wikipedia

  • Planar graph — Example graphs Planar Nonplanar Butterfly graph K5 The complete graph K4 …   Wikipedia

  • Fountain code — In Coding Theory and Communication Theory, fountain codes (also known as rateless erasure codes) are a class of erasure codes with the property that a potentially limitless sequence of encoding symbols can be generated from a given set of source… …   Wikipedia

  • Tornado code — In computer science, tornado codes are a class of erasure codes that support error correction and have fast encoding and decoding algorithms. Software based implementations of tornado codes are about 100 times faster on small lengths and about 10 …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

  • List of algebraic coding theory topics — This is a list of algebraic coding theory topics. ARQ[disambiguation needed  ] Adler 32 BCH code BCJR algorithm Berger code Berlekamp Massey algo …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”