DFT:<\/p>\n\n\n\n
peri\u00f3dicas<\/a><\/p>\n\n\n\n freq negativas<\/a><\/p>\n\n\n\n simetr\u00eda conjugada<\/a><\/p>\n\n\n\n zero padding<\/a><\/p>\n\n\n\n ejemplo_cos<\/a><\/p>\n<\/div>\n\n\n\n Referencia<\/strong><\/em>: McClellan 8.2.1 p311<\/p>\n\n\n\n La DFT de una secuencia finita de N-puntos es una versi\u00f3n discreta de DTFT:<\/p>\n\n\n X[k] = \\sum_{n=0}^{N-1} x[n] e^{-j(2\\pi k\/N)}<\/span>\n\n\n = X\\Big( e^{j\\omega} \\Big) \\Big|_{\\omega=(2\\pi k\/N)}<\/span>\n\n\n = X\\Big( e^{j (2\\pi k\/N)}\\Big) <\/span>\n\n\n\n k= 0, 1, ..., N-1<\/p>\n\n\n\n Dado que DTFT X(ej\u03c9<\/sup>) es siempre peri\u00f3dica con periodo 2\u03c0, la DFT X[k] debe ser por lo tanto tambi\u00e9n peri\u00f3dica. Esto implica que el \u00edndice k se mantiene siempre entre 0 y N-1, sin afectar ser evaluado para k\u2265N o k<0.<\/p>\n\n\n\n Considere que \u03c9 + 2\u03c0 = 2\u03c0k\/N + 2\u03c0(N\/N) = 2\u03c0(k+N)\/N = \u03c9k+N<\/sub> X[k] = X[k+N]<\/p>\n\n\n\n DFT:<\/p>\n\n\n\n peri\u00f3dicas<\/a><\/p>\n\n\n\n freq negativas<\/a><\/p>\n\n\n\n simetr\u00eda conjugada<\/a><\/p>\n\n\n\n zero padding<\/a><\/p>\n\n\n\n ejemplo_cos<\/a><\/p>\n<\/div>\n\n\n\n Referencia<\/strong><\/em>: McClellan 8.2.2 p311, 8.2.3.1 p313<\/p>\n\n\n\n Todos los resultados de DFT y IDFT tienen \u00edndices no negativos por ser convenientes para los c\u00e1lculos y expresiones matem\u00e1ticas. Para la gr\u00e1fica de espectro de frecuencias se espera utilizar frecuencias positivas y negativas, con simetr\u00eda en las conjugadas cuando la se\u00f1al es tipo real.<\/p>\n\n\n\n Cuando la DFT de tama\u00f1o N, siendo N par, la transformada X[k] tiene un valor a k=N\/2. Cuando N es impar, lo indicado no aplica. El \u00edndice k=N\/Se corresponde a una frecuencia normalizada \u03c9=2\u03c0(N\/2)\/N)=\u03c0. Sin embargo los valores en el espectro son de periodos 2\u03c0, siendo \u03c9=-\u03c0 un alias de \u03c9=\u03c0.<\/p>\n\n\n\n Si se realiza la gr\u00e1fica de forma centrada, la frecuencia esta entre [-\u03c0, \u03c0]<\/p>\n\n\n\n En Python el desplazamiento de los \u00edndices se puede realizar usando DFT:<\/p>\n\n\n\n peri\u00f3dicas<\/a><\/p>\n\n\n\n freq negativas<\/a><\/p>\n\n\n\n simetr\u00eda conjugada<\/a><\/p>\n\n\n\n zero padding<\/a><\/p>\n\n\n\n ejemplo_cos<\/a><\/p>\n<\/div>\n\n\n\n Para una se\u00f1al x[n] de tipo real, existe la simetr\u00eda conjugada en la DTFT, los coeficientes deben satisfacer la propiedad:<\/p>\n\n\n\n X[-1] = X*<\/sup>[1] La DFT de una se\u00f1al real satisface:<\/p>\n\n\n\n X[N-k] = X*<\/sup>[k] DFT:<\/p>\n\n\n\n peri\u00f3dicas<\/a><\/p>\n\n\n\n freq negativas<\/a><\/p>\n\n\n\n simetr\u00eda conjugada<\/a><\/p>\n\n\n\n zero padding<\/a><\/p>\n\n\n\n ejemplo_cos<\/a><\/p>\n<\/div>\n\n\n\n Referencia<\/strong><\/em>: McClellan 8.2.4 p314<\/p>\n\n\n\n Para suavizar una gr\u00e1fica de una DTFT como respuesta de frecuencia, se necesita muestras de frecuencia con tama\u00f1os de paso peque\u00f1os. De forma impl\u00edcita, la DFT asume que la longitud o tama\u00f1o de la transformada es igual al tama\u00f1o o longitud de la se\u00f1al L, por lo que la DFT de L puntos calcula las muestras de DTFT para (\u03c9=2\u03c0\/L)k, siendo k=0,1,...,L-1. Las L muestras de frecuencia son con espacios iguales en el intervalo 0\u2264\u03c9\u22642\u03c0, con resultado:<\/p>\n\n\n H[k] = H \\Big( e^{j(2\\pi \/L)k} \\Big) = H \\Big( e^{j\\omega}\\Big) \\Big|_{\\omega=(2\\pi\/L)\/k}<\/span>\n\n\n\n k = 0, 1, ..., L-1<\/p>\n\n\n\n Para disponer de muestras de frecuencia a espacios menores que (2\u03c0\/N) donde N>L, una forma sencilla es rellenar con ceros<\/strong> o zero-padding<\/strong>. Con lo que la se\u00f1al se alarga antes de realizar el c\u00e1lculo para la DFT de N puntos.<\/p>\n\n\n h_{zp}[n] = \\begin{cases} h[n] & n=\\text {0, 1, ..., L-1} \\\\0 & n= L, L+1, ... , N-1 \\end{cases} <\/span>\n\n\n\n Referencia<\/strong><\/em>: McClellan 8.4 p315<\/p>\n\n\n\n Suponer que requiere una gr\u00e1fica de respuesta de frecuencia de un filtro FIR de 8 puntos. Para evaluar la respuesta de frecuencia con mejor resoluci\u00f3n mediante tama\u00f1os de paso mas peque\u00f1os entre frecuencias, se usar\u00e1 relleno con ceros o zero-padding, usando un n\u00famero par en N, por ejemplo N=80.<\/p>\n\n\n\n DFT:<\/p>\n\n\n\n peri\u00f3dicas<\/a><\/p>\n\n\n\n freq negativas<\/a><\/p>\n\n\n\n simetr\u00eda conjugada<\/a><\/p>\n\n\n\n zero padding<\/a><\/p>\n\n\n\n ejemplo_cos<\/a><\/p>\n<\/div>\n\n\n\n El filtro FIR se puede realizar usando un rect\u00e1ngulo con funciones escal\u00f3n o Heaviside(n), luego evaluando para las muestras ti.<\/p>\n\n\n\n Para obtener la DFT se usa El centrado del espectro de frecuencias se puede realizar usando un desplazamiento de \u00edndices El resultado del algoritmo, con X[k] centrada, se presenta como:<\/p>\n\n\n\n DFT:<\/p>\n\n\n\n peri\u00f3dicas<\/a><\/p>\n\n\n\n freq negativas<\/a><\/p>\n\n\n\n simetr\u00eda conjugada<\/a><\/p>\n\n\n\n zero padding<\/a><\/p>\n\n\n\n ejemplo_cos<\/a><\/p>\n<\/div>\n\n\n\n Referencia<\/strong><\/em>: McClellan 8.2.5 p316<\/p>\n\n\n\n Considere la se\u00f1al de entrada x[n] coseno, de frecuencia 0.2 de forma discreta para L=50 tramos en tiempo en un intervalo de dos periodos. Para la DFT considere el caso que N=L, no se requiere relleno de ceros.<\/p>\n\n\n x[n] = 5 cos(2\\pi(0.1)n]<\/span>\n\n\n\n n = 0, 1, ..., L-1<\/p>\n\n\n\n Una se\u00f1al senoidal se puede escribir como la suma de exponenciales complejos y usar la propiedad de linealidad para encontrar el resultado.<\/p>\n\n\n\n El resultado de la DFT muestra la caracter\u00edstica de simetr\u00eda donde ocurre un m\u00e1ximo (pico), en este caso en <\/p>\n\n\n\n k=k0<\/sub>=1 y k=N-k0<\/sub>=50-1=49. <\/p>\n\n\n\n Las correspondientes frecuencias en Hertz son -0.1 y 0.1. La altura de los picos son aproximadamente AL\/2 = 5(50)\/2 = 125.<\/p>\n\n\n\n Resultados num\u00e9ricos con el algoritmo:<\/p>\n\n\n\n
\n\n\n\n1. Periodicidad<\/h2>\n\n\n\n
que implica que los coeficientes X[k] tienen periodo igual a N. Por lo que no se considera necesario m\u00e1s c\u00e1lculos X[k] fuera del intervalo 0\u2264k<N.<\/p>\n\n\n\n
\n\n\n\n
\n\n\n\n2. Frecuencias Negativas y DFT<\/h2>\n\n\n\n
np.fft.fftshift()<\/code> que ubica el centro en la muestra N\/2, siempre que N sea par.<\/p>\n\n\n\n
\n\n\n\n
\n\n\n\n3. Simetr\u00eda conjugada de DFT<\/h2>\n\n\n\n
X[-2] = X*<\/sup>[2]
...
X[-k] = X*<\/sup>[k]<\/p>\n\n\n\n
k = 0, 1, ..., N-1<\/p>\n\n\n\n
\n\n\n\n
\n\n\n\n4. Relleno de ceros - Zero Padding<\/h2>\n\n\n\n
4.1 Ejemplo: Respuesta de frecuencias con DFT con zero-padding<\/h2>\n\n\n\n
![\"fft](\"http:\/\/blog.espol.edu.ec\/algoritmos101\/files\/2024\/12\/fft_rect_zeropaddingL16N80.png\")
<\/a><\/figure>\n\n\n\n
En el caso que N=40, el resultado tiene menor resoluci\u00f3n considerando que el intervalo \u03c9 se mantiene entre [-\u03c0, \u03c0]<\/p>\n\n\n\n![\"fft](\"http:\/\/blog.espol.edu.ec\/algoritmos101\/files\/2024\/12\/fft_rect_zeropaddingL16N40.png\")
<\/figure>\n\n\n\n
\n\n\n\n
\n\n\n\n4.2 Algoritmo en Python<\/h3>\n\n\n\n
np.fft.fft(xn, n=N)<\/code>, si n es menor que el tama\u00f1o de la se\u00f1al de entrada, la entrada se trunca. Si es mas grande, se usa zero-padding para completar las muestras. Por lo que la instrucci\u00f3n de Numpy contempla el uso de zero-padding, lo que simplifica el uso del algoritmo presentado de forma did\u00e1ctica paso a paso.<\/p>\n\n\n\nki_shift<\/code>.<\/p>\n\n\n\nk0: 0 ; i: 40\nfreq_Hz: 0.0 ; Xk[k0]: (8+0j)\n[ i, freq[ki],|X[k]| ,X[k]]\n[0, 0.0, 8.0, (8+0j)]\n[1, 0.0125, 7.871076020105053, (7.575558332074842-2.1365284158195137j)]\n[2, 0.025, 7.491613901992368, (6.387650908672175-3.914357511197061j)]\n[3, 0.037500000000000006, 6.883060301425795, (4.672226464156024-5.054386113140136j)]\n...<\/code><\/pre>\n\n\n\nInstrucciones en Python<\/h3>\n\n\n
\n# ejemplo 8.4 p315 DFT zero-padding\n# telg1034 DSP fiec-espol edelros@espol.edu.ec\nimport numpy as np\nimport matplotlib.pyplot as plt\n\n# INGRESO\nL = 16 # Tramos en un periodo\n\n# se\u00f1al es rectangular peri\u00f3dico rect[n]\nf0 = 1\/16 # frecuencia fundamental de se\u00f1al\nancho = 0.5*(1\/f0) # ancho del impulso rectangular\nxt = lambda t: np.heaviside(t,1)-np.heaviside(t-ancho,1)\n\n# para DFT\nN = 80 #2*L # N par mayor que L, tramos DFT\n\n# PROCEDIMIENTO\n# muestreo de se\u00f1al x[n]\nt0 = 0 ; tn = 1*(1\/f0) # intervalo [t0,tn]\ndt = (tn-t0)\/L\nti = np.arange(t0,tn,dt)\nxn = xt(ti)\n\n# verificar que L<=N\nif L<=N:\n # DFT transformada rapida de Fourier\n Xk = np.fft.fft(xn,n=N)\n Xkmagn = np.abs(Xk) # para gr\u00e1fica\n Xkfase = np.angle(Xk)\n freq_Hz = np.fft.fftfreq(N,dt) # frecuencias en Hz\n\n mitad = int(N\/2)\n k0 = np.argmax(Xk) # Pico |X[k]|\n\n # ki indices de orden\n ki = np.arange(0,N,1)\n ki_shift = np.copy(ki)\n ki_shift[mitad:] = ki[mitad:]-N\n\n# SALIDA\nif N>=L:\n print('k0:',k0,'; i:',mitad+k0)\n print('freq_Hz:',freq_Hz[k0],\n '; Xk[k0]:',Xk[k0])\n print('[ i, freq[ki],|X[k]| ,X[k]]')\n kmin = k0-4 ; kmax = k0+4\n if kmin<0:\n kmin = 0\n if kmax>N:\n kmax = N\n for i in range(kmin,kmax,1):\n print([i,freq_Hz[i],Xkmagn[i],Xk[i]])\nelse:\n print('Revisar: L debe ser menor o igual a N')\n print('L:',L,'; N:',N)\n\n# GRAFICA\nif N>=L:\n LN_texto= ', L='+str(L)+', N='+str(N)\n zp_texto = 'zero padding:'+str(N-L)\n plt.subplot(311)\n plt.stem(ki[0:len(xn)],np.real(xn),label='x[n]',\n markerfmt ='C2.',linefmt='C2-')\n if N>L:\n kj = np.arange(L,N,dt)\n zp = np.zeros(N-L)\n plt.stem(kj,zp,label = 'zero padding',\n markerfmt ='C3.')\n plt.xlabel('ki')\n \n plt.title('x[n] vs |x[k]|'+LN_texto+', '+zp_texto)\n plt.legend()\n\n plt.subplot(312)\n plt.stem(ki[0:mitad], Xkmagn[0:mitad],\n label='X[k], k_=[0:N\/2]',\n markerfmt ='C0.', linefmt='C0-')\n plt.stem(ki[mitad:], Xkmagn[mitad:],\n label='X[k], k_=[N\/2:]',\n markerfmt ='C1.',linefmt='C1-')\n plt.stem(N,0,markerfmt ='C3.')\n plt.xlabel('ki_')\n plt.legend()\n\n plt.subplot(313)\n plt.stem(ki_shift[0:mitad], Xkmagn[0:mitad],\n label='H[k] centrada]',\n markerfmt ='C0.',linefmt='C0-')\n plt.stem(ki_shift[mitad:], Xkmagn[mitad:],\n markerfmt ='C1.',linefmt='C1-')\n plt.stem(mitad,0,markerfmt ='C3.')\n plt.xlabel('ki')\n plt.legend()\n plt.legend()\n plt.tight_layout()\n plt.show()\n<\/pre><\/div>\n\n\n
\n\n\n\n
\n\n\n\n5. DFT de una se\u00f1al Real tipo Coseno<\/h2>\n\n\n\n
![\"fft](\"http:\/\/blog.espol.edu.ec\/algoritmos101\/files\/2024\/12\/fft_seno_L50N50.png\")
<\/a><\/figure>\n\n\n\nk0: 1 ; i: 26\nfreq_Hz: 0.1<\/strong> ; Xk[k0]: (125+1.509903313490213e-14j)\n[ i, freq[ki],|X[k]| ,X[k]]\n[0, 0.0, 9.492406860545088e-15, (9.492406860545088e-15+0j)]\n[1, 0.1, 125.0, (125+1.509903313490213e-14j)]<\/strong>\n[2, 0.2, 4.842919552269065e-15, (-4.774353709997803e-15-8.120446056592065e-16j)]\n[3, 0.30000000000000004, 3.4364294309926203e-15, (2.3207649852950894e-15-2.5343829855056534e-15j)]\n[4, 0.4, 2.032850942959038e-15, (8.108973628378316e-16+1.8641159897474457e-15j)]<\/code><\/pre>\n\n\n\n
![\"fft](\"http:\/\/blog.espol.edu.ec\/algoritmos101\/files\/2024\/12\/fft_seno_L50N400.png\")
<\/a><\/figure>\n\n\n\n