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

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

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

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

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