Fast multi-sequence shift-register synthesis with the Euclidean algorithm

Previous Article
Explicit formulas for real hyperelliptic curves of genus 2 in affine representation
AMC Home
This Issue
Next Article
All binary linear codes of lengths up to 18 or redundancy up to 10 are normal

November 2011, 5(4): 667-680. doi: 10.3934/amc.2011.5.667

Fast multi-sequence shift-register synthesis with the Euclidean algorithm

Alexander Zeh ^1, and Antonia Wachter ^2,

1.	Institute of Communications Engineering, Ulm University, Albert-Einstein-Allee 43, 89083 Ulm, Germany, and Research Center INRIA Saclay - Île-de-France, École Polytechnique, 91128 Palaiseau Cedex, France
2.	Institute of Communications Engineering, Ulm University, Albert-Einstein-Allee 43, 89083 Ulm, Germany, and Institut de Recherche Mathémathique de Rennes (IRMAR), Université de Rennes 1, 35042 Rennes Cedex, France

Received November 2010 Revised June 2011 Published November 2011

Abstract
Related Papers

Feng and Tzeng's generalization of the Extended Euclidean Algorithm synthesizes the shortest-length linear feedback shift-register for $s \geq 1$ sequences, where each sequence has the same length $n$. In this contribution, it is shown that Feng and Tzeng's algorithm which solves this multi-sequence shift-register problem has time complexity $\mathcal{O}(sn^2)$. An acceleration based on the Divide and Conquer strategy is proposed and it is proven that subquadratic time complexity is achieved.

Keywords: interleaved Reed-Solomon codes, Divide and conquer, (multi-sequence) shift-register synthesis., (extended) Euclidean algorithm, fast algorithms.

Mathematics Subject Classification: Primary: 94A55, 94B15; Secondary: 94B3.

Citation: Alexander Zeh, Antonia Wachter. Fast multi-sequence shift-register synthesis with the Euclidean algorithm. Advances in Mathematics of Communications, 2011, 5 (4) : 667-680. doi: 10.3934/amc.2011.5.667

References:

[1]	A. V. Aho and J. E. Hopcroft, "The Design and Analysis of Computer Algorithms,'', Addison-Wesley Longman Publishing Co., (1974).
[2]	R. E. Blahut, "Fast Algorithms for Digital Signal Processing,'', Addison-Wesley, (1985).
[3]	D. Bleichenbacher, A. Kiayias and M. Yung, Decoding interleaved Reed-Solomon codes over noisy channels,, Theor. Comput. Sci., 379 (2007), 348. doi: 10.1016/j.tcs.2007.02.043.
[4]	G. L. Feng and K. K. Tzeng, A generalized Euclidean algorithm for multisequence shift-register synthesis,, IEEE Trans. Inform. Theory, 35 (1989), 584. doi: 10.1109/18.30981.
[5]	G. L. Feng and K. K. Tzeng, A generalization of the Berlekamp-Massey algorithm for multisequence shift-register synthesis with applications to decoding cyclic codes,, IEEE Trans. Inform. Theory, 37 (1991), 1274. doi: 10.1109/18.133246.
[6]	J. Gathen and J. Gerhard, "Modern Computer Algebra'',, Cambridge University Press, (2003).
[7]	C. Hartmann, Decoding beyond the BCH bound,, IEEE Trans. Inform. Theory, 18 (1972), 441. doi: 10.1109/TIT.1972.1054824.
[8]	V. Y. Krachkovsky, Reed-Solomon codes for correcting phased error bursts,, IEEE Trans. Inform. Theory, 49 (2003), 2975. doi: 10.1109/TIT.2003.819333.
[9]	V. Y. Krachkovsky and Y. X. Lee, Decoding for iterative Reed-Solomon coding schemes,, IEEE Trans. Magnetics, 33 (1997), 2740. doi: 10.1109/20.617715.
[10]	J. D. Lipson, "Elements of Algebra and Algebraic Computing,'', Addison-Wesley Educational Publishers Inc, (1981).
[11]	C. Roos, A generalization of the BCH bound for cyclic codes, including the Hartmann-Tzeng bound,, J. Combin. Theory Ser. A, 33 (1982), 229. doi: 10.1016/0097-3165(82)90014-0.
[12]	G. Schmidt, V. R. Sidorenko and M. Bossert, Syndrome decoding of Reed-Solomon codes beyond half the minimum distance based on shift-register synthesis,, IEEE Trans. Inform. Theory, 56 (2010), 5245. doi: 10.1109/TIT.2010.2060130.
[13]	Y. Sugiyama, M. Kasahara, S. Hirasawa and T. Namekawa, A method for solving key equation for decoding Goppa codes,, Inform. Control, 27 (1975), 87. doi: 10.1016/S0019-9958(75)90090-X.
[14]	L. Wang, Euclidean modules and multisequence synthesis,, in, (2001), 239.
[15]	A. Zeh and W. Li, Decoding Reed-Solomon codes up to the Sudan radius with the Euclidean algorithm,, in, (2010), 986. doi: 10.1109/ISITA.2010.5649520.

show all references

References:

[1]	A. V. Aho and J. E. Hopcroft, "The Design and Analysis of Computer Algorithms,'', Addison-Wesley Longman Publishing Co., (1974).
[2]	R. E. Blahut, "Fast Algorithms for Digital Signal Processing,'', Addison-Wesley, (1985).
[3]	D. Bleichenbacher, A. Kiayias and M. Yung, Decoding interleaved Reed-Solomon codes over noisy channels,, Theor. Comput. Sci., 379 (2007), 348. doi: 10.1016/j.tcs.2007.02.043.
[4]	G. L. Feng and K. K. Tzeng, A generalized Euclidean algorithm for multisequence shift-register synthesis,, IEEE Trans. Inform. Theory, 35 (1989), 584. doi: 10.1109/18.30981.
[5]	G. L. Feng and K. K. Tzeng, A generalization of the Berlekamp-Massey algorithm for multisequence shift-register synthesis with applications to decoding cyclic codes,, IEEE Trans. Inform. Theory, 37 (1991), 1274. doi: 10.1109/18.133246.
[6]	J. Gathen and J. Gerhard, "Modern Computer Algebra'',, Cambridge University Press, (2003).
[7]	C. Hartmann, Decoding beyond the BCH bound,, IEEE Trans. Inform. Theory, 18 (1972), 441. doi: 10.1109/TIT.1972.1054824.
[8]	V. Y. Krachkovsky, Reed-Solomon codes for correcting phased error bursts,, IEEE Trans. Inform. Theory, 49 (2003), 2975. doi: 10.1109/TIT.2003.819333.
[9]	V. Y. Krachkovsky and Y. X. Lee, Decoding for iterative Reed-Solomon coding schemes,, IEEE Trans. Magnetics, 33 (1997), 2740. doi: 10.1109/20.617715.
[10]	J. D. Lipson, "Elements of Algebra and Algebraic Computing,'', Addison-Wesley Educational Publishers Inc, (1981).
[11]	C. Roos, A generalization of the BCH bound for cyclic codes, including the Hartmann-Tzeng bound,, J. Combin. Theory Ser. A, 33 (1982), 229. doi: 10.1016/0097-3165(82)90014-0.
[12]	G. Schmidt, V. R. Sidorenko and M. Bossert, Syndrome decoding of Reed-Solomon codes beyond half the minimum distance based on shift-register synthesis,, IEEE Trans. Inform. Theory, 56 (2010), 5245. doi: 10.1109/TIT.2010.2060130.
[13]	Y. Sugiyama, M. Kasahara, S. Hirasawa and T. Namekawa, A method for solving key equation for decoding Goppa codes,, Inform. Control, 27 (1975), 87. doi: 10.1016/S0019-9958(75)90090-X.
[14]	L. Wang, Euclidean modules and multisequence synthesis,, in, (2001), 239.
[15]	A. Zeh and W. Li, Decoding Reed-Solomon codes up to the Sudan radius with the Euclidean algorithm,, in, (2010), 986. doi: 10.1109/ISITA.2010.5649520.

[1]	Yujuan Li, Guizhen Zhu. On the error distance of extended Reed-Solomon codes. Advances in Mathematics of Communications, 2016, 10 (2) : 413-427. doi: 10.3934/amc.2016015
[2]	Peter Beelen, David Glynn, Tom Høholdt, Krishna Kaipa. Counting generalized Reed-Solomon codes. Advances in Mathematics of Communications, 2017, 11 (4) : 777-790. doi: 10.3934/amc.2017057
[3]	Antonio Cafure, Guillermo Matera, Melina Privitelli. Singularities of symmetric hypersurfaces and Reed-Solomon codes. Advances in Mathematics of Communications, 2012, 6 (1) : 69-94. doi: 10.3934/amc.2012.6.69
[4]	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
[5]	José Moreira, Marcel Fernández, Miguel Soriano. On the relationship between the traceability properties of Reed-Solomon codes. Advances in Mathematics of Communications, 2012, 6 (4) : 467-478. doi: 10.3934/amc.2012.6.467
[6]	Weihua Liu, Andrew Klapper. AFSRs synthesis with the extended Euclidean rational approximation algorithm. Advances in Mathematics of Communications, 2017, 11 (1) : 139-150. doi: 10.3934/amc.2017008
[7]	Jaedal Jung, Ertugrul Taciroglu. A divide-alternate-and-conquer approach for localization and shape identification of multiple scatterers in heterogeneous media using dynamic XFEM. Inverse Problems & Imaging, 2016, 10 (1) : 165-193. doi: 10.3934/ipi.2016.10.165
[8]	Michael Baake, John A. G. Roberts, Reem Yassawi. Reversing and extended symmetries of shift spaces. Discrete & Continuous Dynamical Systems - A, 2018, 38 (2) : 835-866. doi: 10.3934/dcds.2018036
[9]	Wenjun Xia, Jinzhi Lei. Formulation of the protein synthesis rate with sequence information. Mathematical Biosciences & Engineering, 2018, 15 (2) : 507-522. doi: 10.3934/mbe.2018023
[10]	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
[11]	Gabriella Bretti, Roberto Natalini, Benedetto Piccoli. Fast algorithms for the approximation of a traffic flow model on networks. Discrete & Continuous Dynamical Systems - B, 2006, 6 (3) : 427-448. doi: 10.3934/dcdsb.2006.6.427
[12]	Petr Lisoněk, Layla Trummer. Algorithms for the minimum weight of linear codes. Advances in Mathematics of Communications, 2016, 10 (1) : 195-207. doi: 10.3934/amc.2016.10.195
[13]	Martino Borello, Olivier Mila. Symmetries of weight enumerators and applications to Reed-Muller codes. Advances in Mathematics of Communications, 2019, 13 (2) : 313-328. doi: 10.3934/amc.2019021
[14]	B. K. Dass, Namita Sharma, Rashmi Verma. Characterization of extended Hamming and Golay codes as perfect codes in poset block spaces. Advances in Mathematics of Communications, 2018, 12 (4) : 629-639. doi: 10.3934/amc.2018037
[15]	Leonid Kunyansky. Fast reconstruction algorithms for the thermoacoustic tomography in certain domains with cylindrical or spherical symmetries. Inverse Problems & Imaging, 2012, 6 (1) : 111-131. doi: 10.3934/ipi.2012.6.111
[16]	Gemma Huguet, Rafael de la Llave, Yannick Sire. Computation of whiskered invariant tori and their associated manifolds: New fast algorithms. Discrete & Continuous Dynamical Systems - A, 2012, 32 (4) : 1309-1353. doi: 10.3934/dcds.2012.32.1309
[17]	Yuying Shi, Ying Gu, Li-Lian Wang, Xue-Cheng Tai. A fast edge detection algorithm using binary labels. Inverse Problems & Imaging, 2015, 9 (2) : 551-578. doi: 10.3934/ipi.2015.9.551
[18]	Daniele Bartoli, Adnen Sboui, Leo Storme. Bounds on the number of rational points of algebraic hypersurfaces over finite fields, with applications to projective Reed-Muller codes. Advances in Mathematics of Communications, 2016, 10 (2) : 355-365. doi: 10.3934/amc.2016010
[19]	Olav Geil, Stefano Martin. Relative generalized Hamming weights of q-ary Reed-Muller codes. Advances in Mathematics of Communications, 2017, 11 (3) : 503-531. doi: 10.3934/amc.2017041
[20]	Andreas Klein, Leo Storme. On the non-minimality of the largest weight codewords in the binary Reed-Muller codes. Advances in Mathematics of Communications, 2011, 5 (2) : 333-337. doi: 10.3934/amc.2011.5.333

2017 Impact Factor: 0.564

American Institute of Mathematical Sciences