JPH0683911A - 配線経路決定方法及びその装置 - Google Patents

Abstract

(57)【要約】 【目的】 レイアウトモデルによらずバス構造を考慮し
た配線経路を決定することができる。 【構成】 隣接平行走行条件を満す部分経路の群を作成
し、所望の配線対象区間に対し、部分経路の群の中から
特定の部分経路の群を選択する。そして配線対象区間に
対する配線経路に対して、特定の部分経路の群の属する
位置情報及び線路幅情報を基に配線禁止領域を設定する
と共に配線禁止領域の周囲に配線許容領域を設定する。
そして配線許容領域内で配線経路の探索を実行する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は配線経路決定方法及びそ
の装置に係り、特に、プリント基板上に論理回路などの
配線パターンを形成する際の配線経路を自動的に決定す
るに好適な配線経路決定方法及びその装置に関する。

【０００２】

【従来の技術】ＶＬＳＩ、プリント基板に対する配線設
計を行なうための配線設計自動化システムにおいては、
コンピュータなど論理装置の高性能化に伴ない、バス配
線など回路の機能的側面を考慮したシステムの必要性が
高まっている。このようなシステムに採用された従来の
自動配線方法のうちバス配線構造を考慮したものとして
は、第２１回 デザイン オートメーション コンファ
レンス プロシーディングス、第６７９頁〜第６８２頁
（proceedings 21st Design AutomationConference,pp.
679-682）において論じられている方法が知られてい
る。この種の従来技術においては、ＶＬＳＩなどを対象
としたレイアウトモデルのレイアウト領域を端子や素子
などを配置するための配置領域とパターンを配線するた
めの配線領域とに分離し、バス構造を考慮した構成が採
用されている。すなわち、チャネル配線法をベースとし
た２段階配線において、「第１段階である概略配線時
に、同一のバスに属すネット群を同一の配線領域に割り
当てる。」ことにある。その後第２段階で、各配線領域
毎にチャネル配線法による詳細配線を行なうことによ
り、同一バスに属すネット群に対し、束線状の配線経路
（すなわちバス構造にかなった配線経路）の発生を可能
としている。

【０００３】一方、論理装置の高性能化を達成すると共
に回路の安定動作を保証するためには、特にプリント基
板に対する配線設計において、さまざまな電気特性上の
対策が必要である。このうち近年特に重要となってきた
のは、同一配線層内の隣接平行配線パターンに起因する
クロストークノイズの対策である。このようなクロスト
ークノイズは、一般に、２本以上平行して配線された信
号線間において引き起こされる電気的エネルギーの結合
に起因して発生する。このクロストークノイズの対策に
は、「平行線の間隔を広くとる」か、または「平行線の
長さを短くする」ことが必要である。そこで、プリント
基板に対する配線設計自動化システムにおいては、「平
行線の間隔を広くとる」ことに関して、２信号線間が満
すべき最少導体間隔を順守しつつ配線経路を決定すると
いう一般的な方法が広く採用されている。この方法によ
れば、一対の配線パターンを平行に配線した場合でも、
各配線パターン間の間隔はクロストークを考慮した最少
導体間隔で配線されているため、２本の平行配線の間隔
に起因するクロストーク低減に対し充分な対策を行なう
ことができる。また「平行線の長さを短くする」ことに
関しては、１９８６年アイ・イー・イー・イー インタ
ーナショナル コンファレンス オン コンピュータ・
エーデッド デザイン プロシーディングス、第２５０
頁〜第２５３頁（proceedings 1986 IEEE Internationa
l Conference on Computer-AidedDesign(ICCAD-86),pp.
250-253)に論じられている方法がある。この方法によれ
ば、平行に配線された配線パターン長に制限値を設け、
この制限値以内で各信号線に対する配線経路を決定する
ことができる。この結果、平行配線の長さに起困するク
ロストーク低減に対し充分な対策を行なうことができ
る。また更に、以上述べた２つの方法、すなわち「平行
線の間隔を広くとる」方法及び「平行線の長さを短くす
る」方法は、互いに組み合わされて実施されるのが一般
的である。

【０００４】

【発明が解決しようとする課題】上記従来技術のうちバ
ス構造を考慮した自動配線方法においては、ＶＬＳＩな
どそのレイアウト領域が配置領域と配線領域とに分離で
きるレイアウトモデルに対しては、バス構造にかなった
配線経路を決定することができる。しかし、プリント基
板のようなレイアウトモデルに対しては、基板上に搭載
される部品同士の間隔が極めて密であり、部品配置領域
も配線領域として用いなければ全ての部品の配線を行な
うことができない。従って、このようなレイアウトモデ
ルにおいては、レイアウト領域を配置領域と配線領域と
に分離することが困難であり、各ネットに対する配線経
路を決定するに際しては、迷路法、線分探索法により１
ネットずつ独立に行なわなければならず、結果として、
バス構造にかなった配線経路を決定することが困難であ
る。

【０００５】またクロストークを考慮した従来の自動配
線方法においては、相隣接して互いに平行に配線された
一対の信号線間に対しては、クロストークを考慮した配
線経路を決定することができる。しかし、隣接して３本
以上平行に配線された信号線間に対しては、一般には、
それらの配線相互間の結合に起因するノイズの重ね合わ
せとしてクロストークノイズが発生するため、平行に配
線された信号線の配線本数が多くなるほど大きなクロス
トークノイズが発生する。この結果、従来技術を単に適
用してもクロストークノイズを充分に低減することがで
きない場合がある。例えば、３本の信号線を互いに平行
に配線した場合、真中の信号線に対してその両側の信号
線に対する導体間隔をクロストークを考慮した間隔に保
って各信号線を配線しても、真中の信号線に対しては両
側の信号線との結合に起因するノイズが重畳し真中の信
号線には大きなクロストークノイズが発生する。更に４
本の信号線を互いに平行に配線した場合には、両端以外
の信号線に対しては、各信号線との結合に起因するノイ
ズが重畳し、大きなクロストークノイズが発生する。こ
のクロストークノイズは、対象とする論理装置の動作速
度が速くなるほど顕著になる。

【０００６】本発明の第１の目的は、レイアウトモデル
によらずバス構造を考慮した配線経路を決定することが
できる配線経路決定方法及びその装置を提供することに
ある。

【０００７】本発明の第２の目的は、隣接して３本以上
平行に配線される配線パターンに対してクロストークノ
イズを考慮した配線経路を決定することができる配線経
路決定方法及びその装置を提供することにある。

【０００８】

【課題を解決するための手段】前記目的を達成するため
に、本発明は、第１の方法として、プリント基板上の配
線対象区間を複数の端子で特定し、この配線対象区間を
結ぶ配線パターンの配線経路を迷路法または線分探索法
で決定するに際して、既に配線経路の決定された配線パ
ターンの配線経路を線路長に応じて複数の部分経路に分
割し、各部分経路を線路間隔と線路の平行条件から複数
のグループに分類し、各グループに属する部分経路の位
置情報と線路幅情報を記憶し、その後配線経路未定の配
線対象区間を特定する複数の端子に関する位置情報を入
力し、この入力情報と配線経路の決定された配線パター
ンに関する情報を基に配線経路の決定された端子群の中
から配線対象区間近傍で且つ配線対象区間と同一バスに
属する端子群を選択し、選択した端子間を結ぶ部分経路
を選択し、選択した各部分経路の属するグループを選択
し、選択した各グループに属する部分経路に関する位置
情報と線路幅情報を入力し、入力した位置情報と線路幅
情報を基に各部分経路に対する配線禁止領域をグループ
毎に設定し、各配線禁止領域の周囲に配線対象区間の配
線経路として許容される配線許容領域を設定し、各グル
ープの配線許容領域の集合を配線経路探索領域に設定
し、設定した配線経路探索領域内で配線パターンの配線
経路を決定することを特徴とする配線経路決定方法を採
用したものである。。

【０００９】第２の方法として、プリント基板上の配線
対象区間を複数の端子で特定し、この配線対象区間を結
ぶ配線パターンの配線経路を迷路法または線分探索法で
決定するに際して、既に配線経路の決定された配線パタ
ーンの配線経路を線路長に応じて複数の部分経路に分割
し、線路の平行条件を満たす部分経路の本数から各部分
経路を複数のグループに分類し、各グループに属する部
分経路の位置情報と線路幅情報を記憶し、その後配線経
路未定の配線対象区間を特定する複数の端子に関する位
置情報を入力し、この入力情報と配線経路の決定された
配線パターンに関する情報を基に配線経路の決定された
端子群の中から配線対象区間近傍の端子群を選択し、選
択した端子間を結ぶ部分経路を選択し、選択した各部分
経路の属するグループを選択し、選択した各グループに
属する部分経路に関する位置情報と線路幅情報を入力
し、入力した位置情報と線路幅情報を基に各部分経路に
対する配線禁止領域をグループ毎に線路の平行条件を満
たす部分経路の本数に応じた大きさに設定し、各配線禁
止領域を外れた領域を配線経路探索領域に設定し、設定
した配線経路探索領域内で配線パターンの配線経路を決
定することを特徴とする配線経路決定方法を採用したも
のである。

【００１０】第１の装置として、配線経路探索領域内を
迷路法または線分探索法に従って探索してプリント基板
上の配線対象区間を結ぶ配線パターンの配線経路を決定
する配線経路決定装置において、既に配線経路の決定さ
れた配線パターンの配線経路を線路長に応じて複数の部
分経路に分割する配線経路分割手段と、配線経路分割手
段の分割による各部分経路を線路間隔と線路の平行条件
から複数のグループに分類する分類手段と、分類手段で
分類されたグループに属する各部分経路の位置情報と線
路幅情報をグループ毎に記憶する記憶手段と、配線経路
未定の配線対象区間を特定する複数の端子に関する位置
情報を入力する端子情報入力手段と、端子情報入力手段
の入力情報と配線経路の決定された配線パターンに関す
る情報を基に配線経路の端子群の中から配線対象区間近
傍で且つ配線対象区間と同一バスに属する端子群を選択
する端子選択手段と、記憶手段に記憶された部分経路に
関する情報を基に端子選択手段の選択による端子間を結
ぶ部分経路を選択する部分経路選択手段と、記憶手段に
記憶されたグループに関する情報を基に部分経路選択手
段の選択による各部分経路の属するグループを選択する
グループ選択手段と、グループ選択手段の選択した各グ
ループに属する部分経路に関する位置情報と線路幅情報
を入力する部分経路情報入力手段と、部分経路情報入力
手段の入力した位置情報と線路幅情報を基に各部分経路
に対する配線禁止領域をグループ毎に設定する配線禁止
領域設定手段と、配線禁止領域設定手段の設定による各
配線禁止領域の周囲に配線対象区間の配線経路として許
容される配線許容領域を設定する配線許容領域設定手段
と、配線許容領域設定手段の設定による各グループの配
線許容領域の集合を配線経路探索領域に設定する配線探
索領域設定手段とを備えていることを特徴とする配線経
路決定装置を構成したものである。

【００１１】第２の装置として、配線経路探索領域内を
迷路法または線分探索法に従って探索してプリント基板
上の配線対象区間を結ぶ配線パターンの配線経路を決定
する配線経路決定装置において、既に配線経路の決定さ
れた配線パターンの配線経路を線路長に応じて複数の部
分経路に分割する配線経路分割手段と、線路の平行条件
を満たす部分経路の本数を基に配線経路分割手段の分割
による各部分経路を複数のグループに分類する分類手段
と、分類手段で分類されたグループに属する各部分経路
の位置情報と線路幅情報をグループ毎に記憶する記憶手
段と、配線経路未定の配線対象区間を特定する複数の端
子に関する位置情報を入力する端子情報入力手段と、端
子情報入力手段の入力情報と配線経路の決定された配線
パターンに関する情報を基に配線経路の決定された端子
群の中から配線対象区間近傍の端子群を選択する端子選
択手段と、記憶手段に記憶された部分経路に関する情報
を基に端子選択手段の選択による端子間を結ぶ部分経路
を選択する部分経路選択手段と、記憶手段に記憶された
グループに関する情報を基に部分経路選択手段の選択に
よる各部分経路の属するグループを選択するグループ選
択手段と、グループ選択手段の選択した各グループに属
する部分経路に関する位置情報と線路幅情報を入力する
部分経路情報入力手段と、部分経路情報入力手段の入力
した位置情報と線路幅情報を基に各部分経路に対する配
線禁止領域をグループ毎に部分経路の本数に応じた大き
さに設定する配線禁止領域設定手段と、配線禁止領域設
定手段の設定による各配線禁止領域を外れた領域を配線
経路探索領域に設定する配線探索領域設定手段とを備え
ていることを特徴とする配線経路決定装置を構成したも
のである。

【００１２】

【作用】前記した手段によれば、バス構造を考慮した配
線経路を迷路法または線分探索法で決定するに先だっ
て、すでに配線経路の決定された配線パターンの配線経
路を線路長に応じて複数の部分経路に分割し、各部分経
路を線路間隔と線路の平行条件から複数のグループに分
類し、各グループに属する部分経路の位置情報と線路幅
情報を記憶する。これらの処理が行なわれたあと、配線
対象区間を特定するために複数の端子に関する位置情報
を入力し、この入力情報と配線経路の決定された配線パ
ターンに関する情報を基に配線経路の決定された端子群
の中から配線対象区間近傍でかつ配線対象区間と同一バ
スに属する端子群を選択する。そして選択した端子間を
結ぶ部分経路を選択し、選択した各部分経路の属するグ
ループを選択し、選択した各グループに属する部分経路
に関する位置情報と線路幅情報を入力する。このあと入
力した位置情報と線路幅情報を基に各部分経路に対する
配線禁止領域をグループ毎に設定し、各配線禁止領域の
周囲に配線対象区間の配線経路として許容される配線許
容領域を設定し、各グループの配線許容領域の集合を配
線経路探索領域に設定する。そして設定した配線経路探
索領域内に迷路法または線分探索法を適用して配線パタ
ーンの配線経路を決定する。これによりバス構造を考慮
した配線経路を決定することができ、プリント基板に対
する高密度配線設計を容易に行なうことができる。

【００１３】またクロストークノイズを考慮した配線経
路を迷路法または線分探索法で決定するに先だって、す
でに配線経路の決定された配線パターンの配線経路を線
路長に応じて複数の部分経路に分割し、線路の平行条件
を満す部分経路の本数から各部分経路を複数のグループ
に分類し、各グループに属する部分経路の位置情報と線
路幅情報を記憶する。このあと配線対象区間を特定する
ために複数の端子に関する位置情報を入力し、この入力
情報と配線経路の決定された配線パターンに関する情報
を基に配線経路の決定された端子群の中から配線対象区
間近傍の端子群を選択し、選択した端子間を結ぶ部分経
路を選択し、選択した各部分経路の属するグループを選
択する。このあと選択した各グループに属する部分経路
に関する位置情報と線路幅情報を入力し、入力した位置
情報と線路幅情報を基に各部分経路に対する配線禁止領
域をグループ毎に線路の平行条件を満す部分経路の本数
に応じた大きさに設定する。すなわち相隣接する部分経
路の本数が多いときには部分経路に対する配線禁止領域
を大きくする。そして各配線禁止領域を外れた領域を配
線経路探索領域に設定し、設定した配線経路探索領域内
に迷路法または線分探索法を適用して配線パターンの配
線経路を決定する。このように、相隣接する配線経路の
本数が大きくなったときには各配線間の間隔を広くする
ようにしたため、クロストークノイズを考慮した配線経
路を決定することができ、高速回路が実装されるプリン
ト基板に対する配線設計を容易に行なうことができる。

【００１４】

【実施例】

（第１実施例）以下、バス構造を考慮した配線経路決定
方法が適用された配線経路自動決定装置の実施例を図面
に基づいて説明する。

【００１５】図１は、本発明に係る配線経路自動決定装
置の構成を示すブロック図である。図１において、配線
経路自動決定装置はコンピュータ１０１、基板情報ファ
イル１０２、ネット情報ファイル１０３、配線パターン
情報ファイル１０４を備えて構成されている。コンピュ
ータ１０１は配線経路決定処理制御部１０５、入力処理
部１０６、配線対象区間抽出処理部１０７、部分経路群
作成更新処理部１０８、特定部分経路群選択処理部１０
９、配線禁止領域作成処理部１１０、配線許容領域作成
処理部１１１、配線経路探索処理部１１２、発生経路編
集処理部１１３、出力処理部１１４、信号情報テーブル
１１５、部分経路情報テーブル１１６、配線対象区間管
理テーブル１１７、配線格子情報テーブル１１８を備え
て構成されている。そして基板情報ファイル１０２に
は、プリント基板の配線層の構成等に関する情報、例え
ば基板の大きさ、配線層の数などに関する情報が格納さ
れている。ネット情報ファイル１０３には、信号に対す
るピン情報及びピン相互間を接続するための配線パター
ンの経路幅、最少導体間隔など配線条件に関する情報が
格納されている。配線パターン情報ファイル１０４に
は、配線パターンに関する情報として、配線経路の位置
情報（座標）や中継穴の位置情報に関する情報が格納さ
れている。各ファイル１０２，１０３，１０４に格納さ
れた各種情報は入力処理部１０６と出力処理部１１４を
介してコンピュータ１０１と情報の授受を行なうように
構成されている。コンピュータ１０１は各ファイルと情
報の授受を行なって配線パターンの配線経路を決定する
処理を行なうように構成されている。そして配線経路決
定処理プログラムに従って配線パターンの配線経路を決
定するコンピュータ１０１の各部は以下のように構成さ
れている。

【００１６】入力処理部１０６は基板情報ファイル１０
２、ネット情報ファイル１０３、配線パターン情報ファ
イル１０４から情報を読み込み、読み込こんだ情報のう
ち信号に関する情報を信号情報テーブル１１５に格納
し、部分経路情報に関する情報を部分経路情報テーブル
１１６に格納するように構成されている。配線対象区間
抽出処理部１０７は、信号情報テーブル１１５内の情報
を参照して所定の情報、例えば配線対象区間の始点、終
点位置情報、経路幅、最少導体間隔などに関する情報を
作成し、作成した情報を配線対象区間管理テーブル１１
７へ格納するようになっている。部分経路群作成更新処
理部１０８は部分経路情報テーブル１１６内の情報、例
えば部分経路群の識別、部分経路情報に関する情報を参
照し、テーブル内の所定の情報を更新処理するようにな
っている。特定部分経路群選択処理部１０９は信号情報
テーブル１１５と部分経路情報テーブル１１６内の情報
を参照して特定部分経路群を選択し、選択した部分経路
群の情報を配線対象区間管理テーブル１１７へ格納する
ようになっている。配線禁止領域作成処理部１１０は部
分経路情報テーブル１１６及び配線対象区間管理テーブ
ル１１７内の所定の情報を参照して配線禁止領域に関す
る情報を作成し、作成した配線禁止領域に関する情報を
配線格子情報テーブル１１８に格納するようになってい
る。配線許容領域作成処理部１１１は、配線禁止領域作
成処理部１１０で作成された配線禁止領域に関する情報
を入力すると共に配線対象区間管理テーブル１１７内の
所定の情報を参照して配線禁止領域の周囲に配線対象区
間の配線経路として許容される配線許容領域に関する情
報を作成し、作成した配線許容領域に関する情報を配線
格子情報テーブル１１８に格納するようになっている。
配線経路探索処理部１１２は配線格子情報テーブル１１
８内の所定の情報を参照すると共に更新し、配線経路探
索領域を設定するための処理を行なうようになってい
る。発生経路編集処理部１１３は、配線格子情報テーブ
ル１１８内の探索来歴情報等を参照して、部分経路情報
テーブル１１６内の所定の情報を更新処理するようにな
っている。出力処理部１１４は部分経路情報テーブル１
１６内の所定の情報を参照し、参照した情報をパターン
情報ファイル１０４へ出力するようになっている。そし
てこれら各部の起動は配線経路決定処理制御部１０５か
らの指令によって行なわれるようになっている。

【００１７】次に、配線経路決定処理部１０５の処理手
順を図２のフローチャートに従って説明する。図２にお
いて、まず入力処理部１０６を起動することにより入力
処理を実行する（ステップ２０１）。このステップで
は、信号情報テーブル１１５内の全情報を作成する処理
を行なうと共に、部分経路情報テーブル１１６内の部分
経路情報を作成する処理を行なう。すなわち、すでに配
線経路の決定された配線パターンの配線経路を線路長に
応じて複数の部分経路に分割し、各部分経路を線路間隔
と線路の平行条件から複数のグループに分類し、分類さ
れたグループに属する各部分経路の位置情報と線路幅情
報をグループ毎に記憶する。次に、配線対象区間抽出処
理部１０７を起動し、作成された信号情報テーブル１１
５内の所定の情報を参照し、配線処理の終了していない
配線区間を１つ取り出し、配線対象区間管理テーブル１
１７内の配線区間に係る始点／終点位置に関する情報を
作成する（ステップ２０２）。すなわち配線経路未定の
配線対象区間を特定する複数の端子（ピン）に関する位
置情報を入力する。更に配線対象区間を結ぶ配線パター
ンの経路幅及び最少導体間隔に関する情報を作成する。
これらの処理が終了したあとはステップ２０３からステ
ップ２１０による配線対象区間の配線処理を実行する。

【００１８】まず、ステップ２０３では、部分経路群作
成更新処理部１０８を起動し、部分経路情報テーブル１
１６内の部分経路情報を参照し、このテーブル内の部分
経路の群識別を作成／更新することにより、部分経路の
うち隣接して互いに平行に配線された部分経路の群を編
集するための処理を行なう。具体的には図３及び図４に
示される処理が行なわれる。

【００１９】まず、配線済みの各ネットの配線経路に対
して隣接して平行に配線された部分経路を再分割する。
すなわち、図３に示されるように、配線済みの各ネット
に対する配線経路を少なくとも中継穴位置乃至は分岐位
置により分割した部分経路ｌｋ（ｋ＝１，２，………）
のうち、互いに隣接して平行に配線された隣接平行条件
を満たしかつ隣接する距離が規定値δ以内であるもの
で、更に相対する部分経路の始点と終点の座標が規定値
θ以上離れるような部分経路に対しては、この座標差が
規定値θ以内となる適当な位置で部分経路を再度分割す
る。

【００２０】次に、作成した部分経路ｌｋ（ｋ＝１，
２，………）に対して、図４に示されるように、「距離
が規定値δ以内であり、かつ相対する部分経路の始点と
終点の座標（端点座標）の差が規定値θ以内（隣接平行
条件）」となる部分経路をグループ毎にまとめて編集す
る。例えば、図４（ａ）に示される部分経路の場合は、
ネット（Ａ１，Ａ２，Ａ３，Ａ４）の配線経路が部分経
路ｌ１，ｌ２，ｌ３，ｌ４，ｌ５に分割され、ネット
（Ｂ１，Ｂ２，Ｂ３）の配線経路が部分経路ｌ６，ｌ
７，ｌ８，ｌ９に分割されている。このような場合、部
分経路ｌ１を第１グループＧ１に、部分経路ｌ２，ｌ６
を第２グループＧ２に、部分経路ｌ３，ｌ７を第３グル
ープＧ３に、部分経路ｌ４，ｌ８を第４グループＧ４
に、部分経路ｌ５，ｌ９を第５グループＧ５に分類す
る。

【００２１】また図４（ｂ）の場合には、部分経路ｌ１
を第１グループＧ１に、部分経路ｌ２，ｌ６を第２グル
ープＧ２に、部分経路ｌ３，ｌ７、ｌ８を第３グループ
Ｇ３に、部分経路ｌ５を第４グループＧ４に、部分経路
ｌ４を第５グループＧ５に、部分経路ｌ９を第６グルー
プＧ６に分類する。このように各部分経路をグループ
（群）に分類すると、各部分経路の群Ｇｉに属する各部
分経路ｇｉｊは必ず距離δ以内で隣接平行条件を満す関
係の情報を作成することができる。また部分経路の群Ｇ
ｉに属する各部分経路ｇｉｊは必ずその平行開始位置と
平行終了位置のずれを規定値θ以内とすることができ
る。

【００２２】次に、ステップ２０４に移り、特定部分経
路群選択処理部１０９を起動し、部分経路情報テーブル
１１６内の所定の情報及び信号情報テーブル１１５内の
信号に対する機能の識別情報を参照しつつ、配線対象区
間管理テーブル１１７内に設けた隣接平行走行させる部
分経路の群情報を作成することより、隣接平行走行させ
るべき特定の部分経路の群を選択するための処理を実行
する。具体的には、図５に示されるような処理が行なわ
れる。すなわち、隣接平行走行する部分経路の群の中か
ら所望の配線区間に対し、隣接平行走行させるべき特定
の部分経路の群を選択する処理を行なう。

【００２３】（１）配線区間（Ｐ，Ｐ′）に対してＰ，
Ｐ′と近傍でかつ同一のバスに属す配線区間（Ｑ，
Ｑ′）を取り出す（但しＱとＱ′は同一ネットであ
る）。

【００２４】（２）上記配線区間（Ｑ，Ｑ′）を接続す
る部分経路ｇｍｓを取り出す。

【００２５】（３）上記部分経路ｇｍｓの属す部分経路
の群Ｇｍ＝（ｇｍｊ）を選択する。

【００２６】例えば、図５（ａ）の場合には、配線経路
の未定の配線区間Ｂ１，Ｂ２に対して、配線区間Ｂ１，
Ｂ２と近傍でかつ同一のバスに属する配線区間として配
線区間Ａ２，Ａ３が取り出される。そして配線区間Ａ
２，Ａ３を結ぶ部分経路として部分経路ｇ２１，ｇ３
１，ｇ４１の属するグループＧ２，Ｇ３，Ｇ４が選択さ
れる。また図５（ｂ）の場合には、配線経路未定の配線
区間Ｃ１，Ｃ２に対し、配線区間Ｃ１，Ｃ２と近傍でか
つ同一のバスに属する配線区間として配線区間Ｂ１，Ｂ
２が取り出される。そしてこの配線区間Ｂ１，Ｂ２を結
ぶ部分経路ｇ２２，ｇ３２，ｇ４２が取り出される。さ
らにこれらの部分経路が属する部分経路のグループＧ
２，Ｇ３，Ｇ４が選択される。また図５（ｃ）の場合に
は、配線経路未定の配線区間ｃ２，Ｃ３に対して配線区
間ｂ２，Ｂ３が取り出される。なお、ｃ２，ｂ２はそれ
ぞれ配線済み経路上の中継穴を示す。そして配線区間ｂ
２，Ｂ３を結ぶ部分経路ｇ５２が取り出されると、部分
経路ｇ５２，ｇ５１が属するグループＧ５が選択され
る。このように、配線対象区間を結ぶ部分経路の属する
グループが選択されることになる。このため、本実施例
では、同一バスに属す配線済みの経路に対し、配線済み
経路に分岐を含む場合においても、隣接平行走行させる
に必要かつ充分な部分経路のみを選択することができ
る。

【００２７】次に、ステップ２０５，２０６に移り、配
線禁止領域作成処理部１１０の起動に続いて配線許容領
域作成処理部１１１を起動し、部分経路情報テーブル１
１６内の所定の情報及び配線対象区間管理テーブル１１
７内の所定の情報を参照しつつ、配線区間の線路探索に
対する配線格子上での配線禁止領域及び配線許容領域を
設定するための処理を実行する。すなわち、図６に示さ
れるように、迷路法または線分探索法による経路探索に
先だって、配線格子上での全ての既配線経路に対する配
線禁止領域の設定処理と同時に、これら既配線経路のう
ち特定の部分経路の群に対しては更に、配線禁止領域の
外側に一定量拡大した配線許容領域を設定する処理を実
行する。

【００２８】具体的には、図６（ａ）に示されるよう
に、例えば、配線経路未定の配線区間Ｃ１，Ｃ２に対し
て隣接平行条件を満す特定の部分経路を含む群として群
Ｇ２，Ｇ３，Ｇ４が選択されたとき、特定の部分経路ｇ
２１，ｇ２２，ｇ３１，ｇ３２，ｇ４１，ｇ４２を含む
群Ｇ２，Ｇ３，Ｇ４に対し隣接平行走行させるべき領域
として配線許容領域Ｒ２，Ｒ３，Ｒ４を設定する。この
場合、例えば、群Ｇ３に対する配線許容領域Ｒ３の設定
に関しては、群Ｇ３に属する２つの部分経路ｇ３１，ｇ
３２に対し隣接平行させるべき領域としての配線許容領
域ｒ３１，ｒ３２を求め、これらの領域の和を配線許容
領域Ｒ３として設定する。ここで、部分経路ｇ３１に対
して配線許容領域ｒ３１は部分経路ｇ３１の中心線から
の距離α（Ｂ）＋δ（Ｂ，Ｃ）＋α（Ｃ）＋ｄ以内の領
域として求める。すなわち、α（Ｂ）＋δ（Ｂ，Ｃ）＋
α（Ｃ）で表わされる配線禁止領域を一定幅ｄで拡大し
た領域として求める。ただし、α（Ｂ）：ネット（Ｂ
１，Ｂ２，Ｂ３）に係る経路幅（半幅）、α（Ｃ）：ネ
ット（Ｃ１，Ｃ２）に係る経路幅（半幅）、δ（Ｂ，
Ｃ）：ネット（Ｂ１，Ｂ２，Ｂ３）とネット（Ｃ１，Ｃ
２）に係る最少導体間隔である。

【００２９】配線許容領域が設定されたあとは、ステッ
プ２０７の処理に移り配線対象区間のセットアップを行
なう。すなわち配線対象区間の始点／終点位置を配線格
子情報テーブル１１８に格納する。このあと配線経路探
索処理部１１２を起動して配線経路探索を行なう。経路
探索は迷路法または線分探索法によって行ない、この経
路探索は配線許容領域Ｒｉからの探索が優先的に行なわ
れるように制御する（ステップ２０８）。更に配線禁止
領域を回避しつつ実行し、隣接平行させ得る経路の中で
迷路法のときには最短経路が探索され、線分探索法の場
合には折れ曲がり数最少経路（中継穴数最少経路）を得
ることができる。そして経路探索の結果配線対象区間の
終点に到達した場合（ステップ２０９）、上記始点から
終点に至る経路は配線格子情報テーブル１１８内の探索
来歴情報に格納され、この情報を基に発生経路編集処理
部１１３が起動される。そしてステップ２１０において
は、始点から終点に至る配線経路の情報が編集され、こ
の編集によって得られた配線経路により部分経路情報テ
ーブル１１６内の部分経路情報が更新される。

【００３０】このような処理を全ての配線対象区間に対
する処理が完了するまで繰り返して行う。そしてステッ
プ２１１による判定で、全ての配線対象区間に対する処
理が完了した場合には出力処理部１１４を起動し、得ら
れた全ての配線経路を配線パターン情報ファイル１１４
に格納し、全ての処理を終了する（ステップ２１２）。

【００３１】このように、本実施例によれば、配線対象
区間を指定したときに、この配線対象区間と隣接平行条
件を満す部分経路群を作成し、作成した部分経路群の中
から特定の部分経路群を選択し、選択した部分経路の群
について配線禁止領域を作成すると共に配線許容領域を
作成し、配線許容領域内で配線経路の探索を行なうよう
にしたため、レイアウトモデルが配置領域と配線領域に
分離不可能であっても、バス構造を考慮した配線経路を
自動的に決定することができ、配線経路によって無駄な
面積が生じるのを防止することができる。

【００３２】（第２実施例）以下、本発明の第２実施例
として、クロストークを考慮した配線方法が適用された
配線経路自動決定装置の構成を図７に従って説明する。

【００３３】図７において、配線経路自動決定装置はコ
ンピュータ３０１，基板情報ファイル３０２、ネット情
報ファイル３０３、配線パターン情報ファイル３０４を
備えて構成されている。コンピュータ３０１は配線経路
決定処理制御部３０５、入力処理部３０６、配線対象区
間抽出処理部３０７、部分経路群作成更新処理部３０
８、部分経路群グループ化処理部３０９、配線禁止領域
作成処理部３１０、配線経路探索処理部３１２、発生経
路編集処理部３１３、出力処理部３１４、信号情報テー
ブル３１５、部分経路情報テーブル３１６、配線対象区
間管理テーブル３１７、配線格子情報テーブル３１８を
備えて構成されている。基板情報ファイル３０２にはプ
リント基板の配線層の構成等に関する情報、例えば基板
の大きさ、配線層の数に関する情報が格納されている。
ネット情報ファイル３０３には信号に対するピン情報及
びピン相互間を接続するための経路幅、最少導体間隔な
ど配線条件に関する情報が格納されている。また配線パ
ターン情報ファイル３０４には配線経路の位置情報（座
標）、中継穴の位置情報など配線パターンに関する情報
が格納されている。そしてコンピュータ３０１は各情報
ファイルと情報の授受を行なってクロストークノイズを
考慮した配線経路を決定するように構成されている。

【００３４】入力処理部３０６は基板情報ファイル３０
２、ネット情報ファイル３０３、配線パターン情報ファ
イル３０４から各種の情報を読み込み、所定の情報、例
えば信号に対する最少導体間隔に関する情報を信号情報
テーブル３１５に格納し、部分経路情報に関する情報を
部分経路情報テーブル３１６に格納するようになってい
る。配線対象区間抽出処理部３０７は信号情報テーブル
３１５内の所定の情報例えば信号に対するピン情報を参
照し、配線対象区間管理テーブル３１７内に配線対象区
間に関する情報として始点／終点位置に関する情報など
を格納するようになっている。部分経路群作成更新処理
部３０８は部分経路情報テーブル３１６内の所定の情報
を参照し、このテーブル内の所定の情報を更新処理する
ようになっている。部分経路群グループ化処理部３０９
は部分経路情報テーブル３１６内の所定の情報を参照
し、平行走行配線本数に応じた部分経路を複数のグルー
プに分け分類した部分経路群に関する情報を部分経路情
報テーブル３１６に格納するようになっている。配線禁
止領域作成処理部３１０は部分経路情報テーブル３１６
と配線対象区間管理テーブル３１７内の所定の情報を参
照し、平行配線本数に応じた部分経路の群毎の配線禁止
領域を作成し、作成した配線禁止領域に関する情報を配
線格子情報テーブル３１８の所定の記憶エリアに格納す
るようになっている。配線経路探索処理部３１２は配線
格子情報テーブル３１８内の所定の情報を参照すると共
に更新しつつ配線経路の探索を行なうようになってい
る。発生経路編集処理部３１３は配線格子情報テーブル
３１８内の所定の情報を参照し、部分経路情報テーブル
３１６内の所定の情報を更新するようになっている。出
力処理部３１４は部分経路情報テーブル３１６内の所定
の情報を参照し、パターン情報ファイル３０４に配線パ
ターン関する情報を格納するようになっている。そして
これら各処理部は配線経路決定処理制御部３０５からの
指令に従って起動するようになっている。

【００３５】次に、配線経路決定処理制御部３０５の処
理手順を図８のフローチャートに従って説明する。

【００３６】まず、入力処理部３０６を起動することに
よって入力処理を行なう（ステップ４０１）。すなわち
信号情報テーブル３１５内の全情報を作成する処理を行
なうと共に部分経路情報テーブル３１６内の部分経路情
報を作成するための処理を行なう。すなわちすでに配線
経路の決定された配線パターンの配線経路を線路長に応
じて複数の部分経路に分割し、線路間隔と線路の平行条
件から各部分経路を複数のグループに分類し、各グルー
プに属する部分経路の位置情報と線路幅情報をグループ
毎に記憶する。次に配線対象区間抽出処理部３０７を起
動し、作成された信号情報テーブル３１５内の所定の情
報を参照し、配線処理の終了していない配線区間を１つ
取り出し、配線対象区間管理テーブル３１７内の配線区
間に係る始点／終点位置に関する情報を作成する。すな
わち配線経路未定の配線対象区間を特定するために複数
の端子に（ピン）に関する位置情報を入力する。更に配
線区間を結ぶ配線経路に関する経路幅及び平行配線本数
に応じた最少導体間隔に関する情報を作成する（ステッ
プ４０２）。そしてこれらの処理が終了したあとは、ス
テップ４０３から４１０による配線対象区間の配線処理
を実行する。

【００３７】まず、ステップ４０３では、部分経路群作
成更新処理部３０８を起動し、部分経路情報テーブル３
１６内の部分経路情報を参照し、テーブル３１６内の部
分経路の群識別を作成／更新することにより、隣接平行
走行する部分経路の群を編集する。すなわち、前記実施
例のステップ２０３と同様の処理により、図３に示され
るような部分経路の再分割を行なうと共に図４に示され
るように、部分経路の編集処理を実行する。

【００３８】次にステップ４０４では、部分経路群グル
ープ化処理部３０９を起動し、部分経路情報テーブル３
１６内の所定の情報を参照しつつ、このテーブル３１６
内に設けた部分経路の群のグループ化情報を作成するこ
とにより、隣接平行走行する配線本数に応じた部分経路
の群の分類を行なう。具体的には、図９に示されるよう
に、配線済みネットに対する部分経路を隣接平行走行条
件を満すグループに分類した場合、グループＧ１には部
分経路ｇ１１が属し、グループＧ２には部分経路ｇ２
１，ｇ２２，ｇ２３が属し、グループＧ３には部分経路
ｇ３１，ｇ３２，ｇ３３が属し、グループＧ４には部分
経路ｇ４１，ｇ４２、グループＧ５には部分経路ｇ５
１，ｇ５２，ｇ５３，ｇ５４が属し、グループＧ６には
部分経路ｇ６１が属する。このような場合、各グループ
に属する部分経路の本数はそれぞれ１，３，３，２，
４，１である。そこで、本実施例では、これら部分経路
の群を以下の方法によって分類する。

【００３９】（１）隣接平行走行する配線本数の等しい
群毎に分類する。

【００４０】（２）規定本数Ｎを超え、隣接平行走行す
る配線本数がＮ以下の群とＮより大きい群に分類する。

【００４１】例えば、図９（ａ）に示される部分経路の
群に対して、上記分類方法（１）に従った場合、部分経
路の群Ｇｉは、（Ｇ１，Ｇ６）、（Ｇ４）、（Ｇ２，Ｇ
３）、（Ｇ５）の４グループに分類することができる。
また上記分類方法（２）により、規定本数を２とした場
合、部分経路の群は、（Ｇ１，Ｇ４，Ｇ６）、（Ｇ２，
Ｇ３，Ｇ５）の２つのグループに分類することができ
る。

【００４２】このように、上記いずれかの方法によって
部分経路群をグループ化すれば、所望の配線対象区間に
対する配線経路決定において、既配線経路との最少導体
間隔を一意に与えるのでなく、既配線経路と隣接平行走
行する本数に応じて可変に与えることができる。すなわ
ち配線経路の本数に応じて最少導体間隔の間隔を広くす
ることができ、クロストークノイズの低減を図ることが
できる。

【００４３】次に、ステップ４０５に移り配線禁止領域
作成処理部３１０を起動し、部分経路情報テーブル３１
６内の所定の情報及び配線対象区間管理テーブル３１７
内の所定の情報を参照しつつ、配線区間の経路探索に対
する配線格子上での配線禁止領域を、隣接平行走行する
配線本数に応じた最少導体間隔に基づいて求め、配線禁
止領域に関する情報を配線格子情報テーブル３１８内の
所定の記憶エリアに格納する。すなわち、ステップ４０
４の処理で複数のグループに分割された部分経路に対
し、配線対象区間の配線経路が保持すべき最少導体間隔
を個別に制御しつつ配線経路を決定する処理を行なう。

【００４４】具体的には、図１０に示されるように、分
類方法（２）により、隣接平行配線本数が１以下の群
（Ｇ１）と隣接平行配線本数が２以上の群（Ｇ２，Ｇ
３，Ｇ４，Ｇ５）に分類された場合、隣接平行配線本数
が一本以下の群（Ｇ１）に対しては、最少導体間隔をδ
１と設定し、また隣接平行配線本数が２本以上の群（Ｇ
２，Ｇ３，Ｇ４，Ｇ５）対しては、最少導体間隔をδ２
と設定する。これら最少導体間隔δ１，δ２は、配線対
象区間のもつネット属性及び既配線経路のもつネット属
性に依存し、更に個別に設定することができる。例え
ば、図１０の場合には、配線対象区間（Ｄ１，Ｄ２）の
もつネット属性及び既配線区間（Ａ１，Ａ４）の有する
ネット属性に対し、最少導体間隔をδ１（Ｄ，Ａ）、δ
２（Ｄ，Ａ）のように設定することができる。

【００４５】そして、本実施例では、迷路法または線分
探索法による経路探索に先だって、全ての既配線経路に
対する配線禁止領域の設定処理において、分類された群
毎に定義された最少導体間隔に従って配線禁止領域を設
定することとしている。例えば、隣接平行配線本数が一
本以下の群Ｇ１に対しては、最少導体間隔δ１に従った
配線禁止領域Ｋ１を設定し、隣接平行配線本数が２以上
の群Ｇ２，Ｇ３，Ｇ４，Ｇ５に対しては、最小導体間隔
δ２に従った配線禁止領域Ｋ２，Ｋ３，Ｋ４，Ｋ５を設
定する。ここで、各禁止領域Ｋｉは、各群Ｇｉに属する
部分経路ｇｉｊに対する配線禁止領域ｋｉｊの和であ
る。更に、部分経路ｇｉｊに対する禁止領域ｋｉｊの設
定については、例えば、部分経路ｇ１１に対する配線禁
止領域ｋ１１は、部分経路の中心線からの距離α（Ａ）
＋δ１（Ａ，Ｄ）＋α（Ｄ）以内の領域として求めるこ
とができる。ただし、α（Ａ）：ネット（Ａ１，Ａ２，
Ａ３，Ａ４）に係る経路幅（半幅）、α（Ｄ）：ネット
（Ｄ１，Ｄ２）に係る経路幅（半幅）、δ１（Ａ，
Ｄ）：ネット（Ａ１，Ａ２，Ａ３，Ａ４）とネット（Ｄ
１，Ｄ２）に係る平行配線本数が１本以下の場合の最少
導体間隔である。

【００４６】また部分経路ｇ３２に対する配線禁止領域
ｋ３２は、部分経路の中心線からの距離α（Ｂ）＋δ２
（Ｂ，Ｄ）＋α（Ｄ）以内の領域として求めることがで
きる。ただし、α（Ｂ）：ネット（Ｂ１，Ｂ２，Ｂ３）
に係る経路幅（半幅）、α（Ｄ）：ネット（Ｄ１，Ｄ
２）に係る経路幅（半幅）、δ２（Ｂ，Ｄ）：ネット
（Ｂ１，Ｂ２，Ｂ３）とネット（Ｄ１，Ｄ２）に係る平
行配線本数が２本以上の場合の最少導体間隔である。

【００４７】次に、ステップ４０７に移り、配線対象区
間のセットアップを行なう。すなわち配線対象区間の始
点／終点位置の位置情報を入力し、この位置情報を配線
格子情報テーブル３１８に格納する。このあと配線経路
探索処理部３０２を起動し配線経路探索を実行する（ス
テップ４０８）。この場合迷路法または線分探索法によ
る線路探索を行ない、配線禁止領域を回避しつつ配線経
路の探索を行なう。すなわち配線禁止領域を除いた領域
内で配線経路の探索を行なう。この配線経路の探索の結
果、配線対象区間の終点に到達した場合（ステップ４０
９）、配線対象区間の始点から終点に至る経路に関する
来歴情報が配線格子情報テーブル３１８内に格納され
る。そしてこの情報を基に、ステップ４１０において、
始点から終点に至る配線経路の編集処理が行なわれる。
この編集処理が行なわれると発生経路編集処理部３１３
が起動され、編集処理により得られた配線経路により部
分経路情報テーブル３１６内の部分経路情報が更新され
る。

【００４８】このような処理は、全ての配線対象区間に
対する処理が完了するまで繰り返して行なわれる。そし
てステップ４１１において全ての処理が終了したと判定
されたときには出力処理部３１４が起動され、以上の処
理で得られた配線経路に関する配線パターン情報が配線
パターン情報ファイル３０４に格納され、全ての処理が
終了する（ステップ４１２）。

【００４９】このように、本実施例によれば、平行配線
本数に応じて配線禁止領域の大きさを大きくするように
したため、信号線が３本以上並行して走行するレイアウ
トモデルにおいてもクロストークノイズを考慮した配線
経路を自動的に決定することができ、高速回路の実装さ
れるプリント基板の配線設計を容易に行なうことができ
る。

【００５０】

【発明の効果】以上説明したように、本発明によれば、
隣接平行走行条件を満す部分経路を複数のグループに分
け、配線対象区間に対して部分経路の群から隣接平行走
行条件を満す特定の部分経路の群を選択し、選択した特
定の部分経路の群に対して配線禁止領域を設定し、この
配線禁止領域の周囲に配線許容領域を設定し、この配線
許容領域内で配線経路を探索するようにしたため、配置
領域と配線領域の分離が困難なレイアウトモデルにおい
ても、バス構造を考慮した配線経路を自動的に決定する
ことができ、配線経路によって無駄な面積が生じるのを
防止することができる。

【００５１】また更に、隣接平行配線本数に応じて配線
禁止領域の大きさを設定するようにしたため、信号線が
３本以上平行に走行するレイアウトモデルにおいても、
クロストークノイズを考慮して配線経路を自動的に決定
することができ、配線収容性を劣化させることなく、ク
ロストークノイズを低減した配線経路を決定することが
できる。

【図面の簡単な説明】

【図１】本発明の第１実施例を示す配線経路自動決定装
置のブロック図である。

【図２】図１に示す装置の作用を説明するためのフロー
チャートである。

【図３】部分経路の再分割方法を説明するための図であ
る。

【図４】部分経路の編集方法を説明するための図であ
る。

【図５】部分経路の群の選択方法を説明するための図で
ある。

【図６】配線禁止領域と配線許容領域の設定方法を説明
するための図である。

【図７】本発明の第２実施例を示す配線経路自動決定装
置のブロック図である。

【図８】図７に示す装置の作用を説明するためのフロー
チャートである。

【図９】配線本数に応じた部分経路群の分類方法を説明
するための図である。

【図１０】配線本数に応じた最少導体間隔の制御方法を
説明するための図である。

【符号の説明】

１０１，３０１ コンピュータ １０２，３０２ 基板情報ファイル １０３，３０３ ネット情報ファイル １０４，３０４ 配線パターン情報ファイル １０５，３０５ 配線経路決定処理制御部 １０６，３０６ 入力処理部 １０７，３０７ 配線対象区間抽出処理部 １０８，３０８ 部分経路群作成更新処理部 １０９ 特定部分経路群選択処理部 ３０９ 部分経路群グループ化処理部 １１０，３１０ 配線禁止領域作成処理部 １１１ 配線許容領域作成処理部 １１２，３１２ 配線経路探索処理部 １１３，３１３ 発生経路編集処理部 １１４，３１４ 出力処理部

───────────────────────────────────────────────────── フロントページの続き (72)発明者 望月 寛 神奈川県秦野市堀山下１番地 株式会社日 立製作所神奈川工場内 (72)発明者 楠原 治郎 神奈川県秦野市堀山下１番地 株式会社日 立製作所神奈川工場内

Claims (4)

【特許請求の範囲】
1. 【請求項１】 プリント基板上の配線対象区間を複数の
   端子で特定し、この配線対象区間を結ぶ配線パターンの
   配線経路を迷路法または線分探索法で決定するに際し
   て、 既に配線経路の決定された配線パターンの配線経路を線
   路長に応じて複数の部分経路に分割し、各部分経路を線
   路間隔と線路の平行条件から複数のグループに分類し、
   各グループに属する部分経路の位置情報と線路幅情報を
   記憶し、その後配線経路未定の配線対象区間を特定する
   複数の端子に関する位置情報を入力し、この入力情報と
   配線経路の決定された配線パターンに関する情報を基に
   配線経路の決定された端子群の中から配線対象区間近傍
   で且つ配線対象区間と同一バスに属する端子群を選択
   し、選択した端子間を結ぶ部分経路を選択し、選択した
   各部分経路の属するグループを選択し、選択した各グル
   ープに属する部分経路に関する位置情報と線路幅情報を
   入力し、入力した位置情報と線路幅情報を基に各部分経
   路に対する配線禁止領域をグループ毎に設定し、各配線
   禁止領域の周囲に配線対象区間の配線経路として許容さ
   れる配線許容領域を設定し、各グループの配線許容領域
   の集合を配線経路探索領域に設定し、設定した配線経路
   探索領域内で配線パターンの配線経路を決定することを
   特徴とする配線経路決定方法。
2. 【請求項２】 プリント基板上の配線対象区間を複数の
   端子で特定し、この配線対象区間を結ぶ配線パターンの
   配線経路を迷路法または線分探索法で決定するに際し
   て、 既に配線経路の決定された配線パターンの配線経路を線
   路長に応じて複数の部分経路に分割し、線路の平行条件
   を満たす部分経路の本数から各部分経路を複数のグルー
   プに分類し、各グループに属する部分経路の位置情報と
   線路幅情報を記憶し、その後配線経路未定の配線対象区
   間を特定する複数の端子に関する位置情報を入力し、こ
   の入力情報と配線経路の決定された配線パターンに関す
   る情報を基に配線経路の決定された端子群の中から配線
   対象区間近傍の端子群を選択し、選択した端子間を結ぶ
   部分経路を選択し、選択した各部分経路の属するグルー
   プを選択し、選択した各グループに属する部分経路に関
   する位置情報と線路幅情報を入力し、入力した位置情報
   と線路幅情報を基に各部分経路に対する配線禁止領域を
   グループ毎に線路の平行条件を満たす部分経路の本数に
   応じた大きさに設定し、各配線禁止領域を外れた領域を
   配線経路探索領域に設定し、設定した配線経路探索領域
   内で配線パターンの配線経路を決定することを特徴とす
   る配線経路決定方法。
3. 【請求項３】 配線経路探索領域内を迷路法または線分
   探索法に従って探索してプリント基板上の配線対象区間
   を結ぶ配線パターンの配線経路を決定する配線経路決定
   装置において、 既に配線経路の決定された配線パターンの配線経路を線
   路長に応じて複数の部分経路に分割する配線経路分割手
   段と、配線経路分割手段の分割による各部分経路を線路
   間隔と線路の平行条件から複数のグループに分類する分
   類手段と、分類手段で分類されたグループに属する各部
   分経路の位置情報と線路幅情報をグループ毎に記憶する
   記憶手段と、配線経路未定の配線対象区間を特定する複
   数の端子に関する位置情報を入力する端子情報入力手段
   と、端子情報入力手段の入力情報と配線経路の決定され
   た配線パターンに関する情報を基に配線経路の決定され
   た端子群の中から配線対象区間近傍で且つ配線対象区間
   と同一バスに属する端子群を選択する端子選択手段と、
   記憶手段に記憶された部分経路に関する情報を基に端子
   選択手段の選択による端子間を結ぶ部分経路を選択する
   部分経路選択手段と、記憶手段に記憶されたグループに
   関する情報を基に部分経路選択手段の選択による各部分
   経路の属するグループを選択するグループ選択手段と、
   グループ選択手段の選択した各グループに属する部分経
   路に関する位置情報と線路幅情報を入力する部分経路情
   報入力手段と、部分経路情報入力手段の入力した位置情
   報と線路幅情報を基に各部分経路に対する配線禁止領域
   をグループ毎に設定する配線禁止領域設定手段と、配線
   禁止領域設定手段の設定による各配線禁止領域の周囲に
   配線対象区間の配線経路として許容される配線許容領域
   を設定する配線許容領域設定手段と、配線許容領域設定
   手段の設定による各グループの配線許容領域の集合を配
   線経路探索領域に設定する配線探索領域設定手段とを備
   えていることを特徴とする配線経路決定装置。
4. 【請求項４】 配線経路探索領域内を迷路法または線分
   探索法に従って探索してプリント基板上の配線対象区間
   を結ぶ配線パターンの配線経路を決定する配線経路決定
   装置において、 既に配線経路の決定された配線パターンの配線経路を線
   路長に応じて複数の部分経路に分割する配線経路分割手
   段と、線路の平行条件を満たす部分経路の本数を基に配
   線経路分割手段の分割による各部分経路を複数のグルー
   プに分類する分類手段と、分類手段で分類されたグルー
   プに属する各部分経路の位置情報と線路幅情報をグルー
   プ毎に記憶する記憶手段と、配線経路未定の配線対象区
   間を特定する複数の端子に関する位置情報を入力する端
   子情報入力手段と、端子情報入力手段の入力情報と配線
   経路の決定された配線パターンに関する情報を基に配線
   経路の決定された端子群の中から配線対象区間近傍の端
   子群を選択する端子選択手段と、記憶手段に記憶された
   部分経路に関する情報を基に端子選択手段の選択による
   端子間を結ぶ部分経路を選択する部分経路選択手段と、
   記憶手段に記憶されたグループに関する情報を基に部分
   経路選択手段の選択による各部分経路の属するグループ
   を選択するグループ選択手段と、グループ選択手段の選
   択した各グループに属する部分経路に関する位置情報と
   線路幅情報を入力する部分経路情報入力手段と、部分経
   路情報入力手段の入力した位置情報と線路幅情報を基に
   各部分経路に対する配線禁止領域をグループ毎に部分経
   路の本数に応じた大きさに設定する配線禁止領域設定手
   段と、配線禁止領域設定手段の設定による各配線禁止領
   域を外れた領域を配線経路探索領域に設定する配線探索
   領域設定手段とを備えていることを特徴とする配線経路
   決定装置。