Mail Archives: geda-user/2012/12/11/17:48:22
On Tue, 2012-12-11 at 19:59 +0100, gedau AT igor2 DOT repo DOT hu wrote:
>
>
> On Tue, 11 Dec 2012, gedau AT igor2 DOT repo DOT hu wrote:
>
> > I can ask a friend today who is good in graph theory.
>
> Today we sat together and I demonstrated the problem in PCB and described
> the details. After modelling the problem (graphs) he evaluated both
> solutions (propagation nets and finding cutting edges).
>
> After decomposing the problem, he concluded that finding the cutting
> edges may be an NP problem (in case it is important to minimize the
> number of cuts) and would be impossible to solve on a large board with a
> complicated situation (multiple traces causing shorts).
Yes - had a fear it might be complex.
That doesn't mean it is intractable though,.. board auto-routing is a NP
complete problem, but we still do a reasonable job.
> The propagation idea (parallel propagation of nets from all pins
> finding the first collision) would work. We've spent some time trying to
> construnct more examples to see how it'd perform. We think it'd
> not find the "real cause" of the short, but something closer to it than
> the current short highlight does.
>
> There were some alternative ideas, mostly improvements of the propagation
> idea; instead of finding a single object to blame, it may highlight a
> longer set of lines in a way that it is very likely to contain the part
> the user is interested in, but this needs some more thinking.
It is probably impossible to identify a single (or list of) object(s)
which is/are to blame in any general case we encounter. There might be
multiple solutions to resolve the short. We just need to try to provide
helpful information to the user so she may resolve the issue.
I'm trying to think of the class of mistakes I make when causing
shorts..
1. Dragged random object out of place (or moved instead of
rubber-banded).
2. Applied thermal to wrong layer
3. Had inappropriately tagged / named mechanical layer short across some
pins or vias.
4. Routed tracks after (1, 2 or 3), compounding the issue with more
cross-connected geometry. This will probably be in the form of wiring
some pins / pads to the wrong track, or to adjacent pins on the shorted
net. It might (occasionally) be due to adding more thermals to the wrong
layer.
Question...
Should we be approaching this as a connectivity extraction, followed by
net-list compare? We could probably retain information about the
branching structure of the extracted wiring from the board to aid
finding suitable points to describe the differences ("shorts").
It might be interesting / useful to be able to perform a generic
net-list comparison. Our "warn" annotation on PCB could then be a form
of (back-?)annotation from the netlist comparison process.
Speaking wildly off-topic, perhaps back-annotating schematic changes to
reflect the as-drawn PCB geometry is a valid thing to wish for!
Regards,
--
Peter Clifton <peter DOT clifton AT clifton-electronics DOT co DOT uk>
Clifton Electronics
- Raw text -