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

Alexander Zeh; Antonia Wachter

doi:10.3934/amc.2011.5.667

Article Contents

2011, Volume 5, Issue 4: 667-680. Doi: 10.3934/amc.2011.5.667

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

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

Received: October 31, 2010

Revised: May 31, 2011

Published: October 2011

Abstract Related Papers Cited by

Abstract

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:

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

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

Citation:

Related Papers

Cited by

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.