Optimal Differential Routing based on Finite State Machine Theory

Noise margins in high speed digital systems continue to erode. Full differential signal routing provides a mechanism for deferring these effects. This paper proposes a three stage routing process for solving the adjacent placement routing problem of differential signal pairs, and proves that it is optimal. The process views differential pairs as logical nets; routes the logical nets; then bifurcates the result to achieve a physical realization. Finite state machine theory provides the critical theoretical underpinning and formal proof of correctness necessary for linear time bifurcation. Regular expressions map the theoretical solution to an appropriate implementation strategy that employs feature vectors for net recognition.