Wire network mapping method and apparatus using impulse responses

1. A method of mapping a wire network having branches, comprising:

obtaining a reflectometry response of the wire network;

estimating an estimated network impulse response from the reflectometry response;

initializing a wire network model having hypothesized branches;

iteratively improving the wire network model by

simulating an impulse response of the wire network model, and

adjusting the wire network model to reduce differences between the simulated impulse response and the estimated network impulse response.

2. The method of claim 1 , wherein obtaining a reflectometry response of the wire network comprises:

injecting a reflectometry test signal into the wire network; and

measuring a reflectometry response of the wire network in response to the reflectometry test signal.

3. The method of claim 2 wherein injecting a reflectometry test signal into the wire network comprises injecting a test signal chosen from the set consisting of a fast rise time pulse, a pseudorandom sequence, a spread spectrum signal, a swept-frequency sine wave, and a stepped-frequency sine wave.

4. The method of claim 2 wherein measuring a reflectometry response of the wire network comprises observing reflections of the reflectometry test signal generated by mismatches in the wire network.

5. The method of claim 2 wherein injecting a reflectometry test signal comprises injecting the reflectometry test signal at a first point in the wire network.

6. The method of claim 5 wherein measuring a reflectometry response of the wire network comprises observing a signal response of the wire network at the first point.

7. The method of claim 5 wherein measuring a reflectometry response of the wire network comprises observing a signal response of the wire network at a second point.

8. The method of claim 1 wherein obtaining a reflectometry response comprises observing a time domain response of the wire network to an injected reflectometry test signal.

9. The method of claim 1 wherein estimating an estimated network impulse response from the reflectometry response comprises differentiating the reflectometry response.

10. The method of claim 1 wherein estimating an estimated network impulse response from the reflectometry response comprises deconvolving the reflectometry response.

11. The method of claim 1 , wherein initializing a wire network model comprises defining the wire network model as a plurality of hypothesized network topologies.

12. The method of claim 1 , wherein initializing a wire network model comprises including known portions of the network topology within the wire network model.

13. The method of claim 11 , wherein iteratively improving the wire network model comprises:

creating a plurality of simulated impulse responses for the plurality of hypothesized network topologies;

comparing each of the plurality of simulated impulse responses to the estimated network impulse response; and

discarding those network topologies for which the difference between the simulated impulse response and the network impulse response exceeds a predetermined limit.

14. The method of claim 1 , wherein iteratively improving a network model comprises:

generating a plurality of hypothesized network topologies;

creating a plurality of simulated impulse responses corresponding to the plurality of hypothesized network topologies;

comparing each of the plurality of simulated impulse responses to the estimated network impulse response; and

adjusting the wire network model to correspond to the hypothesized network topology which most closely matches the estimated network impulse response.

15. The method of claim 14 wherein generating a plurality of hypothesized network topologies comprises hypothesizing a network feature at a location corresponding to a first difference between the estimated network impulse response and one the plurality of simulated impulse responses.

16. The method of claim 15 wherein hypothesizing a network feature comprises selecting a network feature from the group consisting of an open circuit, a short circuit, an impedance change, and a branch.

17. The method of claim 15 wherein generating a plurality of hypothesized network topologies comprises modifying at least one of the plurality of hypothesized network topologies to include the network feature.

18. The method of claim 15 wherein generating a plurality of hypothesized network topologies comprises creating new hypothesized network topologies from one of the plurality of hypothesized network topologies, each new hypothesized network topology having a different network feature at a location corresponding to a first difference between the estimated network impulse response and the one of the plurality of hypothesized network topologies.

19. The method of claim 14 wherein creating a plurality of simulated impulse responses comprises:

defining a plurality of equal length segments of the hypothesized network topology;

defining a state vector wherein each element of the state vector corresponds to the signal state on a unique segment of the hypothesized network topology;

forming a state transition matrix wherein each element of the state transition matrix corresponds to the signal flow between a pair of segments of the hypothesized network topology; and

generating the simulated impulse response using the state vector and the state transition matrix.

20. The method of claim 19 wherein generating the simulated impulse response comprises:

initializing the state vector;

repeatedly multiplying the state vector by the state transition matrix; and

extracting the simulated impulse response from the state vector.

21. The method of claim 19 wherein the state vector has two elements for each segment of the hypothesized network topology, wherein one element corresponds to a forward flowing signal on the segment and one element corresponds to a reverse flowing signal on the segment.

22. The method of claim 14 , wherein comparing each of the plurality of simulated impulse responses comprises determining an error between the simulated impulse response and the estimated network impulse response at an earliest point in time where the simulated impulse response differs from the estimated network impulse response.

23. The method of claim 14 , wherein comparing each of the plurality of simulated impulse responses comprises determining an error between the simulated impulse response and estimated network impulse response at a plurality of points in time.

24. The method of claim 23 , wherein determining the error comprises weighting the error at earlier points in time more heavily than the error at later points in time.

25. The method of claim 14 , wherein adjusting the wire network model comprises selecting the one of the plurality of hypothesized network topologies for which the corresponding simulated impulse response most closely matches the estimated network impulse response and discarding the other ones of the plurality of hypothesized network topologies.

26. The method of claim 14 , wherein adjusting the wire network model comprises maintaining a subset of the plurality of hypothesized network topologies for which the corresponding simulated impulse response approximately match the estimated network impulse response and discarding the other ones of the plurality of hypothesized network topologies.

27. A method of mapping a wire network having branches, comprising:

injecting a reflectometry test signal into the wire network;

measuring a reflectometry response of the wire network in response to the reflectometry test signal;

estimating an estimated network impulse response from the reflectometry response;

initializing a wire network model having hypothesized branches based on the estimated network impulse response; and

adjusting the wire network model if differences between an impulse response of the wire network model and the estimated network impulse response are present.

28. The method of claim 27 , wherein initializing a wire network model comprises selecting a candidate network topology having a most closely matching corresponding impulse response, wherein the candidate network topology is selected from a table having a plurality of candidate network topologies and corresponding impulse responses.

29. The method of claim 27 wherein adjusting the wire network model comprises:

simulating an impulse response of the wire network model, and

adjusting the wire network model to reduce differences between the simulated impulse response and the estimated network impulse response.

30. A method of mapping a wire network, comprising:

obtaining a plurality of reflectometry responses of the wire network at a plurality of differing test points within the network;

estimating a plurality of estimated network impulse response from the corresponding plurality of reflectometry responses;

initializing a wire network model having hypothesized branches;

iteratively improving the wire network model by

simulating a plurality of impulse responses of the wire network model corresponding to each test point within the network, and

adjusting the wire network model to reduce differences between the plurality of simulated impulse responses and the estimated network impulse response.

31. The method of claim 30 , wherein obtaining a reflectometry response of the wire network comprises:

injecting a reflectometry test signal into the wire network at a first test point; and

measuring the plurality of reflectometry responses of the wire network in response to the reflectometry test signal at a corresponding plurality of second test points.

32. The method of claim 30 , wherein obtaining a reflectometry response of the wire network comprises:

injecting a reflectometry test signal into the wire network at a plurality of first test points; and

measuring the plurality of reflectometry responses of the wire network in response to the reflectometry test signal at an at least one second test point.

33. The method of claim 30 , wherein adjusting the wire network model comprises:

generating a plurality of hypothesis network models which correspond to an initial portion of at least a first one of the plurality of estimated network impulse responses; and

eliminating hypothesis network models which do not correspond to an initial portion of at least one second one of the plurality estimated network impulse responses different from the first one of the plurality of estimated network impulse responses.

34. A computer program product, the computer program product comprising:

a computer usable medium having computer readable program code embodied therein for mapping a wire network having branches, the computer readable program code comprising:

computer readable program code configured to obtain a reflectometry response of the wire network;

computer readable program code configured to estimate an estimated network impulse response from the reflectometry response;

computer readable program code configured to initialize a wire network model having hypothesized branches; and

computer readable program code configured to iteratively improve the wire network model by simulating an impulse response of the wire network model and adjusting the wire network model to reduce differences between the simulated impulse response and the estimated network impulse response.

35. An apparatus for mapping a wire network having branches, comprising:

a reflectometry instrument configured to obtain a reflectometry response of the wire network;

an impulse response extractor coupled to the reflectometry instrument and configured to estimate an estimated network impulse response from the reflectometry response;

a network simulator configured to simulate the impulse response from a hypothesized network having hypothesized branches to form a simulated impulse response; and

a mapper coupled to the impulse response extractor and coupled to the network simulator and configured to compare the simulated impulse response to the estimated network impulse response and revise the hypothesized network to reduce differences between the simulated impulse response and estimated network impulse response.

36. The apparatus of claim 35 wherein the reflectometry instrument is chosen from the group of reflectometry instruments consisting of a TDR, a FDR, a SWR, a STDR, a SSTDR, a MSR, and a NDR.

37. The apparatus of claim 35 wherein the impulse response extractor comprises a deconvolver.