scribeGriff Studios

Books • Algorithms • Dart • HTML5 • CSS3

To content | To menu | To search

Exploring the Partial Sums of Fourier Series with Dart

Introduction


I've always been rather fascinated by the concept that just about any signal can be decomposed into a weighted collection of elementary basis functions. My undergraduate linear systems professor would refer to these basis functions as CCFSs (cleverly chosen fundamental signals):

$$f\bigl(x\bigr) = \sum \:\text{weighted} \:\text{CCFS}$$

But what makes a basis function cleverly chosen? In 1665, the extremely clever Isaac Newton used a power series representation [1]:

$$f\bigl(x\bigr) = a_0 + a_1x + a_2x^2 + a_3x^3 +\:\dotsc$$

as a method to compute the general binomial series. He then applied this technique to the computation of infinite series of algaebraic equations as well as the logarithmic series. Newton published his work with power series in the Principia Mathematica in 1687:

$$f\bigl(x\bigr) = \sum_{k=0}^{\infty}\frac{\Delta^k[f](a)}{k!}(x-a)_k$$

which holds for any polynomial function f and for most (but not all) analytic functions. You may recognize (3) as the discrete analog of the continuum Taylor expansion [2].

Some clever basis functions, such as the use of simple oscillating functions to model planetary motion, date back to antiquity. It was 2000 years after the age of Hipparchus, however, that Joseph Fourier published The Analytical Theory of Heat [3] in which he modeled a complicated heat source using a linear combination of sines and cosines [4]. He then wrote a solution to the heat equation of a metal plate as a linear combination of solutions for simpler heat sources. Thus Fourier showed that periodic functions can be synthesized using a linear combination of complex exponentials whose frequencies were harmonics of the fundamental frequency. This linear combination, or superposition, is known as the Fourier series:

$$f\bigl(x\bigr) = \sum_{k=-\infty}^{\infty}c_ke^{jk\frac{2\pi}{L}x}$$ From (1), we observe that the CCFS in (4) is the complex exponential $e^{jk\frac{2\pi}{L}x}$ with a weight given by the Fourier coefficient $c_k$.

In this article, we will look at the Fourier series using the Dart programming language [5] and examine this superposition of weighted sines and cosines as it pertains to some common periodic (and not so periodic) signals.

The Discrete Fourier Series


We now concentrate our analysis on the discrete periodic sequence, $x(n)$ where $x(n)$ is defined as any sequence where: $$x(n) = x(n + kN) \quad \forall n, k$$

and N is the fundamental period of the sequence [6]. This periodic sequence can then be expressed as an exponential Fourier series:

$$x\bigl(n\bigr) = \frac{1}{N}\sum_{k=0}^{N-1}c_ke^{jk\frac{2\pi}{N}n}\quad n = 0, \pm1, \dotsc$$ where the complex discrete time Fourier coefficients $c_k$ are given by: $$c_k = \sum_{n=0}^{N-1}x(n)e^{-jk\frac{2\pi}{N}n}\quad k = 0, \pm1, \dotsc$$ Referring to equation (1), we note that these complex coefficients can be considered the weighting factor for each harmonic of the CCFS. We can also express the sequence $x(n)$ in the trigonometric form of the Fourier series by making use of Euler's formula: $$e^{jnx} = cos(nx) + jsin(nx)$$

If the sequence x(n) is real valued, then the partial sum of its Fourier series is also real [7] and we can write (6) as:

$$x\bigl(n\bigr) = \frac{a_0}{N}+ \frac{2}{N}\sum_{k=1}^{\frac{N}{2}-1}a_kcos(k\frac{2\pi}{N}n) + b_ksin(k\frac{2\pi}{N}n)$$ where $a_k = Real(c_k)$ and $b_k = -Imag(c_k)$.

We now have an expression for computing the Fourier series, so let's see how we can implement this algorithm in Dart.

Computing Partial Sums with Dart


Our signal processing library [8] makes use of several specific characteristics so as to be more familiar to our target audience:

  • access to the library is through function calls rather than constructor methods
  • calls return multiple values which are accessed using object fields
  • function call returns null on failure

For example, the following library function call, fsps(), would be a typical use case of the proposed Fourier series algorithm to compute the partial sums of the series for the indicated waveform and k values:

var fourier = fsps(waveform, kvals, [fraction]);

The parameters waveform and kvals are lists whereas the optional parameter, fraction, identifies what portion of the waveform to use as the period for the series. By default, the period of the discrete Fourier series is set to the length of the sampled data, but this does not have to be the case (and may not be desired), as we will see a little later in this article. As an example, let's say that we construct a square wave with a 3 cycle duration and that we would like to compute the partial sum of the Fourier series to include up to the 2nd, 20th and 80th harmonic. We could implement such a computation as follows:

import 'package:convolab/convolab.dart';

void main() {
  List waveform = square(3);
  List kvals = [2, 20, 80];
  var fourier = fsps(waveform, kvals);
  if (fourier != null) {
    print('We have computed ${fourier.psums.length} Fourier series.');
    if (fourier.psums[kvals[0]].every((element) => element is Complex)) {
      print('The computed Fourier series is of type Complex.');
    } else {
      print('The computed Fourier series is not Complex.');
    }
  } else {
    print('There was an error computing the Fourier series');
  }
}

//Prints:
//We have computed 3 Fourier series.
//The computed Fourier series is of type Complex.

We'll take a look at more interesting output from the series calculation in a moment, but let's first take a look at the algorithm itself. The function fsps() returns an object of type FspsResults and acts as a wrapper to a constructor for private class _PartialSums:

part of convolab;

//Wrapper fsps() calls the sum() method of class _PartialSums
FspsResults fsps(List waveform, List kArray, [num fraction = 1])
    => new _PartialSums(waveform, kArray).sum(fraction);

// Computes the partial sums of Fourier series on waveform.
// The number of sums to compute is defined in each element of list kArray.
class _PartialSums {
  final List waveform;
  final List kArray;

  _PartialSums(this.waveform, this.kArray);

  FspsResults sum(num fraction) {
    //Store results as a map with k value as the key K
    //and the partial sum list as the value V.
    var psums = new Map();
    //Create a map for sending as a json string.
    var jsonData = new Map();
    //Add the waveform to the jsonData.
    jsonData["Waveform"] = {"real": waveform, "imag": null};
    var L = waveform.length;
    //User may define a period less than the length of the waveform.
    var N = (L  * fraction).toInt();
    //The Fourier series coefficients are computed using a FFT.
    var coeff = fft(waveform.getRange(0, N));
    //If the fft returns the complex coefficients, calculate the partial sums.
    if (coeff != null) {
      for (var i = 0; i < kArray.length; i++) {
        List<Complex> y = new List(L);
        List real = new List(L);
        List imag = new List(L);
        for (var n = 0; n < L; n++) {
          var q = complex(0, 0);
          for (var k = 1; k <= kArray[i]; k++) {
            var kth = 2 * n * k * PI / N;
            var wk = complex(cos(kth), sin(kth));
            q = q + (wk * coeff.data[k]);
          }
          y[n] = coeff.data[0].scale(1 / N) + q.scale(2 / N);
          real[n] = y[n].real;
          imag[n] = y[n].imag;
        }
        psums[kArray[i]] = y;
        jsonData["kval ${i + 1} = ${kArray[i]}"] = {"real": real, "imag": imag};
      }
      return new FspsResults(waveform, psums, jsonData);
    } else {
      return null;
    }
  }
}
Let's try to correlate this algorithm to the expression given in equation (9). To compute the complex coefficients $c_k$, we use a FFT which is included as part of the library:
var coeff = fft(waveform.getRange(0, N));

Rather than separate the coefficients into their real and imaginary components, we perform the partial sum using complex arithmetic and then take the real part of the final sum as our solution:

for (var n = 0; j < L; j++) {
  var q = complex(0, 0);
  for (var k = 1; k <= kArray[i]; k++) {
    var kth = 2 * n * k * PI / N;
    var wk = complex(cos(kth), sin(kth));
    q = q + (wk * coeff.data[k]);
  }
  y[n] = coeff.data[0].scale(1 / N) + q.scale(2 / N);
  real[n] = y[n].real;
  imag[n] = y[n].imag;
}

Note that y is a complex list. Let's rewrite the equations used in the algorithm to make them easier to compare with equation (9):

$$kth = \frac{2\pi kn}{N}$$ $$wk = \cos(kth) + j\sin(kth)$$ $$q(n) = \sum_{k=1}^{kval} c_k * wk$$ $$y(n) = \frac{c_0}{N} + \frac{2}{N} * q(n)$$

We do this for each element n of the signal wavefom array and then for each value of k in the list kval. We then store the results in a map. The results are organized differently depending on whether we are processing the data locally (ie, for use on the server) or sending the results on to a client using JSON. JSON requires keys to be strings and does not tolerate complex elements in a list:

//No problem with this in Dart server side.
psums[kArray[i]] = y;
//Sending to the client using JSON requires some changes in formatting.
jsonData["kval ${i + 1} = ${kArray[i]}"] = {"real": real, "imag": imag};

Finally, we return the data as an object of type FspsResults:

return new FspsResults(waveform, psums, jsonData);

The FspsResults class extends from the standard results class and overrides two of its methods: exportToFile() and exportToWeb():

class FspsResults extends ConvoLabResults {
  final Map psums, jsonData;

  //Return a list of the input waveform and also a Map of the
  //partial sums indexed to the value for k.
  FspsResults(List data, this.psums, this.jsonData) : super(data);

  //Override standard results class methods exportToFile() and exportToWeb().
  //Method: Save data to a file in tab delimited form.
  @override void exportToFile(String filename) {
    List<String> tokens = filename.split(new RegExp(r'\.(?=[^.]+$)'));
    if (tokens.length == 1) tokens.add('txt');
    psums.forEach((k, v) {
      File fileHandle = new File('${tokens[0]}_k$k.${tokens[1]}');
      IOSink dataFile = fileHandle.openWrite();
      for (var i = 0; i < psums[k].length; i++) {
        dataFile.write('${psums[k][i].real}\t'
            '${psums[k][i].imag}\n');
      }
      dataFile.close();
    });
    File fileHandle = new File('${tokens[0]}_data.${tokens[1]}');
    IOSink dataFile = fileHandle.openWrite();
    for (var i = 0; i < data.length; i++) {
      dataFile.write('${data[i]}\n');
    }
    dataFile.close();
  }

  //Method: Export data to web/client using a web socket.
  @override void exportToWeb(String host, int port) {
    //connect with ws://localhost:8080/ws
    if (host == 'local') host = '127.0.0.1';
    HttpServer.bind(host, port).then((server) {
      print('Opening connection at $host:$port');
      server.transform(new WebSocketTransformer()).listen((WebSocket webSocket) {
        webSocket.listen((message) {
          var msg = json.parse(message);
          print("Received the following message: \n"
                "${msg["request"]}\n${msg["date"]}");
          webSocket.add(json.stringify(jsonData));          
        },
        onDone: () {
            print('Connection closed by client: Status - ${webSocket.closeCode}'
                ' : Reason - ${webSocket.closeReason}');
            server.close();
        });
      });
    });
}

Writing the data to a file in a tab delimited format allows it to be easily read into other signal processing applications such as Matlab, SciLab and Octave for further processing and visualization. But with Dart, we don't have to rely on other tools to accomplish what we need. Dart works just as well on the client side as the server side. Let's send the data to the web so we can use data visualization right in the browser.

ConvoWeb: Client Side Signal Processing


Let's revisit our earlier example with the exception that we are now going to send the data to the client using the method exportToWeb():

import 'package:convolab/convolab.dart';

void main() {
  List waveform = square(3);
  List kvals = [2, 20, 80];
  FspsResults fourier = fsps(waveform, kvals);
  if (fourier != null) {
    fourier.exportToWeb('local', 8080);
  } else {
    print('There was an error computing the Fourier series');
  }
}

We now set up our client side application [9] to request, then receive, the data from the server. The data is processed and the resulting waveforms are plotted to a browser window. Finally, we save the resulting plots as PNG images, both for an individual plot and for all plots together. So to continue our example in Dart, we can do the following:

//Client
import 'package:convoweb/convoweb.dart';

void main() {
  // Example retrieving data from server and plotting.
  String host = 'local';
  int port = 8080;
  Element display = querySelector('#console');
  String request = 'Send data request';
  //Request the data from the server using a Future.
  Future reqData = requestDataWS(host, port, request, display);
  //We now have the data so let's plot it.
  reqData.then((data) {
    //Get the keys.  This is primarily done to allow sorting.
    List keys = data.keys.toList();
    //Sort keys if there is more than 1.
    if (data.length > 1) {
      keys.sort((a, b) => a.compareTo(b));
    }
    //Create a list to hold all the plots.
    List plots = new List(keys.length);
    //Plot the data using the plot() library function.
    for (var i = 0; i < keys.length; i++) {
      List waveform = data[keys[i]]["real"].sublist(0, 500);
      plots[i] = plot(waveform, style: 'line', color: 'green',
          range: keys.length, index: i+1);
      plots[i]
        ..grid()
        ..xlabel('time (samples)')
        ..ylabel('amplitude')
        ..title(keys[i]);
    }
    //Put the time stamp after the last plot.
    plots[keys.length - 1].date(true);
    //Save last plot as a PNG image;
    plots[keys.length - 1].save();
    //Save all plots as PNG image;
    Window myPlotWindow = saveAll(plots);
  });
}

There are a few things to point out in the code above. First, we use a Future to retrieve the data with a websocket:

Future reqData = requestDataWS(host, port, request, display);

Next, we use the library's plot function to plot each of the waveforms to a canvas, holding a reference to each canvas in the list plots[]:

plots[i] = plot(waveform, style: 'line', color: 'green',
    range: keys.length, index: i+1);

The plot() class contains methods for adding a grid, title, x and y axis labels as well as adding a date stamp. The date stamp can be either in a long form (default) or short form (by setting the optional parameter to true). As we mentioned earlier, the class also has a method for saving an individual plot as a PNG image:

plots[keys.length - 1].save();

To save all the plots contained in list plots[], we can use the saveAll() function which returns a handle to the window containing the plots. The saveAll() function also supports scaling (with a default value of 1):

Window myPlotWindow = saveAll(plots);

Now back to our example. We've computed the Fourier series for our square wave on the server, sent the data to the client and have now plotted the results to a browser window. The waveforms in the panel below illustrate the results (click to expand tab):

+ Partial sum of the Fourier series of a square wave... (click to expand/collapse)

Partial sum of Fourier series for square wave

Some Additional Examples


Sound Sample

We can also use Fourier series to investigate more complex waveforms, such as the sound sample shown below:

fourier-series-sound4-first.png

We have four different sound samples in the library, so the value passed to our waveform generator refers to which sound sample we would like to analyze, rather than the number of cycles as is the case with the other standard waveforms. Computation proceeds as follows:

//Server side:
var waveform = sound(4);
var kvals = [20, 50, 100];
var fourier = fsps(waveform, kvals);
if (fourier != null) {
  fourier.exportToWeb('local', 8080);
}

In our previous example, we did not define an x axis vector against which to plot our sample data. By default, the x axis is just the sample points associated with the waveform to be plotted. In this example, however, we create a row vector for the x axis with the information relating to the rate at which the sound was sampled. In this case, we have 512 points of a sound waveform that was sampled at 22050 samples/sec.

//Client side:
var sndLength = 512;
var sndRate = 22050;
var sndSample = sndLength / sndRate * 1e3;
List xvec = vec(0, sndSample, sndSample / (sndLength - 1));

We now can pass the x axis vector to our plot command along with the sampled data:

plots[i] = plot(waveform, xdata: xvec, style: 'line', color: 'green', 
    range: keys.length, index: i+1);

The resulting waveforms are shown in the following panel:

+ Partial sum of the Fourier series of a sound wave... (click to expand/collapse)

Partial sum of Fourier series for sound wave

Just for fun, let's look at some of the lower order harmonics of the same waveform:

//Server side:
var waveform = sound(4);
var kvals = [1, 4, 16];
var fourier = fsps(waveform, kvals);
if (fourier != null) {
  fourier.exportToWeb('local', 8080);
}

Here are the waveforms:

+ Partial sum of the Fourier series of a sound wave... (click to expand/collapse)

Partial sum of Fourier series for sound wave

What's the Period?

Before we conclude, I did want to include one last example that illustrates the periodic nature of the Fourier series. In the previous examples, the period of the series was not entirely obvious. By default, the period is defined as the length of the list containing the sampled data. But this is not a requirement. A user can define the period to be any portion of the available data. Let's take for example, a triangle waveform as shown below:

fourier-series-triangle3-first.png

We can define a period relative to the length of the data by providing an optional parameter to our fsps() call. Let's say, for example, we want the period over which to compute the Fourier series to be half the length of the input waveform. Setting up the analysis would look something like this:

//Server side:
var waveform = triangle(3);
var kvals = [10, 40, 80];
var fourier = fsps(waveform, kvals, 0.5);
if (fourier != null) {
  fourier.exportToWeb('local', 8080);
}

Now when we plot the data, you can clearly see the periodic behavior of the solution:

+ Partial sum of the Fourier series of a triangle wave... (click to expand/collapse)

Partial sum of Fourier series for triangle wave

Conclusion


In this article, we explored the partial sums of Fourier series with the Dart programming language. We calculated the series for a number of different waveforms using a server side library, then transferred the results from the analysis to a client using a websocket. The client application plotted the resulting data to a browser window using HTML canvas techniques. Next time, we will explore the convolution of signals which will allow us to begin our investigation of digital filters with Dart.


Works Cited

[1] A First Course in Fourier Analysis by David W. Kammler, Prentice-Hall, 2000
[2] Isaac Newton's interpolation formula on Wikipedia
[3] The Analytical Theory of Heat by Joseph Fourier, 1822
[4] The Fourier Series on Wikipedia
[5] The Dart Programming Language for Structured Web Apps
[6] Digital Signal Processing Using Matlab by Vinay Ingle and John Proakis, Brooks/Cole 2000
[7] Numerical Algorithms with C by Gisela Engeln-Mullges and Frank Uhlig, Springer 1996
[8] ConvoLab on GitHub
[9] ConvoWeb on GitHub

Equations in this article powered by

Powered by MathJax
submit to reddit
Google+
Richard Griffith

Author: Richard Griffith

Keep in touch with the latest updates. Subscribe to the RSS Feed for this category.

Comments (0)

Be the first to comment on this article

Add a comment This post's comments feed

no attachment



You might also like

angular-and-dart-iconj.jpg

Today's @NgDirective: Get Up to Speed Using Angular with Dart

Although I spend most of my time working with Dart using Polymer, it's hard not to find the announcement of AngularDart a compelling reason to take it out for a spin. And I confess, the more I use Angular with Dart, the more I'm convinced it is going to be a major component of my Dart toolbox for the foreseeable future. I had come across Jesus Rodriguez's introduction to the model driven framework with his appropriately named blog post Why Does Angular.js Rock?. In this article, we look at the Dart equivalents of the examples Jesus presented.

Continue reading

future-word-cloud-dart.png

Iterables, Futures, and Future.wait() in Dart

Several days ago while working with Dart, I was coding up a problem that required that I iterate over a function that returns its value represented as a Future. The variables that I needed to pass to this function were read from an external file and stored in a List using a Stream. To evaluate the function for each element in the List, I was tempted to use a simple forEach() to pass the elements to the function returning a Future. But I was soon going to discover a much better way for dealing with a scenario such as this.

Continue reading