Here is a list of codes related to orthogonal arrays.

[Jump to code graph excerpt]

Code Description Relation
Binary code Encodes \(K\) states (codewords) in \(n\) binary coordinates and has distance \(d\). Usually denoted as \((n,K,d)\). The distance is the minimum Hamming distance between a pair of distinct codewords. An \((n,K)\) binary code with dual distance \(d^{\perp}\) is an OA\(_{K/2^{d^{\perp}-1}}(d^{\perp}-1,n,2)\) [1][2; Ch. 5].
Denniston code Projective code that is part of a family of \([2^{a+i}+2^i-2^a,3,2^{a+i}-2^a]_{2^a}\) codes for \(i < a\) constructed using Denniston arcs [3; Sec. 19.7.3].
Extended GRS code A GRS code extended by one extra coordinate to form an \([n+1,k,n-k+2]_q\) MDS code. In projective language, this corresponds to adding one more evaluation point, often interpreted as the point at infinity; in suitable equivalent descriptions, one may instead use an affine point such as \(0\). The case when \(n=q-1\), multipliers \(v_i=1\), and \(\alpha_i\) are \(i-1\)st powers of a primitive \(n\)th root of unity is an extended narrow-sense RS code.
Generalized RS (GRS) code An \([n,k,n-k+1]_q\) MDS code that is a modification of the RS code where codeword polynomials are multiplied by additional prefactors [4; Def. 15.3.19].
Hirschfeld code A \([q+1,4,q-2]_q\) projective geometry code for non-prime \(q\) that is an example of an MDS code that is not an RS code; see [5; Exam. 7.6] for the generator matrix.
Hyperoval code Projective code constructed from a hyperoval in the projective plane \(PG(2,q)\), where \(q\) is even. Since a hyperoval is a set of \(q+2\) points with no three collinear, the corresponding projective code has parameters \([q+2,3,q]_q\) [3; Exam. 19.2.1]; the \([6,3,4]_4\) hexacode is the smallest example.
Maximum distance separable (MDS) code A \(q\)-ary linear code whose parameters satisfy the Singleton bound with equality. An MDS code is an OA\(_{1}(k,n,q)\) [6; Thm. 3.3.19].
Mixed code Encodes \(K\) states (codewords) in a string of two or more coordinates, each of which takes values in one of two or more possible groups. Orthogonal arrays generalized to mixed alphabets are called mixed-level orthogonal arrays [7,8] (see [9; Ch. 9]). See Ref. [10] for bounds on mixed orthogonal arrays.
Narrow-sense RS code An \([q-1,k,n-k+1]_q\) RS code whose points \(\alpha_i\) are all \((i-1)\)st powers of a primitive element \(\alpha\) of \(\mathbb{F}_q\).
Niederreiter-Rosenbloom-Tsfasman (NRT) code A poset code based on a partial ordering of \([n]\), i.e., \(1\leq 2\leq \cdots \leq n\). There exist orthogonal arrays in ordered Hamming space [11,12].
Orthogonal array (OA) An orthogonal array, or OA\(_{\lambda}(t,n,q)\), of strength \(t\) with \(q\) levels and \(n\) constraints is a set of \(q\)-ary strings such that any subset of \(t\) coordinates contains every length-\(t\) string an equal number of times \(\lambda\), which is the index of the array [6; Def. 3.3.18].
Ovoid code Member of a \([q^2+1,4,q^2-q]_q\) projective two-weight code family obtained from ovoids in \(\mathrm{PG}(3,q)\). If the columns of a generator matrix are the \(q^2+1\) points of an ovoid, then every hyperplane meets the ovoid in either \(1\) or \(q+1\) points, yielding the two nonzero weights \(q^2\) and \(q^2-q\). See [13; pg. 107][14; pg. 192] for further details.
Perfect binary code A type of binary code whose parameters satisfy the Hamming bound with equality. Perfect distance-three binary codes of length \(n =2^m-1\) are equivalent to binary orthogonal arrays of strength \(t = 2^{m-1}-1\) [15–17].
Perfect-tensor code Block quantum code encoding one subsystem into an odd number \(n\) subsystems whose encoding isometry is a perfect tensor. This code stems from an AME\((n,q)\) AME state, or equivalently, a \(((n+1,1,\lfloor (n+1)/2 \rfloor + 1))\) code. Orthogonal arrays and \(d\)-uniform quantum states are related [18–23].
Reed-Muller (RM) code Member of the RM\((r,m)\) family of linear binary codes derived from multivariate polynomials. The code parameters are \([2^m,\sum_{j=0}^{r} {m \choose j},2^{m-r}]\), where \(r\) is the order of the code satisfying \(0\leq r\leq m\). First-order RM codes are also called biorthogonal codes, while \(m\)th order RM codes are also called universe codes. Punctured RM codes RM\(^*(r,m)\) are obtained from RM codes by deleting one coordinate from each codeword. RM codes are related to orthogonal arrays [24; Exam. 10.57].
Reed-Solomon (RS) code An \([n,k,n-k+1]_q\) linear code based on polynomials over \(\mathbb{F}_q\).
Repetition code \([n,1,n]\) binary linear code encoding one bit of information into an \(n\)-bit string. Majority decoding requires \(n\) to be odd in order to avoid ties. The idea is to increase the code distance by repeating the logical information several times. Its automorphism group is \(S_n\).
Roth-Lempel code Member of a \(q\)-ary linear code family that includes many examples of MDS codes that are not GRS codes.
Semakov-Zinoviev-Zaitsev (SZZ) equidistant code Member of a nonlinear \(q\)-ary code family that is related to affine resolvable block designs and that is universally optimal.
\((16,256,6)\) Nordstrom-Robinson (NR) code A nonlinear \((16,256,6)\) binary code that is the smallest Kerdock code and the smallest Preparata code. The size of this code is larger than the largest possible linear code with the same length and distance. The NR code is an orthogonal array of strength \(5\) [2; pg. 141].
\((2^{m+1}-1,2^{2n-m},3)\) Vasilyev code Member of an infinite \((2^{m+1}-1,2^{2n-m},3)\) family of perfect nonlinear codes for any \(m \geq 3\). Constructed by applying a modification of the \((u|u+v)\) construction to a perfect \((2^m-1,2^{n-m},3)\) code, not necessarily linear [2; pg. 77].
\(ED_m\) code Member of a family of nonlinear \( (c\frac{qt-1}{(t-1,q-1)},qt,ct\frac{q-1}{(t-1,q-1)}) \) \(q\)-ary codes, where \(c,t\geq 1\) and \((a,b)\) is the greatest common divisor of \(a\) and \(b\). Such codes are universally optimal and are related to resolvable block designs.
\([10,5,6]_9\) Glynn code The unique trace-Hermitian self-dual \([10,5,6]_9\) code, constructed using a 10-arc in \(PG(4,9)\) that is not a rational curve.
\([12,6,6]_3\) Extended ternary Golay code Self-dual ternary code that corrects two errors on twelve trits and is unique for its parameters up to equivalence [25]. It is obtained from the \([11,6,5]_3\) ternary Golay code by adding a parity-check trit.
\([23, 12, 7]\) Golay code A \([23, 12, 7]\) perfect binary linear code with connections to various areas of mathematics, e.g., lattices [26] and sporadic simple groups [2]. Up to equivalence, it is unique for its parameters [25]. The dual of the Golay code is its \([23,11,8]\) even-weight subcode [27,28].
\([24, 12, 8]\) Extended Golay code A self-dual \([24, 12, 8]\) code that is obtained from the Golay code by adding a parity check. Equivalently, puncturing any coordinate yields the \([23,12,7]\) Golay code. Up to equivalence, it is unique for its parameters [25], and it is the unique \([24,12,8]\) extremal Type II code [29; Rems. 4.3.10 and 4.3.11]. The extended Golay code is an orthogonal array of strength 7 [30; Exam. 1].
\([2^r-1,2^r-r-1,3]\) Hamming code Member of an infinite family of perfect linear codes with parameters \([2^r-1,2^r-r-1, 3]\) for \(r \geq 2\). Their \(r \times (2^r-1) \) parity-check matrix \(H\) has all possible nonzero \(r\)-bit strings as its columns. Adding a parity check yields the \([2^r,2^r-r-1, 4]\) extended Hamming code.
\([4,2,3]_3\) Tetracode The \([4,2,3]_3\) ternary self-dual MDS code that has connections to lattices [26]. It is the unique MDS code with its parameters [31,32]. Its weight enumerator is the Gleason polynomial \(g_4\) [29; Rem. 4.2.6].
\([4,2,3]_4\) RS\(_4\) code A Type II Euclidean self-dual extended RS code that is the smallest quaternary extended QR code [2; pg. 296][33; Sec. 2.4.2]. Puncturing the \([4,2,3]_4\) RS\(_4\) code yields the \([3,2,2]_4\) shortened RS\(_4\) code, which is an RS code [2; pg. 295].
\([4,3,2]\) single parity-check (SPC) code Binary code that detects any single bit flip on four bits by appending one parity bit to three message bits.
\([5,3,3]_4\) Shortened hexacode A perfect \([5,3,3]_4\) quaternary Hamming code that is the result of puncturing the hexacode [34].
\([56,6,36]_3\) Hill-cap code Projective two-weight ternary code based on the Games graph [35][3; Table 19.1] and Hill’s 56-cap [36]. Its automorphism group contains \(PSL(3,4)\) [37].
\([6,3,4]_4\) Hexacode The \([6,3,4]_4\) Hermitian self-dual MDS code that has connections to projective geometry, lattices [26], and conformal field theory [38]. Its weight enumerator is the Gleason polynomial \(g_7\) [29; Rem. 4.2.6].
\([7,4,3]\) Hamming code Second-smallest member of the Hamming code family.
\([78,6,56]_4\) Hill-cap code Projective two-weight quaternary code based on a cap that corresponds to a strongly regular graph [35; Table 7.1].
\([n,n-1,2]\) Single parity-check (SPC) code An \([n,n-1,2]\) linear binary code whose codewords consist of the message string appended with a parity-check bit or parity bit such that the parity (i.e., sum over all coordinates of each codeword) is zero [39; Sec. 2]. If the Hamming weight of a message is odd (even), then the parity bit is one (zero). This code requires only one extra bit of overhead and is therefore inexpensive. Its codewords are all even-weight binary strings, and its parity-check matrix is a row vector of all ones. Its automorphism group is \(S_n\).
\([n,n-1,2]_q\) \(q\)-ary parity-check code An \([n,n-1,2]_q\) linear \(q\)-ary code whose codewords consist of the message string appended with a parity-check or zero-sum check digit such that the sum over all coordinates of each codeword is zero.
\(q\)-ary repetition code An \([n,1,n]_q\) code consisting of codewords \((j,j,\cdots,j)\) for \(j \in \mathbb{F}_q\).
\(q\)-ary sharp configuration A \(q\)-ary code that admits \(m\) different distances between distinct codewords and forms a design of strength \(2m-1\) or greater.
List (descendants_and_cousins): All descendants and cousins of Orthogonal array (OA).

References

  1. [1]

    P. Delsarte, “Bounds for unrestricted codes, by linear programming”, Philips Research Reports 27, 272-289 (1972)

  2. [2]

    F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes (Elsevier, 1977)

  3. [3]

    A. E. Brouwer, “Two-weight Codes”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 449-462 DOI

  4. [4]

    A. Couvreur, H. Randriambololona, “Algebraic Geometry Codes and Some Applications”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 311-362 DOI

  5. [5]

    S. Ball, Finite Geometry and Combinatorial Applications (Cambridge University Press, 2015) DOI

  6. [6]

    P. R. J. Östergård, “Construction and Classification of Codes”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 61-78 DOI

  7. [7]

    S. Addelman and O. Kempthorne (1961b). Orthogonal Main-Effect Plans. Technical Report ARL 79, Aeronautical Research Lab., Wright-Patterson Air Force Base, Ohio, Nov. 1961

  8. [8]

    C. R. RAO, “Some Combinatorial Problems of Arrays and Applications to Design of Experiments††Paper read at the International Symposium on Combinatorial Mathematics and its Applications, Fort Collins, Colorado, September 1971.”, A Survey of Combinatorial Theory 349 (1973) DOI

  9. [9]

    A. S. Hedayat, N. J. A. Sloane, and J. Stufken, Orthogonal Arrays (Springer New York, 1999) DOI

  10. [10]

    N. J. A. Sloane and J. Stufken, “A linear programming bound for orthogonal arrays with mixed levels”, Journal of Statistical Planning and Inference 56, 295 (1996) DOI

  11. [11]

    W. J. Martin and D. R. Stinson, “Association Schemes for Ordered Orthogonal Arrays and (T, M, S)-Nets”, Canadian Journal of Mathematics 51, 326 (1999) DOI

  12. [12]

    A. Barg and P. Purkayastha, “Bounds on ordered codes and orthogonal arrays”, (2009) arXiv:cs/0702033

  13. [13]

    R. Calderbank and W. M. Kantor, “The Geometry of Two-Weight Codes”, Bulletin of the London Mathematical Society 18, 97 (1986) DOI

  14. [14]

    J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016) DOI

  15. [15]

    P. Delsarte, “Four fundamental parameters of a code and their combinatorial significance”, Information and Control 23, 407 (1973) DOI

  16. [16]

    T. Etzion and A. Vardy, “Perfect binary codes: constructions, properties, and enumeration”, IEEE Transactions on Information Theory 40, 754 (1994) DOI

  17. [17]

    P. R. J. Ostergard, O. Pottonen, and K. T. Phelps, “The Perfect Binary One-Error-Correcting Codes of Length 15: Part II—Properties”, IEEE Transactions on Information Theory 56, 2571 (2010) arXiv:0903.2749 DOI

  18. [18]

    D. Goyeneche and K. Życzkowski, “Genuinely multipartite entangled states and orthogonal arrays”, Physical Review A 90, (2014) arXiv:1404.3586 DOI

  19. [19]

    D. Goyeneche, Z. Raissi, S. Di Martino, and K. Życzkowski, “Entanglement and quantum combinatorial designs”, Physical Review A 97, (2018) arXiv:1708.05946 DOI

  20. [20]

    Y. Zang, Z. Tian, S.-M. Fei, and H.-J. Zuo, “Quantum k-Uniform States From Quantum Orthogonal Arrays”, International Journal of Theoretical Physics 62, (2023) arXiv:2303.15001 DOI

  21. [21]

    S.-Q. Pang, X. Zhang, X. Lin, and Q.-J. Zhang, “Two and three-uniform states from irredundant orthogonal arrays”, npj Quantum Information 5, (2019) DOI

  22. [22]

    M.-S. Li and Y.-L. Wang, “k -uniform quantum states arising from orthogonal arrays”, Physical Review A 99, (2019) DOI

  23. [23]

    R. Yan, S. Pang, M. Chen, and F. Yang, “Quantum Error-Correcting Codes Based on Orthogonal Arrays”, Entropy 25, 680 (2023) DOI

  24. [24]

    Combinatorial Designs (Springer-Verlag, 2004) DOI

  25. [25]

    P. Delsarte and J. M. Goethals, “Unrestricted codes with the golay parameters are unique”, Discrete Mathematics 12, 211 (1975) DOI

  26. [26]

    J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI

  27. [27]

    W. Feit, “Some remarks on weight functions of spaces over GF(2)”, unpublished (1972)

  28. [28]

    C. L. Mallows and N. J. A. Sloane, “Weight enumerators of self-orthogonal codes”, Discrete Mathematics 9, 391 (1974) DOI

  29. [29]

    S. Bouyuklieva, “Self-dual codes”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 79-96 DOI

  30. [30]

    P. Delsarte and V. I. Levenshtein, “Association schemes and coding theory”, IEEE Transactions on Information Theory 44, 2477 (1998) DOI

  31. [31]

    O. Taussky and J. Todd, “Covering theorems for groups”, Bulletin of the American Mathematical Society 54(3) (1948)

  32. [32]

    J. G. Kalbfleisch and R. G. Stanton, “A Combinatorial Problem in Matching”, Journal of the London Mathematical Society s1-44, 60 (1969) DOI

  33. [33]

    Self-Dual Codes and Invariant Theory (Springer-Verlag, 2006) DOI

  34. [34]

    G. Höhn, “Self-dual Codes over the Kleinian Four Group”, (2000) arXiv:math/0005266

  35. [35]

    R. A. Games, “The packing problem for projective geometries over GF(3) with dimension greater than five”, Journal of Combinatorial Theory, Series A 35, 126 (1983) DOI

  36. [36]

    R. Hill, “On the largest size of cap in s53”, Atti della Accademia Nazionale dei Lincei. Classe di Scienze Fisiche, Matematiche e Naturali. Rendiconti 54(3), 378-384 (1973)

  37. [37]

    N. Pace and A. Sonnino, “On linear codes admitting large automorphism groups”, Designs, Codes and Cryptography 83, 115 (2016) DOI

  38. [38]

    J. A. Harvey and G. W. Moore, “Moonshine, superconformal symmetry, and quantum error correction”, Journal of High Energy Physics 2020, (2020) arXiv:2003.13700 DOI

  39. [39]

    R. W. Hamming, “Error Detecting and Error Correcting Codes”, Bell System Technical Journal 29, 147 (1950) DOI

Classical Domain

  • Binary Kingdom
  • Galois-field Kingdom
  • Matrix Kingdom
  • Analog Kingdom
  • Spherical Kingdom
  • Ring Kingdom
  • Group Kingdom
  • Homogeneous-space Kingdom

Quantum Domain

  • Qubit Kingdom
  • Modular-qudit Kingdom
  • Galois-qudit Kingdom
  • Bosonic Kingdom
  • Spin Kingdom
  • Group quantum Kingdom
  • Homogeneous-space quantum Kingdom
  • Category Kingdom

Classical-quantum Domain

  • Binary c-q Kingdom
  • Analog c-q Kingdom

  • Home
  • Code graph
  • Code lists
  • Concepts glossary
  • Handbook
  • Search

  • Team
  • About

  • 🌒
≡
Error correction zoo by Victor V. Albert, Philippe Faist, and many contributors. This work is licensed under a CC-BY-SA License. See how to contribute.