The FAST Algorithm And Its Application In The Weight Distribution Determination Of Turbo Codes

The Turbo Codes, which can approach the Shannon limits, are regarded as a milestone in the development history of channel coding theory. Since its invention, the ideas of designing channel codes in terms of algebraic property design and the increase in the minimum hamming weight have been transformed into that random coding strategy together with the decrease in the multiplicities of the low weight codewords. Although the research results of Turbo codes emerged, however, the research in view of the distance spectrum of Turbo codes is not sufficient. As for the existence of interleavers, it is difficult to quantificationally analyse the distance spectrum of Turbo codes as traditional Convolutional Codes. In this dissertation, a deep study is taken on the algorithm of computing the distance spectrum of Turbo codes. Some positive results are obtained and summarized as follow:This thesis firstly reviews Shannon information theory and channel coding theory in brief, then discusses research status and significance of Turbo codes weight spectrum based on analysis of Turbo coding. Started with analysis of Turbo coding structure and relationship between weight spectrum character and constituent recursive convolutional coder, Turbo codes weight spectrum character analysis research thinking based on constituent recursive convolutional coding character analysis is proposed.The calculation method of Turbo constituent recursive convolutional coding weight spectrum is universally derived from FAST (Fast Algorithm for Searching a Tree) algorithm, which is an effective way of general convolutional coding weight spectrum analysis and calculation adopted and used for reference in this thesis. Research shows that FAST algorithm also provides an effective way of quickly calculating Turbo constituent recursive convolutional coding weight spectrum.Common searching algorithms for Turbo codes free distance include Weight-2 input sequence algorithm, Error event algorithm, Constrained sub-code algorithm and so on. Based on analysis and comparison of advantages and disadvantages as well as limitations of these algorithms respectively, a thinking associated with Constrained sub-code algorithm is proposed. The algorithm framework searching and calculating Turbo codes free distance is implemented adopting FAST algorithm. Moreover, research shows that searching efficiency of this algorithm can be effectively improved by bringing information sequence weight into hamming weight derived from second branch coding and properly limiting hamming weight of input information to be searched. Finally, entire searching results of free distance with interleave length less than 2000 and partial corresponding characteristic input information sequences are completed referred to 3GPP Turbo coding standard. Correlative searching results demonstrates that FAST algorithm associated with restrict sub-code thinking offers an effective way of accurately searching Turbo codes free distance.The work in this thesis provides helpful exploration on further study and improvement of Turbo codeword weight spectrum searching algorithm. The searching results in this thesis have reference value for researching on high quality Turbo coding and decoding techniques.