Register to reply

Hamming Distance

by asdf1234
Tags: distance, hamming
Share this thread:
asdf1234
#1
Mar9-08, 06:15 PM
P: 4
Hello,

I'm working on a proof and I would like some help. I need to show that any set of 6 distinct 5-bit binary numbers must have at least 5 distinct pairs of elements with Hamming distance less than or equal to 2.

Hamming distance is the sum of the absolute value of each pair of coordinates: the distance between 000 and 111 is

[itex]|0-1|+|0-1|+|0-1|=3[/itex]

Any help would be appreciated.
Phys.Org News Partner Science news on Phys.org
Sapphire talk enlivens guesswork over iPhone 6
Geneticists offer clues to better rice, tomato crops
UConn makes 3-D copies of antique instrument parts
rodigee
#2
Mar9-08, 09:41 PM
P: 39
Could you define what you mean by "pairs of elements" and 5-bit binary? I don't know what either of those are.

But without even really understanding the problem my first thought is the infamous pigeion-hole principal. Have you had any luck trying it?
CRGreathouse
#3
Mar9-08, 10:21 PM
Sci Advisor
HW Helper
P: 3,684
Take an element A. (If it helps, you can assume without loss of generality that it's 00000.) If all other elements are within Hamming distance 1 or 2 ("close"), you're essentially done. (You'd have to show this, of course.) Otherwise, there is an element B with Hamming distance 3 or more ("far") from A to B. (If it helps, you can split this into 3 cases WLOG, where B is 00111, 01111, or 11111.) Now you can group the remaining elements into three groups: those close to both A and B, those close to A but far from B, and those close to B but far from A. If you can limit the size of one of the latter two, you're done.

On the other hand, you could try a pigeonhole approach.

John Creighto
#4
Mar9-08, 10:39 PM
P: 813
Hamming Distance

My attempt at a counter example failed. Why not just use a computer to test all possibilities.

A: 01010
B: 11001
C: 01100
D: 00011
E: 11101
F: 00011

|A,B|=3
|A,C|=1
|A,D|=2
|A,E|=3
|A,F|=2
|B,C|=3
|B,D|=3
|B,E|=2
|B,F|=3
|C,D|=2
|C,E|=2
|C,F|=3
asdf1234
#5
Mar9-08, 11:25 PM
P: 4
Quote Quote by CRGreathouse View Post
Take an element A. (If it helps, you can assume without loss of generality that it's 00000.) If all other elements are within Hamming distance 1 or 2 ("close"), you're essentially done. (You'd have to show this, of course.) Otherwise, there is an element B with Hamming distance 3 or more ("far") from A to B. (If it helps, you can split this into 3 cases WLOG, where B is 00111, 01111, or 11111.) Now you can group the remaining elements into three groups: those close to both A and B, those close to A but far from B, and those close to B but far from A. If you can limit the size of one of the latter two, you're done.

On the other hand, you could try a pigeonhole approach.
This seems like an interesting approach. The only problem I can see running into is how to determine how many pairs have been discovered with each element 'close' to A or B. I guess it would be the number 'close' plus 1 (A or B) choose 2, but how would I know the total amount? Would I have to do cases for the amount 'close' to A, B, etc.? I'm not totally sure I understand.

Any idea how the pigeonhole argument would work in this scenario?

Thanks for the input guys.

Quote Quote by John Creighto View Post
My attempt at a counter example failed. Why not just use a computer to test all possibilities.

A: 01010
B: 11001
C: 01100
D: 00011
E: 11101
F: 00011

|A,B|=3
|A,C|=1
|A,D|=2
|A,E|=3
|A,F|=2
|B,C|=3
|B,D|=3
|B,E|=2
|B,F|=3
|C,D|=2
|C,E|=2
|C,F|=3
You didn't test every pair. There should be 6 choose 2 = 15 pairs.
John Creighto
#6
Mar11-08, 01:19 PM
P: 813
Quote Quote by asdf1234 View Post
You didn't test every pair. There should be 6 choose 2 = 15 pairs.
Oh, I stopped because I was only looking for 5. I didn't read carefully enough. By chance does this problem have anything to do with noise immunity and error checking?
dodo
#7
Mar11-08, 01:52 PM
P: 688
I have a sketch for a proof, but at this moment it is terribly informal. Here it goes.

For one given element A (without loss of generality, 00000), the count of 5-bit elements with distance 0,1,2,3,4,5 to A are resp. 1,5,10,10,5,1. Thus A partitions the 5-bit space in exactly half: 16 with distance > 2, and 16 (in this case, including A) with distance <= 2.

Now the informal part. How would you distribute 6 elements to minimize the number of close pairs? If you choose to place the first 4 elements A,B,C,D, two at one extreme (say, A,B) and two at the other (C,D) of the 5-bit range, with those 4 elements you can form 2 pairs (AB, CD), and when placing the 5th element, it will get close to either AB or CD, thus forming other 2 pairs (f.i, AE, BE). The moment you place the 6th, you will have more than 4 pairs.

Alternatively, if you space equally the first 4 elements, you will have 3 pairs (AB, BC, CD); the moment you add a 5th, it will be close to other two. And you still have a 6th element to place.

Terribly informal, I warned you, just a sketch. I think we need a topology guy.

P.S.: I said "topology", because I think the Hamming distance is a metric on the 5-bit space, thus I suspect the triangle inequality d(A,C) <= d(A,B) + d(B,C) will play a major role in a proof, possibly on the lines sketched above.
John Creighto
#8
Mar11-08, 09:52 PM
P: 813
I can show there is atleast 5 as follows:

It is easy to show that given any three 5 bit binary numbers there must be at least one pair with a hamming distance less then two.

Now with 6 binary numbers there are 6!/(3!(6-3)!=20 ways to choose 3 of the 6 binary numbers. Now for any 3 of the 5 digit binary numbers there can be at most 3 other choices of 3 from the 6 numbers which share the same pair that has a hamming distance less then or equal to 2. Consequently of the 20 choices of 3 numbers which contain a pair with hamming distance less then or equal to 2 the redundancy can be no greater then 4. Consequently there must be at least 20/4=5 pairs which have a hamming distance less then or equal to 2.
etaoin shrdlu
#9
Mar12-08, 11:52 AM
P: 2
Quote Quote by John Creighto View Post
It is easy to show that given any three 5 bit binary numbers there must be at least one pair with a hamming distance less then two.
What about
00000
00111
11100
?
Quote Quote by John Creighto View Post
Why not just use a computer to test all possibilities.
I second this suggestion. The search space is tiny, and if you're still looking for a proof, what you find may surprise you.

What reasons do you have to believe that the statement is true?
rodigee
#10
Mar12-08, 12:32 PM
P: 39
Quote Quote by John Creighto View Post
I:
It is easy to show that given any three 5 bit binary numbers there must be at least one pair with a hamming distance less then two.
Are you sure about that?

I tried creating a pigeonhole argument, but just wound up creating more problems. My idea was to do something like this:

Let S = {A,B,C,D,E,F} be our set of 6 5-bit binary numbers. There are 15 pairs of these 6 numbers. Suppose there are only 4 pairs with a Hamming Distance of 2 or 1 and find a contradiction.

Given any distinct pair, they can have a Hamming Distance of 1, 2, 3, 4, or 5. We assumed there are only 4 having a Hamming Distance of 1 or 2, leaving 11 pairs with a Hamming Distance of 3, 4, or 5. Therefore, at least one of those distances must have at least 4 pairs with that distance.

Clearly, there can't be 4 pairs of distance 5 since we only have 6 numbers and we'd need 8 numbers for that to happen. So can there be 4 pairs of distance 3? 4 pairs of distance 4? I have no idea... this is where I think going this route does more harm than good.

On a side note, something cool I noticed while pigeon-holing around is that if you select any two digits, say the 1st and 4th digit, there will be at least one pair of our numbers whose digits match there.


Register to reply

Related Discussions
Hamming Code Engineering, Comp Sci, & Technology Homework 1
Finding the decoding transformation for a hamming code Calculus & Beyond Homework 4
Distance problem, Using Launcher need to find objects distance Introductory Physics Homework 2
Question about a hamming (7,4) code Introductory Physics Homework 0
Question about Hamming Codes Linear & Abstract Algebra 0