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. | |
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. | |
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]. Adding a parity bit to the code results in the self-dual \([24, 12, 8]\) extended Golay code. Up to equivalence, both codes are unique for their respective parameters [4]. Shortening the Golay code yields the \([22,10,8]\), \([22,11,7]\), and \([22,12,6]\) shortened Golay codes [5]. The dual of the Golay code is its \([23,11,8]\) even-weight subcode [6,7]. | The extended Golay code is an orthogonal array of strength 7 [8; Exam. 1] |
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 [9]. Puncturing the code yields the perfect \([5,3,3]_4\) quaternary Hamming code known as the shortened hexacode or shorter hexacode [10]. 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 [11; 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)\) [12; Thm. 3.3.19]. |
Mixed code | Encodes \(K\) states (codewords) in a string of coordinates which takes values in more than one group. | Orthogonal arrays generalized to mixed alphabets are caled mixed-level orthogonal arrays [13,14], (see [15; Ch. 9]). See Ref. [16] 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 [17; pg. 107][18; 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\) [19–21]. |
Perfect-tensor code | Block quantum code encoding one subsystem into \(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))_{\mathbb{Z}_q}\) code. | Orthogonal arrays and \(d\)-uniform quantum states are related [22,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 \(GF(q)\). | |
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 [4]. The dual of the ternary Golay code is a \([11,5,6]_3\) projective two-weight subcode. | |
Tetracode | The \([4,2,3]_3\) 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]. | |
\(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. | |
\([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 non-zero \(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]
- P. Delsarte and J. M. Goethals, “Unrestricted codes with the golay parameters are unique”, Discrete Mathematics 12, 211 (1975) DOI
- [5]
- 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
- [6]
- W. Feit. Some remarks on weight functions of spaces over GF(2), unpublished (1972)
- [7]
- C. L. Mallows and N. J. A. Sloane, “Weight enumerators of self-orthogonal codes”, Discrete Mathematics 9, 391 (1974) DOI
- [8]
- P. Delsarte and V. I. Levenshtein, “Association schemes and coding theory”, IEEE Transactions on Information Theory 44, 2477 (1998) DOI
- [9]
- 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
- [10]
- G. Hoehn, “Self-dual Codes over the Kleinian Four Group”, (2000) arXiv:math/0005266
- [11]
- S. Ball, Finite Geometry and Combinatorial Applications (Cambridge University Press, 2015) DOI
- [12]
- P. R. J. Östergård, "Construction and Classification of Codes." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [13]
- Addelman, S., & Kempthorne, O. (1961b). Orthogonal Main-Effect Plans. Technical Report ARL 79, Aeronautical Research Lab., Wright-Patterson Air Force Base, Ohio, Nov. 1961.
- [14]
- 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
- [15]
- A. S. Hedayat, N. J. A. Sloane, and J. Stufken, Orthogonal Arrays (Springer New York, 1999) DOI
- [16]
- 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
- [17]
- R. Calderbank and W. M. Kantor, “The Geometry of Two-Weight Codes”, Bulletin of the London Mathematical Society 18, 97 (1986) DOI
- [18]
- J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016) DOI
- [19]
- P. Delsarte, “Four fundamental parameters of a code and their combinatorial significance”, Information and Control 23, 407 (1973) DOI
- [20]
- T. Etzion and A. Vardy, “Perfect binary codes: constructions, properties, and enumeration”, IEEE Transactions on Information Theory 40, 754 (1994) DOI
- [21]
- 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
- [22]
- D. Goyeneche and K. Życzkowski, “Genuinely multipartite entangled states and orthogonal arrays”, Physical Review A 90, (2014) arXiv:1404.3586 DOI
- [23]
- D. Goyeneche et al., “Entanglement and quantum combinatorial designs”, Physical Review A 97, (2018) arXiv:1708.05946 DOI
- [24]
- Combinatorial Designs (Springer-Verlag, 2004) DOI