Expander code: Difference between revisions

Revision as of 22:06, 10 December 2021

Revision as of 20:50, 6 February 2022

Line 15:

In [[coding theory]], '''expander codes''' form a class of [[Error detection and correction|error-correcting codes]] that are constructed from [[Bipartite graph|bipartite]] [[expander graph]]s.

Along with [[Justesen code]]s, expander codes are of particular interest since they have a constant positive [[Block_codeBlock code#The_rate_RThe rate R|rate]], a constant positive relative [[Block_codeBlock code#The_distance_dThe distance d|distance]], and a constant [[Block_codeBlock code#The_alphabet_The alphabet .CE.A3|alphabet size]].

In fact, the alphabet contains only two elements, so expander codes belong to the class of [[binary code]]s.

Furthermore, expander codes can be both encoded and decoded in time proportional to the block length of the code.

==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_codeBlock code#The_distance_dThe 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_codeBlock code#The_rate_RThe rate R|rate]] <math>\left(1-\tfrac{m}{n}\right)\,</math>, and decodability (algorithms of running time <math>O(n)\,</math> exist).

==Definition==

Let <math>B</math> be a <math>(c,d)</math>-regular graph between a set of <math>n</math> nodes <math>\{v_1,\cdots,v_n\}</math>, called <i>''variables</i>'', and a set of <math>cn/d</math> nodes <math>\{C_1,\cdots,C_{cn/d}\}</math>, called <i>''constraints</i>''.

Let <math>b(i,j)</math> be a function designed so that, for each constraint <math>C_i</math>, the variables neighboring <math>C_i</math> are <math>v_{b(i,1)},\cdots,v_{b(i,d)}</math>.

Let <math>\mathcal{S}</math> be an error-correcting code of block length <math>d</math>. The <b><i>'''''expander code</i></b>''''' <math>\mathcal{C}(B,\mathcal{S})</math> is the code of block length <math>n</math> whose codewords are the words <math>(x_1,\cdots,x_n)</math> such that, for <math>1\leq i\leq cn/d</math>, <math>(x_{b(i,1)},\cdots,x_{b(i,d)})</math> is a codeword of <math>\mathcal{S}</math>.<ref name="definition">{{cite journal|doi=10.1109/18.556667}}</ref>

It has been shown that nontrivial lossless expander graphs exist. Moreover, we can explicitly construct them.<ref name="lossless">{{cite book |first1=M. |last1=Capalbo |first2=O. |last2=Reingold |first3=S. |last3=Vadhan |first4=A. |last4=Wigderson |chapter=Randomness conductors and constant-degree lossless expanders |chapter-url=http://dl.acm.org/citation.cfm?id=510003 |title=STOC '02 Proceedings of the thirty-fourth annual ACM symposium on Theory of computing |publisher=ACM |year=2002 |isbn=978-1-58113-495-7 |pages=659–668 |doi=10.1145/509907.510003}}</ref>