Transformación de Hadamard

Cambio involutivo de base en álgebra lineal

El producto de una función booleana y una matriz de Hadamard es su espectro de Walsh: ^[1]
(1, 0, 1, 0, 0, 1, 1, 0) × H(8) = (4, 2, 0, −2, 0, 2, 0, 2)

Transformada rápida de Walsh-Hadamard , una forma más rápida de calcular el espectro de Walsh de (1, 0, 1, 0, 0, 1, 1, 0).

La función original puede expresarse mediante su espectro de Walsh como un polinomio aritmético.

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 sobre 2 ^m números reales (o complejos o hipercomplejos , aunque las matrices de Hadamard en sí mismas son puramente reales).

La transformada de Hadamard puede considerarse como construida a partir de transformadas de Fourier discretas (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 recibe su nombre del matemático francés Jacques Hadamard ( en francés: [adamaʁ] ), el matemático germano-estadounidense Hans Rademacher y el matemático estadounidense Joseph L. Walsh .

Definición

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 números reales x _n en 2 ^m 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 .

De forma recursiva, definimos la transformada de Hadamard 1 × 1 H ₀ por la identidad H ₀ = 1, y luego definimos H _m para m  > 0 por: donde 1/ √ 2 es una normalización que a veces se omite. $${\displaystyle H_{m}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}H_{m-1}&H_{m-1}\\H_{m-1}&-H_{m-1}\end{pmatrix}}}$$

Para m  > 1, también podemos definir H _m por: donde representa el producto de Kronecker . Por lo tanto, además de este factor de normalización, las matrices de Hadamard están formadas en su totalidad por 1 y −1. $${\displaystyle H_{m}=H_{1}\otimes H_{m-1}}$$ ${\displaystyle \otimes }$

De manera equivalente, podemos definir la matriz de Hadamard por su entrada ( k ,  n )-ésima escribiendo $${\displaystyle {\begin{aligned}k&=\sum _{i=0}^{m-1}{k_{i}2^{i}}=k_{m-1}2^{m-1}+k_{m-2}2^{m-2}+\dots +k_{1}2+k_{0}\\n&=\sum _{i=0}^{m-1}{n_{i}2^{i}}=n_{m-1}2^{m-1}+n_{m-2}2^{m-2}+\dots +n_{1}2+n_{0}\end{aligned}}}$$

donde k _j y n _j son los elementos de bit (0 o 1) de k y n , respectivamente. Nótese que para el elemento en la esquina superior izquierda, definimos: . En este caso, tenemos: ${\displaystyle k=n=0}$ $${\displaystyle (H_{m})_{k,n}={\frac {1}{2^{m/2}}}(-1)^{\sum _{j}k_{j}n_{j}}}$$

Esta es exactamente la DFT multidimensional, normalizada para ser unitaria , si las entradas y salidas se consideran como matrices multidimensionales indexadas por n _j y k _j , respectivamente. ${\textstyle 2\times 2\times \cdots \times 2\times 2}$

A continuación se presentan algunos ejemplos de matrices de Hadamard. donde es el producto escalar bit a bit de las representaciones binarias de los números i y j. Por ejemplo, si , entonces , lo que concuerda con lo anterior (ignorando la constante general). Nótese que el elemento de la primera fila y la primera columna de la matriz se denota por . $${\displaystyle {\begin{aligned}H_{0}&=+{\begin{pmatrix}1\end{pmatrix}}\\[5pt]H_{1}&={\frac {1}{\sqrt {2}}}\left({\begin{array}{rr}1&1\\1&-1\end{array}}\right)\\[5pt]H_{2}&={\frac {1}{2}}\left({\begin{array}{rrrr}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\end{array}}\right)\\[5pt]H_{3}&={\frac {1}{2^{3/2}}}\left({\begin{array}{rrrrrrrr}1&1&1&1&1&1&1&1\\1&-1&1&-1&1&-1&1&-1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\1&1&1&1&-1&-1&-1&-1\\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{array}}\right)\\[5pt](H_{n})_{i,j}&={\frac {1}{2^{n/2}}}(-1)^{i\cdot j}\end{aligned}}}$$ ${\displaystyle i\cdot j}$ ${\textstyle n\;\geq \;2}$ $${\displaystyle (H_{n})_{3,2}\;=\;(-1)^{3\cdot 2}\;=\;(-1)^{(1,1)\cdot (1,0)}\;=\;(-1)^{1+0}\;=\;(-1)^{1}\;=\;-1}$$ ${\textstyle (H_{n})_{0,0}}$

H ₁ es precisamente la 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 .

Ventajas de la transformada de Walsh-Hadamard

Real

De acuerdo con la definición anterior de la matriz H , aquí dejamos H = H [ m , n ] $${\displaystyle H[m,n]={\begin{pmatrix}1&1\\1&-1\end{pmatrix}}}$$

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 .

No se requiere multiplicación

La DFT necesita multiplicación irracional, mientras que la transformada de Hadamard no. Ni siquiera se necesita multiplicación racional, ya que basta con invertir los signos.

Algunas propiedades son similares a las del DFT

En la matriz de transformada de Walsh, todas las entradas en la primera fila (y columna) son iguales a 1. $${\displaystyle H[m,n]=\left({\begin{array}{rrrrrrrr}1&1&1&1&1&1&1&1\\1&1&1&1&-1&-1&-1&-1\\1&1&-1&-1&-1&-1&1&1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\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{array}}\right)}$$

Transformada de Fourier discreta: $${\displaystyle e^{-j2\pi mn/N}}$$

En la transformada de Fourier discreta, cuando m es igual a cero (media de la primera fila), el resultado de la DFT también es 1. En la segunda fila, aunque es diferente de la primera fila, podemos observar una característica de la matriz de que la señal en 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

Relación con la transformada de Fourier

La transformada de Hadamard es de hecho 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]} Al utilizar la transformada de Fourier en grupos finitos (abelianos) , la transformada de Fourier de una función es la función definida por donde es un carácter de . Cada carácter tiene la forma para algún , donde la multiplicación es el producto punto booleano en cadenas de bits, por lo que podemos identificar la entrada con ( dualidad de Pontryagin ) y definir por ${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$ ${\displaystyle f\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C} }$ ${\displaystyle {\widehat {f}}}$ $${\displaystyle {\widehat {f}}(\chi )=\sum _{a\in (\mathbb {Z} /2\mathbb {Z} )^{n}}f(a){\bar {\chi }}(a)}$$ ${\displaystyle \chi }$ ${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$ ${\displaystyle \chi _{r}(a)=(-1)^{a\cdot r}}$ ${\displaystyle r\in (\mathbb {Z} /2\mathbb {Z} )^{n}}$ ${\displaystyle {\widehat {f}}}$ ${\displaystyle r\in (\mathbb {Z} /2\mathbb {Z} )^{n}}$ ${\displaystyle {\widehat {f}}\colon (\mathbb {Z} /2\mathbb {Z} )^{n}\to \mathbb {C} }$ $${\displaystyle {\widehat {f}}(r)=\sum _{a\in (\mathbb {Z} /2\mathbb {Z} )^{n}}f(a)(-1)^{r\cdot a}}$$

Esta es la transformada de Hadamard de , considerando la entrada a y como cadenas booleanas. ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle {\widehat {f}}}$

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 elemento correspondiente de . ${\displaystyle 2^{n}}$ ${\displaystyle v}$ ${\displaystyle H_{n}}$ ${\displaystyle f}$ ${\displaystyle v}$ ${\displaystyle f}$ ${\displaystyle v}$

Compare esto con la transformada de Fourier discreta habitual que, cuando se aplica a un vector de números complejos, utiliza caracteres del grupo cíclico . ${\displaystyle v}$ ${\displaystyle 2^{n}}$ ${\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} }$

Complejidad computacional

En el dominio clásico, la transformada de Hadamard se puede calcular en operaciones ( ), utilizando el algoritmo rápido de transformada de Hadamard . ${\displaystyle n\log n}$ ${\displaystyle n=2^{m}}$

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 . ${\displaystyle O(1)}$

Aplicaciones de la computación cuántica

La transformada de Hadamard se utiliza ampliamente en la 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 cúbit de un registro de cúbits en paralelo es equivalente a la transformada de Hadamard . ${\displaystyle H_{1}}$ ${\displaystyle n}$ ${\displaystyle H_{n}}$

Puerta de Hadamard

En computación cuántica, la puerta de Hadamard es una rotación de un cúbit , que asigna los estados base del cúbit y a dos estados de superposición con igual peso de los estados base computacionales y . Por lo general, las fases se eligen de modo que ${\displaystyle |0\rangle }$ ${\displaystyle |1\rangle }$ ${\displaystyle |0\rangle }$ ${\displaystyle |1\rangle }$ $${\displaystyle H={\frac {|0\rangle +|1\rangle }{\sqrt {2}}}\langle 0|+{\frac {|0\rangle -|1\rangle }{\sqrt {2}}}\langle 1|}$$

en notación de Dirac . Esto corresponde a la matriz de transformación en la base, también conocida como base computacional. Los estados y se conocen como y respectivamente, y juntos constituyen la base polar en computación cuántica . $${\displaystyle H_{1}={\frac {1}{\sqrt {2}}}{\begin{pmatrix}1&1\\1&-1\end{pmatrix}}}$$ ${\displaystyle |0\rangle ,|1\rangle }$ ${\textstyle {\frac {\left|0\right\rangle +\left|1\right\rangle }{\sqrt {2}}}}$ ${\textstyle {\frac {\left|0\right\rangle -\left|1\right\rangle }{\sqrt {2}}}}$ ${\displaystyle \left|{\boldsymbol {+}}\right\rangle }$ ${\displaystyle \left|{\boldsymbol {-}}\right\rangle }$

Operaciones de la puerta de Hadamard

$${\displaystyle {\begin{aligned}H(|0\rangle )&={\frac {1}{\sqrt {2}}}|0\rangle +{\frac {1}{\sqrt {2}}}|1\rangle =:|+\rangle \\H(|1\rangle )&={\frac {1}{\sqrt {2}}}|0\rangle -{\frac {1}{\sqrt {2}}}|1\rangle =:|-\rangle \\H(|+\rangle )&=H\left({\frac {1}{\sqrt {2}}}|0\rangle +{\frac {1}{\sqrt {2}}}|1\rangle \right)={\frac {1}{2}}{\Big (}|0\rangle +|1\rangle {\Big )}+{\frac {1}{2}}{\Big (}|0\rangle -|1\rangle {\Big )}=|0\rangle \\H(|-\rangle )&=H\left({\frac {1}{\sqrt {2}}}|0\rangle -{\frac {1}{\sqrt {2}}}|1\rangle \right)={\frac {1}{2}}{\Big (}|0\rangle +|1\rangle {\Big )}-{\frac {1}{2}}{\Big (}|0\rangle -|1\rangle {\Big )}=|1\rangle \end{aligned}}}$$

Una aplicación de la puerta de Hadamard a un cúbito 0 o 1 producirá un estado cuántico que, si se observa, será un 0 o un 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 probabilístico estándar de computación . Sin embargo, si la puerta de Hadamard se aplica dos veces seguidas (como se está haciendo efectivamente en las dos últimas operaciones), entonces el estado final siempre es el mismo que el estado inicial.

Transformada de Hadamard en algoritmos cuánticos

Calcular la transformada cuántica de Hadamard es simplemente la aplicación de una compuerta de Hadamard a cada cúbit 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. ${\displaystyle \log _{2}N}$ ${\displaystyle N\log _{2}N}$

Para un sistema de -qubits, las puertas de Hadamard que actúan sobre cada uno de los qubits (cada uno inicializado en ) se pueden utilizar para preparar estados de superposición cuántica uniforme cuando tiene la forma . En este caso con qubits, la puerta de Hadamard combinada se expresa como el producto tensorial de las puertas de Hadamard: ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle |0\rangle }$ ${\displaystyle N}$ ${\displaystyle N=2^{n}}$ ${\displaystyle n}$ ${\displaystyle H_{n}}$ ${\displaystyle n}$ ${\displaystyle H_{n}=\underbrace {H\otimes H\otimes \ldots \otimes H} _{n{\text{ times}}}}$

El estado de superposición cuántica uniforme resultante es entonces: Esto generaliza la preparación de estados cuánticos uniformes utilizando puertas de Hadamard para cualquier . ^[5] ${\displaystyle H_{n}|0\rangle ^{\otimes n}={\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}|j\rangle }$ ${\displaystyle N=2^{n}}$

La medición de este estado cuántico uniforme da como resultado un estado aleatorio entre y . ${\displaystyle |0\rangle }$ ${\displaystyle |N-1\rangle }$

Muchos algoritmos cuánticos utilizan la transformada de Hadamard como paso inicial, ya que, como se explicó anteriormente, asigna n qubits inicializados con a una superposición de los 2 ⁿ estados ortogonales en la base con igual 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 de Hadamard inicial como la transformada de Fourier cuántica , que son ambos tipos de transformadas de Fourier sobre grupos finitos ; la primera sobre y la segunda sobre . ${\displaystyle |0\rangle }$ ${\displaystyle |0\rangle ,|1\rangle }$ ${\displaystyle (\mathbb {Z} /2\mathbb {Z} )^{n}}$ ${\displaystyle \mathbb {Z} /2^{n}\mathbb {Z} }$

Preparación de estados de superposición cuántica uniformes en el caso general, cuando ≠ no es trivial y requiere más trabajo. Recientemente se presentó un enfoque eficiente y determinista para preparar el estado de superposición con una complejidad de compuerta y una profundidad de circuito de solo para todos . ^[6] Este enfoque requiere solo cúbits. Es importante destacar que no se necesitan cúbits ancillarios ni ninguna compuerta cuántica con múltiples controles en este enfoque para crear el estado de superposición uniforme . ${\displaystyle N}$ ${\displaystyle 2^{n}}$ $${\displaystyle |\Psi \rangle ={\frac {1}{\sqrt {N}}}\sum _{j=0}^{N-1}|j\rangle }$$ ${\displaystyle O(\log _{2}N)}$ ${\displaystyle N}$ ${\displaystyle n=\lceil \log _{2}N\rceil }$ ${\displaystyle |\Psi \rangle }$

Aplicaciones de la filogenética molecular (biología evolutiva)

La transformada de Hadamard se puede utilizar para estimar árboles filogenéticos a partir de datos moleculares. ^{[7] [8] [9]} La filogenética es el subcampo de la biología evolutiva centrado en la comprensión de las relaciones entre los organismos. Una transformada de Hadamard aplicada a un vector (o matriz) de frecuencias de patrones de sitios obtenidos a partir de una alineación de secuencias múltiples de ADN se puede utilizar para generar otro vector que contenga información sobre la topología del árbol. La naturaleza invertible de la transformada de Hadamard filogenética también permite el cálculo de probabilidades de sitios 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 verosimilitud de árboles filogenéticos. Sin embargo, la última aplicación es menos útil que la transformación del vector de patrones de sitios al vector de árboles porque hay otras formas de calcular probabilidades de sitios ^{[10] [11]} que son mucho más eficientes. Sin embargo, la naturaleza invertible de la transformada de Hadamard filogenética proporciona una herramienta elegante para la filogenética matemática. ^{[12] [13]}

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 la longitud de las ramas del árbol utilizando el vector o matriz de patrón de sitio . ${\displaystyle \gamma (T)}$ ${\displaystyle T}$ ${\displaystyle s(T)}$

$${\displaystyle \gamma (T)=H^{-1}(\ln(Hs(T)))}$$donde es la matriz de Hadamard del tamaño adecuado. Esta ecuación se puede reescribir como una serie de tres ecuaciones para simplificar su interpretación: ${\displaystyle H}$

$${\displaystyle {\begin{aligned}r&=Hs(T)\\\rho &=\ln r\\\gamma (T)&=H^{-1}\rho \end{aligned}}}$$

La naturaleza invertible de esta ecuación permite calcular un vector (o matriz) de patrón de sitio esperado de la siguiente manera:

$${\displaystyle s(T)=H^{-1}(\exp(H\gamma (T)))}$$

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 se codifican como R y las pirimidinas C y T se codifican como Y). Esto permite codificar el alineamiento de secuencias múltiples como el vector de patrón de sitio que se puede convertir en un vector de árbol , como se muestra en el siguiente ejemplo: ${\displaystyle s(T)}$ ${\displaystyle \gamma (T)}$

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 de sitio se escriben 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); por lo tanto, 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 de ramas largas si los datos se analizan utilizando el criterio de máxima parsimonia (asumiendo que la secuencia analizada es lo suficientemente larga para que las frecuencias de patrones de sitio observadas estén cerca de las frecuencias esperadas que se muestran en la columna). La atracción de rama larga refleja el hecho de que el número esperado de patrones de sitios con índice 6 - que apoyan el árbol ((A,C),(B,D)); - exceden el número esperado de patrones de sitios que apoyan el árbol verdadero (índice 4). Obviamente, la naturaleza invertible de la transformada filogenética de Hadamard significa que el vector del árbol significa que el vector del árbol corresponde al árbol correcto. El análisis de parsimonia después de la transformación es, por lo tanto , estadísticamente consistente , ^[15] como lo sería un análisis de máxima verosimilitud estándar utilizando el modelo correcto (en este caso, el modelo CFN). ${\displaystyle s(T)=H^{-1}\rho }$ ${\displaystyle \gamma (T)}$

Nótese 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 "parsimonia-informativos", y los índices restantes representan patrones de sitios donde un solo taxón difiere de los otros tres taxones (por lo que son el equivalente de las longitudes de las ramas terminales en un árbol filogenético de máxima verosimilitud estándar).

Si se desea utilizar datos de nucleótidos sin recodificarlos como R e Y (y, en última instancia, como 0 y 1), es posible codificar los patrones de sitios como una matriz. Si consideramos un árbol de cuatro taxones, hay un total de 256 patrones de sitios (cuatro nucleótidos 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 ^[16] de una manera similar al vector de 8 elementos utilizado anteriormente para los patrones de sitios de transversión (RY). Esto se logra recodificando los datos utilizando el modelo de cuatro grupos de Klein :

Al igual que con los datos RY, los patrones de sitios se indexan en relación con la base en el primer taxón elegido arbitrariamente, y las bases en los taxones subsiguientes se codifican en relación con esa primera base. Por lo tanto, el primer taxón recibe el par de bits (0,0). Al utilizar esos pares de bits, se pueden producir dos vectores similares a los vectores RY y luego completar la matriz utilizando esos vectores. Esto se puede ilustrar utilizando el ejemplo de Hendy et al. (1994), ^[16], que se basa en una alineación de secuencias múltiples de cuatro pseudogenes de hemoglobina de primates:

El número mucho mayor de patrones de sitios 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 trabajado ^[17] ). 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 (del mismo modo, los patrones de sitios CCAG, GGTC y TTGA, que se codificarían de la misma manera, están ausentes).

Otras aplicaciones

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 vídeo , se suele utilizar en forma de suma de diferencias transformadas absolutas . También es una parte crucial de un número significativo de algoritmos en 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 matriz pseudoaleatorias.

Véase también

• Transformada rápida de Walsh-Hadamard
• Transformada pseudo-Hadamard
• Transformación de Haar
• Ley distributiva generalizada

Enlaces externos

• Ritter, Terry (agosto de 1996). "Transformaciones de Walsh-Hadamard: un estudio de la literatura".
• Akansu , Ali N.; Poluri, R. (julio de 2007). "Códigos ortogonales de fase no lineales similares a Walsh para comunicaciones CDMA de secuencia directa" (PDF) . IEEE Transactions on Signal Processing . 55 (7): 3800–6. Bibcode :2007ITSP...55.3800A. doi :10.1109/TSP.2007.894229. S2CID  6830633.
• Pan, Jeng-shyang Método de cifrado de datos mediante transformación Hadamard fraccionaria discreta (28 de mayo de 2009)
• Lachowicz, Dr. Pawel. Transformada de Walsh-Hadamard y pruebas de aleatoriedad de series de rendimientos financieros (7 de abril de 2015)
• Beddard, Godfrey; Yorke, Briony A. (enero de 2011). "Espectroscopia de bombeo-sonda mediante transformadas de Hadamard" (PDF) . Archivado desde el original (PDF) el 2014-10-18 . Consultado el 2012-04-28 .
• Yorke, Briony A.; Beddard, Godfrey; Owen, Robin L.; Pearson, Arwen R. (septiembre de 2014). "Cristalografía resuelta en el tiempo utilizando la transformada de Hadamard". Nature Methods . 11 (11): 1131–1134. doi :10.1038/nmeth.3139. PMC  4216935 . PMID  25282611.

Referencias

1. Comparar la Figura 1 en Townsend, WJ; Thornton, MA "Cálculos del espectro de Walsh utilizando gráficos de Cayley". Actas del 44.º Simposio IEEE 2001 del Medio Oeste sobre circuitos y sistemas (MWSCAS 2001) . MWSCAS-01. IEEE. doi :10.1109/mwscas.2001.986127.
2. Kunz, HO (1979). "Sobre la equivalencia entre transformadas de Walsh-Hadamard discretas unidimensionales y transformadas de Fourier discretas multidimensionales". IEEE Transactions on Computers . 28 (3): 267–8. doi :10.1109/TC.1979.1675334. S2CID  206621901.
3. Análisis de Fourier de mapas booleanos: un tutorial, págs. 12-13
4. Lección 5: Algoritmos cuánticos básicos, Rajat Mittal, págs. 4-5
5. Nielsen, Michael A .; Chuang, Isaac (2010). Computación cuántica e información cuántica. Cambridge: Cambridge University Press . ISBN 978-1-10700-217-3.OCLC 43641333  .
6. Alok Shukla y Prakash Vedula (2024). "Un algoritmo cuántico eficiente para la preparación de estados de superposición cuántica uniforme". Procesamiento de información cuántica . 23:38 (1): 38. arXiv : 2306.11747 . Bibcode :2024QuIP...23...38S. doi :10.1007/s11128-024-04258-4.
7. Hendy, Michael D.; Penny, David (diciembre de 1989). "Un marco para el estudio cuantitativo de árboles evolutivos". Zoología sistemática . 38 (4): 297. doi :10.2307/2992396. JSTOR  2992396.
8. Hendy, Michael D.; Penny, David (enero de 1993). "Análisis espectral de datos filogenéticos". Revista de clasificación . 10 (1): 5–24. doi :10.1007/BF02638451. ISSN  0176-4268. S2CID  122466038.
9. Székely, LA, Erdős, PL, Steel, MA y Penny, D. (1993). Una fórmula de inversión de Fourier para árboles evolutivos. Cartas de matemáticas aplicadas , 6 (2), 13–16.
10. Felsenstein, Joseph (noviembre de 1981). "Árboles evolutivos a partir de secuencias de ADN: un enfoque de máxima verosimilitud". Journal of Molecular Evolution . 17 (6): 368–376. Bibcode :1981JMolE..17..368F. doi :10.1007/BF01734359. ISSN  0022-2844. PMID  7288891. S2CID  8024924.
11. Stamatakis, Alexandros (2019), Warnow, Tandy (ed.), "Una revisión de los enfoques para optimizar los cálculos de verosimilitud filogenética", Bioinformática y filogenética , Computational Biology, vol. 29, Cham: Springer International Publishing, págs. 1–19, doi :10.1007/978-3-030-10837-3_1, ISBN 978-3-030-10836-6, S2CID  145834168 , consultado el 10/10/2020
12. Chor, Benny ; Hendy, Michael D.; Holland, Barbara R.; Penny, David (1 de octubre de 2000). "Máximos múltiples de verosimilitud en árboles filogenéticos: un enfoque analítico". Biología molecular y evolución . 17 (10): 1529–1541. doi : 10.1093/oxfordjournals.molbev.a026252 . ISSN  1537-1719. PMID  11018159.
13. Matsen, Frederick A.; Steel, Mike (1 de octubre de 2007). Ané, Cécile ; Sullivan, Jack (eds.). "Las mezclas filogenéticas en un solo árbol pueden imitar un árbol de otra topología". Biología sistemática . 56 (5): 767–775. arXiv : 0704.2260 . doi : 10.1080/10635150701627304 . ISSN  1076-836X. PMID  17886146.
14. Waddell, Peter J; Steel, MA (diciembre de 1997). "Distancias generales reversibles en el tiempo con tasas desiguales en los sitios: mezcla de distribuciones Γ y gaussianas inversas con sitios invariantes". Filogenética molecular y evolución . 8 (3): 398–414. doi :10.1006/mpev.1997.0452. PMID  9417897.
15. Steel, MA; Hendy, MD; Penny, D. (1993-12-01). "¡La parsimonia puede ser consistente!". Biología sistemática . 42 (4): 581–587. doi :10.1093/sysbio/42.4.581. ISSN  1063-5157.
16. Hendy, MD; Penny, D.; Steel, MA (12 de abril de 1994). "Un análisis discreto de Fourier para árboles evolutivos". Actas de la Academia Nacional de Ciencias . 91 (8): 3339–3343. Bibcode :1994PNAS...91.3339H. doi : 10.1073/pnas.91.8.3339 . ISSN  0027-8424. PMC 43572 . PMID  8159749. 
17. Miyamoto, MM; Koop, BF; Slightom, JL; Goodman, M.; Tennant, MR (1988-10-01). "Sistemática molecular de primates superiores: relaciones genealógicas y clasificación". Actas de la Academia Nacional de Ciencias . 85 (20): 7627–7631. Bibcode :1988PNAS...85.7627M. doi : 10.1073/pnas.85.20.7627 . ISSN  0027-8424. PMC 282245 . PMID  3174657.