American Institute of Mathematical Sciences

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

An algebraic approach for decoding spread codes

Elisa Gorla 1, , Felice Manganiello 2, and  Joachim Rosenthal 3,

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.
Keywords: spread codes, decoding algorithm., Random linear network coding.
Mathematics Subject Classification: 11T7.
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-1216. 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-2919. doi: 10.1109/TIT.2009.2021376.  Google Scholar

[3]

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

[4]

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

[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. Google Scholar

[6]

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

[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.  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-3591. 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-381. 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, Cambridge, 1994. doi: 10.1017/CBO9781139172769.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. 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-3967. doi: 10.1109/TIT.2008.928291.  Google Scholar

[16]

V. Skachek, Recursive code construction for random networks, IEEE Trans. Inform. Theory, 56 (2010), 1378-1382. 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 IEEE Information Theory Workshop (ITW),'' Dublin, Ireland, (2010), 1-4. doi: 10.1109/CIG.2010.5592788.  Google Scholar

[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. 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-1216. 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-2919. doi: 10.1109/TIT.2009.2021376.  Google Scholar

[3]

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

[4]

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

[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. Google Scholar

[6]

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

[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.  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-3591. 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-381. 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, Cambridge, 1994. doi: 10.1017/CBO9781139172769.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. 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-3967. doi: 10.1109/TIT.2008.928291.  Google Scholar

[16]

V. Skachek, Recursive code construction for random networks, IEEE Trans. Inform. Theory, 56 (2010), 1378-1382. 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 IEEE Information Theory Workshop (ITW),'' Dublin, Ireland, (2010), 1-4. doi: 10.1109/CIG.2010.5592788.  Google Scholar

[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. 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]

Julia Lieb, Raquel Pinto. A decoding algorithm for 2D convolutional codes over the erasure channel. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021031
[4]

Kwankyu Lee. Decoding of differential AG codes. Advances in Mathematics of Communications, 2016, 10 (2) : 307-319. doi: 10.3934/amc.2016007
[5]

Ghislain Fourier, Gabriele Nebe. Degenerate flag varieties in network coding. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021027
[6]

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
[7]

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
[8]

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
[9]

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
[10]

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
[11]

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
[12]

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
[13]

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
[14]

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
[15]

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
[16]

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
[17]

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
[18]

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
[19]

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
[20]

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

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (115)
  • HTML views (0)
  • Cited by (12)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences