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

Коефіцієнт Уолша $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)}$. Після чого для кожної координати $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. Формула для автокореляційних коефіцієнтів $({\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$.

Див. також

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