Difference between revisions of "Error Correction"

From AQA Computer Science
Jump to: navigation, search
(Overview)
(Revision Questions)
(One intermediate revision by the same user not shown)
Line 50: Line 50:
 
=Revision Questions=
 
=Revision Questions=
 
<quiz display=simple>
 
<quiz display=simple>
 
 
{Is the 8-bit binary number "01101001" valid using Even parity or Odd parity?
 
{Is the 8-bit binary number "01101001" valid using Even parity or Odd parity?
 
|type="()"}
 
|type="()"}

Revision as of 13:19, 10 October 2019

Overview

CraigNDave

https://www.youtube.com/watch?v=bUtafZywvSQ&list=PLCiOXwirraUBIKvhutnNnMkVTpQ_psPN2&index=2

Computer Science Tutor

https://www.youtube.com/watch?v=9uAIGQBkQzc&list=PL04uZ7242_M6O_6ITD6ncf7EonVHyBeCm&index=7

TRC PowerPoint

Error Checking & Correction

Parity Checks

One method of error checking would be parity bits which appends a 1 or 0 to the end of 7 bit packet. This additional bit is for even parity and odd parity error checking. Parity checks are a method of error detection only.

Even parity Even parity will check to see if there is an even number of 1's in the first 7 bit of the packet. If there is an even amount, there would be a number 0 appended to the packet, otherwise 1 would be appended to the end of the packet. If there would have been an error in the transmission, the receiving party would receive the packet with either an even number of 1's in the packet but "0" parity bit at the end of the packet or an odd number of 1's in the packet but a "1" parity bit.
Odd parity Odd parity will check to see if there is an odd number of 1's in the first 7 bit of the packet. If there is an even amount, there would be a number 0 appended to the end of the packet, otherwise 1 would be appended. If an error occurred in the transmission, the receiving party would receive the packet with either an even number of 1's in the packet but "1" parity bit at the end of the packet or an odd number of 1's in the packet but a "0" party bit.

However, if there were 2 bits that were transmitted with errors, then the check would not find the errors and it will be sent regardless, causing the parity check to not work.

Majority Voting

Majority voting sends the same bit 3 times and goes with the most common bit for example instead of sending a 1 it would send 1 1 1 and if there was an error it would be 1 1 0 but as there are 2 ones That is what will be used.

Sending 0110 would be sent 000 111 111 000. This means if an error occurs it wont change the data as an error in 0110 might be 1110, Which would be completely different however if an error occurs in 000 111 111 000 It might be 010 111 110 000 But the data wouldn't be different as it would still be read as 0110.

If 2 errors occur in the same 3 bits, the result of the majority voting will result in the wrong bit, changing the output? completely but failing to detect the error. For example, the binary number 010 would ideally be transmitted as 000 111 000. However, if two errors occurred in close proximity, such as 011 111 000, it would be read as 110. This is a downside to majority voting.

Another disadvantage of majority voting is that it can triple the amount of data sent, as each bit needs to be transmitted three times.

Check Sums

A check sum is another form of error correction. A check sums is a method or algorithm to calculate a check value, this value is transmitted separately from the data.

For example, websites which allow you to download large files often provide a checksum value on the page, once you have downloaded a file you can run the checksum method or algorithm and compare your check value with the original value on the site.

The method or algorithm can be simple or complex, a simple method could be to add together every byte of data and then divide by the number of bytes. Remember check sums are trying to verify the data and could be applied to any type of file.

Check Digits

A check digit is an additional digit included at the end of the transmitted data. Check digits are used for error detection, and can be used to ensure that the data received is valid and correct.

A common use of check digits is in International Standard Book Numbers (ISBN) found under bar codes on books. An ISBN is a 10 or 13 digit number; the last digit in the sequence is a check digit generated from the other 12 and is used to check they are correct.

Revision Questions

1. Is the 8-bit binary number "01101001" valid using Even parity or Odd parity?

Even parity
Odd parity

2. Is the 8-bit binary number "11111110" valid using Even parity or Odd parity?

Even parity
Odd parity

3.

Using Majority Voting, what would the transmission "010110111000110101111001" be interpreted as?

4.

Calculate the checksum for "11000101 00001111 00101110".

5.

Find the check digit for the 13 digit number, "1338564796583"

6. Perform an even parity check on 1101110111011110

First and second bytes are valid
This is the correct answer as the first byte has 5 ones and a parity bit of one making it valid by even parity, the second byte has 6 ones and a parity bit of zero meaning it is also valid by even parity.
First byte is invalid, second byte is valid
This answer is half correct as the first byte has 5 ones and a parity bit of one making it valid by even parity, the second byte has 6 ones and a parity bit of zero meaning it is also valid by even parity.
First and second bytes are invalid
This answer is incorrect as the first byte has 5 ones and a parity bit of one making it valid by even parity, the second byte has 6 ones and a parity bit of zero meaning it is also valid by even parity.
first byte is valid, second byte is invalid
this answer is half correct as the first byte has 5 ones and a parity bit of one making it valid by even parity, the second byte has 6 ones and a parity bit of zero meaning it is also valid by even parity.

7.

Find the check digit for the 20 digit number, "12657894562545896716"

8.

Find the check digit for the 11 digit number, "9997586738824"

Your score is 0 / 0