Fisica

INSTITUTO POLITÉCNICO NACIONAL
ESCUELA SUPERIOR DE INGENIERÍA MECÁNICA Y ELÉCTRICA
UNIDAD ZACATENCO

PROCESAMIENTO DE SEÑALES DIGITALES

PDS

-ALGORITMO DE LA MARIPOSA
-FFT

SOTO GARCIA JORGE RODRIGO
MENDOZA VELA JOSE ADRIAN
MARQUEZ JIMINEZ PABLO
HIDALGO SANCHEZ CHRISTIAN GEOVANNY
CUELLAR CONTRERAS CARLOS DANIEL
7CV2
Profa. Lozada Castillo Norma

PROCESAMIENTO DE SEÑALESDIGITALES

2013

INTRODUCCION:
El algoritmo de la mariposa es un método que se desprende de la transformada rápida de Fourier,
y nos permite descomponer o segmentar una transformada discreta de Fourier compleja o grande,
en sub transformadas más simples, o más fáciles de resolver.
El nombre de “mariposa” está dado por la forma que toma el diagrama de datos característico para
resolver laecuación. El ejemplo más sencillo es el de RADIX 2.
En el caso del algoritmo de radix-2 Cooley-Tukey, la mariposa es simplemente una transformada
de Fourier de tamaño-2, que toma dos entradas (x0, x1) (salidas correspondientes de las dos subtransformadas) y proporciona dos salidas (y0, y1 ) por la fórmula.

Si se dibuja el diagrama de flujo de datos para este par de operaciones, el (x0, x1) a (y0,y1) las
líneas se cruzan y se asemejan a las alas de una mariposa, de ahí su nombre.

PROCESAMIENTO DE SEÑALES DIGITALES

2013

ALGORITMO DE FFT MEDIANTE DIEZMADO EN EL TIEMPO
( )
En este proceso explotaremos tanto la simetría como la periodicidad
.Los
algoritmos en los que la descomposición se realiza sobre la secuencia x[n] , que se divide
sucesivamente en secuencias más pequeñas sedenominan algoritmos de diezmado en el tiempo.

El principio de algoritmo de diezmado en el tiempo se ilustra mas convenientemente considerando
el caso especial de que N es una potencia entera de 2, es decir, N= .
Para esto están las muestras pares e impares de x[n]:
[ ]

[

[ ]

[

]
] ,n=0,1,......

La DFT d N puntos en X[k] está dada por la separación de x[n] en secuencias de(N/2) puntos :
[ ]

∑ [ ]

Al separar los puntos pares e impares se obtiene:
[ ]

∑

[ ]

∑

[ ]

con el cambio de variables en n=2r para n par y n=2r+1 para n impar
( )

[ ]

( )

[

∑

( )

∑

Si

que es:

]

∑

[

]

[

]

( )

[

]

∑

PROCESAMIENTO DE SEÑALES DIGITALES

2013

Por lo tanto la Ecuación quedaría:

( )

[ ]

∑

()

[

]

[ ]

∑

[

]

[ ]

Cada una de las sumas de la ecuación anterior se reorganiza como una DFT (Transformada de
Fourier Discreta) de N/2 puntos. La primera suma es la DFT de (N/2) puntos de los puntos pares de
la secuencia original y la segunda suma es la DFT de (N/2) puntos de los puntos impares de la
secuencia original.
De estas ecuaciones se toman como calculo directodel diezmado en el tiempo ya que para
terminar de resolverlo se requiere (N/2) multiplicaciones para calcular
y asi calculando a
+N/2 con multiplicaciones complejas obteniendo a H[0] por
y sumando al resultado G[0]
,se obtiene multiplicando H[1] por
y sumando al resultado G[1]
Ya que al terminar se obtendrán dos secuencias de N/4 puntos
[ ]
[ ]

[
[

[ ]
[ ]

]
]

[
[

]
]Al calcular la DFT´s de N/4 puntos se obtienen las DFT´s de N/2 puntos llegando a una secuencia
con F1(k) y F2(k) a partir de las relaciones siguientes :

(

)

PROCESAMIENTO DE SEÑALES DIGITALES

2013

Donde Vij(k) son las DFT´s de N/4 puntos de las secuencias Vij(n) por que tras realizar la
descomposición tantas veces como sea posible el numero de multiplicaciones y sumas esigual a
Nv=N
. Si N= entonces esto se puede hacer un maximo de v=
.

Este diagrama representa el flujo de las operaciones del cálculo con la ecuaciones anteriores ya q
siendo más largas por las sustituciones y los cálculos de la DTF de (N2) puntos y de (N4) puntos a
N=8
DFT y FFT DE DOS PUNTOS O MARIPOSA
Cada mariposa implica una multiplicación y dos sumas complejas, es decir en la...