Матрица Уолша - Walsh matrix

Матрица Уолша порядка 16, умноженная на вектор

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

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

Двоичная матрица Уолша как матричный продукт. Двоичная матрица (белый 0, красный 1) является результатом операций в F₂. Серые числа показывают результат операций в р.

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

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

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

Формула

Матрицы Адамара размерности 2^k для k ∈ N задаются рекурсивной формулой (нижний порядок матрицы Адамара равен 2):

${\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 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. Если мы переставим строки в последовательном порядке:

${\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 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, 7, 3, 4, 1, 6, 2 и 5.

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

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

Заметки

1. Канжилал П. П. (1995). Адаптивное прогнозирование и прогнозное управление. Стивенейдж: IET. п. 210. ISBN  0-86341-193-2.
2. Юэнь, Ч.-К. (1972). «Замечания о порядке функций Уолша». Транзакции IEEE на компьютерах. 21 (12): 1452. Дои:10.1109 / T-C.1972.223524.