Advanced Search
Article Contents
Article Contents

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

Abstract Related Papers Cited by
  • 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.
    Mathematics Subject Classification: Primary: 94A55, 94B15; Secondary: 94B35.


    \begin{equation} \\ \end{equation}
  • [1]

    A. V. Aho and J. E. Hopcroft, "The Design and Analysis of Computer Algorithms,'' Addison-Wesley Longman Publishing Co., 1974.


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


    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.


    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.


    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.


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


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


    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.


    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.


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


    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.


    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.


    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.


    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.


    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.

  • 加载中

Article Metrics

HTML views() PDF downloads(222) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint