| Low-density parity-check codes had been buried in dust for more than thirty years since 1961 when they were invented for the first time by R.G. Gallager in his doctoral dissertation. In the mid 1990's they were reinvented by D. J. C. Mackay and M. Luby independently. The explosive growth of information technology during the end of the last century and the beginning of this century has produced a corresponding increase of commercial interests in the development of highly efficient data transmission codes as such codes impact literally everything ranging from signal quality to battery life.; Due to the sparsity of the parity-check matrices of low-density parity-check codes, which is a low-density parity-check matrix, the complexity of the belief propagation decoding algorithms for the codes can be polynomial. However, the existing low-density parity-check codes are mainly constructed randomly, which makes the encoding procedures expensive. Furthermore, girth, a parameter of the parity-check matrix, plays an important role in determining the successfulness of the decoding algorithm. Generally, the larger the girth is, the more likely the decoding algorithm will succeed.; In this dissertation, a new class of low-density parity-check codes is introduced. These codes are defined by low-density parity-check matrices based on circular permutation matrices as their parity-check matrices. We prove that the girth of these codes cannot exceed 12. A necessary and sufficient condition for these codes to reach such a bound is given, too. In addition, we construct a family of (3, vc) low-density parity-check codes with girth 12 whose encoding complexity is linear to the code length. Moreover, we modify these codes and construct two classes of maximum distance separable codes, Reed-Solomon-like codes and Rabin-like codes, to correct erasure errors in massive storage systems. The former class has encoding and decoding algorithms linear to code lengths while the other class can recover any arbitrary number of erasures. |
