Home

1 = Wkf nF K ,2,1,0, = l e W Nl /2 θ −= Introducción teórica Objetivos

1. tor K 2 6 M MpeNpERE CENTRO DE INVESTIGAO N Y TRAMSFEREMCA DE TEHNOLOGIA e Conocer que es la Transformada de Fourier Discreta y sus aplicaciones e Resolver problemas que involucren la Transformada de Fourier Discreta e Obtener la Transformada R pida de Fourier de se ales reales usando la tarjeta de sonido 6 1 LA TRANSFORMADA R PIDA DE FOURIER El c lculo de la TFD requiere de M multiplicaciones esto es 0 lt k lt N 0 lt n lt M y el tiempo de computaci n resulta excesivo cuando V es grande La clave para m todos computacionales m s eficientes es hacer uso de la simetr a de los exponenciales complejos tanto como sea posible antes de efectuar las multiplicaciones Los avances han producido un tipo de eficientes algoritmos conocidos como transformada r pida de Fourier TRF que permite reducir sustancialmente el tiempo de computaci n La TRF es un algoritmo es decir un m todo sistem tico de efectuar una secuencia de c lculos que permite calcular la TFD con un m nimo de tiempo de computaci n Al margen del propio algoritmo la interpretaci n de la TRF es igual a la de la TFD El algoritmo que se ver aqu es la formulaci n de Cooley Tukey usada com nmente Este algoritmo calcula M componentes de frecuencia discretos a partir de M muestras discretas en el tiempo donde N 2 y res un entero Esta restricci n a una potencia de dos no es importante en la pr ctica siempre que 2 sea mayor que el n mero
2. n directa es casi 100 veces mayor que si se usa la TRF Sin embargo el algoritmo de la TRF requiere considerable espacio de almacenamiento lo que puede limitar su aplicaci n cuando no se dispone del suficiente espacio A continuaci n se enumeran algunos puntos que resultan tiles al procesar funciones continuas del tiempo con la TRF Puede verse que muchos de ellos provienen de las consideraciones anteriores sobre la TFD y la transformada de Fourier f k tkk finak fn 0 Fon fa 00 Fp 0 ED y Ft Lo 2 A Exe we we Figura 6 2 Gr fica de flujo de se ales del algoritmo Cooley Tukey para N 4 1 El n mero de muestras se elige de forma que M 2 r entero Este n mero puede incluir ceros de aumento ver 7 m s adelante 2 Para N muestras temporales hay n frecuencias discretas Gu a o 3 Como resultado de la extensi n peri dica los puntos de muestra 0 y M son id nticos en ambos dominios 4 Los componentes de frecuencia positiva son los que est n en 0 MW 2 los de frecuencia negativa los que est n en 1 2 M Esta simetr a puede usarse en muestras temporales en tiempo negativo y positivo 5 Para funciones con valor real los componentes de frecuencia positiva son los conjugados complejos de los de frecuencia negativa Los puntos n 0 M 2 son comunes a ambos y tienen valor real 6 El mayor componente de frecuencia esto es n M 2 es 2T Hz puede aumentarse disminuyendo el espaci
3. de datos siempre puede llenarse el resto con ceros de aumento Como se vio en la pr ctica anterior los par metros Q y 7 no est n realmente implicados en el c lculo de la TFD por lo que se adopta una notaci n compacta omiti ndolos y la ecuaci n 4 2 puede rescribirse como N 1 Fy m f x 6 1 k 0 donde W e 1 0 12 6 2 La ecuaci n 6 2 describe un fasor de magnitud unitaria y un ngulo de fase de 0 2ml N Como ejemplo sea V 2 8 los valores correspondientes de la ecuaci n 6 2 est n en la figura 3 W Cooley y J W Tukey An Algorithm for Machine Calculation of Complex Fourier Series Math Comput 19 297 301 Abril 1965 Gu a 9 6 1 En sta puede verse que W y W est n situados sim tricamente con respecto al eje real y rigen las siguientes propiedades de simetr a wW W 1 y yN 1 y w w Eje imaginario j Figura 6 1 Potencias de la funci n exponencial W para N 8 Para aprovechar todas las ventajas del uso de N 2 se expresan n y k como n meros binarios Sup ngase que r 2 es decir N 4 y k k 100 01 10 11 6 4 n n n 100 01 10 11 e donde no 1 ko k solo pueden tomar valores de O y 1 Una forma compacta de escribir el valor num rico de k y nes k 2k k 6 5 n 2n n Usando las ecuaciones 6 4 y 6 5 en la 6 1 se tiene 1 1 A ALO Sido 6 6 ko 0k 0 donde la doble sumatoria es necesaria para indicar la
4. unitario cuyo producto punto con un vector columna de longitud N genera la transformada de Fourier discreta del vector DFTMTX LENGTHOO X es igual que FFT X La matris de la transformada discreta inversa es CONI DFTMTX N N Vea tambi n FFT y IFFT f 2 pi n Incremento angular w 0 f 2 pi f 2 sqrt 1 Columna x 0 n 1 Fila b exp w x Exponenciaci n de producto punto Repita el numeral 3 del procedimiento para probar la funci n dftmtx anterior En MATLAB escriba la siguiente secuencia a a debe ser un vector columna Fd1 fft a Fd2 dftmtx length a a b b Gu a o Fd3 fft b Fd4 dftmtx length b b Son iguales los resultados de Fd1 y Fd2 Son iguales los resultados de Fd3 y Fd4 PARTE II Transformada DFT inversa IDFT 6 Esta transformada se expresa como N 1 le X k e Ni Dada la gran cantidad de algoritmos y hardware espec fico existente para calcular la DFT directa es conveniente encontrar la forma de obtener la IDFT a partir de la DFT A continuaci n se implementar n tres m todos para realizar esto 7 IDFT mediante rotaciones circulares Podemos observar que la diferencia fundamental entre la DTFT y su inversa est en el cambio de signo de las exponenciales complejas Por tanto bastar realizar un cambio de variable gt para obtener la transformada inversa a partir de la directa x n DTFT X 0 Para el caso
5. IFT n size x 2 if n log n log 2 fix n log n log 2 0 fprintf longitud del vector 0fAn n error La longitud del vector debe ser una potencia de 2 end Reordena el vector de datos complejos por la regla del bit inverso j n 2 1 for i 2 n if i lt j temp x i x i x j x j temp end k n 2 while k lt j amp k 0 j j k k fix k 2 end j j k end Realiza los c lculos del patr n de mariposa j sqrt 1 d 1 while d lt n e d d d 2 u 1 w exp pi e j for b 1 e a b while a lt n f a e temp x N u x f x a temp x a x a temp a a d end temp real u j imag temp u u w end end Guarde el archivo con el nombre MITRF M igual que el de la funci n Compare la funci n de la transformada r pida de Fourier que usted hizo con el que ya viene incluida en MATLAB Encuentre la TFD de las secuencias siguientes a 1 0 1 0 b 1 1 0 0 Soluci n En MATLAB escriba la siguiente secuencia a 1 0 1 0 Fd1 fft a Fd2 mitrf a b 1 1 0 0 Fd3 fft b Fd4 mitrf b Son iguales los resultados de Fd1 y Fd2 Son iguales los resultados de Fd3 y Fd4 Cuando la longitud del vector no es una potencia de 2 se puede usar el c lculo de la transformada discreta de Fourier por su definici n function b dftmtx n DFTMTX matriz de Is transformada Discreta de Fourier DFTMTX N es la matriz compleja de N por N de valores alrededor del circulo
6. amiento entre muestras temporales 7 El espaciamiento entre componentes de frecuencia es M7 Hz puede reducirse agregando ceros de aumento a la secuencia de muestras 8 La relaci n exacta de los valores de la TRF depende de los factores constantes asignados en el algoritmo un procedimiento bastante com n es dividir por M de forma que los valores calculados son 1 NWV veces la TFD Algoritmo Aunque existen varias posibilidades desarrollamos aqu un algoritmo de FFT del tipo Cooley Tukey algoritmo de decimaci n en frecuencia que deber implementarse como un programa MatLab y compararse en tiempo de CPU consumido con la expresi n original de la DFT El algoritmo FFT a implementar requiere una se al con un n mero de muestras V potencia de 2 y se resume en la parte a del siguiente gr fico V 8 l 1 l 2 l 3 _ X Xi o Xx X x 0 N x k x k l 14 1 x 1 A We x 2 x _ k N 2 x k N 2 l 1 x 3 b ES A 6 El x el am A x 7 c a El algoritmo se estructura en y log M niveles de c mputo 1 y Para el desarrollo de este algoritmo deben tenerse en cuenta los siguientes puntos e Cada par de puntos de un cierto nivel se obtienen a partir de otros dos del nivel anterior Estos dos puntos origen se dice que son nodos duales e Elespaciado entre dos nodos duales es M 2 e C mputo de nodos duales mariposas El c mputo de dos nuevos nodos a partir de dos nodos dual
7. de Fourier demuestre la propiedad de modulaci n con un ejemplo Presente todas sus observaciones y conclusiones Documentar la forma de obtener la transformada r pida de Fourier de una se al contin a utilizando SCILAB adem s presente el archivo ejecutable Sistemas de Comunicaciones Stremler Ferrel G Alfaomega The MathWorks Inc Manual del usuario de MATLAB C C Interactive Reference Guide
8. de la DFT las frecuencias positivas corresponden a X 0 1 2 1 y las negativas a k M 2 M 1 Por tanto la reordenaci n a realizar sobre la DFT ser la siguiente e 4 o o O N 41 N 2 N 2 N2 1 2 1 Esta reordenaci n puede realizarse como Y X 1 X N 1 2 Escribir una funci n MatLab que calcule la IDFT como x n prTlY 8 IDFT mediante conjugados Este m todo corresponde al siguiente esquema Re X k _ N Re x n FFT Im X k AO 69 N Im x n 1 1 Demostrar que el procesado anterior realiza una IDFT y escribir una funci n MatLab que lo implemente 9 Gu a Q Re X k N Re x n Repetir el apartado anterior para el siguiente esquema FFT Im X k N Im x n PARTE III Transformada R pida de Fourier de una se al de voz 10 11 12 13 E Capture una se al de voz de 32768 muestras con una frecuencia de muestreo de 8000 Hz usando la tarjeta de sonido Presente la magnitud de la se al contra la frecuencia expresada en Hz Compruebe que la mayor potencia de la voz est en el rango de 300Hz a 3400Hz Salga del programa y apague la computadora Encuentre el diagrama de flujo o flujograma del algoritmo de la transformada r pida de Fourier Cu l es la raz n de agregar ceros a la secuencia de n meros en el algoritmo FFT Cu l es la utilidad de emplear la transformada de r pida de Fourier Usando la transformada r pida
9. es se denomina mariposa Su estructura se muestra en la gr fica anterior parte b y se corresponde con la siguiente expresi n x k xa 4 19 x k 00 21 x 0 2 x 4 W x 0 2 lo cual se puede simplificar a la estructura mostrada en la parte c e Salto una vez recorridos W 2 nodos consecutivos se saltan los V 2 siguientes ya que son los duales de los anteriores y se prosigue el c mputo de mariposas e Determinaci n de W Gu a Q 1 Escribir k nodo actual en forma de n mero binario de y bits 2 Desplazar y bits a la derecha rellenando con ceros 3 Invertir el orden de los bits p ej 100 pasa a 001 El resultado es p e Enel ltimo nivel se obtiene x X X es la DFT de la se al con sus muestras permutadas mediante inversi n de bits Por ejemplo X 3 X 011 X 110 X 6 1 Computadora con sistema operativo Windows y el programa Fourier y MATLAB y tarjeta de sonido PARTE 1 Algoritmo de la Transformada R pida de Fourier FFT escrito en MATLAB ja Encienda la computadora y corra el programa MATLAB En MATLAB seleccione del men File la opci n New y en ella seleccione M file Aparecer el Editor Depurador de archivos M Escriba la siguiente funci n function x mitrf x MITRF Transformada Discreta de Fourier TRF X es la transformada discreta de Fourier del vector X La longitud del vector X debe ser una potencia de 2 Vea tambi n FFT IFFT FFT2 IFFT2 FFTSH
10. representaci n binaria completa de k El t rmino exponencial de la ecuaci n 6 6 es yy Crito JQk k0 yy Qro 2k yy Crito Jo yy 210 py Qri no ko 3 6 7 Gu a Q porque yt para todos los n k enteros Este ltimo paso es fundamental para la eficiencia de la TRF porque ahora puede escribirse como F n n y Y Ko Ko W py 200 yy ritmo 6 8 ko 0 k 0 Ahora puede mostrarse el algoritmo escribiendo la sumatoria entre corchetes de la ecuaci n 6 8 como fm k Eh o W 6 9 y la sumatoria exterior como f n n Y Mosh W en 6 10 De las ecuaciones 6 8 y 6 10 se obtiene F npn f 1 1 6 11 Este ltimo paso se incluye porque el orden de la salida se altera en este algoritmo Una variante es alterar el orden a la entrada de forma que a la salida sea el correcto Las ecuaciones 6 9 6 11 son las relaciones que comprenden el algoritmo de Cooley Tukey para W 4 En la figura 6 2 se muestra un gr fico de fluencia de estas relaciones Para potencias de dos mayores los algoritmos se procesan de la misma forma con una sumatoria por cada potencia de dos en la ecuaci n 6 6 Para la evaluaci n directa de la TFD se requieren alrededor de M operaciones complejas de multiplicaci n y suma mientras que el algoritmo de la TRF requiere operaciones del orden de N log N El ahorro neto es apreciable para M grande Por ejemplo el tiempo de computaci n necesario para una TFD de 1024 puntos con evaluaci

1 = Wkf nF K ,2,1,0, = l e W Nl /2 θ −= Introducción teórica Objetivos

Contents

Download Pdf Manuals

Related Search

Related Contents

1 = Wkf nF K ,2,1,0, = l e W Nl /2 &theta; &minus;= Introducci&oacute;n te&oacute;rica Objetivos

Contents

Download Pdf Manuals

Related Search

Related Contents

1 = Wkf nF K ,2,1,0, = l e W Nl /2 θ −= Introducción teórica Objetivos