La transformada de Hadamard (también conocida como transformada de Walsh-Hadamard , transformada de Hadamard-Rademacher-Walsh , transformada de Walsh o transformada de Walsh-Fourier ) es un ejemplo de una clase generalizada de transformadas de Fourier . Realiza una operación ortogonal , simétrica , involutiva y lineal en números reales de 2 m (o números complejos o hipercomplejos , aunque las matrices de Hadamard en sí son puramente reales).
Se puede considerar que la transformada de Hadamard está construida a partir de transformadas discretas de Fourier (DFT) de tamaño 2 y, de hecho, es equivalente a una DFT multidimensional de tamaño 2 × 2 × ⋯ × 2 × 2 . [2] Descompone un vector de entrada arbitrario en una superposición de funciones de Walsh .
La transformada lleva el nombre del matemático francés Jacques Hadamard ( francés: [adamaʁ] ), el matemático germano-estadounidense Hans Rademacher y el matemático estadounidense Joseph L. Walsh .
La transformada de Hadamard H m es una matriz de 2 m × 2 m , la matriz de Hadamard (escalada por un factor de normalización), que transforma 2 m de números reales x n en 2 m de números reales X k . La transformada de Hadamard se puede definir de dos maneras: recursivamente o utilizando la representación binaria ( base -2) de los índices n y k .
Recursivamente, definimos la transformada de Hadamard 1 × 1 H 0 por la identidad H 0 = 1, y luego definimos H m para m > 0 por:
Para m > 1, también podemos definir H m por:
De manera equivalente, podemos definir la matriz de Hadamard por su ( k , n )-ésima entrada escribiendo
donde k j y n j son los elementos de bits (0 o 1) de k y n , respectivamente. Tenga en cuenta que para el elemento en la esquina superior izquierda, definimos: . En este caso tenemos:
Esta es exactamente la DFT multidimensional, normalizada para ser unitaria , si las entradas y salidas se consideran matrices multidimensionales indexadas por n j y k j , respectivamente.
A continuación se muestran algunos ejemplos de las matrices de Hadamard.
H 1 es precisamente el DFT de tamaño 2. También puede considerarse como la transformada de Fourier en el grupo aditivo de dos elementos de Z /(2).
Las filas de las matrices de Hadamard son las funciones de Walsh .
De acuerdo con la definición anterior de matriz H , aquí dejamos que H = H [ m , n ]
En la transformada de Walsh, solo aparecerán 1 y −1 en la matriz. Los números 1 y −1 son números reales, por lo que no es necesario realizar un cálculo con números complejos .
La DFT necesita una multiplicación irracional, mientras que la transformada de Hadamard no. Incluso la multiplicación racional no es necesaria, ya que basta con invertir signos.
En la matriz de transformación de Walsh, todas las entradas de la primera fila (y columna) son iguales a 1.
Transformada discreta de Fourier:
En la transformada discreta de Fourier, cuando m es igual a ceros (media primera fila), el resultado de DFT también es 1. En la segunda fila, aunque es diferente a la primera fila podemos observar una característica de la matriz de que la señal en la La primera matriz sin procesar es de baja frecuencia y aumentará la frecuencia en la segunda fila, aumentará más frecuencia hasta la última fila.
Si calculamos el cruce por cero:
Primera fila = 0 cruce por ceroSegunda fila = 1 cruce por ceroTercera fila = 2 cruces por cero ⋮Ocho filas = 7 cruces por cero
De hecho, la transformada de Hadamard es equivalente a una DFT multidimensional de tamaño 2 × 2 × ⋯ × 2 × 2 . [2]
Otro enfoque es ver la transformada de Hadamard como una transformada de Fourier en el grupo booleano . [3] [4] Usando la transformada de Fourier en grupos finitos (abelianos) , la transformada de Fourier de una función es la función definida por
Esta es la transformada de Hadamard de , considerando la entrada a y como cadenas booleanas.
En términos de la formulación anterior, donde la transformada de Hadamard multiplica un vector de números complejos a la izquierda por la matriz de Hadamard, la equivalencia se ve tomando como entrada la cadena de bits correspondiente al índice de un elemento de y teniendo como salida el correspondiente elemento de .
Compare esto con la transformada discreta habitual de Fourier que, cuando se aplica a un vector de números complejos, utiliza caracteres del grupo cíclico .
En el dominio clásico, la transformada de Hadamard se puede calcular en operaciones ( ), utilizando el algoritmo rápido de transformada de Hadamard .
En el dominio cuántico, la transformada de Hadamard se puede calcular en el tiempo, ya que es una puerta lógica cuántica que se puede paralelizar .
La transformada de Hadamard se utiliza ampliamente en computación cuántica . La transformada de Hadamard 2 × 2 es la puerta lógica cuántica conocida como puerta de Hadamard, y la aplicación de una puerta de Hadamard a cada qubit de un registro -qubit en paralelo es equivalente a la transformada de Hadamard .
En computación cuántica, la puerta de Hadamard es una rotación de un qubit , que asigna los estados básicos del qubit a dos estados de superposición con el mismo peso de los estados básicos computacionales y . Generalmente las fases se eligen de modo que
en notación de Dirac . Esto corresponde a la matriz de transformación.
Una aplicación de la puerta de Hadamard a un qubit 0 o 1 producirá un estado cuántico que, si se observa, será 0 o 1 con la misma probabilidad (como se ve en las dos primeras operaciones). Esto es exactamente como lanzar una moneda al aire en el modelo de cálculo probabilístico estándar . Sin embargo, si la puerta de Hadamard se aplica dos veces seguidas (como se hace efectivamente en las dos últimas operaciones), entonces el estado final es siempre el mismo que el estado inicial.
Calcular la transformada cuántica de Hadamard es simplemente la aplicación de una puerta de Hadamard a cada qubit individualmente debido a la estructura del producto tensorial de la transformada de Hadamard. Este simple resultado significa que la transformada cuántica de Hadamard requiere operaciones, en comparación con el caso clásico de operaciones.
Muchos algoritmos cuánticos utilizan la transformada de Hadamard como paso inicial, ya que asigna m qubits inicializados con una superposición de los 2 m estados ortogonales en la base con el mismo peso. Por ejemplo, esto se utiliza en el algoritmo de Deutsch-Jozsa , el algoritmo de Simon , el algoritmo de Bernstein-Vazirani y en el algoritmo de Grover . Tenga en cuenta que el algoritmo de Shor utiliza tanto una transformada inicial de Hadamard como la transformada cuántica de Fourier , que son ambos tipos de transformadas de Fourier en grupos finitos ; el primero y el segundo .
La transformada de Hadamard se puede utilizar para estimar árboles filogenéticos a partir de datos moleculares. [5] [6] [7] La filogenética es el subcampo de la biología evolutiva centrado en comprender las relaciones entre organismos. Se puede utilizar una transformada de Hadamard aplicada a un vector (o matriz) de frecuencias de patrón de sitios obtenidas a partir de un alineamiento de secuencias múltiples de ADN para generar otro vector que transporte información sobre la topología del árbol. La naturaleza invertible de la transformada filogenética de Hadamard también permite el cálculo de las probabilidades de sitio a partir de un vector de topología de árbol, lo que permite utilizar la transformada de Hadamard para la estimación de máxima probabilidad de árboles filogenéticos. Sin embargo, esta última aplicación es menos útil que la transformación del vector de patrón de sitio al vector de árbol porque hay otras formas de calcular las probabilidades de sitio [8] [9] que son mucho más eficientes. Sin embargo, la naturaleza invertible de la transformada filogenética de Hadamard proporciona una herramienta elegante para la filogenética matemática. [10] [11]
La mecánica de la transformada filogenética de Hadamard implica el cálculo de un vector que proporciona información sobre la topología y las longitudes de las ramas del árbol utilizando el vector o matriz de patrón de sitio .
La naturaleza invertible de esta ecuación permite calcular un vector (o matriz) de patrón de sitio esperado de la siguiente manera:
Podemos utilizar el modelo de sustitución de dos estados de Cavender-Farris- Neyman (CFN) para el ADN codificando los nucleótidos como caracteres binarios (las purinas A y G están codificadas como R y las pirimidinas C y T están codificadas como Y). Esto hace posible codificar la alineación de secuencia múltiple como el vector de patrón de sitio que se puede convertir en un vector de árbol , como se muestra en el siguiente ejemplo:
El ejemplo que se muestra en esta tabla utiliza el esquema simplificado de tres ecuaciones y es para un árbol de cuatro taxones que se puede escribir como ((A,B),(C,D)); en formato newick . Los patrones del sitio están escritos en el orden ABCD. Este árbol en particular tiene dos ramas terminales largas (0,2 sustituciones de transversión por sitio), dos ramas terminales cortas (0,025 sustituciones de transversión por sitio) y una rama interna corta (0,025 sustituciones de transversión por sitio); así, se escribiría como ((A:0.025,B:0.2):0.025,(C:0.025,D:0.2)); en formato newick. Este árbol exhibirá atracción por ramas largas si los datos se analizan utilizando el criterio de máxima parsimonia (asumiendo que la secuencia analizada es lo suficientemente larga como para que las frecuencias del patrón del sitio observado estén cerca de las frecuencias esperadas que se muestran en la columna). La atracción de las ramas largas refleja el hecho de que el número esperado de patrones de sitio con índice 6, que sostienen el árbol ((A,C),(B,D)); -- exceder el número esperado de patrones de sitios que soportan el árbol verdadero (índice 4). Obviamente, la naturaleza invertible de la transformada filogenética de Hadamard significa que el vector de árbol significa que el vector de árbol corresponde al árbol correcto. Por lo tanto, el análisis de parsimonia después de la transformación es estadísticamente consistente , [13] como lo sería un análisis de máxima verosimilitud estándar utilizando el modelo correcto (en este caso, el modelo CFN).
Tenga en cuenta que el patrón de sitios con 0 corresponde a los sitios que no han cambiado (después de codificar los nucleótidos como purinas o pirimidinas). Los índices con asteriscos (3, 5 y 6) son "informativos de parsimonia" y. los índices restantes representan patrones de sitio donde un solo taxón difiere de los otros tres taxones (por lo que son el equivalente a las longitudes de las ramas terminales en un árbol filogenético estándar de máxima probabilidad).
Si se desea utilizar datos de nucleótidos sin recodificar como R e Y (y en última instancia como 0 y 1), es posible codificar los patrones de sitio como una matriz. Si consideramos un árbol de cuatro taxones, hay un total de 256 patrones de sitios (cuatro nucleótidos elevados a la cuarta potencia). Sin embargo, las simetrías del modelo de tres parámetros de Kimura (o K81) nos permiten reducir los 256 patrones de sitios posibles para el ADN a 64 patrones, lo que hace posible codificar los datos de nucleótidos para un árbol de cuatro taxones como una matriz de 8 × 8 . 14] de una manera similar al vector de 8 elementos utilizado anteriormente para los patrones de sitio de transversión (RY). Esto se logra recodificando los datos utilizando el grupo de cuatro de Klein :
Al igual que con los datos de RY, los patrones de sitio están indexados en relación con la base en el primer taxón elegido arbitrariamente y las bases de los taxones posteriores codificadas en relación con esa primera base. Por tanto, el primer taxón recibe el par de bits (0,0). Usando esos pares de bits se pueden producir dos vectores similares a los vectores RY y luego poblar la matriz usando esos vectores. Esto se puede ilustrar usando el ejemplo de Hendy et al. (1994), [14] que se basa en un alineamiento de secuencias múltiples de cuatro pseudogenes de hemoglobina de primates:
El número mucho mayor de patrones de sitio en la columna 0 refleja el hecho de que la columna 0 corresponde a diferencias de transición , que se acumulan más rápidamente que las diferencias de transversión en prácticamente todas las comparaciones de regiones genómicas (y definitivamente se acumulan más rápidamente en los pseudogenes de hemoglobina utilizados para este ejemplo elaborado). [15] ). Si consideramos el patrón de sitio AAGG, sería el patrón binario 0000 para el segundo elemento del par de bits del grupo Klein y 0011 para el primer elemento. en este caso, el patrón binario basado en el primer elemento corresponde al índice 3 (por lo tanto, la fila 3 en la columna 0; indicada con un solo asterisco en la tabla). Los patrones de sitio GGAA, CCTT y TTCC se codificarían exactamente de la misma manera. El patrón de sitio AACT se codificaría con el patrón binario 0011 basado en el segundo elemento y 0001 basado en el primer elemento; esto produce el índice 1 para el primer elemento y el índice 3 para el segundo. El índice basado en el segundo par de bits del grupo Klein se multiplica por 8 para obtener el índice de la columna (en este caso sería la columna 24). La celda que incluiría el recuento de patrones de sitios AACT se indica con dos asteriscos; sin embargo, la ausencia de un número en el ejemplo indica que la alineación de secuencia no incluye patrones de sitios AACT (de la misma manera, los patrones de sitios CCAG, GGTC y TTGA, que se codificarían de la misma manera, están ausentes).
La transformada de Hadamard también se utiliza en el cifrado de datos , así como en muchos algoritmos de procesamiento de señales y compresión de datos , como JPEG XR y MPEG-4 AVC . En aplicaciones de compresión de video , generalmente se usa en forma de suma de diferencias transformadas absolutas . También es una parte crucial de un número significativo de algoritmos en la computación cuántica. La transformada de Hadamard también se aplica en técnicas experimentales como RMN , espectrometría de masas y cristalografía . Además, se utiliza en algunas versiones de hash sensible a la localidad , para obtener rotaciones de matrices pseudoaleatorias.
{{cite journal}}
: Citar diario requiere |journal=
( ayuda )