Optimal differential routing based on finite state machine theory

Noise margins in high speed digital systems continue to erode. Full differe ntial signal routing provides a mechanism for deferring these effects, This paper proposes a three stage routing process for solving the adjacent plac ement routing problem of differential signal pairs, and proves that it is o ptimal. The process views differential pairs as logical nets; routes the lo gical nets; then bifurcates the result to achieve a physical realization. F inite stale machine theory provides the critical theoretical underpinning a nd formal proof of correctness necessary for linear time bifurcation. Regul ar expressions map the theoretical solution to an appropriate implementatio n strategy that employs feature vectors for net recognition.