(57)【要約】      （修正有）【課題】ＬＳＩの単体テストのパターン入力時に、ＬＳＩの外部端子数の不足を補うために、テストパターンのＬＦＳ符号化（符号化・複合化）により、ピット幅を最適化する。【解決手段】符号のビット幅の初期値を設定し（Ｓ１）、与えられたビット幅において、テスト対象の回路に印加すべきすべてのテストパターンのＬＦＳ符号化が可能か否かを判定し（Ｓ２）、符号化できないテストパターンが存在するときは、ビット幅を歩進し（Ｓ４）、再度、符号化を試みる。【選択図】      図４
2004295833.tif 000002
【特許請求の範囲】
【請求項１】
（ａ）符号のビット幅の初期値を定め、
（ｂ）与えられたビット幅において、テスト対象の回路に印加すべきすべてのテストパターンのＬＦＳ（Ｌｉｎｅａｒ  Ｆｅｅｄｂａｃｋ  Ｓｈｉｆｔ  ）符号化が可能か否かを判定し、
（ｃ）ステップ（ｂ）において符号化に失敗するテストパターンが存在するとき、符号のビット幅を歩進し、
（ｄ）すべてのテストパターンについて符号化に成功するまでステップ（ｂ）および（ｃ）を繰り返すステップを具備するテストパターンのＬＦＳ符号化の設計方法。
【請求項２】
ステップ（ｂ）は、
（ｉ）与えられたビット幅におけるテストパターンの復号化の論理式を生成し、
（ｉｉ）該論理式の出力の各ビットにテストパターンを構成する各ビットをそれぞれアサインし、
（ｉｉｉ）１つのテストパターンのうち、該論理式において入力値がそのまま出力として使用される部分にアサインされた部分から該論理式に従って復号化されたビットパターンが該テストパターンに包含されるか否か、またはその部分が未確定のビットを含むとき、該テストパターンに包含されるビットパターンを復号後に与える未確定ビットの実値が存在するか否かを判定することによって、前記与えられたビット幅において該テストパターンを符号化し得るか否かを判定し、
（ｉｖ）全てのテストパターンについて順次サブステップ（ｉｉ）（ｉｉｉ）を実行することによって、すべてのテストパターンの符号化が可能か否かを判定するサブステップを含む請求項１記載の方法。
【請求項３】
（ｅ）ステップ（ｂ）の前において、テストパターンに含まれる未確定のビットをビット位置ごとにカウントするステップをさらに具備し、サブステップ（ｂ）（ｉｉ）において、テストパターンの未確定のビットの数がより多いビット位置が、前記論理式における関連する入力の数のより多い出力にアサインされる請求項２記載の方法。
【請求項４】
（ｅ）ステップ（ｂ）の前において、テストパターンの集合に対してＸ抽出処理を行なうステップをさらに具備する請求項１記載の方法。
【請求項５】
符号のビット幅の初期値を定める手段と、
与えられたビット幅において、テスト対象の回路に印加すべきすべてのテストパターンのＬＦＳ（Ｌｉｎｅａｒ  Ｆｅｅｄｂａｃｋ  Ｓｈｉｆｔ  ）符号化が可能か否かを判定する第１の判定手段と、
第１の判定手段における判定において符号化に失敗するテストパターンが存在するとき、符号のビット幅を歩進する手段と、
すべてのテストパターンについて符号化に成功するまで第１の判定手段および歩進手段を繰り返し起動する手段とを具備するテストパターンのＬＦＳ符号化の設計装置。
【請求項６】
第１の判定手段は、
与えられたビット幅におけるテストパターンの復号化の論理式を生成する手段と、
該論理式の出力の各ビットにテストパターンを構成する各ビットをそれぞれアサインする手段と、
１つのテストパターンのうち、該論理式において入力値がそのまま出力として使用される部分にアサインされた部分から該論理式に従って復号化されたビットパターンが該テストパターンに包含されるか否か、またはその部分が未確定のビットを含むとき、該テストパターンに包含されるビットパターンを復号後に与える未確定ビットの実値が存在するか否かを判定することによって、前記与えられたビット幅において該テストパターンを符号化し得るか否かを判定する第２の判定手段と、
全てのテストパターンについて順次前記アサイン手段および第２の判定手段を起動することによって、すべてのテストパターンの符号化が可能か否かを判定する手段とを含む請求項５記載の装置。
【請求項７】
第１の判定手段による判定の前において、テストパターンに含まれる未確定のビットをビット位置ごとにカウントする手段をさらに具備し、前記アサイン手段は、テストパターンの未確定のビットの数がより多いビット位置を、前記論理式における関連する入力の数のより多い出力にアサインする請求項６記載の装置。
【請求項８】
第１の判定手段による判定の前において、テストパターンの集合に対してＸ抽出処理を行なう手段をさらに具備する請求項５記載の装置。
【請求項９】
請求項１〜４のいずれかに記載のテストパターンのＬＦＳ符号化の設計方法をコンピュータに実現させるプログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はテストパターンのビット幅の圧縮を目的として符号化するＬＦＳ符号化を最適に設計する方法と装置に関する。
【０００２】
【従来の技術】
例えば、既設計のＩＰコアを組み合わせて設計するＳｏＣ（Ｓｙｓｔｅｍ  ｏｎ  Ｃｈｉｐ）では、搭載するコア毎に単体テストを行うことでＬＳＩ全体の動作を保証する。このため、各コアの入出力をＬＳＩの外部端子に引き出し、単体テストのパターンを入力し、出力応答を観測する仕組みを付加する。このとき、コア単体のテストに必要な入出力数がＬＳＩ外部端子数よりも多い場合は完全なテストを行うことができなくなる。そこで、テスト時の入出力ビット幅の調整機構が必要となる。
【０００３】
ビット幅調整機能としては、コアの入出力にシリアル・パラレル変換器を配置し、シリアルにテストパターンを入出力する方法と、テストパターンを符号化する方法がある。前者ではテストパターンがシリアルに入出力されるので、ほぼ確実に入出力端子数の問題を回避できる。しかし、テストパターンの入出力に時間がかかるため、テスト実行時間が長くなることと、高速動作のテストを行うことが困難になる。このため、シリアルアクセスを前提としないビット幅調整技術としてのテストパターン符号化・復号化手法が重要となる。
【０００４】
ビット幅調整技術としてのテストパターン符号化・復号化手法とは、テストパターンを符号化してビット幅を狭めて印加し、ＳｏＣ内部にデコーダを内蔵し、ＬＳＩ内部で元のビット幅に復号化する技術である。中でも、ＬＦＳ（Ｌｉｎｅａｒ  Ｆｅｅｄｂａｃｋ  Ｓｈｉｆｔ  ）符号化手法（ＥＰ０４８１０９７Ｂ１）は、組合せ回路で復号化できること、テストパターンのｄｏｎ’ｔ  ｃａｒｅ（１でも０でもテストに影響を与えない論理値）が多いと効率よく圧縮できる等の特徴があり、実用性の高い手法である。以下その概要を説明する。
【０００５】
図１は４ビットのＬＦＳＲ（Ｌｉｎｅａｒ  Ｆｅｅｄｂａｃｋ  Ｓｈｉｆｔ  Ｒｅｇｉｓｔｅｒ）１０に６ビットのシフトチェーン１２を接続した論理である。ＬＦＳＲ１０のシード（初期値）を（ａ，ｂ，ｃ，ｄ）としたとき、６時刻後のシフトチェーン１２の論理値はそれぞれシードの論理値を用いて図１右下の論理式で表現できる。
【０００６】
図１のシフトチェーンに６時刻後、（０，Ｘ，０，１，Ｘ，１）という内部状態を設定するためにはシード（ａ，ｂ，ｃ，ｄ）に何を設定すればよいか分かれば、シフトチェーンの内部状態６ビットのパターンをＬＦＳＲの６時刻前のシード４ビットのパターンに符号化できることを意味する。ここで、Ｘはｄｏｎ’ｔｃａｒｅ（１でも０でも良い）である。このとき、図１左下の連立方程式を解くことで、（ａ，ｂ，ｃ，ｄ）＝（０，１，１，１）が得られる。
【０００７】
図２に図１の符号化に対応する復号論理を示す。図２は符号化で用いたシフトチェーンの論理関数をそのまま組合せ回路にしたものである。前述の例で符号化したパターン（０，１，１，１）を復号化した（０，１，０，１，１，１）と符号化前のパターンはｄｏｎ’ｔ  ｃａｒｅビット以外は一致しており、復号化したパターンは符号化前のパターンに包含されていることが分かる。
【０００８】
以上のように、ＬＦＳ符号化では、ＮビットのＬＦＳＲにＭビットのシフトチェーンが接続されている回路モデルを用い、シフトチェーンの各ビットの論理関数を左辺に、符号化すべきＭビットパターンを右辺に置いた連立方程式を解き、Ｎビットの符号化パターンを得ることができる。
【０００９】
【特許文献１】
ＥＰ０４８１０９７Ｂ１
【非特許文献１】
Ｓ．  Ｋａｊｉｈａｒａ  ａｎｄ  Ｋ．  Ｍｉｙａｓｅ，“Ｏｎ  Ｉｄｅｎｔｉｆｙｉｎｇ  Ｄｏｎ’ｔ  Ｃａｒｅ  Ｉｎｐｕｔｓ  ｏ          ｆ  Ｔｅｓｔ  Ｐａｔｔｅｒｎｓ  ｆｏｒ  ｃｏｍｂｉｎａｔｉｏｎａｌ  Ｃｉｒｃｕｉｔｓ，”Ｐｒｏｃ．  ｏｆ  Ｉｎｔ’ｌ  Ｃｏ          ｎｆ．  ｏｆ  ＣＡＤ，  ｐｐ．  ３６４−３６９，  ２００１
【非特許文献２】
Ｋ．  Ｍｉｙａｓｅ  ｅｔ  ａｌ．，“Ｄｏｎ’ｔ−Ｃａｒｅ  Ｉｄｅｎｔｉｆｉｃａｔｉｏｎ  ｏｎ  Ｓｐｅｃｉｆｉｃ  Ｂｉｔｓ            ｏｆ  Ｔｅｓｔ  Ｐａｔｔｅｒｎｓ”，  ＩＣＣＤ，  ２００２
【００１０】
【発明が解決しようとする課題】
ＬＦＳ符号化は連立方程式を解くことで符号化を行う。このとき、図３に示すように連立方程式が解なしとなる場合、ＬＦＳＲのビット数を変えないと符号化できない。ＳｏＣテストのビット幅調整技術として利用する際、ビット幅の圧縮率が高い（Ｎ／Ｍが小さい）符号化が出来る程、コア入力数に対するＬＳＩ外部ピン数の制約を緩和できる。従って、与えられたテストパターン系列に対し、できるだけ小さなビット長のＬＦＳＲを見出すことが重要である。従来技術では、この方法が明確に示されていないという問題がある。
【００１１】
したがって本発明の目的は、与えられたテストパターンに対して、圧縮率の高いＬＦＳ符号化を設計する手法を提案することにある。
【００１２】
【課題を解決するための手段】
本発明によれば（ａ）符号のビット幅の初期値を定め、（ｂ）与えられたビット幅において、テスト対象の回路に印加すべきすべてのテストパターンのＬＦＳ（Ｌｉｎｅａｒ  Ｆｅｅｄｂａｃｋ  Ｓｈｉｆｔ  ）符号化が可能か否かを判定し、（ｃ）ステップ（ｂ）において符号化に失敗するテストパターンが存在するとき、符号のビット幅を歩進し、（ｄ）すべてのテストパターンについて符号化に成功するまでステップ（ｂ）および（ｃ）を繰り返すステップを具備するテストパターンのＬＦＳ符号化の設計方法が提供される。
【００１３】
ステップ（ｂ）は、（ｉ）与えられたビット幅におけるテストパターンの復号化の論理式を生成し、（ｉｉ）該論理式の出力の各ビットにテストパターンを構成する各ビットをそれぞれアサインし、（ｉｉｉ）１つのテストパターンのうち、該論理式において入力値がそのまま出力として使用される部分にアサインされた部分から該論理式に従って復号化されたビットパターンが該テストパターンに包含されるか否か、またはその部分が未確定のビットを含むとき、該テストパターンに包含されるビットパターンを復号後に与える未確定ビットの実値が存在するか否かを判定することによって、前記与えられたビット幅において該テストパターンを符号化し得るか否かを判定し、（ｉｖ）全てのテストパターンについて順次サブステップ（ｉｉ）（ｉｉｉ）を実行することによって、すべてのテストパターンの符号化が可能か否かを判定するサブステップを含む。
【００１４】
（ｅ）ステップ（ｂ）の前において、テストパターンに含まれる未確定のビットをビット位置ごとにカウントするステップをさらに具備し、サブステップ（ｂ）（ｉｉ）において、テストパターンの未確定のビットの数がより多いビット位置が、前記論理式における関連する入力の数のより多い出力にアサインされることが望ましい。
【００１５】
あるいはまた、（ｅ）ステップ（ｂ）の前において、テストパターンの集合に対してＸ抽出処理を行なうステップをさらに具備することも望ましい。
【００１６】
【発明の実施の形態】
図４は本発明に係るテストパターン符号化方法の第１の実施例を示すフローチャートである。
【００１７】
与えられたテストパターン系列に対し、ＬＦＳＲのビット幅Ｎの初期値として最小値２から探索を開始する（図４：Ｓ１）。符号化判定処理において、対象のテストパターン集合の符号化を試行する（Ｓ２）。全テストパターンの符号化に成功すれば終了する（Ｓ３）。さもなければ、ビット幅Ｎを１つ増やし（Ｓ４）、符号化判定処理に戻る。以下、図５に示す論理回路のテストパターン（図６）の符号化を例に、符号化判定処理を説明する。
【００１８】
図７に符号化判定処理（図４：Ｓ２）の詳細フローを示す。初めに、ＬＦＳＲのビット幅Ｎ、与えられたテストパターンのビット幅Ｍに対応する復号論理を生成する（図７：Ｓ２−１）。図５、図６より、テストパターンのビット幅Ｍ＝１７である。Ｎ＝１５の時の復号論理を図８に示す。
【００１９】
次に、未試行のパターンを１つ選択し（図７：Ｓ２−２）、シード割当処理を行う（Ｓ２−３）。シード割当処理とは、復号論理の入力論理値＝出力論理値である部分に対し、対象パターンのビットを割り当てる処理である。図９にシード割当処理の例を示す。Ｎ＝１５の復号論理では、復号ビットのうち１３ビットが入力論理値＝出力論理値である。この１３ビットは符号化の前後で変化しないため、符号化前のパターンをそのままシードとして当てはめる。図９は、パターンとして図６のＮｏ．４を選択し、右側１３ビットをシードに割り当てた例である。
【００２０】
次にシードの未確定部に確定論理値を割当て、復号パターンを生成するＳｅｅｄ復号処理を行う（図７：Ｓ２−４）。図１０は図７の２ビットの未確定部分に、確定値００を割り当て、復号したものである。復号後のパターンと元パターンを比較し（図７：Ｓ２−５）、復号パターンが元パターンに包含されていれば次の未試行パターンの復号化を行う。さもなければ、シードの未確定部への割当論理値を変えて試行する（Ｓ２−６）。シードの未確定部にどんな値を割り当てても符号化できない場合は失敗終了となる。図１０の例では、テストパターンＮｏ．４はシードの未確定値を００，０１，１０，１１のどの値に設定しても、左から２ビット目が復号化パターンと異なるため、失敗終了となる。このことにより、Ｎ＝１５では図６のパターンは符号化できないことが分かる。
【００２１】
本実施例ではＮ＝１６の時、図１１の復号論理により、全パターンの復号化が成功する。また、このとき、同時に符号化済みテストパターンが得られる。図１２に符号化されたテストパターンを示す。
【００２２】
図１３は本発明に係るテストパターン符号化方法の第２の実施例を示すフローチャートである。初めにビットアサイン処理（Ｓ１）を実行し、ＬＦＳ符号化が成功しやすいように復号論理の出力ビットと復号化すべきテストパターンのビットアサインを行う。その後、実施例１と同じ探索を実行する（図１３：Ｓ２〜Ｓ５）。以下、本実施例の特徴であるビットアサイン処理について説明する。
【００２３】
図１４はビットアサイン変更処理のフローである。Ｘ値カウント処理（Ｓ１−１）とは、符号化するテストパターン集合の各ビット毎に、Ｘ値の数を数える処理である。例として、図６のテストパターン集合のＸ数カウント結果を図１５に示す。次に、ビットソート処理（図１４：Ｓ１−２）で上記カウント値に基づきテストパターンのビット列をソートする。図１６に図６のテストパターンのビットソート結果を示す。ＬＦＳ符号化の復号論理において、関係する入力の多いビットと少ないビットが混在する。図１で説明した符号化時のモデルでＬＦＳＲ１０により近いビットが依存する入力の数が多くなり、符号化失敗の要因になる。そこで、図１７に示すように、マッピング処理（図１４：Ｓ１−１）により、テストパターンにＸ値が多いビットを符号化モデル上論理関数が複雑になる側の復号ビットに割当ることで、符号化失敗の可能性を低減する。図１７のビットアサインにより、図６のテストパターンはＮ＝１５で全符号化される。図１８に符号化後のテストパターンを示す。
【００２４】
図１９はビットアサイン処理を含む第２実施例の一変形を示すフローチャートである。符号化のビット幅Ｎが変わると論理関数も変わる。このため、Ｎにあわせてビットアサインも変更すると更に符号化の成功率が高まる。このときのビットアサイン処理として、図２０に示すように復号ビットの関係する入力数をカウントする処理（図２０：Ｓ１−３）を導入する。このことにより、依存する入力数が多いビットとＸ値の多いビットとをより正確にマッピングできる。図２１、図２２はそれぞれＮ＝１３，Ｎ＝１５の時のマッピングを示したものである。
【００２５】
図２３は本発明に係るテストパターン符号化方法の第３の実施例を示すフローチャートである。初めにＸ抽出処理（Ｓ１）を実行し、ＬＦＳ符号化が成功しやすいようにテストパターンの特定ビットにＸ値が集中するよう処理を行う。その後、実施例１と同じ探索を実行する（図２３：Ｓ２〜Ｓ５）。Ｘ抽出処理（Ｓ．  Ｋａｊｉｈａｒａ  ａｎｄ  Ｋ．  Ｍｉｙａｓｅ，“Ｏｎ  Ｉｄｅｎｔｉｆｙｉｎｇ  Ｄｏｎ’ｔ  Ｃａｒｅ  Ｉｎｐｕｔｓ  ｏｆ  Ｔｅｓｔ  Ｐａｔｔｅｒｎｓ  ｆｏｒ  Ｃｏｍｂｉｎａｔｉｏｎａｌ  Ｃｉｒｃｕｉｔｓ，”Ｐｒｏｃ．  ｏｆ  Ｉｎｔ’ｌ  Ｃｏｎｆ．  ｏｆ  ＣＡＤ，  ｐｐ．  ３６４−３６９，  ２００１）とは論理回路と対応するテストパターンを入力としてテストパターンの検出率を下げることなくｄｏｎ’ｔ  ｃａｒｅを抽出する技術である。特定ビットを指定し、そのビットを極力Ｘ値にすることが可能である。図２４に図６テストパターンについて上位５ビットのＸ値指定してＸ抽出を行った結果を示す。図２４のパターンはＮ＝１３で符号化することができる。このときの復号論理を図２５に、符号化後のテストパターンを図２６に示す。
【００２６】
本発明の方法はいずれも、コンピュータに上記の処理を実行させるプログラムにより実現することができる。
【００２７】
第一に、本発明により、ＬＦＳ符号化の必要な符号ビット幅を探索することができる。
【００２８】
第二に、本発明により、与えられたテストパターンと符号ビット幅に対してＬＦＳ符号化が成功する可能性が向上する。
【００２９】
上記２点により、本発明でＬＦＳ符号化の圧縮率を向上することができる。また、本技術をＳｏＣテストのビット幅調整に適用することで、テスト時のスループット向上をもたらす。すなわち、テストコストの低減に直接効果を及ぼす。更に、ＳｏＣテストのピン数の制約を緩和し、高速機能テストのようにパラレルアクセスを必要とするテストの実現性が高まるため、間接的にＳｏＣテスト品質の向上につながる。
【図面の簡単な説明】
【図１】ＬＦＳＲの機能とＬＦＳ符号化を説明する図である。
【図２】図１の符号化に対応する復号論理の図である。
【図３】符号化できない例を説明する図である。
【図４】本発明の第１の実施例を示すフローチャートである。
【図５】テストの対象となる論理回路の例を示す回路図である。
【図６】図５の回路に対するテストパターンの例を示す図である。
【図７】図４の符号化判定処理の詳細フローチャートである。
【図８】ビット幅Ｎ＝１５のときの復号論理の一例を示す図である。
【図９】シードの割当を説明する図である。
【図１０】符号化の失敗例を示す図である。
【図１１】Ｎ＝１６のときの復号論理を示す図である。
【図１２】Ｎ＝１６のときの符号化結果を示す図である。
【図１３】本発明の第２の実施例を示すフローチャートである。
【図１４】ビットアサイン変更処理の詳細を示すフローチャートである。
【図１５】Ｘ数カウント結果の一例を示す図である。
【図１６】Ｘ数カウント結果に基づくビットソートの結果を示す図である。
【図１７】Ｘ数カウント結果に基づくマッピング結果を示す図である。
【図１８】図１７のビットアサインの結果として得られる符号化結果を示す図である。
【図１９】本発明の第２実施例の一変形を示すフローチャートである。
【図２０】図１９のビットアサイン変更処理の詳細を示すフローチャートである。
【図２１】Ｎ＝１３におけるマッピングを示す図である。
【図２２】Ｎ＝１５におけるマッピングを示す図である。
【図２３】本発明の第３の実施例を示すフローチャートである。
【図２４】Ｘ抽出を説明する図である。
【図２５】Ｘ抽出後に得られる符号化の復号論理を示す図である。
【図２６】Ｘ抽出後に得られる符号化の結果を示す図である。
【図１】
2004295833.tif 000003
【図２】
2004295833.tif 000004
【図３】
2004295833.tif 000005
【図４】
2004295833.tif 000006
【図５】
2004295833.tif 000007
【図６】
2004295833.tif 000008
【図７】
2004295833.tif 000009
【図８】
2004295833.tif 000010
【図９】
2004295833.tif 000011
【図１０】
2004295833.tif 000012
【図１１】
2004295833.tif 000013
【図１２】
2004295833.tif 000014
【図１３】
2004295833.tif 000015
【図１４】
2004295833.tif 000016
【図１５】
2004295833.tif 000017
【図１６】
2004295833.tif 000018
【図１７】
2004295833.tif 000019
【図１８】
2004295833.tif 000020
【図１９】
2004295833.tif 000021
【図２０】
2004295833.tif 000022
【図２１】
2004295833.tif 000023
【図２２】
2004295833.tif 000024
【図２３】
2004295833.tif 000025
【図２４】
2004295833.tif 000026
【図２５】
2004295833.tif 000027
【図２６】
2004295833.tif 000028