wu :: forums
« wu :: forums - HARD: Hamming Distance Questions »

Welcome, Guest. Please Login or Register.
Jun 22nd, 2018, 8:04am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   hard
(Moderators: william wu, Icarus, towr, SMQ, Grimbal, ThudnBlunder, Eigenray)
   HARD: Hamming Distance Questions
« Previous topic | Next topic »
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: HARD: Hamming Distance Questions  (Read 29859 times)
James Fingas
Uberpuzzler
*****





   
Email

Gender: male
Posts: 949
Re: HARD: Hamming Distance Questions  
« Reply #25 on: Aug 29th, 2002, 7:28am »
Quote Quote Modify Modify

Here's how I'm currently working on the problem. First of all, draw out Pascal's triangle, and pick out the kth row. Now the 1 on the end of the kth row corresponds with the first message we'll pick.
 
Now the interior of the "ball" of messages that are closer the D away from our first message are the next D-1 numbers in the row. In the Dth row are all the messages which are far enough away from our first message. This gives us an idea of the "surface area" of the "ball" around our first message. But how are the messages on this surface organized? How many can we fit on the surface with a distance >=D? What is the optimal way to choose them?
 
And then things get a little more complicated. After we've put as many messages as we can on the surface, we have a new "surface" made up of all the messages that are exactly D away from at least one of the selected messages. This surface will probably be "bumpy"--not all messages on the surface will have the same distance from our first message. How large is this surface? How many messages can we fit? How do we choose where to fit them in? I'm guessing we should prefer to choose the messages which are closer to the first message.  
 
As we choose more layers of messages, the surface gets more and more convoluted. However, I think that we can probably get an optimal packing of messages with a greedy algorithm. If not, then choosing the messages will be very difficult...
IP Logged

Doc, I'm addicted to advice! What should I do?
eKtoric
Guest

Email

Re: HARD: Hamming Distance Questions  
« Reply #26 on: Oct 11th, 2002, 2:18pm »
Quote Quote Modify Modify Remove Remove

Forgive me for interrupting.  I haven't given it much thought, but one thing did come to mind that might point in a different direction.
 
Upon first reading, the question reminded me of Orthogonality.  What popped into my head was the selection of interference codes for CDMA whereby the signal is filtered by an orthogonal code.
 
My CDMA is rusty (so I could have stated that all wrong), but perhaps this area of study may shed some additional thoughts?
IP Logged
oliver
Newbie
*





   


Posts: 25
Re: HARD: Hamming Distance Questions  
« Reply #27 on: Oct 16th, 2002, 6:53am »
Quote Quote Modify Modify

Riddlers,  
 
this problem apparently is harder, much harder, then we (I) thought.  
You can see for yourself if you search in google for:
"coding theory" "sphere packing"
 
Here are some link for your reading pleasure:
 
http://www.research.att.com/~njas/doc/1218codes.ps
 
and (this actually contains a riddle!)
 
http://www.research.att.com/~njas/doc/1218related.ps
 
The main page (of an at&t researcher) is
http://www.research.att.com/~njas/
 
Ok, I officially declare I have given up on this Wink, but it's really fascinating that no one didn't see how hard this problem really is ...
IP Logged
local__
Guest

Email

Re: HARD: Hamming Distance Questions  
« Reply #28 on: Nov 21st, 2002, 7:49am »
Quote Quote Modify Modify Remove Remove

hi,
i think i'm almost finished.. but i'm not sure if i understand the task correctly..  i will tell it in my words and can u correct me please? i'm not pro at english
 
u have given K.. then in this K there is max bitstrings 2k..  and then n is between> 0 < n <  2k ..
but for n = 2 the distance is K, so we can assume  2 < n < 2k.....
so u have given K and N ,, and we need formula that will compute the minimal distance between any 2 bitstrings, and this minimal distance (= min )MUST be as maximazed as possible..
so there cant be another subset of same power(same number of elements) at same K, that will have minimal H distance, bigger than the "min"?
tnx for answering
 
ok , if this is it, i can tell u its not so hard as u think it is..
just needs apropriate aprouch (aproach?)(approuch?)
IP Logged
wingyen LAU
Guest

Email

Re: HARD: Hamming Distance Questions  
« Reply #29 on: Nov 23rd, 2002, 11:45pm »
Quote Quote Modify Modify Remove Remove

Hi ALL:
    I don't remember the exact details to this problem.  And I am not sure if i understand this question full.  But I don't have a little memory of seeing this problem in one of my summer school course (discrete math) from binghamton university by prof. guzman http://www.math.binghamton.edu/dept/server/research.html.  I think the solution has an upper bound for n.  
I'll try to get back to u guys if i find the solution again.
 
WING
IP Logged
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: HARD: Hamming Distance Questions  
« Reply #30 on: Dec 15th, 2002, 2:53am »
Quote Quote Modify Modify

on Oct 16th, 2002, 6:53am, oliver wrote:
and (this actually contains a riddle!)
 
http://www.research.att.com/~njas/doc/1218related.ps

 
 
SWEET! I've never seen this one before! I'll have to read this paper later.
 
 

In the Math. Dept. Commons Room at Bell Labs in Murray Hill there is a light­bulb game built by Elwyn Berlekamp nearly twenty years ago. There are 100 light­bulbs, arranged in a 10 × 10 array. At the back of the box there are 100 individual switches, one for each bulb. On the front there are 20 switches, one for each row and column. Throwing one of the rear switches changes the state of a single bulb, while throwing one of the front switches changes the state of a whole row or column. Suppose some subset S of the 100 bulbs are turned on using the rear switches. Let f (S) be the minimum number of illuminated bulbs that can now be attained by throwing any sequence of row and column switches. The problem is to determine  
 
R = max f(S) over all possible S


 
 
It sounds very similar to Positive Matrix Sums in the medium section (http://www.ocf.berkeley.edu/~wwu/riddles/medium.shtml#positiveMatrixSums ):
 
 

You have an m x n grid with some real numbers in each cell. You can multiply any row by -1, or any column by -1. Show that by making multiplications of this kind, the sum of the numbers in every row, and the sum of the numbers in every column, can all be made positive simultaneously.

 
 
Quote:

Ok, I officially declare I have given up on this Wink, but it's really fascinating that no one didn't see how hard this problem really is ...

 
Actually a Mr. Fisher e-mailed me earlier this year, hoping to convince me that the Maximum Minimum Hamming Distance puzzle I posted was an unsolved problem. He works on software that generates codes such as the ones we are looking for, and it uses table lookups to determine maximum minimum Hamming distances for given parameters. We argued for a little while, but after some miscommunications I thought he did not understand the problem correctly, so I just ignored his advice. I guess the truth comes out.
« Last Edit: Dec 15th, 2002, 7:32pm by william wu » IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
william wu
wu::riddles Administrator
*****





   
WWW

Gender: male
Posts: 1291
Re: HARD: Hamming Distance Questions  
« Reply #31 on: Dec 15th, 2002, 2:59am »
Quote Quote Modify Modify

on Nov 23rd, 2002, 11:45pm, wingyen LAU wrote:
I think the solution has an upper bound

 
Yeah, when I checked out this problem over the summer, I recall trying to apply a basic coding theory bound whose escapes me at the moment. My knowledge of information theory however is practically garbage though (periodic frivolous browsings of a textbook for a few weeks ... hopefully I'll take an actual info theory course someday), so it's entirely possible that the bound doesn't apply in this case. Mr. Fisher mentioned it though in his e-mail so maybe it does; I'll have to track down what exactly he said.
 
In any case, I'm not interested in a bound, I want the exact numbers.
« Last Edit: Dec 15th, 2002, 2:59am by william wu » IP Logged


[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
Joe Pellino
Guest

Email

Re: HARD: Hamming Distance Questions  
« Reply #32 on: Jan 13th, 2003, 2:59pm »
Quote Quote Modify Modify Remove Remove

I have no idea about this problem.  Actually i just want to know willy wu's email adress.  I want to email him a solution to 100 prisoners and a lightbulb I have no idea about this problem.  Actually i just want to know willy wu's email adress.  I want to email him a solution to 100 prisoners and a lightbulb I have no idea about this problem.  Actually i just want to know willy wu's email adress.  I want to email him a solution to 100 prisoners and a lightbulb I have no idea about this problem.  Actually i just want to know willy wu's email adress.  I want to email him a solution to 100 prisoners and a lightbulb I have no idea about this problem.  Actually i just want to know willy wu's email adress.  I want to email him a solution to 100 prisoners and a lightbulb I have no idea about this problem.  Actually i just want to know willy wu's email adress.  I want to email him a solution to 100 prisoners and a lightbulb I have no idea about this problem.  Actually i just want to know willy wu's email adress.  I want to email him a solution to 100 prisoners and a lightbulb I have no idea about this problem.  Actually i just want to know willy wu's email adress.  I want to email him a solution to 100 prisoners and a lightbulb I have no idea about this problem.  Actually i just want to know willy wu's email adress.  I want to email him a solution to 100 prisoners and a lightbulb I have no idea about this problem.  Actually i just want to know willy wu's email adress.  I want to email him a solution to 100 prisoners and a lightbulb I have no idea about this problem.  Actually i just want to know willy wu's email adress.  I want to email him a solution to 100 prisoners and a lightbulb I have no idea about this problem.  Actually i just want to know willy wu's email adress.  I want to email him a solution to 100 prisoners and a lightbulb I have no idea about this problem.  Actually i just want to know willy wu's email adress.  I want to email him a solution to 100 prisoners and a lightbulb I have no idea about this problem.  Actually i just want to know willy wu's email adress.  I want to email him a solution to 100 prisoners and a lightbulb
IP Logged
Damien Fisher
Guest

Email

Re: HARD: Hamming Distance Questions  
« Reply #33 on: Sep 18th, 2003, 10:59pm »
Quote Quote Modify Modify Remove Remove

on Dec 15th, 2002, 2:53am, william wu wrote:

 
Actually a Mr. Fisher e-mailed me earlier this year, hoping to convince me that the Maximum Minimum Hamming Distance puzzle I posted was an unsolved problem. He works on software that generates codes such as the ones we are looking for, and it uses table lookups to determine maximum minimum Hamming distances for given parameters. We argued for a little while, but after some miscommunications I thought he did not understand the problem correctly, so I just ignored his advice. I guess the truth comes out.

 
Hey, that's me!  No worries about the miscommunication.  After all, I knew I was right...hehe.  Smiley
 
There's plenty of interesting work on this.  The software I work on is at http://magma.maths.usyd.edu.au, but there is plenty of resources available for free.  E.g., here (http://www.win.tue.nl/~aeb/voorlincod.html) is an (out-of-date) database of bounds for various values of n and k for linear codes.  If you search around you'll find tons more work.
IP Logged
Damien Fisher
Guest

Email

Re: HARD: Hamming Distance Questions  
« Reply #34 on: Sep 24th, 2003, 7:51pm »
Quote Quote Modify Modify Remove Remove

on Dec 15th, 2002, 2:59am, william wu wrote:

 
In any case, I'm not interested in a bound, I want the exact numbers.

 
In some cases (especially over GF(2), which I believe is the case you are interested in), the known lower and upper bounds meet, giving the "exact number" you are interested in.
 
E.g. (this is output from Magma, BKLC = "Best Known Linear Code"):
 
> SetPrintLevel("Minimal");  
> SetVerbose("BestCode",true);  
> SetPrintLevel("Minimal");    
> SetVerbose("BestCode", true);
> BKLCLowerBound(GF(2), 22, 13), BKLCUpperBound(GF(2), 22, 13);
5 5
> BKLC(GF(2), 22, 13);
Construction of a [ 22 , 13 , 5 ] Code:
[1]:  [23, 14, 5] Linear Code over GF(2)
   Construction from a stored generator matrix
[2]:  [22, 13, 5] Linear Code over GF(2)
   Shortening of [1] at { 23 }
[22, 13, 5] Linear Code over GF(2)
true
IP Logged
Digitalis
Guest

Email

Re: HARD: Hamming Distance Questions  
« Reply #35 on: Oct 27th, 2004, 3:51pm »
Quote Quote Modify Modify Remove Remove

Give up on this one. The case n=k eventually resolves into the Hadamard Conjecture, which is considered to be one of the central and most difficult problems in combinatorics. Mathworld has a decent blurb about it.
IP Logged
NumBeast
Newbie
*





   
Email

Posts: 6
Re: HARD: Hamming Distance Questions  
« Reply #36 on: Jun 13th, 2006, 7:30pm »
Quote Quote Modify Modify

Unless I am being completely Stupid, You all are being completely stupid.   Tongue
 
to quote James
" For a given length k and a distance D, find the maximum possible number of messages n"  
be warned that you'll never get a complete list, there can be multiple n's for one distance.   Grin
 
James, you gave 2 lists of 20 bit-strings that are "3" apart from each other. in the first (and second) list you have 2 0000's and multiple other repeats. not to mention the multiple bit-strings that are less than 3 away from each other.  
 
 Cool EVERY STRING OF LENGTH k THAT HAS A DISTANCE OF k-1 FROM A GIVEN STRING, HAVE A DISTANCE OF 2 FROM EACH OTHER.  Cool
I have a proof to this but I'll let you do it
 
if n=k D=2 (unproven)
 
so here are my thoughts...
If n=2 D=k, this is pretty obvious  
 
For any K say that when n=x, D=y
then when n>X D<=Y, meaning when the number of bitstrings increases the maximum minimum distance either stays the same or decreases.
 
so here is a 'correct' listing that I found in 2 hours, I'll update it later as I spend more time on this.
(the max for n is 2^k)
k=1
     n=2 D=1 (1,0)
K=2
    n=2 D=2 (00,11)
    n>=3 D=1  
K=3
    n=2 D=3 (000,111)
    n=3 D=2 (010,111,100)
    n=4 D=2 (011,000,110,101)
    n>=5 D=1
k=4
   n=2 D=4 (above theorm)
   n=3 D=2 (other not so above theorm)
   n=4,5 D=2
   n>=6 D=1
k=5
   n=2 D=5
   n=3 D=3
   n=4 D=3
   n=5,6 D=2
  n>=7 D=1  
 
BTY in all of my calculatins I have assumed that  
n =! 1,0
k>=1
 
 
 
as I mentioned at the beginning I might have made multiple mistakes while reading your posts and/or writing my own, if so I am sorry for insulting you and please tell me where I went wrong
 
P.S. If you are reading this and happen to wonder why I am talking to people who wrote thier last posts 2 years ago, the answer is it makes me feel better
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13614
Re: HARD: Hamming Distance Questions  
« Reply #37 on: Jun 14th, 2006, 1:24am »
Quote Quote Modify Modify

on Jun 13th, 2006, 7:30pm, NumBeast wrote:
James, you gave 2 lists of 20 bit-strings that are "3" apart from each other. in the first (and second) list you have 2 0000's and multiple other repeats. not to mention the multiple bit-strings that are less than 3 away from each other.  
You're misinterpreting his post, his list is 20 8-bit string, not two lists of 20 4-bit strings.
 
Indeed with 4 bits, you can't get more than 16 distinct binary strings, let alone 20.
IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
NumBeast
Newbie
*





   
Email

Posts: 6
Re: HARD: Hamming Distance Questions  
« Reply #38 on: Jun 15th, 2006, 9:30am »
Quote Quote Modify Modify

Thanks for pointing that out.   Wink
 
and i've ben thinking about it, trying to" For a given length k and a distance D, find the maximum possible number of messages n"  is a good way to set some milestones for a more through approach later.   Sad
IP Logged
Avin
Newbie
*





   


Gender: male
Posts: 1
Re: HARD: Hamming Distance Questions  
« Reply #39 on: Jul 27th, 2006, 7:20am »
Quote Quote Modify Modify

Hi NumBeast,
 
Your numbers are non-optimal. I got  
 
Quote:
k=4
   n=2 D=4 (as you did)
   n=3 D=2
   n=4 D=2
   n=5 D=2
   n=6 D=2
   n=7 D=2
   n=8 D=2
   n>=9 D=1
k=5
   n=2 D=5
   n=3 D=3
   n=4 D=3
   4<n<17 D=2
  n>=17 D=1  

 
The following is a list of 8 4-bit strings with d=2:
 
0000
0011
0101
0110
1001
1010
1100
1111
 
In fact, I can generalize this list to show that for n=2^(k-1) and k>=2, D>=2, and it should be easy to show that D<=2 as well. This is why I assert that for k=5 n=16, D is 2 as well: take the above list of 4 bit strings and append a 0 to them, then take the 8 remaining 4 bit strings that are not on that list (which also satisfy the property of d=2) and append a 1 to them. Now you've got 16 5-bit strings for which d=2.  
 
Actually when I first saw this problem a few minutes ago before getting to the case of n>=5 I thought the problem was mind numbingly easy and that all values of n would follow a similar pattern based on the next smaller power of 2, and I couldn't understand why this was an unsolved problem, but once I started trying it out for n>=5 I realized why I was mistaken.
IP Logged
jczerwinski
Newbie
*





   


Posts: 9
Re: HARD: Hamming Distance Questions  
« Reply #40 on: Mar 1st, 2008, 9:55am »
Quote Quote Modify Modify

I've already found myself posting to this thread twice, then retracting what I've said, because I've realized it was incorrect Smiley
 
Anyway, I can also confirm that James' set of 20 k=8 strings has no two elements with d < 3 from each other.
 
So, oliver's algorithm isn't generating an optimal set of  these bitstrings. I wrote the same algorithm in c:
Code:

#include <stdio.h>
#define N 10
 
main(){
  int stringLength;
  for (stringLength = 1; stringLength <= N; stringLength++){
      printf("k: %d\n",stringLength);
      int numStrings = pow(2,stringLength);
      int minDist;
      for (minDist = 1; minDist <= stringLength; minDist++){
     unsigned long int setStrings[numStrings];
     int setCount = 1;
     setStrings[0] = 0;
 
 
 
  int totalCount;
  for (totalCount = 1 ; totalCount < numStrings; totalCount++){
      int i;
      for (i = 0; i < setCount; i++){
     if (hamDist(totalCount,setStrings[i]) < minDist){
             break;
             }
     if (i == (setCount - 1)){
      setStrings[setCount] = totalCount;
      setCount++;
      }
       
 
 
 
 
}
 
 
 
}
 
 
 
printf("
d: %d
n: %d\n",minDist,setCount);
 
 
}
 
}
 
}
 
 
/* hamDist takes two bitstrings and returns the hamming distance between them */
int hamDist(unsigned long int a,unsigned long int b){
 
int i = 0;
 
unsigned long int axorb;
 
for (axorb = a ^ b; axorb != 0; axorb = axorb >> 1){
 
 
if (1 & axorb){
    i++;
 
 
}
 
}
 
return i;
}

 
Basically, for each k and d, the algorithm tries to build an optimal set. That is, the largest possible set that has hamming distance d or greater. The thing is, oliver and I simply assumed that iterating over the natural numbers n and checking if, for every n, the distance between the binary coding for n and the numbers already in our set is less than our minimum distance. If it is, we skip the number. If it isn't, we add the number to the set.
 
So, we know the natural iteration over the natural numbers  (n, n+1, ...) does not generate an optimal set. However, there does exist some optimal set for any k and d, and possibly more than one. So, there must exist some iteration over the natural numbers, and some two seed elements of our set, that when tested against the elements already in our set, will generate the optimal set. What is this iteration?
 
My first other guess was ensuring that the numbers we consider adding to the set are not only greater than d away from all other elements of our set, but also that the distance is as small as possible. So, first only add elements that are exactly d from our seed elements. Then, once you've iterated over all the bitstrings of length k, iterate over them again, this time allowing length d and length d+1. Do this until, on the last iteration, you've allowed any distance greater than d.
 
Turns out, this iteration is no better. It gives the exact same (sub-optimal) table that oliver gives.
 
If anyone wants the code or output for this, I'll send it over. I also have code that tested James' 8-bit set for its minimum hamming distance. If anyone wants that i'll send it as well. It's all in C.
 
I'm going to keep trying different iterations today. Next up is going to be a pascal's triangle traversal. Start from 000...000, then iterate through the bitstrings d=1 from 0 (I.e. 0001, 0010, 0100, 1000 for k=4, d=1), then goto the next d, and try it again.  I'll keep you posted. James suggested something along those lines. I'll implement his idea exactly if it's clear enough.
 
Also, if he ever comes back, I want to know how the heck he generated his 20 string set. It's a doozy.
IP Logged
jczerwinski
Newbie
*





   


Posts: 9
Re: HARD: Hamming Distance Questions  
« Reply #41 on: Mar 2nd, 2008, 1:01am »
Quote Quote Modify Modify

Mmk. So the algorithm is pretty much done. Getting a seg fault for k=5, so I'll have to fix it up in the morning. But! The numbers are different from the algorithm oliver and myself implemented earlier! Here're the tables it's given me so far:
 
k: 1
     d: 1    n: 2
k: 2
     d: 1    n: 4
     d: 2    n: 2
k:3
     d: 1    n: 8
     d: 2    n: 5 (Different! One more here!)
     d: 3    n: 2
k:4
     d: 1    n: 16
     d: 2    n: 8
     d: 3    n: 3 (Different! One more here!)
     d: 4    n: 2
 
So, clearly up to k = 4, this algorithm generates at least as optimal a set as the first, as well as a more optimal set for some distances. Progress!
 
So, the algorithm works like this. For every k, d, we compute an array where the elements in the array are k digit bitstrings exactly d from the 0 bitstring. Then, we take all these arrays of elements and concatenate them, in order of increasing distance from 0. So, we've got an array that enumerates these bitstriings. Then we use this to feed the same algorithm as before.
 
The idea is, by picking strings more optimally using a finely-honed input sequence, we should be able to pack them tighter. I haven't bothered trying to prove this yet - I want the rest of my tables, and then I'll try and optimize further, and if I don't think it's possible, try and prove optimality.
 
Anyway, progress! I'll post the code tomorrow, as well as new, improved tables Smiley
IP Logged
jczerwinski
Newbie
*





   


Posts: 9
Re: HARD: Hamming Distance Questions  
« Reply #42 on: Mar 2nd, 2008, 12:35pm »
Quote Quote Modify Modify

Mmk. So turns out a couple of those numbers above are the result of bad programming. Namely, those that were different than before Wink
 
However, I fixed the program, and it still is more optimal than the original algorithm. Here are the updated tables, to k = 10.
 
k: 1
d: 1  n: 2
k: 2
d: 1  n: 4
d: 2  n: 2
 
k: 3
d: 1  n: 8
d: 2  n: 4
d: 3  n: 2
 
k: 4
d: 1  n: 16
d: 2  n: 8
d: 3  n: 2
d: 4  n: 2
 
k: 5
d: 1  n: 32
d: 2  n: 16
d: 3  n: 4
d: 4  n: 2
d: 5  n: 2
k: 6
 
d: 1  n: 64
d: 2  n: 32
d: 3  n: 8
d: 4  n: 4
d: 5  n: 2
d: 6  n: 2
 
k: 7
d: 1  n: 128
d: 2  n: 64
d: 3  n: 16
d: 4  n: 8
d: 5  n: 2
d: 6  n: 2
d: 7  n: 2
 
k: 8
d: 1  n: 256
d: 2  n: 128
d: 3  n: 16
d: 4  n: 16
d: 5  n: 4
d: 6  n: 2
d: 7  n: 2
d: 8  n: 2
 
k: 9
d: 1  n: 512
d: 2  n: 256
d: 3  n: 32
d: 4  n: 16
d: 5  n: 6     (Different)
d: 6  n: 4
d: 7  n: 2
d: 8  n: 2
d: 9  n: 2
 
k: 10
d: 1  n: 1024
d: 2  n: 512
d: 3  n: 64
d: 4  n: 32
d: 5  n: 12  (Different)
d: 6  n: 4
d: 7  n: 2
d: 8  n: 2
d: 9  n: 2
d: 10n: 2
 
 
Here's oliver's original list, for comparison:
 
k: 3, d: 2, n: 4
 
k: 4, d: 2, n: 8
k: 4, d: 3, n: 2
 
k: 5, d: 2, n: 16
k: 5, d: 3, n: 4
k: 5, d: 4, n: 2
 
k: 6, d: 2, n: 32
k: 6, d: 3, n: 8
k: 6, d: 4, n: 4
k: 6, d: 5, n: 2
 
k: 7, d: 2, n: 64
k: 7, d: 3, n: 16
k: 7, d: 4, n: 8
k: 7, d: 5, n: 2
k: 7, d: 6, n: 2
 
k: 8, d: 2, n: 128
k: 8, d: 3, n: 16
k: 8, d: 4, n: 16
k: 8, d: 5, n: 4
k: 8, d: 6, n: 2
k: 8, d: 7, n: 2
 
k: 9, d: 2, n: 256
k: 9, d: 3, n: 32
k: 9, d: 4, n: 16
k: 9, d: 5, n: 4
k: 9, d: 6, n: 4
k: 9, d: 7, n: 2
k: 9, d: 8, n: 2  
 
So, this new algorithm is still generating better sets than the original, up to k=9. Still, it hasn't generated James' 20-string set for k=8, d=3 yet, so clearly it's still not optimal.
 
I'm figuring, when we arrange the bitstrings based on their distance from 0, and then start choosing elements to add to our set, we choose the first natural number whose binary representation is d from 0 as our second set element. This is fine: however, then, this same element has a similar "Pascal Sequence". That is, we already ordered the natural numbers so that the distance from 0 of the next number in the array is greater than or equal to the distance from 0 of the current element in the array. Well, such a sequence exists with respect to the next string we add to our set, just as it did with 0.
 
So, to what extent do these sets overlap? It's actually easy to generate the new sequence for any other element given that element: just take the sequence for the 0 string and exclusive-or all the bits in each string in the sequence with our new string. We can then compare these two arrays to find shared elements between the sets, and select any elements that are shared first.
 
I know the problem we're trying to solve isn't the generation of these sets, but it seems that we need to have them if we want to know how many elements are in them. For the time being, anyway.
 
Maybe I'll just write a brute force algorithm to try all possible combinations of sets for any k and then compute the minimum hamming distance for them all..... but I hate doing things so stupidly... and the search space would get massive extremely quickly.
« Last Edit: Mar 2nd, 2008, 12:37pm by jczerwinski » IP Logged
jczerwinski
Newbie
*





   


Posts: 9
Re: HARD: Hamming Distance Questions  
« Reply #43 on: Mar 2nd, 2008, 12:54pm »
Quote Quote Modify Modify

Interesting! I just tried the new algorithm PLUS the semi-improved old one. That is, I generate the new "Pascal Sequence", and then, ensure that the distance between any element I add to the set is EXACTLY d from all the elements, and then I go over the elements so that the distance is between d and d+1.... until the upper bound = k. I get these tables:
 
k: 1
  d: 1  n: 2
k: 2
  d: 1  n: 4
  d: 2  n: 2
k: 3
  d: 1  n: 8
  d: 2  n: 4
  d: 3  n: 2
k: 4
  d: 1  n: 16
  d: 2  n: 8
  d: 3  n: 2
  d: 4  n: 2
k: 5
  d: 1  n: 32
  d: 2  n: 16
  d: 3  n: 4
  d: 4  n: 2
  d: 5  n: 2
k: 6
  d: 1  n: 64
  d: 2  n: 22  (Worse)
  d: 3  n: 8
  d: 4  n: 4
  d: 5  n: 2
  d: 6  n: 2
k: 7
  d: 1  n: 128
  d: 2  n: 64
  d: 3  n: 13  (Worse)
  d: 4  n: 8
  d: 5  n: 2
  d: 6  n: 2
  d: 7  n: 2
k: 8
  d: 1  n: 256
  d: 2  n: 107 (Worse)
  d: 3  n: 17   (Better)
  d: 4  n: 16
  d: 5  n: 4
  d: 6  n: 2
  d: 7  n: 2
  d: 8  n: 2
k: 9
  d: 1  n: 512
  d: 2  n: 256  
  d: 3  n: 32
  d: 4  n: 16
  d: 5  n: 6
  d: 6  n: 4
  d: 7  n: 2
  d: 8  n: 2
  d: 9  n: 2
k: 10
  d: 1  n: 1024
  d: 2  n: 386
  d: 3  n: 64
  d: 4  n: 32
  d: 5  n: 12
  d: 6  n: 4
  d: 7  n: 2
  d: 8  n: 2
  d: 9  n: 2
  d: 10  n: 2
 
Notice some of them are better, some of them are worse! And the better set is for the same k, d that James found that nice set for. Weird.
IP Logged
dk39ab
Newbie
*





   


Posts: 1
Re: HARD: Hamming Distance Questions  
« Reply #44 on: Mar 4th, 2008, 3:50am »
Quote Quote Modify Modify

Hi, there's believed to be an approximate solution to this.
 
From Information Theory, Inference, and Learning Algorithms by David MacKay:
 
Quote:
... We thus expect, for large N, that the minimum distance of a random linear code will be close to the distance dGV defined by
 
H2(dGV/N) = (1 - R).
 
Definition. This distance, dGV =  NH2-1(1 - R), is the Gilbert-Varshamov distance for rate R and blocklength N.
 
The Gilbert-Varshamov conjecture, widely believed, asserts that (for large N) it is not possible to create binary codes with minimum distance significantly greater than dGV.

 
In the terminology used here the length k is N and the number of strings n is 2RN.
 
also, H2(x) = xlog2(1/x)+(1-x)log2(1/(1-x))
 
So, the maximum minimum distance should be around kH2-1(1-log2(n)/k) for large k, if this conjecture holds.
IP Logged
jczerwinski
Newbie
*





   


Posts: 9
Re: HARD: Hamming Distance Questions  
« Reply #45 on: Mar 5th, 2008, 2:18pm »
Quote Quote Modify Modify

Thanks for the link. Here's another. http://scholar.lib.vt.edu/theses/available/etd-05042004-120929/unrestric ted/thesis_revised.pdf
 
These binary strings we're considering are closely related to Hadamard matrices. A poster suggested earlier that this problem resolves into the Hadamard Conjecture for the case n=k. He seems to be correct.
 
The conjecture states, in the same terms we have been using here, that for any bitstring length of 4k for any k of the naturals, there exists at least 4k bitstrings with d = k/2 from one another. So, the problem we've been looking at here is in some ways more complicated than even the hadamard conjecture. So, even a simple proof of this:
 
k = string length
d = minimum hamming distance
n = max number of such strings  
 
k = 4j (j of the naturals)
    d = 2j  n = 4j (or greater)
 
For all j, would be quite the breakthrough. So, apparently, even solving for this case has never been done. Or at least not published. So, that means an algorithm even to generate such sets has not been proven, in general, to exist. And only sets up to some 800 or so bitlength have been proven to exist. This suggests (I'm hypothesizing) that it's computationally difficult to generate such optimal sets. Nieve algorithms that do this are probably worse than factorial time in the size of k. So my comment on trying it above would be utterly useless for almost any input.
 
Anyway, I'm going to go study that paper Smiley
IP Logged
titan
Newbie
*





   


Posts: 33
Re: HARD: Hamming Distance Questions  
« Reply #46 on: Oct 14th, 2013, 11:11am »
Quote Quote Modify Modify

"How many bitstrings are in such a ball? By symmetry,  
|B(k,s,d)| = |B(k,0,d)|, where 0 is the string of k zeroes.  
But a bitstring is at Hamming distance i from 0 iff it has  
i one-bits, so the number of bitstrings at Hamming distance  
i from 0 is the number of ways of choosing i one-bits  
from k bits. "
So, shouldn't f() = kCi ? and not sum( 0<=i<=d). And what is this sum defining f() at all? Not able to understand!
 
Also, I don't nderstand the inequality :
nf()<=2^k
 
Isn't n always equal to 2^k? bcoz n is the no. of strings possible.
So, say if k=3, and we know that it forms a cube with 8 vertices. so, n=2^3=8.
 
I'm new to this world of hamming codes. Trying to understand this concept.
« Last Edit: Oct 18th, 2013, 8:46am by titan » IP Logged
titan
Newbie
*





   


Posts: 33
Re: HARD: Hamming Distance Questions  
« Reply #47 on: Oct 18th, 2013, 8:47am »
Quote Quote Modify Modify

Please help!!
I really want to understand this!
Please refer to my last post on this thread.
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7393
Re: HARD: Hamming Distance Questions  
« Reply #48 on: Oct 20th, 2013, 12:58am »
Quote Quote Modify Modify

f(k,d) = |B(k,0,d)| = sum(0 <= i <= d : k choose i).  
Obviously f(k,d) cannot be kCi because there is no i.
If you mean kCd, you only count the strings at distance = d and not <= d.
 
n*f(k,d)<=2^k results from the fact that there is no overlap between the sets B(k,s,d).  Each of the 2^k bitstrings can appear only once.  n*f(k,d)=2^k would mean there is no gap between the sets.  This is not true in general.
« Last Edit: Oct 20th, 2013, 12:58am by Grimbal » IP Logged
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board