論理最小化と言うのは、情報系の勉強をしたことのある人ならば必ず一度はやったことののある話だと思う。大体は2~3変数の論理入力に対して最適なAND-OR回路を導出するのが論理圧縮の基本であるが、入力変数が大きくなると人の手では負えなくなる。
これはCPUのデコード論理でも同じことが言えて、32ビットのデコード領域から最適なデコード回路を導出して論理デコード回路を導出するのはなかなか難しかったりする。 最適なデコード回路をどのようにして導出するか、というのはなかなか難しいのだが、これをヒューリスティックかつ効率的に導出するのがepsresso-logic-minimizerである。 論理屋さんにとっては大変便利そうなツールであるが、あまり情報が無くて自分でも忘れそうなのでメモしておく。
Wikipediaにも書いてある通り、効率的な論理圧縮ツールなのであるが、まずはビルド方法から。
git clone https://github.com/scottinet/espresso-logic-minimizer.git cd espresso-logic-minimizer/espresso-src make -j$(nproc)
とするとリポジトリの先頭にbin/espresso
という実行ファイルが生成される。
ここではWikipediaのように8セグメントの生成論理を作ってみよう。
Digit Code Segments A B C D E F G 0 0000 1 1 1 1 1 1 0 -A- 1 0001 0 1 1 0 0 0 0 | | 2 0010 1 1 0 1 1 0 1 F B 3 0011 1 1 1 1 0 0 1 | | 4 0100 0 1 1 0 0 1 1 -G- 5 0101 1 0 1 1 0 1 1 | | 6 0110 1 0 1 1 1 1 1 E C 7 0111 1 1 1 0 0 0 0 | | 8 1000 1 1 1 1 1 1 1 -D- 9 1001 1 1 1 1 0 1 1
Digit Codeを入力して、A-Gのセグメントにはどのような論理を出力すればよいのか考えてみる。入力は4ビット、出力は7ビットという訳だ。
7seg.tbl
.i 4 # .i specifies the number of inputs .o 7 # .o specifies the number of outputs .ilb DCODE # This line specifies the names of the inputs in order .ob A B C D E F G # This line specifies the names of the outputs in order 0000 1 1 1 1 1 1 0 0001 0 1 1 0 0 0 0 0010 1 1 0 1 1 0 1 0011 1 1 1 1 0 0 1 0100 0 1 1 0 0 1 1 0101 1 0 1 1 0 1 1 0110 1 0 1 1 1 1 1 0111 1 1 1 0 0 0 0 1000 1 1 1 1 1 1 1 1001 1 1 1 1 0 1 1 .e
入力は1つ、ilb DCODE
により入力が1種類であることを示している。そして.ob A B C D E F G
により出力が7種類であることを示している。これをテーブルとして並べる。そして以下を実行する。
./bin/espresso 7seg.tbl
.i 4 .o 7 .ilb DCODE # This line .ob A B C D E F G .p 9 0-00 0100010 0-11 1110000 01-0 0010011 -000 1001100 0-10 1001100 -00- 0110000 001- 0101001 100- 1001011 0101 1011011 .e
このように論理圧縮が行われ、これを解釈するためには、まずは縦方向の行数だけ中間論理表現を作成する。
tmp[0] = !DCODE[3] & & !DCODE[1] & !DCODE[0] // 0-00 tmp[1] = !DCODE[3] & & DCODE[1] & DCODE[0] // 0-11 tmp[2] = !DCODE[3] & DCODE[2] & & !DCODE[0] // 01-0 tmp[3] = !DCODE[2] & !DCODE[1] & !DCODE[0] // -000 tmp[4] = !DCODE[3] & & DCODE[1] & !DCODE[0] // 0-10 tmp[5] = !DCODE[2] & !DCODE[1] & // -00- tmp[6] = !DCODE[3] & !DCODE[2] & DCODE[1] & // 001- tmp[7] = DCODE[3] & !DCODE[2] & !DCODE[1] & // 100- tmp[8] = !DCODE[3] & DCODE[2] & DCODE[1] & DCODE[0] // 0101
これらをA~Gの論理に応じて圧縮していく。
// ABCDEFG // 0100010 // 1110000 // 0010011 // 1001100 // 1001100 // 0110000 // 0101001 // 1001011 // 1011011 A = tmp[1] | tmp[3] | tmp[4] | tmp[7] | tmp[8] B = tmp[0] | tmp[1] | tmp[5] | tmp[6] ...
このようにしてデコード回路を作成することができる。これは便利そうだ。