Parity

Data transfer inevitably threatens data integrity. It does not matter whether you save and restore files on your hard disk or you transmit data over long distances. Bits can always get twisted by interfering electric and electromagnetic fields. TCP/IP uses CRC checksums which often is too complex and too performance-consuming to be used in simple communication systems (e.g. RS-232).

In such simple systems it can be sufficient to use a parity bit to ensure (or at least to improve) data integrity. Since the parity bit is just a bit, its power is limited. It allows you to detect an error, but it won’t tell you which data bit is wrong. Also, if any even number of bits in a word have been affected by interference at the same time, you won’t even see any error at all.

To understand what a parity bit is simply imagine any word of data bits, for example the byte 01000011 (which is 0x43 or ASCII-letter ‘C’). Now attach a bit to this word which ensures that the total word (including the added bit) contains an even number of 1s.

In the example above: 101000011

If the word of data contained only two 1s, you had to add 0. The bit added is called parity bit. In this case we ensure even parity, but you can also opt for odd parity.

Most CPUs internally provide a parity bit often located in the PSW (program status word). It automatically indicates the parity of certain register (e.g. accumulator). Usually the parity bit is determined by a parity decoder. This is a logic circuit which consists of cascaded XOR-Gates. You can easily see the XOR dependency when setting up an according boolean equation. No magic involved.

But have you ever thought of how the parity of n bits could be calculated by software — just for fun?

A hardware parity decoder XOR-combines a bit with the result of the previous bit, which is XOR-combined with the result of the previous bit, which is XOR-combined with … you get the idea.

We can describe this process of subsequent XOR-ing mathematically by the following relationship.

Even Parity, mathematically expressedWhat it represents is a loop which loops over the whole word (from 0 to n-1). In each step it XORs the previous result and a specific bit out out of the data word. The shifting operator (>>) allows us to extract each bit out of the squence by using a mask that has the LSB set.

For those of you who are not feeling comfortable with mathematical descriptions, here is an example program in C. It calculates the even parity of an eight bit word (0…7).

for( i = 0; i < 8; i++ ) {
   parity = parity ^ ( data & 0x01 );
   data = data >> 1;
}

That’s all for now. Have a try and play with it! šŸ™‚

— Andre M. Maier

Advertisements

About bitjunkie

Teacher, Lecturer, and BITJUNKIE ...
This entry was posted in Bit-Twiddling, Uncategorized and tagged , . Bookmark the permalink.