A different criterion for equivalence of codes?

Question

I've been thinking about equivalence of codes (two codes that are equal up to order of positions of the letters, or permutations of the letters in a fixed position).

It is obvious that if we have two codes with the same distance $d$, it doesn't mean they are equivalence; nor if they have the same set of distances.

However, I thought about listing the distances and counting them, that is, make a list of the type "there are $n_1$ pairs of words in the code with distance $1$, $n_2$ pairs of words that differ only in two positions, $n_3 \ldots$"

It is not difficult to see that this criterion does not imply equivalence if we talk about ternary codes; but what if we take binary codes? I have a gut feeling it's wrong too, but can't think of a counter example.

Answer 1

In the case of linear codes, this is the same as asking for non-equivalent codes with the same weight enumerator. There are many examples known. Search for "same weight enumerator" at google scholar and you'll find some examples quickly.

For example, this paper and this one and this one and this one.

Answer 2

• An example of two $(n,M)$ codes that have the same distance enumerator, but not necessarily the same weight enumerator is any two cosets of a $[n,\log_2(M)]$ linear code. Thus, the $(2,2)$ codes with codewords $\{00, 11\}$ and $\{01,10\}$ respectively have the same distance enumerator but not the same weight enumerator. Obviously the codes cannot be equivalent under a permutation of coordinates.

• An example of two codes with the same weight enumerator but different distance enumerators is the pair of $(3,3)$ codes with codewords $\{110, 100, 010\}$ and $\{110, 100, 001\}$ respectively. Both have weight enumerator $2z+z^2$ but the codes are not equivalent under permutation of coordinates.

• An example of inequivalent linear codes with identical weight enumerators (and thus identical distance enumerators) is the $[32,16]$ 2nd-order Reed-Muller (RM) code and the $[32,16]$ extended quadratic residue (QR) code. These codes are not equivalent under permutation of coordinates. The RM code has $155$ cosets that have $8$ coset leaders of weight $4$ while the QR code has no such cosets. In fact, cosets of the QR code that have coset leaders of weight $4$ have at most $5$ such coset leaders. The details are in Chapter 8 of my unpublished Ph.D. thesis "Weight Enumerators of Reed-Muller Codes and Cosets" Princeton University, 1973.

Answer 3

Here are two inequivalent binary codes with the same distance enumerator. Code A consists of the codewords $a=00000000000$, $b=11110000000$, $c=11111111100$, $d=11000110011$; code R consists of the codewords $r=0000000000$, $s=1111000000$, $t=0111111111$, $u=1000111100$. Writing $xy$ for the Hamming distance between words $x$ and $y$, we have $ab=rs=4$, $bc=ru=5$, $cd=tu=6$, $ac=rt=9$, and $ad=bd=st=su=7$, so the distance enumerators are identical. But code A has the 7-7-4 triangle $adb$, while code R has the 7-7-6 triangle $tsu$, so there is no distance-preserving bijection between the two codes.

I'm sure there are shorter examples.

EDIT: a much shorter example: Code A consists of the codewords $a=000$, $b=100$, $c=011$, $d=111$; code R consists of the codewords $r=0000$, $s=1000$, $t=0100$, $u=0011$. Both codes have two pairs of words at each of the distances 1, 2, and 3; R has a 1-1-2 triangle, A doesn't.

MORE EDIT: In response to Jyrki's objections, here's one where both codes are of the same length, and no component is constant over all code words. $a=0000$, $b=1000$, $c=1110$, $d=1111$; $r=0000$, $s=0111$, $t=1110$, $u=1111$. Each code has two pairs at distance 1 and two at distance 3, and one each at distances 2 and 4; first code has a 1-3-4 triangle, $abd$, second code doesn't.