Charlieplexing Topology Question

Question

I'm sitting here with a pencil and paper trying to arrange a charlieplexed 5x8 LED matrix. I'm trying to arrange this in such a manner that no two lines cross each other. Without a guiding theorem of some sort, I keep isolating lines, that is, the line ends up completely surrounded in a box composed of it's neighbor lines.

I'm looking at this problem and thinking "Some mathematician must have already solved this". Nodes, matrices, edges...it just feels like a topology problem. Anyhow, I don't have the maths to solve it, at least not conclusively.

Anybody have any thoughts on this?

To head this off - yes, this would be simple with multiplexing. I need to charlieplex this.

Answer 1

Since most of the column lines are also row lines I doubt it is possible. To avoid crossing lines in a schematic I use named nets.

My Charlie-plexing schematics (which use named nets) are at -- http://wiblocks.luciani.org/FAQ/faq-charlie-plex.html

Answer 2

I am unclear what you mean by "no two lines cross each other". Is this just a problem with the display of the schematic? If so, it's quite common for un-connected lines to cross on a schematic. Often you will see connected lines have a little filled circle 'joint' to indicate the connect, and unconnected lines, one of the lines will make a little unfilled half-circle 'jump' over the other line, to indicate they are crossing but not connected.

Answer 3

A "Charlieplexed" display (Wikipedia lists the concept as having been invented in 1996, but I'm sure the approach was used before that) represents a complete graph of all processor signals (every pair of processor signals has to have an LED on it). A complete planar graph of N nodes may only be drawn for N less than 4.

I think the most natural way to visualize a Charlieplexed display would be as a square matrix with the LED's on the primary diagonal replaced with shorting jumpers. When laying out a board, simply shove the LEDs on either side of the diagonal inward so as to yield an NxN-1 physical configuration.

The only disadvantages Charlieplexing would have over normal multiplexing would be the fact that Charlieplexing uses a nearly-square square grid, and that one has to in software shift the pixels on one side of the diagonal so as to account for the gap. Electrically, I would think driving a Charlieplexed display from a tri-state CPU pin should be easy: wire an NPN transistor (e.g. 2N2222) with the collector at VDD, base connected to the CPU pin, and the emitter tied to the Charlieplex line to supply the positive (row-scanned) drive; wire a current-setting resistor between the CPU pin and the column wire.

Answer 4

I think a better formulation of this question is:

Can the schematic of an n-channel charlieplexed circuit be drawn as a finite, connected planar graph?

Euler's formula could probably be used in some way (it's a planar graph if vertices − edges + faces = 2), but you'd need a nice clean formula (well, maybe a messy one would work too) for determining the number of faces in the graph.