Here is a list of codes related to orthogonal arrays.
| 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]_{GF(2^a)}\) codes for \(i < a\) constructed using Denniston arcs. | |
| Extended GRS code | A GRS code with an additional parity-check coordinate with corresponding evaluation point of zero. In other words, an \([n+1,k,n-k+2]_q\) GRS code whose polynomials are evaluated at the points \((\alpha_1,\cdots,\alpha_n,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. | |
| Five-qubit perfect code | Five-qubit cyclic stabilizer code that is the smallest qubit stabilizer code to correct a single-qubit error. | |
| Generalized RS (GRS) code | An \([n,k,n-k+1]_q\) linear code that is a modification of the RS code where codeword polynomials are multiplied by additional prefactors. | |
| 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. | |
| Griesmer code | A type of \(q\)-ary code whose parameters satisfy the Griesmer bound with equality. | |
| Hexacode | The \([6,3,4]_4\) self-dual MDS code that has connections to projective geometry, lattices [3], and conformal field theory [4]. Puncturing the code yields the perfect \([5,3,3]_4\) quaternary Hamming code known as the shortened hexacode or shorter hexacode [5]. Both codes are sometimes refereed to as Golay codes over \(GF(4)\). | |
| Hirschfeld code | A projective geometry code that is an example of an MDS code that is not an RS code; see [6; Exam. 7.6] for the description. | |
| Maximum distance separable (MDS) code | A type of \(q\)-ary code whose parameters satisfy the Singleton bound with equality. | An MDS code is an OA\(_{1}(k,n,q)\) [7; 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 [8,9], (see [10; Ch. 9]). See Ref. [11] 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 \(GF(q)\). | |
| 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. | |
| Ovoid code | Member of a \([q^2+1,4,q^2-q]_q\) projective code family that is universally optimal and that is constructed using ovoids in projective space. See [12; pg. 107][13; pg. 192] for further details. | |
| Perfect binary code | An \((n,K,2t+1)\) binary code is perfect if parameters \(n\), \(K\), and \(t\) are such that the binary Hamming (a.k.a. sphere-packing) bound \begin{align} \sum_{j=0}^{t} {n \choose j} \leq 2^{n}/K \tag*{(1)}\end{align} becomes an equality. For example, for a code with one logical bit (\(K=2\)) and \(t=1\), the bound becomes \(n+1 \leq 2^{n-1}\). Perfect codes are those for which balls of Hamming radius \(t\) exactly fill the space of all \(n\) binary strings. | Perfect distance-three binary codes of length \(n =2^m-1\) are equivalent to binary orthogonal arrays of strength \(t = 2^{m-1}-1\) [14–16]. |
| 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 [17–21]. |
| Quantum convolutional code | One-dimensional translationally invariant qubit stabilizer code whose whose stabilizer group can be partitioned into constant-size subsets of constant support and of constant overlap between neighboring sets. Initially formulated as a quantum analogue of convolutional codes, which were designed to protect a continuous and never-ending stream of information. Precise formulations sometimes begin with a finite-dimensional lattice, with the intent to take the thermodynamic limit; logical dimension can be infinite as well. | |
| Quantum irregular convolutional code (QIRCC) | Quantum convolutional code whose stabilizer group consists of different constant-size subsets. | |
| Quantum turbo code | A quantum version of the turbo code, obtained from an interleaved serial quantum concatenation [22; Def. 30] of quantum convolutional codes. | |
| 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 [23; Exam. 10.57]. |
| Reed-Solomon (RS) code | An \([n,k,n-k+1]_q\) linear code based on polynomials over \(GF(q)\). | |
| Repetition code | \([n,1,n]\) binary linear code encoding one bit of information into an \(n\)-bit string. The length \(n\) needs to be an odd number, since the receiver will pick the majority to recover the information. The idea is to increase the code distance by repeating the logical information several times. It is a \((n,1)\)-Hamming code. 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 family that is related to affine resolvable block designs and that is universally optimal. | |
| 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. 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. Its automorphism group is \(S_n\). | |
| Ternary Golay code | A \([11,6,5]_3\) perfect ternary linear code with connections to various areas of mathematics, e.g., lattices [3] and sporadic simple groups [2]. Adding a parity bit to the code results in the self-dual \([12,6,6]_3\) extended ternary Golay code. Up to equivalence, both codes are unique for their respective parameters [24]. The dual of the ternary Golay code is a \([11,5,6]_3\) projective two-weight subcode. | |
| Tetracode | The \([4,2,3]_3\) ternary self-dual MDS code that has connections to lattices [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]. | |
| \((5,1,2)\)-convolutional code | Family of quantum convolutional codes that are 1D lattice generalizations of the five-qubit perfect code, with the former''s lattice-translation symmetry being the extension of the latter''s cyclic permutation symmetry. | |
| \(ED_m\) code | Member of the family of \( (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. | |
| \([23, 12, 7]\) Golay code | A \([23, 12, 7]\) perfect binary linear code with connections to various areas of mathematics, e.g., lattices [3] and sporadic simple groups [2]. Up to equivalence, it is unique for its parameters [24]. Shortening the Golay code yields the \([22,10,8]\), \([22,11,7]\), and \([22,12,6]\) shortened Golay codes [25]. The dual of the Golay code is its \([23,11,8]\) even-weight subcode [26,27]. | |
| \([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. Up to equivalence, it is unique for its parameters [24]. | The extended Golay code is an orthogonal array of strength 7 [28; Exam. 1]. |
| \([2^m-1,m,2^{m-1}]\) simplex code | A member of the code family that is dual to the \([2^m,2^m-m-1,3]\) Hamming family. The columns of its generator matrix are in one-to-one correspondence with the elements of the projective space \(PG(m-1,2)\), with each column being a chosen representative of the corresponding element. The codewords form a \((2^m,2^m+1)\) simplex spherical code under the antipodal mapping. | |
| \([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. | |
| \([7,3,4]\) simplex code | Second-smallest member of the simplex code family. The columns of its generator matrix are in one-to-one correspondence with the elements of the projective space \(PG(2,2)\), with each column being a chosen representative of the corresponding element. The codewords form a \((8,9)\) simplex spherical code under the antipodal mapping. | |
| \([7,4,3]\) Hamming code | Second-smallest member of the Hamming code family. | |
| \(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 encoding consisting of codewords \((j,j,\cdots,j)\) for \(j \in GF(q)\). The length \(n\) needs to be an odd number, since the receiver will pick the majority to recover the information. | |
| \(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. | |
| \(q\)-ary simplex code | An \([n,m,q^{m-1}]_q\) projective code with \(n=\frac{q^m-1}{q-1}\), denoted as \(S(q,m)\). The columns of the generator matrix are in one-to-one correspondence with the elements of the projective space \(PG(m-1,q)\), with each column being a chosen representative of the corresponding element. |
References
- [1]
- Delsarte, Philippe. "Bounds for unrestricted codes, by linear programming." (1972).
- [2]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [3]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [4]
- 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
- [5]
- G. Hoehn, “Self-dual Codes over the Kleinian Four Group”, (2000) arXiv:math/0005266
- [6]
- S. Ball, Finite Geometry and Combinatorial Applications (Cambridge University Press, 2015) DOI
- [7]
- P. R. J. Östergård, "Construction and Classification of Codes." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [8]
- Addelman, S., & Kempthorne, O. (1961b). Orthogonal Main-Effect Plans. Technical Report ARL 79, Aeronautical Research Lab., Wright-Patterson Air Force Base, Ohio, Nov. 1961.
- [9]
- 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
- [10]
- A. S. Hedayat, N. J. A. Sloane, and J. Stufken, Orthogonal Arrays (Springer New York, 1999) DOI
- [11]
- 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
- [12]
- R. Calderbank and W. M. Kantor, “The Geometry of Two-Weight Codes”, Bulletin of the London Mathematical Society 18, 97 (1986) DOI
- [13]
- J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016) DOI
- [14]
- P. Delsarte, “Four fundamental parameters of a code and their combinatorial significance”, Information and Control 23, 407 (1973) DOI
- [15]
- T. Etzion and A. Vardy, “Perfect binary codes: constructions, properties, and enumeration”, IEEE Transactions on Information Theory 40, 754 (1994) DOI
- [16]
- 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
- [17]
- D. Goyeneche and K. Życzkowski, “Genuinely multipartite entangled states and orthogonal arrays”, Physical Review A 90, (2014) arXiv:1404.3586 DOI
- [18]
- D. Goyeneche, Z. Raissi, S. Di Martino, and K. Życzkowski, “Entanglement and quantum combinatorial designs”, Physical Review A 97, (2018) arXiv:1708.05946 DOI
- [19]
- 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
- [20]
- 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
- [21]
- M.-S. Li and Y.-L. Wang, “k -uniform quantum states arising from orthogonal arrays”, Physical Review A 99, (2019) DOI
- [22]
- D. Poulin, J.-P. Tillich, and H. Ollivier, “Quantum serial turbo-codes”, (2009) arXiv:0712.2888
- [23]
- Combinatorial Designs (Springer-Verlag, 2004) DOI
- [24]
- P. Delsarte and J. M. Goethals, “Unrestricted codes with the golay parameters are unique”, Discrete Mathematics 12, 211 (1975) DOI
- [25]
- J. H. Conway and N. J. A. Sloane, “Orbit and coset analysis of the Golay and related codes”, IEEE Transactions on Information Theory 36, 1038 (1990) DOI
- [26]
- W. Feit. Some remarks on weight functions of spaces over GF(2), unpublished (1972)
- [27]
- C. L. Mallows and N. J. A. Sloane, “Weight enumerators of self-orthogonal codes”, Discrete Mathematics 9, 391 (1974) DOI
- [28]
- P. Delsarte and V. I. Levenshtein, “Association schemes and coding theory”, IEEE Transactions on Information Theory 44, 2477 (1998) DOI