Algebraic and combinatorial constructions of low-density parity-check codes

Low-density parity-check (LDPC) codes form a Shannon limit approaching class of linear block codes. With iterative decoding based on their Tanner graphs, they can achieve outstanding performance. Design and construction of LDPC codes have become one of the focal research points.;This dissertation proposes several systematic constructions of both regular and irregular LDPC codes. Construction methods are algebraic and combinatorial in nature, and simple. They yield good LDPC codes of practical lengths that perform well with iterative decoding. Graph-theoretic construction is based on finding a set of paths in an arbitrary connected graph with the constraint that any two paths in the set have at most one vertex in common. Construction based on Reed-Solomon codes with two information symbols results in a class of regular LDPC codes whose parity-check matrices consist of permutation matrices. A simple systematic method, called masking, for constructing irregular LDPC codes with desired node degree distributions is also proposed.