wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> Hamming distance
        
(Message started by: erick lee on Oct 5^th, 2004, 1:25pm)

Title: Hamming distance
Post by erick lee on Oct 5^th, 2004, 1:25pm

Hamming Distance
I saw a previous post regarding hamming distance, and came up with another problem about it.
I have a difficult riddle that my professor gave us in class.
Basically, this is how it goes:

Consider the n-blocks for n = 3, 4, 5. In each case use single bit redundancy, meaning that half of the n-blocks are legal codewords and the other half are illegal n-blocks.

For a given n, what is the average dmin across all the possible codes? Dmin is the minimum hamming distance.

For example, for n=2, and using single bit redundancy, there are 6 possible combinations. The dmin(minimum hamming distance) for the 6 possible combinations are 1,1,2,2,1,1, with an average Dmin of 1.333.

To find the dmin average for n=3 is much more difficult, as there are 70 different combinations. For n=4, there are 12,870 combinations. Thus, a program needs to be made to calculate the average minimum hamming distance, or
dmin. Email me or post below!

Thanks!