Search

CN-121997880-A - Multilayer PCB wiring searching algorithm based on millimeter wave image

CN121997880ACN 121997880 ACN121997880 ACN 121997880ACN-121997880-A

Abstract

The invention relates to a multilayer PCB wiring searching algorithm based on millimeter wave images, and provides an analysis obstacle avoidance exploration algorithm model based on millimeter wave images, aiming at the problems that resolution limitation and calculation cost are too high in the existing grid A algorithm based on multilayer PCB wiring and the problem that the grid A algorithm is not suitable for multilayer wiring under a grid-free method. The model is based on heuristic path optimization based on a grid A algorithm, marks obstacles and a routable area through pixel coordinates of millimeter wave images, generates a plurality of groups of obstacle vertex pixel coordinate sets, dynamically monitors local obstacles and performs geometric filtration, and combines multi-pin network routing optimization to avoid sharp corner routing, enhance signal transmission efficiency and reduce the number of through holes. The method for introducing cross-layer projection in multi-layer PCB wiring marks a starting point, a barrier vertex and a terminal point, so that the analysis obstacle avoidance exploration algorithm of millimeter wave images reduces the total wiring length when the PCB is subjected to cross-layer wiring, reduces the number of through holes to reduce the cost of the multi-layer PCB, reduces the complexity of interlayer connection and the delay and electromagnetic interference of additional signals, and is suitable for the design of the multi-layer PCB board diagram of a high-frequency electronic circuit.

Inventors

  • YUAN MINGHUI
  • ZHANG MOHAN

Assignees

  • 上海理工大学

Dates

Publication Date
20260508
Application Date
20260410

Claims (10)

  1. 1. The multilayer PCB wiring searching algorithm based on the millimeter wave image is characterized by comprising the following steps of: Acquiring a millimeter wave element arrangement composite image of a multilayer PCB, and dividing and positioning element barrier boundary point position coordinates and routable region boundary coordinates by utilizing pixel coordinates of the millimeter wave image, wherein the design data comprise routable regions of each layer of the PCB, barrier distribution, routing constraint conditions, pin positions and connection relations, and the routing constraint conditions comprise obtuse rules, line interval threshold values, via hole positions and routable region ranges; Based on the characteristics of the corresponding pixel point coordinates after image processing, the high-frequency signal transmission efficiency of the multilayer PCB wiring is improved and the signal distortion is reduced through a barrier avoidance heuristic algorithm generated by the via hole positions and the barrier vertex positions among the multilayer PCBs.
  2. 2. The algorithm of claim 1, wherein the starting point q and the ending point p of each network to be wired are the same, and the image segmentation pixel coordinate obstacle avoidance heuristic algorithm is adopted to generate the connectable point set T, and the algorithm specifically comprises the following steps: initializing a candidate point set A and a connectable point set T to be empty, and setting a starting point q, an ending point p and a PCB layer to which the starting point q and the ending point p belong; Generating cross-layer connecting points q 'and p' according to the layer attribution relation of the starting point q and the end point p, adding the starting point q into the connectable point set T, and adding the end point p into the candidate point set A if the starting point q and the end point p are positioned on the same layer; If the starting point q and the ending point p are positioned on different layers, taking a projection point of the ending point p on the layer to which the starting point q belongs as an interlayer connecting point p', and adding a candidate point set A; Extracting all barriers in the current wiring area, and adding the vertex of each barrier into the candidate point set A; and judging whether a pre-explored line from the starting point q to the candidate point a intersects with the obstacle or not according to line segment intersection detection for each candidate point a in the candidate point set A, and adding the candidate point a into the connectable point set T if the pre-explored line does not intersect with the obstacle.
  3. 3. The algorithm for searching the multilayer PCB wiring based on the millimeter wave image according to claim 1, wherein the method for planning the optimal wiring path by adopting the obstacle avoidance heuristic path optimization algorithm comprises the following steps: inspiring a cost function: f(neighbor) = g(current) + d(current,neighbor) + v·δ layer + h(neighbor,goal) Wherein g (current) is the actual path cost from the starting point q to the current point, d (current) is the euclidean distance from the current point to the neighbor point, v is the via cost weight, delta layer is the interlayer switching indication function (1 is taken during interlayer switching, or 0 is taken), and h (neighbor, goal) is the heuristic estimated cost from the neighbor point to the end point p; Initializing a priority queue open_set, an actual cost set g_score, a total cost set f_score and a record set came _from, adding a starting point q into the open_set, setting g_score [ start ] =0, and f_score [ start ] =h (start, goal); Circularly extracting a current point with the minimum total cost in the priority queue open_set, and generating an initial wiring path by backtracking a record set came _from if the current point is an end point p, if the current point is already in the search completion set closed_set, skipping, otherwise, adding the current point into the closed_set; Outputting a final wiring path meeting all wiring constraint conditions of the multi-layer PCB, wherein the final wiring path comprises the trend of each layer of wires and via holes of interlayer transition.
  4. 4. The algorithm for searching the multilayer PCB wiring based on the millimeter wave image according to claim 1, wherein the specific implementation of the line segment intersection detection comprises the following steps: For the two line segments to be detected, L 1 (P 1 ,P 2 ) and L 2 (Q 1 ,Q 2 ), pixel coordinates P 1 (x 1 ,y 1 )、P 2 (x 2 ,y 2 ) and Q 1 (x 3 ,y 3 )、Q 2 (x 4 ,y 4 ): The support line equation of line segment L 1 is A 1 x+B 1 y=C 1 , in which A 1 =P 2 .y−P 1 .y,B 1 =P 1 .x−P 2 .x,C 1 =A 1 ×P 1 .x+B 1 ×P 1 .y; The support line equation of line segment L 2 is A 2 x+B 2 y=C 2 , in which A 2 =Q 2 .y−Q 1 .y,B 2 =Q 1 .x−Q 2 .x,C 2 =A 2 ×Q 1 .x+B 2 ×Q 1 .y; Calculating a determinant det=a1×b2-a2×b1, and if det=0, determining that the two line segments are parallel or collinear and do not intersect; If det is not equal to 0, solving the intersection point (x, y) of the two supporting lines, judging whether the intersection point is simultaneously located in the coordinate range of the line segments L1 and L2, if so, judging that the two supporting lines are intersected, and if not, judging that the two supporting lines are not intersected.
  5. 5. The algorithm of claim 4, wherein the coordinate range of the intersection point (x, y) of the supporting lines is: The intersection point x coordinate must lie within the coordinate range of the first line segment x: min(p 1 .x,p 2 .x) ≤ x ≤ max(p 1 .x,p 2 .x) The intersection point y coordinate must lie within the coordinate range of the first line segment y: min(p 1 .y,p 2 .y) ≤ y ≤ max(p 1 .y,p 2 .y) The intersection point x coordinate must lie within the coordinate range of the second line segment x: min(q 1 .x,q 2 .x) ≤ x ≤ max(q 1 .x,q 2 .x) the intersection point y coordinate must lie within the coordinate range of the second line segment y: min(q 1 .y,q 2 .y) ≤ y ≤ max(q 1 .y,q 2 .y)。
  6. 6. The algorithm of claim 1, wherein the area constraint is calculated by the following formula: Let the PCB routable area be rectangular area A, its lower left corner coordinates be (0, 0), width be W, height be H, all routing traces and vias must be completely contained within the physical boundary of the PCB: (x,y) e or (x,y)v ∈ [0,W] × [0,H] wherein, any line segment E E and via V E V, The obstacle avoidance constraint is that O is set as an obstacle set on the PCB, bo represents the area occupied by the obstacle O ε O, and each wire segment E ε E and via V ε V must avoid all such obstacle areas, specifically, the following conditions must be satisfied: (x,y,k) e or (x,y,k) v Bo The line spacing threshold S w−w and the pin-to-wire spacing threshold S w−pin are not less than 1 length unit, and the multi-layer PCB supports bandwidth configurations of 0-2GHz, 0-4GHz or 0-8 GHz.
  7. 7. The multilayer PCB wiring searching algorithm based on the millimeter wave image according to claim 1, wherein the obstacle avoidance heuristic path optimization algorithm further comprises an endpoint layer guiding mechanism, wherein if a layer to which a neighbor point belongs is different from a layer to which an endpoint belongs, a via cost weight v is additionally superimposed in a total cost f (neighbor), and a guiding path approaches to the endpoint layer.
  8. 8. The multi-layer PCB routing search algorithm based on the millimeter wave image of claim 1, wherein in the pixel coordinate segmentation heuristic algorithm of the image, a quadrilateral approximation process is adopted for obstacles without explicit vertices such as circles and ellipses, and vertices approximating the quadrilateral are extracted as candidate point sources.
  9. 9. The millimeter wave image-based multilayer PCB routing search algorithm of claim 1, comprising: The data input module is used for acquiring design data of the multi-layer PCB, wherein the design data comprises a wiring area, barrier distribution, pin positions, connection relations and wiring constraint conditions; A connection point generating module, configured to execute the pixel coordinate segmentation heuristic algorithm of the image according to claim 2, and generate a connectable point set T; the path planning module is used for executing the obstacle avoidance heuristic path optimization algorithm described in claim 2 and planning an initial wiring path based on the connectable point set T; A path optimization module for performing the post-processing optimization of claim 7, including multi-pin network repair and wire shape optimization, outputting a final routing path; And the output module is used for outputting the coordinate data of the final wiring path, the via position and the wiring layer allocation information.
  10. 10. The multilayer PCB wiring searching algorithm based on millimeter wave images according to claim 9, further comprising a parameter configuration module, configured to configure parameters such as a via cost weight v, a line spacing threshold, a pin-to-line spacing threshold, an obtuse rule tolerance, etc., wherein the value range of the via cost weight v is 0-50.

Description

Multilayer PCB wiring searching algorithm based on millimeter wave image Technical Field The invention relates to the field of millimeter wave imaging technology and electronic circuit design, in particular to an automatic wiring method suitable for a multilayer Printed Circuit Board (PCB), and especially relates to the processing of millimeter wave imaging on image segmentation and obstacle avoidance position selection of the multilayer PCB, which is suitable for multilayer PCB geometric wiring scenes under high-density and multi-constraint conditions. Background With the rapid development of millimeter wave imaging technology and electronic technology, the design complexity of integrated circuits is continuously improved, and the PCB is used as a core carrier for component interconnection in an electronic system, so that the wiring quality of the PCB directly determines the circuit function and performance. Multilayer PCBs have become a mainstream choice for high-end electronics due to their higher integration and flexibility of routing, but automated routing techniques for multilayer PCBs face many challenges. The existing PCB automatic wiring method is mainly divided into two types, namely a grid wiring method and a grid-free method. The algorithm A of the grid wiring method relies on a grid with fixed resolution to search paths, when the grid resolution is not matched with the element size and wiring specification, accuracy errors are easy to generate, and when a fine grid is adopted for ensuring high-pass-through rate, calculation cost is increased rapidly, and wiring efficiency is seriously affected. Although the grid-free method gets rid of the constraint of grid resolution and has stronger flexibility, the method is difficult to support interlayer transition optimization of the multilayer PCB and cannot meet the requirement of complex multilayer wiring. In addition, the existing wiring method has the defects that firstly, in grid-free multilayer wiring, the effectiveness of connection points is difficult to guarantee, insufficient solution space is caused by over-sparse, and the method is degraded into a quasi-grid method due to over-dense, secondly, obstacles possibly exist between the connection points, path connectivity is difficult to ensure, thirdly, acute angle bending of a wiring path is easy to occur, signal integrity and reliability are affected, fourthly, connection failure is easy to occur during multi-pin network wiring, and the efficiency of an existing repairing mechanism is low. In summary, there is currently a lack of an obstacle avoidance heuristic algorithm that uses a gridless routing method to solve or partially solve the foregoing problems. Disclosure of Invention The invention aims to overcome the defects of the prior art and provide a multilayer PCB wiring searching algorithm based on millimeter wave images so as to solve or partially solve the fixed grid constraint. The multi-layer PCB wiring is carried out in a continuous space, so that the contradiction between precision and efficiency caused by the resolution of a grid is avoided, and the problems of high wiring cost, unreliable information transmission and wiring solidification and dead plate exist in the existing wiring model. The aim of the invention can be achieved by the following technical scheme: In one aspect of the present invention, a multi-layer PCB routing search algorithm based on millimeter wave images is provided, comprising the steps of: And acquiring a millimeter wave multilayer PCB element arrangement composite image, positioning obstacle boundary point coordinates and routable region boundary coordinates by using pixel coordinates of the image, wherein [ A xmin, Aymin, Axmax, Ay max ] represents a rectangular region, and [ x, y, k ] represents obstacle boundary point coordinates, wherein x, y represents pixel point coordinates of a two-dimensional plane, and k represents the position of a layer plate. The obstacle distribution information comprises element packaging coordinates, coordinates of a forbidden wiring area, coordinates of via holes and the like, and quadrilateral approximation processing is adopted for obstacles without clear vertexes such as circles, ellipses and the like; based on the obstacle avoidance heuristic algorithm of the PCB millimeter wave image, each network to be wired is provided with a starting point q and an ending point p, and the initialization candidate point set A and the connectable point set T are both empty. The coordinates of a starting point q are (x q,yq,kq) and the coordinates of an end point p are (x p,yp,kp), wherein k q、kp is a PCB layer to which the starting point q and the end point p belong respectively, cross-layer connection points q ' and p ' are generated according to the layer attribution relation of the starting point q and the end point p, q ' is a projection point of the starting point q on other layers, p ' is a projection point of the end point p on