MERSENNE-WALSH MATRICES

Z-TRANSFORMATION



Zome picturing around matrix Z=diag(1,-1,1,-1...)




Z*Z = I, so Z is root of I; CHESS=Z*J*Z looks like board chess



N=Z*M*Z we can calculate as N=M.*CHESS или N=CHESS.*M, where .* is Hadamard product (point by point multiplication). Let M be core of Mersenne-Walsh matrix.



N=Z*M*Z=M.*CHESS=N=CHESS.*M overturns M (twin flip)


CHESS makes from filter of low frequence the filter of high frequence. We see this stroboscopy effect in cinemathograph, when wheels of cars, they run slowly and just backwards.

Two level {a=1, –b}, b<a, quasi-orthogonal matrices of orders (Mersenne numbers) n = 2k–1= 3, 7, 15, 31, 63, 127, … (OEIS-sequence A000225). Mersenne-Walsh matrices follow prime and non prime numbers. Mersenne matrices of orders n = 2k–1 exist. Look also: Fermat matrices.



Matrix H32





Matrices M7 and M31 (M31 level b=0.738796, m-norm is 0.203332)

DESCRIPTION (IN RUSSIAN)


Матрицы Мерсенна-Уолша: матрицы порядков n=2k–1, отличаются от матриц Мерсенна, получаемых алгоритмом Сильвестра, сортировкой.

Двухуровневые функции Уолша: cледуя идее Хармута (Harmuth, 1969), столбцы матрицы Мерсенна-Уолша отвечают последовательно нечетным Sal(n,k) и четным Cal(n,k) ортогональным функциям, но в отличие от обычной их дефиниции, это функции двухуровневые {1, –b}, параметр b=t/(t+sqrt(t)), n=4t–1. Альтерантивная запись b=1/2 при n=3, b=(q–2q1/2)/(q–4), q=n+1 (порядок матриц Адамара) при n>3.

В отличие от базисов, производных от матриц Адамара, ряд функций Мерсенна-Уолша стартует с полного периода "синуса". Базис ортогонального преобразования удобен для построения настраиваемых полосовых фильтров Мерсенна, в частности, фильтра высокой частоты (ФВЧ Мерсенна). Пример задач, где очищают низкие частоты – убирание блеклых пятен фона. Скажем, при чтении текстов низкая частота ненужна, неинформативна.

Инверстная разновидность матрицы Мерсенна –M отличается только знаком, функции осциллируют в пределах {b, –1}, можно построить также к ним близкие базисы, опираясь на сопряженные матрицы Мерсенна ZMZ и –ZMZ с удвоенным числом уровней.



Двухуровневые функции Мерсенна-Уолша массива M



Четырехуровневые функции Мерсенна-Уолша массива ZMZ


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

Система функций Мерсенна–Уолша – двухуровневая, такая же, как и классическая система. Она отличается от функций Уолша пониженным по амплитуде нижним значением –b, которое с ростом размерности системы стремится к –1. В этом смысле она отличается от системы функций Уолша, но является достаточно близкой аппроксимацией ее на нечетных значениях порядка. Систему функций Мерсенна–Уолша отличает также пониженное на единицу число порождающих ее элементов столбцов матрицы Мерсенна, т.е. она проще классической для вычисления.

Любой базис отличает предпочтительная область его применения. Система функций Мерсенна–Уолша более высокочастотная, чем система функций Уолша, в ее составе нет функции нулевой частоты (константы).

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

Заметим, в четырехуровневой конструкции появляется функция, относительно более близкая к постоянной составляющей (последняя функция). Такая система представляет собой компромисс между функциями Уолша и двухуровневыми функциями Мерсенна-Уолша.

СТАТЬЯ ВО ВКИТ

СОПРЯЖЕННЫЙ БАЗИС ЭЙЛЕРА-УОЛША


ОБЗОР БАЗИСА УОЛША-РАДЕМАХЕРА


Систему ортогональных меандров предложил Ганс Радемахер в 1822 году: Rk(t)=sign(sin(2kπt)), где t – безразмерное время. Ниже дан график до округления.



Система функций Радемахера ортонормирована на интервале [0,1], но неполна (синусы без косинусов). Дополнить ее с помощью косинусов тех же частот получается порядка до восьмого, а в общем условие ортогональности противоречит такой периодичности выборки. В 1923 году американский ученый Уолш получил полную систему ортонормированных функций, дополняя систему функций Радемахера: W0=R0, W1=R1, W2=R2, W3=R1R2, и т.п. На практике их находят, систематизируя строки матриц Адамара последовательности Сильвестра: ниже матрица до и после систематизации.


ФУНКЦИИ РАДЕМАХЕРА | ВИКИ


Литература

1. Harmuth, H. F. "Applications of Walsh Functions in Communications." IEEE Spectrum 6, 82-91, 1969.

Rambler's Top100