On The Backward State Transition Based Distance Spectrum Computation Algorithm For Turbo Codes

As a capacity approaching error correction code, Turbo codes have received great attention due to its impressive performance. There is a number of research work, in terms of either theoretical analysis or practical implementation considerations, the existing straightforward algorithm for the determination of weight spectrum of convolutional codes can not be extended directly to accurately calculate the distance spectrum of Turbo codes due to the presence of interleaver. Although there are some algorithms proposed recently, the accurate distance spectrum calculation algorithm for Turbo codes is not sufficient.After a brief survey of the channel coding theory, the state of the art of Turbo codes and the weight spectrum determination problem for Turbo codes are presented at first. It is shown that, weight-two input search algorithm, error events search algorithm, the constrained subcode search algorithm are three primary known schemes for the free distance/weight spectrum estimate/ calculation so far. And the constrained subcode search algorithm and its variations are the only known one that offers an effective method to get the accurate weight distribution knowledge for a specific Turbo codes. It is unveiled that the critical problem is how to accurately evaluate the so called Constrained Input and the Minimum Output hamming Weight (CMOW) of the component RSC encoder for any input candidate. Then a new algorithm of the so called Backward State Transition-based (BST) algorithm is proposed to solve the CIMOW problem in the first step, and determine the free distance for Turbo codes by incorporating itself into the constrained subcode algorithm. The proposed BST algorithm distinguish itself with the previsouly proposed algorithm in the following two aspects: state transition merging and backward computation. It is unveiled that, multiple consecutive "0" input constraints or non-constraints could be merged into one step, thus the BST algorithm could be utilized to improve the computation efficiency. Meanwhile, it is shown that, two tricks, i.e., by including input weight into the CIMOW determination for the second component code and a backward traverse searching, can improve the efficiency as well. It is validated by comparison that, the proposed algorithm can get exactly the same free distance and multiplicities as those by using the Garello's constrained subcode algorithm for the 3GPP standard Turbo codes.Then the BST based constrained subcode algorithm is employed to determine the free distance for the punctured Turbo codes, nonsystematic Turbo codes, asymmetric Turbo codes. It is unveiled that, when the code rate is less than a certain value, the Non-Systematic puncturing pattern and the irregular puncturing pattern can both improve the performance of Turbo codes. Nonsystematic Turbo codes and asymmetric Turbo codes may have larger free distance as well. It is shown that, the block segemented coding strategy will affect significantly the achieved free distance/effective distance; however, it has a lttile impact on the achieved reliability. Since the block segemented coding strategy is some kind of nonlinear modified coding scheme, besides the weight distribution, it seems that its influence on the achieved performance for Turbo codes needs more investigation to understand its mechanism.