2
$\begingroup$

We are considering length n strings over the alphabet S.

The goal is to compute a set of string, M, such that for any string, x, in S^n there exists a string, y, in M such that the hamming distance between x and y is at least r.

A way of thinking of this is that we want to guarantee that for any string, we have a string in our solution M which is far away from the given string.

For a given S (with size at least 3), n and r (which may be a funciton of n, for example n/2) for many strings a needed to include in M to guarantee that for any string in S^n, we have a string in M which has a hamming distance to it of at least r.

I have a feeling this is well studied and might be related to covering designs. Can someone give me a good reference (or insight)? I would be very grateful.

$\endgroup$
  • $\begingroup$ Hmm... do you want to minimize set M? Actually, in your example you need only two strings $aa \cdots a$ and $bb \cdots b$ to get n/2 distance. $\endgroup$ – Vsevolod Oparin May 11 '15 at 21:50
  • $\begingroup$ Yes I want to minimize the size of M. You are right, for n/2 distance you only need two, but what about other (bigger distances)? You may assume that the size of the alphabet is a constant. $\endgroup$ – user32149 May 12 '15 at 10:27
  • $\begingroup$ does the answer below go some way towards what you want? $\endgroup$ – kodlu Jun 24 '15 at 11:07
  • $\begingroup$ yes, thanks. Anticodes was the magic word I was looking for. $\endgroup$ – user32149 Jul 2 '15 at 9:08
2
$\begingroup$

Look up the concept of anticodes. Some bounds exist.

Also if you have a linear $t-$error correcting code over $GF(q)$ with length $n$ and covering radius $r$ and use homogeneity under translations by adding vectors $n-d=n-2t-1$ would seem to be your answer but I haven't checked carefully. Cohen and Litsyn have a book on covering codes.

A Simple Construction

Fix $k\geq 1$ and let $v=\lceil n/k \rceil$ and consider the strings as $GF(q)^n.$ Generate all $k-$tuples over $GF(q)$ to obtain $M=q^k$ codewords. Map these codewords to $GF(q)^n$ by expanding by $v$ for the first $k-1$ coordinates and expanding by $n-(k-1)v$ for the last coordinate. For example, let $q=3,$ $n=5$ and $k=2.$ Your codewords are $$ \begin{array}{cc} 0&0\\ 0&1\\ 0&2\\ 1&0\\ 1&1\\ 1&2\\ 2&0\\ 2&1\\ 2&2\\ \end{array} $$

which become upon expansion with $v=4$

$$ \begin{array}{c} 0000~000\\ 0000~111\\ 0000~222\\ 1111~000\\ 1111~111\\ 1111~222\\ 2222~000\\ 2222~111\\ 2222~222\\ \end{array} $$ Now, for any possible vector in $GF(3)^7$ there is a codeword which is quite far from it. Namely, if there are fewer than 2 symbols for that vector in a block, there is a codeword which is at Hamming distance $v$ from it. If all 3 symbols occur, there is a codeword at Hamming distance $\geq \lfloor 2v/3 \rfloor$ from it. Since all possible constant blocks occur, for any possible vector in $GF(3)^7$ there is a codeword in this code of only $M=9$ codewords which is at Hamming distance $\geq k \lfloor (q-1)v/q \rfloor \approx n(1-\frac{1}{q}).$ Choosing $v$ a multiple of $q$ will make this more efficient.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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