close

Вход

Забыли?

вход по аккаунту

?

Подходы к классификации регулярных систем однотипных двоичных функций построенных с помощью циклического сдвига.

код для вставкиСкачать
МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ
ПОДХОДЫ К КЛАССИФИКАЦИИ РЕГУЛЯРНЫХ СИСТЕМ
ОДНОТИПНЫХ ДВОИЧНЫХ ФУНКЦИЙ, ПОСТРОЕННЫХ С
ПОМОЩЬЮ ЦИКЛИЧЕСКОГО СДВИГА
А.В. САРАНЦЕВ, ИКСИ, Москва
работе рассматриваются вопросы, свяВ
занные с классификационными исследованиями биективных преобразований специального вида.
Преобразование пространства Vn двоичных векторов длины n может быть задано
с помощью системы координатных функций
(f1, ..., fn). Вычисление образа (y1, ..., yn)
входного вектора (x1, ..., xn) производится по
формуле
yi = fi(x1, ..., xn), i = 1, 2, ..., n.
В работе [4] для компактной реализации биективных отображений предложено
использовать регулярные системы (f, g1f, ...,
gn–1f) булевых функций, порожденных одной
базовой функцией f таким образом, что все
координатные функции задаются из исходной с помощью преобразований g1, g2, ..., gn–1,
принадлежащих некоторой группе G. В этом
случае все координатные функции являются
представителями классов эквивалентности
по группе G или типов [3]. В работе [4] приводятся результаты классификационных исследований таких функций и порождаемых
ими систем с использованием свойств групп
преобразований координат двоичных функций. В работе [5] исследуется вопрос построения таких систем функций с помощью
преобразования координат, осуществляемого аффинным регистром сдвига.
В настоящей работе рассмотрим частный случай построения регулярных систем однотипных двоичных функций с помощью преобразования циклического сдвига
координат порождающей функции.
Пусть σ: (x1, x2, ..., xn) → (x2, x3, ..., xn, x1)
преобразование циклического сдвига координат векторов пространства Vn, f – двоичная
функция от n переменных. В представлен-
176
ной работе исследуются вопросы классификации биективных преобразований вида
f ;σ = ( f ,σf ,…,σ f ) ,
n −1
где σf = f (σ ( x1 , x2 ,…, xn )) = f ( x2 , x3 ,…, xn , x1 ) .
Опишем алгоритм построения всех регулярных систем вида 〈f; σ〉. На предварительном этапе разбиваем все множество векторов
пространства Vn на непересекающиеся орбиты
преобразования циклического сдвига σ
Vn =
i∈I
Δi =
i∈I
{ α ,σ (α ),…,σ
i
i
Δ i −1
}
(α i ) .
Каждую орбиту Δ мощности t записываем в виде матрицы размера t × n и через
Δ↓i обозначаем i-й столбец построенной матрицы.
Теперь, чтобы построить порождающую функцию f системы 〈f; σ〉, сначала для
каждой орбиты Δi мощности t по перестановке s на множестве орбит мощности t выбираем орбиту Δs(i). Затем полагаем вектор
значений функции f на множестве векторов
↓
орбиты Δi, равным вектору (Δ s (i ) ) j , где j –
произвольный столбец матрицы, соответствующей орбите Δs(i).
Остальные координатные функции
системы 〈f; σ〉 строим из порождающей
функции f циклическим сдвигом ее координат.
Рассмотрим преобразование циклического сдвига σ координат как элемент σˆ
группы SVn подстановок на векторах пространства Vn. Через
N SV (σˆ )
n
обозначим
нормализатор этого элемента в группе SVn ,
т.е. множество подстановок g из SVn таких,
что g ⋅ σˆ = σˆ ⋅ g [2]. Описание элементов
ЛЕСНОЙ ВЕСТНИК 6/2005
МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ
нормализатора N SV (σˆ ) по цикловой струкn
туре подстановки σˆ представлено в работе
[1]. Поскольку цикловая структура подстановки σˆ соответствует разбиению пространства Vn на непересекающиеся орбиты
циклического сдвига σ, то множество всех
построенных выше систем вида 〈f; σ〉 совпадает с нормализатором N SV (σˆ ) . Отсюда
n
следует, что построенные системы являются
регулярными и образуют подгруппу в группе SVn . В частности, преобразование 〈f; σ〉–1,
обратное к преобразованию 〈f; σ〉, может
быть представлено в виде 〈ϕ; σ〉, где ϕ – некоторая двоичная функция. Число всех регулярных систем вида 〈f; σ〉 равно
d |n
где М(d) – число орбит мощности d преобразования циклического сдвига.
Для проверки регулярности преобразования 〈f; σ〉 может быть применен критерий
Хаффмана [4]. В одной из интерпретаций
этого критерия требуется проверить равновероятность любой нетривиальной линейной
комбинации координатных функций системы. Для исследуемых систем вида 〈f; σ〉 такая
проверка может быть несколько упрощена.
Утверждение 1
{ α ,σ (α ),…,σ
i
i∈I
i
Δ i −1
(α i )
}–
разбиение пространства Vn на орбиты преобразования σ. Система 〈f; σ〉 регулярна в том и
только том случае, когда функции
σ j f ⊕ … ⊕ σ f равновероятны для всех
векторов
jα
1
1
⎞
⎠
i
Доказательство
Любой нетривиальной линейной
i
i
комбинации σ 1 f ⊕… ⊕ σ k f координатных
функций преобразования 〈f; σ〉 поставим в
соответствие двоичный вектор
⎛⎜ 0,…,0,1,0,…,0, 1,0,… 0 ⎞⎟ ,
i1
ik
⎝
⎠
содержащий единицы только на местах с
номерами i1, ..., ik. Построенный вектор принадлежит некоторой орбите преобразования
σ, поэтому он может быть получен из соответствующего вектора
⎛
⎝
⎞
⎠
αi = ⎜ 0,…,0,1,0,…,0, 1 ,0,…0 ⎟
j
jα
∏ M (d )!d M (d ) ,
Пусть Vn =
⎛
⎝
αi = ⎜ 0,…,0,1,0,…,0, 1 ,0,…0 ⎟ .
j
jα
i
1
i
орбиты посредством циклического сдвига на
несколько позиций влево. Поскольку для
всех целых t из равновероятности функции
j
σ j1 f ⊕ … ⊕ σ αi f следует равновероятность
(
j
)
функции σ t σ j1 f ⊕… ⊕ σ α i f , то далее
справедливость утверждения вытекает непосредственно из критерия Хаффмана.
Таким образом, для построения всех
регулярных систем вида 〈f; σ〉 необходимо
создать массив векторов-представителей орбит циклического сдвига и, воспользовавшись предыдущим утверждением, провести
классификацию двоичных функций относительно циклического сдвига координат. Такие экспериментальные исследования были
проведены для множества равновероятных
функций от 3 до 5 переменных без свободного члена в многочлене Жегалкина. Результаты исследований представлены в табл. 1.
Таблица 1
n
Количество классов
эквивалентности
3
4
5
13
1629
60108055
ЛЕСНОЙ ВЕСТНИК 6/2005
Количество классов,
порождающих
системы вида 〈f; σ〉
6
192
2250000
Количество классов,
не порождающих
системы вида 〈f; σ〉
7
1437
57858055
177
МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ
Ввиду сложности проверки регулярности системы 〈f; σ〉 для больших значений
n, возникает прикладная задача описания
некоторых классов функций, заведомо порождающих регулярные системы такого вида. В этом направлении видятся два подхода.
Первый заключается в «увеличении» группы, по которой проводится классификация
порождающих функций. Второй подход состоит в разработке способов построения
«новых» систем из регулярных систем, построенных ранее.
В описанной выше классификации
равновероятных двоичных функций в качестве группы, по которой проводилось разбиение функций на классы эквивалентности,
была выбрана группа 〈σ〉 преобразований
пространства Vn, порожденная циклическим
сдвигом координат векторов. При выборе
группы, содержащей группу 〈σ〉 в качестве
подгруппы, требуется, чтобы у построенных
классов эквивалентности двоичных функций
свойство порождать регулярную систему
вида 〈f; σ〉 было инвариантом класса.
Утверждение 2
Пусть G некоторая группа, содержащая группу 〈σ〉, NG(〈σ〉) – нормализатор группы 〈σ〉 в группе G. Тогда, если система 〈f; σ〉
регулярна, то для любого преобразования g
из нормализатора NG(〈σ〉) система 〈gf; σ〉
является регулярной.
Доказательство
Пусть система 〈f; σ〉 регулярна,
g – произвольное преобразование из нормализатора NG(〈σ〉). Рассмотрим действие системы 〈gf; σ〉 на вектор x из пространства Vn.
В силу перестановочности элемента g со степе-
нями преобразования σ справедливы соотношения
( ( ) ( ( ))
= ( f , σf ,…, σ f )(g ( x) ) =
( ( )))
f ;σ (g ( x) ).
gf ;σ ( x) = f g ( x) , f σ g ( x) ,…, f σ n−1 g ( x) =
n −1
Последние равенства доказывают
справедливость утверждения.
Определим действие на пространстве
Vn группы GL (n, 2) обратимых матриц над
полем GF (2) как умножение матрицы на
столбец координат вектора. Тогда, используя изоморфизм группы перестановок координат и группы перестановочных матриц,
преобразованию циклического сдвига влево
координат векторов пространства Vn можно
поставить в соответствие n × n матрицу
⎛0
⎜0
⎜
⎜
⎜
T =⎜
⎜
⎜
⎜0
⎜1
⎝
1
0
0
1
0
0
0
0
0
0⎞
0 ⎟⎟
⎟
⎟.
⎟
0⎟
⎟
1⎟
0 ⎟⎠
Нормализатором матрицы T в группе
GL (n, 2), как нетрудно проверить, являются
обратимые матрицы, каждая строка которых
получена циклическим сдвигом вправо предыдущей строки. Таким образом, при построении регулярных систем вида 〈f; σ〉, достаточно выбирать функции из класса эквивалентности по группе N GL (n, 2)(T).
В ходе экспериментальных исследований проведена классификация по нормализатору циклического сдвига двоичных функций
от 3 до 5 переменных без свободного члена в
многочлене Жегалкина, которые порождают
регулярные системы вида 〈f; σ〉. Результаты
исследований представлены в табл. 2.
Таблица 2
n
3
4
5
178
Мощность
нормализатора
N GL (n, 2) (T)
3
8
15
Количество классов
эквивалентности
13
865
20036053
Количество классов,
порождающих системы
вида 〈f; σ〉
6
96
750000
Количество классов, не
порождающих системы
вида 〈f; σ〉
7
769
19286053
ЛЕСНОЙ ВЕСТНИК 6/2005
МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ
Опишем способ построения регулярных систем вида 〈f; σ〉 из систем, построенных ранее. Поскольку композиция регулярных преобразований есть регулярное преобразование, то для любой регулярной системы 〈f; σ〉 и обратимой матрицы A из группы
GL (n, 2) преобразование A ◦ 〈f; σ〉 регулярно.
При этом, если в i-й строке матрицы
A единицы стоят только на местах с номерами i1, i2, ..., it, то i-я координатная функция
преобразования A ◦ 〈f; σ〉〈f; σ〉 представляет
собой линейную комбинацию координатных
функций преобразования 〈f; σ〉 с номерами i1,
i2, ..., it. Таким образом, для того чтобы преобразование A ◦ 〈f; σ〉 имело вид 〈φ; σ〉, необходимо и достаточно выполнение двух требований: во-первых, матрица A должна быть
обратима; во-вторых, каждая строка матрицы A должна быть получена из предыдущей
строки циклическим сдвигом координат
вправо.
Представленный способ построения
новых регулярных систем функций позволяет в приведенной выше классификации частично «склеить» классы эквивалентности по
нормализатору N GL (n, 2) (〈σ〉). Количественные результаты экспериментальных исследований в данном направлении представлены в табл. 3.
Таблица 3
n
Количество классов, порождающих системы вида 〈f; σ〉
3
4
5
6
52
250040
Вернемся к алгоритму построения
всех регулярных систем вида 〈f; σ〉 и рассмотрим структуру построенных порождающих функций.
Для любого n существует ровно две
орбиты преобразования циклического сдвига, мощность которых равна 1. Это орбиты
{(0, ...,0)} и {(1, ...,1)}. Поскольку без ограничения общности достаточно рассматривать только двоичные функции без свободного члена в многочлене Жегалкина [4], то
построенные функции принимают значение
ЛЕСНОЙ ВЕСТНИК 6/2005
0 на векторе (0, ...,0) и 1 на векторе (1, ...,1).
В противном случае порожденные такими
функциями системы не будут являться регулярными.
Заметим, что если
{
Δ = α , σ (α ),… , σ t −1 (α )
}
– некоторая орбита мощности t, то множество векторов
{
}
Λ = α ,σ (α ),…,σ t −1 (α ) ,
в которое входят отрицания элементов орбиты Δ, также является орбитой мощности t.
Последний факт вытекает из равенства
σ (α ) = σ (α ) .
При этом каждый столбец (Λ )↓j является отрицанием столбца (Δ ) j , j ∈1, t .
Таким образом, инвертирование всех
значений, которые функция f принимает на
векторах орбит одинаковой мощности, соответствует перестановке значений функции
на векторах этих орбит. При этом возможны
↓
два случая. Если векторы значений (Δ) j и (Δ )j
соответствуют орбитам, отличающимся инверсией векторов, то происходит переста↓
новка этих значений. Если же векторы (Δ) j и
↓
(Δ )
↓
↓
являются столбцами одной и той же
матрицы, соответствующей орбите, то происходит циклический сдвиг значений функции на этой орбите. Отметим, что в любом
из этих случаев возможно получение функции, которая будет лежать в другом классе
эквивалентности по нормализатору N GL (n, 2)
(〈σ〉) и не может быть представлена в виде
линейной комбинации координатных функций системы, порожденных исходной функцией. Это связано с тем, что такое преобразование координатных функций системы не
является линейным.
j
Пример
Пусть n четно. Рассмотрим регулярную систему 〈x1; σ〉. Эта система задает тождественное преобразование векторов пространства Vn. В случае четного n преобразо-
179
МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ
вание циклического сдвига координат двоичных векторов имеет орбиту Δ = {(0, 1, 0, 1,
..., 0,1), (1, 0, 1, 0, ..., 0, 1)} мощности 2. Зададим двоичную функцию φ следующим образом
⎧1, если x ∈ Δ,
⎩0, если x ∉ Δ.
ϕ ( x) = ⎨
Из предыдущих рассуждений следует, что система 〈x1 + φ; σ〉 регулярна. Однако
никаким линейным преобразованием координат функция φ не может быть получена из
функции x1, поскольку их степени нелинейности различны.
Таким образом, классификация двоичных функций, порождающих системы
вида 〈f; σ〉 с точностью до функцийслагаемых, принимающих единичные значения на орбитах циклического сдвига одинаковой мощности, позволяет уменьшить
количество классов эквивалентности порождающих функций. При этом сокращение
числа классов пропорционально мощности
множества таких функций-слагаемых. В частности, в случае простого n, когда две орбиты циклического сдвига имеют мощность 1, а
остальные – n, количество классов сокращается в два раза. По результатам экспериментальных исследований получено следующее количество классов, порождающих
регулярные системы рассматриваемого вида (табл. 4).
Таблица 4
n
Количество классов, порождающих системы вида 〈f; σ〉
3
4
5
3
14
125020
Таким образом, проведенные классификационные исследования позволяют выписать представителей классов двоичных
функций, порождающих регулярные системы вида 〈f; σ〉. Полиномы Жегалкина представителей таких классов функций от 3 и 4
переменных имеют следующий вид.
180
Для n = 3:
1. x1,
2. x1 + x1 x3 + x2 x3,
3. x1 + x1 x2 + x2 x3.
Для n = 4:
1. x1,
2. x1 + x1 x3 x4+ x2 x3 x4,
3. x1 + x1 x2 x4+ x2 x3 x4, ,
4. x1 + x1 x2 x3+ x2 x3 x4,
5. x1 + x1 x4 +x2 x3+ x1 x2 x3 + x1 x2 x4 + x1 x3 x4+
+ x 2 x 3 x 4,
6. x1 +x2 x3+ x1 x2 x3 + x1 x3 x4 + x2 x3 x4,
7. x1 + x2 x3+ x2 x3 x4,
8. x1 +x1 x4+ x2 x3 + x1 x2 x3 + x1 x3 x4,
9. x1 +x2 + x1 x2 +x1 x4+ x2 x3 + x2 x4 + x1 x2 x3+
+ x 1 x 3 x 4 + x 2 x 3 x 4,
10. x1 +x2 + x2 x3 + x2 x4 + x2 x3 x4,
11. x1 +x2 + x1 x2 +x1 x4+ x2 x3 + x2 x4 + x1 x2 x3,
12. x1 +x2 + x1 x2 +x1 x4+ x2 x3 + x2 x4 + x1 x3 x4,
13. x1 +x2 + x2 x3 + x2 x4 + x1 x2 x4,
14. x1 +x2 + x2 x3 + x2 x4 + x1 x2 x3.
В качестве приводимых выше представителей классов выбирались функции,
имеющие минимальный номер (где под номером функции подразумевается число,
двоичное представление которого совпадает
с вектором значений функции).
Работа осуществлена при поддержке
гранта Президента РФ (НШ-2358.2003.9).
Библиографический список
1.
2.
3.
4.
5.
Глухов М.М., Елизаров В.П., Нечаев А.А. Алгебра. Т.1. – М.: Гелиос АРВ, 2003.
Каргаполов М.И., Мерзляков Ю.И. Основы теории групп. – М.: Наука, 1972.
Никонов В.Г. Классификация минимальных базисных представлений всех булевых функций от
четырех переменных // Обозрение прикл. и промышл. матем. Сер. дискретн. матем. – 1994. –
Т. 1. – Вып. 3. – С. 458–545.
Никонов В.Г., Саранцев А.В. Методы компактной
реализации биективных отображений, заданных
регулярными системами однотипных булевых
функций // Вестник РУДН. Серия прикл. и комп.
математика. – Т.2. – № 1. – 2003. – С. 84–95.
Саранцев А.В. Построение регулярных систем
однотипных двоичных функций с использованием регистра сдвига // Вестник МГУЛ – Лесной
вестник. – 2004. – № 1(32) – С. 164–169.
ЛЕСНОЙ ВЕСТНИК 6/2005
1/--страниц
Пожаловаться на содержимое документа