Abstract
The error-correcting code (ECC) is one of the channel coding technique widely used in many applications. Low density parity check (LDPC) codes have a remarkable performance Among the error-correcting codes, and have drawn significant attention for their error-correcting capability using the message-passing decoding algorithm. The PEG algorithm is a good sub-optimal method to construct the Tanner graph for a LDPC code. By progressively establishing edges between the furthest nodes, the PEG algorithm is able to build a Tanner graph while maximizing length of the cycle caused in the edge adding progress. In this thesis, we introduces a greedy algorithm for quasi-cyclic (QC) LDPC code construction, which works in the same manner as the PEG algorithm. QC-LDPC codes are a subclass of LDPC codes which gains benefits on encoding/decodng complexity reduction from their circular shifting structures. In the proposed algorithm, a QC-LDPC code is built by extending a small size matrix to the target size with large cycles. Our algorithm focuses on cycle length stretching during the matrix extension. The matrix extension is implemented by fitting proper circulant matrix while eliminating short cycles. We present a new kind of depth tree for circulant search in matrix extension procedure. Our algorithm brings out the QC-LDPC code with reconfigurable code parameter settings and has good performance close to PEG LDPC codes. Furthermore, the use of matrix extension reduces the computation scale, and provides a efficient and easy-to-implement method to construct a QC-LDPC code.