Study On The Constructions And Decoding Algorithms For LDPC Codes

Low-density parity-check (LDPC) codes are a class of channel codes which havecapacity-approaching performance and relatively low decoding complexity. So it is agood candidate for future communication systems. In this thesis, constructions and itera-tive decoding algorithms of fnite-length LDPC codes are studied, and some main resultsare obtained as follows:Firstly, a method for constructing parity-check matrices of LDPC codes with largegirth by progressively establishing non-zero entry in an entry-by-entry manner, whichis based on optimizing the number distribution of cycles of each non-zero entry. Theadvantages of proposed LDPC codes over codes constructed by progressively edge growth(PEG) algorithm are demonstrated by extensive simulation results on code performance.Secondly, a method for constructing parity-check matrices with large girth and irreg-ular cycle structure by progressively establishing columns in a column-by-column manneris proposed. Given the size and the symbol-node-degree of a parity-check matrix, anentries-selection procedure is started such that the placement of new non-zero entries onthe base matrix has as small number of short cycles and large irregularity cycle structureas possible. Compared with PEG constructed codes, the proposed codes perform betterin the high signal-to-noise ratio (SNR) region.Thirdly, based on a sufcient and necessary conditions of a collection of short cyclesin the parity-check matrix expanded from same length cycles in a base matrix, a cycleelimination algorithm of constructing quasi-cyclic (QC) LDPC codes of large girth is stud-ied. It is shown by simulations that there exist many short cycles in the Tanner graphof the designed code and the performance is not good enough with iterative decoding. Ageneralized sufcient and necessary conditions of short cycles in the parity check matrixexpanded from a base matrix is given. Furthermore, an improved cycle elimination algo-rithm is developed to detect and break such short cycles. Compared with the QC-LDPCcodes constructed by cycle elimination, the codes with the improved cycle eliminationalgorithm show a better performance in the high SNR region.Fourthly, for a cycle-free Tanner graph of an LDPC code, belief propagation (BP)algorithm results in optimal a posteriori probability (APP) decoding algorithm. However,the cycles in the Tanner graphs of LDPC codes make BP decoding algorithm no longeroptimal and Tanner graphs of fnite-length LDPC codes without singly connected nodesinevitably have cycles. A remedy to this problem by synchronizing the timing at whichdiferent nodes pass non-optimal messages based on the graph property of the LDPCcode is studied. By this strategy, the non-optimality of nodes would not afect the global optimality and the number of iterations in which the optimal messages are passed throughthe graph is maximized. Due to not only the correlation information among the incomingmessages through cycle to a variable node and the initial message to the variable node butalso the other information contained in the non-optimal messages of that variable node,an improved BP algorithm is proposed based on making reasonable use of the non-optimalmessages of the variable nodes.Finally, compared to the BP algorithm, the min-sum (MS) algorithm greatly reducesimplementation complexity by replacing the hyperbolic function of the BP algorithm bya linear equation, but it incurs a degradation of performance due to its overestimatedoutputs of check nodes. Therefore, an improved MS algorithm based on reducing thereliability of messages in the MS algorithm is developed by scaling the inequality. Itis shown by simulation results that the proposed algorithm performs better than theBP algorithm in the high signal-to-noise ratio (SNR) region while the computationalcomplexity of the proposed algorithm is much lower.