Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm reading a book on Error Correcting Codes, It introduces the concept of Hamming's Distance:

Given two elements $u,v\in A^n$ for some natural number $n$.

$d(u,v)=|\{i;u_i\neq v_i,1\leq i \leq n\}|$

For example in $\{0,1\}^3$ we have;

1) $ d(001,111)=2$

2) $d(000,111)=3$

3) $d(100,110)=1$

With the examples, I understand that it seems to be about the number of spins that is needed for one number to become another, in the first example, we just need to spin the zeroes, so it becomes $111$. My problem the following: Is it really possible to understand this with that definition alone? I've read it a lot of times - ignoring I knew the definition given by the example, I tried to search for the meaning of it in the definition.


My first interpretation: I've read $d(u,v)=|\{i;u_i\neq v_i,1\leq i \leq n\}|$ like this: The distance between $u$ and $v$ is $i$ - and I'm thinking that $i$ is the index of all numbers of $A^n$, so using the example I mentioned before:

$$\begin{matrix} {i}&{}&{}&{}\\ {1}&{0}&{0}&{0}\\ {2}&{0}&{0}&{1}\\ {3}&{0}&{1}&{0}\\ {4}&{0}&{1}&{1}\\ {5}&{1}&{0}&{0}\\ {6}&{1}&{0}&{1}\\ {7}&{1}&{1}&{0}\\ {8}&{1}&{1}&{1} \end{matrix}$$

Then it would be the distance between $i=8$ and $i=2$, but there's a symmetry [$d(u,v)=d(v,u)$] property on the operation, going from $8$ to $2$ would require two jumps, going from $2$ to $8$ would require $6$ jumps. I guess this would make this interpretation plainly wrong, unless perhaps we consider only the minimal distance from both (I guess it's viable, but I still have no proof that it would work - although I feel that it's obvious it would work).


My second interpretation:I've also thought about the number of changes needed for going from one number to the other in the following form: Again, using the first example for going from $001$ to $111$, we need to compare both and ignore the equal part on them, for example:

$$001+111\rightarrow 00\color{red}{1}+11\color{red}{1}\rightarrow 00+X=11$$

And then discover that the sum needed to find $X$ can be found inside $A^2$ which have the following elements: $\{00,01,10,11\}$.

My problem is that the first interpretation seems more close to the definition and also a little incorrect, and the second one seems to be correct but less closer.


  • Bonus Question: My book calls the aforementioned concept of Métrica de Hamming which could be translated (roughly, I suppose) to Hamming's Metric - Is there a problem of using Hamming's Metric instead of Hamming's Distance? I'm confused because I guess this could conflict with the meaning of something in measure theory.
share|improve this question
1  
You seem to have a lingering misunderstanding with set notation. Let's calculate $d(u,v)$ where $n=3$ and $u=(u_1,u_2,u_3)=110$ and $v=(v_1,v_2,v_3)=011$ with the definition. We have $u_1=u_2=1, u_3=0$ and $v_1=0,v_2=v_3=1$. We see that $u_i\neq v_i$ holds when $i=1$ and $i=3$, but does not hold, when $i=2$. Therefore $$\{i: u_i\neq v_i, 1\le i\le 3\}=\{1,3\}.$$ This set has two elements, so $$ d(u,v)=|\{i: u_i\neq v_i, 1\le i\le 3\}|=|\{1,3\}|=2.$$ –  Jyrki Lahtonen Sep 16 '13 at 10:35
1  
Note that in coding theory we write a vector with three bit-components like $110$ instead of $(1,1,0)$ as we would do in linear algebra. This is basically a space saving thing. It is possible to do so without creating confusion, because $1$ and $0$ are the only possible values for a coordinate. This means that you absolutely are not allowed to leave out leading zeros! Something that you might be able to do, if the bit strings represented integers which they might do in e.g. a programming setting. –  Jyrki Lahtonen Sep 16 '13 at 10:41

2 Answers 2

The Hamming distance, or the Hamming metric (means the exact same thing) is the number of bit flips required to change one string $n$ binary bits to another string of $n$ binary bits. In more detail, assuming some fixed value of $n$, strings of $n$ binary bits can be modeled as functions $f:\{1,2,\cdots, n\}\to \{0,1\}$. Then, given two such strings given by $f,g$, then $S=\{1\le i\le n\mid f(i)\ne g(i)\}$ is the set of indices where $f$ and $g$ differ. Then, $d(f,g)=|S|$ is the number of differing bits, and is, by definition, the Hamming distance. It is easy to show that it turns the set of all $n$-length binary strings into a metric space.

share|improve this answer

It's possible to think of Hamming Distance between two strings $i$ and $j$ as the minimum number of single-coordinate changes to $i$ that converts it to $j$. It's just another way of phrasing the number of disagreements.

We can also think of a graph, with the vertex set formed by all possible strings, and an edge from $i$ to $j$ if they disagree at one coordinate. So the Hamming Distance is distance (in the graph theoretical sense) from $i$ to $j$.

There's no distinction between using "Hamming Metric" and "Hamming Distance".

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.