LDPC codes based on µ-geodetic graphs

Marina Šimac, Dean Crnković, Sanja Rukavina

Marina Šimac

The main subjects of the thesis are LDPC codes constructed from combinatorial structures. Combinatorial structures that have been used for the construction are: \(\mu\)-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 \(\mu\)-geodetic graphs obtained from block \((v, k, \lambda)\) designs. We have shown that the Tanner graphs of LDPC codes constructed from \(\mu\)-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.

Valentina Pepe

Xiuli Li, Chen Zhang, Jun Shen

Josef Lauri, Cen Jung Tjhai

The authors show that a popular way of constructing quasi-cyclic low-density parity check (LDPC) codes is a special case of a construction which is common in graph theory and group theory. It is shown that a generalisation of this construction as coset graphs produces (dv, dc)-regular LDPC codes that have an advantage in terms of the minimum stopping set size compared to quasi-cyclic LDPC codes. A (dv, dc)-regular quasi-cyclic LDPC code cannot have minimum stopping set size larger than (dv+1)!. However, by using coset graphs, a (3, 5)-regular LDPC code with minimum stopping set size of 28 and a (3, 4)-regular LDPC code with minimum stopping set size larger than 32 have been obtained. In addition, the idea of coset graphs also provides a compact algebraic way of describing bipartite graph and the associated parity-check matrix of an LDPC code. Simulation results of iterative decoding of the coset graphs LDPC codes over the binary erasure channel show that some of the codes converge well and based on the truncated stopping set distributions of the codes, which are exhaustively and efficiently enumerated, the error-floor of the codes at low probability of erasure is estimated.

H. Pishro-Nik, Faramarz Fekri