Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Designs, Codes and Cryptography
Published in: Designs, Codes and Cryptography 10/2019

12-02-2019

Theory of supports for linear codes endowed with the sum-rank metric

Author: Umberto Martínez-Peñas

Published in: Designs, Codes and Cryptography | Issue 10/2019

Login to get access

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The sum-rank metric naturally extends both the Hamming and rank metrics in coding theory over fields. It measures the error-correcting capability of codes in multishot matrix-multiplicative channels (e.g. linear network coding or the discrete memoryless channel on fields). Although this metric has already shown to be of interest in several applications, not much is known about it. In this work, sum-rank supports for codewords and linear codes are introduced and studied, with emphasis on duality. The lattice structure of sum-rank supports is given; characterizations of the ambient spaces (support spaces) they define are obtained; the classical operations of restriction and shortening are extended to the sum-rank metric; and estimates (bounds and equalities) on the parameters of such restricted and shortened codes are found. Three main applications are given: (1) Generalized sum-rank weights are introduced, together with their basic properties and bounds; (2) It is shown that duals, shortened and restricted codes of maximum sum-rank distance (MSRD) codes are in turn MSRD; (3) Degenerateness and effective lengths of sum-rank codes are introduced and characterized. In an Appendix, skew supports are introduced, defined by skew polynomials, and their connection to sum-rank supports is given.
previous article On the uniqueness of a type of cascade connection representations for NFSRs
next article Hadamard matrices, d-linearly independent sets and correlation-immune Boolean functions with minimum Hamming weights
Appendix
Available only for authorised users
Literature
1.
2.
Berger T.P.: Isometries for rank distance and permutation group of Gabidulin codes. IEEE Trans. Inf. Theory 49(11), 3016–3019 (2003).MathSciNetMATHCrossRef
3.
Blaum M., Hafner J.L., Hetzler S.: Partial-MDS codes and their application to RAID type of architectures. IEEE Trans. Inf. Theory 59(7), 4510–4519 (2013).MathSciNetMATHCrossRef
4.
Boucher D., Ulmer F.: Linear codes using skew polynomials with automorphisms and derivations. Des. Codes Cryptogr. 70(3), 405–431 (2014).MathSciNetMATHCrossRef
5.
Byrne E., Ravagnani A.: Covering radius of matrix codes endowed with the rank metric. SIAM J. Discret. Math. 31(2), 927–944 (2017).MathSciNetMATHCrossRef
6.
Chen, H., Cramer, R., Goldwasser, S., de Haan, R., Vaikuntanathan, V.: Secure computation from random error correcting codes. In: Advances in cryptology—EUROCRYPT 2007, volume 4515 of Lecture Notes in Computer Science, pp. 291–310 (2007)
7.
Couvreur A., Márquez-Corbella I., Pellikaan R.: Cryptanalysis of McEliece cryptosystem based on algebraic geometry codes and their subcodes. IEEE Trans. Inf. Theory 63(8), 5404–5418 (2017).MathSciNetMATHCrossRef
8.
9.
De la Cruz J., Gorla E., López H.H., Ravagnani A.: Weight distribution of rank-metric codes. Des. Codes Cryptogr. 86(1), 1–16 (2018).MathSciNetMATHCrossRef
10.
Delsarte P.: Bilinear forms over a finite field, with applications to coding theory. J. Comb. Theory Ser. A 25(3), 226–241 (1978).MathSciNetMATHCrossRef
11.
Dodunekova R., Dodunekov S.M., Kløve T.: Almost-MDS and near-MDS codes for error detection. IEEE Trans. Inf. Theory 43(1), 285–290 (1997).MathSciNetMATHCrossRef
12.
Ducoat, J.: Generalized rank weights: a duality statement. In: Topics in Finite Fields, volume 632 of Comtemporary Mathematics, pp. 114–123 (2015)
13.
Feng G.-L., Rao T.R.N.: A simple approach for construction of algebraic-geometric codes from affine plane curves. IEEE Trans. Inf. Theory 40(4), 1003–1012 (1994).MathSciNetMATHCrossRef
14.
Forney Jr. G.D.: Dimension/length profiles and trellis complexity of linear block codes. IEEE Trans. Inf. Theory 40(6), 1741–1752 (1994).MathSciNetMATHCrossRef
15.
Freij-Hollanti R., Gnilke O.W., Hollanti C., Karpuk D.A.: Private information retrieval from coded databases with colluding servers. SIAM J. Appl. Algebra Geom. 1(1), 647–664 (2017).MathSciNetMATHCrossRef
16.
Gabidulin E.M.: Theory of codes with maximum rank distance. Probl. Inf. Trans. 21(1), 1–12 (1985).MathSciNetMATH
17.
El Gamal H., Hammons A.R.: On the design of algebraic space-time codes for MIMO block-fading channels. IEEE Trans. Inf. Theory 49(1), 151–163 (2003).MathSciNetMATHCrossRef
18.
Gopalan P., Huang C., Jenkins B., Yekhanin S.: Explicit maximally recoverable codes with locality. IEEE Trans. Inf. Theory 60(9), 5245–5256 (2014).MathSciNetMATHCrossRef
19.
Greferath M., Honold T., Mc Fadden C., Wood J.A., Zumbrägel J.: Macwilliams’ extension theorem for bi-invariant weights over finite principal ideal rings. J. Comb. Theory Ser. A 125, 177–193 (2014).MathSciNetMATHCrossRef
20.
21.
Helleseth T., Kløve T., Levenshtein V.I., Ytrehus Ø.: Bounds on the minimum support weights. IEEE Trans. Inf. Theory 41(2), 432–440 (1995).MathSciNetMATHCrossRef
22.
Helleseth T., Kløve T., Mykkeltveit J.: The weight distribution of irreducible cyclic codes with block lengths \(n_l((q^l-1)/{N})\). Discret. Math. 18(2), 179–211 (1977).MATHCrossRef
23.
Horlemann-Trautmann A.-L., Marshall K.: New criteria for MRD and Gabidulin codes and some rank-metric code constructions. Adv. Math. Commun. 11(3), 533 (2017).MathSciNetMATHCrossRef
24.
25.
Jurrius R., Pellikaan R.: Defining the q-analogue of a matroid. Electron. J. Comb. 25, 321–330 (2018).MathSciNetMATH
26.
Kötter, R.: A unified description of an error locating procedure for linear codes. In: Proceeding of the Algebraic and Combinatorial Coding Theory, pp. 113–117 (1992)
27.
Kötter R., Kschischang F.R.: Coding for errors and erasures in random network coding. IEEE Trans. Inf. Theory 54(8), 3579–3591 (2008).MathSciNetMATHCrossRef
28.
Kurihara J., Matsumoto R., Uyematsu T.: Relative generalized rank weight of linear codes and its applications to network coding. IEEE Trans. Inf. Theory 61(7), 3912–3936 (2015).MathSciNetMATHCrossRef
29.
30.
31.
Lu H.-F., Kumar P.V.: A unified construction of space-time codes with optimal rate-diversity tradeoff. IEEE Trans. Inf. Theory 51(5), 1709–1730 (2005).MathSciNetMATHCrossRef
32.
Luo Y., Mitrpant C., Han Vinck A.J., Chen K.: Some new characters on the wire-tap channel of type II. IEEE Trans. Inf. Theory 51(3), 1222–1229 (2005).MathSciNetMATHCrossRef
33.
MacWilliams, F.J.: Combinatorial problems of elementary abelian groups. PhD thesis, Harvard (1962)
34.
Mahmood R., Badr A., Khisti A.: Convolutional codes with maximum column sum rank for network streaming. IEEE Trans. Inf. Theory 62(6), 3039–3052 (2016).MathSciNetMATHCrossRef
35.
Martínez-Peñas U.: On the similarities between generalized rank and Hamming weights and their applications to network coding. IEEE Trans. Inf. Theory 62(7), 4081–4095 (2016).MathSciNetMATHCrossRef
36.
Martínez-Peñas, U.: Linearized multivariate skew polynomials and Hilbert 90 theorems with multivariate norms, In: Proceeding of the XVI EACA, Zaragoza-Encuentros de Álgebra Computacional y Aplicaciones, pp. 119–122 (2018)
37.
Martínez-Peñas U.: Skew and linearized Reed–Solomon codes and maximum sum rank distance codes over any division ring. J. Algebra 504, 587–612 (2018).MathSciNetMATHCrossRef
38.
Martínez-Peñas, U.: Private information retrieval from locally repairable databases with colluding servers. (2019). Preprint: arXiv:​1901.​02938.
39.
Martínez-Peñas, U., Kschischang, F.R.: Reliable and secure multishot network coding using linearized Reed–Solomon codes. In: Proceeding of the 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton), (2018). Extended version: arXiv:​1805.​03789
40.
Martínez-Peñas, U., Kschischang, F.R.: Universal and dynamic locally repairable codes with maximal recoverability via sum-rank codes. In: Proceeding of the 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton), (2018). Extended version: arXiv:​1809.​11158.
41.
Martínez-Peñas, U., Kschischang, F.R.: Evaluation and interpolation over multivariate skew polynomial rings. J. Algebra, pp. 1–28, (2019). In press. Available: arXiv:​1710.​09606
42.
43.
Martínez-Peñas U., Matsumoto R.: Relative generalized matrix weights of matrix codes for universal security on wire-tap networks. IEEE Trans. Inf. Theory 64(4), 2529–2549 (2018).MathSciNetMATHCrossRef
44.
Napp, D., Pinto, R., Rosenthal, J., Vettori, P.: MRD rank metric convolutional codes. In: Proceeding of the 2017 IEEE International Symposium on Information Theory, pp. 2766–2770 (2017)
45.
Napp D., Pinto R., Sidorenko V.: Concatenation of convolutional codes and rank metric codes for multi-shot network coding. Des. Codes Cryptogr. 86(2), 303–318 (2018).MathSciNetMATHCrossRef
46.
Nóbrega, R.W., Uchôa-Filho, B.F.: Multishot codes for network coding: bounds and a multilevel construction. In: Proceeding of the 2009 IEEE International Symposium on Information Theory, pp. 428–432 (2009)
47.
Nóbrega, R.W., Uchôa-Filho, B.F.: Multishot codes for network coding using rank-metric codes. In: Proceeding of the 2010 Third IEEE International Workshop on Wireless Network Coding, pp. 1–6 (2010)
48.
Oggier, F.E., Sboui, A.: On the existence of generalized rank weights. In: Proceeding of the 2012 International Symposium on Information Theory and its Applications, pp. 406–410 (2012)
49.
50.
51.
Ozarow, L.H., Wyner, A.D.: Wire-tap channel II. In: advances in cryptology: EUROCRYPT 84, volume 209 of Lecture Notes in Computer Science, pp. 33–50 (1985)
52.
53.
54.
Roth R.M.: Maximum-rank array codes and their application to crisscross error correction. IEEE Trans. Inf. Theory 37(2), 328–336 (1991).MathSciNetMATHCrossRef
55.
Silva D., Kschischang F.R.: Universal secure network coding via rank-metric codes. IEEE Trans. Inf. Theory 57(2), 1124–1135 (2011).MathSciNetMATHCrossRef
56.
57.
58.
Wachter A., Sidorenko V.R., Bossert M., Zyablov V.V.: On (partial) unit memory codes based on Gabidulin codes. Probl. Inf. Trans. 47(2), 117–129 (2011).MathSciNetMATHCrossRef
59.
Wachter-Zeh A., Stinner M., Sidorenko V.: Convolutional codes in rank metric with application to random network coding. IEEE Trans. Inf. Theory 61(6), 3199–3213 (2015).MathSciNetMATHCrossRef
60.
Metadata
Title
Theory of supports for linear codes endowed with the sum-rank metric
Author
Umberto Martínez-Peñas
Publication date
12-02-2019
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 10/2019
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-019-00619-8

Other articles of this Issue 10/2019

Designs, Codes and Cryptography 10/2019 Go to the issue

OriginalPaper

Three-weight codes, triple sum sets, and strongly walk regular graphs

OriginalPaper

Linked systems of symmetric group divisible designs of type II

OriginalPaper

A note on good permutation codes from Reed–Solomon codes

OriginalPaper

On the weight distribution of second order Reed–Muller codes and their relatives

OriginalPaper

On the uniqueness of a type of cascade connection representations for NFSRs

OriginalPaper

Construction and enumeration for self-dual cyclic codes over of oddly even length

Premium Partner

    Image Credits