FPGA開発日記

カテゴリ別記事インデックス https://msyksphinz.github.io/github_pages , English Version https://fpgadevdiary.hatenadiary.com/

論理最小化のためのツールespresso-logic-analyzerを試す

論理最小化と言うのは、情報系の勉強をしたことのある人ならば必ず一度はやったことののある話だと思う。大体は2~3変数の論理入力に対して最適なAND-OR回路を導出するのが論理圧縮の基本であるが、入力変数が大きくなると人の手では負えなくなる。

これはCPUのデコード論理でも同じことが言えて、32ビットのデコード領域から最適なデコード回路を導出して論理デコード回路を導出するのはなかなか難しかったりする。 最適なデコード回路をどのようにして導出するか、というのはなかなか難しいのだが、これをヒューリスティックかつ効率的に導出するのがepsresso-logic-minimizerである。 論理屋さんにとっては大変便利そうなツールであるが、あまり情報が無くて自分でも忘れそうなのでメモしておく。

github.com

en.wikipedia.org

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]
...

このようにしてデコード回路を作成することができる。これは便利そうだ。