Fourier series - by Ray Betz

Fourier Series

If

1. $x(t)=x(t+T)$
2. Dirichlet conditions are satisfied

then we can write

${\mathbf {x}}(t)=\sum _{k=-\infty }^{\infty }\alpha _{k}e^{\frac {j2\pi kt}{T}}$

The above equation is called the complex fourier series. Given $x(t)$, we may determine $\alpha _{k}$ by taking the inner product of $\alpha _{k}$ with $x(t)$. Let us assume a solution for $\alpha _{k}$ of the form $e^{\frac {j2\pi nt}{T}}$. Now we take the inner product of $\alpha _{k}$ with $x(t)$ over the interval of one period, $T$. $<\alpha _{k}|x(t)>=<e^{\frac {j2\pi nt}{T}}|\sum _{k=-\infty }^{\infty }\alpha _{k}e^{\frac {j2\pi kt}{T}}>$ $=\int _{-{\frac {T}{2}}}^{\frac {T}{2}}x(t)e^{\frac {-j2\pi nt}{T}}dt$ $=\int _{-{\frac {T}{2}}}^{\frac {T}{2}}\sum _{k=-\infty }^{\infty }\alpha _{k}e^{\frac {j2\pi kt}{T}}e^{\frac {-j2\pi nt}{T}}dt$ $=\sum _{k=-\infty }^{\infty }\alpha _{k}\int _{-{\frac {T}{2}}}^{\frac {T}{2}}e^{\frac {j2\pi (k-n)t}{T}}dt$

If $k=n$ then,

$\int _{-{\frac {T}{2}}}^{\frac {T}{2}}e^{\frac {j2\pi (k-n)t}{T}}dt=\int _{-{\frac {T}{2}}}^{\frac {T}{2}}1dt=T$

If $k\neq n$ then,

$\int _{-{\frac {T}{2}}}^{\frac {T}{2}}e^{\frac {j2\pi (k-n)t}{T}}dt=0$

We can simplify the above two conclusion into one equation. (What is the delta function below?)

$\sum _{k=-\infty }^{\infty }\alpha _{k}\int _{-{\frac {T}{2}}}^{\frac {T}{2}}e^{\frac {j2\pi (k-n)t}{T}}dt=\sum _{k=-\infty }^{\infty }T\delta _{k,n}\alpha _{k}=T\alpha _{n}$

So, we conclude $\alpha _{n}={\frac {1}{T}}\int _{-{\frac {T}{2}}}^{\frac {T}{2}}x(t)e^{\frac {-j2\pi nt}{T}}dt$

Orthogonal Functions

The function $y_{n}(t)$ and $y_{m}(t)$ are orthogonal on $(a,b)$ if and only if $<y_{n}(t)|y_{m}(t)>=\int _{a}^{b}y_{n}^{*}(t)y_{m}(t)dt=0$.

The set of functions are orthonormal if and only if $<y_{n}(t)|y_{m}(t)>=\int _{a}^{b}y_{n}^{*}(t)y_{m}(t)dt=\delta _{m,n}$.

Linear Systems

Let us say we have a linear time invarient system, where $x(t)$ is the input and $y(t)$ is the output. What outputs do we get as we put different inputs into this system? File:Linear System.JPG

If we put in an impulse response, $\delta (t)$, then we get out $h(t)$. What would happen if we put a time delayed impulse signal, $\delta (t-u)$, into the system? The output response would be a time delayed $h(t)$, or $h(t-u)$, because the system is time invarient. So, no matter when we put in our signal the response would come out the same (just time delayed).

What if we now multiplied our impulse by a coefficient? Since our system is linear, the proportionality property applies. If we put $x(u)\delta (t-u)$ into our system then we should get out $x(u)h(t-u)$.

By the superposition property(because we have a linear system) we may put into the system the integral of $x(u)\delta (t-u)$ and we would get out $\int _{-\infty }^{\infty }x(u)h(t-u)du$. What would we get if we put $e^{j2\pi ft}$ into our system? We could find out by plugging $e^{j2\pi ft}$ in for $x(u)$ in the integral that we just found the output for above. If we do a change of variables ($v=t-u$, and $dv=-du$) we get $\int _{-\infty }^{\infty }x(u)h(t-u)du=\int _{-\infty }^{\infty }e^{j2\pi ft}h(t-u)du=-\int _{\infty }^{-\infty }e^{j2\pi f(t-v)}h(v)dv=e^{j2\pi ft}\int _{-\infty }^{\infty }h(v)e^{-j2\pi fv}dv$. By pulling $e^{j2\pi ft}$ out of the integral and calling the remaining integral $B_{k}$ we get $e^{j2\pi ft}B_{k}$.

INPUT	OUTPUT	REASON
$\delta (t)$	$h(t)$	Given
$\delta (t-u)$	$h(t-u)$	Time Invarient
$x(u)\delta (t-u)$	$x(u)h(t-u)$	Proportionality
$\int _{-\infty }^{\infty }x(u)\delta (t-u)du$	$\int _{-\infty }^{\infty }x(u)h(t-u)du$	Superposition
$\int _{-\infty }^{\infty }e^{j2\pi ft}h(t-u)du$	$e^{j2\pi ft}\int _{-\infty }^{\infty }e^{j2\pi vt}h(v)dv$	Superposition
$e^{j2\pi ft}$	$e^{j2\pi ft}B_{k}$	Superposition (from above)

Fourier Series (indepth)

I would like to take a closer look at $\alpha _{k}$ in the Fourier Series. Hopefully this will provide a better understanding of $\alpha _{k}$.

We will seperate x(t) into three parts; where $\alpha _{k}$ is negative, zero, and positive. ${\mathbf {x}}(t)=\sum _{k=-\infty }^{\infty }\alpha _{k}e^{\frac {j2\pi kt}{T}}=\sum _{k=-\infty }^{-1}\alpha _{k}e^{\frac {j2\pi kt}{T}}+\alpha _{0}+\sum _{k=1}^{\infty }\alpha _{k}e^{\frac {j2\pi kt}{T}}$

Now, by substituting $n=-k$ into the summation where $k$ is negative and substituting $n=k$ into the summation where $k$ is positive we get: $\sum _{n=1}^{\infty }\alpha _{-n}e^{\frac {-j2\pi nt}{T}}+\alpha _{0}+\sum _{n=1}^{\infty }\alpha _{n}e^{\frac {j2\pi nt}{T}}$

Recall that $\alpha _{n}={\frac {1}{T}}\int _{-{\frac {T}{2}}}^{\frac {T}{2}}x(u)e^{\frac {-j2\pi nt}{T}}dt$

If $x(t)$ is real, then $\alpha _{n}^{*}=\alpha _{-n}$. Let us assume that $x(t)$ is real.

$x(t)=\alpha _{0}+\sum _{n=1}^{\infty }(\alpha _{n}e^{\frac {j2\pi nt}{T}}+\alpha _{n}^{*}e^{\frac {-j2\pi nt}{T}})$

Recall that $y+y^{*}=2Re(y)$ Here is further clarification on this property

So, we may write:

$x(t)=\alpha _{0}+\sum _{n=1}^{\infty }2Re(\alpha _{n}e^{\frac {j2\pi nt}{T}})$

Fourier Transform

Fourier transforms emerge because we want to be able to make Fourier expressions of non-periodic functions. We can take the limit of those non-periodic functions to get a fourier expression for the function.

Remember that: $x(t)=x(t+T)=\sum _{k=-\infty }^{\infty }\alpha _{k}e^{\frac {j2\pi kt}{T}}=\sum _{k=-\infty }^{\infty }1/T\int _{-{\frac {T}{2}}}^{\frac {T}{2}}x(u)e^{\frac {-j2\pi ku}{T}}due^{\frac {j2\pi kt}{T}}$

So, $\lim _{x\to \infty }x(t)=\int _{-\infty }^{\infty }(\int _{-\infty }^{\infty }x(u)e^{-j2\pi fu}du)e^{j2\pi ft}df$

From the above limit we define $x(t)$ and $X(f)$.

$x(t)={\mathcal {F}}^{-1}[X(f)]=\int _{-\infty }^{\infty }X(f)e^{j2\pi ft}df$

$X(f)={\mathcal {F}}[x(t)]=\int _{-\infty }^{\infty }x(t)e^{-j2\pi ft}dt$

By using the above transforms we can now change a function from the frequency domain to the time domain or vise versa. We are not limited to just one domain but can use both of them.

We can take the derivitive of $x(t)$ and then put it in terms of the reverse fourier transform.

${\frac {dx}{dt}}=\int _{-\infty }^{\infty }j2\pi fX(f)e^{j2\pi ft}df={\mathcal {F}}^{-1}[j2\pi fX(f)]$

What happens if we just shift the time of $x(t)$?

$x(t-t_{0})=\int _{-\infty }^{\infty }X(f)e^{j2\pi f(t-t_{0})}df=\int _{-\infty }^{\infty }e^{-j2\pi ft_{0}}X(f)e^{j2\pi ft}df={\mathcal {F}}^{-1}[e^{-j2\pi ft_{0}}X(f)]$

In the same way, if we shift the frequency we get:

$X(f-f_{0})=\int _{-\infty }^{\infty }x(t)e^{j2\pi (f-f_{0})t}dt=\int _{-\infty }^{\infty }e^{-j2\pi tf_{0}}x(t)e^{j2\pi ft}df={\mathcal {F}}[e^{-j2\pi tf_{0}}x(t)]$

What would be the Fourier transform of $cos(2/pif_{0}t)x(t)$?

${\mathcal {F}}[cos(2\pi f_{0}t)x(t)]=\int _{-\infty }^{\infty }x(t)cos(2\pi f_{0}t)e^{-j2\pi ft}dt=\int _{-\infty }^{\infty }{\frac {e^{j2\pi f_{0}t}+e^{-j2\pi f_{0}t}}{2}}x(t)e^{-j2\pi ft}dt$

$={\frac {1}{2}}\int _{-\infty }^{\infty }x(t)e^{-j2\pi (f-f_{0})t}dt+{\frac {1}{2}}\int _{-\infty }^{\infty }x(t)e^{j2\pi (f+f_{0})t}dt={\frac {1}{2}}X(f-f_{0})+{\frac {1}{2}}X(f+f_{0})$

What would happen if we multiplied our time by a constant in $x(t)$? We will substitute $u=at$ and $du=adt$. If $a\neq 0$:

${\mathcal {F}}[x(at)]=\int _{-\infty }^{\infty }x(at)e^{-j2\pi ft}dt=\int _{-\infty }^{\infty }x(u)e^{\frac {-j2\pi fu}{a}}{\frac {du}{|a|}}={\frac {1}{|a|}}X({\frac {f}{a}})$

Ok, lets take the fourier transform of the fourier series.

${\mathcal {F}}[\sum _{n=-\infty }^{\infty }\alpha _{n}e^{\frac {j2\pi nt}{T}}]=\int _{-\infty }^{\infty }\sum _{n=-\infty }^{\infty }\alpha _{n}e^{\frac {j2\pi nt}{T}}e^{-j2\pi ft}dt=\sum _{n=-\infty }^{\infty }\alpha _{n}\int _{-\infty }^{\infty }e^{-j2\pi (f-{\frac {n}{T}})t}dt=\sum _{n=-\infty }^{\infty }\alpha _{n}\delta (f-{\frac {n}{T}})$

Remember: $\delta (f)=\int _{-\infty }^{\infty }e^{-j2\pi ft}dt$

CD Player

Below is a diagram of how the information on a CD player is read and processed. As you can see the information on the CD is processed by the D/A converter and then sent through a low pass filter and then to the speaker. If you were recording sound, the sound would be captured by a microphone. Then, it should be sent through a low pass filter. The reason you want a low-pass filter is to keep high frequencies (that you don't intend to record) from being recorded. If a high frequency was recorded at say 30 KHz and the maximum frequency you intended to record was 20KHz, then when you played back the recording you would here a tone at 10KHz. From the filter the signal goes onto the A/D converter and then it is ready to be put on the CD. Recording signals (as just described) is essentially the reverse of the operation pictured below.

File:CDsystem.jpg

In Time Domain:

Let's start with a signal $h(t)$, as shown in the below picture. In this signal there is an infinite amount of information. Obviously, we can't hold it all in a computer, but we could take samples every $T$. Lets do that by multiplying $h(t)$ by $\sum _{n=-\infty }^{\infty }\delta (t-nT)$. Since the magnitude of our delta function is one, we get a series of delta functions that record the value of $h(t)$ at intervals of $T$. This gives us a result that looks like: $h(t)\sum _{n=-\infty }^{\infty }\delta (t-nT)=\sum _{n=-\infty }^{\infty }x(nt)\delta (t-nT)$

In Frequency Domain:

In the frequency domain we start with $H(f)$. Now we are in frequency, so we must convolve instead of multiply like we did in the time domain. We would have to convolve $H(f)$ with ${\mathcal {F}}[\sum _{n=-\infty }^{\infty }\delta (t-nT)]$.

Aside:${\mathcal {F}}[\sum _{n=-\infty }^{\infty }\delta (t-nT)]=\int _{-\infty }^{\infty }\sum _{n=-\infty }^{\infty }\delta (t-nT)e^{j2\pi ft}dt=\sum _{n=-\infty }^{\infty }\int _{-\infty }^{\infty }\delta (t-nT)e^{j2\pi ft}dt=\sum _{n=-\infty }^{\infty }e^{j2\pi fnT}$

This result looks it could be a fourier series. We would like to get our result in terms of delta functions. As shown below, the periodic delta functions could be represented as a fourier series with coefficients $\alpha _{m}$.

$\sum _{n=-\infty }^{\infty }\delta (t-nT)=\sum _{m=-\infty }^{\infty }\alpha _{m}e^{j2\pi mt}$

Now we can solve for $\alpha _{m}$.

$\alpha _{m}={\frac {1}{T}}\int _{\frac {-T}{2}}^{\frac {T}{2}}\sum _{n=-\infty }^{\infty }\delta (t-nT)e^{\frac {j2\pi mt}{T}}dt={\frac {1}{T}}\int _{\frac {-T}{2}}^{\frac {T}{2}}\delta (t)e^{\frac {j2\pi mt}{T}}dt={\frac {1}{T}}$

Since the only delta function within the integration limits is the delta function at $t=0$, we can take out the summation and just leave one delta function. Then, evaluating the integral at $t=0$ we get ${\frac {1}{T}}$

$\sum _{n=-\infty }^{\infty }\delta (t-nT)=\sum _{n=-\infty }^{\infty }{\frac {1}{T}}e^{\frac {j2\pi kt}{T}}$ ${\mathcal {F}}[\sum _{n=-\infty }^{\infty }\delta (t-nT)]={\mathcal {F}}[\sum _{n=-\infty }^{\infty }{\frac {1}{T}}e^{\frac {j2\pi kt}{T}}]=\sum _{n=-\infty }^{\infty }{\frac {1}{T}}\int _{-\infty }^{\infty }e^{\frac {j2\pi kt}{T}}e^{-j2\pi ft}dt={\frac {1}{T}}\sum _{n=-\infty }^{\infty }\int _{-\infty }^{\infty }e^{-j2\pi (f-{\frac {m}{T}}t}dt={\frac {1}{T}}\sum _{n=-\infty }^{\infty }\delta (f-{\frac {n}{T}})$

Now wer are ready to take the convolution.

$H(f)*{\frac {1}{T}}\sum _{n=-\infty }^{\infty }\delta (f-{\frac {n}{T}})={\frac {1}{T}}\sum _{n=-\infty }^{\infty }H(f-{\frac {n}{T}})$

File:Barnsasample.jpg

Time Domain

In order to output as sound any of the signals that we have we must run them through a D/A converter. This is like convolving the below signal by a step function $p(t)=U(t+{\frac {T}{2}})-U(t-{\frac {T}{2}})$.

This gives us $\sum (nt)p(t-nT)$. This is what the signal looks like as it is output through the D/A converter.

Frequency Domain

To find out what we would multiply by in the frequency domain we just take the inverse fourier transform of $p(t)$ and we get $P(f)={\frac {sin({\frac {\pi t}{T}})}{\frac {\pi t}{T}}}$.

By multiplying ${\frac {1}{T}}\sum _{n=-\infty }^{\infty }X(f-{\frac {n}{T}})P(f)=X(f)$. This is hopefully close to what we started with for a signal.

File:BarnsaDA.jpg

For 2 times oversampling:

In time, multiply: $\sum _{n=-\infty }^{\infty }x(nT)\delta (t-nT)$ by $\sum _{n=-M}^{M}h(m{\frac {T}{2}})\delta (t-{\frac {mT}{2}})$. This profides points that are interpolated and makes our output sound better because it looks closer to the original wave.

In frequency, convolve: ${\frac {1}{T}}\sum _{n=-\infty }^{\infty }X(f-{\frac {n}{T}})$ with $\sum _{m=-M}^{M}h({\frac {mT}{2}})e^{\frac {-j2\pi mf}{\frac {2}{T}}}$. The X(f) that you get is great because there is little distortion near the original frequency plot. This means that you can use a cheaper low-pass filter then you would otherwise have been able to.

Nyquist Frequency

If you are sampling at a frequency of 40 KHz, then the highest frequency that you can reproduce is 20 KHz. The nyquist frequency, would be 20 KHz, the highest frequency that can be reproduced for a given sampling rate.

FIR Filters

A finite impulse response filter (FIR filter) is a digital filter that is applied to data before sending to out a D/A filter. This type of filter allows for compensation of the signal before is it destorted so that it will look as it was originally recorded. Using an FIR filter also allows us to put a cheap low-pass filter on after the D/A converter because the signal has been compensated so it doesn't take as good a low-pass filter as it would without the FIR filter.

Note: From the Circular Convolution we get: $y(n)=\sum _{m=0}^{N-1}h(m)x(n-m)$

Discrete Fourier Transforms (DFTs)

The DFT allows us to take a sample of some signal that is not periodic with time and take the Fourier series of it. There is the DFT and the Inverse DFT listed below.

DFT

$x(m)=\sum _{n=0}^{N-1}x(n)e^{\frac {-j2\pi mn}{N}}$

IDFT

$x(k)={\frac {1}{N}}\sum _{n=0}^{N-1}x(n)e^{\frac {j2\pi kn}{N}}$

With the DFT all the negative frequency components are just the complex conjugate of the positive frequency components.

One problem with the DFT is that if the sample taken does not begin and end at zero, (or the same point) then we get what is called leakage. Because the DFT is discrete, if the end of the sample is not at the same place it began then it will make a jump back to the point that it began (leakage). This is because the DFT repeats the recorded section of signal over and over. It is this periodic manner of the DFT that allows us to reproduce a discrete signal that is not periodic. The DFT and IDFT are periodic with period N. This can be easily proved by simplifying $x(n+N)$.

Adaptive FIR Filters

File:Adaptive.JPG

It should be noted that in the above diagram, $e(n)=y(n)-r(n)=[\sum _{k=0}^{N-1}h_{n}(k)x(n-k)]-r(n)$. The goal of an adaptive FIR filter is to drive the error, e(n), to zero. If we consider that this is a two coefficient filter and we have a contour plot of $e^{2}(n)$ then we want to travel in the direction of the negative gradient to minimize the error. Let us say that $\mu$ is the stepping size. So... $\triangle h_{n}(m)=-{\frac {\partial (e^{2}(n))}{\partial h_{n}(m)}}\mu =-\mu 2e(n){\frac {\partial (e(n))}{\partial h_{n}(m)}}=-2\mu e(n)x(n-m)$

What would $h_{n+1}(m)$ look like?

$h_{n+1}(m)=h_{n}(m)+\triangle h_{n}(m)=h_{n}(m)-2\mu (y(n)-r(n))x(n-m)=h_{n}(m)-2\mu ([\sum _{k=0}^{N-1}h_{n}(k)x(n-k)]-r(n))x(n-m)$

How might one find an unknown transfer function? Lets use the example of the tuner upper. The idea here is that we want to remove a sine wave from the signal and leave the original signal(voice) in place.

File:AdaptiveFilter.JPG