\documentclass[11pt,leqno]{article}
\usepackage{amssymb, amsmath} 
\usepackage{latexsym} 
\usepackage{graphics} 
\usepackage[hyphens]{url}
%\def\UrlBreaks{\do\/\do-}
\expandafter\def\expandafter\UrlBreaks\expandafter{\UrlBreaks% save the current one
  \do\a\do\b\do\c\do\d\do\e\do\f\do\g\do\h\do\i\do\j%
  \do\k\do\l\do\m\do\n\do\o\do\p\do\q\do\r\do\s\do\t%
  \do\u\do\v\do\w\do\x\do\y\do\z\do\A\do\B\do\C\do\D%
  \do\E\do\F\do\G\do\H\do\I\do\J\do\K\do\L\do\M\do\N%
  \do\O\do\P\do\Q\do\R\do\S\do\T\do\U\do\V\do\W\do\X%
  \do\Y\do\Z\do\*\do\-\do\~\do\'\do\"\do\-}%

\usepackage{xcolor}
\usepackage{hyperref} 


%\usepackage[notcite,notref,color]{showkeys}


%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% 	SPANISH
%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage[spanish]{babel}
\usepackage[latin1]{inputenc}
%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% 	FORMAT
%%%%%%%%%%%%%%%%%%%%%%%%%%
%\setlength{\textheight}{23.0cm}
\setlength{\textwidth}{15.75cm}
\setlength{\oddsidemargin}{0.5cm}
\setlength{\evensidemargin}{0.5cm}
%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% 	COUNTERS
%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcounter{ejeno}
\setcounter{ejeno}{1}


%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% 	MACROS
%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\R}{{\mathbb R}} 
\newcommand{\C}{{\mathbb C}} 
\newcommand{\N}{{\mathbb N}} 
\newcommand{\Z}{{\mathbb Z}} 
\newcommand{\Q}{{\mathbb Q}} 


\newcommand{\ejer}{\ \par\vspace{-7pt}{\bf\number\value{ejeno})\ }\addtocounter{ejeno}{1}}


\usepackage{listings}


\lstdefinelanguage{Sage}[]{Python}
{morekeywords={False,sage,True},sensitive=true}

\lstset{
  frame=none,
  showtabs=False,
%  showtabs=True,
  showspaces=False,
  showstringspaces=False,
%  showstringspaces=True,
  commentstyle={\ttfamily\color{green!30!black}},
  keywordstyle={\ttfamily\color{blue!30!black}\bfseries},
  stringstyle={\ttfamily\color{gray!30!black}\bfseries},
%  language=Sage,
%  basicstyle={\fontsize{10pt}{10pt}\ttfamily},
  basicstyle=\footnotesize,
%  basicstyle={\fontsize{10pt}{10pt}\rmfamily},
  aboveskip=0.6em,
  belowskip=0.5em,
%  numbers=left,
%  numberstyle=\footnotesize
  xleftmargin=25pt
}

%\lstset{framexleftmargin=5mm, frame=shadowbox, rulesepcolor=\color{blue}}



\begin{document}
\pagestyle{myheadings}
\markboth{}{\rm\textsf{\jobname}\qquad\hfill}


Esta hoja y las sucesivas, la previsión es que haya cinco en total, las iré poniendo en 
\url{http://matematicas.uam.es/~fernando.chamizo/supervision/TFG/tfg.html} donde se encuentra la propuesta inicial de los contenidos.
La fuente {\LaTeX}, en los ficheros \verb!MC24hoja*.tex!, te será muy útil como plantilla y para poder copiar fórmulas y referencias.
Más o menos imita el formato indicado en la guía docente. De todas formas, seguramente es más adecuado, para ahorrar tiempo, que las entregas de cada hoja las incluyas en la plantilla oficial del TFG que puedes descargar en Moodle.  

\

Antes de nada, quisiera aclarar que el término ``señales'' que aparece en el título de la propuesta y que usaré en lo sucesivo, está poco definido matemáticamente, es más propio de la ingeniería. Para nosotros, una señal será simplemente una función (por ejemplo, en gran parte de esta hoja de $\{0,1,\dots, N\}$ en $\C$) que pensamos que contiene alguna información relevante. 

\bigskip




Fijemos una par de cosas sobre la notación. La primera es que usaremos la abreviatura
\[
 {\setlength\fboxrule{1.2pt}\boxed{\ e(x) \quad\text{para indicar}\quad e^{2\pi i x}\ }}
\]
la cual no es universal en análisis. Te recomiendo destacarla en tu trabajo y en tu presentación porque nada garantiza que esta notación sea familiar a quien los vaya a juzgar. 
La segunda es que $\langle \vec{a},\vec{b}\rangle$ denotará el producto escalar. Tomaremos $\langle \vec{a},\vec{b}\rangle=\sum_j \overline{a}_j b_j$ como producto escalar usual en $\C^n$. En álgebra lineal hay cierta tradición en poner el conjugado sobre las $b_j$. No lo haremos aquí porque choca con la costumbre en otras áreas de las matemáticas más cercanas al tratamiento de señales.  
\medskip 

Esta hoja está dedicada a aspectos básicos del análisis de Fourier discreto y continuo. Nos centraremos sobre todo en el primero que quizá no hayas visto nunca.


Una señal dada por $N$ valores reales o complejos $\{x_n\}_{n=0}^{N-1}$, por ejemplo, correspondientes a diferentes instantes de tiempo, se puede representar como el vector 
$\vec{x}=(x_0,x_1,\dots,x_{N-1})$.
Se llama \emph{transformada de Fourier discreta}, abreviada como DFT por sus siglas en inglés, al vector
\[
 \text{DFT}(\vec{x})
 =
 (\widehat{x}_0,\widehat{x}_1,\dots,\widehat{x}_{N-1})
 \qquad\text{con}\qquad 
 \widehat{x}_n
 =
 \sum_{m=0}^{N-1}
 x_m\,
 e\Big(-\frac{nm}{N}
 \Big).
\]

\ejer
Sea 
$\vec{v}_n
=
\Big(
e\big(\frac{0\cdot n}{N}\big),
e\big(\frac{1\cdot n}{N}\big),
\dots
,
e\big(\frac{(N-1)\cdot n}{N}\big)
\Big)$. 
Comprueba que $\{\vec{v}_0,\dots,\vec{v}_{N-1}\}$ es una base ortogonal de $\C^N$ y deriva de ello la 
\emph{fórmula de inversión} de la DFT:
\[
 x_n
 =
 \frac{1}{N}
 \sum_{m=0}^{N-1}
 \widehat{x}_m
 e\Big(\frac{nm}{N}
 \Big).
\]
Esta operación sobre los $\widehat{x}_m$ se suele indicar con $\text{IDFT}$, de esta forma, $\text{IDFT}\big(\text{DFT}(\vec{x})\big)=\vec{x}$. 
{\sf Indicación}: Justifica que si $\mathcal{B}=\{\vec{u}_0,\dots,\vec{u}_{N-1}\}$ son ortonormales no nulos, forman una base y las coordenadas de un vector arbitrario $\vec{v}$ en $\mathcal{B}$ son $\langle \vec{u}_n,\vec{v}\rangle$.

\ejer
Continuando un argumento de álgebra lineal, deduce también la \emph{identidad de Parseval}
$\langle \vec{x},\vec{y}\rangle
=
\frac 1N
\big\langle \text{DFT}(\vec{x}),\text{DFT}(\vec{y})\big\rangle$, 
que implica 
$\| \vec{x}\|^2
=
\frac 1N
\big\|\text{DFT}(\vec{x})\big\|^2$ (de hecho, se puede probar que ambas fórmulas son equivalentes).  
\medskip

El siguiente ejercicio es solo para que practiques con las fórmulas, no tiene especial interés. Si te falta espacio, no lo incluyas en tu TFG. 

\ejer
Calcula la DFT de $\big\{\cos\big(\frac{7\pi}{8}n\big)\big\}_{n=0}^{15}$ escribiendo el resultado de la manera más simplificada posible. Indica la igualdad que se obtiene al aplicar la identidad de Parseval para $\|\vec{x}\|^2$. 
{\sf Indicación}: $\cos(2\pi x)=\frac 12\big( e(x)+e(-x)\big)$. 
\medskip

Al igual que los coeficientes de Fourier que has visto en el grado, las coordenadas de la DFT indican el contenido en frecuencias. De cara a las aplicaciones hay dos inconvenientes menores. El primero es que si uno parte de $\vec{x}\in\R^N$ en general $\text{DFT}(\vec{x})\not\in\R^N$. Dependiendo del {\sl software} disponible, esto puede ser un problema. 
El segundo es más sutil. Gracias a la igualdad 
$e\big(\frac{nm}{N}\big)=e\big(\frac{n(N-m)}{N}\big)$, en la fórmula de inversión $\widehat{x}_m$ y  $\widehat{x}_{N-m}$ multiplican ambos a algo de frecuencia $m/N$, pues oscila $m$ veces en $[0,N)$. Así, subíndices altos no implica frecuencias altas, lo cual es un poco lioso cuando uno quiere filtrar señales. 

Estas dos dificultades se resuelven con una nueva transformada, algo menos importante que la DFT, pero, también, ampliamente usada. Es la \emph{transformada de coseno discreta}\footnote{Técnicamente esta es la DCT-II, hay otras tres DCT (e incluso se amplían con 4 más \cite{strang}), pero son mucho menos importantes. Si tienes curiosidad, mira \cite{wiki_dct}.}, abreviada por sus siglas en inglés DCT, que se define para 
$\vec{x}=\{x_n\}_{n=0}^{N-1}\in\C^N$
como 
\[
 \text{DCT}(\vec{x})
 =
 (\widehat{x}_0^c,\widehat{x}_1^c,\dots,\widehat{x}_{N-1}^c)
 \qquad\text{con}\qquad 
 \widehat{x}_n^c=
\sum_{m=0}^{N-1} x_m\cos\Big(\frac{\pi n}{N}\big(m+\frac 12\big)\Big).
\]

Seguro que te preguntas de dónde sale esta fórmula tan rara. En realidad la DCT es la DFT aplicada a una señal simetrizada (véase el siguiente ejercicio) para evitar la aparición de números complejos y discontinuidades. En \cite{wiki_dct} hay una figura que muestra gráficamente cómo se hace tal simetría con diferentes tipos de DCT. Como indica la nota anterior, te tienes que fijar en la DCT-II. 

\ejer
Dada una señal $\vec{x}\in\C^{N}$,
sea $\vec{y}\in\C^{2N}$ la señal  definida por $y_n=x_n$ si $0\le n<N$ e $y_n=x_{2N-1-n}$ si $N\le n<2N$.
Consideremos los subíndices de $\widehat{y}_n$ módulo $2N$, por ejemplo, $\widehat{y}_{-1}$ se define como $\widehat{y}_{2N-1}$. 
Prueba que para $|n|\le N$ se tiene:
\[
  \widehat{y}_n
  =
  \sum_{m=0}^{N-1}
  x_me\Big(-\frac{nm}{2N}\Big)
  +
  \sum_{m=N}^{2N-1}
  x_{2N-1-m}e\Big(-\frac{nm}{2N}\Big)
  =
  \sum_{m=0}^{N-1}
  x_m
  \bigg(
  e\Big(-\frac{nm}{2N}\Big)
  +
  e\Big(\frac{n(m+1)}{2N}\Big)
  \bigg).
\]

\ejer
Utilizando el ejercicio anterior, prueba que 
$\widehat{y}_n=
2e\big(\frac{n}{4N}\big)\widehat{x}^c_{|n|}$
para $|n|<N$ e 
$\widehat{y}_N=0$.
Con ello y con la fórmula de inversión para la DFT, deduce la \emph{fórmula  de inversión} para la DCT:
\[
 x_m=
 \frac{\widehat{x}_0^c}{N}+\frac{2}{N}
 \sum_{n=1}^{N-1} \widehat{x}_n^c\cos\Big(\frac{\pi n}{N}\big(m+\frac 12\big)\Big).
\]
En analogía con la DFT, a esta operación sobre los $\widehat{x}_n^c$ se le llama IDCT y entonces la fórmula de inversión afirma  
$\text{IDCT}\big(\text{DCT}(\vec{x})\big)=\vec{x}$. 
\medskip 

En la DFT
$\widehat{x}_n$
y 
$\widehat{x}_{N-n}$
daban ambas el contenido en la frecuencia $n/N$ mientras que en la DCT,
$\widehat{x}_n^c$
representa el contenido en la frecuencia $n/(2N)$, ahora sí un $n$ grande corresponde a una frecuencia grande. 
\medskip 

Veamos todo esto en un ejemplo práctico. Puedes  usar matlab, octave, sagemath o el paquete o lenguaje que prefieras. Para incorporar código en tu trabajo, revisa cómo uso el paquete \texttt{listings} en la fuente \LaTeX{} de este documento. Para insertar imágenes mira \cite[\S9.2]{ch_latex}.

Consideremos las funciones 
\[
 f(x)=
 4\Big(\frac{x}{117}\Big)^2\Big(1-\frac{x}{117}\Big)^2
 \qquad\text{y}\qquad 
 g(x)=
 \Big|
 \frac{2}{9}x-
 \big\lfloor \frac{2}{9}x+\frac 12 \big\rfloor
 \Big|
 -\frac14
\]
donde $\lfloor x\rfloor$ indica la parte entera. La primera función es bastante suave en el intervalo $[0,59)$, mientras que la segunda oscila unas~13 veces. La señal 
$\vec{x}=\{f(n)+0.02g(n)\}_{n=0}^{58}\in\R^{59}$
puede considerarse como una perturbación con ruido periódico de 
$\vec{s}=\{f(n)\}_{n=0}^{58}$. Para dibujar ambas y guardar los resultados en ficheros, se podría usar el siguiente código sagemath:
\lstset{language=Sage}
\begin{lstlisting}
f = 4*(x/117)^2 * (1 - x/117 )^2
g = abs( 2/9*x - floor(2/9*x+1/2) ) - 1/4
p = f + 0.02*g
list_plot([f(x=nn) for nn in srange(N)]).save('./fichero1.png')
list_plot([p(x=nn) for nn in srange(N)]).save('./fichero2.png')
\end{lstlisting}
Si prefieres usar octave o matlab, en \cite[\S1.5,\S1.9]{ch_cni} hay una descripción rápida acerca de cómo dibujar y almacenar en ficheros.

\ejer
Haz un programa para limpiar $\vec{x}$ siguiendo el procedimiento: $\vec{x}\mapsto \text{IDCT}\big(H_{10}(\vec{x})\big)$ donde 
$H_{10}(\vec{x})=(\widehat{x}_0^c,\widehat{x}_1^c,\dots, \widehat{x}_9^c,0,0,\dots, 0)$. 
Si el programa está bien, apenas notarás diferencia entre el resultado y $\vec{s}$. A la luz de lo que has aprendido, explica por qué este procedimiento ha funcionado. 

\ejer
Cambia $H_{10}(\vec{x})$ por
$H_{k}(\vec{x})=(\widehat{x}_0^c,\widehat{x}_1^c,\dots, \widehat{x}_{k-1}^c,0,0,\dots, 0)$ con $0<k\le 59$ y experimenta con tu programa para dar un rango aproximado de valores de $k$ para los que  la limpieza sea satisfactoria. Explica el resultado. 
\medskip

Estas transformaciones discretas en algunas aplicaciones se usan sobre señales muy largas, con $N$ grande, y se vuelve crucial llevar a cabo las operaciones de forma eficiente. En principio, el cálculo de $\widehat{x}_n$ requiere $N$ multiplicaciones y como hay $N$ valores de $n$, parece que nada nos libra de al menos $N^2$ multiplicaciones para calcular la DFT. Sorprendentemente, hay un algoritmo llamado FFT (por {\sl Fast Fourier Transform}) que cuando $N$ es una potencia de dos (un caso importante) reduce enormemente esta cota. 

\ejer
Lee en el PDF que te adjunto (las primeras dos páginas son de \cite{bremaud}) o en \cite{wiki_fft} sobre la FFT y escribe alrededor de una página acerca de ella. Intenta bien explicar la idea básica, no hace falta que te metas en muchos detalles. 
\medskip

Una vez que hemos visto el análisis de Fourier discreto, repasemos el continuo que deberías conocer del grado. 

Recuerda que una función $f$ que sea  
$1$-periódica y que tenga regularidad suficiente, por ejemplo Lipschitz, coincide con su serie de Fourier, esto es, 
\[
 f(x)
 =
 \sum_{n\in\Z} f_n\, e(nx)
 \qquad\text{con}\quad 
 f_n 
 =
 \int_0^1 
 f(t)\, e(-nt)\, dt.
\]
Dicho sea de paso, 
dos buenas referencias si quieres repasar el análisis de Fourier son \cite{DyMc} y \cite{korner}. 

Usando sumas de Riemann, este desarrollo de Fourier se puede ver como un límite de la fórmula de inversión de la DFT cuando $N\to\infty$, aunque no lo haremos aquí. 

\ejer
Sea $G(x)=g(9x/2)$ con $g$ como en el problema práctico. Comprueba que es $1$-periódica y utiliza la serie de Fourier para probar:
\[
 G(x)=-\frac{2}{\pi^2}
 \sum_{k=0}^\infty
 \frac{\cos\big(2\pi (2k+1)x\big)}{(2k+1)^2}.
\]
No hace falta que entres en consideraciones sobre la regularidad, puedes dar por hecho que $G$ es Lipschitz.
\medskip

El análogo de los coeficientes de Fourier para una función $f:\R\longrightarrow\C$ no periódica es la \emph{transformada de Fourier} definida mediante
\[
 \widehat{f}(\xi)
 =
 \int_{-\infty}^\infty
 f(x)\, e(-\xi x)\, dx. 
\]
Esta integral tiene sentido (Lebesgue) para $f\in L^1(\R)$. La \emph{fórmula de inversión} 
\[
 f(x)
 =
 \int_{-\infty}^\infty
 \widehat{f}(\xi)
 \, e(-x\xi)\, d\xi 
\]
recupera $f$ a partir de $\widehat{f}$ y es más exigente con la regularidad. Es cierta para \emph{funciones de decaimiento rápido} \cite[\S2.2]{DyMc}, aunque modificando un poco el sentido de las integrales se puede extender a $L^2(\R)$ \cite[\S2.3]{DyMc}.

Para series e integrales de Fourier, la \emph{identidad de Parseval} es, respectivamente,
\[
 \langle f,g\rangle
 =
 \big\langle \{f_n\}_{n\in\Z},\{g_n\}_{n\in\Z}\big\rangle
 \qquad\text{y}\qquad
 \langle f,g\rangle
 =
 \langle \widehat{f},\widehat{g}\rangle
\]
donde el producto escalar de funciones es el habitual en $L^2$, esto es, $\int_0^1\overline{f}g$ en el primer caso y $\int_{-\infty}^\infty\overline{f}g$ en el segundo, y el de sucesiones es el de $\ell^2$, esto es, el segundo miembro de la primera igualdad significa $\sum_{n\in\Z}\overline{f}_ng_n$.
\medskip 

Es conveniente conocer que la trasformada de Fourier de $e^{-\pi x^2}$ es ella misma y, en general que la de $f(x)=e^{-\alpha \pi x^2}$ con $\alpha>0$ es $\widehat{f}(\xi)=\alpha^{-1/2}\,e^{-\pi x^2/\alpha }$.

\ejer
Escribe una prueba de esta última afirmación adaptando la de \cite{pwiki_gaussian}. 
\medskip

Un último comentario solo para tu información: hay una manera de unificar la DFT, las series de Fourier, la transformada de Fourier y otros objetos similares. Dentro del marco del análisis armónico en grupos abelianos localmente compactos, todos son casos particulares de una transformada de Fourier general que satisface una fórmula de inversión. Lo único que varía es el grupo que se considera.  Si tienes interés en ello, hay un introducción en \cite{katznelson}. 


\



\begin{center}
\noindent\rule{0.95\textwidth}{1.1pt}
\end{center}


\paragraph{Tarea a entregar.}
Debes escribir un documento que combine las soluciones de los ejercicios anteriores.   La extensión es libre con una fuerte recomendación de que no superes las 7 páginas con el formato de esta hoja o de la plantilla, sin contar la bibliografía ni el listado del programa (que pasará a un apéndice), para que no tengamos que hacer muchos recortes al final.   Es mucho más importante poner buenas explicaciones que detalles en los cálculos.  El resultado debe dar lugar a un primer capítulo de tu TFG  llamado {\sl Análisis de Fourier discreto y continuo} o algo parecido. 

\begin{center}
\noindent\rule{0.95\textwidth}{1.1pt}
\end{center}

\begin{thebibliography}{10}

\bibitem{bremaud}
P.~Br{\'{e}}maud.
\newblock {\em Mathematical principles of signal processing}.
\newblock Springer-Verlag, New York, 2002.
\newblock Fourier and wavelet analysis.

\bibitem{ch_cni}
F.~Chamizo.
\newblock Pr\'acticas de {C}\'alculo {N}um\'erico {I} en la {UAM}.
\newblock
  {\small\url{https://matematicas.uam.es/~fernando.chamizo/libreria/fich/APcni.pdf}},
  Curso 2021/2022.

\bibitem{ch_latex}
F.~Chamizo.
\newblock {LaTeX} en la {UAM} en diez lecciones.
\newblock
  {\small\url{https://matematicas.uam.es/~fernando.chamizo/libreria/fich/APlatex24.pdf}},
  Curso 2023/2024.

\bibitem{DyMc}
H.~Dym and H.~P. McKean.
\newblock {\em Fourier series and integrals}.
\newblock Probability and Mathematical Statistics, No. 14. Academic Press, New
  York-London, 1972.

\bibitem{katznelson}
Y.~Katznelson.
\newblock {\em An introduction to harmonic analysis}.
\newblock Cambridge Mathematical Library. Cambridge University Press,
  Cambridge, third edition, 2004.

\bibitem{korner}
T.~W. K\"{o}rner.
\newblock {\em Fourier analysis}.
\newblock Cambridge Mathematical Library. Cambridge University Press,
  Cambridge, 2022.
\newblock With a foreword by T. Tao.

\bibitem{pwiki_gaussian}
{Pr$\infty$fWiki contributors}.
\newblock Fourier {T}ransform of {G}aussian {F}unction --- {Pr$\infty$fWiki}.
\newblock
  {\footnotesize\url{https://proofwiki.org/w/index.php?title=Fourier_Transform_of_Gaussian_Function&oldid=668452}},
  2023.
\newblock [Online; accessed 26-December-2023].

\bibitem{strang}
G.~Strang.
\newblock The discrete cosine transform.
\newblock {\em SIAM Rev.}, 41(1):135--147, 1999.

\bibitem{wiki_fft}
{Wikipedia contributors}.
\newblock Cooley{-}{T}ukey {FFT} algorithm --- {Wikipedia}{,} the free
  encyclopedia.
\newblock
  {\small\url{https://en.wikipedia.org/w/index.php?title=Cooley%E2%80%93Tukey_FFT_algorithm&oldid=1237705262}},
  2024.
\newblock [Online; accessed 21-August-2024].

\bibitem{wiki_dct}
{Wikipedia contributors}.
\newblock Discrete cosine transform --- {Wikipedia}{,} the free encyclopedia.
\newblock
  {\small\url{https://en.wikipedia.org/w/index.php?title=Discrete_cosine_transform&oldid=1237214220}},
  2024.
\newblock [Online; accessed 20-August-2024].

\end{thebibliography}


%\bibliography{bibtfg24MC}
%\bibliographystyle{plain}

\end{document}

