Discrete Fourier Transform

From Mainsequence

Jump to: navigation, search


Contents

Related links to Wikipedia


Introduction

The Fourier transform is a construction for creating a new representation for an ordered set of numbers. The above links lead to some web pages on this topic that I won't reiterate. Rather the point here is to take a simple mechanical approach, rather like a game, to look at some patterns in the discrete Fourier transform or DFT.


The discrete Fourier transform is something of a gateway to signal processing in the way that say a derivative is a gateway to calculus. In particular it decomposes a time-like signal into a collection of sinusoidal components of different characteristic frequencies. This in turn leads to an analysis of constituent periodicity, or 'what rhythms led to the original observation?'


The mechanics of the DFT quickly become tedious to do by hand so they are invariably done by a computer program. The idea here is to do a couple of simplest cases by hand and then a few slightly more complicated cases using a simple computer program.


There are three aims behind all this:


1. Exhibit complex numbers and arithmetic as a simple construction independent of the unfortunate term imaginary.
2. Identify some patterns in DFTs and IDFTs that suggest signal processing applications.
3. Lay out groundwork for transforming the zeta function along the critical line to recover the distribution of primes \;\pi(x).

Complex numbers

A complex number is defined as a pair of real numbers \;(a, b). I'll start by making the a's and b's 0, 1, or -1. Hence for example (0, 0), (1, 0), (-1, 0), (0, 1), (0, -1), (1, 1), (-1, -1), (-1, 1), (1, -1) are all good complex numbers for starters. The familiar real numbers are simply complex numbers where the second number is identically zero, as in items 1, 2, and 3 in the above list.


Complex numbers are added according to: \;(a, b) + (c, d) = (a + c, b + d).
Complex numbers are multiplied according to: \;(a, b) \cdot (c, d) = (a \cdot c - b \cdot d, a \cdot d + b \cdot c).

The rule for the Discrete Fourier Transform (DFT)

Take \;N ordered (sequential) complex values \;x_n; then the DFT is \;N new ordered complex values \;X_k. Each \;X_k accumulates a little piece of every single \;x_n by means of this rule:


X_k = \sum_{n=0}^{N-1} x_n e^{-\frac{2 \pi i k n}{N}} = \sum_{n=0}^{N-1} x_n \cdot (\cos{\frac{2 \pi k n}{N}}, -\sin{\frac{2 \pi k n}{N}})


Incidentally since this is a sum-over-products applied across a vector it may also be written as a matrix multiplication.


Incidentally number two there is a weird trick for differentiation of \;x_n in the frequency domain that is worth including in this discussion, particularly as it might be applied first in 1D and then in 2D. This might serve as a doorway into "weird things one can do in frequency space".

Simple example

Take two real numbers (0, 0) and (1, 0) and create their Fourier transform \;X_0, X_1:


\;X_0 = (0, 0) \cdot (cos{(0)}, sin{(0)}) + (1, 0) \cdot (cos{(0)}, sin{(0)}) = (1, 0)


\;X_1 = (0, 0) \cdot (cos{(0)}, sin{(0)}) + (1, 0) \cdot (cos{(2 \pi)}, sin{(2 \pi)}) = (1, 0)


Painless enough but doesn't illustrate why we care. I'm going to write a little Excel program to produce DFTs for 3-component and 4-component series.


More examples

Let's call an \;N-valued sequence of complex numbers an \;N-vector just for grins. 

Some real-valued 3-vectors and their transforms:

( 1,  0) ( 1,  0) ( 1,  0)   -->
( 1,  0) ( 0,  0) (-1,  0)   -->
( 0,  0) ( 1,  0) ( 0,  0)   -->
( 0,  0) ( 1,  0) (-1,  0)   -->


Some complex-valued 3-vectors plus transforms:

( 0,  0) ( 1,  1) (-1, -1)
( 0,  1) ( 1, -1) (-1,  0)
( 0,  1) ( 1, -1) (-1,  0)


Some real-valued 4-vectors and their transforms:



Some complex-valued 4-vectors and their transforms:

Plan

  • Do 3- and 4-element DFTs for simple cases
  • Show that the IDFT recovers the original values (use 1/N)
  • Observations on patterns
  • Consider an unevenly spaced series of harmonic frequencies and show how to add them together...

Retrieved from "http://robfatland.net/mainsequence/index.php?title=Discrete_Fourier_Transform"
Personal tools