Error checking and correction

Parity Bit

An extra (parity bit) is a bit added to the bit pattern for error checking.


Computer systems can use one of two parity systems:


  1. Odd parity - In odd parity there must be an odd number of 1 bits.
  2. Even parity - In even parity there must be an even number of 1 bits.


Examples:


The 7 bit ASCII code for the character J (CAPS) is 1001010 (74)


Odd parity - a 0 is added to keep the total of 1 bits as 3 (an odd number) 01001010


Even parity - a 1 is added to make the total of 1 bits 4 (an even number) 11001010


If an ASCII character is transmitted using odd parity, the receiver will check the parity after the transmission and if the parity is now even there will have been an error in the transmission.

Majority Vote

Majority vote is the process in which each bit three times and use the idea of a 'Majority vote' to determine the correct bit (that was supposed to be sent).


Example:


To send the bit pattern (01011101) 000111000111111111000111 would have to be transmitted.

Interference could cause this bit pattern to be received differently it could be transmitted as : 010110100110011101000011


As every 3 bits represents 1 bit, the majority in each 3 wins the majority vote and becomes assumed to be the 1 bit. So 010 at the start of the false transmission will be interpreted correctly as '0' because there are more 0's in the 3 bits than there are 1's.


The second three bits in the error effected transmission are 110, this means that because of majority vote the second bit is interpreted as 1.


Both of the above examples have been accurate because they have matched the 01 pattern that the correct transmission takes. If the error transmissions first 3 bits had come through as 101 then majority vote would have assumed that the first bit being represented was a 1, which would be incorrect.


Issues:


  • Different interference levels can occur and this could cause the majority vote to give the wrong answers when used (can be inaccurate quite often).
  • Three times the data is sent when you use majority vote (more expensive).

Gray code

Gray code is a method used to ensure that binary numbers are kept intact by making it so that two consecutive values only differ in 1 bit. Gray code counters consume only half the electrical power of an equivalent binary counter.


How to convert Binary to gray code:


Take the most significant bit and keep it, then put every pair of numbers after the first bit through an XOR gate.



0 XOR 0 = 0
1 XOR 1 = 0
1 XOR 0 = 1


0110

Keep the 0 (M.S.B)

0110: 0 XOR 1 = 1 (01 so far)

0110: 1 XOR 1 = 0 (010 so far)

0110: 1 XOR 0 = 1 (0101 final)

answer:= 0101


Converting Gray Code to Binary:


Example:


101011

1 stays the same (M.S.B) XOR this first value against the second value from the Gray code (which is 0 in this case)

M.S.B XOR 0 =1 (After you have calculated the next XOR result you keep adding them as the next digits to create your binary number )(11???? so far)

take the second bit as a 1 which you just got through the XOR and XOR it with the third value from the Gray code (which is 1 also).

1 XOR 1 =0 (110??? so far)

take this newly found 0 and XOR with the fourth value from the Gray code (which is 0)

0 XOR 0 = 0 (1100?? so far)

take the 0 XOR with fifth value ( is a 1)

0 XOR 1 = 1 (11001? so far)

take the 1 XOR with sixth value ( is a 1)

1 XOR 1 = 0 (110010 so far)

Result: 110010