Abstract
In this paper we prove two results related to low-density parity-check (LDPC) codes. The first is to show that the generating function attached to the pseudo-codewords of an LDPC code is a rational function, answering a question raised in [6]. The combinatorial information of its numerator and denominator is also discussed.
The second concerns an infinite family of q-regular bipartite graphs with large girth constructed in [8]. The LDPC codes based on these graphs have attracted much attention. We show that the first few of these graphs are Ramanujan graphs.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Arslan, O.: The dimension of LU(3,q) codes (preprint) (2008), http://arxiv.org/abs/0802.0015
Beck, M., Robins, S.: Computing the Continuous Discretely: integer-point enumeration in polyhedra. Springer, New York (2007)
Gallager, R.G.: Low-density parity-check codes. IRE Trans. Inform. Theory 8, 21–28 (1962)
Kim, J.-L., Peled, U.N., Perepelitsa, I., Pless, V., Friedl, S.: Explicit construction of families of LDPC codes with no 4-cycles. IEEE Trans. Inform. Theory 50, 2378–2388 (2004)
Koetter, R., Li, W.-C.W., Vontobel, P.O., Walker, J.L.: Pseudo-codewords of cycle codes via zeta functions. In: Proc. IEEE Inform. Theory Workshop, San Antonio, TX, USA, pp. 7–12 (2004)
Koetter, R., Li, W.-C.W., Vontobel, P.O., Walker, J.L.: Characterizations of pseudo-codewords of (low-density) parity check codes. Adv. in Math. 213, 205–229 (2007)
Koetter, R., Vontobel, P.O.: Graph covers and iterative decoding of finite-length codes. In: Proc. 3rd Intern. Conf. on Turbo Codes and Related Topics, Brest, France, pp. 75–82 (2003)
Lazebnik, F., Ustimenko, V.A.: Explicit construction of graphs with arbitrary large girth and of largh size. Discrete Applied Math. 60, 275–284 (1997)
Loeliger, H.-A.: An introduction to factor graphs. IEEE Sig. Proc. Mag. 21, 28–44 (2004)
Lu, M.: Low-density parity-check codes: asymtotic behavior and zeta functions. Thesis, Penn State University, U.S.A (2009)
Lubotzky, A., Phillips, R., Sarnak, P.: Ramanujan graphs. Combinatorica 8, 261–277 (1988)
Rosenthal, J., Vontobel, P.O.: Constructions of LDPC codes using Ramanujan graphs and ideas from Margulis. In: Proceedings of the 38th Allerton Conference on Communication, Control, and Computing, pp. 248–257 (2000)
Sin, P., Xiang, Q.: On the dimensions of certain LDPC codes based on q-regular bipartite graphs. IEEE Trans. Inform. Theory 52, 3735–3737 (2006)
Stark, H.M., Terras, A.A.: Zeta functions of finite graphs and coverings. Adv. in Math. 121, 124–165 (1996)
Wang, C.: Analysis of finite-length low-density parity-check codes. Thesis, Penn State University, U.S.A (in preparation)
Wiberg, N., Loeliger, H.-A., Kotter, R.: Codes and iterative decoding on general graphs. Europ. Trans. on Telecomm. 6, 513–525 (1995)
Wiberg, N.: Codes and Decoding on General Graphs. Thesis, Linköping University, Linköping, Sweden (1996), http://www.it.isy.liu.se/publikationer/LIU-TEK-THESIS-440.pdf
Ziegler, G.M.: Lectures on Polytopes. Springer, New York (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Li, WC.W., Lu, M., Wang, C. (2009). Recent Developments in Low-Density Parity-Check Codes. In: Chee, Y.M., Li, C., Ling, S., Wang, H., Xing, C. (eds) Coding and Cryptology. IWCC 2009. Lecture Notes in Computer Science, vol 5557. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-01877-0_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-01877-0_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-01813-8
Online ISBN: 978-3-642-01877-0
eBook Packages: Computer ScienceComputer Science (R0)