Browse Prior Art Database

# Algorithm to Trace a Path for Wiring Between Circuits

IP.com Disclosure Number: IPCOM000083182D
Original Publication Date: 1975-Apr-01
Included in the Prior Art Database: 2005-Mar-01
Document File: 2 page(s) / 14K

IBM

## Related People

Habra, RR: AUTHOR

## Abstract

Fig. 1 shows a typical wiring for a net between different circuit pins. Each node is given a unique number and a connection matrix is generated (Fig. 2).

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 2

Algorithm to Trace a Path for Wiring Between Circuits

Fig. 1 shows a typical wiring for a net between different circuit pins. Each node is given a unique number and a connection matrix is generated (Fig. 2).

The matrix reads as follows: node 1 is connected to node 2. Node 2 is connected to nodes 1, 9 and 3, etc. . .

Suppose it is desired to find a oath from node 1 to node 8. The algorithm works as follows. The matrix is searched for all entries with one connection, excluding the FROM and TO points. These nodes are deleted, as well as any reference to them in the matrix. An array containing the number of connections to every node is revised accordingly. Nodes 6, 11 and 12 will thus be deleted. Figs. 3 and 4 show the result of such an operation.

The matrix is searched again for one-node connections (excluding FROM and TO nodes). In this second pass, node 10 will be deleted and a third pass will delete node 9, thus leaving the desired path from node 1 to node 8. If a pass through the matrix does not produce any deletions, this is the time to stop and that final version of the matrix shows the desired path.

The resistance of each segment is then computed (length x resistivity) and the total resistance between nodes 1 and 8 ( cross section is the sum of series resistors.

Four important corollaries can be derived from that method. I. Detection of Loops.

If the final form of the connection matrix contains any entry with more than two connections, this implies a loop starting at that node. For example, if a loop existed by connecting nodes 2 and 5, the final connection matrix, after reduction, would be as shown in Figs. 5 and 6, where

The same is true if the FROM and TO nodes ended up with more than one connection. It implies a loop starting at that node. The resistance between nodes 1 and 8 can no longer be computed by adding series resistors. The program calls a special routine to compute the equivalent resistance. The description of the method is beyond the scope...