Mail Archives: geda-user/2012/12/11/00:16:24
On Tue, 11 Dec 2012, Peter Clifton wrote:
> However, in general, coping with the "it started out shorted" case, I
> can imagine producing a graph structure (quite possibly including
> cycles), representing the topology of the connected traces. Nodes would
> represent pins / pads, or junction points between copper tracks and
> polygons. (Although I'm not sure exactly how polygons should work in
> this scheme - perhaps a polygon is node?)
I think you may need to consider any junction as a node, since it is
possible to cause a short by inserting a new trace line connecting two
existing traces, without connecting any pin/pad. But first, we need to
decide what should be highlighted.
I see many different apporaches here:
1. we try to highlight the shortest trace(s) which if the user removes the
short is resolved - this assumes the short is caused by a wrong trace,
which is not very long
2. we try to highlight whole, diverse segments of traces an polys from
which removing one careflly would solve the problem - this assumes
the short is cased by any trace/poly
3. we highligh pads affected - this doesn't assume anything but doesn't
help much either
For examples, let's assume a simple netlist that connects nodes a and b in
the net1 and C and D in net2. The simplex shorted example comes to mind:
(example A)
a---b
|
C---D
Removing the vertical line connecting the wrong pins helps.
Same example where using only pins as nodes of the graph wouldn't work:
(example B)
a-+-b
|
C-+-D
The reason I used plural in the above listing:
(example C)
a---b
| |
C---D
Both vertical traces need to be highlighted, removing only one doesn't
help.
A tricky case is when we share shorts:
(example D)
a b
| |
+---+
| |
C D
Connected everything wrong:
(example E)
a b
| |
C D
> Assuming a two-nets shorted case for simplicity, we could then start
> colouring / labelling the graph in some way. Pins and pads would be
> tagged with their proper net assignment, and this _could_ be allowed to
> propagate down edges representing copper tracks / polygons etc..
This would work well for examples A and C, but I am not sure it woudln't
do something strange with example B if it is assymetrical (can't come up
with an example, tho). In example D it would probably highlight the entier
horizontal line (assuming we started propagation from all four pins in the
same time and did it in parallel), which seems to be a good choice. In
example D it would highlight the two vertical lines, which is fine.
>
> It might be possible to use the structure of the graph to help tease out
> where the problem lies. (It could be, for example, that the graph
> identifies a single edge connecting an otherwise partitioned graph of
> nodes belonging to two different nets).
>
> I don't know enough (any?) graph theory, but perhaps we should
> investigate finding whether there are known algorithms for finding
> optimum partitions of graphs which separate various populations of
> nodes.
I can ask a friend today who is good in graph theory.
> For that "what is shorted to what" case, we might employ some kind of
> voting heuristic which flags that there are (say), 3 mis-connected pins
> on the "should be VCC" pins connected to a piece of copper where 100
> "should be GND" pins are connected... therefore that copper should
> "probably" be GND, so flag the VCC pins as a warning.
This would work as long as the connections are assymetrical. Take example
C: the two vertical lines try to be as much net1 as much net2.
I may misunderstand the original question here, but if we define each
junction as a node, that also means we had to split up a long line into
segments (in example D vertical lines are not single lines for
finding short or even for highlighting shorts). Together with your
parallel propagation idea, it doesn't seem to be necessary to decide what
is shorted to what, only to find a collision during propagation, and that
would do the Right Thing to highlight.
Thus This propagation seems to be a simple and elegant solution on the
graph level, but gets tricky when we translate it to PCB at the end.
For lines, this means we need to be able to split up lines at junctions
for highlight - I think really splitting PCB lines into segments would
cause serious side effects (changing width or clearance would affect only
a shoirt segment that the user did not create).
With polygons it is even trickier: take example C and imagine the lines
drawn are only the outline of a polygon. I see two ways to handle this:
1. take the poly as a single object; in this case the whole poly is
highlighted. The user would remove it and then a set of rats would
remain, which may be a reasonable behaviour. Handle overlapping polys
as single.
2. vote the poly to be one of the nets (dangerous in symmetrical cases)
and detach pins/pads of other networks. This is easy only with
thermals, in other cases this means finding and removing the right
set of traces. Handle overpallying polys as single
3. split up the poly to lines modelling it; i'd use a star topology, or
maybe a ring in the middle:
a b
| |
+---+
| |
+---+
| |
C D
The same propagation algo could be run and it would highlight the two
vertical (virtual) lines in this topology, which may give a hint how we
need to split the poly. However, as long as the example is symmetrical,
it's impossible to decide whether the poly is more net1 or net2. I'd
draw a schematics of the problem with non-copper lines over the
poly and highight the poly. Overlapping polys: take them as single
_before_ drawing the ring map. Drawing the ring map may be tricky if
pins are dispersed.
>
>
> Another possible heuristic would be to have a metric of "how badly
> shorted" the net(s) are, and to evaluate how removing each piece of
> copper in turn affects that metric. Perhaps this could lead to us
> highlighting the errant track or clearance which introduced the short.
This brute force approach will work in all my examples; however, this
still assumes the short is caused by a line/poly. Take a huge board with
ground plane connecting 42 pins legally; place a new pin that should be
connected to VCC in the middle of ground plane by mistake. This method
would remove the whole ground plane, while the user knows moving that
single pin would have been the solution. In this case only the 2nd
approach of the poly resolution above would do something reasonable.
Regards,
Tibor
- Raw text -