Parity Error and correction

This might be of interest to some (heh)
I am sure people (some again) may have heard of PAR archive's etc. What is a PAR file anyhow?
The simple version is PAR is short for PARITY. Parity refers to the count of 1's bits in a string of bits (byte word double word quad word are strings of bits).

So .. what's the deal?
Let's say we have Data sets A B C D E F G H and P (P for parity)
where A XOR B ...G XOR H = P
The exclusive or (XOR for short) is used to generate parity because by nature (see table) it will indicate there is an odd or even number of 1's bits in a given word.
Say A and B are 2 bits of a binary string, the XOR table shows that if they are both 0 there is an EVEN number of 1's if both are 1 then there is also an even number of 1's.

XOR gates can be cascaded to generate the same parity over a larger number of bits.

If you wish to play with an XOR gate to see for yourself try this URL. click on F and G and watch I21 output to see what happens.

Cascading them is simply wiring the output of 2 gates to another XOR gate in series.
Therefore A XOR B ... G XOR H is the same as ((A XOR B) XOR (C XOR D))XOR((E XOR F)XOR(G XOR H)). ( I suppose I could write the C ^ symbol for XOR operator however I'll restrain myself).

P = this value is the parity data generated by all that bitting around.

So lets say one of those bits gets corrupted? What do you do?
So lets say it's bit C (why not?), well first the parity of C would be reversed of it's original state. That means the parity is changed. This also means that you know that block of data is wrong. Hence this is called the PARITY CHECK.

Now how do we correct this? Ahhh that's the rub isn't it?
It turns out C = A XOR B XOR D XOR E XOR F XOR G XOR H XOR P, thus we know what C is by the parity bit.

This is by no means a very acurate method of error correction. Trust me it's not very good at all but gives you an idea of what is going on and what one can do with just a simple logic gate to fix errors.

Until the next illogical write up.

Cyb

ACK Reed Solomon is WAY beyond the scope of a simple tutorial!
RS is very handy etc. However it's not exactlly simple or easy to implement. I wouldn't try implementing it with a microcontroller. Right now I'm looking at simple error correction (although I am looking at use of parity codes with a CPLD and NAND flash for a microcontroller based system).

Hamming codes will be next then complete parity codes and such. This is just one half the code on generating the codes. Then you have to know how to use them (IE error correction).

Cyb

Parody of Parity (warning this is riddled with bad puns)

So We continue on with this months installment of "what bit am I on!"

Homour aside parity checks alone alone just say "you are a bit off" (1 bit normally) however, how do you FIX the bit?
From the previous lesson we learned "parity is they number of 1's in a string of bits" If you use a single parity bit in a byte for example, you can know if the byte has a high probabilty of bit twiddled issues.


So how do we 'fix' the bit that's off?
First we must find the bit that is off.
A simple place to start is the proverbial byte or a string of 8 bits.
We will not make grandios conclusions before something is proven.
The majority of data in a computer is organized in bit strings that are base 2 in length. The byte (8bits) is a 3rd order length IE 2 to the 3rd power is 8. The nice thing about the number 2 is it's easy to divide and conquer the data with.
Our first truely crappy diagram shows parity groups (IE groups of bits for parity). To flip the right bit the best thing to do is use binary tree traversal. Each group of bits can be isolated as having the wrong number of 1's in it. This is why base 2 strings is important in this form of error correction.
Our parity groups are labeled P1, P2, P3, P4, P5, and P6.
Assuming the bits of a byte are ordered bit0 to bit7 IE
Then Notice it requires 6 values in order to do this correctly.
From these parity bits on a single byte you can find 2 errors and correct 1 bit.
P1/P2 you can think of these as the lower bit of an address (in a computer your address bus is N bits and this addresses 2^N words of memory). So if the address of the bit we are looking for was A A0 (bit A0) would be determined by the comparison (exclusive or) of P1/P2 of the current word and the parity check bits. A1 (bit A1) of this address uses P3/4 and A2 uses P5/P6. If you XOR the bit addressed by address A with 1 you will have the correct bit fixed (of course if the parity bits are matched this operation exclusively ors it with 0 and as a result does nothing).

This method can be expanded across numerous bytes as well. Now some analysis. Notice the power of 2 factor. Notice 6 bits are needed for an 8 bit string. Extending this method to 512 byte (4096 bits) string, the number of bits needed to perform a single bit correction (and find 2 bad bits) happens to become 24 bits. The number is 2N to remember. Where N is the power of 2 length of bits you are looking at. A 512 byte string would be 24bits (2^12 N = 12 2N = 24).