Цель работы: Получение практических навыков по изучению свойств БФ f(x₁,x₂,x₃) и булевых функций, используемых в нелинейном преобразовании алгоритма «Кузнечик» стандарта ГОСТ 34.12-2015. Используемое программное обеспечение: В работе используется электронный документ «Исследование БФ.xlsx», разработанный в Microsoft Excel – программа для работы с электронными таблицами. Ход выполнения лабораторной работы:Часть 1.Булевой функцией (БФ) называется отображение {0,1}ⁿ  {0,1}, т. е. сопоставление вектору из n бит значение 0 или 1. Задать БФ от n переменных можно, указав значение функции на каждом из наборов значений переменных. Булева функция может быть задана таблицей истинности. В лабораторной работе булева функция задана согласно варианту студента в списке группы – 20 вариант.Таблица 1 – Булева функция

Аргумент			Номер варианта
X3	X2	X1	20
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	0

---

Вторым этапом выполнения лабораторной работы является нахождение полинома Жегалкина. Любая булева функция может представляться в виде алгебраической нормальной формы – АНФ. Алгебраическую нормальную форму также называют полиномом Жегалкина: f_n = y₀·1 ⨁ y₁·x₁ ⨁ y₂·x₂…⨁y₁₂·x₁·x₂…⨁y_1..n·x_1..xn.Заданная БФ:Построили матрицу A_n = [8*8] рекуррентным образом:A_n = Для нахождения коэффициентов уi, необходимо перемножить две матрицы A_nи f(x) и от каждого элемент полученной матрицы найти остаток от деления на 2:После перемножения двух матриц получаем столбец коэффициентов y0, y1 … y123. Для более удобного восприятия, запишем столбец в транспонированном виде:Таблица 2 – Коэффициенты

X1	X2	X3	y	Переменные
0	0	0	0	1
0	0	1	1	х3
0	1	0	0	х2
0	1	1	1	x2х3
1	0	0	1	х1
1	0	1	1	х1х3
1	1	0	0	х1х2
1	1	1	0	х1х2х3

Таким образом, АНФ булевой функции имеет вид:В следующем этапе лабораторной работы необходимо определить вес БФ. Вес БФ - число единиц среди его элементов. Таким образов вес представленной БФ = 4.Четвёртый этап – найти нелинейность исследуемой БФ. Термин «нелинейность» принят для оценки степени нелинейности

---

, использующей понятия веса и расстояния Хэмминга. Расстоянием Хэмминга это число, равное количеству позиций, в которых различаются соответствующие символы двух функций одинаковой длины т.е., это число позиций, на которых f(x) не равно g(x).

Нелинейность находится по формуле:

N(f) = 2^n-1 -

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





где a это векторный параметр, принимающие все возможные комбинации 1 и 0.
Первое, что необходимо сделать для нахождения нелинейности БФ это найти скалярное произведение b= (а, х). Скалярное произведение в координатах ищется по формуле:

b = a₁x₁; a₂x₂;…;a_nx_n.
Таблица 3 - Таблица векторов x и а.

	x			a
x0	0	0	0	0	0	0	a0
x1	0	0	1	0	0	1	a1
x2	0	1	0	0	1	0	a2
x3	0	1	1	0	1	1	a3
x4	1	0	0	1	0	0	a4
x5	1	0	1	1	0	1	a5
x6	1	1	0	1	1	0	a6
x7	1	1	1	1	1	1	a7

---

Таблица 4 – Скалярное произведение векторов

xi, a0	xi, a1	xi, a2	xi, a3	xi, a4	xi, a5	xi, a6	xi, a7
0	0	0	0	0	0	0	0
0	1	0	1	0	1	0	1
0	0	1	1	0	0	1	1
0	1	1	0	0	1	1	0
0	0	0	0	1	1	1	1
0	1	0	1	1	0	1	0
0	0	1	1	1	1	0	0
0	1	1	0	1	0	0	1

Таблица 5 –

0	0	0	0	0	0	0	0
1	0	1	0	1	0	1	0
0	0	1	1	0	0	1	1
0	1	1	0	0	1	1	0
1	1	1	1	0	0	0	0
1	0	1	0	0	1	0	1
1	1	0	0	0	0	1	1
0	1	1	0	1	0	0	1

---

Таблица 6 – (-1) в степени

1	1	1	1	1	1	1	1
-1	1	-1	1	-1	1	-1	1
1	1	-1	-1	1	1	-1	-1
1	-1	-1	1	1	-1	-1	1
-1	-1	-1	-1	1	1	1	1
-1	1	-1	1	1	-1	1	-1
-1	-1	1	1	1	1	-1	-1
1	-1	-1	1	-1	1	1	-1

Таблица 7 – Сумма

0

0

-4

4

4

4

0

0

Получаем, что максимальный ПАУ по модулю равен 4: .Таким образом нелинейность рассчитывается по формуле:Существует граница значений нелинейности:В следующем этапе лабораторной работы необходимо рассчитать коэффициент корреляции. Коэффициентом корреляции R(i,j) между двумя булевыми функциями называется величина: R(i,j) = ∑ (fi*( ∙ fj*(x)),где f*(x) - сопряженная функция к булевой функции.

---

Смотрите также файлы

• Технология ремонта колесной пары 2ЭС6.docx

• 1. Проблема переработки мусора 5 Сортировка мусора 7.rtf

• Эссе. Совокупный объём деятельности и оборот розничной торговли на примере Сибирского федерального округа.docx

• 322у.docx

• Биология бойынша зерттеу жмысын йымдастыру жне іске асыру Сегізінші кн.docx