Feeds:
Posts

## Matlab and Fibonacci Numbers

Matlab has long been an immensely convenient tool for processing and visualizing signals in a DSP system. The tool makes it very easy to simultaneously visualize a signal in multiple domains. The following is a simple demonstration of some of these signal-processing capabilities.

The Fibonacci sequence is the sequence of numbers formed when each number in the sequence is equal to the sum of the two Fibonacci numbers immediately preceding that number. The sequence is initialized by the numbers 0 and 1, and looks something like this: 0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,etc. It is trivial to design a digital filter that produces the Fibonacci sequence as it’s impulse response. The impulse response of a discrete-time or digital filter is the response produced when the filter is stimulated by the Kronecker delta function:

$\delta[n] = \begin{cases} 1, & n = 0 \\ 0, & otherwise \end{cases}$

If the initial state of such a filter is such that all internal elements are at zero, the filter described by the following difference equation can produce an impulse response equal to the Fibonacci sequence. The input and output sequences are denoted x[n] and y[n], respectively.

$y[n] = x[n] + y[n-1] + y[n-2]$

Taking the Z-transform of this difference equation yields the following transfer function H(z) through the filter:

$\begin{array}{lcl} H(z) & = & \frac{Y(z)}{X(z)} \\ & = & \frac{1}{1 - z^{-1} - z^{-2}} \\ & = & \frac{z^{2}}{z^{2} - z - 1} \end{array}$

This transfer function has two zeros at the origin, and a pair of real-valued poles at z=-0.618 and z=1.618. A pole-zero plot can quickly be produced using the roots and zplane commands in Matlab:

zplane(roots([1,0,0]), roots([1,-1,-1]))


For the transfer function H(z), the coefficient matrices of the numerator and denominator polynomials in z-1 are given by B=[1] and A=[1,-1,-1], respectively. The frequency response of the filter can easily be computed using the freqz command in Matlab. In the following snippet of code, H is the complex-valued DFT and W is a vector of radian frequencies at which H has been computed. The following plot shows the magnitude of the frequency response.

% numerator polynomial
B = [1];
% denominator polynomial
A = [1,-1,-1];
% compute frequency response
[H,W] = freqz(B,A);
% plot the magnitude response (normalize W to pi)
plot(W/pi,abs(H));


The frequency response is computed along the unit circle in the Z-domain (z=ejw). Since the response is symmetric, the above plot only shows W/pi going from 0 to 1. As expected, the magnitude response shows peaks near 0 and 1, due to the relative proximity of the poles to these two points.

In the time-domain (or sample-domain), the response of such a system to a particular input sequence can easily be computed using the filter command in Matlab. In the following fragment of code, the above filter polynomials are used, along with initial states of zero. The input stimulus sequence x is ten samples of a Kronecker delta function, starting at n=0 and ending at n=9. The filter output y is initially 0, but then proceeds through the next ten numbers in the Fibonacci sequence.

% Kronecker delta function starting from n=0 to n=9
x = [1,zeros(1,9)];
% initial conditions of filter
init = [0,0];
% compute the filter response
y = filter(B,A,x,init);


A quicker way to compute the impulse response is through the impz command. The following line of code not only gives the first 10 values of the impulse response, it also produces a stem-line plot of the impulse response.

% compute impulse response
impz(B,A,10)


A simpler way to implement a Fibonacci sequence generator would be to discard the input x and initialize the filter to [1,0] instead of [0,0]. In any case, the Fibonacci filter example is not really practical, as the numbers increase until the internal states exceed the numerical limitations of the implemented machine. An unbounded response indicates that the filter is unstable, and this is confirmed by the location of a pole outside the unit circle in the Z-domain.

## Mathematical hand-writing recognition and LaTeX

I came across a really neat web demo of a mathematics equation hand-writing recognition tool called Web Equation. It can be used to recognize a hand-written mathematical expression (using your computer mouse or track-pad), and then convert it to the corresponding LaTeX or MathML code fragment. A few moments after the user has ‘drawn’ the formula, the code-fragment appears in a small box and can then be copy-and-pasted into your document editor.

When creating technical documents using the LaTeX document markup language, mathematical equations can get complicated enough to require frequent visits to the corresponding reference manuals. This tool is apparently written using JavaScript and simplifies the process of creating equations through an intuitive interface and a simple cut-and-paste operation.

It does pretty well with my track-pad written Discrete Fourier Transform:

## Installing GHDL on a Mac

GHDL is a popular open-source compiler and simulator for VHDL. Precompiled binaries are available for Windows, Gnu/Linux and MacOS-X (PowerPC), but unfortunately, not for MacOS-X (Intel). In order to run GHDL on an Intel-based Macbook Pro, compiling GHDL from source is one option, and various packages (including ADA) need to first be installed. Another option is to use the WINE software layer to run an existing GHDL binary compiled for Windows or Gnu/Linux.

WINE is available for installation through the MacPorts project. Installation instructions for MacPorts can be found here, if needed. Before installing anything through MacPorts, it’s a good idea to update the dependencies and the MacPorts installation by using the ‘selfupdate’ option. WINE can then be installed using the ‘install’ option:

# update the MacPorts installation
sudo port selfupdate
# install software using the official project name
sudo port install wine


Periodic maintenance and updates through MacPorts can be achieved by running the ‘upgrade’ option, and the following command updates all software installed through MacPorts, if anything is out-of-date.

# upgrade any outdated installations


The next step is to download and install the precompiled binary from here. Here’s the direct download link to GHDL-0.26-2008Apr07.dmg. Once downloaded, double-clicking the file will mount the disk image ‘GHDL-0.26’. Navigate down to the sub-folder called ‘wine’, in which two items will be found: a sub-folder called ‘GHDL’ and a bundle called ‘Wine.bundle’. Copy the ‘GHDL’ folder to your home-directory and rename it to ‘.wine’ (make sure a .wine folder doesn’t already exist in your home directory). This places the executable ‘ghdl.exe’ in the WINE search path.

# change directory to the sub-folder
cd /Volumes/GHDL-0.26/wine/.
# copy and rename the executable folder
cp GHDL ~/.wine


As an example, if your top-level design is called ‘mydesign’ and the VHDL source code is placed in the file ‘mycode.vhd’, the following sequence of commands will compile and run your code. The compilation command can be run as many times as necessary to compile all source files. The elaboration command is for linking/loading and creating the final binary, which is executed when the simulation is run.

# compile the design
wine ghdl.exe -a mycode.vhd
# elaborate the design
wine ghdl.exe -e mydesign
# run the simulation
wine ghdl.exe -r mydesign


For more details on other GHDL options, use the ‘–help’ argument. Useful options include ‘-work’ for specifying the work library, ‘–ieee=synopsys’ for specifying the use of a particular version of the IEEE standard VHDL libraries, and ‘–vcd=FILENAME’ for specifying the name of the VCD waveform dump file.

# compile the design
wine ghdl.exe --help


## Unix and the Fink Project

Ever since the Apple Mac operating system switched to its Unix-based underpinnings with Mac OS X, one of the most useful tools for Mac users has been the Fink Project. Their stated aims to “bring the full world of Unix open source software to Darwin and Mac OS X” has been wildly successful for those of us still reliant on Unix tools despite having guiltily moved on to one of the major commercial operating systems.

Some of the software tools available through Fink include Gnu/Emacs (which I had admittedly already installed on my powerbook from source), the Xfig drawing program, and the teTeX distribution of the TeX document preparation system invented by Donald Knuth. The totality of these three tools comprise all that I need in order to write and publish papers in my preferred format of TeX.

The Fink Project homepage has a link to a binary installer for the PowerPC version of Mac OS (as well as the newer Intel architecture). Once Fink has been installed, the shell paths need to be updated to use the specific fink directory paths. The Fink Project decided to use entirely separate Unix System Resources (/usr/) and binary (/bin/) locations as the main Unix installation by Mac OS. These are located in the seemingly arbitrarily named directory of /sw/. I agree with this setup decision because it minimizes the potential for interference between the Mac system Unix installation and the Fink project installation, especially during future updates.

Based on the Debian package management system (apt-get, etc), fink keeps a list of package dependencies in order to maintain all software within its purview. This tree of dependencies is used to ensure that all software libraries are installed or updated before any dependent updates take place. In this way, your open source software always remains in full working order without the problems that accompany out-of-date libraries.

Not all packages are available in binary format, and need to be built from source. This can be done by first installing the Apple Xcode developer tools (available from http://developer.apple.com/), which includes versions of the Gnu Compiler Collection (gcc). Finally, many older graphics-oriented tools such as xv and tgif require the X window system, or X11. Although X11 is available through Fink, there is also a version available directly from Apple. Fink allows either to be in use by its applications, and this can easily be configured.