Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Jyrki Lahtonen Jul 16 '12 at 12:05
    
Thanks. Looking forward to it. –  Rob Jul 16 '12 at 12:35
    
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. –  Jyrki Lahtonen Jul 18 '12 at 8:49
    
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). –  Jyrki Lahtonen Jul 18 '12 at 20:10

3 Answers 3

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.

share|improve this answer
    
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). –  Rob Jul 16 '12 at 12:40
    
I added some links. –  Brendan McKay Jul 16 '12 at 13:41
    
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. –  Rob Jul 16 '12 at 15:23
  • 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.

share|improve this answer
    
That's a nice one (+1). I was half expecting something longer. –  Jyrki Lahtonen Jul 18 '12 at 6:55
    
Welcome to MathOverflow! Gerhard "Ask Me About System Design" Paseman, 2012.07.18 –  Gerhard Paseman Jul 18 '12 at 22:52
    
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. –  Jyrki Lahtonen Jul 19 '12 at 8:10
    
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. –  Jyrki Lahtonen Jul 19 '12 at 15:41

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.

share|improve this answer
    
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. –  Jyrki Lahtonen Jul 19 '12 at 8:15
    
different length - may be add zeroes at the end will cure ? –  Alexander Chervov Jul 19 '12 at 8:43
    
Sorry about being a bit cranky here. I cannot get rid of my preconceived notion of the "correct" version of this question :-) –  Jyrki Lahtonen Jul 19 '12 at 15:42
    
@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. –  Gerry Myerson Jul 20 '12 at 3:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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