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.
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\) [1].
Notes
Parents
Cousins
- Galois-field \(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 [2; Corr. 5.2.4].
- Reed-Muller (RM) code — Fixed-weight RM codewords of weight less than \(2^m\) support combinatorial 3-designs [2; 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 [2; Ex. 5.2.5].
- 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)\) [6; pg. 89].
- 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)\) [6; pg. 89].
- 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)\)) [6; 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)\)) [6; pg. 89]. Its blocks are called hexads.
- Perfect code — Perfect codes and combinatorial designs are related [7].
- Dual linear code — Linear codes and their duals are related to combinatorial designs via the Assmus-Mattson theorem [8] (see [2; Sec. 5.4]).
- Self-dual linear code — Self-dual extremal codes yield combinatorial \(\leq 5\)-designs using the Assmus-Mattson theorem [8] (see [2; Sec. 5.4]). See [9; 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 [10].
- Algebraic LDPC code — Combinatorial designs can be used to construct explicit LDPC codes [11–13].
- \([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 [8].
- Hoffman-Sims graph-adjacency code — Codewords of weight 36 of the Hoffman-Sims graph-adjacency code form a \(2\)-\((100,36,525)\) design [14; 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 [14; Prop. 1.1].
- Preparata code — Preparata codewords of each weight form a 3-design [15; pg. 471].
- Nordstrom-Robinson (NR) code — NR codewords give \(3\)-\((16, 6, 4)\), \(3\)-\((16, 8, 3)\), and \(3\)-\((16, 10, 24)\) designs [15; pg. 164].
- Mixed code — Combinatorial designs have been generalized to mixed alphabets [16].
- Dodecacode — There exists a \(5\)-\((12, 6, 3)\) design in the dodecacode, and a \(3\)-\((11, 5, 4)\) design in the shortened dodecacode [17].
- Spherical design code
References
- [1]
- L. Teirlinck, “Non-trivial t-designs without repeated blocks exist for all t”, Discrete Mathematics 65, 301 (1987) DOI
- [2]
- V. D. Tonchev, "Codes and designs." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [3]
- T. Beth, D. Jungnickel, and H. Lenz, Design Theory (Cambridge University Press, 1999) DOI
- [4]
- C. J. Colbourn and J. H. Dinitz, editors , Handbook of Combinatorial Designs (Chapman and Hall/CRC, 2006) DOI
- [5]
- P. J. Cameron and J. H. van Lint, Designs, Graphs, Codes and Their Links (Cambridge University Press, 1991) DOI
- [6]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [7]
- E. F. Assmus, Jr. and H. F. Mattson, Jr., “Coding and Combinatorics”, SIAM Review 16, 349 (1974) DOI
- [8]
- E. F. Assmus Jr. and H. F. Mattson Jr., “New 5-designs”, Journal of Combinatorial Theory 6, 122 (1969) DOI
- [9]
- C. J. Colbourn, editor , CRC Handbook of Combinatorial Designs (CRC Press, 2010) DOI
- [10]
- 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
- [11]
- 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
- [12]
- 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
- [13]
- 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
- [14]
- V. D. Tonchev, “Binary codes derived from the Hoffman-Singleton and Higman-Sims graphs”, IEEE Transactions on Information Theory 43, 1021 (1997) DOI
- [15]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [16]
- W. J. Martin, Designs, Codes and Cryptography 16, 271 (1999) DOI
- [17]
- J. Kim and V. Pless, Designs, Codes and Cryptography 30, 187 (2003) DOI
Page edit log
- Victor V. Albert (2023-04-24) — most recent
Cite as:
“Combinatorial design code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/combinatorial_design