A probabilistic model for the analysis of the routing process for circuits

✍ Scribed by P. Agrawal; M. A. Breuer

• Publisher: John Wiley and Sons
• Year: 1980
• Tongue: English
• Weight: 784 KB
• Volume: 10
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.3230100203

✦ Synopsis

Abstract

A probabilistic model is developed for studying the problem of routing printed circuits. The model, which uses the density of blockages on the carrier as a parameter, is based on the path‐searching mechanism of Lee's algorithm. Lee's algorithm is used in our analysis because it belongs to a class of pathfinding procedures which guarantee finding a path between two given points if one exists. It is shown that the routing probability, RM(d), is bounded above by PM(d), where PM(d) is the probability of existence of an arbitrary path of ideal Manhattan distance d from a given source point. Analytical computation shows that PM(d) is practically one until a density of about 35%. After this it sharply reduces, reaching a negligible value at a density of 43% for all but very small values of d. Some experiments related to the verification of the model are described. These experimental results show good agreement with the theoretically derived probabilities.