A maximum distance separable code, or MDS code, is a way of encoding data so that the distance between code words is as large as possible for a given data capacity. This post will explain what that means and give examples of MDS codes.

## Notation

A linear block code takes a sequence of *k* symbols and encodes it as a sequence of *n* symbols. These symbols come from an alphabet of size *q*. For binary codes, *q* = 2. But for non-trivial MDS codes, *q* > 2. More on that below.

The purpose of these codes is to increase the ability to detect and correct transmission errors while not adding more overhead than necessary. Clearly *n* must be bigger than *k*, but the overhead *n-k* has to pay for itself in terms of the error detection and correction capability it provides.

The ability of a code to detect and correct errors is measured by *d*, the minimum distance between code words. A code has separation distance *d* if every pair of code words differs in at least *d* positions. Such a code can detect up to *d* errors per block and can correct ⌊(*d*-1)/2⌋ errors.

### Example

The following example is not an MDS code but it illustrates the notation above.

The extended Golay code used to send back photos from the Voyager missions has *q* = 2 and [*n*, *k*, *d*] = [24, 12, 8]. That is, data is divided into segments of 12 bits and encoded as 24 bits in such a way that all code blocks differ in at least 8 positions. This allows up to 8 bit flips per block to be detected, and up to 3 bit flips per block to be corrected.

(If 4 bits were corrupted, the result could be equally distant between two valid code words, so the error could be detected but not corrected with certainty.)

## Separation bound

There is a theorem that says that for any linear code

*k* + *d* ≤ *n* + 1.

This is known as the singleton bound. MDS codes are optimal with respect to this bound. That is,

*k* + *d* = *n* + 1.

So MDS codes are optimal with respect to the singleton bound, analogous to how perfect codes are optimal with respect to the Hamming bound. There is a classification theorem that says perfect codes are either Hamming codes or trivial with one exception. There is something similar for MDS codes.

## Classification

MDS codes are essentially either **Reed-Solomon codes** or trivial. This classification is not as precise as the analogous classification of perfect codes. There are variations on Reed-Solomon codes that are also MDS codes. As far as I know, this accounts for all the *known* MDS codes. I don’t know that any others have been found, or that anyone has proved that there are no more.

### Trivial MDS codes

What are these trivial codes? They are the codes with 0 or 1 added symbols, and the duals of these codes. (The dual of an MDS code is always an MDS code.)

If you do no encoding, i.e. take *k* symbols and encode them as *k* symbols, then* d* = 1 because different code words may only differ in one symbol. In this case *n* = *k* and so *k* + *d* = *n* + 1, i.e. the singleton bound is exact.

You could take *k* data symbols and add a checksum. If *q* = 2 this would be a parity bit. For a larger alphabet of symbols, it could be the sum of the *k* data symbols mod *q*. Then if two messages differ in 1 symbol, they also differ in added checksum symbol, so *d* = 2. We have *n* = *k* + 1 and so again *k* + *d* = *n* + 1.

The dual of the code that does no encoding is the code that transmits no information! It has only one code word of size *n*. You could say, vacuously, that *d* = *n* because any two different code words differ in all *n* positions. There’s only one code word so *k* = 1. And again *k* + *d* = *n* + 1.

The dual of the checksum code is the code that repeats a single data symbol *n* times. Then *d* = *n* because different code words differ in all *n* positions. We have *k* = 1 since there is only one information symbol per block, and so *k* + *d* = *n* + 1.

## Reed Solomon codes

So the stars of the MDS show are the Reed-Solomon codes. I haven’t said how to construct these codes because that deserves a post of its own. Maybe another time. For now I’ll just say a little about how they are used in application.

As mentioned above, the Voyager probes used a Golay code to send back images. However, after leaving Saturn the onboard software was updated to use Reed-Solomon encoding. Reed-Solomon codes are used in more down-to-earth applications such as DVDs and cloud data storage.

Reed-Solomon codes are optimal block codes in terms of the singleton bound, but block codes are not optimal in terms of Shannon’s theorem. **LDPC** (low density parity check) codes come closer to the Shannon limit, but some forms of LDPC encoding use Reed-Solomon codes as a component. So in addition to their direct use, Reed-Solomon codes have found use as building blocks for other encoding schemes.