An Algorithm for BCH Codes Extended with Finite State Automata

• Autorzy: Kelarev A.
• Języki publikacji: EN

Abstrakty

EN

This article develops a combinatorial algorithm for a class of codes extending BCH codes and constructed with finite state automata. Our algorithm computes the largest number of errors that the extended codes can correct, and finds a generator for each optimal code in this class of extensions. The question of finding codes with largest possible information rates remains open.

Słowa kluczowe

EN

finite fields; BCH codes; finite state automata

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 84, nr 1
• Strony: 51--60
• Opis fizyczny: bibliogr. 28 poz.

Twórcy

autor

Kelarev A.

• School of Information Technology and Mathematical Sciences, University of Ballarat, P.O. Box 663, Ballarat, Victoria 3353, Australia,

Bibliografia

• [1] Bǎca, M., Jendrol, S., Miller, M. and Ryan, J.: Antimagic labelings of generalized Petersen graphs that are plane, Ars Combin. 73, 2004, 115-128.
• [2] Bereg, S.N., Kelarev, A.V. and Salagean, Ana: Directed graphs and minimum distances of error-correcting codes in matrix rigns, New Zealand J. Math. 33(2), 2004, 113-120.
• [3] Bierbrauer, J., Edel, Y. and Tolhuizen, L.: New codes via the lengthening of BCH codes with UEP codes, Finite Fields Appl. 5(4), 1999, 345-353.
• [4] Calude, C.S., Calude, E., and Dinneen, M.J.: Developments in Language Theory. 8th Internat. Conf., DLT 2004, Massey, Albany, Auckland, December 13-17, 2004. Lecture Notes in Computer Science, 3340. Springer-Verlag, Berlin, 2004.
• [5] Calude, C.S., Dinneen,M.J., and Vajnovszki, V.: DiscreteMathematics and Theoretical Computer Science. 4th Internat. Conf., DMTCS 2003, Dijon, July 7-12, 2003. Lecture Notes in Computer Science, 2731. Springer-Verlag, Berlin, 2003.
• [6] Cazaran, J., Kelarev, A.V., Quinn, S.J. and Vertigan, D.: An algorithm for computing the minimum distancesof extensions of BCH codes embedded in semigroup rings, Semigroup Forum 73 (2006), 317-329.
• [7] Chen, H.: On minimum Lee weights of Hensel lifts of some binary BCH codes, IEEE Trans. Inform. Theory 45, 1999, 2157-2162.
• [8] Downey, R., Fellows, M. R., Whittle, G. and Vardy, A.: The parametrized complexity of some fundamental problems in coding theory, SIAM J. Comput. 29(2), 2001, 545-570.
• [9] Gallian, J.A.: Graph labeling, Electronic J. Combinatorics, Dynamic Survey DS6, January 20, 2005, 148pp.
• [10] Holub, J., Iliopoulos, C.S., Melichar, B. Mouchard, L.: Distributed string matching using finite automata, Combinatorial Algorithms, AWOCA 99, Perth, 114-127.
• [11] Iliopoulos, C.S., Computing in general abelian groups is hard, Theoret. Comput. Sci. 41 (1985)(1), 81-93.
• [12] Kelarev, A.V.: Ring Constructions and Applications,World Scientific, River Edge, NJ, 2002.
• [13] Kelarev, A.V.: Graph Algebras and Automata, Marcel Dekker, New York, 2003.
• [14] Kelarev, A.V.: On group automata over finite fields, Finite Fields and Their Applications 10, 2004, 65-71.
• [15] Kelarev, A.V., Miller,M. and Sokratova, O.V.: Directed graphs and closure properties for languages, Proc.12 AustralasianWorkshop on Combinatorial Algorithms (Ed. E.T. Baskoro), Putri Gunung Hotel, Lembang, Bandung, Indonesia, July 14-17, 2001, pp.118-125.
• [16] Kelarev, A.V.,Miller,M. and Sokratova, O.V.: Languages recognized by two-sided automata of graphs, Proc. Estonian Akademy of Science 54(1), 2005, 46-54.
• [17] Lin, Y. and Miller, M.: Vertex magic total labelings of complete graphs, Bull. Inst. Combin. Appl. 33, 2001, 68-76.
• [18] Lin, Y., Slamin, Baˇca, M. and Miller,M.: On d-antimagic labelings of prisms, Ars Combin. 72, 2004, 65-76.
• [19] Martin-Vide, C., Mitrana, V. and P˘aun, G.: Formal Languages and Applications. Studies in Fuzziness and Soft Computing, 148. Springer-Verlag, Berlin, 2004.
• [20] Miller, M., Patel, D., Ryan, J., Sugeng, K.A., Slamin and Tuga, M.: Exclusive sum labeling of graphs, J. Combin. Math. Combin. Comput. 55, 2005, 137-148.
• [21] Miller, M., Rodger, C. and Simanjuntak, R.: Distance magic labelings of graphs, Australas. J. Combin. 28, 2003, 305-315.
• [22] Pǎun, G., Rozenberg, G. and Salomaa, A.: Current Trends in Theoretical Computer Science. The Challenge of the New Century. Vol. 1,2..World Scientific, River Edge, NJ, 2004.
• [23] Pless, V. S., Huffman,W. C. and Brualdi, R. A.: Handbook of Coding Theory, Elsevier, New York, 1998.
• [24] Slamin, Bǎca, M., Lin, Y., Miller, M. and Simanjuntak, R.: Edge-magic total labelings of wheels, fans and friendship graphs, Bull. Inst. Combin. Appl. 35, 2002, 89-98.
• [25] Smyth, B.: Computing Patterns in Strings, Addison-Wesley, 2003.
• [26] Spiegel, E. and O'Donnell, C.J.: Incidence Algebras, Marcel Dekker, 1997.
• [27] Stallings, W.: Wireless Communications and Networking, Prentice Hall, 2002.
• [28] Tuga, M., Miller, M., Ryan, J. and Ryj´aˇcek, Z.: Exclusive sum labelings of trees, J. Combin. Math. Combin. Comput. 55, 2005, 109-121.