A parity bit, or check bit, is a
bit
The bit is the most basic unit of information in computing and digital communications. The name is a portmanteau of binary digit. The bit represents a logical state with one of two possible values. These values are most commonly represente ...
added to a string of
binary code
A binary code represents text, computer processor instructions, or any other data using a two-symbol system. The two-symbol system used is often "0" and "1" from the binary number system. The binary code assigns a pattern of binary digits, also ...
. Parity bits are a simple form of
error detecting code
In information theory and coding theory with applications in computer science and telecommunication, error detection and correction (EDAC) or error control are techniques that enable reliable delivery of digital data over unreliable commun ...
. Parity bits are generally applied to the smallest units of a communication protocol, typically 8-bit
octets (bytes), although they can also be applied separately to an entire message string of bits.
The parity bit ensures that the
total number of 1-bits in the string is
even or odd.
Accordingly, there are two variants of parity bits: even parity bit and odd parity bit. In the case of even parity, for a given set of bits, the bits whose value is 1 are counted. If that count is odd, the parity bit value is set to 1, making the total count of occurrences of 1s in the whole set (including the parity bit) an even number. If the count of 1s in a given set of bits is already even, the parity bit's value is 0. In the case of odd parity, the coding is reversed. For a given set of bits, if the count of bits with a value of 1 is even, the parity bit value is set to 1 making the total count of 1s in the whole set (including the parity bit) an odd number. If the count of bits with a value of 1 is odd, the count is already odd so the parity bit's value is 0. Even parity is a special case of a
cyclic redundancy check
A cyclic redundancy check (CRC) is an error-detecting code commonly used in digital networks and storage devices to detect accidental changes to digital data. Blocks of data entering these systems get a short ''check value'' attached, based on t ...
(CRC), where the 1-bit CRC is generated by the
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
''x''+1.
Parity
In mathematics ''
parity'' can refer to the evenness or oddness of an integer, which, when written in its
binary form
Binary form is a musical form in 2 related sections, both of which are usually repeated. Binary is also a structure used to choreograph dance. In music this is usually performed as A-A-B-B.
Binary form was popular during the Baroque period, of ...
, can be determined just by examining only its
least significant bit
In computing, bit numbering is the convention used to identify the bit positions in a binary number.
Bit significance and indexing
In computing, the least significant bit (LSB) is the bit position in a binary integer representing the binary 1 ...
.
In information technology parity refers to the evenness or oddness, given any set of binary digits, of the number of those bits with value one. Because parity is determined by the state of every one of the bits, this property of parity—being dependent upon all the bits and changing its value from even to odd parity if any one bit changes—allows for its use in error detection and correction schemes.
In telecommunications the parity referred to by some protocols is for error-''detection''. The transmission medium is preset, at both end points, to agree on either odd parity or even parity. For each string of bits ready to transmit (data packet) the sender calculates its parity bit, zero or one, to make it conform to the agreed parity, even or odd. The receiver of that packet first checks that the parity of the packet as a whole is in accordance with the preset agreement, then, if there was a parity error in that packet, requests a re-transmission of that packet.
In computer science the parity stripe or parity disk in a
RAID
Raid, RAID or Raids may refer to:
Attack
* Raid (military), a sudden attack behind the enemy's lines without the intention of holding ground
* Corporate raid, a type of hostile takeover in business
* Panty raid, a prankish raid by male college ...
provides
error-''correction''. Parity bits are written at the rate of one parity bit per ''n'' bits, where ''n'' is the number of disks in the array. When a read error occurs, each bit in the error region is recalculated from its set of ''n'' bits. In this way, using one parity bit creates "redundancy" for a region from the size of one bit to the size of one disk. See below.
In electronics, transcoding data with parity can be very efficient, as
XOR
Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false).
It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
gates output what is equivalent to a check bit that creates an even parity, and XOR logic design easily scales to any number of inputs. XOR and AND structures comprise the bulk of most integrated circuitry.
Error detection
If an odd number of bits (including the parity bit) are
transmitted incorrectly, the parity bit will be incorrect, thus indicating that a parity error occurred in the transmission. The parity bit is only suitable for detecting errors; it cannot
correct any errors, as there is no way to determine which particular bit is corrupted. The data must be discarded entirely, and
re-transmitted from scratch. On a noisy transmission medium, successful transmission can therefore take a long time, or even never occur. However, parity has the advantage that it uses only a single bit and requires only a number of
XOR gate
XOR gate (sometimes EOR, or EXOR and pronounced as Exclusive OR) is a digital logic gate that gives a true (1 or HIGH) output when the number of true inputs is odd. An XOR gate implements an exclusive or (\nleftrightarrow) from mathematical log ...
s to generate. See
Hamming code
In computer science and telecommunication, Hamming codes are a family of linear error-correcting codes. Hamming codes can detect one-bit and two-bit errors, or correct one-bit errors without detection of uncorrected errors. By contrast, the sim ...
for an example of an error-correcting code.
Parity bit checking is used occasionally for transmitting
ASCII
ASCII ( ), abbreviated from American Standard Code for Information Interchange, is a character encoding standard for electronic communication. ASCII codes represent text in computers, telecommunications equipment, and other devices. Because of ...
characters, which have 7 bits, leaving the 8th bit as a parity bit.
For example, the parity bit can be computed as follows. Assume
Alice and Bob
Alice and Bob are fictional characters commonly used as placeholders in discussions about cryptographic systems and protocols, and in other science and engineering literature where there are several participants in a thought experiment. The A ...
are communicating and Alice wants to send Bob the simple 4-bit message 1001.
This mechanism enables the detection of single bit errors, because if one bit gets flipped due to line noise, there will be an incorrect number of ones in the received data. In the two examples above, Bob's calculated parity value matches the parity bit in its received value, indicating there are no single bit errors. Consider the following example with a transmission error in the second bit using XOR:
There is a limitation to parity schemes. A parity bit is only guaranteed to detect an odd number of bit errors. If an even number of bits have errors, the parity bit records the correct number of ones, even though the data is corrupt. (See also
Error detection and correction
In information theory and coding theory with applications in computer science and telecommunication, error detection and correction (EDAC) or error control are techniques that enable reliable delivery of digital data over unreliable communi ...
.) Consider the same example as before with an even number of corrupted bits:
Bob observes even parity, as expected, thereby failing to catch the two bit errors.
Usage
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
Small Computer System Interface (SCSI, ) is a set of standards for physically connecting and transferring data between computers and peripheral devices. The SCSI standards define commands, protocols, electrical, optical and logical interface ...
and
PCI bus
PCI may refer to:
Business and economics
* Payment card industry, businesses associated with debit, credit, and other payment cards
** Payment Card Industry Data Security Standard, a set of security requirements for credit card processors
* Prov ...
es use parity to detect transmission errors, and many
microprocessor
A microprocessor is a computer processor where the data processing logic and control is included on a single integrated circuit, or a small number of integrated circuits. The microprocessor contains the arithmetic, logic, and control circu ...
instruction
caches include parity protection. Because the
I-cache
This glossary of computer hardware terms is a list of definitions of terms and concepts related to computer hardware, i.e. the physical and structural components of computers, architectural issues, and peripheral devices.
A
...
data is just a copy of
main memory
Computer data storage is a technology consisting of computer components and recording media that are used to retain digital data. It is a core function and fundamental component of computers.
The central processing unit (CPU) of a computer ...
, it can be disregarded and re-fetched if it is found to be corrupted.
In
serial data transmission
Data transmission and data reception or, more broadly, data communication or digital communications is the transfer and reception of data in the form of a digital bitstream or a digitized analog signal transmitted over a point-to-point o ...
, a common format is 7 data bits, an even parity bit, and one or two
stop bit
Asynchronous serial communication is a form of serial communication in which the communicating endpoints' interfaces are not continuously synchronized by a common clock signal. Instead of a common synchronization signal, the data stream contai ...
s. This format accommodates all the 7-bit
ASCII
ASCII ( ), abbreviated from American Standard Code for Information Interchange, is a character encoding standard for electronic communication. ASCII codes represent text in computers, telecommunications equipment, and other devices. Because of ...
characters in an 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
A universal asynchronous receiver-transmitter (UART ) is a computer hardware device for asynchronous serial communication in which the data format and transmission speeds are configurable. It sends data bits one by one, from the least significan ...
) and, on reception, the result made available to a
processor
Processor may refer to:
Computing Hardware
* Processor (computing)
**Central processing unit (CPU), the hardware within a computer that executes a program
*** Microprocessor, a central processing unit contained on a single integrated circuit (I ...
such as the CPU (and so too, for instance, the
operating system
An operating system (OS) is system software that manages computer hardware, software resources, and provides common services for computer programs.
Time-sharing operating systems schedule tasks for efficient use of the system and may also in ...
) via a status bit in a
hardware register
In digital electronics, especially computing, hardware registers are circuits typically composed of flip flops, often with many characteristics similar to memory, such as:
* The ability to read or write multiple bits at a time, and
* Using an a ...
in the
interface
Interface or interfacing may refer to:
Academic journals
* ''Interface'' (journal), by the Electrochemical Society
* ''Interface, Journal of Applied Linguistics'', now merged with ''ITL International Journal of Applied Linguistics''
* '' Inte ...
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).
When the total number of transmitted bits, including the parity bit, is even, odd parity has the advantage that the all-zeros and all-ones patterns are both detected as errors. If the total number of bits is odd, only one of the patterns is detected as an error, and the choice can be made based on which is expected to be the more common error.
RAID array
Parity data is used by RAID arrays (
redundant array of independent/inexpensive disks) to achieve
redundancy. If a drive in the array fails, remaining data on the other drives can be combined with the parity data (using the Boolean
XOR
Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false).
It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , ...
function) to reconstruct the missing data.
For example, suppose two drives in a three-drive
RAID 5
In computer storage, the standard RAID levels comprise a basic set of RAID ("redundant array of independent disks" or "redundant array of inexpensive disks") configurations that employ the techniques of striping, mirroring, or parity to create lar ...
array contained the following data:
To calculate parity data for the two drives, an XOR is performed on their data:
The resulting parity data, 10111001, is then stored on Drive 3.
Should any of the three drives fail, the contents of the failed drive can be reconstructed on a replacement drive by subjecting the data from the remaining drives to the same XOR operation. If Drive 2 were to fail, its data could be rebuilt using the XOR results of the contents of the two remaining drives, Drive 1 and Drive 3:
as follows:
The result of that XOR calculation yields Drive 2's contents. 11010100 is then stored on Drive 2, fully repairing the array.
XOR logic is also equivalent to even parity (because ''a'' XOR ''b'' XOR ''c'' XOR ... may be treated as XOR(''a'',''b'',''c'',...) which is an n-ary operator which is true if and only if an odd number of arguments are true). So the same XOR concept above applies similarly to larger RAID arrays with parity, using any number of disks. In the case of a RAID 3 array of 12 drives, 11 drives participate in the XOR calculation shown above and yield a value that is then stored on the dedicated parity drive.
Extensions and variations on the parity bit mechanism "double," "dual," or "diagonal" parity, are used in
RAID-DP.
History
A ''parity track'' was present on the first
magnetic tape data storage
Magnetic-tape data storage is a system for storing digital information on magnetic tape using digital recording.
Tape was an important medium for primary data storage in early computers, typically using large open reels of IBM 7 track, 7-track, ...
in 1951. Parity in this form, applied across multiple parallel signals, is known as a
transverse redundancy check. This can be combined with parity computed over multiple bits sent on a single signal, a
longitudinal redundancy check
In telecommunication, a longitudinal redundancy check (LRC), or horizontal redundancy check, is a form of redundancy check that is applied independently to each of a parallel group of bit streams. The data must be divided into transmission block ...
. In a parallel bus, there is one longitudinal redundancy check bit per parallel signal.
Parity was also used on at least some paper-tape (
punched tape
Five- and eight-hole punched paper tape
Paper tape reader on the Harwell computer with a small piece of five-hole tape connected in a circle – creating a physical program loop
Punched tape or perforated paper tape is a form of data storage ...
) data entry systems (which preceded magnetic tape systems). On the systems sold by British company ICL (formerly ICT) the paper tape had 8 hole positions running across it, with the 8th being for parity. 7 positions were used for the data, e.g., 7-bit ASCII. The 8th position had a hole punched in it depending on the number of data holes punched.
See also
*
BIP-8
*
Parity function In Boolean algebra, a parity function is a Boolean function whose value is one if and only if the input vector has an odd number of ones. The parity function of two inputs is also known as the XOR function.
The parity function is notable for its ...
*
Single-event upset
A single-event upset (SEU), also known as a single-event error (SEE), is a change of state caused by one single ionizing particle (ions, electrons, photons...) striking a sensitive node in a live micro-electronic device, such as in a microprocesso ...
*
8-N-1
8-N-1 is a common shorthand notation for a serial port parameter setting or configuration in asynchronous mode, in which there is one start bit, eight (8) data bits, no (N) parity bit, and one (1) stop bit. As such, 8-N-1 is the most common c ...
*
Check digit
A check digit is a form of redundancy check used for error detection on identification numbers, such as bank account numbers, which are used in an application where they will at least sometimes be input manually. It is analogous to a binary parity ...
References
{{reflist
External links
Different methods of generating the parity bit, among other bit operations
Binary arithmetic
Data transmission
Error detection and correction
Parity (mathematics)
RAID
fr:Somme de contrôle#Exemple : bit de parité