Concepts and implementation ideas of error detection and correction-EEWORLD

Collect

Errors may occur during the processing, access and transmission of data in a computer system. In order to reduce and avoid such errors, on the one hand, various circuits should be carefully selected, production processes and testing methods should be improved, and the reliability of computer hardware itself should be improved as much as possible; on the other hand, a solution should be found in data coding, that is, a coding method with certain characteristic capabilities should be adopted, and a small amount of additional circuits should be used to enable it to detect certain errors, and even accurately determine the error location, thereby providing the ability to automatically correct errors.

Data checksum is a commonly used data coding method with the ability to detect certain errors and even with a certain automatic error correction capability. Its implementation principle is to add some (illegal) codes that are not allowed to appear between legal data codes, so that when certain errors occur in legal data codes, they become illegal codes. In this way, the purpose of detecting errors can be achieved by checking the legality of the codes. By rationally designing coding rules and arranging the number of legal and illegal codes, the ability to detect errors can be obtained, and even the purpose of automatically correcting errors can be achieved. The concept of code distance (minimum code distance) is used here. The code distance refers to the number of binary bits that are different between any two legal codes. If only one bit is different, it is called the (minimum code distance) of 1. For example, if four bits of binary are used to represent 16 states, all 16 codes are used. In this case, the code distance is 1. That is to say, if one or more bits of the four-bit code of any coding state are wrong, it will become another legal code, and there is no error detection capability at this time. If four bits are used to represent 8 legal states, only 8 of them can be used to represent them, and the other 8 codes can be used as illegal codes. In this case, the code distance of the legal code can be 2. Generally speaking, the ability to detect errors can be improved by reasonably increasing the code distance, but the number of binary bits used to represent a certain number of legal codes will increase, which increases the complexity of electronic circuits and the amount of data storage and data transmission. When determining and using data check codes, it is usually necessary to consider finding as many errors as possible without increasing hardware overhead, and even automatically correcting some of the most common errors. Commonly used data check codes are parity check codes, Hamming check codes, cyclic redundancy check codes, etc. Error correction coding is a further development and application of error detection coding.

There are two main types of errors that are often encountered in computers: random errors and burst errors. The former refers to an isolated error, while the latter refers to a group of errors that occur continuously (and may be related to each other). The difficulty and complexity of handling them will be very different. In our course, we basically do not involve the inspection and correction of burst errors. Those who are interested can refer to the relevant materials by themselves. The classification scheme of error correction coding is given in Figure 2.1.