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

Metrics

  • PDF downloads (5)
  • HTML views (0)
  • Cited by (10)

[Back to Top]