American Institute of Mathematical Sciences

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

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

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

2017 Impact Factor: 0.564