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

show all references

##### References:

2018 Impact Factor: 0.879