Study On Encoding And Decoding Algorithms Of The Tail-biting Convolutional Codes

Registers are introduced into the convolutional codes during the encoding process,which increases the correlation between symbols,and a higher coding gain than linear block codes can be obtained with the same complexity.In general,the initial state of the registers in a traditional convolutional codes is set to zero,but the end state of the registers cannot be determined after the encoding is completed.And this uncertainty will reduce the decoding accuracy.Usually,the registers status need to be reset to zero,and thus more redundant bits will be transmitted,and causes a loss of code rate.When it comes to a shorter code length,the loss will be more serious.To solve the problem,a pre-encoding operation is added before the actual encoding process in the tail-biting convolutional codes.That is,the initial state of the registers in the actual encoding process is set according to the state information after the pre-encoding process,which can make the registers state before and after encoding the same.The tail biting operation does not introduce return-to-zero bits and thus can avoid the code rate loss.This thesis mainly studies on the encoding and decoding algorithms of tail-biting convolutional codes.Based on the characteristic that the encoding process can be divided into two stages: pre-encoding and actual encoding,a fast tail-biting convolutional encoding scheme has been proposed and implemented.The ordinary ping-pong operation is improved by adding a set of registers,so that the data can be input continuously without waiting,which greatly improves the encoding speed.Besides,the advantages,disadvantages and specific principles of several decoding algorithms are briefly analyzed,and the Bi PFSA decoding algorithm is introduced in detail.Based on the Bi PFSA,and starting with reducing decoding delay,two improved parallel decoding algorithms are proposed: MBi PFSA1 and MBi PFSA2.The innovation of this two algorithms is to parallelize the calculation and update process of the heuristic function and the actual search process,which can decrease the number of searches in the entire decoding process and thus reduce the decoding delay.The MBi PFSA1 directly parallelizes the backward search and forward search of Bi PFSA algorithm.Based on the MBi PFSA1,the MBi PFSA2 alters the stop conditions of the backwards search,making the information of the heuristic function more accurate,which is conducive to reduce search times.Finally,it is proved theoretically that this two algorithms have the same optimality as Bi PFSA,that is,a maximum likelihood tail-biting path can be found at the end of the algorithm.The simulation of the proposed decoding algorithms under different frame lengths shows that the decoding accuracy of these two algorithms is only slightly worse than that of Bi PFSA algorithm.The time complexity of the algorithm is mainly reflected in the number of path expansions.By analyzing the extension numbers during the simulation,it can be seen that the two proposed parallel algorithms can reduce the decoding delay compared to the Bi PFSA algorithm.And the lower the Signal-to-Noise rate is,the higher efficiency of delay reduction can be.Of course,more computing and space resources are required in the parallel processing of the backward and forward researches.According to the analysis of the storage paths number in the stack,it can see that the parallel characteristics makes the space complexity of the two algorithms has increased compared to the Bi PFSA algorithm,and with the decrease of signal-to-noise ratio,this phenomenon is more serious.In summary,the two algorithms proposed in this thesis have achieved an improvement in decoding delay at the cost of increased space and calculation complexity.