LDPC codes based on algebraic graphs

• Autorzy: Polak M. , Ustimenko V.

Identyfikatory

DOI

10.2478/v10065-012-0034-y

• Języki publikacji: EN

Abstrakty

EN

In this paper we investigate correcting properties of LDPC codes obtained from families of algebraic graphs. The graphs considered in this article come from the infinite incidence structure. We describe how to construct these codes, choose the parameters and present several simulations, done by using the MAP decoder. We describe how error correcting properties are dependent on the graph structure. We compare our results with the currently used codes, obtained by Guinand and Lodge [1] from the family of graphs D(k; q), which were constructed by Ustimenko and Lazebnik [2].

Słowa kluczowe

EN

algebraic graph; LDPC codes; MAP decoder

• Wydawca: Wydawnictwo UMCS
• Czasopismo: Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica
• Rocznik: 2012
• Tom: Vol. 12, no. 3
• Strony: 107--119
• Opis fizyczny: Bibliogr. 16 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 Universit,y pl. M. Curie-Sklodowskiej 5, 20-031 Lublin, Poland
• Institute of Telecommunications and Global Information Space, Kiev, National Academy of Science of Ukraine Chokolovsky Boulevard 13, Kiev, Ukraine

Bibliografia

• [1] Guinand P., Lodge J., Tanner type codes arising from large girth graphs, Canadian Workshop on Information Theory CWIT ’97, Toronto, Ontario, Canada, June 3-6 (1997): 5.
• [2] Lazebnik F., Ustimenko V. A., Woldar A. J., A characterization of the components of the graphs D(k, q), Discrete Mathematics 157 (1996): 271.
• [3] Shannon C. E., A Mathematical Theory of Communication, Bell System Technical Journal 27 (1948): 379.
• [4] Gallager R. G., Low-Density Parity-Check Codes, IRE Trans of Info Thy 8 (1962): 21.
• [5] Luby M. G., Mitzenmacher M., Shokrollahi M. A., Spielman D. A., Improved Low-Density Parity-Check Codes Using Irregular Graphs and Belief Propagation, in ISIT 98-IEEE International Symposium of Information Theory, Cambridge, USA (1998): 171.
• [6] MacKay D. J. C., Neal R. M., Good Codes Based on Very Sparse Matrices, in Cryptography and Coding 5th IMAConference, BERLIN (1995): 100.
• [7] Sipser M., Spielman D. A., Expander codes, IEEE Trans on Info Theory 42 (6) (1996): 1710.
• [8] Tanner R. M., A recursive approach to low density codes, IEEE Transactions on Information Theory IT 27 (5) (1984): 533.
• [9] Guinand P., Lodge J., Graph theoretic construction of generalized product codes, IEEE International Symposium on Information Theory ISIT’97 Ulm, Germany June 29-July 4 (1997): 111.
• [10] Romanczuk U., Ustimenko V., On Extremal Graph Theory, explicit algebraic constructions of extremal graphs and corresponding Turing encryption machines, in Artificial Intelligence, Evolutionary Computing and Metaheuristics, In the footsteps of Alan Turing Series: Studies in Computational Intelligence 427 (2012).
• [11] Bollobas B., Extremal Graph Theory, Academic Press (1978).
• [12] Lazebnik F., Ustimenko V. A., New examples of graphs without small cycles and of large size, European Journal of Combinatorics 14 (1993): 445.
• [13] Lazebnik F., Ustimenko V. A., Explicit construction of graphs with an arbitrary large girth and of large size, Discrete Applied Mathematics 60 (1995): 275.
• [14] Brower A., Cohen A., Nuemaier A., Distance regular graphs, Springer, Berlin (1989).
• [15] Tonchev V. D., Error-correcting codes from graphs, Discrete Math. 257 (2002): 549.
• [16] Zhang Z., Lee P., Anantharam V., Nikolic B., Wainwright M., Dolecek L., Predicting error floors of structured LDPC codes: deterministic bounds and estimates, Journal IEEE Journal on Selected Areas in Communications - Special issue on capaciyy approaching codes archive 27 (6) (2009): 908.