ダイオードなしキーボードで可能な「3キー同時押し」を最大化する

TL;DR

こちらの記事の追加情報。ダイオードなしキーボードでは「キーマトリクス上の長方形の頂点のうち3点を押す組み合わせ」は一律で禁止されがちである。これは「ゴーストキー」の発生を防ぐためである。しかし、実はその長方形の4点目にキーが物理的に存在しない場合は曖昧さが生じないため、3キー同時押しを認めることが出来る。ku1255-firmware-modifierのv0.9.0以降のバージョンでは、これを明示的に扱うことで、有効な3キー同時押しの数を公式ファームウェアと比較して大幅に増加させた。

前提1: キーボードはどうやってキー押下を検出しているか

多くのキーボードでは、各キーがスイッチとなっており、下図のように行（Column）× 列（Row） の格子状に配線されている（キーマトリクス）。この時、どの行とどの列との間で導通が生じるかによって、どのキーが押されたかを判定することが出来る。

たとえば上の図の場合、row 1とcolumn 1との間に導通が生じることで、「Aキー」が押されたと判定出来る。同様に、もしrow 1とcolumn 1, row 2とcolumn 1との間に導通が生じるなら、「Aキー」と「Bキー」との間に導通が生じることが分かる。

前提2: 「3キー同時押し」が出来ない組み合わせの存在

2キー同時押しまでなら、前項の方法で問題は生じない。しかし、3キー以上になると問題が現れ始める。たとえば、下の図は「A」「B」「C」の3キーを押した状態の図である。row 1 - column 1 (A), row 1 - column 2 (B), row 2 - column 1 (C)の間に導通が生じるまでは良いのだが、実はrow 2 - column 2 (D)の間にも導通が生じてしまう。

これは、矢印で示したようにA, B, Cスイッチを介して「回り込み電流」の導通経路が繋がってしまうためである。したがって、実際には押していない「D」キーが、あたかも押されているかのように判定されてしまう。これをゴーストキー（ghost key）という

この「回り込み電流」を防ぐには、各キースイッチ部分ひとつひとつに整流用のダイオードを取り付ければ良い。いわゆる「Nキーロールオーバー」という謳い文句がついている製品はそのような設計になっている。特に同時押しが重要になるゲーミングキーボードの分野に多い。ただしその分生産コストは増大する。

一般の事務用キーボードではそれほど同時押しが重要でないため、単に「キーマトリクス上の長方形の頂点」を占有する形での3キー同時押しを認めないことで、ゴーストキーの発生を防いでいる（たとえば上図「A」「B」「C」のような位置関係）。逆に言えば、キーマトリクス上で同一矩形の頂点に位置する3キーは同時押し出来ない。私が知る限りでは、ほぼ全ての一般のキーボードのファームウェアはこのような設計になっている。

キーマトリクスにおける空隙の利用

ここで、実際のキーマトリクスを見てみよう。下表はLenovo Lenovo ThinkPad Compact USB キーボード with トラックポイント（モデル名: KU-1255）の例だが、一般的なキーボードのキーマトリクスは似たり寄ったりなことが多い（ロジクール系を除く）。

	0	1	2	3	4	5	6	7
00	UP	(none)	(none)	END	FN	PAUSE	LEFT	KP_MEMSTORE
01	(none)	HOME	(none)	F11	(none)	(none)	DOWN	(none)
02	F5	F9	INTERNATIONAL3	F10	BACKSLASH	RETURN	SPACE	BACKSPACE
03	(none)	DELETE	(none)	INSERT	PRINTSCREEN	PAGEUP	PAGEDOWN	(none)
04	F4	F2	E	3	D	C	(none)	F3
05	H	6	U	7	J	M	N	Y
06	ESCAPE	GRAVE	Q	1	A	Z	INTERNATIONAL5	TAB
07	(none)	(none)	(none)	(none)	(none)	RSHIFT	(none)	LSHIFT
08	NONUSBACKSLASH	F1	W	2	S	X	(none)	CAPSLOCK
09	G	5	R	4	F	V	B	T
10	INTERNATIONAL4	F8	O	9	L	PERIOD	INTERNATIONAL2	F7
11	APOSTROPHE	MINUS	P	0	SEMICOLON	NONUSHASH	SLASH	LEFTBRACKET
12	F6	EQUALS	I	8	K	COMMA	INTERNATIONAL1	RIGHTBRACKET
13	(none)	LCTRL	(none)	(none)	(none)	RCTRL	(none)	(none)
14	LALT	KP_MEMSUBTRACT	(none)	(none)	(none)	(none)	RALT	(none)
15	(none)	(none)	KP_MEMCLEAR	F12	(none)	(none)	RIGHT	LGUI

細かい配置は置いておいて、(none)と書かれた箇所が多いことに気付いただろうか。これは、その格子点に割り振られたキーが存在しない（空隙）、ということである。特に、Ctrlをはじめとしたモディファイアキーが存在する列に空隙が多い。これは、同時押しすることが多いモディファイアキーを含む同時押しの組み合わせにおいて、矩形の3頂点を埋めてしまう確率を低下させることを目的としている。

多くの人にとってはこれで問題は生じないが、キーリマップでCtrl等のモディファイアキーの位置を変更する人にとっては、この3キー同時押し制限がしばしば問題となってきた。たとえば「CapsLockキーをCtrlとして使う」はありふれたリマップの一つだが、上の表を見てわかるとおり、たとえば「CapsLock + Left Shift + S or X or W or 2」などは禁止対象の3キー同時押しになってしまう。実用上これはかなり不便である。

ここで、先ほど述べた「キーマトリクス上に空隙が多い」という事実を再度考えてみる。すると、以下のように「キーマトリクス上で同一矩形の頂点に位置する3キーだが、4つ目の頂点にキーがアサインされていない」となるような3キー同時押しの組み合わせが多く存在することに気付く。

このような組み合わせがあるとどうなるだろうか？上述したように、通常のキーボードファームウェアでは、この組み合わせを「同一矩形の頂点に位置する3キー」として禁止してしまう。しかし、実はこれは過剰な安全策である。

今、row 1 - column 1 (A), row 1 - column 2 (B), row 2 - column 1 (C), row 2 - column 2 (none)の間に導通が生じている訳だが、(D)の位置にキーがアサインされていないので、この状態を実現するのはA, B, Cの3キー同時押ししかあり得ない。よって、Dの位置にキーがアサインされていない時のみ、A, B, Cの3キー同時押しを認めても問題ない、ということが言える。

ku1255-firmware-modifierでは、このような組み合わせを認めるようにファームウェアを書き換えており、その結果として可能な3キー同時押しの組み合わせを最大化することに成功している。

おまけ1: 5キー同時押しの問題

勘の良い方はお気づきになったかと思うが、5キー同時押しになると別の経路での回り込み電流パスが成立する可能性があるため、厳密には別の対策が必要になる。ku1255-firmware-modifierにおいてはそのような組み合わせが生じた際には5キー同時押しを認めないような設計になっている（どのような組み合わせが相当するか、キーマトリクスを見て考えてみて欲しい）。普通のUSBキーボードの同時押し数はHID規格上6キーまでなので、7キー以上の同時押しのことは考える必要がない。

おまけ2: ビットトリック

アセンブラで今回の設計を実装する上で、「1バイト内に立っている（1である）ビットの数が0または1であるか？」を判定する機会が頻発する。元々公式ファームウェアは、1バイト内に立っているビットの数を数え、それが2未満であるか否かを判定していたが、これはかなり非効率な方法である。
ku1255-firmware-modifierでは以下の定理を利用することで、処理を高速化＆命令列の省容量化している。

x & (x - 1) == 0 ⇔ x の 1 の数が 0 個または 1 個

該当部分のアセンブラコードは以下のとおりである。

    MOV     R, A           ; 
    SUB     A, #0x01       ; A = x - 1
    AND     A, R           ; A = x & (x - 1)
    B0BTS0  FZ             ; 
    JMP     two_or_more    ; 
    JMP     one_or_zero:   ; 

このビットトリックは、限られた容量内に命令を収めるとともに、処理を高速化する上でとても有用だった。詳しくは実装を参照。