Results 1 to 1 of 1

Math Help - Expected value of minimum Hamming distance (MHD)

  1. #1
    Newbie
    Joined
    Apr 2012
    From
    lebanon
    Posts
    18

    Expected value of minimum Hamming distance

    The Hamming distance(HD) between two strings of equal length is the number of characters that differ between the two strings at the same position, for example the HD between "gold" and "wolf" is 2; the minimum Hamming distance(MHD) between k strings of same length selected out of N strings is equal to the minimum of the HDs among all possible combinations of size k selected out of N.
    My question is: If I randomly select k binary numbers of length n out of N=2^n numbers, what is the expected value of the minimum Hamming distance between the k selected numbers? I need to find a general formula that gives me the expected value of the MHD from the values of K and N.

    Below is a table that shows, for N=8 and all k's, the MHD plus its occurrences frequency (OF):

    MHD OF
    k=2 k=3 k=4 k=5 k=6 k=7 k=8
    1 12 48 68 56 28 8 1
    2 12 8 2
    3 4

    Below another table for N=16

    MHD OF
    k=2 k=3 k=4 k=5 k=6 k=7 k=8 k=9 .......
    1 32 352 1592 4240 7952 11424 12868 11440
    2 48 208 228 128 56 16 2
    3 32
    4 8


    Appreciate any help, regards.
    Last edited by billobillo; November 19th 2012 at 10:50 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Vectors, Hamming Distance, Coding Theory
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: September 16th 2010, 10:43 PM
  2. Minimum distance
    Posted in the Calculus Forum
    Replies: 11
    Last Post: January 11th 2010, 05:12 AM
  3. minimum distance
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: April 21st 2009, 04:07 PM
  4. Minimum Distance
    Posted in the Geometry Forum
    Replies: 6
    Last Post: October 25th 2007, 02:58 AM
  5. Minimum Distance
    Posted in the Calculus Forum
    Replies: 2
    Last Post: March 14th 2007, 07:40 PM

Search Tags


/mathhelpforum @mathhelpforum