**Post: #1**

Convolutional Encoder and Viterbi Decoder

viterbi verilog code.pdf (Size: 1.88 MB / Downloads: 94)

Introduction and Definitions

In digital communication system, the transmitted data is presented in

binary form that is modulated to analog waveforms and transmitted through a channel to

a receiver. In the channel the noise and interference corrupt the transmitted signal, which

is mapped back to binary bits in the receiver. Some bit errors may occur if the

interference is too strong so channel coding is often used to prevent these errors. The

channel coding means that extra bits are added to the transmitted data and these bits are

then used when reconstructing transmitted data sequence in the receiver. There are many

different methods for channel coding like linear block codes and convolutional codes.

Convolutional Encoder

Convolutional coding has been used in communication systems including

deep space communications and wireless communications. Convolutional codes offer an

alternative to block codes for transmission over a noisy channel. Convolutional coding

can be applied to a continuous input stream (which cannot be done with block codes), as

well as blocks of data. A convolutional encoder is a Mealy machine, where the output is a

function of the current state and the current input. It consists of one or more shift registers

and multiple XOR gates. XOR gates are connected to some stages of the shift registers as

well as to the current input to generate the output.

The Viterbi Algorithm

The Viterbi decoding algorithm was proposed by Viterbi in 1967 is a

decoding process for convolutional codes. Viterbi decoding is one of two types of

decoding algorithms used with convolutional encoding-the other type is sequential

decoding. Sequential decoding has the advantage that it can perform very well with longconstraint-

length convolutional codes, but it has a variable decoding time. Viterbi

decoding algorithm has the advantage that it has a fixed decoding time. It is well suited to

hardware decoder implementation. But its computational requirements grow

exponentially as a function of the constraint length, usually limited to constraint lengths

of K = 9 or less.

THE VITERBI ALGORITHM

For years, convolutional coding with Viterbi decoding has been the

predominant FEC technique used in space communications. The algorithm can be applied

to a host of problems encountered in the design of communication systems. The Viterbi

decoding algorithm is based on maximum likelihood decoding. Perhaps the single most

important concept to aid in understanding the Viterbi algorithm is the trellis diagram. A

typical trellis diagram is shown in Fig 3.1

BRANCH METRIC UNIT

The branch metric unit calculates the branch metrics of the trellis structure

from bit metrics. The branch metrics are difference values between received code symbol

and the corresponding branch words from the encoder trellis. The bit metrics can be

calculated with a separate unit as shown in figure or a look-up table can be used. The

inputs needed for this task are bit metrics, which in this case come from the convolutional

encoder. These encoder branch words are the code symbols that would be expected to

come from the encoder output as a result of the state transitions. In hard-decision

decoding the calculation method is called Hamming distance. The Hamming distance

d(X, Y) between two words X and Y is defined to equal the number of differing

elements. For soft-decision decoding, there is another algorithm called Euclidean

distance. When the input symbol is X and encoder symbol is Y, the Euclidean distance is

calculated from the formula (X-Y)2.