QM法について

QM法とは

QM法は、論理値の真偽値表を与えられたときに、それを記述する論理式を簡略化するアルゴリズムです。

任意の真偽値表を与えられたときに、それを(冗長な)論理式で表せることが知られていますが、

例えば、Xに関する真偽値表

a

b

c

X

0

0

0

0

0

0

1

0

0

1

0

0

1

0

0

0

1

1

0

1

→ a and b and (!c)

1

0

1

1

→ a and (!b) and c

0

1

1

1

→ (!a) and b and c

1

1

1

1

→ a and b and c

だったら、 各1で表されている部分をorで結んで、

X=(a and b and (!c)) or (a and (!b) and c) or ((!a) and b and c) or (a and b and c)

という形で表せるでしょう。

これを人間の手で簡単にすると、

X=(b and c) or (a and c) or (a and b)

とか、

X=((a and b) or ((a xor b) and c))

とか、

X=a+b+c >= 2

などという形になります。

ですが、下の2つはともかく、こういうように論理式を簡潔にするのは、

「充足可能性問題というNP困難な問題」

(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#.E8.A8.88.E7.AE.97.E9.87.8F )

なんだそうで、まあ要するに難しい問題なわけです。

それで、QM法は、とりあえず論理式を簡単そうにするアルゴリズムってわけです。

正式名称は、「クワイン・マクラスキー法」というらしいです。

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

正確には、

「最小の主加法標準形を求めるアルゴリズム」

と言えます。

一般的なQM法の内容

Wikipedia先生にも書かれいている通り、主に以下の2段階からなります。

1.主項を求める 1.主項の最小被覆を求める

順に見ていきましょう

主項を求める

主項(prime implicant)とは、これ以上他の項とマージできない論理積の節の事です。これだけ言っても分からないと思うので、具体的な動作と一緒に見ていきましょう。

具体的な操作:例1

まず、QM法では結果が1になる項に注目します。

さっきの例なら、

a

b

c

X

1

1

0

1

→ a and b and (!c)

1

0

1

1

→ a and (!b) and c

0

1

1

1

→ (!a) and b and c

1

1

1

1

→ a and b and c

の部分だけを取り出します。(残りは0になるということ)

上の例では簡単すぎるので、以下の例を考えていきましょう。

a

b

c

1

0

0

1

1

0

1

0

1

0

1

1

1

1

1

一番上の行を追加しました。

これを、1を含む数でグループ分けします。

a

b

c

1

0

0

1

1

0

1

0

1

0

1

1

1

1

1

これの、それぞれ上下のグループを見比べて、ハミング距離が1の物をマージします。 要するに、「ある変数以外は同じで、ある変数だけ0と1が入れ替わっている」2つの項をマージするわけです。

一度使った行を複数回使って下さい。

今回は全てマージされます。

a

b

c

1

-

0

1

0

-

1

1

-

1

-

1

-

1

1

一回このマージをする作業をする毎に、グループの数が1減っていきます。

このマージを繰り返します。

2回目はマージされないものが出てきます。 マージされなかったものは、「主項」という集合の中に移しておいて下さい。

マージされなかったもの→「主項」にする

a

b

c

-

1

1

マージされたもの

a

b

c

1

-

-

1

-

-

2回目以降は、マージされたものに同じ式が出てくるのですが、これはなるべくまとめて下さい。

マージされたもの

a

b

c

1

-

-

マージできなくなったら終了ですが、 この場合これ以上はグループが1つしかマージできないので、これで終わりです。 グループが2つ以上ある場合もマージできなくなって終了することがあります。

最終的に残ったものも「主項」に移して下さい。

さて、ここで、最終的に「主項」の集合に入ったものが、この主項なわけです。

主項

a

b

c

1

-

-

-

1

1

この操作の意味

とりあえず操作をズラーっといってしまったので、何が起きているか分からない人もいるかも知れません。 一応この操作にどういう意味があるかを見ていきましょう。

この操作の根幹はマージです。

例えば、

a

b

c

1

0

0

1

1

0

をマージして、

a

b

c

1

-

0

にしましたね。

これは、

(a and (!b) and (!c)) or (a and b and (!c))

という式を、

(a and (!c))

という式に論理圧縮する操作を表しています。

さっきの式では、これを繰り返して、

a

b

c

1

-

-

-

1

1

という形になりましたが、これは

(a) or (b and c)

を表しています。

今回は、この操作だけで、式が簡略化できてしまいました。

これでは次のステップが不要になってしまうので、他の例を見てみましょう。

例2

今度は次の表をマージしていきましょう。

a

b

c

番号

0

0

0

0

1

0

0

1

0

1

0

2

1

0

1

5

今度は番号を振っておきます。

1回目: マージされなかったもの:なし

マージされたもの

a

b

c

番号

-

0

0

0,1

0

-

0

0,2

1

0

-

1,5

これ以上はマージできないので、主項は、

a

b

c

番号

-

0

0

0,1

0

-

0

0,2

1

0

-

1,5

という事になります。

それでは次のステップに進みましょう。

最小集合被覆を求める

a

b

c

番号

-

0

0

0,1

0

-

0

0,2

1

0

-

1,5

この表は、番号と書かれた部分が、元の表のどの行をカバーしているかを表すものです。

当然、圧縮した結果は、元の表をすべてカバーしていないといけないわけですが、 それには必ずしも最終的にマージされた結果すべてが必要になるわけではありません。

上の例では、2行目と3行目を採用すれば、1行目がいらなくなることがわかります。

すなわち、

0

-

0

0,2

1

0

-

1,5

で、0,1,2,5行目全てをカバーしているわけです。

これで、結果は、

((!a) and (!c)) or (a and (!b))

という事になります。

最小集合被覆をどうやって求めるか

ここで、最小集合被覆というのは、QM法に限った問題ではなく、一般的な集合に関する問題で、たしかNP困難だったような気がします。←自信がない

一般的な最小集合被覆:集合族Iの和と同じ和を持つ、Iの部分集合族のうち最小のものを求めよ

ですが、実用的な範囲では高速化につながる手法が知られていて、「必須項」を求めることで、高速化できます。

必須項とは、(一般的に集合の問題としてみたときに、)集合族のうち一つの集合にしか含まれていない項の事で、これをどんどん除去していくだけでもかなり高速化できます。

この問題では、

a

b

c

番号

0

1

2

5

-

0

0

0,1

0

1

0

-

0

0,2

0

2

1

0

-

1,5

1

5

となっていて、2と5は、この表の2行目と3行目によってしかカバーされていないことがわかります。よって、この2行は絶対になくてはならない。

ということは、この2,3行目によってカバーされている範囲しかカバーしていない他の行(1行目)は削除できることが分かります。

今回はこれで残りがなくなってしまいましたが、必須項と、それによってカバーされる行をどんどん取り除いていくという作業を繰り返すことで、高速化できるわけです。

ここで注意が必要なのは、必ずしも必須項とそれに伴なう除去だけで最小集合被覆問題が解けるとは限らないと言うことです。

必須項とそれに伴う除去を行って、必須項は無くなったがまだカバーされていない・まだ残っている行があるということがあります。

そういう場合は各項に対して、どの行を選択するかを決めて探索していかないといけません。

ちなみに、探索にはA*がいいらしいです。自分は知りませんw(なげやり)

参考

以下の式の真偽値表をテストしてみるといいでしょう。

  1. (a or b or c) and ((!a) or (!b) or (!c)) : 必須項がない例
  2. ((a or b) and (c or d)) : QM法によって複雑になる例(正しいんだけど)

自分の年は、以下のような問題が出されました。: 4bit加算器(3bit + 3bit -> 4bit)の(出力の各桁に対する)真偽値表を作成し、QM法を実行せよ

以上が、一般的なQM法です。

以下は、それを(主に前半部)高速化しようとちょっと考えた時のメモです。多分実装すると前半部が少し速くなると思います。

では、実際にHW演習で課題が出されて締め切りが来る前に実装しましょうw。

以下古いメモ

原理

QM法(クワイン・マクラスキー法)

merge_rec(var/*何番目の変数か*/,cube[]/*Cとかだったらポインタとかでうまくこれが使える*/){
        if(var==1){
                cube[2]=cube[0]&cube[1];
        }else{
                merge_rec(var-1,cube+3^(var-1));
                merge_rec(var-1,cube+2*3^(var-1));
                for(i=3^(var-1)-1;i>=0;i--){
                        cube[2*3^(var-1)+i]=cube[3^(var-1)+i]&cube[i];
                        //ここで、1が返ってきたら、後の処理をうまく省略する方法とかが多分ある
                }
        }
}

merge(size,data[]/*最初のこれからマージしていくデータ*/){
        cube[3^size]を生成
        (data[i]を、iを2進数にしてそれを3進数とみなしたときのcubeの領域に放り込む)
        merge_rec(size,data)
}

//項の状態として、既に選択、必要ないので捨てられている、まだ分からない(未選択)の3種類の状態を考える

//mincover:返り値は、(minより小さい数の集合の和でカバーするのに成功したか(内部用),成功したときの項,成功したときの最小)
(bool,,) mincover(arr/*カバーするものとカバーされるものの項と表*/,int min){
        (arrから、必須項を抽出して、必ず必要になる項を調べ、選択する)
        
        now1 <- (arrで、今選択されている項の数)
        now2 <- (arrで、今選択されている項の数)+(arrで、未選択の項の数)
        if(now1>=min){//既に出ている最小のものより大きくなったら意味がないので
                return (false,_,_)
        }else{
                if(now2<min){
                        min=now
                }
        }
        
        (arrから、必須項を選択することで、カバーする領域を調べる)
        (arrから、カバーされたことで、まだ選択していない項が必要なくなったか(既にカバーされている領域しかカバーしていないか)を調べる)
        (arrから、必要なくなった項を削除)
        
        
        /*ここまでで、残りのまだカバーされていない領域は、必ず2つ以上の未選択の項にカバーされている*/
        /*まだ選択されていない項で残りの領域をカバーしていくことになる*/
        /*ここからがメイン*/
        if(未選択の項がない){
                return (true,arr,min)
        }
        a<-(未選択の項で、一番上の項)
        /* aを選択したものと、選択していないもので、より小さい方を選ぶ */
        arr1 <- (arrをコピー)
        arr2 <- (arrをコピー)
        /*もちろん、実装するときはこのコピーは最適化する*/
        
        (arr1で、aを捨てる)
        (arr2で、aを選択)
        
        (r1,arr1ret,min1) = mincover(arr1,min)
        if(r1){
                min=min1
        }
        (r2,arr2ret,min2) = mincover(arr2,min)
        if(r2){//成功したとしたら、minを書き換えているので、arr2retの方がより小さい
                return (true,arr2ret,min2)
        }else{
                if(r1){
                        return (true,arr1ret,min)
                }else{
                        return (false,_,_)
                }
        }
}

init(arr/*カバーするものとカバーされるものの項と表*/){
        (true,arrret,_)=mincover(arr,(arrの項の数+1)/*これの代わりに、小さいほうから順に反復深化すると速いといわれた*/)
}

QM法を超えて

より回路を組み立てるのにふさわしい結果

xyx/QM (last edited 2010-03-24 08:48:14 by xyx)