Re: minimum Hamming distance among random bit vectors
From: Michael Amling (nospam_at_nospam.com)
Date: 04/30/04
- Next message: Mok-Kong Shen: "Re: Algorithm to generate prime number from fix SERIAL"
- Previous message: Andrew Swallow: "Re: Cracking DES with C++ is faster than Java?"
- In reply to: Francois Grieu: "Re: minimum Hamming distance among random bit vectors"
- Next in thread: Keith A. Lewis: "Re: minimum Hamming distance among random bit vectors"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Fri, 30 Apr 2004 14:17:45 GMT
Francois Grieu wrote:
>
>>>I also fail to characterise
>>> N(b,d) = min(n such that p(b,n,d)=1)
>>
>>Of course N(b,d) <= (2^b)/v(b,d)+1,
>>where v(b,d) is the sum for k=0 through d of C(b,k).
>
>
> Maybe, but I fail to see why. I'm stuck at the bound
> suggested by Keith Lewis, which assigns a "ball" of
> radius floor(d/2) to each of the n vectors, giving
> N(b,d) <= 2^b / v(b,floor(d/2))
Sorry, I meant N(b,2d)<=(2**b)/v(b,d)+1. My mistake. But I think you
still need the +1, because without it p() is less than 1 when the
spheres fill the space without overlapping. E.g., N(7,2) is 5, not 4.
--Mike Amling
- Next message: Mok-Kong Shen: "Re: Algorithm to generate prime number from fix SERIAL"
- Previous message: Andrew Swallow: "Re: Cracking DES with C++ is faster than Java?"
- In reply to: Francois Grieu: "Re: minimum Hamming distance among random bit vectors"
- Next in thread: Keith A. Lewis: "Re: minimum Hamming distance among random bit vectors"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
|
|
