EE4253 Digital Communications Department of Electrical and Computer Engineering - University of New Brunswick, Fredericton, NB, Canada

Ensuring reliable communications depends on information being transmitted and received without error. Even a single error in a binary transmission can destroy the value of the message being sent. There are many ways with which error detection or correction may be accomplished - some are better than others.

Send the Message Twice

An obvious way to deal with the potential for errors in a message is to send the message twice. While this apppears useful, it is also quite expensive in terms of data throughput. Furthermore, even if the two copies differ upon reception, there is still no way to tell which is the correct version. This method accomplishes error detection, but no correction.

      transmitted message                          received message
   SEND $100 NOW SEND $100 NOW ------------> SEND $200 NOW SEND $100 NOW

The value of an error control scheme is measured in:

1. The ability to detect errors;
2. The ability to correct errors;
3. The cost in terms of additional bits on a message.

We note that in many applications, it is sufficient to achieve reliable error detection, as the data can simply be repeated upon request when errors occur. This is know as an Automatic Repeat Request (ARQ) method.

In other cases, no retransmissions are possible (broadcasting information, or reading data from a damaged CD-ROM, for example) and the necessary information to accomplish error correction must be included. This is often called Forward Error Correction (FEC).

EVEN PARITY

The simplest of error detection methods is the well-known addition of a parity bit to a codeword. Typically, a 7-bit value is transmitted with one additional bit chosen to ensure that the total number of '1' bits in the word is EVEN. This is called 'Even Parity'.

In the shorthand of error control codes, this would be called an (8,7) code, since 8-bit codewords are used to send 7-bit data words. For example, the 7-bit message "0101100" is transmitted by appending one bit, either 0 or 1, such that the total number of 1's is an EVEN number. This requires sending the 8-bit codeword "01011001". If a single bit is changed during transmission, the receiver can detect this error by checking the parity of the received codeword, as shown below.

      transmitted message                          received message
       0 1 0 1 1 0 0 1         ------------>       0 1 0 1 0 0 0 1 

Value of simple parity checking:

1. Detection of single-bit errors;
2. No correction possible;
3. Cost is one additional bit per message word.

Finally, we note that a parity generator can be constructed in hardware using nothing more than exclusive-OR (XOR) gates.

The XOR operation accomplishes modulus 2 addition, and an EVEN parity bit can be generated as the XOR of all the message bits.

The parity method works because a single-bit error in any position in a codeword will change the parity from EVEN to ODD. While this observation may seem obvious, a closer study of parity reveals details which will be useful in the study of more powerful coding methods.

Consider all possible 8-bit codewords (there are 256) and all possible 7-bit messages (there are 128). When a given 7-bit message is sent using an 8-bit codeword, it is uniquely mapped onto one of the 256 available 8-bit codewords. Consequently, only 128 of the 8-bit words represent valid messages (in this case, those 128 words having EVEN parity), and these are the only codewords which are ever transmitted. The other 128 8-bit codewords, if received, represent errored messages. The use of EVEN parity is really only one way to map the 128 valid messages onto 256 available codewords. (Use of ODD parity is another way.) The magic of parity, and why it works, is that every valid codeword is exactly one bit error away from an invalid codeword. No single bit error will change a codeword with EVEN parity into another valid codeword with EVEN parity.

The Hamming distance is defined as the number of bit changes required to change from one codeword to another. For example, the codewords P=10101011 and Q=11011011 are separated by a distance of 3 because it is necesary to change three bits to change P into Q.

In the case of parity, there are 128 valid codewords and 128 invalid codewords which are carefully arranged to ensure that there is at least a distance of 2 between any two valid codewords.

Imagine a chessboard with 256 squares. The valid squares are BLUE, while invalid squares are RED. It takes two horizontal or vertical jumps to move from one BLUE square to another. Any single jump in any direction from any BLUE square must necessarily land on a RED square. Note that any other arrangement of the BLUE squares would result in two BLUE squares being adjacent.

Now look at the binary value stored at each square. It takes two bit changes to move from one BLUE codeword to another. Any single bit change in any direction from any BLUE codeword must necessarily land on a RED codeword. Any single bit error in a valid codeword must lead to an invalid codeword. Any other arrangement of these codewords would result in two valid codes being adjacent.

If a set of codewords is defined as above such that the minimum distance between those codewords is at least 2, then single bit error detection is possible. This is what simple parity protection accomplishes.

If this minimum distance can be increased, (with fewer valid codewords on a bigger chessboard) then error correction becomes possible. This will require adding additional bits to increase the number of available codewords and allow greater distance between valid codewords.

In the next section, the Hamming Code is explored, which allows single bit error correction by adding three bits to a 7-bit message.

Sat May 18 20:31:19 ADT 2013 Last Updated: 23 SEP 2008	Richard Tervo [ tervo@unb.ca ]	Back to the course homepage...