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 \([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)\). | |
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)\) [11; 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 [12,13], (see [14; Ch. 9]). See Ref. [15] for bounds on mixed orthogonal arrays. |
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 [16; pg. 107][17; 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\) [18–20]. |
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 [21,22]. |
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)\). | |
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 | \([n,1,n]_q\) binary linear 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]
- P. R. J. Östergård, "Construction and Classification of Codes." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [12]
- Addelman, S., & Kempthorne, O. (1961b). Orthogonal Main-Effect Plans. Technical Report ARL 79, Aeronautical Research Lab., Wright-Patterson Air Force Base, Ohio, Nov. 1961.
- [13]
- 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
- [14]
- A. S. Hedayat, N. J. A. Sloane, and J. Stufken, Orthogonal Arrays (Springer New York, 1999) DOI
- [15]
- 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
- [16]
- R. Calderbank and W. M. Kantor, “The Geometry of Two-Weight Codes”, Bulletin of the London Mathematical Society 18, 97 (1986) DOI
- [17]
- J. Bierbrauer, Introduction to Coding Theory (Chapman and Hall/CRC, 2016) DOI
- [18]
- P. Delsarte, “Four fundamental parameters of a code and their combinatorial significance”, Information and Control 23, 407 (1973) DOI
- [19]
- T. Etzion and A. Vardy, “Perfect binary codes: constructions, properties, and enumeration”, IEEE Transactions on Information Theory 40, 754 (1994) DOI
- [20]
- 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
- [21]
- D. Goyeneche and K. Życzkowski, “Genuinely multipartite entangled states and orthogonal arrays”, Physical Review A 90, (2014) arXiv:1404.3586 DOI
- [22]
- D. Goyeneche et al., “Entanglement and quantum combinatorial designs”, Physical Review A 97, (2018) arXiv:1708.05946 DOI
- [23]
- Combinatorial Designs (Springer-Verlag, 2004) DOI