{
  "id": "enwiki-001376125949",
  "slug": "expander-code",
  "title": "Expander code",
  "qid": "",
  "lead": "In coding theory, expander codes form a class of error-correcting codes that are constructed from bipartite expander graphs. Along with Justesen codes, expander codes are of particular interest since they have a constant positive rate, positive relative distance, and alphabet size. In fact, the alphabet contains only two elements, so expander codes belong to the class of binary codes. Furthermore, expander codes can be both encoded and decoded in time proportional to the block length of the code.",
  "body": "In coding theory, expander codes form a class of error-correcting codes that are constructed from bipartite expander graphs. Along with Justesen codes, expander codes are of particular interest since they have a constant positive rate, positive relative distance, and alphabet size. In fact, the alphabet contains only two elements, so expander codes belong to the class of binary codes. 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 [n,n-m]_2\\, linear block code whose parity check matrix is the adjacency matrix of a bipartite expander graph. These codes have good relative distance 2(1-\\varepsilon)\\gamma\\, , where \\varepsilon\\, and \\gamma\\, are properties of the expander graph as defined later, rate \\left(1-\\tfrac{m}{n}\\right)\\, , and decodability (algorithms of running time O(n)\\, exist). ==Definition== Let B be a (c,d) -biregular graph between a set of n nodes \\{v_1,\\cdots,v_n\\} , called variables, and a set of cn/d nodes \\{C_1,\\cdots,C_{cn/d}\\} , called constraints. Let b(i,j) be a function designed so that, for each constraint C_i , the variables neighbouring C_i are v_{b(i,1)},\\cdots,v_{b(i,d)} . Let \\mathcal{S} be an error-correcting code of block length d . The expander code \\mathcal{C}(B,\\mathcal{S}) is the code of block length n whose code words are the words (x_1,\\cdots,x_n) such that, for 1\\leq i\\leq cn/d , (x_{b(i,1)},\\cdots,x_{b(i,d)}) is a code word of \\mathcal{S} . It has been shown that nontrivial lossless expander graphs exist. Moreover, we can explicitly construct them. ==Rate== The rate of C\\, is its dimension divided by its block length. In this case, the parity check matrix has size m \\times n\\, , and hence C\\, has rate at least (n-m)/n = 1 - m/n\\, . ==Distance== Suppose \\varepsilon . Then the distance of a (n, m, d, \\gamma, 1-\\varepsilon)\\, expander code C\\, is at least 2(1-\\varepsilon)\\gamma n\\, . ===Proof=== Note that we can consider every code word c\\, in C\\, as a subset of vertices S \\subset L\\, , by saying that vertex v_i \\in S\\, if and only if the i\\, th index of the code word is a 1. Then c\\, is a code word if every vertex v \\in R\\, is adjacent to an even number of vertices in S\\, . (In order to be a code word, cP = 0\\, , where P\\, is the parity check matrix. Then, each vertex in R\\, corresponds to each column of P\\, . Matrix multiplication over \\text{GF}(2) = \\{0,1\\}\\, then gives the desired result.) So, if a vertex v \\in R\\, is adjacent to a single vertex in S\\, , we know immediately that c\\, is not a code word. Let N(S)\\, denote the neighbours in R\\, of S\\, , and U(S)\\, denote those neighbours of S\\, which are unique, i.e., adjacent to a single vertex of S\\, . Trivially, |N(S)| \\geq |U(S)|\\, , since v \\in U(S)\\, implies v \\in N(S)\\, . |N(S)| \\leq d|S|\\, follows since the degree of every vertex in S\\, is d\\, . By the expansion property of the graph, there must be a set of d(1-\\varepsilon)|S|\\, edges which go to distinct vertices. The remaining d\\varepsilon|S|\\, edges make at most d\\varepsilon|S|\\, neighbours not unique, so U(S) \\geq d(1-\\varepsilon)|S| - d\\varepsilon|S| = d(1-2\\varepsilon)|S|\\, . Lemma 1 proves the case |T| \\leq \\gamma n\\, , so suppose 2(1-\\varepsilon)\\gamma n > |T| > \\gamma n\\, . Let S \\subset T\\, such that |S| = \\gamma n\\, . By Lemma 1, we know that |U(S)| \\geq d(1-2\\varepsilon)|S|\\, . Then a vertex v \\in U(S)\\, is in U(T)\\, if v \\notin N(T \\setminus S)\\, , and we know that |T \\setminus S| \\leq 2(1-\\varepsilon)\\gamma n - \\gamma n = (1-2\\varepsilon)\\gamma n\\, , so by the first part of Lemma 1, we know |N(T \\setminus S)| \\leq d(1-2\\varepsilon)\\gamma n\\, . Since \\varepsilon , |U(T)| \\geq |U(S) \\setminus N(T \\setminus S)| \\geq |U(S)| - |N(T \\setminus S)| > 0\\, , and hence U(T)\\, is not empty. ==Encoding== The encoding time for an expander code is upper bounded by that of a general linear code - O(n^2)\\, by matrix multiplication. A result due to Spielman shows that encoding is possible in O(n)\\, time. ==Decoding== Decoding of expander codes is possible in O(n)\\, time when \\varepsilon using the following algorithm. Let v_i\\, be the vertex of L\\, that corresponds to the i\\, index in the code words of C\\, . Let y \\in \\{0,1\\}^n\\, be a received word, and V(y) = \\{v_i \\mid \\text{the } i^{\\text{th}} \\text{ position of } y \\text{ is a } 1\\}\\, . Let e(i)\\, be |\\{v \\in R \\mid v_i \\in N(v) \\text{ and } N(v) \\cap V(y) \\text{ is even}\\}|\\, , and o(i)\\, be |\\{v \\in R \\mid v_i \\in N(v) \\text{ and } N(v) \\cap V(y) \\text{ is odd}\\}|\\, . Then consider the greedy algorithm: ---- Input: received word y\\, . initialize y' to y while there is a v in R adjacent to an odd number of vertices in V(y') if there is an i such that o(i) > e(i) flip entry i in y' else fail Output: fail, or modified code word y'\\, . ---- We must show that the algorithm terminates with the correct code word when the received code word is within half the code's distance of the original code word. Let the set of corrupt variables be S\\, , s = |S|\\, , and the set of unsatisfied (adjacent to an odd number of vertices) vertices in R\\, be c\\, . The following lemma will prove useful. If we start with s , then we never reach s = \\gamma n\\, at any point in the algorithm. Pre-processing 2: We take O(dn) = O(dmr)\\, time to compute a list of vertices v_i\\, in L\\, which have o(i) > e(i)\\, . Each Iteration: We simply remove the first list element. To update the list of odd / even vertices in R\\, , we need only update O(d)\\, entries, inserting / removing as necessary. We then update O(dr)\\, entries in the list of vertices in L\\, with more odd than even neighbours, inserting / removing as necessary. Thus each iteration takes O(dr)\\, time. As argued above, the total number of iterations is at most m\\, . This gives a total runtime of O(mdr) = O(n)\\, time, where d\\, and r\\, are constants. ==See also== Expander graph Low-density parity-check code Linear time encoding and decoding of error-correcting codes ABNNR and AEL codes ==Notes== This article is based on Dr. Venkatesan Guruswami's course notes. ==References==",
  "categories": [
    "11060667",
    "20476821",
    "20548265",
    "22921020",
    "23603337",
    "24196488",
    "26220375",
    "26606269"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1376125949",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1790048361.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001376125949",
    "type": "webpage",
    "title": "Expander code",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/expander-code",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          18
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          18
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001376125949",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1376125949",
    "note": "Immutable snapshot enwiki-001376125949"
  }
}