## Exploring the Partial Sums of Fourier Series with Dart

Posted on Friday 14 September 2012, 15:58 - updated on 12/01/2013 - Dart - Permalink

- Article
- |
- Comments (0)
- |
- Attachments (0)

### 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:

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:

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:

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):

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):

### Some Additional Examples

#### Sound Sample

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

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:

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:

#### 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:

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:

### 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