(実装) クワインマクラスキー法を用いた論理関数の簡単化

プログラミング

一ヶ月ぶりの投稿です。
自由課題でクワインマクラスキー法を実装すれば点数がもらえるという事で早々に実装。

pfpacket / Quine-McCluskey
https://github.com/pfpacket/Quine-McCluskey

・クワインマクラスキー法とは
実際のところwikipedia http://ja.wikipedia.org/wiki/%E3%82%AF%E3%83%AF%E3%82%A4%E3%83%B3%E3%83%BB%E3%83%9E%E3%82%AF%E3%83%A9%E3%82%B9%E3%82%AD%E3%83%BC%E6%B3%95
を見ていただけると早いんですが、簡単にまとめ。

1. まず、簡単化する論理関数の真理値表を得る。
2. つぎに真理値表で出力が真になる組みである最小項を論理和で足していき、加法標準形を得る。
3. 加法標準形の最小項の各項を真の値の数に応じてグループ分けする。(各ビットの異なる数が=ハミング距離が1)
4. ハミング距離が1同士の各項の異なるビットを消して圧縮する。 (例. ABCと~ABC -> BC)
5. 圧縮に使用した項をマークする
6. 圧縮された項を使って次の圧縮を行う
7. 圧縮できなくなるまで4-6を繰り返す
8. マークされていない項が主項になる
9. 最小項と手順8で求められた主項からなる圧縮表を作る
10. 各主項がカバーする最小項に印をする。
11. 一番少ない数ですべての最小項をカバーできるよう主項を選択する (選択の仕方が複数ある場合がある)
12. 11で選択された主項を論理和したものが対象の論理関数の最簡形になる (複数ある場合がある)

現状では対象の論理関数の出力のdon't careをサポートしていないのでwikipediaのサンプルを使わずに
家にある教科書のサンプルを載せておきます。

入力: f(A, B, C, D) = ~AB~C + A~B~C + AB~C~D + A~BC~D + BC~D + ~ABCD + A~BCD + ~A~BD
出力:
Logical Function Simplifier (Quine-McCluskey)
[*] Enter a logical expression to be simplified
(ex. "f(A, B, C) = A + BC + ~A~B + ABC" )
[*] Input:
Sum of products form:
Truth Table: f = ~A~B~CD + ~A~BCD + ~AB~C~D + ~AB~CD + ~ABC~D + ~ABCD + A~B~C~D + A~B~CD + A~BC~D + A~BCD + AB~C~D + ABC~D
ABCD | f()

          • |----

0000 | 0
0001 | 1
0010 | 0
0011 | 1
0100 | 1
0101 | 1
0110 | 1
0111 | 1
1000 | 1
1001 | 1
1010 | 1
1011 | 1
1100 | 1
1101 | 0
1110 | 1
1111 | 0

Compressing ...
1-level compression:
COMPRESS(0001, 0011) = 00x1
COMPRESS(0001, 0101) = 0x01
COMPRESS(0001, 1001) = x001
COMPRESS(0100, 0101) = 010x
COMPRESS(0100, 0110) = 01x0
COMPRESS(0100, 1100) = x100
COMPRESS(1000, 1001) = 100x
COMPRESS(1000, 1010) = 10x0
COMPRESS(1000, 1100) = 1x00
COMPRESS(0011, 0111) = 0x11
COMPRESS(0011, 1011) = x011
COMPRESS(0101, 0111) = 01x1
COMPRESS(0110, 0111) = 011x
COMPRESS(0110, 1110) = x110
COMPRESS(1001, 1011) = 10x1
COMPRESS(1010, 1011) = 101x
COMPRESS(1010, 1110) = 1x10
COMPRESS(1100, 1110) = 11x0
2-level compression:
COMPRESS(00x1, 01x1) = 0xx1
COMPRESS(00x1, 10x1) = x0x1
COMPRESS(0x01, 0x11) = 0xx1
COMPRESS(x001, x011) = x0x1
COMPRESS(010x, 011x) = 01xx
COMPRESS(01x0, 01x1) = 01xx
COMPRESS(01x0, 11x0) = x1x0
COMPRESS(x100, x110) = x1x0
COMPRESS(100x, 101x) = 10xx
COMPRESS(10x0, 10x1) = 10xx
COMPRESS(10x0, 11x0) = 1xx0
COMPRESS(1x00, 1x10) = 1xx0
3-level compression:

Prime implicants:
~AD ~BD ~AB B~D A~B A~D

Result of simplifying:
f = ~AD + B~D + A~B
f = ~BD + ~AB + A~D