Error checking and correction

Parity bits, majority voting, checksums and check digits, with checksums on the robot's radio messages.

A7.6Data representationA level30 min

Bits get corrupted. Radio interference flips a bit in a message, a scratch damages a disc, a person mistypes a code. A robot that obeys LEFT 90 when it was sent LEFT 10 is a hazard. The methods in this lesson add a little extra data, calculated from the real data, so the receiver can detect that something went wrong, and in some cases correct it.

Parity bits

A parity bit is one extra bit added to a group of bits so that the total number of 1s is even (even parity) or odd (odd parity). Sender and receiver agree which in advance.

With even parity and 7-bit ASCII, the parity bit goes in front to make a byte:

The receiver counts the 1s in each byte. An odd count under even parity means an error.

def even_parity_byte(code7):
    ones = bin(code7).count("1")
    return (ones % 2) << 7 | code7     # put the parity bit in bit 7

def parity_ok(byte):
    return bin(byte).count("1") % 2 == 0

sent = even_parity_byte(ord("G"))
print(format(sent, "08b"), parity_ok(sent))
damaged = sent ^ 0b00000100            # one bit flipped in transit
print(format(damaged, "08b"), parity_ok(damaged))
twice = sent ^ 0b00000110              # two bits flipped
print(format(twice, "08b"), parity_ok(twice))

Run this in the simulator

Parity is cheap, one bit per byte, but it has two limits. It detects any odd number of flipped bits and misses any even number, and it cannot say which bit is wrong, so it cannot correct anything. The receiver has to ask for the data again.

Majority voting

In majority voting each bit is sent an odd number of times, usually three. The receiver takes whichever value appears most often in each group.

A single flipped bit in a group is corrected, not just detected, with no need to resend. The cost is size: the data triples. Two flips in the same group give the wrong answer without warning. It suits links where resending is impossible or slow, such as a space probe.

Checksums

A checksum is a value calculated from a whole block of data and sent with it. The receiver does the same calculation on what arrived and compares. If the two differ, the data (or the checksum) was corrupted, and the block is sent again.

A simple checksum adds the byte values of a message and keeps the remainder after dividing by 256, so it fits in one byte. The robot's radio messages are text, so this lesson sends each command followed by a star and the checksum in two hex digits:

def checksum(text):
    return sum(ord(ch) for ch in text) % 256

for text in ["GO 20", "G0 20", "OG 20"]:
    print(text, format(checksum(text), "02X"))

Run this in the simulator

G0 20 (with a zero) is caught. But OG 20 has the same checksum as GO 20: adding is the same in any order, so a simple sum cannot detect characters that have swapped places. Real protocols use stronger checksums, such as cyclic redundancy checks (CRCs), that weight each byte by its position. A checksum only detects errors; it cannot correct them.

Check digits

A check digit is a digit added to the end of a code number, calculated from the other digits. It catches the mistakes people make when typing or reading numbers, such as one wrong digit or two digits swapped. Barcodes and ISBNs use them.

ISBN-13 multiplies the digits alternately by 1 and 3, adds the results, and picks the check digit that makes the total a multiple of 10. For the first twelve digits 978030640615:

digits   9  7  8  0  3  0  6  4  0  6  1  5
weights  1  3  1  3  1  3  1  3  1  3  1  3
products 9 21  8  0  3  0  6 12  0 18  1 15   total 93
check digit = (10 - 93 mod 10) mod 10 = 7      ISBN 9780306406157

Because neighbouring digits have different weights, swapping two neighbours usually changes the total, which a plain sum would miss. (It misses a swap of neighbours that differ by 5, since 5 × 3 and 5 × 1 end in the same digit.)

Comparing the methods

Task: checksums on the radio

Write checksum(text). The parameter text is a string. It returns the sum of the character codes (use ord) modulo 256, as a string of exactly two uppercase hex digits (you may use format(n, "02X")).

1. For each command in GO 20, LEFT 90, STOP, in that order, build the packet <command>*<checksum>, send it with send(), and print sent <packet>. Send the packet you built, not typed-in text.
2. For each packet in received, split it at the *, recalculate the checksum of the text part and print <packet> ok if it matches the checksum that arrived, or <packet> corrupt if it does not.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

def checksum(text):
    return "00"

received = ["GO 20*18", "G0 20*18", "STOP*46", "LEFT 80*B4"]

Challenges

1. Show a corruption of STOP that the checksum misses.
2. Send each byte of GO three times as bits and write the majority-voting decoder.
3. Weight each character code by its position before adding. Does OG 20 now get a different checksum from GO 20?