Книга: Introduction to Microprocessors and Microcontrollers

Parity

If you were to walk into a crowded room and say ‘Burgers’ and nothing further, many of those present would turn to their neighbours and say ‘What was that?’ and some would just stand and stare. (Some may even mis-hear and feel offended.) As a form of communication, this is not very efficient. Try instead, walking in and saying ‘Lunch will consist of burgers’. Everyone would understand your message.

The first attempt was very efficient in terms of the number of words used but is probably likely to be inefficient communication since many people will not receive the message. In the second attempt, we have used five words to make sure that the one important one gets through. This is called adding ‘redundancy’. The more redundancy we add, the more certain is the message but the slower and less efficient becomes the communication system. Data being returned from space probes use very high levels of redundancy, over 96%, which allows for correction of really scrambled signals due to the extremely low power levels involved.

We can use parity for alerting us to the possibility of an error in a stream of data or, in some cases, we can detect and correct the error. In its simplest form, we take a group of bits in a transmission, 4 or 8 bits are normally used though the idea is applicable to other values. In this example, we will look at a 4-bit group, say 1001. At the transmitting end, we add an extra bit on the end, either a 0 or a 1 to make the total number of ‘1’s an even number. In this case, there are two ‘1’s and so the number is already even, so we add a zero. The data now reads 10010. At the receiving end, if the data has been mutilated and now reads 11010, a quick count will show that there is an odd number of ‘1’s and so an error has occurred.

This simple approach can be easily fooled. If there are two errors there will be an even number of ‘1’s and passed as correct. And, another disappointment, if it shows an error, we cannot tell which bit is wrong and therefore cannot correct it. When this system is used, an error signal is sent back to the transmitter requesting a repetition but this assumes that the transmitter and the receiver are in communication with each other. We can modify the system to make limited automatic correction feasible.

Let’s assume we have, say, 16 bits of data to send.

Step 1 Rewrite the data in the form of a square:

0 0 1 0

1 1 1 1

0 1 0 1

1 0 1 1

Step 2 Add parity bits. Across the top row, we have the numbers 0010 which includes a single ‘1’. In this system, which we will call ‘even’ parity, we add another ‘1’ if necessary to ensure that there is an even number of ‘1’s across the first row. As we have only a single ‘1’, we add another ‘1’ on the end. It now looks like this:

0 0 1 0 1

1 1 1 1

0 1 0 1

1 0 1 1

The top row now has an even number of ‘1’s. The next row has four ‘1’s which is an even number so we do not need to add another ‘1’. We therefore add a ‘0’:

0 0 1 0 1

1 1 1 1 0

0 1 0 1

1 0 1 1

The third row will be completed with a ‘0’ since it contains an even number of ‘1’s and the last row, with three ‘1’s will need an extra one to be added. The result is now:

0 0 1 0 1

1 1 1 1 0

0 1 0 1 0

1 0 1 1 1

Step 3 We now have five columns down the page and we can add extra ‘1’s in the same way to make the total number of ‘1’s an even number. The first two and the last columns each contain two ‘1’s so zeros will be added. The third and fourth columns have three ‘1’s so we need to add an extra ‘1’ to each. The result is now:

0 0 1 0 1

1 1 1 1 0

0 1 0 1 0

1 0 1 1 1

0 0 1 1 0

Notice how we have now got a total of 25 bits to be transmitted. This represents 16 bits of data and 9 bits added to check the accuracy of the data. The final serial transmission is 0010111110010101011100110. This means that 9 out of 25 or 36% of the transmission is not actual data and represents redundancy.

Let’s see how it works. We will assume an error has occurred and one of the bits is received incorrectly so here is the received transmission:

0010111110010101001100110

Step 1 Layout the data as a 5?5 square.

0 0 1 0 1

1 1 1 1 0

0 1 0 1 0

1 0 0 1 1

0 0 1 1 0

Step 2 Check the parity in each row across the square. We decided to make each row and column to have an even parity.

The first row has two ‘1’s, this is even – OK.

The second row has four ‘1’s, this is even – OK.

The third row has two ‘1’s, this is even – OK.

The fourth row has three ‘1’s, this is odd – an error has occurred.

The last row has two ‘1’s, this is even – OK.

We now know that one of the bits in the fourth row has been received incorrectly.

Step 3 Do the same for the columns.

The first column has two ‘1’s, this is even – OK.

The second column has two ‘1’s, this is even – OK.

The third column has three ‘1’s, this is odd – an error exists in column three.

The fourth column has four ‘1’s, this is even – OK.

The last column has two ‘1’s, this is even – OK.

Step 4 Isolate the error and change the data.

The error occurs in the third column and the fourth row. Since this is now known to be an error and we only have a choice of 0 or 1, we can confidently change the 0 to a 1 and recover the correct data stream.

0 0 1 0 1

1 1 1 1 0

0 1 0 1 0

1 0 1 1 1

0 0 1 1 0

In this example, we chose to use even parity, that is, we made each row and column have an even number of ‘1’s. It would work equally well if we used odd parity by making the number of ‘1’s an odd number. It would also work just as well if we counted the zeros instead of the ones. If more than one error occurs, it will warn us of an error but it will be unable to make any corrections. If you try it, you will see that it indicates four possible positions for the two errors and nine for three errors.

Example

Correct this received data which includes one error. To provide automatic correction, odd parity on the ‘1’s has been used.

The received signal: 1101001001111001010101101.

Step 1 Layout the data as a 5?5 square

1 1 0 1 0

0 1 0 0 1

1 1 1 0 0

1 0 1 0 1

0 1 1 0 1

Step 2 Check the columns and rows for an odd number of ‘1’s

1 1 0 1 0 ?

0 1 0 0 1 ?

1 1 1 0 0 ?

1 0 1 0 1 ?

0 1 1 0 1 ?

? ? ? ? ?

Step 3 Isolate the error

1 1 0 1 0 ?

0 1 0 0 1 ?

1 1 1 0 0 ?

1 0 1 0 1 ?

0 1 1 0 1 ?

? ? ? ? ?

Step 4 The data where the column and row intersect is the error. So we simply change the ‘1’ to a ‘0’.

Step 5 Strip out the parity bits to recover the original data

11010000111010100110

Оглавление книги