# American Institute of Mathematical Sciences

November  2012, 6(4): 443-466. doi: 10.3934/amc.2012.6.443

## An algebraic approach for decoding spread codes

 1 Institut de Mathématiques, Université de Neuchâtel, Rue Emile-Argand 11, 2000 Neuchâtel, Switzerland 2 Department of Electrical and Computer Engineering, University of Toronto, Toronto, Ontario, M5S 3G4, Canada 3 Institut für Mathematik, Universität Zürich, 8057 Zürich, Switzerland

Received  September 2011 Revised  June 2012 Published  November 2012

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.
Citation: Elisa Gorla, Felice Manganiello, Joachim Rosenthal. An algebraic approach for decoding spread codes. Advances in Mathematics of Communications, 2012, 6 (4) : 443-466. doi: 10.3934/amc.2012.6.443
##### References:
 [1] R. Ahlswede, N. Cai, S.-Y. R. Li and R. W. Yeung, Network information flow,, IEEE Trans. Inform. Theory, 46 (2000), 1204. doi: 10.1109/18.850663. Google Scholar [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. doi: 10.1109/TIT.2009.2021376. Google Scholar [3] T. Etzion and A. Vardy, Error-correcting codes in projective space,, in, (2008), 871. Google Scholar [4] È. M. Gabidulin, Theory of codes with maximum rank distance,, Problemy Peredachi Informatsii, 21 (1985), 3. Google Scholar [5] E. Gorla, C. Puttmann and J. Shokrollahi, Explicit formulas for efficient multiplication in $GF(3$6m$)$,, in, (2007), 173. Google Scholar [6] J. W. P. Hirschfeld, "Projective Geometries over Finite Fields,'' 2nd edition,, The Clarendon Press, (1998). Google Scholar [7] A. Kohnert and S. Kurz, Construction of large constant dimension codes with a prescribed minimum distance,, in, (2008), 31. Google Scholar [8] R. Kötter and F. R. Kschischang, Coding for errors and erasures in random network coding,, IEEE Trans. Inform. Theory, 54 (2008), 3579. doi: 10.1109/TIT.2008.926449. Google Scholar [9] S.-Y. R. Li, R. W. Yeung and N. Cai, Linear network coding,, IEEE Trans. Inform. Theory, 49 (2003), 371. doi: 10.1109/TIT.2002.807285. Google Scholar [10] R. Lidl and H. Niederreiter, "Introduction to Finite Fields and their Applications,'' revised edition,, Cambridge University Press, (1994). doi: 10.1017/CBO9781139172769. Google Scholar [11] P. Loidreau, A Welch-Berlekamp like algorithm for decoding Gabidulin codes,, in, (2006), 36. doi: 10.1007/11779360_4. Google Scholar [12] H. Mahdavifar and A. Vardy, Algebraic list-decoding on the operator channel,, in, (2010), 1193. doi: 10.1109/ISIT.2010.5513656. Google Scholar [13] F. Manganiello, E. Gorla and J. Rosenthal, Spread codes and spread decoding in network coding,, in, (2008), 851. doi: 10.1109/ISIT.2008.4595113. Google Scholar [14] G. Richter and S. Plass, Fast decoding of rank-codes with rank errors and column erasures,, in, (2004). Google Scholar [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. doi: 10.1109/TIT.2008.928291. Google Scholar [16] V. Skachek, Recursive code construction for random networks,, IEEE Trans. Inform. Theory, 56 (2010), 1378. doi: 10.1109/TIT.2009.2039163. Google Scholar [17] A.-L. Trautmann, F. Manganiello and J. Rosenthal, Orbit codes - a new concept in the area of network coding,, in, (2010), 1. doi: 10.1109/CIG.2010.5592788. Google Scholar [18] A.-L. Trautmann and J. Rosenthal, A complete characterization of irreducible cyclic orbit codes,, in, (2011), 219. Google Scholar

show all references

##### References:
 [1] R. Ahlswede, N. Cai, S.-Y. R. Li and R. W. Yeung, Network information flow,, IEEE Trans. Inform. Theory, 46 (2000), 1204. doi: 10.1109/18.850663. Google Scholar [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. doi: 10.1109/TIT.2009.2021376. Google Scholar [3] T. Etzion and A. Vardy, Error-correcting codes in projective space,, in, (2008), 871. Google Scholar [4] È. M. Gabidulin, Theory of codes with maximum rank distance,, Problemy Peredachi Informatsii, 21 (1985), 3. Google Scholar [5] E. Gorla, C. Puttmann and J. Shokrollahi, Explicit formulas for efficient multiplication in $GF(3$6m$)$,, in, (2007), 173. Google Scholar [6] J. W. P. Hirschfeld, "Projective Geometries over Finite Fields,'' 2nd edition,, The Clarendon Press, (1998). Google Scholar [7] A. Kohnert and S. Kurz, Construction of large constant dimension codes with a prescribed minimum distance,, in, (2008), 31. Google Scholar [8] R. Kötter and F. R. Kschischang, Coding for errors and erasures in random network coding,, IEEE Trans. Inform. Theory, 54 (2008), 3579. doi: 10.1109/TIT.2008.926449. Google Scholar [9] S.-Y. R. Li, R. W. Yeung and N. Cai, Linear network coding,, IEEE Trans. Inform. Theory, 49 (2003), 371. doi: 10.1109/TIT.2002.807285. Google Scholar [10] R. Lidl and H. Niederreiter, "Introduction to Finite Fields and their Applications,'' revised edition,, Cambridge University Press, (1994). doi: 10.1017/CBO9781139172769. Google Scholar [11] P. Loidreau, A Welch-Berlekamp like algorithm for decoding Gabidulin codes,, in, (2006), 36. doi: 10.1007/11779360_4. Google Scholar [12] H. Mahdavifar and A. Vardy, Algebraic list-decoding on the operator channel,, in, (2010), 1193. doi: 10.1109/ISIT.2010.5513656. Google Scholar [13] F. Manganiello, E. Gorla and J. Rosenthal, Spread codes and spread decoding in network coding,, in, (2008), 851. doi: 10.1109/ISIT.2008.4595113. Google Scholar [14] G. Richter and S. Plass, Fast decoding of rank-codes with rank errors and column erasures,, in, (2004). Google Scholar [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. doi: 10.1109/TIT.2008.928291. Google Scholar [16] V. Skachek, Recursive code construction for random networks,, IEEE Trans. Inform. Theory, 56 (2010), 1378. doi: 10.1109/TIT.2009.2039163. Google Scholar [17] A.-L. Trautmann, F. Manganiello and J. Rosenthal, Orbit codes - a new concept in the area of network coding,, in, (2010), 1. doi: 10.1109/CIG.2010.5592788. Google Scholar [18] A.-L. Trautmann and J. Rosenthal, A complete characterization of irreducible cyclic orbit codes,, in, (2011), 219. Google Scholar
 [1] Giuseppe Bianchi, Lorenzo Bracciale, Keren Censor-Hillel, Andrea Lincoln, Muriel Médard. The one-out-of-k retrieval problem and linear network coding. Advances in Mathematics of Communications, 2016, 10 (1) : 95-112. doi: 10.3934/amc.2016.10.95 [2] Irene I. Bouw, Sabine Kampf. Syndrome decoding for Hermite codes with a Sugiyama-type algorithm. Advances in Mathematics of Communications, 2012, 6 (4) : 419-442. doi: 10.3934/amc.2012.6.419 [3] Kwankyu Lee. Decoding of differential AG codes. Advances in Mathematics of Communications, 2016, 10 (2) : 307-319. doi: 10.3934/amc.2016007 [4] Washiela Fish, Jennifer D. Key, Eric Mwambene. Partial permutation decoding for simplex codes. Advances in Mathematics of Communications, 2012, 6 (4) : 505-516. doi: 10.3934/amc.2012.6.505 [5] Alexander Barg, Arya Mazumdar, Gilles Zémor. Weight distribution and decoding of codes on hypergraphs. Advances in Mathematics of Communications, 2008, 2 (4) : 433-450. doi: 10.3934/amc.2008.2.433 [6] Artyom Nahapetyan, Panos M. Pardalos. A bilinear relaxation based algorithm for concave piecewise linear network flow problems. Journal of Industrial & Management Optimization, 2007, 3 (1) : 71-85. doi: 10.3934/jimo.2007.3.71 [7] Keisuke Minami, Takahiro Matsuda, Tetsuya Takine, Taku Noguchi. Asynchronous multiple source network coding for wireless broadcasting. Numerical Algebra, Control & Optimization, 2011, 1 (4) : 577-592. doi: 10.3934/naco.2011.1.577 [8] Min Ye, Alexander Barg. Polar codes for distributed hierarchical source coding. Advances in Mathematics of Communications, 2015, 9 (1) : 87-103. doi: 10.3934/amc.2015.9.87 [9] Terasan Niyomsataya, Ali Miri, Monica Nevins. Decoding affine reflection group codes with trellises. Advances in Mathematics of Communications, 2012, 6 (4) : 385-400. doi: 10.3934/amc.2012.6.385 [10] Heide Gluesing-Luerssen, Uwe Helmke, José Ignacio Iglesias Curto. Algebraic decoding for doubly cyclic convolutional codes. Advances in Mathematics of Communications, 2010, 4 (1) : 83-99. doi: 10.3934/amc.2010.4.83 [11] Michael Braun. On lattices, binary codes, and network codes. Advances in Mathematics of Communications, 2011, 5 (2) : 225-232. doi: 10.3934/amc.2011.5.225 [12] Stefan Martignoli, Ruedi Stoop. Phase-locking and Arnold coding in prototypical network topologies. Discrete & Continuous Dynamical Systems - B, 2008, 9 (1) : 145-162. doi: 10.3934/dcdsb.2008.9.145 [13] T. Jäger. Neuronal coding of pacemaker neurons -- A random dynamical systems approach. Communications on Pure & Applied Analysis, 2011, 10 (3) : 995-1009. doi: 10.3934/cpaa.2011.10.995 [14] Qian Guo, Thomas Johansson, Erik Mårtensson, Paul Stankovski Wagner. Some cryptanalytic and coding-theoretic applications of a soft stern algorithm. Advances in Mathematics of Communications, 2019, 13 (4) : 559-578. doi: 10.3934/amc.2019035 [15] Hannes Bartz, Antonia Wachter-Zeh. Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases. Advances in Mathematics of Communications, 2018, 12 (4) : 773-804. doi: 10.3934/amc.2018046 [16] Jiangtao Mo, Liqun Qi, Zengxin Wei. A network simplex algorithm for simple manufacturing network model. Journal of Industrial & Management Optimization, 2005, 1 (2) : 251-273. doi: 10.3934/jimo.2005.1.251 [17] Joan-Josep Climent, Diego Napp, Raquel Pinto, Rita Simões. Decoding of $2$D convolutional codes over an erasure channel. Advances in Mathematics of Communications, 2016, 10 (1) : 179-193. doi: 10.3934/amc.2016.10.179 [18] Johan Rosenkilde. Power decoding Reed-Solomon codes up to the Johnson radius. Advances in Mathematics of Communications, 2018, 12 (1) : 81-106. doi: 10.3934/amc.2018005 [19] Anas Chaaban, Vladimir Sidorenko, Christian Senger. On multi-trial Forney-Kovalev decoding of concatenated codes. Advances in Mathematics of Communications, 2014, 8 (1) : 1-20. doi: 10.3934/amc.2014.8.1 [20] Vladimir Sidorenko, Christian Senger, Martin Bossert, Victor Zyablov. Single-trial decoding of concatenated codes using fixed or adaptive erasing. Advances in Mathematics of Communications, 2010, 4 (1) : 49-60. doi: 10.3934/amc.2010.4.49

2018 Impact Factor: 0.879