1

ELT 3952 PROCESAMIENETO DIGITAL DE SEÑALES

CAPITULOS

1) Señales y sistemas en tiempo discreto

2) Convolución

3) Transformada Z

4) Teorema del muestreo

5) Conversores A/D y D/A Sigma

6) Transformada discreta de Fourier

7) Transformada rápida de Fourier

8) Técnica de diseño de filtros.

BIBLIOGRAFIA

1) Tratamiento de Señales en Tiempo Discreto. Alan Oppenheim, et al

2) Tratamiento Digital de Señales Proakis Manolakis

3) The Scientist and Engineer’s Guide Steven W. Smith

4) Análisis de Fourier Hwei Hsu

2

Capitulo 1: SEÑALES Y SISTEMAS

Señal.-

Es algo que lleva información, una señal se representa matemáticamente como funciones de una

o más variables independientes por ej. Voz=f(t).

Imagen fotográfica = función de brillo respecto a dos variables espaciales.

La variable independiente puede ser continua o discreta.

1.- Señal en tiempo continuo es continua en sentido temporal y es una variable independiente

continua (señal analógica)

2.- Señal en tiempo discreto está representado en instantes discretos de tiempo o sea la variable

independiente toma valores discretos o se representan como secuencias de números y su

amplitud también puede ser continua o discreta.

Seña digital es discreta tanto en tiempo como en amplitud.

Secuencias.-

Son señales en tiempo discreto y son secuencias de números x en los que el n-simo número indica

como x[n] y se representa. ∞ ∞

Estas secuencias surgen de muestrear una señal analógica siendo el n-simo número de la

secuencia el valor de la señal analógica Xa(t) en el intervalo nT.

O sea: x[n]=Xa(nT) en el intervalo ∞ ∞

T es el periodo de muestreo 1/T = f muestreo

En forma gráfica

Figura 1

X[n] no está definida para valores no enteros de n

Secuencias básicas y operaciones básicas

El producto y la suma de secuencias x[n] y y[n] son también producto y suma muestra a muestra.

X[n] * α

Cada muestra se multiplica por

y[n] se retrasa respecto a x[n]

si y[n]=x[n-n0] n0

1.- Secuencia muestra unidad

Esta secuencia juega el mismo papel que la función Impulso Unidad (Delta Dirac) para tiempo

continuo.

Se la llama también “Impulso en tiempo discreto”. Cualquier secuencia se puede expresar como

una sumatoria de impulsos desplazados y escalados.

Ej. P[n]

Figura 4

Se puede expresar como

P[n]=a

Generalmente

2.- Escalón Unidad.-

3

Figura 2

Secuencias básicas y operaciones básicas.-

secuencias x[n] y y[n] son también producto y suma muestra a muestra.

Cada muestra se multiplica por .

y[n] se retrasa respecto a x[n]

Secuencia muestra unidad.-

Figura 3

Esta secuencia juega el mismo papel que la función Impulso Unidad (Delta Dirac) para tiempo

Se la llama también “Impulso en tiempo discreto”. Cualquier secuencia se puede expresar como

una sumatoria de impulsos desplazados y escalados.

P[n]=a-3 δ[n+3] + a-1δ[n-1] + a-2δ[n-2] + a-7δ[n-7]

Figura 5

secuencias x[n] y y[n] son también producto y suma muestra a muestra.

Esta secuencia juega el mismo papel que la función Impulso Unidad (Delta Dirac) para tiempo

Se la llama también “Impulso en tiempo discreto”. Cualquier secuencia se puede expresar como

4

U[n]=δ[n] + δ[n-1] + δ[n-2] + …..

Recíprocamente

δ[n]=u[n] - u[n-1]

3.- Secuencia Exponencial.-

є

La secuencia es real si α y A є

Si 0<α<1 y A 0 !"#$%$&"'

La secuencia es positiva y decrece al incrementar n

Figura 6

Si -1<α<0 los valores alternan el signo y el módulo decrece al aumentar n

Si |α| 1 el módulo de los valores de la secuencia crece al aumentar n.

Combinación de secuencias básicas.-

Si queremos una función

xn + , 00 0 -

Se puede lograr de un modo simple como:

X[n]= combinación

4.- Secuencias senoidales.-

X[n]=A cos(W0n+θ) .n

A y θ є

5

Figura 7

Si con є/ tiene parte Real e Imaginaria. Son sinusoides ponderadas exponencialmente.

Si || 123 y A=|| 124 || 124 . || 123 || || 12 364' || || cos : ; <' = >|| || #1 : ; <'

Si || 1 envolvente exponencial creciente

Si || 1 envolvente exponencial decreciente

Y : = π ||=1 secuencia exponencial compleja || 12 3?6@' = || cos : ; <' = >|| #1 : ; <' : frecuencia de la sinusoide compleja en radianes. < fase

Practica No. 1

Graficar todas las secuencias básicas en Excel o Matlab.

Sistemas en tiempo discreto.-

Un sistema en tiempo discreto se define como una transformación u operador que transforme una

secuencia x[n] en una secuencia de salida y[n]

y[n]=Tx[n]

x[n]=

figura 8

Ejemplo un sistema de retardo ideal.

y[n]=x[n-nd] ∞ ∞ nd >0 nd muestras a la derecha.

Si nd<0 |A| muestras a la izquierda entonces se trata de avance temporal.

Sistemas sin memoria.-

Si su salida .n depende solo de la entrada en el mismo valor n

Ej. y[n]= (x[n])2 .n

Sistemas lineales.-

Son sistemas que están definidos por el principio de superposición.

Si y1[n] e y2[n] si son las respuestas de un sistema cuando x1[n] e x2[n] el sistema es lineal si y solo

si

T x1[n]+ x2[n]= T x1[n] + T x2[n]= y1[n]+ y2[n]

Y T ax1[n] = aT x1[n] = ay[n]

Donde a es una constante

6

Sistema acumulador.-

Este sistema es lineal

Un sistema no lineal.

y[n]=log10 (||)

Sistemas invariantes en el tiempo.-

También llamado sistema invariante en el desplazamiento (shift invariant) es un sistema para el

que un desplazamiento temporal o retardo de la secuencia de entrada provoca el mismo

desplazamiento o retardo en la secuencia de salida.

Si x1[n]= x[n-n0] entonces y1[n]= y[n-n0]

Práctica.- Enumerar algunos sistemas lineales y no lineales, graficar las secuencias ya sea en Excel

o matlab.

Causalidad.-

Para todo no valor de secuencia de salida en el índice n=n0 depende de solo valores de secuencia

de entrada para n> n0, es no anticipativo, esto implica que si

x1[n]= x2[n] n≤n0

entonces y1[n]= y2[n] n≤n0

Ejemplo.-

y[n]= x[n-nd] ∞ ∞ Este sistema es causal para nd≥0 y no causal para nd<0

Sistemas LTI.-

Esta combinación de dos propiedades conduce a representaciones especialmente convenientes de

los sistemas que los cumplen. Existen muchas aplicaciones en el tratamiento de señales.

1) Superposición.-

T ax1[n]+b x2[n]= aT x1[n] + bT x2[n]

2) Linealidad.- Mas combinación de impulsos retrasados. Un sistema lineal queda

caracterizado por su respuesta al impulso.

hk[n]= respuesta del sistema a la entrada un impulso en n=k

Entonces

y[n]=T∑

y[n]=∑ C

y[n]= ∑ C

Sistema LTI

Linear Time Invariant

Dicha ecuación se puede llamar ecuación de convolución

y[n]=x[n]*h[n]

Respuesta al Impulso.-

La anterior ecuación nos da una

por x[n] es transformada por el sistema en una secuencia de salida

y que para cada valor de k estas secuencia se superponen para formar la

secuencia total de salida.

x[n] es la suma de las tres secuencias individuales

x[-2] x[0]

x-2[n]=

X0[n]=

X3[n]=

7

Dicha ecuación se puede llamar ecuación de convolución

La anterior ecuación nos da una interpretación de que la muestra de entrada en n=k representada

es transformada por el sistema en una secuencia de salida

y que para cada valor de k estas secuencia se superponen para formar la

Figura 9

x[n] es la suma de las tres secuencias individuales

x[3]

y-2

Figura 10

[n]= y0

Figura 11

[n]= y3

Figura 12

interpretación de que la muestra de entrada en n=k representada

para

y que para cada valor de k estas secuencia se superponen para formar la

8

x[n]=x-2[n]+x0[n]+x3[n] y[n]=y-2[n]+y0[n]+y3[n]

Figura 13

9

Capitulo 2: CONVOLUCION

Haciendo un resumen de cómo trabaja el sistema, el sistema cambia una señal de entrada en una

señal de salida.

Primero, la señal de entrada se descompone en un juego de impulsos, cada uno de los cuales

pueden ser vistos y escalados y desplazados por una función δ.

Segundo, la salida resultante de cada impulso se escala y desplaza según la respuesta impulso.

Tercero, la señal de salida resultante se encuentra añadiendo cada una de estas respuestas

escaladas y desplazadas individuales.

Este es un método grafico para realizar la convolución pero primero veremos lo que es la suma de

convolución.

Se demuestra que: h[n-k]=h[-(k-h)]

Si

h[k]

Figura 14

h[-k]=h[0-k]

Figura 15

h[n-k]=h[-(k-n)] (lqqd)

Figura 16

Resumiendo los tres pasos anteriores

1) Si h[k] es una secuencia y deseamos calcular h[n-k]=h[-(k-n)], se define h1[k]=h[-k]

2) Se define h2[k]=h1[k]retrasada n muestras en el eje k es decir h2[k]=h1[k-n]

3) Se demuestra la relación entre h1[k] y h[k] h2[k]=h1[k-n]=h[-(k-n)]

Para realizar la convolución en tiempo discreto se multiplican dos secuencias x[n] y h[n-k] en ∞ ∞ y se suman los productos para obtener la salida y[n]. Para obtener otra

muestras de salida se desplaza el origen de la secuencia h[-k] hasta la posición de la nueva

muestra y se repite el proceso.

10

Método gráfico.-

Haremos un ejercicio con un método gráfico de resolución.

Halle la convolución de la respuesta al impulso de un sistema lineal e invariante en el tiempo

H[n]=1,2↑,1,-1

Y la señal de entrada es x[n]= 1↑,2,3,1

La flecha indica la posición 0 en el eje n

1.- El primer paso, reflejamos h[k], la secuencia reflejada h[-k] es la resultante secuencia finita.

h[k] x[k]

Figura 17

2.- Reflejamos Multiplicamos x[k] punto a punto

h[-k] V0[k]

Figura 18

Donde V0[k]=x[k].h[-k]

3.- Reflejamos h[-k]

h[1-k] v1[k]

Figura 19

Donde V1[k]=h[1-k].x[k]

4.- Desplazamos a la izquierda

h[-1-k] V-1[k]

Figura 20

Donde V-1[k]=h[-1*k].x[k]

11

5.- Seguimos desplazando tanto a la derecha como a la izquierda hasta tener resultantes = 0 luego

se hace la suma general.

y[n]

Figura 21

Donde ∑ D

y[1]=8, y[-1]=1, y[n]=0 para n≤-2

entonces y[n]=…,0,0,1,4↑,8,8,3,-2,-1,0,0,….

Debemos señalar que la convolución es conmutativa, o sea que se puede desplazar tanto la

respuesta al impulso o la secuencia de entrada.

Procedimiento.-

1.- Reflexión h[k] respecto a k0 hasta h[-k]

2.- Desplazamiento de h[-k] una cantidad n0 hacia derecha o izquierda, si n0 es positivo (negativo)

para obtener h[n0-k]

3.- Multiplicación de x[k] por h[n0-k] para obtener una secuencia producto.

Vn0[k]=x[k]h[n0-k]

4.- Suma de todos los valores de la secuencia producto Vn0[k] para obtener el valor de la salida en

el instante n=n0.

Se evalúa en n= n0 y en todos los valores ∞ ∞ y se repite puntos 2 y 4 para todos los

posibles valores de desplazamiento temporal ∞ ∞

Método de la tira deslizante.-

También llamado Sliding Strip Method, este método es para secuencias finitas y al igual que en el

otro método se hace el reflejo de una de ellas luego se alinea las secuencias y se suman y

desplazan sucesivamente, veremos un ejemplo para notar mejor este procedimiento.

Sea h[n]=2,5,0,4, x[n]=4,1,3, ts=1/2. Las dos secuencias comienzan en n=0.

Se hace el “reflejo” de una de ellas, x[-n]=3,1,4.

Se alinea las secuencias y se suman y desplazan sucesivamente.

t=0

t=ts

t=2ts

h

2 5 0 4

2 5 0 4

2 5 0 4 k 3 1 4

3 1 4

3 1 4

0 0 8 0 0 0

0 2 20 0 0

6 5 0 0

suma=8

suma=22

suma=11

Ys(0)=8. 1/2=4

Ys(1)=22. 1/2=11.5 Ys(2)=11. 1/2=5.5

12

t=3ts

t=4ts

t=5ts

h 2 5 0 4

2 5 0 4

2 5 0 4 k 3 1 4

3 1 4

3 1 4

0 15 0 16

0 0 0 4 0

0 0 0 12 0 0

suma=31

suma=4

suma=12

Ys(3)=31. 1/2=15.5 Ys(4)=4. 1/2=2

Ys(5)=12. 1/2=6

Figura 22

La convolución discreta y[n] es 8,22,11,31,4,12. La convolución numérica es 4,11,5.5,15.5,2,6.

Método de las Suma por Columnas.-

Se hace el mismo ejemplo. No es necesario “reflejar” una de las secuencias.

n 0 1 2 3 4 5

h 2 5 0 4 x 4 1 3

8 20 0 16

2 5 0 4

6 15 0 12

y 8 22 11 31 4 12

Figura 23

8,22,11,31,4,12, 0,1,2, … 5

Método de la malla.-

C

2 5 0 4

8 20 0 16 4

8 2 5 0 4 1 x[n]

22 6 15 0 12 3

11 31 4 12 Figura 24

8,22,11,31,4,12, 0,1,2, … 5 En este método se colocan las dos secuencias en los dos ejes de una matriz que se forma de

acuerdo al tamaño de las dos secuencias y se van multiplicando casilla a casilla h[n] con x[n], los

resultados se colocan en cada casilla y luego se suman en forma diagonal todos los componentes y

la suma general se va colocando en los ejes opuestos a las secuencias.

Convolución en Matlab.-

13

Matlab dispone de dos funciones para el cálculo de convoluciones y correlaciones.

>>y=conv(x,h)

Convolución de dos vectores x y h. El vector resultante y tiene un tamaño igual a length(x) +

length(h)-1.

>>rxy=xcorr(x,y)

Hace la correlación de los vectores de M elementos x e y. Devuelve un vector de 2M-1 elementos.

>>rxx=xcorr(x)

Hace la autocorrelación del vector x de M elementos. Devuelve un vector de 2M-1 elementos.

Correlación y autocorrelación.-

Es una operación similar a la convolución, con la diferencia de que en la correlación nohay que

reflejar una de las señales.

Rxy(t)=x(t)**y(t)=L M' N %'O% %' = %'

Relación entre la convolución y la correlación

Rxx(t)=x(t)**x(t)=L M' M %'OM'

La autocorrelación representa la similitud entre una señal y su desplazada. El máximo de

autocorrelación ocurre cuando no hay desplazamiento (t=0) y es simétrica respecto al origen, ya

que Rxx(t) = Rxx(-t)

Ejercicio para los alumnos.-

Realiza la convolución y[n] por el método gráfico de x[n]=(1↑,2) y h[n]=(2↑,1,1,1).

Capitulo 3: TRANSFORMADA Z

Esta transformada es una herramienta muy importante para el análisis de señales y sistemas LTI.

La Transformada Z realiza el mismo papel en señales discretas lo que la transformada de Laplace

para las señales continuas.

Por ejemplo, la convolución, el tiempo es equivalente a producto en la transformada Z.

La transformada Z proporciona un medio de caracterizar a los sistemas LTI y su respuesta a

diversas señales mediante las posiciones de polos y ceros.

Concepto.-

Si X(n) es una señal discreta en el tiempo entonces

P' 'P

Z es variable compleja esta es la transformada directa.

Ejemplo: Si x(n)=(1↑,2,5,7,0,1) una secuencia finita.

X(Z)= 1+2Z-1 + 5Z-2 + 7Z-3 + Z-5

Su región de convergencia ROC es el plano Z complejo excepto en Z=0.

ROC.-

La región de convergencia es un conjunto de todos los valores de Z para los que X(Z) toma valor

finito.

14

La variable compleja Z en forma polar

P Q12@ Q |P| < R P

P' 'Q

12@

STN | P'| ∞

| 'Q|

U

Figura 25

Pero | P'| V∑ 'Q 12@V W ∑ V 'Q12@V ∑ | 'Q|

Desde el punto de vista matemático la Transformada Z es una representación alternativa de una

señal como P' 'P

Los coeficientes de P corresponden al valor de la señal en el instante n o sea el exponente de Z

contiene la información temporal que se necesita para identificar las muestras de la señal.

Ejemplo.-

' XUY

Z ' Número infinito de valores diferentes a 0

x(n)=´1, (1/2), (1/2)2, (1/2)3,…, (1/n)n

X(z)= 1 + (½)Z-1 + (½)2Z-2 + … + (½)nZ-n

P' 12'P

P' 12 PU'

Esta es una serie geométrica infinita de la forma

1+A+A2+A3+…+An = U

U[ si || 1

Luego \UY PU\ 1 |P| U

Y

Esto se llama una alternativa compacta de la señal x(n).

Propiedades de la Transformada Z.-

15

1.- Linealidad.-

Si x1(n) ↔ X1(Z)

Y x2(n) ↔ X2(Z)

Entonces x(n)=a1x1(n)+a2x2(n) ↔a1 X1(Z)+a2 X2(Z)

Ejemplo.-

Si x(n)=[3(2n)-4(3n)]u(n)

Determinar la Transformada Z y su ROC

x1(n)=2nu(n)

x2(n)=3nu(n)

x(n)= 3x1(n)-4x2(n)

X(Z)= 3X1(z) – 4X2(Z)

Como anu(n) ↔ U

U]^_`

ROC= |P| |a| a=2 a=3

x1(n)=2nu(n) ↔ X1(Z)= U

UY^_` |P| 2

x2(n)=3nu(n) ↔ X2(Z)= U

Ub^_` |P| 3

X(Z)= bUY^_` c

Ub^_` ROC = |P| 3

2.- Desplazamiento temporal.-

Si x (n) ↔ X (Z)

x(n-k) ↔ Z-kx(z) ROC x(Z) excepto en z=0 si k>0 y z=∞ si k<0

3.- Cambio de escala en el dominio Z.-

Si x (n) ↔ X (Z) ROC QU || QY

anx(n) ↔x(aUP) ROC |a|QU |P| |a|QY

4.- Inversión temporal.-

Si x (n) ↔ X (Z) ROC QU |P| QY

x(-n) ↔ X(Z-1) ROC U

dee |P| Ude

5.- Diferenciación en el dominio Z.-

Si x (n) ↔ X (Z)

nx(n) ↔ P Af g'Ag

6.- Convolución.-

Si x1 (n) ↔ X1 (Z)

Y x2 (n) ↔ X2 (Z)

X(n)=x1(n)*x2(n) ↔ X(Z)=X1(Z).X2(Z)

Ejercicios para el alumno.-

Realizar las siguientes transformadas.-

1) x(n)=1,2,5↑,7,0,1

2) x(n)=0↑,0,1,2,5,7,0,1

16

3) x(n)=2,45↑,70

4) x(n)=δ(n)

5) x(n)= δ(n-k) k>0

6) x(n)= δ(n+k) k>0

17

Capitulo 4: MUESTREO DE SEÑALES EN TIEMPO CONTINUO

Las señales en tiempo discreto aparecen de varias formas, una de ellas es que aparezcan como

consecuencia del muestreo de señales en tiempo continuo.

Señal continua →muestreo →señal en tiempo discreto

Muestreo periódico, a partir de una señal continua, se obtienen secuencias de muestras x[n]

mediante la relación:

X[n]=xc(nT)

T es el periodo de muestreo y fs=1/T es la frecuencia de muestreo [muestras/seg].

Cuando se desea usar unidades en radianes por segundo Ωs=2π/T, es la frecuencia de muestreo.

Este proceso se denomina C/D o conversor ideal de tiempo continuo en tiempo discreto.

En la práctica este proceso se realiza por un ADC (conversor Análogo digital)

El muestreo no es invertible.

El muestreo se puede representar dividiéndola en dos etapas.

Figura 26

1.- Modulador con un tren de impulsos

2.- Conversión del tren de impulsos en una secuencia.

Aquí se muestra una señal de tiempo continuo Xc(t) y el resultado de muestrearla con un tren de

impulsos para dos frecuencias de muestreo diferentes y sus secuencias de salida respectivas.

Figura 27

La secuencia de números x[n] no contiene información sobre la frecuencia de muestreo.

Xs(T) es señal continua(tren de impulsos) que es cero excepto en múltiplos enteros de T.

x[n] está indexada con la variable entera n, es decir normalizado en el tiempo.

Representación del muestreo en el dominio de la frecuencia.-

Conversión de tren de impulsos a

secuencia en tiempo discreto.

S(t)

Xc(t)

Xs(t)

X[n]=Xc(nT)

18

Para obtener una relación entre la entrada y la salida de un conversor C/D ideal en el dominio de

la frecuencia, se considera la conversión de Xc(t) en Xs(t) mediante la modulación con el tren de

impulsos.

h %' % i'

δ(t) función impulso unitario o delta Dirac. Si modulamos δ(t) con Xc(t)

Xs(t)=Xc(t)s(t)

Xs(t)=xc(t) ∑ % i'

Xs(t)= ∑ j i' % i'

Propiedad de desplazamiento

Transformando con Fourier Xs(t)

Como Xs(t)=xc(t)s(t)

Sus transformadas se pueden convolucionar

h >Ω' 2li % i'

Ωs=2π/T frecuencia de muestreo en radianes

# >Ω' 12l j >Ω' = # >Ω'

Convolución

# >Ω' 1i j > Ω kΩs''

Es decir que la transformada de Xs(t) consiste en copias repetidas en forma periódica de la

transformada de Fourier de Xc(t)

Figura 28

Espectro de la señal original.

Figura 29

Espectro de la función de muestreo

19

Figura 30

Espectro de la señal muestreada con Ωs>2ΩN

Entonces Ωs- ΩN >ΩN del grafico o sea

Ωs >2ΩN

Es decir que la frecuencia de muestre debe ser al menos dos veces la frecuencia de la señal

muestreada ΩN.

Esas réplicas no se solapan, por tanto la señal Xc(t) se puede recuperar con un filtro paso bajo.

Figura 31

Espectro de la señal muestreada con Ωs >2ΩN. Existe solapamiento (aliasing) de las copias, de tal

forma que al sumar, ya no se puede recuperar la señal Xc(t) original.

Xc(t) se puede recuperar a partir de Xs(t) con un filtro paso bajo.

Figura 32

Figura 33

(ΩS-ΩN)

Figura 34

Hr(jΩ)

Xc(t)

Xr(t) Xs(t)

Hc(jΩ)

20

Figura 35

Señal recuperada con el filtro pasobajo

Xr(jΩ)=Xc(jΩ)

2.- Caso de transformada de Fourier de una señal coseno.-

Xc(t) = Cos Ωot

Primero se muestra la transformada de Fourier de dicha señal, primero con una frecuencia de

muestreo Ωo < Ωs/2 y luego Ωo > Ωs/2.

Figura 36

Transformada de Fourier de cos Ωot

Ωo<π/T= Ωs/2

Figura 37

Cuando Ωo < Ωs/2

Ωo>π/T= Ωs/2

Figura 38

Cuando Ωo > Ωs/2

Ωo<π/T

Figura 39

Reconstrucción de la señal cuando Ωo < Ωs/2

21

Figura 40

Reconstrucción de la señal cuando Ωo > Ωs/2

Reconstrucción de la señal cuando Ωo > Ωs/2, la señal reconstruida en el primer caso es

Xr(t)= cos Ωo t y en el segundo gráfico Xr(t)=cos ( Ωs- Ωo)t Estas son señales diferentes alias de baja

frecuencia.

Con este ejemplo se ve la base del teorema de muestreo o de Nyquist o Shannon que dice:

Si Xc(t) es la señal de banda limitada que cumple que Xc(jΩ)=0 para |Ω|≥ΩN Xc(t) estará

determinada de forma única por sus muestras x[n]=Xc(nT) para n=0, ±1, ±2, ±3, ±4,….

Si se cumple que Ω# Yno , 2Ωp

2ΩN debe ser menor que la frecuencia de muestreo se denomina frecuencia de Nyquist. Como

# >Ω' 1i j > Ω kΩs''

Y ω= ΩT escalado, entonces

q123r 1i j > sωT 2πkT w'

Y Ω = Ωs en Xs(j Ω) se convierte en ω= 2π en X(123)

Ejemplo de muestreo y reconstrucción de una señal senoidal.-

Si Xc(t)=cos(4.000 πt) y la muestreamos con un periodo T de muestreo T= 1/6.000 obtenemos la

señal x[n]=xc(nT) = cos (4.000 πTn)= cos(ωon) con ωo= 4.000πT= 2π/3

En este caso Ωs=2π/T = 12.000 π y la frecuencia más alta de la señal es Ωo= 4.000 π y se satisfacen

las condiciones de un muestreo de Nyquist y no hay solapamiento.

La transformada de Fourier de Xc(t) en tiempo continuo.

Xc(j Ω)= π δ(Ω-4.000 π)+ π δ(Ω+4.000 π)

Transformada de Fourier de Xc(t) en tiempo continuo

Figura 41

Transformada de Fourier en tiempo discreto de frecuencia = Ωo=4.000 π con T=1/6.000

Figura 42

22

Se ve que Xc(j Ω) es una pareja de impulsos situados en Ω=±4.000 π y que aparecen copias de la

transformada de Fourier centradas en ± Ωs, ± 2Ωs, etc. El segundo párrafo muestra a X(123)= Xc(j

ω/T) en función de la frecuencia normalizada ω =Ω /T; δ(ω/T' T δ(ω'

Ωo=4.000π= ωo=4.000 ω T=2 π/3 ó ωo< π, ωo=4.000 ω < π; Ωo=4.000π< π/T=6.000 π

Hr(jΩ) es el filtro de reconstrucción ideal para Ωs=12.000 π

Se reconstruye con una frecuencia igual a Ωo=4.000π que es la frecuencia original y no existe

solapamiento.

Capitulo 5: CONVERSORES DIGITAL ANALOGO Y ANALOGO DIGITAL

El proceso de conversion A/D se puede desglosar en dos etapas: muestreo y cuantización.

La primera etapa sería la de muestreo y mantenimiento S/H Sample and Hold donde la

información analógica es la instantánea a medida que se le va muestreando.

Figura 43

Entre la señal digital y la señal muestreada existe un error que se le llama error de cuantificación,

que puede ser ±1/2 LSB, el cual a veces se puede tomarlo como ruido aditivo a la señal.

Por ejemplo si tenemos una señal con una amplitud máxima de 1 volt y un ruido random de 1

mV.rms. Al digitalizar esta señal en 8 bits resulta que 1 volt es 255 y 1 mV llega a ser 0.255 LSB. Las

señales de ruido ase añaden a la señal como varianza aditiva en cuadratura es decir 1 √Y ; zY. Entonces el ruido total en la señal digitalizada está dada por

0.386 |hz √0.255Y ; 0.29Y , esto incrementa casi en 50% al ruido existente en la señal.

23

Al digitalizar esta misma señal pero en 12 bits no se produce virtualmente ningún incremento y

por tanto nada se pierde debido a las cuantización.

Por tanto se debe decidir en cual utilizar preguntándose si cuanto ruido existe ya en la señal

analógica y/o cuanto ruido se puede tolerar en la señal digital.

En algunos sistemas sin embargo, debido a la señal original que varia muy poco, se puede añadir

un poco de ruido intencionalmente de forma que en el proceso de cuantización la señal contenga

mas información (dithering). Esto puede añadirse con un generador de ruido randomico.

Luego de la digitalización, la computadora puede restar estos números randómicos (substractive

dither) para recuperar la señal original.

Conversión D/A.-

Este proceso trata de jalar las muestras realizadas de la memoria y convertirlas luego en un tren

de impulsos. Como electrónicamente es difícil generar los pulsos se necesita de un elemento que

es el retenedor de orden cero, que es el equivalente al S/H de los ADC, esto produce una señal

como gradas durante el proceso.

Figura 44

En el dominio de la frecuencia, el retenedor de orden cero resulta en el espectro del tren de

impulsos que esta multiplicado por una curva que se la llama función sin o sinc(x).

~ ' sin l#'l/#

Esta función puede ser entendida como la convolución del tren de impulsos con un pulso

rectangular que tiene un ancho igual al periodo de muestreo.

24

Espectro del tren de impulsos Espectro multiplicado por Sinc

Filtro de reconstrucción ideal 1/sinc Espectro reconstruido (regenerado)

Figura 45

Filtros analógicos para la conversión de datos.-

Este es un sistema DSP ideal como lo dicta el teorema del muestreo de Nyquist.

Figura 46

El filtro antialiasing remueve frecuencias encima de ½ la velocidad de muestreo antes de llevarlo al

ADC para prevenir el solapamiento.

El segundo filtro remueve frecuencias hasta la frecuencia de Nyquist para reconstruir la señal, se le

llama filtro de reconstrucción y este incluye la frecuencia retenedora de orden cero.

Los tipos de filtros son los comunes Chebyshev, Butterworth y Bessel (Thompson), los cuales se

pueden ajustar mediante el número de polos y seros. Más polos y ceros significan más electrónica,

y lógicamente mejor rendimiento.

Para propósitos de DSP, es más importante las características del filtro que como se las

construye.

Este es un punto fijo de filtro analógico que se describe a continuación.

Entrada

analógica

Entrada

analógica

filtrada

Entrada

Digitalizada

Salida

digitalizada

Salida

analógica

S/H

Salida

analógica

25

Figura 47

Circuito Sallen Key de dos polos paso bajo

S UN

S SUY

Por ejemplo se utiliza la siguiente tabla para encontrar los diferentes parámetros.

Bessel Butterworth Chebyshev

# de polos K1 K2 K1 K2 K1 K2

2 etapa 1 0.1251 0.268 0.1592 0.586 0.1293 0.842

4 etapa 1 0.1111 0.084 0.1592 0.152 0.2666 0.582

4 etapa2 0.0991 0.759 0.1592 1.235 0.1544 1.660

6 etapa 1 0.0990 0.040 0.1592 0.068 0.4019 0.537

6 etapa 2 0.0941 0.364 0.1592 0.586 0.2072 1.448

6 etapa 3 0.0834 1.023 0.1592 1.483 0.1574 1.846

8 etapa 1 0.0894 0.024 0.1592 0.038 0.5359 0.522

8 etapa 2 0.0867 0.213 0.1592 0.337 0.2657 1.379

8 etapa 3 0.0814 0.593 0.1592 0.889 0.1848 1.711

8 etapa 4 0.0726 1.184 0.1592 1.610 0.1582 1.913

Tabla 1

Ejemplo.- Para diseñar un filtro Butterworth de dos polos a 1 Khz localizamos la tabla y nos da

k1=0.1592 y k2=0.586, seleccionamos valores comerciales para R y C empezando por R1=10KΩ y

C=0.0.1µF, de donde R=k1/Cfc= 0.1592/0.01*1 Khz=15.95 kΩ.

Con resistencias comerciales a 1% se tiene Rf=5.9 kΩ y R=15.8 kΩ

El amplificador operacional no es crítico pero su ganancia se debe dar entre 30 y 100 más alta de

la fc, siempre que fc sea menor a 100Khz.

Para formar filtros de 4,6 y 8 polos, se coloca el mismo circuito Sallen-Key en cascada y las etapas

se numeran de izquierda a derecha, si se necesita un filtro paso alto entonces solo debe

intercambiarse R y C.

Ahora se debe analizar 3 características clásicas de los filtros.

1.- Frecuencia de corte Fc chebyshev es mejor, butterworth es peor y Bessel el peor.

26

2.- Rizado o sea variaciones en forma de ondas en la amplitud de las frecuencias que pasan

Chebyshev permite, Butterworth permite y Bessel no permite.

3.- Respuesta al escalón, Chebyshev tiene overshoot y rizado, Butterworth tiene overshoot y

ringing, la que son oscilaciones que lentamente decrecen en amplitud, Bessel no tiene.

Resumiendo Chebyshev optimiza la rectitud de la banda pasante y Bessel optimiza la respuesta al

escalón.

Para elegir hay que ver la aplicación, si la codificación es en el dominio del tiempo o de la

frecuencia.

Conversión de datos a multivelocidad.-

Cuando se trata de reemplazar circuitos analógicos en algoritmos digitales se utiliza la conversión

de datos.

Ejemplo.- Si capturamos frecuencias de voz de banda entre 100 y 3000 Hz pero el micrófono

introduce frecuencias de 40 Khz. Aplicando fríamente la técnica, es de pasar un filtro Chebyshev

de8 polos a 3 Khz y luego muestrear a 8 Khz. Al otro lado, el DAC reconstruye la señal a 8 Khz con

un retenedor de orden cero y otro filtro Chebyshev a 3 Khz para producir la señal original.

Pero la otra solución sería muestrear la voz a 64 Khz y el filtro pasa bajo a 3 Khz y rechaza

frecuencias por encima de los 32 Khz, igualmente al otro lado. Pero el filtro esta vez es solo un

arreglo RC. Otro nivel sería el de técnica multivelocidad en donde se pasa la señal de voz por un

filtro RC y muestrear a 64 Khz, la señal así tiene la información de 100 a 3 Khz.

Luego remover frecuencias indeseables por software, con un filtro paso bajo digital a 3 Khz.

Por último, remuestrear dicha señal de 64 Khz a 8Khz simplemente descartando 7 de cada 8

muestras (decimación).

El resultante es equivalente al producido por un filtro analógico a 8 Khz

Conversión de datos a un solo bit.-

Esto se usa en música de alta velocidad DAC y ADC de simple bit, y usa el modulador DELTA.

Modulador DELTA.-

Figura 48

El comparador decide cual tiene mayor voltaje y se forma un 0 o un 1 que se aplica a la entrada del

latch, el reloj a 100 Khz sincroniza el latch de modo que la salida da 0 o 1 y carga ya sea

positivamente o negativamente al capacitor C por pequeños montos de voltaje (mV) , el positivo

aumenta la carga al capacitor y el negativo lo disminuye

27

Figura 49

El número relativo de unos Vs. Ceros es directamente proporcional a la pendiente o derivada de la

señal de entrada analógica.

Desventaja.- Hay que muestrear a altas velocidades ejemplo la voz a 64 Khz no es comercial.

Pendiente Delta de variable continua.-

Para solucionar el problema anterior esta técnica se implemento por Motorola MC3518. El reloj y

el tamaño de la cuantización se colocan entre 30 Khz y 2000 niveles, el slew rate muy pronunciado

y un registro chequea los últimos 4 bits que produce el sistema.

Si el circuito esta en condición de slew rate limitada, y los últimos 4 bits sean todos 1 (pendiente

positiva) o todos 0 (pendiente negativa) y un circuito lógico detecta esto y produce una señal

analógica que incremente el nivel de carga producido por los inyectores.

Figura 50

Este filtro y lógica mejoran el slew rate mientras dure la condición de pendiente, la lógica

incrementa el nivel de carga de los inyectores. Esto amplifica el slew rate incrementando el

tamaño de los escalones de voltaje aplicados al capacitor.

28

Convertidor Delta Sigma.-

Figura 51

Este circuito combina electrónica analógica con algoritmos DSP. El capacitor se compara con

potencial de tierra y el voltaje decrece cuando la salida digital es 1 e incrementa su salida digital si

es 0.

Se trata de mantener el voltaje en el capacitor a 0 volts.

El numero de 1 y 0 entonces ya no es pendiente sino nivel del voltaje de entrada.

Ej.- Si tenemos 12 bits entonces en 4096 ciclos de reloj contamos el numero de unos y el número

4095 es igual al máximo nivel positivo y 0 es el máximo nivel negativo de voltaje.

2048 seria el cero.

Para reconstruir esta señal de 1 y 0 se requiere un filtro RC y saca un promedio por ejemplo si un

uno = 5 volts y cero = 0 volts, si el 80% de los bits en la serie de datos son 1 y 20% ceros entonces

el Capacitor se carga a 4 Volts.

El decimador reduce la velocidad de muestreo el cual descarta la mayoría de las muestras.

Capitulo 6 LA TRANSFORMADA DISCRETA DE FOURIER

Como se vio en anteriores temas, el muestreo en el dominio del tiempo de una secuencia

aperiódica de energía finita x(n), nos lleva directamente al concepto de la TDF, las muestras en

frecuencia espaciadas X(2kπ/N) con k=0,1,2,3,….N-1, no representan a la secuencia original x(n)

cuando esta tiene duración infinita. En lugar, las muestras en frecuencia X(2kπ/N) con

k=0,1,2,3,….N-1 corresponden a una secuencia periódica xp(n) de periodo N, esta xp(n) es una

versión con aliasing o solapamiento de x(n)

' '

Y si la secuencia tiene una longitud finita L ≤ N, entonces xp(n) es una repetición periódica de x(n)

donde esta se da en un solo periodo por

' + ' 0 W | 1 0 | W W 1-

Por tanto dichas muestras representan la secuencia de duración finita x(n) que se pueden obtener

de las muestras en frecuencia por medio de

29

' 1 Ynp '12Yn/ppU

0,1,2 … . 1

Hay que hacer notar que el rellenado con ceros no da información adicional acerca del espectro

de la señal X(ω)). Las L muestras equidistantes de X(ω) son suficientes para reconstruir X(ω)

usando las formula de reconstrucción

X ω' X s2πN kw P sω 2πN w kU

Resumiendo la secuencia de duración finita x(n) de longitud L tiene una transformada de Fourier

X ω' x n' eU

0 W ω W 2π

Si muestreamos X(ω) en frecuencias igualmente espaciadas ωk=2πkn/N, k=0,1,2,…N-1 donde N≥L

las muestras resultantes son:

X k' X s2πN kw x n' eY/U

X k' x n' eY/U

k 0,1,2, … N 1

Donde el índice superior del sumatorio se ha incrementado de L-1 a N-1 ya que x(n)=0 para n≥L.

Esta fórmula permite transformar una secuencia x(n) de longitud N≤L en una secuencias de

muestras en frecuencia de longitud N. Ya que dichas muestras se obtienen evaluando la TDF en un

conjunto de de N frecuencias discretas espaciadas equitativamente, la relación anterior se define

como la TDF de x(n).

Resumen de las formulas:

DFT: X k' x n' eY/

U

k 0,1,2, … N 1

IDFT: ' 1 '12Yn/p

pU

0,1,2 … . 1

Ejemplo:

Una secuencia de duración finita de longitud L está dada por:

' X1 ,0 W W | 10 , 1 "%Q" ja#" Z

Determinar la DFT de N puntos de esta secuencia para N≥L

Solución:

La transformada de Fourier de esta secuencia es:

X ω' x n' eU

30

eU

1 123

1 123 sen ωL2 'sen ω2' e U'/Y

El módulo y la fase de X(ω) se muestra en la figura, para L=10. La DFT de N puntos de x(n=) es

simplemente X(ω) evaluada en el conjunto de N frecuencias espaciadas equitativamente X(2kπ/N)

con k=0,1,2,3,….N-1 luego se tiene:

X k' 1 12Ynp1 12Ynp

k 0,1,2, … N 1

sen πkLN 'sen πkN ' e U'/

Si N se selecciona de tal forma que N=L la DFT es: ' X | , 0 0 , 1,2,3 … | 1Z

Entonces existe solo un valor distinto de cero en la DFT. Esto es así porque observamos X(ω), ya

que X(ω)=0 en las frecuencias ωk=2πk/L, k≠0, se puede calcular la IDFT con L puntos y recuperar

x(n).

Aunque con L puntos es suficiente para representar la secuencia x(n) en el dominio de la

frecuencia, no da mucho detalle para sus características espectrales. Si queremos mejorar

tendremos que interpolar X(ω) con un menor espaciado por ej. En donde N L podemos ver esto

como una expansión del tamaño de la secuencia de L a N puntos. Añadiendo N-L ceros a las

secuencia x(n)k, así la DFT de N puntos proporciona una interpolación más ajustada que la DFT de

L Puntos.

En el dibujo se nota el modulo y la fase para L=10 N=50 y N=100 en donde la secuencia se ve más

clara al comparar dichos espectros.

31

Figura 52

Figura 53

32

Figura 54

La DFT como transformación lineal.-

Haciendo un cambio de definición donde

Tenemos que las formulas de DFT e IDFT serían como siguen:

Es la raíz enésima de valor unidad.

El cálculo de cada punto de la DFT se puede llevar a cabo realizando N multiplicaciones complejas

y (N-1) sumas complejas, luego los valores de la DFT de N puntos pueden calcularse realizando un

total de N2multiplicaciones complejas y N(N-1) sumas complejas.

Definimos un vector de N puntos xN de la secuencia x(n) con n=0,1,2,….n-1, un vector de N puntos

XN de muestras en frecuencia y una matriz N x N WN como sigue:

x(0)

xN = x(1)

…..

x(N-1)

X(0)

XN = X(1)

…..

X(N-1)

33

1 1 1 … 1

WN = 1 WN WN2 ... WN N-1

1 WN2 WN

4 … WN 2(N-1)

… … … …

1 WN N-1 WN 2(N-1) WN (N-1)(N-1)

Con estas definiciones la DFT de N puntos se puede expresar en forma matricial como:

XN = WN xN

Donde WN es la matriz de la transformación lineal. WN es una matriz simétrica, si disponemos de la

inversa de WN, entonces se puede invertir la matriz premultiplicando ambos lados de la ecuación

por WN-1 , de donde se tienen las siguientes relaciones:

xN = WN-1 XN

Y la IDFT se expresa como:

xN = 1/N WN* XN

Donde WN* es el conjugado complejo de la matriz WN de donde comparando se tiene.

WN-1 = 1/N C

Lo que a su vez implica que

WN WN* = NIN

Donde IN es una matriz identidad N x N, por tanto, la matriz WN de la transformación es una matriz

ortogonal (unitaria), además existe su inversa y está dada por WN*/N y la existencia de la inversa

de WN se ha establecido antes.

Ejemplo de cálculo de la DFT

Sea una secuencia de cuatro puntos, calcule la DFT

X(n)= (0 1 2 3)

Encontrar la matriz W4 y la propiedad de simetría

WN k +N/2 = -WNk

La propiedad de periodicidad:

WN k +N = WNk

W40 W4

0 W40 W4

0 1 1 1 1

WN = W40 W4

1 W42 W4

3 = 1 W41 W4

2 W43

W40 W4

2 W44 W4

6 1 W42 W4

0 W42

W40 W4

3 W46 W4

9 1 W43 W4

2 W41

1 1 1 1

WN = 1 -j -1 j

1 -1 1 -1

1 j -1 -j

34

6

De donde X4=W4x4 = -2+2j

-2

-2-2j

La IDFT de X4 puede determinarse conjugando los elementos de W4 para obtener W4* y aplicando

la formula: xN = 1/N WN* XN

La DFT y la IDFT son herramientas de calculo que desarrollan un papel importante en las

aplicaciones de tratamiento digital de la señal, como ser análisis en frecuencia de señales,

estimación del espectro de potencia y filtrado lineal.

Capitulo 7 TRANSFORMADA RAPIDA DE FOURIER

Se ha visto que el algoritmo de la DFT es muy importante en las aplicaciones del tratamiento

digital de la señal, incluyendo el filtrado lineal, correlación y análisis espectral, pero en esta

sección se estudia un algoritmo eficiente para calcular la DFT, mediante otros algoritmos que se

llaman FFT (Fast Fourier Transform) especialmente cuando el tamaño de N es una potencia de 2 y

cuando es potencia de 4.

Básicamente el problema de calcular la DFT es calcular la secuencia X(k) de N valores complejos

dada otra secuencia de datos x(n) de longitud N, esto se aprecia en la formula:

' 'p 0,1,2, … 1pU

Donde p 12Yn/p

La secuencia de datos x(n) se considera compleja.

Igualmente la IDFT es:

' 1 'p 0,1,2, … 1pU

En estas formulas se puede ver que tanto la DFT como la IDFT implican el mismo tipo de cálculos,

es decir el cálculo implica N multiplicaciones complejas (4N multiplicaciones reales) y N-1 sumas

complejas y N2-N sumas complejas.

El cálculo de la DFT es ineficiente, ya que no se aprovecha las propiedades de la simetría y

periodicidad del factor de fase WN cuyas propiedades son:

Simetría: WN k +N/2 = -WNk

Periodicidad: WN k +N = WNk

Los algoritmos eficientes de cálculo conocidos como FFT aprovechan estas dos propiedades del

factor de fase.

35

Para el cálculo directo de la DFT y teniendo en cuenta una secuencia compleja x(n) de N puntos la

DFT se puede expresar como sigue:

' 'j"# 2l ; '#1 2l pU

' '#1 2l 'j"# 2l pU

Este cálculo directo requiere:

1.- 2N2 evaluaciones trigonométricas

2.- 4N2 multiplicaciones reales

3.- 4N (N-1) sumas reales

4.- Una serie de operaciones de indexación y direccionamiento.

Operaciones realizadas en lel algoritmo de DFT las multiplicaciones reales y las sumas reales dan

los resultados de los valores XR(k) y XI(k) de la DFT, las operaciones de indexación y

direccionamiento son necesarias para extraer los datos de x(n) en los valores de n entre 0 y N-1 y

los factores de fase y almacenar los resultados.

En esta sección se explicará un método para volver eficiente este cálculo.

Método divide y vencerás para calcular la DFT.- Este algoritmo posibilita la descomposición de una

DFT de N puntos en transformadas DFT sucesivamente más pequeñas. Esto nos lleva a una familia

de algoritmos de cálculos eficientes conocidos como algoritmos FFT.

Si consideramos el cálculo de una DFT de N puntos, donde N puede descomponerse en factores

como un producto de dos enteros.

N=LM

La suposición de que N no es un número primo no es restrictiva, ya que podemos rellenar

cualquier secuencia con ceros para asegurar una descomposición en factores de la forma indicada

arriba.

n 0 1 2 N-1

x(0) x(1) x(2) … X(N-1)

La secuencia x(n), 0≤n≤N-1, puede almacenarse en una matriz unidimensional indexada por n o

como una matriz bidimensional indexada por l y m donde 0≤l≤L-1 y 0≤m≤M-1, las cuales se

muestran en la siguiente tabla, l es el índice de las filas y m es de las columnas. Así, la secuencia

x(n) puede almacenarse en una matriz rectangular de diferentes maneras, dependiendo cada una

de la correspondencia existente entre el índice n y los índices (l,m)

36

x(0,0) x(0,1) ………..

x(1,0) X(1,1) ………..

x(2,0) x(2,1) ………..

…….. ……… ………..

………..

Por ejemplo si seleccionamos la correspondencia

n=Ml+m

Esto lleva a disposición de que la primera fila consta de los primeros M elementos de x(n), la

segunda fila está formada por los M elementos siguientes de x(n) y así sucesivamente como se

muestra abajo.

x(0) x(1) x(2) ……….. x(M-1)

x(M) x(M+1) x(M+2) ……….. x(2M-1)

x(2M) x(2M+1) x(2M+2) ……….. x(3M-1)

…….. ……… ……… ………..

x((L-1)M) x((L-1)M+1) x((L-1)M+2) ……….. x(LM-1)

Sin embargo la correspondencia

n=l+mL

Almacena los primeros L elementos de x(n) en la primera columna, los siguientes L elementos en la

segunda columna y así sucesivamente como se muestra abajo.

x(0) x(L) x(2L) ……….. x((M-1)L)

x(1) x(L+1) x(2L+1) ……….. x((M-1)L+1)

x(2) x(L+2) x(2L+2) ……….. x((M-1)L+2)

…….. ……… ……… ………..

x(L-1) x(2L-1) x(3L-1) ……….. x(LM-1)

Se puede utilizar una disposición similar para almacenar los valores calculados de la DFT, en este

caso, la correspondencia se establece entre el índice k y la pareja de índices (p,q) donde 0≤p≤L-1 y

0≤q≤M-1.

0 1 M-1

0 1 2 M-1

Indice de filas

Indice de columnas

m

l

0 1 2 M-1 0 1 2

L-1

n=Ml+m m

l

Por filas

0 1 2 M-1

0 1 2

L-1

n=l+mL

m

l

Por columnas

37

Si seleccionamos la correspondencia

k=Mp+q

la DFT se almacena por filas, donde la primera fila contiene los M primeros elementos de la DFT

X(k), la segunda fila contiene el siguiente conjunto de M elementos y asi sucesivamente. Por el

contrario la correspondencia

k= qL +p

da como resultado un almacenamiento de X(k) donde los L primeros elementos se almacenan en

la primera columna, el segundo conjunto de L elementos se almacena en la segunda columna, y así

sucesivamente.

Ahora suponemos que x(n) se hace corresponder con una matriz rectangular x(l,m) y X(k) con la

correspondiente matriz rectangular X(p,q). Luego la DFT se puede expresar como una suma doble

sobre los elementos de la matriz rectangular multiplicada por los correspondientes factores de

fase. Más específicamente, adoptamos la correspondencia por columnas para x(n) dada por

n=l+mL y la correspondencia por filas para la DFT dada por k=Mp+q. Por tanto:

!, ' U

, 'p 6' 6' U

Pero

p 6' 6' pppp Sin embargo

pp 1, p p/ , y p p/

Con estas simplificaciones la sumatoria se expresa como:

!, ' p ¡ , ' U

¢£

U

Esta expresión implica el cálculo de transformadas DFT de longitud M y L, luego subdividimos el

cálculo en tres pasos:

1.- En primer lugar, calculamos la DFT de M puntos:

¤ , ' , ' 0 W W ¥ 1U

Para cada una de las filas l=0,1,2,….., L-1

2.- En segundo lugar, calculamos una nueva matriz rectangular G(l,q) definida como:

¦ , ' p¤ , '

Con 0≤l≤L-1 y 0≤q≤M-1.

3.- Por último calculamos la DFT de L puntos.

!, ' ¦ , ' U

Para cada columna q=0, 1, 2,………….., M-1 de la matriz G(l,q)

38

En principio puede parecer que el procedimiento de cálculo anterior es más complicado que el

cálculo directo de la DFT, pero evaluemos la complejidad de cálculo de :

!, ' p ¡ , ' U

¢£U

El primer paso implica el cálculo de L transformadas DFT, cada una de ellas de M puntos. Luego

este paso requiere LM2 multiplicaciones complejas y LM(M-1) sumas complejas. El segundo paso

requiere LM multiplicaciones complejas, por último, el tercer paso requiere ML2 multiplicaciones

complejas y ML(L-1) sumas complejas. Por tanto la complejidad de cálculo es

Multiplicaciones complejas N(M+L+1)

Sumas complejas N(M+L-2)

Donde N=ML. Por tanto, el número de multiplicaciones se ha reducido de N2 a N(M+L+1) y el

número de sumas se ha reducido de N(N-1) a N(M+L-2).

Por ejemplo si N=1000 y seleccionamos L=2 y M = 500. Por tanto en lugar de tener que realizar 106

multiplicaciones complejas del cálculo directo de la DFT, este método nos lleva a 503,000

multiplicaciones complejas, lo que representa una reducción de aproximadamente 50 por ciento.

El número de sumas se reduce en la misma cantidad.

Cuando N es un número compuesto muy alto, es decir, N puede descomponerse en factores para

definir un producto de números primos de la forma

N=r1r2….rv

Entonces la descomposición anterior puede repetirse (v-1) más veces. Este procedimiento da

como resultado transformadas DFT más pequeñas, lo que, a su vez, lleva a un algoritmo de cálculo

más eficiente.

La primera segmentación de la secuencia x(n) en una matriz rectangular de M columnas con L

elementos en cada columna genera transformadas DFT de tamaños L y M. Además, la

descomposición de los datos implica la segmentación de cada fila (o columna) en matrices

rectangulares más pequeñas que darán lugar a transformadas DFT más pequeñas. Este

procedimiento termina cuando N se descompone en sus factores primos.

Ejemplo

Consideremos el cálculo de una DFT de N=15 puntos. Como N=5 x 3 =15 seleccionamos L=5 y M

=3, o sea almacenamos por columnas la secuencia x(n) de 15 puntos de esta manera:

Fila 1: x(0,0)=x(0) x(0,1)=x(5) x(0,2)=x(10)

Fila 2: x(1,0)=x(1) x(1,1)=x(6) x(1,2)=x(11)

Fila 3: x(2,0)=x(2) x(2,1)=x(7) x(2,2)=x(12)

Fila 4: x(3,0)=x(3) x(3,1)=x(8) x(3,2)=x(13)

Fila 5: x(4,0)=x(4) x(4,1)=x(9) x(4,2)=x(14)

39

Ahora comparamos la DFT de tres puntos para cada una de las cinco filas y hacemos una matriz 5 x

3

F(0,0) F(0,1) F(0,2)

F(1,0) F(1,1) F(1,2)

F(2,0) F(2,1) F(2,2)

F(3,0) F(3,1) F(3,2)

F(4,0) F(4,1) F(4,2)

El siguiente paso consiste en multiplicar cada uno de los términos F(l, q) por los factores de fase

p U§ 0≤l≤4 y 0≤q≤2. Esto da una matriz 5 x 3

Columna 1 Columna 2 Columna 3

G(0,0) G(0,1) G(0,2)

G(1,0) G(1,1) G(1,2)

G(2,0) G(2,1) G(2,2)

G(3,0) G(3,1) G(3,2)

G(4,0) G(4,1) G(4,2)

El paso final consiste en calcular la DFT de cinco puntos para cada una de las tres columnas. Este

cálculo proporciona los valores deseados de la DFT de la forma:

X(0,0)=X(0) X(0,1)=X(5) X(0,2)=X(10)

X(1,0)=X(1) X(1,1)=X(6) X(1,2)=X(11)

X(2,0)=X(2) X(2,1)=X(7) X(2,2)=X(12)

X(3,0)=X(3) X(3,1)=X(8) X(3,2)=X(13)

X(4,0)=X(4) X(4,1)=X(9) X(4,2)=X(14)

MATRIZ DE ENTRADA

X(0) x(5) x(10) x(1) x(6)x(11) x(2) x(7) x(12) x(3) x(8) x(13) x(4) x(9) x(14)

MATRIZ DE SALIDA

X(0) X(1) X(2) X(3) X(4)X(5) X(6) X(7) X(8) X(9) X(10) X(11) X(12) X(13) X(14)

La secuencia de datos se ha reestructurado respecto al orden normal en el cálculo de la DFT y la

secuencia de salida se genera en el orden normal. En este caso la reordenación de la matriz de los

datos de entrada se debe a la segmentación de la matriz unidimensional en una matriz rectangular

y al orden en que se calculan las DFT. Esta reestructuración de la secuencia de datos de entrada o

de la secuencia de los datos de salida es una característica de la mayoría de los algoritmos FFT.

En resumen el algoritmo sigue los siguientes pasos:

1) Almacenar la señal por columnas

2) Calcular la DFT de M puntos de cada fila

3) Multiplicar la matriz resultante por los factores de fase p

4) Calcular la DFT de L puntos de cada columna

5) Leer la matriz resultante por filas.

40

Puede obtenerse un algoritmo adicional con una estructura de cálculo similar si la señal de

entrada se almacena por filas y la transformación resultante se hace por columnas. En dicho caso

seleccionamos n=Ml+m y k=qL+p

Esta elección de índices nos lleva a la fórmula de la DFT del a forma

!, ' , 'pp U

U

¡ , ' U

¢£U

p

Así obtenemos el segundo algoritmo

1) Almacenar la señal por filas

2) Calcular la DFT de L puntos en cada columna

3) Multiplicar la matriz resultante por los factores p

4) Calcular la DFT de M puntos de cada fila

5) Leer la matriz resultante por columnas.