Algorithms for generation of Ramanujan graphs, other Expanders and related LDPC codes

• Autorzy: Polak M. , Ustimenko V.

Identyfikatory

DOI

10.1515/umcsinfo-2015-0006

• Języki publikacji: EN

Abstrakty

EN

Expander graphs are highly connected sparse finite graphs. The property of being an expander seems significant in many of these mathematical, computational and physical contexts. For practical applications it is very important to construct expander and Ramanujan graphs with given regularity and order. In general, constructions of the best expander graphs with a given regularity and order is no easy task. In this paper we present algorithms for generation of Ramanujan graphs and other expanders. We describe properties of obtained graphs in comparison to previously known results. We present a method to obtain a new examples of irregular LDPC codes based on described graphs and we briefly describe properties of this codes.

Słowa kluczowe

EN

Ramanujan graphs; LDPC codes

• Wydawca: Wydawnictwo UMCS
• Czasopismo: Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica
• Rocznik: 2015
• Tom: Vol. 15, no. 2
• Strony: 14--21
• Opis fizyczny: Bibliogr. 24 poz., rys., tab.

Twórcy

autor

Polak M.

• Institute of Mathematics, Maria Curie-Sklodowska University, pl. M. Curie-Sklodowskiej 5, 20-031 Lublin, Poland

autor

Ustimenko V.

• Institute of Mathematics, Maria Curie-Sklodowska University, pl. M. Curie-Sklodowskiej 5, 20-031 Lublin, Poland

Bibliografia

• [1] D. Gillman, A Chernoff bound for random walks on expander graphs, SIAM J. Comput. 27 (4) (1998): 1203.
• [2] M. Polak, V. Ustimenko, On new expanders of unbounded degree for practical applications in Informatics, Dopovidi Nacionalnoj Akademii Nauk Ukrain 12 (2014): 44.
• [3] M. Polak, V. Ustimenko, Examples of Ramanujan and expander graphs for practical applications, Proceedings of the 2013 Federated Conference on Computer Science and Information Systems (2013): 499.
• [4] B. Bollobas, Extremal Graph Theory, Academic Press (1978).
• [5] N. L. Biggs, Algebraic Graph Theory, (2nd ed), Cambridge, University Press (1993).
• [6] A. Brouwer, A. Cohen, A. Neumaier, Distance-Regular Graphs, Springer-Verlag (1989).
• [7] S. Hoory, N. Linial, A. Wigderson, Expander graphs and their applications, Bulletin (New Series) of the American Mathematical Society 43 (2006): 439.
• [8] G.A. Margulis, Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction of expanders and concentrators, Problemy Peredachi Informatsii 24 (1) (1988): 51.
• [9] A. Lubotsky, R. Philips, P. Sarnak, Ramanujan graphs, Combinatorica 9 (1988): 261.
• [10] R. Weiss, Distance transitive graphs and generalised polygons, Arch. Math 45 (1985): 186.
• [11] W. Feit, D. Higman, The nonexistence of certain generalised polygons, J. of Algebra 1 (1964): 114.
• [12] V. A. Ustimenko, On some properties of geometries of the Chevalley groups and their general- izations, Studies in Algebraic Theory of Combinatorial Objects, Moskow; English transl, Kluwer Publ., Dordresht (1991): 112.
• [13] F. Lazebnik, V. A. Ustimenko, A. J. Woldar, A new series of dense graphs of high girth, Bulletin (New Series) of the AMS 32 (1995): 73.
• [14] R. G. Gallager, Low-Density Parity-Check Codes, Monograph, M.I.T. Press (1963).
• [15] M. Luby, M. Mitzenmacher, M. A. Shokrollahi, D. A. Spielman, Improved Low-Density Parity- Check Codes Using Irregular Graphs and Belief Propagation, ISIT 98-IEEE International Symposium of Information Theory, Cambridge, USA (1998): 171.
• [16] D. J. C. MacKay, Good error-correcting codes based on very sparse matrices, Information Theory, IEEE Transactions 45 (2) (1999): 399.
• [17] M. Sipser, D. A. Spielman, Expander codes, IEEE Trans on Info Theory, 42 (6) (1996): 1710.
• [18] R. M. Tanner, A recursive approach to low density codes, IEEE Transactions on Information Theory IT 27 (5) (1984): 533.
• [19] P. Guinand, J. Lodge, Tanner type codes arising from large girth graphs, in Canadian Workshop on Information Theory CWIT, Toronto, Ontario, Canada (1997): 5.
• [20] M. Luby, M. Mitzenmacher, M. A. Shokrollahi, D. A. Spielman, and V. Stemann, Practical loss-resilient codes, Proc. 29th Annu. ACM Symp. Theory of Computing (1997): 150.
• [21] M. Luby, M. Mitzenmacher, M. A. Shokrollahi, D. A. Spielman, Analysis of low density codes and improved designs using irregular graphs, Proc. 30th Annu. ACM Symp. Theory of Computing (1998): 249.
• [22] D. MacKay, S. Wilson, M. Davey, Comparison of constructions of irregular Gallager codes, IEEE Trans. Commun. 47 (Oct. 1999): 1449.
• [23] M. Luby, M. Mitzenmacher , M. A. Shokrollahi , D. A. Spielman, and V. Stemann, Practical loss-resilient codes, IEEE Trans. Inform. Theory 47 (2001): 569.
• [24] F. Lazebnik, V. A. Ustimenko, Explicit construction of graphs with an arbitrary large girth and of large size, Discrete Applied Mathematics 60 (1995): 275.