Matriz de Walsh

Matriz de Hadamard de orden 16 multiplicada por un vector

Matriz de Hadamard ordenada naturalmente permutada en una matriz de Walsh ordenada secuencialmente. El número de cambios de signo por fila en la matriz ordenada naturalmente es (0, 15, 7, 8, 3, 12, 4, 11, 1, 14, 6, 9, 2, 13, 5, 10); en la matriz ordenada secuencialmente, el número de cambios de signo es consecutivo.

Descomposición LDU de una matriz de Hadamard. Los valores de las matrices triangulares forman triángulos de Sierpinski . Las entradas de la matriz diagonal son valores de la sucesión de Gould , con los signos menos distribuidos como los de la sucesión de Thue-Morse .

Matriz binaria de Hadamard como producto matricial . La matriz binaria (blanco 0, rojo 1) es el resultado con operaciones en F 2 . Los números grises muestran el resultado con operaciones en . ${\displaystyle \mathbb {N} }$

En matemáticas , una matriz de Walsh es una matriz cuadrada específica de dimensiones 2 ⁿ , donde n es un número natural particular . Las entradas de la matriz son +1 o −1 y sus filas y columnas son ortogonales . La matriz de Walsh fue propuesta por Joseph L. Walsh en 1923. ^[1] Cada fila de una matriz de Walsh corresponde a una función de Walsh .

Las matrices de Walsh son un caso especial de matrices de Hadamard, en las que las filas se reorganizan de modo que el número de cambios de signo en una fila esté en orden creciente. En resumen, una matriz de Hadamard se define mediante la fórmula recursiva que se muestra a continuación y está ordenada de forma natural , mientras que una matriz de Walsh está ordenada secuencialmente . ^[1] Resulta confuso que distintas fuentes se refieran a cada una de las matrices como la matriz de Walsh.

La matriz de Walsh (y las funciones de Walsh) se utilizan para calcular la transformada de Walsh y tienen aplicaciones en la implementación eficiente de ciertas operaciones de procesamiento de señales .

Fórmula

Las matrices de Hadamard de dimensión para se dan mediante la fórmula recursiva (el orden más bajo de la matriz de Hadamard es 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}}}$

y en general

${\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),}$

para 2 ≤  k  ∈  N , donde ⊗ denota el producto de Kronecker .

Permutación

Podemos obtener una matriz de Walsh a partir de una matriz de Hadamard. Para ello, primero generamos la matriz de Hadamard para una dimensión dada. Luego, contamos el número de cambios de signo de cada fila. Finalmente, reordenamos las filas de la matriz según el número de cambios de signo en orden ascendente.

Por ejemplo, supongamos que tenemos una matriz de Hadamard de dimensió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}}}$,

donde las filas sucesivas tienen 0, 3, 1 y 2 cambios de signo (contamos el número de veces que cambiamos de un 1 positivo a un 1 negativo y viceversa). Si reorganizamos las filas en orden secuencial, obtenemos:

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

donde las filas sucesivas tienen 0, 1, 2 y 3 cambios de signo.

Formas alternativas de la matriz de Walsh

Ordenamiento de secuencias

El ordenamiento de secuencia de las filas de la matriz de Walsh se puede derivar del ordenamiento de la matriz de Hadamard aplicando primero la permutación de inversión de bits y luego la permutación de código Gray : ^[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}},}$

donde las filas sucesivas tienen 0, 1, 2, 3, 4, 5, 6 y 7 cambios de signo.

Ordenamiento diádico

${\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}},}$

donde las filas sucesivas tienen 0, 1, 3, 2, 7, 6, 4 y 5 cambios de signo.

Ordenamiento natural

${\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}},}$

donde las filas sucesivas tienen 0, 7, 3, 4, 1, 6, 2 y 5 cambios de signo (matriz de Hadamard).

Véase también

• Ondícula de Haar
• Matriz quincuncial
• Transformación de Hadamard
• Acceso múltiple por división de código
• OEIS : A228539 ( OEIS : A228540 ): filas de las matrices binarias de Walsh (negadas) leídas como números binarios inversos
• OEIS : A197818 – antidiagonales de la matriz binaria negada de Walsh leídas como números binarios

Referencias

1. Kanjilal, PP (1995). Predicción adaptativa y control predictivo. Stevenage: IET. pág. 210. ISBN 0-86341-193-2.
2. Yuen, C.-K. (1972). "Observaciones sobre el ordenamiento de las funciones de Walsh". IEEE Transactions on Computers . 21 (12): 1452. doi :10.1109/TC.1972.223524.