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

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