Tuesday, February 9, 2010

Canonical Signed Digit Representation

I've recently had the opportunity to play around with multiplierless filter designs. Here's some Python code to convert numbers to and from Canonical Signed Digit (CSD) representation. It does fractional too, as I like to keep track of my binary points with negative net indices in Verilog-land.

It's based on a short paper I can't remember the name of. More specifically, it's based on the pictures from a short paper I can't remember the name of as I couldn't really follow all the set theory in the text.

To use it, put it on your path somewhere and:

canavan% python
Python 2.6.4 (r264:75706, Dec 7 2009, 18:45:15)
[GCC 4.4.1] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import csd
>>> csd.to_csd(34)
'+000+0'
>>> csd.to_csd(34.75)
'+00+0-'
>>> csd.to_csd(34.75,4)
'+00+0-.0-00'
>>> csd.to_csd(34.75,6)
'+00+0-.0-0000'
>>> csd.to_decimal('+0000')
16.0
>>> csd.to_decimal('+0000.0-000+0-000+0000-')
15.761955261230469
>>>

Beware, I don't do any input validation yet...

Oh yeah, linkage: http://sourceforge.net/projects/pycsd/