Подсчет числа перемен знаков в матрице Адамара

Аналогом частоты в базисе Фурье для матриц Адамара является число перемен знаков в строке.

Предложение. Для того, чтобы найти число перемен знаков в строке с номером в матрице Адамара, нужно сделать следующие операции:

Представить в двоичной форме

Подсчитать , где - матрица перехода от двоичного кода к коду Грея

Число перемен знаков в двоичной форме имеет вид .

Доказательство. Для утверждение проверяется непосредственно. Предположим, что оно справедливо для . Рассмотрим матрицу и ее строку с номером . Элементы этой строки подсчитываются по формуле , где .

По определению, =

. Положим . Когда пробегает все значения, знак определяется четностью скалярного произведения вектора на все коды Грея. Последние изобразим таблицей. Проходя первую половину таблицы, согласно предположению индукции, получим число перемен знаков, имеющее двоичное представление . Столько получится при прохождении второй половины таблицы. Если , то в силу зеркальности, на стыке будет еще одна перемена, в противном случае ее не будет.

При вычислении преобразования Адамара номер коэффициента можно ассоциировать с частотой, однако, не следует думать, что это действительно частота. Для этого достаточно подсчитать преобразование Адамара от .