Main Content

Esta página es para la versión anterior. La página correspondiente en inglés ha sido eliminada en la versión actual.

Transformación discreta Walsh-Hadamard

Introducción

Este ejemplo muestra cómo utilizar la transformación Walsh-Hadamard (WHT) y algunas de sus propiedades mostrando dos aplicaciones: comunicaciones mediante espectro extendido y procesamiento de señales ECG.

Los WHT se utilizan en muchas aplicaciones diferentes, como el análisis del espectro de potencia, el filtrado, el procesamiento de señales médicas y de voz, la multiplexación y codificación en las comunicaciones, la caracterización de señales no lineales, la resolución de ecuaciones diferenciales no lineales y diseño lógico y análisis.

El WHT es una transformación ortogonal subóptima, no sinusoidal, que descompone una señal en un conjunto de formas de onda rectangulares ortogonales llamadas funciones Walsh. La transformación no tiene multiplicadores y es real porque la amplitud de las funciones Walsh (o Hadamard) tiene solo dos valores, +1 o -1.

Funciones Walsh (o Hadamard)

Las funciones Walsh son formas de onda rectangulares o cuadradas con valores de -1 o +1. Una característica importante de las funciones Walsh es la secuenciación que se determina a partir del número de cruces cero por intervalo de tiempo de unidad. Cada función Walsh tiene un valor de secuenciación único.

Las funciones Walsh se pueden generar de muchas maneras (véase [1]). Aquí usamos la función en MATLAB® para generar funciones Walsh.hadamard Longitud ocho funciones Walsh se generan de la siguiente manera.

N = 8;  % Length of Walsh (Hadamard) functions hadamardMatrix = hadamard(N)
hadamardMatrix = 8×8

     1     1     1     1     1     1     1     1
     1    -1     1    -1     1    -1     1    -1
     1     1    -1    -1     1     1    -1    -1
     1    -1    -1     1     1    -1    -1     1
     1     1     1     1    -1    -1    -1    -1
     1    -1     1    -1    -1     1    -1     1
     1     1    -1    -1    -1    -1     1     1
     1    -1    -1     1    -1     1     1    -1

Las filas (o columnas) de lo simétrico contienen las funciones Walsh.hadamardMatrix Las funciones Walsh en la matriz no están dispuestas en orden creciente de sus secuencias o número de cruces cero (es decir, "orden de secuencia") sino que están dispuestas en "orden Hadamard". La matriz Walsh, que contiene las funciones Walsh a lo largo de las filas o columnas en el orden creciente de sus secuencias se obtiene cambiando el índice de la siguiente manera.hadamardMatrix

HadIdx = 0:N-1;                          % Hadamard index M = log2(N)+1;                           % Number of bits to represent the index

Cada columna del índice de secuenciación (en formato binario) se da por la adición modulo-2 de columnas del índice Hadamard invertido en bits (en formato binario).

binHadIdx = fliplr(dec2bin(HadIdx,M))-'0'; % Bit reversing of the binary index binSeqIdx = zeros(N,M-1);                  % Pre-allocate memory for k = M:-1:2     % Binary sequency index      binSeqIdx(:,k) = xor(binHadIdx(:,k),binHadIdx(:,k-1)); end SeqIdx = binSeqIdx*pow2((M-1:-1:0)');    % Binary to integer sequency index walshMatrix = hadamardMatrix(SeqIdx+1,:) % 1-based indexing
walshMatrix = 8×8

     1     1     1     1     1     1     1     1
     1     1     1     1    -1    -1    -1    -1
     1     1    -1    -1    -1    -1     1     1
     1     1    -1    -1     1     1    -1    -1
     1    -1    -1     1     1    -1    -1     1
     1    -1    -1     1    -1     1     1    -1
     1    -1     1    -1    -1     1    -1     1
     1    -1     1    -1     1    -1     1    -1

Transformación discreta Walsh-Hadamard

El par de transformación Walsh hacia adelante e inverso para una señal x(t) de longitud N son

<math display="block">
<mrow>
<msub>
<mrow>
<mi>y</mi>
</mrow>
<mrow>
<mi>n</mi>
</mrow>
</msub>
<mo>=</mo>
<mfrac>
<mrow>
<mn>1</mn>
</mrow>
<mrow>
<mi>N</mi>
</mrow>
</mfrac>
<munderover>
<mrow>
<mo></mo>
</mrow>
<mrow>
<mi>i</mi>
<mo>=</mo>
<mn>0</mn>
</mrow>
<mrow>
<mi>N</mi>
<mo>-</mo>
<mn>1</mn>
</mrow>
</munderover>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mi>i</mi>
</mrow>
</msub>
<mi>W</mi>
<mi>A</mi>
<mi>L</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo>,</mo>
<mi>i</mi>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mi>n</mi>
<mo>=</mo>
<mn>1</mn>
<mo>,</mo>
<mn>2</mn>
<mo>,</mo>
<mo></mo>
<mo>,</mo>
<mi>N</mi>
<mo>-</mo>
<mn>1</mn>
</mrow>
</math>

<math display="block">
<mrow>
<msub>
<mrow>
<mi>x</mi>
</mrow>
<mrow>
<mi>i</mi>
</mrow>
</msub>
<mo>=</mo>
<munderover>
<mrow>
<mo></mo>
</mrow>
<mrow>
<mi>n</mi>
<mo>=</mo>
<mn>0</mn>
</mrow>
<mrow>
<mi>N</mi>
<mo>-</mo>
<mn>1</mn>
</mrow>
</munderover>
<msub>
<mrow>
<mi>y</mi>
</mrow>
<mrow>
<mi>n</mi>
</mrow>
</msub>
<mi>W</mi>
<mi>A</mi>
<mi>L</mi>
<mo stretchy="false">(</mo>
<mi>n</mi>
<mo>,</mo>
<mi>i</mi>
<mo stretchy="false">)</mo>
<mo>,</mo>
<mi>i</mi>
<mo>=</mo>
<mn>1</mn>
<mo>,</mo>
<mn>2</mn>
<mo>,</mo>
<mo></mo>
<mo>,</mo>
<mi>N</mi>
<mo>-</mo>
<mn>1</mn>
</mrow>
</math>

Algoritmos rápidos, similares al algoritmo Cooley-Tukey, se han desarrollado para implementar la transformación Walsh-Hadamard con complejidad O(NlogN) (ver [1] y [2]). Dado que la matriz Walsh es simétrica, las transformaciones hacia delante e inversas son operaciones idénticas, excepto por el factor de escala de 1/N. Las funciones e implementar el WHT hacia adelante e inverso respectivamente.fwhtifwht

Realice WHT en la matriz Walsh.Ejemplo 1 El resultado esperado es una matriz de identidad porque las filas (o columnas) de la matriz simétrica Walsh contienen las funciones Walsh.

y1 = fwht(walshMatrix)                % Fast Walsh-Hadamard transform
y1 = 8×8

     1     0     0     0     0     0     0     0
     0     1     0     0     0     0     0     0
     0     0     1     0     0     0     0     0
     0     0     0     1     0     0     0     0
     0     0     0     0     1     0     0     0
     0     0     0     0     0     1     0     0
     0     0     0     0     0     0     1     0
     0     0     0     0     0     0     0     1

Construya una señal discontinua escalando y agregando columnas arbitrarias de la matriz Hadamard.Ejemplo 2 Esta señal se forma utilizando funciones Walsh ponderadas, por lo que el WHT debe devolver valores distintos de cero iguales a los pesos en los índices de secuenciación respectivos. Al evaluar el WHT, se especifica como 'hadamard', porque se utiliza una matriz Hadamard (en lugar de la matriz Walsh) para obtener las funciones Walsh.ordering

N = 8; H = hadamard(N);                      % Hadamard matrix % Construct a signal by adding a few weighted Walsh functions x = 8.*H(1,:) + 12.*H(3,:) + 18.*H(5,:) + 10.*H(8,:);            y = fwht(x,N,'hadamard')
y = 1×8

     8     0    12     0    18     0     0    10

WHT es una transformación reversible y la señal original se puede recuperar perfectamente utilizando la transformación inversa. La norma entre la señal original y la señal obtenida de la transformación inversa es igual a cero, lo que indica una reconstrucción perfecta.

xHat = ifwht(y,N,'hadamard'); norm(x-xHat)
ans = 0 

La transformación Walsh-Hadamard implica la expansión utilizando un conjunto de formas de onda rectangulares, por lo que es útil en aplicaciones que implican señales discontinuas que se pueden expresar fácilmente en términos de funciones Walsh. A continuación se presentan dos aplicaciones de transformaciones Walsh-Hadamard.

Aplicaciones Walsh-Transform

A menudo, es necesario registrar las señales de electrocardiograma (ECG) de los pacientes en diferentes instantes de tiempo.Procesamiento de señalecé ECG Esto da como resultado una gran cantidad de datos, que deben almacenarse para su análisis, comparación, etc. en un momento posterior. La transformación Walsh-Hadamard es adecuada para la compresión de señales ECG porque ofrece ventajas como el cálculo rápido de los coeficientes Walsh-Hadamard, menos espacio de almacenamiento requerido ya que es suficiente para almacenar sólo aquellos coeficientes de secuenciación con grandes magnitudes, y la reconstrucción rápida de la señal.

Una señal ECG y su transformación Walsh-Hadamard correspondiente se evalúan y se muestran a continuación.

x1 = ecg(512);                    % Single ecg wave x = repmat(x1,1,8);                  x = x + 0.1.*randn(1,length(x));  % Noisy ecg signal y = fwht(x);                      % Fast Walsh-Hadamard transform figure subplot(2,1,1) plot(x) xlabel('Sample index') ylabel('Amplitude') title('ECG Signal') subplot(2,1,2) plot(abs(y)) xlabel('Sequency index') ylabel('Magnitude') title('WHT Coefficients')

Como se puede ver en la gráfica anterior, la mayor parte de la energía de la señal se concentra en valores de secuenciación más bajos. A efectos de investigación, sólo se almacenan y utilizan los primeros 1024 coeficientes para reconstruir la señal original. Truncar los coeficientes de secuenciación más altos también ayuda con la supresión del ruido. Las señales originales y reproducidas se muestran a continuación.

y(1025:length(x)) = 0;            % Zeroing out the higher coefficients     xHat = ifwht(y);                  % Signal reconstruction using inverse WHT   figure plot(x) hold on plot(xHat,'r') xlabel('Sample index') ylabel('ECG signal amplitude') legend('Original Signal','Reconstructed Signal')

La señal reproducida está muy cerca de la señal original.

Para reconstruir la señal original, almacenamos sólo los primeros 1024 coeficientes y la longitud de la señal ECG. Esto representa una relación de compresión de aproximadamente 4:1.

req = [length(x) y(1:1024)];    whos x req
  Name      Size              Bytes  Class     Attributes    req       1x1025             8200  double                 x         1x4096            32768  double               

Las tecnologías de comunicación basadas en espectro, como la CDMA, utilizan códigos Walsh (derivados de las funciones Walsh) para difundir señales de mensajes y transformaciones WHT para propagarlas.Comunicación mediante espectro extendido Dado que los códigos Walsh son ortogonales, cualquier señal codificada en Walsh aparece como ruido aleatorio a un terminal a menos que ese terminal utilice el mismo código para la codificación. A continuación mostramos el proceso de propagación, determinación de los códigos Walsh utilizados para la propagación y la propagación para recuperar la señal del mensaje.

Dos terminales CDMA propagan sus respectivas señales de mensaje utilizando dos códigos Walsh diferentes (también conocidos como códigos Hadamard) de longitud 64. Las señales de los mensajes de propagación están dañadas por un aditivo blanco de ruido gaussiano de varianza 0.1.

En el receptor (estación base), el procesamiento de la señal no es coherente y la secuencia recibida de longitud N debe correlacionarse con las palabras clave Walsh de 2 N para extraer los códigos Walsh utilizados por los transmisores respectivos. Esto se puede hacer efectivamente transformando las señales recibidas al dominio de secuenciación utilizando la rápida transformación Walsh-Hadamard. Utilizando la ubicación de secuenciación en un lugar donde se produce un pico, se puede determinar el código Walsh-Hadamard correspondiente (o la función Walsh) utilizado. La siguiente trama muestra que los códigos Walsh-Hadamard con secuenciación (con 'hadamard') 60 y 10 se utilizaron en el primer y segundo transmisor, respectivamente.ordering

load mess_rcvd_signals.mat N = length(rcvdSig1); y1 = fwht(rcvdSig1,N,'hadamard'); y2 = fwht(rcvdSig2,N,'hadamard'); figure plot(0:63,y1,0:63,y2,'r') xlabel('Sequency index') ylabel('WHT of the Received Signals') title('Walsh-Hadamard Code Extraction') legend('WHT of Tx - 1 signal','WHT of Tx - 2 signal')

La desdifusión (o decodificación) para extraer la señal del mensaje se puede llevar a cabo de una manera sencilla multiplicando las señales recibidas por los respectivos códigos Walsh-hadamard generados utilizando la función.hadamard (Tenga en cuenta que la indexación en MATLAB® comienza a partir de 1, por lo tanto, los códigos Walsh-Hadamard con la secuencia 60 y 10 se obtienen seleccionando las columnas (o filas) 61 y 11 en la matriz Hadamard.)

N = 64;  hadamardMatrix = hadamard(N); codeTx1 = hadamardMatrix(:,61);         % Code used by transmitter 1   codeTx2 = hadamardMatrix(:,11);         % Code used by transmitter 2

La operación de decodificación para recuperar la señal de mensaje original es

xHat1 = codeTx1 .* rcvdSig1;            % Decoded signal at receiver 1 xHat2 = codeTx2 .* rcvdSig2;            % Decoded signal at receiver 2

Las señales de mensaje recuperadas en el lado del receptor se muestran a continuación y se superponen con las señales originales para la comparación.

subplot(2,1,1) plot(x1) hold on plot(xHat1,'r') legend('Original Message','Reconstructed Message','Location','Best') xlabel('Sample index') ylabel('Message signal amplitude') subplot(2,1,2) plot(x2) hold on plot(xHat2,'r') legend('Original Message','Reconstructed Message','Location','Best') xlabel('Sample index') ylabel('Message signal amplitude')

Referencias

  1. K.G. Beauchamp, , Prensa Académica, 1984Applications of Walsh and Related Functions - With an Introduction to Sequency Theory

  2. T. Beer, , American Journal of Physics, Vol. 49, Número 5, mayo de 1981Walsh Transforms