6
$\begingroup$

The Hamming distance satisfies the triangle inequality that is for all $x,y,u$ in $c$ such that $d(x,y) \le d(x,u) + d(u,y)$ where $c$ is a code. Also when does the equality hold?

My approach is: turn $x$ to $u$ by changing at most $d(x,u)$ letters and turn $u$ to $y$ by changing at most $d(u,y)$ letters. So turning $x$ to $t$ will change no more than $d(x,u) + d(u,y)$ letters.

By looking at the following example, $x = 001111, \ y = 111111, \ z = 011111$, the equality holds when changing $x$ to $y$, $z$ is just an intermediate step.

Does this make sense?

$\endgroup$
6
$\begingroup$

It’s a good intuition, but some work is needed in order to translate it into a proof. For $x\in C$ assume that $x=x_1\ldots x_n$. For $x,y\in C$ let $D(x,y)=\{k:x_k\ne y_k\}$; then by definition $d(x,y)=|D(x,y)|$.

Now suppose that $x,y,z\in C$. Then

$$D(x,y)=D(x,z)\mathrel{\triangle}D(z,y)\subseteq D(x,z)\cup D(z,y)\;,$$

where $\triangle$ denotes the symmetric difference, and therefore

$$d(x,y)=|D(x,y)|\le|D(x,z)\cup D(z,y)|\le|D(x,z)|+|D(z,y)|=d(x,z)+d(z,y)\;.$$

The equality $D(x,y)=D(x,z)\mathrel{\triangle}D(z,y)$ is really just your observation that to get from $x$ to $y$, we can first flip the bits in $D(x,z)$ to get from $x$ to $z$ and then flip the bits in $D(z,y)$ to get from $z$ to $y$. The bits that are affected by at least one stage of this process are those in $D(x,z)\cup D(z,y)$, and those that are affected by both stages are those in $D(x,z)\cap D(z,y)$. Thus $D(x,y)$, the set of bits that are actually changed in going from $x$ to $y$ by way of $z$ are those in

$$\big(D(x,z)\cup D(z,y)\big)\setminus\big(D(x,z)\cap D(z,y)\big)=D(x,z)\mathrel{\triangle}D(z,y)\;.$$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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