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.  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.  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.  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.  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.  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.  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.  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.  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.  doi: 10.1016/S0019-9958(75)90090-X.  Google Scholar

[14]

L. Wang, Euclidean modules and multisequence synthesis,, in, (2001), 239.   Google Scholar

[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.  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.  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.  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.  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.  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.  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.  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.  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.  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.  doi: 10.1016/S0019-9958(75)90090-X.  Google Scholar

[14]

L. Wang, Euclidean modules and multisequence synthesis,, in, (2001), 239.   Google Scholar

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

[1]

Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $ A_n $-lattice codes of full diversity. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020118
[2]

Thierry Horsin, Mohamed Ali Jendoubi. On the convergence to equilibria of a sequence defined by an implicit scheme. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020465
[3]

Hirokazu Ninomiya. Entire solutions of the Allen–Cahn–Nagumo equation in a multi-dimensional space. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 395-412. doi: 10.3934/dcds.2020364
[4]

Dan Zhu, Rosemary A. Renaut, Hongwei Li, Tianyou Liu. Fast non-convex low-rank matrix decomposition for separation of potential field data using minimal memory. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020076
[5]

A. M. Elaiw, N. H. AlShamrani, A. Abdel-Aty, H. Dutta. Stability analysis of a general HIV dynamics model with multi-stages of infected cells and two routes of infection. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020441

2019 Impact Factor: 0.734

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences