Terry Woods
Member
- Join Date
- Apr 2002
- Posts
- 3,170
http://www.freelearning.com/knots/
An "ideal" circuit routing scheme is one where all circuits can be displayed in a single 2-dimensional image (schematic) without having any circuit line crossing any other circuit line.
You open a control cabinet to work on some device. You find that the wiring to and from that device is in the particular configuration called "rat's nest". The wiring is in a complicated knot-state.
You look at the schematic and see that the wiring shown for the particular device is drawn without any wires crossing any other wires.
Out of shear frustration in trying to follow the real wires, you decide that enough is enough. You have several wires, each with a pair of terminating points. Selecting one wire, you disconnect the wire at one terminal point. You then go to the other terminal point, grab the wire and pull it out of the "rat's nest". The wire is now a single, untangled wire connected at one terminal point. Then, by-passing the nest, you reconnect the unterminated end of the wire back to its' proper termination. The exercise is repeated until all wires have been untangled and properly terminated.
Pop-Quiz... Does the last wire need to be unterminated and re-routed?
As usual... it depends. If the goal is to remove all entanglements (knots) and the last wire is "knotted" unto itself, then the answer is yes. If the last wire is not "knotted" unto itself then the answer is no.
The point of this little story is to illustrate that a simple, "ideal" routing scheme can be made to appear very complicated. At the same time, if a simple, "ideal" routing scheme exists, then an apparently complicated routing can be made simple, "ideal".
Now, if you were to run into the same situation again, on a different type of device, but this time you didn't have a schematic... could you reroute the wires into an "ideal", completely untangled, unknotted routing?
The simple answer is, maybe. Since this is a normal wiring routine, using real, insulated wires, it really doesn't matter if the wires can be routed in an "ideal" manner. Even though any number of wires might cross any number of other wires, there is no contact between the wires because of the insulation.
This means, even though a "rat's nest" is unsightly and a pain to work with, it can be electrically adequate.
Now, imagine having to make those routings using uninsulated wire. This becomes more challenging however, it is not unsurmoutable. Since there is a 3-dimensional space available for routing, these wires can be mounted on insulated standoffs (think bus-bar arrangements).
Now, imagine having to route those uninsulated wires on a 2-dimensional plane; think etches on a single-sided circuit board. This has the potential of becoming very much more complicated. In fact, it might be impossible.
If you look at the schematic for the circuit board and see that each etch is drawn without crossing another etch then that circuit board schematic has been designed with the "ideal" routing scheme. In this case, it is theoretically possible to layout all etches in that 2-dimensional plane. I say "theoretically" because there is always that damned density issue. If you've ever made your own circuit board, by hand, then you know how hard it can be to run an 8-bit or 16-bit bus in a small area. The typical scheme involves "fanning out" etches from the chip-mount location (whether the chip is directly-mounted or carrier-mounted). If there is room available, "Fanning out" etches allows etches to be made more substantial and more separated. This can work only if the "real-estate" is available.
Historically, board-densities have been ever increasing. And board schematics are increasingly more complicated. These days, it is far less common to find a schematic that can be layed out in the "ideal" fashion. It is more common to find circuit paths that can not be untangled, unknotted. This does not mean that the circuit board can not be realized. What it does mean, however, is that the tangled or knotted nature of the circuit needs to be understood.
Each circuit is analyzed as a knot. The first effort is to determine whether a particular circuit is a knot or an "unknot". An "unknot" is a knot in the "ideal" form; no lines crossing, as in a circle. After separating all of the circuits into knots and unknots, the process then goes onto to determine the minimum "stick-knot number" of the remaining "knot" circuits. The "stick-knot number" represents the smallest number of straight lines that can be used to reproduce the knot. No "nontrivial" knot can be formed by less than 6 sticks. In other words, if you join 5 sticks at the ends, you can never form a knot other than the "unknot".
Once all of the circuits have been classified and quantified, they are then subjected to a "best-fit" algorithm. Now, the "best-fit" algorithm can be controlled as to how much effort it will put into finding the "best-fit". That is, at one extreme, the algoritm can be told to find the first-fit, without regard to the number of layers required to support that fit. At the other extreme, the algorithm can be told to find the best-fit with the least number of layers.
Now, in the course of looking for the best-fit with the least number of layers, the algorithm might need to raise the "stick-not number" of a particular knot to make it work. In the end, the largest "stick-knot number" is used to determine the minimum number of layers required to support the particular fit.
The algorithm might be subjected to other constraints as well. For example, all "Clocking Lines" must be on the same layer; or all "Data Lines" must be on the same layer".
It is a "given" that the more constraints there are, the longer it will take to find the "specified best-fit".
If indeed a COMPLETE "best-fit" can be found under the given constraints, the routing software can provide a schematic based on layers where the circuits on each layer will be in the "ideal" form.
In some cases, under the given constraints, a COMPLETE "best-fit" can not be found. In those cases, it might be necessary to complete the ciruit board by installing insulated jumpers or multi-conductor ribbons between particular points. That would fall under the category of, "You can't get there from here... but, if you go from here over to that other place first, then you can get there".
An "ideal" circuit routing scheme is one where all circuits can be displayed in a single 2-dimensional image (schematic) without having any circuit line crossing any other circuit line.
You open a control cabinet to work on some device. You find that the wiring to and from that device is in the particular configuration called "rat's nest". The wiring is in a complicated knot-state.
You look at the schematic and see that the wiring shown for the particular device is drawn without any wires crossing any other wires.
Out of shear frustration in trying to follow the real wires, you decide that enough is enough. You have several wires, each with a pair of terminating points. Selecting one wire, you disconnect the wire at one terminal point. You then go to the other terminal point, grab the wire and pull it out of the "rat's nest". The wire is now a single, untangled wire connected at one terminal point. Then, by-passing the nest, you reconnect the unterminated end of the wire back to its' proper termination. The exercise is repeated until all wires have been untangled and properly terminated.
Pop-Quiz... Does the last wire need to be unterminated and re-routed?
As usual... it depends. If the goal is to remove all entanglements (knots) and the last wire is "knotted" unto itself, then the answer is yes. If the last wire is not "knotted" unto itself then the answer is no.
The point of this little story is to illustrate that a simple, "ideal" routing scheme can be made to appear very complicated. At the same time, if a simple, "ideal" routing scheme exists, then an apparently complicated routing can be made simple, "ideal".
Now, if you were to run into the same situation again, on a different type of device, but this time you didn't have a schematic... could you reroute the wires into an "ideal", completely untangled, unknotted routing?
The simple answer is, maybe. Since this is a normal wiring routine, using real, insulated wires, it really doesn't matter if the wires can be routed in an "ideal" manner. Even though any number of wires might cross any number of other wires, there is no contact between the wires because of the insulation.
This means, even though a "rat's nest" is unsightly and a pain to work with, it can be electrically adequate.
Now, imagine having to make those routings using uninsulated wire. This becomes more challenging however, it is not unsurmoutable. Since there is a 3-dimensional space available for routing, these wires can be mounted on insulated standoffs (think bus-bar arrangements).
Now, imagine having to route those uninsulated wires on a 2-dimensional plane; think etches on a single-sided circuit board. This has the potential of becoming very much more complicated. In fact, it might be impossible.
If you look at the schematic for the circuit board and see that each etch is drawn without crossing another etch then that circuit board schematic has been designed with the "ideal" routing scheme. In this case, it is theoretically possible to layout all etches in that 2-dimensional plane. I say "theoretically" because there is always that damned density issue. If you've ever made your own circuit board, by hand, then you know how hard it can be to run an 8-bit or 16-bit bus in a small area. The typical scheme involves "fanning out" etches from the chip-mount location (whether the chip is directly-mounted or carrier-mounted). If there is room available, "Fanning out" etches allows etches to be made more substantial and more separated. This can work only if the "real-estate" is available.
Historically, board-densities have been ever increasing. And board schematics are increasingly more complicated. These days, it is far less common to find a schematic that can be layed out in the "ideal" fashion. It is more common to find circuit paths that can not be untangled, unknotted. This does not mean that the circuit board can not be realized. What it does mean, however, is that the tangled or knotted nature of the circuit needs to be understood.
Each circuit is analyzed as a knot. The first effort is to determine whether a particular circuit is a knot or an "unknot". An "unknot" is a knot in the "ideal" form; no lines crossing, as in a circle. After separating all of the circuits into knots and unknots, the process then goes onto to determine the minimum "stick-knot number" of the remaining "knot" circuits. The "stick-knot number" represents the smallest number of straight lines that can be used to reproduce the knot. No "nontrivial" knot can be formed by less than 6 sticks. In other words, if you join 5 sticks at the ends, you can never form a knot other than the "unknot".
Once all of the circuits have been classified and quantified, they are then subjected to a "best-fit" algorithm. Now, the "best-fit" algorithm can be controlled as to how much effort it will put into finding the "best-fit". That is, at one extreme, the algoritm can be told to find the first-fit, without regard to the number of layers required to support that fit. At the other extreme, the algorithm can be told to find the best-fit with the least number of layers.
Now, in the course of looking for the best-fit with the least number of layers, the algorithm might need to raise the "stick-not number" of a particular knot to make it work. In the end, the largest "stick-knot number" is used to determine the minimum number of layers required to support the particular fit.
The algorithm might be subjected to other constraints as well. For example, all "Clocking Lines" must be on the same layer; or all "Data Lines" must be on the same layer".
It is a "given" that the more constraints there are, the longer it will take to find the "specified best-fit".
If indeed a COMPLETE "best-fit" can be found under the given constraints, the routing software can provide a schematic based on layers where the circuits on each layer will be in the "ideal" form.
In some cases, under the given constraints, a COMPLETE "best-fit" can not be found. In those cases, it might be necessary to complete the ciruit board by installing insulated jumpers or multi-conductor ribbons between particular points. That would fall under the category of, "You can't get there from here... but, if you go from here over to that other place first, then you can get there".
