Reed-Solomon error correction codes are widely used in data storage and communication. Unlike an error detection code such as parity checking, cyclic redundancy codes, and hash functions, which simply detect the presence of error(s) in a message (usually resulting in a request to resend it in a data communication system), a forward error correction code, of which Reed-Solomon is an example, allows correcting one or more errors (up to a maximum determined by the redundancy included in the code) in a message without requiring it to be re-transmitted. This is obviously a requirement for applications such as reading data from storage media such as compact discs and digital broadcasting where the receiver has no way to request the corrupted data be sent again. Forward error correction is also widely used in deep space missions where transmission time, due to the finite speed of light, may be measured in minutes or hours.
A forward error correction code requires additional information be sent with the message, which adds to its length, storage requirement, and transmission time, but the overhead is usually much less than, for example, sending duplicate copies of a message. The redundancy added to the message can be varied depending upon the error rate in the channel, and this can even be done dynamically to accommodate changes in the signal to noise ratio of the transmission (for example, as a deep space probe gets further from a ground station on Earth).
Reed-Solomon code, invented in 1960, uses a clever polynomial scheme to detect errors and reconstruct the original message from redundant information included within it. Implemented as computation in a finite field, adding t=n-k check symbols to a message of k symbols to obtain a transmitted block of n symbols, Reed-Solomon code can detect errors in as many as t symbols and completely correct up to \lfloor t/2 \rfloor errors in the block. It doesn’t matter whether the errors are in the message or in the check symbols.
Reed-Solomon codes are used in compact discs, DVD and Blu-ray dscs, QR codes, Wi-Fi transmission, and spacecraft downlinks.