The Cycle-structures Of LDPC Code And The Relevant Algorithms For Constructing The Optimal LDPC Code

In the past two decades,low-density parity-check(LDPC)codes have been deeply and extensively investigated and applied due to their superior performance in approaching the Shannon limit.However,in order to explore the various benefits brought by the pure coding gain of even 0.1 dB,and to solve the scientific problems in the design of LDPC codes,such as the maximization of the girth of the optimal code,both academia and industry are still sparing no effort to deepen research on LDPC codes.As a tireless effort in this deepening research,this dissertation mainly achieves a total of five innovative results in the following three aspects.1)Research on the progressive edge-growth(PEG)-like design methodsWhen the conventional PEG-like design methods establish the edges of a variable node(VN),the establishment of each edge strives to maximize this VN's local girth,but has nothing to do with the subsequently established edges.Therefore,it is difficult for this kind of methods to maximize this VN's local girth after adding more than one edge to this VN.First,to solve this problem,this dissertation innovatively extends the concept of local girth to the concept of multi-edge local girth,and then proposes a new PEG-like design method,called the multi-edge metric-constrained PEG algorithm(MM-PEGA),for constructing non-quasi-cyclic(non-QC)LDPC codes.When this algorithm constructs the edges of a VN,the establishment of each edge is constrained by the subsequently established edges,so as to achieve further optimization of the multi-edge local girth.Second,this dissertation innovatively proposes a new shortest path algorithm to reduce the computational complexity of the MM-PEGA,and generalizes the MM-PEGA under different metrics to extend the MM-PEGA's applicable range.The theoretical analysis and the numerical results consistently show that,the LDPC codes constructed by the MM-PEGA have larger girths than the codes constructed by the conventional PEG-like design methods.Therefore,it is reasonable that the codes constructed by the MM-PEGA have better error performances.2)Research on the PEG-like design methods of QC-LDPC codesThird,this dissertation innovatively defines a new concept,called the cyclic edge set minimum virtual cycle(CMVC),and shows the reason why the QC-PEG algorithm(QCPEGA)easily generates unnecessary small cycles,such as 4-and 8-cycles,is because the QC-PEGA cannot effectively detect CMVCs.In order to overcome the drawback that the QC-PEGA cannot effectively detect CMVCs,this dissertation extends the concept of multi-edge local girth to the design of QC-LDPC codes.Then,based on the extended concept,this dissertation proposes a new PEG-like design method,called the multi-edge metric-constrained QC-PEG algorithm(MM-QC-PEGA),for constructing QC-LDPC codes.By accurately calculating the length of any CMVC,the MM-QC-PEGA can detect CMVCs of all lengths,making the MM-QC-PEGA effective in avoiding generating unnecessary small cycles.Fourth,this dissertation finds that the computational complexity in the design of QC-LDPC codes can be reduced by sacrificing part of the ability to detect CMVCs.To this end,this dissertation innovatively proposes a method,called the greatest common divisor(GCD)-approximation,to approximately compute the length of CMVC.GCDapproximation is also applied in the MM-QC-PEGA to construct QC-LDPC codes.Using the GCD-approximation,the number of times for accurately computing the length of CMVC in the MM-QC-PEGA can be reduced.In addition,optimizing the PEG-like design methods of QC-LDPC codes by using the GCD-approximation leads to a lower computational complexity.The numerical and the simulation results are consistent with the theoretical analysis in that,the codes constructed by the MM-QC-PEGA and the G-MM-QC-PEGA have improved cycle structures and error performances.For example,regarding the flame error performance at 1E-6,the(576,288)QC-LDPC codes constructed by the MM-QCPEGA and the G-MM-QC-PEGA have about 0.5dB coding gain over the code with the same parameters in the 802.16 e standard.3)Research on the masking techniqueThe conventional masking techniques generally require the base matrix to consist of an array of circulant permutation matrix(CPM)or permutation matrix of the same size.In addition,some conventional mask techniques are not suitable for constructing a large masking matrix because of high computational complexity.Fifth,based on the principle of edge growth,this dissertation proposes a new concept called the PEG-masking.Then,this dissertation proposes a PEG-masking technique called the MM-QC-PEGA-based PEG-masking,which has low computational complexity and high flexibility(being suitable for masking a based matrix consisting of an array of circulant matrix(not just CPM)or permutation matrix of the same size).The numerical and the simulation results show that,the MM-QC-PEGA-based PEGmasking can achieve better cycle-structures and error performances than the conventional masking techniques.