• Author / Uploaded
• Myfred Marcial Mndz

• Categories
• Transformada rápida de Fourier
• Transformada discreta de Fourier
• Objetos matemáticos
• Ciencias de la Computación
• Informática teórica

Citation preview

Cálculo de la transformada rápida de Fourier Implementando el Algoritmo Decimación en tiempo en lenguaje C

26 de noviembre de 2013

INSTITUTO POLITECNICO NACIONAL ESCUELA SUPERIOR DE INGENIERIA MECANICA Y ELECTRICA

MATERIA: PROCESAMIENTO DIGITAL DE SEÑALES

PROFESOR: MIRA GONZALEZ CARLOS NOMBRE DEL ALUMNO: MYFRED MARCIAL MENDEZ

REPORTE: REPORTE DE PROYECTO (CÁLCULO DE LA TRANSFORMADA RÁPIDA DE FOURIER IMPLEMENTANDO EL ALGORITMO DECIMACIÓN EN TIEMPO EN LENGUAJE C)

GRUPO: 7CM5

TURNO: MATUTINO

1

Transformada Rápida de Fourier: Decimación en Tiempo

Calculo de la transformada rápida de Fourier Implementando el Algoritmo Decimación en el tiempo en lenguaje C. Marcial Méndez Myfred Escuela Superior de Ingeniería Mecánica y Eléctrica Unidad Zacatenco, Av. Instituto Politécnico Nacional s/n, Unidad Profesional “Adolfo López Mateos”, Edif. 1, 2, 3, 4, 5, Col. Lindavista, Del. Gustavo A. Madero, México, D.F. C.P. 07738 E-mail: [email protected] Durante este proyecto, con el uso del algoritmo de decimacion en el tiempo se calculara la transformada rápida de Fourier implementado en lenguaje C, se utilizara Borland para compilar el código necesario para el cálculo, en particular se construirá un analizador de espectros empleando la transformada rápida de Fourier (FFT) y los resultados se visualizaran en un archivo ejecuctable.EXE.

I.

INTRODUCCIÓN Objetivos:

FFT es la abreviatura usual de un eficiente algoritmo que permite calcular la transformada de Fourier discreta (DFT) y su inversa. La FFT es de gran importancia en una amplia variedad de aplicaciones, desde el tratamiento digital de señales y filtrado digital en general a la resolución de ecuaciones en derivadas parciales o los algoritmos de multiplicación rápida de grandes enteros. Sin embargo, existen algunas limitaciones en el algoritmo por ejemplo pone ciertas limitaciones en la señal y en el espectro resultante, la señal de la que se tomaron muestras que se va a transformar debe consistir de un número de muestras igual a una potencia de dos. La mayoría de los analizadores TRF permiten la transformación de 512, 1024, 2048 o 4096 muestras. El rango de frecuencias cubierto por el análisis TRF depende de la cantidad de muestras recogidas y de la proporción de muestreo.

General. Calculo de una transformada rapida de fourier de un coseno usando lenguaje C,con posibilidad de utilizar e implementar el codigo en un dispositivo o precesador para PDS. Específicos. Aplicación del algoritmo Decimación en el tiempo, ya que este reduce de gran manera el numero de adicciones y multiplicaciones en el cálculo directo de una transformada discreta de Fourier (DFT). II.

MARCO TEÓRICO

Transformada de Fourier discreta en el tiempo. Supongamos que una señal continúa en el tiempo se le hace un muestreo con periodo o frecuencia de muestreo para obtener una señal discreta en el tiempo Se definirá la transformada discreta de Fourier de como la siguiente sumatoria, si es que existe:

La transformada rápida de Fourier es uno de los algoritmos más ampliamente usados ya que es un medio eficaz de ejecutar un cálculo matemático básico y de frecuente empleo. La transformada rápida de Fourier es de importancia fundamental en el análisis matemático y ha sido objeto de numerosos estudios. La aparición de un algoritmo eficaz para esta operación fue una piedra angular en la historia de la informática.

La transformada de la señal es obtenida haciendo la sustitución .Se puede notar que tiene periodo ya que la sumatoria es una serie de Fourier.

Las aplicaciones de la transformada rápida de Fourier son múltiples. Es la base de muchas operaciones fundamentales del procesamiento de señales, donde tiene amplia utilización. Además, proporciona un medio oportuno para mejorar el rendimiento de los algoritmos para un conjunto de problemas aritméticos comunes. [1]

La señal discreta en el tiempo puede determinarse a partir de su transformada discreta de Fourier a través de la integral inversa: 2

Transformada Rápida de Fourier: Decimación en Tiempo

Así, x[n] puede ser considerada como la suma de ondas senoidales a las que se les hace un muestreo en un continuo de frecuencias en la banda de Nyquist con amplitudes complejas dadas por el espectro de frecuencia de la señal. Transformada Discreta de Fourier y su inversa. Se tiene que sea una señal que es cero para fuera del conjunto {0,1,…, -1}.A esto se le llama una secuencia de N puntos [2].Suponemos que

algoritmos conocidos como transformadas rápidas de Fourier (FFT) que calculan la DFT indirectamente. Por ejemplo con la FFT reduce los requerimientos computacionales por un factor y la mejora aumenta con .

Un algoritmo de FFT tiene el nombre de algoritmo de Decimación en el tiempo. A continuación presento un breve desarrollo como referencia. Para simplificar la notación, hice que , así que (1) se convierte en

es la transformada discreta de Fourier de definida anteriormente. Entonces la transformada discreta de Fourier (DFT) de esa secuencia se define como la nueva secuencia de N puntos:

Este algoritmo asume que es una potencia de 2. Dividiendo la sumatoria en una suma sobre las pares y una suma sobre impares da

(1) + La DFT es simplemente conjunto de N muestras de tomadas en frecuencias separadas por en la banda de Nyquist. Se puede notar que si se permite que tome valores fuera del conjunto {0,1,…, -1}, el valor calculado por (1) se repite con periodo N. La secuencia original de N puntos puede ser determinada empleando la formula da la transformada directa de Fourier inversa (IDFT)

(2) Haciendo que los puntos pares sean la secuencia de puntos

y que los puntos impares sean la secuencia de puntos Transformada Rápida de Fourier. El cálculo directo de un solo punto de la DFT empleando (1) requiere adiciones y multiplicaciones, ignorando el hecho de que, para alguna , las exponenciales son 1 o -1.Entonces, el cálculo directo de todos los puntos requiere adiciones complejas y multiplicaciones complejas. La complejidad computacional puede ser reducida en un orden de mediante

También se puede notar que (2) puede ser escrita como

. Entonces

Transformada Rápida de Fourier: Decimación en Tiempo

III.

DESARROLLO Y ANÁLISIS.

Asumiendo que las DFT de puntos y son conocidas, se requiere multiplicaciones complejas para calcular , adiciones complejas para calcular , y sustracciones complejas para calcular para las adiciones y

+

Haciendo que y sean las DFT de puntos de y de tal forma que estas DFT tengan periodo . Con estas definiciones (2) se convierte en

el siguiente paso resulta en las ecuaciones clave para la FFT de Decimación en el tiempo. Primero se puede notar que .Entonces la ecuación anterior puede separase en dos ecuaciones:

(3)

sustracciones puede ser consideradas como iguales en términos de complejidad computacional. Entonces, la DFT completa de puntos fue calculada con multiplicaciones complejas y adicciones complejas a partir del par de DFT de puntos. Se empleo el mismo procedimiento para calcular las DFT de puntos a partir de DFT de puntos. El cálculo de las mediante estos métodos requiere multiplicaciones complejas y adicciones complejas. Encontrar las requeriría de la misma cantidad de cálculos. Por lo que la cantidad total de cálculos para determinar tanto como son multiplicaciones y adiciones, que es lo mismo que el cálculo de a partir de y . A partir de este análisis se implemento se implemento una función en C para calcular la FFT compleja de Decimación en el tiempo, de raíz 2.Toma el arreglo complejo de entrada en orden natural y lo acomoda en orden de bit- invertido. La salida se encuentra en orden natural.

(4) Las ecuaciones (3) y (4) muestran como calcular una DFT de N puntos mediante la combinación de un par de DFT de .En la siguiente figura se muestra un diagrama para este par de ecuaciones .Este cálculo es llamado mariposa de FFT debido a la forma del diagrama.

Las exponenciales complejas recursivamente.

son calculadas

Transformada Rápida de Fourier: Decimación en Tiempo

La salida de este programa de este programa debe ser toda 0 excepto para =8.La salida genera líneas espectrales en K=5 y 11 de altura 8.

La función principal calcula una FFT de 16 puntos de .

IV. CONCLUSIONES En este proyecto estudie sobre la transformada rápida de Fourier utilizando el algoritmo de Decimación en el tiempo, ya que me llamo mucho la atención puesto es una herramienta muy útil para el cálculo de la DFT minimizando el numero de cálculos, implementándolo particularmente en este lenguaje es posible darle uso en un procesadores específicos para PDS. Se procede a compilar

REFERENCIAS [1]http://es.wikipedia.org/wiki/Transformada_r%

C3%A1pida_de_Fourier [2] José G. viveros talavera, Fedro E. Ponce de león Luengas, Miguel Ángel pájaro Martínez, Diseño de sistemas de comunicaciones utilizando algoritmos de DSP (editorial UAM,2001).

Transformada Rápida de Fourier: Decimación en Tiempo

/*archivo de encabezado complex.h ---*/ /*archivo de encabezado que define la estructura de datos complex*/ struct cmpx { double real; double imag; }; typedef struct cmpx complejo;

//CODIGO #include #include "complejos.h" #include #include #include extern void fft(complejo *X, int M); void main(void) { complejo X[16]; /*declara el arreglo de entrada */ int i; /*indice para los cilos */ int M=4; /*log2(16)*/ double PI=3.141592653589; int N=16; /* numero de puntos de la FFT*/ /*inicializar el arreglo de entrada */ /*generar lineas espectrales en k=5 y 11 de altura 8 */ for (i=0;i