So last night I built my minipov2 board [1] and got it running, and
wrote a few simple programs for it. Several things finally clicked:
- It's faster to compile a program, load it into the microcontroller
with avrdude, and see the results, than to restart Firefox.
- Bresenham's line-drawing algorithm is a first-order delta-sigma
converter. This isn't news to the world, but it was news to me.
When I use a first-order delta-sigma converter instead of the usual
PWM crap to drive the LEDs to fade, they flicker a lot less.
A kragen-hacks post is on the way.
- I can make a "bidirectional LED" circuit [0] by cutting a trace and
running a single patch wire to an unused I/O pin, thus converting
this output-only machine into a machine with both input and output.
- If you have three light sensors (such as LEDs) in a triangle about
half an inch apart, you should be able to use differential light
input variations over time to sense the shadow of someone's thumb or
finger moving over the area. That could be an inexpensive
replacement or supplement to a touchpad, and might work better for
tiny portable electronics whose capacitive coupling to their
environment is very poor.
- the persistence-of-vision lettering is actually quite hard to see,
partly because it appears backwards half the time, partly because
the font is kind of lame, partly because the vertical lines aren't
very well defined (the LEDs are on for too long), and partly because
it appears in a different position on every stroke. Adding an
accelerometer could synchronize the locations, but the cheapest one
I can find, the ADXL322, costs US$6 in quantity 1 or US$5 in
quantity 100 --- nearly twice the parts cost of the rest of the
Minipov. However, if the waving back and forth is under the control
of a person, you might be able to synchronize the person's motions
with the cycling of the text by emitting a rhythmic sound through
earphones, enabling the person to shake the device in time like a
maraca. Rhythmic sounds should be well within the capability of the
8MHz ATtiny2313 on the minipov2.
- I was thinking about Walsh functions and Hadamard matrices; the
"fast Walsh transform" allows you to transform a vector of length
2^N into a space defined by 2^N basis functions called "Walsh
functions", using N * 2^N time instead of the straightforward 2^(2N)
time. It's also its own inverse except that you have to divide your
result by the scalar 2^N.
So far, this sounds like a Fourier transform. The main difference
is that all the values in the Walsh (or Hadamard) matrix are all +/-
1, so the Fourier multiply-accumulates become merely adds or
subtracts.
And the Walsh transform seems to do a reasonably good job of
approximating the Fourier transform's localization of frequency
information. I sampled a single cycle of sin(x) at 256 points, ran
it through the Walsh transform, zeroed all but the six points whose
absolute value were >8, and ran it through the Walsh transform
again; the result was a reasonable approximation of the sine wave.
(The noise introduced by the approximation was 25dB below the
signal.) So you can imagine testing for this sine wave in the
output of a 1-bit ADC by multiplying a 256-bit vector of 1-bit input
through this small 6x256 matrix (most naturally done using XOR and
then population count).
Apparently Walsh transforms have been used for some decades for
digital signal processing. Thanks again to Derek Robinson for
turning me on to them.
- In Henry Massalin's thesis [2], he made a wish for a bitwise
perfect-shuffle instruction in future CPUs, in particular for
interleaving bit planes on their way to a framebuffer. It seems
that if you had an embedded processor with largish registers and you
wanted to do Walsh transforms on bitstreams, maybe you could get
started sort of as follows:
- load 8 bits of the bitstream into the low 8 bits of a 32-bit
register, setting the rest to zero; usually this is a single
instruction
- perfect-shuffle the register twice. Now each of those 8 bits is
the LSB of an otherwise-zero nibble; as long as the nibbles don't
overflow, you can add and subtract them in parallel without special
SIMD instructions.
- copy the register to another register; shift the low 16 bits into
the high 16 bits of a third register
- add and subtract the three registers to perform a step of the
Walsh transform on 8 samples at once. (Maybe you should do this
in nibble-wise excess-8 to avoid carries.)
I wonder what other SIMDish operations are enabled by
perfect-shuffle. The idea that perfect-shuffle is useful for doing
the Walsh transform isn't new, but I haven't seen it suggested in
the context of implementations on CPUs before. (I'm not entirely
sure it works.)
I still don't know of any CPUs that provide the perfect-shuffle
operation. The AVR used in the minipov2 doesn't [4], nor does the
ARM7 [3], nor the x86 [5], nor did the PowerPC as of 2000 [6].
[0] Mitsubishi Electric Research Laboratories Tech Report TR2005-35,
"Very Low-Cost Sensing and Communication Using Bidirectional
LEDs", Paul Dietz, William Yerazunis, Darren Leigh,
http://www.merl.com/publications/TR2003-035/
[1] http://www.ladyada.net/make/minipov2/index.html --- sorry, the kit
has negative-one units in stock. By Limor Fried.
[2] Henry Massalin, 1992, "Synthesis: An Efficient Implementation of
Fundamental Operating System Services",
http://citeseer.ist.psu.edu/massalin92synthesi.html
ftp://ftp.cs.columbia.edu/reports/reports-1992/cucs-039-92.ps.gz
http://www.cs.columbia.edu/~library/TR-repository/reports/reports-1992/cucs-039-92.ps.gz
[3] ARM7TDMI data sheet, ARM DDI 0029E, section 4, "ARM Instruction
Set", http://www.e-lab.de/ARM7/ARM-instructionset.pdf
[4] Atmel preliminary data sheet for ATtiny2313/V, apparently last
revised 2004-08, Rev. 2543H-AVR-02/05,
http://www.atmel.com/dyn/resources/prod_documents/doc2543.pdf
[5] AMD, "AMD64 Architecture Programmer's Manual Volume 3:
General-Purpose and System Instructions", publication no. 24594,
rev. 3.11, revised 2005-12.
http://www.amd.com/us-en/assets/content_type/white_papers_and_tech_docs/24594.pdf
[6] IBM, "PowerPC Microprocessor Family: The Programming Environments
for 32-Bit Microprocessors: Software Reference Manual",
publication number G522-0290-01, revised 2000-02-21,
http://www-3.ibm.com/chips/techlib/techlib.nsf/techdocs/852569B20050FF778525699600719DF2/$file/6xx_pem.pdf
