Коефіцієнт Уолша

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

Обчислення коефіцієнтів Уолша

Коефіцієнти Уолша можуть бути обчислені за $O(n2^{n})$ дій. Для цього потрібно на початку проініціалізувати масив $a$: $a[x]=(-1)^{f(x)}$. Після чого для кожної координати $a$: $a[x]=(-1)^{f(x)}$ і для кожної пари точок $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. Формула для автокореляційних коефіцієнтів $\left(\Delta _{f}(u)=\sum _{x\in F_{2}^{n}}(-1)^{f(x)+f(x+u)}\right)$: $\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$.

Див. також

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