Meaning of distance between two codes in coding theory

Suppose I have been given two codes $x$ and $y$ such that $x = x_1 x_2 . . . .x_m$ and $y = y_1 y_2 . . . .y_m$ where ${x_i} 's$ and ${y_i} 's$ are binary digits. Then we define the concept of distance between $x$ and $y$ as $$\delta (x,y) = |\{ j : x_j \neq y_j \}|$$

i.e. we compare $x$ and $y$ term by term and count how many digits are different at corresponding positions in $x$ and $y$. That count gives the value of distance between $x$ and $y$ .

I am unable to understand the concept of this distance. From above theory I can only understand the way in which distance between two codes is calculated but not what actually a distance between two codes mean ?

5 Answers

If it helps in terms of traditional metrics, this is equivalent to 1-norm (which is sometimes called the taxicab norm), which for $\vec{x},\vec{y} \in \mathbb{R}^n$ is defined as $$\left\|\vec{x} - \vec{y} \right\|_1 = \sum_{j=1}^n \left| x_j - y_j \right|.$$

Note that since you are dealing with binary sequences, $\left| x_j - y_j \right|$ is nonzero when $x_j \ne y_j$, in which case $\left| x_j - y_j \right| = 1....$

The calculation of the "distance" between two codes is pretty literal in that you are simply adding up the number of ways in which the two codes differ. However, I can see how the usage of the word distance can be fairly misleading. You can also think of it as the number of "flips" (0 -> 1 , or 1 -> 0), are required to transform one code into the other.

Normally, the distance measure is used to calculate the minimum of distance of any two code words of one and the same code. It is a measure of how well errors in transmitted code words can be detected/corrected.

Interpretation

The distance between two codewords is the number of positions in which the codewords differ.

Example

The codewords 11000011 and 11010010 differ in two positions (No. 4 and 8), so their distance is 2.

• Thanks. The interpretation(how we are calculating the distance) is clear to me. I am just asking what does it mean? Apr 7, 2016 at 14:30

You interpret it to mean how "far apart" the codewords are. In this measurement of distance, they are far apart if you have to change a lot of the symbols in order to change one codeword into the other.