Parity check

Basic introduction

How it works

In order to detect and correct memory soft errors, the first thing that appears is memory "parity". The smallest unit in the memory is a bit, which is also called a "bit". There are only two states of a bit that are marked with 1 and 0 respectively. Every 8 consecutive bits are called a byte. The memory without parity has only 8 bits per byte. If one of its bits stores an incorrect value, it will cause the corresponding data stored in it to change, which in turn leads to errors in the application. The parity check is to add another bit as an error detection bit in addition to each byte (8 bits). After storing data in a byte, the data stored in its 8 bits is fixed, because the bits can only have two states 1 or 0. Assuming that the stored data is marked as 1, 1, 1, 0, 0, 1, 0, 1, then add each bit (1+1+1+0+0+1+0+1=5), and the result is an odd number. For even parity, the parity bit is defined as 1; for odd parity, the opposite is true. When the CPU reads the stored data, it will add the data stored in the first 8 bits again, and the calculation result is consistent with the check digit. As a result, memory errors can be detected to a certain extent. Parity can only detect errors but cannot correct them. At the same time, although the probability of double-bit errors occurring at the same time is quite low, parity cannot detect double-bit errors.

Advantages and disadvantages

There are two types of parity: odd and even. The parity bit is a binary number that indicates that the number of 1 in the binary number of a given location is odd or even. The parity bit is the simplest error detection code. If an odd number of data bits including the parity bit is changed during the transmission, the parity bit will be wrong, indicating that an error has occurred during the transmission. Therefore, the parity bit is an error detection code, but since there is no way to determine which bit is in error, it cannot perform error correction. When an error occurs, you must throw away all the data, and then transfer the data from the beginning. It may take a long time to successfully transmit data on a noisy medium, or even impossible at all. But the parity bit also has its advantages. It is the best check code that can be achieved with one bit of data, and it only needs some XOR gates to generate it. Parity check is widely used.

Supervision code

The parity supervision code is a simple and widely used method to increase the minimum distance of a binary transmission system. For example, a single parity supervision will increase the minimum distance of the code from one to two.

A binary codeword, if its code element has an odd number of ones, it is called singularity. For example, the codeword "1011010111" has seven ones, so this codeword has singularity. Similarly, even codewords have an even number of ones. Note that singularity detection is equivalent to modulo two addition of all symbols, and can be determined by the exclusive OR operation of all symbols. For an n-bit word, singularity is given by formula (8-1):

singularity=a0⊕a1⊕a2⊕…⊕an(8-1)

very Obviously, in the same way, we can also construct parity supervision based on the number of zeros in each codeword.

A single parity supervision code can be described as: add a supervision bit to each codeword and use it to form odd or even supervision. For example, in Figure 8-2, this is done for binary codes. It can be seen that the additional symbol d2 is simply selected to make each word even. Therefore, if one symbol is wrong, it can be distinguished because the parity supervision will become odd.

In a typical system, the parity generator adds parity supervision bits to each word before transmission. The numbers in the original information are detected in the receiver. If there is no correct odd or even, the information is calibrated as wrong, and the system will discard the wrong words or request a retransmission. Note that with a single parity supervision code, only odd-numbered symbol errors can be detected.

For example, consider the singularity supervision code in Figure 8-4. Add the odd and even supervision bits to an 8-4-2-1BCD code to enable odd supervision (turning all supervision bits in turn will generate even supervision codes). It can be seen that if the odd number of code elements in any code word is reversed, it will become an even code. Therefore, invalid words can be distinguished. However, if two or four symbols are reversed, then the parity supervision will still be an odd code, and the word is considered correct. Only when the probability of two errors appearing in a given word at the same time is ignored, a single parity supervision is effective. In fact, the odd supervision code is preferable to the even supervision code because it excludes the transmission of all zeros. .

One-way parity

Overview

One-way parity (Row Parity) uses only a single parity at a time, so it is also called a single bit Parity (Single Bit Parity). The transmitter adds a parity bit after the signal bit of each character of the data frame, and the receiver checks the parity bit. A typical example is the transmission of ASCII-oriented data signal frames. Since the ASCII code is a seven-bit code, the eighth bit code is used as the parity bit.

One-way parity is divided into odd parity (Odd Parity) and even parity (Even Parity). The sender uses the parity bit to verify the transmitted signal value as follows: Odd parity The verification ensures that the total number of 1s in the 8 bits of each character transmitted is an odd number; the even check ensures that the total number of 1s in the 8 bits of each character is an even number.

Obviously, if there is an odd number (such as 1, 3, 5, 7) of the 7 signal bits of the transmitted character at the same time, it can be detected; but if there are even number ( For example, if there are errors in bits 2, 4, and 6), the one-way parity cannot be checked.

Generally, odd parity is often used in synchronous transmission, and even parity is often used in asynchronous transmission.

Check method

Odd check: Make the number of 1 in the original data sequence (including the one you want to add) an odd number

1000110 (0) You must add 0 so that there are 3 1s that are already odd numbers, so after you add 0, the number of 1s is still an odd number.

Even parity: Make the number of 1s in the original data sequence (including the one bit you want to add) an even number. Even parity is actually a special case of cyclic redundancy check. Through the polynomial x + 1 to obtain a 1-bit CRC.

1000110 (1) You must add 1 so that there are 3 1s. If the number of 1s is even, you can only add 1.

Two-way check

In order to improve the error detection ability of parity, two-way parity (Row and Column Parity) can be used, which can also be called two-way redundancy check ( Vertical and Longitudinal Redundancy Checks).

Bidirectional parity check, also known as "square check" or "vertical horizontal" check.

Example:

1010101×

1010111×

1110100×

0101110×

0011010×

×××××××

"×" means odd or even parity check Verification code.

In this way, the attention to each number has increased from 1×7 times to 7×7 times. Therefore, the verification capability is stronger than that of the single-item verification.

A simple check of the correctness of the data, in the computer is 010101 binary representation, each byte has eight binary, the last digit is the check code, and the first seven digits of the odd check are calculated The parity of the number of 1s, and the even check measures the parity of the number of 0s in the first seven bits. When one of the bits in the data changes, the parity obtained will change, and the receiving party will request the sender to retransmit the data. The parity check can only simply judge the correctness of the data. It can be seen from the principle that when one bit is wrong, it can be accurately judged. The probability of errors in the bit and check code during transmission is relatively low, and the parity check can be used in applications with relatively low requirements.

Example

During the transmission of serial data, interference may cause information errors. For example, the transmission character'E', the digits of which are:

0100, 0101=45H

D7 D0

Due to interference, the bit may be changed to 1, (why does it not change to 0?) In this case, we call it "error ". We call "error detection" how to find errors in transmission. After discovering the error, how to eliminate the error is called "error correction". The simplest error detection method is "parity check", that is, in addition to the bits of the transmitted character, an odd/even parity bit is transmitted.

Odd parity: In all transmitted digits (including the digits and check digits of characters), the number of "1" is an odd number, such as:

1 0110, 0101

0 0110, 0101

Even parity: In all transmitted digits (including the digits and parity digits of characters), the number of "1" is an even number, such as:

1 0100, 0101

0 0100, 0101

If the odd number of data bits including the parity bit changes during transmission, then the parity check A bit check error will indicate an error occurred during the transmission process. However, if the even number of data bits including the parity bit changes during transmission, it will not be possible to detect whether the received data has errors. You can only ask the sender to resend.