JPH0426148B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION (A) Technical Field of the Invention The present invention relates to a method for optimizing and determining wiring routes, particularly to determining a wiring route along a wiring grid formed on both sides of a printed circuit board. After that, the wiring route that has been tentatively determined can be further removed by removing vias (ViA - through holes) that can be placed in undesired positions, and the wiring route that could not be determined because the route could not be found first can be determined. The present invention relates to a wiring route optimization determination processing method.

(B) Background and problems of the technology Conventionally, when determining the wiring route to be created on a printed circuit board, a wiring route search processing unit is used to determine the wiring route as shown in Figure 6. is being carried out. In addition, in Figure 6,
1 represents a wiring route search processing section, 2 represents a wiring result storage memory, and 3 represents a wiring processing information input section. That is, desired information is input from the wiring processing information input section 3, a wiring route is determined by the wiring route search processing section 1, and the obtained wiring route is stored in the wiring result storage memory 2.

This situation will be explained with reference to FIG. In the figure, 4 is a printed board, 5 is a wiring grid formed on both the front and back sides of the printed board 4, and the wiring route to be determined is determined along the wiring grid, and 5-1 is a grid. Point, 6 is
IC pin, 7 is a via formed on the printed board,
Reference numeral 8 represents a wiring route formed on, for example, the front side of the printed board, and 9 represents a wiring route formed on the back side of the printed board.

The processing in the wiring route search processing unit 1 shown in FIG. 6 will be described later with reference to FIG. 2, but for example, when determining the wiring route from IC pin 6A to IC pin 6B shown in FIG. For example, on the front side of the printed board, a wiring route 8 is provided that extends only in the illustrated X-axis direction (extension in the Y-axis direction for one grid is allowed), and on the back side of the printed board, it is provided in the illustrated Y-axis direction. Only in the direction (1
A wiring route 9 is provided that extends (extension in the X-axis direction of the lattice is allowed), and when connecting both wiring routes 8 and 9, vias 7 are created on the printed board 4 to connect them. That's what I do. Of course, when determining the wiring route between the IC pins 6A and 6B, the wiring route is determined by using only the surface of the printed board 4, for example, and extending in both the X-axis direction and the Y-axis direction. However, if this decision is allowed, it may undesirably intersect with the wiring route 8 between the IC pins 6C and 6D shown in FIG. For this purpose, the wiring route 8 extending in the X-axis direction and the wiring route 9 extending in the Y-axis direction are coupled by vias 7 to avoid the above-mentioned intersection.

The wiring route search processing unit 1 shown in FIG. 6 determines the wiring route as explained with reference to FIG. As in the case with 9, other X
If the wires are not intersected by wiring routes extending in the axial direction, there is no reason to take the trouble to create vias 7 and utilize both the front and back sides of the printed board.

(C) Object and Structure of the Invention The present invention aims to solve the above-mentioned problems, and by reexamining the wiring route once determined as shown in FIG. The purpose of this method is to omit the ``routes'' and thereby try to determine new wiring routes that could not be determined previously. Therefore, the wiring route optimization determination processing method of the present invention has wiring pattern information related to the grid points corresponding to the grid points in the wiring grid formed on one side of the printed board, and also has wiring pattern information related to the grid points. A storage device having wiring pattern information related to a grid point in a wiring grid formed on the other surface is provided, and at least one of the grid points is used as a starting point and at least another of the grid points is set as a starting point. In a wiring route processing system that determines a wiring route that passes through the wiring grid using a wiring route search processing unit that determines a wiring route that has one of the end points as an end point, the wiring route search processing unit determines a wiring route that passes through the wiring grid. The device is configured to be able to select between a one-dimensional search condition state mode in which a one-dimensional search is substantially performed on one surface of the printed board and a two-dimensional search condition state mode in which a two-dimensional search is performed in relation to one surface on the printed board. and a storage device in which the wiring pattern information regarding the wiring route obtained by setting the wiring route search processing unit to the one-dimensional search condition state mode is stored, and the information obtained on the storage device. a wiring route deletion processing unit which temporarily deletes one wiring route as a processing target and then provides a start point and an end point for the wiring route to be processed; and the wiring route search processing unit. , a wiring result memory in which wiring pattern information resulting from a search process performed under the two-dimensional search condition state mode using the results of temporary deletion performed by the wiring route deletion processing unit; The wiring route search processing unit executes the process under the one-dimensional search condition state mode to perform the above-mentioned process for the wiring route obtained by setting the one-dimensional search condition state mode. The information is stored in a storage device in which wiring pattern information is stored, and then the wiring route deletion processing unit executes processing under the two-dimensional search condition state mode, and temporary deletion is performed by the wiring route deletion processing unit. The present invention is characterized in that a search process is performed using the results of the process, and wiring pattern information resulting from the process is stored in the wiring result memory. This will be explained below with reference to the drawings.

(D) Embodiments of the Invention FIG. 1 shows the configuration of an embodiment for carrying out the method of the present invention, FIG. 2 is an explanatory diagram illustrating the processing in the wiring route search processing section shown in FIG. Similarly, FIG. 4 shows a flowchart specifically representing the processing in the wiring route search processing section. In addition, FIG. 5 is an explanatory diagram explaining the prerequisite problem of the present invention,
FIG. 6 shows an explanatory diagram for explaining the conventional method.

In FIG. 1, reference numerals 1 and 2 correspond to those in FIG. 6, and 10 is a temporary wiring processing memory, for example, by executing the processing shown in FIG. 6, the wiring shown in FIG. The information obtained in the result storage memory 2 is stored as grid point information, and 11 represents a wiring route deletion processing section. As explained with reference to FIGS. 5 and 6, the illustrated wiring route search processing unit 1 searches wiring routes extending in the X-axis direction on the front surface of the printed board, and wiring routes extending in the Y-axis direction on the back surface of the printed board. A two-dimensional search condition that has a search function in the one-dimensional search condition state where the route is determined, and can extend in either the X-axis direction or the Y-axis direction only on the front or back side of the printed board. It has a state search function. It can be considered that the mode can be changed by switching the mode.

Before explaining the present invention, the processing in the illustrated wiring route search processing section 1 will be explained.

As shown in FIG. 2A, "lattice point information" is stored in the memory corresponding to the grid points 5-1, 5-1, . . . shown in FIG. Note that the memory shown in FIG. 2A may be considered to be the same as the temporary wiring processing memory 10 shown in FIG. In general, the following may be considered as grid point information corresponding to a grid point having coordinates (xi, yi).

That is, the types of information are (a) "Numberable grid" information that indicates whether or not it is permissible to spread numbering for wiring route searching as described later; (b) wiring route searching. (c) "Route search start or end grid point" information indicating that the wiring route is a starting point or end point (such as the position of an IC pin); (c) "Obstacle" information indicating that the wiring route is prohibited; "Object grid point" information is prepared, and as data for each information, (d) Corresponding to the information in (a) above, data indicating that it is vacant or the number that has been propagated is written, ( e) Corresponding to the information in (b) above, it is written whether it is a start point S, a point SN adjacent to the start point, an end point E, or a point EN adjacent to the end point, (f) Corresponding to the information in (c) above, the multiplicity of obstacles is described. Furthermore, whether or not the grid point is prohibited from forming a via, and if so, its multiplicity is given.

Assuming that the wiring route search processing unit 1 shown in FIG. 1 is in a mode that allows the above-mentioned two-dimensional search, the wiring route search is performed as shown in FIGS. 2B and 2C.

First, as shown in Figure 2B, the starting point S of the wiring route is at the coordinates (0, 0), the end point E is at the coordinates (7, 0), and the obstacle grid point is at the coordinates (4, 0). , 0) is shown in Figure 2A.
It is stored (or has been stored) on the illustrated memory 10 . In addition, the coordinates (1, 0), (0, 1),
(-1, 0), (0, -1) is the neighboring point SN of the start point
and the coordinates (8, 0), (7, 1), (6,
It is stored that 0) and (7, -1) are the neighboring points EN of the end point.

Under this state, the above lattice point is stored on memory a12.
Collect grid point information regarding SN. Then, focusing on one grid point SN (for example, coordinates (1, 0)),
A lattice of lattice points corresponding to coordinates (2, 0), (1, 1), (1, -1) in two-dimensional directions (however, one direction is omitted because it is the direction of the ripple source) adjacent to the lattice point. The point information is collected on the memory b13, and the number "1" is given to the "numberable grid" information of the grid point. Similarly, focusing on the grid point SN (coordinates (0, 1)), coordinates (1, 1), (0, 2),
Collect the lattice point information about the lattice points corresponding to (-1, 1) on the memory b13 and set the number "1"
give. In the same manner, when the number "1" has finished spreading next to the grid point SN, next memory b13
The contents of the grid point are transferred to the memory a12, and the neighboring grid points to which the number "1" has spread are collected in the memory b13, thereby giving the number "2". That is, as shown in FIG. 2B, the numbers "1", "2",
``3''... will spread in sequence. At this time, if there is an obstacle grid point as in the case of coordinates (4, 0), the ripple effect is performed while avoiding it. While carrying out such propagation, when the grid point EN is reached as shown in FIG. 2B, the propagation process is stopped there. In the explanation given with reference to FIG. 2B above, only the influence on the surface of the printed board 4 is considered, but in reality, if it is allowed to create a via at each lattice point, the corresponding lattice point It is made to spread from the beginning to the other side.

When the propagation continues as described above and reaches the end point, the wiring route is determined by tracing the propagation route in reverse. That is, in the case shown in FIG. 2B, for example, the wiring route is determined to follow the arrow R in the diagram in the opposite direction to reach the starting point S, and the wiring route is determined to follow the arrow R, and the wiring route is determined to correspond to each lattice point that the route passes through. Indicates that the grid point is on the route in the grid point information.

FIG. 3 shows a flowchart corresponding to the above-mentioned spread, and FIG. 4 shows a flowchart corresponding to the process of retracing the above-mentioned spread route. "Memory c" in the figure indicates the memory 10 shown in FIG. 2A,
"Memory a" indicates the memory 12 shown in FIG. 2C,
"Memory b" indicates the memory 13 shown in FIG. 2C. Further, "being an X layer" refers to one surface of the printed board 4, and "not being an X layer" refers to another surface of the printed board 4. Furthermore, in the figure, "X+1" means one lattice point to the right of the X coordinate value "X" of the lattice point of interest, and "X-1" means one lattice point to the right of the X coordinate value "X" of the lattice point of interest. The grid point on the left, "Y+1" is the grid point one above the Y coordinate value "Y" of the grid point of interest, and "Y-1" is the same grid point with respect to the Y coordinate value "Y". The lattice point one below, ``opposite side'', indicates a lattice point that has the same difference standard value (X, Y) as the lattice point of interest and is on the opposite side of the printed board.

The illustrations in FIGS. 3 and 4 are flowcharts corresponding to processes in which one-dimensional search and two-dimensional search are performed according to the present invention.

As described above, the processing in the wiring route search processing section shown in FIG. The wiring route determined under the original search condition is stored, and the first
At the time of processing shown in the diagram, the wiring route search processing unit 1
is processed under two-dimensional search conditions.

The wiring routes that have already been tentatively determined are supplied from the memory 10 shown in FIG. The wiring route is deleted in the deletion processing unit 11, and the start point S and end point E of the deleted wiring route are given. In this state, the wiring route search processing section 1 performs a search under the two-dimensional search condition. As a result, for example, from IC pin 6E shown in FIG.
For the wiring route to pin 6C, please use via 7.
will be omitted. This result is stored in memory 2. When determining the next route by deleting the wiring route, the previously obtained result is used. Of course, even if the two-dimensional search is performed, there may be no change at all, but in general, many undesired vias will be omitted. And by using this result,
Even for routes for which wiring routes could not be determined by only the process shown in FIG. 6, a desired route can be determined.

(E) Effects of the Invention As explained above, according to the present invention, it is possible to omit vias in undesired positions that occur only in the case of the process shown in FIG. 6. It also becomes possible to determine routes that could not be determined. Needless to say, in the present invention, the wiring pattern is once obtained in a simple form, and then, if it can be modified into a more preferable form, it is modified. Therefore, compared to the process that tries to determine the most preferable wiring pattern from the beginning, the process is simpler, and since it is possible to leave unmodified areas that cannot be modified, it requires strict judgment processing. It has the advantage of not being

[Brief explanation of drawings]

FIG. 1 is an exemplary configuration for carrying out the method of the present invention, FIG. 2 is an explanatory diagram explaining the processing in the wiring route search processing section shown in FIG. 1, and FIGS. 3 and 4 are wiring route searching. A flowchart specifically representing processing in the processing section is shown. In addition, FIG. 5 is an explanatory diagram explaining the prerequisite problem of the present invention,
FIG. 6 shows an explanatory diagram for explaining the conventional method. In the figure, 1 is a wiring route search processing unit, 2 is a wiring result storage memory, 10 is a temporary wiring processing memory, 1
1 represents a wiring route deletion processing section.

Claims (1)

[Scope of Claims] 1. Wiring that corresponds to a grid point in a wiring grid formed on one surface of a printed board and has wiring pattern information related to the grid point, and that is formed on the other surface of the printed board. A memory device having wiring pattern information associated with each grid point in the grid is provided, and at least one of the grid points is set as a start point and at least one other of the grid points is set as an end point. In a wiring route processing system that determines a wiring route passing through the wiring grid using a wiring route search processing unit that determines a wiring route, the wiring route search processing unit is configured to perform a wiring route search processing unit that determines a wiring route that passes through the wiring grid using a wiring route search processing unit that determines a wiring route. The wiring route search processing unit is configured to be able to select between a one-dimensional search condition state mode in which an original search is performed and a two-dimensional search condition state mode in which a two-dimensional search is performed regarding one surface on the printed board. A storage device that stores the wiring pattern information about the wiring route obtained by setting the above one-dimensional search condition state mode, and one wiring route obtained on the storage device as the processing target. A wiring route deletion processing unit that temporarily deletes the wiring route to be processed and then provides a start point and an end point for the wiring route to be processed, and the wiring route search processing unit operates in the two-dimensional search condition state mode. A wiring result memory is created in which the wiring pattern information of the processing result obtained by performing the search process using the result of the temporary deletion performed by the wiring route deletion processing section is created, and the above wiring The route search processing unit executes processing under the one-dimensional search condition state mode, and stores the wiring pattern information regarding the wiring route obtained by setting the one-dimensional search condition state mode. The information is stored in the device, and then the wiring route deletion processing unit executes the processing under the two-dimensional search condition state mode, and the result of the temporary deletion performed by the wiring route deletion processing unit is used. A wiring route optimization determination processing method, characterized in that a search process is performed and wiring pattern information resulting from the process is stored in the wiring result memory.