Low Complexity Regular LDPC codes for Magnetic Storage Devices

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.

• Gabofetswe Malema
• Michael Liebelt

• Structured LDPC codes
• cage graphs.

[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.