Zenn
🍄

恣意的指摘MUX (ゲームに学ぶFPGA)

2020/11/10に公開
Verilog
FPGA
tech

ハードウェアデザインゲーム 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体験できます!
https://8bitworkshop.com/
https://8bitworkshop.com/

正確に言うと、Verilog HDLのシミュレーション。キーボードなどから信号を入力できて、VGA出力をリアルタイム見れます。いろんなレトロゲーム機のエミュレーションもついてますよ!

さっそく使ってみます。Verilogを選択しましょう。デフォルトはAtari 2600になってるかと。

Atari 2600 ▶︎ Hardware ▶︎ Verilog

で、次にMUXサンプルをGitHubからインポートします。

≡ ▶︎ Sync ▶︎ Import project from GitHub...

こちらのURLがMUXのサンプル。ダイアログの入力欄にコピペして、Import Projectボタンを押します。ブラウザ内で閉じてるんで安全です。
https://github.com/splhack/8bitworkshop_if

できました? なんか警告出たかもしれませんが、まず右側の黒いところをクリックしてフォーカスをあてます。で、スペースキーを押す。赤くなりました? このスクリーンキャストみたいになるはずです。

で、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で実行するには、コンパイルしますよね。

https://mbebenita.github.io/WasmExplorer/

こちらが、でき上がった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