When we looked at filters, we found that the signal $y(n)=\frac{1}{2}x(n)+\frac{1}{2}x(n-1)$ is a low pass filter. This was an example of a \emph{Finite Duration Impulse Response}, otherwise known as a finite impulse response, or FIR. FIR filters have no recursion. On the other hand, consider the \emph{Infinite Duration Impulse Response} (IIR filter) characterized by the Linear Constant Coefficient Difference Equation (LCCDE):

$$ y(n) = \alpha y(n-1) + x(n) \mbox{ where } \alpha \in (0,1) \mbox{, the system is causal, and initially at rest. } $$

Consider what would happen if the system were not initially at rest, that is, what if $y(-1) = 1 \neq 0$? This violates linearity because the system does not satisfy the zero-input-zero-output (ZIZO) property of linear systems. Let $x(n) = 0$ $ \forall n \in \Z$:

$$ y(0) = \alpha y(-1) + x(0) = \alpha \neq 0 $$

Since the zero signal did not produce a zero output, the system doesn't satisfy ZIZO, and is therefore not linear. What about Time Invariance (TI)? Let $\hat{x}(n) = x(n-N)$:

$$ \hat{y}(n) = \alpha \hat{y}(n-1) + \hat{x}(n) $$

To be valid, $\hat{x}$ and $\hat{y}$ must also satisfy the initial conditions (note that if the system was not recursive, the initial conditions would not be so important). So, the following must hold:

$$
\hat{y}(-1) = 1
$$

Since $\hat{y}(-1) = y(-1-N)$, then $y(-1-N) = 1$ must also hold. But this information was not given, therefore the system is not TI. Lets determine the frequency response of the system.

The first method is to let $x(n) = e^{i\omega n}$ and $y(n) = H(\omega)e^{i\omega n}$, then plug into the recursive formula:

\begin{align*}
y(n) &= \alpha y(n-1) + x(n) \\
H(\omega)e^{i\omega n} &= \alpha H(\omega)e^{i\omega (n-1)} + e^{i\omega n} \\
H(\omega)e^{i\omega n} &= \alpha H(\omega)e^{i\omega n} e^{-i\omega)} + e^{i\omega n} \\
H(\omega) &= \alpha H(\omega) e^{-i\omega)} + 1 \quad \mbox{ divide by } e^{i\omega n} \\
H(\omega) - \alpha H(\omega) e^{-i\omega)} &=  1 \\
H(\omega) \left(1 - \alpha e^{-i\omega)} \right) &=  1 \\
H(\omega) &= \frac{1}{1 - \alpha e^{-i\omega}} \\
\end{align*}

We implicity used the fact that $\left| \alpha \right| \lt 1$ by the fact that $H(\omega) = \sum \limits_{n\in\Z} h(n)e^{-i\omega n}$ would be divergent otherwise.


Alternatively, we could have used the following formula for the frequency response:

\begin{nicebox}
$$H(\omega) = \sum \limits_{k \in \Z} h(n) e^{-i\omega n}$$
\end{nicebox}

\begin{align*}
H(\omega) &= \sum \limits_{n=-\infty}^{\infty} h(n) e^{-i\omega n} \\
H(\omega) &= \sum \limits_{n=-\infty}^{\infty} \alpha^n u(n) e^{-i\omega n} \\
H(\omega) &= \sum \limits_{n=0}^{\infty} \alpha^n e^{-i\omega n} \quad \mbox{ change limits since } h(n) \alpha \cdot u(n)\\
H(\omega) &= \sum \limits_{n=0}^{\infty} \left( \alpha e^{-i\omega} \right)^n \quad \mbox{ group as one exponential } \\
H(\omega) &= \frac{1}{1-\alpha e^{-i \omega}} \quad \mbox{ since } \left| \alpha e^{-i \omega} \right| = \left| \alpha \right| \left| e^{-i\omega}  \right| = \left| \alpha \right| \lt 1
\end{align*}


Another method is to solve utilizing properties of the Discrete-Time Fourier Transform (DTFT). Recall that convolution in the time-domain corresponds to multiplication in the frequency domain:

\begin{nicebox}
$$y(n) = (x*h)(n) \ftp Y(\omega) = X(\omega)H(\omega) $$
\end{nicebox}


This implies the following relationship:

$$ H(\omega) = \frac{Y(\omega)}{X(\omega)} $$

Lets derive the fourier transform pair for $y(n-1)$:

\begin{align*}
\tilde{y}(n) &= y(n-1) \\
\tilde{y}(n) &\ftp \tilde{Y}(\omega) = \sum \limits_{n\in\Z} \tilde{y}(n)e^{-i\omega n} \\
y(n-1) &\ftp \tilde{Y}(\omega) = \sum \limits_{n\in\Z} y(n-1)e^{-i\omega n} \\
y(n-1) &\ftp \tilde{Y}(\omega) = \sum \limits_{m\in\Z} y(m)e^{-i\omega (m+1)} \quad \mbox{let } m = n-1 \\
y(n-1) &\ftp \tilde{Y}(\omega) = \lr{\sum \limits_{m\in\Z} y(m)e^{-i\omega m}} e^{-i\omega} \\
y(n-1) &\ftp \tilde{Y}(\omega) = Y(\omega)e^{-i\omega}
\end{align*}

We can generalize this to 

\begin{nicebox}
$$y(n-N) \ftp Y(\omega)e^{-i\omega N}$$
\end{nicebox}



Now we can solve the recursive formula using the fourier transform:

\begin{align*}
y(n) &= \alpha y(n-1) + x(n) \\
\ftrans{y(n)} &= \ftrans{\alpha y(n-1) + x(n)} \\
Y(\omega) &= \ftrans{\alpha y(n-1)} + \ftrans{x(n)} \\
Y(\omega) &= \alpha Y(\omega)e^{-i\omega} + X(\omega) \\
H(\omega) &= \alpha H(\omega)e^{-i\omega} + 1 \quad \mbox{divide by } X(\omega) \\
H(\omega) \left(1 - \alpha e^{-i\omega)} \right) &=  1 \\
H(\omega) &= \frac{1}{1-\alpha e^{-i \omega}}
\end{align*}



One method to find the impulse response is to use a little intuition and analyze the recursive formula:

First, lets solve for a few values of $h(n)$:
\begin{align*}
h(n) &= \alpha h(n-1) + \delta(n) \\
h(0) &= \alpha h(-1) + \delta(0) \\
h(0) &= 0 + 1 \\
h(1) &= \alpha h(0) + \delta(1) \\
h(1) &= \alpha + 0 \\
h(2) &= \alpha h(1) + \delta(2) \\
h(2) &= \alpha^2 \\
h(3) &= \alpha^3
\end{align*}
Remember that because the system is causal, we know that $h(n) = 0$ $ \forall n \lt 0$. This seems to show that $h(n) = \begin{cases} \alpha^n & n \geq 0 \\ 0 & n \lt 0 \end{cases}$ 

We can simplify this expression by using the \emph{Discrete-Time Unit Step} function, $u(n) \begin{cases} 0 & n \lt 0 \\ 1 & n\geq0 \end{cases}$.

Now we can define the impulse response as $ h(n) = \alpha^n \cdot u(n)$. Given that $H(\omega) = \frac{1}{1 - \alpha e^{-i\omega}}$, we can find the magnitude response $\left| H(\omega) \right|$.

\begin{align*}
H(\omega) &= \frac{1}{1 - \alpha e^{-i\omega}} \\
H(\omega) &= \frac{e^{i\omega}}{e^{i\omega} - \alpha } \quad \mbox{multiply by } e^{i\omega} \\
\left| H(\omega) \right| &= \left| \frac{e^{i\omega}}{e^{i\omega} - \alpha } \right| \\
\left| H(\omega) \right| &= \frac{\left| e^{i\omega} \right|}{\left| e^{i\omega} - \alpha  \right| } \\
\left| H(\omega) \right| &= \frac{1}{\left| e^{i\omega} - \alpha \right| } \\
\end{align*}

%\img{images/filters/eminusalpha.ps}

\begin{center}
\begin{pspicture}(-5,-5)(5,5)
		
% y-axis
\rput(0.3,3.75){ $Im$ }
\psline{->}(0,-3.75)(0,3.75)

% x-axis
\rput(3.75,0.3){ $Re$ }
\psline{->}(-3.75,0)(3.75,0)
			
% the circle
\pscircle(0,0){ 3 }
			
% quadrants
\rput(0.3,3.3){ $i^1$ }
\rput(0.3,-3.3){ $i^2$ }
\rput(-3.3,0.3){ $i^3$ }
\rput(3.3,0.3){ $i^0$ }
	
 % new vector 
\rput(1.75,2){$e^{i\omega}$}
\psline[linewidth=1.25 pt]{->}(2.121,2.121)

 % new vector 
\rput(0.725,-0.2){$\alpha$}
\psline[linewidth=1.25 pt]{->}(1.500,0.000)

 % new vector 
\rput(2.3,1){$e^{i\omega}-\alpha$}
\psline[linewidth=1.5 pt]{->}(1.500,0.000)(2.121,2.121)

\rput(-0.75,-4.25){$1+\alpha$}
\rput(2.25,-4.25){$1-\alpha$}
\psline{<->}(-3,-4)(1.5,-4)
\psline{<->}(1.5,-4)(3,-4)
\psline[linestyle=dashed](3,-4.5)(3,0)
\psline[linestyle=dashed](-3,-4.5)(-3,0)
\psline[linestyle=dashed](1.5,-4.5)(1.5,0)

	
\end{pspicture}
\end{center}

By inspection, we can find that this represents a low pass filter. When $\omega = 0$, we have $\left| e^{i\omega} - \alpha \right| = \left| 1 - \alpha \right|$, and when $\omega = \pi$ or $\omega = -\pi$, then  $\left| e^{i\omega} - \alpha \right| = \left| 1 + \alpha \right|$. By looking at this on a unit circle. We have the maximum length when  $\omega = \pm \pi$, so the magnitude response is least since the magnitude of this vector is in the denominator. We have the maximum of the magnitude response when the denominator is the least, when  $\omega = 0$. This is why the filter is a low pass filter. We can also take note of the curvature by acknowledging that when $\omega$ is near $\pm \pi$, the magnitude of $e^{i\omega}-\alpha$ changes much less than when near 0. 

%\img{images/filters/lpf.ps}

%\psset{xunit=1, yunit=1, algebraic, arrowscale=1.5}
\psset{unit=1cm}
\begin{center}
\begin{pspicture}(-3.5,-1)(3.75,3.5)
\psplot[algebraic,linewidth=1.5pt,plotpoints=1000]{-3.14}{3.14}{cos(x)+1.3}
\psaxes[showorigin=false,labels=none, Dx=3.14](0,0)(-3.25,0)(3.25,2.5)

\psline[linestyle=dashed](-3.14,0.3)(3.14,0.3)
\psline[linestyle=dashed](-3.14,2.3)(3.14,2.3)
\rput(3.6,2.3){$\frac{1}{1-\alpha}$}
\rput(3.6,0.3){$\frac{1}{1+\alpha}$}

\rput(3.14, -0.35){$\pi$}
\rput(-3.14, -0.35){$-\pi$}
\rput(0, -0.35){$0$}

\end{pspicture}
\end{center}

Design-oriented analysis with an eye toward design allows you to generalize for similar systems. Notice that in the above example, if we wanted to make a high-pass filter, all we would need to do is make $\alpha \in (-1,0)$. Looking at the last figure, we can see that the vector without the negative gets the arrow. Thus, we would have a vector pointing to $e^{i\omega}$ from $\alpha$ on the left side of the unit circle. The magnitude response would still have a value of $\frac{1}{1-\alpha}$ at $\omega = 0$, and $\frac{1}{1+\alpha}$ at $\omega = \pm \pi$. The only difference is that the values at $\omega = \pm \pi$ are the maxima.

To make a LPF or HPF sharper, simply let $\alpha$ approach 1, but not equal 1. This is because we need a safety margin since numerical approximations and noise could send a vector outside of the unit circle and we would have an unstable system. ($\sum \alpha^n$ diverges)

Lets define a new frequency response to be $H_N(\omega) = \frac{1}{1-\alpha e^{-i\omega N}}$. Notice that this corresponds to the difference equation $y(n) - \alpha y(n-N) = x(n)$:

\begin{align*}
H(\omega) &= \frac{1}{1-\alpha e^{-i\omega N}} \\
H(\omega) - \alpha H(\omega) e^{-i\omega N} &= 1 \\
H(\omega) e^{i\omega n} - \alpha H(\omega)e^{i\omega n} e^{-i\omega N} &= e^{i\omega n} \\
y(n) - \alpha y(n-N) &= x(n) \\
\end{align*}

To graph the magnitude response for a particular value of $N$, we can analyze the vectors representing the numerator and denominator. But, we can also perform a simple trick, since we know the graph of $H_1(\omega)$:

%\img{images/comb/comb1.ps}

%\psset{xunit=1, yunit=1, algebraic, arrowscale=1.5}
\psset{unit=1cm}
\begin{center}
\begin{pspicture}(-3.5,-1)(3.75,3.5)
\psplot[algebraic,linewidth=1.5pt,plotpoints=1000]{-3.14}{3.14}{cos(x)+1.3}
\psaxes[showorigin=false,labels=none, Dx=1.62](0,0)(-3.25,0)(3.25,2.5)

\psline[linestyle=dashed](-3.14,0.3)(3.14,0.3)
\psline[linestyle=dashed](-3.14,2.3)(3.14,2.3)
\rput(3.6,2.3){$\frac{1}{1-\alpha}$}
\rput(3.6,0.3){$\frac{1}{1+\alpha}$}

\rput(0,3){$N=1$}

\rput(3.14, -0.35){$\pi$}
\rput(1.62, -0.35){$\pi/2$}
\rput(-1.62, -0.35){$-\pi/2$}
\rput(-3.14, -0.35){$-\pi$}
\rput(0, -0.35){$0$}

\end{pspicture}
\end{center}

Now let $H_2(\omega) = H_1(2\omega)$, then we need to divide by 2 on our axes:

%\img{images/comb/comb2.ps}

%\psset{xunit=1, yunit=1, algebraic, arrowscale=1.5}
\psset{unit=1cm}

\begin{center}
\begin{pspicture}(-3.5,-1)(3.75,3.5)
\psplot[algebraic,linewidth=1.5pt,plotpoints=1000]{-3.14}{3.14}{cos(4*x/2)+1.3}
\psaxes[showorigin=false,labels=none, Dx=1.62](0,0)(-3.25,0)(3.25,2.5)

\psline[linestyle=dashed](-3.14,0.3)(3.14,0.3)
\psline[linestyle=dashed](-3.14,2.3)(3.14,2.3)
\rput(3.6,2.3){$\frac{1}{1-\alpha}$}
\rput(3.6,0.3){$\frac{1}{1+\alpha}$}

\rput(0,3){$N=2$}

\rput(3.14, -0.35){$\pi$}
\rput(1.62, -0.35){$\pi/2$}
\rput(-1.62, -0.35){$-\pi/2$}
\rput(-3.14, -0.35){$-\pi$}
\rput(0, -0.35){$0$}

\end{pspicture}
\end{center}

If you notice there will always be $N$ peaks and $N$ valleys. In general, we can use the first graph to find the graph of the magnitude response for all value of $N$. The higher the $N$, the more oscillations.

%\img{images/comb/comb4.ps}

%\psset{xunit=1, yunit=1, algebraic, arrowscale=1.5}
\psset{unit=1cm}

\begin{center}
\begin{pspicture}(-3.5,-1)(3.75,3.5)
\psplot[algebraic,linewidth=1.5pt,plotpoints=1000]{-3.14}{3.14}{cos(8*x/2)+1.3}
\psaxes[showorigin=false,labels=none, Dx=1.62](0,0)(-3.25,0)(3.25,2.5)

\psline[linestyle=dashed](-3.14,0.3)(3.14,0.3)
\psline[linestyle=dashed](-3.14,2.3)(3.14,2.3)
\rput(3.6,2.3){$\frac{1}{1-\alpha}$}
\rput(3.6,0.3){$\frac{1}{1+\alpha}$}

\rput(0,3){$N=4$}

\rput(3.14, -0.35){$\pi$}
\rput(1.62, -0.35){$\pi/2$}
\rput(-1.62, -0.35){$-\pi/2$}
\rput(-3.14, -0.35){$-\pi$}
\rput(0, -0.35){$0$}

\end{pspicture}
\end{center}


Infinite Duration Impulse Response

Consider a circuit with a resistor and capacitor in series.

%\img{images/circuits/combo/combo.ps}

Assume the capacitor is initially uncharged. The voltage across the capacitor is given by


$$ y(t) = \frac{1}{C} \int_{-\infty}^t f(\tau) d\tau $$

where $c$ is the capacitance, and $f(\tau)$ is the current. If we look at a resistor, the voltage across the resistor is given by 

$$ g(t) = R f(t) $$

where $R$ is the resistance and $f(t)$ is the current. Thus, the current can also be written as $f(t) = \frac{g(t)}{R}$. The voltage across the resistor can also be given by $x-y$, thus we can solve for the equation that governs the current:

\begin{align*}
g(t) &= x(t) - y(t) \\
Rf(t) &= x(t) - y(t) \\
f(t) &= \frac{x(t)-y(t)}{R}
\end{align*}

Now plug $f(t)$ into the voltage equation for the capacitor:

\begin{align*}
y(t) &= \frac{1}{C} \int_{-\infty}^t f(\tau) d\tau \\
y(t) &= \frac{1}{C} \int_{-\infty}^t \frac{x(\tau)-y(\tau)}{R} d\tau \\
\frac{d}{dt}y(t) &= \frac{d}{dt}\frac{1}{C} \int_{-\infty}^t \frac{x(\tau)-y(\tau)}{R} d\tau \\
\frac{d}{dt}y(t) &= \frac{1}{RC} \lr{x(t)-y(t)} \\
RC\frac{d}{dt}y(t) + y(t) &= x(t) \\
\end{align*}

We can also the equation that governs the current as
$$ RC \dot{y} + y = x $$

We can determine the frequency response using a few methods:
\begin{enumerate}
\item Letting $x(t) = e^{i\omega t}$, and $y(t) = H(\omega) e^{i\omega t}$
\item Using the Continuous-time Fourier Transform (CTFT)
\end{enumerate}

First, lets solve for the frequency response using the first method:

\begin{align*}
RC\dot{y}(t) + y(t) &= x(t) \\
RCi\omega H(\omega)e^{i\omega t} + H(\omega)e^{i\omega t} &= e^{i\omega t} \\
RCi\omega H(\omega) + H(\omega) &= 1 \\
H(\omega) &= \frac{1}{1 + i\omega RC}
\end{align*}

Now for the CTFT method. Recall the synthesis equation for the CTFT:

\begin{nicebox}
$$x(t) = \frac{1}{2\pi} \infint X(\omega) e^{i\omega t}d\omega $$
\end{nicebox}

Lets determine the fourier transform pair for differentiation in the time domain:

\begin{align*}
x(t) = \frac{1}{2\pi} \infint X(\omega) e^{i\omega t}d\omega \\
\frac{d}{dt}x(t) = \frac{1}{2\pi} \frac{d}{dt}\infint X(\omega) e^{i\omega t}d\omega \\
\frac{d}{dt}x(t) = \frac{1}{2\pi} \infint X(\omega) \frac{d}{dt}e^{i\omega t}d\omega \\
\frac{d}{dt}x(t) = \frac{1}{2\pi} \infint X(\omega) i\omega e^{i\omega t}d\omega \\
\frac{d}{dt}x(t) = \frac{1}{2\pi} \infint \tilde{X}{\omega} e^{i\omega t}d\omega \\
\end{align*}

This tells us that differentiation in the time domain corresponds to multiplication of $i\omega$ in the frequency domain:

\begin{nicebox}
$$ \frac{d}{dt}x(t) \ftp i\omega X(\omega) $$
\end{nicebox}

Using this new relationship, lets solve for $H(\omega)$:

\begin{align*}
RC\dot{y}(t) + y(t) &= x(t) \\
RCi\omega Y(\omega) + Y(\omega) &= X(\omega) \\
RCi\omega H(\omega) + H(\omega) &= 1 \quad \mbox{since } H(\omega) =\frac{Y(\omega)}{X(\omega)} \\
H(\omega) &= \frac{1}{1 + i\omega RC}
\end{align*}

How do we plot $\abs{H(\omega)}$? What type of filter is it? Note that in continuous-time, to analyze this function, we will not use the unit circle. Lets first massage the equation for $H(\omega)$:

\begin{align*}
H(\omega) &= \frac{1}{1 + i\omega RC} \\
H(\omega) &= \frac{1/RC}{1/RC + i\omega} \\
H(\omega) &= \frac{1/RC}{i\omega - \lr{-1/RC}}
\end{align*}

Now lets look at the vector that this creates:

%\img{images/iomegaaxis/overrc/overrc.ps}

\psset{unit=1cm}
\begin{center}
\begin{pspicture}(-3,-3)(3,3)
    

% y-axis
\rput(0.3,2.5){ $i\omega$ }
\psline{->}(0,-1.5)(0,2.5)

% x-axis
\rput(2.5,0.3){ $\Re$ }
\psline{->}(-2.5,0)(2.5,0)


\rput(-2,0.4){$-1/RC$}
\psline(-2,-0.2)(-2,0.2)
\rput(0.4,-1){$i\omega$}
\psline(-0.2,-1)(0.2,-1)

 % new vector 
\rput(-1.7,-0.8){$i\omega-\left(-1/RC\right)$}
\psline[linewidth=1.5 pt]{->}(-2,0)(0,-1)
\end{pspicture}
\end{center}


We can see that at $\omega=0$, the vector $i\omega - \lr{-1/RC}$ is the shortest. As $\omega \to \infty$, the magnitude response decays. To get the curvature of the plot, consider the change in magnitude over time. 

% \img{images/graphs/respmag/respmag.ps}

\psset{unit=1cm}
\begin{center}
\begin{pspicture}(-3,-3)(3,3)
    
\fileplot[linewidth=1.5pt]{magresp.dat}
% function name
\rput(3.14159265,1){$\left|H(\omega)\right|$}

% x-axis
\psline(-3.54159265, 0)(3.54159265, 0)
\rput(3.54159265,-0.3){$\omega$}


\rput(0.85840735, 1.2){$(1/\sqrt{2})$}
\rput(-1.14159265, 1.2){$(1/\sqrt{2})$}
\rput(0.85840735, -0.4){$1/RC$}
\rput(-1.14159265, -0.4){$-1/RC$}


\psline[linestyle=dashed](0.85840735, 0)(0.85840735, 0.85)
\psline[linestyle=dashed](-1.14159265, 0)(-1.14159265, 0.85)
\psline[linestyle=dashed](-1.14159265, 0.85)(0.85840735, 0.85)


% begin x-axis labels:
\psline(-3.14159265, -0.1)(-3.14159265, 0.1)
\psline(-1.14159265, -0.1)(-1.14159265, 0.1)
\psline(0.85840735, -0.1)(0.85840735, 0.1)
\psline(2.85840735, -0.1)(2.85840735, 0.1)
% end x-axis labels:

\end{pspicture}
\end{center}

When is the magnitude response have a value of $\frac{1}{\sqrt{2}}$? Using pythagorean theorem, we can see that this occurs at $\omega = \pm \frac{1}{RC}$. 

\begin{align*}
\abs{H(\omega)} &= \abs{\frac{1/RC}{i\omega - \lr{-1/RC}}} \\
\abs{H(1/RC)} &= \frac{\abs{1/RC}}{\abs{i \lr{1/RC} - \lr{-1/RC}}} \\
\abs{H(1/RC)} &= \frac{1}{\abs{i + 1}} = \frac{1}{\sqrt{2}}
\end{align*}

To increase the bandwidth of this signal, what do we do? Note that we can decrease either $R$ or $C$ and $\frac{1}{RC}$ will increase. Now, to plot the phase response of the system:

\begin{align*}
\angle H(\omega) &= \angle \frac{1/RC}{i\omega - \lr{-1/RC}} \\
\angle H(\omega) &= \angle \lr{1/RC} - \angle \lr{i\omega - \lr{-1/RC}} \\
\angle H(\omega) &= 0 - \tan^{-1}(\omega RC) \\
\angle H(\omega) &=  \tan^{-1}(\omega RC) \\
\end{align*}

% \img{images/graphs/respmag/freq/phaseresp.ps}

\psset{unit=1cm}
\begin{center}
\begin{pspicture}(-3,-3)(3,3)
    
\fileplot[linewidth=1.5pt]{phaseresp.dat}
% function name
\rput(3.14159265,0.99783018390619){$\angle H(\omega)$}

% x-axis
\psline{->}(-3.54159265, 0)(3.54159265, 0)
\rput(3.54159265,-0.3){$\omega$}

% y-axis
\psline{->}(0,-2)(0,2)
% begin x-axis labels:
\psline(-0.1, -1.570796325)(0.1, -1.570796325)
\rput(3.2, -1.570796325){$-\frac{\pi}{2}$}
\psline(-0.1, 1.570796325)(0.1, 1.570796325)
\rput(3.2, 1.570796325){$\frac{\pi}{2}$}
% end y-axis labels:

\psline[linestyle=dashed](-3.14, -1.570796325)(3.14, -1.570796325)
\psline[linestyle=dashed](-3.14, 1.570796325)(3.14, 1.570796325)


\end{pspicture}
\end{center}

What if we take the voltage across the resistor instead of the capacitor?

% \img{images/circuits/combo/variation/combo.ps}

If $\omega = 0$, the capacitor opens, no current around the loop, and no voltage drop across the resistor. Therefore, there is zero gain. In other words, $G(0)=0$. If $\omega \to \infty$, the capacitor shorts, becoming a short circuit, so the voltage drop across the resistor, $y$, becomes $x$. In other words, as $\omega \to \infty$, $G(\omega) \to 1$. So this is a high pass filter. 

% \img{images/circuits/combo/both/combo.ps}

The voltage drop across the circuit is the sum of the voltage drops across the resistor and the capacitor, $y_r + y_c$.

\begin{align*}
x(t) &= y_r(t) + y_c(t) \\
X(\omega) &= Y_r(\omega) + Y_c(\omega) \\
X(\omega) &= G(\omega)X(\omega) + G(\omega)X(\omega) \\
1 &= G(\omega) + H(\omega) \\
G(\omega) &= 1 - H(\omega) = 1 - \frac{1}{1+i\omega RC} = \frac{i\omega RC}{1 + i\omega RC} \\
G(\omega) &= \frac{i\omega RC}{1 + i\omega RC}
\end{align*}

Note that as $\omega \to \infty$, $i\omega RC$ dominates the denominator and the 1 is negligible. Thus, as $\omega \to \infty$, $G(\omega) \to 1$.


Basic Circuits

Suppose we have a periodic signal with fundamental period 2.

% \img{images/deltas/periodic/periodic.ps}

\psset{unit=1cm}
\begin{center}
\begin{pspicture}(-3,-1)(4,4)
    

\rput(-2.5,1.5){$\cdots$}
\rput(3.5,1.5){$\cdots$}

% line
\psline{-*}(-2,0)(-2,2)
%  value
\rput(-1.7,2){(2)}
%  position
\rput(-2,-0.3){-2}


% line
\psline{-*}(-1,0)(-1,3)
%  value
\rput(-0.7,3){(3)}
%  position
\rput(-1,-0.3){-1}


% line
\psline{-*}(0,0)(0,2)
%  value
\rput(0.3,2){(2)}
%  position
\rput(0,-0.3){0}


% line
\psline{-*}(1,0)(1,3)
%  value
\rput(1.3,3){(3)}
%  position
\rput(1,-0.3){1}


% line
\psline{-*}(2,0)(2,2)
%  value
\rput(2.3,2){(2)}
%  position
\rput(2,-0.3){2}


% line
\psline{-*}(3,0)(3,3)
%  value
\rput(3.3,3){(3)}
%  position
\rput(3,-0.3){3}

% axes
\psline{->}(-3,0)(4,0)
\rput(4,-0.3){ $n$ }
\rput(4,3){ $x(n)$ }

\end{pspicture}
\end{center}

We can then write the signal $x$ as a linear combination of two signals $\Psi_0(n)$, and $\Psi_1(n)$:

% \img{images/deltas/bases/periodic.ps}

\psset{unit=1cm}
\begin{center}
\begin{pspicture}(-6,-1)(6,6)

\rput(-4.4, 0.5){$\cdots$}
\rput(5.4, 0.5){$\cdots$}
\rput(-4.4, 3.5){$\cdots$}
\rput(5.4, 3.5){$\cdots$}

    

% line
\psline{-*}(-4,3)(-4,4)
%  value
\rput(-3.7,4){(1)}
%  position
\rput(-4,2.7){-4}


% line
\psline{-*}(-3,3)(-3,3)
%  position
\rput(-3,2.7){-3}


% line
\psline{-*}(-2,3)(-2,4)
%  value
\rput(-1.7,4){(1)}
%  position
\rput(-2,2.7){-2}


% line
\psline{-*}(-1,3)(-1,3)
%  position
\rput(-1,2.7){-1}


% line
\psline{-*}(0,3)(0,4)
%  value
\rput(0.3,4){(1)}
%  position
\rput(0,2.7){0}


% line
\psline{-*}(1,3)(1,3)
%  position
\rput(1,2.7){1}


% line
\psline{-*}(2,3)(2,4)
%  value
\rput(2.3,4){(1)}
%  position
\rput(2,2.7){2}


% line
\psline{-*}(3,3)(3,3)
%  position
\rput(3,2.7){3}


% line
\psline{-*}(4,3)(4,4)
%  value
\rput(4.3,4){(1)}
%  position
\rput(4,2.7){4}

% axes
\psline{->}(-5,3)(5,3)
\rput(5,2.7){ $n$ }
\rput(5,4){ $\Psi_0(n)$ }


% line
\psline{-*}(-4,0)(-4,0)
%  position
\rput(-4,-0.3){-4}


% line
\psline{-*}(-3,0)(-3,1)
%  value
\rput(-2.7,1){(1)}
%  position
\rput(-3,-0.3){-3}


% line
\psline{-*}(-2,0)(-2,0)
%  position
\rput(-2,-0.3){-2}


% line
\psline{-*}(-1,0)(-1,1)
%  value
\rput(-0.7,1){(1)}
%  position
\rput(-1,-0.3){-1}


% line
\psline{-*}(0,0)(0,0)
%  position
\rput(0,-0.3){0}


% line
\psline{-*}(1,0)(1,1)
%  value
\rput(1.3,1){(1)}
%  position
\rput(1,-0.3){1}


% line
\psline{-*}(2,0)(2,0)
%  position
\rput(2,-0.3){2}


% line
\psline{-*}(3,0)(3,1)
%  value
\rput(3.3,1){(1)}
%  position
\rput(3,-0.3){3}


% line
\psline{-*}(4,0)(4,0)
%  position
\rput(4,-0.3){4}

% axes
\psline{->}(-5,0)(5,0)
\rput(5,-0.3){ $n$ }
\rput(5,1){ $\Psi_1(n)$ }

\end{pspicture}
\end{center}

Therefore, we can write

$$x(n) = 2\Psi_0(n) + 3\Psi_1(n)$$

Here is another way to decompose the signal:

\begin{align*}
\left[ \begin{array}{r} 2 \\ 3 \\ \end{array} \right]  &= 2  \left[ \begin{array}{r} 1 \\ 0 \\ \end{array} \right] + 3  \left[ \begin{array}{r} 0 \\ 1 \\ \end{array} \right] \\
x &= x(0)\Psi_0 + x(1)\Psi_1
\end{align*}

Fourier analysis is  a way of decomposing signals in terms of some special signals that tell us information:

% \img{images/projections/bases/bases.ps}

\psset{unit=1cm}
\begin{center}
\begin{pspicture}(-3,-6)(3,6)
    

% y-axis
\psline{->}(0,-6)(0,-1)

% x-axis
\psline{->}(-2.5,-3.5)(2.5,-3.5)


 % new vector 
\rput(0.8,-4.8){$\Psi_1 = \left[ \begin{array}{r} 1 \\ -1 \\ \end{array} \right]$}
\psline[linewidth=1.5 pt]{->}(0,-3.5)(1,-4.5)

 % new vector 
\rput(2.22487174976714,-2){$\vec{x}$}
\psline[linewidth=1.5 pt]{->}(0,-3.5)(2.42487174976714,-2.10000107243568)

 % new vector 
\rput(0.8,-2.5){$\Psi_0 = \left[ \begin{array}{r} 1 \\ 1 \\ \end{array} \right]$}
\psline[linewidth=1.5 pt]{->}(0,-3.5)(1,-2.5)

% y-axis
\psline{->}(0,0)(0,5)

% x-axis
\psline{->}(-2.5,2.5)(2.5,2.5)


 % new vector 
\rput(2.22487174976714,3.95){$\vec{x}$}
\psline[linewidth=1.5 pt]{->}(0,2.5)(2.42487174976714,3.89999892756432)

 % new vector 
\rput(1,2){$\Psi_0 = \left[ \begin{array}{r} 1 \\ 0 \\ \end{array} \right]$}
\psline[linewidth=1.5 pt]{->}(0,2.5)(0,3.5)

 % new vector 
\rput(0,3.5){$\Psi_1 = \left[ \begin{array}{r} 0 \\ 1 \\ \end{array} \right]$}
\psline[linewidth=1.5 pt]{->}(0,2.5)(1,2.5)

\end{pspicture}
\end{center}

What we want is to write $x$ as a linear combination of these signals:

$$ x = X_0\Psi_0 + X_1\Psi_1 $$

So to find $X_0$, we can project $\vec{x}$ onto $\Psi_0$:
 
\begin{align*}
\langle\vec{x}, \Psi_0\rangle &= \langle X_0\Psi_0 + X_1\Psi_1, \Psi_0\rangle \\
\langle\vec{x}, \Psi_0\rangle &= X_0\langle\Psi_0,\Psi_0\rangle +X_1\langle\Psi_1,\Psi_0\rangle \\
\langle\vec{x}, \Psi_0\rangle &= X_0\langle\Psi_0,\Psi_0\rangle + 0\quad \mbox{(because of orthogonality)}\\
X_0 &= \frac{\langle\vec{x}, \Psi_0\rangle }{\langle\Psi_0,\Psi_0\rangle}\\
\end{align*}

Fourier analysis says if we have a signal with period $p$, then we can represent the signal with complex exponentials that are harmonically related by a fundamental frequency $\omega_0 = 2\pi/p$:

\begin{nicebox}
$$ x(n) = \sum \limits_{k=0}^{p-1}X_ke^{ik\omega_0 n}  $$
\end{nicebox}

We can also write this relationship as 

\begin{align*}
x(n) &= \sum \limits_{k=0}^{p-1}X_k\Psi_k(n)  \quad \mbox{where } e^{ik\omega_0 n} = \Psi_k(n) \\
\end{align*}

Or even more simplified:

$$ x = \sum \limits_{k=\langle p\rangle}X_k\Psi_k  $$

% Examples

Let $p=2$, then $\omega_0 = 2\pi/2 = \pi$. 
\begin{align*}
\Psi_0(n) &= e^{i0\omega_0n} = 1 \\
\Psi_1(n) &= e^{i\omega_0n} = e^{i\pi n} = \lr{-1}^n \\
\end{align*}

% \img{images/deltas/single/single.ps}

\psset{unit=1cm}
\begin{center}
\begin{pspicture}(-3,-1)(4,4)
    

% line
\psline{-*}(0,0)(0,2)
%  value
\rput(0.3,2){(2)}
%  position
\rput(0,-0.3){0}


% line
\psline{-*}(1,0)(1,3)
%  value
\rput(1.3,3){(3)}
%  position
\rput(1,-0.3){1}

% axes
\psline{->}(-1,0)(2,0)
\rput(2,-0.3){ $n$ }
\rput(2,3){ $x(n)$ }

\end{pspicture}
\end{center}

How can we determine $\Psi_0$ and $\Psi_1$? Since the fundamental period is two, we need only one contiguous interval of 2. Lets use 0 and 1:

\begin{align*}
\Psi_0(0) = 1 \\
\Psi_0(1) = 1 \\
\Psi_1(0) = \lr{-1}^0 = 1 \\
\Psi_1(1) = \lr{-1}^1 = -1 \\
\end{align*}

Hence the basis vectors are as shown:

% \img{images/deltas/bases/single/single.ps}

\psset{unit=1cm}
\begin{center}
\begin{pspicture}(-3,-2)(5,5)
    

% line
\psline{-*}(0,3)(0,4)
%  value
\rput(0.3,4){(1)}
%  position
\rput(0,2.7){0}


% line
\psline{-*}(1,3)(1,4)
%  value
\rput(1.3,4){(1)}
%  position
\rput(1,2.7){1}

% axes
\psline{->}(-1,3)(2,3)
\rput(2,2.7){ $n$ }
\rput(2,4){ $\Psi_0(n)$ }


% line
\psline{-*}(0,0)(0,1)
%  value
\rput(0.3,1){(1)}
%  position
\rput(0,-0.3){0}


% line
\psline{-*}(1,0)(1,-1)
%  value
\rput(1.3,-1){(-1)}
%  position
\rput(1,0.3){1}

% axes
\psline{->}(-1,0)(2,0)
\rput(2,-0.3){ $n$ }
\rput(2,1){ $\Psi_1(n)$ }

\end{pspicture}
\end{center}

What frequencies can be present in a signal $\vec{x}$? The harmonics are given by a signal with period $p$ are $\{0,\omega_0,2\omega_0,\dots,(p-1)\omega_0\}$. Notice that $p\omega_0$ is missing. This is because $e^{ip\omega_0n}=e^{i2\pi n} = e^{i0n}$. Keep in mind that $\omega_0 = 2\pi/p$. In fact, the complex exponential basis of vectors is periodic with respect to $n$ and their indices $k$. 

\begin{align*}
\Psi_k(n+p) &= e^{ik\omega_0(n+p)}=e^{ik\omega_0n}e^{ik\omega_0p}=e^{ik\omega_0n} = \Psi_k(n) \\
\Psi_{k+p}(n) &= e^{i(k+p)\omega_0n} = e^{ik\omega_0n}e^{ip\omega_0n} = \Psi_k(n) 
\end{align*}

So we know that $\Psi_{-1}(n) = e^{-i\omega_0n} = \Psi_{p-1}(n) = e^{i(p-1)\omega_0n }$. So we can see that in general, we can write out a discrete fourier series expansion over any continuous set of $p$ integers. The notation used is
$$ x(n) = \sum \limits_{k=\langle p \rangle} X_ke^{ik\omega_0n}$$


Decomposition of Signals

\begin{claim}
For a signal written in terms of vectors that represent complex exponentials,
$$x(n) = \sum_{k=\langle p\rangle}X_k\Psi_k$$
the spanning set that makes up the set of vectors is an orthogonal set, in other words, 
$$ \Psi_k \perp \Psi_\ell \quad k \neq \ell$$
\end{claim}

\begin{proof}

For $\Psi_k(n) = e^{ik\omega_0}$, and $\Psi_\ell = e^{i\ell\omega_0n}$, we can write
$\Psi_k = 
\left[
\begin{array}{c}
\Psi_k(0) \\
\Psi_k(1) \\
\vdots \\
\Psi_k(p-1) \\
\end{array}
\right]
$, and 
$\Psi_\ell =
\left[
\begin{array}{c}
\Psi_\ell(0) \\
\Psi_\ell(1) \\
\vdots \\
\Psi_\ell(p-1) \\
\end{array}
\right]
$. 

Note that for an aperiodic signal, the inner product can be written as $<\Psi_k,\Psi_\ell> = \sum \limits_{n=-\infty}^{\infty}\Psi_k(n)\Psi_\ell^*(n) $ or $\int_{-\infty}^{\infty}\Psi_k(t)\Psi_\ell^*(t)dt$. For this proof, we will use the summation for a periodic signal. We can take the inner product

\begin{align*}
\langle\Psi_k,\Psi_\ell\rangle &= \sum \limits_{n=0}^{p-1}\Psi_k(n)\Psi_\ell^*(n) \\
\langle\Psi_k,\Psi_\ell\rangle &= \sum \limits_{n=0}^{p-1} e^{ik\omega_0n}e^{-i\ell\omega_0n} \\
\langle\Psi_k,\Psi_\ell\rangle &= \sum \limits_{n=0}^{p-1} e^{i(k-\ell)\omega_0n} \\
\langle\Psi_k,\Psi_\ell\rangle &= \sum \limits_{n=0}^{p-1} \lr{e^{i(k-\ell)\omega_0}}^n \\
\end{align*}

Before we arrive at our answer, lets take a slight mathematical detour. Recall that we can write a sum $S$ as 
\begin{align*}

S &= \sum \limits_{k=0}^{\infty}\alpha^k \\
S &= 1 + \alpha + \alpha^2 + \cdots  \\
\alpha S &= \alpha + \alpha^2 + \alpha^3 + \cdots  \\
(1-\alpha)S &= 1 \\
S &= \frac{1}{1-\alpha} \quad \mbox {if } \alpha \neq 1 
\end{align*}

or for a finite sum
\begin{align*}
S &= \sum \limits_{n=A}^{B}\alpha^n \\
S &= \alpha^A + \alpha^{A+1} + \cdots + \alpha^B \\
\alpha S &= \alpha^{A+1} + \alpha^{A+2} + \cdots + \alpha^{B+1} \\
(1-\alpha)S &= \alpha^{B+1} - \alpha^A \\
S &= \frac{\alpha^{B+1}-\alpha^{A}}{1-\alpha} \quad \mbox{if }\alpha \neq 1 \\
S &= \begin{cases}
\frac{\alpha^{B+1}-\alpha^{A}}{1-\alpha} & \alpha\neq1 \\
B-A+1 & \alpha=1 \\
\end{cases}
\end{align*}

Now back to our proof:
\begin{align*}

\langle\Psi_k,\Psi_\ell\rangle &= \sum \limits_{n=0}^{p-1} \lr{e^{i(k-\ell)\omega_0}}^n \\
\langle\Psi_k,\Psi_\ell\rangle &= \begin{cases} \frac{\lr{e^{i(k-\ell)\omega_0}}^p-\lr{e^{i(k-\ell)\omega_0}}^0}{1-e^{i(k-\ell)\omega_0}} & k\neq\ell \\ (p-1)-0+1 & k=l \\ \end{cases} \\
\langle\Psi_k,\Psi_\ell\rangle &= \begin{cases} 0 & k\neq\ell\\ p & k=l \\ \end{cases}
\end{align*}

\end{proof}

We can generalize the result of the above proof further as

$$ \langle\Psi_k,\Psi_\ell\rangle = p\delta(k-\ell) $$

This works well because the inner product of a vector with itself as the \emph{norm} squared, and the inner product with any other orthogonal vector is 0.
$$\langle\Psi_k,\Psi_k\rangle = \norm{\Psi_k}^2 = p$$

A few properties about the inner product:
\begin{align*}
\langle f,g\rangle &= f^Tg^* \\
\langle \alpha f,g \rangle &= \alpha\langle f,g\rangle \\
\langle f,\beta g \rangle &= \beta^* \langle f,g\rangle \\
\langle \sum_k \alpha_k f_k, g\rangle &= \sum_k \alpha_k\langle f_k,g\rangle \\
\end{align*}

So to find $X_\ell$, we can project $\vec{x}$ onto $\Psi_\ell$. 
\begin{align*}
\langle\vec{x}, \Psi_\ell\rangle &= \langle\langle X_0\Psi_0 + \cdots + X_\ell\Psi_\ell + \cdots + X_{p-1}\Psi_{p-1}, \Psi_\ell\rangle \\
\langle\vec{x}, \Psi_\ell\rangle &= X_0\langle\Psi_0,\Psi_\ell\rangle + \cdots + X_\ell\langle\Psi_\ell,\Psi_\ell\rangle + \cdots + X_{p-1}\langle\Psi_{p-1},\Psi_\ell\rangle \\
\langle\vec{x}, \Psi_\ell\rangle &= X_\ell\langle\Psi_\ell,\Psi_\ell\rangle \quad \mbox{(all other inner products were 0)}\\
X_\ell &= \frac{\langle\vec{x}, \Psi_\ell\rangle }{\langle\Psi_\ell,\Psi_\ell\rangle}\\
X_\ell &= \frac{\langle\vec{x}, \Psi_\ell\rangle }{p}\\
X_\ell &= \frac{\vec{x}^T\Psi_\ell^* }{p}\\
X_\ell &= \frac{1}{p}\sum \limits_{n=0}^{p-1}x(n)\Psi_\ell^*(n) \\
X_\ell &= \frac{1}{p}\sum \limits_{n=0}^{p-1}x(n)e^{-i\ell\omega_0n} \\
\end{align*}

With the discrete fourier series, we can write signals in two distinct forms. We can write a signal in the time domain as a series of complex exponentials which can tell us what happens in the frequency domain:

\begin{nicebox}
\begin{align*}
 x(n) &= \sum \limits_{k=\langle p\rangle}X_ke^{ik\omega_0n}  \quad &\mbox{(synthesis equation)}
\end{align*}
\end{nicebox}

The coefficient in the frequency domain tells us the amount that a certain frequency contributes to the overall signal, which is given by the running sum of the product of the signal in the time domain and the frequency of interest:

\begin{nicebox}
\begin{align*}
 X_k &= \frac{1}{p} \sum \limits_{k=\langle p\rangle}x(n)e^{-ik\omega_0n} \quad &\mbox{(analysis equation)}
\end{align*}
\end{nicebox}



2 Week 2