Thesis Download Link

My PhD thesis is now available for free download at lulu.com. Or get a beautiful hardcover copy for $18.83.

Bar Camp Auckland

Today I gave a presentation on microcontrollers at Barcamp Auckland. As promised, the slides can be found here until I find a more permanent host (7.2 MB). (Image: Ioan Sameli.)

Update: That link is dead. You'll have to email me to get the presentation or suggest a file host.

Peak Estimation

Sometimes it is important to be able to estimate the peak of a sampled continuous function between the samples. This is called subsample peak interpolation and is used in radar, delay estimation, and communication. Typically one fits a model to the sampled data and then finds the maximum of the model. Two models that I have used are parabolas and Gaussian curves. Both have three parameters and can be fit exactly to three samples (even if the samples are not evenly spaced), and, as a bonus, closed form solutions exist for parameters. I've written up a Matlab package to demonstrate this procedure, to be found here. The plot above shows an example, finding the peak of the green curve sampled at the blue markers (click to enlarge).

Fast Correlation

I've uploaded a small package to the Matlab File Exchange to improve the speed of your cross correlations. This package uses the FFT to calculate the circular cross correlation of two periodic signals. Since the FFT calculates the DFT of a N-point signal in O(N log N) calculations (rather than O(N²)) it is much faster than the naïve method, especially for long signals. In Matlab, the fft method is faster than the multiplication method in all but the most trivial cases, as shown in the image, plotting the ratio of the speed of the fast method to that of the naïve method from the definition. The figure also shows that the fft algorithm is typically fastest when N is a power of 2, and slowest when N is prime.

Installing Gnuarm ARM Toolchain on Ubuntu 9.04

It can be surprisingly difficult to install an ARM toolchain on Linux. As far as I know, there's no apt package that is currently maintained, so you have to build it from source. This posting shows how I installed the gnuarm toolchain on Ubuntu 9.04 (Jaunty Jackalope). I installed Ubuntu on a VirtualBox virtual machine, but it should work the same for a regular install.

The toolchain includes a number of pieces: binutils, which includes the linker, assembler, etc; gcc, the compiler; newlib, a standard C library for embedded systems; and GDB, the debugger. I also included Sam_I_Am and sam7utils, which allow one to program ATMEL SAM microcontrollers over USB.

First you need to install some dependencies. It's a good idea to upgrade your system at this time also.

sudo apt-get update
sudo apt-get dist-upgrade
sudo apt-get install libgmp3-dev libmpfr-dev build-essential zlib1g-dev libncurses5-dev patch texinfo libreadline5-dev

The following script should install the components. It's based on a script from Uwe Hermann which fails to build on Ubuntu. Comment out the last section if you're not using ATMEL harware. The USB serial modules isn't included in the 2.6.28-11-generic kernel that is the current kernel, so you may have to upgrade to 2.6.28-12-generic using the pre-release sources. You can check your kernel version with

uname -a

The .samiamrc file is for AT91SAM7S256 device; you'll have to edit it if you use a different one.
Run the following script with 'sudo' and get a coffee, it takes a while.

#!/bin/sh
# Written by Uwe Hermann , released as public domain.
# Edited by Travis Wiens

TARGET=arm-elf # Or: TARGET=arm-none-eabi
PREFIX=/usr/local/arm # Install location of your final toolchain
PARALLEL="" # Or: PARALLEL=""

BINUTILS=binutils-2.19.1
GCC=gcc-4.3.3
NEWLIB=newlib-1.17.0
GDB=gdb-6.8

export PATH="$PATH:$PREFIX/bin"

mkdir build

wget -c http://ftp.gnu.org/gnu/binutils/$BINUTILS.tar.bz2
tar xfvj $BINUTILS.tar.bz2
cd build
../$BINUTILS/configure --target=$TARGET --prefix=$PREFIX --enable-interwork --enable-multilib --with-gnu-as --with-gnu-ld --disable-nls --with-float=soft --disable-werror
make $PARALLEL all
make install
cd ..
#rm -rf build/* $BINUTILS $BINUTILS.tar.bz2

wget -c ftp://ftp.gnu.org/gnu/gcc/$GCC/$GCC.tar.bz2
tar xfvj $GCC.tar.bz2
cd build
../$GCC/configure --target=$TARGET --prefix=$PREFIX --enable-interwork --enable-multilib --enable-languages="c,c++" --with-newlib --without-headers --disable-shared --with-gnu-as --with-gnu-ld --with-float=soft --disable-werror
make $PARALLEL all-gcc
make install-gcc
cd ..
#rm -rf build/* $GCC.tar.bz2

wget -c ftp://sources.redhat.com/pub/newlib/$NEWLIB.tar.gz
tar xfvz $NEWLIB.tar.gz
cd build
../$NEWLIB/configure --target=$TARGET --prefix=$PREFIX --enable-interwork --enable-multilib --with-gnu-as --with-gnu-ld --disable-nls --with-float=soft --disable-werror
make $PARALLEL
make install
cd ..
#rm -rf build/* $NEWLIB $NEWLIB.tar.gz

# Yes, you need to build gcc again!
cd build
../$GCC/configure --target=$TARGET --prefix=$PREFIX --enable-interwork --enable-multilib --enable-languages="c,c++" --with-newlib --disable-shared --with-gnu-as --with-gnu-ld --with-float=soft --disable-werror
make $PARALLEL
make install
cd ..
#rm -rf build/* $GCC

wget -c ftp://ftp.gnu.org/gnu/gdb/$GDB.tar.bz2
tar xfvj $GDB.tar.bz2
cd build
../$GDB/configure --target=$TARGET --prefix=$PREFIX --enable-interwork --enable-multilib --disable-werror
make $PARALLEL
make install
cd ..
#rm -rf build $GDB $GDB.tar.bz2

sudo ln -s $PREFIX/bin/arm-elf* /usr/bin

cd ..
mkdir Sam_I_Am
cd Sam_I_Am
wget http://claymore.engineer.gvsu.edu/%7Esteriana/Software/Sam_I_Am-0.3.tar.gz
tar xfvz Sam_I_Am-0.3.tar.gz
cd Sam_I_Am-0.3
python setup.py install
cd ..
echo "
open /dev/ttyUSB0
version
set readallow 0 0x300000
set ramwriteallow 0x202000 57344
set flashwriteallow 0x100000 0x40000
" >> .samiamrc
cp .samiamrc ~/

rm /usr/bin/Sam_I_Am
echo "
#!/bin/sh
python /usr/local/lib/python2.6/dist-packages/Sam_I_Am/samiam.py $*
" >> /usr/bin/Sam_I_Am
chmod a=rx /usr/bin/Sam_I_Am

sudo modprobe usbserial vendor=0x3eb product=0x6124
#this fails on kernel 2.6.28-11-generic, upgrade to latest prerelease


#install sam7utils
cd ..
wget http://oss.tekno.us/sam7utils/sam7utils-0.2.1.tar.gz
tar xfvz sam7utils-0.2.1.tar.gz
cd sam7utils-0.2.1
./configure
make
make install
ln -s /dev/ttyUSB0 /dev/at91_0

You'll have to run

sudo modprobe usbserial vendor=0x3eb product=0x6124

each time you restart.

To program the device, use

sam7 --exec set_clock --exec unlock_regions --exec "flash main.bin"

Acoustic Bird Location and Directional Recording

A few weeks ago Victor Obolonkin and I traveled to Pureora Forest to record kōkako calls with my microphone array.

The microphone array is made of 12 microphones mounted on a 5 m beam, as shown mounted on the van.



Using beam-forming techniques, we can turn the microphones into a highly directional microphone which can be electronically "steered" in any direction. This is better than a traditional dish-type of directional mic, because we can steer the beam in any direction after the recording is made, allowing us to listen to two or more birds with overlapping calls. You can listen to an example of the power of the system below. The first file is a recording of a kōkako using a single microphone, which includes background noises from other birds and insects.


The next is a recording using the full array, steered in the direction of the kōkako. Many of the background noises are greatly attenuated, especially the sounds between 6 and 15 seconds.


Here is a photo of the kōkako in its tree, as well as a zoomed in version.



We can also do the opposite: use the array to locate the direction that the sound came from. This array has an angular resolution of approximately 4° for a sound of 1000 Hz, which is much better than a human ear. We intend to use this capability to track endangered birds, such as the kōkako, by using two arrays to triangulate their position.

An example of tracking a sound is shown below, recorded at the Physics Field Site at Ardmore. This shows the sound pressure level over time and angle from the array. You can see a steady source at approximately 90° (straight in front of the array); this is a speaker transmitting a kokako recording. You can also see a source that moves between 120° and 180°, a helicopter flying nearby.

Zoom in for a better view.

Driving Times in NZ

After our trip around the South Island, I got to thinking about how long it takes to get everywhere in this small country. So I made this map of the driving time from our house in Auckland to everywhere in the country. The driving times come from a Matlab script I wrote that queries Google maps, and the mapping functions are from M_Map for Matlab, using shoreline data from GSHHS. Click it for higher resolution.

MLS and Kasami Set Generators for Matlab

Linear feedback shift registers (LFSR) are a simple method of generating sequences, including pseudorandom number sequences. Some of these LFSR sequences have special properties; a maximal length sequence (MLS or m-sequence) has a large autocorrelation at zero lag, with near zero autocorrelation elsewhere. This 'impulsive' autocorrelation function allows one to quickly determine the impulse response of a linear time invariant (LTI) system.

Maximal length sequences are also the base for sets of sequences with good correlation properties. One such set is the small set of Kasami sequences. These sequences have small off-peak autocorrelations and also small cross correlations between sequences. This property allows for code-division multiplexing as well as accurately determining the arrival time of a transmitted sequence, even in the presence of other interfering transmissions.

I've uploaded some Matlab code for generating LFSR sequences, m-sequences, and sets of Kasami sequences, as well as examples. As alwasy, find it here. Please review, rate, or leave feedback so that I know people are finding these uploads interesting.

MLS Generator for ATMEGA8

Maximal length sequences (MLS or m-sequences) are useful for system identification and digital communication. For example if a MLS is used to excite the input to a linear time-invariant (LTI) system, the system's impulse response can be determined from the cross correlation of the input and output. The impulse response can be useful in its own right or can be windowed to obtain a quasi-anechoic frequency response.

This code is written for an AVR ATMEGA8, which is an easy-to-use, low-cost microcontroller, but should work with others. It outputs the MLS on pin 18 (PB4). A clock signal is output on pin 19 (PB5), transitioning high on each value. Pin 17 (PB3) is a synchronizing signal, going high for one sample at the start of each loop of the sequence.

The MLS is generated by a 16-bit linear feedback shift register. The "feedback" variable can be changed to other values to generate other sequences. See http://www.ece.cmu.edu/~koopman/lfsr/index.html for other values.

The code is written for gcc with -O3 optimization and the loop runs in a minimum 19 clock cycles if the delay function is removed. The "NOP" (No OPeration) lines must be tuned if you use a different compiler, to ensure that each branch of each "if" statement takes the same number of cycles.

"N_delay" can be used to change the loop's speed. It is currently set for a loop of 73 cycles or approx 219 kHz for a 16 MHz clock.

Download from here. You have to sign up (free), but if you're interested in AVR microcontrollers you should be a member anyway.

Acoustic Tomography

One of the projects that I'm currently working on is a method of measuring temperature and velocity fields using sound, called acoustic tomography. This method relies on the two properties of sound: it's speed is temperature dependent, and the sonic speed is relative to the motion of the fluid (in our case, air). The principle is similar to that used for sonic anemometers, the time taken for a sound to cross a distance is measured in two directions and the mean wind speed and temperature can be determined. If we set up a large number of speakers and microphones around a measurement area, it is possible to reconstruct the temperature and/or velocity fields within the area. This can be used to generate an image or video of the temperature and wind distribution.

This has been done before, however we are looking at much smaller scales in order to measure the flow in street canyons.

For more information, see my paper at the New Zealand Acoustic Society conference. Example code is also available from my section of the Matlab File Exchange.

The image above shows the temperature (colours) and wind velocity (arrows) field for votex shedding behind a cylinder. The top image shows the simulated flow, and the bottom one shows the reconstruction. The video below shows multiple frames of similar data. Unfortunately the resolution is low, if you would like to see the full video, please contact me.