Parity bit
From Free net encyclopedia
In computing and telecommunication, a parity bit is a binary digit that indicates whether the number of 1 bits in the preceding data was even or odd. If a single bit is changed in transmission, the message will change parity and the error can be detected at this point. (Note that the bit that changed may have been the parity bit itself!) The most common convention, or parity scheme, is that a parity bit of 1 indicates that there is an odd number of ones in the data, and a parity bit of 0 indicates that there is an even number of ones in the data.
Contents |
Usage
In serial data transmission, a common format is 7 data bits, an even parity bit, and one or two stop bits. Even parity means that the total number of 1 bits must be even. This format neatly accommodates all the 7-bit ASCII characters in a convenient 8-bit byte. Other formats are possible; 8 bits of data plus a parity bit can convey all 8-bit byte values. In serial communication contexts, parity is usually generated and checked by interface hardware (e.g., a UART) and, on reception, the result made available to the CPU (and so to, for instance, the operating system) via a status bit in a register in the interface hardware. Recovery from the error is usually done by retransmitting the data, the details of which are usually handled by software (e.g., the operating system I/O routines).
Simple error correction
Parity bits are mainly used as a very simple form of redundancy check. A single parity bit can detect the alteration of any odd number of bits (including the most common case of one bit), but cannot detect the alteration of an even number of bits. Nor does it include enough information to correct any error.
Because of its simplicity, parity is used in many hardware applications where an operation can be repeated in case of difficulty, or where simply detecting the error is helpful. For example, the SCSI bus uses parity to detect transmission errors, and many microprocessor instruction caches include parity protection. Because the I-cache data is just a copy of main memory, it can be thrown away and re-fetched if it is found to be corrupted.
Parity checking is not very robust, since if the number of bits changed is even, the check bit will be valid and the error will not be detected. Moreover, parity does not indicate which bit contained the error, even when it can detect it. The data must be discarded entirely, and re-transmitted from scratch. On a noisy transmission medium a successful transmission could take a long time, or even never occur. Parity does have the advantage, however, that it is about the best possible code that uses only a single bit of space. See Hamming code for other error-correction codes.
RAID parity blocks
In certain RAID (Redundant array of independent disks) levels, redundancy is achieved by the use of parity blocks. If a single drive in the array fails, data blocks and a parity block from the working drives can be combined to reconstruct the missing data.
Given the diagram below, assume A1 = 00000111, A2 = 00000101, and A3 = 0000000. Ap, generated by XORing A1, A2, and A3, will then equal 00000010. If the second drive fails, A2 will no longer be accessible, but can be reconstructed by XORing A1, A3, and Ap:
A1 XOR A3 XOR Ap = 00000101 (A2).
RAID Array A1 A2 A3 Ap B1 B2 Bp B3 C1 Cp C2 C3 Dp D1 D2 D3
Note: Data blocks are in the format A#, parity blocks Ap.
CRC Polynomial origins of parity bits
Even parity is actually a special case of a cyclic redundancy check, where the 1-bit CRC is generated by the polynomial x+1. Parity is a setting used in serial port data transmission. Parity is used to recover data in RAIDs. Parity RAM uses parity to detect memory errors. Hamming code error-correction code, the usual "next step up" from parity.
de:Paritätsbit es:Bit de paridad fr:Bit de parité nl:Pariteitsbit ja:パリティビット pl:Bit parzystości pt:Paridade (telecomunicações) ru:Бит чётности