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

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

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

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

Див. також

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