LDPC codes constructed from cubic symmetric graphs
- PDF / 1,243,678 Bytes
- 18 Pages / 439.37 x 666.142 pts Page_size
- 59 Downloads / 223 Views
LDPC codes constructed from cubic symmetric graphs Dean Crnković1 · Sanja Rukavina1 · Marina Šimac1 Received: 20 February 2020 / Revised: 20 September 2020 / Accepted: 3 October 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract Low-density parity-check (LDPC) codes have been the subject of much interest due to the fact that they can perform near the Shannon limit. In this paper we present a construction of LDPC codes from cubic symmetric graphs. The codes constructed are (3, 3)-regular and the vast majority of the corresponding Tanner graphs have girth greater than four. We analyse properties of the codes obtained and present bounds for the code parameters, the dimension and the minimum distance. Furthermore, we give an expression for the variance of the syndrome weight of the codes constructed. Information on the LDPC codes constructed from bipartite cubic symmetric graphs with less than 200 vertices is presented as well. Some of the codes constructed are optimal, and some have an additional property of being self-orthogonal or linear codes with complementary dual (LCD codes). Keywords LDPC code · Cubic graph · Arc-transitive graph · Bipartite graph Mathematics Subject Classification 94B05 · 05C99
1 Introduction We assume that the reader is familiar with the basic facts of graph theory and coding theory. We refer the reader to [1, 8] and [15] for related background materials on graphs and codes, respectively. In this paper we consider only non-trivial finite connected graphs without loops and multiple edges. LDPC codes were first introduced by Gallager in the early 1960’s (see [10]) and rediscovered by MacKay and Neal (see [19]). These codes have been the subject of * Dean Crnković [email protected] Sanja Rukavina [email protected] Marina Šimac [email protected] 1
Department of Mathematics, University of Rijeka, Radmile Matejčić 2, 51000 Rijeka, Croatia
13
Vol.:(0123456789)
D. Crnković et al.
much interest due to the fact that they can perform near the Shannon limit (see [10]). For some recent results on LDPC codes we refer the reader to [30, 33]. Over the past years researchers have constructed LDPC codes that are free of cycles of length four using various structures, including graphs (see, e.g., [7, 28]). Regular bipartite graphs with large girth constructed in [18] were used in [17] as Tanner graphs of LDPC codes. In this paper we construct LDPC codes using bipartite cubic symmetric graphs as Tanner graphs of LDPC codes. We study properties of these LDPC codes and in Sect. 3 we prove our Main theorem. Theorem 1 (Main theorem) Let G be a connected bipartite CSG with 2n, n > 7, vertices and girth g. Further, let Γ be the corresponding bit node graph and let 𝜆2 be the second largest eigenvalue of an adjacency matrix of G. Then the following hold. 1. The minimum distance of the code C(G) is at least six if and only if the clique number of the graph Γ is at most three. 2. The minimum distance d of the code C(G) satisfies the following condition:
⎧ 2 n, for 𝜆 ≤ 2, 2
Data Loading...
