QM法

Quine-McCluskey法とは，n変数論理関数のみたすべき仕様（2^n行n+1列のテーブル）から，（andとorによる）最も単純な実現法を求める方法のこと．単に実現するだけなら積和もしくは和積標準型を求めればよいだけだが，さすがにそれは無駄が多過ぎるので，挙動を変えないまま単純化する必要がある（論理圧縮）．
ちょうど昨年の今頃，サークルの先輩が実装しているという話をしていたので興味を持ったのだが，どうもwebを漁っても役立つ資料がなかった．そこで今ちょうどOcamlで書いていると言うMくん＠地下に概略を教えてもらう．
併合できる場所を探す際，trueの数でソートすれば効率がよくなるとのこと．なるほどねぇ．下手をするとすさまじく効率の悪いコードになる... って言うか上手くやっても（最悪の場合に対しては）大して効率の良いコードにはなりそうもないが，それでも「多くの場合」にうまく動くようにするのは重要だ．地下では4bit加算器に対してきちんと動作することを要求されているらしい．最後に要る項と要らない項を判別する必要があるらしいが，そこはまだ知らない．
しかしm出力論理関数に対して最適化するのはまた別の問題だし，繰り上げのディレイを最優先して下げる必要もあるだろう（例えば，半加算器をnaiveに組み合わせたのではよい全加算器はできない）．
演習資料のうpマダァ？