Линейно-алгебраический подход к синтезу регистра сдвига, порождающего несколько последовательностей

Предложен эффективный алгоритм синтеза всех минимальных регистров сдвига с линейными обратными связями, порождающих $K$ последовательностей, возможно, различной длины над произвольным полем. Доказана корректность этого алгоритма. Предложенный алгоритм является обобщением алгоритмов Берлекэмпа–Мэсси и Фенга–Тзенга и основан на идеях Мэсси. Вычислительная сложность этого алгоритма имеет порядок $O(K\lambda N)\lesssim O(KN^2)$, где $N$ – длина самой длинной последовательности, а $\lambda$ – линейная сложность этих последовательностей.