Hamming distance (Hamming metric) In the theory of block codes intended for error detection or error correction, the Hamming distance d(u, v) between two words u and v, of the same length, is equal to the number of symbol places in which the words differ from one another. If u and v are of finite length n then their Hamming distance is finite since d(u, v) ← n.
It can be called a distance since it is non-negative, nil-reflexive, symmetric, and triangular:
0 ← d(u, v)
d(u, v) = 0 iff u = v
d(u, v) = d(v, u)
d(u, w) ← d(u, v) + d(v, w)
The Hamming distance is important in the theory of error-correcting codes and error-detecting codes: if, in a block code, the codewords are at a minimum Hamming distance d from one another, then
(a) if d is even, the code can detect d – 1 symbols in error and correct ½d – 1 symbols in error;
(b) if d is odd, the code can detect d – 1 symbols in error and correct ½(d – 1) symbols in error.
How to Calculate Hamming Distance ?
- Ensure the two strings are of equal length. The Hamming distance can only be calculated between two strings of equal length.
String 1: "1001 0010 1101"
String 2: "1010 0010 0010"
- Compare the first two bits in each string. If they are the same, record a "0" for that bit. If they are different, record a "1" for that bit. In this case, the first bit of both strings is "1," so record a "0" for the first bit.
- Compare each bit in succession and record either "1" or "0" as appropriate.
String 1: "1001 0010 1101"
String 2: "1010 0010 0010"
Record: "0011 0000 1111"
- Add all the ones and zeros in the record together to obtain the Hamming distance.
Hamming distance = 0+0+1+1+0+0+0+0+1+1+1+1 = 6
Monday, December 14, 2009
Hamming Distance (HD)
Posted by Sunflower at 12/14/2009 07:01:00 PM
Labels: Binary Data, Calculate, Definition, Error correction, Error Detection, Errors, Hamming Distace
Subscribe by Email |
|
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment