Monthly Archives: February 2010

Arduino Adventures :: Day 5

As I stated last time, I had decided to try out Charlieplexing as a way of individually addressing 64 LEDs with only 14 I/O pins (9 is all I need for this actually). So I ordered some resistors and some very specific LEDs. Before I get into the build, let me give a high level overview of what Charlieplexing is and how it works, so that you can understand the conclusions I came to later.

Charlieplexing was invented in 1995 by Charlie Allen as a way of driving many LEDs with few I/O pins and nothing but resistors to implement it. It relies on two facts about LEDs:

  1. That they are diodes, thus electricity will only flow through them in one direction
  2. That they have a specific “operating voltage”, below which they will not light up even if current is flowing through them

( Instructables has a really great in-depth explanation here. )

Simply put, you hook LEDs up in combinations such that electricity will either not flow through certain LEDs due to the fact they are diodes in the wrong direction, or that electricity will flow through ones you don’t want to light up, but not enough current to actually light them:

When all is said and done, only one LED will light up at a time. Thus, individual addressing:

Now the more astute reader may have noticed I just glossed over something. Yes I can turn individual LEDs on by themselves, but as is dictated by the circuit, I can not turn on all the LEDs at once, in fact not even a third of them, and in practice, you can actually only turn one LED on at a time using this method, which sounds pretty limiting. But there is a way around it: Persistence of Vision.

I’m sure you’ve seen it used some where before but not known it. The idea is if you can turn a light on and off fast enough, the human eye won’t be able to perceive that it was ever actually off, and thus it will look like it is always on. So to make this useful, you “schedule” all the lights that you want to be on, and then the software scans through and turns each one on and off in succession, when it gets to the end, it starts over. You have to be able to scan through the lights enough times per second to fake out the human eye:

So with all that, I set forth to implement a prototype on my breadboard, and have a video of it here (it look a long time to make, not because it’s long, but because I suck with the video editing software, so give it a watch πŸ˜€ ).

Now this whole research and prototype cycle allowed me to draw some important conclusions. And they aren’t favorable for Charlieplexing πŸ˜›

There are some small issues that make this method problematic for my application.

The circuit layout does not lend itself to have the LEDs in a grid. It could be designed around, but would be a real pain. This isn’t a big one, but it’s certainly a consideration.

As the circuit expands with more pins, and you want to have more LEDs on at once, I found the LEDs got dimmer. This could be for one of two reasons (or both). It could be the fact that the circuit itself is larger and has more resistance built into it over all (and the current is being split many different ways), and the more LEDs are scheduled to be on, the longer each LED will be off for during a given “scan”. Now you can counteract this, by using lower ohm resistors to increase the overall current in the circuit, but then you run into the issue of the “compliment drive” LEDs lighting up dimly when they shouldn’t.
And that last issue is a problem I ran into even in my small circuit.

So where does this leave me!

Well it leaves me out in the cold as far as Charlieplexing is concerned.

But I got to thinking… my original idea of using demultiplexers could still work, so that’s where I am at, I have a few ideas I’m going to explore on paper, and I’ll post when I have something concrete.

Arduino Adventures :: Day 4

So I’ve been thinking about what I want my first big project to be, tossing around a lot of ideas. Trying to balance complexity & difficulty VS coolness. (Also, I want the project to be fun to make!) One of the things I’ve been interested in doing ever since I heard that you could do it at home, was acid etching your own circuit boards, so I wanted that to be a part of the project too.

With those requirements in mind, I finally settled on a project: John Conway’s Game of Life. I’ve written two different versions of it in software previously:

I am absolutely fascinated by the whole thing. At one point I was in the planning stages of a hardware based version using only logic gates. But the complexity was astronomical, I would have ended up building an ENIAC sized machine πŸ˜›

But now with a micro-controller to do all the heavy lifting, it’s feasible! With that as my goal, I began planning and research in earnest. So what do I need. Well all I really need is a way to display a grid. There are some LCD screens you can buy and hook up, but thats no fun, and doesn’t look very cool. So I began looking into LEDs.

Now, in the software version I wrote, the longer a cell had been alive, the more it’s color would change. So I wanted multi-color LEDs that I could modulate the color on. The plan was to have a grid of NxN multi-color LEDs. But after thinking things through a little, I decided I had enough issues to deal with anyway, without adding in the whole analog aspect, so I opted for digital (one color, on or off) LEDs.

My next step was to prototype. I needed to determine what the value of N would be. This would determine a lot about the circuit complexity and how I would go about implementing things. Now in the theory behind the Game of Life, the grid is infinite, there for the larger your actual grid is, the more interesting the result will be. So size is key.

The grid in my software version is 64×64. But after looking at things from a hardware perspective I figured roughly 8×8 was the largest I could manager. So I tweaked my software to be 8×8 to see if it was still interesting. It wasn’t…

Until I wrapped the world that is! (So each edge is connected to each other edge.) Satisfied that it could still be interesting at 8×8 as long as the edges wrapped to each other, it was time to start thinking seriously about how I was going to implement this in hardware.

The key here, is I need to be able to individually address each LED. An 8×8 grid means 64 individually addressable LEDs, but the Arduino only has 14 digital I/O pins! (and even less analog I/O pins.) So the question became: “How to drive 64 LEDs with only 14 digital I/O pins?”

The first thing that jumped into my head was multiplexing (well, demultiplexing to be accurate). But that meant researching and ordering ICs, and during some research on the interwebs I found a possible alternative called “Charlieplexing”. No ICs were required, just a few current limiting resistors. It allowed you to address N(N-1) LEDs where N is the number of I/O pins. Thus with only 14 pins, I could address 182 LEDs! (Plus the circuit looks fun to design)

So I ordered parts for that: 100 red LEDs and some 68 and 82 Ohm resistors (I’ll get into why that is later) and I will write up another entry on that build soon πŸ™‚
(Probably do a video too, I’m still exploring video editing software, trying to figure it all out.)

DIY Capacitive Touch Gloves, Take that Apple patent #20090000010

So a small diversion from my Arduino efforts today, and a focus on warm winter apparel.

I bought a Motorola Droid when it came out last year and haven’t looked back to my LG 77C (the C is for crap) or what ever it’s stupid model was.

But now that winter is firmly upon us, grinding us down ’till the last breath of hope and life escapes from our frigid, sun starved bodies, as nothing more then a fart in the arctic wind… I got to thinking:

“Boy my hands are cold, wish I could answer phone calls with out having to take my gloves off.”

So I began testing a few materials around my house, trying to find something non-abrasive that would create some capacitance on the screen (since they are capacitive touch screens). Nothing worked, not well anyway, so I tried tinfoil which worked of course, but covered it with some thin plastic, as to protect the screen, and it worked!

So without further ado, I give you the DIY Capacitive Touch Glove, or as I like to call it, “The one glove to rule them all”:

Arduino Adventures :: Day 3

It’s time to do my first actual Arduino project!

This is a very simple one, but taught me some very important lessons about physical computing. Modern computers do tons of things so that we as programmers don’t have to worry about all the random chaos in the real world. But in physical computing, small micro-controllers like the Arduino don’t have the complexity to handle these things, so we as the designers/programmers must handle them our selves.

Take a look and see what I mean:

[I also took this as an opportunity to try making a real video about it. Still learning the best ways to record it all, and splice it together, so some parts of this are rough.]

Arduino Adventures :: Day 2

After talking with a few people who saw Day 1’s pictures, I tried a different technique, and it worked so well I didn’t get a single Cold Solder, and finished the entire board in the time it took me to do just 10 pins last night!

The finished product!

Those are some nice solder joints!

Plugged in for the first time, and Win7 found the drivers w\o any help, I’m kinda impressed!

Running my first program! (it just toggles 1 of the digital outputs High (5V) and then Low (0V)) and I hooked up an LED so it would look pretty while doing it:

I disected an old XBox controller and extracted the 2 rumble motors. Then I hooked the larger of the 2 up to the digital output that my program is toggling:

Now I am going to run through some of the tutorials and stuff to learn all the little ins and outs of programming this thing, and then I can start coming up with some cool projects!

Arduino Adventures :: Day 1

The encryption is coming along very well. All the key generation, and calculation and actual encryption/decryption is 100% done and working, and I have over come most of the hurdles in rendering it all. But as my project A.D.D. dictates, I’m taking a break for a little bit, to do some electronics stuff…

I’ve had an interest in electronics projects ever since I was little when I had one of those 300 in 1 Electronic Projects kits:

In recent years I’ve had a real hankering to get back into it and do a hardware project, but for one reason or another, all of my ideas for projects had some fatal flaw (cost, complexity, time, ect…) and none of them have ever gotten off the ground.

Thats why when I found the Arduino, I jumped at it, not even having a particular project in mind. It was a cheap micro-controller (about $30), both simple to assemble and use. Yet it had a huge open source community that produced tons of add-ons, so it was flexible.

I ended up spending about $80 to get the micro-controller, plus a book, wires, resistors, LEDs, Bread Board, and a few other odds and ends in this bundle which I can’t recommend enough.

Now I had never actually soldered before (except for that one time in 8th grade when I tried to mod my Playstation. It didn’t go well…) so I had to buy a Soldering Iron as well.

Now with everything I needed, I set to building the Arduino. All the hard, very tiny parts are already on, but there is still some assembly required πŸ˜‰

I only soldered 10 pins tonight. A few of them came out ok, but many are Cold Solders:

Silly Encryption Schemes: Part 1

[ This post is a bit long, sorry about that πŸ˜€ ]

[ I’m more accustom to writing for less technical audiences, so if this comes across as too much hand holding, I apologize, I’ll try to tech it up moreΒ Β in the future πŸ˜‰ ]

So I have had an interest in Cryptography for a while. Now let me stop you right there, no, I’m not a crazy math genius, so I’m not going to regale you with formulas and number theory. No my interest is more… playful.

My first ever Cryptography related thing I wrote some years back was a super simple cipher tool. My girl friend at the time was giving me notes in a cipher she created (it was a straight forward, 1 for 1, substitution cipher), so I wrote a program to decode them more quickly. I then expanded the program to some other simple ciphers.

Later I wrote a simple XOR encryption program, and also a steganography program which can hide ASCII text in 24bit Bitmap images. (Both projects can be seen here)

Finally I wrote a web based cryptography game called Decrypt that teaches people how to decode ciphers by hand while unveiling a story to them. (Though as browsers have changed and improved, it has falling into a bit of disrepair, though it is still playable I believe.)

Fast forward to a few months ago:

I have been milling around on cryptography sites again, pretending to understand what I’m reading. I can’t see the day when my pseudo understanding of asymmetrical encryption will pay off, but hey, you never know πŸ˜‰

So with thoughts of lovely encryption algorithms dancing in my head, I turned to another topic I had been mulling about, it had to do with some 3D math I had abandoned in another project: Calculating the intersection points of 3D Spheres (It’s not redundant, look up 4D Spheres, AKA: Quaternions). This oddly enough lead me to a silly idea for an encryption key generation scheme: Distributed Planar Key Encryption

( Or at least that’s what I’m calling it. I don’t know if it’s something that has been done before.Β Β It’s kinda pointless, but cool πŸ˜› )

Let me stop right there, I’ll come back to the math in a moment. So the idea for this encryption scheme came (as many ideas of mine do) from the movies. You’ve seen those movies where a super important vault, or missile launch system, or whatever has multiple key holes, and both keys must be inserted at the same time to be able to unlock it? It prevents any single person from misusing their key, as multiple people are required to agree on accessing it.

Well maybe it’s just me, but I think that’s kinda cool πŸ˜›

Ok so back to Distributed Planar Key Encryption, that’s exactly what this scheme aims to be. You see, several Child Keys will be generated at encryption time. These keys, Child Keys, will combine to form the single unique Parent Key which is the actual encryption key. That of course will be used to encrypt the data.

Then the encrypted data can be sent to each concerned party along with a single Child Key. Or the encrypted data can be kept in a single place, whatever, that’s not the point. The point is that no single user can decrypt the data with their given key. They must bring together enough keys to pass the Key Threshold. Once that Threshold is passed, the Parent Key can be generated, and the data can be decrypted.

The important part is that ANY combination of Child Keys, as long as you have enough of them, can generate the Parent Key. So you can’t just take the Parent key and break it up into pieces. If you did that, you would have to have specific Child Keys in order to reconstruct the Parent Key. It would also mean that given one Child Key you could begin to solve for the other Child Keys. Needless to say, this would be a bad thing…

OHKAY… So. How do you go about making a scheme that satisfies these requirements! Actually it’s a lot easier than you’d think. And this is where we come back to the 3D Spheres I mentioned earlier. Given 4 unique Spheres (they ALL must overlap) you can calculate a single unique point in 3D space where they all intersect. And use that point as the basis for your encryption key (aka: the Parent Key).

So this was my first attempt at a Distributed Key Encryption Scheme, dubbed: Distributed Spherical Key Encryption

But there were some problems. The first was that the math to intersect Spheres is quite complicated. Though I got that working finally. The next problem is what killed it however. See, on the surface of a sphere, there are, in theory, an infinite number of points, because 1.3 is a different number then 1.33, and so on. (Of course, a computer is a finite machine, so it’s not quite infinite, but still pretty good.) The problem came in how modern computers store decimal (aka: rational) numbers.

They are called “Floating Point” numbers, and computers actually suck at storing them exactly. You can read up more on why that is on Wikipedia if it really interests you. But here is why it’s a problem: when I run these complicated equations to calculate the point of intersection, I get slightly different numbers every time. That is to be expected with Floating Point arithmetic. And we, as computer scientists, have ways of dealing with it. Generally, we look at two numbers that we want to compare, and if the difference between them is under some threshold (epsilon) then we consider them to be the same number.

So the difference between 1.45555 and 1.45556 is less then the threshold of 0.001, we would consider them the same number. I’m pulling these numbers out of you know where, in reality epsilon (aka: 0.001) is much much smaller, but you get the idea.

So it should have worked, right? Wrong. See, the equations are complicated enough, and each time a floating point operation is done (+, -, *, /) there is a slight bit of error. Since so many operations are done in the course of determining the point of intersection, all the different errors add up to quite significant fractions so that the epsilon test would fail ~9 out of 10 times, making it quite unreliable.

What this means is… Given however many Child keys, 9 out of 10 times, you would NOT generate the proper Parent Key. And the Decryption of the data would fail.

My only option was either to round off to, at MOST two decimals, or to use fixed point math and drop decimals all together (sort of).

Neither solution was preferable. The first one, would probably make it reliable to 99 in 100, but that 1 in 100 times when your secret data didn’t decrypt, wouldn’t be a happy day.

The latter method can be refereed to as “Discretizing” the math. Or, making the math use Discrete numbers. The problem with this is that, instead of having theoretically INFINITE points of intersection on the surface of your sphere, you now had a discrete, known number of possible points. Now remember, the point of intersection of 4 Child Keys IS the Parent Key. Thus, the complete Parent Key actually and truly exists on the surface of every single Child Key sphere.

When there were an infinite number of points of the surface of each child, it didn’t matter. But now, by making the numbers discrete, there are a known number of points on each sphere. Thus, given a single Child Key you could brute force through the points on that Sphere alone, and find the Parent Key.

(While there are ways to mitigate this [using particularly massive spheres], it actually reduces the search space in other ways, but that’s for another article.)

Just to reiterate, one of the key points of this encryption scheme is to not be able to determine the Parent Key with any fewer then N Child Keys. N being the Key Threshold as defined by the algorithm.

So this was clearly not an acceptable solution as it violated one of the core tenants of the encryption scheme.

(As a side note. The spherical keys were flawed from the start. See, N (the Key Threshold) for the algorithm was 4. You need 4 spheres to generate a completely unique point. But given just 3 spheres, you can in fact generate exactly 2 unique points. Well you don’t need a computer scientist to tell you that brute forcing 2 possible solutions won’t take you very long… Thus with only 3 of the 4 required Child Keys, the Parent Key could easily be deduced.)

Quite a bit discouraged, I stepped back from it and had some dinner. And it struck me. I was only fixated on using Spheres because it was what I had been working with previously in an unrelated project. And that in fact, as I just mentioned, they are quite poorly suited to the task anyway.

3D Planes however are perfect!

For those who forgot their highscool geometry:
3 Dimensional Plane: A theoretical surface which has infinite width and length, zero thickness, and zero curvature.

  • Planes have a theoretically infinite surface area, thus they don’t suffer the same problems from using discrete, fixed point math
  • Planar intersection testing is much simpler then Spherical intersection testing.
  • It only required 3 planes to determine a unique point of intersection (Thus the Key Threshold is one less then for Spheres)
  • Given 2 keys (AKA Planes) an entire line of intersection results with theoretically, infinite points on it, even with discrete math, the security of the algorithm doesn’t degrade as you approach but do not meet the key threshold.

So while 3 keys are the minimum that must be generated, you can generate any number you wish that all intersect at a single unique point, and any 3 keys can be intersected to unlock the Parent Key.

This was exactly what I had been searching for. So I began coding in earnest. (It also occurred to me, that a Linear Key system could work as well, reducing the number of Child Keys required down to 2. But I stuck with the Planar Keys.)

Now. That’s all well and good. Mission accomplished and all that. (No really!) But encryption can be a very boring subject to many people. And it sure doesn’t look as cool as it does in the movies, crazy blocks flying every which way to unlock the secret file. Which got me thinking. I am actually using 3D constructs in the math, so there really is no reason I couldn’t visualize this in a 3D app. Ya know, actually show the different planes (keys) in a 3D view, and show them intersecting, and then highlight the common intersection point. I could even do a little animation with it to make it snazzier.

So that’s what I’m currently working on, and I will be sure to post here about it when it’s done!