Error checking and correction
Parity Bit
Computer systems can use one of two parity systems:
- Odd parity - In odd parity there must be an odd number of 1 bits.
- 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
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
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