Parity check code

Basic concept

Parity check code

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

A binary codeword, if its code element has an odd number of 1, is called singularity. For example, the codeword "10110101" has five 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 the following formula: singularity=a0⊕a1⊕a2⊕…⊕an

Parity check can be described as: add a check bit to each codeword , Use it to form odd or even check. It can be seen that the additional symbol d2 is simply used to make each word even. Therefore, if one symbol is wrong, it can be distinguished, because the parity will become odd. The parity check code adds a check bit to make one number in the code odd (odd check) or even (even check), so that the code distance becomes 2. Because it uses the parity of the number of 1s in the code as a basis, even bit errors cannot be found.

Code distance

The number of different binary digits (bit) between any two legal codes (codewords) in an encoding system is called the code distance of these two codewords. The minimum distance between any two code words in the entire coding system is the code distance of the coding system.

In order for a system to check and correct an error, the minimum distance between codes must be at least "3". When the minimum distance is 3, either one error can be corrected or two errors can be detected, but one error and two errors cannot be detected at the same time. To further improve the error correction and error detection capabilities of coded information, it is necessary to further increase the minimum distance between codewords.

The larger the code distance, the stronger the error correction capability, but the greater the data redundancy, that is, the lower the coding efficiency. Therefore, the choice of code distance depends on the parameters of the specific system. The designer of a digital system must consider factors such as the probability of information errors and the minimum error rate that the system can tolerate.

Basic classification:

Vertical parity

Vertical parity is also called vertical parity, which divides the entire information block to be sent into For fixed-length p-bit segments (for example, q-segment), after each segment, the number of "1" is odd or even plus one parity bit, as shown in Figure 2.19. In the information (I11, I21,..., Ipl, I12,..., Ipq), each p-bit constitutes a section (that is, a column in the figure), and there are q sections (that is, a total of q columns). Each section adds a parity check Check the redundant bits, that is, the rio encoding rule in the figure is

Note: The "+" here refers to the modular two addition, that is, the exclusive OR operation.

The arrow in the figure The sequence of serial transmission is given, that is, the bit-by-bit order is I11, I21,...,Ip1,r1,I12,...,Ipa,r2,...,child,...,I, rq. During the encoding and verification process In this method, the above-mentioned continuous half-addition operation can be easily realized by hardware or software methods, and redundant bits can be generated while sending; similarly, the receiving end can also be checked while receiving and then the check bit can be removed.

The coding efficiency of the vertical parity check method is R=p/(p+1). Generally, the code of a character is taken as an information segment. This vertical parity check is sometimes called character parity. For example. , In an 8-bit character code (that is, a character is represented by an 8-bit binary digit), p=8, and the coding efficiency is 8/9.

The vertical parity check method can detect the All odd-numbered errors, but even-numbered errors cannot be detected. For burst errors, the probability of occurrence of odd-numbered errors and even-numbered errors is close to the same, so the missed detection rate of errors is close to 1/2. p>

Horizontal parity check

In order to reduce the rate of missed detection of burst errors, the horizontal parity check method can be used. Horizontal parity check is also called horizontal parity check, which is correct The corresponding bits of each information segment are encoded horizontally to generate a parity redundant bit, as shown in Figure 2.20, the encoding rule is

If each information segment is a character, the q here is sent The number of characters in the information block.

The coding efficiency of the horizontal parity check is R=q/(q+1).

The horizontal parity check can not only detect each segment Odd-numbered bit errors on the same bit, and all burst errors with burst length≦p can also be detected, because according to the sending order, it can be seen from Figure 2.20 that burst errors with burst length≦p must be distributed in different rows , And one bit per line, so you can check for errors, and its missed detection rate is lower than the vertical parity check method. However, when implementing the horizontal parity check code, no matter whether it is hardware or software methods, it cannot be generated during the transmission process. The parity check redundant bit is inserted and sent, and the redundant bit must be calculated after all the information blocks to be sent are all. That is to say, the data buffer must be used, so its encoding and detection are complicated to implement Some.

Horizontal and vertical parity check

Conducting horizontal and vertical parity checks at the same time constitutes a horizontal and vertical parity check, which is also called a horizontal and vertical parity test, as shown in the figure. As shown in 2.21. If both the horizontal and vertical parity check are used, the coding efficiency of the horizontal and vertical parity check is R=pq/[(p+1)(q+1 )]. .

The horizontal and vertical parity check can detect all errors of 3 bits or less (because there is at least one bit error in a certain row or column at this time), odd bit errors, and bursts Burst errors of length <=p+1 and a large part of even bit errors. The measurement table shows that this way of coding can reduce the bit error rate from one percent to one ten thousandth of the original bit error rate.

The horizontal and vertical parity check can not only detect errors, but also correct some errors. For example, when there is only one bit error in the data block, it can be determined that the position of the error code is at the intersection of a certain row and a certain column, so that it can be corrected.

Principle of Parity Check Code

Parity check code is the general term for odd check code and even check code, and is the most basic error detection code. It is composed of n-1 bits of information element and 1 bit of parity element, which can be expressed as (n, n-1). If it is an odd check code, after adding a check element, the number of "1"s in the code word with code length n is an odd number; if it is an even check code, after adding a check element, The number of "1"s in the code word with code length n is an even number. Suppose: if the codeword of an even parity check code is represented by A=[an-1,an-2,...,a1,a0], then: (1) where is the check element, and "+" is the modulo two sum (This will also be said in the future, please pay attention). Equation (1) is usually called the calibration equation. Using formula (1), the check element can be obtained from the information element. In addition, if a single (or odd number) error occurs, this relational expression will be destroyed, so it can be used to detect whether a single or odd number of errors have occurred in the codeword.