3
$\begingroup$

Hi all, I have been interested in La Jolla covering tables lately and I was wondering if there is some theory around sets where the same element is allowed to be present more than once. For example the following block would be considered valid: {1, 1, 1, 2, 3}. Basically given an alphabet {A, B, C, D} and given a word length (k), find the minimum set of words which cover the whole language with a max of N "letter replacements". For example, if the alphabet is binary {0,1} and word length is 3, a set covering "-1" would be { 000, 111} since all other words differ for at most by one char.

P.S. I would also be interested in the algorithms used to generate the tables itself, by I cannot find pointers. Thanks

$\endgroup$
1
  • $\begingroup$ It sounds like you want to look at coding theory, although that is usually concerned with packing instead of covering. $\endgroup$ Nov 24, 2011 at 0:01

1 Answer 1

3
$\begingroup$

The concept you are referring to is a covering code. These have been extensively studied and a great reference would be the book "Covering Codes" by G. Cohen, I. Honkala, S. Litsyn, and A. Lobstein. (On a side note, the repetition code you give as an example is both a packing and a covering, i.e., a tiling, or perfect code.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.