TM ispLever CORECORE Viterbi Decoder Users Guide October 2005 ipug04 02.0 Lattice Semiconductor Viterbi Decoder Users Guide Introduction Lattices Viterbi Decoder core is a parameterizable core for decoding different combinations of convolutionally encoded sequences. The decoder core supports various code rates, constraint lengths and generator polynomials. The core also supports soft-decision decoding and is capable of decoding punctured codes. The architectural details of the core are given in the next section. Viterbi Decoder Basics Viterbi decoding is an efcient algorithm for decoding convolutionally encoded sequences. In the decoder, the con- volutional coded sequences, corrupted by channel noise, are decoded back to the original sequence. A digital transmit-receive system is shown in Figure 1, which uses a Viterbi decoder for decoding the convolutionally coded data. The digital data stream (e.g., voice, image or any packetized data) is rst convolutionally encoded, modulated and transmitted through a wired or wireless channel. The channel noise is symbolically denoted by a noise block added to the channel. The data received from the channel at the receiver side is rst demodulated and then decoded using the Viterbi decoder. The decoded output is equivalent to the transmitted digital data stream. Figure 1. Digital Transmit-Receive System Transmitted Convolutional Viterbi Received Modulator Channel Demodulator Data Stream Encoder Decoder Data Stream Noise Convolutional Encoding Convolutional encoding can be considered as a series of state transitions for every input symbol. The input and the resulting state transition can be shown in a special state transition diagram called a trellis tree (Figure 2). Figure 2. Trellis Tree 0/00 0/00 0/00 00 1/00 1/00 1/00 0/01 0/01 0/01 01 1/01 1/01 1/01 0/10 0/10 0/10 10 1/10 1/10 1/10 0/11 0/11 0/11 1/11 1/11 1/11 11 Trellis for 3 stages and constraint length = 3 Branches corresponding to input seq. 101 is highlighted In the above trellis, the branches for three transitions are drawn. The path of the trellis for a typical input sequence, 101, is highlighted in the gure. Any transmission error alters the path traversed in the trellis. In Viterbi decoding, the trellis is formed in memory, where the metrics corresponding to every path are recorded. After constructing the trellis for a sufcient length (called the traceback length), the traceback is continued from the node having the mini- mum path metric. This will lead to a stating node on the trellis. From this point one can trace forward and decode the original sequence. Figure 3 shows an example of convolutional encoding. In this example, each input symbol has two corresponding output symbols, hence the encoding is called 1/2 rate convolutional encoding. To generate the output, the encoder uses three values of the input signal, one present and two past. The set of past values of input data is called a state. The number of input data values used to generate the code is called the constraint length. In this case, the 2