×

zbMATH — the first resource for mathematics

Skew and linearized Reed-Solomon codes and maximum sum rank distance codes over any division ring. (English) Zbl 1417.94122
Summary: Reed-Solomon codes and Gabidulin codes have maximum Hamming distance and maximum rank distance, respectively. A general construction using skew polynomials, called skew Reed-Solomon codes, has already been introduced in the literature. In this work, we introduce a linearized version of such codes, called linearized Reed-Solomon codes. We prove that they have maximum sum-rank distance. Such distance is of interest in multishot network coding or in singleshot multi-network coding. To prove our result, we introduce new metrics defined by skew polynomials, which we call skew metrics, we prove that skew Reed-Solomon codes have maximum skew distance, and then we translate this scenario to linearized Reed-Solomon codes and the sum-rank metric. The theories of Reed-Solomon codes and Gabidulin codes are particular cases of our theory, and the sum-rank metric extends both the Hamming and rank metrics. We develop our theory over any division ring (commutative or non-commutative field). We also consider non-zero derivations, which give new maximum rank distance codes over infinite fields not considered before.

MSC:
94B60 Other types of codes
12E10 Special polynomials in general fields
16S36 Ordinary and skew polynomial rings and semigroup rings
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Augot, D., Generalization of gabidulin codes over fields of rational functions, (Proc. 21st International Symposium on Mathematical Theory of Networks and Systems, MTNS 2014, Groningen, Netherlands, (2014))
[2] Augot, D.; Loidreau, P.; Robert, G., Rank metric and gabidulin codes in characteristic zero, (Proc. 2013 IEEE International Symposium on Information Theory, (2013)), 509-513
[3] Augot, D.; Loidreau, P.; Robert, G., Generalized gabidulin codes over fields of any characteristic, (2017), Available:
[4] Boucher, D.; Ulmer, F., Linear codes using skew polynomials with automorphisms and derivations, Des. Codes Cryptogr., 70, 3, 405-431, (2014) · Zbl 1302.94065
[5] Cohn, P. M., Free rings and their relations, (1971), Academic Press London · Zbl 0232.16003
[6] Gabidulin, E. M., Theory of codes with maximum rank distance, Probl. Inf. Transm., 21, (1985) · Zbl 0585.94013
[7] Gómez-Torrecillas, J.; Lobillo, F. J.; Navarro, G., A new perspective of cyclicity in convolutional codes, IEEE Trans. Inform. Theory, 62, 5, 2702-2706, (2016) · Zbl 1359.94752
[8] Hammons, A. R.; El Gamal, H., On the theory of space-time codes for PSK modulation, IEEE Trans. Inform. Theory, 46, 2, 524-542, (2000) · Zbl 0999.94009
[9] Kshevetskiy, A.; Gabidulin, E. M., The new construction of rank codes, (Proc. 2005 IEEE International Symposium on Information Theory, (2005)), 2105-2108
[10] Lam, T. Y., A general theory of Vandermonde matrices, Expo. Math., 4, 193-215, (1986) · Zbl 0598.15015
[11] Lam, T. Y.; Leroy, A., Algebraic conjugacy classes and skew polynomial rings, (Perspectives in Ring Theory, (1988), Springer), 153-203 · Zbl 0694.16002
[12] Lam, T. Y.; Leroy, A., Vandermonde and Wronskian matrices over division rings, J. Algebra, 119, 2, 308-336, (1988) · Zbl 0657.15015
[13] Lam, T. Y.; Leroy, A., Hilbert 90 theorems over division rings, Trans. Amer. Math. Soc., 345, 2, 595-622, (1994) · Zbl 0820.16024
[14] Leroy, A., Pseudolinear transformations and evaluation in ore extensions, Bull. Belg. Math. Soc., 2, 3, 321-347, (1995) · Zbl 0840.16023
[15] Leroy, A., Noncommutative polynomial maps, J. Algebra Appl., 11, 4, (2012) · Zbl 1256.16017
[16] Lidl, R.; Niederreiter, H., Finite fields, Encyclopedia of Mathematics and Its Applications, vol. 20, (1983), Addison-Wesley Amsterdam
[17] Liu, S., Generalized skew Reed-Solomon codes and other applications of skew polynomial evaluation, (2016), University of Toronto, PhD thesis
[18] Liu, S.; Manganiello, F.; Kschischang, F. R., Construction and decoding of generalized skew-evaluation codes, (Proc. 2015 IEEE 14th Canadian Workshop on Information Theory, (2015)), 9-13
[19] Liu, S.; Manganiello, F.; Kschischang, F. R., Matroidal structure of skew polynomial rings with application to network coding, Finite Fields Appl., 46, C, 326-346, (2017) · Zbl 1369.11090
[20] Mahmood, R.; Badr, A.; Khisti, A., Convolutional codes with maximum column sum rank for network streaming, IEEE Trans. Inform. Theory, 62, 6, 3039-3052, (2016) · Zbl 1359.94754
[21] Martínez-Peñas, U., On the similarities between generalized rank and Hamming weights and their applications to network coding, IEEE Trans. Inform. Theory, 62, 7, 4081-4095, (2016) · Zbl 1359.94721
[22] Napp, D.; Pinto, R.; Rosenthal, J.; Vettori, P., MRD rank metric convolutional codes, (Proc. 2017 IEEE International Symposium on Information Theory, (2017)), 2766-2770
[23] Nobrega, R. W.; Uchoa-Filho, B. F., Multishot codes for network coding using rank-metric codes, (Proc. 2010 Third IEEE International Workshop on Wireless Network Coding, (2010)), 1-6
[24] Ore, O., Theory of non-commutative polynomials, Ann. of Math. (2), 34, 3, 480-508, (1933) · JFM 59.0925.01
[25] Reed, I. S.; Solomon, G., Polynomial codes over certain finite fields, J. Soc. Ind. Appl. Math., 8, 2, 300-304, (1960) · Zbl 0099.34403
[26] Silva, D.; Kschischang, F. R., On metrics for error correction in network coding, IEEE Trans. Inform. Theory, 55, 12, 5479-5490, (2009) · Zbl 1367.94467
[27] Silva, D.; Kschischang, F. R., Universal secure network coding via rank-metric codes, IEEE Trans. Inform. Theory, 57, 2, 1124-1135, (2011) · Zbl 1366.94321
[28] Wachter, A.; Sidorenko, V. R.; Bossert, M.; Zyablov, V. V., On (partial) unit memory codes based on gabidulin codes, Probl. Inf. Transm., 47, 2, 117-129, (2011) · Zbl 1248.94117
[29] Wachter-Zeh, A.; Stinner, M.; Sidorenko, V., Convolutional codes in rank metric with application to random network coding, IEEE Trans. Inform. Theory, 61, 6, 3199-3213, (2015) · Zbl 1359.94756
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.