Abstract:
The problem of operationally analyzing spread spectrum frequency-hopping transmissions has been known since the invention of frequency-hopping radios. A frequency-hopping radio transmits a communication using small signal segments of data making up the transmission in accordance to a set of predetermined parameters. In this type of transmission each small segment of data is transmitted at a different frequency, one after another, until the transmission is completed. In some cases, it may be desirable to analyze these radio transmissions and to be able to determine radio spectrum usage and provide a mean to report on interference in frequency bands where multiple types of transmissions are possible. A novel method of isolating multiple transmission signals that are transmitted using frequency-hopping and apparatus is thus proposed which receives at least a transmission and performs operations within frequency bands of the received transmission in order to monitor and characterize signal energy therein.

Description:
This application claims priority from Provisional Application No. 60/325,185 filed Sep. 28, 2001. 

   FIELD OF THE INVENTION 
   The field of the invention relates generally to wireless communications and more specifically to a method of blind signal extraction from wireless signals transmitted using spread spectrum frequency hopping. 
   BACKGROUND OF THE INVENTION 
   The problem of operationally monitoring frequency-hopping transmissions has been known since the invention of frequency-hopping radios. A frequency-hopping radio transmits communication data in small signal segments of data, with each typically being at a different frequency to the one preceding and following it. The order and selection of frequencies used within a transmission is selected in accordance with a set of predetermined parameters. Given a same set of parameters as a transmitter, a frequency-hopping receiver, hops frequencies in a near identical fashion to the frequency-hopping transmitter and is thus able to ensure complete and proper reception of the communication data. Thus, by using a predetermined set of parameters for both transmitter and receiver, communication is possible between two radios. This is a very efficient way to reduce signal interference in radio bands where channel assignment is not regulated or where different signal types can be encountered, as in the Industrial, Scientific and Medical (ISM) radio frequency band. 
   Prior Art receiving radios, used for blind analysis of communication data transmitted using frequency hopping, absent the necessary predetermined set of parameters, hop their receiver frequencies in a different order than the transmitting radio and as such, even if they receive a segment of the transmission, are not capable of reconstructing the complete communication data. Thus, spread spectrum frequency hopping, is a challenge for spectrum monitoring as it prevents a clear representation of time-coherent signal activities, especially if more than one user is present at the same time instant. 
   Recently, a few approaches that make use of filter banks for estimating some of the critical predetermined set of parameters associated with frequency-hopping transmitters have been proposed. These techniques rely on filter banks and use a time-frequency plane to detect a single signal and then estimate several of its parameters. While they provide some basic concepts for signal extraction for obtaining a portion of transmitted communication data from a single source, they either assume knowledge of key predetermined parameters or assume the presence of only one transmitted signal. Unfortunately, this is unrealistic in an operational environment since typically none of the parameters are known and because many signals are typically transmitted simultaneously in a same local area. 
   A need therefore exists for a spectrum monitoring and surveillance system for realistic signal environment in spectrum bands in usage today. It is therefore an object of the invention to provide a spectrum monitoring system for monitoring portions of a communication from a frequency hopping radio transmitter that overcomes limitations in the prior art for wireless communication applications. 
   SUMMARY OF THE INVENTION 
   In accordance with the invention there is provided a method of isolating transmission signals that are transmitted using spread spectrum frequency-hopping comprising the steps of: receiving RF energy within a frequency band and providing a received signal in dependence thereon; digitizing the receive signal to form a digital signal; transforming the digital signal to provide transformed data within one of a time-frequency domain and a time-scale domain using a known transform; locating regions within the one of a time-frequency domain and a time-scale domain wherein the transformed data is indicative of energy other than noise being present; analyzing the transformed data within the located region to determine first signal parameters thereof; and, de-interleaving the frequency-hopping signals in dependence upon the located regions and the determined first signal parameters thereof. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     An embodiment of the invention will now be described with reference to the figures in which: 
       FIG. 1  illustrates a system used to receive, sample and buffer multiple frequency-hopped signals; 
       FIG. 2  is a schematic block diagram of a DFT filter bank with M frequency bins and N observations of the each frequency bin; 
       FIG. 3   a  illustrates a block diagram indicative of operations performed in order to extract data from signals found in the bins; 
       FIG. 3   b  illustrates steps performed in the signal detection block outlined in  FIG. 3   a;    
       FIG. 4  is a computer generated spectrogram of a plurality of signal segments located within a plurality of frequency bands for multiple frequency hopped transmitters; 
       FIG. 5  is a computer generated spectrogram as shown in  FIG. 4 , having a constant probability of false alarm threshold of 10 −3 ; 
       FIG. 6  is a computer generated spectrogram as shown in  FIG. 4  after filtering of signals contained within the frequency bands; and, 
       FIG. 7  is a signal table for the spectrogram of  FIG. 4 . 
   

   DETAILED DESCRIPTION OF THE INVENTION 
   Signal Acquisition 
   In accordance with an embodiment of the invention shown in  FIG. 1 , is a system used to receive, sample and buffer multiple frequency-hopped signals contained within a number of different transmissions, with each frequency-hopped signal relating to a same transmission having a plurality of signal segments with each signal segment having RF energy within a different frequency band. Prior to extracting of signal segments from the multiple frequency-hopped signals, a wideband signal is first received by a receiver  101  as part of a signal acquisition system  100  that includes one or more controllable phase-locked tuners  102   a  through  102   n  to tune to within different frequency bands of the frequency-hopped signals, one or more synchronizer A/Ds  103   a  through  103   n  are used for digitizing analogue signals within the different frequency bands, with memory  104   a  through  104   n  used for buffering digital data representative of the sampled signals, and a real-time or quasi real-time frequency digital signal processing device. Optionally, a non-volatile storage medium can be included to record large amounts of data for post processing in applications with different requirements. 
     FIG. 2  illustrates a block diagram indicative of operations performed in order to extract hopping signals from the acquired wideband signal in a frequency band. A buffer memory  201  is used to store the received multiple frequency-hopped signal vectors r n  from the receiver and digitizer pair(s), within each of a plurality of frequency bands, Filters  310  within the DFT filter bank, as shown in  FIG. 3   a , filter  202  the signals within each frequency band using an FFT algorithm to perform noise floor estimation  203  and hopping signal segment detection  204 . Afterwards, a hop chaining process is performed  205  followed by hop signal extraction  206  to form a de-interleaved and extracted hop signal. A hop signal post processing block  207  receives this extracted hop signal. Within this block  207 , signal parameter estimation is performed  208 , as well as signal modulation recognition  209 , and demodulating  210 , on each of the signals located within the frequency band.  FIG. 3   b  illustrates the steps of bin thresholding, median filtering in the time-frequency dimension and signal delimitation that are performed in the signal detection block  204 , shown in  FIG. 2 . 
   TRANSFORMING THE ACQUIRED SIGNAL 
   A first filter bank applicable is the DFT filter bank shown in  FIG. 3   a . The DFT filter has M′ frequency bands. A bin is typically a located region having a predetermined frequency band, with a number of bins being located within a broadband frequency range of the receiver. The four main functions of the DFT filter bank are windowing with a symmetric function  310 . Discrete Fourier Transfrom (DFT)  311 , a frequency bin complex sample magnitude squared  312 , and a frequency swapping operation to have a frequency range from −αF s /2 to αF s /2 with 0&lt;α&lt;1 the efficiency factor of the digitizaton process, and F s  the sampling frequency, thus M=M′α. 
   The samples of the received signal and located within the frequency band are denoted by r, with i=0, 1, 2, . . . , . They are grouped in vectors of length M′ to form a series of vectors r n , n=0, 1, 2, . . . , N defined as 
   
     
       
         
           
             
               
                 
                   
                     
                       
                         r 
                         n 
                       
                       = 
                       
                         
                           [ 
                           
                             
                               
                                 
                                   
                                     r 
                                     
                                       nM 
                                       ′ 
                                     
                                   
                                   ⁢ 
                                   
                                     + 
                                     
                                       
                                         M 
                                         ′ 
                                       
                                       - 
                                       1 
                                     
                                   
                                 
                               
                             
                             
                               
                                 ⋮ 
                               
                             
                             
                               
                                 
                                   r 
                                   
                                     
                                       nM 
                                       ′ 
                                     
                                     + 
                                     1 
                                   
                                 
                               
                             
                             
                               
                                 
                                   r 
                                   
                                     nM 
                                     ′ 
                                   
                                 
                               
                             
                           
                           ] 
                         
                         . 
                       
                     
                   
                   
                     
                       ( 
                       1 
                       ) 
                     
                   
                 
               
             
             
               
                   
               
             
           
         
       
     
   
   The sampled received signals relating to frequencies located within the frequency band are therefore contiguous and non-overlapping. Received signal portions within the frequency band are element-by-element multiplied by the window samples w k , with k=0, 1, . . . , M′−1, to create a vector x n . The windowing operation is described by
 
x n =Wr n ,  (2)
 
where the square matrix W is a diagonal matrix with element w k  in the k-th diagonal position. The window samples are assumed to be symmetric such that w k =w MK−1−k . Of course, for windows constrained to an odd number of taps, the symmetry is w k =w MK−2−k . Having a last tap set to zero, the vector x n  is then linearly and efficiently transformed by an inverse DFT to produce another vector named y n . This operation transforms the digital signal within a frequency band to provide a transformed signal within a frequency band that is either in the time-frequency domain or the time-scale using a known transform. The operation is formulated as:
 
y n Fx n =FWr n ,  (3)
 
where F is a square matrix with the k-th row f k  given by the k-th DFT basis, i.e.,
 
 f   k =exp[ j 2π ki /( M′ )]/√{square root over (M′)}
 
with i, k=0, 1, . . . , M′−1. Of course, FF H =I, where (•) H  denotes a Hermitien transpose and I is the identity matrix. The transformed signal within a frequency band, windowing, and the IDFT are efficiently used in implementing of a block filter bank. The vector y n  is finally used to derive an estimate of the m-th bin output power by using a squaring operation  212   a  to  212   n , on elements of y n , for m=0, 1, . . . , M′−1, equation (4) results, where:
 
z n   m =|y n   m | 2 ,  (4)
 
y n   m  the N elements of y n  associated with the m-th bin at time n. The final operation is to perform the typical reordering operation to have frequency going from the negative values to the positive values.
 
   The filter prototype is limited to be a linear phase filter. Therefore, only linear phase finite impulse response (FIR) filters are of concern in the present embodiment. Other filter bank structures are also possible, like the weighted overlap-add structure as is found in the two following publications: R. E. Crochiere, and L. R. Rabiner, Multirate Digital Signal Processing, Prentice-Hall, Signal Processing Series, pp. 313–326, 1983, and C. C. Gumas, “Window-presum FFT achieves high-dynamic range, resolution,” Personal Engineering &amp; Instrumentation News, pp. 58–65, July 1997, incorporated herein by reference. The polyphase DFT filter bank is also an implementation that is well suited. Details of the realization can be found in: R. E. Crochiere, and L. R. Rabiner, Multirate Digital Signal Processing. However, these latter structures do not add any general fundamental advantages to the filter bank presented herein, except for the addition of non-integer decimation for the cases where the sampling rate is not an integer multiple of the data rate for a channel within the signal within a frequency band. Each frequency band of course having a number of channels contained therein. 
   The aforementioned is applicable when the positions in frequency of the channels within a frequency band are known. In the context of spectrum monitoring, this is often not the case. Therefore, the position of a hop signal within a frequency band is preferably estimated in frequency. 
   Also, the bandwidth of the hop signal can be unknown. The parameters F s , and M′, are chosen such that several bins in the frequency or time scale domain are likely used by each hop signal. 
   The raw output of the filter bank, prior to signals detection  204 , over the observation period NMT s /α is shown in a computer generated spectrogram shown in  FIG. 4 .  FIG. 4  illustrates a computer spectrogram for a group of frequency hopped signals with 102.4 ms of data having a frequency resolution (frequency bin width) of ˜5 kHz. A vertical axis of the spectrogram is in the time domain with 10.24 ms/division, with the division dependent upon a sampling frequency of the A/D converters. Along the horizontal axis frequency is shown, where in this case there are 0.448 MHz/division. 
   LOCATING SIGNALS WITHIN THE TRANSFORMED DOMAIN 
   From such a spectrogram, it is possible to estimate the noise floor level  203  within each frequency band using a technique disclosed in U.S. patent application Ser. No. 09/503,834, incorporated herein by reference. The noise floor estimator makes use of all frequency bands available or a subset of them. Once the noise floor level is estimated, assuming white Gaussian noise, a threshold is calculated within the signal detection block  204  that results in constant indication of a false alarm on a bin by bin basis. This process locates regions, within the time-frequency domain or time-scale domain, that are other than noise from within the transformed signal. 
   After applying a threshold at the level calculated, the computer generated spectrogram shown in  FIG. 4  is now reduced to a two-level computer generated image in the time-frequency domain, as shown in  FIG. 5 .  FIG. 5  presents the computer generated results of the thresholded spectrogram of  FIG. 4 . The figure clearly shows the presence of signal segments  501  within the bins, as well as the presence of impulsive noise  503  within some time segment. To eliminate this unwanted impulsive noise as well as reducing the number of bin false alarms, a one-dimensional median filter in the time domain at fixed frequencies) or a two-dimensional median filter is performed on the thresholded spectrogram within the step of signal detection  204 . An example result is displayed in computer generated  FIG. 6  for the detected signals within the frequency bands shown in  FIG. 5 . The filtering operation results in a figure where the signal segments located within the frequency band have been marginally affected while other unwanted signals, such as impulsive noise, have been largely eliminated from within each of the frequency bands. The result of the filtering operation is now fed to a signal segments delimitation stage that deliminates each signal segment in time and frequency. As a result, short duration signals such as signal segments, as well as continuous signals contained within the frequency band are now advantageously characterized. 
   The process of deliminating the signal segments from the transformed signal within a frequency band is described herein below and is performed within the signal detection processing block  204 . Other than the data received itself from the receiver, two other parameters are used by the algorithm: the minimum bandwidth of the detected signal segment of interest and the minimum duration of the signal segment of interest. These two parameters are preferably used to reduce the number of false signal extractions as well as to provide estimation of the time and frequency resolution required in the FFT filter bank  202 . The general idea of the signal extraction function is to find rectangular clusters in the time-frequency plane. Cluster analysis is known to those of skill in the art, an example of which is disclosed in J. C. Bezdek, S. K. Pal, Fuzzy Models for Pattern Recognition Methods That Search for Structures in Data, IEEE Press, New York, 1992, incorporated herein by reference. 
   An exemplary signal segment delimination process starts with an OR operation on consecutive binary frequency frames, within the frequency band, followed by a counter to track the time length of each group of 1&#39;s produced by the OR operation. Each group of 1&#39;s is identified by looking at transition in the frequency dimension (output of the OR process) from 0 to 1 for the group start and transition from 1 to 0 for the group end. Groups of 1&#39;s of course merge over time but cannot split. The width of the group of 1&#39;s is an indication of bandwidth for a signal segment. The duration of a group is estimated by a counter that records the length, in number, of frequency frames of the group. Several strategies can be included to deal with signal impairments during the delimitation of a signal. A group is terminated when the counter fails to increment for a new frequency frame and when no signal segment appears to be present in the near future. The terminated group is then compared to the minimum signal segment bandwidth and signal segment duration to ensure the validity of the signal segment. If one of the two criteria is not satisfied, the extracted signal segment is rejected and the memory associated with it, the group of 1&#39;s and the counter are reset to zero. If both criteria are satisfied, then the signal segment is extracted by recording the frame start and end, and the frequency start and end. This results in a rectangle in the time-frequency plane, as shown in  FIG. 6 , represented by the vertical lines, which represent each signal segment. The signal segment detection process is then completed by providing estimates of various parameters for each segment, where the parameters include at least a hop start time, hop duration, and segment power, but can also include bandwidth, signal to noise ratio, and carrier frequency. These parameters are stored in a signal segment table. 
   ANALYSIS OF DETECTED SIGNAL SEGMENTS 
   Once the table of signal segments has been generated by the time-frequency signal detection stage, the application associates appropriate signal segments to a same transmission. This is commonly known as hop de-interleaving. At this point, the hop de-interleaving is performed on a frequency-hopped signal acquisition basis with the time and frequency constraints associated with the acquisition system. This means that several hops, or signal segments, of a same transmission may unfortunately be missing in the current time-frequency plane. The signal segments at this point are not constrained to any channelization that is often used by frequency-hopping communication systems. 
   The parameters used to perform the operations of de-interleaving and analyzing of the transformed data within the frequency band are first signal parameters in the form of: hop duration, hop-timing, which is a start time of a hop, and occasionally a power level of the hop. A hop of course defined as being an individual signal segment. To those of skill in the art it is known that radio networks are typically asynchronous. Therefore, hops that overlap, are typically not from the same transmission, and hops that are from the same transmission typically form a non-overlapping sequence of signal transmissions. With the above constraint in mind, it is now feasible to test signal segments against each other and quickly come to a conclusion of which hops are associated together. 
   Details of one approach to do so are now presented. The ensemble of delimited signal segments from the signal detection  204  are then passed to the hop chaining process  205 . The process starts with a grouping of the signal segments based on similar segment length and bandwidth if applicable. The grouping results in one or more groups each having a number of signal segments of similar length. The similarity may be measured by a running average of signal segment lengths having a small percentage of length difference. The second step of the process is the estimation of the repetition rate of the groups of similar length. This estimation for each group of signal segments of similar length involves measuring the start time difference between valid signal segments. A valid signal segment is one that does not overlap a reference segment and that is within a duty cycle of typical radios. The repetition rate can be calculated as the inverse of the maximum of the differences. Other way could be to average, to assign a fixed value, or otherwise. Finally, the groups that result in a repetition rate not being estimated are removed from the list of valid groups. This allows De-Interleaving of the Signal Segments as once the signal segments have been associated with a group and the repetition rate of a group has been estimated, the main step of the de-interleaving process is to assign the signal segments an identification number to form a chain or a transmission. Again, the logic consists of using signal segments of the same signal segment group length and check for non-overlapping assuming the repetition rate estimated in the second step. 
   For signal segments that have a timing that can not be resolved or that is too close according to the discrimination criteria, then the signal power difference is used as a discrimination feature. Other possibilities are weighted combination of timing and power difference, angle of arrival if available, or any combination of signal characteristics available. The choice of parameters to resolve ambiguity is application dependant and dictated by the uncertainty related to each sets of parameters. This terminates the hop chaining process and allows for the Hop Chain or Transmission Analysis and Demodulation. After the completion of the hop chaining process, the output is in the form of a list of chained signals, the actual chain of individual signal segments of interest are isolated by down converting the raw time samples to baseband and by decimating to the appropriate sampling rate in the step of hop signal extraction  206 . This sampling rate is indicated by the bandwidth of the signal segment estimated by the width of the rectangle. The baseband decimated signal segments then feed to an automatic modulation recognition module  209 . The automatic modulation recognition module  209 , disclosed in U.S. patent application Ser. No. 09/504,676, incorporated herein by reference, is for modulation identification and for parameter estimation  208 . Parameters that are estimated are for instance: carrier frequency, precise bandwidth, signal to noise ratio, and symbol rate if applicable. 
   The result of the time-frequency signal segment extraction is a table list with all the relevant parameter measurements as shown in  FIG. 7 , where the table is an example of such a list for the time-frequency spectrogram of  FIG. 6 . 
   In some instances, a given signal segment chain could be demodulated to determine signal content. The signal table list provides the necessary information to dedicate a particular demodulator block to the task. 
   The single channel networks or fixed frequency channels are easy to locate since they appear as vertical lines in the spectrogram and they go from the start to the end in the time dimension. The output of the hop chain post-processing stage is a signal report with some valuable parameters for spectrum monitoring analysis. 
   Advantageously, by using the aforementioned system, the at least one received radio transmission is at least partially reconstructed thus allowing for at least partial determination of information transmitted in the transmission by using hop duration, hop-timing, and occasionally a power level of the hop. The process could be repeated for subsequent or continuous data blocks to track over time the transmissions of interest. In these cases, signal information memory between blocks is typically added. This does not change the fundamentals of the invention, simply modifying the initial conditions of the hop chaining process. 
   Numerous other embodiments of the invention may be envisaged without departing from the spirit and scope of the invention.