Associative Hierarchiacl Deinterleaver

This invention pertains to the field of deinterleaving a sequence of received signal pulses, and more particularly to identifying radar emitters in an electronic warfare system.

A primary function of electronic warfare (EW) systems is to identify radar signal sources. If the EW system is carried aboard a fighter aircraft, for example, the system will listen for radar signals striking the aircraft. It will then attempt to determine the location and movement of the various sources of the radar signals and perhaps identify the source as well. For every object which emits receivable radio waves, the optimal EW system would give the aircraft pilot a complete description of the object.

With the optimal EW system, the pilot would be warned of missiles, aircraft, ground and airborne surveillance systems and a host of other objects, complete with a report of the missile or aircraft type, its location, its trajectory, and more. Unfortunately, the signals received by the aircraft are not sorted according to source, but superimposed over each other or interleaved. A basic requirement of any EW system is that it be capable of deinterleaving the radar signals. In other words, it must be able to group the signals according to their source.

Present EW systems attempt to do this by matching groups of incoming signals to models of various known radar sources, for example, friendly aircraft or dangerous missiles. The groups of signals which do not match any of the models are either discarded or stored for analysis on the ground in much .larger computing systems. This approach has several disadvantages. First, any group of signals which does not match a known model cannot be identified unless and until the aircraft lands. By that time it is too late for the pilot to take evasive action. Second, there is an inherent time delay because a group of signals must be collected before they may be analyzed. If a radar signal source emits only a small number of pulses very quickly, it may not be identified until it disappears.

With the advent of digital radar, the problems with existing deinterleavers become even more acute. While analog radars could generate only a small range of different signals, a digital radar can greatly vary amplitude, frequency, modulation, and many other parameters of its signals with great speed. As a result, a great many more models are required to effectively deinterleave even signals from known sources. With analog radar, one or two models might suffice to identify a specific type of airplane or missile. Once this signal was received and analyzed, it remained a characteristic for that type of source until substantial changes were made to the source's radar hardware. With digital radar, a much larger range of radar signals must be analyzed in order to identify the radar source. It is highly unlikely that the source will display its whole range of capabilities after only a few encounters.

The present invention overcomes these difficulties because it processes incoming radar signals as they are received and because it does not need to rely on preprogrammed models. While pre-programmed models may be used to help identify some stable sources of radar signals, the present invention generates its own models based on the signals actually received.

The present invention is a method and apparatus for deinterleaving signal pulses. The method includes the steps of (1) grouping signal pulses which have at least one similar parameter, (2) based on the parameter values of the group, predicting a value for a different parameter for other signal pulses which have yet to be associated with the group, (3) associating signal pulses with the group which have both the at least one similar parameter and the predicted parameter in common with the group (4) reporting an indication of the parameters of the group after a threshold number of pulses are associated with the group. The apparatus is comprised of means for accomplishing these steps.

FIG. I is a block diagram of an EW system; and

FIG. 2 is a flow diagram showing the major features of the present invention.

The present invention is an integral part of a radar signal receiving and processing system commonly used in electronic warfare (EW systems). As shown in FIG. 1, the digital EW system typically includes an antenna 2 for receiving radar signals from unknown and known sources in the surrounding environment, an analog to digital converter 4 for converting the analog signal pulses to digital pulse descriptor words, a weighting engine 6 for boosting the signal pulses above the level of background noise, a Fourier transform engine 8 for converting the signals from the time domain to the frequency domain, a deinterleaver 10 for associating related signals and identifying their source, a signal processor 12 for any further processing which may be necessary, a storage device 14 for storing signal information, and a display 16 for reporting the information to an EW system operator, for example, an aircraft pilot. The system may include additional components not shown and not essential to the description here. The present invention may also be used in other types of systems. For example, the converter 4, weighting engine 6 and Fourier transform engine 8 could be placed with an analog, channelizer and detector and the present invention may be used in other signal processing environments. The present invention replaces the deinterleaver presently used in these types of systems.

In an exemplary embodiment, the input to the deinterleaver is a series of pulse descriptor words. As can be seen from FIG. 1, the incoming radar signal pulses are processed in real time through to the deinterleaver. The pulse descriptor words therefore arrive in a steady stream. The information in each word will vary depending on the capabilities of the system used. However, for purposes of the present example, the word will be assumed to describe a single pulse. The components of the word will be assumed to be the frequency of the pulse, the angle of arrival of the pulse, and the time of arrival of the pulse. While the pulse descriptor words arrive at the deinterleaver in the same order in which they arrived at the antenna, it is convenient to have the time of arrival be a part of the pulse descriptor words.

A major purpose of the deinterleaver is to reassociate randomly ordered signal pulses into their proper groups according to their source. To this end, the pulse descriptor words go through three hierarchical levels of matching tests. FIG. 2 shows a flow chart of the basic operation of the invention. In FIG. 2, each pulse descriptor word 22 is first compared to confirmed emitters 24. If there is no match with any of the first through Nth confirmed emitters 26-1 to 26-N, it is compared to hypothetical emitters 30. If there is no match with any of the first through Mth hypothetical emitters, 32-1 to 32-M, then the word is placed in one of the first through Kth clusters, 38-1 to 38-K at the clustering step 36. The emitters are groups of pulses built up from the clusters, so this description shall begin at the level of the cluster. While the cluster level is the end level for the pulse descriptor words, it is the beginning level for the emitters.

For purposes of this discussion, it will be assumed that, initially, the deinterleaver contains no emitters. All signals are therefore accumulated in clusters. In the present example, the pulse descriptor words describe frequency, angle of arrival and time of arrival. Each cluster is a group of words that have similar values for frequency and angle of arrival. Similarity is determined using a tolerance as described below. The clustering step is essentially a matching function.

The first pulse descriptor word received cannot be matched as there is nothing to match it with, so it is placed in a storage register. This creates the first cluster 38-1. The second descriptor word is compared to the first descriptor word. If the frequency and angle for the second word are similar to the first word, then the second word is also placed in the first cluster 38-1. The two words are thus clustered together in a single group. If the parameters of the second word are clearly different, then it is placed in a second cluster 38-2.

The clusterer 36 uses four truth tests to determine whether there is a match for each cluster.

Test 1 (T.sub.1): F.sub.w >F.sub.c -dF

Test 2 (T.sub.2): F.sub.w <F.sub.c +dF

Test 3 (T.sub.3): A.sub.w >A.sub.c -dA

Test 4 (T.sub.4): A.sub.w <A.sub.c +dA

The first test asks whether the frequency of the new word (F.sub.w) is greater than the frequency of the cluster (F.sub.c) less a tolerance level (dF). The tolerance level accounts for measurement errors and variations in the output of the radar signal source. The second test asks whether the frequency of the new word (F.sub.w) is less than the frequency of the cluster (F.sub.c) plus the tolerance (dF). Tests 1 and 2 are therefore satisfied if the frequency of the new word is equal to the frequency of the cluster plus or minus the tolerance. Tests 3 and 4 ask the same question for angle of arrival. A.sub.w is the angle of arrival of the new word. A.sub.c is the angle of arrival for the cluster and dA is the tolerance for the angle of arrival. If all four tests are satisfied for a cluster, then the new word is declared to be similar and is placed in that cluster. If not, the new word is compared to the other clusters. Symbolically, a match is declared if:

So far in the discussion, only two words have been received, therefore, only one matching test has been performed. If there is no match, then the second word begins its own cluster. The third word will be compared to both the first and second cluster if a second cluster exists.

The invention continues to associate words into clusters as they are received. When a cluster acquires a given number of words, for example, two, then a hypothetical emitter 32 is generated by the hypothesis generator 42. The word "emitter" is used here to mean a model of the radar emission of a signal source. The emitter corresponds to the models mentioned in the Background section, but these emitters are generated by the deinterleaver and not pre-programmed as the prior art models are. Each emitter begins as a hypothetical emitter as will be explained below. The emitters are then either confirmed or rejected depending on the signals received by the deinterleaver.

To generate a hypothetical emitter, the hypothesis generator 42 analyzes the words in a particular cluster. When the cluster contains only two words, the exemplary embodiment will consider the difference between the times of arrival of the words and, based on that, predict the time of arrival of the next two words that will match the cluster. For example, if the times of arrival of the two words differ by 10 microseconds, then the hypothesis generator assumes a pulse repetition interval (PRI) of 10 microseconds. 10 microseconds are added to the time of arrival of the second pulse to obtain a first predicted time of arrival, and 10 microseconds are added to the first predicted time of arrival to obtain a second predicted time of arrival. Two predictions are made as a security measure in case the first predicted pulse is not detected for some reason.

The hypothetical emitter therefore is an outline for a group of words with a similar frequency, angle of arrival, and PRI. The outline includes predicted values and tolerances for each parameter. The hypothetical emitter is placed at the second matching level in the three-level hierarchy of FIG. 2 and becomes the first hypothetical emitter 32-1. The emitter is then matched to incoming descriptor words by the hypothetical emitter matcher 30.

The hypothetical emitter matcher 30 uses a series of truth tests just as the clusterer does. The tests for each hypothetical emitter are as follows:

Test 1 (T.sub.1): F.sub.w >F.sub.h -dF

Test 2 (T.sub.2): F.sub.w <F.sub.h +dF

Test 3 (T.sub.3): A.sub.w >A.sub.h -dA

Test 4 (T.sub.4): A.sub.w <A.sub.h +dA

Test 5 (T.sub.5): T.sub.w >PT.sub.1 -dT.sub.1

Test 6 (T.sub.6): T.sub.w <PT.sub.1 +dT.sub.1

Test 7 (T.sub.7): T.sub.w >PT.sub.2 -dT.sub.2

Test 8 (T.sub.8): T.sub.w <PT.sub.2 +dT.sub.2

F.sub.w, A.sub.w and T.sub.w are the frequency, angle of arrival and time of arrival, respectively, of the incoming pulse descriptor word. F.sub.h and A.sub.h are the frequency and angle of arrival, respectively, for the hypothetical emitter. PT.sub.1 and PT.sub.2 are the first and second predicted times of arrival for the incoming pulse descriptor words, respectively. dF, dA, dT.sub.1 and dT.sub.2 are the tolerance levels for the frequency, angle of arrival, first time of arrival and second time of arrival, respectively.

An incoming descriptor word will be associated with the hypothetical emitter if tests 1, 2, 3 and 4 are satisfied, and either tests 5 and 6 or tests 7 and 8 are satisfied. Put another way, a match is declared with the hypothetical if:

When an incoming descriptor word does not match any of the hypothetical emitters, it is passed on to the clusterer 36 at the third level in the matching hierarchy.

When a new word is associated with the hypothetical emitter, the hypothetical must be updated. The frequency and angle of arrival remain the same, but the predicted estimated times of arrival must be adjusted, so that the para-hypothetical emitter can be matched to new incoming words. The new first predicted time of arrival in this example is obtained by adding the PRI, 10 microseconds, for the first hypothetical emitter to the time of arrival of the new word. The second predicted time of arrival is obtained by adding the PRI to the first predicted time of arrival.

Hypothetical emitter may also be refined by techniques well known in the literature.

Each emitter 32-1 to 32-M also has a confirmation counter 44 which counts the number of words associated with the hypothetical emitter. When the counter reaches a threshold number of words, for example, seven or eight, then the hypothetical emitter becomes a confirmed emitter. When confirmed, the counter elevates the emitter to the first level of matching. The first hypothetical emitter to be confirmed becomes the first confirmed emitter 26-1. New incoming pulse descriptor words are matched with confirmed emitters at step 24 before they are matched with hypothetical emitters.

Each confirmed emitter, 26-1 to 26-N, is reported. In the present example, the reporting process starts at the pulse train descriptor word generator 28, which generates a pulse train descriptor word. The word describes the frequency, angle of arrival and PRI of the group of signal pulses that make up a confirmed emitter. The pulse train descriptor word also indicates when the emitter was confirmed and how long it has been received. The pulse train descriptor word is reported to the signal processor 12. From there it may be stored in the storage medium 14 and reported to the EW system operator on the display 16. From the display, the operator learns the angle of arrival, frequency and PRI for the emitter. Using this information, the operator can identify the nature of the source of the radar signal pulses. If the characteristics of the emitter correspond to a known source of radar, then the source can be identified either by the operator or by an automated device. If not, the information can be stored in the storage medium 14 shown in FIG. 1 for later analysis and identification.

Even if the signal source cannot be identified, the characteristics of the source and the amount of time that it is focusing radar signal pulses on the operator's aircraft are of great interest to the operator. Using prior art systems, the operator would not have this information. When the signals did not match a model with some prior art systems, the operator may be warned that unidentified radar signals are being received, but he would know nothing about their characteristics because signals, which do not match a predetermined known model, remain interleaved. Using the present invention, an operator with a good knowledge of radar systems can recognize whether radar sources are threatening or nonthreatening even if he has never seen the particular signal train before.

Returning now to the third matching level 36 where the clusters are formed, the first hypothetical emitter was generated when the first cluster acquired two words. It is likely that the cluster will soon acquire a third word. The third word allows two more hypothetical emitters to be generated. Hypothetical emitters are generated by predicting times of arrival for succeeding pulses based on the times of arrival of the pulses in the cluster. The first hypothetical emitter assumed a PRI equal to the difference between the time of arrival for the first word and the second word. The PRI was added to the second word's time of arrival to obtain a first predicted time of arrival. The second predicted time of arrival was obtained by adding the PRI to the first predicted time of arrival.

Using the third word, two new hypothetical emitters based on the PRIs are generated, the first by comparing the time of arrival of the third and first words and the second by comparing the time of arrival of the third and second words. From these two PRIs, two hypothetical emitters are generated and added to the second matching level 30.

When a fourth word is added to the cluster, three more PRIs are calculated. The first is generated by comparing the fourth and third words, the second by comparing the fourth and second words, and the third by comparing the fourth and first words. This results in three more hypothetical emitters and so on. New hypotheticals are generated in each cluster each time a new word is associated with that cluster. Obviously, the number of hypothetical emitters could grow very quickly. Suppose an airplane were equipped with the present invention, and there were no confirmed or hypothetical emitters in the system. If the airplane was exposed to one radar signal source with constant frequency and angle of arrival, and a PRI of 10 microseconds which is not uncommon, then, after 1 millisecond, assuming that all the pulses fall to the clustering level, the system would have generated 5,000 hypothetical emitters. This volume of emitters would reach huge amounts of memory and processing ability. As a result, several features of the system are designed to limit the number of hypothetical emitters which are generated.

If, in fact, there was only one signal source, then no deinterleaving would be required. The present invention is intended for use in environments with substantially more signal sources, which would mean substantially more hypothetical emitters. Therefore, in order to limit the amount of hardware needed to implement the invention, there are limits on the generation and retention of hypothetical emitters.

First, the matching is hierarchical. Words that are matched with a confirmed emitter are retained at that level and not matched to hypothetical emitters. Words that are matched to hypothetical emitters are retained at that level and not associated with clusters. As a result, a great number of words are prevented from reaching the level of the clusters and cannot contribute to generating hypothetical emitters.

Second, hypothetical emitters are not generated using every single pulse that matches a cluster's parameters. Only a limited number of words are retained in each cluster. When the cluster's capacity is reached, the earliest received word in the cluster is discarded to make room for the latest word. The precise number of words in each cluster will depend on the hardware used to implement the invention. If, for example, each cluster has a ten word capacity, then after the cluster is filled, only nine new hypothetical emitters would be generated for each new word associated with the cluster.

Third, every hypothetical emitter includes a delete checker 34. Each hypothetical emitter processes every new word which is not matched with a confirmed emitter. If the time of arrival for a new word is later than the second predicted time of arrival, for a hypothetical emitter, then the hypothetical has failed and it is deleted. Symbolically, a self-deletion occurs if:

A new hypothetical emitter may then fill the space formerly occupied by the old.

In this exemplary embodiment, the deinterleaver is implemented in rows of parallel processing cells. Confirmed emitter matching is done in parallel in the first row. If matches are declared, the incoming pulse descriptor words are retained at the confirmed emitter level. If no match occurs, the pulse descriptor words are transmitted to the second row, which is the hypothetical emitter level. All hypothetical emitter matching is done in parallel as well. The substantial majority of incoming pulse descriptor words will be matched with confirmed emitters. In the exemplary embodiment, an emitter can be confirmed after only ten pulses are received from a radar signal source. Two pulses are required to generate the hypothetical emitter and eight more are required to confirm the emitter. Since most radars send substantially more than ten pulses at a particular target, most pulses will be associated with confirmed emitters.

If the incoming pulse descriptor words do not match a confirmed emitter but do match a hypothetical emitter, then they are retained at the hypothetical emitter level. This level will absorb the substantial majority of the remaining incoming pulse descriptor words. The small number remaining will correspond to pulses from either brand new or highly erratic sources. These are sent to the third row of parallel processors for association with clusters.

It is very likely that clusters will quickly become inactive. A cluster is begun when a pulse with a unique frequency and angle of arrival are received. This pulse ordinarily corresponds to a radar signal source in the environment which has begun emitting a steady stream of identical radar signals. When the second pulse is received, a hypothetical emitter is generated and placed in a processor at the second row. The hypothetical emitter will retain the third through the tenth pulses from that same source. When the hypothetical is confirmed, it is placed in a processor at the first row where it will retain all pulses received after the tenth, until the signal source stops sending pulses to the antenna, or until it changes the characteristics of its pulses. As a result, the processor at the cluster level acquires no new pulses after the second pulse. Since the number of processors available for collecting clusters is limited, each processor has a self-clearing checker 40. If no new words are added to a cluster within a certain amount of time, the self-clearing checker discards the cluster, clearing the processor for a new cluster. A computer program listing which simulates the exemplary embodiment of the invention described above is attached to this application as Appendix A.

The invention as described above achieves nearly total deinterleaving using a minimum of hardware. The deinterleaving is much more complete and more flexible than with previous designs, because the device does not rely on any pre-programmed models. Any received signals can be grouped on the basis of their pattern of parameters, regardless of whether or not the pattern has been observed before.

The exemplary embodiment uses frequency, angle of arrival and time of arrival as its three parameters for deinterleaving, and it processes incoming pulses in real time. This mode of operation is considered the most useful for present airborne EW systems. However, the present invention is not limited to these parameters, to real-time parallel processing, nor to airborne systems. As radar systems change, different or additional parameters may be more desirable. Clusters may rely on matching three or four, or more, parameters. Or different clusters may be formed to match different sets of parameters. For example, one group of clusters may be used to match frequency and angle of arrival, and another group of clusters may be used to match modulation frequency and amplitude. Still another group of clusters may be used to match three or four, or more, of the measured parameters. All types of clusters may be combined in a single system.

Real-time parallel processing was chosen for speed. However, the invention may also be implemented with serial processing. In addition, the invention is not limited to EW systems. The present invention is useful wherever signals with unknown parameters must be sorted out and grouped together. These signals need not be radar signals but may be any other type of signal. Also, it is not necessary that the EW system be a digital system. The invention applies equally well to analog deinterleaving systems which produce digital pulses. In an analog system, the processing would not be applied to pulse descriptor words, but, for example, analog models of the pulses using rows of filters. In the prior art, the deinterleaver was preprogrammed with models of known emitters. Pulses which matched the emitters were separated out and reported. Preprogrammed confirmed emitters can be used for matching in the confirmed emitter matcher 24. In the parallel processor architecture described above, certain cells can be dedicated to preprogrammed models. These cells would not have a selfdelete checker, but would continuously separate out signals which match the models. Using preprogrammed models in addition to the confirmed emitters frees the deinterleaver from generating emitters for known, stable, radar signal sources, for example control towers, commercial communications transmitters and friendly aircraft.

It will be understood by one skilled in the art that many other modifications and adaptations to the present invention are possible without departing from the spirit and scope of the invention. The applicant, by describing only one embodiment, does not intend to abandon other modifications and adaptations within the spirit and scope of the invention.