Codes attaining the Hamming bound

Question

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?

Answer 1

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.