\documentclass[a4paper]{scrartcl}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{ngerman}
\usepackage[dvips]{graphicx}
\usepackage{ulem}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{array}
\usepackage{booktabs}
\usepackage{listings}
\usepackage{color} % f{\"u}r den grauen Hintergrund

%\usepackage{endnotes}

\setlength{\parindent}{0 em}

\definecolor{Gray}{gray}{0.9}

\lstset{basicstyle=\ttfamily\scriptsize,
backgroundcolor=\color{Gray}, numbers=left, numberstyle=\tiny,
stepnumber=1, numbersep=5pt}

\DeclareGraphicsExtensions{.eps}

%\DeclareGraphicsRule{.gif}{eps}{}{`convert #1 'eps:-'}

  \setcounter{MaxMatrixCols}{11}

\begin{document}
\begin{center}
\textbf{\huge{Runde 9, Beispiel 57}}

\Large{LVA 118.181, {\"U}bungsrunde 9, 12.01.2007}

\large{Markus Nemetz, \emph{markus.nemetz@tuwien.ac.at}, TU Wien,
13.01.2007}
\end{center}

\section{Angabe}
Seien $y,z \in \mathbb{C}^N$ und $c,d \in \mathbb{C}^N$ ihre
Spektralwerte. Außerdem bezeichne $(x_k)_k$ die ''N''-periodische
Fortsetzung des Vektors $x \in \mathbb{C}^N$ sowie $\omega =
e^{2\pi i/N}$. Zeigen Sie, daß die sogenannte periodische Faltung
gilt:

\begin{gather*}
    y \cdot z := (\frac{1}{N} \sum_{t=0}^{N-1} y_{\mathcal{l}} z_{k -
    \mathcal{l}})_k \, \, \overbrace{\longrightarrow}^{\text{DFT}} \,
    \, (c_k \cdot d_k)_k
\end{gather*}

\section{Lösung des Beispiels}
Gegeben seien die periodischen Folgen $\tilde{x}_1[n]$ und
$\tilde{x}_2[n]$ mit der Periodendauen N. Ihre diskreten
Fouriertransformierten (DFT) sind gegeben durch:
\begin{gather*} \tilde{X}_1(k) = {1\over N} \sum_{m=0}^{N-1} \tilde{x}_1[m]
W_N^{mk}\\
\tilde{X}_2(k) = {1\over N} \sum_{r=0}^{N-1} \tilde{x}_2[r]
W_N^{rk} \end{gather*}

Wir definieren eine neue Folge $\tilde{x}_3[n]$, die sich wie
folgt bildet:
\begin{gather*} \tilde{X}_3(k) = \tilde{X}_1(k) \cdot \tilde{X}_2(k) \nonumber \end{gather*}

$\tilde{x}_3[n]$ ergibt sich durch die IDFT
\begin{gather*} \tilde{x}_3[n] = IDFT\{ \tilde{X}_3(k) \} \nonumber\\ \tilde{x}_3[... ...\sum_{k=0}^{N-1} \tilde{X}_1(k) \cdot \tilde{X}_2(k) W_N^{-nk}\nonumber \end{gather*}

Durch Einsetzen der ersten beiden Gleichungen und Umordnen der
Summen ergibt sich:
\begin{gather*} \tilde{x}_3[n] = {1\over N} \sum_{m=0}^{N-1} \tilde{x}_1[m] \sum_{r=0}^{N-1} \tilde{x}_2[r] \sum_{k=0}^{N-1} W_N^{-(n-m-r)k} \end{gather*}

Der letzte Term läßt sich wie folgt auswerten:
\begin{gather*} \sum e^{j2\pi k(n-m-r)/N} = \begin{cases} N, \quad & r=m-m+p\cdot N, \,\, p \in \mathbb{Z}\\
0, & \text{sonst} \end{cases}\end{gather*}

Mit p als ganzer Zahl vereinfacht sich Gleichung 8.20 zu:
\begin{gather*} \tilde{x}_3[n] = \sum_{m=0}^{N-1} \tilde{x}_1[m] \cdot \tilde{x}_2[n-m+p\cdot N]\\ = \sum_{m=0}^{N-1} \tilde{x}_1[m] \cdot \tilde{x}_2[n-m] \end{gather*}

Dieser Ausdruck ergibt sich durch die Periodizität von
$\tilde{x}_2[n]$. Bis auf die Summationsgrenzen, die hier nur über
eine Periode laufen, ist er identisch mit der Faltungssumme.
$\tilde{x}_3[n]$ ist selber auch periodisch. Gleichung 8.21 wird
daher als periodische Faltung bezeichnet.


\end{document}
