An algebraic approach for decoding spread codes

Previous Article
On the relationship between the traceability properties of Reed-Solomon codes
AMC Home
This Issue
Next Article
Syndrome decoding for Hermite codes with a Sugiyama-type algorithm

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

Abstract
Related Papers

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.
[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,'' 2^nd 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.

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.
[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,'' 2^nd 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.

[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]	Keisuke Minami, Takahiro Matsuda, Tetsuya Takine, Taku Noguchi. Asynchronous multiple source network coding for wireless broadcasting. Numerical Algebra, Control and Optimization, 2011, 1 (4) : 577-592. doi: 10.3934/naco.2011.1.577
[9]	Artyom Nahapetyan, Panos M. Pardalos. A bilinear relaxation based algorithm for concave piecewise linear network flow problems. Journal of Industrial and Management Optimization, 2007, 3 (1) : 71-85. doi: 10.3934/jimo.2007.3.71
[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 and Continuous Dynamical Systems - B, 2008, 9 (1) : 145-162. doi: 10.3934/dcdsb.2008.9.145
[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]	T. Jäger. Neuronal coding of pacemaker neurons -- A random dynamical systems approach. Communications on Pure and Applied Analysis, 2011, 10 (3) : 995-1009. doi: 10.3934/cpaa.2011.10.995
[16]	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
[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]	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
[19]	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
[20]	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

2021 Impact Factor: 1.015

Tools

Metrics

Other articles
by authors

on AIMS
Elisa Gorla Felice Manganiello Joachim Rosenthal
on Google Scholar
Elisa Gorla Felice Manganiello Joachim Rosenthal

[Back to Top]