Distance of a code#

A crucial quantity of interest when discussing codes, is their distance. The distance determines the number of errors that can be corrected. Whenever an error occurs on a codeword $\vec{c}$, it creates a corrupted codeword $\vec{\tilde{c}}$ that is at some 'distance' away from the $\vec{c}$. If the distance is small, then it is still possible to correct the error, but if the distance is larger than some value, than the error cannot be corrected. The threshold value is called the distance of the code. We formalize it below.

Hamming distance#

The Hamming distance (not to be confused with the Hamming code; Hamming was just a very prolific scientist) is going to be used to build the notion of code distance.

The Hamming distance between two bit strings $\vec{s},\vec{t}$ is the number of places where they have different symbols. This will be denoted $d_H(s,t)$.

The Hamming distance determines the number of substitutions or errors required to transform a length-$n$ $\vec{s}$ into another length-$n$ vector $\vec{t}$ or vice versa. Hence, it is a very natural definition for our purposes. The Hamming distance can be calculated as \begin{equation} d_H(\vec{s},\vec{t}) = \sum_i \vec{s}_i + \vec{t}_i, \end{equation} where the addition is in the binary field, but the summation is regular integer addition.

For example, the distance between $1011$ and $0111$ is two. You have to flip the first two entries to go from the first to the second or vice versa.

Distance of a code#

Using the above definition, we define the notion of the distance of a code.

The distance $d$ of a code is the minimum Hamming distance between any two codewords. Formally, \begin{equation} d = \min_{\vec{c}_1,\vec{c}_2\in \vecs{C}} d_H(\vec{c}_1,\vec{c}_2). \end{equation}

This seems to be a tedious optimization problem. However, we can simplify the calculation in the following way. First, we define the weight of a bit string.

The weight of a string $\vec{s}$, denoted $wt(\vec{s})$, is the number of ones in the string.

The weight can also be thought of as the Hamming distance of $\vec{s}$ from the all $0$ string, i.e. \begin{equation} wt(\vec{s}) = d_H(\vec{s},0^n). \end{equation}

Next note that the zero message, $\vec{m} = 0^k$, maps to the zero codeword $\vec{c} = 0^kG = 0^n$.

Then, using the properties of the Hamming distance and the fact that the codespace is a vector space, and letting $\vec{c}_1 = \vec{x}_1G \ne \vec{c}_2=\vec{x}_2G$, we have \begin{align} d_H(\vec{c}_1,\vec{c}_2) &= d_H(\vec{x}_1G, \vec{x}_2G), \\ &= d_H(\vec{x}_1G + \vec{x}_2G, 0^k), \\ &= d_H((\vec{x}_1 + \vec{x}_2)G, 0^k), \\ &= d_H(\vec{c}_3, 0^k), \\ &= wt(\vec{c}_3), \end{align} where in the second last step we have defined $\vec{c}_3 = (\vec{x}_1 + \vec{x}_2)G$, which must exist in $C$ because $\vec{x}_1 + \vec{x}_2$ is part of the message space, and $\vec{c}_3 \ne 0$. So we have discovered that the distance of a code, \begin{equation} d = \min_{\vec{c} \in \vecs{C}} wt(\vec{c}), \end{equation} is just the minimum weight string.

Another theorem simplifies the calculation even more.

Theorem: The distance $d$ of a code $\vecs{C}$ is equal to the minimum number of linearly dependent columns of the parity check matrix $H$ of the code.

Relationship of distance and correctable errors#

The use of the distance of a code is given by the following theorem.

Theorem: A code with distance $d$ can

  • Correct at most $d-1$ erasure errors,
  • Detect at most $d-1$ bit flip errors,
  • Correct at most $\left\lfloor \frac{d-1}{2}\right\rfloor$ bit flip errors.

Therefore, a single quantity tells us the power of a code at detecting and correcting various types of errors.

Question: Compute the distance of the $[7,4]$ Hamming code, using both methods outlined above. Show $d = 3$.

If the distance $d$ of a code $\vecs{C}$ is known, then $\vecs{C}$ is denoted as $[n,k,d]$.

Question: Determine the distance $d$ of the $[n,1,d]$ repetition code.