Parity bit
The parity bit of a sequence of bits is used as a supplementary bit to supplement the number of bits (including the parity bit) assigned to 1 in the sequence as even or odd.
The " parity " of the bit string is straight ( English even ), when the number of bits occupied with 1 in the sequence is straight, otherwise odd ( English odd ).
The parity bit can be used for parity control; this is used to detect transmission errors. In this context, the bit sequence is referred to as an information word. The parity control coding appends a parity control bit, also called a parity bit, to the information word. The result, which is one bit longer than the information word, is called the code word here . This is done so that all code words to be transmitted have the same parity. Depending on whether even or odd parity is to be transmitted, the addition is made with E or O, according to the examples in the graphics. The method of error detection using parity bits is called parity check . Since it is not known where the error occurred within the code word, no error correction is possible. In addition, with a parity bit (N = 1), only an uneven number of bit errors can be determined in a code word. There are further developments for error correction such as the multidimensional parity method shown below, the Hamming code or the error correction method .
Generation of N parity bits
At the transmitter, all bits of a data block (here information word ) are added modulo N + 1. Accordingly, up to N bit errors can be recognized. For N = 1, the sum of the ones (parity sum ) in the information word is calculated. If this sum is even, the parity bit becomes zero with even parity. Correspondingly, an odd sum of the information word results in the parity bit one. (The opposite applies to odd parity.)
Example 1 (even parity):
- If even parity (parity sum even → parity bit: 0, parity sum odd → parity bit: 1) is specified for the data transmission, the following two examples apply:
- The information word 0011.1010 has four ones. Four is an even number, so the parity check bit is zero and the resulting code word is 0011.1010 0 .
- The information word 1010.0100, on the other hand, has an odd parity sum and is encoded in the code word 1010.0100 1 .
Example 2 (odd parity):
- If odd parity (parity sum even → parity bit: 1, parity sum odd → parity bit: 0) is specified for the data transmission, the following two examples apply:
- The information word 0011.1010 has four ones. Four is an even number, so the parity check bit is one, and the resulting code word is 0011.1010 1 .
- The information word 1010.0100, on the other hand, has an odd parity sum and is encoded in the code word 1010.0100 0 .
| Sum of the ones of an information word | Value of the parity bit for even parity | Value of the parity bit for odd parity |
|---|---|---|
| straight | 0 | 1 |
| odd | 1 | 0 |
In practice, the parity bit can be generated both by hardware and software , see parity generator .
Reception of the code word with N parity bits
The receiver also adds the bits of the received code word and checks whether it has calculated the same code. N is specific to the respective data transmission method. If N = 1, then the parity check code consists of exactly one parity bit, if N = 2 it consists of 2 parity bits, etc.
With asynchronous data transmission via a serial RS-232 interface, the block size is usually 8 bits and N = 1. If a bit is corrupted (a zero into a one or a one into a zero), the parity sum of the resulting code word is odd , and the decoder recognizes that an error has occurred. However, it is not possible for the decoder to correct the error, since it is not known which bit was corrupted. The decoder recognizes a maximum of one error and can correct a maximum of zero errors, because if more than one bit has been corrupted, it may not be possible at all to recognize the error, since the parity sum can then be even. It is said that the parity control code is 1-error-detecting and 0-error-correcting .
scope of application
Find parity bits a. used in remote data transmission , network technology and memory modules .
The original form of the ASCII table consists of 128 characters, each character is uniquely defined by a sequence of seven bits. Since a computer combines eight bits into one byte , this eighth bit was often used to append a parity check bit. Today, however, this is seldom used anymore. Instead, the eighth bit is almost always used to expand the character set beyond 128 characters.
Even and odd parity
A distinction is made between two parity protocols: even (even) and odd (odd) . In both cases, the number of ones within the assigned word is determined. If the parity is set to "even", the parity bit is set if an uneven number of data bits is set in the character. In the case of "odd", the bit is set if an even number of data bits is set within the character. With "even" or "odd" is meant the number of set data bits including the parity bit.
Example: In the following example, an odd parity is to be established:
| "Word" | Parity bit | Remarks |
|---|---|---|
| 0100.1110 | 1 | The “word” already contains four ones, the parity bit is set to produce an odd code word (five ones). |
| 1011.0110 | 0 | The parity is already odd with five ones, the parity bit is not set. |
| 0100.0000 | 1 | The entire code word has two ones here, although the number should be odd. An error has occurred. Either the parity bit was calculated incorrectly or the "word" was incorrectly transmitted. |
If the parity bit is always 1, then one speaks of a mark parity (it contains no information); if it is always 0, it is called space parity (it represents a space).
Alternative explanation
When data is transmitted in the form of a bit stream , error detection can take place with the aid of parity bits. A parity bit can secure a certain number of bits. The value (0 or 1) of the parity bit must be calculated at the sender and is checked at the receiver using the same calculation. The parity bit can be calculated for even or odd parity. Sender and receiver have to define / negotiate beforehand whether they will choose an even or odd parity calculation.
If there is agreement on the calculation of an even parity, the number of all 1-bits in the data to be protected is counted. The job of the parity bit is to expand this number to an even number. If the number of 1 bits is already even, the parity bit must be transmitted as 0, if the number is odd, it must be transmitted as 1.
If there is agreement on the calculation of an odd parity, the number of all 1-bits in the data to be protected is also counted. The task of the parity bit is to expand this number to an odd number. If the number of 1-bits is already odd, the parity bit must be transmitted as 0, if the number is even, it must be transmitted as 1.
In short, the number of all bits protected by the parity bit (including the parity bit) must be either even (for even parity) or odd (for odd parity).
Multi-dimensional parity control
(also: cross parity or block parity)
As an extension of the one-dimensional parity check shown above, a two- or higher-dimensional parity method can also be created, which as an extension can not only recognize certain errors, but can also correct certain combinations of errors. The parity check thus becomes an error-detecting and error-correcting method.
The construction should be represented using a simple two-dimensional parity check for eight-bit long data words:
- Eight user data words eight bits long (one byte) are combined in a square (array) . It therefore comprises exactly eight bits for each row and each column.
- A parity bit is calculated for each line according to the procedure described above and is added as the ninth data bit of each line.
- A parity bit is calculated for each column according to the procedure described above and is written as the ninth line.
The resulting array comprises nine by nine data bits and can be transmitted in a suitable manner , for example serially . On the receiver side, the data block is received as nine data words and mapped as an array . If a single bit error occurs at a certain point , the parity of the row and column in question is faulty. In this way, the faulty bit can be clearly localized and converted into the correct state by inversion.
With this method, all individual bit errors per block can be clearly identified and corrected. If several bit errors occur in a block, error correction is no longer possible in all cases. However, faulty blocks can still be recognized as faulty under certain circumstances, which in these methods includes, for example, all double bit errors per block.
Extended parity control (block codes)
The parity check is also used in an extended form with various block codes such as the Hamming code or the low-density parity check code, both for error detection and for error correction. As shown above, these codes are based on a user data block of fixed length, to which, however, not just one parity bit, but several parity bits are appended in order to then result in the actual code word. In order to enable not only error detection but also error correction with those parity bits, different positions (bits) of the useful data block are included in the individual parity bits per block. The selection of these positions per parity bit must be made according to certain rules and certain criteria such as the linear independence of the individual parity positions must be guaranteed in order to enable error correction. Due to these code constructions, there are possibilities to determine the exact bit position (s) of the error in the user data block in the event of transmission errors and to correct the affected incorrect binary digits.
The so-called Turbo Product Codes (TPC) represent an extension of these block codes, which are based on the multi-digit parity check , which include an extended parity block code such as the Hamming code with the above-mentioned multi-dimensional parity control in an iterative decoding between rows and columns of the two-dimensional data block connects.
literature
- Ulrich Tietze, Christoph Schenk: Semiconductor circuit technology . 12th edition. Springer, Berlin a. a. 2002, ISBN 3-540-42849-6 .
- Klaus Beuth: Digital technology . 10th revised and expanded edition. Vogel, Würzburg 1998, ISBN 3-8023-1755-6 ( Electronics 4; Vogel reference book ).
- Manfred Seifart, Helmut Beikirch: Digital circuits . 5th completely revised edition. Verlag Technik, Berlin 1998, ISBN 3-341-01198-6 .