\note<1>{just some of the design \\ parameters of the spectrogram. \\ This is almost an art \\ and much literature exists.\\ We will just talk about window size}
Questions:
\begin{itemize}[<+->]
\item width of the analysis window?
\item position of the windows (overlapping?)
\item shape of the window (weighing the samples)
\end{itemize}
\end{frame}
-\begin{frame}
- \frametitle{Wideband vs Narrowband}
+\def\tf{180 mul dup 1.1 mul cos 1 add 2 div exch 5 mul sin 0.1 mul add 0.1 add }
+\def\td{cvi 16 mod 16 div \tf }
+\def\tr{cvi 16 mod 15 exch sub 16 div \tf }
+\def\twin{.5 sub abs .5 div 1 exch sub 0.06 add }
+\def\tw{cvi 16 mod 16 div \twin }
+\def\tdw{cvi 16 mod 16 div dup \tf exch \twin mul }
+
+
+\begin{frame} \frametitle{Tapering Windows}
+ \centering
+ the DFT is inherently $N$-periodic and assumes the signal is $N$-periodic
\frametitle{ Matrix factorization view of DFT, N = 8, 8/8}
Is this a big deal?
\begin{itemize}[<+->]
\item In image processing (e.g. digital photography) one takes block of 8 by 8 pixels
\item One computes a transform (called DCT) similar to a DFT
\item It has a fast algorithm inspired by what we just saw
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{Some examples}
image processing (JPEG compression)
\begin{itemize}[<+->]
\item image is divided into $8\times 8$-pixel blocks
\item DFT performed on rows and columns: 16 8-point DFTs
\item direct computation: $16\times 8^2 = 1024$ multiplications
\item FFT: $16\times 2 = 32$ multiplications
\end{itemize}
\end{frame}
\begin{frame}
\frametitle{Some examples}
audio processing (MP3 compression)
\begin{itemize}[<+->]
\item audio is split into 1152-point frames
\item direct DFT computation: $1.3\cdot 10^6$ multiplications
\item FFT: $3500$ multiplications
\end{itemize}
\end{frame}
% remove the esoteric stuff
% \begin{frame}
% \frametitle{How about other lengths? To each their own!}
%
% \begin{itemize}[<+->]
% \item if $N = p^K$ with $p$ a prime, we can use an algorithm similar to that for $p=2$; this is the \textbf{Cooley-Tukey} algorithm (1965, but invented several times before)
% \item if $N=N_1 N_2$, with $N_1$ and $N_2$ coprime, we can reorder this into a two-dimensional DFT of size $N_1$ by $N_2$; this is the \textbf{Good-Thomas} algorithm (1958, 1963)
% \item if $N$ is prime, a mapping transforms the result into a convolution of size $N-1$, which can be solved by a DFT of size $N-1$; this is the \textbf{Rader} algorithm (1968)
% \item by combining all the tricks, and minimizing the number of multiplications, we have the \textbf{Winograd} FFT (1979)
% \end{itemize}
%\end{frame}
%\begin{frame}
% \frametitle{ How about other lengths? Example for $N = 5$}
% According to Rader's algorithm:
%
% Skip first and column and first row (trivial computation)
% \[
% \mathbf{W}_5 =
% \begin{bmatrix}
% 1 & 1 & 1 & 1 & 1\\
% 1 & W & W^2& W^3 & W^4 \\
% 1 & W^2 & W^4 & W & W^3\\
% 1 & W^3 & W & W^4 & W^{2}\\
% 1 & W^4 & W^3 & W^2 & W
% \end{bmatrix}
% \rightarrow
% \begin{bmatrix}
% W & W^2& W^3 & W^4 \\
% W^2 & W^4 & W & W^3\\
% W^3 & W & W^4 & W^{2}\\
% W^4 & W^3 & W^2 & W
% \end{bmatrix}
% =
% {\bf P}
% \begin{bmatrix}
% W & W^2& W^3 & W^4 \\
% W^4 & W & W^2& W^3 \\
% W^3 & W^4 & W & W^2\\
% W^2 & W^3 & W^4 & W
% \end{bmatrix}
% {\bf Q}
% \]
% where ${\bf P}$ and $ {\bf Q}$ are appropriate permutation matrices.
%
%
% This is now a circulant matrix, diagonizable by a DFT of size 4!
%\end{frame}
%\begin{frame}
% \frametitle{ How about other lengths? Example for $N = 6$}
% According to the Good-Thomas algorithm, this can be written as 3 DFT-2 and 2 DFT-3:
% \[
% \mathbf{W}_6 =
% {\bf P}
% \begin{bmatrix}
% 1 & 1 & & & & \\
% 1 & -1 & & & & \\
% & & 1 & 1 & & \\
% & & 1 & -1 & & \\
% & & & & 1 & 1 \\
% & & & & 1 & -1
% \end{bmatrix}
% {\bf Q}
% \begin{bmatrix}
% 1 & 1 & 1 & & &\\
% 1 & W & W^2 & & &\\
% 1 & W^2 & W & & & \\
% & & & 1 & 1 & 1 \\
% & & & 1 & W & W^2 \\
% & & & 1 & W^2 & W
% \end{bmatrix}
% {\bf R}
% \]
%
% where ${\bf P}$, $ {\bf Q}$ and $ {\bf R}$ are appropriate permutation matrices.
%
% Except for permutations (no arithmetic operation, just addressing), there is no cost!
%\end{frame}
\begin{frame}
\frametitle{ Conclusions}
Don't worry, be happy!
\begin{itemize}
\item The Cooley-Tukey is the most popular algorithm, mostly for $N=2^N$
\item Note that there is always a good FFT algorithm around the corner
\item Do not zero-pad to lengthen a vector to have a size equal to a power of 2
\item There are good packages out there (e.g. Fastest Fourier Transform in the West, SPIRAL)