Here is a list of codes related to combinatorial designs.

[Jump to code graph excerpt]

Code Relation
Algebraic LDPC code Combinatorial designs can be used to construct explicit LDPC codes [1–3].
Binary BCH code A family of BCH codes supports an infinite family of combinatorial 4-designs [4,5].
Binary code If the number of a code is less than or equal to its dual distance, then some sets of fixed-weight codewords form a combinatorial design [6; Thm. 6.7].
Combinatorial design
Constant-weight block code Optimal constant-weight codes over \(\mathbb{Z}_q\) can be constructed [7] from a generalization of combinatorial designs to \(q\)-ary alphabets [8,9].
Cyclic linear \(q\)-ary code Two families of cyclic \(q\)-ary codes support an infinite family of combinatorial 3-designs [10]. The supports of all fixed-weight codewords of a \(q\)-ary cyclic code support a combinatorial \(1\)-design [11; Corr. 5.2.4].
Dual linear code Linear codes and their duals are related to combinatorial designs via the Assmus-Mattson theorem [12,13] (see [11; Sec. 5.4]).
EA combinatorial-design QLDPC code Combinatorial designs can be used to construct EA QLDPC codes [14].
Editing code Perfect deletion correcting codes can be constructed using combinatorial design theory [15,16].
Extended quaternary Golay code Supports of codewords of any fixed symmetrized type of the extended quaternary Golay code form a 5-design [17–19].
Gallager (GL) code Some Steiner systems can be used to construct Gallager codes [20].
Hadamard code Hadamard designs are combinatorial designs constructed from Hadamard matrices [21,22]; see Ref. [23].
Higman-Sims graph-adjacency code Codewords of weight 36 of the Higman-Sims graph-adjacency code form a \(2\)-\((100,36,525)\) design [24; Remark 1.7]
Hoffman-Singleton cycle code The incidence matrix of the Hoffman-Singleton graph can be converted into a \(2\)-\((50,14,13)\) design [24; Prop. 1.1].
Jump code Certain types of combinatorial designs can be used to obtain jump codes [25–27].
Lexicographic code Some lexicodes yield Steiner systems [28].
Mixed code Combinatorial designs have been generalized to mixed alphabets [29].
Nordstrom-Robinson (NR) code NR codewords give \(3\)-\((16, 6, 4)\), \(3\)-\((16, 8, 3)\), and \(3\)-\((16, 10, 24)\) designs [6; pg. 164].
Perfect code Perfect codes and combinatorial designs are related [30,31].
Perfect-tensor code Combinatorial designs and \(d\)-uniform quantum states are related [32–34].
Pless symmetry code The supports of fixed-weight codewords of certain Pless symmetry codes support combinatorial designs [35–37].
Preparata code Preparata codewords of each weight form a 3-design [6; pg. 471].
Pseudo Golay code Supports of codewords of any fixed symmetrized type of pseudo Golay codes form a 5-design [17–19].
Quadratic-residue (QR) code The supports of fixed-weight codewords of certain \(q\)-ary QR codes support combinatorial designs [12,30,37], including \(3\)-designs [38].
Reed-Muller (RM) code Fixed-weight RM codewords of weight less than \(2^m\) support combinatorial 3-designs [11; Exam. 5.2.7].
Self-dual linear code Self-dual extremal codes yield combinatorial \(\leq 5\)-designs using the Assmus-Mattson theorem [12] (see [11; Sec. 5.4]). See [39; Table 1.61, pg. 683] for a table of combinatorial designs obtained from self-dual codes.
Subspace design Combinatorial designs are designs in Johnson space, the space of all size-\(w\) subsets of a set with \(n\) elements. The \(q\)-Johnson spaces generalize this notion to subspaces and reduce to Johnson spaces at \(q=1\). In other words, combinatorial designs are designs over spaces of subsets, while subspace designs are designs over spaces of subspaces.
ZRM code The weight-four codewords of the binary image of the dual of ZRM\((1,m)\) form a Steiner system that is identical to that formed by the weight-four codewords of an extended Hamming code [40].
\((12,4^6,6)_4\) Dodecacode There exists a \(5\)-\((12, 6, 3)\) design in the dodecacode, and a \(3\)-\((11, 5, 4)\) design in the shortened dodecacode [41].
\([11,6,5]_3\) Ternary Golay code The supports of the weight-five (weight-six) codewords of the (extended) ternary Golay code support the Steiner system \(S(4,5,11)\) (\(S(5,6,12)\)) [37,42][43; pg. 89]. Its blocks are called hexads.
\([23, 12, 7]\) Golay code The supports of the weight-seven codewords of the Golay code support the Steiner system \(S(4,7,23)\) [37,42][43; pg. 89]. Its blocks are called octads.
\([24, 12, 8]\) Extended Golay code The supports of the weight-eight codewords of the extended Golay code support the Steiner system \(S(5,6,12)\) [37,42][43; pg. 89]. Its blocks are called octads.
\([2^m,2^m-m-1,4]\) Extended Hamming code Weight-four codewords of the \([2^r,2^r-r-1, 4]\) extended Hamming code support the Steiner system \(S(3,4,2^r)\) [43; pg. 89].
\([2^m-1,m,2^{m-1}]\) simplex code Simplex codewords form a 2-design [6; pg. 166].
\([2^r-1,2^r-r-1,3]\) Hamming code Weight-three codewords of the \([2^r-1,2^r-r-1, 3]\) Hamming code support the Steiner system \(S(2,3,2^r-1)\) [43; pg. 89].
\([48,24,12]\) self-dual code Fixed-weight codewords of extremal self-dual doubly even codes whose length divides 24 form a combinatorial 5-design [12]. There are several designs associated with this code [44].
\([7,3,4]\) simplex code
\([7,4,3]\) Hamming code Weight-three and weight-four codewords of the \([7,4,3]\) Hamming code support combinatorial \(2\)-\((7,3,1)\) and \(2\)-\((7,4,2)\) designs, respectively [11; Exam. 5.2.5].
\(q\)-ary code Designs can be constructed from \(q\)-ary codes by taking the supports of a subset of codewords of constant weight.
\(q\)-ary code over \(\mathbb{Z}_q\) Optimal constant-weight codes over \(\mathbb{Z}_q\) can be constructed [7] from a generalization of combinatorial designs to \(q\)-ary alphabets [8,9].

References

[1]
S. J. Johnson and S. R. Weller, “Regular low-density parity-check codes from combinatorial designs”, Proceedings 2001 IEEE Information Theory Workshop (Cat. No.01EX494) 90 DOI
[2]
S. J. Johnson and S. R. Weller, “Construction of low-density parity-check codes from Kirkman triple systems”, GLOBECOM’01. IEEE Global Telecommunications Conference (Cat. No.01CH37270) 2, 970 DOI
[3]
S. J. Johnson and S. R. Weller, “Resolvable 2-designs for regular low-density parity-check codes”, IEEE Transactions on Communications 51, 1413 (2003) DOI
[4]
C. Ding and C. Tang, “Infinite families of near MDS codes holding \(t\)-designs”, (2019) arXiv:1910.08265
[5]
C. Tang and C. Ding, “An infinite family of linear codes supporting 4-designs”, (2020) arXiv:2001.00158
[6]
F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[7]
T. Etzion, “Optimal constant weight codes over Zk and generalized designs”, Discrete Mathematics 169, 55 (1997) DOI
[8]
H. Hanani, “On Some Tactical Configurations”, Canadian Journal of Mathematics 15, 702 (1963) DOI
[9]
S.-T. Xia and F.-W. Fu, “Undetected error probability of q-ary constant weight codes”, Designs, Codes and Cryptography 48, 125 (2007) DOI
[10]
C. Ding, C. Tang, and V. D. Tonchev, “The Projective General Linear Group \(\mathrm{PGL}_2(\mathrm{GF}(2^m))\) and Linear Codes of Length \(2^m+1\)”, (2020) arXiv:2010.09448
[11]
V. D. Tonchev, “Codes and designs.” Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[12]
E. F. Assmus Jr. and H. F. Mattson Jr., “New 5-designs”, Journal of Combinatorial Theory 6, 122 (1969) DOI
[13]
A. R. Calderbank, P. IDelsarte, and N. J. A. Sloane, “A strengthening of the Assmus-Mattson theorem”, IEEE Transactions on Information Theory 37, 1261 (1991) DOI
[14]
Y. Fujiwara, D. Clark, P. Vandendriessche, M. De Boeck, and V. D. Tonchev, “Entanglement-assisted quantum low-density parity-check codes”, Physical Review A 82, (2010) arXiv:1008.4747 DOI
[15]
P. A. H. Bours, “On the construction of perfect deletion-correcting codes using design theory”, Designs, Codes and Cryptography 6, 5 (1995) DOI
[16]
A. Mahmoodi, “Existence of Perfect 3-Deletion-Correcting Codes”, Designs, Codes and Cryptography 14, 81 (1998) DOI
[17]
T. A. Gulliver and M. Harada, “Extremal double circulant Type II codes over Z4 and construction of 5-(24, 10, 36) designs”, Discrete Mathematics 194, 129 (1999) DOI
[18]
M. Harada, “New 5-designs constructed from the lifted Golay code over ?4”, Journal of Combinatorial Designs 6, 225 (1998) DOI
[19]
A. Bonnecaze, E. Rains, and P. Solé, “3-Colored 5-Designs and Z4-Codes”, Journal of Statistical Planning and Inference 86, 349 (2000) DOI
[20]
D. J. C. MacKay and M. C. Davey, “Evaluation of Gallager Codes for Short Block Length and High Rate Applications”, The IMA Volumes in Mathematics and its Applications 113 (2001) DOI
[21]
Seberry, Jennifer; Yamada, Mieko (1992). Hadamard matrices, Sequences, and Block Designs. University of Wollongong. Journal contribution. https://hdl.handle.net/10779/uow.27846666.v1
[22]
J. A. Todd, “A Combinatorial Problem”, Journal of Mathematics and Physics 12, 321 (1933) DOI
[23]
C. J. Colbourn and J. H. Dinitz, editors , Handbook of Combinatorial Designs (Chapman and Hall/CRC, 2006) DOI
[24]
V. D. Tonchev, “Binary codes derived from the Hoffman-Singleton and Higman-Sims graphs”, IEEE Transactions on Information Theory 43, 1021 (1997) DOI
[25]
G. Alber, Th. Beth, Ch. Charnes, A. Delgado, M. Grassl, and M. Mussinger, “Detected-jump-error-correcting quantum codes, quantum error designs, and quantum computation”, Physical Review A 68, (2003) arXiv:quant-ph/0208140 DOI
[26]
T. Beth, C. Charnes, M. Grassl, G. Alber, A. Delgado, and M. Mussinger, Designs, Codes and Cryptography 29, 51 (2003) DOI
[27]
Y. Lin and M. Jimbo, “Extremal properties of t-SEEDs and recursive constructions”, Designs, Codes and Cryptography 73, 805 (2013) DOI
[28]
J. Conway and N. Sloane, “Lexicographic codes: Error-correcting codes from game theory”, IEEE Transactions on Information Theory 32, 337 (1986) DOI
[29]
W. J. Martin, Designs, Codes and Cryptography 16, 271 (1999) DOI
[30]
E. F. Assmus, Jr. and H. F. Mattson, Jr., “Coding and Combinatorics”, SIAM Review 16, 349 (1974) DOI
[31]
K. T. Phelps, “Combinatorial designs and perfect codes”, Electronic Notes in Discrete Mathematics 10, 220 (2001) DOI
[32]
D. Goyeneche, D. Alsina, J. I. Latorre, A. Riera, and K. Życzkowski, “Absolutely maximally entangled states, combinatorial designs, and multiunitary matrices”, Physical Review A 92, (2015) arXiv:1506.08857 DOI
[33]
D. Goyeneche, Z. Raissi, S. Di Martino, and K. Życzkowski, “Entanglement and quantum combinatorial designs”, Physical Review A 97, (2018) arXiv:1708.05946 DOI
[34]
Y. Zang, P. Facchi, and Z. Tian, “Quantum combinatorial designs and k-uniform states”, Journal of Physics A: Mathematical and Theoretical 54, 505204 (2021) arXiv:2111.04055 DOI
[35]
V. Pless, “The Weight of the Symmetry Code for p=29 and the 5‐Designs Contained Therein”, Annals of the New York Academy of Sciences 175, 310 (1970) DOI
[36]
V. Pless, “Symmetry codes over GF(3) and new five-designs”, Journal of Combinatorial Theory, Series A 12, 119 (1972) DOI
[37]
M. HUBER, “CODING THEORY AND ALGEBRAIC COMBINATORICS”, Series on Coding Theory and Cryptology 121 (2010) arXiv:0811.1254 DOI
[38]
M. Awada, “Infinite series of \(3\)-designs in the extended quadratic residue code”, (2024) arXiv:2310.14281
[39]
C. J. Colbourn, editor , CRC Handbook of Combinatorial Designs (CRC Press, 2010) DOI
[40]
A. R. Hammons Jr., P. V. Kumar, A. R. Calderbank, N. J. A. Sloane, and P. Solé, “The Z_4-Linearity of Kerdock, Preparata, Goethals and Related Codes”, (2002) arXiv:math/0207208
[41]
J. Kim and V. Pless, Designs, Codes and Cryptography 30, 187 (2003) DOI
[42]
L. J. Paige, “A Note on the Mathieu Groups”, Canadian Journal of Mathematics 9, 15 (1957) DOI
[43]
J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
[44]
M. Harada, A. Munemasa, and V. D. Tonchev, “A Characterization of Designs Related to an Extremal Doubly-Even Self-Dual Code of Length 48”, Annals of Combinatorics 9, 189 (2005) DOI