JPH0620000A - 組み合せ論理処理方法 - Google Patents
組み合せ論理処理方法Info
- Publication number
- JPH0620000A JPH0620000A JP4176323A JP17632392A JPH0620000A JP H0620000 A JPH0620000 A JP H0620000A JP 4176323 A JP4176323 A JP 4176323A JP 17632392 A JP17632392 A JP 17632392A JP H0620000 A JPH0620000 A JP H0620000A
- Authority
- JP
- Japan
- Prior art keywords
- node
- procedure
- terminated
- nodes
- value
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Withdrawn
Links
- 238000003672 processing method Methods 0.000 title description 8
- 238000000034 method Methods 0.000 claims abstract description 63
- 238000012163 sequencing technique Methods 0.000 abstract 1
- 230000014509 gene expression Effects 0.000 description 6
- 238000010586 diagram Methods 0.000 description 3
- 238000007796 conventional method Methods 0.000 description 2
- 238000007781 pre-processing Methods 0.000 description 1
- 238000002360 preparation method Methods 0.000 description 1
Abstract
(57)【要約】
【目的】２分決定グラフのＡｐｐｌｙ手続き実行時に一
時的に多くの冗長な終端ノードが作り出されることによ
る計算時間と記憶容量の増加を防ぐ。 【構成】Ａｐｐｌｙ手続き実行時に常に冗長な終端ノー
ドを取り除くことによる組合せ論理処理方法。
時的に多くの冗長な終端ノードが作り出されることによ
る計算時間と記憶容量の増加を防ぐ。 【構成】Ａｐｐｌｙ手続き実行時に常に冗長な終端ノー
ドを取り除くことによる組合せ論理処理方法。
Description
【０００１】
【産業上の利用分野】本発明は組み合わせ論理処理方法
に関し、特に２分決定グラフを用いた組み合わせ論理処
理方法に関する。
に関し、特に２分決定グラフを用いた組み合わせ論理処
理方法に関する。
【０００２】
【従来の技術】２分決定グラフ（ＢＤＤ：Ｂｉｎａｒｙ
Ｄｅｃｉｓｃｏｎ Ｄｉａｇｒａｍｓ）は組み合わせ
論理を表現する手法のひとつとして用いられている（例
えばＢｒｙａｎｔ，Ｒ．Ｅ：Ｇｒａｐｈ−Ｂａｓｅｄ
Ａｌｏｒｉｎｈｍｓ ｆｏｒＢｏｏｌｅａｎ Ｆｕｎｃ
ｎｉｏｎ Ｍａｎｉｐｕｌａｔｉｏｎ，ＩＥＥＥ Ｔｒ
ａｎｓ．Ｃｏｎｐｕｔｅｒ，Ｖｏｌ．Ｃ−３５，Ｎｏ．
８，ｐｐ．６７７−６９１）。
Ｄｅｃｉｓｃｏｎ Ｄｉａｇｒａｍｓ）は組み合わせ
論理を表現する手法のひとつとして用いられている（例
えばＢｒｙａｎｔ，Ｒ．Ｅ：Ｇｒａｐｈ−Ｂａｓｅｄ
Ａｌｏｒｉｎｈｍｓ ｆｏｒＢｏｏｌｅａｎ Ｆｕｎｃ
ｎｉｏｎ Ｍａｎｉｐｕｌａｔｉｏｎ，ＩＥＥＥ Ｔｒ
ａｎｓ．Ｃｏｎｐｕｔｅｒ，Ｖｏｌ．Ｃ−３５，Ｎｏ．
８，ｐｐ．６７７−６９１）。
【０００３】図２は論理式ｘ1 ・ｘ2 ＋ｘ4 を２分決定
グラフで表されている。以下の説明では組み合わせ論理
の入力変数の数をＮＩＮとする。２０１，２０２，２０
３は入力変数を表す非終端ノードであり、数値はそれぞ
れ入力変数ｘ1 ，ｘ2 ，ｘ4の添え字（ｉｎｄｅｘ）を
表す。２０４，２０５は定数を表す終端ノードであり、
数値はそれぞれ定数１、定数０を表す。非終端ノードは
自分より大きな添え字を持つ非終端ノードまたは終端ノ
ードへ向けて２本のエッジを持ち、一方のエッジはラベ
ル１を持つ高エッジ、もう一方はラベル０を持つ低エッ
ジである。２０６，２０７はそれぞれ２０１の高エッ
ジ、低エッジである。２０８，２０９はそれぞれ２０
６，２０７のラベルである。２分決定グラフは他のノー
ドからのエッジが無いただ１個の根をもつ。２０１は図
２の根である。
グラフで表されている。以下の説明では組み合わせ論理
の入力変数の数をＮＩＮとする。２０１，２０２，２０
３は入力変数を表す非終端ノードであり、数値はそれぞ
れ入力変数ｘ1 ，ｘ2 ，ｘ4の添え字（ｉｎｄｅｘ）を
表す。２０４，２０５は定数を表す終端ノードであり、
数値はそれぞれ定数１、定数０を表す。非終端ノードは
自分より大きな添え字を持つ非終端ノードまたは終端ノ
ードへ向けて２本のエッジを持ち、一方のエッジはラベ
ル１を持つ高エッジ、もう一方はラベル０を持つ低エッ
ジである。２０６，２０７はそれぞれ２０１の高エッ
ジ、低エッジである。２０８，２０９はそれぞれ２０
６，２０７のラベルである。２分決定グラフは他のノー
ドからのエッジが無いただ１個の根をもつ。２０１は図
２の根である。
【０００４】ノードは６個の属性を持っている。ノード
をｖとしたときｖ．ｌｏｗとｖ．ｈｉｇｈはそれぞれ低
エッジにより接続されているノード、高エッジにより接
続されているノードを示す。終端ノードの場合はともに
空とする。ｖ．ｉｎｄｅｘは非終端ノード場合は対応す
る入力変数の添え字を示し、終端ノードの場合はＮＩＮ
＋１とする。ｖ．ｉｄは整数値をとり、後述のＲｅｄｕ
ｃｅ手続きで使われる。ｖ．ｖａｌは非終端ノードの場
合は常にＸであり、終端ノードの場合はそのノードの
値、すなわち定数０または定数１を示す。ｖ．ｍａｒｋ
は真または偽の値をとり、後述のＴｒａｖｅｒｓｅ手続
きで用いられる。２０１をｖとするとｖ．ｌｏｗは２０
３、ｖ．ｈｉｇｈは２０２、ｖ．ｉｎｄｅｘは１、ｖ．
ｖａｌは０となる。２０５をｖとするとｖ．ｌｏｗは
空、ｖ．ｈｉｇｈは空、ｖ．ｉｎｄｅｘは５、ｖ．ｖａ
ｌは０となる。
をｖとしたときｖ．ｌｏｗとｖ．ｈｉｇｈはそれぞれ低
エッジにより接続されているノード、高エッジにより接
続されているノードを示す。終端ノードの場合はともに
空とする。ｖ．ｉｎｄｅｘは非終端ノード場合は対応す
る入力変数の添え字を示し、終端ノードの場合はＮＩＮ
＋１とする。ｖ．ｉｄは整数値をとり、後述のＲｅｄｕ
ｃｅ手続きで使われる。ｖ．ｖａｌは非終端ノードの場
合は常にＸであり、終端ノードの場合はそのノードの
値、すなわち定数０または定数１を示す。ｖ．ｍａｒｋ
は真または偽の値をとり、後述のＴｒａｖｅｒｓｅ手続
きで用いられる。２０１をｖとするとｖ．ｌｏｗは２０
３、ｖ．ｈｉｇｈは２０２、ｖ．ｉｎｄｅｘは１、ｖ．
ｖａｌは０となる。２０５をｖとするとｖ．ｌｏｗは
空、ｖ．ｈｉｇｈは空、ｖ．ｉｎｄｅｘは５、ｖ．ｖａ
ｌは０となる。
【０００５】図３はＴｒａｖｅｒｓｅ手続きを示してお
りノードｖを引数として受け取る。Ｔｒａｖｅｒｓｅは
ｖを根とする２分決定グラフに対して、その２分決定グ
ラフに属する全ノードに対して１回ずつある操作を行う
ための手続きである。この手続きは再帰的な手続きとな
っている。ノードの属性ｍａｒｋはノードを１回だけ処
理するためのフラグとして用いられ、この手続き呼び出
し時に全てのノードのｍａｒｋが同じ値になっている必
要がある。３０１でｍａｒｋの値を反転し、同じノード
を２回以上処理しない用にしている。３０２でｖに対す
る処理を行い、３０３でｖが終端ノードならば３０４へ
制御を移し、そうでなけらば現在の手続きを終了して上
位の手続きへ戻る。３０４、３０５ではｖ．ｍａｒｋと
ｖ．ｌｏｗ．ｍａｒｋが異なる場合にはｖ．ｌｏｗに対
して再帰的にＴｒａｖｅｒｓｅ手続きを行う。３０６、
３０７ではｖ．ｍａｒｋとｖ．ｈｉｇｈ．ｍａｒｋが異
なる場合にはｖ．ｈｉｇｈに対して再帰的にＴｒａｖｅ
ｒｓｅ手続きを行う。
りノードｖを引数として受け取る。Ｔｒａｖｅｒｓｅは
ｖを根とする２分決定グラフに対して、その２分決定グ
ラフに属する全ノードに対して１回ずつある操作を行う
ための手続きである。この手続きは再帰的な手続きとな
っている。ノードの属性ｍａｒｋはノードを１回だけ処
理するためのフラグとして用いられ、この手続き呼び出
し時に全てのノードのｍａｒｋが同じ値になっている必
要がある。３０１でｍａｒｋの値を反転し、同じノード
を２回以上処理しない用にしている。３０２でｖに対す
る処理を行い、３０３でｖが終端ノードならば３０４へ
制御を移し、そうでなけらば現在の手続きを終了して上
位の手続きへ戻る。３０４、３０５ではｖ．ｍａｒｋと
ｖ．ｌｏｗ．ｍａｒｋが異なる場合にはｖ．ｌｏｗに対
して再帰的にＴｒａｖｅｒｓｅ手続きを行う。３０６、
３０７ではｖ．ｍａｒｋとｖ．ｈｉｇｈ．ｍａｒｋが異
なる場合にはｖ．ｈｉｇｈに対して再帰的にＴｒａｖｅ
ｒｓｅ手続きを行う。
【０００６】図４、図５、図６はＲｅｄｕｃｅ手続きを
示しており、ノードｖを引数として受け取る。Ｒｅｄｕ
ｃｅ手続きはｖは根とする２分決定グラフに対して、冗
長な部分を削除しその論理を表す一意な２分決定グラフ
を求める手続きである。
示しており、ノードｖを引数として受け取る。Ｒｅｄｕ
ｃｅ手続きはｖは根とする２分決定グラフに対して、冗
長な部分を削除しその論理を表す一意な２分決定グラフ
を求める手続きである。
【０００７】図４はＲｅｄｕｃｅ手続きのメイン手続き
であり、４０１ではＮＩＮ＋１個の集合の配列ｖｌｉｓ
ｔを用意しｖ以下の全てのノードｕをｖｌｉｓｔ［ｕ．
ｉｎｄｅｘ］に追加する。４０２では変数ｎｅｘｔｉｄ
を０に初期化する。４０３、４０４、４０５および４０
６ではループ変数ｉをＮＩＮ＋１から１に変化させなが
らＲｅｄｕｃｅ ｓｔｅｐ手続きを行う。４０７では結
果の２分決定グラフを返す。 図５はＲｅｄｕｃｅ ｓ
ｔｅｐ手続きの前半部分を示しており、変数ｉ、ｎｅｘ
ｔｉｄ、ｖｌｉｓｔを上位の手続きから引き継ぐ。５０
１ではノードの集合Ｑを空にする。５０２では５０３か
ら５０７迄の処理をｖｌｉｓｔ［ｉ］の全てのノードｕ
に対して行うための制御を行う。ｕが終端ノードの場合
は５０４でｋｅｙ＝（ｕ．ｖａｌｕｅ）をキーとしてＱ
に〈ｋｅｙ，ｕ〉を登録する。ｕが非終端ノードの場
合、ｕ．ｌｏｗ．ｉｄとｌ．ｈｉｇｈ．ｉｄが等しい場
合は５０６でｕ．ｉｄにｕ．ｌｏｗ．ｉｄを代入し、等
しくない場合は５０７でｋｅｙ＝（ｕ．ｌｏｗ．ｉｄ，
ｕ．ｈｉｇｈ．ｉｄ）をキーとしてＱに〈ｋｅｙ，ｕ〉
を登録する。５０８ではＱの要素をｋｅｙでソートす
る。ソートの方法は同一のｋｅｙを持つ要素が隣り合う
様になれば何でも良い。
であり、４０１ではＮＩＮ＋１個の集合の配列ｖｌｉｓ
ｔを用意しｖ以下の全てのノードｕをｖｌｉｓｔ［ｕ．
ｉｎｄｅｘ］に追加する。４０２では変数ｎｅｘｔｉｄ
を０に初期化する。４０３、４０４、４０５および４０
６ではループ変数ｉをＮＩＮ＋１から１に変化させなが
らＲｅｄｕｃｅ ｓｔｅｐ手続きを行う。４０７では結
果の２分決定グラフを返す。 図５はＲｅｄｕｃｅ ｓ
ｔｅｐ手続きの前半部分を示しており、変数ｉ、ｎｅｘ
ｔｉｄ、ｖｌｉｓｔを上位の手続きから引き継ぐ。５０
１ではノードの集合Ｑを空にする。５０２では５０３か
ら５０７迄の処理をｖｌｉｓｔ［ｉ］の全てのノードｕ
に対して行うための制御を行う。ｕが終端ノードの場合
は５０４でｋｅｙ＝（ｕ．ｖａｌｕｅ）をキーとしてＱ
に〈ｋｅｙ，ｕ〉を登録する。ｕが非終端ノードの場
合、ｕ．ｌｏｗ．ｉｄとｌ．ｈｉｇｈ．ｉｄが等しい場
合は５０６でｕ．ｉｄにｕ．ｌｏｗ．ｉｄを代入し、等
しくない場合は５０７でｋｅｙ＝（ｕ．ｌｏｗ．ｉｄ，
ｕ．ｈｉｇｈ．ｉｄ）をキーとしてＱに〈ｋｅｙ，ｕ〉
を登録する。５０８ではＱの要素をｋｅｙでソートす
る。ソートの方法は同一のｋｅｙを持つ要素が隣り合う
様になれば何でも良い。
【０００８】図６はＲｅｄｕｃｅ ｓｔｅｐ手続きの後
半部分を示している。ノードの配列ｓｕｂｇｒａｐｈを
用いる。６０１では直前のｋｅｙの値を保存する変数ｏ
ｌｄｋｅｙを実際のどのｋｅｙとも一致しない値（−
１，−１）で初期化する。６０２では６０３から６０８
までの処理をＱのすべての要素について処理するために
制御する。６０３ではＱの先頭の要素〈ｋｅｙ，ｕ〉を
取り出し、Ｑから削除する。ｋｅｙとｏｌｄｋｅｙが一
致すれば６０５でｕ．ｉｄにｎｅｘｔｉｄを代入し、一
致しなければ６０６でｎｅｘｔｉｄに１を加え、ｕ．ｉ
ｄにｎｅｘｔｉｄを代入し、ｓｕｂｇｒａｐｈ［ｎｅｘ
ｔｉｄ］にｕを代入する。さらに６０７ではｕ．ｌｏｗ
にｓｕｂｇｒａｐｈ［ｕ．ｌｏｗ．ｉｄ］をｕ．ｈｉｇ
ｈにｓｕｂｇｒａｐｈ［ｕ．ｈｉｇｈ．ｉｄ］を代入
し、６０８でｏｌｄｋｅｙにｋｅｙを代入する。
半部分を示している。ノードの配列ｓｕｂｇｒａｐｈを
用いる。６０１では直前のｋｅｙの値を保存する変数ｏ
ｌｄｋｅｙを実際のどのｋｅｙとも一致しない値（−
１，−１）で初期化する。６０２では６０３から６０８
までの処理をＱのすべての要素について処理するために
制御する。６０３ではＱの先頭の要素〈ｋｅｙ，ｕ〉を
取り出し、Ｑから削除する。ｋｅｙとｏｌｄｋｅｙが一
致すれば６０５でｕ．ｉｄにｎｅｘｔｉｄを代入し、一
致しなければ６０６でｎｅｘｔｉｄに１を加え、ｕ．ｉ
ｄにｎｅｘｔｉｄを代入し、ｓｕｂｇｒａｐｈ［ｎｅｘ
ｔｉｄ］にｕを代入する。さらに６０７ではｕ．ｌｏｗ
にｓｕｂｇｒａｐｈ［ｕ．ｌｏｗ．ｉｄ］をｕ．ｈｉｇ
ｈにｓｕｂｇｒａｐｈ［ｕ．ｈｉｇｈ．ｉｄ］を代入
し、６０８でｏｌｄｋｅｙにｋｅｙを代入する。
【０００９】図７、図８はＡｐｐｌｙ手続きを示してい
る。Ａｐｐｌｙは与えられたノードを根とする２つの２
分決定グラフに対して、与えられた演算を行いその結果
の２分決定グラフを返す手続きである。この手続きは再
帰的な手続きとなっている。
る。Ａｐｐｌｙは与えられたノードを根とする２つの２
分決定グラフに対して、与えられた演算を行いその結果
の２分決定グラフを返す手続きである。この手続きは再
帰的な手続きとなっている。
【００１０】図７はＡｐｐｌｙ手続きをのメイン処理を
示しており、２個のノードｖ1 ，ｖ2 と演算ｏｐを引数
として受け取る。７０１でノードの２次元の配列Ｔを空
で初期化し、７０２でノードｕにＡｐｐｌ ｓｔｅｐ
（ｖ1 ，ｖ2 ）の結果を代入し、７０３でＲｅｄｕｃｅ
（ｕ）の結果を返す。
示しており、２個のノードｖ1 ，ｖ2 と演算ｏｐを引数
として受け取る。７０１でノードの２次元の配列Ｔを空
で初期化し、７０２でノードｕにＡｐｐｌ ｓｔｅｐ
（ｖ1 ，ｖ2 ）の結果を代入し、７０３でＲｅｄｕｃｅ
（ｕ）の結果を返す。
【００１１】図８はＡｐｐｌｙ ｓｔｅｐ手続き示して
おり、２個のノードｖ1 ，ｖ2 を引数として受け取る。
また上位の手続きから演算ｏｐと配列Ｔを引き継ぐ。８
０１ではｕにＴ［ｖ1 ．ｉｄ，ｖ2 ．ｉｄ］を代入し、
ｕが空でなければｕを返す。８０３では新しいノードを
作成しｕとし、８０４でｕ．ｍａｒｋに偽を代入し、Ｔ
［ｖ1 ．ｉｄ，ｖ2 ．ｉｄ］にｕを代入し、ｕ．ｖａｌ
にｖ1 ．ｖａｌとｖ2．ｖａｌに演算ｏｐを行った結果
を代入する。ｕ．ｖａｌがＸでなければ８０６でｕを終
端ノードとして設定する。ｕ．ｖａｌがＸならば８０７
でｕ．ｉｎｄｅｘにｖ1 ．ｉｎｄｅｘとｖ2 ．ｉｎｄｅ
ｘの小さいほうの値を代入し、８０８、８０９、８１０
でｖｌｏｗ１、ｖｈｉｇｈ１にノードを代入し、８１
１、８１２、８１３でｖｌｏｗ２、ｖｈｉｇｈ２にノー
ドを代入する。８１４ではＡｐｐｌｙｓｔｅｐ（ｖｌｏ
ｗ１，ｖｌｏｗ２）の結果をｕ．ｌｏｗに代入し、Ａｐ
ｐｌｙ ｓｔｅｐ（ｖｈｉｇｈ１，ｖｈｉｇｈ２）の結
果をｕ．ｈｉｇｈに代入する。８１５ではｕを結果とし
て返す。
おり、２個のノードｖ1 ，ｖ2 を引数として受け取る。
また上位の手続きから演算ｏｐと配列Ｔを引き継ぐ。８
０１ではｕにＴ［ｖ1 ．ｉｄ，ｖ2 ．ｉｄ］を代入し、
ｕが空でなければｕを返す。８０３では新しいノードを
作成しｕとし、８０４でｕ．ｍａｒｋに偽を代入し、Ｔ
［ｖ1 ．ｉｄ，ｖ2 ．ｉｄ］にｕを代入し、ｕ．ｖａｌ
にｖ1 ．ｖａｌとｖ2．ｖａｌに演算ｏｐを行った結果
を代入する。ｕ．ｖａｌがＸでなければ８０６でｕを終
端ノードとして設定する。ｕ．ｖａｌがＸならば８０７
でｕ．ｉｎｄｅｘにｖ1 ．ｉｎｄｅｘとｖ2 ．ｉｎｄｅ
ｘの小さいほうの値を代入し、８０８、８０９、８１０
でｖｌｏｗ１、ｖｈｉｇｈ１にノードを代入し、８１
１、８１２、８１３でｖｌｏｗ２、ｖｈｉｇｈ２にノー
ドを代入する。８１４ではＡｐｐｌｙｓｔｅｐ（ｖｌｏ
ｗ１，ｖｌｏｗ２）の結果をｕ．ｌｏｗに代入し、Ａｐ
ｐｌｙ ｓｔｅｐ（ｖｈｉｇｈ１，ｖｈｉｇｈ２）の結
果をｕ．ｈｉｇｈに代入する。８１５ではｕを結果とし
て返す。
【００１２】図１０、図１１は図９（ａ）と図９（ｂ）
の２分決定グラフに論理和のＡｐｐｌｙ手続きを実行し
た実行例である。図９（ａ）は論理式反転（ｘ1 ＋
ｘ3 ）を表し、図９（ｂ）は論理式ｘ2 ・ｘ3 を表して
いる。図１０は７０２を終了した時点での２分決定グラ
フを示し、図１１はＡｐｐｌｙ手続きの結果を示してい
る。
の２分決定グラフに論理和のＡｐｐｌｙ手続きを実行し
た実行例である。図９（ａ）は論理式反転（ｘ1 ＋
ｘ3 ）を表し、図９（ｂ）は論理式ｘ2 ・ｘ3 を表して
いる。図１０は７０２を終了した時点での２分決定グラ
フを示し、図１１はＡｐｐｌｙ手続きの結果を示してい
る。
【発明が解決しようとする課題】従来の手法ではＡｐｐ
ｌｙ手続き実行時に一時的に多くの終端ノードが新たに
作り出されるが、これらは最終的にＲｅｄｕｃｅ手続き
で２個の終端ノードに集約される冗長なノードである。
このような冗長なノードを数多く作ることにより無駄な
計算時間と気後容量を費やしている。
ｌｙ手続き実行時に一時的に多くの終端ノードが新たに
作り出されるが、これらは最終的にＲｅｄｕｃｅ手続き
で２個の終端ノードに集約される冗長なノードである。
このような冗長なノードを数多く作ることにより無駄な
計算時間と気後容量を費やしている。
【００１３】
【課題を解決するための手段】本発明による組合せ論理
処理方法は、定数０と定数１を表す終端ノードと、番号
付けられた入力変数を表す非終端ノードをもち、非終端
ノードを入力変数の番号順に順序付けし、冗長性を取り
除いた２分決定グラフにより表現された組み合わせ論理
を処理する方法において、終端ノードの冗長性を常に取
り除く手法を有している。
処理方法は、定数０と定数１を表す終端ノードと、番号
付けられた入力変数を表す非終端ノードをもち、非終端
ノードを入力変数の番号順に順序付けし、冗長性を取り
除いた２分決定グラフにより表現された組み合わせ論理
を処理する方法において、終端ノードの冗長性を常に取
り除く手法を有している。
【００１４】
【実施例】次に本発明について図面を参照して説明す
る。
る。
【００１５】図１は本発明の一実施例であり図８のＡｐ
ｐｌｙ ｓｔｅｐ手続きを改良したものである。Ａｐｐ
ｌｙ手続き本体は図７と同じ手続きを用いる。従来の技
術ではＡｐｐｌｙ ｓｔｅｐ手続きを実行することにそ
の結果が終端ノード、非終端ノードにかかわらず８０４
で必ず１個の新しいノードを作成していた。本実施例の
方法ではＡｐｐｌｙ ｓｔｅｐ手続き中に終端ノードの
冗長性を常に取り除く為に、終端ノードとして値１を持
つ終端ノードＮＯＤＥ１と値２をもつ終端ノードＮＯＤ
Ｅ０を用意しておき、１０２で作ろうとするノードが終
端ノードが否かを判定し、値１をもつ終端ノードならば
１０５でｕにＮＯＤＥ１を代入し、値０をもつ終端ノー
ドならば１０４でｕにＮＯＤＥ０を代入している。従っ
てＡｐｐｌｙ ｓｔｅｐ手続きが終端ノードを返す場合
は新たなノードを作ることが無くなっている。
ｐｌｙ ｓｔｅｐ手続きを改良したものである。Ａｐｐ
ｌｙ手続き本体は図７と同じ手続きを用いる。従来の技
術ではＡｐｐｌｙ ｓｔｅｐ手続きを実行することにそ
の結果が終端ノード、非終端ノードにかかわらず８０４
で必ず１個の新しいノードを作成していた。本実施例の
方法ではＡｐｐｌｙ ｓｔｅｐ手続き中に終端ノードの
冗長性を常に取り除く為に、終端ノードとして値１を持
つ終端ノードＮＯＤＥ１と値２をもつ終端ノードＮＯＤ
Ｅ０を用意しておき、１０２で作ろうとするノードが終
端ノードが否かを判定し、値１をもつ終端ノードならば
１０５でｕにＮＯＤＥ１を代入し、値０をもつ終端ノー
ドならば１０４でｕにＮＯＤＥ０を代入している。従っ
てＡｐｐｌｙ ｓｔｅｐ手続きが終端ノードを返す場合
は新たなノードを作ることが無くなっている。
【００１６】図１２は図１の詳細を示している。
【００１７】図１３は図９（ａ）と図９（ｂ）の２分決
定グラフに論理和のＡｐｐｌｙ手続きを適用した実行例
であり、７０２を終了した時点での２分決定グラフを示
している。１３０５はＮＯＤＥ０を示している。このよ
うに本実施例の手法を用いれば２分決定グラフはつねに
２個の終端ノードしか持たない。
定グラフに論理和のＡｐｐｌｙ手続きを適用した実行例
であり、７０２を終了した時点での２分決定グラフを示
している。１３０５はＮＯＤＥ０を示している。このよ
うに本実施例の手法を用いれば２分決定グラフはつねに
２個の終端ノードしか持たない。
【００１８】図１４は本実施例を実際の論理回路に適用
した結果である。この例では同じ論理で表現の異なる論
理式からそれぞれの論理を表す２分決定グラフを作成し
た時の作成したノードの総数と従来技術の手法に比べて
削減できた終端ノードの総数を示している。
した結果である。この例では同じ論理で表現の異なる論
理式からそれぞれの論理を表す２分決定グラフを作成し
た時の作成したノードの総数と従来技術の手法に比べて
削減できた終端ノードの総数を示している。
【００１９】
【発明の効果】本発明の手法を用いることにより、２分
決定グラフ処理時に一時的に作成するノードの数を大幅
に削減し、計算時間と記憶容量を削減することができ
る。
決定グラフ処理時に一時的に作成するノードの数を大幅
に削減し、計算時間と記憶容量を削減することができ
る。
【図面の簡単な説明】
【図１】本発明の一実施例の組合せ論理処理方法を示す
フローチャートである。
フローチャートである。
【図２】２分決定図の例である。
【図３】従来技術のＴｒａｖｅｒｓｅ手続きを示すフロ
ーチャートである。
ーチャートである。
【図４】従来技術のＲｅｄｕｃｅ手続きを示すフローチ
ャートである。
ャートである。
【図５】従来技術のＲｅｄｕｃｅ ｓｔｅｐ手続きの前
半部分を示すフローチャートである。
半部分を示すフローチャートである。
【図６】従来技術のＲｅｄｕｃｅ ｓｔｅｐ手続きの後
半部分を示すフローチャートである。
半部分を示すフローチャートである。
【図７】従来技術のＡｐｐｌｙ手続きを示すフローチャ
ートである。
ートである。
【図８】従来技術のＡｐｐｌｙ ｓｔｅｐ手続きを示す
フローチャートである。
フローチャートである。
【図９】２分決定図の例であり、（ａ）は論理式反転
（ｘ1 ＋ｘ3 ）を表し（ｂ）は論理式ｘ2 ・ｘ3 を表わ
す。
（ｘ1 ＋ｘ3 ）を表し（ｂ）は論理式ｘ2 ・ｘ3 を表わ
す。
【図１０】従来のＡｐｐｌｙ手続きの実行例である。
【図１１】従来のＡｐｐｌｙ手続きの実行例である。
【図１２】本発明の一実施例の組合せ論理処理方法の詳
細を示すフローチャートである。
細を示すフローチャートである。
【図１３】本発明の一実施例の組合せ論理処理方法のＡ
ｐｐｌｙ手続きの実行例である。
ｐｐｌｙ手続きの実行例である。
【図１４】本発明の一実施例の組合せ論理処理方法の実
行例である。
行例である。
１０１ 前処理工程 １０２，１０３ 判定工程 ２０１，２０２，２０３ 非終端ノード ２０４，２０５ 終端ノード ２０６，２０７ エッジ ２０８，２０９ ラベル ３０１ ノードｍａｒｋ値反転工程 ３０２ ２分決定グラフ操作 ３０３，３０４，３０５，３０７ Ｔｒａｖｅｓ手続
工程 ４０１ 配列ｖｉｌｓｔ準備工程 ４０２ 初期化工程 ４０３，４０４，４０５，４０６ Ｒｅｄｕｃｅ−ｓ
ｔｅｐ手続工程
工程 ４０１ 配列ｖｉｌｓｔ準備工程 ４０２ 初期化工程 ４０３，４０４，４０５，４０６ Ｒｅｄｕｃｅ−ｓ
ｔｅｐ手続工程
Claims (1)
- 【請求項１】 定数０と定数１を表す終端ノードと、番
号付けられた入力変数を表す非終端ノードをもち、前記
非終端ノードを入力変数の番号順に順序付けし、冗長を
取り除いた２分決定グラフ（ＢＤＤ）により表現された
組み合わせ論理を処理する手法において、前記終端ノー
ドの冗長性を常に取り除く手法を有することを特徴とす
る組み合わせ論理処理方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP4176323A JPH0620000A (ja) | 1992-07-03 | 1992-07-03 | 組み合せ論理処理方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP4176323A JPH0620000A (ja) | 1992-07-03 | 1992-07-03 | 組み合せ論理処理方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH0620000A true JPH0620000A (ja) | 1994-01-28 |
Family
ID=16011580
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP4176323A Withdrawn JPH0620000A (ja) | 1992-07-03 | 1992-07-03 | 組み合せ論理処理方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0620000A (ja) |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| WO1996034351A1 (en) * | 1995-04-25 | 1996-10-31 | Hitachi, Ltd. | Method for designing semiconductor integrated circuit and automatic designing device |
| US6188934B1 (en) | 1997-06-06 | 2001-02-13 | Nec Corporation | Register correspondence method using I/O terminals, determined registers, the number of undetermined registers and self-feedback information to define unique registers |
| US6260185B1 (en) | 1995-04-21 | 2001-07-10 | Hitachi, Ltd. | Method for designing semiconductor integrated circuit and automatic designing device |
| US6845349B1 (en) | 1995-04-21 | 2005-01-18 | Renesas Technology Corp. | Method for designing semiconductor integrated circuit and automatic designing device |
-
1992
- 1992-07-03 JP JP4176323A patent/JPH0620000A/ja not_active Withdrawn
Cited By (7)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6260185B1 (en) | 1995-04-21 | 2001-07-10 | Hitachi, Ltd. | Method for designing semiconductor integrated circuit and automatic designing device |
| US6845349B1 (en) | 1995-04-21 | 2005-01-18 | Renesas Technology Corp. | Method for designing semiconductor integrated circuit and automatic designing device |
| WO1996034351A1 (en) * | 1995-04-25 | 1996-10-31 | Hitachi, Ltd. | Method for designing semiconductor integrated circuit and automatic designing device |
| US6259276B1 (en) | 1995-04-25 | 2001-07-10 | Hitachi, Ltd. | Semiconductor integrated circuit |
| KR100334001B1 (ko) * | 1995-04-25 | 2002-04-25 | 가나이 쓰도무 | 반도체 집적회로의 설계방법 및 자동설계장치 |
| US6388474B2 (en) | 1995-04-25 | 2002-05-14 | Hitachi, Ltd. | Semiconductor integrated circuit |
| US6188934B1 (en) | 1997-06-06 | 2001-02-13 | Nec Corporation | Register correspondence method using I/O terminals, determined registers, the number of undetermined registers and self-feedback information to define unique registers |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Zhao et al. | Static logic implication with application to redundancy identification | |
| CN110297853A (zh) | 频繁集挖掘方法和装置 | |
| US6993740B1 (en) | Methods and arrangements for automatically interconnecting cores in systems-on-chip | |
| Venkateswaran et al. | A new pebble game that characterizes parallel complexity classes | |
| US6397370B1 (en) | Method and system for breaking complex Boolean networks | |
| Hosobe et al. | Locally simultaneous constraint satisfaction | |
| Chitour et al. | Dynamics and stability of continuous-time switched linear systems | |
| JPH0620000A (ja) | 組み合せ論理処理方法 | |
| Kapur et al. | Mechanically verifying a family of multiplier circuits | |
| CN109359334A (zh) | 一种组合电路门级网表转化为aiger格式文件的方法 | |
| Ponse et al. | An introduction to program and thread algebra | |
| JPS6142031A (ja) | ソ−ト処理装置 | |
| CN111142944A (zh) | 一种基于流水线执行策略的硬件sat求解器 | |
| Gregorio-Rodríguez et al. | Denotational semantics for probabilistic refusal testing | |
| US6018621A (en) | Identifying an optimizable logic region in a logic network | |
| EP1019811B1 (en) | Method and apparatus for processing a request to a boolean rule | |
| US6035110A (en) | Identifying candidate nodes for phase assignment in a logic network | |
| CN120337837B (zh) | 一种合并d型触发器的优化方法 | |
| CN109684761B (zh) | 一种宽同或电路优化方法 | |
| JPH06149927A (ja) | 積和形論理式の処理方法 | |
| Visser et al. | Efficient CTL* model checking for analysis of rainbow designs | |
| CN121351723B (zh) | 一种基于Undef_SAT的电路输入敏感性分析方法 | |
| JP2003122410A (ja) | コントローラの演算実行方法 | |
| JP3654941B2 (ja) | 論理シミュレーション方法及び論理シミュレータ | |
| CN116127894A (zh) | 一种数据排序的电路、方法、装置及介质 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A300 | Application deemed to be withdrawn because no request for examination was validly filed |
Free format text: JAPANESE INTERMEDIATE CODE: A300 Effective date: 19991005 |