Wednesday, 5 December 2012

Bit-shifting. Shift over.

As part of our word clock made from two 8x8 LED matrix modules, we're trying to work out a way of quickly lighting up columns of 8 LEDs at a time.


Here's how it works: we set (and unset) any number of 8 different pins (connected to the "rows" line). Then we pull one of the 16 columns low, leaving the other column pins high, thus lighting up to eight LEDs in a single column. After a short delay, we then change the eight "row" pins and move along to the next column.

One way of achieving this is to have one single byte variable for the rows data, and a two byte (16-bit) variable for the columns data. If we start by lighting the first column, the two byte variable value would be 0111-1111-1111-1111 (in binary). After changing the row data, we need to make the two-byte variable value 1011-1111-1111-1111

In short, we need to make the zero value "move along" one space to the right.
A really easy way to do this is bit shifting.

We're going to simplify things (although not immediately obvious) by bit-shifting the (binary) value 1000-0000-0000-0000 one place to the right, then sending the inverse value to the column pins (so every 1 becomes a zero and every 0 becomes a one).

The reason for this is because bit-shifting isn't necessarily "circular". When a bit "drops off the end" it doesn't necessarily appear back at the start of the value. Consider a simpler example, the number 0110.
If we bit-shift one place to the right, the number becomes 0011. But if we bit-shift one more place to the right, the number becomes 0001. The trailing one has "dropped off the end" and disappeared - it doesn't appear back at the start of the value.

If we had the initial value 01111111 etc. and bit-shift one place to the right, we end up with 00111111 and not 10111111 (which is what we need). Whereas taking the value 10000000 and bit-shifting one place to the right gives us 01000000 which - when inverted - gives us the value we're after.

Right, that's that cleared up.
First we declare our variable:

unsigned short colData;  (SourceBoost)
Dim colData As Word (Oshonsoft)


Why unsigned rather than signed?
A two-byte signed value is simply a 15-bit value and the very first (leading) bit determines whether the value is positive (leading bit zero) or negative (leading bit one). If we used signed values, the leading bit would need to be toggled from zero to one depending on the position of the zero in the rest of the string. This is more hassle than just inverting an unsigned value (where the leading bit actually makes up part of the value represented by the binary pattern).

Then give our variable an initial value
colData=0x8000;
or
colData=32768;

The hex value 0x8000 is the same as binary value 1000-0000-0000-0000
Now when we need to move onto the next column, we bit-shift the colData value one place to the right:

colData = colData >> 1

This means that the value now becomes 0100-0000-0000-0000
And bit-shifting again:

colData = colData >> 1

returns the value 0010-0000-0000-0000
And so on and son on.

When the column is all the way over to the right, 0000-0000-0000-0001, and we bit-shift once more, we end up with 0000-0000-0000-0000 whereas we want the one to wrap around to the start again.
A simple if statement takes care of this:

If colData = 0 Then colData = 32768 (Oshonsoft)
if (colData==0){ colData = 0x8000;} (Sourceboost)

But as we've already stated, our colData is inverted to what we actually want. We don't want to pull 15 of the 16 columns low, we want only one column low at any one time. So we need to invert the value in the colData variable and put this value onto the output port(s):

tmp = colData XOR 0xFFFF

XOR is an exclusive OR statement:


If either of the bit patterns BUT NOT BOTH are one, the result is a one, otherwise it's zero. So simply XOR-ing our colData value with a load of ones 0xFFFF is binary 1111-1111-1111-1111 inverts the value, turning all the ones to zeros and all the zeros to ones.

Now we put the first (most significant) byte of the two byte variable onto PORTB and the second (least significant) onto PORTD:

Oshonsoft
Dim H As Byte
Dim L as Byte
H = colData.HB
L = colData.LB
PORTB = H
PORTD = L



SourceBoost
unsigned short b;
b=colData;
PORTD=b;  // only the lower 8-bits are put onto the output pins
b = b >> 8;  // move the upper 8-bits eight places to the right
PORTB=b;


The end result is that only one pin is pulled low at any one time.
Every time we use the bit-shift operator, the low pin "moves along" one place to the right, effectively lighting up the next column of LEDs in our matrix.

Heres's a quick guide to bit-shifting and unsigned/signed variables:
http://stackoverflow.com/questions/141525/absolute-beginners-guide-to-bit-shifting