×

Some low-density parity-check codes derived from finite geometries. (English) Zbl 1185.05033

Summary: 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.

MSC:

05B25 Combinatorial aspects of finite geometries
05C38 Paths and cycles
05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
51E12 Generalized quadrangles and generalized polygons in finite geometry
51E21 Blocking sets, ovals, \(k\)-arcs
51E22 Linear codes and caps in Galois spaces
94B27 Geometric methods (including applications of algebraic geometry) applied to coding theory

Software:

LDPC
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bagchi B., Sastry N.S.N.: Codes associated with generalized polygons. Geometriae Dedicata 27, 1–8 (1988) · Zbl 0655.94017 · doi:10.1007/BF00181609
[2] Biggs N.: Algebraic graph theory, Cambridge tracts in mathematics 67. Cambridge University Press, London (1974)
[3] Bose R.C.: Mathematical theory of the symmetric factorial designs. Sankhya 8, 107–166 (1947) · Zbl 0038.09601
[4] Fossorier M.P.C.: Quasicyclic low-density parity check codes from circulant permutation matrices. IEEE Trans. Inform. Theory 50, 1788–1793 (2004) · Zbl 1300.94123 · doi:10.1109/TIT.2004.831841
[5] Gallager R.G.: Low density parity check codes. IRE Trans. Inform. Theory 8, 21–28 (1962) · Zbl 0107.11802 · doi:10.1109/TIT.1962.1057683
[6] Hirschfeld J.W.P.: Projective geometries over finite fields 2nd edn. Oxford University Press, Oxford (1998) · Zbl 0899.51002
[7] 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). · Zbl 1025.51012
[8] Johnson S.J., Weller S.R.: Regular low-density parity-check codes from oval designs. Eur. Trans. Telecommun. 14(5), 399–409 (2003)
[9] 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).
[10] 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).
[11] 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).
[12] 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) · Zbl 1123.51015 · doi:10.1007/s10623-006-9017-6
[13] 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) · Zbl 1315.94140 · doi:10.1109/TIT.2004.834760
[14] 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) · Zbl 1015.94015 · doi:10.1109/18.959255
[15] Liu Z., Pados D.A.: LDPC codes from generalized polygons. IEEE Trans. Inform. Theory 51(11), 3890–3898 (2005) · Zbl 1318.94112 · doi:10.1109/TIT.2005.856936
[16] MacKay D.J.C., Neal R.M.: Near Shannon limit performance of low density parity check codes. Electron. lett. 32(18), 1645–1646 (1996) · doi:10.1049/el:19961141
[17] MacKay D.J.C.: Good error correcting codes based on very sparse matrices. IEEE Trans. Inform. Theory 45(2), 399–431 (1999) · Zbl 0946.94030 · doi:10.1109/18.748992
[18] 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) · Zbl 0995.94035
[19] Margulis G.A.: Explicit constructions of graphs without short cycles and low density codes. Combinatorica 2, 71–78 (1982) · Zbl 0492.05044 · doi:10.1007/BF02579283
[20] Payne S.E., Thas J.A.: Finite Generalized Quadrangles. Pitman Advanced Publishing Program, MA (1984) · Zbl 0551.05027
[21] 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) · Zbl 1161.94010 · doi:10.1002/jcd.20179
[22] 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.
[23] Segre B.: Ovals in a finite projective plane. Canad J Math 7, 414–416 (1955) · Zbl 0065.13402 · doi:10.4153/CJM-1955-045-x
[24] 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) · Zbl 1309.94172 · doi:10.1109/TIT.2006.878231
[25] Sipser M., Spielman D.A.: Expander codes. IEEE Trans. Inform. Theory 42, 1710–1722 (1996) · Zbl 0943.94543 · doi:10.1109/18.556667
[26] 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) · Zbl 1287.94122 · doi:10.1109/TIT.2004.838370
[27] 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).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.