×

zbMATH — the first resource for mathematics

Roos bound for skew cyclic codes in Hamming and rank metric. (English) Zbl 07313136
Summary: In this paper, a Roos like bound on the minimum distance for skew cyclic codes over a general field is provided. The result holds in the Hamming metric and in the rank metric. The proofs involve arithmetic properties of skew polynomials and an analysis of the rank of parity-check matrices. For the rank metric case, a way to arithmetically construct codes with a prescribed minimum rank distance, using the skew Roos bound, is also given. Moreover, some examples of MDS codes and MRD codes over finite fields are built, using the skew Roos bound.

MSC:
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
94B65 Bounds on codes
16S36 Ordinary and skew polynomial rings and semigroup rings
Software:
SageMath; Magma
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Augot, D., Generalization of Gabidulin codes over fields of rational functions, (21st International Symposium on Mathematical Theory of Networks and Systems (MTNS 2014) (2014))
[2] Augot, D.; Loidreau, P.; Robert, G., Rank metric and Gabidulin codes in characteristic zero, (2013 IEEE International Symposium on Information Theory (2013), IEEE), 509-513
[3] Augot, D.; Loidreau, P.; Robert, G., Generalized Gabidulin codes over fields of any characteristic, Des. Codes Cryptogr., 86, 8, 1807-1848 (2018) · Zbl 1402.94122
[4] Bose, R. C.; Ray-Chaudhuri, D. K., Further results on error correcting binary group codes, Inf. Control, 3, 3, 279-290 (1960) · Zbl 0104.36403
[5] Bose, R. C.; Ray-Chaudhuri, D. K., On a class of error correcting binary group codes, Inf. Control, 3, 1, 68-79 (1960) · Zbl 0104.36402
[6] Bosma, W.; Cannon, J.; Playoust, C., The Magma algebra system. I. The user language, Computational Algebra and Number Theory. Computational Algebra and Number Theory, London, 1993. Computational Algebra and Number Theory. Computational Algebra and Number Theory, London, 1993, J. Symb. Comput., 24, 3-4, 235-265 (1997) · Zbl 0898.68039
[7] Boucher, D.; Geiselmann, W.; Ulmer, F., Skew-cyclic codes, Appl. Algebra Eng. Commun. Comput., 18, 4, 379-389 (2007) · Zbl 1159.94390
[8] Boucher, D.; Ulmer, F., Codes as modules over skew polynomial rings, (IMA International Conference on Cryptography and Coding (2009), Springer), 38-55 · Zbl 1234.94083
[9] Boucher, D.; Ulmer, F., Coding with skew polynomial rings, J. Symb. Comput., 44, 12, 1644-1656 (2009) · Zbl 1174.94025
[10] Boucher, D.; Ulmer, F., Linear codes using skew polynomials with automorphisms and derivations, Des. Codes Cryptogr., 70, 3, 405-431 (2014) · Zbl 1302.94065
[11] Bueso, J.; Gómez-Torrecillas, J.; Verschoren, A., Algorithmic Methods in Non-Commutative Algebra: Applications to Quantum Groups, Mathematical Modelling: Theory and Applications (2003), Springer · Zbl 1063.16054
[12] Calis, G.; Koyluoglu, O. O., A general construction for PMDS codes, IEEE Commun. Lett., 21, 3, 452-455 (2017)
[13] Cauchy, A. L.B., Recherches sur les nombres, J. Éc. Polytech., 9, 99-123 (1813)
[14] Chaussade, L.; Loidreau, P.; Ulmer, F., Skew codes of prescribed distance or rank, Des. Codes Cryptogr., 50, 3, 267-284 (2009) · Zbl 1237.94144
[15] Davenport, H., On the addition of residue classes, J. Lond. Math. Soc., 10, 30-32 (1935) · JFM 61.0149.02
[16] Delenclos, J.; Leroy, A., Noncommutative symmetric functions and w-polynomials, J. Algebra Appl., 06, 05, 815-837 (2007) · Zbl 1144.16021
[17] Delsarte, P., Bilinear forms over a finite field, with applications to coding theory, J. Comb. Theory, Ser. A, 25, 3, 226-241 (1978) · Zbl 0397.94012
[18] Etzion, T.; Wachter-Zeh, A., Vector network coding based on subspace codes outperforms scalar linear network coding, IEEE Trans. Inf. Theory, 64, 4, 2460-2473 (2018) · Zbl 1390.94938
[19] Forney, G. D., Convolutional codes I: algebraic structure, IEEE Trans. Inf. Theory, 16, 6, 720-738 (1970) · Zbl 0205.20702
[20] Gabidulin, E. M., Theory of codes with maximum rank distance, Probl. Pereda. Inf., 21, 1, 3-16 (1985) · Zbl 0585.94013
[21] Gabidulin, E. M.; Paramonov, A.; Tretjakov, O., Ideals over a non-commutative ring and their application in cryptology, (Advances in Cryptology - EUROCRYPT’91 (1991), Springer), 482-489 · Zbl 0766.94009
[22] Gaborit, P.; Murat, G.; Ruatta, O.; Zémor, G., Low rank parity check codes and their application to cryptography, (Workshop on Coding and Cryptography (WCC) (2013))
[23] Gluesing-Luerssen, H., Skew-polynomial rings and skew-cyclic codes (2019), preprint
[24] Gómez-Torrecillas, J.; Lobillo, F. J.; Navaro, G., Computing free distances of idempotent convolutional codes, (Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation. Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation, ISSAC ’18 (2018), ACM: ACM New York, NY, USA), 175-182 · Zbl 1467.94059
[25] Gómez-Torrecillas, J.; Lobillo, F. J.; Navarro, G., A new perspective of cyclicity in convolutional codes, IEEE Trans. Inf. Theory, 62, 5, 2702-2706 (2016) · Zbl 1359.94752
[26] Gómez-Torrecillas, J.; Lobillo, F. J.; Navarro, G., A Sugiyama-like decoding algorithm for convolutional codes, IEEE Trans. Inf. Theory, 63, 10, 6216-6226 (2017) · Zbl 1390.94925
[27] Gómez-Torrecillas, J.; Lobillo, F. J.; Navarro, G., Peterson-Gorenstein-Zierler algorithm for skew RS codes, Linear Multilinear Algebra, 66, 3, 469-487 (2018) · Zbl 07144617
[28] Gómez-Torrecillas, J.; Lobillo, F. J.; Navarro, G.; Neri, A., Hartmann-Tzeng bound and skew cyclic codes of designed Hamming distance, Finite Fields Appl., 50, 84-112 (2018) · Zbl 1425.94084
[29] Gómez-Torrecillas, J.; Lobillo, F.; Navarro, G., Cyclic distances of idempotent convolutional codes, J. Symb. Comput. (2019) · Zbl 07249896
[30] Hartmann, C. R.; Tzeng, K. K., Generalizations of the BCH bound, Inf. Control, 20, 5, 489-498 (1972) · Zbl 0241.94013
[31] Hocquenghem, A., Codes correcteurs d’erreurs, Chiffres, 2, 2, 147-156 (1959) · Zbl 0090.34608
[32] Jacobson, N., Finite-Dimensional Division Algebras over Fields (1996), Springer: Springer Berlin · Zbl 0874.16002
[33] Kshevetskiy, A.; Gabidulin, E. M., The new construction of rank codes, (Proceedings of the International Symposium on Information Theory (ISIT) 2005 (Sept 2005)), 2105-2108
[34] Lam, T.-Y., A General Theory of Vandermonde Matrices (1985), Center for Pure and Applied Mathematics, University of California: Center for Pure and Applied Mathematics, University of California Berkeley · Zbl 0598.15015
[35] Lam, T.-Y.; Leroy, A., Vandermonde and Wronskian matrices over division rings, J. Algebra, 119, 2, 308-336 (1988) · Zbl 0657.15015
[36] Lang, S., Algebra, Graduate Texts in Mathematics, vol. 211 (2002), Springer · Zbl 0984.00001
[37] Leroy, A., Noncommutative polynomial maps, J. Algebra Appl., 11, 04, Article 1250076 pp. (2012) · Zbl 1256.16017
[38] Liu, S.; Manganiello, F.; Kschischang, F. R., Construction and decoding of generalized skew-evaluation codes, (2015 IEEE 14th Canadian Workshop on Information Theory (CWIT) (2015), IEEE), 9-13
[39] Martínez-Peñas, U., On the roots and minimum rank distance of skew cyclic codes, Des. Codes Cryptogr., 83, 3, 639-660 (2017) · Zbl 1361.94065
[40] Neri, A.; Horlemann-Trautmann, A.-L., Random construction of partial MDS codes, Des. Codes Cryptogr., 88, 4, 711-725 (2020) · Zbl 1454.94128
[41] Ore, O., Theory of non-commutative polynomials, Ann. Math., 34, 3, 480-508 (1933) · Zbl 0007.15101
[42] Overbeck, R., Structural attacks for public key cryptosystems based on Gabidulin codes, J. Cryptol., 21, 2, 280-301 (2008) · Zbl 1159.94009
[43] Rawat, A. S.; Koyluoglu, O. O.; Silberstein, N.; Vishwanath, S., Optimal locally repairable and secure codes for distributed storage systems, IEEE Trans. Inf. Theory, 60, 1, 212-236 (2013)
[44] Roos, C., A generalization of the BCH bound for cyclic codes, including the Hartmann-Tzeng bound, J. Comb. Theory, Ser. A, 33, 2, 229-232 (1982) · Zbl 0497.94011
[45] Roos, C., A new lower bound for the minimum distance of a cyclic code, IEEE Trans. Inf. Theory, 29, 3, 330-332 (1983) · Zbl 0519.94010
[46] Roth, R. M., Maximum-rank array codes and their application to crisscross error correction, IEEE Trans. Inf. Theory, 37, 2, 328-336 (mar 1991)
[47] Roth, R. M., Tensor codes for the rank metric, IEEE Trans. Inf. Theory, 42, 6, 2146-2157 (1996) · Zbl 0874.94041
[48] Silva, D.; Kschischang, F. R., Universal secure network coding via rank-metric codes, IEEE Trans. Inf. Theory, 57, 2, 1124-1135 (2011) · Zbl 1366.94321
[49] Silva, D.; Kschischang, F. R.; Koetter, R., A rank-metric approach to error control in random network coding, IEEE Trans. Inf. Theory, 54, 9, 3951-3967 (2008) · Zbl 1318.94119
[50] Singleton, R., Maximum distance q-nary codes, IEEE Trans. Inf. Theory, 10, 2, 116-118 (1964) · Zbl 0124.11505
[51] Stein, W., Sage mathematics software (Version 8.9) (2019), The Sage Development Team
[52] van der Waerden, B. L., Modern Algebra, vol. I (1949), Frederick Ungar Publishing Co. · Zbl 0039.00902
[53] Van Lint, J. H.; Wilson, R. M., On the minimum distance of cyclic codes, IEEE Trans. Inf. Theory, 32, 1, 23-40 (January 1986)
[54] Vosper, A. G., The critical pairs of subsets of a group of prime order, J. Lond. Math. Soc., 1, 2, 200-205 (1956) · Zbl 0072.03402
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.