Parity bit

The parity check is used for the detection of incorrectly transmitted information words. A information word here is a sequence of bits will be referred to. The " parity " is the number of bits occupied with 1 in the information word meaning straight ( engl. "even" ), as the number of bits is even, otherwise odd (English " odd" ). The parity check coding depends on the information word a Paritätskontrollbit, also called parity on. 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 is supplementing with E or O, according to the examples in the graphs. The result of which is by one bit longer than the information word, here called codeword. The method of error detection using parity bits, called parity check. Since it is not known where the fault has occurred within the code word, no error correction is possible. In addition, only an odd number of bit errors in a code word can be detected in a parity bit ( N = 1). An even number of bit errors is not detected, since the parity remains unchanged in the code word.

For error correction, there are further developments like the one shown below multidimensional Parityverfahren, the Hamming code or the error correction method.

Generation of N parity bits

At the transmitter, all the bits of a data block ( information word here ) modulo N adds 1. Accordingly, can be detected up to N bit errors. For N = 1, the sum of ones ( parity sum ) is calculated in the information word. This sum is even, for even parity, the parity bit to zero. Correspondingly an odd sum of the information word, the parity bit one. ( This applies vice versa for odd parity. )

Example 1 ( even parity ):

• If the data transfer even parity ( parity sum straight → parity: 0, parity sum odd parity →: 1) fixed, then for the following two examples:
• The information word 0011.1010 has four ones. Four is an even number, the Paritätskontrollbit is thus zero, and the resulting codeword is 0011.1010 0
• The information word 1010.0100, however, has an odd parity sum and is encoded into the codeword 1010.0100 1.

Example 2 ( odd parity ):

• Is data transfer Odd -parity ( parity sum straight → parity 1, parity odd sum → parity: 0) set, then for the following two examples:
• The information word 0011.1010 has four ones. Four is an even number, which is thus the Paritätskontrollbit one, and the resulting code word is 1 0011.1010
• The information word 1010.0100, however, has an odd parity sum and is encoded into the codeword 0 1010.0100.

Practically the parity bit can be generated both by hardware and by software, see parity generator.

Receiving the codeword with N parity bits

The receiver adds the bits of the received codeword, and also checks whether it has computed the same code. N is specific to the data transmission method. If N = 1, then there is the parity -check code of exactly one parity bit, for N = 2 of 2 parity, etc.

In asynchronous data transmission via a serial RS232 interface, the block size is usually 8 bits and N = 1 If a bit can be corrupted ( a zero to a one or a one to a zero ), then the parity sum of the resulting code word is odd, and the decoder detects that there has been an error. However, it is for the decoder not possible to correct the error because it is not known which bit was corrupted. The decoder detects ie a maximum of an error and can correct a maximum of zero error, because if more than one bit has been corrupted, so it may be impossible to detect the error because the parity sum can then be straight. It is said that the parity check code is one - recognize errors and 0 - error- correcting.

Scope

Parity bits, see, inter alia, in the Dial, networking and memory modules use.

The original form of ASCII table consists of 128 characters, each character is uniquely defined by a sequence of seven bits. And because it summarizes eight bits to a byte, this eighth bit was often used to attach a Paritätskontrollbit. Today, however, this is hardly any usual, the eighth bit is instead almost always used to expand the font 128 characters out.

Even and odd parity

We distinguish between two protocols parity: even (even) and odd ( odd). In both cases, the number of ones is detected within the associated word. If the parity is "even" (straight ), so the parity bit is set if an odd number of data bits is set in characters. In the case of "odd" (odd), the bit is set if an even number of data bits is set within the character. By " even" or " odd " is thus meant the number of set bits, including the parity bit.

Example: In the example below, an odd ( " Odd ") is parity are made ​​:

If the parity bit is always 1, then one speaks of a mark- parity (it contains no information); it is always 0, we speak of space-parity (there is an empty space ).

Alternative explanation

When transmitting data in the form of a bit stream can take place using parity bits of error detection. A parity bit can secure a certain number of bits. The value ( 0 or 1 ) of the parity bits must be calculated at the transmitter and the receiver is checked by using the same calculation. The calculation of the parity bits can be odd or even parity. Transmitter and receiver must define / negotiate whether they choose odd or even parity calculation before.

If both parties agree on the calculation of an even parity, the total number of 1 bits is counted in the hedged data. The task of the parity bit is this number to expand to an even number. If the number of 1 bits has therefore already is just the parity bit is transmitted as 0, if the number is odd, it must be transmitted as a 1.

If both parties agree on the calculation of an odd parity, the total number of 1 bits is also counted in the hedged data. The object of the parity bit is, however, to extend this number then an odd number. If the number of 1 bits is therefore an odd number, the parity bit must be transmitted as a 0 if the number is even, it has to be transmitted as a 1.

In short, must the total number of bits, which are protected by the parity bit (including the parity bit ) either ( for even parity) or odd ( for odd parity) straight.

Multidimensional parity check

(also: cross- parity or parity block )

As an extension of the parity check shown above, one-dimensional can be created, which can detect certain errors as an extension of not only but also can correct certain errors combinations also a two -, or higher-dimensional parity method. The parity check is thus to a error-detecting and error-correcting process.

The construction is to be represented by a simple two-dimensional parity check for eight -bit data words:

• Are summarized ( a byte ) in a square (array) eight useful data to eight bits in length. It thus includes each row and each column exactly eight bits.

• A parity bit for each row is calculated and adjusted as the ninth bit of data of each line according to the method as described above.

• For each column, a parity bit is calculated and written to the ninth line is displayed above by the process as.

The resulting array has nine times nine data bits and may be suitable, for example serially transmitted. On the receiver side of the data block is received to nine data words and shown as an array. Now occurs at a specific point on a single bit error, the parity of the corresponding row and column is exactly wrong. Thus, the erroneous bits are clearly localized and are transformed by inversion in the right state.

With this method, all single bit errors per block are clearly identifiable and correctable. If multiple bit errors in a block, the error correction is no longer possible in all cases. However, bad blocks may still be faulty can be identified, which in these processes, for example, includes all double bit errors per block.

Advanced parity check (block codes)

The parity check is used in expanded form and in various block codes such as the Hamming code or the low- density parity -check code for both error detection and error correction. These codes are based as shown on top of a user data block of fixed length, on which not only a parity bit, but several parity bits are appended to then give the actual code word. In order to enable not only an error detection but also error correction parity bits with those different places ( bits) are included in the user data block, the individual parity bits per block. The selection of these sites per parity bit must be done and ensure certain criteria such as the linear independence of the individual Paritystellen to enable error correction according to certain rules. Because this code constructions options, the precise bit position ( s) shown in the case of transmission errors to determine the error in the net data block and to correct the affected faulty binary digits.

An extension of this approach based on multi-digit parity check block codes represent the so-called Turbo Product Codes ( TPC), which an extended parity block code such as the Hamming code with the above-mentioned multi-dimensional parity check in an iterative decoding between rows and columns of the two-dimensional data block connects.