Коэффициент Уолша

Материал из Википедии — свободной энциклопедии

Для улучшения статьи желательно:

Найти и установить ссылки из других статей Википедии

Коэффициент Уолша $W f (u)$ булевой функции $f$ — это величина $\sum_{x\in F_2^n}(-1)^{f(x)+<u,x>}$ , где $<a,b>=\sum_{i=1}^{n}a_ib_i$ . Коэффициенты Уолша являются спектральной характеристикой булевой функции, то есть являются аналогом коэффициентов Фурье.

[править] Вычисление коэффициентов Уолша

Коэффициенты Уолша могут быть вычислены за $O (n 2 n)$ действий. Для этого нужно в начале проиницилизировать массив $a$ : $a [x] = ( - 1) f (x)$ . После чего для каждой координаты $i$ и для каждой пары точек $x$ и $y$ , отличающихся по $i$ -той координате, нужно заменить значения $a [x]$ и $a [y]$ на $a [x] + a [y]$ и $a [x] - a [y]$ (считаем, что у $x$ $i$ -тый бит сброшен, а у $y$ установлен). Окончательное состояние массива $a$ и будет коэффициентами Уолша.

[править] Свойства коэффициентов Уолша

Формула обращения: $(-1)^{f(x)}=2^{-n}\sum_{u\in F_2^n}W_f(u)(-1)^{<u,x>}$ .
Равенство Парсеваля: $\sum_{u\in F_2^n}W^2_f(u)=2^{2n}$ .
Формула для автокорреляционных коэффициентов ( $\Delta_f(u)=\sum_{x\in F_2^n}(-1)^{f(x)+f(x+u)}$ ): $\Delta_f(u)=-2^n+2^{1-n}\sum_{x\in F_2^n, 2|<x,u>}W^2_f(x)$ .
Выражение коэффициентов Уолша через автокорреляционных коэффициенты: $W^2_f(x)=\sum_{u\in F_2^n}(-1)^{<x,u>}\Delta_f(u)$ .
Формула для нелинейности булевой функции: $nl(f)=2^{n-1}-\frac{1}{2}\max_{u\in F_2^n}|W_f(u)|$ .
Теорема Титсворта: $\sum_{u\in F_2^n}W_f(u)W_f(u+s)=0$ . Вместе с равенством Парсеваля это тождество является необходимым и достаточным условием того, что набор коэффициетов Уолша задает какую-то булеву функцию.
Тождество Саркара: $\sum_{u\in F_2^n, u\in w}W_f(u)=2^n-2^{|w|+1}wt(f_w)$ , где $u\in w$ означает доминирование, то есть что все единичные биты $u$ содержатся среди единичных битов $w$ , $w t (f)$ означает вес функции (количество наборов, на которых функция равна 1), $f w$ означает функцию полученную подстановкой вместо $x i$ нуля для всех $i$ при которых $w i = 1$ .