Матрица Уолша

Матрица Адамара 16-го порядка, умноженная на вектор

Естественно упорядоченная матрица Адамара, переставленная в последовательно упорядоченную матрицу Уолша. Количество изменений знака на строку в естественно упорядоченной матрице равно (0, 15, 7, 8, 3, 12, 4, 11, 1, 14, 6, 9, 2, 13, 5, 10), в последовательно упорядоченной матрице количество изменений знака является последовательным.

LDU-разложение матрицы Адамара. Единицы в треугольных матрицах образуют треугольники Серпинского . Элементы диагональной матрицы являются значениями из последовательности Гулда , причем знаки минус распределены так же, как в последовательности Туэ–Морса .

Двоичная матрица Адамара как произведение матриц . Двоичная матрица (белый 0, красный 1) — это результат с операциями в F 2 . Серые числа показывают результат с операциями в . ${\displaystyle \mathbb {N} }$

В математике матрица Уолша — это определенная квадратная матрица размерности 2 ⁿ , где n — некоторое конкретное натуральное число . Элементы матрицы равны либо +1, либо −1, а ее строки и столбцы ортогональны . Матрица Уолша была предложена Джозефом Л. Уолшем в 1923 году. ^[1] Каждая строка матрицы Уолша соответствует функции Уолша .

Матрицы Уолша являются особым случаем матриц Адамара , где строки переставлены так, что число изменений знака в строке находится в порядке возрастания. Короче говоря, матрица Адамара определяется рекурсивной формулой ниже и является естественно упорядоченной , тогда как матрица Уолша является последовательно-упорядоченной . ^[1] Сбивает с толку то, что разные источники называют любую из матриц матрицей Уолша.

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

Формула

Матрицы Адамара размерности задаются рекурсивной формулой (минимальный порядок матрицы Адамара равен 2): ${\displaystyle 2^{k}}$ ${\displaystyle k\in \mathbb {N} }$

${\displaystyle {\begin{aligned}H\left(2^{1}\right)&={\begin{bmatrix}1&1\\1&-1\end{bmatrix}},\\H\left(2^{2}\right)&={\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\\\end{bmatrix}},\end{aligned}}}$

и вообще

${\displaystyle H\left(2^{k}\right)={\begin{bmatrix}H\left(2^{k-1}\right)&H\left(2^{k-1}\right)\\H\left(2^{k-1}\right)&-H\left(2^{k-1}\right)\end{bmatrix}}=H(2)\otimes H\left(2^{k-1}\right),}$

для 2 ≤  k  ∈  N , где ⊗ обозначает произведение Кронекера .

Перестановка

Мы можем получить матрицу Уолша из матрицы Адамара. Для этого мы сначала генерируем матрицу Адамара для заданного измерения. Затем мы подсчитываем количество смен знаков каждой строки. Наконец, мы переупорядочиваем строки матрицы в соответствии с количеством смен знаков в порядке возрастания.

Например, предположим, что у нас есть матрица Адамара размерности ${\displaystyle 2^{2}}$

${\displaystyle H(4)={\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\\\end{bmatrix}}}$,

где последовательные строки имеют 0, 3, 1 и 2 смены знака (мы считаем, сколько раз мы переключаемся с положительной 1 на отрицательную 1 и наоборот). Если мы переставим строки в порядке последовательности, мы получим:

${\displaystyle W(4)={\begin{bmatrix}1&1&1&1\\1&1&-1&-1\\1&-1&-1&1\\1&-1&1&-1\\\end{bmatrix}},}$

где последовательные строки имеют 0, 1, 2 и 3 смены знака.

Альтернативные формы матрицы Уолша

Последовательность упорядочивания

Последовательный порядок строк матрицы Уолша можно получить из порядка матрицы Адамара, применив сначала перестановку с обратным порядком битов , а затем перестановку с кодом Грея : ^[2]

${\displaystyle W(8)={\begin{bmatrix}1&1&1&1&1&1&1&1\\1&1&1&1&-1&-1&-1&-1\\1&1&-1&-1&-1&-1&1&1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\1&-1&-1&1&-1&1&1&-1\\1&-1&1&-1&-1&1&-1&1\\1&-1&1&-1&1&-1&1&-1\\\end{bmatrix}},}$

где последовательные строки имеют 0, 1, 2, 3, 4, 5, 6 и 7 изменений знака.

Диадическое упорядочение

${\displaystyle W(8)={\begin{bmatrix}1&1&1&1&1&1&1&1\\1&1&1&1&-1&-1&-1&-1\\1&1&-1&-1&1&1&-1&-1\\1&1&-1&-1&-1&-1&1&1\\1&-1&1&-1&1&-1&1&-1\\1&-1&1&-1&-1&1&-1&1\\1&-1&-1&1&1&-1&-1&1\\1&-1&-1&1&-1&1&1&-1\\\end{bmatrix}},}$

где последовательные строки имеют 0, 1, 3, 2, 7, 6, 4 и 5 изменений знака.

Естественный порядок

${\displaystyle H(8)={\begin{bmatrix}1&1&1&1&1&1&1&1\\1&-1&1&-1&1&-1&1&-1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\1&1&1&1&-1&-1&-1&-1\\1&-1&1&-1&-1&1&-1&1\\1&1&-1&-1&-1&-1&1&1\\1&-1&-1&1&-1&1&1&-1\\\end{bmatrix}},}$

где последовательные строки имеют 0, 7, 3, 4, 1, 6, 2 и 5 изменений знака (матрица Адамара).

Смотрите также

• вейвлет Хаара
• Матрица квинконса
• преобразование Адамара
• Множественный доступ с кодовым разделением каналов
• OEIS : A228539 ( OEIS : A228540 ) – строки (отрицательных) двоичных матриц Уолша, читаемые как обратные двоичные числа
• OEIS : A197818 – антидиагонали инвертированной двоичной матрицы Уолша, читаемые как двоичные числа

Ссылки

1. Kanjilal, PP (1995). Адаптивное прогнозирование и прогнозное управление. Stevenage: IET. стр. 210. ISBN 0-86341-193-2.
2. Юэн, Ч.-К. (1972). «Замечания об упорядочении функций Уолша». IEEE Transactions on Computers . 21 (12): 1452. doi :10.1109/TC.1972.223524.