Fourier analysis

From HvWiki

Any physically realisable signal can be decomposed into a sum of sine waves. This allows any theory applying to sinusoidal signals in a linear system to be generalised to all signals.

1 Fourier Series
2 Fourier Transform
3 Digital Realisations of the Fourier Transform
- 3.1 Discrete Fourier Transform
- 3.2 Fast Fourier Transform
4 External links

[edit]

Fourier Series

The Fourier Series expansion applies to periodic signals, ie. signals which repeat themselves forever.

A periodic signal can be decomposed into a DC component and a set of sine and cosine harmonics. For a signal $f (x)$ of period $T$ :

$f(x) = a_0 + \sum_{k=1}^{\infty}\left ( a_k\cos(\omega kx) + b_k\sin(\omega kx)\right )$

Where:

$a_0 = \frac{2\pi}{\omega}\int_{-T/2}^{T/2} f(x).dx$ ie. $a 0$ is the average value of the function, the DC component.

and for $k > 0$ :

$a_k = \frac{4\pi}{\omega}\int_{-T/2}^{T/2} f(x)\cos(\omega kx).dx$ $b_k = \frac{4\pi}{\omega}\int_{-T/2}^{T/2} f(x)\sin(\omega kx).dx$

Also, $ω = 2π f$ and $T = 1 / f$ .

[edit]

Theorems and Qualitive Concepts

The fourier expansion for the sum of two signals is the sum of the expansions of each signal.

If a signal is even, then it expands to purely cosine terms. If it is odd, it expands to purely sine terms. See Even and Odd Functions

Since a square wave integrates to a sine wave, the expansion for a triangle wave can be taken by just integrating the expansion for a square wave. Likewise for differentiation and all signals.

Changing the phase of a signal changes the expansion, so there are multiple expansions for a "square wave".

[edit]

Example of Use

What is the output of this circuit?

Squarewave applied to low-pass RC filter

[edit]

Finding the Expansion

If the signal is a common one then it's likely the expansion can just be looked up in a reference such as the one below. Then this step can be skipped.

If we align the square wave like in the diagram, it is an odd function and hence the expansion is only made up of sine terms. Also, because of symmetry, we only have to calculate for the second half of the period and just double the result.

[edit]

Applying Circuit Theory

The square wave is a common signal and its expansion can be looked up.

Using AC circuit theory, if a sine wave $A sin(ω t)$ is the input to this RC network, the output is $\frac {A . X_C}{\sqrt{R^2 + X_C^2}} \sin (\omega t + \phi) =$

[edit]

Common Expansions

[edit]

Square Wave

The Fourier series for an odd square wave contains only the odd harmonics of the sine wave. Ie: $\frac{4}{\pi} \left ( \sin (\omega t) + \sin (3\omega t) + \sin (5 \omega t) + ... \right )$

[edit]

Fourier Transform

The Fourier transform is more general than the Fourier Series and can be applied to any physical signal.

The Fourier transform is defined as: $F(s) = \int_\infty^\infty f(t)( \cos(-2 \pi s t) + i\sin (-2 \pi s t)).dx$

Note that $cos(x) = cos( - x)$ so the minus sign was left in the above purely for symmetry. Also, $cos(x) + i sin(x) = e i x$ so this transform is often more neatly written: $F(s) = \int_\infty^\infty f(t) e^{-2\pi s t}.dx$

[edit]

Repeated and Inverse Transforms

[edit]

Basic Theorems

Here $f * g$ means the convolution of $f$ with $g$ , while $\bar{f}$ is the transform of $f$ . $\bar{f} = F$ can also be written $f \supset F$ .

[edit]

Additivity

$f + g \supset \bar{f} + \bar{g}$

[edit]

Similarity

If $f(x) \supset F(s)$ then $f(ax) \supset \frac{F\left (\frac{s}{a} \right )}{|a|}$ .

This means that as a signal gets narrower, it contains higher and higher frequencies. The extreme end of this is the Dirac Delta Function which transforms to a completely uniform unit spread of every single possible freqency.

[edit]

Convolution (or Multiplicativity)

$f * g \supset \bar{f} \bar{g}$

$fg \supset \bar{f} * \bar{g}$

[edit]

Periodic Functions

Periodic functions are generally best analysed with the Fourier series.

In the strictest sense, periodic functions do not have a Fourier transform, however, if you accept the Dirac Delta Function as a true function, you can find transforms of periodic functions.

See information on the shah function, $I I I$ on the Dirac Delta Function page.

A periodic function can be treated as a finite "building block" function convolved with $I I I (t)$ . For example, a square wave is a single square repeated infinitely by convolution with shah.

Symbollically then, a periodic function is $p (t) = g (t) * I I I (t)$

And because $III \supset III$ , and from the convolution theorem above: $p \supset \bar{g}(s) III(s)f$

In other words, a truly periodic function only contains exact harmonics. The transform is taken by taking the transform of the fundamental "building block" and sampling at regular intervals.

[edit]

Common Transforms

Table of Common Transforms
$δ(x)$	$1$
$I I I (x))$	$I I I (s)$
$e^{-\pi x^2})$	$e^{-\pi s^2}$

[edit]

Digital Realisations of the Fourier Transform

[edit]

Discrete Fourier Transform

The DFT has no restrictions on array size (n) and is hard to get wrong. It is a very expensive transform that takes O*n² operations.

'Complex Forward transform
For i = 0 To n - 1
   arg = -(2 * PI * i) / n
   For k = 0 To n - 1
       cosarg = Cos(k * arg)
       sinarg = Sin(k * arg)
       dataOutR(i) = dataOutR(i) + (dataInR(k) * cosarg - dataInI(k) * sinarg)
       dataOutI(i) = dataOutI(i) + (dataInR(k) * sinarg + dataInI(k) * cosarg)
   Next k
   dataOutR(i) = dataOutR(i) / n
   dataOutI(i) = dataOutI(i) / n
Next i

'Real Forward transform
For i = 0 To n - 1
   arg = -(2 * PI * i) / n
   For k = 0 To n - 1
       dataOutR(i) = dataOutR(i) + (dataInR(k) * Cos(k * arg) + (dataInR(k) * Sin(k * arg))
   Next k
   dataOutR(i) = dataOutR(i) / n
Next i

'Complex Reverse transform
For i = 0 To n - 1
   arg = (2 * PI * i) / n
   For k = 0 To n - 1
       cosarg = Cos(k * arg)
       sinarg = Sin(k * arg)
       dataOutR(i) = dataOutR(i) + (dataInR(k) * cosarg - dataInI(k) * sinarg)
       dataOutI(i) = dataOutI(i) + (dataInR(k) * sinarg + dataInI(k) * cosarg)
   Next k
Next i

'Real Reverse transform
For i = 0 To n - 1
   arg = (2 * PI * i) / n
   For k = 0 To n - 1
       dataOutR(i) = dataOutR(i) + (dataInR(k) * Cos(k * arg) + (dataInR(k) * Sin(k * arg))
   Next k
Next i

[edit]

Fast Fourier Transform

There are many different ways the above algorithms can be improved to make significant reductions in computational complexity.

Ignoring the fact that there are many different kinds of fast fourier transform, the term FFT is popularly used to mean the power of two FFT (also referred to with terms like bifurcation and butterfly). This is the only kind of FFT most people learn, most software out there uses it and, in fact, many people are unaware that other FFTs exist.

'Complex radix 2 forward Fast Fourier Transform
'Array size is restricted to 2^m and the number of operations is O*n*log2(n).

  n = 2 ^ m

  j = 0
  For i = 0 To n - 2
     If (i < j) Then
        tmpR = dataR(i)
        tmpI = dataI(i)
        dataR(i) = dataR(j)
        dataI(i) = dataI(j)
        dataR(j) = tmpR
        dataI(j) = tmpI
     End If
     k = n / 2
     While (k <= j)
        j = j - k
        k = k / 2
     Wend
     j = j + k
  Next i
   
  c1 = -1
  c2 = 0
  l2 = 1
  For l = 0 To m - 1
     l1 = l2
     l2 = l2 + l2
     u1 = 1
     u2 = 0
     For j = 0 To l1 - 1
       For i = j To n - 1 Step l2
           i1 = i + l1
           t1 = u1 * dataR(i1) - u2 * dataI(i1)
           t2 = u1 * dataI(i1) + u2 * dataR(i1)
           dataR(i1) = dataR(i) - t1
           dataI(i1) = dataI(i) - t2
           dataR(i) = dataR(i) + t1
           dataI(i) = dataI(i) + t2
       Next i
       z = u1 * c1 - u2 * c2
       u2 = u1 * c2 + u2 * c1
       u1 = z
    Next j
    c2 = -Sqr((1 - c1) / 2)
    c1 = Sqr((1 + c1) / 2)
   Next l

  For i = 0 To n - 1
     dataR(i) = dataR(i) / n
     dataI(i) = dataI(i) / n
  Next i

'Complex radix 2 reverse Fast Fourier Transform
'Array size is restricted to 2^m and the number of operations is O*n*log2(n).

  n = 2 ^ m

  j = 0
  For i = 0 To n - 2
     If (i < j) Then
        tmpR = dataR(i)
        tmpI = dataI(i)
        dataR(i) = dataR(j)
        dataI(i) = dataI(j)
        dataR(j) = tmpR
        dataI(j) = tmpI
     End If
     k = n / 2
     While (k <= j)
        j = j - k
        k = k / 2
     Wend
     j = j + k
  Next i
   
  c1 = -1
  c2 = 0
  l2 = 1
  For l = 0 To m - 1
     l1 = l2
     l2 = l2 + l2
     u1 = 1
     u2 = 0
     For j = 0 To l1 - 1
       For i = j To n - 1 Step l2
           i1 = i + l1
           t1 = u1 * dataR(i1) - u2 * dataI(i1)
           t2 = u1 * dataI(i1) + u2 * dataR(i1)
           dataR(i1) = dataR(i) - t1
           dataI(i1) = dataI(i) - t2
           dataR(i) = dataR(i) + t1
           dataI(i) = dataI(i) + t2
       Next i
       z = u1 * c1 - u2 * c2
       u2 = u1 * c2 + u2 * c1
       u1 = z
    Next j
    c2 = Sqr((1 - c1) / 2)
    c1 = Sqr((1 + c1) / 2)
   Next l

[edit]

External links

Retrieved from "http://wiki.4hv.org/index.php/Fourier_analysis"

Categories: General Science

Fourier analysis

From HvWiki

Contents

Fourier Series

Theorems and Qualitive Concepts

Example of Use

Finding the Expansion

Applying Circuit Theory

Common Expansions

Square Wave

Fourier Transform

Repeated and Inverse Transforms

Basic Theorems

Additivity

Similarity

Convolution (or Multiplicativity)

Periodic Functions

Common Transforms

Digital Realisations of the Fourier Transform

Discrete Fourier Transform

Fast Fourier Transform

External links

Views

Personal tools

Navigation

Search

Toolbox