Method and system for deinterleaving

• US 6,985,102 B1
• Filed: 07/01/2004
• Issued: 01/10/2006
• Est. Priority Date: 07/01/2004
• Status: Expired due to Fees

• Current Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Original Assignee: Lockheed Martin Corporation (Martin Marietta Corporation)
• Inventors: Horn, William T., Hurt, Steven F.
• Primary Examiner(s): Sotomayor, John B.
• Application Number:
  US10/883,130
• Time in Patent Office: 558 Days
• Field of Search: 342/13, 342/40, 342/90, 342 97- 99, 342/108, 342/109, 342/111, 342/113, 342/115, 342/133, 342/137, 342/139, 342145-147, 342/159, 342/162, 342/189, 342/192, 342/194, 342/195
• US Class Current: 342/13
• CPC Class Codes: G01S 7/021 Auxiliary means for detecting or identifying radar signals or the like, e.g. radar jamming signals

Abstract

A method of deinterleaving parameter descriptor word (PDW) data includes parallel scoring of pulses in an a posteriori search for associating of pulses based on proximity within a multi-parameter problem space. The a posteriori search includes scoring an oldest pulse against all newer pulses, and then scoring a next oldest pulse against all newer pulses. The associating utilizes at least one of a plurality of parallel computation modes, parallel tasks to operate on separate data fields, and multi-threading or multitasking that can implement one of parallel and configuration-overlaid operation, synchronized by events.

Claims

1. A method of deinterleaving a data stream which includes a plurality of pulse words each representative of received pulses from a plurality of emitters comprising pulse data words (PDW'"'"'s) generated from received signals from a plurality of emitters comprising the steps of:

receiving a data stream which includes a plurality of the PDW'"'"'s;

receiving a first PDW, and establishing a first set of candidate information based on parameter information included in the first PDW;

starting a search thread and scoring each additional PDW received within a first time period in an a posteriori search and identifying one or more candidate PDW'"'"'s based on a comparison with the first set of candidate information; and

connecting in one or more pulse trains, the first PDW and identified candidates which meet a predetermined criteria.

2. A method of claim 1 wherein additional search threads are created upon receipt of each of the PDW'"'"'s and evaluation of the PDW'"'"'s is performed in parallel for each of the search threads.

3. A method according to claim 1, wherein the scoring is based on deinterleaving parameters comprising at least one of time of arrival (TOA), angle of arrival (AOA), pulse width (PW), radio frequency (RF), pulse amplitude (PA), and unintentional modulation on pulse (UMOP).

4. A method according to claim 2, wherein the scoring is based on time difference of arrival (TDOA).

5. A method of claim 1 wherein the additional PDW'"'"'s not identified as candidates in any of the parallel search threads, are identified as residue and are further processed in one or more additional stages which employ time periods longer than the first time period.

6. A method according to claim 1, wherein the a posteriori search is composed of a plurality of stages, each stage being for extracting signals within a respective time interval range.

7. A method according to claim 6, wherein the time interval is sized to encompass a pulse repetition interval (PRI) for one or more known emitters.

8. A method according to claim 6, wherein the plurality stages employ time intervals which grow larger in succession.

9. A method according to claim 8, wherein each of the additional stages includes a candidate search portion and a pulse connection portion.

10. A method according to claim 9, wherein the candidate search portion comprises:

searching forward from a received pulse up to a specified time;

a posteriori scoring of parametric and interval matches for the received pulse and all other pulses within the specified time; and

identifying a predetermined number of top candidates based on the scoring.

11. A method according to claim 1, wherein the scoring is performed on a single clock cycle of a reconfigurable computing (RCC) device.

12. A method according to claim 11 wherein the RCC comprises one or more field-programmable gate arrays (FPGA'"'"'s).

13. A method according to claim 9, wherein the pulse connection portion comprises each received pulse attempting to connect with at least one of:

a highest scoring received pulse in the specified time and a second highest scoring received pulse.

14. A method according to claim 13, further comprising, if no connection is made, checking for missed pulses along an unstable interval sequence.

15. A method according to claim 1 further comprising the step of accepting the data stream from a parameter measurement unit via a single-cycle first-in-first-out (FIFO) memory;

and

composing parallel interconnects in a spatial processing engine that reconfigures processing hardware according to a high-level source program.

16. A method according to claim 15, wherein the step of connecting the PDW'"'"'s is based on requirements of an a posteriori candidate search that windows the data from the parameter measurement unit based on temporal parametric information.

17. A method according to claim 16, wherein the candidate search includes searching each window for pulse repetition intervals based on a scoring mechanism.

18. A method according to claim 1, wherein the connecting of PDWs forms trains, the method further comprising connecting a plurality of the trains, from parallel locations, into longer trains that form candidate signals.

19. A method according to claim 1, wherein the scoring comprises determining a parametric score for an incoming pulse against every other pulse within the predetermined time period in order to determine a top candidate for the incoming pulse.

20. A system configured to perform parallel candidate search deinterleaving, comprising:

an input device for receiving an incoming data stream of pulse from a plurality of emitter devices, said input device being further configured to convert the incoming data stream to a word format for each received pulse; and

a processor configured to receive the pulse stream in word the format and to;

simultaneously scoring within a plurality of first a posteriori windows, of a plurality of windows, wherein the scoring includes employing parametric and interval match in a backward search from each oldest received pulse word within the a priori window, the scoring being performed against all other pulses in the window;

identifying at least one candidate pulse within each of the a posteriori windows for connecting with the oldest receive pulse word; and

connecting in a pulse train the oldest pulse word from each of the windows and each of the candidate pulse words which meet a plurality of connection criteria including matching pulse repetition intervals (PRIs).

21. The system of claim 20 wherein the scoring is based on deinterleaving parameters comprising at least one of time of arrival (TOA), angle of arrival (AOA), pulse width (PW), radio frequency (RF), pulse amplitude (PA), and unintentional modulation on pulse (UMOP).

22. The system of claim 21 wherein the scoring is based on time difference of arrival (TDOA).

23. The system of claim 20 wherein the processor is further configured to further process pulse words not connectable in a pulse train as residue in one or more additional stages which employ a priori windows of durations greater than the first a posteriori window.

24. The system of claim 20 wherein required processing power of the processor is configured to scale linearly with data density of the data stream by providing performance that is proportional to the number of pulses processed.

25. The system of claim 24 wherein the processor is configured as at least one reconfigurable computing (RCC) engine.

26. The system of claim 25 wherein the RCC engine includes at least one field-programmable gate arrays (FPGAs) programmable via a high-level language to perform deinterleaving operations both in sequence and in parallel.

27. The system of claim 20 wherein the deinterleaving is performed as part of at least one of:

an Electronic Warfare Support Measures (ESM) and ELectronic INTelligence (ELINT) radar system.

28. The system of claim 20 further including a single-cycle first-in-first-out (FIFO) memory configured to accept the data from a parameter measurement unit.

29. The system of claim 20 wherein the input device includes a parameter encoder configured to convert radar pulses to pulse descriptor words (PDW'"'"'s) which are deinterleaved by the processor.