Study Guide

Error Detection

Why data can be damaged on its way across a network, and how parity checks, checksums, echo checks, check digits and automatic repeat query let a receiver notice a mistake and ask for the data again.

Lesson 4.3 Networks, the Internet and Security

For: Cambridge IGCSE Computer Science learners, or anyone who wants to know how a computer can tell that data has been damaged

Stage: Think

A message that changes on the way

In the playground game of whispers, a message is passed along a line of pupils by whispering. By the end, “Meet at the library at three” has become “Eat a pie at the lorry at tea”. Nobody meant to change it.

Think it through

Data travelling through a cable or through the air can be changed in the same way. How might it happen, and how could the receiver tell that a message had been changed, without knowing the original?

Show a model answer

Anything that disturbs the signal can change it: electrical noise from nearby machinery, other signals in a neighbouring wire, a weak signal over a long distance, or a radio signal passing through walls. To tell that a message had changed, the sender could add something extra, worked out from the message, which the receiver can work out again and compare. That is the idea behind everything in this lesson.

When something disturbs a signal on its way, the disturbance is called interference. It can damage data in three ways:

  • data loss: a bit, or a whole packet, never arrives;
  • data gain: an extra bit arrives that was never sent;
  • data change: a bit arrives as the opposite value: a 1 as a 0, or a 0 as a 1.
What kind of damage happened?
Bits sentBits receivedData loss, gain or change?
1011001010010010
101100101011001
10110010101100101

    Show the completed table
    Bits sentBits receivedData loss, gain or change?
    1011001010010010change
    101100101011001loss
    10110010101100101gain

    Stage: Discover

    An extra bit that makes the count of 1s even

    Suppose the sender and receiver agree on a rule: every byte must have an even number of 1s. A byte has eight bits, and the first seven carry the data. The eighth is a spare bit, which the sender sets to 0 or 1 to make the rule come true.

    Think it through

    The seven data bits are 1011001. How many 1s do they hold? What must the spare bit be, so that the whole byte has an even number of 1s?

    Show what happens

    1011001 has four 1s, which is already even, so the spare bit is 0, and the byte is 0 1011001. If the data had held an odd number of 1s, the spare bit would be 1.

    The spare bit is the parity bit. Putting it in the byte so that the number of 1s is even is even parity; making the number odd instead is odd parity. Together, the rule and the process of testing it make up the parity check. The sender and receiver must agree in advance whether they use even or odd parity.

    A sender wants to send the seven data bits 0110100 using even parity.

    1. Count the 1s in the data. 0110100 has three 1s.
    2. Decide what the parity bit must be. Three is odd, so one more 1 makes four, which is even. The parity bit is 1.
    3. Put the parity bit at the left and send the byte. The byte is 1 0110100.
    4. The receiver counts the 1s in the whole byte. If 10110100 arrives, there are four 1s, which is even, so the byte passes the check. If 10110000 arrives, there are three 1s, which is odd, so the receiver knows the byte was damaged.

    For odd parity the steps are the same, but the parity bit makes the total odd, so the same data would have been sent as 0 0110100.

    Parity bits for seven data bits
    7 data bitsNumber of 1sEven parity bitOdd parity bit
    1011001401
    1100110
    0010000
    1111111
    0100001

      Show the completed table
      7 data bitsNumber of 1sEven parity bitOdd parity bit
      1011001401
      1100110401
      0010000110
      1111111710
      0100001201

      Check your understanding

      Two computers use even parity. The byte 10110101 arrives. What does the receiver conclude?
      Show the answer

      Answer: C. There is an error, because the byte has five 1s, which is an odd number.

      Count every 1 in the whole byte: 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1 = 5, which is odd, so at least one bit has changed.

      Apply it

      Using even parity, the byte 01011001 is sent. Interference changes two bits, and 01111011 arrives. What does the parity check report?
      Show the answer

      Answer: A. No error, even though two bits changed: the byte has six 1s, an even number.

      The receiver only sees the byte that arrived. 01111011 has six 1s, an even number, so it passes. Parity can miss an error when an even number of bits change.

      A parity check does not prove that a byte is correct, and it does not say which bit changed. It only shows that an odd number of bits changed. An even number of changes goes unnoticed. This is why parity is often combined with other checks.

      Stage: Predict

      Finding the bit that flipped: parity blocks

      One check on its own cannot say which bit changed. Imagine that, as well as a parity bit for each byte, a whole block of four bytes is sent with one extra byte at the end, made by checking each column.

      Think it through

      Suppose one bit in the middle of a block changes. The parity check of its row will fail, because that row now has the wrong number of 1s. If the columns have a parity check too, what will happen to the column that bit is in? How could the receiver use the two together?

      Show what happens

      The column the bit belongs to will fail its check too. The receiver finds the row that fails and the column that fails. The flipped bit is where they cross.

      A group of bytes sent together is a block. Each byte has its own parity bit. After the last byte comes an extra byte, the parity byte, whose bits are the parity bits of the columns: its first bit makes the first column even, its second bit makes the second column even, and so on. The whole block, with its parity byte, is a parity block.

      Here is a block of four bytes, sent with even parity. P is the parity bit of each row. The parity bit of each column is in the last row.

      RowP1234567
      101011001
      210110100
      301110010
      400001111
      Parity byte10010000

      The sender worked out the parity byte by counting the 1s in each column of the four rows. Do the same for the columns, and check the answer against the last row of the block. Columns P and 1 are done for you.

      The parity byte of the block, one column at a time (rows 1 to 4 only)
      ColumnNumber of 1s in rows 1 to 4Even parity bit for the column
      P11
      120
      2
      3
      4
      5
      6
      7

        Show the completed table
        ColumnNumber of 1s in rows 1 to 4Even parity bit for the column
        P11
        120
        220
        331
        420
        520
        620
        720

        The block is sent, and this arrives. One bit has changed on the way. Find which one.

        RowP1234567
        101011001
        210110000
        301110010
        400001111
        Parity byte10010000
        Count the 1s in each row of the received block (all eight bits)
        RowNumber of 1sPasses even parity?
        14yes
        2
        3
        4
        Parity byte

          Show the completed table
          RowNumber of 1sPasses even parity?
          14yes
          23no
          34yes
          44yes
          Parity byte2yes
          Count the 1s in each column of the received block (all five rows)
          ColumnNumber of 1sPasses even parity?
          P2yes
          1
          2
          3
          4
          5
          6
          7

            Show the completed table
            ColumnNumber of 1sPasses even parity?
            P2yes
            12yes
            22yes
            34yes
            42yes
            51no
            62yes
            72yes

            Check your understanding

            Row 2 fails and column 5 fails; every other row and column passes. Which bit changed, and what was it before?
            Show the answer

            Answer: B. Row 2, column 5, which was 1 before: the bit is now 0.

            Row 2 and column 5 cross at one bit. The row and column checks together locate it, which a parity check on a single byte cannot do. A system can then correct the bit by flipping it, or ask for the block to be sent again.

            Stage: Explain

            A sum worked out from the data: the checksum

            Parity looks at 1s and 0s. A different idea works with the values of the data: the sender adds up the data, and sends the total as well.

            Think it through

            A shop sends four numbers to its head office: 200, 150, 90 and 45. How could it send one extra number that lets the head office check that nothing was changed on the way? What would the head office do?

            Show what happens

            The shop could add the four numbers and send the total with them. The head office adds the four numbers it received and compares its total with the one sent. If the totals are different, something was changed.

            A value worked out from the data by an agreed method and sent with it is a checksum. The receiver works the checksum out again from the data it received. If the two checksums are the same, the data is very likely correct; if they are different, there is an error. Real checksums use many methods; this lesson uses a simple one: add up the byte values, divide the total by 256, and keep the remainder, so that the checksum fits in one byte.

            The data bytes are 200, 150, 90 and 45.

            1. Add the byte values. 200 + 150 = 350, then 350 + 90 = 440, then 440 + 45 = 485.
            2. Divide by 256 and keep the remainder, so that the result fits in one byte. 485 ÷ 256 = 1, remainder 229. The checksum is 229.
            3. The sender sends the four bytes and the checksum 229.
            4. The receiver does the same. Suppose it receives 200, 156, 90, 45. The total is 200 + 156 + 90 + 45 = 491, and 491 − 256 = 235. 235 is not 229, so an error is reported.
            The checksum of the bytes 60, 130, 99 and 180
            StepValue
            Add the first byte: 6060
            Add the second byte: 130
            Add the third byte: 99
            Add the fourth byte: 180
            The remainder after dividing by 256: the checksum

              Show the completed table
              StepValue
              Add the first byte: 6060
              Add the second byte: 130190
              Add the third byte: 99289
              Add the fourth byte: 180469
              The remainder after dividing by 256: the checksum213

              Check your understanding

              The data 60, 130, 99 and 180 is sent with the checksum 213. The receiver gets 60, 130, 99 and 188 with the checksum 213, and works out 221 from the data. What can it conclude?
              Show the answer

              Answer: D. An error has occurred, because 221 is not 213, so the data or checksum changed.

              The values differ, so the receiver reports an error.

              A matching checksum makes an error unlikely, not impossible. The bytes 200, 150, 90, 45 and the same bytes in a different order have the same total, so the same checksum: a swap would not be noticed. Real checksums use more careful calculations, which reduce, but do not remove, this risk.

              Stage: Predict

              Reading the number back: the echo check

              A pupil gives a friend a phone number over a noisy phone line. The friend writes it down and reads it back.

              Think it through

              Why does reading the number back help? And suppose the number read back is different from the number the pupil gave: can the pupil tell whether the friend misheard, or whether the line made a mistake when the friend read it back?

              Show what happens

              The pupil compares the number read back with the one they gave. If the two are the same, it is very likely right. If they differ, the pupil knows something went wrong, but not where: the first message could have been damaged, or the reply could have been.

              An echo check works in the same way. The receiver sends a copy of the data it received back to the sender, who compares it with the original. If the two are the same, the data was probably sent correctly. If they differ, the data is sent again.

              Its weakness is the one in the question. If the data comes back different, the sender cannot tell whether the data was damaged on the way there or on the way back. It also doubles the traffic, because every message is sent twice.

              Check your understanding

              Zara sends the word LIBRARY to a printer, and her computer receives LIBRAAY back. What does the echo check tell her?
              Show the answer

              Answer: C. Something changed somewhere on the round trip, so she sends the word again.

              A difference means an error somewhere on the round trip; the check cannot say where.

              Stage: Discover

              Checking numbers typed by people: check digits

              So far the errors came from interference. Errors also happen when a person types a number wrongly, or a scanner misreads it. A shop has to type or scan the 13-digit number printed under a barcode, and a library the 13-digit number of a book (its ISBN, the International Standard Book Number).

              Think it through

              A librarian types the 13-digit number of a book and makes one mistake in a digit. How could the number be designed so that the computer notices the mistake straight away?

              Show what happens

              The last digit could be worked out from the other twelve by a fixed rule. The computer repeats the calculation on the digits it was given. If the answer does not match the last digit typed, at least one digit is wrong.

              A digit added to the end of a number, worked out from its other digits, is a check digit. It is used for data entry: when someone types a code, the computer repeats the calculation and rejects a number that does not match. Check digits are used in ISBNs and in the numbers under bar codes (the EAN-13 code on most products).

              The rule for ISBN-13 and EAN-13 is:

              1. Multiply the first twelve digits, in turn, by 1, 3, 1, 3, 1, 3 …: weight 1 for the first digit, 3 for the second, and so on.
              2. Add the twelve products.
              3. Find the remainder when the total is divided by 10.
              4. The check digit is 10 minus that remainder. If the remainder is 0, the check digit is 0, not 10.

              To check a complete number, apply weights 1, 3, 1, 3 … to all thirteen digits, including the check digit. The total is a multiple of 10 if the number is valid.

              The first twelve digits are 9 7 8 1 7 1 2 3 4 5 6 7. The weights are 1, 3, 1, 3, 1, 3, 1, 3, 1, 3, 1, 3.

              1. Multiply each digit by its weight. 9×1 = 9, 7×3 = 21, 8×1 = 8, 1×3 = 3, 7×1 = 7, 1×3 = 3, 2×1 = 2, 3×3 = 9, 4×1 = 4, 5×3 = 15, 6×1 = 6, 7×3 = 21.
              2. Add the products. 9 + 21 + 8 + 3 + 7 + 3 + 2 + 9 + 4 + 15 + 6 + 21 = 108.
              3. Find the remainder when divided by 10. 108 ÷ 10 = 10, remainder 8.
              4. Subtract the remainder from 10. 10 − 8 = 2. The check digit is 2, so the number is 9781712345672.
              5. Check it, by including the check digit. The total of all thirteen products is 108 + 2×1 = 110, which is a multiple of 10. The number is valid.

              The ISBN is fictional, worked out for this lesson.

              A product’s barcode starts 501928374650. Find its check digit.

              The check digit of the barcode 501928374650
              DigitWeightDigit × weight
              515
              030
              11
              93
              21
              83
              31
              73
              41
              63
              51
              03
              Total of the products–
              Remainder when divided by 10–
              Check digit–

                Show the completed table
                DigitWeightDigit × weight
                515
                030
                111
                9327
                212
                8324
                313
                7321
                414
                6318
                515
                030
                Total of the products–110
                Remainder when divided by 10–0
                Check digit–0

                Apply it

                A librarian types the ISBN 9780001112323. Multiplying the thirteen digits by 1, 3, 1, 3 … and adding gives a total of 61. What should the system do?
                Show the answer

                Answer: A. Reject it, because 61 is not a multiple of 10: a digit has been typed wrongly.

                The total should be a multiple of 10. 61 is not, so the system rejects the number and asks for it to be typed again.

                A check digit shows that a number was probably typed correctly, not that it is the right number for the right product. A number can pass the test and still be a different, valid number. Also, swapping two neighbouring digits is usually, but not always, noticed: swapping two digits that differ by 5 changes the total by a multiple of 10 and goes unnoticed.

                Stage: Experiment

                Asking for the data again: automatic repeat query

                Checks find errors. Something else must fix them, by sending the data again. A pupil who posts a parcel and asks the friend to “text me when it arrives” has the basic idea: if there is no text after a few days, the pupil sends another.

                Think it through

                A sender sends a packet and waits. Three things could happen: the packet arrives correctly; the packet arrives damaged; the packet never arrives. What should the receiver do in each case, and what should the sender do if it never hears back?

                Show what happens

                If it arrives correctly, the receiver tells the sender so. If it arrives damaged, the receiver tells the sender that it needs to be sent again. If it never arrives, the receiver does not know anything was sent, so it says nothing, and the sender must decide for itself that too long has passed and send the packet again.

                Automatic repeat query (ARQ) is a method in which the receiver checks each packet (with a method such as parity or a checksum) and sends the sender a message, an acknowledgement:

                • a positive acknowledgement means the packet arrived without error;
                • a negative acknowledgement means an error was found, so please send it again.

                The sender also starts a timeout: a fixed period of time it waits for an acknowledgement. If none arrives before the timeout ends, the sender assumes the packet or the acknowledgement was lost, and sends the packet again.

                Three packets sent with automatic repeat query

                Each step names the device that acts. Packet 2 is damaged, and packet 3 is lost.

                1. Sender

                  Step 1 of 7: Packet 1 is sent, and a timeout starts

                  The sender sends packet 1 and starts a timer of, say, two seconds.

                2. Receiver

                  Step 2 of 7: Packet 1 passes the check

                  The receiver checks the packet and finds no error, so it sends a positive acknowledgement.

                3. Sender

                  Step 3 of 7: The acknowledgement arrives before the timeout

                  The sender sees the positive acknowledgement, so it sends packet 2.

                4. Receiver

                  Step 4 of 7: Packet 2 fails the check

                  Interference has changed a bit, so the check finds an error. The receiver sends a negative acknowledgement.

                5. Sender

                  Step 5 of 7: A negative acknowledgement means: send it again

                  The sender sends packet 2 again. This time it passes the check, and a positive acknowledgement comes back. The sender goes on to packet 3.

                6. Sender

                  Step 6 of 7: Packet 3 is lost, so nothing comes back

                  Packet 3 never arrives, so the receiver sends nothing. The sender waits, and the timeout ends with no acknowledgement.

                7. Sender

                  Step 7 of 7: The timeout ends, so the sender sends packet 3 again

                  It sends packet 3 again, and this time it arrives and is acknowledged. If this keeps failing, the sender gives up after a set number of attempts.

                Apply it

                A sender sends a packet and waits. The timeout ends and no acknowledgement of any kind has arrived. What does the sender do?
                Show the answer

                Answer: B. It sends the packet again, because the packet or its reply may have been lost.

                The timeout lets the sender recover from a lost packet or a lost acknowledgement, which nobody would otherwise notice.

                Stage: Consolidate

                Choosing the right check

                Apply it

                A school’s office computer receives a 12-digit stock code typed in by a technician. The office wants the computer to notice a typing mistake at once. Which method should it use?
                Show the answer

                Answer: C. A check digit, worked out from the other digits and repeated when the code is typed.

                For mistakes by a person typing or scanning, a check digit.

                Think it through

                Choose two of the five methods in this lesson (parity, checksum, echo check, check digit, automatic repeat query). Explain, in your own words, how each works, and one thing it cannot do.

                Show a model answer

                A good answer, for two methods, might read: “Parity: an extra bit makes the number of 1s even (or odd); the receiver counts the 1s; it cannot find an error if an even number of bits changed. Checksum: a total of the data, sent with it; the receiver works it out again and compares; two different pieces of data can have the same checksum. An echo check: the receiver sends the data back; it cannot say where an error happened. A check digit: an extra digit worked out from the others; the computer repeats the calculation when a number is typed; it cannot tell that a valid number is the wrong one. ARQ: acknowledgements and a timeout make the sender repeat packets that were damaged or lost; it needs another check to find errors.”

                • Interference can cause data loss, gain or change, so receivers need to check for errors.
                • A parity check adds a parity bit so that the number of 1s in a byte is even (even parity) or odd (odd parity). A parity block adds a parity byte, so that a single flipped bit is found where its failing row and column cross. Parity misses an even number of changes.
                • A checksum is a value worked out from the data, sent with it and recalculated by the receiver. Different values mean an error.
                • An echo check sends the data back to the sender to compare; it cannot say where an error happened.
                • A check digit is an extra digit worked out from the other digits, used in data entry: ISBN-13 and EAN-13 weight the digits 1, 3, 1, 3 … and the total must be a multiple of 10.
                • Automatic repeat query uses positive and negative acknowledgements and a timeout so that damaged or lost packets are sent again.

                Sources and scope

                • What this lesson is. The third lesson of the Networks, the Internet and Security module, written for this site. Its curriculum links are provisional: the wording of each linked specification point has been checked against the published specification, but no link has been verified by the site owner, and the links imply no endorsement by any examination board.
                • Original material. The whispers game, the shop and head office, the library and printer, the ISBN 9781712345672, the barcode 5019283746500, the parity block, the checksum values and every other number are fictional, made up and worked out for this lesson; none belongs to a real book or product.
                • Simplified on purpose. The checksum method (add the bytes and keep the remainder after dividing by 256) is a teaching example: real checksums and cyclic redundancy checks use more careful calculations. Parity is shown with the parity bit at the left of the byte, and a block of four rows, which real systems may arrange differently. ISBN-10, an older number with a different rule, is not taught. ARQ is described in its simplest form, one packet at a time.