3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Yes. This is the case. There are known families of relatively simple extended cyclic codes that are known to be non-equivalent, but nevertheless have identical weight enumerators. I will look for a reference, when I am back in my office. $\endgroup$ Jul 16, 2012 at 12:05
  • $\begingroup$ By "simple" I mean that the number of zeros of a cyclic code was either two or three. The lengths of these are powers of two $\ge 64$ (IIRC) or one less. $\endgroup$ Jul 18, 2012 at 8:49
  • 1
    $\begingroup$ Here's the link dl.acm.org/citation.cfm?id=255876.255880 It is a bit embarassing that I didn't remember this right away. My firstborn graduate student worked on their decoding (among other things). $\endgroup$ Jul 18, 2012 at 20:10

3 Answers 3

4
$\begingroup$
  • 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.

$\endgroup$
4
  • $\begingroup$ That's a nice one (+1). I was half expecting something longer. $\endgroup$ Jul 18, 2012 at 6:55
  • $\begingroup$ Welcome to MathOverflow! Gerhard "Ask Me About System Design" Paseman, 2012.07.18 $\endgroup$ Jul 18, 2012 at 22:52
  • $\begingroup$ Hmm. I rather like the third example only. While it may fit the scope of the question, going for a coset feels like cheating. As does a code with one component always zero. $\endgroup$ Jul 19, 2012 at 8:10
  • $\begingroup$ Sorry about being a bit cranky here. I cannot get rid of my preconceived notion of the "correct" version of this question, and only the third (or chronologically the first) example is a good match with that. $\endgroup$ Jul 19, 2012 at 15:41
4
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thank you for your answer. I looked it up and couldn't find anything; it's possible that I did find but couldn't understand it (I only know the basics of coding theory). $\endgroup$
    – Rob
    Jul 16, 2012 at 12:40
  • $\begingroup$ I added some links. $\endgroup$ Jul 16, 2012 at 13:41
  • 1
    $\begingroup$ Thanks. I can only open the second and fourth links, and I don't really see the connection, but I'll have a closer look shortly. $\endgroup$
    – Rob
    Jul 16, 2012 at 15:23
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Hmm. Am I counting something wrong? I see $d(a,d)=d(b,d)=6$. Also using codes of different length feels like cheating, because the question of equivalence becomes meaningless. $\endgroup$ Jul 19, 2012 at 8:15
  • $\begingroup$ different length - may be add zeroes at the end will cure ? $\endgroup$ Jul 19, 2012 at 8:43
  • $\begingroup$ Sorry about being a bit cranky here. I cannot get rid of my preconceived notion of the "correct" version of this question :-) $\endgroup$ Jul 19, 2012 at 15:42
  • $\begingroup$ @Jyrki, you're right about the distances in the first example. I'll have to check my notes to see what I really meant to say. But I think I got the distances right in the second example. And I did have Alexander's idea in mind for the lengths; take 0000, 1000, 0110, 1110 for Code A, and it's the same length as Code R. I don't know why you feel that a code with one component constant is cheating, but I'll edit in an example without that feature. $\endgroup$ Jul 20, 2012 at 3:25

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.