Get Complete Project Material File(s) Now! »
The emerging world of telecommunication needs growth in reliability and speed in communication. In a communication systems the reliability in transmission and information storage is provided by different coding techniques. The communication media carrying the information bits is susceptible to errors because of the noise, which is present in the analog portion of the channel. Therefore the detection and correction of errors is needed during the decoding process. The task of encoding to detect the errors is performed by channel coding. Channel coding is a process in which we add some redundant bits to our data which is to be transmitted through the channel is called channel coding. It is the job of channel coding to make the transmitted signal insensitive to errors introduced by the channel. This is achieved by carefully adding redundancy to the information that is to be transmitted.
Channel coding is used in many everyday devices, such as Compact disc players, computer modems, computer memories and mobile telephones.
There are two categories of coding methods:
a. Backward error correction codes
b. Forward error correction codes
BEC (backward error correction)
Backward error correction codes are capable of the single task which is error correction. It is commonly used in the cases when the transmitted data is lost or corrupted, a request is made by the reciever to retransmit the data. BEC is also known as automatic repeat request (ARP). BEC is bandwidth efficient and mostly used in the systems with small data and minimum number of errors.
FEC (forward error correction)
FEC is used for the improvement in the channel capacity. In this process we add some designed information to our data which is to be transmitted through the channel. For the improvement of 6 channel different techniques are used one of them is channel coding. The performance of FEC is multi sender and multi path scenario depends heavily on the correlation of packet loss between paths .
Convolution codes were invented in 1955 by P.ELIAS . Convolution codes are generally error correcting codes, that are used to improve the performance of many digital systems e.g to improve the performance of digital radio, mobile phones and the Bluetooth implementations. Viterbi decoder together with its improved versions is one of the best application of convolutional codes.
When a signal is transmitted over the channel, it is affected by any of three channel impairments i.e. noise, interference, fading. To reduce the number of bit errors in the information is accomplished by introducing redundant bits into the transmitted information stream. These bits will allow detection and correction of received data, and provide reliable transmission of information.
Convolution codes are also used in real time error correction to improve the performance of digital radio, mobile phones, satellite links etc. The simplicity and performance of convolution codes for Gaussian channel is very close to the accurate. They are one of the most widely used channel codes in the practical communication systems.
Convolution codes convert the entire data stream into one single codeword. The encoded bits depend not only on the current input bits but also on past input bits as well. Convolution code structure is easy to draw from its parameters. Convolution encoding and decoding is implemented in different manners also convolution codes are applied in applications that require good performance with low implementation cost.
There are three other methods to describe a convolutional code
1. Tree diagram
2. Trellis diagram
3. State diagram
Tree diagram of convolutional encoder
A tree diagram also makes it possible to represent the operation of a convolution encoder. This diagram is represented below in Figure for the convolution encoder from example discussed above
making the assumption that its initial state S0 is equal to a = (00). Two branches associated to the 7 presence of the symbol “1” (respectively “0”) at th e encoder input leave from each state Sk of the tree diagram, just as for the trellis diagram. This diagram is also used to decode convolutional codes, in particular, when the encoder has a large memory m (typically more than 10).
The architecture of VITERBI and its description is discussed in detail in the next chapter. Also the architecture and detail description of new designed decoder which works better than the VITERBI in certain aspects is the part of further chapters.
Trellis diagram of convolutional encoder
The trellis diagram of the convolutional encoder gives us the information that “how each possible input to the encoder influences both the output and the state transitions of the encoder”
Maximum likelihood decoding
Maximum likelihood decoding means finding the code branch in the code trellis that was most likely to transmit. Therefore maximum likelihood decoding is based on calculating the hamming distances for each branch forming encode word. The most likely path through the trellis will maximize this metric. Also the trellis module increases exponentially due to (k) and (m) factor which leads to the complexity when we go for high rate codes, to overcome this problem punctured convolutional codes (PCC) were introduced by cain et al .
The trellis diagram of the convolutional code for above state diagram is plotted above with the assumption that S0(k = 0) is a = (00) generally referred to as the “all at zero” state. A binary pair whose first symbol is ck,1 and the second is ck,2 is associated to each branch of the diagram.
From each trellis node, corresponding to a value of the state Sk and noted by a point in Figure, leave two branches associated to the presence of a “1” sy mbol (dotted) and of a “0” symbol (solid) at the encoder input respectively.
The succession of branches constitutes a path in the trellis diagram; each path is associated to particular sequence transmitted by the encoder (here, sequence indicates the sequence of coded symbols transmitted by the encoder, placed in a series).
Examining Figure we can notice that the encoder produces particular sequences known by the decoder. If the sequence received by the decoder does not correspond to a path of the trellis diagram, the decoder will be able to detect the presence of transmission error(s). Moreover, as we will see later on, it will be able to correct the error(s) by finding in the trellis diagram the sequence “nearest” t o the received sequence.
The complexity of the trellis diagram depends on the number of states of the encoder and the number of branches that leave (or merge towards) each node (2K). Its complexity thus grows exponentially with the memory of the encoder but also with the length K of the coded blocks. For packet transmissions, the state of the encoder is generally initialized at zero at the beginning of each coded block. That can be achieved by adding m K zero symbols at the end of each coded block. All the paths of the trellis diagram then merge towards the zero state. These m K symbols are called tail-biting symbols of the trellis diagram. The convolution encoder then associates a unique coded sequence with each information sequence. Convolutional codes are in this case perfectly similar to block codes and the coded sequences are code words. The trellis diagram is mainly used for the decoding of convolutional codes.
State transition diagram of convolutional encoder
The operation of a convolution encoder is represented by a graph called a state transition diagram. Convolutinal codes are also represented by the state diagram. Following below is the state transition diagram of a convolutional code which describes the transition between the states.
The state of the encoder at the moment k noted Sk = (dk, dk−1) can take four values regardless of k. We will note them here: a = (00) b = (01) c = (10) d = (11). Two transitions are possible for each state according to the value of the symbol presented at the encoder input. Binary pairs carried by the transitions between states, or buckling on the same state, correspond to the blocks transmitted by the encoder at every moment k. The transitions in solid (respectively dotted) lines correspond to the presence of one “1” (respectively “0”) at the encod er input.
Decoding convolutional codes
First convolution encoding is applied to the channel in which the transmitted signal is corrupted with AWGN (additive white Gaussian noise). Then decoding is performed by the algorithms listed below: Two algorithms which are most commonly used for decoding convolutional codes:
a. Viterbi decoding
b. Sequential decoding.
The first method proposed for decoding convolutional codes is sequential decoding. Viterbi decoders are most commonly used for relatively small values of (k) constraint length .Similarly for the long constraint length (k) values sequential decoding is used. Viterbi decoding is a very suitable option for hardware implementation because of the fixed decoding time. Viterbi decoding is a common technique used for decoding when convolution encoding is applied.because of optimum performance and its easy implementation.
Viterbi algorithm a common digital signal processing function
Viterbi algorithm is one of the most common used digital signal processing function, which is used to design a decoder known as Viterbi decoder. Viterbi algorithm performs decoding of a convolutional codes as well as the maximum like-lihood estimation of the transmitted sequence. Viterbi maximum like-lihood algorithm is considered to be one of the best technique for decoding convolutional codes. Implementation of viterbi decoder in DSP provides reasonable operational flexibility.
The two DSPs (56300 and 56600) are specifically designed for communication functions. Because of Viterbi decoder prominent position in communication systems these processors have Viteri Shift Left instruction .
Table of contents :
1.1 Introduction to Viterbi Algorithm
1.2 Introduction to Viterbi decoder
1.3 Role of viterbi decoder in Digital communication systems
1.4 Previous research work
1.5 Problem statement
2.1 Communication systems
2.2 BEC (backward error correction)
2.3 FEC (forward error correction)
2.4 Convolution codes
2.5 Tree diagram of convolutional encoder
2.6 Trellis diagram of convolutional encoder
2.6.1 Maximum likelihood decoding
2.7 State transition diagram of convolutional encoder
2.8 Decoding convolutional codes
2.9 Viterbi algorithm a common digital signal processing function
2.10 Viterbi decoder
2.11 Viterbi Algorithm working
2.12 FPGAs (Field Programmable Gate Arrays)
2.13 Why FPGAs?
2.14 Important factors
2.14.1 Error detection capability
2.14.2 Error correction capability
2.14.3 Encoding complexity
2.14.4 Decoding complexity
2.15 Xilinx/modelsim (software used)
3 System design and implementation
3.1 Flow chart
3.3 Viterbi decoder architecture
3.4 Synthesis results of viterbi decoder
3.5 Architecture of the enhanced decoder
3.6 Synthesis results for the enhanced algorithm
3.7 Previous work presented (comparison)
3.8 Major differences between both decoders
3.8.1 Viterbi decoder
3.8.2 New designed decoder
3.9 Pseudo code of new design decoder
4 Testing limitations and conclusions
4.1 Testing on different test samples
4.4 Suggested future work