論理回路の簡単化装置及び簡単化方法
【課題】ゲート数、信号線数を最小限とすることができ、また簡単化回数及び実行時間において、回数及び時間とも他の方法よりも少なくすることができる論理回路の簡単化装置及び簡単化方法を提供する。
【解決手段】故障の許容性を利用した論理回路の簡単化装置であって、故障箇所集合生成手段と、故障箇所集合生成手段にて生成された故障箇所のうち、未定領域の許容故障から選択し、未定領域の許容故障の選択終了後、許容領域の故障箇所を選択することにより回路簡単化を行う第１簡単化手段と、多い信号線数を除去できる故障箇所の順に回路簡単化を行う第２簡単化手段と、少ない信号線数を除去できる故障箇所の順に回路簡単化を行う第３簡単化手段と、これらの簡単化手段のうちゲート数、信号線数等において減少数が大きいものを選択する選択手段と、選択されたこれらの手段のいずれかにより回路の設計変更を行う回路設計変更手段にて構成される。
【解決手段】故障の許容性を利用した論理回路の簡単化装置であって、故障箇所集合生成手段と、故障箇所集合生成手段にて生成された故障箇所のうち、未定領域の許容故障から選択し、未定領域の許容故障の選択終了後、許容領域の故障箇所を選択することにより回路簡単化を行う第１簡単化手段と、多い信号線数を除去できる故障箇所の順に回路簡単化を行う第２簡単化手段と、少ない信号線数を除去できる故障箇所の順に回路簡単化を行う第３簡単化手段と、これらの簡単化手段のうちゲート数、信号線数等において減少数が大きいものを選択する選択手段と、選択されたこれらの手段のいずれかにより回路の設計変更を行う回路設計変更手段にて構成される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、大規模集積回路における故障の許容性を利用した論理回路の簡単化装置及び簡単化方法に関する。
【背景技術】
【０００２】
近年のLSIの微細化、高性能化に伴いLSIの用途は幅広くなっており、求められる信頼性も様々である。医療機器や金融システムなどのように、高い信頼性が必要なシステムもある一方、それほど高い信頼性を求められないシステム、例えば、オーディオ、画像処理システム、ゲーム機などがあり、そのようなシステムにおいて故障が存在してもわずかな誤りならば目的とする処理に重大な影響を及ぼさない場合も多い（非特許文献１ないし４）。このような、目的とする処理に与える影響が許容できる範囲の故障を許容故障と呼ぶ。
【０００３】
故障の許容性を考慮することで、実効歩留まりの向上（非特許文献２）、耐故障設計のコスト削減（非特許文献５）などの効果が期待できる。さらに、故障の許容性を利用した回路簡単化も提案されている（非特許文献６）。これは組合せ回路の冗長な縮退故障を見つけることにより、回路内の冗長信号線を見つけ除去する方法（非特許文献７）と同様に、回路内の冗長故障を判定し、その故障が存在する部分回路を除去する方法である。このような部分回路除去を行ったとしても、元の回路と除去後の回路の出力差は許容範囲内であることが保証される。よって、ある一定の精度を保証するための回路を効率的に設計する目的や、設計した回路から精度を落とした低精度の回路を再設計するという目的に利用できる。
【０００４】
また、被テスト論理回路をテストする論理回路テスト装置及びテスト方法は公知である（特許文献１）。このテスト装置及び方法は、端子数の少ない論理回路テスト装置においてもオリジナルなテストパターンと同等なテストを可能とするものである。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】S.Shahidi and Sandeep K.Gupta,”A Theory OfError Rate Testing”,Proc. ICCD.pp.438 〜445.2006
【非特許文献２】Z.Jiang and S.K.Gupta.”An ATPG for Threshold Testing:Obtaining Acceptable Yieldin Future Processes.”Proc.ITC.pp.824〜833.2002.
【非特許文献３】張、安浦、”算術演算回路における許容故障とチップコスト削減への応用”、第50回FTC研究会資料、2004.
【非特許文献４】K. J.Lee,T. Y Hsieth,and M.A,Breuer,”Reduction of detected acceptable faultsfor yield improvement via error tolerance,”Proc.DATE,pp.1599~1604,2007.
【非特許文献５】I.Polian,D.Nowroth,and B.Becker,”Identification of Critical Errors in ImagingApplications,”Proc.IOLTS,pp.201〜202,2007.
【非特許文献６】D.Shin and S.K.Gupta,“A new circuit simplification method for error tolerantapplications,”Proc.DATE,pp.1〜6,2011.
【非特許文献７】S.Kajihara,H.Shiba,K.Kinoshita,”Removal of redundancy in logic circuits underclassification of undetectable faults,”Digest Papers of FTCS 22,pp.263〜270,1992.
【特許文献】
【０００６】
【特許文献１】特開２００４−１１７３０５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
前述の先行文献には、論理回路の故障テストの後、回路の簡単化をどのような装置又は方法で行うかについて、具体的な記載はない。
【０００８】
本発明は、この故障の許容性を利用した回路簡単化に着目し、複数の簡単化手段を設けて、これらを選択して適用することにより、より簡単な論理回路を得る装置及び方法を提供するものである。
【課題を解決するための手段】
【０００９】
請求項１に係る簡単化装置は、故障箇所集合生成手段と、該故障箇所集合生成手段にて生成された故障箇所のうち、未定領域の許容故障から選択し、未定領域の許容故障の選択終了後、許容領域の故障箇所を選択することにより回路簡単化を行う第１簡単化手段と、多い信号線数を除去できる故障箇所の順に回路簡単化を行う第２簡単化手段と、少ない信号線数を除去できる故障箇所の順に回路簡単化を行う第３簡単化手段と、前記第１ないし第３簡単化手段のうちゲート数、信号線数等において減少数が大きい簡単化手段を選択する選択手段と、該選択手段によって選択された前記第１ないし第３簡単化手段のいずれかにより回路の設計変更を行う回路設計変更手段とを含むことを特徴とするものである。
【００１０】
また請求項２に係る簡単化方法は、故障箇所集合生成工程と、該故障箇所集合生成工程にて生成された故障箇所のうち、未定領域の許容故障から選択し、未定領域の許容故障の選択終了後、許容領域の故障箇所を選択することにより回路簡単化を行う第１簡単化工程と、多い信号線数を除去できる故障箇所の順に回路簡単化を行う第２簡単化工程と、少ない信号線数を除去できる故障箇所の順に回路簡単化を行う第３簡単化工程と、前記第１ないし第３簡単化工程のうちゲート数、信号線数等において減少数が大きい簡単化工程を選択する選択工程と、該選択工程によって選択された前記第１ないし第３簡単化工程のいずれかに従って回路の設計変更を行う回路設計変更工程とを含むことを特徴とするものである。
【発明の効果】
【００１１】
本発明によれば、ゲート数、信号線数を最小限とすることができ、また簡単化回数及び実行時間において、回数及び時間とも他の方法よりも少なくすることができる。
【図面の簡単な説明】
【００１２】
【図１】本発明実施の形態に係る論理回路の簡単化装置及び簡単化方法を説明するための概略図である。
【図２】第１ないし第３簡単化手段を説明するためのフローチャートである。
【図３】０縮退故障f1をもつ故障回路図である。
【図４】１縮退故障f2をもつ故障回路図である。
【図５】図３に示す故障f1に基づいて簡単化した回路図である。
【図６】多重故障（f1,f3）、（f2,f4）を有する回路図である。
【図７】多重故障（f1,f3）に基いて簡単化した回路図である。
【図８】多重故障（f2,f4）に基いて簡単化した回路図である。
【図９】図６に示す回路の故障f1に基いて簡単化した回路図である。
【図１０】図６に示す回路において閾値T＝４のときの許容領域、非許容領域及び未定領域を示す回路図である。
【発明を実施するための形態】
【００１３】
図１において、１は、論理回路の除去対象信号線に対応する故障箇所集合Fを生成する故障箇所集合生成手段、２は、故障箇所集合生成手段１にて生成された故障箇所集合Fのうち、未定領域の許容故障から選択し、未定領域の許容故障の選択終了後、許容領域の故障箇所を選択することにより回路簡単化を行う第１簡単化手段、３は、故障箇所集合生成手段１にて生成された故障箇所集合Fのうち、多い信号線数を除去できる故障箇所の順に回路簡単化を行う第２簡単化手段、４は、故障箇所集合生成手段１にて生成された故障箇所集合Fのうち、少ない信号線数を除去できる故障箇所の順に回路簡単化を行う第３簡単化手段、５は、前記第１ないし第３簡単化手段のうちゲート数、信号線数等において減少数が大きい簡単化手段を選択する選択手段である。６は、選択手段５によって選択された第１ないし第３簡単化手段２〜４のいずれかにより回路の設計変更を行う回路設計変更手段である。これらはいずれもコンピュータによって処理される。
【００１４】
故障箇所集合生成手段１にて生成された故障箇所集合Fは、それぞれ第１ないし第３簡単化手段２〜４に入力され、それぞれ簡単化処理され、その結果が選択手段５に入力されて、最適な簡単化手段、すなわちゲート数、信号線数を最小限とすることができ、また簡単化回数及び実行時間において、回数及び時間とも他の方法よりも少なくすることができる簡単化手段が選択される。ゲート数、信号線数等判断項目は、総合的に判断され選択される。この選択手段５により選択された第１ないし第３簡単化手段２〜４のいずれかの手段にしたがって回路設計変形手段６にて回路が簡単化される。
【００１５】
第１ないし第３簡単化手段２〜４では、以下のようなフローによる処理がなされる。第１簡単化手段２を例に、図２を参照して説明する。簡単化処理スタートにより、故障集合Fの許容性を判定するため故障箇所集合Fが生成される（S1）。次いで故障集合Aが空か否かが反転される(S2)。空であれば終了、空でなければ、第１簡単化手段２による処理、すなわち未定領域の後に許容領域にあるものがくるように故障集合Aを整列する(S3)。故障集合A内の先頭故障に基く回路の簡単化を行う(S4)。続いて簡単化により削除された故障を故障集合Fから除去する(S5)。その後S１に戻って、同様の処理が故障集合Aが空になるまで繰り返される。
【００１６】
第２簡単化手段３においては、S3における処理が、１つの故障箇所から削除される信号線が多い順に整列する処理とされ、第３簡単化手段４においては、同様にS3における処理が、１つの故障箇所から削除される信号線が少ない順に整列される処理とされる。他の処理工程は共通である。
以下、本発明実施の形態を詳述する。
【００１７】
（許容故障）
許容故障は大きく分けて誤りの深刻さに基づくものと誤りの発生頻度に基づくものがある。ここでは誤りの深刻さに基づく許容故障に着目する。テスト対象回路C(図３)とその故障集合をF、入力値xに対する出力値z(x)とする。ここで、出力はnビットとし、出力値は、下記数式にて、非負整数を表現することとする。
【００１８】
【数１】
【００１９】
同様に、故障f(∈F)をもつ故障回路Cfの入力xに対する出力値はzf(x)と表現する。このとき、入力xを印加したときの誤りの大きさef(x)は、故障f(∈F)を持つ回路の出力値zf(x)と正常回路の出力値z(x)との差は、下記数式で表される。
【００２０】
【数２】
【００２１】
図３は0縮退故障f1(stuck at
0)をもつ故障回路である。縮退故障f1を有する回路をC f1と表記する。出力z0における信号値0/1は、正常時の値が0、故障時の値が1であることを表現している。つまり、入力値
【００２２】
【数３】
【００２３】
をこの回路に入力したとき、故障時の出力は、
【００２４】
【数４】
【００２５】
正常時の出力は(1,1,1,1,0)となり、その誤りの大きさは、下記数式にて表される。
【００２６】
【数５】
【００２７】
入力値集合Xが与えられたとき、故障fのエラーの深刻さE(f)は、下記数式で定義される。
【００２８】
【数６】
【００２９】
図３の回路における0縮退故障f1では、すべての入力値の集合に対して誤りの大きさef1(0,1,0,1)が最大値であるため、誤りの深刻さE(f1)は3となる。
【００３０】
（誤りの深刻さに基づく許容故障）
もし故障fの誤りの深刻さE(f)が閾値Tよりも小さければ(E(f)<T)、故障fは閾値Tのもとで許容できる。反対に、もし故障fの誤りの深刻さE(f)が閾値T以下（等しい場合を含む）であれば、故障fは閾値Tのもとで許容できないことになる。
【００３１】
図３及び図４に示した2つの故障f1(stuck
at 0）とf2(stuck at 1）の故障の閾値Tを4としたときの許容性について述べる。故障f1の故障の深刻さE(f1)は3であるため、故障f1は許容故障である。一方、故障f2に対しては誤りの大きさが
【００３２】
【数７】
【００３３】
となるテストパターン(1,0,0,0)が存在することから誤りの深刻さEf2がTより大きくなるため、故障f2は非許容故障である。
【００３４】
誤りの深刻さに基づく許容故障の判定は、閾値テスト生成アルゴリズムによりテスト生成を行うことで可能となる。閾値テスト生成アルゴリズムは故障の影響を外部出力に伝えるテストベクトルを探索するだけではなく、その誤りの大きさもあわせて評価するアルゴリズムである。ある故障に対して閾値T以上の誤りを出力するテストベクトルが存在しないことがこのアルゴリズムにより証明されれば、その故障は閾値Tのもとで許容となる。これは冗長故障の判定が一般的なテスト生成アルゴリズムを用いてテストパターンが存在しないことを証明して行われていることと同様である。
【００３５】
（許容故障に基づく回路簡単化）
縮退故障fを持つ故障回路Cfは、その故障値が影響する信号線をその故障値で固定することにより得られる簡単化された回路Cfと等価である。例えば、図５は、図３に示す故障f1に基づいて簡単化した回路である。図３と図５を比べれば、故障f1の存在する信号線がつながる2つのNANDゲートの出力が信号値1に縮退し、その結果、この2つのNANDゲートを含む3つのゲートが除去され、それに伴い図３の太線で示した信号線aが除去されていることがわかる。
【００３６】
組合せ回路Cにおける故障frが冗長故障であれば、冗長故障の定義から故障回路CfrとCが等価(すべての対応する出力関数が等価)であるため、その故障に基づいて簡単化された回路Cfrと回路Cも等価となる。
【００３７】
同様に、組合せ回路Cにおける故障faが閾値Tのもとで許容できる場合、故障回路CfaとCの出力値の差(エラー)は閾値T以下であるため、簡単化後、回路CfaとCの出力値の差も閾値T以下となる。このとき、回路CfaとCは「閾値Tのもとで等価」と呼ぶ。図３と図５に示す2つの回路は閾値Tが4のもとで等価である。
【００３８】
（許容故障判定と簡単化アルゴリズム）
組合せ回路Cと閾値Tが与えられたとき、故障の許容性に基づいて最も回路素子数が少ない回路を得る方法について述べる。一般には、回路Cに複数の単一縮退故障が存在しても、すなわち多重縮退故障が存在しても許容できるため、許容できる多重縮退故障の中でより多くの回路素子数を削減できる多重故障を見つけることによってなされる。
【００３９】
図６において、回路に2つの多重故障m1,m2
【００４０】
【数８】
【００４１】
【数９】
【００４２】
が存在するとする。これらはどちらも閾値Tが4のもとで許容できる多重故障である。この2つの多重故障に基づいて簡単化した回路をそれぞれ図７及び図８に示す。この場合、図７に示す回路の方がゲート数および信号線数共に少ないため、許容できる多重故障m1に基づいて簡単化する方が良い。なお、この例ではこの多重故障m1に基づいて簡単化した回路が、最も回路素子数が小さい回路となる。
【００４３】
一般に、単一縮退故障の許容性から、多重許容故障の許容性を判断することはできない。例えば、図６に示す故障f1とf3は、それぞれの単一故障を考えるとどちらも閾値Tが3のもとでも許容故障であるが、多重故障故障m3
【００４４】
【数１０】
【００４５】
は閾値3のもとでは許容できない。なぜなら、入力x=(1,1,1)の時に出力zf(1,1,1)=(1,1,0,0)であり、正常時の出力z(1,1,1)=(1,1,1,1)との差が3となり、閾値以上となるからである。
【００４６】
これは冗長故障でも同じことが言えるため、冗長故障に基づく回路簡単化は、本質的に1つの単一冗長故障を除去する度に、冗長故障判定を繰り返すことを行っている。
【００４７】
本発明におけるアルゴリズムも同様に1つの単一許容故障に基づいて回路を簡単化するごとに、許容故障を再度判定し直す。ただし、以下に述べるように、冗長故障に基づく回路簡単化で行われている冗長判定の考え方は、そのまま許容性の判定のために導入できないため、故障の許容性の判定は異なる方法で行う。
【００４８】
冗長故障に基づく回路簡単化において、回路Cを冗長故障f1に基づいて簡単化した回路をCf1とする。このときCとCf1は等価であるため、回路Cf1をこの回路Cf1における冗長故障f2’で簡単化した回路C{f1,f2’} はCと等価である。このように、冗長故障に基づく回路簡単化では、簡単化された回路に対してテスト生成を行うことで故障の冗長性を判定すればよい。
【００４９】
一方、許容故障に基づく回路簡単化では、簡単化した回路に対して、故障の許容性を判定した場合、正しく判定できない可能性がある。回路Cにおける閾値Tのもとでの許容故障f1に基づいて、Cを簡単化した回路をCf1とする。このときCとCf1は閾値Tのもとで等価である。さらに、回路Cf1上で閾値Tのもとで許容できる故障f2’が見つかり、これに基づいて簡単化を行ったとする。このとき、回路Cf1の出力と故障回路C{f1,f2′}は閾値Tのもとで等価であるが、回路Cと故障回路C{f1,f2′}との出力誤差は閾値以下であることは保証できないため、閾値Tのもとで等価かどうかは不明である。
【００５０】
図９は、図６に示す回路の故障f1に基づいて簡単化した回路C1f1である。この回路C1f1の信号線z1上の故障f3′(回路C1の故障f3に対応)は、C1f1に対しては閾値3のもとで許容であるが、先に述べたように、回路C1において多重故障{ f1, f3}は閾値 3のもとで許容ではない。よって、図７に示すような回路C1f1を故障f3’に基づいて簡単化した回路C1{f1,f3′}は、回路C1と閾値3のもとで等価ではない。
【００５１】
表1にこの3つの回路C1、C1f1、C1{f1,f3′}の全出力と誤りの大きさを示す。この出力を見るとC1f1 とC1{f1,f3′}の出力差は、Tが3以下であるが、回路C1と故障回路C1{f1,f3′}の差は入力000の時に3となり、閾値3以上になることがわかる。
【表１】
【００５２】
本発明におけるアルゴリズムでは、回路Cをk−1個の許容故障に基づいて簡単化した下記数式１１で示す回路に対して、次の簡単化の対象となる故障fkを見つけるために、回路C上の多重故障{f1,f2…fk-1,fk}に対して、閾値テスト生成を行い、この多重故障が許容かどうか判定する。多重故障が許容であれば、故障fkに基づいて、数式１１に示す回路をさらに簡単化する。そのアルゴリズムを以下に示す。
【００５３】
【数１１】
【００５４】
（故障の許容性に基づく回路簡単化）
入力:組合せ回路C、単一故障集合F、閾値T。
1 (1)選択した多重故障M=φ、簡単化した回路Co=Cとする。
2 (2)故障集合Fが空になるまで次を繰り返す。
3 (2-1)すべての故障f∈Fに対して、
4 (2-1-1)多重故障M∪fがCにおいて許容故障かどうか判定する。
5 (2-1-2)許容故障ならば、A=A∪{f}。
6 (2-2)もし、A=φならば、Coを返して終了。
7 (2-3)Aから1つの単一許容故障f′を選択。
8 (2-4)Coをf′に基づいて簡単化。
9 (2-5)FをCoの故障リストに更新。
10 (3)Coを返す。
7行目でどの許容故障を選択するかによって、最終的に得られる回路のゲート数および信号線数が異なる。
次に、信号線の選択基準について説明する。
【００５５】
（許容故障の選択基準）
前述したアルゴリズに従って回路を簡単化することで最終的に多くの信号線を除去するためには、1回の除去で削除できる信号線を多くすることと、1つの故障から行う削減の回数(2行目から9行目までのループの回数)をできるだけ増やすことが望ましい。ここでは、後者を実現するための1つの方法を説明する。
【００５６】
許容故障の選択基準は、故障が次に示す3つの領域のどの信号線上にあるのかによってその優先度を変えるものである。3つの領域の定義は以下の通りである。なお、回路Cの出力はnビットとし、出力値z(x)は、下記数式１２で示すように非負整数を表す。
【００５７】
【数１２】
【００５８】
「非許容領域」
下記数式１３で示す外部出力のいずれかにのみ到達可能な信号線集合。ここで、
【００５９】
【数１３】
【００６０】
【数１４】
【００６１】
「許容領域」
下記数式１５で示す外部出力のいずれかにのみ到達可能な信号線集合。ここで、
【００６２】
【数１５】
【００６３】
【数１６】
【００６４】
「未定領域」
許容領域、非許容領域以外の信号線集合。
【００６５】
図１０は図６に示す回路C1における閾値4の時の3つの領域を示している。閾値4のとき、kua=ka=2であるため、外部出力z0、z1のみに到達可能な信号線は許容領域に含まれ、外部出力z2、z3のみに到達可能な信号線は非許容領域に含まれる。
【００６６】
許容領域の信号線上の故障は、回路構造からその誤りの大きさが必ず閾値T以下になるため、閾値Tのもとで許容である。同様に、非許容領域内の故障もその誤りの大きさが必ず閾値T以上になるため、必ず閾値Tのもとで非許容であると言える。また、許容領域内の故障集合の任意の部分集合からなる多重故障に基づいて簡単化した回路は、元の回路と閾値Tのもとで等価であるため、これらの許容故障は同時に除去することが可能である。
【００６７】
ここで1つの選択基準として未定領域の許容故障から選択し、未定領域内の許容故障がなくなれば許容領域の故障を選択することとする（第１簡単化手段及び方法）。未定領域の許容故障は、許容領域の故障に基づいて回路を簡単化した後では非許容になる場合が多いため、このような選択をすると、簡単化できる回数が増加することが期待できる。
【００６８】
図６に示す回路C1上の故障f1、f2、f3、f4を再度説明する。これらはそれぞれ単一縮退故障として閾値T=4のもとで許容である。許容領域内にある故障からなる多重故障{f3,f4}も閾値Tのもとで許容であるため、これらを除去して回路を簡単化できる。しかし、簡単化後の回路では許容故障は存在しないため、これ以上の簡単化はできない。
【００６９】
一方、非許容領域の故障f1は閾値Tのもとで許容であるため簡単化した回路は元の回路と閾値Tのもとで等価であるが、その簡単化後の回路においても故障f3に対応する故障f3′は閾値Tのもとで許容できるため、さらに簡単化が可能であり、最終的に図７に示す回路C1{f1,f3}を得ることができる。
【００７０】
各領域内の故障を選択するとき、対象となる故障の中で最も多くの信号線数を除去できる故障を選択することにより、1回の簡単化で除去できる信号線数をできるだけ大きくする（第２簡単化手段及び方法）。すなわち許容故障選択アルゴリズは次のように表される。
【００７１】
（許容故障選択アルゴリズム）
入力:許容故障集合A、簡単化後回路Co
1 (1)Aを許容領域の集合Aaと未定領域の故障Auに分ける。
2 (2)もし、Au≠φならば、
3 (2-1)すべての故障f∈Auに対して、回路Coを故障fに基づいて簡単化した回路を求め、
最も多くの信号線を除去できる故障fmを求める。
4 (2-2)fmを返して終了。
5 (3)もし、Aa≠ φならば、
6 (3-1)すべての故障f∈Aaに対して、回路Coを故障fに基づいて簡単化した回路を求め、
最も多くの信号線を除去できる故障fmを求める。
・ (3-2)fmを返して終了。
【００７２】
(結果)
ISCAS85のベンチマーク回路c880、c2670、c7552に対して、本発明を適用した場合における回路簡単化の効果について、表２を参照して述べる。閾値テスト生成アルゴリズムはPODEMベースのアルゴリズムを用い、C言語で実装した。このアルゴリズムは単一縮退故障を対象としているが、本発明に係る回路簡単化装置及び方法のアルゴリズムでは多重故障の許容性を判定する必要があるために多重故障を単一故障に変換する回路変換を行い、多重故障の許容性判定を単一縮退故障のそれに帰着させた。実験にはApple Macmini(2.53GHz Intel Core 2 Duo,Memory 4GB)を用いた。
【００７３】
表2は、回路簡単化前と後のゲート数、信号線数、さらに簡単化回数と実行時間を示している。表中、手段１が第１簡単化手段を、手段２が第２簡単化手段を、手段３が第３簡単化手段による処理結果を示す。閾値は8を用いた。
【００７４】
また本発明の有効性を確認するために、許容領域の故障を優先的に選択するアルゴリズム(「許容故障選択アルゴリズム」において、ステップ(2)と(3)を入れ換えたもの、領域逆)、領域は考えずに最も多くの信号線を除去できる故障順(面積降順)（第２簡単化手段及び方法）、領域は考えずに最も少ない信号線を除去する故障順(面積昇順)の結果（第３簡単化手段及び方法）を示す。
【表２】
【００７５】
この表から、c7552では本発明方法が最も良い結果を示していることがわかる。すなわちゲート数、信号線数ともにオリジナル回路より大きく減少している。これは目標とした回路簡単化の回数を増やせたことが1つの原因である。なお、手段３（面積昇順）による方法でも同様に回路簡単化回数が多いが、この方法では1回あたりに除去できる信号線数が小さいため、最終的な信号線数やゲート数は提案手法よりも大きい結果になっている。すなわち、変換回数を増やしつつ、より面積削減効果が大きな許容故障を選ぶことができる。
【００７６】
一方で、c880、c2670では4つの手段に差は見られなかった。これらの回路では未定領域内に単一許容故障が存在していないため、差が生じない。
【００７７】
処理時間については、手段１の逆（領域逆）が最も良いことがわかる。これは簡単化回数が少ないこと、そして許容領域内の多重故障の許容性は判定するまでもなく、許容故障であることがすぐに分かるためである。なお、処理時間が大きいものは、閾値テスト生成を行っている時間がその大半を占めている。
【符号の説明】
【００７８】
１ 故障箇所集合生成手段
２ 第１簡単化手段
３ 第２簡単化手段
４ 第３簡単化手段
５ 選択手段
６ 回路設計変更手段
【技術分野】
【０００１】
本発明は、大規模集積回路における故障の許容性を利用した論理回路の簡単化装置及び簡単化方法に関する。
【背景技術】
【０００２】
近年のLSIの微細化、高性能化に伴いLSIの用途は幅広くなっており、求められる信頼性も様々である。医療機器や金融システムなどのように、高い信頼性が必要なシステムもある一方、それほど高い信頼性を求められないシステム、例えば、オーディオ、画像処理システム、ゲーム機などがあり、そのようなシステムにおいて故障が存在してもわずかな誤りならば目的とする処理に重大な影響を及ぼさない場合も多い（非特許文献１ないし４）。このような、目的とする処理に与える影響が許容できる範囲の故障を許容故障と呼ぶ。
【０００３】
故障の許容性を考慮することで、実効歩留まりの向上（非特許文献２）、耐故障設計のコスト削減（非特許文献５）などの効果が期待できる。さらに、故障の許容性を利用した回路簡単化も提案されている（非特許文献６）。これは組合せ回路の冗長な縮退故障を見つけることにより、回路内の冗長信号線を見つけ除去する方法（非特許文献７）と同様に、回路内の冗長故障を判定し、その故障が存在する部分回路を除去する方法である。このような部分回路除去を行ったとしても、元の回路と除去後の回路の出力差は許容範囲内であることが保証される。よって、ある一定の精度を保証するための回路を効率的に設計する目的や、設計した回路から精度を落とした低精度の回路を再設計するという目的に利用できる。
【０００４】
また、被テスト論理回路をテストする論理回路テスト装置及びテスト方法は公知である（特許文献１）。このテスト装置及び方法は、端子数の少ない論理回路テスト装置においてもオリジナルなテストパターンと同等なテストを可能とするものである。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】S.Shahidi and Sandeep K.Gupta,”A Theory OfError Rate Testing”,Proc. ICCD.pp.438 〜445.2006
【非特許文献２】Z.Jiang and S.K.Gupta.”An ATPG for Threshold Testing:Obtaining Acceptable Yieldin Future Processes.”Proc.ITC.pp.824〜833.2002.
【非特許文献３】張、安浦、”算術演算回路における許容故障とチップコスト削減への応用”、第50回FTC研究会資料、2004.
【非特許文献４】K. J.Lee,T. Y Hsieth,and M.A,Breuer,”Reduction of detected acceptable faultsfor yield improvement via error tolerance,”Proc.DATE,pp.1599~1604,2007.
【非特許文献５】I.Polian,D.Nowroth,and B.Becker,”Identification of Critical Errors in ImagingApplications,”Proc.IOLTS,pp.201〜202,2007.
【非特許文献６】D.Shin and S.K.Gupta,“A new circuit simplification method for error tolerantapplications,”Proc.DATE,pp.1〜6,2011.
【非特許文献７】S.Kajihara,H.Shiba,K.Kinoshita,”Removal of redundancy in logic circuits underclassification of undetectable faults,”Digest Papers of FTCS 22,pp.263〜270,1992.
【特許文献】
【０００６】
【特許文献１】特開２００４−１１７３０５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
前述の先行文献には、論理回路の故障テストの後、回路の簡単化をどのような装置又は方法で行うかについて、具体的な記載はない。
【０００８】
本発明は、この故障の許容性を利用した回路簡単化に着目し、複数の簡単化手段を設けて、これらを選択して適用することにより、より簡単な論理回路を得る装置及び方法を提供するものである。
【課題を解決するための手段】
【０００９】
請求項１に係る簡単化装置は、故障箇所集合生成手段と、該故障箇所集合生成手段にて生成された故障箇所のうち、未定領域の許容故障から選択し、未定領域の許容故障の選択終了後、許容領域の故障箇所を選択することにより回路簡単化を行う第１簡単化手段と、多い信号線数を除去できる故障箇所の順に回路簡単化を行う第２簡単化手段と、少ない信号線数を除去できる故障箇所の順に回路簡単化を行う第３簡単化手段と、前記第１ないし第３簡単化手段のうちゲート数、信号線数等において減少数が大きい簡単化手段を選択する選択手段と、該選択手段によって選択された前記第１ないし第３簡単化手段のいずれかにより回路の設計変更を行う回路設計変更手段とを含むことを特徴とするものである。
【００１０】
また請求項２に係る簡単化方法は、故障箇所集合生成工程と、該故障箇所集合生成工程にて生成された故障箇所のうち、未定領域の許容故障から選択し、未定領域の許容故障の選択終了後、許容領域の故障箇所を選択することにより回路簡単化を行う第１簡単化工程と、多い信号線数を除去できる故障箇所の順に回路簡単化を行う第２簡単化工程と、少ない信号線数を除去できる故障箇所の順に回路簡単化を行う第３簡単化工程と、前記第１ないし第３簡単化工程のうちゲート数、信号線数等において減少数が大きい簡単化工程を選択する選択工程と、該選択工程によって選択された前記第１ないし第３簡単化工程のいずれかに従って回路の設計変更を行う回路設計変更工程とを含むことを特徴とするものである。
【発明の効果】
【００１１】
本発明によれば、ゲート数、信号線数を最小限とすることができ、また簡単化回数及び実行時間において、回数及び時間とも他の方法よりも少なくすることができる。
【図面の簡単な説明】
【００１２】
【図１】本発明実施の形態に係る論理回路の簡単化装置及び簡単化方法を説明するための概略図である。
【図２】第１ないし第３簡単化手段を説明するためのフローチャートである。
【図３】０縮退故障f1をもつ故障回路図である。
【図４】１縮退故障f2をもつ故障回路図である。
【図５】図３に示す故障f1に基づいて簡単化した回路図である。
【図６】多重故障（f1,f3）、（f2,f4）を有する回路図である。
【図７】多重故障（f1,f3）に基いて簡単化した回路図である。
【図８】多重故障（f2,f4）に基いて簡単化した回路図である。
【図９】図６に示す回路の故障f1に基いて簡単化した回路図である。
【図１０】図６に示す回路において閾値T＝４のときの許容領域、非許容領域及び未定領域を示す回路図である。
【発明を実施するための形態】
【００１３】
図１において、１は、論理回路の除去対象信号線に対応する故障箇所集合Fを生成する故障箇所集合生成手段、２は、故障箇所集合生成手段１にて生成された故障箇所集合Fのうち、未定領域の許容故障から選択し、未定領域の許容故障の選択終了後、許容領域の故障箇所を選択することにより回路簡単化を行う第１簡単化手段、３は、故障箇所集合生成手段１にて生成された故障箇所集合Fのうち、多い信号線数を除去できる故障箇所の順に回路簡単化を行う第２簡単化手段、４は、故障箇所集合生成手段１にて生成された故障箇所集合Fのうち、少ない信号線数を除去できる故障箇所の順に回路簡単化を行う第３簡単化手段、５は、前記第１ないし第３簡単化手段のうちゲート数、信号線数等において減少数が大きい簡単化手段を選択する選択手段である。６は、選択手段５によって選択された第１ないし第３簡単化手段２〜４のいずれかにより回路の設計変更を行う回路設計変更手段である。これらはいずれもコンピュータによって処理される。
【００１４】
故障箇所集合生成手段１にて生成された故障箇所集合Fは、それぞれ第１ないし第３簡単化手段２〜４に入力され、それぞれ簡単化処理され、その結果が選択手段５に入力されて、最適な簡単化手段、すなわちゲート数、信号線数を最小限とすることができ、また簡単化回数及び実行時間において、回数及び時間とも他の方法よりも少なくすることができる簡単化手段が選択される。ゲート数、信号線数等判断項目は、総合的に判断され選択される。この選択手段５により選択された第１ないし第３簡単化手段２〜４のいずれかの手段にしたがって回路設計変形手段６にて回路が簡単化される。
【００１５】
第１ないし第３簡単化手段２〜４では、以下のようなフローによる処理がなされる。第１簡単化手段２を例に、図２を参照して説明する。簡単化処理スタートにより、故障集合Fの許容性を判定するため故障箇所集合Fが生成される（S1）。次いで故障集合Aが空か否かが反転される(S2)。空であれば終了、空でなければ、第１簡単化手段２による処理、すなわち未定領域の後に許容領域にあるものがくるように故障集合Aを整列する(S3)。故障集合A内の先頭故障に基く回路の簡単化を行う(S4)。続いて簡単化により削除された故障を故障集合Fから除去する(S5)。その後S１に戻って、同様の処理が故障集合Aが空になるまで繰り返される。
【００１６】
第２簡単化手段３においては、S3における処理が、１つの故障箇所から削除される信号線が多い順に整列する処理とされ、第３簡単化手段４においては、同様にS3における処理が、１つの故障箇所から削除される信号線が少ない順に整列される処理とされる。他の処理工程は共通である。
以下、本発明実施の形態を詳述する。
【００１７】
（許容故障）
許容故障は大きく分けて誤りの深刻さに基づくものと誤りの発生頻度に基づくものがある。ここでは誤りの深刻さに基づく許容故障に着目する。テスト対象回路C(図３)とその故障集合をF、入力値xに対する出力値z(x)とする。ここで、出力はnビットとし、出力値は、下記数式にて、非負整数を表現することとする。
【００１８】
【数１】
【００１９】
同様に、故障f(∈F)をもつ故障回路Cfの入力xに対する出力値はzf(x)と表現する。このとき、入力xを印加したときの誤りの大きさef(x)は、故障f(∈F)を持つ回路の出力値zf(x)と正常回路の出力値z(x)との差は、下記数式で表される。
【００２０】
【数２】
【００２１】
図３は0縮退故障f1(stuck at
0)をもつ故障回路である。縮退故障f1を有する回路をC f1と表記する。出力z0における信号値0/1は、正常時の値が0、故障時の値が1であることを表現している。つまり、入力値
【００２２】
【数３】
【００２３】
をこの回路に入力したとき、故障時の出力は、
【００２４】
【数４】
【００２５】
正常時の出力は(1,1,1,1,0)となり、その誤りの大きさは、下記数式にて表される。
【００２６】
【数５】
【００２７】
入力値集合Xが与えられたとき、故障fのエラーの深刻さE(f)は、下記数式で定義される。
【００２８】
【数６】
【００２９】
図３の回路における0縮退故障f1では、すべての入力値の集合に対して誤りの大きさef1(0,1,0,1)が最大値であるため、誤りの深刻さE(f1)は3となる。
【００３０】
（誤りの深刻さに基づく許容故障）
もし故障fの誤りの深刻さE(f)が閾値Tよりも小さければ(E(f)<T)、故障fは閾値Tのもとで許容できる。反対に、もし故障fの誤りの深刻さE(f)が閾値T以下（等しい場合を含む）であれば、故障fは閾値Tのもとで許容できないことになる。
【００３１】
図３及び図４に示した2つの故障f1(stuck
at 0）とf2(stuck at 1）の故障の閾値Tを4としたときの許容性について述べる。故障f1の故障の深刻さE(f1)は3であるため、故障f1は許容故障である。一方、故障f2に対しては誤りの大きさが
【００３２】
【数７】
【００３３】
となるテストパターン(1,0,0,0)が存在することから誤りの深刻さEf2がTより大きくなるため、故障f2は非許容故障である。
【００３４】
誤りの深刻さに基づく許容故障の判定は、閾値テスト生成アルゴリズムによりテスト生成を行うことで可能となる。閾値テスト生成アルゴリズムは故障の影響を外部出力に伝えるテストベクトルを探索するだけではなく、その誤りの大きさもあわせて評価するアルゴリズムである。ある故障に対して閾値T以上の誤りを出力するテストベクトルが存在しないことがこのアルゴリズムにより証明されれば、その故障は閾値Tのもとで許容となる。これは冗長故障の判定が一般的なテスト生成アルゴリズムを用いてテストパターンが存在しないことを証明して行われていることと同様である。
【００３５】
（許容故障に基づく回路簡単化）
縮退故障fを持つ故障回路Cfは、その故障値が影響する信号線をその故障値で固定することにより得られる簡単化された回路Cfと等価である。例えば、図５は、図３に示す故障f1に基づいて簡単化した回路である。図３と図５を比べれば、故障f1の存在する信号線がつながる2つのNANDゲートの出力が信号値1に縮退し、その結果、この2つのNANDゲートを含む3つのゲートが除去され、それに伴い図３の太線で示した信号線aが除去されていることがわかる。
【００３６】
組合せ回路Cにおける故障frが冗長故障であれば、冗長故障の定義から故障回路CfrとCが等価(すべての対応する出力関数が等価)であるため、その故障に基づいて簡単化された回路Cfrと回路Cも等価となる。
【００３７】
同様に、組合せ回路Cにおける故障faが閾値Tのもとで許容できる場合、故障回路CfaとCの出力値の差(エラー)は閾値T以下であるため、簡単化後、回路CfaとCの出力値の差も閾値T以下となる。このとき、回路CfaとCは「閾値Tのもとで等価」と呼ぶ。図３と図５に示す2つの回路は閾値Tが4のもとで等価である。
【００３８】
（許容故障判定と簡単化アルゴリズム）
組合せ回路Cと閾値Tが与えられたとき、故障の許容性に基づいて最も回路素子数が少ない回路を得る方法について述べる。一般には、回路Cに複数の単一縮退故障が存在しても、すなわち多重縮退故障が存在しても許容できるため、許容できる多重縮退故障の中でより多くの回路素子数を削減できる多重故障を見つけることによってなされる。
【００３９】
図６において、回路に2つの多重故障m1,m2
【００４０】
【数８】
【００４１】
【数９】
【００４２】
が存在するとする。これらはどちらも閾値Tが4のもとで許容できる多重故障である。この2つの多重故障に基づいて簡単化した回路をそれぞれ図７及び図８に示す。この場合、図７に示す回路の方がゲート数および信号線数共に少ないため、許容できる多重故障m1に基づいて簡単化する方が良い。なお、この例ではこの多重故障m1に基づいて簡単化した回路が、最も回路素子数が小さい回路となる。
【００４３】
一般に、単一縮退故障の許容性から、多重許容故障の許容性を判断することはできない。例えば、図６に示す故障f1とf3は、それぞれの単一故障を考えるとどちらも閾値Tが3のもとでも許容故障であるが、多重故障故障m3
【００４４】
【数１０】
【００４５】
は閾値3のもとでは許容できない。なぜなら、入力x=(1,1,1)の時に出力zf(1,1,1)=(1,1,0,0)であり、正常時の出力z(1,1,1)=(1,1,1,1)との差が3となり、閾値以上となるからである。
【００４６】
これは冗長故障でも同じことが言えるため、冗長故障に基づく回路簡単化は、本質的に1つの単一冗長故障を除去する度に、冗長故障判定を繰り返すことを行っている。
【００４７】
本発明におけるアルゴリズムも同様に1つの単一許容故障に基づいて回路を簡単化するごとに、許容故障を再度判定し直す。ただし、以下に述べるように、冗長故障に基づく回路簡単化で行われている冗長判定の考え方は、そのまま許容性の判定のために導入できないため、故障の許容性の判定は異なる方法で行う。
【００４８】
冗長故障に基づく回路簡単化において、回路Cを冗長故障f1に基づいて簡単化した回路をCf1とする。このときCとCf1は等価であるため、回路Cf1をこの回路Cf1における冗長故障f2’で簡単化した回路C{f1,f2’} はCと等価である。このように、冗長故障に基づく回路簡単化では、簡単化された回路に対してテスト生成を行うことで故障の冗長性を判定すればよい。
【００４９】
一方、許容故障に基づく回路簡単化では、簡単化した回路に対して、故障の許容性を判定した場合、正しく判定できない可能性がある。回路Cにおける閾値Tのもとでの許容故障f1に基づいて、Cを簡単化した回路をCf1とする。このときCとCf1は閾値Tのもとで等価である。さらに、回路Cf1上で閾値Tのもとで許容できる故障f2’が見つかり、これに基づいて簡単化を行ったとする。このとき、回路Cf1の出力と故障回路C{f1,f2′}は閾値Tのもとで等価であるが、回路Cと故障回路C{f1,f2′}との出力誤差は閾値以下であることは保証できないため、閾値Tのもとで等価かどうかは不明である。
【００５０】
図９は、図６に示す回路の故障f1に基づいて簡単化した回路C1f1である。この回路C1f1の信号線z1上の故障f3′(回路C1の故障f3に対応)は、C1f1に対しては閾値3のもとで許容であるが、先に述べたように、回路C1において多重故障{ f1, f3}は閾値 3のもとで許容ではない。よって、図７に示すような回路C1f1を故障f3’に基づいて簡単化した回路C1{f1,f3′}は、回路C1と閾値3のもとで等価ではない。
【００５１】
表1にこの3つの回路C1、C1f1、C1{f1,f3′}の全出力と誤りの大きさを示す。この出力を見るとC1f1 とC1{f1,f3′}の出力差は、Tが3以下であるが、回路C1と故障回路C1{f1,f3′}の差は入力000の時に3となり、閾値3以上になることがわかる。
【表１】
【００５２】
本発明におけるアルゴリズムでは、回路Cをk−1個の許容故障に基づいて簡単化した下記数式１１で示す回路に対して、次の簡単化の対象となる故障fkを見つけるために、回路C上の多重故障{f1,f2…fk-1,fk}に対して、閾値テスト生成を行い、この多重故障が許容かどうか判定する。多重故障が許容であれば、故障fkに基づいて、数式１１に示す回路をさらに簡単化する。そのアルゴリズムを以下に示す。
【００５３】
【数１１】
【００５４】
（故障の許容性に基づく回路簡単化）
入力:組合せ回路C、単一故障集合F、閾値T。
1 (1)選択した多重故障M=φ、簡単化した回路Co=Cとする。
2 (2)故障集合Fが空になるまで次を繰り返す。
3 (2-1)すべての故障f∈Fに対して、
4 (2-1-1)多重故障M∪fがCにおいて許容故障かどうか判定する。
5 (2-1-2)許容故障ならば、A=A∪{f}。
6 (2-2)もし、A=φならば、Coを返して終了。
7 (2-3)Aから1つの単一許容故障f′を選択。
8 (2-4)Coをf′に基づいて簡単化。
9 (2-5)FをCoの故障リストに更新。
10 (3)Coを返す。
7行目でどの許容故障を選択するかによって、最終的に得られる回路のゲート数および信号線数が異なる。
次に、信号線の選択基準について説明する。
【００５５】
（許容故障の選択基準）
前述したアルゴリズに従って回路を簡単化することで最終的に多くの信号線を除去するためには、1回の除去で削除できる信号線を多くすることと、1つの故障から行う削減の回数(2行目から9行目までのループの回数)をできるだけ増やすことが望ましい。ここでは、後者を実現するための1つの方法を説明する。
【００５６】
許容故障の選択基準は、故障が次に示す3つの領域のどの信号線上にあるのかによってその優先度を変えるものである。3つの領域の定義は以下の通りである。なお、回路Cの出力はnビットとし、出力値z(x)は、下記数式１２で示すように非負整数を表す。
【００５７】
【数１２】
【００５８】
「非許容領域」
下記数式１３で示す外部出力のいずれかにのみ到達可能な信号線集合。ここで、
【００５９】
【数１３】
【００６０】
【数１４】
【００６１】
「許容領域」
下記数式１５で示す外部出力のいずれかにのみ到達可能な信号線集合。ここで、
【００６２】
【数１５】
【００６３】
【数１６】
【００６４】
「未定領域」
許容領域、非許容領域以外の信号線集合。
【００６５】
図１０は図６に示す回路C1における閾値4の時の3つの領域を示している。閾値4のとき、kua=ka=2であるため、外部出力z0、z1のみに到達可能な信号線は許容領域に含まれ、外部出力z2、z3のみに到達可能な信号線は非許容領域に含まれる。
【００６６】
許容領域の信号線上の故障は、回路構造からその誤りの大きさが必ず閾値T以下になるため、閾値Tのもとで許容である。同様に、非許容領域内の故障もその誤りの大きさが必ず閾値T以上になるため、必ず閾値Tのもとで非許容であると言える。また、許容領域内の故障集合の任意の部分集合からなる多重故障に基づいて簡単化した回路は、元の回路と閾値Tのもとで等価であるため、これらの許容故障は同時に除去することが可能である。
【００６７】
ここで1つの選択基準として未定領域の許容故障から選択し、未定領域内の許容故障がなくなれば許容領域の故障を選択することとする（第１簡単化手段及び方法）。未定領域の許容故障は、許容領域の故障に基づいて回路を簡単化した後では非許容になる場合が多いため、このような選択をすると、簡単化できる回数が増加することが期待できる。
【００６８】
図６に示す回路C1上の故障f1、f2、f3、f4を再度説明する。これらはそれぞれ単一縮退故障として閾値T=4のもとで許容である。許容領域内にある故障からなる多重故障{f3,f4}も閾値Tのもとで許容であるため、これらを除去して回路を簡単化できる。しかし、簡単化後の回路では許容故障は存在しないため、これ以上の簡単化はできない。
【００６９】
一方、非許容領域の故障f1は閾値Tのもとで許容であるため簡単化した回路は元の回路と閾値Tのもとで等価であるが、その簡単化後の回路においても故障f3に対応する故障f3′は閾値Tのもとで許容できるため、さらに簡単化が可能であり、最終的に図７に示す回路C1{f1,f3}を得ることができる。
【００７０】
各領域内の故障を選択するとき、対象となる故障の中で最も多くの信号線数を除去できる故障を選択することにより、1回の簡単化で除去できる信号線数をできるだけ大きくする（第２簡単化手段及び方法）。すなわち許容故障選択アルゴリズは次のように表される。
【００７１】
（許容故障選択アルゴリズム）
入力:許容故障集合A、簡単化後回路Co
1 (1)Aを許容領域の集合Aaと未定領域の故障Auに分ける。
2 (2)もし、Au≠φならば、
3 (2-1)すべての故障f∈Auに対して、回路Coを故障fに基づいて簡単化した回路を求め、
最も多くの信号線を除去できる故障fmを求める。
4 (2-2)fmを返して終了。
5 (3)もし、Aa≠ φならば、
6 (3-1)すべての故障f∈Aaに対して、回路Coを故障fに基づいて簡単化した回路を求め、
最も多くの信号線を除去できる故障fmを求める。
・ (3-2)fmを返して終了。
【００７２】
(結果)
ISCAS85のベンチマーク回路c880、c2670、c7552に対して、本発明を適用した場合における回路簡単化の効果について、表２を参照して述べる。閾値テスト生成アルゴリズムはPODEMベースのアルゴリズムを用い、C言語で実装した。このアルゴリズムは単一縮退故障を対象としているが、本発明に係る回路簡単化装置及び方法のアルゴリズムでは多重故障の許容性を判定する必要があるために多重故障を単一故障に変換する回路変換を行い、多重故障の許容性判定を単一縮退故障のそれに帰着させた。実験にはApple Macmini(2.53GHz Intel Core 2 Duo,Memory 4GB)を用いた。
【００７３】
表2は、回路簡単化前と後のゲート数、信号線数、さらに簡単化回数と実行時間を示している。表中、手段１が第１簡単化手段を、手段２が第２簡単化手段を、手段３が第３簡単化手段による処理結果を示す。閾値は8を用いた。
【００７４】
また本発明の有効性を確認するために、許容領域の故障を優先的に選択するアルゴリズム(「許容故障選択アルゴリズム」において、ステップ(2)と(3)を入れ換えたもの、領域逆)、領域は考えずに最も多くの信号線を除去できる故障順(面積降順)（第２簡単化手段及び方法）、領域は考えずに最も少ない信号線を除去する故障順(面積昇順)の結果（第３簡単化手段及び方法）を示す。
【表２】
【００７５】
この表から、c7552では本発明方法が最も良い結果を示していることがわかる。すなわちゲート数、信号線数ともにオリジナル回路より大きく減少している。これは目標とした回路簡単化の回数を増やせたことが1つの原因である。なお、手段３（面積昇順）による方法でも同様に回路簡単化回数が多いが、この方法では1回あたりに除去できる信号線数が小さいため、最終的な信号線数やゲート数は提案手法よりも大きい結果になっている。すなわち、変換回数を増やしつつ、より面積削減効果が大きな許容故障を選ぶことができる。
【００７６】
一方で、c880、c2670では4つの手段に差は見られなかった。これらの回路では未定領域内に単一許容故障が存在していないため、差が生じない。
【００７７】
処理時間については、手段１の逆（領域逆）が最も良いことがわかる。これは簡単化回数が少ないこと、そして許容領域内の多重故障の許容性は判定するまでもなく、許容故障であることがすぐに分かるためである。なお、処理時間が大きいものは、閾値テスト生成を行っている時間がその大半を占めている。
【符号の説明】
【００７８】
１ 故障箇所集合生成手段
２ 第１簡単化手段
３ 第２簡単化手段
４ 第３簡単化手段
５ 選択手段
６ 回路設計変更手段
【特許請求の範囲】
【請求項１】
大規模集積回路における故障の許容性を利用した論理回路の簡単化装置であって、該簡単化装置は、故障箇所集合生成手段と、該故障箇所集合生成手段にて生成された故障箇所のうち、未定領域の許容故障から選択し、未定領域の許容故障の選択終了後、許容領域の故障箇所を選択することにより回路簡単化を行う第１簡単化手段と、多い信号線数を除去できる故障箇所の順に回路簡単化を行う第２簡単化手段と、少ない信号線数を除去できる故障箇所の順に回路簡単化を行う第３簡単化手段と、前記第１ないし第３簡単化手段のうちゲート数、信号線数等において減少数が大きい簡単化手段を選択する選択手段と、該選択手段によって選択された前記第１ないし第３簡単化手段のいずれかにより回路の設計変更を行う回路設計変更手段とを含むことを特徴とする論理回路の簡単化装置
【請求項２】
大規模集積回路における故障の許容性を利用した論理回路の簡単化方法であって、該簡単化方法は、故障箇所集合生成工程と、該故障箇所集合生成工程にて生成された故障箇所のうち、未定領域の許容故障から選択し、未定領域の許容故障の選択終了後、許容領域の故障箇所を選択することにより回路簡単化を行う第１簡単化工程と、多い信号線数を除去できる故障箇所の順に回路簡単化を行う第２簡単化工程と、少ない信号線数を除去できる故障箇所の順に回路簡単化を行う第３簡単化工程と、前記第１ないし第３簡単化工程のうちゲート数、信号線数等において減少数が大きい簡単化工程を選択する選択工程と、該選択工程によって選択された前記第１ないし第３簡単化工程のいずれかに従って回路の設計変更を行う回路設計変更工程とを含むことを特徴とする論理回路の簡単化方法
【請求項１】
大規模集積回路における故障の許容性を利用した論理回路の簡単化装置であって、該簡単化装置は、故障箇所集合生成手段と、該故障箇所集合生成手段にて生成された故障箇所のうち、未定領域の許容故障から選択し、未定領域の許容故障の選択終了後、許容領域の故障箇所を選択することにより回路簡単化を行う第１簡単化手段と、多い信号線数を除去できる故障箇所の順に回路簡単化を行う第２簡単化手段と、少ない信号線数を除去できる故障箇所の順に回路簡単化を行う第３簡単化手段と、前記第１ないし第３簡単化手段のうちゲート数、信号線数等において減少数が大きい簡単化手段を選択する選択手段と、該選択手段によって選択された前記第１ないし第３簡単化手段のいずれかにより回路の設計変更を行う回路設計変更手段とを含むことを特徴とする論理回路の簡単化装置
【請求項２】
大規模集積回路における故障の許容性を利用した論理回路の簡単化方法であって、該簡単化方法は、故障箇所集合生成工程と、該故障箇所集合生成工程にて生成された故障箇所のうち、未定領域の許容故障から選択し、未定領域の許容故障の選択終了後、許容領域の故障箇所を選択することにより回路簡単化を行う第１簡単化工程と、多い信号線数を除去できる故障箇所の順に回路簡単化を行う第２簡単化工程と、少ない信号線数を除去できる故障箇所の順に回路簡単化を行う第３簡単化工程と、前記第１ないし第３簡単化工程のうちゲート数、信号線数等において減少数が大きい簡単化工程を選択する選択工程と、該選択工程によって選択された前記第１ないし第３簡単化工程のいずれかに従って回路の設計変更を行う回路設計変更工程とを含むことを特徴とする論理回路の簡単化方法
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１３−４１５０８（Ｐ２０１３−４１５０８Ａ）
【公開日】平成２５年２月２８日（２０１３．２．２８）
【国際特許分類】
【出願番号】特願２０１１−１７９１８５（Ｐ２０１１−１７９１８５）
【出願日】平成２３年８月１８日（２０１１．８．１８）
【出願人】（５１０１０８９５１）公立大学法人広島市立大学 (11)
【Ｆターム（参考）】
【公開日】平成２５年２月２８日（２０１３．２．２８）
【国際特許分類】
【出願日】平成２３年８月１８日（２０１１．８．１８）
【出願人】（５１０１０８９５１）公立大学法人広島市立大学 (11)
【Ｆターム（参考）】
[ Back to top ]