FPGA Design and Implementation of a Convolutional Encoder and a Viterbi Decoder Based on 802.11a for OFDM ()
1. Introduction
The wireless local area network (WLAN) is considered as one of the most effective wideband access ways between electronic devices. The IEEE 802.11a standard [1] for WLAN is based on Orthogonal Frequency Division Multiplexing (OFDM), supporting multiple transmission modes, providing data rate up to 54 Mbps in the 5 GHz band. In order to overcome frequency selective weaknesses from distortion channels in the above-mentioned OFDM-WLAN systems, strong Forward Error Correction (FEC) technologies which have been widely utilized in digital communication applications especially such as the Viterbi Algorithm (VA) are employed. The VA was first introduced as an available scheme for decoding convolutional codes in 1967 [2]. Later, the convolutional codes and VA laid a significant influence in combating with the channel distortion effects such as multipath fading and intersymbol interference. Shaking changes have been made on FPGA technologies over the recent years. Complex real-time signal processing tasks can yet be fulfilled owing to high clock speeds and huge gate densities provided by FPGA. Many efficient structures of Viterbi decoder are researched to decrease the survivor path memory since it can dominate the chip area. Some designs can reduce the memory size significantly [3]. But they cannot be commercialized because of wiring area. Most commercial products [4] still use the classical two-pointer trace-back scheme [5] and demand memory of size 4*K*N bits (K is the constraint length, N is the number of states). An alternative scheme using dual-port memory is proposed recently [6]. The memory requirement is halved while the number of trace-back multiplexers (N to 1) increase one to three.
Convolutional codes are a kind of non-block codes whose performances are superior to block codes in the same coding efficiency situation [7]. Their coding scheme makes information elements have correlations by means of exclusive-or operation, resulting in the increase of transmission redundancy. Based on these correlations, the VA can be used for decoding and error correction in the receiving end. The complexity of software and hardware implementation for VA are growing exponentially with the increase of the m (m is the number of shift registers); Therefore, careful design has to be made to realize such a practical decoder. With the FPGA technology development the VA operation problem has been solved to a great extent. This makes the Viterbi the most extensive, robust and capable decoding algorithm when the value of m is less than or equal to 10. Without a doubt, the primary purpose of any decoder design might be to decrease the FPGA area, reduces the power consumption and improve the decoding performance. The Virtex-II family is a platform FPGA developed for high performance from low-density to high-density designs which are optimized for high speed with low power consumption. The device XC2V2000 of this family can excellently meet the performance and stability requirements of the encoder and decoder according to the experiments. The designs are described using Verilog HDL for the hardware implementation on the above FPGA and it can be configurable.
The remainders of this paper are organized as follows. In Section 2, The analysis and FPGA design of (2, 1, 7) convolutional encoder are presented. Section 3 shows the algorithm and the Viterbi decoder architecture. In Section 4, the implementation results analyses are provided based on a Xinlinx virtex2 FPGA by ISE 7.1i. The paper is concluded in Section 5.
2. Convolutional Encoder Analysis and Design
Convolutional Encoder Analysis and Architecture
Convolution codes are better codes of error controlling performance. Convolutional encoder outputs are not only associated with the encode elements at present, but also affected by several ones before. (n, k, m) is used for describing convolutional codes, where k are the input encode elements, n are the output encode elements and m are the shift register numbers of convolution encoder. Usually, the value of n and k is smaller and k is less than n, but the number of shift registers takes larger value.
In WLAN standards the convolutional codes are defined by given generator polynomials with constraint length of 7 and code rate of 1/2, resulting in 64 trellis states. The given generator polynomials codes are G1 = 133(OCT) and G2 = 171(OCT), equally
(1)
(2)
Figure 1 indicates the block diagram of (2, 1, 7) convolutional encoder. The (2, 1, 7) convolutional encoder consists of six shift registers and two exclusive-or gates. When starting coding, all these registers are reset for initialization. Every shift register is equivalent to a flip flop. These six flip flops are connected in series to complete shifting and updating operation under the action of the clock pulse. The exclusive-or gates are used for modular-2 adders to obtain the coding data. With every clock pulse the encoder outputs two bits according to the generator polynomials whenever one binary bit is inputted. The output is not only relevant with the current input binary bit, but also influenced by the inputs six clock pulses before.
3. The Viterbi Decoder
3.1. Viterbi Algorithm
Viterbi is known as a maximum likelihood decoding algorithm of convolutional codes for estimating and searching the most likely survivor path in the trellis according to the receiving sequences, meanwhile the error during transmission can be corrected. This algorithm is based on calculating the hamming distance for each branch and the path that is most likely through the trellis will maximize that metric [8]. For binary encoders, the corresponding trellis is composed of L + 1 sections with 
nodes each, where L is the length of the message to be decoded in bits and K is the constraint length of the code. While the entire trellis must be considered for optimal sequence detection, practical realizations will work only on a section of the complete trellis with Ltb 
stages, where is called trace-back length [9].
Figure 1. (2, 1, 7) convolutional encoder for OFDM-WLAN.
3.2. The Architecture of the Viterbi Decoder
In this paper, hamming distance computation module, ACS module, survivor path storage and management module, trace-back module, timing controller module and minimum value choice module are included for the Viterbi decoder.
However, there are two remarkable problems before the design. One is the choice of decoding depth; the other is the survivor path storage. In general, the VA starts to trace-back until the survivor path is to zero, and then finds a best path. But this would not only increase decoding delay, and will cause the problem of much bigger storage capacity. Despite the growing decoding depth can improve the decoding accuracy, according to former experiences the system performance has no significant influence when decoding depth is five times as much to 10 times of the registration numbers [9]. Based on the 802.11a decoding depth is set to thirty six. Convolutional decoder has sixty four states, it needs to store the sixty four survivor paths and keep the corresponding path lengths. Therefore, the capacity of each RAM block should be set to sixty four storage units, the size of each storage unit equals to decoding depth.
The whole hardware architecture is shown in Figure 2. The proposed Viterbi decoder works as follows:
Step 1, two parallel binary bits are inputted into the Viterbi decoder with every clock pulse, and then the hamming distance computation module begins to work when the input enabling signal is valid. It calculates sixty four groups of hamming distance. Each group consists of two because each current state can be reached by two possible paths.
Step 2, the ACS modules begin to work. Cumulative hamming distance one clock before is added to hamming distance of the new branch path correspondingly. After adding operation each current state gets two new cumulative hamming distances, and then the ACS module compares the size of the two cumulative distances and selects the smaller one as a survivor. The path of the survivor represents survived path. The smaller cumulative hamming distance becomes the benchmark for the next computation. Survivor paths of all the sixty four states are stored in RAM blocks.
Step 3, sixty four survivor paths are stored in the RAM blocks and each of them equals to decoding depth when the decoding depth is reached, then sixty four cumulative hamming distances are inputted into the minimum value choice module. This module outputs the minimum value to trace-back module, then the trace-back module reads survivor values from the paths storage RAM blocks according to survivor path values. The outputs of the backtracking module are the Viterbi decoding results.
3.2.1. The Hamming Distance Computation Module
This module compares the received codes with the expected codes of the current state and calculates the hamming distance between them. The hamming distance computation schematic diagram is shown in Figure 3.
Table 1 gives the algorithm expressions for the hamming distance calculation of two received codes under the four possible values of the excepted codes, where data_in1 and data_in2 stand for the two-bit inputs in the trellis.