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}
