% Activate the following line by filling in the right side. If for example the name of the root file is Main.tex, write
% "...root = Main.tex" if the chapter file is in the same directory, and "...root = ../Main.tex" if the chapter is in a subdirectory.
 
%!TEX root = ../vision.tex

\chapter{Transformada de Fourier}

\section{Representación de señales periódicas.}

Recordemos que la exponencial compleja $e^{j(2\pi /N)n}$ es periódica con periodo $N$. A partir de esta podemos crear una  familia de exponenciales complejas también con periodo $N/k$ dadas por

\[
\phi _{k}\left( n\right) =e^{jk(2\pi /N)n} 
\]
\begin{equation}
\phi _{k}\left( n\right) =cos (\frac{2 \pi k}{N} n) + j seno (\frac{2 \pi k}{N} n) \label{eq:ExpC}
\end{equation}
donde $k$ es un número entero que representa una frecuencia fundamental.
Todas estas exponenciales complejas tienen frecuencias que son múltiplos de las misma frecuencia fundamental $2\pi /N$. Así cuando $k=0$ llamaremos a este el componente de CD de la señal (constante), cuando $k=1$ como armónico de frecuencia  $2 \pi k/N$ fundamental, con $k=2$ tenemos $4 \pi k/N$ segundo armónico y así sucesivamente para todos los valores $k$. 

Con esto queremos llegar a hacer la representación de una señal periódica como la combinación lineal de exponenciales complejas, dadas como (\ref{eq:ITF})

\begin{eqnarray}
x[n] =\frac{1}{N}\sum_{k=0}^{N-1}X[k]\phi _{k}\left( n\right)  \nonumber \\
x[n] =\frac{1}{N} \sum_{k=0}^{N-1}X[k]e^{jk(2\pi /N)n} \label{eq:ITF}
\end{eqnarray}

donde la ecuación (\ref{eq:ITF}) es conocida como la Transformada  Discreta  Inversa de Fourier (TDIF) de $x[n]$  y cuyos coeficientes son $X[k]$ .

Para determinar los coeficientes $X$ de la TDIF procedemos
\begin{eqnarray*}
x[0] =\frac{1}{N} \left (X[0] \phi _{0}(0) + X[1]\phi _{1}(0) +X[2] \phi _{2}(0) +...+X[N-1]\phi_{N-1}(0) \right )\\
x[1] =\frac{1}{N} \left (X[0] \phi _{0}(1) + X[1]\phi _{1}(1) +X[2] \phi _{2}(1) +...+X[N-1]\phi _{N-1}(1) \right )\\
x[2] =\frac{1}{N} \left (X[0] \phi _{0}(2) + X[1]\phi _{1}(2) +X[2] \phi _{2}(2) +...+X[N-1]\phi _{N-1}(2) \right ) \\
\vdots \\
x[N-1] =\frac{1}{N} \left (X[0]\phi _{0}( N-1) + X[1]\phi _{1}(N-1) +...+ X[N-1]\phi _{N-1}(N-1) \right)
\end{eqnarray*}

En forma matricial
\[
\frac{1}{N}
\left[
\begin{array}{cccc}
\phi _{0}\left( 0\right) & \phi _{1}\left( 0\right) & \ldots & \phi_{N-1}\left( 0\right) \\
\phi _{0}\left( 1\right) & \phi _{1}\left( 1\right) & \ldots & \phi_{N-1}\left( 1\right) \\
\vdots & \vdots & \ddots & \vdots \\
\phi _{0}\left( N-1\right) & \phi _{1}\left( N-1\right) & \ldots & \phi_{N-1}\left( N-1\right)
\end{array}
\right] \left[
\begin{array}{c}
X[0] \\
X[1] \\
\vdots \\
X[N-1]
\end{array}
\right] =\left[
\begin{array}{c}
x[0] \\
x[1] \\
\vdots \\
x[N-1]
\end{array}
\right]
\]

donde $\phi_k[n]$ se calcula utilizando (\ref{eq:ExpC}),  podemos representar en forma compacta esta ecuación como :
\begin{equation}
\frac{1}{N}\Phi X = x \label{eq:S_TDIF}
\end{equation}

Para el sistema de ecuaciones ponemos calcular la Transformada Discreta de Fourier $X$ resolviendo \ref{eq:S_TDIF}

\begin{equation*}
X = N \Phi^{-1} x
\end{equation*}

\section{Cálculo de la Transformada Discreta de Fourier}

Si bien, la Transformada Discreta de Fourier (TDF) se puede resolver a partir de un sistema de ecuaciones (\ref{eq:S_TDIF})  como $X = \Phi ^{-1} x$ no es del todo correcto, además de requerir la inversa de un sistema de ecuaciones. 

Una alternativa es multiplicar, ambos lados de la ecuación (\ref{eq:ITF}), por $e^{-jr(2\pi /N)n}$\ 
\[
x[n] e^{-jr(2\pi /N)n}=\frac{1}{N} \sum_{k=0}^{N-1}X[k]e^{jk(2\pi /N)n}e^{-jr(2\pi /N)n}
\]
y sumar para todos los $N$ términos de la serie

\begin{eqnarray*}
\sum_{n=0}^{N-1}x[n] e^{-jr(2\pi /N)n}=\frac{1}{N} \sum_{n=0}^{N-1}\sum_{k=0}^{N-1}X[k]e^{jk(2\pi /N)n}e^{-jr(2\pi /N)n}
\\
\sum_{n=0}^{N-1}x[n] e^{-jr(2\pi/N)n}=\frac{1}{N}\sum_{k=0}^{N-1}X[k]\sum_{n=0}^{N-1}e^{j\left( k-r\right) (2\pi /N)n} \\
\sum_{n=0}^{N-1}x[n] e^{-jr(2\pi/N)n}=\frac{1}{N}\sum_{k=0}^{N-1}X[k]s_N
\end{eqnarray*}


Para la resolver $s_N$ de la ecuación anterior
\[
s_N = \sum_{n=0}^{N-1}e^{j\left( k-r\right) (2\pi /N)n} = \sum_{n=0}^{N-1} a^n
\]
con $a =e^{j\left( k-r\right) (2\pi /N)} $

La solución de $s_N$ en el caso de ($k = r$) es:
\[
s_N = \sum_{n=0}^{N-1}e^{j\left( 0\right) (2\pi /N)n} =  \sum_{n=0}^{N-1} 1 = N
\]
y en caso de que ($k\neq$) haremos uso de la sucesión dada por (\ref{eq:sum_util})

\begin{equation}
s_N = \sum_{n=0}^{N-1}  a^{n} = \frac{1-a^N}{1-a} \label{eq:sum_util}
\end{equation}

\[
s_N = \frac{1- e^{j\left( k-r\right) (2\pi /N)N}}{1- e^{j\left( k-r\right) (2\pi /N)}} 
= \frac{1- e^{j\left( k-r\right) (2\pi)}}{1- e^{j\left( k-r\right) (2\pi /N)}} 
= \frac{1 -1}{1- e^{j\left(k-r\right) (2\pi /N)}} = 0
\]

Por tanto si escogemos valores de $r$ igual que $k$, tendremos que esta suma es igual a $N$ y cero de lo contrario, por lo que tenemos

\begin{eqnarray*}
X[r]=\sum_{n=0}^{N-1}x[n] e^{-jr(2\pi /N)n} \\
X[k]=\sum_{n=0}^{N-1}x[n] e^{-jk(2\pi /N)n} \\
X[k]=\sum_{n=0}^{N-1}x[n] \phi _{r}^{*}\left( n\right)
\end{eqnarray*}

En lo general representaremos la transformada Discreta de Fourier como (\ref{eq:TF})
\begin{equation}
X[k] =\sum_{n=0}^{N-1}x[n] e^{-jk(2\pi /N)n} \label{eq:TF}
\end{equation}

En forma matricial lo podemos expresar (\ref{eq:TF}) como

\[
\left[
\begin{array}{c}
X[0] \\
X[1] \\
\vdots \\
X[N-1]
\end{array}
\right] =
\left[
\begin{array}{cccc}
\phi _{0}^*\left( 0\right) & \phi _{1}^*\left( 0\right) & \ldots & \phi_{N-1}^*\left( 0\right) \\
\phi _{0}^*\left( 1\right) & \phi _{1}^*\left( 1\right) & \ldots & \phi_{N-1}^*\left( 1\right) \\
\vdots & \vdots & \ddots & \vdots \\
\phi _{0}^*\left( N-1\right) & \phi _{1}^*\left( N-1\right) & \ldots & \phi_{N-1}^*\left( N-1\right)
\end{array}
\right] \left[
\begin{array}{c}
x[0] \\
x[1] \\
\vdots \\
x[N-1]
\end{array}
\right]
\]

\[
X = \Phi^* x
\]

donde $\phi_k^*(n)$ es el valor conjugado de  $\phi_k(n)$ y  se calcula utilizando (\ref{eq:ExpC}) cambiando el signo de la parte imaginaria.

\subsection{Implementación de la Transformada de Fourier}

A partir de las ecuaciones de la TDF (\ref{eq:TF}) y de la TDIF (\ref{eq:ITF}), es necesario construir una matriz $\Phi^*$ y $\Phi$ respectivamente. Matricialmente  la TDF se  calcula con $X = \Phi^* x$ y TDIF como $x = \frac{1}{N}\Phi X$. Note que la diferencia es un signo en la parte imaginaria de las exponenciales complejas y la división entre $N$. La implementación genérica de la TDF y TDIF se muestra en el siguiente código denominado DFT\_1D:

\begin{verbatim}
  void funciones::DFT_1D(float *entrada_r, float *entrada_i, 
          float * salida_r, float * salida_i, int signo, int N){
      
      int n, k;
      float **Ar, **Ai
      Ar = funciones::Matriz(N,N);
      Ai = funciones::Matriz(N,N);
      float w = 2.0*(3.1415926)/(float) N, suma_r, suma_i;
      
      float factor;
      
      factor = signo == 1 ? 1.0/(double) N : 1.0 ;
      
      for(n=0; n<N; n++){
          for(k=n; k<N; k++) {
              Ar[n][k] = cos(w*n*k);
              Ar[k][n] = Ar[n][k];
              Ai[n][k] = signo*sin(w*n*k);
              Ai[k][n] = Ai[n][k];            
          }
      }     
            
      for(k=0; k<N; k++) {
          suma_r = 0;
          suma_i = 0;
          
          for(n=0; n<N; n++){
              suma_r += (Ar[k][n]*entrada_r[n] - Ai[k][n]*entrada_i[n]);
              suma_i += (Ar[k][n]*entrada_i[n] + Ai[k][n]*entrada_r[n]);
          } 
          
          salida_r[k] = suma_r*factor;
          salida_i[k] = suma_i*factor;
      }
  }
\end{verbatim}

Para evitar confusiones, de manera particular, para el calculo de la TDF utilizaremos la función

\begin{verbatim}
  void funciones::Fourier(float *entrada_r, float *entrada, 
          float *salida_r, float * salida_i, int N){
       DFT_1D(entrada_r, entrada_i, salida_r, salida_i, -1, N);
  } 
 \end{verbatim}
 
y para la TDIF utilizamos

\begin{verbatim}
   void funciones::Inversa_Fourier(float *entrada_r, float * entrada_i, 
          float * salida_r, float * salida_i, int N){
       DFT_1D(entrada_r, entrada_i, salida_r, salida_i, 1, N);
  } 
\end{verbatim}

Se puede comprobar los resultados de estas funciones en Mathematica haciendo Fourier[x, FourierParameters$ \rightarrow \{1,-1\}$] y InverseFourier[X, FourierParameters$ \rightarrow \{1,-1\}$].

\subsection{Ejemplo}

Determinar la TDF $X$ para una señal $x = [1,4,1,1]^T$

De acuerdo con la ecuación (\ref{eq:TF}), tenemos que calcular la TDF $X$, haciendo simplemente la multiplicación:
\[
\left[
\begin{array}{c}
 X[0]  \\
 X[1]\\
 X[2]\\
 X[3]  
\end{array}
\right]
=
\left[
\begin{array}{cccc}
 1 &  1 & 1 & 1  \\
 1 &  -j & -1&  j\\
 1 &  -1 & 1 & -1 \\
 1 & j & -1 & -j  
\end{array}
\right]
\left[
\begin{array}{c}
 1  \\
 4\\
 1 \\
 1  
\end{array}
\right]
=
\left[
\begin{array}{r}
7 \\
-j 3\\
- 3 \\
 j 3  
\end{array}
\right]
\]

Si nuestra formulación es consistente la transformada Inversa de Fourier de $X$, nos debe dar el vector original $x$

\[
\left[
\begin{array}{c}
 x[0]  \\
 x[1]\\
 x[2] \\
 x[3]  
\end{array}
\right] =
\frac{1}{4}
\left[
\begin{array}{cccc}
 1 &  1 & 1 & 1  \\
 1 &  j & -1&  -j\\
 1 &  -1 & 1 & -1 \\
 1 & -j & -1 & j  
\end{array}
\right]
\left[
\begin{array}{r}
7 \\
-j 3\\
- 3 \\
 j 3  
\end{array}
\right]
=
\left[
\begin{array}{c}
 1  \\
 4\\
 1 \\
 1  
\end{array}
\right]
\]

\subsection{Ejemplo}

Encontrar los coeficientes de la TDF para la señal mostrada en la Fig. \ref{fig:orig}, cuyos elementos son $x=[1,1,1,0,0,0,0,1,1]^{T}$.

\begin{figure}[h!]
{\normalsize \centering
\centerline{\psfig{figure = TFourier/figuras/orig.eps,width=6.0cm}} }
\caption{Señal a descomponer en Fourier}
\label{fig:orig}
\end{figure}

Para encontrar los coeficientes de Fourier de la señal $x$, es necesario calcular :

\[
X = \Phi^* x 
\]

\noindent donde $\Phi $ es la matriz de exponenciales complejas (\ref{eq:ExpC}) y $N$ es la cantidad de muestras de la señal, en este caso es 9. Así la matriz es:

\[
\Phi^* =  \left(
\begin{array}{ccccccccc}
\phi _{0}(0) & \phi _{1}(0) & \phi _{2}(0) & \phi _{3}(0) & \phi _{4}(0) &
\phi _{5}(0) & \phi _{6}(0) & \phi _{7}(0) & \phi _{8}(0) \\
\phi _{0}(1) & \phi _{1}(1) & \phi _{2}(1) & \phi _{3}(1) & \phi _{4}(1) &
\phi _{5}(1) & \phi _{6}(1) & \phi _{7}(1) & \phi _{8}(1) \\
\phi _{0}(2) & \phi _{1}(2) & \phi _{2}(2) & \phi _{3}(2) & \phi _{4}(2) &
\phi _{5}(2) & \phi _{6}(2) & \phi _{7}(2) & \phi _{8}(2) \\
\phi _{0}(3) & \phi _{1}(3) & \phi _{2}(3) & \phi _{3}(3) & \phi _{4}(3) &
\phi _{5}(3) & \phi _{6}(3) & \phi _{7}(3) & \phi _{8}(3) \\
\phi _{0}(4) & \phi _{1}(4) & \phi _{2}(4) & \phi _{3}(4) & \phi _{4}(4) &
\phi _{5}(4) & \phi _{6}(4) & \phi _{7}(4) & \phi _{8}(4) \\
\phi _{0}(5) & \phi _{1}(5) & \phi _{2}(5) & \phi _{3}(5) & \phi _{4}(5) &
\phi _{5}(5) & \phi _{6}(5) & \phi _{7}(5) & \phi _{8}(5) \\
\phi _{0}(6) & \phi _{1}(6) & \phi _{2}(6) & \phi _{3}(6) & \phi _{4}(6) &
\phi _{5}(6) & \phi _{6}(6) & \phi _{7}(6) & \phi _{8}(6) \\
\phi _{0}(7) & \phi _{1}(7) & \phi _{2}(7) & \phi _{3}(7) & \phi _{4}(7) &
\phi _{5}(7) & \phi _{6}(7) & \phi _{7}(7) & \phi _{8}(7) \\
\phi _{0}(8) & \phi _{1}(8) & \phi _{2}(8) & \phi _{3}(8) & \phi _{4}(8) &
\phi _{5}(8) & \phi _{6}(8) & \phi _{7}(8) & \phi _{8}(8)
\end{array}
\right)
\]
La parte real de $\Phi^*$ es
\[
\Phi_r^* =  \left(
\begin{array}{rrrrrrrrr}
1.000 & 1.000 & 1.000 & 1.000 & 1.000 &1.000 & 1.000 & 1.000  & 1.000 \\
1.000 & 0.766 & 0.174 & -0.500 & -0.940 & -0.940 & -0.500 & 0.174 & 0.766\\
1.000 & 0.174 & -0.940 & -0.500 & 0.766 & 0.766 & -0.500 & -0.940 & 0.174 \\
1.000 & -0.500 & -0.500 & 1.000 & -0.500 & -0.500 & 1.000 & -0.500 & -0.500 \\
1.000 & -0.940 & 0.766 & -0.500 & 0.174 & 0.174 & -0.500 & 0.766 & -0.940 \\
1.000 & -0.940 & 0.766 & -0.500 & 0.174 & 0.174 & -0.500 & 0.766 & -0.940\\
1.000 & -0.500 & -0.500 & 1.000 & -0.500 & -0.500 & 1.000 & -0.500 & -0.500\\
1.000 & 0.174 & -0.940 & -0.500 & 0.766 & 0.766 & -0.500 & -0.940 & 0.174\\
1.000 & 0.766 & 0.174 & -0.500 & -0.940 & -0.940 & -0.500 & 0.174 & 0.766
 \end{array}
\right)
\]
y la parte imaginaria de $\Phi^*$ es
\[
\Phi_i^* =  \left(
\begin{array}{rrrrrrrrr}
0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 & 0.000 \\
0.000 & -0.643 & -0.985 & -0.866 & -0.342 & 0.342 & 0.866 & 0.985 & 0.643 \\
0.000 & -0.985 & -0.342 & 0.866 & 0.643 & -0.643 & -0.866 & 0.342 & 0.985 \\
0.000 & -0.866 & 0.866 & 0.000 & -0.866 & 0.866 & 0.000 &  -0.866 & 0.866 \\
0.000 & -0.342 & 0.643 & -0.866 & 0.985 & -0.985 & 0.866 & -0.643 & 0.342\\
0.000 &  0.342 & -0.643 & 0.866 & -0.985 & 0.985 & -0.866 & 0.643 & -0.342 \\
0.000 & 0.866 & -0.866 & 0.000 &  0.866 & -0.866 & 0.000 & 0.866 & -0.866 \\
0.000 & 0.985 & 0.342 & -0.866 & -0.643 & 0.643 & 0.866 & -0.342 &-0.985\\
0.000 & 0.643 & 0.985 & 0.866 & 0.342 & -0.342 & -0.866 & -0.985 & -0.643
\end{array}
\right)
\]

La solución del producto  $(\Phi_r^*  + j \Phi_i^*) x$ es:

\[
X=\left(
\begin{array}{r}
5.0000\\ 
2.87939\\
-0.5321 \\
-1.0000 \\
0.6527 \\ 
0.6527 \\ 
-1.0000\\ 
-0.5321\\
2.8794
\end{array}
\right)
\]

Note que $X$ no contiene elementos imaginario. 

A continuación se va a reconstruir la señal original usando los coeficientes de Fourier obtenidos calculando,

\[
y =\Phi X
\]

Para poder observar la importancia de cada uno de los coeficientes encontrados, primero se va a reconstruir la señal usando un solo coeficiente de manera que $X=[X[0],0,0,0,0,0,0,0,0]^{T}$, después se van a usar dos coeficientes, de modo que $X=[X[0],X[1],0,0,0,0,0,0,0]^{T}$, y así sucesivamente hasta utilizar los 9 coeficientes. Los resultados de este ejercicio se muestran en las Figs. \ref{fig:graf0}-\ref{fig:graf8}.

\begin{figure}[h!]
\begin{center}
{\normalsize \subfigure[\label{fig:graf0}]{
\psfig{figure = TFourier/figuras/graf0.eps,width=3.5cm}} \hfill \subfigure[\label{fig:graf1}]{
\psfig{figure = TFourier/figuras/graf1.eps,width=3.5cm}} \hfill \subfigure[\label{fig:graf2}]{
\psfig{figure = TFourier/figuras/graf2.eps,width=3.5cm}} }
\par
{\normalsize \subfigure[\label{fig:graf3}]{
\psfig{figure = TFourier/figuras/graf3.eps,width=3.5cm}} \hfill \subfigure[\label{fig:graf4}]{
\psfig{figure = TFourier/figuras/graf4.eps,width=3.5cm}} \hfill \subfigure[\label{fig:graf5}]{
\psfig{figure = TFourier/figuras/graf5.eps,width=3.5cm}} }
\par
{\normalsize \subfigure[\label{fig:graf6}]{
\psfig{figure = TFourier/figuras/graf6.eps,width=3.5cm}} \hfill \subfigure[\label{fig:graf7}]{
\psfig{figure = TFourier/figuras/graf7.eps,width=3.5cm}} \hfill \subfigure[\label{fig:graf8}]{
\psfig{figure = TFourier/figuras/graf8.eps,width=3.5cm}}\label{fig:graf} }
\end{center}
\caption{Reconstrucción de la señal usando los coeficientes de Fourier}
\end{figure}

\section{Transformada Rapida de Fourier}

La trasformada Discreta de Fourier TDF es $O(N^{2})$ y existe la Transformada Rápida de Fourier FFT la cual es $O(N\log N)$, para una señal en una sola dimensión. Para el caso de señales en dos dimensiones, la TDF es $O(\left( NM\right) ^{2})$ y la FFT es $O(NM\log NM)$, razón por la cual se utiliza la FFT. Sin embargo, la FFT requiere que el tamaño de la señales sea potencia de 2, es decir $N=2^{r}$ y $M=2^{s}.$ Todas la propiedades de la transformada de Fourier son validas para el caso multidimensional y para hacer la demostración solo hay que tener en cuenta que se trata de arreglos bidimensionales.

Danielson y Lanczos mostraron que la transformada Discreta de Fourier para una señal $x$ de longitud $N$, puede ser descrita como la suma de dos transformadas Discretas de Fourier, cada uno de tamaño $N/2$. Esto lo podemos mostrar a partir de la definición de la TDF (\ref{eq:TF}), podemos reagrupar la suma en los componentes $N/2$ pares e impares como 

\[
X[k] = \sum_{n=0}^{N-1}x[n]e^{-j(\frac{2 \pi k}{N}) n} = \sum_{n=0}^{N/2-1}x[2n]e^{-j(\frac{2 \pi k}{N}) 2n} + \sum_{n=0}^{N/2-1}x[2n+1]e^{-j(\frac{2 \pi k}{N}) (2n+1)}
\]

Agrupando términos tenemos 
\[
X[k] = \sum_{n=0}^{N/2-1}x[2n]e^{-j(\frac{2 \pi k}{N}) 2n} +e^{-j(\frac{2 \pi k}{N})}\sum_{n=0}^{N/2-1}x[2n+1]e^{-j(\frac{2 \pi k}{N}) (2n)}
\]
\[
X[k] = \sum_{n=0}^{N/2-1}x[2n]e^{-j(\frac{2 \pi k}{N/2}) n} +W[N] \sum_{n=0}^{N/2-1}x[2n+1]e^{-j(\frac{2 \pi k}{N/2}) n}
\]

El paso recursivo de la Transformada Rapida de Fourier es
\[
TDF(x) = TDF(x_p) + W(N) \times TDF(x_i)
\]

y el caso Base será cuando la señal sea de tamaño $N=1$ 
\[
X[0] = x[0]
\]
 
donde $x_p$  y $x_i$ son vectores de tamaño $N/2$ con los coeficientes pares e impares de $x$ y $W(N) = e^{-j(\frac{2 \pi k}{N})}$.

\subsection{Ejemplo}

Calcular la Transformada Rapida de Fourier de la señal $x=[3,2,1,5,9,4,7,6]^T$

\begin{eqnarray*}
TDF(3,2,1,5,9,4,7,6) & = & TDF(3,1,9,7) + W(8) TDF(2,5,4,6)\\
						\\
                                 & = & TDF(3,9) + W(4)  TDF(1,7) \\
                                 & & +  W(8) ( TDF(2,4) + W(4) TDF(5,6)) ) \\
                                 \\
                                 & = & TDF(3) + W(2) TDF(9) \\
                                 & & +  W(4) (TDF(1) + W(2) TDF(7)) \\
                                 & & +  W(8) (TDF(2) + W(2) TDF(4))\\
                                 & & + W(8) W(4) (TDF(5) + W(2) TDF(6)) 
\end{eqnarray*}

Sustituyendo valores tenemos

\begin{eqnarray*}
X[k] = 3 + 9 \times e^{-j(2 \pi k /2)} + 1 \times e^{-j(2 \pi k /4)} + 7 \times e^{-j(3 \pi k /2)}  \\
 + 2 \times  e^{-j(2 \pi k /8)}  + 4 \times  e^{-j(10 \pi k /8)}  + 5 \times  e^{-j(6 \pi k /8)} + 6 \times  e^{-j(14 \pi k /8)}  \\
X[k] = [37.0000, -6.70711 + j 8.1213, 4.0000 + j 5, -5.2929 - j 3.8787,\\
 3.0000, -5.29289 + j 3.8787, 4.0000 - j5.0000, -6.7071 - j8.1213]^T
\end{eqnarray*}

\subsection{Complejidad}

Consideremos que el número de elementos es potencia de $2$, así por ejemplo $N=32 =2^5$. Definimos $C_1$ el tiempo para calcular la TDF de una señal con un elemento y $C_2$ el tiempo para sumar la TDF de los elementos pares e impares. Así el tiempo para calcular la TDF de una señal con  $N$ elementos lo resolvemos con la recurrencia 

\[
T(N)=2T(N/2)+N C_2
\]

lo cual significa que el tiempo calcular la TDF de $N$ datos será equivalente al tiempo de la TDF de dos señales la mitad del tamaño más el tiempo de sumar los $N$ elementos

Por ejemplo en el caso de tener  $N =32$ elementos los tiempo los calculamos  de la manera siguiente:


\[
\begin{array}{ccc}
Llamado	& Regresa\\
T(32) = 2T(16) + 32 C_2	& T(32) = 32 C_1 + 160 C_2 \\
T(16)=2T(8)+16 C_2 	& T(16) =16  C_1 + 64 C_2 \\
T(8)=2T(4)+8 C_2	& T(8)=8 C_1 + 24 C_2 \\
T(4)=2T(2)+4 C_2	& T(4)=4 C_1 + 8 C_2 \\
T(2)=2T(1)+2 C_2	 & T(2)=2 C_1 +2 C_2 \\
T(1) = C_1   &C_1
\end{array}
\]


De la solución podemos generalizar
\[
T(N)= N C_1 + k N C_2
\]

donde $k = log_2(N)$

De acuerdo con esto la complejidad es 
\[
T(N)= N C_1 +  N log_2(N) C_2 = O(N log (N))
\]

\subsection{Implementación}

Para su implementación se tomo el código del libro Numerical Recipes in C correspondiente a la función four1. Para facilitar su uso se escribió la función fft1 la cual se encarga de ordenar los vectores p y q correspondientes a las partes real e imaginaria. 

\begin{verbatim}
/**
 * Funcion Auxiliar para calcular la Transformada Rapida de Fourier
 * @param p Señal de entrada
 * @param q Señal de salida
 * @param npts Numero de elementos
 * @param Direccion -1 Transformada de Fourier
 *                   1 Transformada Inversa de Fourier
 */

void funciones::fft1(float *p, float *q, int npts, int Direccion) {
    float *fh = Vector(2 * (npts + 1));
    float fact = 1.0;
    int j;
    if (Direccion == 1)
        fact = 1.0 / (float) (npts);

    for (j = 0; j < 2 * npts; j += 2) {
        fh[j + 1] = p[j / 2];
        fh[j + 2] = q[j / 2];
    }

    four1(fh, npts, Direccion);

    for (j = 0; j < 2 * npts; j += 2) {
        p[j / 2] = fact * fh[j + 1];
        q[j / 2] = fact * fh[j + 2];
    }
}

/**
 * Transformada Rapida de Fourier en 1 dimension
 * @param data datos de entrada
 * @param nn tamaño de la muestra
 * @param isign -1 Transformada Rapida de Fourier
 *               1 Transformada Inversa de Fourier
 */

void funciones::four1(float *data, int nn, int isign) {
    int n, mmax, m, j, istep, i;
    float wtemp, wr, wpr, wpi, wi, theta;
    float tempr, tempi, tt;

    n = nn << 1;
    j = 1;
    for (i = 1; i < n; i += 2) {
        if (j > i) {
            tt = data[j];
            data[j] = data[i];
            data[i] = tt;
            tt = data[j + 1];
            data[j + 1] = data[i + 1];
            data[i + 1] = tt;
        }
        m = n >> 1;
        while (m >= 2 && j > m) {
            j -= m;
            m >>= 1;
        }
        j += m;
    }
    mmax = 2;
    while (n > mmax) {
        istep = 2 * mmax;
        theta = 6.28318530717959 / (isign * mmax);
        wtemp = sin(0.5 * theta);
        wpr = -2.0 * wtemp * wtemp;
        wpi = sin(theta);
        wr = 1.0;
        wi = 0.0;
        for (m = 1; m < mmax; m += 2) {
            for (i = m; i <= n; i += istep) {
                j = i + mmax;
                tempr = wr * data[j] - wi * data[j + 1];
                tempi = wr * data[j + 1] + wi * data[j];
                data[j] = data[i] - tempr;
                data[j + 1] = data[i + 1] - tempi;
                data[i] += tempr;
                data[i + 1] += tempi;
            }
            wr = (wtemp = wr) * wpr - wi * wpi + wr;
            wi = wi * wpr + wtemp * wpi + wi;
        }
        mmax = istep;
    }
}
\end{verbatim}

\section{Transformada de Fourier de algunas funciones interesantes}

\subsection{Exponencial Compleja}

Dado $x[n]=e^{j\left( \frac{2\pi }{N}\right) k_{0}n}$ la transformada de Fourier esta dada como
\begin{eqnarray*}
X[k] = \sum_{n=0}^{N-1}x[n]e^{-j\left( \frac{2\pi }{N}\right) kn} \\
X[k] = \sum_{n=0}^{N-1}e^{j\left( \frac{2\pi }{N}\right) k_{0}n}e^{-j\left( \frac{2\pi }{N}\right) kn} \\
X[k] = \sum_{n=0}^{N-1}e^{j\left( \frac{2\pi }{N}\right) \left(
k_{0}-k\right) n}
\end{eqnarray*}

La sumatoria tendrá solución $N$ en el caso de que $k=k_{0}$ dado que $e^0 = 1$ y en caso contrario aplicamos la formula (\ref{eq:sum_util}) 
\[
s[n] = \frac{1- a^N}{1-a} = \frac{1 - e^{j\left( \frac{2\pi }{N}\right) (k_0-k) N} }{1 - e^{j\left( \frac{2\pi }{N}\right) \left(
k_{0}-k\right)  }} = 0
\]

Por lo tanto la transformada de Fourier es

\[
e^{j\left( \frac{2\pi }{N}\right) k_{0}n}\stackrel{\mathcal{F}}{\leftrightarrow } N \delta \left( k-k_{0}\right)
\]

\subsection{Función seno}

Dada la función seno, podemos hacer la representación de esta función como

\[
sen\left( \frac{2\pi }{N}k_{0}n\right) =\frac{1}{2j}\left[ e^{j\left( \frac{2\pi }{N}\right) k_{0}n}-e^{-j\left( \frac{2\pi }{N}\right) k_{0}n}\right]
\]

dado que tenemos la suma de dos exponenciales complejas, la transformada de
Fourier es
\[
sen\left( \frac{2\pi }{N}k_{0}n\right) \stackrel{\mathcal{F}}{%
\leftrightarrow }-j\frac{N}{2}\delta \left( k-k_{0}\right) +j\frac{N}{2}\delta
\left( k+k_{0}\right)
\]

\subsection{Función coseno}

La representación de la función coseno la podemos dar como
\[
\cos \left( \frac{2\pi }{N}k_{0}n\right) =\frac{1}{2}\left[ e^{j\left( \frac{%
2\pi }{N}\right) k_{0}n}+e^{-j\left( \frac{2\pi }{N}\right) k_{0}n}\right]
\]
de manera similar que en la función seno tenemos
\[
\cos \left( \frac{2\pi }{N}k_{0}n\right) \stackrel{\mathcal{F}}{%
\leftrightarrow }\frac{N}{2}\delta \left( k-k_{0}\right) +\frac{N}{2}\delta
\left( k+k_{0}\right)
\]

\subsection{Función impulso unitario}

Recordemos que la función impulso unitario es
\[
\delta \left( n\right) =\left\{
\begin{array}{c}
1\text{ si }n=0 \\
0\text{ en caso contrario}
\end{array}
\right.
\]
la transformada de Fourier para esta la calculamos
\begin{eqnarray*}
X[k]=\sum_{n=0}^{N-1}\delta \left( n-n_{0}\right) e^{-j\left(
\frac{2\pi }{N}\right) kn} \\
X[k]=e^{-j\left( \frac{2\pi }{N}\right) kn_{0}}
\end{eqnarray*}
podemos comprobar que $\left| e^{-j\left( \frac{2\pi }{N}\right) kn_{0}}\right| =1$ para cualquier valor que tome $k$ por lo que finalmente la magnitud de la transformada de Fourier es
\[
\delta \left( n-n_{0}\right) \stackrel{\mathcal{F}}{\leftrightarrow } 1
\]

\subsection{Constante}

Consideremos una función $x\left( n\right) =a$ la transformada de Fourier es
\begin{eqnarray*}
X[k]=\sum_{n=0}^{N-1}ae^{-j\left( \frac{2\pi }{N}\right) kn} \\
X[k]=a\sum_{n=0}^{N-1}e^{-j\left( \frac{2\pi }{N}\right) kn}
\end{eqnarray*}
la sumatoria tendrá la solución $N$ para $k=0$ y $0$ para $k\neq 0$ por lo
cual
\[
a\stackrel{\mathcal{F}}{\leftrightarrow } N a\delta \left( k\right)
\]

\subsection{Escalón Unitario}
La función escalón unitario esta definida como

\[
u \left( n_0\right) =\left\{
\begin{array}{c}
1\text{ si }n>=n_0 \\
0\text{ en caso contrario}
\end{array}
\right.
\]
la transformada de Fourier estará dada como
\begin{eqnarray*}
U[k]=\sum_{n=0}^{N-1}u(n_0)e^{-j\left( \frac{2\pi
}{N}\right) kn} \\
U[k]=\sum_{n=n_0}^{N-1}e^{-j\left( \frac{2\pi
}{N}\right) kn} \\
U[k]=\sum_{n=0}^{N-1}e^{-j\left( \frac{2\pi }{N}\right)
kn}  - \sum_{n=0}^{n_0-1}e^{-j\left( \frac{2\pi
}{N}\right) kn}\\
\end{eqnarray*}
Lo cual da como resultado
\[
U[k] =\left\{
\begin{array}{c}
N-n_0\text{ si }k =0 \\
\widehat{U}[k]\text{ en caso contrario}
\end{array}
\right.
\]
con
\begin{eqnarray*}
\widehat{U}[k]&=&-\frac{1-e^{-j\left( \frac{2\pi }{N}\right)kn_0}}{1-e^{-j\left( \frac{2\pi }{N}\right) k}} \\
\widehat{U}[k]&=&-\frac{e^{-j\left( \frac{\pi }{N}\right)kn_0}\left ( e^{j\left( \frac{\pi }{N}\right) kn_0}-e^{-j\left(
\frac{\pi }{N}\right) kn_0} \right) }{e^{-j\left( \frac{\pi
}{N}\right) k}\left ( e^{j\left( \frac{\pi }{N}\right)
k}-e^{-j\left( \frac{\pi }{N}\right)
k} \right) } \\
\widehat{U}[k]&=&-\frac{\sin(\frac{\pi n_0
k}{N})}{\sin(\frac{\pi k}{N})} e^{-j\left( \frac{\pi }{N}\right)
k(n_0-1)}
\end{eqnarray*}

\subsection{Caja}

Consideremos una función $x\left( n\right) $ dada por la siguiente expresión
\[
c[n]=\left\{
\begin{array}{l}
1\text{ si -}d<n<d \\
0\text{ si no}
\end{array}
\right.
\]
Aplicando la formula podemos ver
\begin{eqnarray*}
C[k] &=&\sum_{n=-N/2}^{N/2}c[n]e^{-j\left( \frac{2\pi}{N}\right) kn}\\
C[k] &=& \sum_{n=-d}^{d}e^{-j\left( \frac{2\pi}{N}\right) kn}\\
\end{eqnarray*}

Podemos organizar los términos de la siguiente forma

\begin{eqnarray*}
C[k] &=&\sum_{n=-d}^{-1}e^{-j\left( \frac{2\pi}{N}\right) kn} + \sum_{n=0}^{d}e^{-j\left( \frac{2\pi}{N}\right) kn}\\
C[k] &=&\sum_{n=1}^{d}e^{-j\left( \frac{2\pi}{N}\right) k(-n)} + \sum_{n=0}^{d}e^{-j\left(\frac{2\pi}{N}\right) kn}\\
C[k] &=&\sum_{n=0}^{d}e^{j\left( \frac{2\pi }{N}\right)kn} -1 + \sum_{n=0}^{d}e^{-j\left( \frac{2\pi}{N}\right) kn}\\
\end{eqnarray*}

Lo cual da como resultado
\[
C[k]=\left\{
\begin{array}{l}
\text{ si } k=0 \\
\text{...... } 2d+1  \\
\text{ si no}\\
\text{...... } \left(\frac{1 - e^{j\frac{2\pi}{N}k(d+1)}}{1 - e^{j\frac{2\pi}{N}k}}
+ \frac{1 - e^{-j\frac{2\pi}{N}k(d+1)}}{1 - e^{-j\frac{2\pi}{N}k}} -1 \right)\\
\end{array}
\right.
\]

En la figura \ref{fig:sinc2} se presenta la parte real de esta función ya que la imaginaria es cero.

La transformada de Fourier continua de esta función, esta dada por la siguiente expresión

\[
C[k]=\int_{-\infty }^{\infty }c(t)e^{-j(\frac{2\pi}{N})kt}dt
\]

al sustituir nuestra función obtenemos

\begin{eqnarray*}
C[k]&=&\int_{-d}^{d}e^{-j(\frac{2\pi }{N})kt}dt \\
C[k]&=&\frac{1}{\left[ -j(\frac{2\pi }{N})k\right] }\left. e^{-j(\frac{2\pi }{N})kt}\right| _{-d}^{d} \\
C[k]&=&\frac{1}{\left[ -j(\frac{2\pi }{N})k\right]}\left(-2j\right) sen\left[ \frac{2\pi }{N}kd\right] \\
C[k]&=& N \frac{sen\left[ \frac{2\pi }{N}kd\right] }{\pi k}
\end{eqnarray*}

la cual luce como \ref{fig:sinc}

\begin{figure}[h!]
{\normalsize \centering
\centerline{\psfig{figure = TFourier/figuras/sinc2.eps,width=8.0cm}} }
\caption{Función Sinc con d = 10 y N = 128.} \label{fig:sinc2}
\end{figure}

\begin{figure}[h!]
{\normalsize \centering
\centerline{\psfig{figure = TFourier/figuras/sinc.eps,width=8.0cm}} }
\caption{Función Sinc con k = 10 y N = 128.}
\label{fig:sinc}
\end{figure}

\subsection{Ejemplos}

En un programa en Java que utilice las clases funciones y gráfica, obtener y explicar brevemente la Transformada de Fourier Discreta (TFD) de las siguientes señales:

\begin{enumerate}
\item  $x_{1}[n]=\cos (\frac{2\pi }{N}n)+\sin (\frac{10\pi }{N}n)$ \label{eq:eje_uno}

\item  $x_{2}[n]=\delta [n]+\delta (n-3)$

\item  $x_{3}[n]=1+\delta (n+5)+cos(\frac{6\pi }{N}n)+\exp ^{-j(\frac{2\pi }{%
N})n}$
\end{enumerate}

\subsubsection{Ejercicio 1}

La figura \ref{fig1} muestra las cuatro gráficas que se obtienen al aplicar la TFD en la señal \ref{eq:eje_uno}. Se puede observar en la figura \ref{fig1:a} la señal que contiene parte real pero no contiene parte imaginaria, además la parte real se forma por un seno y un coseno. El resultado de aplicar la TFD a esta señal equivale a aplicar la TFD a las dos señales que la componen por separado y luego sumarlas. En las figuras \ref{fig1:c} y \ref{fig1:d} se puede observar el resultado de la aplicación de la TFD a la señal 1, cuya solución analítica es:

\[
X_{1}[k]=\frac{N}{2}\delta (k-1)+\frac{N}{2}\delta (k+1)-j\frac{N}{2}\delta
(k-5)+j\frac{N}{2}\delta (k+5)
\]

\begin{figure}[h!]
\begin{center}
{\normalsize \subfigure[x \ref{eq:eje_uno} \label{fig1:a}]{%
\psfig{figure = TFourier/figuras/1tiempo-real.eps,width=4.0cm}} \hfill \subfigure[Parte real de
la FFT(x)\label{fig1:c}]{\psfig{figure = TFourier/figuras/1frec-real.eps,width=4.0cm}}
\hfill \subfigure[Parte imaginaria de la FFT(x)\label{fig1:d}]{%
\psfig{figure = TFourier/figuras/1frec-imag.eps,width=4.0cm}} \label{fig1} }
\end{center}
\caption{Señal \ref{eq:eje_uno} y su transformada de Fourier}
\end{figure}

Con las figuras podemos constatar que el coseno efectivamente contribuye con
dos impulsos positivos en $k=1$ y $k=-1$. Asimismo, el seno contribuye con
dos pulsos con diferente signo en la parte imaginaria de la señal, el
positivo en $k=5$ y el negativo en $k=-5$.

\subsubsection{Ejercicio 2}

La solución analítica de la señal 2 es:
\[
X_{2}[k]=1+ \cos \left( \frac{6\pi }{N}k \right) -j \sin \left( \frac{6\pi }{N}k \right)
\]

Las figura \ref{fig2} muestra las gráficas de la señal original su TFD. Observando las gráficas \ref{fig2:c} y \ref{fig2:d} se puede observar que existe un coseno con frecuencia 3 en la parte real y un seno con igual frecuencia en la parte imaginaria. La contribución del impulso en el origen casi no se percibe en las gráficas, ya que es es una constante que se suma al resto de la señal.

\begin{figure}[h!]
\begin{center}
{\normalsize \subfigure[Señal real \label{fig2:a}]{%
\psfig{figure = TFourier/figuras/2tiempo-real.eps,width=4.0cm}}\subfigure[Parte real de la
FFT($x$) \label{fig2:c}]{\psfig{figure = TFourier/figuras/2frec-real.eps,width=4.0cm}} %
\subfigure[Parte imaginaria de la FFT($x$)\label{fig2:d}]{%
\psfig{figure = TFourier/figuras/2frec-imag.eps,width=4.0cm}} \label{fig2} }
\end{center}
\caption{Señal 2 y su transformada de Fourier}
\end{figure}

\subsubsection{Ejercicio 3}

Las figuras \ref{fig3:a} y \ref{fig3:b} muestra la parte real e imaginaria respectivamente de la señal 3. Al aplicar la TFD de manera analítica a la señal se obtiene:

\[
X_{3}[k]=N \delta {[k]}+ \cos \left ( \frac{6\pi }{N}k \right)-j\sin \left (\frac{6}{N} \right)+N\delta (k+1)
\]

La contribución de la constante se puede observar en la gráfica de la figura \ref{fig3:c} como un impulso en 1 de la parte real. La contribución del impulso es coseno con frecuencia 5 en la parte real y un seno negativo con frecuencia 5 en la parte imaginaria (figura \ref{fig3:d}). El coseno contribuye con un par de impulsos en la parte real, cuando $k=3$ y $k=-3$, y finalmente el exponencial complejo contribuye con un pulso en $k=-1$.

\begin{figure}[h!]
\begin{center}
{\normalsize 
\subfigure[Señal real en el tiempo\label{fig3:a}]{\psfig{figure = TFourier/figuras/3tiempo-real.eps,width=4cm}} \hfill \subfigure[Señal imaginaria en el tiempo\label{fig3:b}]{\psfig{figure = TFourier/figuras/3tiempo-imag.eps,width=4cm}} \hfill \subfigure[Señal real en la frecuencia\label{fig3:c}]{\psfig{figure = TFourier/figuras/3frec-real.eps,width=4cm}} \hfill %
\subfigure[Señal imaginaria en la frecuencia\label{fig3:d}]{\psfig{figure = TFourier/figuras/3frec-imag.eps,width=4cm}} \label{fig3} }
\end{center}
\caption{Señal 3 y su transformada de Fourier}
\end{figure}


\section{Propiedades de la Transformada Discreta de Fourier}

La transformada de Fourier discreta, presenta algunas propiedades un cuanto diferentes que la transformada continua. A continuación se mencionan algunas y se da la demostración de tales

\subsection{Periodicidad} \label {sec:periodicidad}

Sea una señal $x[n]$, mostrar que la transformada de Fourier, $X[k]$ tiene periodo N.

Si la función es periódica entonces
\begin{equation*}
  X[k] = X[k+N]
\end{equation*}
La TDF (\ref{eq:TF}) de $x$ es 
\[  
X[k] = \sum_{n=0}^{N-1} x[n] e^{-j\left(\frac{2\pi }{N}\right)
  nk}
\]
y la TDF para $x(n+N)$ se calcula a partir de (\ref{eq:TF}) como
\begin{eqnarray*}
  X[k+N] &=& \sum_{n=0}^{N-1} x[n] e^{-j\left(\frac{2\pi }{N}\right)
  n(k+N)}\\
  X[k+N] &=& \sum_{n=0}^{N-1} x[n] e^{-j\left(\frac{2\pi }{N}\right)
  nk} e^{-j\left(\frac{2\pi }{N}\right) nN} \\
  X[k+N] &=& \sum_{n=0}^{N-1} x[n] e^{-j\left(\frac{2\pi }{N}\right)
  nk} = X[k] \\
\end{eqnarray*}
Note que
\[
X[k+N] = X[k]  
\]


\subsection{Linealidad} \label{sec:linealidad}

Si

\begin{eqnarray*}
x_{1}[n]\stackrel{\mathcal{F}}{\leftrightarrow }X_{1}[k] \\
x_{2}[n]\stackrel{\mathcal{F}}{\leftrightarrow }X_{2}[k]
\end{eqnarray*}
entonces
\[
ax_{1}[n]+bx_{2}[n]\stackrel{\mathcal{F}}{\leftrightarrow } aX_{1}[k]+bX_{2}[k]
\]
Prueba:
Comenzamos por  la TDF (\ref{eq:TF})
\[
X[k]=\sum_{n=0}^{N-1}x[n]e^{-j\left( \frac{2\pi}{N}\right) nk}
\]
para la suma de $ax_{1}[n]+bx_{2}[n]$ queda
\begin{eqnarray*}
\hat X[k] = \sum_{n=0}^{N-1}\left[ ax_{1}[n]+bx_{2}[n]\right]
e^{-j\left(
\frac{2\pi }{N}\right) nk} \\
\hat X[k]=a \sum_{n=0}^{N-1}x_{1}[n]e^{-j\left( \frac{2\pi }{N}\right) nk}+ b \sum_{n=0}^{N-1}x_{2}[n]e^{-j\left( \frac{2\pi }{N}\right) nk} \\
\hat X[k]=aX_{1}[k]+bX_{2}[k]
\end{eqnarray*}

\subsection{Desplazamiento en tiempo} \label{sec:tiempo}

Si
\begin{eqnarray*}
x[n]\stackrel{\mathcal{F}}{\leftrightarrow }X[k] \\
x[n-n_{0}]\stackrel{\mathcal{F}}{\leftrightarrow }e^{-j\left( \frac{2\pi }{N}%
\right) n_{0}k}X[k]
\end{eqnarray*}
Demostración: 

La TDF (\ref{eq:TF}) de la señal desplazada $x[n-n_0]$ es:
\[
X[k]=\sum_{n=0}^{N}x[n-n_{0}]e^{j\left( \frac{2\pi}{N}\right) nk}
\]
haciendo en cambio de variable $\widehat{n}=n-n_{0}$ tenemos
\begin{eqnarray*}
X_2[k]&=&\sum_{\widehat{n}=-n_0}^{N-1-n_0}x[\widehat{n}]e^{-j\left(
\frac{2\pi }{N}\right)
\left( \widehat{n}+n_{0}\right) k} \\
X_2[k]&=&\sum_{\widehat{n}=0}^{N-1}x[\widehat{n}]e^{-j\left(
\frac{2\pi }{N}\right)
\widehat{n}k}e^{-j\left( \frac{2\pi }{N}\right) n_{0}k} \\
X_2[k]&=&e^{-j\left( \frac{2\pi }{N}\right) n_{0}k} \sum_{\widehat{n}=0}^{N-1}x[
\widehat{n}]e^{-j\left( \frac{2\pi }{N}\right) \widehat{n}k} \\
X_2[k]&=&e^{-j\left( \frac{2\pi }{N}\right) n_{0}k}X[k]
\end{eqnarray*}

\subsection{Desplazamiento en frecuencia} \label{sec:frecuencia}

Ahora si hacemos un desplazamiento en frecuencia tenemos que
\[
e^{j\left( \frac{2\pi }{N}\right) nk_{0}}x[n]\stackrel{\mathcal{F}}{\leftrightarrow }X[k-k_{0}]
\]
Demostración:
Escribimos la formula de la TDIF (\ref{eq:ITF})
\[
x_2[k]= \frac{1}{N} \sum_{k=0}^{N-1}X[k-k_{0}]e^{j\left( \frac{2\pi }{N}\right)
nk}
\]
haciendo el cambio de variable $\widehat{k}=k-k_{0}$ tenemos
\begin{eqnarray*}
x_2[k]&=&\frac{1}{N}\sum_{\widehat{k}=-k_{0}}^{N-1-k_{0}}X[\widehat{k}]e^{j\left(
\frac{2\pi }{N}\right)
n\left( \widehat{k}+k_{0}\right) } \\
x_2[k]&=& \frac{1}{N} \sum_{\widehat{k}=0}^{N-1}X[\widehat{k}]e^{j\left( \frac{2\pi }{N}\right) n
\widehat{k}}e^{j\left( \frac{2\pi }{N}\right) nk_{0}} \\
x_2[k]&=& \frac{1}{N} e^{j\left( \frac{2\pi }{N}\right) nk_{0}}\sum_{\widehat{k}=0}^{N-1}X[\widehat{k}]e^{j\left( \frac{2\pi }{N}\right) n \widehat{k}} \\
x_2[k]&=&e^{j\left( \frac{2\pi }{N}\right) nk_{0}}x[n]
\end{eqnarray*}

\subsection{Conjugación} \label{sec:conjugacion}

La definición del conjugado de un numero complejo es
\begin{eqnarray*}
x=R+jI \\
x^{*}=R-jI
\end{eqnarray*}

Mostrar que:
\[
x^{*}[n]\stackrel{\mathcal{F}}{\leftrightarrow }X^{*}[-k]
\]
comenzaremos por
\begin{eqnarray*}
X_2[k]&=&\sum_{n=0}^{N-1}x^{*}[n]e^{-j\left( \frac{2\pi }{N}\right) nk} \\
X_2[k]&=&\left( \sum_{n=0}^{N-1}x[n]e^{-j\left(\frac{2\pi }{N}\right)n\left( -k\right) }\right) ^{*} \\
X_2[k]&=&X^{*}[-k]
\end{eqnarray*}

\subsection{Inversión en Tiempo} \label{sec:invtiempo}

Mostrar que
\[
x[-n]\stackrel{\mathcal{F}}{\leftrightarrow }X[-k]
\]
Comenzaremos por calcular la transformada de Fourier de $x(-n)$%
\[
X_2[k]=\sum_{n=0}^{N-1}x[-n]e^{-j\left( \frac{2\pi}{N}\right) nk}
\]
hacemos el cambio de variable $m=-n$
\begin{eqnarray*}
X_2[k]&=&\sum_{m=0}^{-N+1}x[m]e^{-j\left( \frac{2\pi }{N}\right) (-m)k} \\
X_2[k]&=&\sum_{m=0}^{N-1}x[m]e^{-j\left( \frac{2\pi }{N}\right) m(-k)} \\
X_2[k]&=&X[-k]
\end{eqnarray*}

\subsection{Escalamiento en tiempo} \label{sec:esctiempo}

Sea $x[an]$ una señal multiplicada por un entero, calcular latransformada de Fourier para este caso
\[
X_2[k]=\sum_{n=0}^{N-1}x[an]e^{-j\left( \frac{2\pi
}{N}\right) nk}
\]
haciendo $m=an$ tenemos
\begin{eqnarray*}
X_2[k]&=&\sum_{n=0}^{N-1}x[m]e^{-j\left( \frac{2\pi}{N}\right) \left(\frac{m}{a}\right) k} \\
X_2[k]&=&\sum_{m=0}^{a(N-1)}x[m]e^{-j\left( \frac{2\pi}{N}\right)m\left( \frac{k}{a}\right) } \\
&=&X\left[\frac{k}{a}\right]
\end{eqnarray*}
Note que el rango de la TDF, también se escala.

\subsection{Convolución} \label{sec:convolucion}

El teorema de la convolución afirma que si $\mathcal{F}\left[
x\left(
n\right) \right] =X[k]$ y $\mathcal{F}\left[ y\left( n\right) \right] =Y[k]$%
\ entonces
\[
x\left[n\right] *y\left[ n\right]  \stackrel{\mathcal{F}}{\leftrightarrow } X[k]Y[k]
\]
demostración:

Consideremos que la convolución está $g[n] = x\left[ n\right]*y\left[ n\right]$ dada por

\[
g[n] = \sum_{m=0}^{N-1}x\left[ m\right] y\left[ n-m\right]
\]

y la transformada de Fourier de $g[n]$ es

\begin{eqnarray*}
G[k] &=&\sum_{n=0}^{N-1} g[n]  e^{-j\left(\frac{2\pi}{N}\right) nk} \\
G[k] &=&\sum_{n=0}^{N-1}\left( \sum_{m=0}^{N-1}x[m] y[ n-m] \right) e^{-j\left( \frac{2\pi}{N}\right) nk}
\end{eqnarray*}

cambiando el orden de la sumatoria
\[
G[k]=\sum_{m=0}^{N-1}x[ m] \left( \sum_{n=0}^{N-1}y[ n-m] e^{-j\left( \frac{2\pi}{N}\right) nk}\right)
\]

haciendo $\widehat{n}=n-m$

\begin{eqnarray*}
G[k]&=&\sum_{m=0}^{N-1}x[ m] \left(
\sum_{n=0}^{N-1}y[\widehat{n}] e^{-j\left( \frac{2\pi }{N}\right) \left( \widehat{n}%
+m\right) k}\right) \\
G[k]&=&\left(\sum_{m=0}^{N-1}x[m]
e^{-j\left( \frac{2\pi }{N}\right) mk}\right) \left(
\sum_{\widehat{n}=0}^{N-1}y[\widehat{n}] e^{-j\left( \frac{2\pi }{N}\right) \widehat{n}k}\right) \\
G[k]&=&X[k]Y[k]
\end{eqnarray*}

\subsection{Multiplicación} \label{sec:multiplicacion}

De manera inversa podemos ver que si $\mathcal{F}\left[ x\left( n\right) \right] =X[k]$ y $\mathcal{F}\left[ y\left( n\right) \right] =Y[k]$\ entonces

\[
Nx[n] y[n]  \stackrel{\mathcal{F}}{\leftrightarrow }  X[k]*Y[k]
\]
demostración:

Consideremos que la convolución $G[k] = X[k]*Y[k]$ está dada por

\begin{equation*}
G[k] = \sum_{l=0}^{N-1}X[l] Y[ k-l]
\end{equation*}

y su transformada Inversa de Fourier (\ref{eq:ITF}) la podemos calcular como:

\begin{eqnarray*}
g[n] &=& \frac{1}{N} \sum_{k=0}^{N-1}\left( G[k]\right) e^{j\left( \frac{2\pi}{N}\right) nk}
\\
g[n] &=& \frac{1}{N}\sum_{k=0}^{N-1}\left( \sum_{l=0}^{N-1}X[ l]Y[ k-l]  \right) e^{j\left( \frac{2\pi }{N}\right) nk}
\end{eqnarray*}

cambiando el orden de la sumatoria

\[
g[n] = \frac{1}{N}\sum_{l=0}^{N-1}X[l] \left(\sum_{k=0}^{N-1}Y[k-l] e^{j\left( \frac{2\pi
}{N}\right) nk}\right)
\]

haciendo $\widehat{k}=k-l$

\begin{eqnarray*}
g[n] & = & \frac{1}{N}\sum_{l=0}^{N-1}X[l] \left(
\sum_{\widehat{k}=-l}^{N-1-l}Y[\widehat{k}] e^{j\left( \frac{2\pi }{N}\right) n\left( \widehat{k}%
+l\right) }\right) \\
g[n] & = & N\left( \frac{1}{N}\sum_{l=0}^{N-1}X[ l] e^{j\left(
\frac{2\pi }{N}\right) nl}\right) \left( \frac{1}{N}
\sum_{\widehat{k}=0}^{N-1}Y[ \widehat{k}]
e^{j\left( \frac{2\pi }{N}\right) n\widehat{k}}\right) \\
g[n] & = & Nx[n]y[n]
\end{eqnarray*}

\subsection{Diferenciación en Tiempo} \label{sec:diftiempo}

Demostrar que
\[
x[n]-x[n-1]\stackrel{\mathcal{F}}{\leftrightarrow }\left(
1-e^{-j\left( \frac{2\pi }{N}\right) k}\right) X[k]
\]
tenemos que
\[
x[n]\stackrel{\mathcal{F}}{\leftrightarrow }X[k]
\]
y
\[
x[n-1]\stackrel{\mathcal{F}}{\leftrightarrow }e^{-j\left( \frac{2\pi }{N}%
\right) k}X[k]
\]
por superposición demostramos la primera.


\subsection{Diferenciación en Frecuencia} \label{sec:diffrecuencia}
Demostrar que
\[
X[k]-X[k-1]\stackrel{\mathcal{F}}{\leftrightarrow }\left(
1-e^{j\left( \frac{2\pi }{N}\right) k}\right) x[n]
\]
tenemos que
\[
X[k]\stackrel{\mathcal{F}}{\leftrightarrow }x[n]
\]
y
\[
X[k-1]\stackrel{\mathcal{F}}{\leftrightarrow }e^{j\left( \frac{2\pi }{N}%
\right) k}x[n]
\]
por superposición demostramos la primera.

\subsection{Propiedades de Simetría de la transformada de Fourier.} \label{sec:simetria}

Para cualquier secuencia discreta $x$ la parte real la podemos calcular haciendo

\[
\mathcal{R}\left[ x[n] \right] =\frac{1}{2}\left[
x[n]+x^{*}[n]\right]
\]
y la parte imaginaria como
\[
\mathcal{I}\left[ x[ n] \right] =\frac{1}{2}\left[
x[n]-x^{*}[n]\right]
\]
Si $x[n]$ es una secuencia real entonces:
\[
\frac{1}{2}\left[ x[n]-x^{*}[n]\right] =0
\]
lo que es equivalente a
\[
x[n]=x^{*}[n]
\]

Al aplicar la transformada de Fourier tendremos que

\[
X[k]=X^{*}[-k]
\]

A partir de esto se observa que la parte real de $X[k]$ es una función par de $k$ y la parte imaginaria de $X[ k] $ es una función impar de $k$. De manera similar, la magnitud de $X[
k] $ es una función par y el ángulo de de fase es una función impar. Además
\[
\mathcal{E}\left ( x[n] \right ) \stackrel{\mathcal{F}}{%
\leftrightarrow }\mathcal{R}\left ( X[k] \right )
\]
y
\[
\mathcal{O}\left ( x[ n] \right ) \stackrel{\mathcal{F}}{%
\leftrightarrow }\mathcal{I}\left ( X [ k ] \right )
\]
demostración:

En el caso de una señal real y par se cumple que $x[n]=x[-n]$ y que $x[n]=x^{*}[n]$ por lo tanto en el dominio de Fourier

\begin{eqnarray*}
X[k]=X[-k]=\mathcal{R}\left( X[-k]\right) +j\mathcal{I}\left( X[-k]\right) \\
X[k]=X^{*}[-k]=\mathcal{R}\left( X[-k]\right) -j\mathcal{I}\left(
X[-k]\right)
\end{eqnarray*}

la única posibilidad de que esto sea cierto es que la parte imaginaria sea cero. Así la transformada de Fourier se transforma en

\[
X[k]=\sum_{n=0}^{N}x[n]\cos \left( \frac{2\pi }{N}nk\right)
\]

a esta ecuación es común que se le conozca como la transformada coseno.

En el caso de una señal real e impar, se cumple que $x[n]=-x[-n]$ $x[n]=x^{*}[n],$ entonces en el dominio de Fourier

\begin{eqnarray*}
X[k]=-X[-k]=-\mathcal{R}\left( X[-k]\right) -j\mathcal{I}\left(
X[-k]\right)
\\
X[k]=X^{*}[-k]=\mathcal{R}\left( X[-k]\right) -j\mathcal{I}\left(
X[-k]\right)
\end{eqnarray*}

la única posibilidad de que esto ocurra es que la parte real sea cero. La transformada de Fourier en este caso queda como

\[
X[k]=j \sum_{n=0}^{N}x[n]sen\left( \frac{2\pi }{N}nk\right)
\]

\subsection{Relación de Parseval.} \label{sec:parseval}

Si $x $ y $X $ son la señal y su transformada discreta de Fourier respectivamente, entonces tenemos que:

\[
N \sum_{n=0}^{N-1}\left| x[n]\right| ^{2}\stackrel{\mathcal{F}}{\leftrightarrow }\sum_{k=0}^{N-1}\left| X[k]\right| ^{2}
\]

podemos representar como

\[
N \sum_{n=0}^{N-1}x[n]x^{*}[n]=\sum_{k=0}^{N-1}X[k]X[k]^{*} 
\]
Tomando únicamente el segundo termino de la ecuación anterior
\[
E=\sum_{k=0}^{N-1}X[k]X[k]^{*} 
\]
\begin{eqnarray*}
E=\sum_{k=0}^{N-1}X[k]\left[\sum_{n=0}^{N-1}x[n]e^{-j\left(
\frac{2\pi }{N}\right) nk}\right] ^{*} \\
E = \sum_{k=0}^{N-1}X[k]\sum_{n=0}^{N-1}x^{*}[n]e^{j\left( \frac{2\pi }{N}\right) nk}
\end{eqnarray*}

cambiando el orden en que se hacen las sumatorias

\begin{eqnarray*}
= N \sum_{n=0}^{N-1}x^{*}[n]\left[ \frac{1}{N}\sum_{k=0}^{N-1}X[k]e^{j\left( \frac{2\pi }{N%
}\right) nk}\right] \\
= N \sum_{n=0}^{N-1}x^{*}[n]x[n] \\
= N \sum_{n=0}^{N-1}\left| x[n]\right| ^{2}
\end{eqnarray*}

\subsection{Resumen de Propiedades}
Dado lo anterior podemos resumir en la siguiente tabla las propiedades de la transformada discreta de Fourier.

\begin{tabular}{|c|c|c|c|}
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
    & \textbf{Señal en} & \textbf{Señal en } &   \\
  \textbf{Propiedad} & \textbf{el tiempo} & \textbf{la frecuencia}  & \textbf{Referencia}\\
  \hline
  Periodicidad & $x[n]$ & $X[k]$ periodo N & \ref{sec:periodicidad} \\
  \hline
  Linealidad & $ax_{1}[n]+bx_{2}[n]$ & $aX_{1}[k]+bX_{2}[k]$  & \ref{sec:linealidad} \\
  \hline
  Desp. en tiempo & $x[n-n_{0}]$ & $e^{-j\left( \frac{2\pi }{N}\right) n_{0}k}X[k]$ & \ref{sec:tiempo} \\
  \hline
  Desp. en frecuencia & $e^{j\left( \frac{2\pi }{N}\right) nk_{0}}x[n]$ & $X[k-k_{0}]$ & \ref{sec:frecuencia} \\
  \hline
  Conjugación & $x^{*}[n]$ & $X^{*}[-k]$ & \ref{sec:conjugacion}\\
  \hline
  Inversión en tiempo & $x[-n]$ & $X[-k]$ & \ref{sec:invtiempo} \\
  \hline
  Escalamiento en el Tiempo &  $x[an]$ & $X[k/a]$ & \ref{sec:esctiempo} \\
  \hline
  Convolución & $x[n]*y[n]$ & $X[k]Y[k]$ &  \ref{sec:convolucion}\\
  \hline
  Multiplicación & $N x[n]y[n]$ & $X[k]*Y[k]$  & \ref{sec:multiplicacion}\\
  \hline
  Dif. en tiempo & $x[n]-x[n-1]$ & $\left(1-e^{-j\left( \frac{2\pi }{N}\right) k}\right) X[k]$  & \ref{sec:diftiempo} \\
  \hline
  Dif. en Frecuencia & $\left(1-e^{j\left( \frac{2\pi }{N}\right) n}\right) x[n]$ & $X[k]-X[k-1]$ & \ref{sec:diffrecuencia} \\
  \hline
  Simetría conjugada & $x[n]$ real & $X[k] = X^*[k]$ & \ref{sec:simetria}\\
  \hline
  Simetría & $x[n]$ real y par  & $X[k]$ real y par & \ref{sec:simetria}\\
  \hline
  Simetría & $x[n]$ real e impar& $X[k]$ imaginaria e impar & \ref{sec:simetria}\\
  \hline
  Parseval & $N \sum_{n=0}^{N-1}\left| x[n]\right| ^{2}$ & $\sum_{k=0}^{N-1}\left| X[k]\right| ^{2}$ & \ref{sec:parseval} \\
  \hline
\end{tabular}

\section{Transformada de Discreta de Fourier en Dos dimensiones.}

En dos dimensiones las exponenciales complejas (\ref{eq:ExpC}) las expresaremos como
\begin{eqnarray}
\phi_{k,l}(n,m) &=& e^{j \left((2 \pi n k)/N  + (2 \pi m l)/M \right)} \label{eq:ExpC_2D}\\
\phi_{k,l}(n,m) &=& \phi_k(n) \phi_l(m) \nonumber
\end{eqnarray}
 
Definidas las exponenciales complejas (\ref{eq:ExpC_2D}) y de acuerdo con (\ref{eq:TF}) podemos escribir la Transformada Discreta de Fourier en 2D (TDF2), como

\begin{equation}
X[k,l]= \sum_{n=0}^{N-1}\sum_{m=0}^{M-1}x[n,m]e^{-j\left( \frac{2k\pi }{N}n+\frac{2l\pi }{M}m\right)} \label{eq:TF2}
\end{equation}

reorganizando términos tenemos:
\[
X[k,l]=\sum_{m=0}^{M-1}\left[ \sum_{n=0}^{N-1}x[n,m]e^{-j\left(
\frac{2\pi }{N}\right) nk}\right] e^{-j\left( \frac{2\pi }{M}\right) ml}
\]

La formulación de la Transformada Discreta Inversa de Fourier en dos dimensiones (TDIF2) esta dada por (\ref{eq:TIF2}):

\begin{equation}
x[n,m]= \frac{1}{NM}\sum_{k=0}^{N-1}\sum_{l=0}^{M-1}X[k,l]e^{j\left( \frac{2k\pi }{N}n+\frac{2l\pi }{M}m\right)} \label{eq:TIF2}
\end{equation}

reorganizando términos
\[
x[n,m]= \frac{1}{N} \sum_{k=0}^{N-1}\left[\frac{1}{M}\sum_{l=0}^{M-1}X[k,l]e^{j\left( \frac{2l\pi }{M}m\right)} \right] e^{j\left( \frac{2k\pi }{N}n \right)}
\]

En la siguiente sección se muestra la implementación de la TDF y TDIF en dos dimensiones.

\subsection{Ejemplo}

Calcular la TDF2 para la señal bidimensional
\[
x =
\left[
\begin{array}{cccc}
 1 & 2  & 3  & 4 \\
 4 & 3  & 2  & 1
\end{array}
\right]
\]

De acuerdo con las formulaciones, podemos hacer la TDF en una dimensión para cada uno de los renglones para luego proceder por columna. La matriz de exponenciales complejas por columnas es

\[
\Phi_r^* = 
\left[
\begin{array}{rrrr}
 1 &  1 & 1 & 1  \\
 1 &  -j & -1&  j\\
 1 &  -1 & 1 & -1 \\
 1 & j & -1 & -j  
\end{array}
\right]
\]
y por renglones es

\[
\Phi_c^* = 
\left[
\begin{array}{rr}
 1 &  1   \\
 1 &  -1 
\end{array}
\right]
\]

Comenzamos haciendo la Transformada de Fourier por renglones. 

Así para el primer renglón calculamos 

\[
\left[
\begin{array}{rrrr}
 1 &  1 & 1 & 1  \\
 1 &  -j & -1&  j\\
 1 &  -1 & 1 & -1 \\
 1 & j & -1 & -j  
\end{array}
\right]
\left[
\begin{array}{r}
 1  \\
 2  \\
 3  \\
 4   
\end{array}
\right] =
\left[
\begin{array}{r}
 10 + j 0  \\
 -2 + j 2  \\
 -2  + j0\\
 -2 - j2  
\end{array}
\right] 
\]

para el segundo renglón calculamos 

\[
\left[
\begin{array}{rrrr}
 1 &  1 & 1 & 1  \\
 1 &  -j & -1&  j\\
 1 &  -1 & 1 & -1 \\
 1 & j & -1 & -j  
\end{array}
\right]
\left[
\begin{array}{r}
 4  \\
 3  \\
 2  \\
 1   
\end{array}
\right] =
\left[
\begin{array}{r}
 10 + j 0  \\
  2 - j 2  \\
  2  + j0\\
  2  + j2  
\end{array}
\right] 
\]

Los dos renglones quedan

\[
\left[
\begin{array}{rrrr}
 10 + j 0 & -2 + j 2  & -2  + j0 & -2 - j2   \\
 10 + j 0 & 2 - j 2  & 2  + j0 & 2  + j2  
\end{array}
\right] 
\]

Por columnas hacemos
\begin{eqnarray*}
X &=& \left[
\begin{array}{rr}
 1 &  1   \\
 1 &  -1 
\end{array}
\right]
\left[
\begin{array}{rrrr}
 10 + j 0 & -2 + j 2  & -2  + j0 & -2 - j2   \\
 10 + j 0 & 2 - j 2  & 2  + j0 & 2  + j2  
\end{array}
\right] \\
X &=&
\left[
\begin{array}{rrrr}
 20 + j 0 & 0 + j 0  & 0  + j0 &  0 + j0   \\
   0 + j 0 & -4 + j 4 & -4  + j0 & -4  - j4  
\end{array}
\right]  
\end{eqnarray*}


\section{Implementación de la Transformada Discreta de Fourier en 2D}

Analizando las expresiones reorganizadas de la TDF2 y TDIF2 podemos ver que son equivalentes a realizar la Transformada en una dirección del arreglo bidimensional y después realizarlo en la otra dirección. Adicionalmente en las formulaciones dadas por (\ref{eq:TF2}) y (\ref{eq:TIF2}), podemos ver que la diferencia entre ambas es un signo y una división, por lo tanto la implementación genérica de ambas es:

\begin{verbatim}
  private static void DFT_2D(double entrada_r[][], double entrada_i[][], 
          double salida_r[][], double salida_i[][], int signo){
      
      int N = entrada_r.length, M = entrada_r[0].length, n, k;
      double Cr[][] = new double [M][M];
      double Ci[][] = new double [M][M];
      double Rr[][] = new double [N][N];
      double Ri[][] = new double [N][N];
      double w , suma_r, suma_i, factor =1.0;
      int i, j;
      int max = N >M ? N : M;

      double b_r[] = new double[max];
      double b_i[] = new double[max];
      
            
      w = 2.0*Math.PI/(double) N;
      
      for(n=0; n<N; n++){
          for(k=n; k<N; k++) {
              Rr[n][k] = Math.cos(w*n*k);
              Rr[k][n] = Rr[n][k];
              Ri[n][k] = signo*Math.sin(w*n*k);
              Ri[k][n] = Ri[n][k];            
          }
      }       
      
      w = 2.0*Math.PI/(double) M;
      
      for(n=0; n<M; n++){
          for(k=n; k<M; k++) {
              Cr[n][k] = Math.cos(w*n*k);
              Cr[k][n] = Cr[n][k];
              Ci[n][k] = signo*Math.sin(w*n*k);
              Ci[k][n] = Ci[n][k];            
          }
      }
      
      factor = signo == 1 ? 1.0/(double) N : 1.0 ;
      
      for(i=0; i<N; i++) {     
          for(k=0; k<M; k++) {
              suma_r = 0;
              suma_i = 0;

              for(n=0; n<M; n++){
                  suma_r += (Cr[k][n]*entrada_r[i][n] - Ci[k][n]*entrada_i[i][n]);
                  suma_i += (Cr[k][n]*entrada_i[i][n] + Ci[k][n]*entrada_r[i][n]);
              } 
              salida_r[i][k] = suma_r*factor;
              salida_i[i][k] = suma_i*factor;
          }         
      }
      
      factor = signo == 1 ? 1.0/(double) M : 1.0 ;
      
      for(j=0; j<M; j++) {      
          
          for(k=0; k<N; k++) {
              suma_r = 0;
              suma_i = 0;

              for(n=0; n<N; n++){
                  suma_r += (Rr[k][n]*salida_r[n][j] - Ri[k][n]*salida_i[n][j]);
                  suma_i += (Rr[k][n]*salida_i[n][j] + Ri[k][n]*salida_r[n][j]);
              } 
              b_r[k] = suma_r;
              b_i[k] = suma_i;
          }
          
          for(i=0; i<N; i++){
              salida_r[i][j] = b_r[i]*factor;
              salida_i[i][j] = b_i[i]*factor;
          }    
      } 
  }
\end{verbatim}

Para el calculo de la TDF2 y de ls TDIF haremos uso de las funciones

\begin{verbatim}
  public static void Fourier(double entrada_r[][], double entrada_i[][], 
          double salida_r[][], double salida_i[][]) {
      DFT_2D(entrada_r, entrada_i, salida_r, salida_i, -1);
  }
\end{verbatim}

\begin{verbatim}
  public static void Inversa_Fourier(double entrada_r[][], double entrada_i[][], 
          double salida_r[][], double salida_i[][]) {
      DFT_2D(entrada_r, entrada_i, salida_r, salida_i, 1);
  }
\end{verbatim}

\subsection{Ejemplo}

Transformada de Fourier de una señal bidimensional

Dada la señal $x\left[ n, m\right] =\cos \left( \frac{2*\pi }{N}\left(k_{0}n+l_{0}m\right) \right) $ determinar su transformada de Fourier.

Esta señal puede ser representada como la suma de dos exponenciales complejas

\begin{eqnarray*}
x[n,m]=\cos \left( \frac{2*\pi }{N}\left( k_{0}n+l_{0}m\right) \right) \\
=\frac{1}{2}e^{j\left( \frac{2\pi }{N}\right) (k_{0}n+l_{0}m)}+\frac{1}{2}%
e^{-j\left( \frac{2\pi }{N}\right) (k_{0}n+l_{0}m)}
\end{eqnarray*}
por lo tanto
\[
X[k,l]=\frac{N}{2}\delta \left( k-k_{0},l-l_{0}\right) +\frac{N}{2}\delta
\left( k+k_{0},l+l_{0}\right)
\]

En la figura \ref{fig:coseno} podemos ver la señal bidimensional correspondiente $x[n,m]=\cos \left[ \frac{2*\pi }{N}\left( 10n+20m)\right) \right] $ y su transformada de Fourier. Note que en la imagen de la transformada de Fourier aparecen dos picos en las coordenadas $[10,20]$ y $[118,108]$, lo cual, corresponde con la deducción anterior.

\begin{figure}[h!]
{\normalsize \centering
\centerline{\psfig{figure = TFourier/figuras/coseno.eps,width=8.0cm}} }
\caption{Señal coseno en dos dimensiones}
\label{fig:coseno}
\end{figure}

\subsection{Ejemplo}

El primer renglón de una imagen es creado utilizando una distribución normal $N(0,1)$ (ver \ref{fig:fig03}) y los renglones subsiguientes se calculan de acuerdo con la siguiente sucesión $f[n,m]=f\left[ n-1,m-1\right] $ tal que se produce un patrón como el mostrado en la figura \ref{fig:fig02} (a la izquierda). Explique a qué se debe que la magnitud de la transformada de Fourier esta dominado por una linea recta a 45 grados. La transformada de Fourier del ruido gaussiano la podemos ver a la derecha de la figura \ref{fig:fig02} .

\begin{figure}[h!]
{\normalsize \centering
\centerline{\psfig{figure = TFourier/figuras/fig02.eps,width=8.0cm}} }
\caption{A la izquierda Patron regular creado con una señal uni--dimensional
trasladada (ruido Gaussiano) y a la derecha Magnitud de su transformada de
Fourier}
\label{fig:fig02}
\end{figure}

\begin{figure}[h!]
{\normalsize \centering
\centerline{\psfig{figure = TFourier/figuras/fig03.eps,width=8.0cm}} }
\caption{Valores aleatorios calculado con una distribución Normal con media
cero y varianza unitaria}
\label{fig:fig03}
\end{figure}

Demostración:

El primer renglón de imagen fue generado utilizando una distribución normal,
y los renglones subsecuentes utilizando la recursión
\[
f[n,m]=f\left[ n-1,m-1\right]
\]
la transformada de Fourier para $f[n,m]$ es $F[k,l]$ si aplicamos la propiedad de translación de la TF, podemos ver:

\begin{eqnarray*}
f[n,m]\stackrel{\mathcal{F}}{\leftrightarrow }F[k,l] \\
f[n-n_{0},m-m_{0}]\stackrel{\mathcal{F}}{\leftrightarrow }e^{-j\left( \frac{%
2\pi }{NM}\right) (n_{0}k+m_{0}l)}F[k,l]
\end{eqnarray*}
lo cual nos da como resultado la transformada de Fourier $F(x),$ esta
multiplicada por una exponencial compleja $e^{-j\left( \frac{2\pi }{NM}%
\right) (n_{0}k+m_{0}l)}$ cuyo máximo se localiza sobre la recta $%
n_{0}k+m_{0}l=0$, dado que $n_{0}=m_{0}=1$, tendremos que la pendiente de

esta linea recta es 45 grados.


\section{Convolución utilizando TF.}

En una imagen tenemos que la referencia se encuentra en la esquina superior izquierda. Cuando estamos utilizando la transformada de Fourier debemos recordar que está, considera que las señales tienen periodos N en la dirección de x y M en la dirección de y. Así, una imagen estará representada virtualmente, por un conjunto de copias infinitas es un espacio infinito.

Para realizar una translación de la imagen, una manera es convolucionar la imagen con la función delta de Dirac $\delta \left( n-n_{0},m-m_{0}\right) $ donde $n_{0}$ y $m_{0}$ es el desplazamiento, hay que recordar que la convolución es Lineal e invariante a la translación, por lo que, la convolución de dos señales no se vera afectada cuando hacemos la translación del kernel.

Cuando aplicamos el teorema de la convolución
\[
x[n,m]*y[n,m]\stackrel{\mathcal{F}}{\leftrightarrow }X[k,l]Y[K,l]
\]
debemos tomar en cuenta que si el kernel se desplaza, la transformada de
Fourier del kernel estará multiplicada por una exponencial compleja
\begin{eqnarray*}
x[n-n_{0},y-m_{0}] \stackrel{\mathcal{F}}{\leftrightarrow }X[k,l]e^{-j\frac{%
2\pi }{NM}(n_{0}k+m_{0}l)} \\
x[n,m]*\delta \left( n-n_{0},m-m_{0}\right) \stackrel{\mathcal{F}}{%
\leftrightarrow }X[k,l]e^{-j\frac{2\pi }{NM}(n_{0}k+m_{0}l)}
\end{eqnarray*}

Cuando aplicamos el teorema de la convolución tendremos
\begin{eqnarray*}
x[n,m]*\left( y[n,m]*\delta \left( n-n_{0},m-m_{0}\right) \right) \stackrel{%
\mathcal{F}}{\leftrightarrow }X[k,l]\left[ Y[k,l]e^{-j\frac{2\pi }{NM}%
(n_{0}k+m_{0}l)}\right] \\
\left( x[n,m]*\delta \left( n-n_{0},m-m_{0}\right) \right )*y[n,m]\stackrel{%
\mathcal{F}}{\leftrightarrow }\left( X[k,l]e^{-j\frac{2\pi }{NM}%
(n_{0}k+m_{0}l)}\right) Y[k,l] \\
x[n-n_{0},m-m_{0}]*y[n,m]\stackrel{\mathcal{F}}{\leftrightarrow }\left(
X[k,l]e^{-j\frac{2\pi }{NM}[n_{0}k+m_{0}l]}\right) Y[k,l]
\end{eqnarray*}
lo cual significa que $x[n-n_{0},m-m_{0}],$ estará desplazada a las
coordenadas $\left[ n_{0},m_{0}\right] $

\section{Teorema del Muestreo para señales discretas}

Consideramos el caso de una señal continua en el tiempo dada por $x(t)=cos(15\pi t)$. Es claro que la señal tiene una frecuencia angular $w =15\pi$, una frecuencia $f=7.5$ y un periodo $T=\frac{1}{7.5}$. Esto significa que si graficamos la señal tendremos siete ciclos y medio por segundo y la gráfica para esta lucirá como la figura \ref{fig:fig04}. Si esta misma función la submuestreamos con incrementos de $\frac{\pi }{9}$ lucirá como la fig \ref{fig:fig05} y esta misma a intervalos de 0.01 lucirá como \ref{fig:fig06}. ¿Cual es el valor de incremento al que debo discretizar mi señal sin perder información?.

\begin{figure}[h!]
\begin{center}
{\normalsize \subfigure[Señal original\label{fig:fig04}]{%
\psfig{figure = TFourier/figuras/fig04.eps,width=3.5cm}} \hfill \subfigure[Señal muestreada a $%
\frac{\pi}{9}$\label{fig:fig05}]{\psfig{figure = TFourier/figuras/fig05.eps,width=3.5cm}}
\hfill \subfigure[Señal muestreada a 0.01 \label{fig:fig06}]{%
\psfig{figure = TFourier/figuras/fig06.eps,width=3.5cm}} }
\end{center}
\caption{Señal $cos(15\pi t)$ con diferentes muestreos} \label{fig:cos_muestreda}
\end{figure}

Podemos definir una señal muestreada $x_m[n]$ con un periodo $T_m$ como:

\begin{equation} \label{eq:muestreada}
x_m[n] = x(nT_m)
\end{equation}

Aplicando (\ref{eq:muestreada}) a la señal $x(t) = cos(15 \pi t)$ tenemos una señal muestreada
\[
x_m[n] = cos((15 \pi T_m) n)
\]
note que la frecuencia de la señal original se ve afectada por el periodo de muestreo.  La transformada de Discreta de Fourier de una función coseno con periodo de muestreo $T_m$ es:

\[
cos\left(\frac{2 \pi k_0 T_m}{N}  n \right)  \stackrel{\mathcal{F}}{\leftrightarrow } \frac{N}{2} [\delta(k - T_m k_0) + \delta(k + T_m k_0)]
\]

En la figura \ref{fig:TDF_cos_muestreda}, se muestra la TDF de la señal con diferentes periodos de muestreo $T_m = 2/150$, $T_m = 4/150$, $T_m = 6/150$, $T_m = 8/150$, $T_m = 10/150$ y $T_m = 12/150$. Note en esta figura que la los impulso se encuentran en diferentes posiciones de $k_0$, debido a que alteramos la frecuencia original de la señal al multiplicarla por el periodo de muestreo $T_m$. ¿Ahora que relación tienen?.

Recordemos que la TDF solamente tiene valores de frecuencia que son múltiplos de $2 \pi /N$, a acuerdo con esto, todas las frecuencias $\omega_0$ tendrán una representación dada por:

\[
\omega_0 T_m = \frac{2 \pi}{N} k_0
\]

y el múltiplo $k_0$ de la frecuencia $2 \pi /N$ lo podemos encontrar como (\ref{eq:freq_muestreada})

\begin{equation} 
k_0 = \frac{N \omega T_m}{2 \pi} \label{eq:freq_muestreada}
\end{equation}

De acuerdo con \label{eq:freq_muestreada} y considerando que la señal tiene $N=100$ muestras, en la siguiente tabla, se presentan los valores de $k_0$ para diferentes valores de muestreo $T_m$

\begin{table}[htp]
\caption{Multiplos de la frecuencia $2 \pi /100$ para la señal $cos(15 \pi T_m n)$}
\begin{center}
\begin{tabular}{|c|c|}
	\hline
	$T_m$ & $k_0$ \\
	\hline
	$2/150$  & 10	\\
	\hline
	$4/150$  & 20	\\
	\hline
	$6/150$  & 30	\\
	\hline
	$8/150$  & 40	\\
	\hline
	$10/150$  & 50	 \\
	\hline
	$12/150$  & 60	 \\
	\hline
\end{tabular}
\end{center}
\label{default}
\end{table}

\begin{figure}[h!]
\begin{center}
\subfigure[$T_m = 2/150$]{\psfig{figure = TFourier/figuras/muestra_1.eps,width=4.5cm}} 
\subfigure[$T_m = 4/150$]{\psfig{figure = TFourier/figuras/muestra_2.eps,width=4.5cm}} 
\subfigure[$T_m = 6/150$]{\psfig{figure = TFourier/figuras/muestra_3.eps,width=4.5cm}} 
\subfigure[$T_m = 8/150$]{\psfig{figure = TFourier/figuras/muestra_4.eps,width=4.5cm}} 
\subfigure[$T_m = 10/150$]{\psfig{figure = TFourier/figuras/muestra_5.eps,width=4.5cm}} 
\subfigure[$T_m = 12/150$]{\psfig{figure = TFourier/figuras/muestra_6.eps,width=4.5cm}} 
\end{center}
\caption{TDF de la señal $cos(15\pi t)$ con diferentes valores de $T_m$} \label{fig:TDF_cos_muestreda}
\end{figure}

Note que cuando tenemos un periodo de muestreo $T_m = 12/150$ el múltiplo de frecuencia $k_0 = 60$. Si solamente tenemos múltiplos que van de $-N/2$ hasta $N/2$, tenemos el problema que no podemos representar la señal sin que se traslapen sus transformada.

\subsection{Teorema del muestreo de Nyquist}

De acuerdo con la antes expuesto tenemos una cuota máxima:
\[
k_0 < \frac{N}{2}
\]

donde $k_0$ es el múltiplo de nuestra frecuencia que queremos representar y $N/2$ es el múltiplo de frecuencia máxima que podemos representar.

En virtud de esto podemos calcular para una frecuencia $\omega_0$, muestreada con periodo $T_m$  el valor de $k_0$ utilizando (\ref{eq:freq_muestreada}) y sustituyendo en la ecuación anterior

\[
k_0 = \frac{N \omega_0 T_m}{2 \pi} < \frac{N}{2} 
\]
\[
\omega_0  < \frac{\pi}{T_m} 
\]
\[
2\omega_0 < 2 \frac{\pi}{T_m} 
\]

de donde se desprende la formulación del Teorema de Nyquist

\begin{equation}
2  \omega_0 < \omega_m \label{eq:Nyquist}
\end{equation}

donde $\omega_m$ es la frecuencia de muestreo y esta definida por $\frac{2 \pi}{T_m}$. Esta ecuación la podemos poner también como
\[
2\frac{2 \pi}{T_0} < \frac{2 \pi}{T_m}
\]
\[
2T_m < T_0
\]

Con esto podemos concluir que para una señal con ancho de banda $\omega_0$ tenemos que muestrear, si queremos recuperar la señal original, al menos a una frecuencia de dos veces el ancho de banda o que el periodo de muestreo tiene que ser al meno dos veces menor que el periodo de la señal.

En la figura \ref{fig:ejem_muestreo} se muestra una señal coseno, con un periodo $T_0 = 1333.33$, la cual fue muestreada con un periodo mayor que $T_m =28$. Para este caso podemos notar que la señal muestreada para nada luce como una señal de la frecuencia original y el Teorema de Nyquist no se cumple ya que $2T_0 > Tm$

\begin{figure}[h!]
{\normalsize \centering
\centerline{\psfig{figure = TFourier/figuras/ejem_muestreo.eps,width=8.0cm}} }
\caption{{\bf Ejemplo de una señal con bajo muestro}}
\label{fig:ejem_muestreo}
\end{figure}

\subsection{Transformada Discreta de Fourier de un tren de Pulso} 

La transformada de Fourier de una función $\delta(n-n_0)$  es una exponencial compleja dada por

\[
X[k] = e^{-\left(\frac{2 \pi }{N} n_0 \right  )k}
\]

La transformada de Furier de un tren de pulsos $p[n]$

\[
p[n] = \sum_{m=0}^{\frac{N}{T} -1} \delta(n - mT)
\]

por linealidad la podemos calcular utilizando

\[
P[k] = \sum_{m=0}^{\frac{N}{T} -1}  e^{-\left(\frac{2 \pi }{N} mT \right ) k}
\]

Utilizado la (\ref{eq:sum_util})  podemos ver que

\[
X[k] =\frac{1 - e^{-\left( \frac{2 \pi }{N} \frac{N}{T} T \right ) k}} {1- e^{-\left( \frac{2 \pi }{N} T \right ) k}} = 0
\]


Sin embargo cuando $m$ es múltiplo de $N /T$ tenemos que $e^{-\left(\frac{2 \pi }{N} \frac{N}{T} l T \right ) k}=1$ para $l=0, 1, 2, \dots $

\[
P[k] = 
\left \{
\begin{array}{cc}
  1 & m = 0    \\
  1 & m = \frac{N}{T}    \\
  1 & m = \frac{2N}{T} \\
  1 & m = \frac{3N}{T} \\
  \vdots & \vdots      
\end{array}
\right .
\]

de manera compacta lo podemos escribir como
\[
P[k] = \sum_{l=0}^{\infty} \delta\left(k-\frac{N}{T} l \right)
\]

Podemos concluir que la TDF de un tren de pulso con periodo $T$ es un tren de pulso con un periodo $N/T$. En la figura \ref{fig:tren_n} se muestra un tren de pulsos con periodo $T = 6$  y su TDF en \ref{fig:tren_k}. Note que el periodo de la TDF es $N/T = 25$, para una señal con $N=150$

\begin{figure}[h!]
\begin{center}
\subfigure[\label{fig:tren_n}Tren de pulsos con periodo 6]{\psfig{figure = TFourier/figuras/tren_n.eps,width=6cm}} 
\subfigure[\label{fig:tren_k}Transformada de Fourier ]{\psfig{figure = TFourier/figuras/tren_k.eps,width=6cm}}
\end{center} \label{fig:tren}
\caption{Tren de Pulsos y su transformada}
\end{figure}

\subsubsection{Señal muestrada con un tren de pulsos}

Una forma de muestrear una señal es multiplicando la señal $x[n]$ por un tren de pulso $p[n]$ cuya TDF esta dada por

\[
N x[n]p[n] \stackrel{\mathcal{F}}{\leftrightarrow } X[k]*P[k]
\]

En la figura \ref{fig:gauss_n} se muestra una Gaussiana $g(n;\mu, \sigma)$ con media $\mu = 0$ y varianza $\sigma = 10$, la cual se muestrea con un tren de pulsos $p(n;T)$, con periodo $T=6$, como el que se muestra en la figura \ref{fig:tren2_n}. La transformada de furier $G[k]$ de la Gaussiana se muestra en la figura \ref{fig:gauss_k}  y en la figura \ref{fig:tren2_k} la TDF del tren de pulsos. Finalmente en la figura \ref{fig:GP_k} se muestra la TDF de la función $g(n;0, 10)$ multiplicada por el tren de pulsos $p(n; 6)$

\begin{figure}[h!]
\begin{center}
\subfigure[\label{fig:gauss_n} $g(n; 0, 10)$]{\psfig{figure = TFourier/figuras/gn.eps,width=6cm}} 
\subfigure[\label{fig:gauss_k}TDF$(g(n;0,10))$ ]{\psfig{figure = TFourier/figuras/Gk.eps,width=6cm}}
\subfigure[\label{fig:tren2_n} $p(n;6)$ con periodo 6]{\psfig{figure = TFourier/figuras/tren_n.eps,width=6cm}} 
\subfigure[\label{fig:tren2_k}TDF$(p)$ ]{\psfig{figure = TFourier/figuras/tren_k.eps,width=6cm}}
\subfigure[\label{fig:GP_k}TDF$(g(n;0,10) p(n;6))$]{\psfig{figure = TFourier/figuras/GPk.eps,width=12cm}}
\end{center} \label{fig:tren2}
\end{figure}


Para el ejemplo de la figura \ref{fig:GP_k} podemos notar que tenemos una cuota superior que no debemos superar. Si definimos el ancho de banda $k_b$ como la mitad del tamaño de la Gaussiana, tenemos que para que la Gussiana no se mezcle con los datos de otra Gaussiana, se debe cumplir:

\[
2 k_b < \frac{N}{T_m}
\]

si multiplicamos ambos lados por $2\pi /N$

\[
2 \left( \frac{2 \pi}{N} \right) k_b < \left( \frac{2 \pi}{N} \right) \frac{N}{T_m}
\]

tenemos

\[
2 \left( \frac{2 \pi}{N} \right) k_b < \frac{2 \pi}{T_m} \
\]

\[
2 \omega_b < \omega_m
\]

que coincide con el resultado de la ecuación (\ref{eq:Nyquist}) del Teorema de Nyquist.

\section{Teorema del Muestreo señales continuas}
En esta sección se presenta todo el análisis con señales continuas a diferencia de la sección anterior donde se presento con señales discretas.

\subsection{Transformada de Fourier de una señal periódica}

Supongamos que una señal con periodo $T_0$ (con $\omega_0 =
\frac{2\pi}{T_0}$), pudiera representarse como la serie
\begin{equation}\label{eq:f_per}
x(t) =\sum_{k=-\infty}^{k=\infty} X[k] e^{j\omega_0kt}
\end{equation}

multiplicando ambos miembros de la ecuación por $e^{-jn\omega_0t}$ e integrando en el intervalo

\begin{equation*}
\int_{-\frac{T_0}{2}}^{\frac{T_0}{2}} x(t) e^{-jn\omega_0t} dt=
\int_{-\frac{T_0}{2}}^{\frac{T_0}{2}}\sum_{k=-\infty}^{k=\infty}
X[k] e^{j\omega_0kt}e^{-jn\omega_0t}dt
\end{equation*}
reagrupando los términos tenemos
\begin{equation*}
\int_{-\frac{T_0}{2}}^{\frac{T_0}{2}} x(t) e^{-jn\omega_0t} dt =
\sum_{k=-\infty}^{k=\infty} X[k] \left[
\int_{-\frac{T_0}{2}}^{\frac{T_0}{2}} e^{j\omega_0(k-n)t} \right
]dt
\end{equation*}

La evaluación de la integral en los corchetes es, considerando que $k\neq n$:

\begin{eqnarray*}
\int_{-\frac{T_0}{2}}^{\frac{T_0}{2}} e^{j\omega_0(k-n)t} dt&=&
\frac{1}{j(k-n)\omega_0}e^{j\omega_0(k-n)t}
|_{-\frac{T_0}{2}}^{\frac{T_0}{2}}\\
&=& \frac{1}{j(k-n)\omega_0 }\left[ e^{j(k-n)\pi} -
e^{-j(k-n)\pi}\right]\\
&=& \frac{1}{j(k-n)\omega_0 }\left[ -1 +1\right]\\
&=& 0\\
\end{eqnarray*}
en el caso de que $k=n$, la integral se transforma en
\begin{eqnarray*}
\int_{-\frac{T_0}{2}}^{\frac{T_0}{2}} dt &=& T_0
\end{eqnarray*}

Por lo tanto la transformada de Fourier de una señal periódica ecuación (\ref{eq:f_per}) es

\begin{equation}\label{eq:int_per}
X[n] = \frac{1}{T_0} \int_{-\frac{T_0}{2}}^{\frac{T_0}{2}} x(t) e^{-jn\omega_0t}
dt
\end{equation}

\subsection{Transformada de Furier de un Tren de Pulsos}

Un tren de pulsos lo podemos definir por

\begin{eqnarray*}
p(t)=\cdots +\delta \left( t+2T\right) +\delta \left( t+T\right) +\delta
\left( t\right) + \\
\delta \left( t-T\right) +\delta \left( t+2T\right) +\cdots
\end{eqnarray*}
la cual podemos representar en forma compacta como
\[
p(t)=\sum_{k=-\infty }^{\infty }\delta \left( t-kT\right)
\]
donde $T=\frac{2\pi }{\omega_s }$. Note que esta ecuación es una
función periódica y su transformada puede ser calculada utilizando
el resultado de la ecuación (\ref{eq:int_per})

En este caso hablamos de una transformada de Fourier continua por lo cual haremos la transformada de Fourier utilizando la definición continua

\[
P(\omega )=\int_{-\infty }^{+\infty }p(t)e^{-j\omega t}dt
\]

sustituyendo tenemos

\begin{eqnarray}
P(\omega )=\sum_{k=-\infty }^{\infty }\int_{-\infty }^{+\infty}\delta \left( t-kT\right) e^{-j\omega t}dt
\end{eqnarray}

Aplicando el resultado de la ecuación (\ref{eq:int_per}) tenemos

\begin{equation*}
P(\omega )=\sum_{k=-\infty }^{\infty
}\frac{1}{T_0}\int_{-\frac{T_0}{2}}^{\frac{T_0}{2}}\delta \left(
t-kT\right) e^{-j\omega t}dt
\end{equation*}

de donde se desprende que si $k=0$

\begin{equation*}
\frac{1}{T_0}\int_{-\frac{T_0}{2}}^{\frac{T_0}{2}}\delta \left(
t-kT\right) e^{-j\omega t}dt = \frac{1}{T}=\frac{1}{T}\delta (\omega - 0 \omega_s)
\end{equation*}

entonces da como resultado un tren de pulsos equiespaciados en la frecuencia con $\omega _{s}=\frac{2\pi }{T}$.

\[
P(\omega )=\sum_{k=-\infty }^{\infty }\delta \left( \omega -k\omega
_{s}\right)
\]


\subsection{Señal Muestreada en el Tiempo}

Una señal muestreada se calcula como
\[
x_{p}(t)=x(t)p(t)
\]

Esto significa que tenemos que hacer la convolución de la TDF de la señal $X[k]$ con un tren de pulsos $P[k]$. En la figura se muestra una función gaussiana 

donde $p(t)$ es un tren de pulsos. Aplicando el teorema de la convolución tenemos que la transformada de Fourier de esta señal es
\begin{eqnarray*}
X_{p}(\omega )=X(\omega )*P(\omega ) \\
X_{p}(\omega )=X(\omega )*\sum_{k=-\infty }^{\infty }\delta \left( \omega-k \omega _{m}\right) \\
=\sum_{k=-\infty }^{\infty }X(\omega -k\omega _m)
\end{eqnarray*}

lo cual significa que tendremos copias de nuestra señal $X(\omega )$ repetidas cada $\frac{2\pi }{T}$. ¿Pero que ocurre si el ancho de banda de la señal $X(\omega )$ sobre pasa el valor $\frac{2\pi }{T}$?.

Llamemos $\omega _{m}$ la frecuencia de muestreo la cual esta dada como
\[
\omega _{m}=\frac{2\pi }{T_m}
\]
y $\omega _{b}$ el ancho de banda de la señal $x(t)$, podemos ver que si
\[
\omega _{m}>2\omega _{b}
\]

podemos reconstruir exactamente la señal continua $x\left( t\right) $ a partir de la señal muestreada $x_{p}\left( t\right) $. La frecuencia de muestreo $\omega _{m}$ también se conoce como la frecuencia de Nyquist.

Podemos notar que

\[
x_{p}[n]=x(nT)=\frac{1}{2\pi }\int_{-\infty }^{\infty }X\left( \omega
\right) e^{j\omega nT}d\omega
\]

dado que la señal en el dominio de la frecuencia es periódica podemos considerar que

\[
x_{p}[n]=\frac{1}{2\pi }\sum_{r=-\infty }^{\infty }\int_{\left( 2r-1\right)
\pi /T}^{\left( 2r+1\right) \pi /T}X\left( \omega \right) e^{j\omega
nT}d\omega
\]

y cada término de la suma puede ser reducido a una integral sobre el rango $\frac{\pi }{T}$ a $\frac{\pi }{T}$ haciendo el cambio de variable $\omega=\Omega +\frac{2\pi r}{T}$

\[
x_{p}[n]=\frac{1}{2\pi }\sum_{r=-\infty }^{\infty }\int_{-\pi /T}^{\pi
/T}X\left( \Omega +\frac{2\pi r}{T}\right) e^{j\Omega nT}e^{j2\pi rn}d\Omega
\]

Si intercambiamos el orden de integración y considerando que $e^{j2\pi rn}=1$ para cualquier valor de $n$ y $r$, tenemos que:

\[
x_{p}[n]=\frac{1}{2\pi }\int_{-\pi /T}^{\pi /T}\left[ \sum_{r=-\infty
}^{\infty }X\left( \Omega +\frac{2\pi r}{T}\right) e^{j\Omega nT}\right]
d\Omega
\]

haciendo un cambio de variable $\Omega =\frac{\omega }{T}$%

\[
x_{p}[n]=\frac{1}{2\pi }\int_{-\pi }^{\pi }\left[ \frac{1}{T}\sum_{r=-\infty
}^{\infty }X\left( \frac{\omega }{T}+\frac{2\pi r}{T}\right) e^{j\omega
n}\right] d\omega
\]

de esta ecuación tenemos que

\[
X_{p}\left( \omega \right) =\frac{1}{T}\sum_{r=-\infty }^{\infty }X\left(
\frac{\omega }{T}+\frac{2\pi r}{T}\right)
\]

o si hacemos $\widehat{\omega }=\frac{\omega }{T}$ tenemos

\[
X_{p}\left( \widehat{\omega }T\right) =\frac{1}{T}\sum_{r=-\infty }^{\infty
}X\left( \widehat{\omega }+\frac{2\pi r}{T}\right)
\]

\subsection{Integración de la señal continua.}

Ahora que hacemos para recuperar la señal continua a partir de la señal muestreada. Puesto que la señal $X_{p}(\omega )$ solo esta definida en el rango $\left[ -\frac{\pi }{T},\frac{\pi }{T}\right] $, calcularemos la antitrasformada en estos límites, además $X_{p}\left( \omega T\right) =\frac{1}{T}X\left( \omega \right) $

\begin{eqnarray*}
x(t)=\frac{1}{2\pi }\int_{-\frac{\pi }{T}}^{+\frac{\pi }{T}}TX_{p}\left(
\omega T\right) e^{j\omega t}d\omega \\
=\frac{T}{2\pi }\int_{-\frac{\pi }{T}}^{+\frac{\pi }{T}}\left[
\sum_{n=-\infty }^{\infty }x\left( nT\right) e^{-j\omega nT}\right]
e^{j\omega t}d\omega \\
=\sum_{n=-\infty }^{\infty }x\left( nT\right) \left[ \frac{T}{2\pi }\int_{-%
\frac{\pi }{T}}^{+\frac{\pi }{T}}e^{j\omega \left( t-nT\right) }d\omega
\right] \\
=\sum_{n=-\infty }^{\infty }x\left( nT\right) \frac{sen\left( \frac{\pi }{T}%
\left( t-nT\right) \right) }{\left( \frac{\pi }{T}\right) \left( t-nT\right)
}
\end{eqnarray*}

El código para realizar esta integración es:
\begin{verbatim}
  public static double Interpola(double x[], double t, double T)
  {
    int n, N = x.length, i;
    double val =0;

    for(i=-3*N; i<3*N; i++)
    {
      n = (i % N);
      if(n<0) n = N + n;
      val += x[n] * Sinc( (t - (double) i * T) * Math.PI / T);
    }
    return val;
  }
\end{verbatim}

\subsection{Ejemplos}
\subsubsection{Ejemplo 1}

Aquella frecuencia que de acuerdo con el teorema de muestreo, debe ser excedida por la frecuencia de muestreo se llama razón de Nyquist. Determine la razón de Nyquist para las siguientes señales

a) $x(t)=1+\cos (2000\pi t)+sen(4000\pi t).$

La transformada de Fourier para esta señal es

\[
x[k]=\delta (0)+\frac{1}{2}\left[ \delta (w-2000\pi )+\delta
(w+2000\pi)\right] +\frac{j}{2}\left[ \delta (w-4000\pi )-\delta
(w+4000\pi )\right]
\]
lo cual indica que el espectro de frecuencia tendrá valores en el intervalo $\left[ -4000\pi ,4000\pi \right] $, o bien que $\omega_{b}=4000\pi .$ De acuerdo con esto la razón de Nyquist es $\omega_{s}=8000\pi .$

b) $x(t)=\frac{sen\left( 200\pi t\right) }{\pi t}$. Podemos ver que la antitransformada de Fourier de una caja es

\begin{eqnarray*}
x(t)=A\int_{-d}^{d}e^{j\omega t}d\omega \\
x(t)=\frac{A}{jt}\left. e^{^{j\omega t}}\right| _{-d}^{d} \\
x(t)=\frac{1}{jt}\left( 2j\right) sen\left[ dt\right] \\
x(t)=\frac{2Asen\left[ dt\right] }{t}
\end{eqnarray*}

de donde podemos ver que la transformada de Fourier de esta señal es una caja de ancho $d=200\pi $ y altura $A=\frac{1}{2\pi }$, por lo tanto su ancho de banda será de $\omega _{b}=200\pi $ y su razón de Nyquist será $\omega _{s}=400\pi .$

\subsubsection{Ejemplo 2}

Dada la señal continua $x(t) = sen^2(10 \pi t)$, calcular:

a) El ancho de banda correspondiente a esta señal

b) La transformada discreta de Fourier si la señal es muestreada en con periodo $T_s=\frac{5}{2N}$ segundos, con un número de muestras $N=128$.

c) Cual es la transformada discreta de Fourier si la señal es muestreada con un periodo del doble del anterior.

Para esta señal aplicando identidades trigonométricas tenemos que:
\begin{equation*}
x(t) = sen^2(10 \pi t) = \frac{1}{2} \left(1 - cos(20 \pi t)\right)
\end{equation*}

Respuestas

a) La frecuencia del primer termino es $\omega_0 = 0$ y del segundo termino es $\omega_1 = 20 \pi$, con lo cual tenemos que el ancho de banda es $\omega_b = 20 \pi$

b)En este caso la frecuencia de muestreo es $\omega_m = \frac{2\pi}{\frac{5}{2N}} = \frac{4N \pi}{5}$ considerando 128 muestras la frecuencia de muestreo es $\omega_m = 321.6991$, note que

\begin{eqnarray*}
\omega_m >= 2*\omega_b \\
321.6921 >= 40 \pi
\end{eqnarray*}

Nuestra señal cumple con el teorema del muestreo, ahora es necesario calcula $k$ de la frecuencia $\frac{2 \pi}{N}$ para ello

\begin{eqnarray*}
x_p[n] = x(nT) \\
x_p[n]= \frac{1}{2} \left( 1 - cos(20 \pi n T)\right)\\
x_p[n]= \frac{1}{2} \left( 1 - cos(\frac{2 \pi}{N}k n)\right)\\
\end{eqnarray*}

Por comparación podemos ver que $20 \pi T = \frac{2 \pi}{N}k$ con lo cual tenemos

\begin{eqnarray*}
\frac{2 \pi}{N}k &=&20 \pi T \\
k & = & \frac{20 \pi T N}{2 \pi}\\
k & = & \frac{20 \pi \frac{5}{2N} N}{2 \pi}\\
k & = & 25
\end{eqnarray*}

Con esto tenemos que la transformada Discreta de Fourier es

\begin{equation*}
X[k] = 64 \delta[k] - 32 \left(\delta(k-25) +
\delta(k+25))\right)
\end{equation*}

c) Si duplicamos el periodo de Muestreo $T_s = \frac{5}{N}$ aplicando los pasos anteriores tenemos

\begin{eqnarray*}
\frac{2 \pi}{N}k &=&20 \pi T \\
k & = & \frac{20 \pi T N}{2 \pi}\\
k & = & \frac{20 \pi \frac{5}{N} N}{2 \pi}\\
k & = & 50
\end{eqnarray*}
y la TDF es
\begin{equation*}
X[k] = 64 \delta[k] - 32 \left(\delta(k-50) +
\delta(k+50))\right)
\end{equation*}

Note como la frecuencia de muestreo afecta la transformada discreta de Fourier.

\subsubsection{Ejemplo 3}
Para el ejemplo anterior considerando un periodo de muestreo $T_s = 0.0390625$, calcular utilizando el código dado y los valores muestreados $x_p[n]$, los valores de la función en $t=T$, $t=1.5T$ y $t=2.0 T$.

Solución

Para llenar el arreglo dada la función $x(t) = sen^2(10\pi t)$ se hizo

\begin{equation*}
x_p[n] = sen^2(10 \pi n T)
\end{equation*}

Al aplicar

\begin{center}
\begin{tabular}{|c|c|c|c|}
  \hline
  & t & calculados & valores reales \\
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  T       & 0.0390625 & 0.886505 & 0.886505 \\
  1.5 T & 0.05859375 & 0.928864 & 0.928864 \\
  2.0 T & 0.078125 & 0.402455 &  0.402455 \\
  \hline
\end{tabular}
\end{center}

