Multi-twisted codes as free modules over principal ideal domains

Document Type : Research Paper

Author

Faculty of Engineering, Ain Shams University, Cairo, Egypt

Abstract

We begin by introducing the simple algebraic structure of cyclic, constacyclic, quasi-cyclic (QC), quasi-twisted (QT), generalized quasi-cyclic (GQC), and multi-twisted (MT) codes over finite fields. Then, we establish the correspondence between these codes and submodules of the free Fq[x]-module (Fq[x]). We show that an MT code is a linear code over the principal ideal domain (PID) Fq[x]. Hence, a basis of this code exists and is used to build a generator matrix with polynomial entries, called the generator polynomial matrix (GPM). The Hermite normal form of matrices over PIDs is exploited to achieve the reduced GPMs of MT codes. Some properties of the reduced GPM are introduced, for example, the identical equation. A formula for a GPM of the dual code of an MT code is established. At this point, special attention is paid to QC codes. We characterize GPMs for QC codes that combine reversibility and self-duality/self-orthogonality. We show the existence of binary self-orthogonal reversible QC codes that have the best known parameters as linear codes.

Keywords


[1] N. Aydin and A. Halilović, A generalization of quasi-twisted codes: Multi-twisted codes, Finite Fields Their Appl., 45 (2017) 96-106.
[2] M. Barbier, C. Chabot, and G. Quintin, On quasi-cyclic codes as a generalization of cyclic codes, Finite Fields Their Appl., 18 No. 5 (2012) 904-919.
[3] Y. Cao, Structural properties and enumeration of 1-generator generalized quasi-cyclic codes, Des. Codes Cryptogr., 60 No. 1 (2010) 67-79.
[4] P. L. Cayrel, C. Chabot, and A. Necer, Quasi-cyclic codes as codes over rings of matrices, Finite Fields Their Appl., 16 No. 2 (2010) 100-115.
[5] V. Chauhan, Multi-twisted Codes Over Finite Fields and Their Generalizations, Ph.D. thesis, Indraprastha Institute of Information Technology, 2021.
[6] E. Chen and N. Aydin, A database of linear codes over F13 with minimum distance bounds and new quasi-twisted codes from a heuristic search algorithm, J. Algebra Comb. Discrete Struct. Appl., 2 (2015).
[7] S. T. Dougherty, Algebraic coding theory over finite commutative rings, 1st ed., Springer International Publishing, Switzerland, 2017.
[8] R. Taki Eldin and H. Matsui, Quasi-cyclic codes via unfolded cyclic codes and their reversibility, IEEE Access, 7 (2019) 184500-184508.
[9] R. Taki Eldin and H. Matsui, Good reversible quasi-cyclic codes via unfolding cyclic codes, IEICE Commun. Express, 9 No. 12 (2020) 668-673.
[10] R. Taki Eldin and H. Matsui, On reversibility and self-duality for some classes of quasi-cyclic codes, IEEE Access, 8 (2020) 143285-143293.
[11] R. Taki Eldin and H. Matsui, Linking reversed and dual codes of quasi-cyclic codes, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 105 No. 3 (2021) 381-388.
[12] J. Gao and F. W. Fu, Note on quasi-twisted codes and an application, J. Appl. Math. Comput., 47 No. 1-2 (2014) 487-506.
[13] J. von zur Gathen and J. Gerhard, Modern Computer Algebra, 3rd ed., Cambridge University Press, 2013.
[14] E. N. Gilbert, A comparison of signalling alphabets, Bell Syst. Tech. J., 31 No. 3 (1952) 504-522.
[15] M. Grassl, Searching for linear codes with large minimum distance, In Discovering Mathematics with Magma, pp. 287-313, Springer Berlin Heidelberg, Berlin, Heidelberg, 2006.
[16] M. Grassl, Bounds on the minimum distance of linear codes and quantum codes, Online available at http://www.codetables.de (2007).
[17] G. G. L. Guardia, On optimal constacyclic codes, Linear Algebra Appl., 496 (2016) 594-610.
[18] C. Güneri, F. Özbudak, B. Özkaya, E. Saçıkara, Z. Sepasdar, and P. Solé, Structure and performance of generalized quasi-cyclic codes, Finite Fields Their Appl., 47 (2017) 183-202.
[19] Y. Jia, On quasi-twisted codes over finite fields, Finite Fields Their Appl., 18 No. 2 (2012) 237-257.
[20] R. Kipp Martin, Large Scale Linear and Integer Optimization: A Unified Approach, Springer, New York, 2012.
[21] K. Lally and P. Fitzpatrick, Algebraic structure of quasicyclic codes, Discrete Appl. Math., 111 No. 1-2 (2001) 157-175.
[22] C. Martinez-Perez and W. Willems, Self-dual doubly even 2-quasi-cyclic transitive codes are asymptotically good, IEEE Trans. Inf. Theory, 53 No. 11 (2007) 4302-4308.
[23] J. L. Massey, Reversible codes, Inf. Control, 7 No. 3 (1964) 369-380.
[24] H. Matsui, On generator and parity-check polynomial matrices of generalized quasi-cyclic codes, Finite Fields Their Appl., 34 (2015) 280-304.
[25] S. Roman, Advanced Linear Algebra, Graduate Texts in Mathematics, Springer, New York, 2008.
[26] A. Sharma, V. Chauhan, and H. Singh, Multi-twisted codes over finite fields and their dual codes, Finite Fields Their Appl., 51 (2018) 270-297.
[27] I. Siap and N. Kulhan, The structure of generalized quasi-cyclic codes, Appl. Math. E-Notes, 5 (2005) 24-30.