JPH0636014B2 - 回路ネット探索装置 - Google Patents

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は回路ネット探索装置に関し、特にプリント基板
に形成された配線パターンの正常・異常を検査する抵抗
検査に必要な情報を得るために用いられる回路ネット探
索装置に関する。

〔技術環境〕

近年、プリント基板は大型化，高密度化，多層化する傾
向にあり、これに伴いプリント基板上に導体で形成され
る配線パターンも細線化，複雑化し、長さも長くなる傾
向にある。

一方、配線パターンの形成技術は完全ではないため、配
線パターン同士の誤接続（ショート）や配線パターンの
断線（オープン）等の異常は依然として残っており、こ
れをどのように発見してゆくかが大きな問題となってい
る。

従来、配線パターンの正常・異常の検査は人間が目視で
行っていたが、上述の配線パターンの細線化，複雑化の
ため、人間の能力を超えるプリント基板が出現し、目視
検査に代わる機械による電気検査が重要な手段となって
きている。

電気検査には様々な手法があるが、中でも回路ネットと
呼ばれるひとつながりの配線パターンに属する二つの端
点間の電気抵抗を測定し、論理的な抵抗値と比較して回
路ネットの正否を判定する抵抗検査が有力である。原理
の簡単なこと、測定精度が良いこと、異常箇所を発見し
やすいことなどがその理由である。

しかし、抵抗検査においては、抵抗の論理値が必要なた
め、回路ネットの中でどのような経路を通って一つの端
点と他の端点とが接続されているから明らかにしなくて
はならない。回路ネット探索装置はこのために必要なも
のである。

〔従来の技術〕

第２図はプリント基板に形成された回路ネットの一例を
示す平面図である。一般にプリント基板上には多くの回
路ネットが形成されているが、説明を簡単にするため
に、第２図にはプリント基板１４上に回路ネット１５が
一つだけ形成されている例を示す。１２Ａ〜１２Ｇが回
路ネット１５の端点であり、１１Ａ〜１１Ｋが回路ネッ
ト１５を構成する枝（端点または分岐点間の配線素子）
である。１３Ａ〜１３Ｅは枝の分岐を表す分岐点であ
る。

従来の回路ネット探索装置は、回路ネット１５の抵抗検
査を行う際に測定の基準となる開始点を端点１２Ａとす
ると、端点１２Ａとそれに接続されている端点１２Ｂ，
１２Ｃ，１２Ｄ，１２Ｅ，１２Ｆ，１２Ｇとの各組合わ
せを出力するだけのものであった。

〔発明が解決しようとする課題〕

上述したように、従来の回路ネット探索装置は単に２点
間の接続・非接続の区別を出力するだけのものであり、
回路ネットを構成する枝の接続状態を明らかにすること
はできず、その結果から測定したい２点間の抵抗の論理
値を計算することはできなかった。従って、従来の抵抗
検査では、同じ回路ネット内の２点間の抵抗が無限大な
らば断線、異なる回路ネットに属する２点間の抵抗が有
限値ならばショートといった大づかみな検査しか行うこ
とができなかった。

このような事情から、抵抗の論理値との比較が必要な、
配線パターンの「やせ」や不完全な接続などを検出する
正確な検査は実現することができなかった。

本発明の目的は、上述の欠点を除去し、２点間の接続経
路情報を出力できる回路ネット探索装置を提供すること
である。

〔課題を解決するための手段〕

本発明の回路ネット探索装置は、プリント基板上に構成
された回路ネットの接続を探索する回路ネット探索装置
において、前記回路ネットを構成する枝の接続状態を記
憶した枝接続記憶部と、前記回路ネットの探索中の各時
点で枝の探索状態を記憶する枝探索記憶部と、前記枝接
続記憶部と枝探索記憶部中のデータを入力して探索を行
い前記回路ネットの開始枝と終端枝とを結ぶ枝経路デー
タを出力する探索部とを備え、前記探索記憶部が、探索
実施中の自枝とこの自枝の開始枝側に接続されている親
枝とを対として順次収納するスタック構造のオープンス
タックと、開始枝から始まり自枝に至る順序で相互に接
続している枝のリストを収納するスタック構造の経路ス
タックとを含み、前記探索部が、探索の始点となる開始
枝を検出し前記オープンスタック及び経路スタックの底
にプッシュする開始枝検出手段と、前記オープンスタッ
クの先頭が終端枝であるかどうかを判定し、終端枝であ
った場合にその時点の前記経路スタックの内容を枝経路
データとして出力し、その後前記オープンスタックの先
頭を廃棄し、前記経路スタックの内容を前記オープンス
タックの先頭の枝までの経路を表すように更新する終端
枝検出手段と、前記オープンスタックの先頭が終端枝で
ない場合に、その枝から分岐する枝のリストをオープン
スタックの先頭に置き換える分岐枝展開手段とを含んで
構成されている。

〔実施例〕

次に、本発明の実施例について図面を参照して説明す
る。

第１図は本発明の一実施例を示すブロック図である。

第１図に示す回路ネット探索装置は、回路ネットを構成
する枝の接続情報を記憶した枝接続記憶部１と、回路ネ
ットの探索中の各時点で枝の探索状態を記憶する枝探索
記憶部２と、枝接続記憶部１及び枝探索記憶部２のデー
タを用いて実際の探索処理を行う探索部３とから成り、
探索結果は経路データ４として出力される。枝探索記憶
部２はオープンスタック５と経路スタック６とから成
り、探索部３は開始枝検出部７と終端枝検出部８と分岐
枝展開部９とから構成されている。

本発明の機能を要約して述べれば、枝接続記憶部１には
回路ネットを構成する枝の枝名のセットが複数組収納さ
れており、この情報を入力とし、枝探索記憶部２を構成
するオープンスタック５及び経路スタック６を作業用記
憶装置として用いながら、探索部３が回路ネットの開始
枝とすべての終端枝とを結ぶ枝接続経路情報を経路デー
タ４として出力することである。

第２図を用いて具体的に述べると、次のようになる。枝
接続記憶部１には、回路ネット１５を構成している枝１
１Ａ〜１１Ｋの接続情報が収納されており、これが入力
となる。回路ネット１５の端点１２Ａを開始点とすれ
ば、枝１１Ａが開始枝となる。探索部３が作動すると、
出力には、最初に（１１Ａ，１１Ｂ，１１Ｃ，１１Ｄ，
１１Ｅ）が経路データ４として得られる。つまり、開始
点１２Ａと終端点１２Ｂを結ぶ枝接続経路情報が得られ
たことになる。この場合、終端枝は１１Ｅである。同様
にして終端点１２Ｃに対しては（１１Ａ，１１Ｂ，１１
Ｃ，１１Ｄ，１１Ｆ）が、終端点１２Ｄに対しては（１
１Ａ，１１Ｂ，１１Ｃ，１１Ｄ）が、終端点１２Ｇに対
しては（１１Ａ，１１Ｉ，１１Ｋ）が経路データ４とし
て出力される。終端点１２Ｂ〜１２Ｇに対応して合計６
組が経路データ４として出力される。

以下、枝接続記憶部１，枝探索記憶部２及び探索部３の
動作について詳細に説明する。

第３図は枝接続記憶部１の詳細構成図である。第２図に
示すように、端点１２Ａに接続された枝１１Ａには、枝
１１Ｂと枝１１Ｉとが接続している。この互いに接続し
ている枝の枝名の対（１１Ａ，１１Ｂ）及び（１１Ａ，
１１Ｉ）が、枝接続ペアとして枝接続記憶部１に収納さ
れている。以下、回路ネット１５に含まれるすべての接
続関係のある枝接続ペアが枝接続記憶部１に収納されて
いる。枝接続ペアの配列の順序には様々なものが考えら
れるが、ここでは説明を簡単にするため、枝１１Ａに近
いものから配置されている。第３図には、第２図に示す
回路ネット１５について、端点１２Ａを開始点とした枝
接続ペアの組を示したが、他の端点１２Ｂ〜１２Ｇを開
始点とした枝接続ペアの組を収納しておいてもよい。こ
れらは、分岐点１３Ａ〜１３Ｅを含む回路ネット１５の
接続情報からあらかじめ作成することができる。

第４図はオープンスタック５の詳細構成図である。この
スタックは、各項が自枝名３１と親枝名３２の二つの要
素から構成されている。今取扱おうとしている枝が自枝
であり、自枝に接続している枝のうち開始枝に近いもの
が親枝である。例えば、枝１１Ｈの親枝は、第２図から
１１Ｂであることが分かる。

第５図は経路スタック６の詳細構成図である。このスタ
ックは、各項とも経路枝名４１の１要素のみから構成さ
れ、スタックの底から先頭までの枝名の列が開始枝から
現在扱っている自枝までの経路を表すようになってい
る。

第６図は開始枝検出部７の動作説明用のブロック図であ
る。開始枝検出部７は枝接続記憶部１に収納されている
枝の中から開始枝を検出する。検出の方法としては、第
３図に示す枝接続ペアのうち左側の項にだけ現れるもの
を検索し開始枝とすればよい。従って、開始枝は１１Ａ
になる。開始枝が発見されたら、それをオープンスタッ
ク５及び経路スタック６の底にプッシュする。開始枝の
親枝は存在しないのでオープンスタック５の親枝名には
なにも入れないでおく。

第７図は終端枝検出部８の動作の流れを示すフローチャ
ート、第９図は終端枝検出部８の動作説明用のブロック
図である。

まず、終端枝検出部８はオープンスタック５が空である
かどうかを確認する。空の場合はそこで終了となる（Ｓ
１０１）。

次にオープンスタック５の先頭の自枝名が終端枝である
かどうかを確認する（Ｓ１０２）。オープンスタック５
の先頭の自枝名が終端枝でない場合には、その枝は分岐
枝であるから、分岐枝信号１０を出力し、分岐枝展開部
９を動作させ（Ｓ１０７）、その終了を待合わせる（Ｓ
１０８）。終端枝であるかないかは、問題の枝が枝接続
記憶部１を構成する枝接続ペアの左側の項に現れるかど
うかで判定できる。第８図の例ではオープンスタック５
ａの先頭の自枝名は１１Ｅであるから、第３図を見れば
分かるとおり、これは枝接続ペアの左側の項には現れな
い。従って終端枝である。

終端枝であった場合は、その時点で経路スタック６の内
容をそのまま経路データ４として出力する（Ｓ１０
３）。そしてオープンスタック５の先頭を廃棄する（Ｓ
１０４）。第８図の例では先頭の項（自枝名１１Ｅ，親
枝名１１Ｄ）が廃棄されてオープンスタック５ｂのよう
になる。

続いて、オープンスタック５の先頭の親枝名と同じ経路
枝名を経路スタック６から探し、この経路枝名よりも浅
い部分を経路スタック６から廃棄する（Ｓ１０５）。そ
して、オープンスタック５の先頭の自枝名を経路スタッ
ク６にプッシュする（Ｓ１０６）。第８図の例では、オ
ープンスタック５ｂの先頭親枝名は１１Ｄであるから、
ステップＳ１０５により、経路スタック６ａの中の経路
枝名１１Ｄより浅い部分、つまり１１Ｅが廃棄される。
そしてオープンスタック５ｂの先頭の自枝名は１１Ｆで
あるから、ステップＳ１０６により経路スタック６の先
頭に１１Ｆがプッシュされ、結果的に経路スタック６ｂ
に示した結果が得られる。

第９図は分岐枝展開部９の動作説明用のブロック図であ
る。上述したように、分岐枝展開部９はオープンスタッ
ク５の先頭の自枝名が終端枝を表さない場合に分岐枝信
号１０により起動される。分岐枝展開部９は枝接続記憶
部１を参照し、オープンスタック５の先頭の自枝名が表
す枝から分岐する枝（複数あることもある）の枝名で、
オープンスタック５の先頭の自枝名を置き換える。置き
換えられた新しいオープンスタック５の先頭の親枝名は
以前の先頭の自枝名である。そして、オープンスタック
５の先頭の自枝名を経路スタック６にプッシュする。

この実施例では、ある自枝名が表す枝から分岐する枝
は、枝接続記憶部１中の枝接続ペアの左側の項がその自
枝名と一致するすべての枝接続ペアの右側の項を抽出す
れば得られる。分岐する枝が複数あるときには、その分
岐枝名を降順でソートし、ソートした順でオープンスタ
ック５の先頭を置き換えるものとする。

第９図に示すた例では、オープンスタック５ｃの先頭の
自枝名は１１Ａであるから、枝接続記憶部１を見ると、
１１Ａを枝接続ペアの左側の項に持つものは二つある。
これらの枝接続ペアの右側の項は１１Ｂと１１Ｉである
から、これらを自枝名とし、親枝名を以前の自枝名１１
Ａとした項でオープンスタック５ｃの先頭を置き換え
る。置き換えるとき分岐枝名は降順でソートされるか
ら、１１Ｉ，１１Ｂの順でプッシュされる。その結果第
９図のオープンスタック５ｄが得られる。経路スタック
６ｃにはオープンスタック５ｄの先頭の自枝名１１Ｂが
プッシュされるから、経路スタック６ｄの結果となる。

第１０図は上記の実施例の全体の処理を第２図に示す回
路ネット１５に施した場合の状態遷移図である。時刻の
項は本実施例の状態が変化する時点を表す。

まず、時刻０において、上述のように開始枝検出部７が
起動され、オープンスタックの自枝名および経路スタッ
クに開始枝名１１Ａがプッシュされる。オープンスタッ
クの先頭の自枝名１１Ａは終端枝ではないので、時刻１
には分岐枝展開部９によって起き換えられ、オープンス
タックの自枝名には底から順に１１Ｉ，１１Ｂが入り、
経路スタックには１１Ｂがプッシュされる。

同様に時刻３までは置き換え処理だけが行われる。

時刻４では、オープンスタックの先頭の自枝名１１Ｅが
終端枝検出部８により終端枝であると判断される。この
時、経路スタックの内容（底から順に１１Ａ，１１Ｂ，
１１Ｃ，１１Ｄ，１１Ｅ）が経路データとして出力され
る。そして、オープンスタックの先頭が廃棄され、それ
に伴って経路スタックの内容も更新される。

同様にして、上に詳述した分岐枝展開部９の動作によ
り、時刻５，６，７，９，１０で経路データが出力され
る。最後に、時刻１０でオープンスタックの自枝名が１
１Ｋとなり、これは終端枝であるので廃棄され、時刻１
１ではオープンスタックは空になる。終端枝検出部８は
これを検出してこの回路ネットの探索処理を終了する。

〔発明の効果〕

以上詳細に説明したように、本発明の回路ネット探索装
置は、回路ネット全体を探索し回路ネットに属する開始
点と終端点とのみならず、開始点と終端点を結ぶ枝接続
経路情報も出力するので、正確な抵抗検査用のデータの
作成を可能にするという効果がある。

【図面の簡単な説明】

第１図は本発明の一実施例を示すブロック図、第２図は
本発明が扱う回路ネットの一例を示す平面図、第３図は
第１図に示す枝接続記憶部の詳細構成図、第４図は第１
図に示すオープンスタックの詳細構成図、第５図は第１
図に示す経路スタックの詳細構成図、第６図は第１図に
示す開始枝検出部の動作ブロック図、第７図は第１図に
示す終端枝検出部の概略動作のフローチャート、第８図
は第１図に示す終端枝検出部の動作ブロック図、第９図
は第１図に示す分岐枝展開部の動作ブロック図、第１０
図は本発明の一実施例の状態遷移図である。 １……枝接続記憶部、２……枝探索記憶部、３……探索
部、４……経路データ、５……オープンスタック、６…
…経路スタック、７……開始枝検出部、８……終端枝検
出部、９……分岐枝展開部、１０……分岐枝信号、１１
Ａ〜１１Ｋ……枝、１２Ａ〜１２Ｇ……端点、１３Ａ〜
１３Ｅ……分岐点、１４……プリント基板、１５……回
路ネット。

Claims (1)

【特許請求の範囲】
1. 【請求項１】プリント基板上に構成された回路ネットの
   接続を探索する回路ネット探索装置において、前記回路
   ネットを構成する枝の接続状態を記憶した枝接続記憶部
   と、前記回路ネットの探索中の各時点で枝の探索状態を
   記憶する枝探索記憶部と、前記枝接続記憶部と枝探索記
   憶部中のデータを入力して探索を行い前記回路ネットの
   開始枝と終端枝とを結ぶ枝経路データを出力する探索部
   とを備え、 前記探索記憶部が、探索実施中の自枝とこの自枝の開始
   枝側に接続されている親枝とを対として順次収納するス
   タック構造のオープンスタックと、開始枝から始まり自
   枝に至る順序で相互に接続している枝のリストを収納す
   るスタック構造の経路スタックとを含み、 前記探索部が、探索の始点となる開始枝を検出し前記オ
   ープンスタック及び経路スタックの底にプッシュする開
   始枝検出手段と、前記オープンスタックの先頭が終端枝
   であるかどうかを判定し、終端枝であった場合にその時
   点の前記経路スタックの内容を枝経路データとして出力
   し、その後前記オープンスタックの先頭を廃棄し、前記
   経路スタックの内容を前記オープンスタックの先頭の枝
   までの経路を表すように更新する終端枝検出手段と、前
   記オープンスタックの先頭が終端枝でない場合に、その
   枝から分岐する枝のリストをオープンスタックの先頭に
   置き換える分岐枝展開手段とを含むことを特徴とする回
   路ネット探索装置。