Signal detector using matched filter for training signal detection

RELATED PATENT APPLICATION

This application claims the benefit of U.S. Provisional Application No. 60/805,276, filed Jun. 20, 2006 and entitled “SIGNAL DETECTOR USING MATCHED FILTER FOR TRAINING SIGNAL DETECTION.”

TECHNICAL FIELD OF THE INVENTION

This invention relates to signal processing, and more particularly to signal detection by using a filter matched to a training sequence of a signal of interest.

BACKGROUND OF THE INVENTION

“Blind” signal detection generally involves receiving and decoding incoming signals when the signal type is not known to the receiver. Many fields of science deal with this type of signal detection, and various techniques have been developed to identify an incoming signal of unknown type, so that its parameters, such as the modulation type and baud rate, can be known and used to decode the signal.

Several examples of signal recognition techniques are parameter-based algorithms, pattern recognition, algorithms that exploit cyclostationarity characteristics, and neural networks. U.S. Pat. No. 6,690,746, entitled “Signal Recognizer for Communications Signals”, assigned to Southwest Research Institute, discusses a system and method for classifying incoming signals as being one of a variety of signal types. Signal parameters are estimated and signals are demodulated in accordance with the estimated parameters.

A subfield of signal recognition includes methods that attempt to decode (or otherwise use) only signals of a desired type. For example, a signal of interest might be a signal that carries a particular training sequence.

BRIEF DESCRIPTION OF THE DRAWINGS

A more complete understanding of the present embodiments and advantages thereof may be acquired by referring to the following description taken in conjunction with the accompanying drawings, in which like reference numbers indicate like features, and wherein:

<figref idrefs="DRAWINGS">FIG. 1</figref> illustrates a method of identifying a signal by identifying its training sequence in accordance with the invention.

<figref idrefs="DRAWINGS">FIG. 2</figref> illustrates the relative degradation caused by various conditions affecting an incoming signal.

<figref idrefs="DRAWINGS">FIG. 3</figref> illustrates a signal detection system in accordance with the invention.

DETAILED DESCRIPTION OF THE INVENTION

For purposes of this description, “signal detection” is the process by which an unknown signal is classified as a signal of interest or not. The method and system described herein are for “blind channel” conditions, in the sense that the receiving end of the system (referred to herein as the “signal detector”) has no knowledge of the transmitted signal's path, its frequency, the type of signal, or the signal parameters.

As explained below, the object of the method and system is to detect whether an incoming signal has a particular training sequence. Because a training sequence is unique to a particular type of signal, if the training sequence is identified, then the signal type and hence its signal parameters are assumed to be known. The message in the signal can then be decoded.

A feature of the invention is that it provides for a computationally efficient search for the training sequence. The method is robust in the presence of unknown carrier frequency offset values and channel distortion.

A “training sequence” is a part of a signal that is a known sequence of transmitted symbols. The training sequence does not contain any “message” information, but rather is used for equalization processing. Specifically, the training sequence enables the receiver to gather information about the channel characteristics. Typically, a particular type of signal has its own unique training sequence. If a signal complies with a standard, the training sequence is part of that standard. For example, for a GSM signal, which arrives in bursts of 126 bits, 26 bits are reserved for a training sequence.

A training sequence is typically associated with a digital signal, but can be used with analog signals. In general, the invention described herein can be used with any signal having a training sequence.

For an incoming signal containing a training sequence, a matched filter provides an optimum detection strategy. In general, in communications systems, “filters” are used to remove or attenuate an undesired portion of signal's spectrum while enhancing desired portions of the signal. Filters may be analog or digital, with the later being used in connection with processing devices to process a signal after it has been sampled and digitized. A “matched filter” is the filter design for a particular signal that maximizes the signal to noise ratio at the output of the filter.

For detecting a training sequence, the matched filter is designed to find a match to the training sequence of the signal of interest. As explained below, the filter is designed as the conjugated training sequence t. The values of the convolution of the matched filter with the input signal can be tested against a suitably chosen threshold to make the detection decision. If the correlation is high, the signal is determined to be a signal of interest.

<figref idrefs="DRAWINGS">FIG. 1</figref> illustrates a method of signal recognition in accordance with the invention. The steps of the method, particularly the processing of Steps <b>11</b>-<b>16</b> can be implemented with conventional processing equipment, programmed in accordance with the method described herein.

Step <b>10</b> is receiving an incoming signal of an unknown type. Step <b>11</b> is sampling the signal at a sampling frequency, F_s, which is the same as the sample frequency assumed for the filter calculations described below. It the signal is already digital, it is resampled at F_s.

Noteably, the signal is not mixed with different frequencies prior to application of the matched filter processing in Step <b>12</b>. As explained below, a feature of the invention is the re-ordering of processing steps for computation efficiency. The “mixing” is performed within the filter processing rather than before the filter processing.

Step <b>12</b> is processing the data through a filter that is matched to a known training signal, and is described in further detail below. Step <b>14</b> is determining whether the signal training signal is matched to the filter. If so, the signal is assumed to be a signal of interest, in Step <b>16</b>, the message portion of the signal may be decoded using the training sequence.

The use of a matched filter for detecting a training sequence may be described in mathematical terms. Specifically, in matrix-vector notation, matched filtering can be expressed as:

<maths id="MATH-US-00001" num="00001"><math overflow="scroll"><mtable><mtr><mtd><mrow><mi>N</mi><mo>≡</mo><mi /><mo>⁢</mo><mrow><mi>Length</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>of</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Training</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Sequence</mi></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mi>t</mi><mo>≡</mo><mi /><mo>⁢</mo><mrow><mi>Training</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Sequence</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Vector</mi></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mi>Q</mi><mo>≡</mo><mi /><mo>⁢</mo><mrow><mi>Length</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>of</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Input</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Signal</mi></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mrow><munder><mi>x</mi><mi>_</mi></munder><mo>⁡</mo><mrow><mo>[</mo><mi>n</mi><mo>]</mo></mrow></mrow><mo>≡</mo><mi /><mo>⁢</mo><mrow><mi>Input</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Signal</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Vector</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Over</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Sample</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mrow><mi>Indices</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>[</mo><mrow><mi>n</mi><mo>,</mo><mrow><mi>n</mi><mo>+</mo><mi>N</mi><mo>-</mo><mn>1</mn></mrow></mrow><mo>]</mo></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mi>α</mi><mo>≡</mo><mi /><mo>⁢</mo><mrow><mi>Minimum</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Confidence</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Threshold</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>in</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Range</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mrow><mo>(</mo><mrow><mn>0</mn><mo>,</mo><mn>1</mn></mrow><mo>]</mo></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mi>μ</mi><mo>≡</mo><mi /><mo>⁢</mo><mrow><mi>Detection</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Threshold</mi></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><mrow><msup><mi>α</mi><mn>2</mn></msup><mo>⁢</mo><mrow><mo></mo><munder><mi>t</mi><mi>_</mi></munder><mo></mo></mrow><mo>⁢</mo><mrow><mo></mo><mrow><munder><mi>x</mi><mi>_</mi></munder><mo>⁡</mo><mrow><mo>[</mo><mi>n</mi><mo>]</mo></mrow></mrow><mo></mo></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><mrow><mrow><msup><mi>α</mi><mn>2</mn></msup><mo>⁡</mo><mrow><mo>(</mo><mrow><msup><munder><mi>t</mi><mi>_</mi></munder><mi>H</mi></msup><mo>·</mo><munder><mi>t</mi><mi>_</mi></munder></mrow><mo>)</mo></mrow></mrow><mo>⁢</mo><mrow><mo>(</mo><mrow><mrow><msup><munder><mi>x</mi><mi>_</mi></munder><mi>H</mi></msup><mo>⁡</mo><mrow><mo>[</mo><mi>n</mi><mo>]</mo></mrow></mrow><mo>·</mo><mrow><munder><mi>x</mi><mi>_</mi></munder><mo>⁡</mo><mrow><mo>[</mo><mi>n</mi><mo>]</mo></mrow></mrow></mrow><mo>)</mo></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mrow><mi>y</mi><mo>⁡</mo><mrow><mo>[</mo><mi>n</mi><mo>]</mo></mrow></mrow><mo>≡</mo><mi /><mo>⁢</mo><mrow><mi>Matched</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Filter</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Output</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>at</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Sample</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Index</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>n</mi></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><mrow><msup><munder><mi>t</mi><mi>_</mi></munder><mi>H</mi></msup><mo>·</mo><mrow><munder><mi>x</mi><mi>_</mi></munder><mo>⁡</mo><mrow><mo>[</mo><mi>n</mi><mo>]</mo></mrow></mrow></mrow></mrow></mtd></mtr></mtable></math></maths>

The number of multiplications required to evaluate y[n] for all possible n can be expressed as: <br /><i>Q</i>(1+3·log₂<i>Q</i>), <i>Q&gt;N, Q=</i>2^k<br /> in the most efficient implementation.

If y[n] exceeds μ at any index, the training sequence has been detected. Under perfect conditions and in the absence of noise, a confidence threshold of 1 may be chosen. In practice, however, the confidence is degraded by the signal to noise ratio (SNR), channel propagation filter h, and carrier or doppler frequency offset f. The perfect confidence is multiplicatively degraded by:

<maths id="MATH-US-00002" num="00002"><math overflow="scroll"><mrow><mfrac><mn>1</mn><mrow><mn>1</mn><mo>+</mo><mi>SNR</mi></mrow></mfrac><mo>·</mo><mfrac><mrow><msup><mi>h</mi><mn>2</mn></msup><mo>⁡</mo><mrow><mo>[</mo><mn>0</mn><mo>]</mo></mrow></mrow><mrow><msup><munder><mi>h</mi><mi>_</mi></munder><mi>H</mi></msup><mo>·</mo><munder><mi>h</mi><mi>_</mi></munder></mrow></mfrac><mo>·</mo><mrow><mo></mo><mfrac><mrow><mi>sin</mi><mo>⁡</mo><mrow><mo>(</mo><mi>ω</mi><mo>)</mo></mrow></mrow><mi>ω</mi></mfrac><mo></mo></mrow></mrow></math></maths><maths id="MATH-US-00002-2" num="00002.2"><math overflow="scroll"><mrow><mi>where</mi><mo>⁢</mo><mstyle><mtext>:</mtext></mstyle></mrow></math></maths><maths id="MATH-US-00002-3" num="00002.3"><math overflow="scroll"><mrow><mi>ω</mi><mo>=</mo><mfrac><mrow><mn>2</mn><mo>⁢</mo><mi>π</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mi>N</mi></mrow><mi>M</mi></mfrac></mrow></math></maths><maths id="MATH-US-00002-4" num="00002.4"><math overflow="scroll"><mrow><mi>M</mi><mo>=</mo><mfrac><msub><mi>F</mi><mi>s</mi></msub><mi>f</mi></mfrac></mrow></math></maths><maths id="MATH-US-00002-5" num="00002.5"><math overflow="scroll"><mrow><msub><mi>F</mi><mi>s</mi></msub><mo>≡</mo><mrow><mi>Sampling</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Frequency</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>in</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Hz</mi></mrow></mrow></math></maths>

As illustrated in <figref idrefs="DRAWINGS">FIG. 2</figref>, it is the third degradation term (due to frequency offset) that has the greatest effect. The x-axis units have been normalized relative to each other.

There is nothing that can be done at the receiver to change the SNR or propagation channel conditions. However, in conventional matched filter methods, mixing the input signal with M different frequencies prior to performing the matched filter search has been used to reduce degradation due to unknown carrier offset. M is chosen to set the worst-case degradation to a manageable value (no lower than 0.9). This greatly increases the number of required complex multiplications to: <br /><i>M·Q</i>(1+3·log₂<i>Q</i>)

The conventional filtering method, with mixing, can be expressed as follows:

<maths id="MATH-US-00003" num="00003"><math overflow="scroll"><mtable><mtr><mtd><mrow><mrow><mrow><msub><mi>y</mi><mi>m</mi></msub><mo>⁡</mo><mrow><mo>[</mo><mi>n</mi><mo>]</mo></mrow></mrow><mo>≡</mo><mi /><mo>⁢</mo><mrow><mi>Matched</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Filter</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Output</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>at</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Sample</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Index</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>n</mi></mrow></mrow><mo>,</mo></mrow></mtd></mtr><mtr><mtd><mrow><mi /><mo>⁢</mo><mrow><mi>Frequency</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Offset</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><msub><mi>f</mi><mi>m</mi></msub></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><mrow><msup><munder><mi>t</mi><mi>_</mi></munder><mi>H</mi></msup><mo>·</mo><msub><mi>E</mi><mi>m</mi></msub><mo>·</mo><mrow><munder><mi>x</mi><mi>_</mi></munder><mo>⁡</mo><mrow><mo>[</mo><mi>n</mi><mo>]</mo></mrow></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msub><mi>E</mi><mi>m</mi></msub><mo>≡</mo><mi /><mo>⁢</mo><mrow><mi>Mixing</mi><mo>⁢</mo><mstyle><mspace width="0.8em" height="0.8ex" /></mstyle><mo>⁢</mo><mi>Matrix</mi></mrow></mrow></mtd></mtr><mtr><mtd><mrow><mo>=</mo><mi /><mo>⁢</mo><mrow><mi>diag</mi><mo>⁡</mo><mrow><mo>(</mo><msup><mi>ⅇ</mi><mrow><mi>j</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><mn>2</mn><mo>⁢</mo><mi>π</mi><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mi>f</mi><mi>m</mi></msub><mo>⁢</mo><mi>n</mi></mrow></msup><mo>)</mo></mrow></mrow></mrow></mtd></mtr><mtr><mtd><mrow><msub><mi>f</mi><mi>m</mi></msub><mo>=</mo><mi /><mo>⁢</mo><mrow><mi>m</mi><mo>·</mo><mfrac><msub><mi>F</mi><mi>s</mi></msub><mi>M</mi></mfrac></mrow></mrow></mtd></mtr></mtable></math></maths>

A feature of the method of <figref idrefs="DRAWINGS">FIG. 1</figref> (Step <b>12</b>) is that by rearranging the order of operations, the matched filter output is performed as the (fast) Fourier transform of the dot product of the conjugated training sequence and the input signal. In this method, y_m[n] is the matched filter output at sample index n and frequency offset f_m. <br /><i>y</i>_m<i>[n</i>]=FFT(<i>t*·<u>x</u>[n]</i>)

The method of <figref idrefs="DRAWINGS">FIG. 1</figref> has computational complexity: <br /><i>N·Q</i>(1+log₂<i>N</i>)<br /> and a decrease in complex multiplications by a factor of:

<maths id="MATH-US-00004" num="00004"><math overflow="scroll"><mfrac><mrow><mi>M</mi><mo>·</mo><mrow><mo>(</mo><mrow><mn>1</mn><mo>+</mo><mrow><mn>3</mn><mo>⁢</mo><mstyle><mspace width="0.3em" height="0.3ex" /></mstyle><mo>⁢</mo><msub><mi>log</mi><mn>2</mn></msub><mo>⁢</mo><mi>Q</mi></mrow></mrow><mo>)</mo></mrow></mrow><mrow><mi>N</mi><mo>·</mo><mrow><mo>(</mo><mrow><mn>1</mn><mo>+</mo><mrow><msub><mi>log</mi><mn>2</mn></msub><mo>⁢</mo><mi>N</mi></mrow></mrow><mo>)</mo></mrow></mrow></mfrac></math></maths><br /> This is always a decrease because both M and Q are required to be greater than N.

To understand the reduced computational complexity of the improved method of <figref idrefs="DRAWINGS">FIG. 1</figref>, consider the following practical example: <ul><li id="ul0001-0001" num="0000"><ul><li id="ul0002-0001" num="0034">N=128</li><li id="ul0002-0002" num="0035">F_s=8000</li><li id="ul0002-0003" num="0036">M=512</li><li id="ul0002-0004" num="0037">Q=512</li></ul></li></ul>

The number of complex multiplies of the traditional method is 7,340,032. The number of complex multiplies of the improved, efficient method is 524,288.

There is one further innovation that should be mentioned. Each y_m[n] comprises one column of a two-dimensional time-frequency image of size (M×Q). This necessitates a two-dimensional peak search against the threshold. Once a peak is detected, computing the 2-D expected value around the peak provides precise estimates of the carrier frequency and symbol timing clock offsets. Considering the example values provided above, the accuracy is typically less than 1 Hz and 1 sample, respectively.

In other words, the output of the matched filter (Step <b>12</b>) provides at least four signal parameters. The correlation has a position in time and a position in frequency, as well as a value. The correlation value and position can be used to determine the following parameters: the start time of the training sequence (which indicates the symbol timing clock offset), the carrier frequency, the carrier offset, and the signal to noise ratio.

<figref idrefs="DRAWINGS">FIG. 3</figref> illustrates a signal detection system <b>300</b>, designed to detect a signal having a particular training sequence. System <b>300</b> is an example of an application of signal detection for the purpose of decoding the signal. Other applications are possible.

System <b>300</b> may be part of a larger system, having different “modules” each associated with recognizing a different type of signal. For example, a system <b>300</b> may be a module of a larger system which has additional modules like system <b>300</b> but for signals having different training sequences. A larger system might also process an incoming signal prior to the signal being processed by system <b>300</b>, such as a system that first determines if the incoming signal is of a type that uses a training sequence. If so, the signal would be directed to one or more modules like system <b>300</b>, and if not, the signal could be deemed not of interest or it could be directed to some other type of recognition module.

As described above, the incoming signal is sampled (or resampled) by an A/D converter <b>31</b>. It is then processed by the training sequence filter <b>33</b>, which is designed to detect a particular training sequence of interest. The process performed by filter <b>33</b> is that of Step <b>12</b> in the method of <figref idrefs="DRAWINGS">FIG. 2</figref> discussed above. The results of the filter <b>33</b>, typically a correlation value, are delivered to a confidence analyzer <b>35</b>, which uses the filter results to determine whether the signal is likely to be the signal of interest. Data from the confidence analyzer may also be delivered to a graphical user interface (GUI) <b>37</b>, for interaction with an operator. If the signal is determined to be the signal of interest, it may be routed to a decoder <b>39</b>, which uses signal parameters associated with that type of signal to decode the “message” portion of the signal.