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

Коэффициент Уолша $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(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. Формула обращения: $(-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. Формула для автокорреляционных коэффициентов (${\mathrm{\Delta }}_f(u)=\sum _{x\in F_2^n}(-1{)}^{f(x)+f(x+u)}$): ${\mathrm{\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>}{\mathrm{\Delta }}_f(u)$.
5. Формула для нелинейности булевой функции: $nl(f)=2^{n-1}-\frac{1}{2}\underset{u\in F_2^n}{\max }|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$.

См. также

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