Русская Википедия:Коэффициент Уолша

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Коэффициент Уолша <math>W_f(u)</math> булевой функции <math>f</math> — это величина <math>\sum_{x\in F_2^n}(-1)^{f(x)+<u,x>}</math>, где <math><a,b>=\sum_{i=1}^{n}a_ib_i</math>. Коэффициенты Уолша являются спектральной характеристикой булевой функции, то есть являются аналогом коэффициентов Фурье.

Вычисление коэффициентов Уолша

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

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

1. Формула обращения: <math>(-1)^{f(x)}=2^{-n}\sum_{u\in F_2^n}W_f(u)(-1)^{<u,x>}</math>.
2. Равенство Парсеваля: <math>\sum_{u\in F_2^n}W^2_f(u)=2^{2n}</math>.
3. Формула для автокорреляционных коэффициентов (<math>\Delta_f(u)=\sum_{x\in F_2^n}(-1)^{f(x)+f(x+u)}</math>): <math>\Delta_f(u)=-2^n+2^{1-n}\sum_{x\in F_2^n, 2|<x,u>}W^2_f(x)</math>.
4. Выражение коэффициентов Уолша через автокорреляционных коэффициенты: <math>W^2_f(x)=\sum_{u\in F_2^n}(-1)^{<x,u>}\Delta_f(u)</math>.
5. Формула для нелинейности булевой функции: <math>nl(f)=2^{n-1}-\frac{1}{2}\max_{u\in F_2^n}|W_f(u)|</math>.
6. Теорема Титсворта: <math>\sum_{u\in F_2^n}W_f(u)W_f(u+s)=0</math>. Вместе с равенством Парсеваля это тождество является необходимым и достаточным условием того, что набор коэффициетов Уолша задает какую-то булеву функцию.
7. Тождество Саркара: <math>\sum_{u\in F_2^n, u\in w}W_f(u)=2^n-2^{|w|+1}wt(f_w)</math>, где <math>u\in w</math> означает доминирование, то есть что все единичные биты <math>u</math> содержатся среди единичных битов <math>w</math>, <math>wt(f)</math> означает вес функции (количество наборов, на которых функция равна 1), <math>f_w</math> означает функцию полученную подстановкой вместо <math>x_i</math> нуля для всех <math>i</math> при которых <math>w_i=1</math>.

См. также

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