|
BURST ERRORS AND REED SOLOMON CODES The Beginning Irving S Reed and Gustave Solomon introduced Reed Solomon codes in 1960. At that time, hardware technology wasnt powerful enough to efficiently use these codes. When technology did become powerful enough a few years later, an efficient and revolutionary decoding algorithm for these codes, developed by Elwyn Berlekamp (1968), was available for implementation. J L Massey (1969) simplified the algorithm and its proof. Practical Applications Reed-Solomon codes are omnipresent these days. Computer hard disks, digital TVs, digital audio tapes, CD drives, cable TV and other digital imaging systems all use Reed-Solomon codes to maintain data integrity. NASA used RS codes to successfully transmit the spectacular pictures of the outer planets sent back by Voyager II. Considering that Voyager II was transmitting these messages over hundreds of millions of kilometres, and at very low power - almost like a faint whisper (and that too with cosmic noise all around), it is a stunning tribute to the utility of Reed-Solomon codes and the Berlekamp-Massey decoding algorithm that they were still able to provide us with those spectacular pictures. Burst Errors If the errors occur in consecutive symbols, they are called burst errors. Scratches or fingerprints on a CD affect consecutive blocks of data causing burst errors (or erasures). Since Reed Solomon codes tackle not individual bits of data, but whole blocks of data, they are particularly suited to handling burst errors. Current implementations of RS codes in CD technology are able to cope with error bursts as long as thousands of consecutive bits. Scratches (up to a few mm long) do not affect output of the data or the quality of music. You could even drill holes in a CD and still play the music! Reed Solomon Codes A Reed-Solomon code which (encodes &) transmits a message of length k as a message of length n is called a (n,k) RS code. The symbols in the message are members of a finite field of order n + 1. For example, a (255,223) RS code encodes a message string of 223 elements of a field (of order 256; hence each symbol could be a byte), by adding 32 parity check symbols. It can be easily proved that an (n, k) RS code has minimum distance 2t + 1 where n - k = 2t. Thus it can correct up to t errors.
Copyright © 2022 ICICI Centre for Mathematical Sciences |
