Alternative names: Block design, Covering design.
Description
A constant-weight binary code that is mapped into a combinatorial \(t\)-design.
The mapping proceeds as follows for a length-\(n\) code with codewords of constant weight \(w\). A codeword \(c\) corresponds to a block of the design, with the codeword's \(j\)th coordinate labeling whether or not element \(j\) is contained in the block. There are a total of \(n\) elements, and the constant weight of the code implies that each block contains a fixed number \(w\) of elements. The code supports an \(S(t,w,n)\) Steiner system if each subset of \(t\leq w\) elements is contained in exactly one block. More generally, the code supports a combinatorial \(t\)-design, or, more precisely, a \(t\)-\((n,w,\lambda)\)-design, if each such \(t\)-subset is contained in exactly \(\lambda \geq 1\) blocks. A combinatorial 2-design with two block intersection sizes is called a quasi-symmetric design. A \(3\)-\((q^d+1,q+1,1)\) combinatorial design is sometimes called a Witt design (a.k.a. a spherical geometry design) [1,3][2; Remark 6.10].
For example, the eight codewords of weight \(w=3\) of the \([7,4,3]\) Hamming code support a \(2\)-\((7,3,1)\)-design a.k.a. an \(S(2,3,7)\) Steiner system. The codeword \(1000110\) corresponds to a block containing elements 1, 5, and 6. Similarly, the other seven codewords correspond to blocks 257, 367, 147, 246, 345, and 123. Each pair of elements is contained in exactly one block.
Combinatorial \(t\)-designs exist for all \(t\) [4–8]. Existence of certain quasi-symmetric designs has also been established [9].
Notes
See [10–12] for reviews on combinatorial designs.See [2,13–15] for books on combinatorial designs.Cousins
- \(q\)-ary code— Designs can be constructed from \(q\)-ary codes by taking the supports of a subset of codewords of constant weight.
- Reed-Muller (RM) code— Fixed-weight RM codewords of weight less than \(2^m\) support combinatorial 3-designs [11; Exam. 5.2.7].
- \([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].
- \([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)\) [16; pg. 89].
- \([2^r,2^r-r-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)\) [16; pg. 89].
- Quadratic-residue (QR) code— The supports of fixed-weight codewords of certain \(q\)-ary QR codes support combinatorial designs [12,17,18].
- Pless symmetry code— The supports of fixed-weight codewords of certain Pless symmetry codes support combinatorial designs [12,19,20].
- \([23, 12, 7]\) Golay code— The supports of the weight-seven codewords of the Golay code support the Steiner system \(S(4,7,23)\) [12,21][16; 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)\) [12,21][16; pg. 89]. Its blocks are called octads.
- \([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)\)) [12,21][16; pg. 89]. Its blocks are called hexads.
- Perfect code— Perfect codes and combinatorial designs are related [17,22].
- Dual linear code— Linear codes and their duals are related to combinatorial designs via the Assmus-Mattson theorem [18,23] (see [11; Sec. 5.4]).
- Self-dual linear code— Self-dual extremal codes yield combinatorial \(\leq 5\)-designs using the Assmus-Mattson theorem [18] (see [11; Sec. 5.4]). See [24; Table 1.61, pg. 683] for a table of combinatorial designs obtained from self-dual codes.
- Gallager (GL) code— Some Steiner systems can be used to construct Gallager codes [25].
- Algebraic LDPC code— Combinatorial designs can be used to construct explicit LDPC codes [26–28].
- Hadamard code— Hadamard designs are combinatorial designs constructed from Hadamard matrices [29]; see Ref. [13].
- Binary BCH code— A family of BCH codes supports an infinite family of combinatorial 4-designs [30,31].
- \([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 [18]. There are several designs associated with this code [32].
- Higman-Sims graph-adjacency code— Codewords of weight 36 of the Higman-Sims graph-adjacency code form a \(2\)-\((100,36,525)\) design [33; 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 [33; Prop. 1.1].
- Preparata code— Preparata codewords of each weight form a 3-design [34; pg. 471].
- Nordstrom-Robinson (NR) code— NR codewords give \(3\)-\((16, 6, 4)\), \(3\)-\((16, 8, 3)\), and \(3\)-\((16, 10, 24)\) designs [34; pg. 164].
- Mixed code— Combinatorial designs have been generalized to mixed alphabets [35].
- Editing code— Perfect deletion correcting codes can be constructed using combinatorial design theory [36,37].
- \((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 [38].
- Cyclic linear \(q\)-ary code— Two families of cyclic \(q\)-ary codes support an infinite family of combinatorial 3-designs [39]. The supports of all fixed-weight codewords of a \(q\)-ary cyclic code support a combinatorial \(1\)-design [11; Corr. 5.2.4].
- Lexicographic code— Some lexicodes yield Steiner systems [40].
- 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 [41].
- Pseudo Golay code— Supports of codewords of any fixed symmetrized type of pseudo Golay codes form a 5-design [42–44].
- Extended quaternary Golay code— Supports of codewords of any fixed symmetrized type of the extended quaternary Golay code form a 5-design [42–44].
- Perfect-tensor code— Combinatorial designs and \(d\)-uniform quantum states are related [45–47].
- EA combinatorial-design QLDPC code— Combinatorial designs can be used to construct EA QLDPC codes [48].
- Jump code— Certain types of combinatorial designs can be used to obtain jump codes [49–51].
Primary Hierarchy
Parents
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 [34; Thm. 6.7].
Combinatorial design
References
- [1]
- E. Witt, “Über Steinersche Systeme”, Springer Collected Works in Mathematics 288 (1998) DOI
- [2]
- T. Beth, D. Jungnickel, and H. Lenz, Design Theory (Cambridge University Press, 1999) DOI
- [3]
- J. D. Key and A. Wagner, “On an infinite class of Steiner systems constructed from affine spaces”, Archiv der Mathematik 47, 376 (1986) DOI
- [4]
- P. Keevash, “The existence of designs”, (2024) arXiv:1401.3665
- [5]
- L. Teirlinck, “Non-trivial t-designs without repeated blocks exist for all t”, Discrete Mathematics 65, 301 (1987) DOI
- [6]
- S. Glock, D. Kühn, A. Lo, and D. Osthus, “The existence of designs via iterative absorption: hypergraph \(F\)-designs for arbitrary \(F\)”, (2020) arXiv:1611.06827
- [7]
- P. Keevash, “The existence of designs II”, (2018) arXiv:1802.05900
- [8]
- P. Keevash, “A short proof of the existence of designs”, (2024) arXiv:2411.18291
- [9]
- G. McGuire, “Quasi-Symmetric Designs and Codes Meeting the Grey–Rankin Bound”, Journal of Combinatorial Theory, Series A 78, 280 (1997) DOI
- [10]
- W. de Launey and D. Flannery, Algebraic Design Theory (American Mathematical Society, 2011) DOI
- [11]
- V. D. Tonchev, "Codes and designs." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [12]
- M. HUBER, “CODING THEORY AND ALGEBRAIC COMBINATORICS”, Series on Coding Theory and Cryptology 121 (2010) arXiv:0811.1254 DOI
- [13]
- C. J. Colbourn and J. H. Dinitz, editors , Handbook of Combinatorial Designs (Chapman and Hall/CRC, 2006) DOI
- [14]
- P. J. Cameron and J. H. van Lint, Designs, Graphs, Codes and Their Links (Cambridge University Press, 1991) DOI
- [15]
- Combinatorial Designs (Springer-Verlag, 2004) DOI
- [16]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [17]
- E. F. Assmus, Jr. and H. F. Mattson, Jr., “Coding and Combinatorics”, SIAM Review 16, 349 (1974) DOI
- [18]
- E. F. Assmus Jr. and H. F. Mattson Jr., “New 5-designs”, Journal of Combinatorial Theory 6, 122 (1969) DOI
- [19]
- 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
- [20]
- V. Pless, “Symmetry codes over GF(3) and new five-designs”, Journal of Combinatorial Theory, Series A 12, 119 (1972) DOI
- [21]
- L. J. Paige, “A Note on the Mathieu Groups”, Canadian Journal of Mathematics 9, 15 (1957) DOI
- [22]
- K. T. Phelps, “Combinatorial designs and perfect codes”, Electronic Notes in Discrete Mathematics 10, 220 (2001) DOI
- [23]
- 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
- [24]
- C. J. Colbourn, editor , CRC Handbook of Combinatorial Designs (CRC Press, 2010) DOI
- [25]
- 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
- [26]
- 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
- [27]
- 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
- [28]
- 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
- [29]
- J. A. Todd, “A Combinatorial Problem”, Journal of Mathematics and Physics 12, 321 (1933) DOI
- [30]
- C. Ding and C. Tang, “Infinite families of near MDS codes holding \(t\)-designs”, (2019) arXiv:1910.08265
- [31]
- C. Tang and C. Ding, “An infinite family of linear codes supporting 4-designs”, (2020) arXiv:2001.00158
- [32]
- 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
- [33]
- V. D. Tonchev, “Binary codes derived from the Hoffman-Singleton and Higman-Sims graphs”, IEEE Transactions on Information Theory 43, 1021 (1997) DOI
- [34]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [35]
- W. J. Martin, Designs, Codes and Cryptography 16, 271 (1999) DOI
- [36]
- P. A. H. Bours, “On the construction of perfect deletion-correcting codes using design theory”, Designs, Codes and Cryptography 6, 5 (1995) DOI
- [37]
- A. Mahmoodi, “Existence of Perfect 3-Deletion-Correcting Codes”, Designs, Codes and Cryptography 14, 81 (1998) DOI
- [38]
- J. Kim and V. Pless, Designs, Codes and Cryptography 30, 187 (2003) DOI
- [39]
- 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
- [40]
- J. Conway and N. Sloane, “Lexicographic codes: Error-correcting codes from game theory”, IEEE Transactions on Information Theory 32, 337 (1986) DOI
- [41]
- 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
- [42]
- 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
- [43]
- M. Harada, “New 5-designs constructed from the lifted Golay code over ?4”, Journal of Combinatorial Designs 6, 225 (1998) DOI
- [44]
- A. Bonnecaze, E. Rains, and P. Solé, “3-Colored 5-Designs and Z4-Codes”, Journal of Statistical Planning and Inference 86, 349 (2000) DOI
- [45]
- 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
- [46]
- D. Goyeneche, Z. Raissi, S. Di Martino, and K. Życzkowski, “Entanglement and quantum combinatorial designs”, Physical Review A 97, (2018) arXiv:1708.05946 DOI
- [47]
- 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
- [48]
- 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
- [49]
- 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
- [50]
- T. Beth, C. Charnes, M. Grassl, G. Alber, A. Delgado, and M. Mussinger, Designs, Codes and Cryptography 29, 51 (2003) DOI
- [51]
- Y. Lin and M. Jimbo, “Extremal properties of t-SEEDs and recursive constructions”, Designs, Codes and Cryptography 73, 805 (2013) DOI
- [52]
- Delsarte, Philippe. "An algebraic approach to the association schemes of coding theory." Philips Res. Rep. Suppl. 10 (1973): vi+-97.
- [53]
- V. I. Levenshtein, “Universal bounds for codes and designs,” in Handbook of Coding Theory 1, eds. V. S. Pless and W. C. Huffman. Amsterdam: Elsevier, 1998, pp.499-648.
Page edit log
- Victor V. Albert (2023-04-24) — most recent
Cite as:
“Combinatorial design”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/combinatorial_design