Abstract
Error-correcting pairs were introduced as a general method of decoding linear codes with respect to the Hamming metric using coordinatewise products of vectors, and are used for many well-known families of codes. In this paper, we define new types of vector products, extending the coordinatewise product, some of which preserve symbolic products of linearized polynomials after evaluation and some of which coincide with usual products of matrices. Then we define rank error-correcting pairs for codes that are linear over the extension field and for codes that are linear over the base field, and relate both types. Bounds on the minimum rank distance of codes and MRD conditions are given. Finally we show that some well-known families of rank-metric codes admit rank error-correcting pairs, and show that the given algorithm generalizes the classical algorithm using error-correcting pairs for the Hamming metric.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Berger T.P.: Isometries for rank distance and permutation group of Gabidulin codes. IEEE Trans. Inf. Theory 49(11), 3016–3019 (2003).
Boucher D., Geiselmann W., Ulmer F.: Skew-cyclic codes. Appl. Algebra Eng. Commun. Comput. 18(4), 379–389 (2007).
Chaussade L., Loidreau P., Ulmer F.: Skew codes of prescribed distance or rank. Des. Codes Cryptogr. 50(3), 267–284 (2009).
Delsarte P.: Bilinear forms over a finite field, with applications to coding theory. J. Comb. Theory Ser. A 25(3), 226–241 (1978).
Delsarte P.: On subfield subcodes of modified reed-solomon codes. IEEE Trans. Inf. Theory 21(5), 575–576 (2006).
Duursma I.M., Kötter R.: Error-locating pairs for cyclic codes. IEEE Trans. Inf. Theory 40(4), 1108–1121 (1994).
Duursma I.M., Pellikaan R.: A symmetric Roos bound for linear codes. J. Comb. Theory Ser. A 113(8), 1677–1688 (2006).
Gabidulin E.M.: Theory of codes with maximum rank distance. Prob. Inf. Transm. 21, 3–16 (1985).
Gabidulin E.M.: Rank q-cyclic and pseudo-q-cyclic codes. In: IEEE International Symposium on Information Theory (ISIT 2009), pp. 2799–2802 (2009).
Hartmann C.R.P., Tzeng K.K.: Generalizations of the BCH bound. Inf. Control 20(5), 489–498 (1972).
Jurrius R.P.M.J., Pellikaan R.: The extended and generalized rank weight enumerator. ACA 2014, Applications of Computer Algebra, 9 July 2014, Fordham University, New York, Computer Algebra in Coding Theory and Cryptography (2014).
Jurrius R.P.M.J., Pellikaan R.: On defining generalized rank weights. arXiv:1506.02865 (2015).
Kötter R.: A unified description of an error locating procedure for linear codes. In: Proceedings of Algebraic and Combinatorial Coding Theory, Voneshta Voda, pp. 113–117 (1992).
Kshevetskiy A., Gabidulin E.M.: The new construction of rank codes. In: IEEE International Symposium on Information Theory (ISIT 2005), pp. 2105–2108 (2005).
Lidl R., Niederreiter H.: Finite Fields. Encyclopedia of Mathematics and Its Applications, vol. 20. Addison-Wesley, Amsterdam (1983).
Loidreau P.: A Welch–Berlekamp like algorithm for decoding Gabidulin codes. In: Ytrehus Ø. (ed.) Coding and Cryptography. Lecture Notes in Computer Science, vol. 3969, pp. 36–45. Springer, Berlin (2006).
Martínez-Peñas U.: On the roots and minimum rank distance of skew cyclic codes. Des. Codes Cryptogr. (2016). doi:10.1007/s10623-016-0262-z.
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).
Pellikaan R.: On decoding linear codes by error correcting pairs. Preprint, Eindhoven University of Technology (1988).
Pellikaan R.: On decoding by error location and dependent sets of error positions. Discret. Math. 106, 369–381 (1992).
Pellikaan R.: On the existence of error-correcting pairs. J. Stat. Plan. Inference 51(2), 229–242 (1996). Shanghai Conference Issue on Designs, Codes, and Finite Geometries, Part I.
Ravagnani A.: Rank-metric codes and their duality theory. Des. Codes Cryptogr. 80(1), 197–216 (2015).
Roos C.: A generalization of the BCH bound for cyclic codes, including the Hartmann–Tzeng bound. J. Comb. Theory Ser. A 33, 229–232 (1982).
Roos C.: A new lower bound for the minimum distance of a cyclic code. IEEE Trans. Inf. Theory IT–29, 330–332 (1982).
Silva D., Kschischang F.R.: On metrics for error correction in network coding. IEEE Trans. Inf. Theory 55(12), 5479–5490 (2009).
Acknowledgments
Rank error-correcting pairs of type II have been obtained in the case \( m = n \) independently by Alain Couvreur (About error correcting pairs. Personal communication, September 15, 2015). The authors wish to thank him for this communication and for useful discussions and comments. The authors wish to thank the anonymous reviewers for their helpful comments and also gratefully acknowledge the support from The Danish Council for Independent Research (Grant No. DFF-4002-00367). This paper was started during the visit of the second author to Aalborg University, Denmark, which was supported by the previous grant.
Author information
Authors and Affiliations
Corresponding author
Additional information
This is one of several papers published in Designs, Codes and Cryptography comprising the special issue in honor of Andries Brouwer’s 65th birthday.
Rights and permissions
About this article
Cite this article
Martínez-Peñas, U., Pellikaan, R. Rank error-correcting pairs. Des. Codes Cryptogr. 84, 261–281 (2017). https://doi.org/10.1007/s10623-016-0284-6
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-016-0284-6