JPH0652532B2 - Ｃａｄによる回路基板の配線経路探索方法 - Google Patents
Ｃａｄによる回路基板の配線経路探索方法Info
- Publication number
- JPH0652532B2 JPH0652532B2 JP63124125A JP12412588A JPH0652532B2 JP H0652532 B2 JPH0652532 B2 JP H0652532B2 JP 63124125 A JP63124125 A JP 63124125A JP 12412588 A JP12412588 A JP 12412588A JP H0652532 B2 JPH0652532 B2 JP H0652532B2
- Authority
- JP
- Japan
- Prior art keywords
- wiring
- empty
- empty line
- circuit board
- point
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Expired - Fee Related
Links
Landscapes
- Design And Manufacture Of Integrated Circuits (AREA)
Description
【発明の詳細な説明】 〔概要〕 ＣＡＤによる回路基板の配線径路探索方法に関し， ＣＡＤによる回路基板の配線径路探索にあたって，処理
時間を大幅に短縮して処理の高速化を図るとともに，必
要な処理データ量を大幅に削減することを目的とし， 回路基板に主配線方向に走る配線走行軸を複数並列に配
列して各配線走行軸を配線可能な空ラインと配線不能な
障害物ラインに区分し，始点を含む空ラインから探索を
開始して終点を含む空ラインに到達するまで互いに隣接
する空ラインを，探索した空ラインに追番を付与しつつ
順次に探索し，終点を含む空ラインに到達したら追番を
逆に辿って終点から始点に到る空ラインを決定し，この
決定した空ラインについて隣接する空ラインのオーバラ
ップする区間のうちの少なくとも１点を両者間の接続箇
所に決定することで，配線経路を決定するように構成さ
れる。
時間を大幅に短縮して処理の高速化を図るとともに，必
要な処理データ量を大幅に削減することを目的とし， 回路基板に主配線方向に走る配線走行軸を複数並列に配
列して各配線走行軸を配線可能な空ラインと配線不能な
障害物ラインに区分し，始点を含む空ラインから探索を
開始して終点を含む空ラインに到達するまで互いに隣接
する空ラインを，探索した空ラインに追番を付与しつつ
順次に探索し，終点を含む空ラインに到達したら追番を
逆に辿って終点から始点に到る空ラインを決定し，この
決定した空ラインについて隣接する空ラインのオーバラ
ップする区間のうちの少なくとも１点を両者間の接続箇
所に決定することで，配線経路を決定するように構成さ
れる。
本発明はＣＡＤ(Computer Aided Design) によるによる
回路基板の配線径路探索方法に関する。
回路基板の配線径路探索方法に関する。
ＣＡＤによる配線径路探索処理においては処理の高速化
をはかって処理時間を短縮することが必要とされてい
る。
をはかって処理時間を短縮することが必要とされてい
る。
従来，ＣＡＤ装置によるプリント基板に配線処理，すな
わち一方の部品ピン位置と他方の部品ピン位置とを接続
する配線径路を探索する処理，としてはセル方式が用い
られている。
わち一方の部品ピン位置と他方の部品ピン位置とを接続
する配線径路を探索する処理，としてはセル方式が用い
られている。
セル方式においては，プリント基板面をＸおよびＹ軸方
向にメッシュ状に区分し，このメッシュの各枡（セルと
称される）に障害物の有無を示す情報を保持させ，障害
物のないセルを始点から終点に辿ることによって配線パ
ターンの探索を行うものである。
向にメッシュ状に区分し，このメッシュの各枡（セルと
称される）に障害物の有無を示す情報を保持させ，障害
物のないセルを始点から終点に辿ることによって配線パ
ターンの探索を行うものである。
すなわち，第３図はセル構造による径路探索処理の一例
を示す図であり，図中の網目状の各枡がセルであり，斜
線が施されたセルは障害物セル，それ以外は空セルであ
る。またＳは始点となる部品ピン位置に対応する始点セ
ル，Ｅは終点となる部品ピン位置に対応する終点セルで
ある。
を示す図であり，図中の網目状の各枡がセルであり，斜
線が施されたセルは障害物セル，それ以外は空セルであ
る。またＳは始点となる部品ピン位置に対応する始点セ
ル，Ｅは終点となる部品ピン位置に対応する終点セルで
ある。
始点セルＳから終点セルＥまでのパターン径路の探索
は， （１）始点セルＳからその上下左右のセルを見てそれら
が障害物セルであるか否かを判定し，障害物セルでない
場合にはパターン走行可能であるためそれらのセルに追
番「１」をセル情報として付加する。
は， （１）始点セルＳからその上下左右のセルを見てそれら
が障害物セルであるか否かを判定し，障害物セルでない
場合にはパターン走行可能であるためそれらのセルに追
番「１」をセル情報として付加する。
（２）次に追番「１」のセルから更に上下左右のセルを
見てそれらのセルが障害物セルあるいは追番が既に付加
されたセルでなければ，それらのセルに「追番＋１」の
セル情報を付加する。なお既に追番がセル情報として付
加されているセルに対しては追番付加処理は行わない。
このような処理を繰り返し行うと，始点セルＳから始ま
って隣接する空セルに追番１，２，３，４…がセル情報
として順次に付加されていく。
見てそれらのセルが障害物セルあるいは追番が既に付加
されたセルでなければ，それらのセルに「追番＋１」の
セル情報を付加する。なお既に追番がセル情報として付
加されているセルに対しては追番付加処理は行わない。
このような処理を繰り返し行うと，始点セルＳから始ま
って隣接する空セルに追番１，２，３，４…がセル情報
として順次に付加されていく。
（３）追番が付加されたセルの隣接セルが終点セルＥと
なった場合，径路探索処理は完了する。第３図では追番
「１１」の隣接セルが終点セルＥとなっている。
なった場合，径路探索処理は完了する。第３図では追番
「１１」の隣接セルが終点セルＥとなっている。
配線パターン径路は，終点セルＥから各セルの追番を，
Ｅ→１１→１０→９→……→３→２→１→Ｓのように逆
にトレースして始点セルＳまで到達することによって求
められる。
Ｅ→１１→１０→９→……→３→２→１→Ｓのように逆
にトレースして始点セルＳまで到達することによって求
められる。
セル構造による配線径路の探索では，始点セルＳと終点
セルＥとが遠く離れている場合には多数のセルをその間
に経由しなければなない。この場合，セル情報の蓄積は
多数の経由セルの各々について行うため，処理時間が長
くなり，処理するデータ量も膨大となる。
セルＥとが遠く離れている場合には多数のセルをその間
に経由しなければなない。この場合，セル情報の蓄積は
多数の経由セルの各々について行うため，処理時間が長
くなり，処理するデータ量も膨大となる。
したがって本発明の目的は，ＣＡＤによる回路基板の配
線径路探索にあたって，処理時間を大幅に短縮して処理
の高速化を図るとともに，必要な処理データ量を大幅に
削減することにある。
線径路探索にあたって，処理時間を大幅に短縮して処理
の高速化を図るとともに，必要な処理データ量を大幅に
削減することにある。
本発明にかかるＣＡＤによる回路基板の配線経路探索方
法は，回路基板に主配線方向に走る配線走行軸を複数並
列に配列して各配線走行軸を配線可能な空ラインと配線
不能な障害物ラインに区分し，始点を含む空ラインから
探索を開始して終点を含む空ラインに到達するまで互い
に隣接する空ラインを，探索した空ラインに追番を付与
しつつ順次に探索し，終点を含む空ラインに到達したら
追番を逆に辿って終点から始点に到る空ラインを決定
し，この決定した空ラインについて隣接する空ラインの
オーバラップする区間のうちの少なくとも１点を両者間
の接続箇所に決定することで，配線経路を決定するよう
に構成される。
法は，回路基板に主配線方向に走る配線走行軸を複数並
列に配列して各配線走行軸を配線可能な空ラインと配線
不能な障害物ラインに区分し，始点を含む空ラインから
探索を開始して終点を含む空ラインに到達するまで互い
に隣接する空ラインを，探索した空ラインに追番を付与
しつつ順次に探索し，終点を含む空ラインに到達したら
追番を逆に辿って終点から始点に到る空ラインを決定
し，この決定した空ラインについて隣接する空ラインの
オーバラップする区間のうちの少なくとも１点を両者間
の接続箇所に決定することで，配線経路を決定するよう
に構成される。
本発明方法を第１図の径路探索処理例を参照にして説明
する。第１図は第３図の場合と障害物の配置位置が同じ
環境における径路探索処理を示す図である。
する。第１図は第３図の場合と障害物の配置位置が同じ
環境における径路探索処理を示す図である。
プリント基板配線においては，基板を多層構造として配
線層別に主配線方向を決定し，ＸＹ軸方向に分離配線す
る手法が配線率向上に寄与することが知られている。
線層別に主配線方向を決定し，ＸＹ軸方向に分離配線す
る手法が配線率向上に寄与することが知られている。
本発明方法では，各配線層別に径路探索を行うものと
し，第２図はＸ軸方向が主配線方向となっている層につ
いての径路探索を取り扱う。すなわち第２図では主配線
方向に平行な複数のパターン走行軸Ｌ１〜Ｌ８を複数
本，列状に配置する。各パターン走行軸は配線パターン
の走行が可能な空ライン範囲と不可能な障害物範囲とに
区分された空ライン構造となっている。障害物範囲は図
中に斜線領域で示される。
し，第２図はＸ軸方向が主配線方向となっている層につ
いての径路探索を取り扱う。すなわち第２図では主配線
方向に平行な複数のパターン走行軸Ｌ１〜Ｌ８を複数
本，列状に配置する。各パターン走行軸は配線パターン
の走行が可能な空ライン範囲と不可能な障害物範囲とに
区分された空ライン構造となっている。障害物範囲は図
中に斜線領域で示される。
始点部品ピン位置Ｓから終点部品ピン位置Ｅまでの径路
探索は以下の手順により行われる。
探索は以下の手順により行われる。
（１）始点Ｓをその領域上に含む空ラインに空ライン情
報として追番「１」を付加する。
報として追番「１」を付加する。
（２）追番「１」の空ラインからみて上下配線走行軸Ｌ
５，Ｌ７上の空ライン「１」に隣接する空ライン位置を
探し，あればその空ラインに対して「追番＋１」を空ラ
イン情報として付加する。この時，既に空ラインに追番
が付加されていれば追番付加処理は行わない。
５，Ｌ７上の空ライン「１」に隣接する空ライン位置を
探し，あればその空ラインに対して「追番＋１」を空ラ
イン情報として付加する。この時，既に空ラインに追番
が付加されていれば追番付加処理は行わない。
（３）上述の処理（２）を，終点Ｅを含んだ空ラインに
追番が付加されるまで繰り返し行い，終点Ｅの空ライン
に追番が付加されたのならば径路探索処理を完了する。
追番が付加されるまで繰り返し行い，終点Ｅの空ライン
に追番が付加されたのならば径路探索処理を完了する。
（４）終点Ｅを含む空ラインから，Ｅ→４→３→２→１
→Ｓの順に追番を逆に辿る逆トレースを行って，終点Ｅ
から始点Ｓに到る空ラインを決定する。
→Ｓの順に追番を逆に辿る逆トレースを行って，終点Ｅ
から始点Ｓに到る空ラインを決定する。
（５）上記の（４）で決定した空ラインについて所定の
規則に従って隣接する空ライン間を接続して，配線パタ
ーン経路を決定する。所定の規則としては，，空ライン
４上の終点Ｅと空ライン１上の始点Ｓを固定点とし，例
えば空ライン４と空ライン３間は両者の配線がオーバラ
ップしている区間のうちの少なくとも１点を両者間の接
続箇所とする。これを空ライン３と２間，空ライン２と
１間についても行う。この際，図４に示されるように，
これらの空ライン１〜４で作られる面領域を主配線方向
と垂直方向あるいは４５゜方向に走って空ライン１から
４に到る配線（イ）（ロ）などが可能であれば，そのよ
うに配線するとよい。
規則に従って隣接する空ライン間を接続して，配線パタ
ーン経路を決定する。所定の規則としては，，空ライン
４上の終点Ｅと空ライン１上の始点Ｓを固定点とし，例
えば空ライン４と空ライン３間は両者の配線がオーバラ
ップしている区間のうちの少なくとも１点を両者間の接
続箇所とする。これを空ライン３と２間，空ライン２と
１間についても行う。この際，図４に示されるように，
これらの空ライン１〜４で作られる面領域を主配線方向
と垂直方向あるいは４５゜方向に走って空ライン１から
４に到る配線（イ）（ロ）などが可能であれば，そのよ
うに配線するとよい。
なお，上記接続を行った結果，隣接する空ライン間で電
気経路として重複しているため不要となる部分が生じた
場合には，経路決定後にその部分を再び空ラインとして
解放するとよい。
気経路として重複しているため不要となる部分が生じた
場合には，経路決定後にその部分を再び空ラインとして
解放するとよい。
この空ライン構造による径路探索では，従来，複数のパ
ターン走行可能セルで構成されていた箇所をライン化し
て連続した１ラインと見なしてＦＲＯＭ−ＴＯ座標で管
理するものであるから，始点と終点を結ぶ径路はそれを
構成するコンポーネントが一般に少なくてすむ。上述の
例では，従来のセル方式の場合には経由セル数が１１個
であるものが，本発明の空ライン方式では経由ライン数
が４本ですみ，この経由コンポーネント数の差がそのま
ま径路探索時間の差およびデータ削減量となる。
ターン走行可能セルで構成されていた箇所をライン化し
て連続した１ラインと見なしてＦＲＯＭ−ＴＯ座標で管
理するものであるから，始点と終点を結ぶ径路はそれを
構成するコンポーネントが一般に少なくてすむ。上述の
例では，従来のセル方式の場合には経由セル数が１１個
であるものが，本発明の空ライン方式では経由ライン数
が４本ですみ，この経由コンポーネント数の差がそのま
ま径路探索時間の差およびデータ削減量となる。
以下，図面を参照して本発明の実施例を説明する。第２
図は交換機用のプリント基板を設計するためのＣＡＤ装
置に本発明方法を適用した場合のプリント基板配線処理
の手順の一実施例を示す流れ図である。
図は交換機用のプリント基板を設計するためのＣＡＤ装
置に本発明方法を適用した場合のプリント基板配線処理
の手順の一実施例を示す流れ図である。
まず初期設定として，部品ピン位置や配線禁止領域等の
データにもとづき，プリント基板上の主配線方向の走行
軸毎にパターン走行可能空ラインと障害物ラインとを決
定し，これらの情報を空ライン構造情報としてメモリＤ
１に保持する（ステップＳ２）。
データにもとづき，プリント基板上の主配線方向の走行
軸毎にパターン走行可能空ラインと障害物ラインとを決
定し，これらの情報を空ライン構造情報としてメモリＤ
１に保持する（ステップＳ２）。
次に全配線区間中から，これから配線処理しようとして
いる配線区間の始点ピン位置と終点ピン位置のデータを
一つ抽出する（ステップＳ３）。
いる配線区間の始点ピン位置と終点ピン位置のデータを
一つ抽出する（ステップＳ３）。
抽出するデータがない場合には全配線区間の配線トライ
が終了したものであるので，配線処理を終了する（ステ
ップＳ８）。
が終了したものであるので，配線処理を終了する（ステ
ップＳ８）。
未配線区間が抽出されたのならば，当該区間に対して前
述の〔作用〕の欄で説明した空ライン構造を使用して配
線径路を探索する（ステップＳ４）。
述の〔作用〕の欄で説明した空ライン構造を使用して配
線径路を探索する（ステップＳ４）。
径路探索の結果，配線不可能であれば，配線処理で各空
ラインに付加した到着追番情報をクリアして（ステップ
Ｓ７），再び未配線区間の抽出を行う（ステップＳ
３）。
ラインに付加した到着追番情報をクリアして（ステップ
Ｓ７），再び未配線区間の抽出を行う（ステップＳ
３）。
配線可能な径路が探索できた時には，そのパターンデー
タを障害物データとして空ライン構造Ｄ１に追加する
（ステップＳ６）。その後，各空ラインの追番情報をク
リアする（ステップＳ７）。なお空ライン構造Ｄ１は各
区間の配線処理毎に毎回再設定する必要はなく，配線結
果パターンデータを障害物として初期空ライン構造に追
加（更新）していくものである。
タを障害物データとして空ライン構造Ｄ１に追加する
（ステップＳ６）。その後，各空ラインの追番情報をク
リアする（ステップＳ７）。なお空ライン構造Ｄ１は各
区間の配線処理毎に毎回再設定する必要はなく，配線結
果パターンデータを障害物として初期空ライン構造に追
加（更新）していくものである。
ステップＳ３で全区間の配線が終了したと判定された場
合には処理を終了する（ステップＳ８）。
合には処理を終了する（ステップＳ８）。
交換機用プリント基板は他のプリント基板と同様に多く
の回路的機能を満足させるべく回路の大規模化，プリン
ト基板に搭載される部品の高安定化が要求されており，
このためには回路配線が非常に複雑化する。上述の本発
明方法はこれら多数の配線区間を持ち，配線が進むにつ
れて障害物が増えて配線が複雑となる処理に対して，顕
著な処理時間と処理データ量の削減効果がある。
の回路的機能を満足させるべく回路の大規模化，プリン
ト基板に搭載される部品の高安定化が要求されており，
このためには回路配線が非常に複雑化する。上述の本発
明方法はこれら多数の配線区間を持ち，配線が進むにつ
れて障害物が増えて配線が複雑となる処理に対して，顕
著な処理時間と処理データ量の削減効果がある。
本発明によれば，ＣＡＤによる回路基板の配線径路探索
にあたって，処理時間を大幅に短縮して処理の高速化を
図れるとともに，必要な処理データ量も大幅に削減する
ことができる。
にあたって，処理時間を大幅に短縮して処理の高速化を
図れるとともに，必要な処理データ量も大幅に削減する
ことができる。
第１図は本発明方法による径路探索処理を説明する図， 第２図は本発明方法を適用したＣＡＤ装置における径路
探索処理手順の例を示した流れ図， 第３図は従来のセル方式による径路探索処理を説明する
図である。 第４図は本発明方法における主配線方向に垂直な方向へ
の配線経路を説明するための図である。 図において， Ｓ……始点、Ｅ……終点 １〜１１……追番
探索処理手順の例を示した流れ図， 第３図は従来のセル方式による径路探索処理を説明する
図である。 第４図は本発明方法における主配線方向に垂直な方向へ
の配線経路を説明するための図である。 図において， Ｓ……始点、Ｅ……終点 １〜１１……追番
Claims (1)
- 【請求項１】回路基板に主配線方向に走る配線走行軸を
複数並列に配列して各配線走行軸を配線可能な空ライン
と配線不能な障害物ラインに区分し， 始点を含む空ラインから探索を開始して終点を含む空ラ
インに到達するまで互いに隣接する空ラインを，探索し
た空ラインに追番を付与しつつ順次に探索し， 終点を含む空ラインに到達したら追番を逆に辿って終点
から始点に到る空ラインを決定し， この決定した空ラインについて隣接する空ラインのオー
バラップする区間のうちの少なくとも１点を両者間の接
続箇所に決定することで，配線経路を決定するようにし
たＣＡＤによる回路基板の配線経路探索方法。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP63124125A JPH0652532B2 (ja) | 1988-05-20 | 1988-05-20 | Ｃａｄによる回路基板の配線経路探索方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP63124125A JPH0652532B2 (ja) | 1988-05-20 | 1988-05-20 | Ｃａｄによる回路基板の配線経路探索方法 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH01293472A JPH01293472A (ja) | 1989-11-27 |
| JPH0652532B2 true JPH0652532B2 (ja) | 1994-07-06 |
Family
ID=14877546
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP63124125A Expired - Fee Related JPH0652532B2 (ja) | 1988-05-20 | 1988-05-20 | Ｃａｄによる回路基板の配線経路探索方法 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JPH0652532B2 (ja) |
-
1988
- 1988-05-20 JP JP63124125A patent/JPH0652532B2/ja not_active Expired - Fee Related
Also Published As
| Publication number | Publication date |
|---|---|
| JPH01293472A (ja) | 1989-11-27 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| JPH0550780B2 (ja) | ||
| JPH0786883B2 (ja) | 網図または諭理回路図自動生成方法およびそのシステム | |
| JP3608832B2 (ja) | 自動配線方法および自動配線装置 | |
| JP4311244B2 (ja) | 配線経路決定方法及びシステム | |
| JPH0652532B2 (ja) | Ｃａｄによる回路基板の配線経路探索方法 | |
| US5825659A (en) | Method for local rip-up and reroute of signal paths in an IC design | |
| JP2523702B2 (ja) | 半導体集積回路の自動配線方法 | |
| JP2000057175A (ja) | 半導体集積回路装置の自動配線方式 | |
| JPS5846173B2 (ja) | 論理配線設計方式 | |
| JP2566788B2 (ja) | プリント板の配線方式 | |
| Nishioka et al. | A minicomputerized automatic layout system for two-layer printed wiring boards | |
| JP2938910B2 (ja) | 三次元配線方法 | |
| JP3006244B2 (ja) | 自動配線方式 | |
| JP2536189B2 (ja) | 自動配線方法 | |
| JP3006156B2 (ja) | 自動配線方式 | |
| JP3077383B2 (ja) | プリント基板ｃａｄの自動配線機構 | |
| JPH0325942A (ja) | 配線パターン決定方法及びそのシステム | |
| JP2607694B2 (ja) | Ｃａｄシステム | |
| JPS5910767Y2 (ja) | 多層印刷配線構造 | |
| JPS62209890A (ja) | 自動配線方法 | |
| JP2914025B2 (ja) | Ｌｓｉの自動配置配線処理方法 | |
| JP2721712B2 (ja) | 自動配線方法 | |
| JPH0476154B2 (ja) | ||
| JP2523703B2 (ja) | 半導体集積回路の自動配線方法 | |
| JPH0754532B2 (ja) | 多層同時配線方法 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| LAPS | Cancellation because of no payment of annual fees |