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 \(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)\) [3; 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)\) [3; 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)\)) [3; 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)\)) [3; pg. 89]. Its blocks are called hexads.
- Perfect code — Perfect codes and combinatorial designs are related [4].
- Dual linear code — Linear codes and their duals are related to combinatorial designs via the Assmus-Mattson theorem [5] (see [2; Sec. 5.4]).
- Self-dual linear code — Self-dual extremal codes yield combinatorial \(\leq 5\)-designs using the Assmus-Mattson theorem [5] (see [2; Sec. 5.4]). See [6; 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 [7].
- Algebraic LDPC code — Combinatorial designs can be used to construct explicit LDPC codes [8–10].
- Dodecacode — There exists a \(5-(12, 6, 3)\) design in the dodecacode, and a \(3-(11, 5, 4)\) design in the shortened dodecacode [11].
- 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]
- 10.1007/978-1-4757-6568-7
- [4]
- E. F. Assmus, Jr. and H. F. Mattson, Jr., “Coding and Combinatorics”, SIAM Review 16, 349 (1974) DOI
- [5]
- E. F. Assmus Jr. and H. F. Mattson Jr., “New 5-designs”, Journal of Combinatorial Theory 6, 122 (1969) DOI
- [6]
- C. J. Colbourn, editor , CRC Handbook of Combinatorial Designs (CRC Press, 2010) DOI
- [7]
- 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
- [8]
- 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
- [9]
- 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
- [10]
- 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
- [11]
- 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