Navigation Panel: (IMAGE)(IMAGE)(IMAGE)(IMAGE) (SWITCH TO TEXT-ONLY VERSION) (IMAGE)(IMAGE) (These buttons explained below)

UNIVERSITY OF TORONTO
MATHEMATICS NETWORK

Question Corner and Discussion Area


How To Code Information With Error Detection

Asked by David Dudley on November 25, 1997:
Please, Please could you give me an explanation of these number systems:-

Two out of five code

Excess3 (XS3)

We believe that "two out of five code" is a special case of what is known more generally as a Hamming code. In this case pieces of information are encoded as a string of 5 bits (0's or 1's) in such a way that errors of 1 bit or less can be detected and corrected.

To do this, we pick a collection of 5-bit binary strings such that any two strings in the collection differ in more than 2 bits. We also pick the collection in such a way that if we have any string of 5 bits, there is exactly one string in our collection which differs from it in 2 or fewer bits. Now we record encoding/decoding scheme which tells us which letters/numbers correspond to which strings. One entry in our decoding sheet might by "A = 00010," for instance.

To transfer data using this coding scheme, we take our information and write it in terms of 5-bit strings according to our encoding table. The data is then transfered or stored and recovered. To decode a 5-bit string, we find the unique string in our collection which differs from it in at most 2 bits. We then use the decoding table to convert this string into readable information.

Of course if no errors have occurred, all the strings which are received will actually appear on the list. In the event of a minor error (1 bit changed), the damaged string is still closest to the original string. Note that an error of 2 bits can also be detected, though it may not be properly corrected.

In general, if we want to use n binary digits to code numbers and be able to detect errors of size at most k (being able to correct errors of size at most k/2) then we search for a collection of n-bit sequences such that any two of them differ in more than k bits. We also require that any n-bit string differ from exactly one string in the collection by k or fewer bits. The encoding and decoding method is the same as described above.

We remark here that a true Hamming code may have to meet a slightly more strict (and more complicated) criterion. The details have be eliminated for simplicity.

We are unfamiliar with "Excess3."

[ Submit Your Own Question ] [ Create a Discussion Topic ]

This part of the site maintained by (No Current Maintainers)
Last updated: April 19, 1999
Original Web Site Creator / Mathematical Content Developer: Philip Spencer
Current Network Coordinator and Contact Person: Joel Chan - mathnet@math.toronto.edu


Navigation Panel: (IMAGE)(IMAGE)(IMAGE)(IMAGE) (SWITCH TO TEXT-ONLY VERSION) (IMAGE)(IMAGE)

(IMAGE) Go backward to Origin of Orders of Operations
(IMAGE) Go up to Question Corner Index
(IMAGE) Go forward to How To Build A Parabolic Dish
 (SWITCH TO TEXT-ONLY VERSION) Switch to text-only version (no graphics)
(IMAGE) Access printed version in PostScript format (requires PostScript printer)
(IMAGE) Go to University of Toronto Mathematics Network Home Page