[Date Prev][Date Next][Thread Prev][Thread Next] - [Date Index][Thread Index][Author Index]

Re: Fade remover

>Am I correct in assuming that most of the Reed-Solomon and Vitribi encoding 
>could be done with lookup tables if necessary?  I thought

Pretty much correct. A Reed-Solomon encoder looks a lot like a CRC
generator. Each element in the shift register is a group of bits
called a "symbol" rather than a single bit. You can define a RS code
with symbols of any size, but 8-bit symbols are especially popular
because most computers have 8-bit bytes. You also typically have two
lookup tables (each 256 bytes long for 8-bit symbols) used to convert
symbols between "polynomial" and "index" form, though there are ways
to do these conversions on the fly to save memory at the expense of a
little speed.

Re "Viterbi encoding", strictly speaking there is no such thing.  The
"Viterbi algorithm" is one of several algorithms for decoding a
certain class of codes known as "convolutional" codes. So it's
arguably more correct to refer to a "Viterbi-decoded convolutional

Regardless of the decoding algorithm, all convolutional codes are
generated in much the same way. You shift the data bits into a shift
register with predetermined taps feeding networks of XOR gates.  The
outputs of each XOR network is sent sequentially on the channel.  If
there are two XOR networks, then two distinct encoded bits are sent on
the channel for each input data bit and you have a "rate 1/2" code.
If there are three XOR networks, you have a "rate 1/3" code.

That's all there is to convolutional coding. It's one of the most
widely used FEC codes used on spacecraft precisely because it's so
easy to implement on the sending end. It's the *receiver* that has to
do the hard work of decoding it, e.g., with the Viterbi algorithm, but
that's all on the ground where lots of computing power is available.

My web page has C and C++ code to encode and decode Reed-Solomon
codes. I also have code to generate convolutional codes and decode
them with either the Viterbi or Fano algorithms. See


Via the amsat-bb mailing list at AMSAT.ORG courtesy of AMSAT-NA.
To unsubscribe, send "unsubscribe amsat-bb" to Majordomo@amsat.org