Error Codes

concept

In real world systems mistakes happen, logic highs and lows can sometimes be corrupted and show as the wrong value. In fact, it happens pretty regularly, especially when transmitting data wirelessly. An error code is an extra bit of data stuck onto the end of the data you want to send that lets the receiver know whether it was sent correctly. The error code won't prevent error but if one occurs it lets the receiver know and the receiver can tell the transmitter to send that piece again. Without error codes and error checking almost every website you visited would have bizarre garbage scattered throughout it as errors in the transmitting sent data that didn't make sense to your browser.

The simplest type of error checking is the parity bit. A parity bit will let the receiver know if an odd number of the bits in the transmitted data have been corrupted. That just one bit gets corrupted is quite common so this kind of error checking is more convenient than it might seem. Additionally parity checking is very fast and doesn't require sending much extra data, so it's a popular error checking method.

fact

A parity bit is an extra bit at the end of a piece of transmitted data which tells the receiver whether the number of "1"s in the data is even or odd.

fact

An even parity system sets the parity bit to "0" when the number of "1"s in the data is even. An odd parity system sets the parity bit to "0" when the number of "1"s in the data is odd.

fact

The total number of "1"s (including the parity bit) is always even for even parity systems and always odd for odd parity system.

fact

The parity bit is added either at the beginning of the data or at the end, both the receiver and transmitter must know beforehand which it will be.

example

Determine the parity bit for the data $0110$ in an even parity system.

In an even parity system the total number of 1s is even, our data already has two 1s so our parity bit will be 0.

$01100\quad \text{with parity bit at the end}$

So say our transmitter is an even parity system and wants to send the

$0110$ data like in the above example, it generates the parity bit 0 and sticks it on the end to send

$01100$ to the receiver. Along the way the first bit gets corrupted and becomes a 1 so our receiver actually gets

$11100$ at its end. Now it counts all the 1s and realises something terrible.

$\text{Odd number of 1s in even parity system} \\ 11100$ It's an even parity system but it received an odd number of 1s, so somewhere along the way there must have been an error. So our receiver tells our transmitter than the last lot of data didn't transmit properly so the transmitter can try again.

fact

A parity bit can't tell the receiver which bit is corrupted when there's an error, only that there was a corruption

Now what if two bits get flipped during transmission? Say our transmitter is again trying to transmit

$0110$ and it sticks on the even parity bit 0 and transmits

$01100$ Along the way the first two bits get corrupted and the receiver actually receives:

$10100$ Now the receiver checks the parity and sees everything as fine, even though the data has been corrupted the receiver thinks everything worked! Luckily as long as we keep our data segments short the parity bit checker is quite good as having only one bit flip is the most common error (unless you're trying to send dozens, or hundreds, of bits per parity bit).

Parity bits are nice but for some situations we need something that's able to detect errors in 2, 4, 6, 8 bits etc. One very popular method for this is Cyclic Redundancy Check (CRC). CRC is a more complex method but once you get it you'll have no troubles.

fact

CRC is able to detect more errors than parity bits.

fact

In CRC a code is generated (just like a parity bit, but multiple bits) and appended to the end of the data to be sent.

fact

Part of the CRC process requires modulo-2 division. This is just like usual long division but the subtraction steps are replaced by the XOR (you'll learn this later) operation on each column. If two bits are the same the result is 0 if they're different the result is 1.

This modulo-2 division process is simple but sounds complicated when you try to read the instructions so instead we're going to do an example to cover the steps. To calculate a CRC code we don't need the quotient of the division, just the remainder, so we won't be writing anything above the division line, this also makes the steps a little simpler to explain.

example

Compute the remainder of the modulo-2 division of $10011 \over 1110$

First we'll write this up like a regular binary long division problem.

$1110\ \overline{\big)10011}$ Now the leftmost bit of our dividend is 1 so we write our divisor beneathe it and do our XOR operation on the columns of bits:

$1110\ \overline{\big)10011} \\ \ \ \ \ \ \ \ \ \ 1110 \\ \ \ \ \ \ \ \ \ \ \overline{0111} \\$ You can see that whenever the bits were different we wrote a "1" and whenever they were the same we wrote a "0". Now for the next step you can see that our XOR operation result has a single "0" out the front, that means we bring down a single number from the dividend. If there had been two leading "0"s we'd have brought down two new numbers and so on. So we bring down the next number and repeat our process:

$\begin{align} & 1110\ \overline{\big)10011} \\ & \ \ \ \ \ \ \ \ \ \ \ 1110\;| \\ & \ \ \ \ \ \ \ \ \ \ \ \overline{0111}1 \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ 1110 \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \overline{0001} \\ \end{align}$ Now we're out of digits in the dividend so our remainder is 1.

fact

To generated a CRC code:

Sender and receiver agree on a fixed generator code
Append a number of 0s to the data equal to the number of bits in the generator code $-1$
Divide this new data by the generator code using modulo-2 division
Add the remainder of the division to the 0-padded data
Send your new data code

example

Find the data transmitted by a CRC system with data $10011$ and generator $1110$

This question is asking us to find what a CRC system will send if the data it's given is

$10011$ and it uses a generator

$1110$ to find the CRC code. So we'll follow the above steps. First we padd the data bits with three 0s. We use three because our generator is four bits long. So our new data string is:

$10011000$ Now we need to find the remainder when we use modulo-2 division of

$\frac{10011000}{1110}$ (that's our padded data over our generator). The division starts out the same as before so we'll skip right to that point:

$\begin{align} & 1110\ \overline{\big)10011000} \\ & \ \ \ \ \ \ \ \ \ \ \ 1110\;| \\ & \ \ \ \ \ \ \ \ \ \ \ \overline{0111}1 \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ 1110 \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \overline{0001} \\ \end{align}$ Now our XOR operation gave us a result with THREE leading 0s so we bring down the next THREE digits from the dividend.

$\begin{align} & 1110\ \overline{\big)10011000} \\ & \ \ \ \ \ \ \ \ \ \ \ 1110\,|\,|\,|\,| \\ & \ \ \ \ \ \ \ \ \ \ \ \overline{0111}1\,|\,|\,| \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ 1110\,|\,|\,| \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \overline{0001000} \\ \end{align}$ Now we write down our divisor and do our XOR operation again:

$\begin{align} & 1110\ \overline{\big)10011000} \\ & \ \ \ \ \ \ \ \ \ \ \ 1110\,|\,|\,|\,| \\ & \ \ \ \ \ \ \ \ \ \ \ \overline{0111}1\,|\,|\,| \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ 1110\,|\,|\,| \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \overline{0001000} \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 1110 \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \overline{0110} \\ \end{align}$ So we're out of digits in the dividend and our remainder is

$0110$ . Our final step is to add this remainder to our padded data:

$10011000 + 0110 = 10011110$ And we send that off to our receiver.

When the receiver gets the data they'll divide it by the generator and if the remainder is 0 they know it probably isn't corrupted. If the remainder ISN'T 0 then the receiver knows the data definitely was corrupted and they request that data from the transmitter again.

practice problems