1. Field of the Invention
The invention generally relates to electronic communications systems. In particular, the invention relates to Viterbi decoding.
2. Description of the Related Art
Forward error correction (FEC) techniques are often used in communication systems in order to enhance the reliability of the transmitted signal and to improve the capacity of a data channel. A forward error correction (FEC) encoder encodes input bits to output symbols. The output symbols contain redundancy, which allow a decoder to recover the original input bits even when the output symbols are transmitted in the presence of interference or noise, and thus tolerate the occasional corruption of output symbols. A related forward error correction technique is convolutional coding. Another forward error correction technique is trellis-coded modulation (TCM).
With convolutional coding, input bits are provided to an encoder and mapped by the encoder to output symbols. The mapping by the encoder depends on the code rate and the constraint length. The code rate k/n corresponds to the ratio of input bits k to output symbols n. Thus, the encoder produces n output symbols for k input cycles. The constraint length K corresponds to the number of input bits that determine the state or value of an output symbol. Thus, for a given constraint length K, an encoder will typically store K-1 states of the input signal and combine these K-1 states with the present state of the input signal to specify the output symbol. The output symbols are constrained according to the Boolean logic characteristics of the encoder. The value of K-1is referred to as m or the memory length of the encoder.
The values for the code rate k/n and the constraint length K can vary in a broad range and are selected according to the requirements of the communication system. An example of a code rate k/n is 1/2. An example of a constraint length K is 7. Where the modulation technique used to transmit an encoded output symbol is the same as the modulation technique that would have been used to transmit an unencoded input bit, convolutional coding increases the bandwidth required to transmit information by the inverse of the code rate. However, the benefits of error correction and the advantages of transmitting information with less power overcome these disadvantages.
Convolutional codes with relatively high code rates k/n can be constructed by puncturing or removing coded symbols from a relatively low code rate convolutional code. Puncturing techniques do not affect the performance of the convolutional code significantly, and yet, puncturing techniques can increase the data rate of the convolutional code when transmitted in a bandwidth limited channel. Puncturing techniques further simplify decoding of the encoded symbols.
With trellis-coded modulation (TCM), error correction coding and modulation are combined. Trellis-coded modulation is used in many applications including relatively high data rate dialup modem standards such as CCITT V.34 communications, CCITT V.90 communications, CCITT V.92 communications, and the like, all from the International Telecommunication Organization (ITU). With trellis-coded modulation, the error correction coding corresponds to a selected convolutional code and the modulation scheme is selected from a modulation scheme such as quadrature amplitude modulation (QAM) or phase shift keying (PSK). With trellis-coded modulation, every point in the modulation constellation is mapped by a convolutional code. Moreover, the selection of the convolutional code mapping maximizes the squared Euclidean distance between distinct symbols, thereby maximizing the noise immunity of a trellis-coded modulation system. Set partitioning techniques are used to determine the convolutional code mapping.
Although convolutional coding can be implemented relatively simply, decoding is more difficult as the path taken in coding the input signal is not known until the encoded symbols are decoded. Convolutional codes can be decoded at a receiver by a variety of techniques. One such decoding technique is Viterbi decoding, where the convolutional code is decoded in accordance with a maximum likelihood decoding algorithm known as the Viterbi algorithm. With each received symbol, a Viterbi decoder computes metrics of the likelihood for all the paths that could have been taken by the encoder. A conventional Viterbi decoder traces back about several times the constraint length K of the encoder in order to compute the likelihood of a path. The trace back depth can also vary with the code rate, and can be selected within a relatively broad range by the designer. To decode the encoded symbol stream, the Viterbi decoder selects the path calculated to be the most likely path, which is known as the surviving path.
In many conventional systems, such as modems, receivers, mobile telephones, satellite communications systems, and the like, a host processor such as a general purpose microprocessor or a general purpose digital signal processor (DSP) decodes the convolutional code or decodes the trellis-coded modulation. Disadvantageously, the execution of a Viterbi decoding algorithm can be a relatively time-consuming process and can consume a relatively large amount of the host processor's time. When the host processor is executing the Viterbi decoding algorithm, many of the host processors functional blocks remain idle. This is a waste of valuable host processor resources. What is needed is a technique to alleviate the host processor from the burden of Viterbi decoding, thereby freeing the host processor to perform other tasks.