Tristate multiplexing (or Charlieplexing) is a simple to use technique to expand the number of LEDs that you can light from a simple microcontroller. This post explores the concept, and looks at some interesting calculations we can do when thinking about them.

I’ve been meaning to get around to writing something of a tutorial on the basics of assembly programming using a PIC microcontroller for a while: and this post stared off as the first part of that… But then, in the best traditions of geekery, I got distracted by the interesting mathematics behind the scenes, and instead this post was born. But I’ve not given up on the idea and I will get back to that. Eventually. (But don’t hold your breath). Instead this post is written without any reference to any specific microcontroller architecture, and so you can use the ideas described here on a PIC, an Arduino, and it should even work on a Raspberry Pi (though I’ve not actually tried that yet).

To begin, let’s think about a simple situation where we have a microcontroller which we wish to use to control two LEDs. The simplest implementation is to use one of the microcontroller’s GPIO pins for each LED. This works well for a small number of LEDs; but very quickly gets expensive in terms of the number of pins it uses if you want more than a handful of LEDs; and depending on what else your microcontroller needs to do (and/or how many pins it has available to begin with) it soon becomes unsuitable.

The solution is to multiplex the LEDs – that is to say connect more than one LED to each pin, and use a combination of multiple pins to select the one we want.

Simple multiplexing would take grid of LEDs (here a 3×3 grid) and use 6 GPIO pins to drive them… This uses the fact that a logic level of low isn’t just the absence of voltage in an abstract sense – but rather that it denotes that the pin is pulled down to ground (and so can be used to sink current flowing from another pin).

To light (for example) LED5, we set pins 1 & 3 high, pin 2 low, pins 4 & 6 low, and pin 5 high… The only combination where there’s a potential difference across an LED is LED5 – which lights. The problem is that if we want to light LED7 as well as LED5 we’d have to set pin 4 to high and pin 3 to low in addition to the pins set for LED5… This would have the effect of turning on LEDs 5 & 7 – but also LED4 & LED8: not what we wanted. So to use this technique to light multiple LEDs “simultaneously”: we need to  switch very rapidly between the settings for the first LED and the settings for the second. The human eye isn’t very good at seeing very fast flickering like this – so providing we’re at 50Hz or faster both will appear to be lit at the same time (even though we’re actually only turning one at a time on).

Using this technique we achieve a saving of 3 pins for 9 LEDs (using 6, rather than 9): and if we scale that to 16 LEDs – we’d need 8 pins not 16: a very significant difference.

More generally we can need \(2n\) pins to drive \(n^2\) LEDs. That’s pretty good: but we can do better! Enter tristate multiplexing!

Tristate multiplexing relies on the fact that GPIO pins have three, rather than just two possible states (hence the name tristate). They can be set to either high or low, if they’re in (what we generally think of as) an output mode – or they can be in an input mode – whereupon they have a high impedance (resistance): meaning as far as the circuit is concerned it’s just like we’ve disconnected them.

We can now wire-up our LEDs in a rather different manner to take advantage of this.

Here we’re using just 4 pins to drive 12 LEDs! We save 8 pins over connecting them on a 1:1 basis – and 4 pins over the simple multiplexing.

Before we look any further at the numbers: let’s look at how we use the 4 pins to drive an LED.

Each pin can take one of three states. High (1), low (0), or high impedance (Z). To light LED3 (for example) we set pin 1 to high, pin 3 low – and pins 2 & 4 to the disconnected Z state. Reversing the polarity of pins 1 & 3 would light LED4 instead.

Using this technique we can drive many more LEDs than we have pins: in fact in a general form we can light \(n^2-n\) LEDs from $n$ pins.

This means that as we’ve seen 4 pins can drive 12 LEDs, but 5 pins can drive 20, and 6 can drive 30 (and 8 pins would give us 56 different LEDs). As with our simple multiplexing example in order to achieve any arbitrary combination of LEDs, we have to use the flickering technique to drive each LED in turn to achieve the combination that we want.

But that’s just an artefact of a practical implementation; there are in fact quite a few combinations that we can light truly simultaneously. But how many?

At this point we leave the details of a practical implementation behind, and move into the world of solving a mathematical puzzle just because it’s there.

If we take the 4 pin setup where we have 12 LEDs – there are \(2^{12} = 4,096\) different combinations of lit / unlit LEDs; and if each of our 4 pins has 3 possible values that’s \(3^4=81\) input settings.

If we were to try to draw-up a truth table for the configuration of inputs require to achieve each of the theoretically possible one of the 4,096 outputs we’d very soon run into many combinations that were impossible: you might be forgiven for thinking that there’d be \((n^2-n) – 3^n\) missing rows; but in fact it’s worse than that! One of our 4,096 states is all of the LEDs off – which we can achieve by setting all of our input pins to 0… But we get the same output if we set all of the inputs to 1, or to Z…

So just how many different states are there?

We know the upper-bound is \(3^n\); and there’d be no-point in building it if we couldn’t at very least light up each of the LEDs we’ve put in singly: so the lower-bound is \(n^2-n\)

For a 2-pin system that would give us a maximum of 9, and a minimum of 2: and that’s small enough to draw – so let’s have a look at the truth table. For simplicity I’ll label the input pins A & B; and the LEDs as 1 & 2.

As you can see – here there are just 2 valid states where at least one of the LEDs is on… But if you do the same thing for a 3-pin system (which has 27 rows – so I’ll leave that as an exercise for the reader…) you’ll find that there are 12 states. But how many are there for a 4-pin system, or 5-pins, or 8-pins?

Drawing the truth table is impractical – so let’s calculate the answer.

We know that any combination of inputs where there are no 1’s will result in no output, similarly, any state where there are no 0’s will also give no output. So providing that we have a row with at least a single 1, and a single 0 in it we’ll have at least one pin lit in the output. We can ignore the Z states since they’ll only effect which LEDs light – not whether or not they do. This means it’s back to plain-old binary maths to work out the answer.

In a 3-pin table – there are \(2^3 = 8\) states of the input without a 1 in them, and 8 states without a 0. So we’ll start by summing these. \((8+8=16)\); but the case of ZZZ overlaps since it has neither a 1 or a 0 – so we’re double-counting it. Hence there are \((2 \times (2^3))-1 = 15\) states where nothing is lit. We can subtract this from our \(3^3\) possible input states to get \(27-15 = 12\) valid states where at least 1 pin is lit.

More generally we can say that for any system of size \(n\) pins, there will be \(p\) valid combinations of input data: where \(p=3^n-((2 \times (2^n))-1)\); which we can simplify to:

\(p=3^n-2^{n+1}+1\)

There’s no practical benefit to knowing this of course. In our 3-pin example, the 12 states relate to the 6 useful ones (a single LED on); and 6 more where we light only two LEDs at once; which isn’t useful (perhaps unless you’re making Christmas lights?) – but I had a bit of fun working it out! 🙂

Anyway, normal (more practical) service will resume in due course – with the start of an exploration of programming PIC microcontrollers.

---

Filed under: Hardware,Mathematics - @ July 25, 2017 20:47