Parity is a property of a binary string.  A binary string with even parity has an even number of ‘1’s.  A binary string with an odd number of ‘1’s is said to have odd parity.  Notably, zero is considered even.

A parity code can be devised so that all code words are even, meaning that each code word is even.  At first glance, this can appear wasteful because it is easy to show that half of the possible code words are odd and are not valid members of the parity code.  Consider a the scenario where a binary string is transmitted across a noisy communications channel.  Because of the noise, its possible that one of the bits being communicated can be changed, either from a ‘0’ to ‘1’ or ‘1’ or ‘0’.  When this happens as a result of the bit in error, the parity changes from even to odd.  Further, the error can be detected upon receipt and corrective actions can be taken.

A simple way to create a parity code is to take a simple code, such as ASCII and add a bit.  This bit is called the parity bit.  Further, this type of code is a separable code because the original data is copied directly into the code and the parity bit is a separate bit. The value of the bit is selected so that when you combine the simple code and the parity bit, the parity is either even or odd.  Here is a couple examples of even parity.

Character	ASCII	Parity Bit	Parity Code
‘d’	“1100100”	‘1‘	“11001001“
‘A’	“1000001”	‘0‘	“10000010“
‘5’	“0110101”	‘0‘	“01101010“
‘$’	“0100100”	‘0‘	“01001000“

Likewise, here are a couple of examples of odd parity.

Character	ASCII	Parity Bit	Parity Code
‘d’	“1100100”	‘0‘	“11001000“
‘A’	“1000001”	‘1‘	“10000011“
‘5’	“0110101”	‘1‘	“01101011“
‘$’	“0100100”	‘1‘	“01001001“

The idea of parity parity codes can be extended to devise a code that not only permits detection but also correction of bit errors.  These so called error correcting codes employ multiple parity groups each with its own parity bit.  Bits are assigned to parity groups in such a way that individual bit error exhibits parity errors that uniquely identifies the bit in error.  Assume that you have 8-bit data and wish to transmit the data so that you can detect and correct errors.  Since you have eight bits, you must distinguish among eight possible errors, which requires the addition of some parity bits.  When you include the parity bits, the parity bits themselves can have errors as well, so you must differentiate the parity errors from the data bit errors.  It can be shown that four parity groups are sufficient in order to detect and correct individual bit errors.  The bits will be assigned to parity groups as follows:

Data: D= D₇ D₆ D₅ D₄ D₃ D₂ D₁ D₀

Parity groups
PG0: {D₀ D₂ D₄ D₆ P₀}
PG1: {D₀ D₃ D₄ D₅ P₁}
PG2: {D₁ D₂ D₃ D₇ P₂}
PG3: {D₄ D₅ D₆ D₇ P₃}

The relation between the data, parity, & parity groups and their relationship to bit errors is easily illustrated in the following table.

Bit	0	1	2	3	4	5	6	7	8	9	10	11
Data	P0	P1	D0	P2	D1	D2	D3	P4	D4	D5	D6	D7
P0	*		*		*		*		*		*
P1		*	*			*	*			*	*
P2				*	*	*	*					*
P3								*	*	*	*	*

Inspecting each column, you can see that each bit belongs to a unique set of parity groups.  Further, if a bit is in error, it will result in parity errors for cells with a *.  For example, if the bit D₄ is in error, parity errors will show up in PG0 and PG3.  The convention in ECC is to show the parity errors for all groups, typically called the syndrome.  With no errors for parity groups PG1 and PG2 in this case the syndrome P₃ P₂ P₁ P₀=1001.

 

About me.

© 2016 AMRAP Software, LLC.