Page 272 - Anatomy of a Robot

09_200256_CH09/Bergren 4/17/03 11:24 AM Page 257
of the Shannon limit. The coding is similar to the block coding of RS, with data and
checksum bytes, but it has several differences. COMMUNICATIONS 257
First and foremost, whereas RS has a row of data and checksum bytes, the turbo prod-
uct codes have a three-dimensional structure. Checksums are computed for all three
dimensions for the data: x, y, and z. In this way, the original data is given error-
correcting checksums in multiple directions. The decoder has a relatively simple com-
pute engine. The decoder works on one checksum at a time, doing x, y, and z vector
checksums in separate calculations. Every time the decoder compute engine makes cor-
rections on a vector, it changes the results in the other two dimensions. Once the decoder
has been used on all the vectors in all three dimensions, the entire process can start over.
The decoder can process the data as many times as needed to make the data as perfect
as possible. The more times the decoder is used, the better the results. If the data is
known to have many noise errors, the decoder can be used several times. If the data is
known to be fairly clean, the decoder can be used one or two times. Sufficient infor-
mation is built into the originally transmitted data so the decoder knows when to stop
iterating through the received data.
The following web site and PDF files have further descriptions of turbo codes:

www-ext.crc.ca/fec/Compare_Ref2.pdf
www.ee.vt.edu/ yufei/turbo.html

INTERLEAVER

Interleaving is a way of spreading out errors. Often, an error-correcting scheme will
break down if the errors occur in a regular pattern. Viterbi codes, for instance, will
gather errors into concentrated bursts. An interleaver takes adjacent data and moves
them apart, much like a deck of cards is shuffled. The data is not expanded, just
rearranged. The encoder can interleave the data before transmission, and the decoder
can deinterleave the data on reception. Interleaving can be done in many different ways,
each of which conveys specific advantages and disadvantages.
Here’s the bottom line on interleaving. In general, if interleaving is used within a stan-
dard communications link protocol, all the options are already specified. In this case,
no choices will affect the performance of the communications link. More information
can be found at these sources
www.es.lth.se/home/jht/interleaverdownload.html
www.comblock.com/download/com1016.pdf
www.cs.ucl.ac.uk/staff/jon/talks/rtpi/sld001.htm
Here interleaving is used with compression, not coding. See slides 3, 4, and 5.