A linear algebraic approach to multisequence shift-register synthesis

An efficient algorithm which synthesizes all shortest linear-feedback shift registers generating $K$ given sequences with possibly different lengths over a field is derived, and its correctness is proved. The proposed algorithm generalizes the Berlekamp–Massey and Feng–Tzeng algorithms and is based on Massey's ideas. The time complexity of the algorithm is $O(K\lambda N)\lesssim O(KN^2)$, where $N$ is the length of a longest sequence and $\lambda$ is the linear complexity of the sequences.