HDL Implementation of convolution encoder and viterbi decoder

HDL Implementation of convolution encoder and viterbi decoder

ABSTRACT

Forward Error Correction(FEC) schemes are an essential component of wireless communication systems. Convolutional codes are employed to implement FEC but the complexity of corresponding decoders increases exponentially according to the constraint length. Present wireless standards such as Third generation (3G) systems, GSM, 802.11A, 802.16 utilize some configuration of convolutional coding. Convolutional encoding with Viterbi decoding is a powerful method for forward error correction.The Viterbi algorithm, which is the most extensively employed decoding algorithm for convolutional codes. The main aim of this project is to design FPGA based viterbi algorithm which encrypts / decrypts the data . In this project the encryption / decryption algorithm is designed and programmed in to the FPGA.

1. INTRODUCTION

   In telecommunication and information theory, forward error correction (FEC) (also called channel coding]) is a system of error control for data transmission, whereby the sender adds systematically generated redundant data to its messages, also known as an error-correcting code (ECC). The carefully designed redundancy allows the receiver to detect and correct a limited number of errors occurring anywhere in the message without the need to ask the sender for additional data. FEC gives the receiver an ability to correct errors without needing a reverse channel to request retransmission of data, but this advantage is at the cost of a fixed higher forward channel bandwidth. FEC is therefore applied in situations where retransmissions are relatively costly, or impossible such as when broadcasting to multiple receivers. The process of adding this redundant information is known as channel coding. Convolutional coding and block coding are the two major forms of channel coding. Convolutional codes operate on serial data, one or a few bits at a time. Block codes operate on relatively large (typically, up to a couple of hundred bytes) message blocks. There are a variety of useful convolutional and block codes,

   and a variety of algorithms for decoding the received coded information sequences to recover the original data.

   Convolutional codes are employed to implement FEC. In telecommunication, a convolutional code is a type of error-correcting code in which

   • each m-bit information symbol (each m-bit string) to be encoded is transformed into an n-bit symbol, where m/n is the code rate (n m) and

   • the transformation is a function of the last k information symbols, where k is the constraint length of the code.

   Convolutional codes are used extensively in numerous applications in order to achieve reliable data transfer, including digital video, radio, mobile communication, and satellite communication.

   convolutional encoder is used to obtain convolution codes .It take a single or multi-bit input and generate a matrix of encoded outputs. In digital modulation communications systems (such as wireless communication systems, etc.) noise and other external factors can alter bit sequences. By adding additional bits we make bit error checking more successful and allow for more accurate transfers. By transmitting a greater number of bits than the original signal we introduce a certain redundancy that can be used to determine the original signal in the presence of an error.

   Several algorithms exist for decoding convolutional codes. For relatively small values of k, the Viterbi algorithm is universally used .

   A Viterbi decoder uses the Viterbi algorithm for decoding a bitstream that has been encoded using forward error correction based on a convolutional code.There are other algorithms for decoding a convolutionally encoded stream (for example, the Fano algorithm). The Viterbi algorithm is the most resource-consuming, but it does the maximum likelihood decoding. .

   Here we designed the two stage convolutional encoder and viterbi decoder and will implement in FPGA.

   For our illustration we will assume a 4-bit and give as an input to the convolutional encoder rate-1/2 code (two output bits for every input bit). This will yield a 2×4 output matrix, with the extra bits allowing for the correction. This 8 bit output is given as the input to the viterbi decoder which decodes the convolutional codes into original data.

2. REVIEW OF PREVIOUS ARCHITECTURES

   In wireless communication AWGN (Additive White Gaussian Noise) properties of most of the communication media introduce noise in real data during transmission.Channel Coding is a technique to introduce redundant code in real code to remove interference and error during transmission. Coded data in sender side thus increased by volume and error effect becomes less compare with uncoded data. Receiver end receives this data and decodes the data using some techniques. Viterbi decoding is one of the popular techniques to decode data effectively. Viterbi algorithm (VA) is an optimum decoding algorithm for the convolutional code. Convolutional encoding and Viterbi Decoding are widely used for reliable data transmission.

   There are different approaches of implementation for Convolutional Encoder and Viterbi Decoder in the literatures. previously the implementation of Convolutional Encoder and Viterbi Decoder in the DSP Platform. It is a flexible platform but slow in speed. Using C Platform implementation of Convolutional Encoder and Viterbi Decoder is also Slow.

   To overcome the performance issue of Convolutional Encoder and Viterbi Decoder, FPGA based implementation has been proposed. These Implementations have Fixed Constraint Length and Code Rate or with Partial Configuration Facility. Complexity of Viterbi decoding algorithm increases in terms of convolutionally encoded trellis length. Increasing the trellis length causes the algorithm to take more time to decode. This will cause transmission speed lower but make the transmission more reliable. Lowering the trellis length will increase the transmission speed . A highly complex Viterbi Decoder someway loses its advantages, when it is adopted to decode sequences transmitted on a low-noise channel. In this case, low minimum distance codes are more suitable for achieving a good performance, and a higher bit rate can be transmitted by lowering the coding rate.

3. CONVOLUTIONAL ENCODER

   Convolutional codes are employed to implement FEC convolutional encoder is used to obtain convolution codes .It take a single or multi-bit input and generate a matrix of encoded outputs. In digital modulation communications systems (such as wireless communication systems, etc.) noise and other external factors can alter bit sequences. By adding additional bits we make bit error checking more successful and allow for more accurate transfers. By transmitting a greater number of bits than the original signal we introduce a certain redundancy that can be used to determine the original signal in the presence of an error.

   Fig 1: Block Diagram of Convolutional Encoder

   Fig 2: Truth Table of convolutional encoder

   Trellis Diagram: To draw trellis diagram, refer the above table. Write the all possible present state buffers (C D),then next state (C D). Now refer the above table, for zero input and the buffer values are 00 (C D) the respective next state is 00 (C D). So draw a straight line from 00 of present state to 00 of next state, and above the straight line write the output value (A B) in bracket. As like the same for one input, but the line is dotted line.

   Fig 5: Block Diagram of viterbi decoder

   Fig 3: Trellis Diagram/p>

   STATE TABLE:

   Fig 4: State Table

   To write the state table, refer the trellis diagram. If you see the second next state, the 00 is from 00 and 01 of the previous sate. So we can divide into two states. Write 00 in state 0 and 01 in state 1 and write the respective output (values with in bracket of the straight and dotted line) in value 0 and value 1.As like the same write for 01, 10, 11.Now the required value that is state 0 and 1, Value 0 and 1 are generated.

4. VITERBI DECODER

   Viterbi decoder is most commonly used to resolve convolution codes. This is essential for the purpose of secure transmission of data and its corresponding retrieval during reception. Viterbi decoders also have the property of compressing the number of bits of the data input to half. As a result redundancy in the codes is also reduced. Hence viterbi decoding is more effective and efficient. The Viterbi decoder designed here is an 8:4 decoder. The same logic and concept can also be extended to further number of bits also. Viterbi decoders are based on the basic algorithm which comprises of minimum path and value calculation and retracing the path. This minimum values calculation is determined by EX-OR operation and then comparing .This can be briefed by means of the block diagram .

   BMU: Branch metric unit

   ACS: Add , compare and select

   TBU: Trace back unit

   d in: Input data

   d out: Output data

   VITERBI ALGORITHM

   The algorithm for Viterbi decoder can be explained by using the example below. Let us consider the input 11010001.

   Mininum value and minimum path calculation

   The input is taken in the form of four sets each,comprising of 2 bits starting from the MSB. The first two bits from the MSB are taken and are XOR-ed with the values predetermined for the encoder as STATE 0 and the values are obtained.Similarly they are also EXOR-ed with the values of STATE 1 and the values are also noted down. Thus we obtain 2 sets of 4 values each , for state 0 and state 1. The corresponding values are compared and the minimum of each of the 2 values is noted down for all the 4 values. Also corresponding position values are marked as 00,01,10,11 respectively. For the minimum path calculation, the value corresponding to that particular minimum path is taken and its state value (state 0 or state 1) is assigned to the minimum path in decimal notation. This is the function of the BMU.

   Once the 1st row is resolved, the second set of two bits starting from the MSB (01 in our case) is EXOR- ed as explained for the first set.Now the corresponding states of the respective values(value 0 or value 1) are obtained and their corresponding STATE VALUES are noted down(in binary). These state values denote the minimum distance positions , obtained in the previous row resolution. The corresponding value of the minimum distance is chosen and is added to the EXOR-ed outputs of the present row(both in binary) for both value 0 and value 1. They are then compared and minimum distance is once again obtained and corresponding positions are assigned. This is the function of the ACS unit. The path calculation is the same as the first row.

   The above procedure is repeated for rows 3 and 4 also and their corresponding values are obtained.

   Path trace back procedure

   The final step is the trace back procedure, wherein the all the values are consolidated to obtain the final output. If the position of minimum value is 00 or 01, a 0 is obtained in the output. For any other values, a 1 is obtained at the output. In this calculation, the minimum value of the last row is taken and based on its position a 1 or 0 is assigned as one of the output

   bits. The corresponding path is noted and converted to binary. The minimum value corresponding to that particular path ,is noted and once again a position based output bit assignment is made as explained previously, for the row 3. This is repeated for all the remaining rows . Thus,4 output bits are obtained. These bits are then concatenated and a process of bit reversal is made .thus a 4 bit output is derived from an 8 bits input that was given to the viterbi decoder

   The output for the 8 to 4 viterbi decoder is shown below. The encoded bit is given as input and the 4 bit original message bit is decoded and got as the output.

5. RESULT

   Model simwaveform & Synthesis Report of convolutional encoder and viterbi decoder:

   Fig 6: Modelsim waveform of convolutional encoder

   Fig 7: Synthesis Report of convolutional encoder

   Fig 8: Modelsim waveform of viterbi decoder

   Fig 9: Synthesis Report of viterbi decoder

6. CONCLUSION

   In our project, a Viterbi algorithm based on the strongly connected trellis decoding of binary convolutional codes has been implemented in FPGA. The use of error-correcting codes has proven to be an effective way to overcome data corruption in digital communication channels. The adaptive Viterbi decoders are modelled using Verilog, and post synthesized by Xilinx FPGA logic.

   We can implement a higher performance Viterbi decoder with such as pipelining or interleaving. So in the future, with Pipeline or interleave the ACS and the trace-back and output decode block, we can make it better.

7. REFERENCE

   1. Shannon, C. A mathematical theory of Communication, Bell Sys.Tech .J., vol. 27

      ,pp. 379-423 and 23-656, 1948

   2. Hamming, R. Error detecting and correcting codes, Bell Sys.Tech .J., vol. 29

      ,pp.147-160 , 1960.

   3. Golay, M. Notes on digital coding, Proc. IEEE, Vol. 37, p. 657 , 1949 .

   4. Azim, C., Monir, M. Implementation of Viterbi Decoder for WCDMA System, Proceedings of IEEE International Conference (NMIC 2005), pp. 1-3 , 2005.

   5. Wong, Y., Jian, W., HuiChong, O., Kyun, C., Noordi, N. Implementation of Convolutional Encoder and Viterbi Decoder using VHDL, Proceedings of IEEE International conference on Research and Development Malaysia, November 2009.

   6. Bissi, L., Placidi. P., Baruffa, G., Scorzoni,

      1. A Multi- Standard Reconfigurable Viterbi Decoder using Embedded FPGA blocks, Proceedings of the 9th EUROMICRO Conference on Digital System Design(DSD06),pp. 146-153 , 2006.

   7. Shaker, S., Elramly. S., Shehata. K. FPGA Implementation of a reconfigurable Viterbi Decoder for WiMax Receiver, IEEE International conference on Microelectronics, pp. 246-267,2009