Here is a list of codes related to combinatorial designs.

Code | Relation |
---|---|

Algebraic LDPC code | Combinatorial designs can be used to construct explicit LDPC codes [1–3]. |

Combinatorial design | |

Cyclic linear \(q\)-ary code | The supports of all fixed-weight codewords of a \(q\)-ary cyclic code support a combinatorial \(1\)-design [4; Corr. 5.2.4]. |

Dodecacode | There exists a \(5\)-\((12, 6, 3)\) design in the dodecacode, and a \(3\)-\((11, 5, 4)\) design in the shortened dodecacode [5]. |

Dual linear code | Linear codes and their duals are related to combinatorial designs via the Assmus-Mattson theorem [6,7] (see [4; Sec. 5.4]). |

EA combinatorial-design QLDPC code | Combinatorial designs can be used to construct EA QLDPC codes [8]. |

Editing code | Perfect deletion correcting codes can be constructed using combinatorial design theory [9,10]. |

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)\) [11; pg. 89]. |

Gallager (GL) code | Some Steiner systems can be used to construct Gallager codes [12]. |

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

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)\)) [13,14][11; pg. 89]. Its blocks are called octads. |

Hadamard code | Hadamard designs form a set of combinatorial designs that are equivalent to Hadamard matrices [15]; see Ref. [16]. |

Higman-Sims graph-adjacency code | Codewords of weight 36 of the Higman-Sims graph-adjacency code form a \(2\)-\((100,36,525)\) design [17; 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 [17; Prop. 1.1]. |

Jump code | Certain types of combinatorial designs can be used to obtain jump codes [18–20]. |

Mixed code | Combinatorial designs have been generalized to mixed alphabets [21]. |

Nordstrom-Robinson (NR) code | NR codewords give \(3\)-\((16, 6, 4)\), \(3\)-\((16, 8, 3)\), and \(3\)-\((16, 10, 24)\) designs [22; pg. 164]. |

Perfect code | Perfect codes and combinatorial designs are related [23,24]. |

Perfect-tensor code | Combinatorial designs and \(d\)-uniform quantum states are related [25]. |

Pless symmetry code | The supports of fixed-weight codewords of certain Pless symmetry codes support combinatorial designs [14,26,27]. |

Preparata code | Preparata codewords of each weight form a 3-design [22; pg. 471]. |

Reed-Muller (RM) code | Fixed-weight RM codewords of weight less than \(2^m\) support combinatorial 3-designs [4; Ex. 5.2.7]. |

Self-dual linear code | Self-dual extremal codes yield combinatorial \(\leq 5\)-designs using the Assmus-Mattson theorem [6] (see [4; Sec. 5.4]). See [28; Table 1.61, pg. 683] for a table of combinatorial designs obtained from self-dual codes. |

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)\)) [13,14][11; pg. 89]. Its blocks are called hexads. |

\([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)\) [11; pg. 89]. |

\([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 [6]. |

\([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 [4; Ex. 5.2.5]. |

\(q\)-ary quadratic-residue (QR) code | The supports of fixed-weight codewords of certain \(q\)-ary QR codes support combinatorial designs [6,14,23]. |

## References

- [1]
- 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
- [2]
- 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
- [3]
- 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
- [4]
- V. D. Tonchev, "Codes and designs." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [5]
- J. Kim and V. Pless, Designs, Codes and Cryptography 30, 187 (2003) DOI
- [6]
- E. F. Assmus Jr. and H. F. Mattson Jr., “New 5-designs”, Journal of Combinatorial Theory 6, 122 (1969) DOI
- [7]
- 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
- [8]
- Y. Fujiwara et al., “Entanglement-assisted quantum low-density parity-check codes”, Physical Review A 82, (2010) arXiv:1008.4747 DOI
- [9]
- P. A. H. Bours, “On the construction of perfect deletion-correcting codes using design theory”, Designs, Codes and Cryptography 6, 5 (1995) DOI
- [10]
- A. Mahmoodi, Designs, Codes and Cryptography 14, 81 (1998) DOI
- [11]
- J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups (Springer New York, 1999) DOI
- [12]
- 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
- [13]
- L. J. Paige, “A Note on the Mathieu Groups”, Canadian Journal of Mathematics 9, 15 (1957) DOI
- [14]
- M. HUBER, “CODING THEORY AND ALGEBRAIC COMBINATORICS”, Selected Topics in Information and Coding Theory 121 (2010) arXiv:0811.1254 DOI
- [15]
- J. A. Todd, “A Combinatorial Problem”, Journal of Mathematics and Physics 12, 321 (1933) DOI
- [16]
- C. J. Colbourn and J. H. Dinitz, editors , Handbook of Combinatorial Designs (Chapman and Hall/CRC, 2006) DOI
- [17]
- V. D. Tonchev, “Binary codes derived from the Hoffman-Singleton and Higman-Sims graphs”, IEEE Transactions on Information Theory 43, 1021 (1997) DOI
- [18]
- 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
- [19]
- T. Beth et al., Designs, Codes and Cryptography 29, 51 (2003) DOI
- [20]
- Y. Lin and M. Jimbo, “Extremal properties of t-SEEDs and recursive constructions”, Designs, Codes and Cryptography 73, 805 (2013) DOI
- [21]
- W. J. Martin, Designs, Codes and Cryptography 16, 271 (1999) DOI
- [22]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [23]
- E. F. Assmus, Jr. and H. F. Mattson, Jr., “Coding and Combinatorics”, SIAM Review 16, 349 (1974) DOI
- [24]
- K. T. Phelps, “Combinatorial designs and perfect codes”, Electronic Notes in Discrete Mathematics 10, 220 (2001) DOI
- [25]
- D. Goyeneche et al., “Absolutely maximally entangled states, combinatorial designs, and multiunitary matrices”, Physical Review A 92, (2015) arXiv:1506.08857 DOI
- [26]
- 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
- [27]
- V. Pless, “Symmetry codes over GF(3) and new five-designs”, Journal of Combinatorial Theory, Series A 12, 119 (1972) DOI
- [28]
- C. J. Colbourn, editor , CRC Handbook of Combinatorial Designs (CRC Press, 2010) DOI