Also known as 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,5]. Existence of certain quasi-symmetric designs has also been established [6].
Notes
Parents
- 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 [13; Thm. 6.7].
- Constant-weight code
- Subspace design — Combinatorial designs are designs on a space of fixed-weight binary strings (a.k.a. Johnson association scheme) [14,15]. Subspace designs reduce to combinatorial designs for \(q=2\).
Cousins
- \(q\)-ary code — Designs can be constructed from \(q\)-ary codes by taking the supports of a subset of codewords of constant weight.
- Cyclic linear \(q\)-ary code — The supports of all fixed-weight codewords of a \(q\)-ary cyclic code support a combinatorial \(1\)-design [8; Corr. 5.2.4].
- Reed-Muller (RM) code — Fixed-weight RM codewords of weight less than \(2^m\) support combinatorial 3-designs [8; Ex. 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 [8; Ex. 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].
- \(q\)-ary quadratic-residue (QR) code — The supports of fixed-weight codewords of certain \(q\)-ary QR codes support combinatorial designs [9,17,18].
- Pless symmetry code — The supports of fixed-weight codewords of certain Pless symmetry codes support combinatorial designs [9,19,20].
- Golay code — The supports of the weight-seven (weight-eight) codewords of the (extended) Golay code support the Steiner system \(S(4,7,23)\) (\(S(5,6,12)\)) [9,21][16; pg. 89]. Its blocks are called octads.
- 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)\)) [9,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 [8; Sec. 5.4]).
- Self-dual linear code — Self-dual extremal codes yield combinatorial \(\leq 5\)-designs using the Assmus-Mattson theorem [18] (see [8; 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. [10].
- 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 [13; pg. 471].
- Nordstrom-Robinson (NR) code — NR codewords give \(3\)-\((16, 6, 4)\), \(3\)-\((16, 8, 3)\), and \(3\)-\((16, 10, 24)\) designs [13; pg. 164].
- Mixed code — Combinatorial designs have been generalized to mixed alphabets [34].
- Editing code — Perfect deletion correcting codes can be constructed using combinatorial design theory [35,36].
- Dodecacode — There exists a \(5\)-\((12, 6, 3)\) design in the dodecacode, and a \(3\)-\((11, 5, 4)\) design in the shortened dodecacode [37].
- Cyclic linear \(q\)-ary code — Two families of cyclic \(q\)-ary codes support an infinite family of combinatorial 3-designs [38].
- Lexicographic code — Some lexicodes yield Steiner systems [39].
- Perfect-tensor code — Combinatorial designs and \(d\)-uniform quantum states are related [40].
- EA combinatorial-design QLDPC code — Combinatorial designs can be used to construct EA QLDPC codes [41].
- Jump code — Certain types of combinatorial designs can be used to obtain jump codes [42–44].
References
- [1]
- E. Witt, “Über Steinersche Systeme”, Collected Papers - Gesammelte Abhandlungen 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”, (2019) arXiv:1401.3665
- [5]
- L. Teirlinck, “Non-trivial t-designs without repeated blocks exist for all t”, Discrete Mathematics 65, 301 (1987) DOI
- [6]
- G. McGuire, “Quasi-Symmetric Designs and Codes Meeting the Grey–Rankin Bound”, Journal of Combinatorial Theory, Series A 78, 280 (1997) DOI
- [7]
- W. de Launey and D. Flannery, Algebraic Design Theory (American Mathematical Society, 2011) DOI
- [8]
- V. D. Tonchev, "Codes and designs." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [9]
- M. HUBER, “CODING THEORY AND ALGEBRAIC COMBINATORICS”, Selected Topics in Information and Coding Theory 121 (2010) arXiv:0811.1254 DOI
- [10]
- C. J. Colbourn and J. H. Dinitz, editors , Handbook of Combinatorial Designs (Chapman and Hall/CRC, 2006) DOI
- [11]
- P. J. Cameron and J. H. van Lint, Designs, Graphs, Codes and Their Links (Cambridge University Press, 1991) DOI
- [12]
- Combinatorial Designs (Springer-Verlag, 2004) DOI
- [13]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [14]
- Delsarte, Philippe. "An algebraic approach to the association schemes of coding theory." Philips Res. Rep. Suppl. 10 (1973): vi+-97.
- [15]
- 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.
- [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”, Codes, Systems, and Graphical Models 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) 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) 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]
- W. J. Martin, Designs, Codes and Cryptography 16, 271 (1999) DOI
- [35]
- P. A. H. Bours, “On the construction of perfect deletion-correcting codes using design theory”, Designs, Codes and Cryptography 6, 5 (1995) DOI
- [36]
- A. Mahmoodi, Designs, Codes and Cryptography 14, 81 (1998) DOI
- [37]
- J. Kim and V. Pless, Designs, Codes and Cryptography 30, 187 (2003) DOI
- [38]
- 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
- [39]
- J. Conway and N. Sloane, “Lexicographic codes: Error-correcting codes from game theory”, IEEE Transactions on Information Theory 32, 337 (1986) DOI
- [40]
- D. Goyeneche et al., “Absolutely maximally entangled states, combinatorial designs, and multiunitary matrices”, Physical Review A 92, (2015) arXiv:1506.08857 DOI
- [41]
- Y. Fujiwara et al., “Entanglement-assisted quantum low-density parity-check codes”, Physical Review A 82, (2010) arXiv:1008.4747 DOI
- [42]
- G. Alber et al., “Detected-jump-error-correcting quantum codes, quantum error designs, and quantum computation”, Physical Review A 68, (2003) arXiv:quant-ph/0208140 DOI
- [43]
- T. Beth et al., Designs, Codes and Cryptography 29, 51 (2003) DOI
- [44]
- Y. Lin and M. Jimbo, “Extremal properties of t-SEEDs and recursive constructions”, Designs, Codes and Cryptography 73, 805 (2013) DOI
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