Think Create | Deqing Sun

Digital Smart Ruler—when Euler circuit meets electronic circuit

by on Jul.21, 2011, under My gadgets


Higher quality of pics will be available soon.

The first time I saw Shay Shafranek’s electronic ruler, I thought it acts as a bunch of keys. Then the controller can scan them and get the value thought I later realized that it actually works in analog mode. But I am curious about its possibility to convert it to a true digital one. And I began to solve the problem.

In other word, the problem can be described as: How to wire the serially connected keys (with least IOs). For example, we can use 7 IO ports to control 6 keys, but it isn’t efficient at all. There should be a solution that require less IOs.

Let’s start from basic problem. When there are 3 keys. We need 3 IOs. It is obvious, right?

It is as good as Charlieplexing which supports (n(n-1))/2 keys without diode.

But can 4 IOs control 6 keys?

It is impossible (not my stupidity). Above is the best solution I can get. 5 keys is the best result.
Hmm… It seems I can not go far without theory. So, dye the different electrical network in the circuit.

We got a sequence of number….

If we rearrange the keys:

So the circuit problem is converted to a “Drawing by one line” one. Four IOs can control 6 keys in Charlieplexing as shown in the right graph. But it can not be drawn in one line because it has four vertices of odd degree. Only up to five edges can be drawn by one line.

Now the arrangement of electrical networks is equivalent to finding an Euler path in a complete graph. For 2n+1 IOs, since each vertex has an even degree, the complete graph can form an Euler circuit. For 2n IOs, n edges need to be deleted to form an Euler circuit, or n-1 edges for an Euler path.

I found a simple way to generate a symmetric solution for a complete graph (or n edge removed for 2N vertex). There is an example.

If we define the edge between vertexes #1 and #2 as length of 1, vertexes #1 and #3 as length of 2, there will be 5 groups of edges with length 1 & 2. Start from any vertex. In this example, I choose vertex #1, then go through one edge of length 1 and one edge of length 2 (backward 1 and forward 2 in this example). Then I arrive in vertex #2. If the difference between the starting vertex number and the ending one is co prime to the number of edges, repeat the procedure. And a symmetric Euler circuit will be generated.

Then use the sequence of vertexes in the Euler circuit for the guide of circuit wiring. The keys can be connected to controller easily.


1 Comment for this entry

  • Shay

    Hi,
    I am so happy and flattered to see this 🙂 Thanks for taking the time for this challenge.
    How is your version working?
    I personally didn’t find the way to solve it and make it at a reasonable cost… well, if you did I’de love to hear more.
    (BTW, I’m not the greatest electronics expert at all…)

    Thanks again!
    Shay

Leave a Reply

Looking for something?

Use the form below to search the site:

Still not finding what you're looking for? Drop a comment on a post or contact us so we can take care of it!

Blogroll

A few highly recommended websites...