Hamming distance

Discussion in 'VHDL' started by Niv, Jan 19, 2006.

  1. Niv

    Niv Guest

    I have to generate some unique codes of 16 bits length, but each code
    must be at least differnt by 5 bits from any other code.

    Now there are 65536 possible 16 bit codes, but what is the maximal
    number of codes with 5 bit differences; I'm assuming, possibly
    incorrectly, it'll vary depending on the seed code used.

    i.e. "000000000000000" could be used as seed, then next code could be
    "0000000000011111" etc etc.

    I could perhaps write a programme to generate a sequence of
    incrementing code, testing for 5 bit differences against all previously
    generated codes, and counting how many I get, then loop back and
    increment the start value.

    This seems like a fairly useful algorithm; length N bits, M bit
    differences, maximal sequence length to be found.

    Has anyone got a pointer to somethingalready done please to save me
    some time.

    (I guess it fairly simple to write a process to fill arrays with codes
    of 5 bit diffs, count the number of codes and then increment the seed
    and see if more codes are generated & then update the filled array if
    so.
     
    Niv, Jan 19, 2006
    #1
    1. Advertising

  2. On 19 Jan 2006 07:47:16 -0800, "Niv" <> wrote:

    >I have to generate some unique codes of 16 bits length, but each code
    >must be at least differnt by 5 bits from any other code.
    >
    >Now there are 65536 possible 16 bit codes, but what is the maximal
    >number of codes with 5 bit differences; I'm assuming, possibly
    >incorrectly, it'll vary depending on the seed code used.
    >
    >i.e. "000000000000000" could be used as seed, then next code could be
    >"0000000000011111" etc etc.


    Since there are only 2^16 codes to test, I would use a sieve, like
    "Sieve of Eratosthenes" but testing for Hamming distance instead of
    primeness.

    Start by testing (and eliminating) every number for distance against
    X"0000". Then test every remaining number for distance against the
    lowest number which remains in the sieve. And so on.
    Two nested loops, but the outer loops get faster as the sieve gets
    sparser.

    - Brian
     
    Brian Drummond, Jan 23, 2006
    #2
    1. Advertising

  3. Niv

    Ben Jones Guest

    "Niv" <> wrote in message
    news:...
    > I have to generate some unique codes of 16 bits length, but each code
    > must be at least differnt by 5 bits from any other code.
    >
    > Now there are 65536 possible 16 bit codes, but what is the maximal
    > number of codes with 5 bit differences; I'm assuming, possibly
    > incorrectly, it'll vary depending on the seed code used.


    Your assumption is indeed incorrect. The seed code is irrelevant, because
    the code is linear.

    To see why:

    The Hamming distance between two words is the number of bits in which those
    words differ. The "difference" function is just logical XOR, e.g.

    01001
    xor 11010
    -------
    10011

    Those two words differ in bits 0, 1 and 4. So bitcount(A xor B) gives you
    the Hamming distance.

    Now repeat the calculation above, but first flip bit 0 in both words:

    01000
    xor 11011
    -------
    10011

    Same answer. If you do the same flip(s) in both words, they will be "just as
    different" as they were before you flipped any bits, because the flips
    cancel out. It doesn't matter how many bits you flip or where they are, the
    result is the same. (Note that flipping arbitrary bits is exactly the same
    as XORing with an arbitrary word.)

    What does this means for you? Say you have a code set that was based on the
    seed code of "0100101001011101". This set is exactly equivalent to a set
    based on the seed code of "0000000000000000". All you have to do to obtain
    this set is XOR every code word with "0100101001011101". Now, since every
    code set can be reduced to one containing the all-zero code word, they must
    all be the *same* set. So, you only need to invesetigate starting from
    all-zeroes, and you are still guaranteed to find the optimum solution.

    Hope that helps.

    Cheers,

    -Ben-
     
    Ben Jones, Jan 23, 2006
    #3
  4. Niv

    Eric Smith Guest

    Niv wrote:
    > I have to generate some unique codes of 16 bits length, but each code
    > must be at least differnt by 5 bits from any other code.


    Brian Drummond wrote:
    > Since there are only 2^16 codes to test, I would use a sieve, like
    > "Sieve of Eratosthenes" but testing for Hamming distance instead of
    > primeness.


    As it happens, I have a C program that does that. I dusted it off and put
    it on my web site:
    http://www.brouhaha.com/~eric/software/hamming/

    In addition to the source code, there's a file giving the 256 16-bit
    codes with a minimum distance of 5. Thus this code could be used to
    detect all three-bit errors in eight bits of data, and correct all
    single- and two-bit errors.
     
    Eric Smith, Jan 23, 2006
    #4
  5. Eric Smith <> writes:

    > Niv wrote:
    >> I have to generate some unique codes of 16 bits length, but each code
    >> must be at least differnt by 5 bits from any other code.

    >
    > Brian Drummond wrote:
    >> Since there are only 2^16 codes to test, I would use a sieve, like
    >> "Sieve of Eratosthenes" but testing for Hamming distance instead of
    >> primeness.

    >
    > As it happens, I have a C program that does that. I dusted it off and put
    > it on my web site:
    > http://www.brouhaha.com/~eric/software/hamming/
    >
    > In addition to the source code, there's a file giving the 256 16-bit
    > codes with a minimum distance of 5. Thus this code could be used to
    > detect all three-bit errors in eight bits of data, and correct all


    Shouldn't that be 4-bit errors? As I recall d_min > t+1 for detection,
    and d_min > 2t+1 for corrections.

    > single- and two-bit errors.



    Kai
    --
    Kai Harrekilde-Petersen <khp(at)harrekilde(dot)dk>
     
    Kai Harrekilde-Petersen, Jan 23, 2006
    #5
  6. Niv

    Eric Smith Guest

    Niv wrote:
    > I have to generate some unique codes of 16 bits length, but each code
    > must be at least differnt by 5 bits from any other code.
    >
    > Now there are 65536 possible 16 bit codes, but what is the maximal
    > number of codes with 5 bit differences;


    Conjecture:

    For an n-bit code (n >= 4) with minimum distance d (1 <= d < n/2),
    if d is odd there are 2^(n+2-2*d) codes, and if d is even there
    are 2^(n+3-2*d) codes.
     
    Eric Smith, Jan 24, 2006
    #6
  7. Niv

    Niv Guest

    Thanks Eric, I'll try & run your prog,or just the values provided.

    Niv.
     
    Niv, Jan 24, 2006
    #7
  8. Niv

    Eric Smith Guest

    I wrote:
    > In addition to the source code, there's a file giving the 256 16-bit
    > codes with a minimum distance of 5. Thus this code could be used to
    > detect all three-bit errors in eight bits of data, and correct all


    Kai Harrekilde-Petersen wrote:
    > Shouldn't that be 4-bit errors?


    Yes, my mistake.

    > As I recall d_min > t+1 for detection, and d_min > 2t+1 for corrections.


    d_min > t for detection of up to t bits in error
    d_min > 2t for correction of up to t bits in error
     
    Eric Smith, Jan 25, 2006
    #8
  9. Eric Smith <> writes:

    > I wrote:
    >> In addition to the source code, there's a file giving the 256 16-bit
    >> codes with a minimum distance of 5. Thus this code could be used to
    >> detect all three-bit errors in eight bits of data, and correct all

    >
    > Kai Harrekilde-Petersen wrote:
    >> Shouldn't that be 4-bit errors?

    >
    > Yes, my mistake.
    >
    >> As I recall d_min > t+1 for detection, and d_min > 2t+1 for corrections.

    >
    > d_min > t for detection of up to t bits in error
    > d_min > 2t for correction of up to t bits in error


    And now that was my mistake :) I should have written >= instead of >.


    Kai
    --
    Kai Harrekilde-Petersen <khp(at)harrekilde(dot)dk>
     
    Kai Harrekilde-Petersen, Jan 25, 2006
    #9
  10. Niv

    adyshon

    Joined:
    Jan 19, 2011
    Messages:
    1
    vhdl hamming encoder-need hellp with modelsim

    Hello all.
    i need some hellp with implementing a vhdl source code for a hamming encoder,for simulating in modelsim.it was given to me a schematic ,but i have no ideea abut nothing.it is for an exam.ps hellp me ..thx all...this is my yahoo mess id : ady24_2008
     
    adyshon, Jan 19, 2011
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. LabWINC

    Low Pass Hamming filter design

    LabWINC, Mar 30, 2006, in forum: Python
    Replies:
    2
    Views:
    1,380
    Robert Kern
    Mar 31, 2006
  2. jaysome

    C Unleashed Chapter 18: Hamming Codes

    jaysome, Dec 18, 2007, in forum: C Programming
    Replies:
    2
    Views:
    486
    Richard Heathfield
    Dec 18, 2007
  3. godavemon

    Hamming Distance

    godavemon, Jun 20, 2008, in forum: Python
    Replies:
    8
    Views:
    522
    godavemon
    Jun 20, 2008
  4. Hamming Distance

    , Mar 16, 2010, in forum: Java
    Replies:
    7
    Views:
    817
    Roedy Green
    Mar 17, 2010
  5. Martin Hansen

    Hamming Distance

    Martin Hansen, Mar 7, 2011, in forum: Ruby
    Replies:
    4
    Views:
    404
Loading...

Share This Page