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

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

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-360. 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-594. 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-1287. 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-444. 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-2984. 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-2742. 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-232. 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-5252. 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-99. doi: 10.1016/S0019-9958(75)90090-X.
[14]	L. Wang, Euclidean modules and multisequence synthesis, in "Applied Algebra, Algebraic Algorithms and Error-Correcting Codes'' (eds. S. Boztaş and I.E. Shparlinski), Springer, Berlin, Heidelberg, (2001), 239-248.
[15]	A. Zeh and W. Li, Decoding Reed-Solomon codes up to the Sudan radius with the Euclidean algorithm, in "Proceedings of the 2010 International Symposium on Information Theory and its Applications (ISITA),'' Taichung, Taiwan, (2010), 986-990. 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-360. 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-594. 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-1287. 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-444. 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-2984. 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-2742. 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-232. 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-5252. 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-99. doi: 10.1016/S0019-9958(75)90090-X.
[14]	L. Wang, Euclidean modules and multisequence synthesis, in "Applied Algebra, Algebraic Algorithms and Error-Correcting Codes'' (eds. S. Boztaş and I.E. Shparlinski), Springer, Berlin, Heidelberg, (2001), 239-248.
[15]	A. Zeh and W. Li, Decoding Reed-Solomon codes up to the Sudan radius with the Euclidean algorithm, in "Proceedings of the 2010 International Symposium on Information Theory and its Applications (ISITA),'' Taichung, Taiwan, (2010), 986-990. 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]	Karan Khathuria, Joachim Rosenthal, Violetta Weger. Encryption scheme based on expanded Reed-Solomon codes. Advances in Mathematics of Communications, 2021, 15 (2) : 207-218. doi: 10.3934/amc.2020053
[5]	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
[6]	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
[7]	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
[8]	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 and Imaging, 2016, 10 (1) : 165-193. doi: 10.3934/ipi.2016.10.165
[9]	Michael Baake, John A. G. Roberts, Reem Yassawi. Reversing and extended symmetries of shift spaces. Discrete and Continuous Dynamical Systems, 2018, 38 (2) : 835-866. doi: 10.3934/dcds.2018036
[10]	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
[11]	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
[12]	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
[13]	Gabriella Bretti, Roberto Natalini, Benedetto Piccoli. Fast algorithms for the approximation of a traffic flow model on networks. Discrete and Continuous Dynamical Systems - B, 2006, 6 (3) : 427-448. doi: 10.3934/dcdsb.2006.6.427
[14]	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
[15]	Kin Ming Hui, Jinwan Park. Asymptotic behaviour of singular solution of the fast diffusion equation in the punctured euclidean space. Discrete and Continuous Dynamical Systems, 2021, 41 (11) : 5473-5508. doi: 10.3934/dcds.2021085
[16]	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
[17]	Lu Tan, Ling Li, Senjian An, Zhenkuan Pan. Nonlinear diffusion based image segmentation using two fast algorithms. Mathematical Foundations of Computing, 2019, 2 (2) : 149-168. doi: 10.3934/mfc.2019011
[18]	Leonid Kunyansky. Fast reconstruction algorithms for the thermoacoustic tomography in certain domains with cylindrical or spherical symmetries. Inverse Problems and Imaging, 2012, 6 (1) : 111-131. doi: 10.3934/ipi.2012.6.111
[19]	Ningyu Sha, Lei Shi, Ming Yan. Fast algorithms for robust principal component analysis with an upper bound on the rank. Inverse Problems and Imaging, 2021, 15 (1) : 109-128. doi: 10.3934/ipi.2020067
[20]	Gemma Huguet, Rafael de la Llave, Yannick Sire. Computation of whiskered invariant tori and their associated manifolds: New fast algorithms. Discrete and Continuous Dynamical Systems, 2012, 32 (4) : 1309-1353. doi: 10.3934/dcds.2012.32.1309

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Alexander Zeh Antonia Wachter
on Google Scholar
Alexander Zeh Antonia Wachter

[Back to Top]