19.2: Error-Correcting Codes

In order to be able to correct errors in transmission, we agree to send only strings that are in a certain set \(\mathcal{C}\) of codewords. (So the information we wish to send will need to be “encoded” as one of the codewords.) In our above examples, \(\mathcal{C}\) was

• the set of all words of length \(5\) that have an even number of \(1\)s, or
• the set of words of length \(12\) that consist of four strings of three equal bits.

The set \(\mathcal{C}\) is called a code. Choosing the code cleverly will enable us to successfully correct transmission errors.

When a transmission is received, the recipient will assume that the sender transmitted the codeword that is “closest” to the string that was received. For example, if \(\mathcal{C}\) were the set of \(5\)-letter words in the English language, and the string “fruiz” were received, then the recipient would assume (presumably correctly), that the sender transmitted the word “fruit,” because that is only off by one letter. (This is how we ordinarily deal with the typographical errors that we encounter.)

By the “closest” codeword, we mean the codeword at the smallest distance, in the following sense:

Definition: Hamming Distance

Suppose \(x\) and \(y\) are two bit strings of the same length. The Hamming distance from \(x\) to \(y\) (denoted \(d(x, y)\)) is the number of bits in which they differ.

Example \(\PageIndex{1}\)

For clarity, we underline the bits in the second string that differ from the corresponding bit in the first string:

• \(d(11111, 11101) = 1\)
• \(d(11100, 01001) = 3\)
• \(d(10101, 01010) = 5\)
• \(d(10101, 10101) = 0\)

Note

When two bits are “transposed” (or “switched”), meaning that a string \(01\) gets changed to \(10\) (or vice-versa), this counts as two bits being different because a \(0\) is changed to a \(1\) and a \(1\) is changed to a \(0\), even though you might think of the switch as being only a single operation.

Exercise \(\PageIndex{1}\)

Compute the Hamming distance between the following pairs of words: \(\{110, 011\}\), \(\{000, 010\}\), \(\{\text{brats }, \text{ grass}\}\), \(\{11101, 00111\}\).

Exercise \(\PageIndex{2}\)

Find each of the following:

1) an English word whose Hamming distance from “math” is \(0\);

2) an English word whose Hamming distance from “math” is \(1\);

3) an English word whose Hamming distance from “math” is \(2\);

4) an English word whose Hamming distance from “math” is \(3\).

5) Can you find more than one of each?

The Hamming distance satisfies the axioms of a “metric” or “distance function:”

Exercise \(\PageIndex{3}\)

Prove that the Hamming function satisfies each of the following properties, which define a metric.

Let \(x\), \(y\), and \(z\) be words of the same length. Then:

1) \(d(x, y) ≥ 0\).

2) \(d(x, y) = 0 \Longleftrightarrow x = y\).

3) \(d(x, y) = d(y, x)\).

4) \(d(x, z) ≤ d(x, y) + d(y, z)\).

Note

Part (4) of the Exercise 19.2.3 is called the triangle inequality because it says that the length of one side of a triangle is always less than (or equal to) the sum of the lengths of the other two sides.

Definition: Minimum Distance

The minimum distance of a code \(\mathcal{C}\) (denoted \(d(\mathcal{C})\)) is the smallest Hamming distance between two distinct elements of \(\mathcal{C}\).

Example \(\PageIndex{2}\)

1. \(d (\{10, 010, 011\}) = 1\) (because \(d(010, 011) = 1\)).
2. \(d (\{000, 011, 101, 110\}) = 2\).
3. \(d (\{10001, 11111\}) = 3\).

Exercise \(\PageIndex{4}\)

What is the minimum distance of each of the following codes?

1) \(\{\text{tell}, \text{ tale},\text{ sale}, \text{ date}\}\)

2) \(\{\text{mon }, \text{ tue}, \text{ wed}, \text{ thu}, \text{ fri}, \text{ sat}, \text{ sun}\}\)

3) \(\{00000, 01011, 10101, 10110, 10011\}\)

Making the minimum distance of a code \(\mathcal{C}\) large is the key to ensuring that it can detect (or correct) large errors. We will make this idea very explicit in our next two results.

Theorem \(\PageIndex{1}\)

A code \(\mathcal{C}\) can detect all possible errors affecting at most \(k\) bits if and only \(d(C) > k\).

Proof

We will prove the contrapositive:

\(d(C) ≤ k \Longleftrightarrow \) there exists an error that cannot be detected, and affects only \(k\) (or fewer) bits.

\((⇐)\) Suppose there is a situation in which:

• a codeword \(x\) is sent,
• a message \(y\) is received,
• with only \(k\) incorrect bits, and
• the receiver does not realize that there were any errors.

Since the receiver did not realize there were any errors, the message that was received must be a codeword. In other words, \(y ∈ C\). Since there are \(k\) errors in the received message, we also know that \(d(x, y) = k\). Since \(x\), \(y ∈ C\), this implies \(d(C) ≤ k\).

\((⇒)\) By assumption, there exist \(x\), \(y ∈ C\) with \(x \neq y\), but \(d(x, y) ≤ k\). Now, suppose codeword \(x\) is sent. Since \(d(x, y) ≤ k\), changing \(k\) (or fewer) bits can change \(x\) to \(y\), so \(y\) can be the message that is received, even if errors in transmission affect only \(k\) bits. Since \(y ∈ C\), the recipient does not realize an error was made, and assumes that \(y\) was the intended message. So the \(k\) (or fewer) errors were not detected.

Although a minimum distance of \(k\) allows us to detect errors that affect at most \(k\) bits, it isn’t sufficient to allow us to correct all such errors. For the purposes of correcting errors, we require the minimum distance to be twice this large.

Theorem \(\PageIndex{2}\)

A code \(\mathcal{C}\) can correct all possible errors affecting at most \(k\) bits if and only \(d(\mathcal{C}) > 2k\).

Proof

We will prove the contrapositive:

\(d(\mathcal{C}) ≤ 2k \Longleftrightarrow \text{ there exists an error that is not properly corrected, and affects only \(2k\) (or fewer) bits. } \)

\((⇐)\) Suppose there is a situation in which:

• a codeword \(x\) is sent,
• a message \(y\) is received,
• with only \(2k\) incorrect bits, and
• the receiver decodes the message incorrectly, as some codeword \(z \neq x\).

It must be the case that \(z\) is the closest codeword to \(y\) (or, at least, it ties for being the closest), so \(d(z, y) ≤ d(x, y) = k\). Then, using Exercise 19.2.3, we have

\[d(x, z) ≤ d(x, y) + d(y, z) = d(x, y) + d(z, y) ≤ k + k = 2k.\]

So \(d(C) ≤ 2k\) (because \(x\), \(z ∈ C\)).

\((⇒)\) By assumption, there exist \(x\), \(y ∈ C\) with \(x \neq y\), but \(d(x, y) ≤ 2k\). Let \(r = \lceil \dfrac{d(x, y)}{2e} \rceil ≤ \lceil \dfrac{2k}{2e} \rceil = k\). (In other words, \(r\) is obtained by rounding \(\dfrac{d(x, y)}{2}\) up to the nearest integer.)

Now suppose codeword \(x\) is sent. Since \(d(x, y) ≤ 2k\), the message \(y\) could be received, with no more than \(2k\) incorrect bits. Construct \(z\) from \(x\) by changing only \(r\) of the \(d(x, y)\) bits that are incorrect in \(y\), so

\[d(x, z) = r \text{ and } d(z, y) = d(x, y) − r.\]

By the definition of \(r\), we have \(r ≤ d(x, y) ≤ 2r\), so

\[d(z, y) = d(x, y) − r ≤ 2r − r = r ≤ d(x, y).\]

Therefore \(z\) is at least as close to \(y\) as \(x\) is, so the recipient has no way of knowing that \(x\) is the message that was sent. So it was not possible to correct the \(2k\) (or fewer) errors.

Exercise \(\PageIndex{5}\)

1) Suppose that a code \(C\) has a minimum distance of \(7\).

(a) How many errors can it detect?

(b) How many errors can it correct?

2) Suppose that a code \(C\) has a minimum distance of \(6\).

(a) How many errors can it detect?

(b) How many errors can it correct?

Exercise \(\PageIndex{6}\)

Let \(\mathbb{B}^n\) represent the set of binary strings of length \(n\). Prove that a code from \(\mathbb{B}^{10}\) that has more than \(2\) words, cannot correct \(3\) errors. Hypothesize a generalisation of this result to codes on \(\mathbb{B}^n\) with more than \(2\) words.