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

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

Вычисление коэффициентов Уолша

Коэффициенты Уолша могут быть вычислены за $O(n2^{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. Формула обращения: $(-1)^{f(x)}=2^{-n}\sum _{u\in F_{2}^{n}}W_{f}(u)(-1)^{<u,x>}$.
2. Равенство Парсеваля: $\sum _{u\in F_{2}^{n}}W_{f}^{2}(u)=2^{2n}$.
3. Формула для автокорреляционных коэффициентов ($\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_{f}^{2}(x)$.
4. Выражение коэффициентов Уолша через автокорреляционных коэффициенты: $W_{f}^{2}(x)=\sum _{u\in F_{2}^{n}}(-1)^{<x,u>}\Delta _{f}(u)$.
5. Формула для нелинейности булевой функции: $nl(f)=2^{n-1}-{\frac {1}{2}}\max _{u\in F_{2}^{n}}|W_{f}(u)|$.
6. Теорема Титсворта: $\sum _{u\in F_{2}^{n}}W_{f}(u)W_{f}(u+s)=0$. Вместе с равенством Парсеваля это тождество является необходимым и достаточным условием того, что набор коэффициетов Уолша задает какую-то булеву функцию.
7. Тождество Саркара: $\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$, $wt(f)$ означает вес функции (количество наборов, на которых функция равна 1), $f_{w}$ означает функцию полученную подстановкой вместо $x_{i}$ нуля для всех $i$ при которых $w_{i}=1$.

См. также

• Функция Уолша