Research On Encoding And Decoding Algorithms Of Rateless Error Correcting Codes For Reducing Decoding Complexity

Different from the traditional channel coding, the rate of rateless codes is not required to be fixed at the transmitter. The encoder can generate encoded symbols on-the-fly, until the receiver decode successfully and feedback an acknowledge information. They have the adaptive channel state properties and are especially suitable for time-varying channels. Rateless codes experience better performance with longer code length when they are used over noisy channels, and belief propagation iterative decoding algorithm based on soft information is utilized for rateless codes over noisy channels, which results in very high decoding complexity. This thesis studies the decoding complexity optimization problem for rateless codes over noisy channels, and considers the decoding complexity reduction scheme from the optimized design of encoding degree distribution and the optimization of the decoding algorithm respectively. The main work is as follows:1. The rateless codes designed by the methods which aim to maximize the coding rate can usually approach capacity. However a large number of decoding iterations are needed to achieve the desired bit error rate performance. Based on the asymptotic convergence analysis of extrinsic information transfer charts, an optimization design method for the degree distributions of non-systematic accumulate rateless codes with a fixed number of decoding iterations is proposed and the mathematical model for optimization is formulated. The degree distributions satisfying the requirements are obtained by solving the mathematical problem. Simulations show that, compared with the codes designed by the traditional maximizing coding rate method, for a given number of decoding iterations, the proposed design scheme can achieve better error correcting performance. What's more, the less the number of iterations is, the more obvious the advantage is.2. The complexity of belief propagation decoding algorithm of rateless codes is closely related to the number of processed symbols in each decoding iteration and the size of the decoding graph. A method to reduce the decoding complexity of rateless codes by deleting low reliable received symbols is proposed. In the decoder, the received symbols whose absolute value of logarithm likelihood ratio is lower than the threshold are removed, together with their corresponding edges, and thus not involved in the decoding process, so as to reduce the decoding complexity. The relationship of the deletion probability and the likelihood ratio deletion threshold is derived, and the average mutual information per symbol with the deletion is analyzed. On the basis of this, the number of symbols should be supplemented by the encoder to achieve the same performance as the decoding without deletion is obtained. And then the reduction of the decoding computations is analyzed. The simulation results of decoding performance are consistent with those of the theoretical analysis, which show that the proposed method can effectively reduce the decoding complexity at the cost of a slight loss of transmission efficiency.