Algebraic Constructions Of Low-Density Parity-Check Codes

Low-density parity-check (LDPC) codes have been the central interest of coding re-searchers. They have been implemented in deep space communication, optical communica-tion, magnetic \ optical recorder, ADSL, wireless LAN etc; they are the most promising codingscheme. Tanner graph is an important tool for studying low-density parity-check codes. Thisdissertation concerns the relation between parity-check matrices and cycles of associated Tan-ner graphs, and algebraic construction of low-density parity-check codes. The main results aresummarized as follows:(1) The concept of 2k-cycle-matrix is proposed, and the one to one correspondence between2k-cycle-matrices included in parity-check matrices and cycles of length-2k in the asso-ciated Tanner graphs is proved.(2) Three equivalent conditions for the girth of associated Tanner graph of given parity-checkmatrix to be 2k are proposed.(3) An algorithm to determine the girth of associated Tanner graph of given parity-checkmatrix is proposed, also with an algorithm to count shortest cycles.(4) A method to construct quasi-cyclic low-density parity-check codes from finite cyclicgroups is proposed.(5) A method to construct regular low-density parity-check codes from finite fields is pro-posed.(6) Three method to construct quasi-cyclic low-density parity-check codes from prime fieldsis proposed.