Биективные отображения, порождаемые фильтрующим генератором | ПДМ. 2014. № 1(23).

Биективные отображения, порождаемые фильтрующим генератором

Рассматривается задача построения биективных отображений B/l : (F2) ^ (F2) , B/, (x) = (f (x),f (8(x)),...,f (8 (x))), x G FT, набор координатных функций которых задаётся преобразованием 8 = 5l регистра сдвига большой длины n с функцией обратной связи L и нелинейной функцией выхода f от небольшого числа k аргументов (k ^ n). При этом биективность отображения B/ l равносильна ортогональности системы его координатных функций. В работе развивается метод, который сводит исходную задачу проверки биектив-ности отображения B/ l при больших значениях длины регистра n к проверке его биективности применительно к регистрам сдвига ограниченной длины n ^ no, что позволяет эффективно использовать для её решения вычислительную технику. На основе данного метода в работе построены новые бесконечные классы биективных отображений для случая нелинейной функции f, зависящей от k ^ 6 переменных. Ранее аналогичные результаты были известны для случая, когда функция f зависит от k = 3 переменных. Полученные результаты могут быть полезны при построении и обосновании статистических свойств датчиков случайных чисел на основе фильтрующих генераторов. При этом особый практический интерес представляет выбор пар (f, L), при которых одновременно обеспечивается биективность отображения B/,l и максимальность периода отображения 8l.

Bijective mappings generated by filtering generator.pdf 1. Основные понятия и обозначения Далее в работе будем придерживаться следующих основных понятий и обозначений (используемые алгебраические понятия изложены в [1]): - F2 - поле из двух элементов; - (fi, f2,... , fm) -задание отображения (F2)n ^ (F2)m в виде системы координатных функций; - L(xi,x2,... ,x„) = L(xi,x2,... ,xs(i),xn-s(2)+i,xn-s(2)+2,... , x„) - функция обратной связи регистра сдвига длины n ^ s(1) + s(2), линейная по переменной xi, (s(1) ^ 1, s(2) ^ 0 - заданные параметры); - 5 = 5l - преобразование векторов пространства (F2)n, осуществляемое регистром сдвига с функцией обратной связи L(xi,x2,... ,xn), действующее на вектор (x1, x2,... , xn) Е (F2)n по правилу £(xbx2, . . . ,x„) = (x2 , x3, . . . , xn, L(xi,x2,..., xn)); - f (x1,x2,... , xk) -функция от k аргументов без запретов (являющаяся фильтрующей функцией съёма с соответствующего регистра сдвига); - Bf,L - преобразование двоичных векторов длины n (отображение (F2)n ^ (F2)n), задаваемое системой координатных функций Bf,L = (f (x), f (£(x)),..., f (^n-1(x))), x Е (F2)n. В работе рассматриваются вопросы выбора нелинейной функции съёма f и функции обратной связи L, при которых преобразование Bf,L является биективным. При этом биективность преобразования Bf,L равносильна ортогональности системы его координатных функций [2]. В [2] показано, что при n ^ 2k-1 + k - 1 отсутствие запретов у функции f = f (x1, x2,... , xk) является необходимым условием биективности отображения Bf,L (функции без запрета называют также функциями без потери информации, сильно равновероятными и совершенно уравновешенными [3-5]). Известно [4], что для функции без запретов f (x1, x2,... , xk) при любом натуральном n существует ровно 2k-1 входных слов x1, x2,... , xn+k-1, перерабатываемых данной функцией в любое фиксированное выходное слово y(1), y(2),... , y(n) по закону n. n y(j) = f (xj ,xj+i,... ,xj+k-i), j = 1, 2,... Поэтому биективность преобразования Bf,L равносильна тому, что среди этих 2k 1 входных слов ровно одно слово будет удовлетворять ограничениям xn+1 = L(x) = L(xi,x2,... ,x„), xn+2 = L(£L(x)), ..., xn+k-1 = L((#i)k 2(x)). При этом xn+1, xn+2,... , xn+k-1 как функции от независимых переменных x1, x2,... , x. (в силу ограничений на вид функции обратной связи L) зависят лишь от k + s(1) - 2 начальных переменных и от s(2) последних переменных. Таким образом, выполняется ограничение 1 или нет для данного входного слова x1,x2,..., xn+k-i, зависит только от его начального отрезка x1,x2,... ,xk+s(1)-2 длины k + s(1) - 2 и конечного отрезка xn-s(2)+1, . . . ,xn, xn+1, xn+2, . . . , xn+k-1 длины k + s(2) - 1. Для заданных функции f (x1,x2, ...,xk), натуральных r, s ^ k - 1 и выходного слова Y = y(1), y(2),..., y(m) через I = I(Y) = Ir,s(Y) обозначим систему пар векторов (a(i),e(i)) , i = 1, 2,..., 2k-1, где a(i) = x1,x2,...,xr и в(i) = xm+k-s, xm+k-s+1, ...,xm+k-i являются соответственно началами и концами входных слов X = x1,x2,...,xk, xk+1,... , xk+m-1, перерабатываемых функцией f в выходное слово Y • y(j) = f (xj ^Ч!^..^^-!^ j = 1, 2,...,m. Так как число различных входов X, отвечающих заданному выходу Y, в точности равно 2k-1, то полагаем, что I(Y) состоит из 2k-1 элементов. При этом соответствующие системы I(Y) и I(Z) считаем равными (I(Y) = I(Z)), если любой элемент (а, в) Е I(Y) встречается в I(Z) ровно столько раз, сколько он встречается в I(Y). Определение 1. Двоичные последовательности Y = y(1), y(2),... , y(n) и Z = = z(1), z(2),... , z(m) назовём эквивалентными (обозначим Y ~ Z), если Ik-1,k-1(Y) = = ^k-1,k-1(Z). Пример 1. Для функции от трёх переменных f (x1,x2,x3) = x1x2 + x2 + x3 выходным словам Y1 = (y(1), y(2), y(3), y(4)) = (0, 0, 0, 0) и Z1 = (z(1), z(2), z(3)) = (0, 0, 0) соответствуют следующие наборы входных слов: (0,0,0,0,0,0), (1,0,0,0,0,0), (0,1,1,0,0,0), (1,1,0,0,0,0) для Yi, (0,0,0,0,0), (1,0,0,0,0), (0,1,1,0,0), (1,1,0,0,0) для Zi. Начала и окончания длины 2 входных векторов свидетельствуют, что I2,2(Yi) = I2,2(Zi) = {(00, 00), (10, 00), (01, 00), (11, 00)}. Следовательно, слова Y1 и Z1 являются эквивалентными. Аналогичным образом можно убедиться, что эквивалентны также слова Y2 = (0,1, 0,1, 0,1) и Z2 = (0,1), для которых /2,2(Y>) = I2,2(Z2) = {(00, 01), (10, 01), (01, 11), (11, 01)}. Определение 2. Упорядоченное множество натуральных чисел {h, t1, t2,... , te}, h > t1 > ... > te, 0 ^ 1, назовём понижающим для функции f (x1,x2,... ,xk), если для любой последовательности Y длины h найдётся эквивалентная ей последовательность Z длины t Е {t1,t2,..., te}. Понижающее множество {h,t1,t2,..., te} называем равновесным, если для любого t Е {t1,t2,... ,te} и любой последовательности Y длины t найдётся эквивалентная ей последовательность длины h. Понижающее множество {h, t}, состоящее из двух элементов, будем также называть понижающей парой и обозначать (h,t). Пример 2. Для функции от двух переменных f (x1,x2) = x1 + x2 выходным словам Y длины 1 и 2 соответствуют следующие множества входов: слову 0 - {(0, 0), (1,1)}, слову 1 - {(0,1), (1, 0)}, слову 00 - {(0, 0, 0), (1,1,1)}, слову 10 - {(0,1,1), (1, 0, 0)}, слову 01 - {(0, 0,1), (1,1, 0)}, слову 11 - {(0,1,0), (1, 0,1)}. Отсюда получаем 1i,i(Y = 0) U 1i,i(Y = 1) = {{(0,0), (1,1)}, {(0,1), (1,0)}}; 1i,i(Y = 00) U 1i,i(Y = 10) U 1i,i(Y = 01) U 1i,i(Y = 11) = {{(0, 0), (1,1)}, {(0,1), (1, 0)}}. Следовательно, для рассматриваемой функции множество (h,t) = (2,1) является равновесной понижающей парой. Определение 3. Длиной (расстоянием) эквивалентности для заданной функции без запретов f = f (x1, x2,... , xk) назовём натуральное число n0, при котором любое слово длины n > n0 эквивалентно некоторому слову длины ^ n0. Для функции из примера 2 расстояние эквивалентности, очевидно, равно 1. Заметим, что если n0 - длина эквивалентности функции f, то и любое n > n0 также является её длиной эквивалентности. Кроме того, непосредственно из определения 3 вытекает: если n0 - длина эквивалентности функции f, то множество {no + 1, no, no - 1,... , 2,1} является для данной функции понижающим. 2. Вспомогательные утверждения Лемма 1. Пусть r, s ^ k - 1, Ir,s(Y) = Ir,s(Z), e G {0,1}, Y1 = eY, Z1 = eZ, Y2 = Ye, Z2 = Ze. Тогда Ir+M(Y 1) ='Ir+1,s(Z 1), Ir,s+1(Y2) = Ir,s+1(Z2). Доказательство. Пусть X = x1, x2,..., xk, xk+1,..., xk+n-1 - произвольное входное слово, соответствующее выходному слову Y длины | Y| = n. Тогда входные слова, соответствующие выходному слову Y2 = Ye, имеют следующий вид: 1) Xa, если имеется единственное значение a G {0,1}, для которого /(xn+1,..., xn+k-1, a) = e; 2) X0, X1, если /(xn+1,... ,xn+k-1, 0) = /(xra+b... ,xn+k-1,1) = e; 3) таких входных слов не существует, если f(xn+1, . . . , xn+k-1, 0) = / (xn+b... 1) = e. Отсюда вытекает справедливость леммы для пары Y2, Z2. Аналогичным образом проводится доказательство и для пары Y1, Z1. ■ Лемма 2. Пусть /(x1,x2,... ,xk) = ^(x1,x2,... ,xk-1) + xk. Двоичные последовательности y(1), y(2),... , y(n) и z(1), z(2),... , z(m) являются эквивалентными, если и только если при любом a G (F2)k-1 £y(n)£y(n-1) . . . £y(1)(a) = £z(m)£z(m-1) . . . где £e(x1,x2,... ,xk-1) = (x2,x3,..., xk-1, ^(xb x2,... ,xk-1) + e). Доказательство. Для функции /(x1, x2,..., xk) = ^(x1, x2,..., xk-1) + xk слова X = x1,x2,... , xn+k-1, перерабатываемые этой функцией в фиксированное выходное слово y(1), y(2),..., y(n), y(j) = /(xj, xj+1,..., xj+k-1), j = 1, 2,..., n, задаются последовательностью векторов a0 = (x1,x2,... ,xk-1), a1 = (x2,x3,... ,xk), xk = ^(a0) + y(1) ^ a1 = £y(1)(a0), an = (x„+1,xra+2,... ,xn+k-1), xra+k-1 = ^(an-1) + y(n) ^ ara = £y(n)(an_1). Отсюда и получаем утверждение леммы. ■ Лемма 3. Пусть {h,t1 ,t2,... ,t#} -понижающее множество. Тогда 1. При любом натуральном e множество {h + e,t1 + e,t2 + e,..., t# + e} также является понижающим. При этом оно будет равновесным, если таким является исходное множество. 2. При любом фиксированном n0 ^ t^ произвольное слово Y = y(1),y(2),... , y(n) длины n ^ n0 эквивалентно некоторому слову длины t G {n0,n0 +1,... , n0 + h - - 1}. Доказательство. С учётом леммы 1 доказательство первой части леммы 3 легко проводится индукцией по e. Докажем вторую часть. Пусть произвольное заданное слово Y = y(1), y(2),... , y(n) длины n ^ n0 эквивалентно некоторому слову Z = z(1), z(2),... , z (t) длины t G {n0,n0 + 1,...,n0 + h - t^ - 1}. Тогда слово Y1 = (y(1), y(2),..., y(n), a) = Ya эквивалентно слову Z1 = Za, длина которого принадлежит множеству {n0 + 1, n0 + 2,..., n0 + h - }. Далее достаточно рассмотреть случай, когда длина слова Z1 равна t = n0 + h - . Слово Z1 можно представить в виде Z1 = VW, где V - начало слова Z1 (длины (n0 - ) ^ 0), а W - его окончание длиной h. Тогда слово W эквивалентно некоторому слову W1 длины t G {t1,t2,... ,t#}. Значит, слово Z1 = VW эквивалентно слову VW1, длина которого равна (n0 - t

Ключевые слова

ортогональные системы функций, регистр сдвига, фильтрующий генератор, понижающее множество, orthogonal system of Boolean functions, feedback shift register, filter generator

Авторы

ФИООрганизацияДополнительноE-mail
Рожков Михаил ИвановичВысшая школа экономики (г. Москва)доцент Московского института электроники и математикиrozhkov.m.i@yandex.ru
Всего: 1

Ссылки

Лидл Р., Нидеррайтер Г. Конечные поля: в 2-х т. М.: Мир, 1988. 822 с.
Рожков М. И. К вопросу построения ортогональных систем двоичных функций с использованием регистра сдвига // Лесной вестник. 2011. Вып.3. С. 180-185.
Huffman D. A. Canonical forms for information loss less finite state logical mashines // IRE Trans. Circuit Theory. 1959. V. 6, spec. suppl. P. 41-59.
Сумароков С. Н. Запреты двоичных функций и обратимость для одного класса кодирующих устройств // Обозрение прикл. и промышл. матем. Сер. дискретн. матем. 1994. Т. 1. Вып. 1. С. 33-35.
Логачев О. А., Смышляев С. В., Ященко В. В. Новые методы изучения совершенно уравновешенных булевых функций // Дискретная математика. 2009. Т. 21. №2. С. 51-74.
Глухов М. М., Елизаров В. П., Нечаев А. А. Алгебра: учебник. В 2-х т. Т. 2. М.: Гелиос АРВ, 2003. 416 с.
Саранцев А. В. Построение регулярных систем однотипных двоичных функций с использованием регистра сдвига // Лесной вестник. 2004. №1(32). С. 164-169.
Рожков М. И. Некоторые алгоритмические вопросы идентификации конечных автоматов по распределению выходных m-грамм. Ч. 2 // Обозрение прикл. и промышл. матем. Сер. дискретн. матем. 2008. Т. 15. Вып. 5. С. 785-806.
Рожков М. И. Некоторые алгоритмические вопросы идентификации конечных автоматов по распределению выходных m-грамм. Ч. 3 // Обозрение прикл. и промышл. матем. Сер. дискретн. матем. 2009. Т. 16. Вып. 1. С. 35-60.
Михайлов В. Г., Чистяков В. П. О задачах теории конечных автоматов, связанных с числом прообразов выходной последовательности // Обозрение прикл. и промышл. матем. Сер. дискретн. матем. 1994. Т. 1. Вып. 1. С. 7-32.
Фомичев В. М. Дискретная математика и криптология. Курс лекций / под общ. ред. Н. Д. Подуфалова. М.: ДИАЛОГ-МИФИ, 2003. 400 с.
Рожков М. И. О некоторых классах нелинейных регистров сдвига, обладающих одинаковой цикловой структурой // Дискретная математика. 2010. Т. 22. №2. С. 96-119.
 Биективные отображения, порождаемые фильтрующим генератором | ПДМ. 2014. № 1(23).

Биективные отображения, порождаемые фильтрующим генератором | ПДМ. 2014. № 1(23).

Полнотекстовая версия