V.B. Afanassiev, A.A. Davydov, V.V. Zyablov

Low density parity check codes on bipartite graphs with Reed-Solomon constituent codes

The following two important problems are considered in the paper: constructing a low density parity check code on a bipartite graph and rapid encoding of this code. For a given constituent code, the first problem solving is reduced to constructing and investigation of parameters of the matrix describing connections of two vertex subsets of a regular bipartite graph (biadjacency matrix). It is convenient to treat the such matrix as a support-matrix of a code word. We propose a number of constructions that essentially extend the region of accessible parameters of the such matrices including these providing graphs without 4-cycles. Biadjacency matrices of regular bipartite graphs without 4-cycles are treated also as the incidence matrices of symmetric combinatorial configurations. This contributes to understanding and solving of the first problem. The second problem solving leads to search of such support-matrix transformations that maximize the encoding speed and allow us to find non trivial complexity estimates.

КЛЮЧЕВЫЕ СЛОВА: low density parity check code, bipartite graph, encoding speed