恣意的指摘MUX (ゲームに学ぶFPGA)
ハードウェアデザインゲーム MHRDをあそんでいるうちに、FPGAのための論理回路が身についてしまうという、Ｎ＆Ｌシリーズ (NAND Logic series) もこれで4作目。MHRDにそって、NOT、AND、OR、XORときましたが、今回もMHRDにそって、MUXです。
念のため、シリーズの一覧表をおいときますね。
| タイトル | NANDになる論理回路 |
|---|---|
| 『すべてがNANDになる』 | NOT、AND |
| 『冷たいNANDとド・モルガン博士たち』 | OR |
| 『XORしない数学者』 | XOR |
| 『恣意的指摘MUX』 (この記事) | MUX |
あわせてこちらもどうぞ!
| タイトル | 内容 |
|---|---|
| 『推しFPGAボード』 | おすすめのFPGAボード 2つ |
| 『FPGA なにで書く』 | ハードウェアデザイン言語 |
| 『ゲームではじめるFPGA』 | おすすめのハードウェアデザインゲーム 3つ |
| 『Verilog HDL 最初の一歩』 | Verilog HDLからツールを使ったNAND変換 |
で、MUXってなに。という本題に入る前に、そろそろ実体験しときたくないですか。
8bitworkshop
ブラウザで、FPGA体験できます!
正確に言うと、Verilog HDLのシミュレーション。キーボードなどから信号を入力できて、VGA出力をリアルタイム見れます。いろんなレトロゲーム機のエミュレーションもついてますよ!
さっそく使ってみます。Verilogを選択しましょう。デフォルトはAtari 2600になってるかと。
Atari 2600 ▶︎ Hardware ▶︎ Verilog
で、次にMUXサンプルをGitHubからインポートします。
≡ ▶︎ Sync ▶︎ Import project from GitHub...
こちらのURLがMUXのサンプル。ダイアログの入力欄にコピペして、Import Projectボタンを押します。ブラウザ内で閉じてるんで安全です。
できました? なんか警告出たかもしれませんが、まず右側の黒いところをクリックしてフォーカスをあてます。で、スペースキーを押す。赤くなりました? このスクリーンキャストみたいになるはずです。
で、MUXってなに?
MUXとはif
ifなんです。
先ほどの8bitworkshopサンプルから抜粋すると
// https://github.com/splhack/8bitworkshop_if/blob/1abecf70444744816053061b09681c28ce430908/DEFAULT#L34-L38
if (switches_p1[4]) begin
rgb = {2'b0, display_on};
end else begin
rgb = 0;
end
Verilogの細かいシンタックスをはぶくと(あらためて見直すとbegin-endとかRubyぽい)、話は単純で
if (switches_p1[4]) {
rgb = display_on;
} else {
rgb = 0;
}
これだけ。もはやJavaScriptでしょ。
真・ソフトウェアif...
しかし、はっきりさせておかなければならない。
いかにMUXがVerilog HDLのifから作られるからといって、ソフトウェアのifと混同してはならない。
ソフトウェアのifをおさらいしときます。
さっきと同じコードを、恣意的にC++で書き直すとこのとおり。
void test(const bool switches_p1[5], bool display_on, bool& rgb) {
if (switches_p1[4]) {
rgb = display_on;
} else {
rgb = false;
}
}
このソフトウェアプログラムを、CPUで実行するには、コンパイルしますよね。
こちらが、でき上がったCPUバイトコード。
sub rsp, 8 ; 0x000000 48 83 ec 08
movzx ecx, byte ptr [r15 + rdi + 4] ; 0x000004 41 0f b6 4c 3f 04
test ecx, ecx ; 0x00000a 85 c9
setne al ; 0x00000c 0f 95 c0
movzx eax, al ; 0x00000f 0f b6 c0
and eax, esi ; 0x000012 23 c6
mov byte ptr [r15 + rdx], al ; 0x000014 41 88 04 17
nop ; 0x000018 66 90
add rsp, 8 ; 0x00001a 48 83 c4 08
ret ; 0x00001e c3
このCPUバイトコードをメモリに配置しておくと、CPUがそれをフェッチして一つ一つ実行する。つまり時間がかかる。
ハードウェアのif
『すべてがNANDになる』という言説どおり、すべての論理回路はNANDから作り出せる。ハードウェアのifであるMUXも、当然NANDになる。
これがMUX(Multiplexer)の記号。
switches_p1[4]が0のとき、注目すべきコードはここ。
if (switches_p1[4]) {
//
} else {
rgb = 0;
}
記号上で電気の流れを妄想すると、こんな感じですね。
で、switches_p1[4]が1のときは
if (switches_p1[4]) {
rgb = display_on;
} else {
//
}
当然、記号上での電気の流れはこう妄想できます。
表にまとめます。Selが0のときAがOutに繋がり、Selが1のときBがOutに繋がる。
色をつけるとわかりやすい。
しかし、こんなのNANDになるの?
カルノー図
昔の人は考えた。表を使ってブール代数をシンプルにする方法を。カルノーさんエラい。
というわけで、カルノーさんが考えたカルノー図を使います。
まず、先ほどの表を並べなおす。表の中身がOutの値以外、並べなおし方は、わりと自由。ここでは、とりたてて理由もなく、左側にSel、上側にABを選択。意味通りますよね?
わりと自由なものの、一つだけゆずれない点が。隣り合う行と列は、1ビットしか変化してはいけない(グレイコード)。はじっこ同士も。
つまり、次の並べ方はダメ。なぜなら、01 → 10で2ビット変化しちゃってるから。
00 → 01 → 10 → 11
図のとおり、こう並べる必要があるわけです。
00 → 01 → 11 → 10
表を並べなおしたら、次は1に注目。つながってるところを囲みます。
どこから囲もうが、どのように囲もうが、あなたの自由。ただし、大きさは、たてよこ別々に、1、2、4、8、など、2のn乗でないといけない。1x1、1x2、2x2、4x1、4x2など、ご自由に。
今回たまたま囲んだところのSel、A、Bの値に注目すると、
Selが0、かつ、Aが1、のとき条件を満たす。Pythonで書けば
(Sel is 0) and (A is 1)
こう書いても同じですよね。
(not Sel) and A
ブール代数で表すと
次はここを囲んどきますか。
同じく囲んだところのSel、A、Bの値に注目すると、
Selが1、かつ、Bが1、のとき条件を満たす。Pythonで書けば
(Sel is 1) and (B is 1)
つまり
Sel and B
ブール代数で表せば
これで1を全部囲めました。
囲んだ同士は+でつなげられるので、MUXのブール代数はこう書けます。
以上が、カルノー図によるMUXブール代数の導出。
NANDへの変換
ブール代数を、論理記号に置き換えれば完成!
念のため、一つ一つNANDを確認しときます。
Pythonでもテストしときましょ。
A = [0, 0, 1, 1, 0, 0, 1, 1]
B = [0, 1, 0, 1, 0, 1, 0, 1]
Sel = [0, 0, 0, 0, 1, 1, 1, 1]
Out = [0, 0, 1, 1, 0, 1, 0, 1]
def mux_if(a, b, sel):
if sel:
return b
else:
return a
def mux_nand(a, b, sel):
def nand(a, b):
return not (a and b)
return nand(nand(not sel, a), nand(sel, b))
for i in range(len(A)):
a = A[i] == 1
b = B[i] == 1
sel = Sel[i] == 1
out = Out[i] == 1
assert mux_if(a, b, sel) == mux_nand(a, b, sel) == out
問題なし!
Verilog HDLからの作図
Yosysでも、ifを作図しときましょ。
module top (
input A,
inout B,
input Sel,
output reg Out,
);
always @(*) begin
if (Sel) begin
Out = B;
end else begin
Out = A;
end
end
endmodule
NANDな論理回路に変換するおまじない。
yosys -q -p "
read_verilog mux.v
synth -top top
abc -g NAND
show -format svg -prefix mux
"
完全に一致!
おさらい
ソフトウェアのif
void mux(bool a, bool b, bool sel, bool& out) {
if (sel) {
out = b;
} else {
out = a;
}
}
sub rsp, 8 ; 0x000000 48 83 ec 08
test edx, edx ; 0x000004 85 d2
cmove esi, edi ; 0x000006 0f 44 f7
mov byte ptr [r15 + rcx], sil ; 0x000009 41 88 34 0f
nop ; 0x00000d 66 90
add rsp, 8 ; 0x00000f 48 83 c4 08
ret ; 0x000013 c3
ハードウェアのif
すべてがNANDになる
超難関MUXもNANDになりました。すべてがNANDになります。
Discussion