Вопросы к зачету часть3 (1085485), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

HH^T=nЕ ,

где H^T- транспонированная матрица H и Е — единичная матрица.

Матрица Адамара обладает следующими свойствами.

1. .

2. HH^T = H^TH .

Имеем HH^T = H^-1HH^TH=nЕ.

3. Если H₁,…,H_n - строки, H⁽¹⁾,…,H⁽ⁿ⁾ – столбцы матрицы H, (H_i,H_j) и (H⁽ⁱ⁾,H^(j)) – скалярные произведения соответствующих векторов, то

.

4 .

Отметим, что каждое из четырех условий при h_ij= является характеристическим, т.е. определяет все остальные свойства и, стало быть, определяет матрицу Адамара.

4. Перестановка строк или столбцов, умножение на -1 строк или столбцов переводят матрицу Адамара снова в матрицу Адамара.

5. Для существования матрицы Адамара порядка n, необходимо, чтобы либо n = 1,2 , либо n0(mod 4).

При n=1 и n=2 матрицы Адамара существуют и имеют вид

с точностью до перестановки строк, столбцов и умножения их на –1.

Используя свойство 4 любую матрицу Адамара порядка n можно привести к нормализованному виду, при котором матрица Адамара имеет первую строку и первый столбец, состоящие только из единиц. Рассмотрим первые три строки матрицы Адамара , приведенной к нормализованному виду. Соответствующая подматрица 3n матрицы имеет столбцы вида

x,y,z, Если число таких столбцов в подматрице 3 n равно соответственно w, то имеют место следующие соотношения

x+y+z+w=n

x+z=y+w

x+y=z+w

x+w=y+z .

Первое равенство означает, что общее число столбцов равно n. Последующие равенства следуют из ортогональности 1 и 2 строк, 1 и 3 строк, 2 и 3 строк подматрицы 3 n. Нетрудно убедиться (например, приведением матрицы системы к треугольному виду методом Гаусса), что детерминант приведенной системы линейных уравнений относительно неизвестных x, y, z, w отличен от нуля и, стало быть, эта система имеет единственное решение: x=y=z=w=n/4. Следовательно, n0(mod 4).

Кронекеровское произведение матриц A=(aij), i,j=1,2,…,n; B=(bij), i,j=1,2,…,m определяется равенством

.

6. Если Hm и Hn — матрицы Адамара, то их кронекеровское произведение - снова матрица Адамара.

Из свойств кронекеровского произведения следует, что элементы матрицы равны ± 1. Кроме того,

где Еm - единичная матрица порядка m.

2. Матрицы Силъвестра-Адамара их свойства.

Матрицы Сильвестра-Адамара имеют порядок n, где n=2k, k=1, 2,…, n и определяются рекурретным соотношением

k=1, 2,… ,

где

.

Матрица Сильвестра-Адамара обладает свойством симметричности, а именно

,

что следует из ее определения.

Независимо от свойства 6 можно убедиться, что матрица H2k действительно является матрицей Адамара. Доказательство можно провести индукцией по к. Имеем: Н2- матрица Адамара ,

.

В силу равенства

для обратной матрицы имеем выражение

.

Рассмотрим совокупность всех двоичных m -мерных векторов V0, V1,…, V2m-1, координаты которых принимают значения 0 или 1. Будем предполагать, что эти векторы расположены в порядке возрастания чисел, для которых они являются двоичными представлениями. Для векторов Vi=(Vi(1),…,Vi(m)), Vj=(Vj(1),…,Vj(m)) будем рассматривать их скалярные произведения

,

где сложение ведется по модулю 2. Покажем, что матрица

есть матрица Силъвестра-Адамара. Доказательство проведем индукцией по m. При m=1 утверждение верно, так как матрица H₂ имеет вид

.

Введем обозначения

.

Матрицу H₂^m+1 представим в виде

где

, , ,

где (0,0), (0,1), (1,0), (1,1) - скалярные произведения векторов размерности единица, . Очевидно, что

,

где - матрица Сильвестра-Адамара порядка 2^m . Следовательно,

и - матрица Сильвестра-Адамара порядка 2^m+1 .

3. Преобразования Уолша-Адамара булевых функций.

Булеву функцию f определим отображением

f : [GF(2)]ⁿ  GF(2),

где GF(2) есть n–я декартова степень множества GF(2).

Пусть [GF(2)]ⁿ = , где векторы расположены в порядке возрастания чисел, для которых они являются двоичными разложениями.

Вектор

называется таблицей истинности булевой функции .

Вектор

.

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

Преобразованием Уолша-Адамара булевой функции называется вектор

,

координаты которого для всех двоичных векторов U₀,…,U₂^m_-1 определяются равенством

,

где и скалярное произведение вычисляется по модулю 2.

Из этих определений и записи матрицы Сильвестра-Адамара порядка следует, что

. (1)

Из этого равенства и равенства следует, что

.

Следовательно,

для любого двоичного вектора U размерности m. Это равенство определяет обратное преобразование Уолша-Адамара.

Для булевой функции , множество

будем называть весовым спектром функции.

Пусть булевы функции и связаны равенством

,

где - обратимая двоичная матрица и двоичный вектор размерности . В этом случае говорят, что функция получается из функции аффинным преобразованием переменных. Имеем

, _,

где . Покажем, что в этом случае весовые спектры функций f(V) и g(V) совпадают.

Положим V=A^-1w+A^-1b. Тогда

где U^/=UA^-1 для всех .

Равенство Парсеваля

следует из цепочки равенств

.

Аналогичным образом из равенств

вытекает равенство Парсеваля для векторов :

.

Для преобразований Уолша-Адамара имеет место соотношение ортогональности

.

ДОКАЖЕМ этот факт. Действительно,

где (W,x) - символ Кронекера.

Из доказанного равенства при V=0 следует равенство Парсеваля

.

В заключение данного пункта изложим трактовку значений преобразования Уолша-Адамара связанную с понятием расстояния Хэмминга между функциями.

Если U=(U₁,U₂,…,U_m), V=(V₁,V₂,…,V_m ), то скалярное произведение

представляет собой линейную функцию U от переменных x₁=V₁, x₂=V₂,…, x_m=V_m. В силу равенства

с учетом того, что

преобразование Уолша-Адамара определяет разность между числом совпадений и несовпадений булевой функци и f(V)=f(x₁, x₂,…,x_m) с линейной фикцией

Расстояние Хэмминга между функциями f и g определяется равенством

.

Нетрудно проверить, что d является метрикой на множестве булевых функций.

Из равенства

имеем

.

Поэтому

.

Аналогичным образом следует, что если есть дополнение линейной функции , т.е. аффинная функция, то

.

Таким образом, расстояние функции f до линейной или аффинной функции является минимальным тогда и только тогда, когда величина достигает максимального значения.

4. Преобразование Фурье булевой функции.

Для булевой функции f(V), имеющей таблицу истинности f=(f(V₀),…,f(V₂^m_-1)), где векторы V₀,…,V₂^m_-1 расположены в порядке возрастания чисел, для которых они являются двоичными разложениями, преобразование Фурье определяется как вектор

C_f=(C_f(U₀), C_f(U₁),… C_f(U₂^m_-1)),

где {U₀, U₁,…, U₂^m_-1} совокупность всех двоичных векторов, а координаты C_f(U) определяются равенством

где, как и ранее, скалярное произведение (U,V) вычисляется по модулю 2.

Числа C_f(U) называются коэффициентами Фурье булевой функции f.

Из последнего равенства следует, что

, (2)

где H - матрица Сильвестра-Адамара порядка 2^m. А так как из соотношения (2) следует, что

то для коэффициентов Фурье получаем следующую формулу

Рассмотрим некоторые свойства коэффициентов Фурье булевой функции.

1⁰. ,

где C_f(0) - значение коэффициента Фурье булевой функции f для нулевого вектора, a вес булевой функции f, т.е. число таких значений , для которых f(V)=1.

Из свойства 1° следует, что булева функция f является cбалансирован-ной (равновероятной) тогда и только тогда, когда для нулевого коэффициента Фурье имеет место равенство

.

2°. Для любого вектора имеет место равенство

.

3°. Для любого вектора имеет место соотношение

,

где P(f(V)=(U,V)) — вероятность совпадения значений булевой функции с линейной функцией (U,V) при случайном равновероятном выборе вектора , скалярное произведение (U,V) вычисляется по модулю 2.

ДОКАЖЕМ 3°. Действительно, имеем

Таким образом,

.

Отсюда вытекает требуемое равенство из свойства 3° .

В криптографических исследованиях иногда используют вектор

координаты которого связаны с коэффициентами Фурье равенством

Вектор называется статистистической структурой булевой функции, а его координаты - коэффициентами статистической cтруктуры этой функции. Для U=0 обычно полагают

.

4°. Для коэффициентов Фурье булевой функции имеет место соотношение

ДОКАЖЕМ это равенство, действительно, из равенства (2) следует, что

.

Из доказанного сейчас равенства для коэффициентов статистической структуры вытекает равенство Парсеваля

.

Из формул и для коэффициентов Фурье булевой функции получаем, что для

Из равенств и следует, что

Для коэффициентов статистической структуры имеют место неравенства

Характеристики

Список файлов ответов (шпаргалок)