Author |
Topic: HARD: Hamming Distance Questions (Read 35490 times) |
|
James Fingas
Uberpuzzler
Gender:
Posts: 949
|
|
Re: HARD: Hamming Distance Questions
« Reply #25 on: Aug 29th, 2002, 7:28am » |
Quote 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
|
|
Re: HARD: Hamming Distance Questions
« Reply #26 on: Oct 11th, 2002, 2:18pm » |
Quote Modify
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 |
|
|
|
local__
Guest
|
|
Re: HARD: Hamming Distance Questions
« Reply #28 on: Nov 21st, 2002, 7:49am » |
Quote Modify
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
|
|
Re: HARD: Hamming Distance Questions
« Reply #29 on: Nov 23rd, 2002, 11:45pm » |
Quote Modify
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
Gender:
Posts: 1291
|
|
Re: HARD: Hamming Distance Questions
« Reply #30 on: Dec 15th, 2002, 2:53am » |
Quote Modify
|
on Oct 16th, 2002, 6:53am, oliver wrote: 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 lightbulb game built by Elwyn Berlekamp nearly twenty years ago. There are 100 lightbulbs, 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 , 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
Gender:
Posts: 1291
|
|
Re: HARD: Hamming Distance Questions
« Reply #31 on: Dec 15th, 2002, 2:59am » |
Quote 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
|
|
|
Damien Fisher
Guest
|
|
Re: HARD: Hamming Distance Questions
« Reply #33 on: Sep 18th, 2003, 10:59pm » |
Quote Modify
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. 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
|
|
Re: HARD: Hamming Distance Questions
« Reply #34 on: Sep 24th, 2003, 7:51pm » |
Quote Modify
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
|
|
Re: HARD: Hamming Distance Questions
« Reply #35 on: Oct 27th, 2004, 3:51pm » |
Quote Modify
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
Posts: 6
|
|
Re: HARD: Hamming Distance Questions
« Reply #36 on: Jun 13th, 2006, 7:30pm » |
Quote Modify
|
Unless I am being completely Stupid, You all are being completely stupid. 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. 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. EVERY STRING OF LENGTH k THAT HAS A DISTANCE OF k-1 FROM A GIVEN STRING, HAVE A DISTANCE OF 2 FROM EACH OTHER. 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:
Posts: 13730
|
|
Re: HARD: Hamming Distance Questions
« Reply #37 on: Jun 14th, 2006, 1:24am » |
Quote 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
Posts: 6
|
|
Re: HARD: Hamming Distance Questions
« Reply #38 on: Jun 15th, 2006, 9:30am » |
Quote Modify
|
Thanks for pointing that out. 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.
|
|
IP Logged |
|
|
|
Avin
Newbie
Gender:
Posts: 1
|
|
Re: HARD: Hamming Distance Questions
« Reply #39 on: Jul 27th, 2006, 7:20am » |
Quote 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 Modify
|
I've already found myself posting to this thread twice, then retracting what I've said, because I've realized it was incorrect 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 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
|
|
IP Logged |
|
|
|
jczerwinski
Newbie
Posts: 9
|
|
Re: HARD: Hamming Distance Questions
« Reply #42 on: Mar 2nd, 2008, 12:35pm » |
Quote Modify
|
Mmk. So turns out a couple of those numbers above are the result of bad programming. Namely, those that were different than before 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 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 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 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
|
|
IP Logged |
|
|
|
titan
Newbie
Posts: 33
|
|
Re: HARD: Hamming Distance Questions
« Reply #46 on: Oct 14th, 2013, 11:11am » |
Quote 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 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:
Posts: 7526
|
|
Re: HARD: Hamming Distance Questions
« Reply #48 on: Oct 20th, 2013, 12:58am » |
Quote 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 |
|
|
|
|