2
$\begingroup$

I am interested in codes with the following property. Given any codeword $x^n$ of a $(n,k,d)_2$ code passed through a binary symmetric channel $y^n = x^n + e^n$, if $|e^n| = d$, then $x^n+e^n \in C$. In other words, if we flip any $d$ bits of any codeword, we always get a new codeword.

My first guess was that only codes attaining the Singleton bound $d-1 \leq n-k$ could attain this property. But on the other hand, codes attaining the Hamming bound are said "to fill out the entire space" with spheres of radius $d$.

With that phrashing, it seems to me that flipping an $d$ bits of any codeword should result in a new codeword. But that's not true, is it? If not, is there some other class of codes with this property?

$\endgroup$
  • $\begingroup$ Looks like you are asking an awful lot. Start with a valid codeword $x$. Flip the first $d$ bits, you require that the resulting word $x'$ is another codeword. Flip the bits at positions $1,2,3,\ldots,d-1$ and $d+1$ you get yet another codeword $x''$. But $x'$ and $x''$ only differ from each other at positions $d$ and $d+1$. In other words, the minimum distance of your code is $\le 2$. Doesn't look like such codes would be very interesting. But, there are codes achieving the Hamming bound. Not too many, but some. Kodlu's answer has a comprehensice list. This was proved by Tietäväinen. $\endgroup$ – Jyrki Lahtonen Jul 1 '16 at 8:16
  • $\begingroup$ Aha! But that's exactly true for binary MDS codes! :) $\endgroup$ – Benjamin Lindqvist Jul 1 '16 at 8:17
3
$\begingroup$

Edit: Does this answer your question?

Let $n=2w$ be the length of the code. Consider the set $E=\{a: w_H(a)=w\}$ of all $n-$vectors of weight $w.$ These are the allowed error patterns, and $|E|=\binom{2w}{w}.$ Now let $$C=E \cup \{\mathbf{1},\mathbf{0}\}$$ where $\mathbf{1}$ is the all 1 vector of length $n$ and $\mathbf{0}$ is the all 0 vector of length $n$. Clearly, for all errors $e \in E$ (which are all errors of weight $w$) an errored codeword $c$ maps to another codeword $c'.$

Let the support of a vector $(x_1,\ldots,x_n)$ be the subset$S_x$ of $\{1,\ldots,n\}$ where, $$i\in S_x \Leftrightarrow x_i=1.$$ There are two special cases: if $e$ is the complement of $c$ then $c+e=\mathbf{1}$ and a if $e=c$ then $e+c=\mathbf{0}.$ In general, if the overlap in the supports of $c$ and $e$ is $t \in \{1,2,\ldots,w-1\},$ i.e., $|S_{c+e}\cap S_c|=t,$ and $c'=c+e$ we have that the size of the support of $c'$ is $$|S_{c+e}|=|S_{c}\setminus (S_c \cap S_e)|+|S_{e}\setminus (S_c \cap S_e)|+|=(w-t)+[n-w-(w-t)]=n-w$$ which equals $w$ when $n=2w$ as required.

End of Edit

If a binary code is perfect (with $d=2t+1$) then the $t-$spheres of radius $t$ around codewords fill the space, not those of radius $d.$

The only binary perfect codes are the repetition code of odd length, the Hamming code and the Golay Code, and these are the only possible parameters.

Consider the $[n,k,d]=[2^m-1,2^m-m-1,3]$ Hamming code, flipping any $d=3$ bits of the Hamming code would give you $\binom{2^m-1}{3}=\frac{(2^m-1)(2^m-2)(2^m-3)}{6}$ distinct vectors but some of those will have pairwise distance $1$ and $2$, surely they are not codewords in the Hamming code.

See wikipedia for more.

Another code with pairwise equal distances is the Simplex code which is a $[2^m-1,m, 2^{m-1}-1]$ code, closely related to the Hadamard code, but these codewords don't have that property either. It can only be that for some set of $d$ flips you get another codeword.

For the trivial repetition code with $d=n$ your property holds, of course.

Edit: So, the only binary MDS codes are

  1. the repetition codes $[n,1,n]$, thus with the two codewords of all zeroes and all ones. When $n$ is odd, these are perfect, and have your property. They achieve the Hamming bound with $t=0.$
  2. the universal code $[n,n,1]$ containing all vectors of length $n$ and have your property. For odd $n$, they achieve the Hamming bound with $t=(n-1)/2,$ but not for $n$ even.
  3. the even weight code $[n,n-1,2]$ made up of codewords of even weight only. These have your property. These don't achieve the Hamming bound.
$\endgroup$
  • $\begingroup$ Good answer, but I can't accept since it does not address which codes have the property. I suspect we require the code to be MDS, but I'll leave it up until I have an answer $\endgroup$ – Benjamin Lindqvist Jun 4 '16 at 20:15
  • $\begingroup$ So the MDS property is sufficient, but we haven't established that it's necessary. $\endgroup$ – Benjamin Lindqvist Jun 30 '16 at 16:07
  • $\begingroup$ I'm going to attempt it tomorrow, will post if I find it $\endgroup$ – Benjamin Lindqvist Jun 30 '16 at 16:08
  • $\begingroup$ @BenjaminLindqvist, does my newest edit address your question? $\endgroup$ – kodlu Jul 4 '16 at 0:50

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.