\documentclass[reqno,twocolumn]{amsart}
\usepackage{amsmath}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{amsfonts}

%\documentstyle[12pt]{article}
%\input{psfig.sty}
%\input{figcommands.tex}
\textwidth 17cm
%\textheight 21cm
\textheight 24cm
\oddsidemargin=0cm
\evensidemargin=0cm
\topmargin=-1cm
%%%\topmargin=-3cm
\pagestyle{empty}
\begin{document}

%\noindent {\bf Student name:}\\
%\noindent {\bf Student number:}

\begin{center}
Department of Electrical and Computer Engineering\\
University of Toronto\\
\vspace{0.5cm}

ECE 431F, Digital Signal Processing (DSP);\\
Prof. S. Mann\\
\vspace{0.5cm}

{\LARGE\bf MIDTERM TEST  }\\
{Friday October 18, 2002, 7PM to 8:30PM}
\vspace{0.2cm}

{\bf Time allowed: 90 minutes.\\
Type X (``aids allowed'').
\\
(3+5+10+7 = 25 points = 25\% of final grade)}
\end{center}
\vspace{0.2cm}

\noindent {\bf Note:} Please write your answers in the allocated space only.
All answers should be properly explained by providing appropriate detailed
arguments, reasoning, formulas, diagrams, etc..\\
All answers must be numbered fully, e.g. 1a, 1b, \ldots 2a, 2b, \ldots,
and not just a, b, \ldots a, b, etc..

%%%%{\bf Problem 1 (3+3+3=total 9 points)} \\

\vspace{.25in}\noindent
{\bf Q0} (3points): A discrete time signal comprises eight samples per second
    of a two hertz continuous time cosine wave, $cos(2\pi 2t)$.

(a) Is the sampling rate above, below, or at the Nyquist frequency?

(b) Is the aforementioned discrete time signal periodic?

(c) Explain clearly and completely whether or not the continuous time
    signal can be reconstructed from the first eight samples
    starting at $t=0$, i.e. eight samples taken over
    a one second half open interval $t \in [0,1)$.  Be sure to state
    any and all assumptions you make.

(d) Write down the numerical values of these eight samples.

(e) What is the 8 point DFT of these eight samples?
    Write down the numerical values of the 8 point DFT of these eight samples.
    %Please don't be stupid and actually waste time computing it.

%Q1. A discrete time signal comprises eight samples per second
%    of a continuous time cosine wave, given by $g(t)=cos(2t)$.
%(a) What is the frequency (in Hertz) of the cosine wave, $g(t)$.
%(b) Is the sampling rate above, below, or at the Nyquist frequency?
%(c) Is the aforementioned discrete time signal periodic?
%(c) Explain clearly and completely whether or not the continuous time
%    signal can be reconstructed from the first eight samples
%    starting at $t=0$, i.e. eight samples taken over
%    a one second half open interval $t \in [0,1)$.  Be sure to state
%    any and all assumptions you make.
%(e) If we were to compute the 8 point DFT of these eight samples, what

\vspace{.25in}\noindent
{\bf Q1} (5points): A discrete time signal comprises eight samples per second
    of a continuous time cosine wave, given by $g(t)=cos(2\pi f_c t)$.
%(a) What is the frequency (in Hertz) of the cosine wave, $g(t)$. % $f_c$

(a) For what values of frequency $f_c \in {\mathbb{R}}$
    is the sampling rate above,
    below, or at the Nyquist frequency? Explain.

(b) For what values of $f_c$ is the aforementioned discrete time signal
    periodic?

(c) Explain clearly and completely for what frequencies $f_c$
    the continuous time signal can be reconstructed from the first eight
    samples starting at $t=0$, i.e. eight samples taken over
    a one second half open interval $t \in [0,1)$.  Be sure to state
    any and all assumptions you make.

(d) If we were to compute the 8 point DFT of these eight samples, what
    values of $f_c$ would result in having at
    most two non-zero entries in the DFT?
    %least one zero entry in the DFT?

\vspace{.25in}\noindent
{\bf Q2} (10points): Suppose onesies (TM) and twosies (TM) are, respectively,
one point and two point Discrete Fourier Transformers (DFTs)
that are offered free of charge, in unlimited quantities.

Any FFT of larger size needs to be custom-built, and has a nonzero
cost associated with it.  The cost is one dollar (\$1.00) per
matrix element of the corresponding DFT matrix, to put the infrastructure
in place, plus an Additional Operating Tax (AOT) of \$ $N(N-1)$ where $N^2$
is the number of elements in the DFT matrix.  Thus the cost of an N-DFT
is $N^2+N(N-1)$.
Signal amplifiers having a constant gain may also be purchased for
\$1.00 plus a \$1.00 Domestic Preparedness Sales Tax (DPST).

Onsies (TM) can be used as hookup wire to connect various devices together.

(a) Explain what a one point DFT does to the signal passing through it.
    Explain therefore, how onsies (TM) can be used as hookup wire.

(b) Explain how you could use a twosie (TM) as an adder, to add two signals
    together.

(c) Explain how you could use a twosie (TM) as a subtractor, to compute the
    difference of two signals.

(d) Design a minimum cost 32 point DFT showing a sparse set of the hookups,
    sufficient to illustrate your understanding of the problem.
    Calculate the cost of your design.  Show all your work clearly.
    You may now re-use this block in what follows, if you wish.

(e) Design a minimum cost 480 point DFT. % 3*5*32
    Show a sparse set of the hookups sufficient to illustrate your
    understanding of the problem.
    Calculate the cost of your design.  Show all your work clearly.
    Provide any diagrams, equations,
    and descriptions of your design that might help in the grading.

(f) Design a minimum cost 640 point DFT. % 4*5*32=5*64
    What is the lowest possible cost?  Provide detailed diagrams, equations,
    and descriptions of your design.

(g) Bonus question: what's the minimum cost of computing the two dimensional
    FFT of a picture that's of dimension 480 down by 640 across.
    What's the minimum cost of computing the three dimensioanl
    FFT of a motion picture film that's 1000 frames by 480 down by 640 across.
    % 1000 = 5*5*5*8

\vspace{.25in}\noindent
{\bf Q3} (7points): Show (prove) that the Fourier operator (i.e. the DFT matrix)
given by ${\mathbb{F}} \in {\mathbb{C}}^{N \times N}$,\\
defined by ${\mathbb{F}}_{nk} = \frac{1}{\sqrt{N}}e^{-2\pi i(n-1)(k-1)/N}$,
for $n = 1,\cdots,N,
\\
k=1, \cdots, N,$ and $i=\sqrt{-1}$,
is a unitary operator.

A unitary operator is one in which the operator times the
complex conjugate of the transpose of the operator is the identity matrix,
i.e., ${\mathbb{F}}^\dag {\mathbb{F}} = {\mathbb{I}}$,
where $({\mathbb{F}}^\dag)_{nk} = ({\mathbb{F}}_{kn})^*$.

%PROOF 1:
%We know that the elements of the inverse Fourier transform are given by
%${\mathbb{F}}_{nk} = 1/\sqrt{N}e^{+2\pi i(n-1)(k-1)/N}$, and each of these
%entries is merely the complex conjugate of the corresponding entry
%in ${\mathbb{F}}$.  We can also easily see that ${\mathbb{F}}$ is symmetric,
%i.e. ${\mathbb{F}}_{nk} = {\mathbb{F}}_{kn}$, because
%$e^{+2\pi i(n-1)(k-1)/N} = e^{+2\pi i(k-1)(n-1)/N}$.
%Thus the complex conjugate of the transpose of ${\mathbb{F}}$ is equal to its
%inverse, ${\mathbb{F}}^{-1}$.  Therefore ${\mathbb{F}}$ is unitary.

%PROOF 2:
%\begin{align*}
%({\mathbb{F}}^\dag {\mathbb{F}})_{nk} &= \sum_{l=1}^N {\mathbb{F}}^*_{nl} {\mathbb{F}}_{lk}\\
%    &= \sum \frac{1}{\sqrt{N}}e^{-2\pi i(n-1)(l-1)} \frac{1}{\sqrt{N}}e^{-2\pi i(l-1)(k-1)/N}\\
%    &= \frac{1}{N} \sum e^{-2\pi i ((n-1)(l-1)/N - (l-1)(k-1)/N}.
%\end{align*}
%For $n=k$, we have:
%\begin{align*}
%({\mathbb{F}}^\dag {\mathbb{F}})_{nn} &=\frac{1}{N} \sum e^{-2\pi i((n-1)(l-1)/N - (l-1)(n-1)/N})\\
%                                      &=\frac{1}{N} \sum e^{-2\pi i (0)/N}\\
%                                      &=\frac{1}{N} \sum 1\\
%                                      &=1.
%\end{align*}
%For $n\neq k$, the result is zero, due to orthogonality of $e^{-2\pi i \cdots}$.

\end{document}

