(Sorry for the repost. The first copy went out without the relevant MIME headers, and unfortunately UTF-8 still isn't the default everywhere.)
Based on some discussions with Nick Johnson, I was thinking about a "downloadable tinkerer's tricorder", software that would turn a commodity microcontroller into a powerful LCR meter, and an additional application occurred to me: a keyboard with up to several dozen keys, supporting N-key rollover ("NKRO"), using only two microcontroller pins, one with ADC and the other with digital output, and a couple of dirt-cheap passive components per key, with latency of a few milliseconds. This represents an order-of-magnitude reduction in cost for NKRO keyboards, which are essential for some kinds of video games and for advanced chording input methods. Background: relative cost of different parts -------------------------------------------- Pins on chips are among the most expensive resource in modern circuitry. A small diode, resistor, or capacitor, with no special requirements, will cost between a sixth of a cent and a whole cent (diodes are the expensive items here), but going from an 8-pin chip to a 14-pin chip will cost you at least a dollar; each pin, in effect, costs as much as 20 to 100 resistors! And adding another 8-pin chip will cost you about 50 cents, but at least three of those pins will be tied up with power and communication, costing you ten cents per pin, or more. Pushbutton switches cost nearly 10 cents if you buy them as separate components, but they're cheaper if you make an assembly with many of them built into a single component. As a result, if you dedicate a microcontroller pin to each pushbutton, you nearly double the cost of the pushbutton, and maybe much more if your keyswitches are really cheap. More than one key per pin ------------------------- So, in addition to the standard matrix multiplexing approach, designers occasionally hang several pushbutton switches off one I/O pin on a microcontroller, each controlling a different resistance. Then you can use a voltage divider so that each pushbutton creates a separate voltage, which you can measure with an analog-to-digital converter. It sounds crazy to use an ADC and some resistors to save an I/O pin or two, but the fact is, lots of microcontrollers have one or more ADCs built in already, and you can time-share it between different uses on different pins. So it doesn't cost you anything extra. The most famous design that does this is probably Limor Fried's [Monochron][]. A variant that avoids the need for an analog-to-digital converter is the [PaperTecladoRC][], which charges up a capacitor ("condensador") and then measures its time to discharge to logic zero through the resistor network, rather than making an analog voltage measurement. [Monochron]: http://www.ladyada.net/make/monochron/design.html [PaperTecladoRC]: http://txapuzas.blogspot.com/2010/09/papertecladorc-varios-pulsadores.html (In the standard matrix multiplexing approach, which is how basically all but the most expensive keyboards work on everything from pocket calculators to Macbook Airs, you make an N×M matrix where each keyswitch connects one of the N rows to one of the M columns, and you alternately energize each row to see which columns get energized. You can get two-key rollover with this approach, but not NKRO, and you still need a substantial number of I/O pins, typically around 20.) Trellis-coding your keys to get N-key rollover on a huge number of keys ----------------------------------------------------------------------- It occurred to me that you can do much better than this. Rather than merely discriminating between different *resistances* attached to each button, you could discriminate between different *complex impedances*: connect each button through not only a resistor but also a capacitor. Now we can subject the pin to a time-varying signal, such as a transient pulse, and watch its response. To consider one possible concrete realization of this approach, consider this layout: GPIO __/\ /\ ____/___/\ /\R1___GND \/ \/ | S1 | \/ \/ R0 | | | |___||_______GND ADC ____________| || | S2 C1 |__/__... Your GPIO pin, a switchable voltage source, connects through a resistor R0 to a common bus to which all the pushbuttons connect. Your ADC is also connected to this common bus. Each pushbutton Si connects the bus to a resistor Ri and a capacitor Ci, each of which is grounded on the other side; that is to say, they're in parallel. This is more or less the configuration of a *single* AVR I/O pin in input mode: you can either connect the pullup resistor R0, which is an imprecise and nonlinear resistance in the 20kΩ–50kΩ to VCC, or leave it in a high-impedance mode where it won't source or sink more than a few microamps. However, it's convenient to us to use *two* pins, both because it lets us use a higher-resistance pullup resistor and correspondingly lower-capacitance capacitors, and because it makes our pullup resistor much more precise. Suppose one of the pushbutton switches S1..SN is pressed; let's say S1. Now, if we bring the pullup high, the voltage measured by the ADC will rise eventually to VCC R1/(R0+R1). If the various Ri are sufficiently different, we can use the ADC to distinguish which of them it was. Indeed, if they're sufficiently different that the sum of each subset of their conductances is sufficiently different to be distinguished by the ADC, we can distinguish *any subset* of them, which is to say that our keyboard has "N-Key Rollover", or NKRO, an advanced gaming keyboard selling point. (According to the documentation for Plover, a Stenotype input method that can get 250 words per minute on a regular NKRO keyboard, you can't find a full-size NKRO keyboard for less than US$50.) If you have a 10-bit ADC, you could conceivably distinguish 1023 different keys merely by their resistances by this method, but you can't distinguish more than 10 of them if you want to be able to distinguish all of the possible chords (that is, get NKRO). Also, your resistances need to really be distinct, which is difficult: we're talking about 1023 different resistances, with better than 0.1% tolerances here for the highest resistances, which is hard to find. (From browsing Digi-key, it seems like regular sixth-of-a-cent resistors these days are ±1%; regular antediluvian resistors are ±20%; ±0.5% resistors cost half a cent; the resistance of the same resistor normally varies by more than 0.1% with temperature.) Worse, the resistances need to be precisely aligned with the bit transitions of the ADC, and the top one needs to have 1022 times higher resistance than the pullup. So in practice I think you'd be lucky to distinguish 8 different keys on resistance alone with NKRO unless you trim each resistor after assembly. But that's what the capacitances are for! If you have two different keys with the same resistance to ground, but different capacitances, they'll both eventually arrive at the same steady-state voltage — but they'll take different amounts of time to get there. Better yet, you can measure the charging speed with greater precision than you can the final voltage, and taking multiple measurements as the capacitor charges can give you better than 10 bits of precision by averaging over time. (In effect, you're using trellis-coding: the complex impedances of each key at a given arbitrary frequency are a sort of exponentially distributed lattice in one quadrant of the complex plane. Although we're actually adding the *reciprocals* of the impedances (we're adding the complex analogues of conductance; maybe there's a word for this), those are also exponentially distributed such that every subset of them has a unique complex sum, and all of these complex sums are far enough apart that we can distinguish them despite measurement error.) Suppose tracing the curve over time gives us 12 bits of precision on the resistance (by averaging 16 samples) and 12 bits of precision on the RC time constant. Intuitively I think it should be easy, then, to distinguish 6 different resistances and 9 different capacitances, for a total of 54 keys with NKRO, on a single ADC pin! To be slightly more precise, we probably want the largest resistance value to be somewhat larger than the pullup resistor value. Suppose we choose 220kΩ for our pullup. We want the smallest resistance value to be less than the error in the largest; and we want all the sums of resistance values to differ by more than the sums of their errors. This suggests using resistances of 500kΩ, 220kΩ, 100kΩ, 50kΩ, 22kΩ, and 10kΩ; if they, improbably, all had an error of 1%, that would be 5kΩ+2.2kΩ+1kΩ+500Ω+220Ω+100Ω = 9020Ω, which is less than 1kΩ. A seven-bit ADC measurement would probably be enough to distinguish between them, and 10 bits definitely will. IIRC, experiments have shown that the nominally 10-bit successive-approximation ADC on the ATMega328 and friends can still give you an effective number of bits ("ENOB") of 7 at about 1Msps, which is to say a microsecond per measurement. In the "worst case", you'd need about 11 bits' worth, which I think is about 600 microseconds (four successive measurements) on the ATMegas. (I'm a little fuzzy on the exact ADC numbers, unfortunately, but I think they may actually be significantly better than the above.) Then we need to do the same trick for the capacitors. The smallest capacitance we can reasonably measure will be one that charges fully through the pullup in a single 600-μs measurement, so the RC time constant should be around, I don't know, 50μs. If the pullup is 220kΩ, that puts it at 227pF (say 220pF for practicality). Then you could use nine capacitances of 220pF, 470pF, 1000pF; 2200pF, 4700pF, 10000pF; and .022μF, .047μF, and 0.1μF. The slowest RC constant, then, should be 0.1μF × 220kΩ, or 22 milliseconds. But since you're using an ADC, you don't need to wait for the capacitor to charge fully, just enough that you can accurately measure its rate of charging — say, ten samples or ten out of 1024 ADC counts, whichever is faster. In the worst case, the 0.1μF capacitor will be in parallel with a 10kΩ resistor, which means its final charged voltage would be 10/(220+10) of the 1023-count max: 45 counts. Charging 10/45 of the way will then take 1.25 time constants, or 28 milliseconds. That's only marginally acceptable, so it's probably worthwhile to blacklist the one, three, or six slowest combinations. The two next-worst are 0.1μF in parallel with a 22kΩ resistor, which will have the same RC constant, but the final voltage is almost twice as high, so you'll rise by 10 counts in only 14 milliseconds; and 0.047μF in parallel with 10kΩ, which will have less than half the RC time constant and the same asymptotic voltage, so will also need only 13 milliseconds. The next three worst are 0.1μF with 47kΩ, .047μF with 22kΩ, and .022μF with 10kΩ, all of which need about 7ms. So if you eliminate these six keys, you can measure any keychord in under 4ms. (Another way to improve this: on the AVRs, there's the possibility of using an internal 1.1V bandgap voltage reference instead of VCC. At a typical 5 volts, this will increase the precision of the measurement of this initial voltage rise by a factor of almost five, and thus decrease that 28ms to some 6ms.) So that gives you a 48-key NKRO keyboard with worst-case 4ms latency for the cost of two microcontroller pins (20¢), 49 1% resistors of six values (10¢), 48 1% ceramic capacitors of nine values (25¢†), and 48 keyswitches (480¢ if discrete, much less if made as one piece, much more if you use Cherry high-end mechanical keyswitches) for a total of some US$5.35, or US$0.55 as the cost of the keyswitches themselves approaches zero. This is an order of magnitude cheaper than the US$50 cost of existing NKRO keyboards, or two orders of magnitude cheaper if the keyswitches are free. † I'm actually having a hard time finding cheap capacitors with reasonably precise capacitances. This could limit the effectiveness of the idea. Information theory shows it won't work quite that well ------------------------------------------------------ There's some kind of problem with my calculations, though. You need 48 bits of entropy to get NKRO on a 48-key keyboard. If you have an estimate of the RC time constant with a precision of 50μs with an upper limit of 3ms, as I've postulated above, that's almost 6 bits of entropy. That, combined with a 12-bit measurement of voltage at some known point in the charging curve (the result of averaging some 16 samples) gives you 18 bits. That's less than half of what you need. In the absence of nonlinear components such as diodes, those two parameters will be able to predict any further measurements down to the limit of measurement noise. So at best you can get 18-key rollover — and that's ignoring that many of the combinations of final voltage and RC time constant are outside of the feasible region! In practice, I think that given 18 bits of data like that, you can probably identify a unique RC time constant and asymptotic voltage for each key, even if the nominal values of the resistors and capacitors were equal. (Precision of ±1% steals the top 6 bits of each parameter, leaving 6; using lower-quality, more-variable components would help by adding more randomness.) If you train the microcontroller for a given keyboard, storing calibration constants for each key and then adjusting them with a linear correction for an estimated temperature (assumed to be constant across the keyboard), you could probably reliably distinguish several thousand keys — but without NKRO. Ways to improve performance --------------------------- If the problem is that we only get 18 bits of entropy and we need 48, here are some approaches. The most glaring problem is that we need at least 9 bits of precision on the capacitance measurement, but our hypothesis above is that we're only getting about 6 bits of RC time constant, which represents the contribution of C. Maybe my calculation is off: maybe from a series of 10-bit voltage measurements, even over only a maximum of some 60 sample times, we can extract some 9, 10, or even 11 bits of precision for RC. Maybe use a least-squares fit in some kind of transformed space. But that only gets us to, like, 23 bits, when we need 48! We need more entropy! (Even an ADM-3A had 59 keys.) Unless we just want a Stenotype, which has exactly 23 keys. A second approach, as mentioned earlier, is to incorporate nonlinearity. For example, if you add a diode somewhere in the network for each switch, your RC time constant changes with voltage, according to the diode's characteristics. This might provide another 12 bits of entropy, if you have diodes with enough variability whose voltage drop is comparable to that of the resistor at comparable currents. By itself, that could get us to maybe 30 bits, at a cost of another 24¢ at half a cent per each of 48 keys. A third approach is to use another ADC pin and pullup resistor from the same GPIO pin, giving you, in essence, a second separate keyboard, at a cost of some 10¢. This approach scales linearly to as many ADC pins as you have available on your microcontroller, at some cost to sampling rate per pin and therefore necessitating somewhat larger capacitors. If this is the only approach you take to improve performance over the basic approach, so that you can only handle about 18 keys per ADC pin, then one GPIO pin and three ADC pins (40¢ of pins) should get you to 54 keys, or maybe a bit more if you push it. That's enough for a full compact keyboard, at a cost of 75¢ (55¢ - 20¢ + 40¢) of electronics, plus the keyswitches. If we combined all three of the above approaches, you'd be getting 35 bits on each of three input pins, for 105 bits in all: enough for a full keyboard with keypad, at a cost of, I don't know, a dollar or two of electronics, plus the keyswitches. However, there's also a solution that works with *no extra hardware*! Since we're able to scan the entire keyboard at 250Hz, it's really completely unnecessary to consider all possible new keyboard states as equally likely. An actual human being won't be able to press and release more than one or two keys in any 4ms interval. So of all the candidate new keyboard states, we can take the one with the smallest hamming distance from the current keyboard state, and we'll essentially always be correct. (That insight is from reading posts by Talkingjazz about their rotary switch decoding problem: <http://www.arduino.cc/forum/index.php/topic,20125.0.html>.) Yeah, or use a shift register like a normal person -------------------------------------------------- You could use a ten-cent 74HC165 shift registers and eight pullup resistors for each set of eight keyswitches, and chain them all together in a long line feeding into one pin on your microcontroller. You need two more microcontroller pins to clock the shift registers and to enable them. Cost for 48 keys: 30¢ for the microcontroller pins, 60¢ for the shift registers, 24¢ for the pullup resistors, total of US$1.14, plus the keyswitches themselves. This is maybe more expensive than the trellis-coding approach, but it sure is a lot simpler. -- To unsubscribe: http://lists.canonical.org/mailman/listinfo/kragen-tol