Cycle Analysis Of Low-Density Parity-Check Codes

With the superior error correction capability, low-density parity-check (LDPC) codeshave wide applications in the satellite communication, wireless communication, andstorage fields. LDPC codes were discovered in as a class of Shannon limits approach-ing error correcting codes. They have gradually become a hot research area. LDPCcodes possess many advantages: error performance approaching Shannon limits, easydescription and implementation, convenient theoretical analysis and research, easilydecoded in complete parallel ways and suitable for hardware implementation, etc..However, their encoding complexity is very high and the storage of LDPC codesrequires large memories. As a class of structured LDPC codes, Quasi-cyclic (QC)LDPC codes then become an interesting topic since they have linear time complexityand require less storage.Girth is an important parameter to evaluate the performance of LDPC codes, sincein iterative decoding, the initial number of iterations is linear to the girth. It shows thatshort cycles, which induce small girth, have negative e?ect on decoding performanceof LDPC codes. It is necessary to avoid or eliminate short cycles to construct goodLDPC codes with large girth. So making clear cycle structures and properties is helpfulfor constructing LDPC codes with large girth.This dissertation mainly discuss cycle structures and properties in LDPC codes.Since the girth of the conventional QC-LDPC codes is at most 12, we will especiallydiscuss cycles in QC-LDPC codes.First, we introduce a more general definition of cycle and investigate simple cy-cles in LDPC codes. We present the number of simple cycles of arbitrary length andall the minimal matrices of simple cycles.Second, to eliminate a special class of cycles in QC-LDPC codes, we considerQC-LDPC codes with circulant permutation matrices as protograph LDPC codes. Andwe reveal the relationship of cycles in a protograph LDPC code and its mother matrix.We show that the girth of a protograph LDPC code is not smaller than the girth of its mother matrix.Finally, we study the inevitable cycles in QC-LDPC codes which is also calledbalanced cycles. We show the structure of balanced cycles and their necessary andsu?cient existence conditions. All the B-minimal matrices of the shortest balancedcycles are presented. We also present a method to determine the B-girth of a QC-LDPC code in its mother matrix.