Combinatorial design code 

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

See [2] for more on combinatorial designs.

Parents

Cousins

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
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)

edit on this site

Zoo Code ID: combinatorial_design

Cite as:
“Combinatorial design code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/combinatorial_design
BibTeX:
@incollection{eczoo_combinatorial_design, title={Combinatorial design code}, booktitle={The Error Correction Zoo}, year={2023}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/combinatorial_design} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/combinatorial_design

Cite as:

“Combinatorial design code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/combinatorial_design

Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/bits/combinatorial_design.yml.