Article Contents
Article Contents

# An algebraic approach for decoding spread codes

• In this paper we study spread codes: a family of constant-dimension codes for random linear network coding. In other words, the codewords are full-rank matrices of size $k\times n$ with entries in a finite field $\mathbb F_q$. Spread codes are a family of optimal codes with maximal minimum distance. We give a minimum-distance decoding algorithm which requires $\mathcal{O}((n-k)k^3)$ operations over an extension field $\mathbb F_{q^k}$. Our algorithm is more efficient than the previous ones in the literature, when the dimension $k$ of the codewords is small with respect to $n$. The decoding algorithm takes advantage of the algebraic structure of the code, and it uses original results on minors of a matrix and on the factorization of polynomials over finite fields.
Mathematics Subject Classification: 11T71.

 Citation:

•  [1] R. Ahlswede, N. Cai, S.-Y. R. Li and R. W. Yeung, Network information flow, IEEE Trans. Inform. Theory, 46 (2000), 1204-1216.doi: 10.1109/18.850663. [2] T. Etzion and N. Silberstein, Error-correcting codes in projective spaces via rank-metric codes and Ferrers diagrams, IEEE Trans. Inform. Theory, 55 (2009), 2909-2919.doi: 10.1109/TIT.2009.2021376. [3] T. Etzion and A. Vardy, Error-correcting codes in projective space, in "IEEE International Symposium on Information Theory,'' (2008), 871-875. [4] È. M. Gabidulin, Theory of codes with maximum rank distance, Problemy Peredachi Informatsii, 21 (1985), 3-16. [5] E. Gorla, C. Puttmann and J. Shokrollahi, Explicit formulas for efficient multiplication in $GF(3$6m$)$, in "Selected Areas in Cryptography: Revised Selected Papers from the 14th International Workshop (SAC 2007) held at University of Ottawa'' (eds. C. Adams, A. Miri and M. Wiener), Springer, (2007), 173-183. [6] J. W. P. Hirschfeld, "Projective Geometries over Finite Fields,'' 2nd edition, The Clarendon Press, Oxford University Press, New York, 1998. [7] A. Kohnert and S. Kurz, Construction of large constant dimension codes with a prescribed minimum distance, in "MMICS'' (eds. J. Calmet, W. Geiselmann and J. Müller-Quade), Springer, (2008), 31-42. [8] R. Kötter and F. R. Kschischang, Coding for errors and erasures in random network coding, IEEE Trans. Inform. Theory, 54 (2008), 3579-3591.doi: 10.1109/TIT.2008.926449. [9] S.-Y. R. Li, R. W. Yeung and N. Cai, Linear network coding, IEEE Trans. Inform. Theory, 49 (2003), 371-381.doi: 10.1109/TIT.2002.807285. [10] R. Lidl and H. Niederreiter, "Introduction to Finite Fields and their Applications,'' revised edition, Cambridge University Press, Cambridge, 1994.doi: 10.1017/CBO9781139172769. [11] P. Loidreau, A Welch-Berlekamp like algorithm for decoding Gabidulin codes, in "Coding and Cryptography,'' Springer, Berlin, (2006), 36-45.doi: 10.1007/11779360_4. [12] H. Mahdavifar and A. Vardy, Algebraic list-decoding on the operator channel, in "Proceedings of 2010 IEEE International Symposium on Information Theory,'' (2010), 1193-1197.doi: 10.1109/ISIT.2010.5513656. [13] F. Manganiello, E. Gorla and J. Rosenthal, Spread codes and spread decoding in network coding, in "Proceedings of 2008 IEEE International Symposium on Information Theory,'' Toronto, Canada, (2008), 851-855.doi: 10.1109/ISIT.2008.4595113. [14] G. Richter and S. Plass, Fast decoding of rank-codes with rank errors and column erasures, in "Proceedings of 2008 IEEE International Symposium on Information Theory,'' (2004), page 398. [15] D. Silva, F. R. Kschischang and R. Kötter, A rank-metric approach to error control in random network coding, IEEE Trans. Inform. Theory, 54 (2008), 3951-3967.doi: 10.1109/TIT.2008.928291. [16] V. Skachek, Recursive code construction for random networks, IEEE Trans. Inform. Theory, 56 (2010), 1378-1382.doi: 10.1109/TIT.2009.2039163. [17] A.-L. Trautmann, F. Manganiello and J. Rosenthal, Orbit codes - a new concept in the area of network coding, in "2010 IEEE Information Theory Workshop (ITW),'' Dublin, Ireland, (2010), 1-4.doi: 10.1109/CIG.2010.5592788. [18] A.-L. Trautmann and J. Rosenthal, A complete characterization of irreducible cyclic orbit codes, in "Proceedings of the Seventh International Workshop on Coding and Cryptography (WCC),'' (2011), 219-223.