Saturday, 10 August 2019

More On Error Detection

Well, we have already looked at some basic forms of error detection in a previous post (though annoyingly much of this subject covered areas that we have already covered), so instead of going over old ground I will instead refer you back to the post that covered Hamming Code and SECDED error detection techniques. However, just to be painful, these aren't actually the only forms of error detection out there, particularly since there is more to errors than just single bit errors.

Sure, computers these days may be efficient enough that double bit errors are an extreme rarity, and errors of more than two bits pretty much never happen, however we are talking about what goes on inside the computer. Things are very different when we are talking about transferring data between computers, particularly over wireless frequencies. You see, while we might get single and double bit errors, there is also another type of error that might occur - the burst error. This is where multiple bits are effected, and could occur in multiple ways, such as, say, a sun spot causing interference with our wireless transmission. In fact, interference is a very big problem when it comes to such transmissions, so we need a way to be able to detect them.

That is just a simple diagram to show how or why a burst error can occur. Here is a diagram showing what a burst error could look like:

As mentioned previously, error detection works on the process of redundancy, that is by adding extra bits to make sure that the data that is received is the correct data. These bits are known as parity bits. However, the problem with the error detection systems that we explored in the previous post is that while it is all well and good for single, and even double, bit errors, they are completely useless when it comes to burst errors, and this is the type of error detection that we want to be able to detect.

So, there are a couple of methods available to us.

Two Dimensional Parity Check 

In this method we basically place the bits into a series of rows. Once again, like the other parity bits we chose whether we want it to be even or odd. Say we want it to be even, so at the end of the row we will have a parity bit that will make all the ones in the row even, so if there is an odd number of 1s then the parity bit will be 1 otherwise it will be zero.

However, there is a second dimension to this method. Note how we mentioned that we would place the streams into rows. Well, you then go down the columns, and have a parity column. Once again, if the number of 1s in the column is odd then the bit in the parity row is 1, and vice verse.

You might have realise that we will then have a cell, the one that is at the intersection of the parity column and parity row. So, what goes in there. Well, once again a parity bit for the row and the column.

Let us do this with the following bit streams: 1100111, 1011101, 0111001, 0101001.


That might look a little confusing, but eventually it will make sense. So, if one, or more, of the bits come through in error, they can be detected. In fact, with the parity-parity bit in the corner, can detect them, as well as the ones in the column.


So, you can see how were have changed two of the bits on the first row. Sure, the parity bit on row 1 won't register an error, but the parity bits on column 3 and 4 will register an error. Yet there is still a problem. Consider this.


These four bits have come across in error, and rows 1 and 2 won't register the error, neither will columns 3 and 4. Unfortunately there are flaws. As such, we need something just that little bit more complicated.

Cyclic Redundancy Check (CRC)

Are you familiar with polynomial long division. In fact, are you familiar with polynomials. Well, this video might not explain polynomials (you will need to go elsewhere for that, maybe Kahn Academy).

CRC is actually one of the more powerful, and most common forms of error detection, probably because it is accurate, and it works. Okay, it might not be able to correct errors, but it certainly can detect them.

So, we have a block of k bits, and the transmitter generates a series of n bits known a the Frame Check Sequence (FCS). The FCS is then added to the block, and the block that happens to be k+n is exactly divisible by a predetermined number. So, if when the frame is received, the remainder is 0, then there is no error. Otherwise the frame is discarded and a resend request is then made.

So, to do this we need some definitions:
  • M(x) is the message that has a k-bit sequence;
  • P(x) is the generator polynomial represented in an n-bit sequence;
    • P(x) is fixed for a given scheme;
    • P(x) is known by both the sender and the receiver;
  •  Create a block polynomial F(x) based on M(x) and P(x);
    • F(x) is divisible by P(x);
Let us see how we can turn a binary number into a polynomial. We will start with the binary number 110010101.

It is then turned into a polynomial as follows:

1* x8 + 1* x7+0*x6 + 0* x5+1*x4 + 0* x3+1*x2 + 0* x1+1*x0

Well, x0 is 1 so we can get rid of that. Also, anything multiplied by 0 is going to be 0, so we can get rid of them. We will also drop the 1s, because they are redundant. So, we are left with the following:

x8 + x7+1*x4 +1*x2 +1

Now that we have worked that out, let us get onto some polynomial division.

At one end we have the following:

M(x) = 100100
P(x) = 1101
n = 3.

We get n by looking at P(x) and noting that the highest bit is three, so that will be n.

Once we have that, we multiply M(x) by n. So, in this instance we have x3(x5 + x2)

To multiply we basically multiply each one inside the brackets by the one outside. Also, to multiply polynomials, you actually add the indices, as such (x5+3 + x2+3). So, we end up with: x8 + x5.

Clear as mud? I thought so.

Now comes the fun part - we divide xnM(x) by P(x). I'll go through it step by step below:

So, that first x under the divisor sign, well you deduct 3 from the 8 (the 3 coming from the first x) and then write the result above the line.

Next, we multiply x5 with each of the x's that we are dividing by, and write them beneath, as such:

Next, we 'divide' the x that is above, by the x that is below, or you could say that you deduct the indice of the x below from the x above, and if it is, well you don't write it down.

Well, is x7 greater than x3 so we repeat the process all over again:

So, do you see what has happened here? Well, once again x6 is greater than x3 so we continue. In fact, here is the rest:

So, the only thing we are interested in here is the 1 right at the bottom, which is the remainder. In fact the remainder is in reality 001, namely because we take into account all the values lower than x6. We then append the 001 to the end of M(x) and send it, so the message being sent will actually be: 100100001. Once the message is received at the other end, we go through the entire process again, and if the remainder is 0, then there are no errors, but if the remainder is 1, well, there is an error and the frame is discarded.

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License. This license only applies to the text and any image that is within the public domain. Any images or videos that are the subject of copyright are not covered by this license. Use of these images are for illustrative purposes only are are not intended to assert ownership. If you wish to use this work commercially please feel free to contact me

No comments:

Post a Comment