Advanced Search
Article Contents
Article Contents

An algebraic approach for decoding spread codes

Abstract Related Papers Cited by
  • 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.


    \begin{equation} \\ \end{equation}
  • [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.


    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.


    T. Etzion and A. Vardy, Error-correcting codes in projective space, in "IEEE International Symposium on Information Theory,'' (2008), 871-875.


    È. M. Gabidulin, Theory of codes with maximum rank distance, Problemy Peredachi Informatsii, 21 (1985), 3-16.


    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.


    J. W. P. Hirschfeld, "Projective Geometries over Finite Fields,'' 2nd edition, The Clarendon Press, Oxford University Press, New York, 1998.


    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.


    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.


    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.


    R. Lidl and H. Niederreiter, "Introduction to Finite Fields and their Applications,'' revised edition, Cambridge University Press, Cambridge, 1994.doi: 10.1017/CBO9781139172769.


    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.


    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.


    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.


    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.


    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.


    V. Skachek, Recursive code construction for random networks, IEEE Trans. Inform. Theory, 56 (2010), 1378-1382.doi: 10.1109/TIT.2009.2039163.


    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.


    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.

  • 加载中

Article Metrics

HTML views() PDF downloads(147) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint