American Institute of Mathematical Sciences

Advanced
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

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

[2]

R. E. Blahut, "Fast Algorithms for Digital Signal Processing,'' Addison-Wesley, 1985. Google Scholar

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

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

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

[6]

J. Gathen and J. Gerhard, "Modern Computer Algebra'', Cambridge University Press, 2003. Google Scholar

[7]

C. Hartmann, Decoding beyond the BCH bound, IEEE Trans. Inform. Theory, 18 (1972), 441-444. doi: 10.1109/TIT.1972.1054824.  Google Scholar

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

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

[10]

J. D. Lipson, "Elements of Algebra and Algebraic Computing,'' Addison-Wesley Educational Publishers Inc, 1981.  Google Scholar

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

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

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

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

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

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

[2]

R. E. Blahut, "Fast Algorithms for Digital Signal Processing,'' Addison-Wesley, 1985. Google Scholar

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

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

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

[6]

J. Gathen and J. Gerhard, "Modern Computer Algebra'', Cambridge University Press, 2003. Google Scholar

[7]

C. Hartmann, Decoding beyond the BCH bound, IEEE Trans. Inform. Theory, 18 (1972), 441-444. doi: 10.1109/TIT.1972.1054824.  Google Scholar

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

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

[10]

J. D. Lipson, "Elements of Algebra and Algebraic Computing,'' Addison-Wesley Educational Publishers Inc, 1981.  Google Scholar

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

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

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

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

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

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

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

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 & Continuous Dynamical Systems, 2021  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 & 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 & 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 & Continuous Dynamical Systems, 2012, 32 (4) : 1309-1353. doi: 10.3934/dcds.2012.32.1309

2020 Impact Factor: 0.935

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences