Codeword decoding - volume bound inequality

Codeword decoding - volume bound inequality

itzik (guest) 23 Jan 2013 13:16

It was written in the presentation that the volume bound inequality
assuming minimum distance between 2 codewords id d=3, is:

(2^k)*(n+1) <= 2^n

I thought about the case that d>3, and i came up with this inequality:

(2^k)*((n^A)+1) <= 2^n
A = floor((n-1)/2)

Do you agree with that claim?

Guest (guest) 23 Jan 2013 18:24

I don't think so…
Imagine the (7,4,3) code we saw in class, but with an added 'overall' parity bit, changing the distance from 3 to 4.
If what you say is correct, then (8,4,4) would fit the inequality you suggested, however -

A=floor((8-1)/2)=3
but the left side of the equation comes out as

(2^4)*((8*3)+1)

which is smaller than 2^13, and then obviously smaller than 2^8

Maybe I just misunderstood the mathematical notations… my computer sort of scrambled it all terribly.

Guest (guest) 23 Jan 2013 18:26

edit: meant bigger than 2^13 and bigger than 2^8, not smaller!

itzik (guest) 23 Jan 2013 19:03

ohh sorry,
I ment A to be:

A = floor((d-1)/2)

and now your example fits the inequality.

Guest (guest) 23 Jan 2013 21:23

I still don't think so….

If you check page 31 in the same presentation, you'll see the inequality for a general d in there, and it turns into an equality iff we deal with a perfect code.

Now, since for d=5, their formula has a smaller value than yours on the left side for every n>1(just write both arguements down and play a little with their form, you'll see that pretty clearly), then a perfect code with d=5 will be a counter-example to your arguement, so assuming that there is a perfect 5-distance code, and assuming that the presentation material is correct, I think this is still a mistake.