Многомерные регистры сдвига и сложность мультипоследовательностей

Понятия комбинаторной (рекурсивной) сложности и линейной сложности периодической последовательности однозначно определяются для последовательностей над простым полем как минимальная длина соответственно нелинейного и линейного регистра сдвига, порождающего эту последовательность. Для периодических последовательностей и мультипоследовательностей над конечным модулем линейную сложность уже нельзя охарактеризовать одним параметром. При оценке линейной сложности (мульти-)последовательности над модулем следует использовать не один – а серию параметров, которые можно пока условно разделить на три группы: параметры, связанные (а) с реализацией ее (полилинейным) регистром сдвига; (b) с описанием аналитического представления ее знаков; (с) с размерностью модуля, порожденного системой сдвигов исходной последовательности. В данной работе развивается подход к оценке сложности, связанный с первым из перечисленных направлений. Проведенные исследования показывают, что комбинаторную сложность периодической (мульти-)последовательности можно измерять размерностью специального автомата, порождающего эту последовательность, называемого мультирегистром сдвига на диаграмме Ферре. Для оценки линейной сложности периодической (мульти-)последовательности над модулем строится соответствующий канонический полилинейный регистр сдвига, размерность которого зависит от используемого кольца коэффициентов модуля. Устанавливаются некоторые соотношения между указанными параметрами.