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.