Elmwood Park gave 2016 a loud farewell and 2017 just as loud a welcome. The paint room was a lot of fun and turned the black canvas into glowing artwork. We started the night with the funky nu-disco heavy on the bass and then had a D.J. take over with some electronic and hip-hop. A sizeable group of people can out to help us welcome the new year, and at the end of the night we had so many people that the three mattresses and pullout couch setup were not enough to sleep everyone.

Biked down to breakfast today, adding an additional 16.62 miles to my yearly total which now stands at 3,506 miles for the year. That's enough. I'm done cycling for the year.

Ceiling and walls covered in black canvas. All that remains is to cover the floor.

Ceiling and walls covered in black canvas. All that remains is to cover the floor.

I have been working on understanding the innards of the Discrete Fourier Transform, and I’ve stumbled on what I believe to be the heart of the algorithm. Since then I have been trying to understand why it works. Let’s take a look at this heart:

These two functions will extract the amplitude and phase of the selected frequency *c* from the function *f*. With some experimentation, I have found the following to be true:

What this means is that if we have a sine wave at frequency *b*, amplitude *a* and phase *d*, we can extract phase and amplitude for some test frequency *c*. Anytime that *b* and *c* are equal, we get a non-zero value relating to phase and amplitude. If they are not equal, the answer is simply zero. This is precisely what is needed in a discrete Fourier transform, and why I call it the heart. In a DFT, the function checks the data for each possible integer frequency for the data set, and gets either it’s amplitude and phase, or zero.

First, the discrete Fourier transform in standard notation:

Use Euler's formula:

Now, assume *x* is real and break this into the real and imaginary parts and all frequencies:

Let’s try this on a set of data.

Here we have a (*b*) of frequency of 5 Hz with an amplitude (*a*) of 1 and phase angle (*d*) of 45°, and a check frequency (*c*) of 5 Hz. The sum of the real and imaginary parts is non-zero.

Now let’s try a check frequency of 6 Hz.

Here, the sum of the check frequencies for both real and imaginary are zero. It is more obvious when the check frequency is higher, say 50:

Here it is more obvious both the real and imaginary parts spend the same amount of time above and below 0, so overall summing to 0. It also doesn’t matter how many frequencies are in the signal. In the above examples there is just a single frequency, but it will extract amplitude and phase for the check frequency regardless of how many other frequencies are present in the signal.

I haven’t yet figured out why this is the case, but it makes perfect sense why this makes a DFT work.

I've been tired of not having one of these, so today I implemented a macro for doing a Discrete Fourier Transform (DFT) in LibreOffice Calc. I implemented a DFT rather than an Fast Fourier Transform (FFT) because I wanted to be able to use an arbitrary data size, and because the algorithm is pretty easy to implement. I cannot remember the last time I did any coding in Basic, but I still don't like it. I find arrays irritating when implemented with the offset of 1 rather than 0. Guess I'm too use to C.
To put this into a Calc document, goto Tool->Macros->Organize Macros->LibreOffice Basic. Then you can assign the macro to a specific document, or put it in My Macros. You will probably have to adjust security permissions just to allow the macro to run by going to Tools->Options->Security->Macro Security and setting the level from High (default) to Medium. If you are not an idiot that shouldn't be a problem.

This implementation isn't fast, but works fine for small data sets of around 50 samples. Larger sets will still work, but you may be waiting awhile.

' Discrete Fourier Transform (DFT).

' The complexity of this function is O( n^2 ) as it is not a Fast Fourier

' Transform (FFT). However, unlike as FFT this function works an any input size.

Function dft_guts( inputData As Variant, direction As Double, isScale As boolean )

Dim OFFSET As Integer

OFFSET = LBound( inputData, 1 )

Dim NUMBER As Integer

NUMBER = UBound( inputData, 1 ) - OFFSET

' If we are only given a single column of data, assume that holds the real

' values, and the imaginary values are all 0. Make a new array with the

' additional imaginary values in it.

If UBound( inputData, 2 ) < 2 Then

Dim newArray( LBound( inputData, 1 ) To UBound( inputData, 1 ), LBound( inputData, 1 ) To UBound( inputData, 1 ) ) As Double

' Copy data into new array.

Dim index As Integer

For index = LBound( inputData, 1 ) To UBound( inputData, 1 )

newArray( index, 1 ) = inputData( index, 1 )

newArray( index, 2 ) = 0.0

Next

' Switch to new array.

inputData = newArray

EndIf

' Storage for results.

Dim outputData( 0 To NUMBER, 1 ) As Double

Dim multiplier As Double

multiplier = direction * 2 * Pi

' If scaled, the scale is the number of samples.

Dim scale As Double

If isScale Then

scale = 1.0 / ( NUMBER + 1 )

Else

scale = 1.0

EndIf

' For each of the sample outputs...

Dim outerIndex As Integer

For outerIndex = 0 To NUMBER

' Start sum at zero.

outputData( outerIndex, 0 ) = 0.0

outputData( outerIndex, 1 ) = 0.0

Dim innerIndex As Integer

' For each input sample...

For innerIndex = 0 To NUMBER

' Angle (radians) at this index.

Dim angle As Double

angle = multiplier * outerIndex * innerIndex / ( NUMBER + 1 )

' Sine and cosine of angle.

Dim cosTerm As Double

Dim sinTerm As Double

cosTerm = cos( angle )

sinTerm = sin( angle )

' Real and imaginary terms at this angle.

Dim realTerm As Double

Dim imaginaryTerm As Double

realTerm = inputData( innerIndex + OFFSET, 1 ) * cosTerm

realTerm = realTerm - inputData( innerIndex + OFFSET, 2 ) * sinTerm

imaginaryTerm = inputData( innerIndex + OFFSET, 1 ) * sinTerm

imaginaryTerm = imaginaryTerm + inputData( innerIndex + OFFSET, 2 ) * cosTerm

' Accumulate results.

outputData( outerIndex, 0 ) = outputData( outerIndex, 0 ) + realTerm

outputData( outerIndex, 1 ) = outputData( outerIndex, 1 ) + imaginaryTerm

Next

' Scale results.

outputData( outerIndex, 0 ) = outputData( outerIndex, 0 ) * scale

outputData( outerIndex, 1 ) = outputData( outerIndex, 1 ) * scale

Next

dft_guts = outputData

End Function

' Discrete Fourier Transform (DFT) in forward direciton (i.e. time->frequency).

Function dft( inputData As Variant )

dft = dft_guts( inputData, -1, false )

End Function

' Inverse Discrete Fourier Transform (iDFT) in reverse direciton (i.e. frequency->time).

Function idft( inputData As Variant )

idft = dft_guts( inputData, 1, true )

End Function

' The complexity of this function is O( n^2 ) as it is not a Fast Fourier

' Transform (FFT). However, unlike as FFT this function works an any input size.

Function dft_guts( inputData As Variant, direction As Double, isScale As boolean )

Dim OFFSET As Integer

OFFSET = LBound( inputData, 1 )

Dim NUMBER As Integer

NUMBER = UBound( inputData, 1 ) - OFFSET

' If we are only given a single column of data, assume that holds the real

' values, and the imaginary values are all 0. Make a new array with the

' additional imaginary values in it.

If UBound( inputData, 2 ) < 2 Then

Dim newArray( LBound( inputData, 1 ) To UBound( inputData, 1 ), LBound( inputData, 1 ) To UBound( inputData, 1 ) ) As Double

' Copy data into new array.

Dim index As Integer

For index = LBound( inputData, 1 ) To UBound( inputData, 1 )

newArray( index, 1 ) = inputData( index, 1 )

newArray( index, 2 ) = 0.0

Next

' Switch to new array.

inputData = newArray

EndIf

' Storage for results.

Dim outputData( 0 To NUMBER, 1 ) As Double

Dim multiplier As Double

multiplier = direction * 2 * Pi

' If scaled, the scale is the number of samples.

Dim scale As Double

If isScale Then

scale = 1.0 / ( NUMBER + 1 )

Else

scale = 1.0

EndIf

' For each of the sample outputs...

Dim outerIndex As Integer

For outerIndex = 0 To NUMBER

' Start sum at zero.

outputData( outerIndex, 0 ) = 0.0

outputData( outerIndex, 1 ) = 0.0

Dim innerIndex As Integer

' For each input sample...

For innerIndex = 0 To NUMBER

' Angle (radians) at this index.

Dim angle As Double

angle = multiplier * outerIndex * innerIndex / ( NUMBER + 1 )

' Sine and cosine of angle.

Dim cosTerm As Double

Dim sinTerm As Double

cosTerm = cos( angle )

sinTerm = sin( angle )

' Real and imaginary terms at this angle.

Dim realTerm As Double

Dim imaginaryTerm As Double

realTerm = inputData( innerIndex + OFFSET, 1 ) * cosTerm

realTerm = realTerm - inputData( innerIndex + OFFSET, 2 ) * sinTerm

imaginaryTerm = inputData( innerIndex + OFFSET, 1 ) * sinTerm

imaginaryTerm = imaginaryTerm + inputData( innerIndex + OFFSET, 2 ) * cosTerm

' Accumulate results.

outputData( outerIndex, 0 ) = outputData( outerIndex, 0 ) + realTerm

outputData( outerIndex, 1 ) = outputData( outerIndex, 1 ) + imaginaryTerm

Next

' Scale results.

outputData( outerIndex, 0 ) = outputData( outerIndex, 0 ) * scale

outputData( outerIndex, 1 ) = outputData( outerIndex, 1 ) * scale

Next

dft_guts = outputData

End Function

' Discrete Fourier Transform (DFT) in forward direciton (i.e. time->frequency).

Function dft( inputData As Variant )

dft = dft_guts( inputData, -1, false )

End Function

' Inverse Discrete Fourier Transform (iDFT) in reverse direciton (i.e. frequency->time).

Function idft( inputData As Variant )

idft = dft_guts( inputData, 1, true )

End Function

This implementation isn't fast, but works fine for small data sets of around 50 samples. Larger sets will still work, but you may be waiting awhile.

New Year's Eve is coming up, and this years gathering to bring it in requires a lot of black canvas. Blacklight paint parties are nothing new at Elmwood Park, but the canvased area will be larger than anything previous. I wanted blank black canvas and setup an area in the basement where it could be hung against plastic and painted. Takes about an hour to dry and I was able to get several painted and hung for the gathering to come.

Using the holiday to work on an FFT demonstration. It is getting closer to being ready, but it isn't there yet.

This evening the Elmwood guys and I decided to build a snowman. We had just finished having some good Indian food (one of the few places open) and I tested the snow to find it just right for rolling snowballs. So I started to roll a ball and sucked up every bit of snow all the way to the grass. Soon it was too big from me to roll alone, so I called in the Elmwood Park team. Xiphos, Xen, James, and Andy (our couch guy) put our backs into getting one giant snowball for a bass rolled and positioned. After securing it we worked on a second one and used a ramp made of a 6 foot 2x12" plank. A third ball was cut in half and required us to lift over our heads. I got out the ladder and a forth layer was added. But I could still reach higher, so a 5th snowball was rolled. We ended up with a pillar about 10 feet tall.

I showed everyone how to build up the sides and went to work smoothing and sculpting. We knew it was going to be a tall person of some sort. It had a pointy head, so we figured it would be wearing stocking cap. In sculpting the face I found the mouth turned into a beard and it was soon obvious we are making a giant Kris Kringle. Xiphos had just picked up a bunch of food coloring to make cookies, and James mixed it up in a spray bottle. It worked well in coloring our snow creation. We positioned an LED light to illuminate our creation and soon Snow Kringle was looking good. Several people driving by slowed down, honked, or told us it looked great, and a couple stopped for pictures. Xiphos had rolled an other large snowball that was sitting unused, and we decided to turn it into a toy sack. We estimate we worked on it for about 2 hours, but are very pleased with the results.

I showed everyone how to build up the sides and went to work smoothing and sculpting. We knew it was going to be a tall person of some sort. It had a pointy head, so we figured it would be wearing stocking cap. In sculpting the face I found the mouth turned into a beard and it was soon obvious we are making a giant Kris Kringle. Xiphos had just picked up a bunch of food coloring to make cookies, and James mixed it up in a spray bottle. It worked well in coloring our snow creation. We positioned an LED light to illuminate our creation and soon Snow Kringle was looking good. Several people driving by slowed down, honked, or told us it looked great, and a couple stopped for pictures. Xiphos had rolled an other large snowball that was sitting unused, and we decided to turn it into a toy sack. We estimate we worked on it for about 2 hours, but are very pleased with the results.

While I didn't work today, I still went out for breakfast with Zach and Pluvius. Zach had wanted to try our breakfast places Bloody Mary and since he didn't have to work today either, today was the day. Pictured are the three states of Zach: without, obtained, and completed. After breakfast I biked down to the coffee shop to sit in front of the fire for a couple hours.

Last day of work for the week due to the holiday weekend. The temperatures were downright summer like after my last few ride. When I set out this morning it was 30°F (-1°C). I had on my full coat, but I think I could have done this ride with just a sweatshirt. I decided not only to cycle in, but that everyone at work needed donuts. So I adjust my route slightly so that I could stop at a donut shop on Regent Street. I then got on the commuter trail back to John Nolen. It was the first time I rode that second of the commuter trail in a couple of years--maybe even since living at Rodney House. The population at work was fairly thin and I spent the day eating all the junk food people brought in. So much food, in fact, I skipped lunch and didn't stop for a slice pizza on the way home. The temperatures seemed so mild. It's like the difference between riding in 65° vs 45°. The world seems completely different.