Kirchhoff-Lukasiewicz Machines

I've been working on analog computing since 1990 when I invented,
and my students and I built, the first Lukasiewicz Logic Arrays.
This is an image of the first VLSI LLA, which is still used
as a comparison benchmark for other designs.

This is a schematic of the compacted "railroad-tie" design of the
LLA I use today.  It generates a complete set of piecewise-linear
functions that are digitally reconfigurable, and would otherwise
fill four MOSIS TinyChips, if implemented as an H-tree LLA.

I have spent the past year working more on robotics -- there's a
large NSF award and students to consider -- so my research into
KLMs has been slowed.

However, I spent my sabbatical in 1996 doing research on tools
and methods to design and use these machines that are so
trivially easy to build.  Here's a screen shot of the KLM visual
layout editor and simulator I am programming for the Macintosh.

Layout is wholly iconic, so one can move one step upward from a
transistor-level layout tool like MAGIC.  This is similar to using
a schematic layout editor in digital.  No such CAD tool yet exists
for KLMs, which is why I am writing one!  Of course, this means
I'm using a digital computer to design analog computers...I find
that amusing.

This is the schematic layout of the first KLM.  It has a conductive
sheet surrounded by a ring diode to restrict current flow into and
out of the sheet to the contacts only.  Two compact LLAs are available
to shape outputs from the sheet.  The sheet and LLA connections are
made at the output pins of the VLSI circuit, which also permits the
sheet and LLAs on the prototype to be tested independently.

This is the VLSI layout of the KLM, created in UNCLE. The conductive sheet
is the green area to the left, with probes embedded in it.  Two Lukasiewicz
logic functional units, in a compacted, efficient form, are at the right.
Note how it compares to the schematic layout in my VLSI CAD tool snapshot.

This is a photograph of the KLM fabricated by MOSIS in a standard 2 micron
ORBIT process (I have yet to use the special analog runs -- haven't needed
them so far).  The conductive sheet is the dark area on the left.
The two Lukasiewicz logic functional units are the white rectangles on the
right.  You can see some of the input and output contacts on the sheet.
They are the white or reddish lines and small squares.  The die is approximately
2.5mm wide by 3mm high.  (This photo was taken by strapping a 10x hand
magnifier onto the lens of a Connectix QuickCam with a rubber band.)

In the next section you can see how several applications can be mapped
to a KLM.  

The first series of diagrams illustrates how the conductive sheet accepts
sensor input to model a cyclotron beam cross-section, then uses the
Lukasiewicz logic functional units to generate a control signal.

This example is from a controller designed and built but not yet installed
at the IU cyclotron. The conductive sheet takes the four sensor outputs, "north",
"south", "east", and "west" and injects their output currents at the edges of
the conductive sheet.

The sheet can be modelled as an ideal infinite plane with constant current
flowing into or out of it, spreading radially from each point.

The outputs of the sheet can then be modified using a set of piecewise-linear 
functions. If the beam drifts away from center, the Lukasiewicz logic units will
generate increasingly stronger signals to correct the error.  More complicated
control functions can be generated than are shown here by using more function
units. The control surfaces are selected using digital values, but could be
"morphed" from one to another if analog inputs were used instead.

Digital values have the benefit of being easy to retain in flip-flops
(memory "bits").  They are also "sharp" and easy to transmit reliably
along long wires in the noisy environment of the cyclotron.

The Lukasiewicz Logic Array functional units are configured to generate
the complete set of piecewise linear functions on a 3 x 3 node mesh. The
functions can be composed to generate more complicated functions either
by adding or subtracting them with wire junctions, using the output
of one functional unit as the input to another, or using the output of
many units as inputs to the same or another conductive sheet.

The same integrated circuit can also act as a silicon "retina" that can be
trained to recognize patterns focused on it, as I described in my 1996
paper at the International Conference on Neural Networks.  No change in the
hardware, i.e. the chip, is necessary.

The same chip can also be trained to compute XOR (exclusive-or), a standard
task for a neural network.

Because the KLM can represent many neurons, the same chip (again!) can also
perform the function of auditory prey localization in a barn owl. The sheet
model doesn't even need Lukasiewicz logic functional units to compute the
localization if the sign of the output can remain inverted (active low).

The next figure shows how the sheet can be thought of as modeling the
barn owl's auditory localizer, translated into a network of leaky neurons.
KLMs abstract away the form of the network, leaving only the function.
The neural network's connectivity and fixed weights (due to distance)
are a function of the sheet.  The neural networks variable weights and
thresholding for groups of neurons is a computed by the Lukasiewicz
logic function unit.

The previous application of KLMs bears a resemblance to Edelman's neuronal
groups, and also illustrates how KLMs can implement Bruce MacLennan's
field computers.

An analog subsumption-like architecture can be constructed for a
hexapod robot by putting the pieces together as shown in the next figure.

The KLM retinas (blue lens-shaped objects) constantly observe the robot and
its environment, and feed processed sensory information "upward" to the
KLM neural field computers, which act on local and global conditions to
generate gaits and select appropriate behavior.  The behavior is generated
using McCulloch and Kilmer's model of the reticular formation.  Kilmer
and I have a paper pending on the use of KLMs to implement the RETIC. 

The reason that the same chip can be used for so many different applications
is because fundamental physical principles underlie the systems in question.

By finding a mapping between these system and the KLMs, or even abstract
mathematical models, we can solve these classes of problems easily.  We
could even use brute force to do word processing with KLMs.  Anyone who
has ever seen Kjell Sandved's "Butterfly Alphabet" poster can understand
how.  Of course, why bother when digital text processing is so much better
suited for the task!

The core of KLM "programming" lies in "shaping" problems for the KLM
by creating a manifold induced in the conductive sheet, and selecting
the  piecewise constant N-dimensional surfaces produced by the Lukasiewicz
logic functional units to generate the solution(s).

There is as yet no "cookbook" way to do this, but I find it relatively
easy to visualize the problem I want to solve, or system I want to
model, and map it to one or more KLMs.  However, that process involves
unlearning the algorithmic mindset we use to program digital computers,
and thinking "backwards" compared to the 1950's style of programming
analog computers, where the equations were turned into machine configurations.

One of the challenges, then, will be to turn this style of visualization
into a rigorous methodology.

There are other important questions in visual design and applied mathematics
of KLMs that I haven't been able to answer yet.  You can find them in my list
of 42 questions about analog computing.

Literature related to KLMs is limited.  I recommend Walter Karplus' 1958
book, "Analog Simulation".  It is, unfortunately, out of print.

The first paper on KLMs  remains unpublished.  I initially called KLMs
"Kirchhoff Machines" because I didn't fully understand their relationship
to Lukasiewicz Logic Arrays.  I periodically revise this paper to include
my new insights into KLMs, and have occasionally provided copies to
interested people.

Since I have tenure I am increasingly unwilling to publish early 
results in the publish-or-perish scramble.  When I have something worth
writing about, I do.  Here is one paper you can obtain by ftp by
clicking on this title:

Programmable VLSI Extended Analog Computer for Cyclotron Beam Control (September 1995) 9 pgs
It shows the prototype beam controller that was built out of conductive foam, the same material used to package digital circuits. I found that amusing, too. That paper preceded the only recent publication on KLMs, my 1996 paper in the Proceedings of the International Conference on Neural Networks: The Continuous Retina: Image Processing with a Single-Sensor Artificial Neural Field Network Another of the things I've learned is that, with the exception of the ISMVL, the long-running International Symposium on Multiple- Valued Logic, there are very few venues that accept undisguised analog computing papers (and I gratefully acknowledge my friends from ISMVL who encouraged my work, among them Jon Butler and Claudio Moraga). The common opinion among most computer scientists is that analog, except in neural networks, is pretty much dead as a computing paradigm ...but is it? Shortly before his death in 1995, and well before Paul Saffo's article, Lee Rubel told me:

"The future of analog computing is unlimited. As a visionary, I see it eventually displacing digital computing, especially, in the beginning, in partial differential equations and as a model in neurobiology. It will take some decades for this to be done. In the meantime, it is a very rich and challenging field of investigation, although (or maybe because) it is not in the current fashion.

Sincerely yours,

It will not take decades, as my early applications demonstrate. I hope that you will examine this modern approach to analog computing in more detail. It is a paradigm that complements digital computing, and unifies digital and analog computer architectures in a very satisfying way.
Return to Jonathan W. Mills Home Page