A linear algebraic approach to multisequence shift-register synthesis
Vladimir R. Sidorenko, Georg Cornelius Schmidt · Problems of Information Transmission · 2011
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λN) ≲ O(KN 2), where N is the length of a longest sequence and λ is the linear complexity of the sequences.