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

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

Свойства коэффициентов УолшаПравить

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

См. такжеПравить

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