A survey of error-correcting codes for computer applications.
Dhriti Kapur · 1976
The thesis presents an investigative survey of Error-Correcting Codes suitable for application in computer environment. Errorcorrecting codes have been successfully utilized to improve reliability in transmitting information in communication systems. In recent years the phenomenol increase in information handled by digital computers has enhanced the need for computer system reliability. In the survey with respect to error-correction the overall computer system has been broadly classified into three sections, • namely the computer memory system, the computer peripheral system and the central processing unit. Each section is discussed under a separate heading. Error-correcting codes used in computer memory systems depend upon the configuration of memory. For those memories which are packaged on single bit per card basis, single error-correcting, double error-detecting Hamming type codes, double error-correcting, triple error-detecting BCH codes, and one step majority decodable codes play a useful role in increasing the reliability of memory. Byte error-correcting codes form the basis of correcting errors in memories configured as multiple bit per card. A general class of maximal codes was developed by Hong and Patel whose structure is not restricted to any homogeneous bit per card arrangement and is capable of correcting single random byte errors. Cyclic codes formed the basis of the error-correcting scheme -1in magnetic tape and disc drives which are part of the computer peripheral system. Cyclic Redundancy Code CCRC) and the Orthogonal Rectangular Code (ORC) were found applicable to magnetic tape units. In magnetic disc systems Fire codes with high speed decoding could be used for single channel. Recently Malhotra and Fisher have come up with a practical error-correcting scheme for multichannel disc systems. Reed-Solomon codes were best suited for photodigital mass storage systems. The decoding scheme employed a hybrid hardware-software technique to simplify the complexity of decoding the multiple character correcting code. v In the processing unit of the computer the error-correcting codes used are arithmetic codes. The best known among these which are suitable for computer arithmetic as well as easily implementable are the residue codes. The Biresidue code proposed by Rao involved circuit redundancy of the magnitude of 30-35 percent of the main processor which is definitely more economical than duplicating redundant schemes like Triple Modular Redundancy. A desirable feature of the error-correcting codes used in computer systems is the fast and simple encoding and decoding procedure. To ensure efficient operation the speed of implementation of the code must be comparable to the speed of operation of the computer system. Most of the codes surveyed in this thesis have been found suitable in computer environment with existing trade-off betweenredundancy and decoding time. -2CHAPTER