Low Complexity Regular LDPC codes for Magnetic Storage Devices

Authors: Gabofetswe Malema, Michael Liebelt

Abstract:

LDPC codes could be used in magnetic storage devices because of their better decoding performance compared to other error correction codes. However, their hardware implementation results in large and complex decoders. This one of the main obstacles the decoders to be incorporated in magnetic storage devices. We construct small high girth and rate 2 columnweight codes from cage graphs. Though these codes have low performance compared to higher column weight codes, they are easier to implement. The ease of implementation makes them more suitable for applications such as magnetic recording. Cages are the smallest known regular distance graphs, which give us the smallest known column-weight 2 codes given the size, girth and rate of the code.

Keywords: Structured LDPC codes, cage graphs.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1330409

References:

[1] R.G. Gallager, "Low-density parity-check codes," IRE Transactions on Information Theory,1964, pp21-28.
[2] H.Song, "Low complexity LDPC codes for magnetic recordings," IEEE Globecom 2002, November 2002.
[3] C.Riggle and S. McCathy, "Design of error correction systems for disk drives," IEEE Transactions Magazine, July 1998, vol. 34,pp .2362- 2371.
[4] H. Zhang and J.M. Moura , "Large-girth LDPC codes based on graphical models ," IEEE Workshop on Signal Processing., 2003, pp-100-103.
[5] N.L Biggs, "Constructions for Cubic Graphs of large Girth," Electronic Journal of Combinatorics, vol. 5, 1998.
[6] G. Exoo , "A Simple Method for Constructing Small Cubic Graphs of Girths 14,15 and 16 ," Electronic Journal of Combinatorics, Vol. 3,1996.
[7] P.K Wong, "CagesÔÇöA Survey," Journal of Graph Theory., vol. 3 1982, pp-1-22.
[8] N.L Biggs, "Cubic Graphs with Large Girth," Combinatorial Mathematics: Proceedings of the Third International Conference,1998, pp.56-62.
[9] E.W Weisstein , "Cage Graph ," From MathWorldÔÇöA Wolfram Web Resource. http://www.mathworld.wolfram.com/CageGraph.html
[10] G. Royle, "Cages of higher valency," (Online) Available:http://www.cs.uwa.edu.au/gordon/cages/allcages.html
[11] M. Meringer, "Fast generation of regular graphs and construction of cages," Journal of Graph Theory, 1999, vol.30, pp.137-146.
[12] M. Meringer, "Genreg-download and manual," (Online) Available: http://www.mathe2.unibayreuth.de/markus/manual/genreg.html.