JPH0426147B2 - - Google Patents

Description

【発明の詳細な説明】 (A) 発明の技術分野 本発明は、配線ルート自動決定処理方法、特
に、プリント板上の両面に形成される配線格子に
沿つて配線ルートを決定する処理に当たつて、複
数の配線格子をひとつのユニツトとした配線格子
領域を設定する情報を与え、個々の配線格子領域
内での配線ルート決定に当たつてはプリント板の
１つの面上で二次元方向に延長するルートを許す
ようにする処理を簡単に行うようにした配線ルー
ト自動決定処理方法に関するものである。

(B) 技術の背景と問題点 従来からプリント板上にもうける配線ルートを
決定するに当たつて、第７図図示の如き形で、配
線ルート探索処理部を利用し、配線ルートを決定
することが行われている。なお第７図において、
１は配線ルート探索処理部、２は配線結果格納メ
モリ、３は配線処理情報入力部を表している。即
ち、配線処理情報入力部３から所望の情報を入力
し、配線ルート探索処理部１によつて配線ルート
を決定してゆき、得られた配線ルートは配線結果
格納メモリ２に格納される。

この状況について、第５図を参照しつつ説明す
る。図において、４はプリント板、５はプリント
板４の表裏両面に形成される配線格子であつて決
定されるべき配線ルートが当該配線格子に沿うよ
うにして決定されるもの、５−１は格子点、６は
ICピン、７はプリント板上に形成されるビア、
８はプリント板の例えば表面側に形成された配線
ルート、９はプリント板の裏面側に形成された配
線ルートを表している。

第７図図示の配線ルート探索処理部１における
処理については第２図を参照しつつ後述される
が、例えば第５図図示のICピン６ＡからICピン
６Ｂに至る配線ルートを決定するに当たつて、例
えばプリント板の表面側においては図示Ｘ軸方向
にのみ（１格子分のＹ軸方向の延びについては許
容している）延びる配線ルート８を与え、プリン
ト板の裏面側においては図示Ｙ軸方向にのみ（１
格子分のＸ軸方向の延びについては許容してい
る）延びる配線ルート９を与えるようにし、両者
配線ルート８と９との結合に当たつてはプリント
板４上にビア７をもうけて結合するようにしてい
る。勿論、上記ICピン６Ａと６Ｂとの間の配線
ルートの決定に当たつてはプリント板４の例えば
表面のみを利用してＸ軸方向とＹ軸方向との両方
に延びるルートにて決定してもよいが、この決定
を許すと、第５図図示ICピン６Ｃと６Ｄとの間
の配線ルート８と非所望に交差してしまうことが
ある。このために、Ｘ軸方向に延びる配線ルート
８とＹ軸方向に延びる配線ルート９とをビア７に
よつて結合するようにし、上記交差をさけるよう
にしている。

第７図図示の配線ルート探索処理部１は第５図
を参照して説明した如く配線ルートを決定してゆ
くが、第５図図示のICピン６Ｅと６Ｃとの間を
結ぶ配線ルート８と９との場合のように、他のＸ
軸方向に延びる配線ルートによつて交差されるこ
とがないような場合には、わざわざビア７をもう
けてプリント板の表・裏両面を利用しなければな
らない理由がない。また、第６図図示配線ルート
８−１や８−２や８−４の如く極く僅かにＹ軸方
向にづらせて配線する必要がある場合において、
当該Ｙ軸方向に向かうルートを与える毎に第５図
を参照して述べた如くビア７をもうけることは好
ましくない。

上述した如く、同一面上でＸ軸方向とＹ軸方向
との両方に延びるルートを許すようにすると、上
述の交差をさける処理が必要となる。そして、第
６図に関連して説明した如く、非所望に多くのビ
ア７をもうけることも好ましくない。このような
相反する問題を解決するに当つては、基本方針と
してＸ軸・Ｙ軸両方の延長を禁止しておき、第６
図に関連して説明した如き問題が生じる個所につ
いて特別の配慮を加えることが望まれる。そし
て、当該特別の配慮を加えるに当つては、配線ル
ート自動決定処理を行う処理システムが正しく理
解でき、かつ人為的な面での煩雑さがないことが
望まれる。

(C) 発明の目的と構成 本発明は、上記の点特に第６図に関連して述べ
た点を解決することを目的としており、第６図図
示の記号UNiT＃１やUNiT＃２の如く、複数本
の配線格子５例えば５本の配線格子を１つのユニ
ツトとした配線格子領域UNiTを設定し、当該１
つのUNiT内での配線ルートの決定に当たつては
可能な限りビア７の存在をなくするようにするこ
とを目的としている。そしてそのため本発明の配
線ルート自動決定処理方法は、プリント板の一方
の面に形成される配線格子における格子点に対応
して当該格子点に関連する配線パターン情報をも
つと共に上記プリント板の他方の面に形成される
配線格子における格子点に対応して当該格子点に
関連する配線パターン情報をもつ記憶装置をそな
え、上記格子点の少なくとも１つをスタート点と
しかつ上記格子点の少なくとも他の１つをエンド
点とする配線ルートを決定する配線ルート探索処
理部を用いて上記配線格子を通る配線ルートを決
定してゆく配線ルート処理システムにおいて、 上記配線ルート探索処理部が上記プリント板上
の１つの面に関して実質上一次元探索を行う一次
元探索条件状態モードと上記プリント板上の１つ
の面に関して二次元探索を行う二次元探索条件状
態モードとを選択するよう構成されると共に、 配線格子領域設定部をもうけて当該配線格子領
域設定部が複数個分の上記配線格子をひとつのユ
ニツトとした配線格子領域を設定せしめた上で、
同一配線格子領域内の各配線格子に対応して他配
線格子領域内の配線格子と区別し得る識別情報を
付与するよう構成されてなり、 上記配線ルート探索処理部が、配線格子に付与
されている上記識別情報を参照し、各個々の配線
格子領域内における配線ルート決定に当たつては
上記配線ルート探索処理部を二次元探索条件状態
モードにて処理し、 かつ上記１つの配線格子領域から他の配線格子
領域に移行する配線ルート決定に当たつては上記
配線ルート探索処理部を一次元探索条件状態モー
ドにて処理するようにして 当該配線結果を上記記憶装置上に格納するよう
にした ことを特徴としている。以下図面を参照しつつ説
明する。

(D) 発明の実施例 第１図は本発明の方法を実行する一実施例構
成、第２図は第１図に示す配線ルート探索処理部
における処理を説明する説明図、第３図および第
４図は同じく配線ルート探索処理部における処理
を具体的に表すフローチヤートを示している。ま
た第５図は本発明の前提問題を説明する説明図、
第６図は本発明にいう配線格子領域を説明する説
明図、第７は従来の方法を説明する説明図を示し
ている。

第１図において、図中の符号１，２，３は第７
図に対応し、１１は配線格子領域設定部を表して
いる。なお図示の配線ルート探索処理部１は、第
５図および第７図を参照して説明した如く、プリ
ント板の例えば表面でＸ軸方向に延びる配線ルー
トを、また裏面でＹ軸方向に延びる配線ルートを
決定する所の一次元探索条件状態での探索機能を
もつと共に、プリント板の表面のみあるいは裏面
のみでＸ軸方向とＹ軸方向とのいずれの方向にも
延びることのできる二次元探索条件状態での探索
機能をもつている。そしてモード切り替えによつ
て切り替え得るようになつていると考えてよい。

以下本発明を説明するに先立つて、図示配線ル
ート探索処理部１における処理について説明して
おく。

第５図図示の格子点５−１，５−１…に対応し
て第２図Ａ図示の如く「格子点情報」がメモリ上
に格納されている。なお第２図Ａ図示のメモリは
第１図図示の配線処理情報入力部３に記憶されて
入力されるものと考えてよい。一般に座標（xi、
yi）をもつ格子点に対応する格子点情報としては
次のようなものが記述されていると考えてよい。

即ち、情報の種類として、 (a) 後述する如く配線ルート探索のために番号付
けを波及せしめてゆくことが許されるか否かを
指示する「番号付可能格子」情報、 (b) 配線ルート探索のためのスタート点あるいは
エンド点（ICピンの位置など）であることを
指示する「ルート探索スタート又はエンド格子
点」情報、 (c) 配線ルートを通すことが禁止されることを指
示する「障害物格子点」情報 が用意され、夫々の情報のデータとして、 (d) 上記(a)の情報に対応して、空き状態にあるこ
とを示すデータか又は波及されてきた番号が記
述され、 (e) 上記(b)の情報に対応して、スタート点Ｓであ
るか、スタート点の隣点SNであるか、エンド
点Ｅであるか、エンド点の隣点ENであるかが
記述され、 (f) 上記(c)の情報に対応して、障害物の多重度が
記述され、 ている。更に当該格子点がビアを形成することに
ついて禁止されているか否かそして禁止されてい
ればその多重度が与えられている。

今第１図図示の配線ルート探索処理部１が上述
の二次元探索を許しているモードにあるものとす
ると、配線ルートの探索は第２図Ｂおよび第２図
Ｃに示す如く行われる。

最初に第２図Ｂが図示の如く、配線ルートのス
タート点Ｓが図示の如く座標（０、０）であり、
エンド点Ｅが座標（７、０）であり、障害物格子
点が座標（４、０）にあるなどの情報が、第２図
Ａ図示のメモリ１０上に格納される（又は格納さ
れている）。あわせて、座標（１、０）、（０、
１）、（−１、０）、（０−１）がスタート点の隣点
SNであることや、座標（８、０）、（７、１）、
（６、０）、（７、−１）がエンド点の隣点ENであ
ることが格納される。

この状態の下で、メモリａ１２上に上記格子点
SNに関する格子点情報を集める。そして、１つ
の格子点SN（例えば座標（１、０））に着目し、
当該格子点に隣接する二次元方向（但し１つの方
向は波及源方向であるので省略）について座標
（２、０）、（１、１）、（１、−１）に該当する格子
点の格子点情報をメモリｂ１３上に集めると共に
当該格子点の「番号付可能格子」情報に対して番
号「１」を与える。また同様に格子点SN（座標
（０、１））に着目し、座標（１、１）、（０、２）、
（−１、１）に該当する格子点についての格子点
情報をメモリｂ１３上に集めると共に番号「１」
を与える。以下同様にして、格子点SNの隣に番
号「１」が波及し終わつたら、次にメモリｂ１３
の内容をメモリａ１２に転送し、番号「１」が波
及している格子点の隣をメモリｂ１３上に集める
ことによつて番号「２」を与えるようにする。即
ち、第２図Ｂ図示の如く、番号「１」、「２」、
「３」…を順次波及せしめてゆく。このとき、座
標（４、０）の場合のように障害物格子点が存在
すると、それをさけるようにして波及を行つてゆ
く。このような波及を行つてゆく間に第２図Ｂ図
示の如く格子点ENに達するとそこまでで波及処
理を停止する。上記第２図Ｂを参照して説明した
説明においてはプリント板４の表面についての波
及のみを考慮しているが、実際には各格子点にビ
アをもうけることが許容されていれば当該格子点
から裏面に波及を行つてゆくようにされる。

上述の如く波及が行われてゆきエンド点に達す
ると、今度は配線ルート決定が上記波及ルートを
逆にたどることによつて行われる。即ち、第２図
Ｂ図示の場合では例えば図示矢印Ｒの如く逆にた
どつてスタート点Ｓに達し、配線ルートを当該矢
印Ｒに沿うように決定し、当該ルートが通る各格
子点に対応する格子点情報中に当該ルート上にあ
ることを指示する。

第３図は上記波及に対応するフローチヤートを
示し、第４図は上記波及ルートを逆にたどる処理
に対応するフローチヤートを示している。図中の
「メモリｃ」は第２図Ａ図示のメモリ１０を示し、
「メモリａ」は第２図Ｃ図示のメモリ１２を示し、
「メモリｂ」は第２図Ｃ図示のメモリ１３を示し
ている。また「Ｘ層である」とはプリント板４の
１つの面を示し、「Ｘ層ではない」とはプリント
板４の他の面を示している。更に図中「Ｘ＋１」
とは注目している格子点のＸ座標値「Ｘ」に対し
て１つの右の格子点、「Ｘ−１」とは同じくＸ座
標値「Ｘ」に対して１つの左の格子点、「Ｙ＋１」
とは注目している格子点のＹ座標値「Ｙ」に対し
て１つ上の格子点「Ｙ−１」とは同じくＹ座標値
「Ｙ」に対して１つの格子点、「反対面」とは注目
している格子点と同じ座標値（Ｘ、Ｙ）をもちか
つプリント板の反対面上の格子点を示している。

第３図および第４図図示の場合には、本発明に
いう一次元探索および二次元探索が行われる処理
に対応するフローチヤートを示している。

上述の如く第１図図示の配線ルート探索処理部
における処理が行われるが、第１図図示の配線格
子領域設定部１１においては、同一の配線格子領
域内に位置する格子点についての格子情報内に共
通の特別情報を設定して他の配線格子領域内に位
置する格子点におけるそれと区別し得るようにす
る。そして、配線ルート探索処理部１は同一の配
線格子領域内で上述の波及を行うに当たつては二
次元探索をとり、他の配線格子領域へ移るときに
は一次元探索をとるようにする。

第１図図示の入力部３から配線情報が入力され
るが、このとき、配線格子領域設定部１１が配線
格子領域毎に夫々識別できる情報を各格子情報中
に記述してゆくようにする。勿論上述のスタート
点Ｓとエンド点Ｅとなどが与えられる。そして、
この状態で配線ルート探索処理部１が上述の探索
を行う。このとき、配線ルート探索処理部１は、
第２図Ｂおよび第２図Ｃを参照して説明した波及
を行うに当たつて、同一の配線格子領域内にある
格子点については二次元探索による波及を行い、
かつ他の配線格子領域へ移る場合には一次元探索
による波及を行うように動作する。このようにし
て得られた配線ルートは配線結果格納メモリ２に
格納される。即ち、第６図に示す如く、他の配線
格子領域に移行する場合には、第６図図示ビア７
の如くビア７がもうけられる形となる。なお言う
までもなく、同一の配線格子領域UNiT内におい
ても、必要ならばビア７をもうけてプリント板の
表裏両面を用いるようにされることがある。

(E) 発明の効果 以上説明した如く、本発明によれば、第６図を
参照して説明した如く、同じ配線格子領域内では
出来る限りビアを用いないようにしており、非所
望なビアの存在がなくなる。また配線格子領域内
での配線密度を向上し得る可能性が増大する。

【図面の簡単な説明】

第１図は本発明の方法を実行する一実施例構
成、第２図は第１図に示す配線ルート探索処理部
における処理を説明する説明図、第３図および第
４図は同じく配線ルート探索処理部における処理
を具体的に表すフローチヤートを示している。ま
た第５図は本発明の前提問題を説明する説明図、
第６図は本発明にいう配線格子領域を説明する説
明図、第７図は従来の方法を説明する説明図を示
している。 図中の符号１は配線ルート探索処理部、２は配
線結果格納メモリ、３は配線処理情報入力部、４
はプリント板、５は配線格子、５−１は格子点、
UNiTは配線格子領域を表している。

Claims (1)

1. 【特許請求の範囲】 １ プリント板の一方の面に形成される配線格子
   における格子点に対応して当該格子点に関連する
   配線パターン情報をもつと共に上記プリント板の
   他方の面に形成される配線格子における格子点に
   対応して当該格子点に関連する配線パターン情報
   をもつ記憶装置をそなえ、上記格子点の少なくと
   も１つをスタート点としかつ上記格子点の少なく
   とも他の１つをエンド点とする配線ルートを決定
   する配線ルート探索処理部を用いて上記配線格子
   を通る配線ルートを決定してゆく配線ルート処理
   システムにおいて、 上記配線ルート探索処理部が上記プリント板上
   の１つの面に関して実質上一次元探索を行う一次
   元探索条件状態モードと上記プリント板上の１つ
   の面に関して二次元探索を行う二次元探索条件状
   態モードとを選択するよう構成されると共に、 配線格子領域設定部をもうけて当該配線格子領
   域設定部が複数個分の上記配線格子をひとつのユ
   ニツトとした配線格子領域を設定せしめた上で、
   同一配線格子領域内の各配線格子に対応して他配
   線格子領域内の配線格子と区別し得る識別情報を
   付与するよう構成されてなり、 上記配線ルート探索処理部が、配線格子に付与
   されている上記識別情報を参照し、各個々の配線
   格子領域内における配線ルート決定に当たつては
   上記配線ルート探索処理部を二次元探索条件状態
   モードにて処理し、 かつ上記１つの配線格子領域から他の配線格子
   領域に移行する配線ルート決定に当たつては上記
   配線ルート探索処理部を一次元探索条件状態モー
   ドにて処理するようにして 当該配線結果を上記記憶装置上に格納するよう
   にした ことを特徴とする配線ルート自動決定処理方法。