\documentclass[10pt,a4paper]{article}

%% Polonizacja
\usepackage[T1]{fontenc}
\usepackage[latin2]{inputenc}
\usepackage{polski}
\usepackage{indentfirst}

%% Wzorki matematyczne
\usepackage{amsmath,amsfonts}

%% Zewnętrze odnośniki
\usepackage{xr}
\externaldocument[fft:]{fft}

\newcommand{\vect}[1]{\ensuremath{\mathbf{#1}}}


\begin{document}

\title{
  Zadania do Metod Numerycznych II A\\
  Grupy 2, 3. Seria 3.\\[1 ex]
  \large
   Dyskretna transformata Fouriera i jej zastosowania}
\author{Jakub Narębski}
\date{25.05.2001~r.}
\maketitle


\section{Obliczenie dyskretnej transformaty Fouriera z definicji}
\label{sec:obliczanie-TF}

Napisać program obliczający zespoloną dyskretną transformatę Fouriera
z~jej definicji:
\begin{equation}
  \label{eq:DFT}
  H_n = \sum_{k=0}^{N-1} h_k e^{2 \pi \imath k n/N}
\end{equation}
gdzie $\imath$ oznacza jednostkę urojoną (t.j. ze wzoru~(15)
w~\texttt{four.ps} albo~\eqref{fft:eq:FT} w~\texttt{fft.ps}).
Sprawdzić, czy odwrotna transformata Fouriera, zadana wzorem:
\begin{equation}
  \label{eq:rev-DFT}
  h_k = \frac{1}{N} \sum_{n=0}^{N-1} H_n e^{-2 \pi \imath k n / N}
\end{equation}
przeprowadza otrzymaną tablicę $H$ z~powrotem w~oryginalną 
funkcję. 

Można przykładowo wziąć funkcję zadaną wzorem (wypełnić tablicę $h$ w
następujący sposób):
\begin{align*}
  h_k &= \sin(2 \pi k/N) + \imath\, 0 \\
  h_k &= \exp(\imath 2 \pi 8k/N) \\
  h_k &= 
  \begin{cases}
    \;1 & \quad\text{dla $k < N/2$} \\
    \;\imath & \quad\text{dla $k \geq N/2$} \\
  \end{cases}
\end{align*}
  
Zrobić wykres oryginalnej funkcji, jej transformaty Fouriera oraz
odwrotnej transformaty Fouriera transformaty Fouriera. Narysować część
rzeczywistą i~urojoną lub moduł (wartość bezwględną). Pod Linuksem
można to zrobić za pomocą programu \texttt{gnuplot} poleceniem
(zakładając, że do pliku \textit{h.dat} zostały zapisane kolejne
elementy tablicy $h$, w~każdym wierszu część rzeczywista i~część
urojona (oddzielone np. spacją)):
\begin{flushleft}
  \ttfamily 
%%%
  plot '\textit{h.dat}' using 1 title "re(h)"
  with linespoints\\
  replot '\textit{h.dat}' using 2 title "im(h)"
  with linespoints\\
  replot '\textit{h.dat}' using (abs(\{\$1,\$2\})) title "abs(h)"
  with linespoints
\end{flushleft}
i~analogicznie dla transformaty Fouriera (zapisanej np. w~pliku
\textit{H.dat} lub jako następne kolumny jednego pliku z~danymi), oraz
transformaty odwrotnej.
  
Polecenie \texttt{replot} powoduje wykreślenie dodatkowych danych na
bieżącym wykresie. Można pominąć fragment \texttt{with linespoints}:
służy on do określenia sposobu wykreślania danych (tutaj: punkty
połączone liniami). \texttt{\{a,b\}} oznacza w~gnuplocie liczbę
zespoloną $a + \imath b$. Argument \texttt{using} z~następującym po
nim wyrażeniem określa jakie dane będą wykreślone na wykresie.
Patrz także \texttt{help plot datafile} w~gnuplocie.


\section{Właściwości transformaty Fouriera}
\label{sec:wlasciwosci-TF}

Napisać program sprawdzający własności transformaty Fouriera.
Sprawdzić jakie własności ma transformata Fouriera funkcji
\begin{list}{\textbullet}{}
\item rzeczywistej, parzystej
\item rzeczywistej, nieparzystej
\item urojonej, parzystej
\item urojonej, nieparzystej
\end{list}
gdzie \emph{nieparzystość} oznacza, że $h_k = h_{N - k} \equiv
h_{-k}$.  

\textbf{Uzupełnienie:} sprawdzić własność tzw. \emph{aliasingu},
t.j. wykreślić funkcję o~częstości większej od {\bfseries krytycznej częstości
Nyquista} $2/N$, jej wartości w~punktach próbkowania, jej
dyskretną transformatę Fouriera oraz transformatę odwrotną.

Przykładową funkcją może być $h(t) = sin(2 \pi \frac{3}{2}N t)$, gdzie
$t_k = k/N$, zaś $h_k = h(t_k)$.


\section{Filtrowanie przy użyciu transformaty Fouriera}
\label{sec:filtrowanie}

Zrobić prosty filtr przy użyciu dyskretnej transformaty Fouriera, tzn.
obliczyć transformatę Fouriera, wyciąć odpowiednie częstości
(pamietając o~tym, że dla zwykłej, zespolonej dyskretnej transformaty
Fouriera po indeksie $N/2$ następują częstości ujemne, t.j. $H_{N-n}
\equiv H_{-n}$ dla $n > \frac{N}{2}$). Przykładem może być prosty
filtr pasmowy: wycinamy nieporządane częstości. Mogą być usuwane częstości
wysokie jeśli wiemy, że sygnał badany jest wolnozmienny; częstości
niskie jeśli chcemy usunąć wolnozmienny trend. Możemy też sostawić
tylko częstości w~pewnym zakresie wokół danej częstości, jeżeli sygnał
jest sygnałem o~modulowanej amplitudzie lub częstości).

\textbf{Uzupełnienie:} zrobić to także przy użyciu rzeczywistej
transformaty Fouriera, wylicznej za pomocą własnej procedury (na
podstawie \texttt{fourrsc.ps}) lub procedury \texttt{realft} z
,,Numerical Recipies in C'' (zawartej w~pliku \texttt{fft\_NRC.tar}).

\vfill

\begin{flushright}
  Jakub Narębski
\end{flushright}

\end{document}