Topology meets custom keyboard circuit design

Lately I've been reading about ergonomic keyboards, including DIY, spilt keyboards, and custom layouts. I'm currently learning to touch type my own variant of the inverted Hands Down Promethium layout on a pre-assembled Corne spilt keyboard (and on my laptop). I'd like more pinkie stagger, so perhaps I'll design and build my own keyboard - but I don't like soldering, so am drawn to the diode free designs.

The microcontrollers used in most DIY keyboard designs have at least 17 pins available to connect to keyboard switches. In the simplest designs each pin is connected directly to one key switch, which in a split design is enough for a 34 key layout. But what happens if you want more keys than your available GPIO pins, and you don't want to add diodes? Enter topology and the Heawood Graph, 14 vertices (GPIO pins) and 21 edges (key switches).

Direct wiring - diode free

Consider the Sweep, a 34 key split keyboard which was inspired by the Ferris (see below, externally they are much the same). Internally this has a controller in each half with no diodes, and 17 data pins (general-purpose input/output or GPIO) each directly connected to a different switch. In the image I manually traced the ground connections which are always to the inner pin holes. This makes it easier to see the comparatively simple data connections fanning out from the chip - electrically simple, but rather tricky to layout?

Sweep Mini PCB (both sides), with ground traced in red

Sticking with no diodes and direct wiring one key per GPIO pin, for more keys you need a controller with more GPIO pins. For instance, the Piantor uses the Rasyberry Pi Pico or other compatible RP2040 for 18 or 21 keys/half, and the Cantor uses the STM32F401CC blackpill microcontroller for 21 keys/half.

With the right controller, I think you could make a diode-free version of most split keyboard layouts without a number row (like the extended Corne v4 with 23 keys/half), or even some with a number row (like the compact ZSA Voyager with 26 keys/half).

The downsides include laying out the traces, a physically larger controller, and not enough spare pins for other functionality like a track pad, RGB lighting effects, or an OLED screen.

Diode Matrix Design

The standard solution to use more keys than pins uses one diode per switch in a matrix design. This costs slightly more in parts (not a significant issue), but does require far less soldering which is not appealing to me for a DIY project. An example here is the split 34 key Ferris (again 17 keys per half). This uses diodes with a 5 by 4 switch matrix (so could handle 20 keys per half), 5 column traces on the underside of the PCB, and 4 row traces on the top side of the PCB. This needs 5+4=9 GPIO pins. The controller sends a current to a single column (or equivalently row) at a time, in a cycle, and measures which rows are powered (i.e. which switch is closed as the key is pressed).

Ferris Mini v0.2 - both sides of the right half PCB (bottom has column traces, top has row traces)

This approach scans in only one direction, compared to (Japanese) duplex matrix scanning where at each location in the scanning matrix there are two keys with their diodes the opposite ways round. So here rather than a 5 by 4 single scan matrix using 5+4=9 GPIO pins for up to 5×4=20 keys, you could use a 3 by 3 duplex scanned matrix using 3+3=6 GPIO pins for up to 3×3×2=18 keys. There do seem to be some cavaets with ghosting (phantom keypresses) depending on the diode specifications. However, you still need one diode per key - making assembly harder and more error prone.

Heawood Graph Wiring

Now we get to the maths bit! T.G. Marbach came up with a way to use the Heawood graph mathematical structure to create the first split diodeless keyboard requiring fewer pins than keys: Their Heawood42 is a split keyboard where each side uses 14 pins to control 21 keys. Quoting:

The Heawood graph is a graph that is the incidence graph of a projective plane of order 2, and has 14 vertices, 21 edges, and a girth of 6. ... This graph converts to a key matrix with just a 4-key rollover. However, by designing the board specifically, all problematic 5-key and 6-key sequences may be practically eliminated, yielding the Heawood42.

As the numbers suggest, the 14 vertices or nodes are the data pins, and the 21 edges are the key switches. The 14 vertices/pins are split into 7 input and 7 output (acting like a traditional matrix for scanning), letting us label this as a bipartate graph (two node types, drawn here in red and white):

 

This defines a potential 7×7=49 scan-matrix keys, but that would be subject to ghosting without diodes. The Heawood Graph lets us pick out 21 of these scan-matrix entries with minimal ghosting (three diagonal bands of seven; just three keys in any row or column of this 7×7=49 scan-matrix):

	0	1	2	3	4	5	6
0	✅	✅		✅
1		✅	✅		✅
2			✅	✅		✅
3				✅	✅		✅
4	✅				✅	✅
5		✅				✅	✅
6	✅		✅				✅

What would ghosting mean in the graph representation? Any closed loop or chain of distinct edges. The shortest closed loops here are six edges long (known as the girth of the graph), an example is highlighted below in red/blue.

Pressing any of five keys in this chain will create a circuit equivalent to also pressing the sixth key. So there is know way to tell if all six are pressed, or just five - nor even which five! This is a ghosting problem, this design is only unambiguous for 4 keys at once (on either half keyboard), termed 4-key rollover (4 KRO).

T.G. Marbach mitigates this by careful allocation of the chains on the per-finger columns (as not every set of 5 keys is a problem in real usage). There was some good discussion on Reddit r/ErgoMechKeyboards about this graph-approach, spelling out the bipartate graph interpretation (two node types).

More keys?

We can expand the Heawood graph into a family of girth 6 graphs (2n nodes, 3n edges), some of which have names - or a more well known graph with equivalent properties for this usecase. Sometimes there is a better option with more edges, generally the bipartite split is equal giving a square scanning matrix:

Nodes, GPIO	Edges, Keys	Graph notes (all girth 6)
14	21	Heawood graph (wikipedia)
16	24	Moebius Kantor Graph (expanded Heawood; wikipedia)
18	27	9,3 Symmetric Configuration Incidence Graph (expanded Heawood), or Pappus Graph (wikipedia), etc.
18	29	Unnamed Graph (better)
20	30	20 node expanded Heawood graph, or Desargues graph (wikipedia), etc.
21	36	Incidence graph of the affine plane of order 3 (21 nodes, 12 + 9 bipartite split)
22	33	22 node expanded Heawood graph
22	37	Unnamed cage graph, or Unnamed cage graph (better than expanded Heawood)
24	36	24 node expanded Heawood graph, or Nauru graph (wikipedia),  Two-orbit graph, etc.
26	39	26 node expanded Heawood graph
26	52	Incidence graph of the projective plane of order 3, PG(2,3) (better than expanded Heawood, two keys per GPIO)
28	42	28 node expanded Heawood graph, etc.
28	56	JESK graph (better than expanded Heawood, two keys per GPIO)
30	60	Integral Graph, Unnamed graph, Unnamed graph (better than expanded Heawood, two keys per GPIO)
32	67	Unnamed graph, Unnamed cage graph, Unnamed cage graph (better than expanded Heawood, over two keys per GPIO)

T.G. Marbach spotted the better 28 node option for larger monoblock keyboard usage, which they called the JESK graph (28 nodes, 56 edges, girth 6; named after Exoo et al. 2023, also featured in Jajcay et al. 2024, Goedgebeur & Jooken 2024). They used this for the JESK56 (56 keys using 28 GPIO pins with 4-key rollover) keyboard, and based on that, the reJESK (70 keys using 28 GPIO with "good" rollover) keyboard.

Personally I am leaning to a smaller keyboard, which might match the odd one out above - a monoblock keyboard with 36 keys using 21 GPIOs split into 9 rows of 12 columns in a non-square scanning matrix. 

More rollover?

Given the USB keyboard protocol is limited to a 6-key rollover, it would be nice to find graphs with girth 7 (giving 5-key rollover) or even 8 (giving 6-key rollover). The trade-off would be more GPIO pins per key. Some searching including Conder & Nedela (2007) "Symmetric cubic graphs of small girth" turned up some candidates.

There is the Subdivided Cubical Graph, 20 vertices/pins, 24 edges/keys, girth 7 (i.e. 5-key rollover), bipartite, but that is hardly better than directly wiring.

Perhaps the McGee graph (wikipedia), 24 vertices/pins, 36 edges/keys, girth 7? That might work nicely for a minimal monobody keyboard, or very large split keyboards with 5-key rollover... but it is not bipartite. I guess that could still be made to work but would complicate the firmware scanning implementation as pins would need to dynamically switch from inputs to outputs.

Or for medium sized monobody keyboards, the Coxeter Graph (wikipedia), 28 vertices/pins, 42 edges/keys, girth 7 (i.e. 5-key rollover)? That's the same number of pins as the JESK56 keyboard used, but gives up keys for better rollover. But again, not bipartite.

And if you really wanted 6-key rollover, the Tutte 8 Cage (aka Tutte–Coxeter graph), 30 vertices/pins, 45 edges/keys, girth 8, bipartite. Controllers with 30 available GPIO pins using the RP2024 chip (eg Olimex RP2040-PICO30), or even 32 GPIOs using the nRF52840 chip (eg MakerDiary nRF52840 Connect Kit), are available. This seems worth considering.

(There are now also RP2350B based controllers with up to 40 GPIOs, which brings even larger graphs into range - including several with 39 or 40 vertices/pins, 60 edges/keys, girth 8, bipartite.)

Still, the Heawood Graph with just 14 vertices/pins for 21 edges/key and girth 6 or 4-key rollover really is a sweet spot.

Update 2025-06-01

Marbach has just released the MoKa-NP, a 24-key numberpad keyboard with thumb keys using 16 GPIOs via the Moebius Kantor Graph for 4-key rollover as discussed above.