(57)【特許請求の範囲】
【請求項１】
複数の論理ゲートを組み合わせてなる組み合わせ論理回路について、入力信号パターンと出力信号パターンとの関係を示す真理値表を作成する装置であって、
複数の入力信号パターンを、前後でハミング距離が１となるような順番に並べた入力信号系列を作成し、この入力信号系列の先頭から順に入力信号パターンを１つずつ取り出す処理を行う第１の手段と、
前記第１の手段が最初に取り出した入力信号パターンについて、前記論理回路内の全論理ゲートにこの入力信号パターンに基づく信号を伝播させて出力信号パターンを生成する処理を行う第２の手段と、
前記第１の手段がｎ回目（ｎ＞１）に取り出した入力信号パターンについて、（ｎ−１）回目に取り出した入力信号パターンとは論理値が異なる１つの入力ビットを特定し、この入力ビットの影響を受ける論理ゲートについてのみ、このｎ回目に取り出した入力信号パターンに基づく信号を伝播させて出力信号パターンの更新を行う処理を行う第３の手段と、
個々の入力信号パターンと、信号伝播により生成された出力信号パターンもしくは信号伝播により更新された出力信号パターンと、を対応させることにより真理値表の作成を行う第４の手段と、
を備えることを特徴とする組み合わせ論理回路における真理値表作成装置。
【請求項２】
請求項１に記載の真理値表作成装置において、
第１の手段が、１ビットからなる入力信号パターンの入力信号系列をデータ列（０，１）もしくはデータ列（１，０）と定義し、（Ｎ−１）ビットからなる入力信号パターンの入力信号系列をデータ列（Ｂ０，Ｂ１，Ｂ２，…，Ｂｋ）と定義したときに、Ｎビットからなる入力信号パターンについての入力信号系列を、データ列（０Ｂ０，０Ｂ１，０Ｂ２，…，０Ｂｋ，１Ｂｋ，…，１Ｂ２，１Ｂ１，１Ｂ０）もしくはデータ列（１Ｂ０，１Ｂ１，１Ｂ２，…，１Ｂｋ，０Ｂｋ，…，０Ｂ２，０Ｂ１，０Ｂ０）とする帰納法により、複数の入力信号パターンを前後でハミング距離が１となるような順番に並べた入力信号系列を作成することを特徴とする組み合わせ論理回路における真理値表作成装置。
【請求項３】
請求項１または２に記載の真理値表作成装置において、
第３の手段が、
前回とは論理値が異なる特定の入力ビットを直接入力する論理ゲートを所定の評価順にイベントリストに入れる手段と、
このイベントリストから先頭の論理ゲートを取り出し、取り出した論理ゲートについて、ｎ回目に取り出した入力信号パターンに基づく出力値を求め、出力値が前回から変化した場合には、後続の論理ゲートのうちイベントリストに存在しないものを、前記評価順にイベントリストに追加する処理を、イベントリストが空になるまで繰り返し実行する手段と、
を備えることを特徴とする組み合わせ論理回路における真理値表作成装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、論理回路における真理値表作成装置に関し、特に、複数の論理ゲートを組み合わせてなる組み合わせ論理回路について、入力信号パターンと出力信号パターンとの関係を示す真理値表を作成する装置に関する。
【０００２】
【従来の技術】
半導体回路の製造技術の発達により、回路の集積度は益々向上してきており、膨大な数の論理ゲートを集積化して複雑な機能を実現したＬＳＩが普及するに至っている。一般に論理回路は、ＡＮＤゲート、ＯＲゲートなどの単純な論理ゲートを多数組み合わせてなる組み合わせ論理回路と、フリップフロップなどの要素を組み入れた順序回路と、に大別できる。順序回路の動作は、前段階の論理状態に左右されるため、その解析には過去の論理動作に関する情報が必要となるが、組み合わせ論理回路の動作は、過去の論理状態には依存せず、入力信号として与えた論理パターンに基づいて、出力信号の論理パターンが一義的に決定できる。このため、入力信号パターンと出力信号パターンとの関係を示す真理値表を定義することができ、組み合わせ論理回路の論理動作は、すべてこの真理値表によって表現することができる。したがって、真理値表は、組み合わせ論理回路の論理機能を示す仕様書としての役目を果たす重要なものである。また、組み合わせ論理回路の設計を行う過程では、論理シミュレータなどを用いて、設計対象となる回路が正常に動作するか否かの検証が行われることになるが、この検証を行う上でも真理値表が必要になる。
【０００３】
【発明が解決しようとする課題】
組み合わせ論理回路の真理値表を作成する方法は、原理的には非常に単純である。すなわち、所定の入力信号パターンを用意し、このパターンに対応する信号を論理回路の入力段の論理ゲートに与え、後続する論理ゲートへと信号が伝播してゆく過程において、論理値がどのように変遷してゆくかを追ってゆき、最終的にどのような出力信号パターンが得られるかを確認すればよい。あらゆる入力信号パターンについて、それぞれどのような出力信号パターンが得られるかが確認できれば、両パターンを対応させることにより真理値表が得られることになる。実際には、このような方法による真理値表の作成は、コンピュータを利用した演算によって行われる。
【０００４】
しかしながら、このような真理値表の作成方法は、小規模な論理回路の場合には問題はないが、大規模な論理回路の場合には、演算負担が大きくなり効率的ではない。論理回路の入力信号のビット数（すなわち、論理回路の入力端子数）をｍとした場合、入力信号パターンは２ｍとおりのバリエーションをもつことになり、ｍの数が増えれば増えるほど、入力信号パターンの数は指数的に増加することになる。また、複雑な機能をもった論理回路になればなるほど、回路を構成する全論理ゲート数も膨大な数になる。たとえば、１００００個の論理ゲートからなり、１６ビットの入力信号を受け入れる論理回路の場合、特定の入力信号パターンに対応する信号を１００００個の論理ゲートに伝播させたときの論理状態の遷移を求める演算を、２１６とおりの入力信号パターンのそれぞれについて行う必要がある。このような膨大な演算を行うには、多大な時間と労力が必要になる。
【０００５】
そこで本発明は、組み合わせ論理回路における真理値表を効率良く作成する装置を提供することを目的とする。
【０００６】
【課題を解決するための手段】
(1)   本発明の第１の態様は、複数の論理ゲートを組み合わせてなる組み合わせ論理回路について、入力信号パターンと出力信号パターンとの関係を示す真理値表を作成する装置において、
複数の入力信号パターンを、前後でハミング距離が１となるような順番に並べた入力信号系列を作成し、この入力信号系列の先頭から順に入力信号パターンを１つずつ取り出す処理を行う第１の手段と、
第１の手段が最初に取り出した入力信号パターンについて、論理回路内の全論理ゲートにこの入力信号パターンに基づく信号を伝播させて出力信号パターンを生成する処理を行う第２の手段と、
第１の手段がｎ回目（ｎ＞１）に取り出した入力信号パターンについて、（ｎ−１）回目に取り出した入力信号パターンとは論理値が異なる１つの入力ビットを特定し、この入力ビットの影響を受ける論理ゲートについてのみ、このｎ回目に取り出した入力信号パターンに基づく信号を伝播させて出力信号パターンの更新を行う処理を行う第３の手段と、
個々の入力信号パターンと、信号伝播により生成された出力信号パターンもしくは信号伝播により更新された出力信号パターンと、を対応させることにより真理値表の作成を行う第４の手段と、
を設けるようにしたものである。
【０００７】
(2)   本発明の第２の態様は、上述の第１の態様に係る真理値表作成装置において、
第１の手段が、１ビットからなる入力信号パターンの入力信号系列をデータ列（０，１）もしくはデータ列（１，０）と定義し、（Ｎ−１）ビットからなる入力信号パターンの入力信号系列をデータ列（Ｂ０，Ｂ１，Ｂ２，…，Ｂｋ）と定義したときに、Ｎビットからなる入力信号パターンについての入力信号系列を、データ列（０Ｂ０，０Ｂ１，０Ｂ２，…，０Ｂｋ，１Ｂｋ，…，１Ｂ２，１Ｂ１，１Ｂ０）もしくはデータ列（１Ｂ０，１Ｂ１，１Ｂ２，…，１Ｂｋ，０Ｂｋ，…，０Ｂ２，０Ｂ１，０Ｂ０）とする帰納法により、複数の入力信号パターンを前後でハミング距離が１となるような順番に並べた入力信号系列を作成するようにしたものである。
【０００８】
(3)   本発明の第３の態様は、上述の第１または第２の態様に係る真理値表作成方法において、
第３の手段を、
前回とは論理値が異なる特定の入力ビットを直接入力する論理ゲートを所定の評価順にイベントリストに入れる手段と、
このイベントリストから先頭の論理ゲートを取り出し、取り出した論理ゲートについて、ｎ回目に取り出した入力信号パターンに基づく出力値を求め、出力値が前回から変化した場合には、後続の論理ゲートのうちイベントリストに存在しないものを、評価順にイベントリストに追加する処理を、イベントリストが空になるまで繰り返し実行する手段と、
によって構成するようにしたものである。
【０００９】
【発明の実施の形態】
以下、本発明を図示する実施形態に基づいて説明する。ここでは、説明の便宜上、図１に示すような論理回路を考える。この論理回路は、三入力ＡＮＤゲート１、二入力ＯＲゲート２、二入力ＯＲゲート３、二入力ＡＮＤゲート４、の４つの論理ゲートから構成され、３ビットからなる入力信号ＡＢＣを受け入れて、１ビットからなる出力信号Ｑを出力する機能を有する。この論理回路の真理値表を図２に示す。この真理値表は、８とおりの入力信号パターン［１］〜［８］（図面上の丸数字は、明細書上では、［］で囲った数字で示す）のそれぞれに対応して得られる出力信号パターンを示すものである。たとえば、入力信号パターン［１］は、「０００」なる３ビットのパターンからなり、この入力信号パターン［１］に対して、「０」なる１ビットの出力信号パターンが得られている。このような真理値表は、個々の入力信号パターンごとに、それぞれ各ビットを与えたときの各論理ゲートの論理動作を追ってゆくことにより得ることができる。
【００１０】
しかしながら、現在実用されている複雑な機能をもった論理回路は、図１に示すような単純な構成ではなく、膨大な数の論理ゲートから構成され、入力信号パターンも膨大な数になる。このような膨大な数の論理ゲートからなる論理回路の動作を、膨大な数の入力信号パターンのそれぞれについて解析するには、多大な演算負担が避けられず、高性能なコンピュータを用いたとしても、長い演算時間が必要になる。本発明はこのような問題を解決するためのより効率的な真理値表の作成方法を提供するものである。
【００１１】
図３は、本発明に係る真理値表の作成装置による処理の基本手順を示す流れ図である。まず、ステップＳ１において、複数の入力信号パターンを、前後でハミング距離が１となるような順番に並べた入力信号系列を作成する。ここで、「ハミング距離」とは、２つのビットパターンについて、論理値が異なるビットがいくつあるかを示す指数である。これを具体的に説明するために、図２の真理値表に示されている８種類の入力信号パターン［１］〜［８］についてのハミング距離を見てみる。たとえば、パターン［１］と［２］とを比べると、入力信号Ｃのみが異なる。すなわち、論理値が異なるビットは１ビットであり、両パターンのハミング距離は１である。また、パターン［２］と［３］とを比べると、入力信号ＢとＣとが異なるので、論理値が異なるビットは２ビットとなり、ハミング距離は２になる。同様にして、パターン［４］と［５］とのハミング距離は３になる。
【００１２】
このように、図２に示す真理値表に示されている入力信号パターン［１］〜［８］の並び順では、前後のパターン間のハミング距離は１〜３とさまざまである。図３のステップＳ１では、前後のパターン間のハミング距離が常に１となるように、各入力信号パターンを並べた入力信号系列を作成する。具体的には、たとえば、図４の真理値表に示されているような入力信号パターン［１］〜［８］からなる入力信号系列が作成される。この入力信号系列では、パターン［１］と［２］とを比べると入力信号Ｃのみが異なり、パターン［２］と［３］とを比べると入力信号Ｂのみが異なり、パターン［３］と［４］とを比べると入力信号Ｃのみが異なり、パターン［４］と［５］とを比べると入力信号Ａのみが異なり、…、というように、前後のパターン間のハミング距離は常に１である。このような入力信号系列が作成できたら、各入力信号パターンについての出力信号パターンを順に求める処理が、ステップＳ２以降で行われる（図４に示す真理値表には、既に出力信号Ｑが書き込まれているが、ステップＳ１の時点では、この出力信号Ｑの欄はまだ空欄となっている）。
【００１３】
続くステップＳ２では、ステップＳ１で作成した入力信号系列の先頭から順に、入力信号パターンを１つずつ取り出す処理が行われ、こうして取り出された各入力信号パターンについて、ステップＳ３を経てステップＳ４の処理もしくはステップＳ５の処理が実行される。すなわち、ステップＳ３における分岐により、最初に取り出された入力信号パターンについては、ステップＳ４の処理が実行され、２回目以降に取り出された入力信号パターンについては、ステップＳ５の処理が実行されることになる。別言すれば、図４の真理値表に示されている８つの入力信号パターン［１］〜［８］をこの順番に並べてなる入力信号系列が作成されていた場合には、この入力信号系列の先頭にある入力信号パターン［１］が最初に取り出され、ステップＳ４の処理が実行されることになり、２回目〜８回目に取り出される入力信号パターン［２］〜［８］については、ステップＳ５の処理が実行されることになる。
【００１４】
ステップＳ４の処理は、取り出した入力信号パターンに基づく信号を、論理回路内の全論理ゲートに伝播させて出力信号パターンを生成する処理である。上述の具体例では、「０００」なる入力信号パターン［１］を図１に示す回路の入力信号ＡＢＣに与えた場合に全論理ゲート１〜４の論理動作を追ってゆき、最終的に出力信号Ｑとして得られる論理値を求める処理になる。したがって、１００００個の論理ゲートからなる論理回路の場合、この１００００個の全論理ゲートの論理動作を解析する必要があり、かなりの演算負担がかかることになる。ただ、本発明による方法では、このステップＳ４の処理は、最初の入力信号パターンについて１回だけ実行すれば足り、それ以降の入力信号パターンについては、演算負担の少ないステップＳ５の処理を実行すればよい。
【００１５】
ステップＳ５の処理は、入力信号の変化の影響を受ける論理ゲートのみに信号を伝播させて出力信号パターンを更新する処理である。ステップＳ１において作成した入力信号系列は、前後のパターン間のハミング距離が常に１となるように、各入力信号パターンを並べたものである。したがって、ｎ回目（ｎ＞１）に取り出した入力信号パターンを、（ｎ−１）回目に取り出した入力信号パターンと比べると、どれか１つの入力ビットの論理値のみが異なっていることになる。そこで、前回と論理値が異なる１つの入力ビットを特定し、この入力ビットの影響を受ける論理ゲートについてのみ、このｎ回目に取り出した入力信号パターンに基づく信号を伝播させて出力信号パターンの更新を行う処理を行えば、全論理ゲートについての論理解析を行う必要はなくなる。別言すれば、全論理回路中、論理値に変化が生じた部分についてのみ新たな解析を行い、最終的な変化が生じた出力値についてのみ更新を行うようにすれば、その他の出力値は前回のものをそのまま流用することができるので、演算負担は大幅に軽減されることになる。
【００１６】
こうして、ステップＳ４において出力信号パターンが生成されるか、ステップＳ５において出力信号パターンが更新されたら、ステップＳ２で取り出した入力信号パターンと生成もしくは更新された出力信号パターンとを対応させて真理値表に記録する処理がステップＳ６において行われる。そして、ステップＳ７を経て、再びステップＳ２からの処理が繰り返し実行される。こうして、入力信号系列の中の全入力信号パターンについての処理が完了したら、この図３に示す手順は終了であり、目的の真理値表が作成されることになる。
【００１７】
続いて、上述の手順によって、図１に示す論理回路の真理値表を作成する過程を、順を追って説明しよう。まず、ステップＳ１において、ハミング距離が１となる入力信号系列が作成される。ここでは、図４の真理値表の入力信号の欄に記載された８種類の入力信号パターン［１］〜［８］からなる入力信号系列（「０００」，「００１」，「０１１」，…，「１００」）が作成されたものとしよう。前述したように、この時点では、まだ出力信号Ｑは得られていない。
【００１８】
さて、続くステップＳ２では、最初の入力信号パターン［１］（「０００」）が取り出され、ステップＳ３からステップＳ４へと進むことになる。ここでは、この「０００」なる３ビットの入力信号を、図１に示す全論理回路に与え、全論理ゲート１〜４に信号を伝播させて最終出力Ｑの論理値が求められる。具体的には、Ｑの論理値として「０」が求まる。そこで、ステップＳ６において、入力信号パターン「０００」と出力信号パターン「０」とが真理値表に記録されることになる。別言すれば、図４に示す真理値表の第１行目が書き込まれる。
【００１９】
次に、ステップＳ７から再びステップＳ２へと戻り、今度は２番目の入力信号パターン［２］（「００１」）が取り出され、ステップＳ３からステップＳ５へと進むことになる。この２番目の入力信号パターン［２］（「００１」）を最初の入力信号パターン［１］（「０００」）と比べると、３ビット目（入力信号Ｃ）のみが変化している。そこで、この入力信号Ｃの変化の影響を受ける論理ゲートのみに信号を伝播させて出力信号パターンを更新する処理が行われる。具体的には、まず、入力信号Ｃを直接入力している論理ゲート１および論理ゲート２に信号を伝播させた状態が調べられる。ここで、論理ゲート１の他の入力信号Ａ，Ｂは「０」のままであるから、論理ゲート１の論理状態に変化は生じていないことがわかる。したがって、論理ゲート１の論理動作に起因して後続する論理ゲートの論理状態が変化することはない。すなわち、後続する論理ゲートについての論理状態には影響が及ばないことがわかる。一方、論理ゲート２はＯＲゲートであるので、一方の入力信号Ｃが「１」に変化すると、その論理出力は「１」に変化することになる。したがって、後続する論理ゲート４に影響が及ぶことになるので、この論理ゲート４の論理動作を調べると、他方の入力値は「０」のまま変化はないので、論理ゲート４の出力値には変化が生じないことがわかる。
【００２０】
かくして、最終出力Ｑの論理値には何ら変化は生じないことが確認でき、更新後の出力信号パターンは、やはり「０」のままである。よって、ステップＳ６では、入力信号パターン「００１」と出力信号パターン「０」とが真理値表に記録されることになる。別言すれば、図４に示す真理値表の第２行目が書き込まれる。結局、入力信号Ｃの変化により、図５に太線で示した部分のみが影響を受けたことになる。
【００２１】
再び、ステップＳ７からステップＳ２へと戻り、３番目の入力信号パターン［３］（「０１１」）が取り出され、ステップＳ３からステップＳ５へと進むことになる。今度は、２ビット目（入力信号Ｂ）のみが変化しているので、この入力信号Ｂの変化による影響を受ける論理ゲートについての論理動作の確認が行われ、最終出力Ｑの論理値が求められる。その結果、図４に示す真理値表の第３行目が書き込まれることになる。
【００２２】
以下、同様に、入力信号パターン［４］〜［８］までが順次取り出され、ステップＳ５において、入力信号の変化の影響を受けた部分についてのみ論理動作の確認が行われ、最終出力Ｑの論理値が求められ、その結果、図４に示す真理値表の各行が書き込まれることになる。いずれの場合も、前回と比べて変化した入力信号は１ビットのみであり、その影響を受ける論理ゲートは全回路中の一部のみとなる。したがって、このステップＳ５の処理は、ステップＳ４の処理に比べて、演算負担は大幅に軽減されることになる。
【００２３】
【実施例】
上述の実施形態では、本発明の基本概念をひととおり説明したが、ここでは、図３に示すステップＳ１の処理およびステップＳ５の処理についてのより具体的な実施例を述べることにする。
【００２４】
まず、ステップＳ１の処理の実施例を説明する。この処理は、ハミング距離が１となる入力信号系列を作成する処理であるが、このような入力信号系列を効率的に作成するためには、何らかのアルゴリズムに基づく処理が必要である。たとえば、図６に示すような一辺が単位長の立方体を考えよう。ここで、図示の方向にＡ軸，Ｂ軸，Ｃ軸を定義し、この立方体の８個の頂点を三次元座標値で表現すれば、各頂点は（０００），（００１），……といった３ビットからなる座標値で表されるので、各頂点をそれぞれ８種類の入力信号パターン［１］〜［８］に対応づけることができる。そして、この立方体の任意の一辺を挟んだ両頂点は、３ビットからなる座標値のいずれか１ビットのみが相違する関係になるので、ハミング距離が１の入力信号パターンに相当することになる。よって、ハミング距離が１となる入力信号系列を作成する処理は、この立方体の８個の頂点を通る一筆書きの経路を見つける処理と等価である。
【００２５】
図６に矢印を付した太線で示す経路は、一筆書きの経路のひとつであり、７個の頂点を通る一筆書きの経路にはなっているが、８個目の頂点を通ることには失敗している。これに対し、図７に矢印を付した太線で示す経路は、８個全部の頂点を通る一筆書きの経路になっている。このように、入力信号が３ビットの場合であっても、ハミング距離が１となる入力信号系列を作成するには、ある程度の工夫が必要になる。したがって、入力信号がより多数のビットからなる実際の論理回路について、ハミング距離が１となる入力信号系列を作成するためには、何らかのアルゴリズムに基づく処理が不可欠である。
【００２６】
このようなアルゴリズムのひとつとして、本願発明者は次のような帰納法を利用するアルゴリズムを見出だした。このアルゴリズムを図８を用いて説明しよう。ここでは、Ｎビットからなる入力信号パターン（２Ｎとおりのパターン）の入力信号系列を、ｔｒｙ（Ｎ）と表わすことにする。そして、図８(a) に示すように、まず、１ビットからなる入力信号パターンの入力信号系列ｔｒｙ（１）を、図示のとおり、データ列（０，１）と定義する。もちろん、最初の入力信号パターン「０」と２番目の入力信号パターン「１」との間のハミング距離は１である。次に、図８(b) に示すように、（Ｎ−１）ビットからなる入力信号パターンの入力信号系列ｔｒｙ（Ｎ−１）をデータ列（Ｂ０，Ｂ１，Ｂ２，…，Ｂｋ）と定義する。ここで、このデータ列（Ｂ０，Ｂ１，Ｂ２，…，Ｂｋ）は前後のハミング距離が１であるものとする。
【００２７】
この場合、図８(c) に示すように、ｔｒｙ（Ｎ−１）のデータ列のそれぞれの頭に「０」を付け加えてなる前半データ列と、ｔｒｙ（Ｎ−１）を逆順にしたデータ列のそれぞれの頭に「１」を付け加えてなる後半データ列と、を接続して、新たなデータ列（０Ｂ０，０Ｂ１，０Ｂ２，…，０Ｂｋ，１Ｂｋ，…，１Ｂ２，１Ｂ１，１Ｂ０）を作成すれば、この新たなデータ列は、Ｎビットからなる入力信号パターンについての入力信号系列ｔｒｙ（Ｎ）となる。しかも、ｔｒｙ（Ｎ−１）は前後のハミング距離が１であるデータ列であるから、ｔｒｙ（Ｎ）の前半データ列および後半データ列のそれぞれも、やはり前後のハミング距離が１であるデータ列となる。そして、前半データ列の最後のデータ「０Ｂｋ」と後半データ列の最初のデータ「１Ｂｋ」との間のハミング距離は１であるから、結局、ｔｒｙ（Ｎ）を構成する全データ列は全体として前後のハミング距離が１であるデータ列となる。
【００２８】
したがって、ｔｒｙ（１）に基づいてｔｒｙ（２）を求め、ｔｒｙ（２）に基づいてｔｒｙ（３）を求め、…、ｔｒｙ（Ｎ−１）に基づいてｔｒｙ（Ｎ）を求める、という帰納法によれば、任意のＮビットからなる入力信号パターンの入力信号系列のうち、前後のハミング距離が１であるという条件を満たす系列を作成することが可能である。なお、上述の例では、ｔｒｙ（Ｎ−１）のデータ列の頭に「０」を付したデータ列を前半データ列とし、ｔｒｙ（Ｎ−１）のデータ列の頭に「１」を付したデータ列を後半データ列として、ｔｒｙ（Ｎ）のデータ列を作成したが、逆に、ｔｒｙ（Ｎ−１）のデータ列の頭に「１」を付したデータ列を前半データ列とし、ｔｒｙ（Ｎ−１）のデータ列の頭に「０」を付したデータ列を後半データ列として、ｔｒｙ（Ｎ）のデータ列を作成してもよい。また、ｔｒｙ（１）のデータ列として、データ列（０，１）を定義する代わりに、データ列（１，０）を定義してもかまわない。
【００２９】
図９は、上述のアルゴリズムに基づいて、実際に入力信号系列を生成した例を示す図である。まず、図９(a) に示すように、ｔｒｙ（１）としてデータ列（０，１）を定義し、続いて、図９(b) に示すように、このデータ列（図に破線で示す部分）をこの順のままにして頭に「０」を付した前半データ列と、逆順にして頭に「１」を付した後半データ列とを作成し、これを接続して新たなデータ列（図に一点鎖線で示す部分）を作成すれば、この新たなデータ列がｔｒｙ（２）のデータ列となる。次に、このｔｒｙ（２）のデータ列（図に一点鎖線で示す部分）をこの順のままにして頭に「０」を付した前半データ列と、逆順にして頭に「１」を付した後半データ列とを作成し、これを接続して新たなデータ列（図に二点鎖線で示す部分）を作成すれば、この新たなデータ列がｔｒｙ（３）のデータ列となる。図４の真理値表の入力信号欄に記載されているデータ列は、このようにして得られたｔｒｙ（３）のデータ列である。同様に、このｔｒｙ（３）のデータ列（図に二点鎖線で示す部分）をこの順のままにして頭に「０」を付した前半データ列と、逆順にして頭に「１」を付した後半データ列とを作成し、これを接続して新たなデータ列を作成すれば、図９(d) に示すように、ｔｒｙ（４）のデータ列を得ることができる。
【００３０】
次に、ステップＳ５の処理の実施例を説明する。この処理は、入力信号の変化の影響を受ける論理ゲートのみに信号を伝播させて出力信号パターンを更新する処理であるが、この実施例では、イベントリストを用意し、影響を受ける論理ゲートをこのイベントリストに入れることにより順次処理を行っている。すなわち、まず、前回とは論理値が異なる特定の入力ビットを直接入力する論理ゲートを所定の評価順にイベントリストに入れる。そして、このイベントリストから先頭の論理ゲートを取り出し、取り出した論理ゲートについて、今回の入力信号パターンに基づく出力値を求め、出力値が前回から変化した場合には、後続の論理ゲートのうちイベントリストに存在しないものを、評価順にイベントリストに追加するという処理を、イベントリストが空になるまで繰り返し実行するのである。
【００３１】
図１０は、この実施例の手順を示す流れ図である。まず、ステップＳ１１において、変化した入力信号を直接入力する論理ゲートを所定の評価順にイベントリストに入れる。ここでは、図４の真理値表に示されている入力信号パターン［２］以降に、この手順を適用した場合の例を述べることにする。入力信号パターンが［１］から［２］に変わったときに変化する入力信号は、入力信号Ｃである。そして、この入力信号Ｃを直接入力する論理ゲートは、図５に示すように、論理ゲート１および２である。そこで、イベントリストには、この２つの論理ゲート１および２が所定の評価順に入れられる。この評価順は、予め所定の方法で定めておく。基本的には、より入力側（上流側）にある論理ゲートを先順とするような評価順を定めればよい。このような評価順の決定方法としては、たとえば、トポロジカルソート法などの方法が知られているので、詳細な説明は省略する。ここでは、図５に示す論理回路について、論理ゲート１，２，３，４の順に評価順が決定されているものとして、以下の説明を進めることにする。結局、ステップＳ１１において、イベントリストには、「論理ゲート１，論理ゲート２」の順にリストアップされることになる。
【００３２】
続くステップＳ１２において、イベントリストが空か否かが判断され、空でなければステップＳ１３へと進むことになる。このステップＳ１３では、イベントリストから先頭の論理ゲートが取り出され、次のステップＳ１４において、取り出した論理ゲートの出力値が求められる。上述の具体例の場合、イベントリストの先頭の論理ゲート１が取り出され、入力信号パターン［２］を与えた場合の出力値「０」が求められる。そして、ステップＳ１５において、この出力値が前回（入力信号パターン［１］を与えたとき）に比べて変化したか否かが判断される。この具体例の場合、論理ゲート１の前回の出力値も「０」であり、出力値は変化していないことになる。そこで、再びステップＳ１２からの処理が実行される。
【００３３】
イベントリストはまだ空ではないので、ステップＳ１２からステップＳ１３へと進み、次の論理ゲート２が取り出される。そして、ステップＳ１４において、入力信号パターン［２］を与えた場合の論理ゲート２についての出力値「１」が求められる。前回の出力値は「０」であるから、出力値に変化が生じていることになる。そこで、ステップＳ１５からステップＳ１６へ進み、後続の論理ゲートのうちイベントリストに存在しないものを、所定の評価順にイベントリストに追加する処理が行われる。上述の具体例の場合、図５に示すように、論理ゲート２には後続する論理ゲート４があり、この論理ゲート４はまだイベントリストには存在しないので、論理ゲート４が新たにイベントリストに追加されることになる。
【００３４】
再びステップＳ１２からステップＳ１３へと進み、イベントリストから論理ゲート４が取り出され、ステップＳ１４において、論理ゲート４についての出力値が求められる。この場合の出力値は「０」であり、前回に比べて変化はない。よって、ステップＳ１５からステップＳ１２へと戻り、この時点でイベントリストは空になっているので、この手順は終了する。このような手順を実行した後、最終的な論理回路の出力値に変化が生じた部分のみを修正し、出力信号パターンの更新を行うことになる。上述の具体例の場合、入力信号パターン［２］についての処理を行った限りでは、最終的な論理回路の出力値に変化は生じないので、更新後の出力信号パターン（出力信号Ｑの値）は更新前のものと同一になる。
【００３５】
【発明の効果】
以上のとおり、本発明に係る真理値表作成装置によれば、組み合わせ論理回路における真理値表を効率良く作成することが可能になる。
【図面の簡単な説明】
【図１】  単純な論理回路の一例を示す回路図である。
【図２】  図１に示す論理回路の真理値表を示す図である。
【図３】  本発明に係る真理値表の作成装置による処理の基本手順を示す流れ図である。
【図４】  図１に示す論理回路の別な真理値表を示す図である。
【図５】  図１に示す論理回路において、入力信号Ｃの変化による影響を受ける部分を示す回路図である。
【図６】  ３ビットの入力信号がある場合の入力信号系列を模擬的に立方体で表現し、８個の頂点を一筆書きで連結する試みに失敗した例を示す図である。
【図７】  ３ビットの入力信号がある場合の入力信号系列を模擬的に立方体で表現し、８個の頂点を一筆書きで連結する試みに成功した例を示す図である。
【図８】  ハミング距離が１となる入力信号系列を作成するためのアルゴリズムを示す図である。
【図９】  図８のアルゴリズムに基づいて、実際に入力信号系列を生成した例を示す図である。
【図１０】  入力信号の変化の影響を受ける論理ゲートのみに信号伝播させて出力信号パターンを更新する処理手順を示す流れ図である。
【符号の説明】
１〜４…論理ゲート
［１］〜［８］（図面上は丸数字）…入力信号パターン
ｔｒｙ（Ｎ）…入力信号系列
【図１】
0003808129.tif 000002
【図２】
0003808129.tif 000003
【図３】
0003808129.tif 000004
【図４】
0003808129.tif 000005
【図５】
0003808129.tif 000006
【図６】
0003808129.tif 000007
【図７】
0003808129.tif 000008
【図８】
0003808129.tif 000009
【図９】
0003808129.tif 000010
【図１０】
0003808129.tif 000011