Error Correction

From TRCCompSci - AQA Computer Science
Jump to: navigation, search

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 sum 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: add together every byte of data, 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

try to add more questions on:

  • about checksum, check digits, parity, and majority voting
  • difference between check digits and checksum

Calculating check digit questions should specify which method to use

Also '||' is the feedback for an answer, and could be greatly improved

1. What is a checksum

A method to calculate a check value
Brute force checking of the value
An additional digit included at the end of a binary digit
Checks to see if there is an odd or even number of 1s, and adds a 1 to make it odd or even

2. What is majority voting

it sends the same bit 5 times to check if it is incorrect
the same bit is sent 3 times and goes with the least common bit
the same bit is sent 3 times and goes with the most common bit
it sends bits

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

Even parity
This is correct because the number of 1s present in the 8 bit number is 4, in which is an even number.
Odd parity
This is wrong; the number of 1s present is 4 making it correct under even parity. If the amount was odd it'd be correct under odd parity.

4. Which of the following do apply to a checksum?

The checksum is an integral part of the data transmitted
This is untrue, as it calculates the sum based on the digit sent.
It is an algorithm applied to the data

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

Even parity
Odd parity

6.

Using Majority Voting, what would the transmission "010 110 111 000 110 101 111 001" be interpreted as?
→ The most frequently sent bits in each section will determine which is the correct data that has been sent.

7. How many bits of data have changed in a single bit error

2
3
1

Your score is 0 / 0