All Topics  
Parity bit

 

 
   Email Print
   Bookmark   Link
 

 

Parity bit
 
 
  Topics Parity bit Topic Home

A parity bit is a bit
Bit

A bit is a binary numeral system numerical digit, taking a value of either 0 or 1. Binary digits are a basic unit of information Computer data storage and transmission in digital computing and digital information theory....
 that is added to ensure that the number of bits with value of one
1 (number)

1 is a number, number names, and the name of the glyph representing that number.It represents a single entity, the unit of counting or measurement....
 in a given set of bits is always even or odd. Parity bits are used as the simplest error detecting code
Error detection and correction

In mathematics, computer science, telecommunication, and information theory, error detection and correction has great practical importance in maintaining data integrity across noisy channels and less-than-reliable storage media....
.

As for binary digits, there are two variants of parity bits: even parity bit and odd parity bit. An even parity bit is set to 1 if the number of ones in a given set of bits is odd (making the total number of ones, including the parity bit, even).






Discussion
Ask a question about 'Parity bit'
Start a new discussion about 'Parity bit'
Answer questions from other users
Full Discussion Forum



Encyclopedia


A parity bit is a bit
Bit

A bit is a binary numeral system numerical digit, taking a value of either 0 or 1. Binary digits are a basic unit of information Computer data storage and transmission in digital computing and digital information theory....
 that is added to ensure that the number of bits with value of one
1 (number)

1 is a number, number names, and the name of the glyph representing that number.It represents a single entity, the unit of counting or measurement....
 in a given set of bits is always even or odd. Parity bits are used as the simplest error detecting code
Error detection and correction

In mathematics, computer science, telecommunication, and information theory, error detection and correction has great practical importance in maintaining data integrity across noisy channels and less-than-reliable storage media....
.

As for binary digits, there are two variants of parity bits: even parity bit and odd parity bit. An even parity bit is set to 1 if the number of ones in a given set of bits is odd (making the total number of ones, including the parity bit, even). An odd parity bit is set to 1 if the number of ones in a given set of bits is even (making the total number of ones, including the parity bit, odd). Even parity is actually a special case of a cyclic redundancy check
Cyclic redundancy check

A cyclic redundancy check is a type of function that takes as input a data stream of any length, and produces as output a value of a certain space, commonly a 32-bit integer....
 (CRC), where the 1-bit CRC is generated by the polynomial
Polynomial

In mathematics, a polynomial is an expression constructed from variables and constants, using the operations of addition, subtraction, multiplication, and constant non-negative whole number exponents....
 x+1.

If the parity bit is present but not used, it may be referred to as mark parity, where the parity bit is always 1, or as space parity, where the bit is always 0.

Error detection

If an odd number of bits (including the parity bit) are changed in transmission
Transmission (telecommunications)

In telecommunications, transmission is the process of sending, propagating and receiving an analogue or digital information signal over a physical point-to-point or point-to-multipoint transmission medium, either wired or wireless....
 of a set of bits then parity bit will be incorrect and will thus indicate that an error in transmission has occurred. Therefore, parity bit is an error detecting code, but is not an error correcting code
Error detection and correction

In mathematics, computer science, telecommunication, and information theory, error detection and correction has great practical importance in maintaining data integrity across noisy channels and less-than-reliable storage media....
 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 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 and it requires only a number of XOR gate
XOR gate

The XOR gate is a digital logic gate that implements exclusive disjunction - it behaves according to the truth table above. A HIGH output results if one, and only one, of the inputs to the gate is HIGH ....
s to generate. See Hamming code
Hamming code

In telecommunication, a Hamming code is a linear code error-correcting code named after its inventor, Richard Hamming. Hamming codes can detect up to two simultaneous bit errors, and correct single-bit errors; thus, reliable communication is possible when the Hamming distance between the transmitted and received bit patterns is less than or e...
 for an example of an error-correcting code.

Parity bit checking is used often for transmission of ASCII characters, since they have 7 bits and the 8th bit can conveniently be used as a parity bit.

For example, our parity bit can be computed as follows assuming we are sending a simple 4-bit value 1001, with the parity bit following on the right, and ^ denoting XOR gate:

Transmission sent using even parity: A wants to transmit: 1001 A computes parity bit value: 1^0^0^1 = 0 A adds parity bit and sends: 10010 B receives: 10010 B computes parity: 1^0^0^1 = 0 B reports correct transmission after observing expected even result.

Transmission sent using odd parity: A wants to transmit: 1001 A computes parity bit value: ~(1^0^0^1) = 1 A adds parity bit and sends: 10011 B receives: 10011 B computes overall parity: 1^0^0^1^1 = 1 B reports correct transmission after observing expected odd result.

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, B'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:

Transmission sent using even parity: A wants to transmit: 1001 A computes parity bit value: 1^0^0^1 = 0 A adds parity bit and sends: 10010 *** TRANSMISSION ERROR *** B receives: 11010 B computes overall parity: 1^1^0^1^0 = 1 B reports incorrect transmission after observing unexpected odd result.

B's calculated parity value (1) does not match the parity bit (0) in its received value, indicating the bit error. Here's the same example but now the parity bit itself gets corrupted:

A wants to transmit: 1001 A computes even parity value: 1^0^0^1 = 0 A sends: 10010 *** TRANSMISSION ERROR *** B receives: 10011 B computes overall parity: 1^0^0^1^1 = 1 B reports incorrect transmission after observing unexpected odd result.

Once again, B's computes an odd overall parity, indicating the bit error.

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
Error detection and correction

In mathematics, computer science, telecommunication, and information theory, error detection and correction has great practical importance in maintaining data integrity across noisy channels and less-than-reliable storage media....
.) Consider the same example as before with an even number of corrupted bits:

A wants to transmit: 1001 A computes even parity value: 1^0^0^1 = 0 A sends: 10010 *** TRANSMISSION ERROR *** B receives: 11011 B computes overall parity: 1^1^0^1^1 = 0 B reports correct transmission though actually incorrect.

B observes even parity, as expected, thereby failing to catch the two bit errors.

Usage

Because of its simplicity, parity is used in many hardware
Computer hardware

A personal computer is made up of computer hardware, multiple physical components onto which can be loaded into a multitude of software that perform the functions of the computer....
 applications where an operation can be repeated in case of difficulty, or where simply detecting the error is helpful. For example, the SCSI
SCSI

Small Computer System Interface, or SCSI , is a set of standards for physically connecting and transferring data between computers and peripheral devices....
  and PCI buses use parity to detect transmission errors, and many microprocessor
Microprocessor

A microprocessor incorporates most or all of the functions of a central processing unit on a single integrated circuit . The first microprocessors emerged in the early 1970s and were used for electronic calculators, using Binary-coded decimal arithmetic on 4-bit Word ....
 instruction cache
Cache

In computer science, a cache is a collection of data duplicating original values stored elsewhere or computed earlier, where the original data is expensive to fetch or to compute, compared to the cost of reading the cache....
s 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.

In serial
Serial communications

In telecommunication and computer science, serial communication is the process of sending data one bit at one time, sequentially, over a communication channel or computer bus....
 data transmission
Data transmission

Data transmission is the physical transfer of data from point-to-point often represented as an electro-magnetic Signal over a point-to-point or point-to-multipoint communication channel....
, a common format is 7 data bit, an even parity bit, and one or two stop bits. This format neatly accommodates all the 7-bit ASCII
ASCII

American Standard Code for Information Interchange , is a coding standard that can be used for interchanging information, if the information is expressed mainly by the written form of English words....
 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
Operating system

An operating system is an interface between hardware and applications; it is responsible for the management and coordination of activities and the sharing of the limited resources of the computer....
) via a status bit in a hardware register
Hardware register

In digital electronics, especially computing, a hardware register stores bits of information, in a way that all the bits can be written to or read out simultaneously....
 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).

Parity block

A parity block is used by certain RAID
RAID

RAID is an acronym first defined by David A. Patterson , Garth A. Gibson and Randy Katz at the University of California, Berkeley in 1987 to describe a Redundant Array of Inexpensive Disks, a technology that allowed computer users to achieve mainframe-class storage reliability from low-cost and less reliable PC-class disk-drive componen...
 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, where each column is a disk, assume A1 = 00000111, A2 = 00000101, and A3 = 00000000. 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

Note: Data blocks are in the format A#, parity blocks Ap.

History

A "parity track" was present on the first magnetic tape data storage
Magnetic tape data storage

Magnetic tape has been used for data storage for over 50 years. In this time, many advances in tape formulation, packaging, and data density have been made....
 in 1951. Parity in this form, applied across multiple parallel signals, is known as a transverse redundancy check
Transverse redundancy check

In telecommunications, a transverse redundancy check or vertical redundancy check is a redundancy check for synchronized parallel bit streams that is applied once per bit time, across the bit streams....
. This can be combined with parity computed over multiple bits sent on a single signal, a longitudinal redundancy check
Longitudinal redundancy check

In telecommunication, a longitudinal redundancy check or horizontal redundancy check is a form of redundancy check that is applied independently to each of a parallel group of bit streams....
. In a parallel bus, there is one longitudinal redundancy check bit per parallel signal.

External links