Saturday, May 18, 2013

My FPGA design skills are a little rustier than I thought

Today I'm going to Makerfaire in the Bay Area. I'd had an idea percolating in my head to use an FPGA to implement fixed-point equivalents of the analog music synthesizer modules of the 1970s, and gave myself a couple of weeks to design and build a simple synthesizer. I'd been a synthesizer enthusiast in high school and college, having attended high school with the late David Hillel Wilson and had many interesting discussions with him about circuit design for synthesizers, a passion he shared with his father. While he taught me what he knew about synthesizers, I taught him what I knew about electronics, and we both benefitted.

Now I have to confess that since my switch to software engineering in the mid-90s, I haven't really done that much with FPGAs, but I've fooled around a couple of times with Xilinx's ISE WebPack software and stumbled across MyHDL, which dovetailed nicely with my long-standing interest in Python. So I ordered a Papilio board and started coding up Python which would be translated into Verilog. My humble efforts appear on Github.
There was a lot of furious activity over the two weeks before Makerfaire, which I hoped would produce something of interest, and I learned some new things, like about delta-sigma DACs. Being an impatient reader, I designed the delta-sigma DAC myself from scratch, and ended up diverging from how it's usually done. My design maintains a register with an estimate of the capacitor voltage on the RC lowpass driven by the output bit, and updates that register (requiring a multiplier because of the exp(-dt/RC) term) as it supplies bits. It works, but has a failure mode of generating small audible high frequency artifacts particularly when the output voltage is close to minimum or maximum. On the long boring flight out, I had plenty of time to think about that failure mode, and it seems to me the classic delta-sigma design would almost certainly suffer from it too. I think it could be reduced by injecting noise, breaking up the repetitive patterns that appear in the bitstream.

I like Python a lot but I'm not sure I'm going to stay with the MyHDL approach. As I learn a little more about Verilog, it seems like a probably better idea to design directly in Verilog. The language doesn't look that difficult, as I study MyHDL's output, and while books on Verilog tend toward expensive, some of them are more affordable. Those books are on the Kindle, and a couple others are affordable in paper form.

MyHDL-translated designs do not implement Verilog modularity well, and I think it would be good to build up a library of Verilog modules in which I have high confidence. MyHDL's simulation doesn't always completely agree with what the Xilinx chip will do. And while MyHDL.org talks a lot about how great it is to write tests in Python, the Verilog language also provides substantial support for testing. Verilog supports signed integers, but as far I've seen, MyHDL doesn't (this is INCORRECT, please see addendum below), and for the fixed-point math in the synth modules, that alone would have steered me toward straight Verilog a lot sooner had I been aware of it.

It appears the world of Verilog is much bigger and much more interesting than I'd originally thought. I've started to take a look at GPL Cver, a Verilog interpreter that (I think) has debugger-like functions of setting breakpoints and single-stepping your design. I had been thinking about what features I'd put into a Verilog interpreter if I were writing one, and a little googling showed me that such a thing already existed. So I look forward to tinkering with CVer when I get home from Makerfaire.

EDIT: Many thanks to Jan Decaluwe, the developer of MyHDL, for taking the time to personally respond to the challenges I encountered with it. Having had a couple of days to relax after the hustle and bustle of Makerfaire, and get over the disappointment of not getting my little gadget working in time, I can see that I was working in haste and neglected to give MyHDL the full credit it deserves. At the very least it explores territory that is largely uncharted, bringing modern software engineering to the HDL world where (like all those computational chemists still running Fortran code) things have tended to lag behind the times a bit.

In my haste, I neglected the documentation specifically addressing signed arithmetic in MyHDL. I didn't take the time to read the docs carefully. As Jan points out in his writings and in the comment to this blog, MyHDL's approach to signed arithmetic is in fact simpler and more consistent than that of Verilog. What does signed arithmetic look like in MyHDL? It looks like this.

    # INCORRECT
    >>> x = Signal(intbv(0)[8:])
    >>> x.next = -1
    Traceback (most recent call last):
        ...blah blah blah...
    ValueError: intbv value -1 < minimum 0

    # CORRECT, range is from min to max-1 inclusive
    >>> x = Signal(intbv(0, min=-128, max=128))
    >>> x.next = -1      # happy as a clam

In the case where MyHDL's behavior appeared to diverge from that of the physical FPGA, my numerically-controlled amplifier circuit above uses one of the hardware multipliers in the XC3S500E, which multiplies two 18-bit unsigned numbers to produce a 36-bit unsigned product. When my music synthesizer was at one point unable to make any sound, I tracked it down to the amplifier circuit, which was working fine in simulation. There was already a hardware multiplier working in the delta-sigma DAC. I poked at things with a scope probe, and scratched my head and studied my code and studied other peoples' code and ultimately determined that I needed to latch the factors in registers just prior to the multiplier. Whether it's exactly that, I still can't say, but finally the amp circuit worked correctly.

I wrongly concluded that it indicated some fault in MyHDL's veracity as a simulator. If it didn't work in the chip, it shouldn't have worked in simulation. But with more careful thought I can see that it's really an idiosyncrasy of the FPGA itself, or perhaps the ISE Webpack software. I would expect to run into the same issue if I'd been writing in Verilog. I might have seen it coming if I'd done post-layout simulation in Webpack, and I should probably look at doing that. Once the bits are actually inside the chip, you can only see the ones that appear on I/O pins.

Monday, March 04, 2013

The Digi-Comp 1 rides again?

As computer people go, I'm rather an old fart, and my favorite childhood toy was this plastic computer, the Digi-Comp 1. See the three horizontal red things that run almost the full width? Those are flipflops, and the window on the left shows whether they are in the zero or one position. The six vertical metal bars in front are AND gates, and the little white tubes stuck onto the pegs on the fronts of the flipflops tell whether that bit is factored into the AND term. The six red plastic things on the top, together with similar stuff on the back, form three OR gates, which drive the values of the flipflops on the next clock edge. The two white sliders on the bottom worked in opposition, providing a hand-powered two-phase clock to drive all this stuff.

Over the past couple of days I placed an order with danger!awesome, a laser cutter shop in Cambridge MA. They have a nifty collection of laser cutters and were happy to hear that design files are available on the Thingiverse website. So I ordered some stuff and picked it up this evening, and that was fun. I had hoped they could make me this marble binary adder, but the designer didn't supply design files they could use. So no marble adding machine for me. Darn.
Thinking about that, my mind inevitably went back to the Digi-Comp 1. I started wondering whether I could build a Digi-Comp 1 using laser cut plywood, like the other trinkets I picked up this evening (a Companion Cube, a desktop trebuchet, a Shrimpbot, and a few little animals). Could that be feasible? The Digi-Comp 1 was basically a programmable logic array, which consists of two rectangular regions, one for AND gates and one for OR gates. On the Digi-Comp 1 these are respectively the front surface and the back surface of the device.

I thought about this for a while and came up with some very incomplete rough sketches to solve the problems of how the gates would work and how the binary values should be latched for one clock cycle. As with the Digi-Comp 1, this would be a rectangular thing with the AND plane on the front and the OR plane on the back. The flipflops would be horizontal bars along the front with two positions (left=0, right=1) and possibly the same window display that appears on the original Digi-Comp 1. The AND gates are vertical bars also on the front, connecting to vertical bars on the back. The OR bars on the back can move left and right if permitted. At a certain point in the clock cycle, the horizontal position of each OR bar is inverted with a little lever and latched as the new position for the corresponding flipflop. There is still a lot of mechanical engineering to think about. Should the bars be retracted with springs or rubber bands? There needs to be a lot of machinery to get everything to move when and where it's supposed to, and there needs to be a crank on the side to drive it. So there will be cams and gears and all sorts of fun stuff.

UPDATE: I found a place called Minds-On Toys that is selling a Digi-Comp kit which reproduces the exact mechanical design of the original. Looks very nice, except for the labor-intensive-looking bit at the bottom about fabricating your own plastic tubes.

Saturday, February 02, 2013

Ruby and Rails and all that stuff

At the suggestion of a recruiter, I'm learning Ruby on Rails this weekend. I was active on the comp.lang.python mailing list when Matz came around talking about Ruby. It seemed like a good thing, but I mostly ignored Ruby for years because it seemed to be solving problems that I already had solutions for with Python. Likewise, Rails seemed to retread the same ground already covered by Django.

Motivated to take another look because of the wild popularity of Rails, I see there's something in Ruby that deserves attention, which is blocks (anonymous closures, or what Lispers would call lambda expressions). They function as closures, and any language that makes a closure a first-class object is a good language. There are a ton of good Ruby tutorials. I myself am partial to Ruby in Twenty Minutes. There are also a good Rails tutorial (and I'm sure there are several others). Another notable thing in the Ruby community is RDoc, an unusually good documentation tool.

I'll be installing Ruby and Rails on an Ubuntu 12.04 machine. I don't like how old the packages are in the official Ubuntu repository, so I'll install from Ruby websites instead. The first thing to do is install RVM with these two commands:
$ curl -L https://get.rvm.io | bash -s stable --ruby
$ source /home/wware/.rvm/scripts/rvm
Later I reversed my decision about the official repositories, when I discovered I could install "ruby1.9.3". What RVM offers is an ability to run multiple Ruby environments on the same machine, like Python's virtualenv.

So now Ruby is installed and you can type "irb" to begin an interactive Ruby session. Next install Rails, and some additional things you'll need soon:
$ gem install -V rails
$ sudo apt-get install libsqlite3-dev nodejs nodejs-dev
Now you can jump to step 3.2 of the Rails tutorial and you should be good to go. Or you can go to the Github repository (README) which I cloned from the railsforzombies.org folks, and that's where I'm going to be tinkering for a while.

When debugging Rails controller code, you'll want to uncomment "gem debugger" in Gemfile, insert "debugger" into your code, and then reload the page in your browser, and it will stop the development server and put you into an interactive shell with all the variables available in mid-process. You'll also have GDB commands like "step", "next", "continue", and breakpoints.

When you're ready to deploy, consider Heroku, a Rails hosting service that lets you use one virtual machine for free. I've deployed my Zombie Twitter app there, and after a few initial bumps, things have gone pretty smoothly.

Here's a custom search for Ruby and Rails:

Saturday, January 26, 2013

Setting up an RDF server in VirtualBox, part 2

This is the second part of a two-part (maybe N-part?) series about setting up an RDF server in a VirtualBox instance with the Ubuntu 12.04 server distribution. In this part, I'll set up Mediawiki as a place to conveniently edit RDF/Turtle documents.

You might be thinking, what about Semantic Mediawiki? Doesn't this already exist? My experience with SMW was disappointing. The source syntax for creating links is pretty straightforward, and the silly naming scheme for importing external ontologies doesn't seem too bad. But when you want to do any real work with external ontologies, it gets difficult. After a few days of hacking around I couldn't find a way to say that a predicate defined in my SMW instance was owl:sameAs some predicate defined externally. At that point, I decided to strike out on my own.

The results of that effort are on GitHub at https://github.com/wware/stuff/tree/master/semantic-wiki. The setup script is to be run in the VirtualBox instance after the Ubuntu 12.04 server installation (with LAMP and SSH servers enabled) has completed.

This is a work in progress. When I've got it beaten into presentable shape, I'll put it up at http://willware.net with more explanatory material.

Sunday, November 18, 2012

Setting up an RDF server in VirtualBox, part 1

VirtualBox is an open-source virtual machine that you can use on Windows, Mac OSX, or Linux to run one of the other operating systems. Here I'll be using VBox on an Ubuntu Linux desktop machine to set up an Ubuntu server machine. The point in doing that when the two operating systems are so similar is to keep the two environments separate, and to discover what I'll need when I move the server to a VPS.

I'm doing this on a laptop with a 160 gig partition with Ubuntu 10.04 desktop. I can comfortably dedicate 20 gig to the virtual hard disk image. The VM will run Ubuntu 12.04 server. No shared folders because they won't be available on the VPS.

Make sure you have a good fast Internet connection for the Ubuntu desktop machine, and download the Ubuntu server ISO. It's available as 32-bit or 64-bit. If you're not sure about your CPU, you're probably better off with 32-bit. Set up VirtualBox:
$ sudo apt-get install virtualbox-ose

Now you'll find "VirtualBox OSE" in the Applications->Accessories menu in the upper left of the screen. Click on that, and when the window comes up, click on the light blue "New" icon. Pick a machine name, and Linux/Ubuntu as the virtual machine type, and give yourself a decent amount of RAM and hard disk space. It's nice to start the hard drive with 20 or 30 gig if you can spare it. Once the VM is created, go into settings for it, click "Storage" and click the third line with the CDROM icon. To the right of "CD/DVD device" click the yellow folder icon and navigate to the Ubuntu server ISO that you downloaded earlier. Set "Network" to the "Bridged adapter" option. Under shared folders, add your home directory (read only) and give it a name you'll remember. Now it's time to start the VM and install Ubuntu server on the virtual hard disk you've created. Before I could do this on my laptop, I found I needed to go into Settings->System->CPU and enable PAE.

During the installation process, you'll be asked what kinds of servers you want to run. Select "OpenSSH server" (so you can ssh/scp into the VM) and "LAMP server" (to get Apache and MySQL) and "Tomcat Java server" (to pick up a bunch of Java stuff you'll want for Jena). If you select an empty password for the root user on MySQL, you'll need to enter it multiple times, so you may want to select something almost as trivial like "root". You don't need to worry too much about security with a VM that will only be reachable on the local subnet.

When the installation is done, the machine will reboot, and the VM window will close and re-open. Go to the "Devices" menu at the top and under "CD/DVD devices", unclick the Ubuntu server ISO.

On to Jena. Looks like there is some good advice here, but some of it is dated so I'm tweaking it a bit: http://ricroberts.com/articles/installing-jena-and-joseki-on-os-x-or-linux

Log into the virtual machine and type:
$ sudo su -
# chmod 777 /opt
# exit
$ cd /opt
$ wget http://www.apache.org/dist/jena/binaries/apache-jena-2.7.4.tar.gz
$ wget http://www.apache.org/dist/jena/binaries/jena-fuseki-0.2.5-distribution.tar.gz
$ for x in *.gz; do tar xfz $x; done
$ rm *gz               
$ mv apache-jena-2.7.4 apache-jena
$ mv jena-fuseki-0.2.5 jena-fuseki
$ chmod u+x jena-fuseki/s-*

Add these lines to your .bashrc:
export FUSEKIROOT="/opt/jena-fuseki"
export JENAROOT="/opt/apache-jena"
export PATH="$FUSEKIROOT:$PATH"
export CLASSPATH=".:$JENAROOT/lib/*.jar:$FUSEKIROOT/*.jar"

You'll want to copy some client-side Ruby scripts from the server's Fuseki directory to your host machine. My VM is at 192.168.2.7, so on the host machine I typed:
$ scp 192.168.2.7:/opt/jena-fuseki/s-* .
I also needed to install Ruby on the host machine.

Now you can start up the Fuseki server and load it with some data. The docs for Fuseki are here. On the server:
$ cd /opt/jena-fuseki
$ ./fuseki-server --update --mem /dataset

This starts an empty database of RDF triples. This database is in-memory and non-persistent, and will vanish when you control-C. Back on the host machine, you can enter some data into the database:
$ ./s-put http://192.168.2.7:3030/dataset/data default family.rdf
$ ./s-put http://192.168.2.7:3030/dataset/data default wares.rdf

This is a small semantic graph talking about who in my family is married and whose kids are whose. To  make sure the data was actually stored, we can query it.
$ ./s-get http://192.168.2.7:3030/dataset/data default

This prints out the entire database in Turtle, an update of N3. Or we can get the same thing in JSON:
./s-query --service http://192.168.2.7:3030/dataset/query 'SELECT * {?s ?p ?o}'

I can see that I don't have the time and energy to get everything done in one sitting that I hoped I would accomplish. So this is part 1, and a part 2 will follow later, and I'll make sure they include links to each other.

Tuesday, November 13, 2012

A Semantic Network of Patient Data

This idea has two inspirations. One is this TED talk by Dave deBronkart or "e-Patient Dave". The other is the work that has been done on the semantic web and linked data.

Dave's talk is about patients taking control of their medical records and sharing them with other like-minded patients, so that they can learn from one another's histories and experiences. Some of these patients, including Dave, had terminal diagnoses and were able to improve or resolve those conditions because of having shared data with others.


The semantic web is the idea of formatting information so that computers can do more with it than simply store it or transmit it or display it on a screen. Computers can understand the meaning of the information much as a human would, so they can reason about it and draw new conclusions that aren't already spelled out. I first learned about it in a 2001 article in Scientific American. There are some more details here. I've blogged in the past about some of the basic ideas.

In the semantic web, all "things" (nouns, basically) are assigned URIs (web addresses). Relationships between things (and relationships are also things) are represented as RDF, where every statement is a triple of URIs, being a subject, predicate, and object. These statements are often printed or transmitted in XML, but the N3 language is more readable for people. Typical relationships look something like this.
  Will, town, "Framingham MA".
  Will, name, "William Ware".
  Will, pet, cat#12345.
  cat#12345, name, "Kokopelli".
  cat#12345, birthyear, 2003.
Strings ("William Ware", "Kokopelli") and numbers (2003) can be raw data, everything else is a URI. The idea is that a URI connects you to the rest of the semantic web of meaning, so if you don't know what a "pet" is, you can follow that URI, or query other triples with "pet" in them, to find out more.

You might wonder if it's silly to have such a primitive representation for knowledge. It allows the same kinds of economies of scale that we get by representing information in a computer with ones and zeroes. Because the format is so simple and uniform, we can build processing architectures that can be very efficient, and people have been doing that for over ten years. We have scalable databases for RDF, and when we set up rules that mimic set theory, we can build reasoning engines that extract new conclusions from the data.

When data is formatted with an appropriate ontology, it can be searched in rich complex ways, and computers can look for patterns and correlations that a human might not notice. When applied to patients' medical data, the results might be new medical knowledge or new treatment options.

There are other ways to find new information hidden in patient data. Semantic web technology is great for pure logic, but for quantitative measures (a dosage increase in this medication seems to cause a decreased amount of that neurotransmitter) we can turn to machine learning, where progress in the last decade or two has been explosive, given the data available on the web and the economic rewards for finding patterns in it.

An idea I've blogged about in the past (and spoken about at a couple of very small conferences) is applying this to general scientific literature, with the goal of hastening scientific progress and in particular medical progress (since I'm an old fart now and interested in that sort of thing).

If this topic interests you and you wish to discuss it, I'm starting a Google Groups forum for that purpose.

UPDATE: I've discovered that there is a company in Cambridge, MA called PatientsLikeMe which already pools patient data into a database, and sells subscriptions to that database. I don't know if they place the same emphasis on machine-tractable formats that I've done above. But knowing that somebody is doing it on a commercial basis, I don't see much point in trying to replicate that effort in my evenings and weekends.

Thursday, November 08, 2012

Node.JS on the Raspberry Pi

Most of this procedure is taken from a posting on Github by Sander Tolsma. His post is a little bit old and some of the steps he included can be skipped because the versions of things have become better synchronized. So very briefly, here is what to do, assuming you've successfully booted into Raspbian.

$ sudo apt-get install git-core build-essential
$ # IIRC, build-essential is already present on Raspbian
$ git clone https://github.com/joyent/node.git
$ cd node
$ git checkout v0.8.14-release
$ #             ^^^^^^ update to most recent stable version
$ ./configure
$ make        # this takes a while
$ sudo make install

Voila, you're done. Type "node" at the Linux prompt and you'll get Node's ">" prompt. Then you can type in JavaScript and watch it run interactively, or you can create a file of JavaScript and run it.

pi@raspberrypi ~ $ cat > foo.js
for (var i = 0; i < 3; i++)
  console.log(i);
^D
pi@raspberrypi ~ $ node foo.js
0
1
2

I'd like to import events from hardware so that they can take handlers, just like DOM event handlers running on a browser. One approach would be to run an HTTP server in Node and set up endpoints for the events I want to handle. That sounds like quite a bit of overhead for hardware events.

Alternatively, I could do what looks like the right thing, involving eventfd and its cohorts. I need to dig into the Node source code to see how to do that, and do more research in general.