Коэффициент Уолша булевой функции — это величина , где . Коэффициенты Уолша являются спектральной характеристикой булевой функции, то есть являются аналогом коэффициентов Фурье. Вычисление коэффициентов Уолша Коэффициенты Уолша могут быть вычислены за действий. Для этого нужно в начале проинициализировать массив : . После чего для каждой координаты и для каждой пары точек и , отличающихся по -й координате, нужно заменить значения и на и (считаем, что у -й бит сброшен, а у установлен). Окончательное состояние массива и будет коэффициентами Уолша.
Свойства коэффициентов Уолша Формула обращения: . Равенство Парсеваля: . Формула для автокорреляционных коэффициентов (): . Выражение коэффициентов Уолша через автокорреляционных коэффициенты: . Формула для нелинейности булевой функции: . Теорема Титсворта: . Вместе с равенством Парсеваля это тождество является необходимым и достаточным условием того, что набор коэффициетов Уолша задает какую-то булеву функцию. Тождество Саркара: , где означает доминирование, то есть что все единичные биты содержатся среди единичных битов , означает вес функции (количество наборов, на которых функция равна 1), означает функцию полученную подстановкой вместо нуля для всех при которых .
См. также Функция Уолша
Категория:Дискретная математика