JPH0223902B2 - - Google Patents

Description

【発明の詳細な説明】

（産業上の利用分野） この発明は、プリント板、LSIなどの配線経路
決定装置に関する。 （従来の技術） 従来、プリント板、LSIなどの基板上における
配線経路決定は、デイスプレイ上にプリント板等
を表示してキーボードからの指示により配線経路
を決定する配線経路決定装置により行なわれてい
る。このような配線経路決定装置において、配線
すべき全ての端子間配線経路が決定されていない
場合は、その未配線経路を決定するために、配線
用端子と配線用端子間の配線経路をデイスプレイ
上に表示し（以下、デイスプレイ上に表示された
配線経路を配線パターンという）、表示された配
線パターンをオペレータが試行錯誤的に既配線パ
ターンを消去し、未配線端子間の配線経路を含め
た新たな配線経路を決定する方法が採られてい
た。 （発明が解決しようとする問題点） 従つて、このような従来の配線経路決定装置に
あつては、配線経路の決定に多くの時間がかか
り、またオペレータが試行錯誤的に決定した新た
な配線経路が最適なものであるかどうかが不明で
あるという問題点を有する。 この発明はこれらの問題点を解決し、未配線端
子間の配線経路を決定する場合に、修正されるべ
き最適な既配線パターンを計算処理してオペレー
タに知らせ、試行錯誤によらず、最適な配線経路
を決定することができる配線経路決定装置を提供
することを目的とする。 （問題点を解決するための手段） この発明の配線経路決定装置は、配線により接
続されるべき基板上の第１及び第２の端子間の未
配線経路を決定すると共に、前記未配線経路を含
む前記基板上の配線のパターンを表示するデイス
プレイを有するものであつて、前記第１の端子を
含む前記基板上の１の領域からその周辺の領域へ
ウエーブを発生させると共に前記ウエーブが既配
線経路を乗り越えて他の領域に進む度にウエーブ
数を増加させる形式により、前記基板上の全領域
にそれぞれウエーブ数を設定させる第１の手段
と、前記第１の手段により設定された複数領域の
前記ウエーブ数が連続し、且つそれらの領域が互
いに隣接しているときは、これらの領域をアクテ
イブ領域として設定する第２の手段と、互いに隣
接する２つの前記アクテイブ領域における前記ウ
エーブ数が異なるときは、これら前記アクテイブ
領域の境界上の任意点にアクテイブ点を設定する
第３の手段と、前記第１の端子から前記アクテイ
ブ点を含む前記アクテイブ領域を介して前記第２
の端子に至る未配線経路を設定する第４の手段
と、前記第４の手段により設定された前記未配線
経路が複数存在するときは、前記未配線経路を距
離が短い順に前記デイスプレイ上に表示させる第
５の手段と設けたことを特徴とする。 （作用） この発明の配線経路決定装置によれば、設定さ
れた前記アクテイブ領域に従つて前記第１及び第
２の端子間に未配線経路を決定する処理が効率よ
く実行されると共に、設定された前記未配線経路
が複数存在するときは、前記経路を距離が短い順
に前記デイスプレイ上に表示されるので、最短距
離となる未配線経路を選択することを容易なもの
にする。また、このようにして決定した未配線経
路を更に合理的なものにするために、既配線経路
の変更を含めた総括的な修正処理も容易に実行可
能にする。 （実施例） 以下、この発明を一実施例に基づき図面を参照
して詳細に説明する。第１図及び第２図は、この
発明の一実施例を示すブロツク図である。第１図
において、１０はキーボード、１１はデイスプレ
イ、１２はインタフエース部、１３はキーボード
１０からのコマンドを解読するコマンド解読処理
部、１４はデイスプレイ１１に配線パターンを表
示させる配線パターン表示処理部、１６は記憶部
１９からの配線端子データ及び端子間配線データ
に基づき配線経路を決定する配線経路決定処理
部、１７はコマンド解読処理部１３、配線パター
ン表示処理部１４、配線経路決定処理部１６、及
びこの発明により設けられた修正対象既配線パタ
ーン検出処理制御部１５（詳細は後述する）を制
御する配線経路決定制御部、１８は配線パターン
表示処理部１４、修正対象既配線パターン検出処
理部１５及び配線経路決定処理部１６と、記憶部
１９とのインタフエースを司るフアイル入出力
部、及び１９は配線端子データ、端子間配線経路
データ及び未配線端子データを格納する記憶部で
ある。 第２図は、第１図に示す修正対象既配線パター
ン検出処理制御部１５により制御される各構成要
素を示すブロツク図である。同図において、２０
は既配線パターンを複数の領域に分類するため
に、未配線端子の一方からウエーブを送出するた
めの制御を行なうウエーブ発生部、２１はアクテ
イブ領域判定処理部であり、ウエーブ発生部２０
が発生するウエーブによつて、基板上で互いに隣
接する３つの領域に設定されたウエーブ数が、以
下で説明する表に示すように、ウエーブの発生サ
イクル上で連続的な関係があるときは、これらの
領域がアクテイブ領域であると判定する処理を実
行するものである。このようなアクテイブ領域
は、第３図に示すように、配線の決定により互い
に接続されるべき未配線端子Ａと未配線端子Ｂと
の間を接続する未配線経路を決定する際に、基板
上の既配線パターンがその障害となつているとき
は、その経路変更のための処理（以下、第４図を
参照して説明する。）の回数を最小限にするのに
有効に利用される。２２はアクテイブ領域をスタ
ツク状に格納するアクテイブ領域スタツク、２３
はアクテイブ領域中の隣接する領域の境界上の任
意の点であるアクテイブ点を抽出するアクテイブ
点抽出処理部、２４はアクテイブ点をスタツク状
に格納するアクテイブ点スタツク、２５は未配線
端子の一方から抽出されたアクテイブ点が設けら
れた境界を通りもう一方の未配線端子に至る最短
距離の配線経路を求め、距離の短い順にソーイン
グする最短距離算出兼ソーイング処理部、及び２
６は得られた修正すべき既配線パターンを示すア
クテイブ点に従つてデイスプレイ１１上の既配線
パターンを自動的に変更する既配線パターン自動
変更処理部である。 次に動作について説明する。 はじめに、この実施例において処理される既配
線パターンの一例を第３図に示す。同図におい
て、１はピン端子、中継端子、電源端子、接地端
子等の配線端子、２は既配線パターン、３はプリ
ント板等におけるメツシユである。４は本来配線
されるべき未配線端子Ａ，Ｂを直線で結んだもの
で、未配線表示を示す。この実施例においては、
２層プリント板を例に説明する。すなわち、第３
図は配線が第１層のみで行なわれている状態であ
り、第１層での配線パターンは太い実線で示して
ある。尚、説明を簡単にするために、第２層での
配線処理は最初禁止されているものとする。 次に、この実施例による配線経路決定の動作
を、第４図ａ〜ｅの動作フローチヤートに従つて
説明する。 まず、キーボード１１より未配線端子の配線指
令を発信する。これにより、記憶部１９に格納さ
れている未配線端子情報がフアイル入出力部１８
を介して修正対象既配線パターン検出処理制御部
１５に読込まれる。すなわち、第３図の既配線パ
ターンにおいては、未配線端子Ａ，Ｂが抽出さ
れ、読込まれる（第４図ａのステツプ30）。次に
ウエーブ（WAVE）発生部２０は未配線端子Ａ
を含む領域から順次領域内のメツシユにウエーブ
を発生させる（ステツプ31）。ウエーブは各領域
を分類するもので、ステツプ３２に示すように、
次の３つの条件に従つて発生する。第１に、ウエ
ーブはサイクリツクに１→２→３→１→２→３…
の順番で発生する。第２に、閉じた領域内は同一
のウエーブとする。第３に、ウエーブは隣接する
領域間の境界も乗り越えて発生する。このステツ
プ32は、未配線端子Ｂを含む領域にウエーブが発
生するまで繰返される（ステツプ33）。この結果、
第３図の既配線パターンに囲まれた領域は、第５
図に示すように分類される。同図からわかるよう
に、Ａ点を含む領域ウエーブ１となり、これに隣
接する領域ウエーブ２となり、更にこれに隣接す
る領域はウエーブ３となる。更に、ウエーブ３に
隣接する領域ウエーブ１となり、この結果Ｂ点を
含む領域ウエーブ１となる。 次に、アクテイブ領域判定処理部２１は、Ａ点
を含む領域から開始し、ウエーブ番号を１→２→
３→１→２…の順番で、各々の閉じた領域が、下
記表により定義されるアクテイブ領域条件に合致
するアクテイブ領域であるか、又はパツシブ領域
（この定義は後述する）であるかを判定する（第
４図ｂのステツプ34の前半部分）。

【表】 このようにして判定されたアクテイブ領域を第
６図に示す。図中、斜線で示された領域がアクテ
イブ領域である。同図からわかるように、アクテ
イブ領域Ａ，Ａ２１，Ａ２２，Ａ３１，Ａ３２及
びＢの領域である。尚、図中パツシブ領域とはア
クテイブ領域以外の領域、換言すればアクテイブ
領域の連鎖が跡切れる領域である。 次に、アクテイブ領域判定処理部２１はＡ点か
らＢ点に至るアクテイブ領域の連鎖を求める。こ
の領域連鎖は一般に複数個存在し、経路（パス）
と呼ばれる。第７図に、第６図におけるＡ点から
Ｂ点の領域連鎖を示す。第７図からわかるよう
に、この場合の領域連鎖はＡ→Ａ２１→Ａ３１→
Ｂと、Ａ→Ａ２２→Ａ３２→Ｂの２つ存在する。 このようにして得られた領域連鎖は、その発生
順序（Ａ点からＢ点に至るアクテイブ領域の順
序）に従つて、アクテイブ領域スタツク２２に登
録される（第４図ｂのステツプ34の後半部分）。
第８図に、アクテイブ領域スタツク２２に登録さ
れたアクテイブ領域の様子を示す。図中、AD_aは
アクテイブ領域スタツク２２のスタツクアドレス
を示し、AD_b及びAD_cはスタツクアドレスAD_aに
格納されたアクテイブ領域に領域連鎖するアクテ
イブ領域に関するアクテイブ領域スタツク２２の
スタツクアドレスAD_aを示す。例えば、スタツク
アドレスAD_aのアドレス０にはアクテイブ領域Ａ
が格納され、このアクテイブＡはアクテイブ領域
Ａ２１及びＡ２２に領域連鎖するので、スタツク
アドレスAD_b及びAD_cにはそれぞれスタツクアド
レス１及び２が格納される。尚、図中の右側に示
されている矢印はこの領域連鎖を示す。 次に、アクテイブ点抽出処理部２３は、アクテ
イブ領域スタツク２２に登録されたアクテイブ領
域の領域連鎖に基づいて経路を求め、各経路につ
いてアクテイブ点を求める（第４図ｃのステツプ
35の前半部分）。ここで、アクテイブ点は経路上
の隣接するアクテイブ領域の境界上の任意の点と
定義される。例えば、アクテイブ点抽出処理部２
３は領域連鎖の一方、例えばＡ→Ａ２１→Ａ３１
→Ｂからパス１を得、他方の領域連鎖Ａ→Ａ２２
→Ａ３２→Ｂからパスを得、第９図の▲印で示さ
れるアクテイブ点を求める。第９図において、パ
ス１のアクテイブ点はＰ１１，Ｐ１２及びＰ１３
であり、パス２のアクテイブ点はＰ２１，Ｐ２２
及びＰ２３である。 このようにして得られたアクテイブ点は、第１
０図に示す如く、パス番号とともにアクテイブ点
スタツク２４に登録される。（第４図ｃのステツ
プ35の後半部分）。第１０図において、AD′_aはア
クテイブ点スタツク２４のスタツクアドレスを示
し、AD′_bはスタツクアドレスAD_aに格納された
パス番号又はスタツク点に続くアクテイブ点に関
するスタツクアドレスAD′_aを示す。例えば、ス
タツクアドレスAD′_aのアドレス０にはパス番号
が１、すなわちパス１が格納され、このパス１は
アクテイブ点Ｐ１１に続くので、スタツクアドレ
スAD′_bにはスタツクアドレス１が格納される。 次に、最短距離算出兼ソーイング処理部２５
は、アクテイブ点スタツク２４に登録された各経
路ごとに、Ａ点から当該経路のアクテイブ点で示
された隣接するアクテイブ領域の境界を通つてＢ
点に至る最短距離を算出する（第４図ｄのステツ
プ36の前半部分）。次に、最短距離算出兼ソーテ
イング処理部２５は、各経路ごとに算出された距
離を比較して、各経路の距離をその短い順にソー
テイング（並び替え）する（第４図ｄのステツプ
36の後半部分）。デイスプレイ１１はソーテイン
グ結果に基づき、距離の短い順に、経路上のアク
テイブ点を高輝度で表示する（第４図ｄのステツ
プ37）。第１１図はデイスプレイ１１に表示され
たパス２のアクテイブ点Ｐ２１，Ｐ２２及びＰ２
３を示す。パス２の距離はパス１の距離より短い
ので、最初パス２のアクテイブ点が表示される。 オペレータはデイスプレイ１１上のアクテイブ
点の表示に基づき、アクテイブ点上の既配線パタ
ーンを修正するために、キーボード１０からの手
段動操作又は既配線パターン自動変更処理部２６
による自動修正のいずれか一方を選択する（第４
図ｅのステツプ38）。この選択はキーボード１０
を介して行なわれる。キーボード１０からの手動
操作が選択されたときは（第４図ｅのステツプ
39）、オペレータはアクテイブ点上の既配線パタ
ーンやこれらの周囲の既配線パターンの混み具合
い等を判断し、（第４図ｅのステツプ41）、経路変
更が可能であれば、既配線パターンの経路変更に
行ない、Ａ点とＢ点との間の配線経路を人為的に
又は自動的に決定する（第４図ｅのステツプ42）。
例えば、オペレータは第１１図に示されたデイス
プレイ１１の上のパス２のアクテイブ点をみて、
破線の如き最短距離経路４６に基づき既配線パタ
ーンの経路変更が可能であると判断し、第１２図
に示す如く既配線パターンを修正する。尚、図中
４３は迂回された既配線パターン、４４は移動さ
れた既配線パターン、４５はAB点間の配線経路
である。一方、既配線パターン自動変更処理部２
６による自動修正（第４図ｅのステツプ40）は、
配線パターン表示処理部１４から既配線パターン
等のデータを読込み前述したようなアクテイブ点
上の既配線パターンやこれらの周囲の既配線パタ
ーンの混みぐあいを既配線パターン自動変更処理
部２６が計算し、計算結果に基づいて経路変更が
可能であれば、既配線パターンを自動的に修正す
ることにより行なわれる。 一方、仮にステツプ41で経路変更が不可とされ
た場合、すなわちこの場合パス２に基づく経路変
更は不可であるとされた場合は、第４図ｄのステ
ツプ37に戻る。この結果、デイスプレイ１１には
パス１のアクテイブ点が表示される。オペレータ
はパス２の場合と同様の操作により、既配線パタ
ーンの経路変更を行なう。 （発明の効果） 以上説明したように、この発明によれば、第１
の端子を含む基板上の１の領域からその周辺の領
域へウエーブを発生させ、これによつて設定され
たウエーブ数が連続している領域をアクテイブ領
域として設定し、更に互いに隣接し、かつウエー
ブ数が異なるアクテイブ領域の境界上の任意点に
アクテイブ点を設定し、前記第１の端子から前記
アクテイブ点を含む前記アクテイブ領域を介して
接続相手の第２の端子に至る経路を設定し、設定
された前記経路距離が短い順に前記デイスプレイ
上に表示させるように構成したので、所望の未配
線経路の決定を効率よく、かつ合理的に決定する
ことが容易なり、また、このようにして設定され
た未配線経路を更に合理的なものにするために、
既配線経路の変更処理を含めた総括的な配線経路
の設定も容易となる効果もある。

【図面の簡単な説明】

第１図及び第２図はこの発明の一実施例のブロ
ツク図、第３図はこの発明により処理される既配
線パターンを示す図、第４図ａ〜ｅはこの実施例
の動作のフローチヤート、第５図はウエーブによ
り分類された領域を示す図、第６図はパツシブ領
域とアクテイブ領域を示す図、第７図は第６図に
基づき得られる経路を示す図、第８図はアクテイ
ブ領域スタツクの内容を示す図、第９図は第８図
に基づき得られるアクテイブ点を示す図、第１０
図はアクテイブ点スタツクの内容を示す図、第１
１図はデイスプレイ上に表示されたアクテイブ点
を示す図、及び第１２図は経路変更された結果を
示す図である。 １０……キーボード、１１……デイスプレイ、
１２……インタフエース部、１３……コマンド解
読処理部、１４……配線パターン表示処理部、１
５……修正対象既配線パターン検出処理制御部、
１６……配線経路決定処理部、１７……配線経路
決定制御部、１８……フアイル入出力部、１９…
…記憶部、２０……ウエーブ発生部、２１……ア
クテイブ領域領域判定処理部、２２……アクテイ
ブ領域スタツク、２３……アクテイブ点抽出処理
部、２４……アクテイブ点スタツク、２５……最
短距離算出兼ソーテイング処理部、２６……既配
線パターン自動変更処理部。

Claims (1)

1. 【特許請求の範囲】 １ 配線により接続されるべき基板上の第１及び
   第２の端子間の未配線経路を決定すると共に、前
   記未配線経路を含む前記基板上の配線のパターン
   を表示するデイスプレイを有する配線経路決定装
   置において、 前記第１の端子を含む前記基板上の１の領域か
   らその周辺の領域へウエーブを発生させると共に
   前記ウエーブが既配線経路を乗り越えて他の領域
   に進む度にウエーブ数を増加させる形式により、
   前記基板上の全領域にそれぞれウエーブ数を設定
   させる第１の手段と、 前記第１の手段により設定された複数領域の前
   記ウエーブ数が連続し、且つそれらの領域が互い
   に隣接しているときは、これらの領域をアクテイ
   ブ領域として設定する第２の手段と、 互いに隣接する２つの前記アクテイブ領域にお
   ける前記ウエーブ数が異なるときは、これら前記
   アクテイブ領域の境界上の任意点にアクテイブ点
   を設定する第３の手段と、 前記第１の端子から前記アクテイブ点を含む前
   記アクテイブ領域を介して前記第２の端子に至る
   未配線経路を設定する第４の手段と、 前記第４の手段により設定された前記未配線経
   路が複数存在するときは、前記未配線経路を距離
   が短い順に前記デイスプレイ上に表示させる第５
   の手段と を設けたことを特徴とする配線経路決定装置。