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

Коэффициент Уолша $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(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^2_f(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^2_f(x)$.
4. Выражение коэффициентов Уолша через автокорреляционных коэффициенты: $W^2_f(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$.

См. также

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