Дата публикации: 2019

Дата публикации в реестре: 2020-03-03T18:38:11Z

Аннотация:

Для регистра сдвига длины n, функция обратной связи которого зависит от двоичного знака управляющей последовательности (на каждом такте реализуется одно из двух регистровых преобразований), исследовано минимальное число y тактов регистра, после которых достигнуто полное перемешивание, то есть существенная зависимость каждой координатной функции композиции преобразований от всех переменных. Эффект полного перемешивания оценен с помощью множества Г перемешивающих n-вершинных орграфов регистровых преобразований, имеющих общий гамильтонов контур. Дана оценка экспонента exp Г примитивного множества Г, которая позволяет оценить снизу число 7: exp Г < 2n — 2 + £ (f(n — S(^«)) + da + , a=0 ' ' где S(<^a) = {s?,..., —множество номеров существенных переменных функции обратной связи ^a(x0,..., xn-1); n — S(<^a) = {n — sa : j = 1,..., m(a)}; da = НОД{п — S(<^a)}; F(n — S(<£>«)) = daФ((n — S(^a))/da); Ф((п — S(^a))/da) — число Фробениуса. Проведён вычислительный эксперимент при n = 6 и 10 по вычислению точного значения y с учётом управляющей последовательности. Установлено, что полное перемешивание возможно за число тактов, превышающее значение экспонента менее чем в 2 раза.

Тип: статьи в журналах

Источник: Прикладная дискретная математика. Приложение. 2019. № 12. С. 80-83