The expectation and the variance of the syndrome weight distribution of linear codes after transmission of codewords through a binary symmetric channel are derived exactly in closed form as functions of the code's parity-check matrix and of the degree distributions of the associated Tanner graph. The influence of (check) regularity of the Tanner graph is studied. Special attention is payed to Tanner graphs that have no cycles of length four. We further study the equivalence of some classes of combinatorial designs and important classes of LDPC codes and apply our general results to those more specific structures. Simulations validate the analytical results and show that the actual cumulative distribution function of the syndrome weight is close to that of a normal distribution.
If a linear (n,k,d) code C has a Tanner graph without cycles, then maximum-likelihood soft-decision decoding of C can be achieved in time O(n/sup 2/). However, we show that cycle-free Tanner graphs cannot support good codes: we prove that d/spl les/max{2,2/R} for any linear code of rate R that can be represented by a cycle-free Tanner graph. Moreover, we explicitly construct codes that meet this bound with equality. We also show that all binary codes that have cycle-free Tanner graphs belong to the class of graph-theoretic cut-set codes. We conclude that the number of cycles in a Tanner graph must increase exponentially with the length n for asymptotically good codes.
The main subjects of the thesis are LDPC codes constructed from combinatorial structures. Combinatorial structures that have been used for the construction are:
μ-geodetic graphs obtained from block designs, strongly regular graphs with parameters
(v,k,0,1), and block designs with parameters
(45,5,1). In the thesis we have constructed a family of LDPC codes using
μ-geodetic graphs obtained from block
(v,k,λ) designs. We have shown that the Tanner graphs of LDPC codes constructed from
μ-geodetic graphs obtained from block designs with
k=3 are free of cycles of length four, and we have analyzed properties of the constructed codes. We have examined a connection between the parameters of the constructed codes and the parameters of the initial design. The existence and the structures of absorbing sets in the Tanner graphs of the constructed codes have been analyzed. Analysis of structures of the absorbing sets enabled us to determine the exact number of the absorbing sets of certain size using parameters of the initial design. For construction of LDPC codes we have used strongly regular graphs with parameters
(v,k,0,1) since the Tanner graph of the corresponding LDPC code is free of cycles of length four. We have examined the existence and the structures of absorbing sets in the Tanner graphs of the constructed codes. LDPC codes from some block designs with parameters
(45,5,1) have been constructed. Simulation results for the constructed LDPC codes have been presented.