Expander code: Difference between revisions

Revision as of 13:55, 8 May 2012

Revision as of 23:03, 18 July 2012

Line 18:

==Expander codes==

In [[coding theory]], an expander code is a <math>[n,n-m]_2\,</math> [[linear block code]] whose parity check matrix is the adjacency matrix of a bipartite [[expander graph]]. These codes have good relative [[Block_code#The_distance_d|distance]] (<math>2(1-\varepsilon)\gamma\,</math>, where <math>\varepsilon\,</math> and <math>\gamma\,</math> are properties of the expander graph as defined later), [[Block_code#The_rate_R|rate]] (<math>1-\tfrac{m}{n}\,</math>), and decodability (algorithms of running time <math>O(n)\,</math> exist).

==Definition==