{
  "id": "enwiki-001377677307",
  "slug": "block-code",
  "title": "Block code",
  "qid": "",
  "lead": "In coding theory, block codes are a large and important family of error-correcting codes that encode data in blocks. There is a vast number of examples for block codes, many of which have a wide range of practical applications. The abstract definition of block codes is conceptually useful because it allows coding theorists, mathematicians, and computer scientists to study the limitations of all block codes in a unified way. Such limitations often take the form of bounds that relate different parameters of the block code to each other, such as its rate and its ability to detect and correct errors. Examples of block codes are Reed–Solomon codes, Hamming codes, Hadamard codes, Expander codes, Golay codes, Reed–Muller codes and Polar codes. These examples also belong to the class of linear codes, and hence they are called linear block codes. More particularly, these codes are known as algebraic block codes, or cyclic block codes, because they can be generated using Boolean polynomials. Algebraic block codes are typically hard-decoded using algebraic decoders. The term block code may also refer to any error-correcting code that acts on a block of k bits of input data to produce n bits of output data (n,k) . Consequently, the block coder is a memoryless device.…",
  "body": "In coding theory, block codes are a large and important family of error-correcting codes that encode data in blocks. There is a vast number of examples for block codes, many of which have a wide range of practical applications. The abstract definition of block codes is conceptually useful because it allows coding theorists, mathematicians, and computer scientists to study the limitations of all block codes in a unified way. Such limitations often take the form of bounds that relate different parameters of the block code to each other, such as its rate and its ability to detect and correct errors. Examples of block codes are Reed–Solomon codes, Hamming codes, Hadamard codes, Expander codes, Golay codes, Reed–Muller codes and Polar codes. These examples also belong to the class of linear codes, and hence they are called linear block codes. More particularly, these codes are known as algebraic block codes, or cyclic block codes, because they can be generated using Boolean polynomials. Algebraic block codes are typically hard-decoded using algebraic decoders. The term block code may also refer to any error-correcting code that acts on a block of k bits of input data to produce n bits of output data (n,k) . Consequently, the block coder is a memoryless device. Under this definition codes such as turbo codes, terminated convolutional codes and other iteratively decodable codes (turbo-like codes) would also be considered block codes. A non-terminated convolutional encoder would be an example of a non-block (unframed) code, which has memory and is instead classified as a tree code. This article deals with \"algebraic block codes\". The data stream to be encoded is modeled as a string over some alphabet \\Sigma . The size |\\Sigma| of the alphabet is often written as q . If q=2 , then the block code is called a binary block code. In many applications it is useful to consider q to be a prime power, and to identify \\Sigma with the finite field \\mathbb F_q . If c=C(m) for some message m , then c is called the codeword of m . R=k/n . A large rate means that the amount of actual message per transmitted block is high. In this sense, the rate measures the transmission speed and the quantity 1-R measures the overhead that occurs due to the encoding with the block code. It is a simple information theoretical fact that the rate cannot exceed 1 since data cannot in general be losslessly compressed. Formally, this follows from the fact that the code C is an injective map. === The distance d === The distance or minimum distance of a block code is the minimum number of positions in which any two distinct codewords differ, and the relative distance \\delta is the fraction d/n . Formally, for received words c_1,c_2\\in\\Sigma^n , let \\Delta(c_1,c_2) denote the Hamming distance between c_1 and c_2 , that is, the number of positions in which c_1 and c_2 differ. Then the minimum distance d of the code C is defined as d := \\min_{m_1,m_2\\in\\Sigma^k\\atop m_1\\neq m_2} \\Delta[C(m_1),C(m_2)] . Since any code has to be injective, any two codewords will disagree in at least one position, so the distance of any code is at least 1 . Besides, the distance equals the minimum weight for linear block codes because: \\min_{m_1,m_2\\in\\Sigma^k\\atop m_1\\neq m_2} \\Delta[C(m_1),C(m_2)] = \\min_{m_1,m_2\\in\\Sigma^k\\atop m_1\\neq m_2} \\Delta[\\mathbf{0},C(m_2)-C(m_1)] = \\min_{m\\in\\Sigma^k\\atop m\\neq\\mathbf{0}} w[C(m)] = w_\\min . A larger distance allows for more error correction and detection. For example, if we only consider errors that may change symbols of the sent codeword but never erase or add them, then the number of errors is the number of positions in which the sent codeword and the received word differ. A code with distance allows the receiver to detect up to d-1 transmission errors since changing d-1 positions of a codeword can never accidentally yield another codeword. Furthermore, if no more than (d-1)/2 transmission errors occur, the receiver can uniquely decode the received word to a codeword. This is because every received word has at most one codeword at distance (d-1)/2 . If more than (d-1)/2 transmission errors occur, the receiver cannot uniquely decode the received word in general as there might be several possible codewords. One way for the receiver to cope with this situation is to use list decoding, in which the decoder outputs a list of all codewords in a certain radius. For binary codes with q=2 , the index is sometimes dropped. For maximum distance separable codes, the distance is always d=n-k+1 , but sometimes the precise distance is not known, non-trivial to prove or state, or not needed. In such cases, the d -component may be missing. Sometimes, especially for non-block codes, the notation (n,M,d)_q is used for codes that contain M codewords of length n . For block codes with messages of length k over an alphabet of size q , this number would be M=q^k . Reed–Solomon codes are a family of [n,k,d]_q codes with d=n-k+1 and q being a prime power. Rank codes are family of [n,k,d]_q codes with d \\leq n-k+1 . Hadamard codes are a family of [n,k,d]_2 codes with n=2^{k-1} and d=2^{k-2} . C =\\{C_i\\}_{i\\ge1} is called family of codes, where C_i is an (n_i,k_i,d_i)_q code with monotonic increasing n_i . Rate of family of codes is defined as R(C)=\\lim_{i\\to\\infty}{k_i \\over n_i} Relative distance of family of codes is defined as \\delta(C)=\\lim_{i\\to\\infty}{d_i \\over n_i} To explore the relationship between R(C) and \\delta(C) , a set of lower and upper bounds of block codes are known. R \\le 1- {1 \\over n} \\cdot \\log_{q} \\cdot \\left[\\sum_{i=0}^{\\left\\lfloor {{\\delta \\cdot n-1}\\over 2}\\right\\rfloor}\\binom{n}{i}(q-1)^i\\right] For q=2 , R+2\\delta\\le1 . In other words, k + 2d \\le n . For the general case, the following Plotkin bounds holds for any C \\subseteq \\mathbb{F}_q^{n} with distance : If d=\\left(1-{1 \\over q}\\right)n, |C| \\le 2qn If d > \\left(1-{1 \\over q}\\right)n, |C| \\le {qd \\over {qd -\\left(q-1\\right)n}} For any -ary code with distance \\delta , R \\le 1- \\left({q \\over {q-1}}\\right) \\delta + o\\left(1\\right) H_q\\left(x\\right) ~\\overset{\\underset{\\mathrm{def}}{}}{=}~ -x\\cdot\\log_q{x \\over {q-1}}-\\left(1-x\\right)\\cdot\\log_q{\\left(1-x\\right)} is the -ary entropy function. Define J_q\\left(\\delta\\right) ~\\overset{\\underset{\\mathrm{def}}{}}{=}~ \\left(1-{1\\over q}\\right)\\left(1-\\sqrt{1-{q \\delta \\over{q-1}}}\\right) . Let J_q\\left(n, d, e\\right) be the maximum number of codewords in a Hamming ball of radius for any code C \\subseteq \\mathbb{F}_q^n of distance . Then we have the Johnson Bound : J_q\\left(n,d,e\\right)\\le qnd , if {e \\over n} \\le {{q-1}\\over q}\\left( {1-\\sqrt{1-{q \\over{q-1}}\\cdot{d \\over n}}}\\, \\right)=J_q\\left({d \\over n}\\right) R={\\log_q \\over n} \\le 1-H_q\\left(J_q\\left(\\delta\\right)\\right)+o\\left(1\\right) ==See also== Channel capacity Shannon–Hartley theorem Noisy channel List decoding Sphere packing",
  "categories": [
    "104792109",
    "20476821",
    "22953528",
    "23118434",
    "23603337",
    "24745114",
    "24745117",
    "24745122",
    "26862229",
    "26862433",
    "31347309",
    "33256317"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1377677307",
  "content_hash": "",
  "created_at": null,
  "updated_at": 1790771160.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "enwiki-001377677307",
    "type": "webpage",
    "title": "Block 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/block-code",
    "issued": {
      "date-parts": [
        [
          2026,
          11,
          18
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          18
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:enwiki-001377677307",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1377677307",
    "note": "Immutable snapshot enwiki-001377677307"
  }
}