Research On The Encoding Algorithms, Decoding Schedules And Algebraic Costructions Of Low-Density Parity-Check Codes

Low-density parity-check (LDPC) codes have been shown to be a class ofcapacity-approaching codes with iterative decoding. For practical considerations, it isdesirable to add some structures to the code design so that the resultant LDPC codes areequipped with efficient encoding algorithms or have good girth and minimum distanceproperties. It is also desirable to develop new decoding schedules to accelerate theconvergence speed of the conventional flooding schedule and shuffled schedules.Investigations of these issues are taken in this dissertation, and the major contributionsare listed as follows:1) Replica versions of horizontal-shuffled schedules are proposed. The extrinsictransfer (EXIT) chart technique is extended to the proposed schedules to analyze theirconvergence speed. Both EXIT chart analyses and numerical results show that thereplica method is very efficient in accelerating the convergence speed ofhorizontal-shuffled schedules. If an equivalence condition is satisfied, the replica grouphorizontal-shuffled schedule will have both a high convergence speed and a moderatedecoding parallelism, and is thus suitable for hardware implementation.2) Two classes of efficiently encodable non-binary quasi-cyclic (QC-) LDPC codesare constructed. For codes in the first class, the parity parts of the parity-check matricesare in a dual-diagonal form, thus facilitating a recursive encoding. Complexity analysesreveal that the number of required operations in the recursive encoding procedure islinearly proportional to the code length; for codes in the second class, the parity-checkmatrices are carefully designed so that the corresponding sparse generator matrices insystematic quasi-cyclic form can be obtained, which enable a parallel encoding withlow complexity.3) Two constructions of QC-LDPC codes are presented based on two-dimensionalMaximum Distance Separable (MDS) codes, the constructed codes have good minimumdistances and girths of at least6. Due to the heavy column weights of our proposedcodes, they are suitable for hard-decision decoding algorithms such as one-stepmajority-logic (OSMLG) decoding and bit-flipping (BF) decoding. Rank analyses of theparity-check matrices of our proposed codes are given by using Fourier transformtechnique, which tell the dimensions of these codes.