Abstract
We look at low-density parity-check codes over a finite field \({\mathbb{K}}\) associated with finite geometries \({T_2^*(\mathcal{K})}\), where \({\mathcal{K}}\) is a sufficiently large k-arc in PG(2, q), with q = p h. The code words of minimum weight are known. With exception of some choices of the characteristic of \({\mathbb{K}}\) we compute the dimension of the code and show that the code is generated completely by its code words of minimum weight.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Bagchi B., Sastry N.S.N.: Codes associated with generalized polygons. Geometriae Dedicata 27, 1–8 (1988)
Biggs N.: Algebraic graph theory, Cambridge tracts in mathematics 67. Cambridge University Press, London (1974)
Bose R.C.: Mathematical theory of the symmetric factorial designs. Sankhya 8, 107–166 (1947)
Fossorier M.P.C.: Quasicyclic low-density parity check codes from circulant permutation matrices. IEEE Trans. Inform. Theory 50, 1788–1793 (2004)
Gallager R.G.: Low density parity check codes. IRE Trans. Inform. Theory 8, 21–28 (1962)
Hirschfeld J.W.P.: Projective geometries over finite fields 2nd edn. Oxford University Press, Oxford (1998)
Hirschfeld J.W.P., Storme L.: The packing problem in statistics, coding theory and finite projective spaces: update 2001. In: Blokhuis A., Hirschfeld J.W.P., Jungnickel D., and Thas J.A.(eds.) Proceedings of the fourth Isle of thorns conference, developments in mathematics, vol. 3, pp. 201–246. Kluwer Academic Publishers, Dordrecht Finite Geometries, (Chelwood Gate, 16-21 July 2000), (2001).
Johnson S.J., Weller S.R.: Regular low-density parity-check codes from oval designs. Eur. Trans. Telecommun. 14(5), 399–409 (2003)
Johnson S.J., Weller S.R.: Construction of low-density parity-check codes from Kirkman triple systems, In: Proceedings of the IEEE globecom conference, San Antonio TX, available at http://www.ee.newcastle.edu.au/users/staff/steve/ (2001).
Johnson S.J., Weller S.R.: Construction of low-density parity-check codes from combinatorial designs. In: Proceedings of the IEEE information theory workshop, pp. 90–92. Cairns, Australia (2001).
Johnson S.J., Weller S.R.: Codes for iterative decoding from partial geometries. In: Proceedings of the IEEE international symposium on information theory, p. 6. Switzerland, June 30–July 5, extended abstract, available at http://murray.newcastle.edu.au/users/staff/steve (2002).
Kim J.L., Mellinger K., Storme L.: Small weight code words in LDPC codes defined by (dual) classical generalized quadrangles. Des. Codes Cryptogr. 42(1), 73–92 (2007)
Kim J.L., Pele U., Perepelitsa I., Pless V., Friedland S.: Explicit construction of families of LDPC codes with no 4-cycles. IEEE Trans. Inform. Theory 50, 2378–2388 (2004)
Kou Y., Lin S., Fosserier M.P.C.: Low-density parity-check codes based on finite geometries: a rediscovery and new results. IEEE Trans. Inform. Theory 47(7), 2711–2736 (2001)
Liu Z., Pados D.A.: LDPC codes from generalized polygons. IEEE Trans. Inform. Theory 51(11), 3890–3898 (2005)
MacKay D.J.C., Neal R.M.: Near Shannon limit performance of low density parity check codes. Electron. lett. 32(18), 1645–1646 (1996)
MacKay D.J.C.: Good error correcting codes based on very sparse matrices. IEEE Trans. Inform. Theory 45(2), 399–431 (1999)
MacKay D.J.C., Davey M.C.: Evaluation of Gallager codes for short block length and high rate applications; Codes, systems and graphical models. In: Marcus, B., Rosethal, J. (eds) IMA in Mathematics and its Applications, vol. 123, pp. 113–130. Springer-Verlag, New York (2000)
Margulis G.A.: Explicit constructions of graphs without short cycles and low density codes. Combinatorica 2, 71–78 (1982)
Payne S.E., Thas J.A.: Finite Generalized Quadrangles. Pitman Advanced Publishing Program, MA (1984)
Pepe V., Storme L., Van de Voorde G.: Small weight code words in the LDPC codes arising from linear representations of geometries. J. Combin. Designs 17, 1–24 (2009)
Rosenthal J., Vontobel P.O.: Construction of LDPC codes using Ramanujan graphs and ideas from Margulis. In: Voulgaris P.G., and Srikant R. (eds.) Proceedings of the 38th Allerton conference on communications, control and computing, Monticello, IL, pp. 248–257. Coordinated Science Laboratory. 4–6 Oct 2000.
Segre B.: Ovals in a finite projective plane. Canad J Math 7, 414–416 (1955)
Sin P., Xiang Q.: On the dimension of certain LDPC codes based on q-regular bipartite graphs. IEEE Trans. Infom. Theory 52, 3735–3737 (2006)
Sipser M., Spielman D.A.: Expander codes. IEEE Trans. Inform. Theory 42, 1710–1722 (1996)
Tanner R.M., Sridhara D., Sridharan A., Fuja T.E., Costello J.D. Jr: LDPC block codes and convolutional codes based on circulant matrices. IEEE Trans. Inform. Theory 50, 2966–2984 (2004)
Vontobel P.O., Tanner R.M.: Construction of codes based on finite generalized quadrangles for iterative decoding. In: Proceedings of 2001 IEEE international symposium information theory, p. 233. Washington DC (2001).
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by J.W.P. Hirschfeld.
Rights and permissions
About this article
Cite this article
Vandendriessche, P. Some low-density parity-check codes derived from finite geometries. Des. Codes Cryptogr. 54, 287–297 (2010). https://doi.org/10.1007/s10623-009-9324-9
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-009-9324-9