m-okada/qmc

Quine-McCluskey algorithm in C language.

Quine-McCluskey algorithm in C language.

クワイン・マクラスキー法とペトリック法による論理圧縮

概要

「クワイン・マクラスキー法とペトリック法による論理圧縮アルゴリズムをCで実装」

http://qiita.com/jun6231jp/items/41b492ce31a109e4cec6

のソースを改造しました。

改造点は

• オンメモリで動作するように。
• ロジックを整理して高速化
• 複数出力に対応

などです。

ビルド

make

使い方

qmc filename

入力ファイルは ０個以上のスペース又はタブのあと １こ以上の　'0' か '1' そのあと１こ以上のスペース又はタブのあと １こ以上の　'0' か '1 それ以外の文字が出てきたら無視。 入力の無い行は無視します。

sample/7seg.tblを参考にしてください。

入力は12ビットまで対応していますが、チェックはしていません。

オプション

-r    必要最小限のビットを求める処理をします。
-s    計算に先立って、入力をソートし重複行を削除します。

テーブル作成

必要最小限のビットを求める時、nビット立った数をnの小さい順、数の小さい順に並べたテーブルを使います。 １２ビットまで対応なので、テーブルサイズは4Kになります。

先に計算しておいたほうがよさそうなので、テーブルを作るツールを用意しました。

mask12.c

その他

メッセージ出力やオリジナルの結果出力を省略したので、別プロジェクトとしています。 以前は元のソースを字面で追いかけて書き直していましたが、Githubに登録するにあたって、処理内容を追いかけて書き直しました。

また、windowsコンソールに対応するためにソースはBOM付きUTF-8にしてあります。

VS2015の開発者コマンドプロンプトでのコンパイル、実行を確認しています。

オリジナルを作成したjun6231jpさん。 そのほかコメント欄に改造案など出してくれた方々に感謝します。