大規模集積回路における故障の許容性を利用した論理回路の簡単化装置であって、該簡単化装置は、故障箇所集合生成手段と、該故障箇所集合生成手段にて生成された故障箇所のうち、未定領域の許容故障から選択し、未定領域の許容故障の選択終了後、許容領域の故障箇所を選択することにより回路簡単化を行う第1簡単化手段と、多い信号線数を除去できる故障箇所の順に回路簡単化を行う第2簡単化手段と、少ない信号線数を除去できる故障箇所の順に回路簡単化を行う第3簡単化手段と、前記第1ないし第3簡単化手段のうちゲート数、信号線数等において減少数が大きい簡単化手段を選択する選択手段と、該選択手段によって選択された前記第1ないし第3簡単化手段のいずれかにより回路の設計変更を行う回路設計変更手段とを含むことを特徴とする論理回路の簡単化装置大規模集積回路における故障の許容性を利用した論理回路の簡単化方法であって、該簡単化方法は、故障箇所集合生成工程と、該故障箇所集合生成工程にて生成された故障箇所のうち、未定領域の許容故障から選択し、未定領域の許容故障の選択終了後、許容領域の故障箇所を選択することにより回路簡単化を行う第1簡単化工程と、多い信号線数を除去できる故障箇所の順に回路簡単化を行う第2簡単化工程と、少ない信号線数を除去できる故障箇所の順に回路簡単化を行う第3簡単化工程と、前記第1ないし第3簡単化工程のうちゲート数、信号線数等において減少数が大きい簡単化工程を選択する選択工程と、該選択工程によって選択された前記第1ないし第3簡単化工程のいずれかに従って回路の設計変更を行う回路設計変更工程とを含むことを特徴とする論理回路の簡単化方法前述の先行文献には、論理回路の故障テストの後、回路の簡単化をどのような装置又は方法で行うかについて、具体的な記載はない。本発明は、この故障の許容性を利用した回路簡単化に着目し、複数の簡単化手段を設けて、これらを選択して適用することにより、より簡単な論理回路を得る装置及び方法を提供するものである。請求項1に係る簡単化装置は、故障箇所集合生成手段と、該故障箇所集合生成手段にて生成された故障箇所のうち、未定領域の許容故障から選択し、未定領域の許容故障の選択終了後、許容領域の故障箇所を選択することにより回路簡単化を行う第1簡単化手段と、多い信号線数を除去できる故障箇所の順に回路簡単化を行う第2簡単化手段と、少ない信号線数を除去できる故障箇所の順に回路簡単化を行う第3簡単化手段と、前記第1ないし第3簡単化手段のうちゲート数、信号線数等において減少数が大きい簡単化手段を選択する選択手段と、該選択手段によって選択された前記第1ないし第3簡単化手段のいずれかにより回路の設計変更を行う回路設計変更手段とを含むことを特徴とするものである。また請求項2に係る簡単化方法は、故障箇所集合生成工程と、該故障箇所集合生成工程にて生成された故障箇所のうち、未定領域の許容故障から選択し、未定領域の許容故障の選択終了後、許容領域の故障箇所を選択することにより回路簡単化を行う第1簡単化工程と、多い信号線数を除去できる故障箇所の順に回路簡単化を行う第2簡単化工程と、少ない信号線数を除去できる故障箇所の順に回路簡単化を行う第3簡単化工程と、前記第1ないし第3簡単化工程のうちゲート数、信号線数等において減少数が大きい簡単化工程を選択する選択工程と、該選択工程によって選択された前記第1ないし第3簡単化工程のいずれかに従って回路の設計変更を行う回路設計変更工程とを含むことを特徴とするものである。本発明によれば、ゲート数、信号線数を最小限とすることができ、また簡単化回数及び実行時間において、回数及び時間とも他の方法よりも少なくすることができる。図1において、1は、論理回路の除去対象信号線に対応する故障箇所集合Fを生成する故障箇所集合生成手段、2は、故障箇所集合生成手段1にて生成された故障箇所集合Fのうち、未定領域の許容故障から選択し、未定領域の許容故障の選択終了後、許容領域の故障箇所を選択することにより回路簡単化を行う第1簡単化手段、3は、故障箇所集合生成手段1にて生成された故障箇所集合Fのうち、多い信号線数を除去できる故障箇所の順に回路簡単化を行う第2簡単化手段、4は、故障箇所集合生成手段1にて生成された故障箇所集合Fのうち、少ない信号線数を除去できる故障箇所の順に回路簡単化を行う第3簡単化手段、5は、前記第1ないし第3簡単化手段のうちゲート数、信号線数等において減少数が大きい簡単化手段を選択する選択手段である。6は、選択手段5によって選択された第1ないし第3簡単化手段2~4のいずれかにより回路の設計変更を行う回路設計変更手段である。これらはいずれもコンピュータによって処理される。故障箇所集合生成手段1にて生成された故障箇所集合Fは、それぞれ第1ないし第3簡単化手段2~4に入力され、それぞれ簡単化処理され、その結果が選択手段5に入力されて、最適な簡単化手段、すなわちゲート数、信号線数を最小限とすることができ、また簡単化回数及び実行時間において、回数及び時間とも他の方法よりも少なくすることができる簡単化手段が選択される。ゲート数、信号線数等判断項目は、総合的に判断され選択される。この選択手段5により選択された第1ないし第3簡単化手段2~4のいずれかの手段にしたがって回路設計変形手段6にて回路が簡単化される。第1ないし第3簡単化手段2~4では、以下のようなフローによる処理がなされる。第1簡単化手段2を例に、図2を参照して説明する。簡単化処理スタートにより、故障集合Fの許容性を判定するため故障箇所集合Fが生成されるS1。次いで故障集合Aが空か否かが反転される。空であれば終了、空でなければ、第1簡単化手段2による処理、すなわち未定領域の後に許容領域にあるものがくるように故障集合Aを整列する。故障集合A内の先頭故障に基く回路の簡単化を行う。続いて簡単化により削除された故障を故障集合Fから除去する。その後S1に戻って、同様の処理が故障集合Aが空になるまで繰り返される。第2簡単化手段3においては、S3における処理が、1つの故障箇所から削除される信号線が多い順に整列する処理とされ、第3簡単化手段4においては、同様にS3における処理が、1つの故障箇所から削除される信号線が少ない順に整列される処理とされる。他の処理工程は共通である。以下、本発明実施の形態を詳述する。許容故障許容故障は大きく分けて誤りの深刻さに基づくものと誤りの発生頻度に基づくものがある。ここでは誤りの深刻さに基づく許容故障に着目する。テスト対象回路Cとその故障集合をF、入力値xに対する出力値zとする。ここで、出力はnビットとし、出力値は、下記数式にて、非負整数を表現することとする。同様に、故障fをもつ故障回路Cfの入力xに対する出力値はzfと表現する。このとき、入力xを印加したときの誤りの大きさefは、故障fを持つ回路の出力値zfと正常回路の出力値zとの差は、下記数式で表される。図3は0縮退故障f1をもつ故障回路である。縮退故障f1を有する回路をCf1と表記する。出力z0における信号値01は、正常時の値が0、故障時の値が1であることを表現している。つまり、入力値をこの回路に入力したとき、故障時の出力は、正常時の出力はとなり、その誤りの大きさは、下記数式にて表される。入力値集合Xが与えられたとき、故障fのエラーの深刻さEは、下記数式で定義される。図3の回路における0縮退故障f1では、すべての入力値の集合に対して誤りの大きさef1が最大値であるため、誤りの深刻さEは3となる。誤りの深刻さに基づく許容故障もし故障fの誤りの深刻さEが閾値Tよりも小さければT、故障fは閾値Tのもとで許容できる。反対に、もし故障fの誤りの深刻さEが閾値T以下等しい場合を含むであれば、故障fは閾値Tのもとで許容できないことになる。図3及び図4に示した2つの故障f1は3であるため、故障f1は許容故障である。一方、故障f2に対しては誤りの大きさがとなるテストパターンが存在することから誤りの深刻さEf2がTより大きくなるため、故障f2は非許容故障である。誤りの深刻さに基づく許容故障の判定は、閾値テスト生成アルゴリズムによりテスト生成を行うことで可能となる。閾値テスト生成アルゴリズムは故障の影響を外部出力に伝えるテストベクトルを探索するだけではなく、その誤りの大きさもあわせて評価するアルゴリズムである。ある故障に対して閾値T以上の誤りを出力するテストベクトルが存在しないことがこのアルゴリズムにより証明されれば、その故障は閾値Tのもとで許容となる。これは冗長故障の判定が一般的なテスト生成アルゴリズムを用いてテストパターンが存在しないことを証明して行われていることと同様である。許容故障に基づく回路簡単化縮退故障fを持つ故障回路Cfは、その故障値が影響する信号線をその故障値で固定することにより得られる簡単化された回路Cfと等価である。例えば、図5は、図3に示す故障f1に基づいて簡単化した回路である。図3と図5を比べれば、故障f1の存在する信号線がつながる2つのNANDゲートの出力が信号値1に縮退し、その結果、この2つのNANDゲートを含む3つのゲートが除去され、それに伴い図3の太線で示した信号線aが除去されていることがわかる。組合せ回路Cにおける故障frが冗長故障であれば、冗長故障の定義から故障回路CfrとCが等価であるため、その故障に基づいて簡単化された回路Cfrと回路Cも等価となる。同様に、組合せ回路Cにおける故障faが閾値Tのもとで許容できる場合、故障回路CfaとCの出力値の差は閾値T以下であるため、簡単化後、回路CfaとCの出力値の差も閾値T以下となる。このとき、回路CfaとCは閾値Tのもとで等価と呼ぶ。図3と図5に示す2つの回路は閾値Tが4のもとで等価である。許容故障判定と簡単化アルゴリズム組合せ回路Cと閾値Tが与えられたとき、故障の許容性に基づいて最も回路素子数が少ない回路を得る方法について述べる。一般には、回路Cに複数の単一縮退故障が存在しても、すなわち多重縮退故障が存在しても許容できるため、許容できる多重縮退故障の中でより多くの回路素子数を削減できる多重故障を見つけることによってなされる。図6において、回路に2つの多重故障m1m2が存在するとする。これらはどちらも閾値Tが4のもとで許容できる多重故障である。この2つの多重故障に基づいて簡単化した回路をそれぞれ図7及び図8に示す。この場合、図7に示す回路の方がゲート数および信号線数共に少ないため、許容できる多重故障m1に基づいて簡単化する方が良い。なお、この例ではこの多重故障m1に基づいて簡単化した回路が、最も回路素子数が小さい回路となる。一般に、単一縮退故障の許容性から、多重許容故障の許容性を判断することはできない。例えば、図6に示す故障f1とf3は、それぞれの単一故障を考えるとどちらも閾値Tが3のもとでも許容故障であるが、多重故障故障m3は閾値3のもとでは許容できない。なぜなら、入力xの時に出力zfであり、正常時の出力zとの差が3となり、閾値以上となるからである。これは冗長故障でも同じことが言えるため、冗長故障に基づく回路簡単化は、本質的に1つの単一冗長故障を除去する度に、冗長故障判定を繰り返すことを行っている。本発明におけるアルゴリズムも同様に1つの単一許容故障に基づいて回路を簡単化するごとに、許容故障を再度判定し直す。ただし、以下に述べるように、冗長故障に基づく回路簡単化で行われている冗長判定の考え方は、そのまま許容性の判定のために導入できないため、故障の許容性の判定は異なる方法で行う。冗長故障に基づく回路簡単化において、回路Cを冗長故障f1に基づいて簡単化した回路をCf1とする。このときCとCf1は等価であるため、回路Cf1をこの回路Cf1における冗長故障f2’で簡単化した回路Cf1f2’はCと等価である。このように、冗長故障に基づく回路簡単化では、簡単化された回路に対してテスト生成を行うことで故障の冗長性を判定すればよい。一方、許容故障に基づく回路簡単化では、簡単化した回路に対して、故障の許容性を判定した場合、正しく判定できない可能性がある。回路Cにおける閾値Tのもとでの許容故障f1に基づいて、Cを簡単化した回路をCf1とする。このときCとCf1は閾値Tのもとで等価である。さらに、回路Cf1上で閾値Tのもとで許容できる故障f2’が見つかり、これに基づいて簡単化を行ったとする。このとき、回路Cf1の出力と故障回路Cf1f2′は閾値Tのもとで等価であるが、回路Cと故障回路Cf1f2′との出力誤差は閾値以下であることは保証できないため、閾値Tのもとで等価かどうかは不明である。図9は、図6に示す回路の故障f1に基づいて簡単化した回路C1f1である。この回路C1f1の信号線z1上の故障f3′は、C1f1に対しては閾値3のもとで許容であるが、先に述べたように、回路C1において多重故障f1f3は閾値3のもとで許容ではない。よって、図7に示すような回路C1f1を故障f3’に基づいて簡単化した回路C1f1f3′は、回路C1と閾値3のもとで等価ではない。表1にこの3つの回路C1、C1f1、C1f1f3′の全出力と誤りの大きさを示す。この出力を見るとC1f1とC1f1f3′の出力差は、Tが3以下であるが、回路C1と故障回路C1f1f3′の差は入力000の時に3となり、閾値3以上になることがわかる。本発明におけるアルゴリズムでは、回路Cをk-1個の許容故障に基づいて簡単化した下記数式11で示す回路に対して、次の簡単化の対象となる故障fkを見つけるために、回路C上の多重故障f1f2...fk1fkに対して、閾値テスト生成を行い、この多重故障が許容かどうか判定する。多重故障が許容であれば、故障fkに基づいて、数式11に示す回路をさらに簡単化する。そのアルゴリズムを以下に示す。故障の許容性に基づく回路簡単化入力組合せ回路C、単一故障集合F、閾値T。1選択した多重故障Mφ、簡単化した回路CoCとする。2故障集合Fが空になるまで次を繰り返す。3すべての故障f∈Fに対して、4多重故障M∪fがCにおいて許容故障かどうか判定する。5許容故障ならば、AA∪f。6もし、Aφならば、Coを返して終了。7Aから1つの単一許容故障f′を選択。8Coをf′に基づいて簡単化。9FをCoの故障リストに更新。10Coを返す。7行目でどの許容故障を選択するかによって、最終的に得られる回路のゲート数および信号線数が異なる。次に、信号線の選択基準について説明する。許容故障の選択基準前述したアルゴリズに従って回路を簡単化することで最終的に多くの信号線を除去するためには、1回の除去で削除できる信号線を多くすることと、1つの故障から行う削減の回数をできるだけ増やすことが望ましい。ここでは、後者を実現するための1つの方法を説明する。許容故障の選択基準は、故障が次に示す3つの領域のどの信号線上にあるのかによってその優先度を変えるものである。3つの領域の定義は以下の通りである。なお、回路Cの出力はnビットとし、出力値zは、下記数式12で示すように非負整数を表す。非許容領域下記数式13で示す外部出力のいずれかにのみ到達可能な信号線集合。ここで、許容領域下記数式15で示す外部出力のいずれかにのみ到達可能な信号線集合。ここで、未定領域許容領域、非許容領域以外の信号線集合。図10は図6に示す回路C1における閾値4の時の3つの領域を示している。閾値4のとき、kuaka2であるため、外部出力z0、z1のみに到達可能な信号線は許容領域に含まれ、外部出力z2、z3のみに到達可能な信号線は非許容領域に含まれる。許容領域の信号線上の故障は、回路構造からその誤りの大きさが必ず閾値T以下になるため、閾値Tのもとで許容である。同様に、非許容領域内の故障もその誤りの大きさが必ず閾値T以上になるため、必ず閾値Tのもとで非許容であると言える。また、許容領域内の故障集合の任意の部分集合からなる多重故障に基づいて簡単化した回路は、元の回路と閾値Tのもとで等価であるため、これらの許容故障は同時に除去することが可能である。ここで1つの選択基準として未定領域の許容故障から選択し、未定領域内の許容故障がなくなれば許容領域の故障を選択することとする第1簡単化手段及び方法。未定領域の許容故障は、許容領域の故障に基づいて回路を簡単化した後では非許容になる場合が多いため、このような選択をすると、簡単化できる回数が増加することが期待できる。図6に示す回路C1上の故障f1、f2、f3、f4を再度説明する。これらはそれぞれ単一縮退故障として閾値T4のもとで許容である。許容領域内にある故障からなる多重故障f3f4も閾値Tのもとで許容であるため、これらを除去して回路を簡単化できる。しかし、簡単化後の回路では許容故障は存在しないため、これ以上の簡単化はできない。一方、非許容領域の故障f1は閾値Tのもとで許容であるため簡単化した回路は元の回路と閾値Tのもとで等価であるが、その簡単化後の回路においても故障f3に対応する故障f3′は閾値Tのもとで許容できるため、さらに簡単化が可能であり、最終的に図7に示す回路C1f1f3を得ることができる。各領域内の故障を選択するとき、対象となる故障の中で最も多くの信号線数を除去できる故障を選択することにより、1回の簡単化で除去できる信号線数をできるだけ大きくする第2簡単化手段及び方法。すなわち許容故障選択アルゴリズは次のように表される。許容故障選択アルゴリズム入力許容故障集合A、簡単化後回路Co1Aを許容領域の集合Aaと未定領域の故障Auに分ける。2もし、Au≠φならば、3すべての故障f∈Auに対して、回路Coを故障fに基づいて簡単化した回路を求め、最も多くの信号線を除去できる故障fmを求める。4fmを返して終了。5もし、Aa≠φならば、6すべての故障f∈Aaに対して、回路Coを故障fに基づいて簡単化した回路を求め、最も多くの信号線を除去できる故障fmを求める。fmを返して終了。ISCAS85のベンチマーク回路c880、c2670、c7552に対して、本発明を適用した場合における回路簡単化の効果について、表2を参照して述べる。閾値テスト生成アルゴリズムはPODEMベースのアルゴリズムを用い、C言語で実装した。このアルゴリズムは単一縮退故障を対象としているが、本発明に係る回路簡単化装置及び方法のアルゴリズムでは多重故障の許容性を判定する必要があるために多重故障を単一故障に変換する回路変換を行い、多重故障の許容性判定を単一縮退故障のそれに帰着させた。実験にはAppleMacminiを用いた。表2は、回路簡単化前と後のゲート数、信号線数、さらに簡単化回数と実行時間を示している。表中、手段1が第1簡単化手段を、手段2が第2簡単化手段を、手段3が第3簡単化手段による処理結果を示す。閾値は8を用いた。また本発明の有効性を確認するために、許容領域の故障を優先的に選択するアルゴリズムとを入れ換えたもの、領域逆、領域は考えずに最も多くの信号線を除去できる故障順第2簡単化手段及び方法、領域は考えずに最も少ない信号線を除去する故障順の結果第3簡単化手段及び方法を示す。この表から、c7552では本発明方法が最も良い結果を示していることがわかる。すなわちゲート数、信号線数ともにオリジナル回路より大きく減少している。これは目標とした回路簡単化の回数を増やせたことが1つの原因である。なお、手段3面積昇順による方法でも同様に回路簡単化回数が多いが、この方法では1回あたりに除去できる信号線数が小さいため、最終的な信号線数やゲート数は提案手法よりも大きい結果になっている。すなわち、変換回数を増やしつつ、より面積削減効果が大きな許容故障を選ぶことができる。一方で、c880、c2670では4つの手段に差は見られなかった。これらの回路では未定領域内に単一許容故障が存在していないため、差が生じない。処理時間については、手段1の逆領域逆が最も良いことがわかる。これは簡単化回数が少ないこと、そして許容領域内の多重故障の許容性は判定するまでもなく、許容故障であることがすぐに分かるためである。なお、処理時間が大きいものは、閾値テスト生成を行っている時間がその大半を占めている。