JP2982017B2 - Automatic wiring processing method - Google Patents

Description

Description: BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an improvement in an automatic wiring processing method in a printed circuit board design system using a computer.

<Prior Art> Conventionally, there is a printed circuit board design system that automatically performs wiring and the like of a printed circuit board by using a computer.

<Problems to be solved by the invention> There are various automatic wiring algorithms used in this type of printed circuit board design system.
After all of them fix the parts, that is, the arranged parts position is treated as an obstacle that can never be overcome in the wiring process (absolutely inviolable obstacle),
Search for routes that do not lead to wiring over parts,
This is a wiring method for selecting a circuitous wiring. For example, when connecting points A and B as shown in FIG. 6 (a), if a slight change (movement of parts) is made, wiring between A and B can be easily performed as shown in FIG. 6 (b). Even in such a case, there is a problem that since the positions of the component 1 and the component 2 are fixed, a detour route as shown by the route P must be selected.

In the manual wiring configuration by an expert, wiring is performed while changing the position (arrangement) of parts as necessary, and the arrangement of parts is changed as shown in FIG. It can be easily wired. One of the points that such a wiring method is inferior to the expert of the automatic wiring system.

The object of the present invention has been made in view of such a point. In the wiring process, if necessary, wiring is performed in consideration of a change in component arrangement, and such processing significantly increases processing time. An object of the present invention is to provide an automatic wiring processing method that does not invite.

<Means for Solving the Problems> FIG. 1 is a flow chart of the principle of the automatic wiring processing method of the present invention, and a route is obtained by the following procedure.

Treat the placed parts as obstacles with penalties and search all possible paths.

For the searched route, a route with the lowest cost value defined by the product of the route length and the penalty value is selected, and if the route crosses an already-placed component, the position of the component is moved so as not to get over. .

<Operation> Conventionally, the arranged components are treated as obstacles that cannot be overcome, but in the present invention, they are treated as those that can be overcome by paying a predetermined penalty.

When wiring, if it is not necessary to go over the placed components, perform wiring using the normal wiring processing method. Perform

Next, with respect to the wiring that goes over, the part is moved so that the part that goes over (the overlapping part of the route and the arranged part) is eliminated.

<Example> Hereinafter, the present invention will be described in detail with reference to the drawings. FIG. 2 is a block diagram showing the configuration of a system for realizing the automatic wiring processing method of the present invention. In FIG. 1, reference numeral 1 denotes a storage device which stores all graphic information on a printed circuit board, that is, data such as arranged components and already-routed paths. Reference numeral 2 denotes a graphic data read processing unit that reads information from the storage device 1, and adds an appropriate penalty to the arranged components. 3 is an optimal route search processing unit,
A process of finding the lowest cost route among the searched possible routes is performed. The route cost is a value defined by the product of the route length and the penalty value. The penalty value added by the graphic data read processing unit 2 is:
Normally, the value is set to 1.0, and the value of the placed component is set to a value larger than this.

The search for the route is performed by, for example, a maze method. When it becomes necessary to read the graphic information from the storage device 1, the graphic data read processing unit 2 is used.

Reference numeral 4 denotes a processing unit for overcoming obstacles due to the movement of components. When the route obtained by the optimum route search processing unit 3 overlaps with the arranged component, a process for moving the component and solving the problem is performed. Note that data necessary for determining whether or not the route overlaps with a component already placed is read directly from the storage device 1.

The operation related to the automatic wiring processing method in such a configuration will be described next with reference to FIGS. In addition,
FIG. 3 and FIG. 4 are operation diagrams, and FIG. 5 is an explanatory diagram for explaining a connection state. Hereinafter, a case where the points A and B are connected as shown in FIG. 5 will be described as an example. It is assumed that the wiring path requires a width of 4 (four times as large as a reference width having an interval between an adjacent component or an adjacent pattern).

First, regarding the connection between the points A and B, all possible routes are searched using, for example, a maze method. As a result, as shown in FIG. 5 (b), two solutions, that is, paths P1 and P2 are obtained.

Here, each cost is calculated according to the cost calculation flow of FIG. The result of the calculation is as follows.

Route P1: (route length is 30) x (penalty is 1.0) = 30 Route P2: (route length is 10) x (penalty is twice the initial value, 2.
0) = 20 Next, the route with the lowest cost is selected by the processing shown in FIG. 3, and the route P2 is selected.

By the way, this solution 2 (path P2) intersects with the arrangement component 2 (the width is 4 or less). Therefore, the component 2 is moved right until there is no overlap with the route P2. As a result, the result is as shown in FIG. 5C, and the wiring is completed.

In the above embodiment, the penalty value of the component is doubled, but a low value is given to a component that is easy to move, and a high value is given to a component that is difficult to move. Wiring can also be performed. For example, when the penalty value is set to 5 in the above embodiment, the solution 1 (route P1) without any change in the arrangement is selected.

It should be noted that the component arrangement change processing is performed only when it is necessary, and there is no waste in the processing.

Also, in the method of the present invention, a process of moving a component is newly required as compared with the conventional process. However, in the wiring problem, most of the processing time is in the search process. Is a time that hardly causes a problem in execution time.

<Effects of the Invention> As described in detail above, the present invention has the following effects.

Wiring can be performed in consideration of a change in component arrangement, which was not possible in the past.

In addition, the priority for the placement change can be expressed, and the found path is the optimum path when both the placement and the wiring are considered at the same time.

Further, the automatic wiring processing method does not significantly affect the execution speed.

[Brief description of the drawings]

FIG. 1 is a flow chart showing the principle of the automatic wiring processing method of the present invention, and FIG.
FIGS. 3 and 4 are diagrams showing an operation flow, and FIGS. 5 and 6 are explanatory diagrams showing connection states. 1 storage device, 2 graphic data read processing unit, 3
... Optimal route search processing unit, 4...

Claims (1)

(57) [Claims] 1. An automatic wiring processing method for performing automatic wiring of a printed circuit board, comprising: treating parts arranged on the printed circuit board as obstacles having a penalty; and searching for all possible wiring paths; A route having the lowest cost value defined by the product of the length of the route and the penalty value is selected from the searched wiring routes, and if the route passes over an already-positioned obstacle, the route is determined so that the route is not overtaken. An automatic wiring processing method, comprising a step of moving the position of an obstacle.