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 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

See [2] for a review combinatorial designs.See [35] for books 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]
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

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

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/edit/main/codes/classical/bits/combinatorial_design.yml.