卷积码外文文献.pdf

a comparative study of viterbi and fano decoding algorithm for convolution codes kapil gupta*, p.k.ghosh*, r.n piplia* and anup dey* * mody institute of technology rather, it remains constant at 2k-1, where k is the constraint length of the code. 35 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 step continue the computation until the algorithm completes its forward search through the trellis and reaches the termination node (i.e., all zero state). at this time it makes the decision on the maximum likelihood path. then, the sequence of the symbols associated with that path is released to the destination as the decoded version of the received sequence. after initial step, a decision is then made on the “best” path and the symbol associated with the last branch on the path is dropped. next, the decoding window is forwarded one time interval, and the decision on the?next code frame is made, and so on. for the above-mentioned steps, the encoder trellis diagram and the survivor path are shown in figures 5 and 6, respectively. figure 5. encoder trellis diagram once this information is built up, the viterbi decoder is ready to recreate the sequence of bits that were inputted to the convolution encoder. this is accomplished by the following steps: figure 6. tracing of right path 1.first, select the state having the smallest accumulated error metric and save the state number of the state. 2.iteratively perform the following step until the beginning of the trellis is reached: working backward through the state history table and for the selected state, select a new state which is listed in the state history table as being the predecessor to that state. save the state number of each selected state. this step is called trace back. now work forward through the list of selected states saved in the previous steps. look up what input bit corresponds to a transition from each predecessor state to its successor state. table 2 shows the accumulated metric for full 15 bit (plus two flushing bits) message at each time t. it is interesting to note that for this hard decision input viterbi decoder example, the smallest accumulated error metric in the final state indicates how many channel symbol errors occurred. table 2. accumulated metric for t=17 table 3 shows the states selected when tracing the path back through the survivor state. table 3: selected metric when traced backward. fano decoding algorithm: the fano decoding algorithm searches for the most probable path through the tree or trellis by examining one path at a time. the increment added to the metric along each branch is proportional to the received bit sequence for that branch and a negative constant is also added to each branch metric. the value of the negative constant is chosen such that the metric for the correct path will increase on the average while the same for the incorrect path will decrease on the average. by comparing the 36 metric of the paths with increasing threshold, fano algorithm detects and discards the incorrect paths. the advantage of fano decoding is that such decoding allows the decoder to avoid the lengthy process of testing every branch of the possible 2k branches of the code tree in the decoding of single message bit. it proceeds from node to node, taking the most probable branch at each node and increasing the threshold such that the threshold is never more than some pre-assigned value, say ?, below the metric. if decoder takes an incorrect path because of noise, it appears more probable than the correct path. since the metric of an incorrect path decreases on the average, the metric will fall below the current threshold, say, ?o when this occurs, the decoder backs up and takes alternate path through the tree in order of decreasing branch metrics, with an aim to find another path that exceeds the threshold ?o .if it is successful in finding the alternative path, it continues along the path, always selecting the most probable branch at each node. on the other hand, if no path exists that exceeds the threshold ?o the threshold is reduced by an amount ? and the original path is retraced. if the original path does not stay above the new threshold value, the decoder resumes its backward search for another path. this procedure is continued, with the threshold reduced by ? for each repetition, until the decoder finds a path that remains above the threshold value. in fano decoding at the arrival of first v message bits the decoder compares these bits with the two branches diverging from the starting node. if one of the branches matches exactly with these v code bits, then the encoder follows this branch. if there are errors in received bits due to noise, the encoder follows the branch with less discrepancy. at the second node a similar comparison is made between the diverging branches and the second set of bits and so on at succeeding nodes. if in the transmission of any v bits, branch errors have found more than half of the bits, then at the node from which the branch diverges, the decoder will make mistake. for such case the entire decoding on this path must be in error. to combat this, the decoder keeps a record of the total number of discrepancies between the received code bits and the corresponding bits encountered in the path. the decoder is programmed in such a way that it retraces its path back to the node at which the apparent errors has taken place and choose an alternative branch out of the node. in this way the decoder will find a path through k nodes. steps involved in simulation of communication channel using convolution encoding with viterbi and fano decoding are as follows: (1) generation of input bits- binary data. (2) pass data from convolution encoder to produce channel symbols. (3) add noise to the transmitted channel symbol. this is the received channel symbols. (4) pass the received channel symbols from viterbi and fano decoder. (5) comparison is made between the decoded data bits and the input bits. (6) count the number of errors. (7) repeat the process for multiple eb/no values. (8) plot the graph between ber and eb/no. iv result monte carlo simulations are performed, five independent trials are carried out and their average is plotted. as illustrated in figure 7, the plot is for the ber of decoding of convolutional codes using viterbi decoder for constraint length k=3, rate=1/2 and decoding delays d = 4, 5 and 6 times of constraint length. for a bit error rate of 10-3 for decoding delay d=4k, 5k & 6k, the snr is 5db, 4.1 db & 3.6 db respectively. if we take the decoding delay of 5k or 6k then the gains come out 0.9db or 1.4db as compared to the decoding delay of 4k respectively for the same constraint length k=3. 012345678910 10 -3 10 -2 10 -1 10 0 eb/no (db) ber performplot of ber v/s snr for viterbi decoder delay=4k delay=5k delay=6k figure 7. performance of viterbi decoder rate=1/2, k=3, delay=4k, 5k and 6k figure 8 shows the plots of the ber of viterbi decoder for constraint length k=3, rate=1/2, decoding delay d= 5k and fano decoder. performance of viterbi decoding delay of 5k is much better than that of fano sequential decoder. the difference in snr is about 5db. 024681012 10-3 10-2 10-1 100 eb/no (db) ber plot of ber v/s snr for fano decoder & viterbi decoder viterbi fano figure 8. performance of viterbi& fano decoder for r=1/2, k=3, d=5k figure 9 depicts the plot of ber of viterbi decoder for constraint length k=3, rate=1/2, decoding delay d= 6k and fano sequential decoder for the same constraint 37 length k=3. the gain in snr for the ber of 10 -3 is found to be 4.1 db. hence the performance of viterbi decoder with decoding delay 6k is better than that of fano sequential decoder. 012345678910 10 -3 10 -2 10 -1 10 0 eb/no (db) ber plot of ber v/s snr for fano decoder & viterbi decoder viterbi fano figure 9. performance of viterbi & fano decoder for r=1/2, k=3, d=6k v conclusion the numerical results show that the performance of the system increases as the decoding delay increases in case of viterbi decoding. for viterbi decoding when delay d=6k required snr is 3.9 db, for d=5k required snr is 4.1db. for d=5k, rate=1/2, k=3 required snr is 9 db in case of fano decoding and 4.1db in case of viterbi decoding. the gain in snr for the ber of 10 -3 is 4.1 db for d=6k, rate=1/2 and k=3.the ove