2.2 Reed-Solomon codes and error correction
Reed–Solomon codes (RS codes) are error-correcting codes invented in 1960 by Irving S. Reed and Gustave Solomon of the Massachusetts Institute of Technology (MIT). They have a wider range of application than EAN-13 codes. Reed-Solomon codes are used in compact disks, Blu-ray disks, DSL broadband, and in many other devices and media.
RS codes are (n, k) block codes (as are EAN-13 codes), but, whereas EAN-13 codes operate on denary digits, the digits of RS codes are bytes. A byte is a group of eight bits, but in the context of RS codes, bytes are thought of as single entities. In the same way that there are ten different possible denary digits (the digits 0 – 9), there are 256 different possible bytes. They are the different possible combinations of eight bits: 00000000, 00000001, 00000010 ... 11111111. So, whereas n and k are the numbers of denary digits for EAN-13 codes (13 and 12 respectively), they are numbers of bytes for RS codes. (In fact the theory of RS codes is very general and can be used with other types of digits, but in practical applications they are used with bytes.)
In RS codes, k bytes of message (referred to as the message digits) have appended to them additional bytes (the check digits) to create a codeword containing a total of n bytes. RS code words are much bigger than EAN-13 code words, and n can be up to 255 (255 bytes).
Activity 2.4 (exploratory)
How many bits are there in a block of 255 bytes?
There are 8 x 255 = 2040 bits
It is not always convenient to use the full block size, and RS codes can be shortened. Conceptually, the block is ‘padded’ with 0s, in other words, some of the message bits are replaced by 0s. Since the decoder knows they are 0s, they do not need to be sent, and so the block size actually used is reduced.
As RS codes are error-correcting codes, the receiver can put right errors. So, if one of the bytes in the message was sent as 01100111, for example, but was received completely differently, such as 10000100, the RS decoder will be able to change it back to the correct value: 01100111. However, error correction can only be done if there are not too many errors.
There are two steps to correcting errors in RS codes:
- Identify which of the digits (bytes) have errors
- Correct those digits.
Both steps involve mathematical procedures. Unlike the procedures used with EAN-13 codes, the maths is done on bytes rather than denary digits, and the theory and methods are much more advanced than those used with EAN-13 for detecting errors. Let’s look at the ‘dimensions’ of the codes and how many errors can be corrected.
RS codes can be designed with differing error-correction ability, depending upon the number of message digits in the block. For a given block size, the more message digits there are, the less redundancy there can be and therefore the fewer errors can be corrected. There will be more details on this trade-off shortly.