Computer Data Recovery

In order to maintain data integrity in unreliable storage media, error detection and correction becomes an important tool. Error detection generally refers to the ability to search out errors that occur during transmission of information from the transmitter to the receiver. After the errors are sorted out reconstruction of the original, unflawed data becomes possible. Data error detection for channel code and error correcting system protocol follows two principles:

 
Automatic repeat-request (ARQ): In this system, the data and the error detection code are sent together by the transmitter. The receiver uses this code to check for errors and thereafter, sends a request for the retransmission of the data containing the error. Within ARQ, this whole process is automatic and the transmission takes place as soon as the receiver sends an acknowledgement (ACK) for proper receipt of data.

Forward error correction (FEC): In this system, the data is first encoded by the transmitter by an error-correcting code (ECC) before it is sent to the receiver. The receiver initiates the decoding process but does not send back any message to the transmitter. What the receiver retrieves is the approximation of the original, non-coded data.  

In order to evade retransmission for minor errors, these two processes are combined. However, when it comes to major errors, requests for retransmissions become mandatory. This combined mechanism is known as hybrid automatic repeat-request.

What are the various error detection schemes?

• The error detection codes send extra bits than the original data contained. This follows a “systematic” process. The transmitter sends a series of original data bits, followed by a series of fixed check bits that owe their origin to the original data only by a deterministic algorithm. This same algorithm is again used by the receiver who makes a comparative analysis of the received data bits and the received check bits. The error detection results when their values are found to be mismatched. There can also be “unsystematic” error detection process. In such codes, the transmitter sends only the data bits transformed as code bits.
• In the Repetition schemes, the stream of data is broken down into blocks of bits that are sent in some previously determined number of times. During the repetition of these bits, similarity between the groups is observed. In case a certain mismatching is found in the series, it is pointed out as an error. However, this process has its own problems and certain types of errors can sometimes render it useless for data error detection.
• A parity scheme belongs to that category of error detection scheme that only takes an odd number of errors into account. When the stream of data is broken down, this system counts the number of 1 bits present in it. The “parity bit” helps to make out whether the number of one bit is odd or even. The error is marked out even when the tested blocks overlap. The shortcoming of parity scheme is that it only applies to the odd number of bit errors and gives the even number errors a miss.
• A little uncommon error detection and correction technique is the polarity scheme. This follows a polarity reversed bitstream process along with the bitstream that is meant for correction. This is only useful for byte or word error detection and correction and is not much effective about detecting bit errors. It may be regarded as the simplest code but not so technically.
• Sometimes an arithmetic sum of message code words is used for error detection and is known as Checksum method. In this, the byte value is determined by the help of the code words of a certain word length and this is stored as an extra code that extends the length of the message. A new checksum is calculated by the receiver when the extended message is received. If this new checksum does not amount to 0, error detection occurs automatically.

How error correction takes place

Error detection and correction are mostly simultaneous processes. There are two main categories of correction, namely convolutional codes and block codes. Most of the correction codes such as Hamming code, BCH code, Reed-Solomon code, Reed-Muller code, Binary Golay code are based on the latter method. These follow Shannon's theorem for error correction. This theorem defines the utmost efficiency of an error-correcting scheme countered by the levels of noise interference.

These methods aim the correction of the decoded stream by putting the redundant information in the data stream. The code rate measures the effectiveness of the coding scheme. The code rate is calculated as the code length divided by the useful information.

Application of error detection and correction techniques   

The Forward Error Correction (FEC) is fitted in the DRAM of computers used in satellites and space research to eliminate soft errors occurring every now and then. The FEC functions by refreshing every part of the memory in every 15 minutes. During this process, the memory controller rereads every word and rewrites them after error detection has been done.

The quality of data storage media is improved by the help of error detection and correction measures. Single bit errors were not only detected but also thoroughly corrected by the aid of magnetic tape data storage. Now checksum method is used for error detection in corrupted data files. Often compact discs are made erroneous due to scratches that are corrected by Reed Solomon error detection procedure.