Convolutional codes and The Viterbi algorithm

Any type of a communication system has its success based on how well it reassembles and presents the data that was transmitted over the channel. All kinds of error correction /prevention techniques have been employed by the mankind, over the years. The Digital Signal Processing (DSP) methods has been the strong the foundation on which the modern communication systems stand and try to stretch the human reach. It is interesting to note that, DSP were just a curiosity in the early 50s'! After the digital revolution following the integrated circuit advancements, it has become omnipresent. The widely used application is the error correction techniques, of which the convolutional coding has the topmost place.

Introduction
Different types of codes are used to encode digital data before transmission through noisy or error-prone channels. At the receiver, the bitstream is to be decoded to recover the original data, correcting errors in the process. The purpose is to improve the capacity of a channel by blending a few carefully designed redundant information to the data being transmitted through the channel, which is commonly known as channel coding. Convolutional coding and block coding are the two major forms of channel coding. When Convolutional codes operate on serial data,the Block codes operate on relatively large blocks of data. The optimum decoding method is maximum-likelihood decoding where the decoder attempts to find the closest "valid" sequence to the received bitstream. The Viterbi Algorithm does just that!

Viterbi algorithm
Convolutional encoding with Viterbi decoding is a Forward Error Correction technique that is particularly suited to a channel in which the transmitted signal is corrupted mainly by additive white gaussian noise (AWGN). Viterbi decoding was developed by Andrew J. Viterbi, a founder of Qualcomm Corporation. Most recently, he has been concentrating his efforts on establishing CDMA as the multiple access technology of choice for cellular telephony and wireless data communication. His seminal paper on the technique is "Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm," published in IEEE Transactions on Information Theory, Volume IT-13, pages 260-269, in April, 1967. Since then, other researchers have expanded on his work by finding good convolutional codes, exploring the performance limits of the technique, and varying decoder design parameters to optimize the implementation of the technique in hardware and software. The Viterbi decoding algorithm is also used in decoding trellis-coded modulation, the technique used in telephone-line modems to squeeze high ratios of bits-per-second to Hertz out of the limited-bandwidth analog telephone lines. Currently,this application of the algorithm forms an integral part of the majority of wireless telecommunication systems, incorporated in both satellite digital television receivers and even your cellular mobile handsets.

Viterbi decoder implementations
For relatively small values of k, the Viterbi algorithm provides maximum likelihood performance and is highly parallelizable. Viterbi decoders are easy to implement in VLSI hardware and in software on CPUs with SIMD instruction sets. As mentioned earlier,at the receiver, the bitstream is to be decoded to recover the original data. The possible received bit sequences form a "trellis" structure and the Viterbi Algorithm tracks likely paths through the trellis before choosing the most likely path. The "trellis diagram" gives the receiver an idea about decoding. If a received sequence doesn't fit this graph, then it was received with errors, and the decoder must choose the nearest correct (fitting the graph) sequence. The real decoding algorithms exploit this idea.

Convolutional codes are usually described using two parameters: the code rate and the constraint length. The code rate, k/n, is expressed as a ratio of the number of bits into the convolutional encoder (k) to the number of channel symbols output by the convolutional encoder (n) in a given encoder cycle. The constraint length parameter, K, denotes the "length" of the convolutional encoder, i.e. how many k-bit stages are available to feed the combinatorial logic that produces the output symbols. Closely related to K is the parameter m, which indicates how many encoder cycles an input bit is retained and used for encoding after it first appears at the input to the convolutional encoder. The m parameter can be thought of as the memory length of the encoder. A convolutional encoder is a discrete LTI - system. Every output of an encoder can be described by its own transfer function, which is closely related to a generator polynomial.

Turbo Codes: replacing Convolutional Codes
AS stated earlier, newer and improved methods have been devised by researchers all over the world for convolutional-decoding. Turbo codes are one such set. These are a new class of iterated short convolutional codes that closely approach the theoretical limits imposed by Shannon's theorem with much less decoding complexity than the Viterbi algorithm on the long convolutional codes that would be required for the same performance. Turbo codes have not yet been concatenated with solid (low complexity) Reed-Solomon error correction codes. However, in the interest of planetary exploration this may someday be done.

The future and the past
The convolutional coding/decoding was considered hopelessly complex in 1967 when it was published by Viterbi. But the algorithm survived the test of times, starting from a huge rack of equipment in the 70s' to a fraction of a tiny chip today. Convolutional codes with Viterbi decoding first used in spacecrafts and military satellites in the early 70s ultimately became the backbone of commercial voice and data ommunication satellites and direct broadcast satellites, residing in tens of millions of receivers today. The reach is counted in billions today! Truly it has been a journey through hardships to the stars!

[get this widget]