Perfect balancedness of k-valued functions and Golic condition.pdf Для всяких n ^ 1, k ^ 2 через Ek будем обозначать множество { 0 , 1 , . . . , к - 1}, черезPkn) - м н о ж е с т в о к - з н а ч н ы х ф у н к ц и й n п е р е м е н н ы х /: En ^ Efc; Pfc = U Pkn). Дляn=0всякого натурального l и всякой функции / Е Pk™ будем рассматривать отображение/ : E k + n - 1 ^ Ek, / i (Х1 ) = ( / ( X 1 , . . . ) , . . . , / ( ж г , . . . , ж г + „ _ 1 ) ) .Определение 1. Функция / Е Pk™ называется совершенно уравновешенной(обозначен|ие / если для всякого натурального l и всякого y Е Ek верноравенство |/i_1(y)| = kn_1.Определение 2. Функция / Е Pk™ имеет правый барьер длины b ^ 1, если изравенства / ь(жьЖ2,... ,ж„_ьжП,... ,xb+n_1) = /ь(жьЖ2,... ,ж„_1 ,хП,... ,xb+n_1) следуетn nАбсолютно аналогично случаю к = 2 (см. [1]) для произвольного к ^ 2 доказыва-ется, что наличие барьера влечет совершенную уравновешенность в Pk.Й. Голичем в работе [2] в 1996 г. рассмотрен (при к = 2) вопрос о важном для ис-пользуемых в фильтрующих генераторах функций свойстве, являющемся естествен-ным усилением свойства совершенной уравновешенности.Определение 3. Функция / Е PBkn)называется сильно совершенно уравнове-шенной, если при добавлении любого числа фиктивных переменных между существен-ными она сохраняет совершенную уравновешенность.Нетрудно показать, что перестановочность дискретной функции по первой или по-следней существенной переменной влечет за собой сильную совершенную уравнове-шенность. Голич в работе [2] предположил, что верно и обратное; данная гипотезапозже, начиная с работы М. Дихтла [3], стала называться гипотезой Голича.Гипотеза 1 [2]. При к = 2 из сильной совершенной уравновешенности некото-рой k-значной функции следует её перестановочность (т. е. линейность) по первой илипоследней существенной переменной.Косвенное подтверждение справедливости гипотезы Голича было впервые полу-чено в [1] (2008г.). В работе [4] (2012г.) гипотеза Голича полностью доказана. Та-ким образом, известно, что невозможно построить кодирующее устройство на основерегистра сдвига и фильтрующей функции (над алфавитом { 0 , 1 } ) , обеспечивающеесохранение истинной случайности битовой последовательности при любом выборе то-чек входа (см. [2]). Интересен вопрос о возможности построения таких кодирующихустройств над алфавитом большей мощности - в особенности в случае алфавита мощ-ности k = 2m, m ^ 2, т. е. в случае рассмотрения кодирующих устройств, преобразую-щих входную битовую последовательность блоками длины m.Условие Голича. Сильная совершенная уравновешенность в Pk эквивалентна пе-рестановочности по первой или последней существенной переменной.Из результатов работ [2, 4] следует, что условие Голича выполнено в P2. Настоящаяработа посвящена рассмотрению следующего обобщения гипотезы Голича, связываю-щего справедливость условия Голича в Pk с простотой числа k.Гипотеза 2. Условие Голича выполнено в Pk тогда и только тогда, когда k -простое.Теорема 1. Для всякого составного k существует функция f . P S k 2 ) , существен-но зависящая от обеих переменных и не перестановочная ни по одной из них.Следствие 1. Если k - составное, то условие Голича не выполнено в Pk.Теорема 2. Для всякого составного k существует функция f . Pk с правым ба-рьером длины 2, существенно зависящая от последней переменной и не перестановоч-ная по ней.Теорема 3. Для всякого составного k и всякого n ^ 2 существует сильно совер-шенно уравновешенная функция f . Pkn), существенно зависящая от всех n перемен-ных, которая не является перестановочной ни по первой, ни по последней переменной,но является сильно совершенно уравновешенной.Теорема 4. Пусть k - простое и функция f . Pkn) имеет правый барьер дли-ны 2. Тогда f не зависит существенно от последней переменной и перестановочна попредпоследней.Следствие 2. При простом k условие Голича не нарушается на функциях с ба-рьером длины 2.Следствие 3. Условие Голича не нарушается на функциях с барьером длины 2в Pk тогда и только тогда, когда k - простое.Теорема 5. При k . {2, 3, 5, 7} все совершенно уравновешенные функции из Pk2)перестановочны по первой или последней переменной.Следствие 4. При k . {2, 3, 5, 7} условие Голича не нарушается на функцияхиз Pk2 ).Таким образом, гипотеза 2 полностью доказана в части необходимости k быть про-стым для выполнения условия Голича в Pk. Кроме того, доказан ряд утверждений,косвенно подтверждающих справедливость гипотезы 2 в части достаточности.

Скачать электронную версию публикации