外文翻译-Viterbi和费诺译码算法的卷积码的比较研究.doc

外文文献：A Comparative Study of Viterbi and Fano Decoding Algorithm for Convolution CodesKapil Gupta, P.K.Ghosh, R.N Piplia and Anup Dey*Mody Institute of Technology & Science, Faculty of Engineering & Technology ECE Department, Lakshmangarh, District Sikar, Rajasthan-332311, India * Modi Institute of Technology/ECE Department, Kota, Rajasthan, India *Kalyani Government Engineering College/ECE Department, Kalyani, West Bengal, India. Abstract.In this paper, simulation of Viterbi decoder and Fano decoder for decoding the convolutional codes in AWGN channel is carried out. Graphs are plotted between Viterbi algorithm and Fano algorithm for decoding the convolutional codes of fixed code rate and fixed constraint length. Result shows that performance of Viterbi decoder is better than Fano decoder for the same code rate, constraint length and decoding delay.1 Introduction Error correction coding has 50 years of history, as early as in 1948, Shannon (Shannon)s seminal paper a mathematical theory of communication in his, first expounded the methods of reliable communication in noisy channels, made famous by the noisy channel coding theorem, laid the cornerstone of the error correcting codes. Later, error correcting codes are more and more communication and mathematics educators, especially the mathematicians attention, the error correcting code both in theory and in practice has been the rapid development.With the development of modern communication, especially in the future 4G communication network, high-speed information transmission and high reliability transmission become the two main aspects of information transmission, and the reliability is especially important. Because the channel condition is bad, signals are inevitably disturbed error. In order to realize the reliability of communication, there are two main ways: one is to increase the power of the transmitted signal, improve the signal noise ratio of receiving end; another method is adopted to control the channel error code. The former often subject to conditions, not all cases can be used. For example, satellite communication system to transmit data to the far distance, due to the influence of fading, noise and interference, signal produce serious distortion in the transmission process. If the signal has the largest possible energy, satellite volume and load will increase greatly, so that the cost of greatly increased compared to the original, so impossible to signal to provide too much energy, and the Shannon based on coding theory can solve this problem, reduce the cost, practicability. Forward error correction (FEC) is a very important part of the wireless digital communication system is a convolutional coding. It is an effective channel coding method, widely used in practice. At present, wireless digital communication systems use some form of convolution code such as W-CDMA, DVB-S, DVB-T, IEE802.11 system using convolutional code. Because of its excellent error correction performance, generally in the concatenated code as inner code, thus ensuring the outer code work effectively, greatly improving the error correcting capability of the whole system. While the Viterbi decoder is one of the best methods for decoding convolutional codes.Characteristics of CDMA system with its large capacity, strong anti-interference ability to become the third generation mobile communication system standard. Channel coding of CDMA system mostly adopts convolutional coding, this is because the error correcting capability of convolution code is strong, not only can correct random errors, but also the burst errors. In the CDMA system, the decoding of convolutional codes used in the Viterbi algorithm, it is a kind of maximum likelihood decoding method, when the code constraint length, or a little bit error rate requirement is not very high, the Viterbi decoder relatively simple equipment, fast calculation speed, so that the Viterbi decoder has been widely applied in various fields.In modern communication, with the transmission rate of the signal sequence of continuous improvement, requirements of convolutional code decoding speed also need to constantly improve, Viterbi decoding and has the best performance because of the characteristics of full use of signal sequence statistical probability. The application field of channel coding include deep space communications, satellite communications, mobile communications, data transmission, file transfer and digital audio / video transmission. Convolutional codes as channel coding mode is the most important one, is widely used in satellite communication, UAVs, deep space communications, mobile communications, underwater acoustic communication, digital communication systems, or even be adopted to some wireless communication standards, such as GSM, IS.95 and CDMA2000 standards. In satellite communications, convolutional code has rate for 1/2 and 1/3 become the standard coding method in commercial satellite communications system. In UAV telemetry and telecontrol system, improve the control instruction transmission error with the traditional channel, coding of UAV remote control channel using convolutional codes, under certain channel conditions, the control command transmission error decreased significantly. In the code rate does not increase under conditions of UAV system, control command transmission reliability is improved obviously.With the continuous expansion of business in the digital communication system, with the continuous development and improvement of the theory of convolution code, convolutional codes will be applied more and more widely, convolutional codes now in communication system function will become more and more large. In the recent years, there has been an increasing demand for efficient and reliable digital data transmission and storage systems. A major concern of the designer is the control of errors so that reliable reproduction of data can be obtained at the receiver end. The system parameters available to the designer are the transmitted signal power and the channel bandwidth. These two parameters together with the power spectral density of the receiver noise, determine the signal energy per bit-to-noise power spectral density ratio Eb/No. For a fixed Eb/No, the only practical option available for changing data quality from problematic to acceptable level is to use Error Control Coding. Error correction coding is essentially a signal processing technique used to improve the reliability of communication system in digital channels. There are two kinds of forward error correction techniques, namely block codes and convolutional codes1. Conceptually, encoder for the block code is a memory-less device, which maps k-symbol input sequence into n-symbol output sequence. The term “memory-less” indicates that each nsymbol block depends only upon a specific k-symbol block. The encoder for convolutional code is a device with memory that accepts binary symbols in set of k bits and output binary symbols in set of n bits. Each set of n output code symbols are determined by the current input set and a span of v of the preceding input symbols. For convolutional codes, two important decoding techniques are rigorously used in various communication systems are Fano decoding and Viterbi decoding. Fano decoding can perform very well with longconstraint length convolutional codes, but it has a variable decoding time . Viterbi decoding is a dominant decoding technique for convolutional codes, and has advantage of highly satisfactory bit error rate performance, high speed operation, ease of implementation and low cost. In digital communication, SNR is usually measured in terms of Eb/No which stand for energy per bit divided by the one-sided noise density. The usual measure of performance of a coded system is the average error rate that is achieved at a specified signal to noise ratio. The interleaved (2, 1, 7) convolution codes with Viterbi decoding are adopted as an anti-interference scheme in mobile image communication system. A better bit error rate (BER) performance is obtained by preparing more codes for the biorthogonal system than in conventional direct sequence spread spectrum (DS/SS) systems using binary convolutional coding methods. Decoder delay is one of the most important aspect by which we are in the position to select the decoding algorithm for decoding the convolutional codes for various communication systems. The organization of this paper is as follow. Section II describes the convolutional encoder. Decoding algorithm for convolutional codes is described in section III. Results are shown in section IV. Finally, conclusion is drawn in section V. 2 Convolutional encoder During encoding, k input bits are mapped to n output bits to give rate k/n coded bit stream. The encoder consists of a shift register of K stages, where K is described as the Constraint length of the code. Convolutional encoders are physically constructed by using shift registers with taps determined by the generator functions. The rate of the encoder is defined as the ratio of input to the output symbols. The number of taps on the shift register determines how many of the output bits are influenced by the input bits. The number of influenced output bits is called the Constraint Length. A convolutional code looks very much like a discrete time filter. Instead of having a single input and output stream, however, we have k input streams and n output streams.Figure 1. Convolutional Encoder for K=3, Rate=1/2 An Encoder is illustrated in Figure 1 for K=3 and v=2. Here M1 through M3 are 1-bit storage devices such as lip-flops. The output v1 and v2 of adder are given by v1=s1s2s3 (1)v2=s1s3 (2) The operation of the encoder proceeds as follows: The shift register is assumed to be clear initially. The 1st bit of the input data stream is entered into M1. During this message bit interval the commutator samples and the adder output are v1 & v2. The next message bit enters M1 while the previous bit in M1 transfers to M2 and the commutator again samples all the v adder outputs. This process continues until eventually the last bit of the message has been entered into M1. Thereafter in order that every message bit may proceed entirely through the shift register to complete process, 3 zeros are added to the message to transfer the last bit of the message to M3 and hence out of the shift register. The shift register then finds itself in its initial clear condition again. Table 1 describes the encoder stages for K=3, rate encoder of Figure 1. Table1. Encoder stages for K=3, code rate=1/2. The tree representation of this encoder is displayed in Figure 2. In accordance with customary practice. The starting node of the code tree at the left; take the initial state of the shift register 00, taking M1M2 = 00, represented by a, and the dimension in which a starting node. When the input symbol is 0, starting from the node onto the slip; when the input symbols are 1:00 slip down from the departure node. For example, when the encoder is first input bit is 0, then embarked on a branch, then the shift register output code 000 is written in the top of the upper branch of the bifurcation; encoder when the first bit is input 1:00, then walked down the slip road, then the output of the shift register code 111 is written above the figure under the branches of a tree branch. In a second input bit, the shift register right one, then to the shift register of the branch status of the case 00, i.e., a, and marked on the branch node; conditions under which lower leg The shift register state O1, namely b, and marked in the lower branch node; while upper and lower arms are two branches of a tree. After each new input bits will cause upper and lower arms of each of two branches of a tree. After four input bits, the encoder to get the tree shown in Figure 2-3. Tree graph, a node represents a marked M1M2 = 00, b represents M1M2 = O1,. C represents M1M2 = 10, d represents M1M2 = 11.Figure 2. Tree representation of encoder(rate=1/2,K=3) 3 Decoding algorithm for convolutional codes Convolutional code decoding method can be divided into two categories: algebraic coding and decoding probability. Generation decoding encoded using algebraic structure itself decoded without considering the statistical characteristics of the channel. Majority logic decoding, also known as threshold decoding of convolutional codes is the most important one algebraic decoding method to be applied to the decoding cyclic codes. Most effective for large numbers logic decoding constraint length of the convolutional code shorter and simpler equipment. Probability decoding (also known as the maximum likelihood decoding) is based on the statistical characteristics of the channel characteristics and the convolutional code is calculated. One of the first sequential decoding Waugh had no memory channel for Kraft is proposed probabilistic decoding method; Another approach is probabilistic Viterbi decoding (Viterbi) algorithm. When the constraint length of the code is shorter, it is more efficient than the sequential decoding algorithm, faster, and is currently widely used.The basic idea of probability decoding of convolutional codes is: to the receiving stream based computing it, and all other possible, continuous grid graph path distance one by one, choose the most likely estimate as a decoding output. Maximum probability in most of the cases can be interpreted as the minimum distance, the minimum distance decoding is a reflection of the maximum likelihood criterion. The maximum likelihood decoding maximum likelihood decoding of convolutional codes and block codes are the same in principle, but on a slightly different implementation method. The main difference is that: block codes is similarity in isolation for single codes, and convolutional codes is to find the similarity between the codeword sequence. Decoding trellis based search is an important way to achieve the maximum likelihood decision. A trellis description, because the path together to eliminate the dendrogram of redundancy, the decoding process only need to consider the entire path set the path of the likelihood function. If at some point found a path has not been possible to obtain the maximum log likelihood function, give up this path, and then in the rest of the survival path rerouting. This has to end the class L (L for sending sequence length). Because this method had rejected the impossible path, thus reducing the workload of Viterbi decoding, decoding is based on this idea. Viterbi decoding algorithm is proposed in 1967. The basic principle of this algorithm is that the received signal sequence and the sequence of all possible transmitted signal comparison, select the minimum Hamming distance of the transmission signal sequence is the sequence considered current. If you send a k-bit sequence, there are 2k possible transmit sequence. When K is large, the storage capacity is too large, so that practical restrictions. In this regard the Viterbi algorithm has been simplified to enable practical. There are a variety of algorithms for decoding the received coded information sequences to recover the original data. Viterbi algorithm is one of the practical techniques. Viterbi decoding algorithm:Viterbi algorithm steps are summarized below: The equivalence between maximum likelihood decoding and minimum distance decoding for a binary symmetric channel implies that a convolutional code may be decoded by choosing a path in the code tree whose coded sequence differs from the received one in the fewest number of places. The change of stages for the input bits is shown in Figure 3. Since a code tree is equivalent to a trellis, trellis representation is considered as depicted in Figure 4. Figure 3: Encoder Input bits and output symbolsFigure 4: The trellis for t=17 for given input. Grid graph can describe the convolutional codes and transfer with the passage of time case. The ordinate represents all state, the abscissa represents time. Grid map in the probability of decoding of convolutional codes is very important, especially in Viterbi decoding, it combines the state graph method is intuitionistic and simple and tree method sequential relationship clear characteristics. The reason for preferring the trellis over the tree is that the number of nodes at any level of the trellis does not continue to grow as the message bit increases; rather, it remains constant at 2K-1, where K is the constraint length of the code. The Viterbi algorithm operates by computing a metric or discrepancy for every possible path in the trellis. The metric for a particular path is defined as the Hamming distance between the coded sequence represented by the path and the received sequence. Thus, for each node (state) in the trellis, the algorithm compares the two paths entering that node. The path with lower metric is retained while the other path is discarded. The paths that are retained by the algorithm are the survivors. The Viterbi algorithm proceeds in a step-by-step fashion as follows: Initial step Label the left most state of the trellis (i.e., the all zero state at level 0) as 0, since there is no discrepancy at this initial point in the computation. Computation step j+1 All survivor paths have been identified. The survivor path and its metric for each state of the trellis are stored. Then at level j+1, compute the metric for all the paths entering each state of the trellis by adding the metric of the incoming branches to the metric of the connecting survivor path from level j. For each state, identify the path with the lowest metric as the survivor of the step j+1, thereby updating the computation. Final ste