Departamento de Informtica de Sistemas y Computadores

Universidad Politcnica de Valencia

Transformada Rpida de Fourier (FFT) e Interpolacin en Tiempo Real

Algoritmos y aplicaciones

Proceso digital de datos en sistemas de tiempo real

Presentado por: D. Juan Luis Posadas Yage Dirigido por: D. Gins Benet Gilabert Valencia, Julio 1.998

Proceso Digital de Datos en Sistemas de Tiempo Real

1. Introduccin
El trabajo que a continuacin se presenta se ha desarrollado para su aplicacin en el procesado digital de seales procedentes de sensores de ultrasonidos. Los objetivos han sido varios:

Y Y

Obtencin e implementacin de un algoritmo que realice la Transformada Rpida de Fourier (FFT) y su inversa (IFFT) para ejecutarlo en el Procesador Digital de Seales (DSP) de coma flotante: TMS320C30. Diseo e implementacin de un algoritmo que realice la interpolacin senoidal (basada en la funcin SINC) en tiempo real.

Para la lectura del trabajo se requieren conocimientos sobre la Transformada de Fourier y las matemticas implicadas, stos pueden adquirirse consultando la bibliografa recomendada [Fourier] y [DSP 1] antes de abordar la lectura. El trabajo se divide en dos apartados coincidiendo con los dos objetivos planteados. En el primer apartado se explica la complejidad de los clculos para realizar la Transformada Discreta de Fourier y se detalla la teora necesaria para obtener un algoritmo eficiente basado en la Transformada Rpida de Fourier, como resultado se presenta una implementacin en C de dicho algoritmo [TMS32C30], [FFT 1] y [FFT 2]. En el segundo apartado se explica la teora que rodea a la interpolacin senoidal en tiempo real [DSP 2] y se implementan paso a paso una serie de algoritmos en C que la realizan. Adems, se analizan dichos algoritmos realizando un estudio de los resultados obtenidos al ejecutarlos obteniendo, para finalizar, una serie de conclusiones sobre cmo realizar y caracterizar una interpolacin dada una seal con unas caractersticas de muestreo determinadas.

_ APARTADO 1 _______________________________________ 2. Transformada Discreta de Fourier (DFT)

La Transformada Discreta de Fourier (DFT del ingls Discrete Fourier Transform) es el equivalente discreto de la Transformada de Fourier donde se ha transformado la variable continua t por la variable discreta nTs siendo Ts el periodo de muestreo. Recordemos que la Transformada de Fourier de una seal analgica x(t) es:

X ( ) =

x (t ) e

jt

dt

La Transformada Discreta de Fourier es un mtodo muy eficiente para determinar el espectro en frecuencia de una seal. Permite convertir una secuencia de valores en el dominio del tiempo a una secuencia de valores equivalente en el dominio de la frecuencia. La Inversa de la Transformada Discreta de Fourier (IDFT) realiza el proceso contrario. Recordemos el par de ecuaciones de la DFT:

X ( k ) = x ( n ) W nk
n =0

N 1

k = 0, 1, . . ., N 1
nk

x(n) =

1 N

X (k ) W
k =0

N 1

n = 0, 1, . . ., N 1

UPV

Pgina

Transformada Rpida de Fourier e Interpolacin en Tiempo Real

Donde las constantes W son conocidas como factores twiddle y definidas como:

W = e j 2

Observar que W es una funcin de longitud N, por ello, tambin suele expresarse como WN. El inconveniente de realizar unos algoritmos que implementen tal cual estas frmulas es la cantidad de tiempo requerido para computar la salida. Esto es debido a que los ndices k y n deben variar de 0 a N-1 para conseguir el rango de salida completo y, por tanto, se deben realizar N2 operaciones. El primer objetivo de este trabajo ha sido implementar un algoritmo eficiente que realice la DFT. Este algoritmo se basa en la Transformada Rpida de Fourier (FFT del ingls Fast Fourier Transform). Un algoritmo para la FFT obtiene los mismos resultados que la DFT pero ms rpidamente debido a que reduce el nmero de clculos requerido para realizar la DFT. El trmino genrico Transformada Rpida de Fourier abarca distintos algoritmos con distintas caractersticas, ventajas y desventajas.

3. Transformada Rpida de Fourier (FFT)

En la frmula de la Transformada Discreta de Fourier obtener X(k) para un k determinado requiere aproximadamente N sumas complejas y N productos complejos, ya que:

X (k ) = x (0) + x (1) W k + x (2) W 2 k + x (3) W 3k + + x ( N 1) W ( N 1) k

para k = 0, 1, ..., N-1. Si lo que se desea es obtener X(0), X(1), ..., X(N-1) entonces se necesitarn un total de aproximadamente N2 sumas complejas y N2 productos complejos. Esto quiere decir que los requerimientos computacionales de la DFT pueden ser excesivos especialmente si el tamao de N es grande. La FFT aprovecha la periodicidad y simetra del factor twiddle W para el clculo del Transformada Discreta de Fourier. La periodicidad de W implica:

W k = W k +N
y su simetra implica:

W k = W k + N 2
La FFT descompone la DFT de N puntos en transformadas ms pequeas. Una DFT de N puntos es descompuesta en dos DFTs de (N/2) puntos. Cada DFT de (N/2) puntos se descompone a su vez en dos DFTs de (N/4) puntos y as sucesivamente. Al final de la descomposicin se obtienen (N/2) DFTs de 2 puntos cada una. La transformada ms pequea viene determinada por la base de la FFT. Para una FFT de base 2, N debe ser una potencia de 2 y la transformada ms pequea es la DFT de 2 puntos. Para implementar la FFT existen dos procedimientos: diezmado en frecuencia (DIF del ingls Decimation In Frequency) y diezmado en el tiempo (DIT del ingls Decimation In Time). En este trabajo se ha utilizado un algoritmo DIF.

4. Algoritmo para la FFT basado en DIF

En este punto, primeramente, vamos a obtener paso a paso de forma terica un algoritmo para realizar la FFT basado en DIF y, a continuacin, se presentar una implementacin de ste en C.
Pgina

DISCA

Proceso Digital de Datos en Sistemas de Tiempo Real

Partiremos de la Transformada Discreta de Fourier para una secuencia x(n) de N puntos:

X ( k ) = x ( n ) W nk
n =0

N 1

k = 0, 1, . . ., N 1

Si la secuencia x(n) la separamos en dos mitades:

N x (0), x (1),...., x 1 2 N N x , x + 1,...., x (N 1) 2 2

la ecuacin para la Transformada Discreta de Fourier tambin podemos separarla en dos sumatorios:

X (k ) =

( N 2 )1
n =0

x(n) W nk +

n=N 2

x (n ) W
( N 2 )1
n =0

N 1

nk

Si en el segundo sumatorio hacemos que: n = n + N/2, la ecuacin se convierte en:

X (k ) =

( N 2 )1
n =0

x(n) W
k

nk

+W

kN 2

x(n) W

nk

donde WkN/2 se saca fuera del segundo sumatorio porque no depende de n. Adems tenemos que:

W kN 2 = e jk = (e j ) = (cos j sen ) = ( 1)
k

Por lo que la ecuacin puede convertirse en:

X (k ) =

( N 2 )1

n =0

N nk k x (n ) + ( 1) x n + 2 W

Debido a que (-1)k = 1 para k pares y 1 para k impares, la ecuacin anterior puede ser dividida en dos ecuaciones, una para los k pares y otra para los k impares:

X (k ) =

( N 2 )1

n =0

N nk x ( n ) + x n + 2 W

para k par

X (k ) =

( N 2 )1

n =0

N nk x ( n ) x n + 2 W

para k impar

Sustituyendo k = 2k para los k pares, y k = 2k+1 para los k impares, podemos escribir la ecuaciones como:

UPV

Pgina

Transformada Rpida de Fourier e Interpolacin en Tiempo Real

X ( 2k ) =

(N 2 )1

n =0

N 2 nk x ( n ) + x n + 2 W

N k = 0,1, . . ., 1 2 N k = 0, 1, . . ., 1 2

X (2k + 1) =

(N 2 )1

n =0

N n 2 nk x ( n ) x n + 2 W W

Debido a que W es una funcin de longitud N, puede escribirse como WN y, de la misma manera, (WN)2 puede escribirse como WN/2. Esto va a permitir escribir de forma ms clara la ecuaciones anteriores. Adems, llamaremos a(n) y b(n) a las expresiones:

N b( n ) = x ( n ) x n + 2 N a ( n ) = x (n ) + x n + 2
De forma que las ecuaciones quedan:

X ( 2k ) =

(N 2 )1
n =0

a(n) W

nk N 2

N k = 0,1, . . ., 1 2 N k = 0,1, . . ., 1 2

X (2k + 1) =

(N 2 )1
n =0

b( n ) W

n N

nk WN 2

Observemos lo que hemos conseguido, partamos de la ecuacin para la transformada de una secuencia x(n) de N puntos:
nk X ( k ) = x ( n ) WN n =0 N 1

k = 0, 1, . . ., N 1

y la hemos descompuesto en dos ecuaciones correspondientes a dos transformadas de N/2 puntos. Si, por ejemplo, la secuencia inicial de puntos fuera de tamao 8 (N=8) siendo los puntos: x(0), x(1), x(3), x(4), x(5), x(6) y x(7), al realizar la primera descomposicin ahora tendremos dos transformadas de 4 puntos. En la primera transformada los nuevos puntos x(n) sern los a(n) que desarrollando su expresin tenemos: a(0) = x(0) + x(4) ser el punto x(0) a(1) = x(1) + x(5) ser el punto x(1) a(2) = x(2) + x(6) ser el punto x(2) a(3) = x(3) + x(7) ser el punto x(3)

Mientras que en la segunda transformada los nuevos puntos vienen dados por b(n)*(WN)n : b(0)*W0 = [x(0) - x(4)]*W0 b(1)*W1 = [x(1) - x(5)]*W1 b(2)*W2 = [x(2) - x(6)]*W2 b(3)*W3 = [x(3) - x(7)]*W3 lo llamaremos: x(4) lo llamaremos: x(5) lo llamaremos: x(6) lo llamaremos: x(7)

Pgina

DISCA

Proceso Digital de Datos en Sistemas de Tiempo Real

Al igual que hemos hecho la descomposicin de la transformada inicial, podemos descomponer de nuevo estas dos transformadas. Ambas transformadas (que son transformadas de secuencias x(n) de 4 puntos) se descompondrn cada una en 2 transformadas de 2 puntos, de manera que tendremos 4 transformadas de 2 puntos. Los puntos para estas transformadas sern: 1 transformada: a(0) = x(0) + x(2) lo llamaremos: x(0) a(1) = x(1) + x(3) lo llamaremos: x(1) 2 transformada: b(0)*W0 = [x(0) x(2)]*W0 lo llamaremos: x(2) b(1)*W2 = [x(1) x(3)]*W2 lo llamaremos: x(3) 3 transformada: a(0) = x(4) + x(6) lo llamaremos: x(4) a(1) = x(5) + x(7) lo llamaremos: x(5) 4 transformada: b(0)*W0 = [x(4) x(6)]*W0 lo llamaremos: x(6) b(1)*W2 = [x(5) x(7)]*W2 lo llamaremos: x(7) Una vez hemos llegado a estas transformadas de dos puntos, ya no podemos seguir descomponiendo y lo que queda es aplicar directamente a cada una de ellas la frmula de la transformada para N=2:

X ( k ) = x (n ) W nk
n =0

k = 0,1

donde:

X (0) = x (0)W 0 + x (1)W 0 = x (0) + x (1)

y:

X (1) = x (0)W 0 + x (1)W 1 = x (0) x (1)

debido a que para N=2:

W 1 = e j 2

= 1

As, aplicando estos resultados a las transformadas, obtenemos: X(0) = x(0) + x(1) X(4) = x(0) x(1) X(2) = x(2) + x(3) X(6) = x(2) x(3) X(1) = x(4) + x(5) X(5) = x(4) x(5) X(3) = x(6) + x(7) X(7) = x(6) x(7)

Los valores X(0), X(4), X(2), ....., X(7) son la secuencia de salida de la Transformada Discreta de Fourier de la secuencia inicial x(n) para N=8 que tenamos. Observemos que mediante este algoritmo

UPV

Pgina

Transformada Rpida de Fourier e Interpolacin en Tiempo Real

la secuencia de salida se obtiene de forma desordenada por lo que habr que reordenarla, para ello se aplica un algoritmo conocido como bit-reversal que veremos ms adelante. Es importante observar que en el desarrollo expuesto para el ejemplo de la transformada de 8 puntos slo se han empleado en los clculos 4 factores twiddle que han sido: W0, W1, W2 y W3 para N=8. De manera que antes de realizar la transformada se pueden calcular a priori los factores que vamos a necesitar que dependern solamente de N. Para realizar una transformada de N puntos se necesitarn slo los N/2 factores twiddle primeros. Bien, pues el algoritmo que a continuacin veremos hace exactamente lo mismo que acabamos de ver. En el caso del ejemplo, en una primera fase calcular a partir de los puntos x(n) los puntos x(n), en una segunda fase calcular a partir de los puntos x(n) los puntos x(n) y en una ltima fase obtendr a partir de los puntos x(n) la secuencia de salida X(k) desordenada que finalmente reordenar. Este algoritmo es conocido como diezmado en frecuencia (DIF) debido a que la secuencia de salida X(k) es descompuesta, o diezmada, en subsecuencias ms pequeas. El nmero de fases o estados para llegar a la secuencia de salida viene dado por M donde N=2M. Un Procesador Digital de Seales (DSP del ingls Digital Signal Processing) es ideal para realizar FFTs ya que puede ejecutar las matemticas implicadas en stas muy rpidamente. Los DSP estn diseados para ello. A continuacin se documenta la implementacin en C del algoritmo.

Implementacin del Algoritmo para la FFT

Antes de ver el cdigo principal veremos un pequeo programa cuya ejecucin tiene como resultado la creacin de un fichero donde se encontrar definido en C un vector con los valores de los 64 factores twiddle necesarios para realizar transformadas de hasta 128 puntos. El fichero generado ser incluido en el fichero donde se encuentre la funcin implementada para el algoritmo de la FFT pues dicha funcin acceder al vector antes comentado para obtener los factores W. /*FFTGEN.C-GENERATES TWIDDLE CONSTANTS */ #include <math.h> #include <stdio.h> #define N 64 /*to generate 64 complex points*/ main() { FILE *fptr; float sinval[N]; float cosval[N]; float arg; int i; fptr=fopen("twid64.h","w"); arg=2*3.141592654/128; for(i=0;i<N;i++) { cosval[i]=(float)cos((i*arg)); sinval[i]=-(float)sin((i*arg)); } fprintf(fptr,"struct\n"); fprintf(fptr," {\n"); fprintf(fptr," double real;\n"); fprintf(fptr," double imag;\n");

Pgina

DISCA

Proceso Digital de Datos en Sistemas de Tiempo Real

fprintf(fptr," }"); fprintf(fptr," w[]={"); for(i=0;i<N;i++) { fprintf(fptr,"%8.5f,%8.5f,\n",cosval[i],sinval[i]); fprintf(fptr," "); } fclose(fptr); return 0; } La implementacin en C para el DSP TMS320C30 del algoritmo de la FFT es la siguiente: /*FFT.C-FFT RADIX-2 USING DIF. FOR UP TO 128 POINTS #include "fft.h" #include "twid64.h" */

/*header file with twiddle constants*/

/* Definicn de COMPLEX: Estructura de los elementos que */ /* forman el vector para FFT */ struct cmpx { float real; float imag; }; typedef struct cmpx COMPLEX;

void FFT(COMPLEX *Y, int N, int signo) /*FFT de vector de N puntos*/ { COMPLEX temp1,temp2; /*temporary storage variables */ int i,j,k; /*loop counter variables */ int upper_leg, lower_leg; /*index of upper/lower butterfly leg*/ int leg_diff; /*difference between upper/lower leg*/ int num_stages=0; /*number of FFT stages, or iterations*/ int index, step; /*index and step between twiddle factor*/ float scale; /*Para escalar en la ifft */ /* log(base 2) de N puntos = M fases o estados i=1; do { num_stages+=1; i=i*2; } while (i!=N); */

/* starting difference between upper and lower butterfly legs*/ leg_diff=N/2; /* step between values in twiddle factor array twid64.h */ step=128/N; /* For N-point FFT */ for (i=0;i<num_stages;i++) /*tantas iteraciones como fases*/ { index=0; for (j=0;j<leg_diff;j++) /*tantas iteraciones como transfor-*/ { /*madas en cada fase*/

UPV

Pgina

Transformada Rpida de Fourier e Interpolacin en Tiempo Real

for (upper_leg=j;upper_leg<N;upper_leg+=(2*leg_diff)) { /*tantas iteraciones como puntos en cada transformada*/ lower_leg=upper_leg+leg_diff; [Link]=(Y[upper_leg]).real + (Y[lower_leg]).real; [Link]=(Y[upper_leg]).imag + (Y[lower_leg]).imag; [Link]=(Y[upper_leg]).real - (Y[lower_leg]).real; [Link]=(Y[upper_leg]).imag - (Y[lower_leg]).imag; (Y[lower_leg]).real=[Link]*(w[index]).[Link]*signo*(w[index]).imag; (Y[lower_leg]).imag=[Link]*signo*(w[index]).imag+ [Link]*(w[index]).real; (Y[upper_leg]).real=[Link]; (Y[upper_leg]).imag=[Link]; } index+=step; } leg_diff=leg_diff/2; step*=2; } /* bit reversal for resequencing data */ j=0; for (i=1;i<(N-1);i++) { k=N/2; while (k<=j) { j=j-k; k=k/2; } j=j+k; if (i<j) { [Link]=(Y[j]).real; [Link]=(Y[j]).imag; (Y[j]).real=(Y[i]).real; (Y[j]).imag=(Y[i]).imag; (Y[i]).real=[Link]; (Y[i]).imag=[Link]; } } if (signo==-1) { scale = (float)(1.0/N); for (i = 0; i < N; i++) { (Y[i]).real = scale*(Y[i]).real; (Y[i]).imag = scale*(Y[i]).imag; }; }; return; } El algoritmo se ha implementado mediante la funcin: FFT donde el significado de los parmetros es el siguiente:

Pgina

10

DISCA

Proceso Digital de Datos en Sistemas de Tiempo Real

Y Y Y

COMPLEX *Y: se especifica la direccin del vector donde se encuentra la secuencia de puntos a la que hay que aplicar la Transformada. Int N: se especifica el nmero de puntos de la secuencia. Int signo: se especifica si hay que realizar la FFT (signo = 1) o la IFFT (signo = -1).

Si observamos la funcin FFT comprobaremos que realiza exactamente los pasos descritos anteriormente. Destacar que esta funcin realiza la FFT para secuencias de valores de N puntos complejos, pudiendo valer N hasta 128 puntos. N siempre debe ser una potencia de 2 (recordemos que esto era una condicin necesaria para poder realizar la FFT). Los factores twiddle necesarios se obtienen del vector W[] definido en el fichero twid64.h, este vector posee los 64 factores twiddle que se utilizan cuando N=128. En el caso en que N sea menor que 128 no ser necesario disponer de otro vector con los factores twiddle correspondientes sino que stos ya se encuentran en el vector actual aunque separados unos de otros 128/N posiciones. Para localizar dentro del vector dichos factores el algoritmo utiliza dos variables: la variable step que indica la distancia entre los factores (se inicializa con el valor 128/N y a medida que se descomponen la transformadas en otras con la mitad de puntos se actualiza multiplicndose por 2) y la variable index que se utiliza para indexar el vector y acceder de uno en uno a los factores necesarios en una transformada (index se inicializa a 0 para obtener el primer factor twiddle y se le suma la variable step para obtener cada uno de los siguientes). Tambin destacar que la funcin FFT despus de obtener la secuencia de salida la reordena mediante un algoritmo conocido como bit-reversal. Este algoritmo, como puede observarse, se encuentra implementado al final de la funcin. Por ltimo, comentar que esta funcin adems de realizar la FFT tambin realiza su inversa o IFFT, para ello se dispone del parmetro signo que se pasa como argumento en la llamada a la funcin. Cuando signo vale 1 se realiza la FFT mientras que cuando vale 1 se realiza la IFFT. Para realizar la Transformada Inversa de Fourier slo hace falta cambiar el signo de unos factores twiddle y efectuar al final un escalado de la secuencia de salida dividiendo cada valor por N. La funcin FFT ha sido probada y utilizada en el DSP TMS320C30 obtenindose los resultados deseados.

_ APARTADO 2 _______________________________________ 5. Interpolacin

Supongamos una seal muestreada a una frecuencia determinada, la interpolacin consiste en introducir puntos de muestreo entre las muestras ya adquiridas. Existen muchas tcnicas para interpolar, como por ejemplo la interpolacin lineal que consiste simplemente en unir los puntos de muestreo con lneas rectas, evidentemente sta no es la mejor solucin. Otro tipo de interpolacin es la polinomial, en la cual se utilizan polinomios de distintos grados (segn la precisin requerida) para reconstruir la seal. Pero las tcnicas ms interesantes para nosotros son la interpolacin a partir del espectro en frecuencia de una seal y la interpolacin senoidal, las cuales aseguran que si la seal original ha sido muestreada cumpliendo el teorema del muestreo sta ser reconstruida con gran exactitud.

UPV

Pgina

11

Transformada Rpida de Fourier e Interpolacin en Tiempo Real

6. Interpolacin basada en la FFT

Podemos realizar la interpolacin de una seal mediante el uso de la Transformada Discreta de Fourier y su inversa. Esta interpolacin se realiza matemticamente una vez tenemos todos los puntos muestreados de la seal, es decir, se aplica en tiempo no real. Deben seguirse los siguientes pasos: Se realiza la Transformada Discreta de Fourier de la seal de N puntos obtenida al muestrear. Para ello, puede emplearse la implementacin del algoritmo para la FFT vista anteriormente. Se aaden ceros al espectro. Para ello tenemos que separar la secuencia de valores obtenida como resultado de la Transformada en dos mitades y aadir entre ellas los ceros que deseemos (tantos como nuevos puntos se quieran obtener). A la secuencia de valores obtenida una vez aadidos los ceros se le aplica la Inversa de la Transformada Discreta de Fourier obtenindose, como resultado, la seal inicial pero con ms puntos (tantos ms como ceros introducidos). La Inversa de la Transformada puede realizarse mediante la IFFT tambin implementada en el algoritmo visto anteriormente. Utilizando la funcin FFT resulta muy sencillo aplicar este mtodo de interpolacin con el que adems, como ya se coment, si la seal original ha sido muestreada cumpliendo el teorema del muestreo, se asegura que la seal ser reconstruida con exactitud. Sin embargo, el inconveniente que posee el mtodo es que no puede aplicarse en tiempo real (no pueden obtenerse nuevos puntos a medida que van obtenindose las muestras de la seal), sino que slo puede realizarse la interpolacin cuando se dispone de todas las muestras. Esto es lgico ya que para calcular la Transformada se necesitan todos los puntos. En el siguiente apartado veremos una forma de realizar la interpolacin en tiempo real, se har mediante la interpolacin senoidal basada en la funcin SINC. Sobre este mtodo se ha centrado y desarrollado principalmente este trabajo con el objetivo de implementar una serie de funciones en C que realicen dicha interpolacin y luego poder efectuar un anlisis de los resultados que se obtengan.

7. Interpolacin Senoidal, Algoritmos e Implementacin en C

La ecuacin para la interpolacin senoidal viene dada por:

x (t ) =

n =

x (n )

sen ( 0 (t nT )) 0 (t nT )

Donde x(t) es la seal continua reconstruida, x(n) es la secuencia de muestras, 0 es la pulsacin y T es el periodo de muestreo. La interpolacin senoidal asegura una reconstruccin de la seal lo ms exacta posible y, adems, puede aplicarse en tiempo real. Atendiendo a la frmula anterior se puede observar que la interpolacin senoidal es un proceso que implica un nmero infinito de sumas. Evidentemente el nmero de muestras que se considerar nunca ser infinito por lo que la reconstruccin no ser exacta pero s lo suficientemente aproximada. Esto se debe a que los puntos muestreados que ms influencia ejercen a la hora de determinar un nuevo punto interpolado son aquellos que se encuentran ms cerca del nuevo punto y cuanto ms lejos se llega en el sumatorio menos influencia ejercen los puntos utilizados sobre el punto a interpolar. De este modo es posible enventanar la seal (utilizando un nmero finito de puntos en la frmula) y an as conseguir una buena aproximacin en la reconstruccin de la seal.

Pgina

12

DISCA

Proceso Digital de Datos en Sistemas de Tiempo Real

Atendiendo de nuevo a la frmula, se puede concluir que la interpolacin senoidal reconstruye la seal mediante un sumatorio de la seal senoidal SINC desplazada. La seal SINC viene dada por la frmula:

sinc(x ) =
Su representacin grfica es:

sen (x ) x

2 3

4 5

Figura 1 En la figura 1 slo se representa la funcin SINC para los valores positivos del eje de las abscisas, esta funcin es simtrica para los valores negativos. En la interpolacin senoidal se tiene una seal SINC por cada punto muestreado y la manera en que se desplazan dichas seales puede observarse en la figura 2. Puntos muestreados

Figura 2 La seal SINC de una muestra cualquiera vale 1 en la abscisa de dicha muestra, abscisa que para la seal SINC vale 0 (ya que SINC(0)=1). En las abscisas de todas las dems muestras dicha seal SINC vale 0, por lo que los valores para estas abscisas son iguales a n siendo n distinto de cero (ya que SINC(n) = 0 para n distinto de 0). De esta manera se observa que una seal SINC entre dos muestras

UPV

Pgina

13

Transformada Rpida de Fourier e Interpolacin en Tiempo Real

debe desplazarse sobre el eje de las abscisas unidades. Resumiendo, la muestra que determina la seal SINC est en la abscisa 0 y las muestras siguientes se encuentran en las abscisas , 2, 3, ..., n siendo n el nmero de muestras siguientes. Este razonamiento es igual para las muestras anteriores cuyas abscisas son -, -2, -3, ..., -n siendo n el nmero de muestras anteriores (la seal SINC es simtrica). Para calcular un nuevo punto interpolado se multiplica cada uno de los puntos muestreados por el valor que tenga su correspondiente SINC en la abscisa del punto nuevo a calcular. Despus se realiza la suma de estos productos obtenindose as el nuevo punto interpolado. Como ya se ha comentado, a la hora de calcular un nuevo punto interpolado se tienen en cuenta slo las muestras ms cercanas a dicho punto pues son las que ms influencia ejercen. El resto de muestras ms lejanas no se tienen en cuenta porque el despreciarlas no se comete un error suficientemente significativo en el clculo del nuevo punto. El nmero de muestras a considerar se toma simtrico, es decir, el mismo nmero de muestras anteriores que posteriores al punto nuevo que se va a obtener. El conjunto de muestras que se utilizan para determinar un nuevo punto forman lo que se conoce como ventana de interpolacin. Habr una seal senoidal SINC para cada una de las muestras de la ventana de interpolacin. En el clculo de todos los puntos nuevos que se deseen obtener entre dos muestras consecutivas la ventana de interpolacin a utilizar ser, lgicamente, la misma. Esta ventana habr que actualizarla sucesivamente con nuevas muestras para as ir obteniendo los puntos interpolados entre todas las muestras. Como ya se coment, esta tcnica de interpolacin se puede aplicar en tiempo real ya que no hace falta tener toda la seal muestreada para obtener los nuevos puntos sino que a medida que se van obteniendo nuevas muestras se van calculando algunos de los nuevos puntos (recordemos que en la interpolacin basada en la FFT esto no era posible pues en este caso se deba tener toda la seal antes de poder interpolar). El tamao de la ventana de interpolacin determina el rango de valores para los cuales se necesita calcular el valor de la funcin SINC. Si, por ejemplo, se consideran 4 muestras anteriores y 4 muestras posteriores para la obtencin de un nuevo punto (ventana de interpolacin de tamao 8), entonces se necesitarn valores para la seal SINC(x) desde x=0 hasta x=4. El nmero de valores a obtener para la SINC en un rango dado depende del nmero de puntos nuevos que se deseen obtener entre dos muestras. Los puntos nuevos que se interpolen cada dos muestras tienen que guardar siempre la misma distancia entre ellos y entre las muestras, dado que el resultado de interpolar ha de ser el de reconstruir la seal como si se hubiera muestreado a una frecuencia mayor. Llamaremos Intervalo entre los valores a la siguiente expresin: Intervalo entre los valores = /(nmero de puntos nuevos entre muestras +1) De esta manera, continuando con el ejemplo, si se desea obtener un punto nuevo cada dos muestras el Intervalo ser igual a /2, lo cual quiere decir que en el rango [0..4] se deben obtener los valores de la seal SINC(x) para x = 0, /2, , 3/2, 2, 5/2, 3, 7/2 y 4. (Los valores para las x negativas son los mismos). Los valores que de esta manera se obtengan para la seal SINC sern los mismos para todas las seales SINC que intervengan en el clculo de un nuevo punto. Para cada seal SINC habr que

Pgina

14

DISCA

Proceso Digital de Datos en Sistemas de Tiempo Real

emplear un valor u otro dependiendo de cmo est desplazada dicha seal o, lo que es lo mismo, de la distancia al punto nuevo a la que se encuentre la muestra asociada a la correspondiente seal SINC. De este modo se podr obtener de forma anticipada una tabla con los valores de la seal SINC necesarios para realizar una interpolacin con un tamao determinado de ventana de interpolacin y con un nmero determinado de puntos nuevos a obtener entre cada dos muestras. Si por ejemplo ahora se desean obtener dos puntos (en lugar de uno) cada dos muestras con una ventana de interpolacin del mismo tamao que antes (8 muestras), el Intervalo ser igual a /3 y los valores de la seal SINC(x) que se tendrn que utilizar sern los correspondientes a x = 0, /3, 2/3, , 4/3, 5/3, 2, 7/3, 8/3, 3, 10/3, 11/3, 4. De estos valores se utilizarn con la 4 muestras anteriores para obtener el primer punto nuevo entre dos muestras los correspondientes a cuando x = /3, 4/3, 7/3 y 10/3, y para obtener el segundo punto nuevo entre las mismas muestras los correspondientes a x = 2/3, 5/3, 8/3 y 11/3. En el caso de las 4 muestras posteriores los valores de la SINC a utilizar para obtener el primer punto nuevo son los valores que utilizan las muestras anteriores para el clculo del segundo punto nuevo y para obtener el segundo punto los valores que utilizan las muestras anteriores para el clculo del primero, esto es debido a la simetra de la funcin SINC. El algoritmo que se ha desarrollado para generar la tabla de valores citada anteriormente se implementa en la siguiente funcin en C: #include <math.h> #define true 1 #define false 0 int gen_valores_sinc (int tam_ventana, int num_puntos_nuevos, double *vector_valores_sinc) { //El tamao del vector tiene que ser: //vector_valores_sinc >= (tam_ventana*num_puntos_nuevos) double pi, auxiliar, intervalo, X; int num_muestras, indice, i, j; if (((tam_ventana%2) != 0) //"%" obtiene el resto de la divisin ||(num_puntos_nuevos<1)) return false; num_muestras = tam_ventana/2; //tam_ventana es par. //pi = 4.0 * atan(1.0); pi = 3.14159265359; auxiliar = 1/(((double)num_puntos_nuevos)+1); intervalo = pi*auxiliar; indice = 0; X = intervalo; for (i=0; i<num_muestras; i++) { for (j=0; j<num_puntos_nuevos; j++) { auxiliar = 1/X; vector_valores_sinc[indice] = auxiliar*((double)sin(X)); indice++; X = X + intervalo; }; X = X + intervalo; };

UPV

Pgina

15

Transformada Rpida de Fourier e Interpolacin en Tiempo Real

return true; } Donde el significado de los parmetros es el siguiente:

Y Y Y

int tam_ventana: se especifica mediante un entero el tamao de la ventana de interpolacin. Este valor tiene que ser par ya que en el clculo de los nuevos puntos se utiliza el mismo nmero de muestras anteriores que posteriores. El tamao de la ventana de interpolacin es utilizado por esta funcin para obtener el rango en el que se van a calcular los valores de la funcin SINC. int num_puntos_nuevos: se especifica mediante un entero el nmero de puntos nuevos que se desean obtener cada dos muestras. Este nmero es utilizado por la funcin para obtener los valores concretos de la funcin SINC que se necesitarn en la interpolacin. double *vector_valores_sinc: se especifica la direccin de un vector donde la funcin almacenar los valores de la SINC obtenidos. El tamao del vector tendr que ser suficiente para poder almacenase todos los valores. Recordemos que el nmero de valores necesarios de la funcin SINC que calcular esta funcin viene determinado por el producto del tamao de la ventana de interpolacin por el nmero de puntos nuevos a obtener.

Si se observa la funcin implementada puede apreciarse que ha sido implementada para minimizar el nmero de productos necesarios. La funcin consta principalmente de dos bucles: en el primero se realiza un nmero de iteraciones igual al tamao de la ventana de interpolacin y en el segundo, dentro del primero, se realiza un nmero de iteraciones igual al nmero de puntos nuevos a obtener. De esta manera el segundo bucle se ejecuta un nmero de veces igual al tamao de la ventana de interpolacin. Antes de la ejecucin de los bucles se obtiene el Intervalo entre los valores (/[nmero de puntos nuevos entre muestras +1]) que se utilizar para ir obteniendo los valores de X en el clculo de los valores de la funcin SINC(X). Cada uno de los valores de la funcin SINC(X) se obtiene en cada una de las iteraciones del segundo bucle. Como vimos en la teora el primer valor para X se corresponde con el valor del Intervalo entre los valores y los siguientes valores para X se pueden obtener sumando al valor actual dicho Intervalo entre los valores. Para ello, se inicializa X con el valor del Intervalo y despus en cada iteracin del segundo bucle se calcula el valor de la funcin SINC(X) y se actualiza el valor de X sumndole el Intervalo entre los valores. Es importante observar como despus del segundo bucle y antes de una nueva iteracin del primer bucle se vuelve a sumar a X el Intervalo entre los valores, esto es debido a que en ese momento X tiene un valor igual a n siendo n distinto de 0 y para este caso la funcin SINC(X) vale 0, valor que conocemos y que adems no ser utilizado por corresponder al valor que la seal SINC tiene en la posicin de las muestras, no en la posicin de los puntos nuevos que es lo que nos interesa. Despus de obtener una tabla con los valores de la seal SINC que se necesitarn en la interpolacin se debe realizar sta. Para ello se han implementado dos algoritmos ms: el primero realiza el clculo de los puntos nuevos entre dos muestras a partir de la ventana de interpolacin y los valores para la seal SINC, y el segundo realiza la actualizacin de la ventana de interpolacin y llama al primer algoritmo para cada muestra de la seal a interpolar que se vaya obteniendo en tiempo real. Adems, el segundo algoritmo se encarga de completar la interpolacin de todos los puntos cuando la seal a interpolar tiene un nmero de muestras finito que adems se repite en el tiempo. El primer algoritmo se presenta a continuacin implementado en la siguiente funcin en C. Esta funcin slo ser utilizada por el segundo algoritmo que veremos ms adelante. void interpolar (double *vector_valores_sinc, double *vector_ventana, int tam_ventana, double *vector_puntos_nuevos, int num_puntos_nuevos) { double auxiliar; int i, j, indice, num_muestras;

Pgina

16

DISCA

Proceso Digital de Datos en Sistemas de Tiempo Real

num_muestras = tam_ventana/2;

//El tamao de la ventana es //siempre par.

for (i=0; i<num_puntos_nuevos; i++) { auxiliar = 0.0; indice = 0; for (j=(num_muestras-1); j>=0; j--) { auxiliar = auxiliar + (vector_ventana[j] * vector_valores_sinc[indice+i]); auxiliar = auxiliar + (vector_ventana[(tam_ventana-1)-j] * vector_valores_sinc[indice+((num_puntos_nuevos-1)-i)]); indice = indice + num_puntos_nuevos; }; vector_puntos_nuevos[i] = auxiliar; }; } Donde el significado de los parmetros es el siguiente:

Y Y Y Y Y

double *vector_valores_sinc: se especifica la direccin del vector donde se encuentran los valores para la funcin SINC necesarios en el clculo de los nuevos puntos. double *vector_ventana: se especifica la direccin de la ventana de interpolacin donde se encuentran las muestras que se deben utilizar para el clculo de los nuevos puntos. int tam_ventana: se especifica el tamao de la ventana de interpolacin, es decir, el nmero de muestras que se considern en el clculo de cada punto nuevo. double *vector_puntos_nuevos: se especifica la direccin del vector donde se almacenarn los puntos nuevos calculados. int num_puntos_nuevos: se especifica el nmero de puntos nuevos a calcular. El tamao del vector para almacenar los puntos nuevos tiene que ser igual o mayor que num_puntos_nuevos.

El algoritmo consta principalmente de dos bucles: el primer bucle tiene un nmero de iteraciones igual al nmero de puntos nuevos a calcular, de manera que en cada iteracin de este bucle se calcular un punto nuevo, y dentro de este primero se encuentra el segundo bucle con un nmero de iteraciones igual a la mitad del tamao de la ventana de interpolacin. De esta manera, para el clculo de cada punto nuevo se ejecuta el segundo bucle donde lo que se realizan son los productos de los valores que la seales SINC tienen en la posicin del punto nuevo a calcular con las muestras correspondientes de la ventana de interpolacin y la suma de todos estos productos, obtenindose, como se explic anteriormente, el nuevo punto. La suma de todos los productos no se realiza al final sino que stos se van sumando a la vez que van obtenindose. En cada iteracin del segundo bucle se realizan dos del total de productos necesarios correspondientes a dos muestras de la ventana de interpolacin, por ello el nmero de iteraciones es la mitad del tamao de la ventana de interpolacin. Cada muestra de esta ventana tiene que multiplicarse por el valor que su seal SINC tenga en la posicin del punto nuevo que toque calcular. Lo que se hace es que en cada iteracin del segundo bucle se toma una muestra anterior y la simtrica posterior de la ventana, entendindose como muestra simtrica aquella que se encuentra en la misma posicin pero opuesta dentro de la ventana y tomndose como centro de la ventana la mitad de sta, es decir, en la primera iteracin se toma la primera muestra anterior de la ventana (que es la muestra con posicin: num_muestras-1 siendo num_muestras la mitad del tamao de la ventana de interpolacin) y la primera muestra posterior de la ventana (que es la muestra con posicin: num_muestras siendo num_muestras la mitad del tamao de la ventana de interpolacin), en la segunda iteracin se toma la segunda muestra anterior (con posicin:
UPV

Pgina

17

Transformada Rpida de Fourier e Interpolacin en Tiempo Real

num_muestras-2) y la segunda muestra posterior (con posicin: num_muestras+1), etc.. El valor de la seal SINC que debe multiplicar a una muestra de la ventana de interpolacin depender de la distancia a la que se encuentre dicha muestra del nuevo punto (distancia disponible con la variable indice) y del nmero del punto que se vaya a obtener (disponible con la variable i del primer bucle). Para obtener el valor se accede al vector: vector_valores_sinc. El segundo algoritmo tambin se ha implementado mediante una funcin en C llamada: gen_nuevos_puntos. Esta funcin utiliza la funcin interpolar antes descrita. Las funciones: gen_valores_sinc y gen_nuevos_puntos son las dos funciones que tendrn que ser usadas por cualquier programa que desee realizar una interpolacin en tiempo real. La funcin gen_valores_sinc tendr que usarse, tal como se explic, para obtener los valores de la seal SINC necesarios y luego la funcin gen_nuevos_puntos, que explicaremos a continuacin, se llamar varias veces para obtener los nuevos puntos. Esta funcin puede verse como una caja negra donde por un lado tiene como entrada los puntos de la seal a interpolar y por otro lado tiene como salida los puntos de la seal ya interpolada. As, a medida que se van obteniendo las muestras de la seal a interpolar stas se pasan de una en una a la funcin gen_nuevos_puntos que tras cada ejecucin ir devolviendo los puntos nuevos o interpolados, todo esto en tiempo real, sin necesidad de esperar a tener todas las muestras de la seal a interpolar. Por ejemplo, si deseamos realizar una interpolacin de una seal cualquiera obteniendo 3 puntos nuevos entre cada dos muestras con una ventana de interpolacin de tamao 4 habr que hacer lo siguiente: primero se llamar a la funcin gen_valores_sinc para obtener los valores necesarios de la seal SINC y despus podremos empezar a obtener las muestras de la seal. Con cada muestra que se obtenga se llamar a la funcin gen_nuevos_puntos pasndole dicha muestra, con la muestra nmero 4 (debido al tamao de la ventana de interpolacin), que corresponder con la cuarta llamada a la funcin gen_nuevos_puntos, la funcin devolver los cuatro primeros puntos de la funcin interpolada y a partir de aqu con cada nueva muestra con la que se llame a la funcin sta devolver los cuatro siguientes puntos. De esta manera, volviendo al concepto de caja negra, la funcin gen_nuevos_puntos puede verse como una caja por la que entra una muestra y se obtienen cuatro, realizndose una interpolacin en tiempo real donde parece que se obtengan cuatro puntos por cada muestra. La implementacin de la funcin gen_nuevos_puntos es la siguiente: int gen_nuevos_puntos (double punto, int numero_punto, // >=0; Los puntos se //numeran a partir de cero. int num_puntos_nuevos, double *vector_ventana, int tam_ventana, double *vector_valores_sinc, double *vector_puntos_a_obtener, // Tamao >= num_puntos_nuevos+1 int senal_se_repite, int max_numero_puntos, double *vector_senal_interpolada) // Si la seal no se repite, // max_numero_puntos y // vector_senal_interpolada se ignoran. { int i, num_muestras, pos_punto, distancia, pos_puntos_a_obtener, ultima_posicion, pos_punto_fin; if ( ((tam_ventana%2) != 0) //"%" obtiene el resto de la divisin ||(num_puntos_nuevos<1) ) return false; num_muestras = tam_ventana/2; //tam_ventana es par. for (i=0; i<(tam_ventana-1); i++)

Pgina

18

DISCA

Proceso Digital de Datos en Sistemas de Tiempo Real

vector_ventana[i] = vector_ventana[i+1]; vector_ventana[tam_ventana-1] = punto; for (i=0; i<=num_puntos_nuevos; i++) vector_puntos_a_obtener[i] = 0.0; if (numero_punto >= (tam_ventana-1)) { vector_puntos_a_obtener[0] = vector_ventana[num_muestras-1]; interpolar(vector_valores_sinc, vector_ventana, tam_ventana, &(vector_puntos_a_obtener[1]), num_puntos_nuevos); }; if (senal_se_repite == 1) { pos_punto = (num_puntos_nuevos+1)*numero_punto; vector_senal_interpolada[pos_punto] = punto; if (numero_punto >= (tam_ventana-1)) { distancia = (num_puntos_nuevos+1)*num_muestras; pos_puntos_a_obtener = pos_punto - distancia; for (i=1; i<=num_puntos_nuevos; i++) vector_senal_interpolada[pos_puntos_a_obtener+i] = vector_puntos_a_obtener[i]; if (numero_punto == (max_numero_puntos-1)) { ultima_posicion = (max_numero_puntos*(num_puntos_nuevos+1))-1; pos_punto_fin = (tam_ventana-2)*(num_puntos_nuevos+1); for (pos_punto=0; pos_punto<=pos_punto_fin; pos_punto=pos_punto+(num_puntos_nuevos+1)) { for (i=0; i<(tam_ventana-1); i++) vector_ventana[i] = vector_ventana[i+1]; vector_ventana[tam_ventana-1] = vector_senal_interpolada[pos_punto]; pos_puntos_a_obtener = pos_punto - distancia; //Como vector_senal_interpolada es una cola cclica: if (pos_puntos_a_obtener<0) pos_puntos_a_obtener = ultima_posicion + pos_puntos_a_obtener + 1; interpolar(vector_valores_sinc, vector_ventana, tam_ventana, &(vector_senal_interpolada[pos_puntos_a_obtener+1]), num_puntos_nuevos); }; }; }; }; return true; } Donde el significado de los parmetros es el siguiente:

Y Y
UPV

double punto: especifica la muestra que se pasa a la funcin. int numero_punto: especifica el nmero de muestra que se pasa.

Pgina

19

Transformada Rpida de Fourier e Interpolacin en Tiempo Real

Y Y Y Y Y Y Y Y

int num_puntos_nuevos: especifica el nmero de puntos nuevos que se desea obtener. double *vector_ventana: especifica la direccin de la ventana de interpolacin donde se encuentran las muestras. int tam_ventana: especifica el tamao de la ventana de interpolacin. double *vector_valores_sinc: especifica la direccin del vector con los valores de la seal SINC necesarios. double *vector_puntos_a_obtener: especifica la direccin del vector donde se almacenarn los puntos generados a devolver. int senal_se_repite: especifica si la seal que se est interpolando tiene un nmero finito de muestras diferentes que se repiten en el tiempo. int max_numero_puntos: especifica cul es el nmero de muestras de la seal a interpolar en caso de haberse indicado con el parmetro anterior que la seal se repite. double *vector_senal_interpolada: especifica la direccin donde se devolver la seal interpolada a medida que vayan obtenindose los puntos. Este parmetro slo se utilizar en el caso de haberse indicado que la seal se repite, en este caso con la ltima muestra de la seal a interpolar (indicada por el parmetro max_numero_puntos) se obtendr en este vector toda la seal interpolada.

El funcionamiento de la funcin es el siguiente: en primer lugar actualiza la ventana de interpolacin con la nueva muestra que se le ha pasado en el parmetro punto, para ello desplaza toda la ventana perdindose la muestra ms antigua (ver figura 3). Las muestras que quedan en este momento en la ventana de interpolacin sern las que se utilizarn para la obtencin de los nuevos puntos. Como el tamao de la ventana es siempre par, la primera mitad de las muestras constituirn las muestras anteriores y la segunda mitad de las muestras sern la muestras posteriores obtenindose los nuevos puntos entre ambos grupos de muestras. La funcin devolver como puntos de la seal interpolada la muestra anterior ms cercana a los puntos nuevos y, por supuesto, los puntos nuevos. Para la obtencin de los puntos nuevos, una vez actualizada la ventana de interpolacin, se llama a la funcin interpolar. Es importante observar como la funcin gen_nuevos_puntos no genera nuevos puntos hasta que la ventana de interpolacin est llena con muestras, esto quiere decir que en las primeras veces que se llama a esta funcin lo nico que se hace es actualizar la ventana de interpolacin sin generar nuevos puntos ya que stos no pueden obtenerse si an no tenemos la ventana completa (ver figura 3). En el caso de no indicar que la seal a interpolar se repite, la ejecucin de la funcin finaliza con lo descrito. Si se indica que la seal se repite entonces se entra en una segunda parte del cdigo que tiene como funcin ir almacenando en el vector: vector_senal_interpolada los puntos de la seal interpolada para que al final, cuando se obtenga la ltima muestra, se disponga del vector con toda la seal. Para ello se realizan varias cosas: primero se almacena en la posicin adecuada del vector: vector_senal_interpolada la muestra que se pas como argumento, dejando los huecos necesarios para la obtencin de nuevos puntos en un futuro. Despus se comprueba que la ventana de interpolacin est completa, si no es as se finaliza y en caso contrario se almacenan los puntos nuevos que se obtuvieron en la primera parte del algoritmo en las posiciones del vector: vector_senal_interpolada donde deban situarse. Estas posiciones estarn libres porque cada punto tiene una posicin nica y reservada. Por eso cuando se almacena en el vector la muestra pasada como argumento se hace dejando libres las posiciones correspondientes a los puntos que debern obtenerse en dichas posiciones en llamadas posteriores a la funcin. Una vez realizado esto se comprueba si la muestra actual (pasada como argumento) es la ltima de la seal, si no es as se finaliza y en caso contrario se deben obtener nuevos puntos para completar toda la seal ya interpolada. Es importante observar que cuando se obtiene la ltima muestra de la seal y se llama a la funcin gen_nuevos_puntos sta, en la primera parte del cdigo, obtiene lo que en un primer momento podramos pensar como ltima serie de puntos nuevos pero, sin embargo, dependiendo del tamao de la ventana de interpolacin, entre las primera muestras an quedan puntos por obtener que no pudieron calcularse por no disponerse en la ventana de interpolacin de las muestras anteriores necesarias (por eso hay que esperar a completar la ventana para poder empezar a obtener nuevos puntos) y lo mismo ocurre con las ltimas muestras donde tampoco se habrn podido generar nuevos puntos por no disponer de las muestras posteriores necesarias, ya que la actual es la ltima (ver figura 3). Pues bien, si se supone que la seal se repite, es decir, despus de esta ltima muestra viene otra vez la primera de todas, entonces s tenemos las muestras anteriores y posteriores que antes nos faltaron para completar la interpolacin de toda la seal. Esta ltima parte del cdigo lo que hace es
Pgina

20

DISCA

Proceso Digital de Datos en Sistemas de Tiempo Real

exactamente esto, genera mediante la funcin interpolar los puntos nuevos que faltan por obtener. Para ello va actualizando la ventana de interpolacin con las nuevas muestras que sern otra vez las primeras de todas (el nmero de muestras a utilizar depende del tamao de la ventana) y llama para cada nueva muestra a la funcin interpolar obtenindose nuevos puntos que se almacenan en las posiciones reservadas correspondientes del vector: vector_senal_interpolada.

Figura 3

8. Ejecucin de los Algoritmos y Estudio de los Resultados

Una vez hemos visto el esquema y funcionamiento de los algoritmos implementados que realizan la interpolacin senoidal en tiempo real vamos a realizar un estudio de su eficiencia y precisin en la obtencin de los nuevos puntos. Para ello analizaremos los resultados que se han obtenido al realizar varias pruebas ejecutando los algoritmos con varias seales y diferentes caractersticas de interpolacin. Para realizar todas la pruebas se ha implementado un programa ejemplo en Visual C++ que utiliza las funciones en C descritas anteriormente. Estas funciones se encuentran definidas en el fichero: Func.h e implementadas en el fichero: Func.c. El cdigo del programa ejemplo se presenta a continuacin. #include <WINDOWS.H> #include <winbase.h> #include #include #include #include #include <math.h> <stdio.h> <string.h> <stdlib.h> "Func.h"

//************** CARACTERSTICAS GENERALES *********************** #define MAX_NUM_VALORES 2000 //Mximo nmero de valores de la //seal interpolada resultante.

UPV

Pgina

21

Transformada Rpida de Fourier e Interpolacin en Tiempo Real

#define MAX_NUM_MUESTRAS 80 #define MAX_NUM_PUNTOS_NUEVOS 40

//MAX_TAM_VENTANA/2; //Puntos nuevos por cada punto de //la seal original. double vector_senal_interpolada[MAX_NUM_VALORES]; double vector_valores_sinc[(MAX_NUM_MUESTRAS*MAX_NUM_PUNTOS_NUEVOS)]; double vector_ventana[MAX_NUM_MUESTRAS*2]; double vector_puntos_a_obtener[(MAX_NUM_PUNTOS_NUEVOS+1)]; //**************************************************************** //************** CARACTERSTICAS CONFIGURABLES ******************* #define tam_senal_a_diezmar 1024 #define puntos_por_periodo_senal_a_diezmar 32 //Entre 0 y 2PI (el //periodo) tienen que haber al menos dos valores para que la seal //est bien muestreada. Luego se va a hacer un diezmado de la //seal que se genere para posteriormente interpolar los valores y //comprobar que coinciden con los originales. Este diezmado hay //que tenerlo en cuenta. Ya que si ahora se obtienen 8 puntos por //periodo y luego se hace un diezmado obteniendo un punto cada //4, la seal resultante tedra dos puntos por periodo que se //corresponde con la mnima frecuencia de muestreo. No estara //mal pero es conveniente que la seal a interpolar haya sido //muestreada a una frecuencia superior a la de Nyquist para //obtener un error no significativo mediante la interpolacin //senoidal (basada en la funcin SINC) que es la utilizada en las //pruebas. #define amplitud_senal_a_diezmar 1000 #define diezmado 8 //La senal de entrada (antes de interpolar) se // diezma obteniendo un solo punto por cada //'diezmado' puntos.

#define tam_senal_a_interpolar (tam_senal_a_diezmar/diezmado) #define ultimo_tam_ventana 100 #define num_puntos_nuevos (diezmado-1) //Por cada punto se obtienen //'num_puntos nuevos' ms. #define senal_se_repite 1 //**************************************************************** #define PI 3.14159265359 void gen_seno(double *vector_senal, int num_puntos, int num_puntos_por_periodo, int amplitud) { double intervalo, auxiliar, valor; int i; intervalo = ((double)PI)/((double)num_puntos_por_periodo); auxiliar = 0; for(i=0; i<num_puntos; i++) { valor = sin(auxiliar); vector_senal[i] = valor*amplitud; auxiliar = auxiliar + intervalo; };
Pgina

22

DISCA

Proceso Digital de Datos en Sistemas de Tiempo Real

} main() { double senal_a_diezmar[tam_senal_a_diezmar]; double senal_a_interpolar[tam_senal_a_interpolar]; double error, media_error, varianza_error, desviacion_tipica_error; //double media_porcent_error, varianza_porcent_error, // desviacion_tipica_porcent_error; int tam_ventana, i, j, tam_final; char nom_fichero[20]; char buffer[10]; FILE *fptr1, *fptr2; int senal_continua = 0; int ficheros_independientes = 1; //Se genera la seal en la que luego se har un diezmado y //seguidamente la interpolacin. if (senal_continua == 1) for (i=0; i<tam_senal_a_diezmar; i++) senal_a_diezmar[i]=amplitud_senal_a_diezmar; else gen_seno(senal_a_diezmar, tam_senal_a_diezmar, puntos_por_periodo_senal_a_diezmar, amplitud_senal_a_diezmar); //Se realiza el diezmado: j=0; for (i=0; i<tam_senal_a_interpolar; i++) { senal_a_interpolar[i] = senal_a_diezmar[j]; j = j+diezmado; }; fptr1=fopen("[Link]","a"); fprintf(fptr1,"\n*********************************************"); fprintf(fptr1,"\n**** SENO VALORES: entre -1000 y +1000 ****"); fprintf(fptr1,"\n*******************************************\n"); fclose(fptr1); for(tam_ventana=2; tam_ventana<=ultimo_tam_ventana; tam_ventana=tam_ventana+2) { //Se obtienen los valores necesarios de la funcin SINC: gen_valores_sinc (tam_ventana, num_puntos_nuevos, vector_valores_sinc); //Se realiza la interpolacin: for (i=0; i<tam_senal_a_interpolar; i++) { gen_nuevos_puntos (senal_a_interpolar[i], i, // >=0 num_puntos_nuevos, vector_ventana, tam_ventana, vector_valores_sinc, vector_puntos_a_obtener, // Tamao >=
UPV Pgina

23

Transformada Rpida de Fourier e Interpolacin en Tiempo Real

//num_puntos_nuevos+1 senal_se_repite, // Si la seal no se //repite, tam_senal_a_interpolar y //vector_senal_interpolada se ignoran. tam_senal_a_interpolar, vector_senal_interpolada); }; tam_final = tam_senal_a_interpolar*(num_puntos_nuevos+1); //tam_final es igual a tam_senal_a_diezmar //Se generan los resultados y estadsticas: media_error = 0.0; for(i=0;i<tam_final;i++) { if ((i%diezmado) != 0) { error = senal_a_diezmar[i] - vector_senal_interpolada[i]; media_error = media_error + error; }; }; media_error = media_error/(tam_final-tam_senal_a_interpolar); varianza_error = 0.0; for(i=0;i<tam_final;i++) { if ((i%diezmado) != 0) { error = senal_a_diezmar[i] - vector_senal_interpolada[i]; varianza_error = varianza_error + pow((error-media_error),2); }; }; varianza_error=varianza_error/(tam_final-tam_senal_a_interpolar-1); desviacion_tipica_error = sqrt(varianza_error); nom_fichero[0] = 0; strcpy(nom_fichero, "RESULT_" ); itoa(tam_ventana, buffer, 10 ); strcat(nom_fichero, buffer); strcat(nom_fichero, "[Link]"); fptr1=fopen("[Link]","a"); fprintf(fptr1,"\n/*************** %s ***************/", nom_fichero); fprintf(fptr1,"\nNmero puntos seal original: %i", tam_senal_a_diezmar); fprintf(fptr1,"\nDiezmado de la seal original: %i", diezmado); fprintf(fptr1,"\nNmero puntos seal a interpolar: %i", tam_senal_a_interpolar); fprintf(fptr1,"\nTamao ventana interpolacin: %i", tam_ventana); fprintf(fptr1,"\nPuntos a obtener entre dos muestras: %i", num_puntos_nuevos); fprintf(fptr1,"\nTamao final seal interpolada: %i", tam_final); fprintf(fptr1,"\n_______________ RESULTADOS _______________"); fprintf(fptr1,"\nMEDIA del ERROR: %8.8f", media_error); fprintf(fptr1,"\nDESVIACIN TPICA del error: %8.8f", desviacion_tipica_error);
Pgina

24

DISCA

Proceso Digital de Datos en Sistemas de Tiempo Real

fprintf(fptr1,"\nPORCENTAJE DESVIACIN TPICA del error: %8.8f %%", (desviacion_tipica_error * (100/(double)amplitud_senal_a_diezmar))); fprintf(fptr1,"\n(Varianza del error: %8.8f)", varianza_error); fprintf(fptr1,"\n"); fclose(fptr1); if (ficheros_independientes==1) { fptr2=fopen(nom_fichero,"w"); fprintf(fptr2,"/*%s*/\n", nom_fichero); fprintf(fptr2,"\n//Nmero puntos seal original: %i", tam_senal_a_diezmar); fprintf(fptr2,"\n//Diezmado de la seal original: %i", diezmado); fprintf(fptr2,"\n\n//Nmero puntos seal a interpolar: %i", tam_senal_a_interpolar); fprintf(fptr2,"\n//Tamao ventana interpolacin: %i", tam_ventana); fprintf(fptr2,"\n//Puntos a obtener entre dos muestras: %i", num_puntos_nuevos); fprintf(fptr2,"\n//Tamao final seal interpolada: %i", tam_final); fprintf(fptr2,"\n"); fprintf(fptr2,"\n//RESULTADOS:"); fprintf(fptr2,"\n//MEDIA del ERROR: %8.8f", media_error); fprintf(fptr2,"\n//DESVIACIN TPICA del error: %8.8f", desviacion_tipica_error); fprintf(fptr2,"\n//PORCENTAJE DESVIACIN TPICA del error: %8.8f %%",(desviacion_tipica_error * (100/(double)amplitud_senal_a_diezmar))); fprintf(fptr2,"\n//(Varianza del error: %8.8f)", varianza_error); fprintf(fptr2,"\n\n"); fprintf(fptr2,"double senal_interpolada[]={"); for(i=0;i<tam_final;i++) { if ((i%diezmado) == 0) { fprintf(fptr2,"\n%8.8f, //Muestra original.", vector_senal_interpolada[i]); } else { error = senal_a_diezmar[i] - vector_senal_interpolada[i]; fprintf(fptr2,"\n%8.8f, //CORRECTO:%8.8f ERROR: %8.8f", vector_senal_interpolada[i], senal_a_diezmar[i], error); }; }; fprintf(fptr2,"\n};"); fclose(fptr2); }; }; return 0; }
UPV Pgina

25

Transformada Rpida de Fourier e Interpolacin en Tiempo Real

El programa, en primer lugar, genera una seal senoidal muestreada mediante la funcin gen_seno. Esta funcin tiene como parmetros la direccin de un vector donde se almacenarn los puntos que se generen para que el programa principal pueda disponer de ellos, el nmero total de puntos a obtener de la funcin seno, los puntos a obtener por periodo de dicha funcin y la amplitud del seno. Una vez generada la seal senoidal el programa realiza un diezmado de sta para posteriormente proceder a interpolar mediante el uso de los algoritmos antes descritos. De esta manera se podrn comparar los resultados obtenidos en la interpolacin con los valores correctos. En el diezmado se indica el nmero de puntos a eliminar por cada punto, despus, en la interpolacin, habr que indicar el mismo nmero de puntos a obtener por cada punto para as poder realizar posteriormente las comparaciones. En una interpolacin ideal, los valores de los puntos que se interpolen deberan ser iguales a los valores de los puntos que se eliminaron en el diezmado. Los algoritmos implementados realizan la interpolacin en tiempo real, lo que quiere decir que a medida que se van obteniendo las muestras se van generando nuevos puntos. No hace falta tener toda la seal muestreada para realizar la interpolacin, como suceda cuando usbamos la FFT. Para simular este comportamiento, el programa ejemplo implementado proporciona de uno en uno, mediante un bucle, los puntos de la seal seno (una vez diezmada) a la funcin gen_nuevos_puntos. El programa supone que los puntos muestreados de la seal a interpolar se corresponden con un periodo completo de la seal real, repitindose sta en el tiempo. De manera que cuando se obtiene la seal seno se ha de procurar que los puntos muestreados correspondan a periodos completos de la seal seno para que la suposicin de la que parte el programa sea correcta. Por ejemplo, si deseamos interpolar una seal seno muestreada con 8 muestras por periodo, el nmero de muestras totales de esta seal tendr que ser mltiplo de 8 para disponer de periodos completos de la seal. De esta manera, cuando el programa supone toda la seal muestreada como un solo periodo, el programa supone de forma acertada que despus del ltimo punto muestreado comienza otra vez el primero (repitindose en el tiempo toda la seal muestreada). Como primer caso, para probar el correcto funcionamiento de los algoritmos, vamos a suponer que tenemos 128 puntos correspondientes al muestreo de una seal continua de valor 1000. A partir de estos puntos se desean interpolar nuevos puntos de la seal hasta obtener un total de 1024 puntos (7 puntos nuevos por cada punto muestreado). Es obvio que todos los puntos nuevos que se obtengan deberan valer 1000 por lo que esta prueba permitir obtener una primera valoracin del funcionamiento y precisin de los algoritmos. En este caso el programa de prueba se configura (senal_continua = 1) para que todos los puntos que proporciona a la funcin gen_nuevos_puntos tengan el mismo valor (no se genera la seal seno antes comentada puesto que sta no se necesita). Realizamos la interpolacin con diferentes tamaos de la ventana de interpolacin. La primera ejecucin corresponde a un tamao de ventana igual a 2, es decir, para la obtencin de un nuevo punto slo se tienen en cuenta las muestras anterior y posterior a ste. En dicha interpolacin se obtiene una media del error igual a 201,56908400 con una desviacin tpica igual a 61,25119165. En la segunda ejecucin se aumenta el tamao de la ventana de interpolacin a 4 y se obtiene una media del error igual a 109,56770064 con una desviacin tpica de 35,08369094. Se observa que el error cometido, como era de esperar, es menor. Pasemos ahora a realizar un estudio con ms detalle de la interpolacin de diferentes seales donde se vara el tamao de la ventana de interpolacin desde 2 hasta 100 muestras. Para ello se han realizado varias pruebas con seales continuas y senoidales obtenindose una serie de grficas donde se presenta la media y desviacin tpica del error de interpolacin en funcin del tamao de la ventana de interpolacin. En el caso de las seales continuas se han realizado pruebas con seales de distintos valores obtenindose como resultado que la media y desviacin tpica del error de interpolacin son linealmente proporcionales al valor de la seal. Tambin se ha hecho lo mismo con seales senoidales
Pgina

26

DISCA

Proceso Digital de Datos en Sistemas de Tiempo Real

de diferente amplitud en donde se concluye que la media y desviacin tpica del error de interpolacin son linealmente proporcionales a la amplitud y no al valor mximo o mnimo que puedan tener las seales senoidales. Debido a esto, en todas la grficas se expresarn la media y desviacin tpica en forma de tanto por cien del valor o amplitud de la seal. As, dichos resultados, pueden extenderse y aplicarse a seales con diferentes valores y amplitudes. Las seales a interpolar estn formadas por 128 muestras que se repiten en el tiempo donde (en el caso de las seales senoidales) cada 4 muestras pertenecen a un periodo diferente. A partir de estos puntos se desean interpolar nuevos puntos de la seal hasta obtener un total de 1024 puntos (7 puntos nuevos por cada punto muestreado). En todas las grficas el tamao de la ventana de interpolacin se representa en el eje de las abscisas variando su valor desde 2 hasta 100 con incrementos de 2 hasta un tamao igual a 40 y a partir de ste con incrementos de 10. De momento continuemos con las seales continuas y veamos que sucede cuando seguimos aumentando el tamao de la ventana de interpolacin:

Media y Desviacin Tpica del Error de Interpolacin en Seales Continuas

Media 15,00000 % Valor de la Seal 10,00000 5,00000 0,00000 -5,00000 -10,00000 -15,00000 -20,00000 -25,00000 2 6 10 14 18 22 26 30 34 38 50 70 90 Tamao Ventana Interpolacin Desviacin Tpica

Grfica 1 En la grfica 1 se puede observar cmo la media del error cometido disminuye a medida que aumenta la ventana de interpolacin alternndose valores positivos y negativos para sta con cada incremento del tamao de dicha ventana. La media del error converge a cero oscilando sobre dicho valor. Cuando el nmero de muestras anteriores y el de muestras posteriores son par, el error cometido es siempre positivo, mientras que cuando el nmero de stas es impar es siempre negativo. Esto es lgico si se observan los valores de la funcin SINC, al considerar slo dos muestras se obtiene un error negativo ya que los valores de la seal SINC son positivos, al considerar dos muestras ms los valores de la seal SINC son negativos y restamos un valor al anterior obteniendo un error positivo aunque en valor absoluto ms pequeo que antes y as sucesivamente.

UPV

Pgina

27

Transformada Rpida de Fourier e Interpolacin en Tiempo Real

Se puede concluir que, para seales positivas, cuando la mitad del tamao de la ventana de interpolacin es impar el error es negativo y cuando es par el error es positivo. En el caso de que el valor de la funcin continua a interpolar fuera negativo, el error cometido hubiera sido positivo para un tamao impar y negativo para un tamao par. En cuanto a la desviacin tpica del error se observa que converge a cero a medida que aumenta el tamao de la ventana de interpolacin pero en este caso sin oscilar (ver tambin la grfica 2).

Desviacin Tpica del Error de Interpolacin en Seales Continuas

Desviacin Tpica 7,00000 6,00000 5,00000 4,00000 3,00000 2,00000 1,00000 0,00000 2 6 10 14 18 22 26 30 34 38 50 70 90 Tamao Ventana Interpolacin

% del Valor de la Seal

Grfica 2 Como resultado de esta prueba podemos concluir que los algoritmos de interpolacin se comportan, hasta el momento, de la forma prevista. Veamos que sucede cuando la seal a interpolar no es continua sino que se corresponde a una seal senoidal. Inicialmente consideraremos los valores de la seal seno siempre positivos. En la grfica 3 podemos observar como, al igual que suceda con las seales continuas, a medida que aumenta el tamao de la ventana de interpolacin la media del error disminuye tendiendo a cero y lo hace oscilando sobre dicho valor. Igualmente se observa que cuando la mitad del tamao de la ventana de interpolacin es impar el error es negativo y cuando es par el error es positivo, esto sucedera al contrario si los valores del seno fueran todos negativos. En la grfica 4 se aprecia que la media obtenida es idntica a la de las seales continuas.

Pgina

28

DISCA

Proceso Digital de Datos en Sistemas de Tiempo Real

Media y Desviacin Tpica del Error de Interpolacin en Seales Senoidales Positivas

Media % Amplitud del Seno 15,00000 10,00000 5,00000 0,00000 -5,00000 -10,00000 -15,00000 -20,00000 -25,00000 2 6 10 14 18 22 26 30 34 38 50 70 90 Tamao Ventana Interpolacin Desviacin Tpica

Grfica 3

Media del Error de Interpolacin en Seales Continuas y Senoidales Positivas

Media en Seales Continuas 15,00000 10,00000 % Valor o Amplitud 5,00000 0,00000 -5,00000 -10,00000 -15,00000 -20,00000 -25,00000 2 6 10 14 18 22 26 30 34 38 50 70 90 Tamao Ventana Interpolacin Media en Seales Senoidales Positivas

Grfica 4 Respecto a la desviacin tpica puede verse (grficas 3 y 5) que no disminuye con el incremento del tamao de la ventana de interpolacin de la misma forma en que lo haca con seales continuas. En este caso la desviacin tpica tambin tiende a cero pero no de forma continua, sino que sigue una trayectoria decreciente con intervalos ascendentes que se repiten de forma peridica, estos intervalos son cada vez de menor amplitud.

UPV

Pgina

29

Transformada Rpida de Fourier e Interpolacin en Tiempo Real

Desviacin Tpica del Error de Interpolacin en Seales Senoidales Positivas

Desviacin Tpica 14,00000 12,00000 10,00000 8,00000 6,00000 4,00000 2,00000 0,00000 2 6 10 14 18 22 26 30 34 38 50 70 90 Tamao Ventana Interpolacin % Amplitud del Seno

Grfica 5 En la grfica 6 pueden compararse las desviaciones tpicas obtenidas para las seales continuas y senoidales positivas.

Desviacin Tpica del Error de Interpolacin en Seales Continuas y Senoidales Positivas

Desviacin Tpica en Seales Continuas Desviacin Tpica en Seales Senoidales Positivas % Valor o Amplitud de la Seal 14,00000 12,00000 10,00000 8,00000 6,00000 4,00000 2,00000 0,00000 2 6 10 14 18 22 26 30 34 38 50 70 90 Tamao Ventana Interpolacin

Grfica 6

Pgina

30

DISCA

Proceso Digital de Datos en Sistemas de Tiempo Real

Se observa que existen valores para el tamao de la ventana de interpolacin donde la el valor de la desviacin tpica del error de interpolacin en las seales continuas y senoidales coincide. Ahora consideraremos la seal seno simtrica al valor cero, con valores positivos y negativos. En este caso para la obtencin de un nuevo punto pueden tenerse en cuenta muestras tanto positivas como negativas.

Media y Desviacin Tpica del Error de Interpolacin en Seales Senoidales Puras

Media % Amplitud del Seno 12,00000 10,00000 8,00000 6,00000 4,00000 2,00000 0,00000 2 6 10 14 18 22 26 30 34 38 50 70 90 Tamao Ventana Interpolacin Desviacin Tpica

Grfica 7 Lo primero que hay que resaltar en la grfica 7 es que la media del error de interpolacin es cero para todos los tamaos de ventana de interpolacin. Esto es lgico debido a que ahora tenemos una seal senoidal pura con muestras positivas y negativas, as que los errores positivos que se cometen al obtener unos puntos se compensan con los errores negativos al obtener otros, de manera que al final la media del error es cero. Hasta ahora hemos visto que las medias de los errores de interpolacin para las seales continuas y senoidales con valores siempre del mismo signo coinciden mientras que la media para las senoidales puras es cero. Si consideramos para una seal cualquiera que el caso mejor (cuando se obtiene menos error de interpolacin) es cuando la seal es senoidal pura y que el caso peor es cuando la seal es continua, podemos concluir que al interpolar una seal cometeremos un error con una media comprendida entre 0 (si la seal es senoidal pura) y el valor de la media del error que se cometera si se interpolase una seal continua con un valor igual a la amplitud de la seal a interpolar, dependiendo este error del tamao de la ventana de interpolacin. A continuacin vamos a profundizar en el estudio del promedio de las desviaciones de los errores respecto a su media, lo haremos mediante la desviacin tpica. En el caso de las seales senoidales puras (ver grfica 7) se observa que la desviacin tpica disminuye hacia cero a medida que aumenta el tamao de la ventana de interpolacin pero lo hace siguiendo una trayectoria semejante a la trayectoria seguida por la desviacin tpica para la seales senoidales positivas. Observemos la grfica 8 donde se comparan estas desviaciones.

UPV

Pgina

31

Transformada Rpida de Fourier e Interpolacin en Tiempo Real

Desviacin Tpica del Error de Interpolacin

14,00000 % Valor o Amplitud 12,00000 10,00000 8,00000 6,00000 4,00000 2,00000 0,00000 2 6 10 14 18 22 26 30 34 38 50 70 90 Tamao Ventana Interpolacin

Desviacin Tpica en Seales Senoidales Positivas Desviacin Tpica en Seales Senoidales Puras Desviacin Tpica en Seales Continuas

Grfica 8 En la grfica 8 pueden verse varias cosas. Se observa que en torno a la desviacin tpica del error de interpolacin en las seales continuas se sitan las desviaciones tpicas para las seales senoidales. Como ya se coment, para las seales senoidales la desviacin tpica sigue una trayectoria decreciente con intervalos ascendientes que se repiten de forma peridica y con una amplitud cada vez menor. En esta grfica puede verse que cuando las seales senoidales son positivas estos intervalos tienen siempre valores superiores a los valores de la trayectoria de la desviacin tpica para las seales continuas, mientras que cuando las seales son senoidales puras se observa que la trayectoria de la desviacin para las seales continuas pasa por la mitad de estos intervalos ascendentes. Puede concluirse que la desviacin tpica para las seales continuas marca la media de las desviaciones tpicas que se sufrirn con seales senoidales. En la grfica 8 tambin podemos apreciar que para las seales senoidales los intervalos ascendentes antes comentados se repiten cada cuatro aumentos de la ventana de interpolacin. Si seguimos la trayectoria de la desviacin tpica primero se produce un decremento de sta en los dos primeros tamaos de la ventana de interpolacin (2 y 4 muestras), seguidamente se produce un aumento de la desviacin y sta no vuelve a tener un valor menor al mnimo obtenido hasta cuatro aumentos posteriores de la ventana de interpolacin (hasta una ventana de 12 muestras) y entonces vuelve a repetirse un aumento de la desviacin tpica de manera que, aunque este aumento es de menor amplitud que el anterior, la desviacin no vuelve a rebasar el valor mnimo obtenido hasta los siguientes cuatro aumentos de la ventana (hasta 20 muestras), y as sucesivamente la desviacin tpica va decreciendo convergiendo a cero. De esta forma tenemos que los tamaos de la ventana de interpolacin en los que se han ido obteniendo desviaciones tpicas menores son: 4, 12, 20, 28, 36, etc., es decir, que a partir de un tamao de la ventana de interpolacin igual a 4 muestras se va mejorando la desviacin tpica del error de interpolacin cada aumento de dicha ventana con 8 muestras ms. Veamos ahora por qu se produce este comportamiento en la desviacin tpica del error de interpolacin. Para ello se han realizado pruebas donde la seal senoidal a interpolar de 128 muestras tiene un nmero de muestras por periodo diferente a 4 (hasta ahora todas las seales utilizadas tenan 4 muestras por periodo). Si la seal a interpolar est formada por 8 muestras por periodo podemos observar la trayectoria que presenta la desviacin tpica del error de interpolacin respecto al tamao de la ventana de interpolacin en la grfica 9.

Pgina

32

DISCA

Proceso Digital de Datos en Sistemas de Tiempo Real

Desviacin Tpica del Error de Interpolacin en Seales Senoidales

Desviacin Tpica (8 muestras por periodo) % Amplitud Seno 15,00000 10,00000 5,00000 0,00000 2 6 10 14 18 22 26 30 34 38 50 70 90 Tamao Ventana Interpolacin

Grfica 9 En este caso tenemos que los tamaos de la ventana de interpolacin en los que se obtienen desviaciones tpicas menores son: 8, 24, 40, 56, etc., es decir, que a partir de un tamao de la ventana de interpolacin igual a 8 muestras se va mejorando la desviacin tpica del error de interpolacin cada aumento de dicha ventana con 16 muestras ms. Puede concluirse que para realizar una interpolacin de una seal cualquiera con N muestras por periodo, el mejor tamao para la ventana de interpolacin es N muestras y a partir de ste cada 2N muestras ms. Veamos si sucede lo mismo cuando la seal a interpolar est formada por 2 muestras por periodo.

Desviacin Tpica del Error de Interpolacin en Seales Senoidales

D esvi n T ca ( m uestas porperodo) aci pi 2 r i 12, 00000 10, 00000 % Amplitud Seno 8, 00000 6, 00000 4, 00000 2, 00000 0, 00000 2 6 10 14 18 22 26 30 34 38 50 70 90 Tamao Ventana Interpolacin

Grfica 10
UPV Pgina

33

Transformada Rpida de Fourier e Interpolacin en Tiempo Real

En la grfica 10 se observa que los resultados de la interpolacin de la seal senoidal con 2 muestras por periodo se ajustan a las conclusiones obtenidas. En este caso los mejores tamaos para la ventana de interpolacin son: 2, 6, 10, 14, 18, etc. Comparemos todos los resultados obtenidos (ver grfica 11).

Desviacin Tpica del Error de Interpolacin en Seales Senoidales

Desviacin Tpica (2 muestras por periodo) Desviacin Tpica (4 muestras por periodo) Desviacin Tpica (8 muestras por periodo) 16,00000 14,00000 12,00000 10,00000 8,00000 6,00000 4,00000 2,00000 0,00000 2 6 10 14 18 22 26 30 34 38 50 70 90 Tamao Ventana Interpolacin

% Amplitud Seno

Grfica 11 El error que se comete al interpolar depende del tamao de la ventana de interpolacin y de la relacin de ste con el nmero de muestras por periodo de que dispone la seal a interpolar. El tamao ms pequeo de la ventana de interpolacin para obtener un error pequeo es igual al nmero de muestras por periodo de la seal a interpolar, de manera que la ventana utilizada para obtener nuevos puntos estar formada exactamente por las muestras correspondientes a un periodo completo de la seal. El error obtenido se puede reducir an ms incrementando dicho tamao en un nmero de muestras igual al doble del nmero de muestras por periodo de la seal, as se aumenta la ventana con un nmero de muestras anteriores correspondientes a un periodo completo y un nmero de muestras posteriores correspondientes tambin a otro periodo completo. Tambin comentar que al interpolar una seal cuantos ms puntos o muestras por periodo se tengan de dicha seal a interpolar menos error se cometer. Esto es lgico, sin embargo, en el caso en que la seal sea senoidal pura esto no ocurre, ya que con slo dos muestras por periodo (que es lo mnimo permitido, la frecuencia de Nyquist) obtemos errores semejantes a los que se obtienen con un mayor nmero de muestras por periodo (ver grfica 11). Esto es debido a que la interpolacin basada en la funcin SINC tiende a interpolar la seal como senoidal pura, por eso, en el caso en que la seal sea senoidal pura, con slo dos muestras por periodo ya se obtiene un error mnimo. Sin embargo, si la seal a interpolar no fuera senoidal no ocurrira lo mismo, en este caso cuantas ms muestras por periodo se tuvieran menor sera el error. Como el error cometido siempre tiende a reconstruir la seal como senoidal pura, cuantas menos muestras por periodo se tengan de la seal a interpolar ms se parecer la seal interpolada resultante a una senoidal pura y ms error se cometer en el caso de que dicha seal a interpolar no se parezca a una senoidal pura.

Pgina

34

DISCA

Proceso Digital de Datos en Sistemas de Tiempo Real

9. Conclusiones
En este trabajo se ha desarrollado:

Y Y

Un algoritmo para la realizacin de la Transformada Rpida de Fourier. Un algoritmo para la realizacin de la interpolacin senoidal en tiempo real.

La funcin FFT ha sido probada y aplicada en el tratamiento digital de seales procedentes de sensores de ultrasonidos obtenindose los resultados deseados. En cuanto al algoritmo de interpolacin senoidal en tiempo real se ha realizado un estudio sobre su aplicacin en seales de diferentes caractersticas obtenindose una serie de conclusiones acerca del error de interpolacin cometido.

Y Y Y

El error de interpolacin cometido siempre tiende a reconstruir la seal como senoidal pura. El error de interpolacin es menor cuantas ms muestras por periodo se obtengan de la seal a interpolar. El error de interpolacin depende del tamao de la ventana de interpolacin. Generalmente cuanto mayor es la ventana menor es el error. El objetivo es obtener un error aceptable con una ventana lo ms pequea posible. El estudio realizado concluye que el mejor tamao de la ventana de interpolacin que garantiza un error pequeo es igual al nmero de muestreas por periodo que se obtengan de la seal a interpolar. Se pueden conseguir errores menores incrementando el tamao de la ventana un nmero de muestras igual al doble de muestras que se obtengan por periodo. Para un tamao de ventana determinado, al interpolar una seal cometeremos un error con una media comprendida entre 0 (si la seal es senoidal pura) y el valor de la media del error que se cometera si se interpolase una seal continua con un valor igual a la amplitud de la seal a interpolar.

Estas conclusiones son el resultado de un primer estudio sobre la interpolacin de seales senoidales, en trabajos futuros se debe extender el estudio a otros tipos de seales para as poder demostrar el carcter general de dichas conclusiones o bien aportar nuevas caractersticas.

10. Bibliografa
[Fourier]: Tratamiento Digital de Seales John G. Proakis Dimitris G. Manolakis Editorial: Prentice Hall Digital Signal Processing Sanjit K. Mitra James F. Kaiser Editorial: John Wiley & Sons

[DSP 1]:

[TMS32C30]: Digital Signal Processing with C and the TMS32C30 Rulph Chassaing Editorial: John Wiley & Sons [FFT 1]: C Language Algorithms for Digital Signal Processing Paul M. Embree Bruce Kimble Editorial: Prentice Hall

UPV

Pgina

35

Transformada Rpida de Fourier e Interpolacin en Tiempo Real

[FFT 2]:

Numerical Recipes in Pascal Wilian H. Press Brian P. Flannery Saul A. Teudsky Willian T. Vetterling Cambridge University Press A Simple Approach to Digital Signal Processing Graig Marven Gillian Ewers Texas Instruments

[DSP 2]:

Pgina

36

DISCA