1 Exploiting Spectral Leakage for Spectrogram Frequency Super-resolution Ray Maleh, Frank A. Boyle Member, IEEE Abstract The spectrogram is a classica...

Author:
Betty Simpson

0 downloads 72 Views 741KB Size

No documents

Exploiting Spectral Leakage for Spectrogram Frequency Super-resolution Ray Maleh, Frank A. Boyle Member, IEEE

Abstract— The spectrogram is a classical DSP tool used to view signals in both time and frequency. Unfortunately, the Heisenberg Uncertainty Principal limits our ability to use them for detecting and measuring narrowband signal modulation in wideband environments. On a spectrogram, instantaneous frequency can only be measured to the nearest bin without additional interpolation. This work presents a novel technique for extracting higher accuracy frequency estimates. Whereas most practitioners seek to suppress spectral leakage, we use mismatched windows to exploit such artifacts in order to produce super-resolved spectral displays. We present a derivation of our methodology and exhibit several interesting examples.

textbook approach to this problem is to tune and filter the signal and differentiate its unwrapped phase. Other approaches for estimating instantaneous frequency,

Index Terms— time-frequency analysis, Fourier Transform, spectrogram, spectral leakage, super-resolution Review Topics— Communications Systems, Signal Processing and Adaptive Systems

SPECTROGRAMS AND HEISENBERG’S UNCERTAINTY PRINCIPLE

Inspired by the Short-Time Fourier Transform, the spectrogram (or periodogram) is a signal processing tool that is often used to view signal contents simultaneously in both time and frequency. Given a discrete signal x[n] of length NS, a window w[n] of length N, and the assumption that N divides equally into NS, we formally define the spectrogram (with 50% overlap) as: N −1

X ( l, k ) =

⎡

∑ x ⎢⎣n + n =0

lN ⎤ ⎛ − j 2πkn ⎞ w[n] exp⎜ ⎟ ⎥ 2 ⎦ ⎝ N ⎠

(1)

In essence, the spectrogram is a matrix whose columns consist of moving DFTs. A graphical depiction of the construction of a spectrogram is show below in Fig. 1. A key observation is that shorter DFT window sizes (increased time resolution) means that fewer DFT bins will be available (decreased frequency resolution). This is consistent with the Heisenberg Uncertainty Principle, which formally states that one cannot simultaneously have full time and frequency resolution. Now suppose the “CW” in Fig. 1 contains some very narrow-band FM modulation that we wish to recover. The The authors are with L-3 Communications Integrated Systems, Mission Integration Division, 10001 Jack Finney Blvd. Greenville, TX 75402, USA (e-mail: [email protected], [email protected],), Phone: 903-408-2605. Cleared by DoD/OSR for public release under 14-S-0121 on 11/05/2013.

frequency

I.

stack successive spectra

time

Fig. 1. Example of spectrogram showing a CW signal and two OOK signals.

including LMS/ML methods, zero-crossing techniques, quadratic interpolations, and others, are presented in [1],[2], and [3]. In Section II, we propose an interesting alternative methodology that exploits spectral leakage in order to visualize a signal and its super-resolved modulation on the same spectrogram surface. In Section 0, we present several examples involving simulated and real signals. Then, in Sections IV and V, we offer a detailed mathematical derivation of the results of this paper including a Cramér-Rao Bound analysis. II.

THE MISMATCHED TIME WINDOW SPECTROGRAM

It was observed per accidens that spectrograms of narrowband signals utilizing rectangular windows with missing (zeroed) entries contained nulls whose instantaneous frequencies matched the underlying signal modulation. An example of this is shown in Fig. 2 where two super-resolved replicas of the original narrow-band signal are present. In order to better characterize this phenomenon, we define the

2

peak − null bin offset = IQ sample rate bin width

standard mismatched time window (MMTW) w[n] as shown below in (2):

narrowband signal

A careful mathematical derivation of this proportionality is presented in Section IV.

sidelobe troughs

In the case of Fig. 4, we can calculate the bin-offset of the red signal (0.703) as follow: peak − null IQ sample rate 0.7 − 0.4 = (0.01) × 1 = 0.003

bin offset = bin width ×

Fig. 2. Curious-looking spectrogram revealing the “microscopic” modulation of the original narrow-band signal.

⎧0 if n = 0 w[n] = ⎨ ⎩1 otherwise

(2)

We consider a short signal of length N (i.e., one timeblock of a spectrogram) which consists of a single tone that is not bin-centered. The magnitudes of its ordinary DFT (with a pure rectangular window) as well as its DFT using the mismatched time window are shown below in Fig. 3.

Magnitude, dB

window length = Nfft

(3)

window length = Nfft ‐1

(4)

The plot on the right side of Fig. 4 shows the inverse magnitudes of the four signals over a fine frequency scale that is derived from (3). Another example of the dual coarsescale/fine-scale representation of a bin-offset signal is shown in Fig. 5. 140

120

0

0.5 Normalized Frequency

1.0

0

0.5 Normalized Frequency

1.0

100

Fine Frequency Scale 0.7839 0.7829 0.7819 0.7809 0.7799

0.7789

80

Sidelobe trough 60

Fig. 3. Power spectra for bin-offset CW signal using both a rectangular window (left) and a mismatched time window (right).

Since the signal’s frequency is not bin-centered, we observe significant spectral leakage. When using the mismatched time window, the spectral energy is redistributed so as to form a null. More interestingly, as portrayed in Fig. 4, the location of this null is related to the degree in which the signal’s frequency is bin-offset.

Distance between extrema

40 0

0.2

0.4 0.6 Frequency

0.1

0.2

0.3

20

0 0

IF Estimate

=

0.78

+

0.5 Normalized Frequency

1.0

.700

.702 .704 .706 .708 Normalized Frequency

0.002273 Fine Estimate

0.7

=

0.8

0.9

1

0.782273 Super-resolved Estimate

Fig. 5. Coarse and fine frequency scale representations of the DFT of a signal using a mismatched time window.

Fine‐resolution Power Spectrum

Carrier: f = 0.701 f = 0.702 f = 0.703 f = 0.704

0

1

0.4 0.5 0.6 Coarse Frequency Scale

Coarse Estimate

Power Spectrum: MMTW

0.8

Zoom In…

.710

Fig. 4. Power spectra for four signals with slightly different bin-offset frequencies.

The plot on the left shows the DFT of four signals (at normalized frequencies 0.701, 0.702, 0.703, and 0.704). In this case, the bin-center is at 0.700 and the bin-width is 0.010. Now observe that the distances between the peak and each null (moving from right to left, wrapping around if necessary) are proportional to the bin-offset frequencies. More precisely, the following relationship holds:

In this example, the maximum of the spectrum occurs at the bin corresponding to normalized frequency 0.78. By examining the location of the null (shown in the green inset) and applying (3), we calculate the bin offset as 0.002273. Adding this offset to the coarse estimate yields the superresolved frequency estimate of 0.782273. Since each column of a spectrogram is precisely equal to a DFT, using a time mismatched window will allow for the extraction of fine frequency modulation from narrowband communications signals. Given a spectrogram or spectrum of a wide-band environment, a user can identify a signal of interest, band-pass filter it, and then apply an MMTW spectrogram in order to super-resolve the underlying modulation. A schematic depiction of this process is shown below in Fig. 6. In the next section, we demonstrate the MMTW on various simulated and laboratory signals.

3

Data stream

spectrogram

algorithm, we were able to estimate DOA to within a few degrees.

Select SOI MMTW spectrogram fine scale RF

Band‐pass Filter about SOI

Extract coarse frequency structure

F

Extract fine frequency structure

Fig. 6. Flowchart of MMTW Spectrogram Processing

III.

EXPERIMENTS

Our first experiment consists of a simulated FSK signal in a wide-band environment with normalized bandwidth 1. The modulation bandwidth is 1 × 10-4, which is considerably smaller than the DFT bin-width of 1 / 512 ≈ 2 × 10-3. Nevertheless, the MMTW spectrogram is successful at recovering the FSK sequence as shown below in Fig. 7. Modulation bandwidth = 1 ൈ 10‐4 Ground‐truth FSK sequence

Conventional Spectrogram 0.75

.17720 .17715

0.50

.17710

0.25

Spectral resolution: Fs/N ≈ 0.002

0

.17705

Spectrogram with MMTW

Fine Structure from MMTW Spectrogram .1775

0.75

.1770

0.50

.1765

0.25

.1760

0

Invert spectrogram and shift scale to show bin‐position

Fig. 8. The effectiveness of the MMTW in dense signal environments.

25

Overlay observed structure onto ground truth 20 .17720 .17715 .17710

15

Magnified Doppler Shift

.17705

10

Fig. 7. Extraction of FSK sequence from simulated narrowband signal.

For the next experiment, we examined a signal in a dense environment as shown in the top panel of Fig. 8. After bandpass filtering the signal and applying the MMTW spectrogram, we extracted the underlying modulation shown in the middle panel. For comparison, the modulation structre was also extracted via conventional means, with the band passed instantaneous frequency. The two approaches produced consistent results. A third shows the effectiveness of the MMTW spectrogram with respect to direction finding. Given an antenna(s) that is mechanically (or electronically) traversing a circular path, it is possible to calculate a signal’s direction of arrival (DOA) using Doppler shift [4]. The direction of arrival is simply the phase shift of the Doppler induced sinusoidal modulation. Unfortunately, due to the extremely fast speed of light, it is impossible to detect this modulation on a traditional spectrogram. However, by using the MMTW spectrogram, it is possible to determine DOA from mere visual inspection. In Fig. 9, we show a simulated signal that is received by a Doppler antenna as well as the super-resolved estimate of the Doppler modulation. By using a very straight-forward

5

Received Signal 0

0

100

200 300 400 500 600 700 800 Meas. DOA = 33.6712 deg, True DOA = 32 deg

900

Fig. 9. Estimating DOA by exposing Doppler induced modulation.

Our final experiment involves the use of the MMTW to expose the fine frequency structure of cricket chirps from a sound recording. As is shown in Fig. 10 (a), a raw spectrogram of cricket chirps does little to help us visualize individual chirps. In order to achieve super-resolution, we first up-sampled and interpolated the signal by a factor of 8 and then applied an MMTW spectrogram, which is shown in Fig. 10 (b). Lastly, as shown in Fig. 10 (c), we isolated a single cricket chirp and generated an MMTW spectrogram that not only shows the downward chirp, but some of the frequency structure that is present when the cricket returns its legs to the chirp starting position. Such spectral structure may be invaluable to a biologist studying cricket anatomy.

4 N −1

Cricket Chirp Recording

X (k ) =

Frequency, kHz

20

n =0

=

15

A

0

+ α )n / N ) exp( − j 2πkn / N )

exp( j 2π (k 0 + α − k ) ) − 1 exp( j 2π (k 0 + α − k ) / N ) − 1

The second equality comes from the fact that the Fourier sum happens to be a geometric series. If we subtract the value of x[0] (i.e., apply the mismatched time window) from the above spectrum and compute its magnitude, we obtain:

10

5

0

∑ A exp( j 2π (k

0

50

100 150 Time, ms

X (k ) − x[0] =

200

(a)

A(exp( j 2π (k0 + α − k ) ) − 1) −A exp( j 2π (k0 + α − k ) / N ) − 1

⎛ ⎛ j 2π (k0 + α − k ) ⎞ ⎞ A⎜ exp( j 2π (k0 + α − k ) ) − exp⎜ ⎟⎟ N ⎝ ⎠⎠ = ⎝ exp( j 2π (k0 + α − k ) / N ) − 1

MMTW Spectrogram 2.5 2

1 ⎞⎞ ⎛ ⎛ A exp⎜ jπ (k0 + α + k )⎜1 + ⎟ ⎟ ⎝ N ⎠ ⎠ sin ⎛ π (k + α − k )⎛1 − 1 ⎞ ⎞ ⎝ = ⎜ ⎜ ⎟⎟ 0 exp( j 2π (k0 + α − k ) / N ) − 1 ⎝ N ⎠⎠ ⎝

1.5 1 0.5 0 0

50

100 150 Time, ms

200

250

(b) Single Cricket Chirp Structure 2.5 2

We note that the above magnitude is equal to zero if, and only if, the sine term is zero, which will happen if, and only if, the quantity (k0 + α − k)(1 − 1/N) = (k0 + α − k)(N − 1)/N is equal to an integer. As a consequence, the maximum value of Y(k) = 1 / | X(k) − x[0] | will occur at the integer value of k where the fractional part of (k0 + α − k)(1 − 1/N) is closest to zero. To find the value of k, let’s assume for simplicity that the value of the bin-offset α falls on a uniform discrete grid with spacing 1/(N−1), i.e. assume α = r / (N − 1) for some integer r. Further suppose that there exists some integer m such that

1.5

r ⎛ ⎞⎛ N − 1 ⎞ (k 0 − k )( N − 1) + r =m − k ⎟⎜ ⎜ k0 + ⎟= N − 1 N ⎝ ⎠⎝ N ⎠

1

(5)

0.5 0

0

2

4

6 Time, ms

8

10

12

(c) Fig. 10. (a) Traditional spectrogram of cricket chirp sampled at 44.1 kHz. (b) MMTW spectrogram of several cricket chirps. (c) MMTW spectrogram of a single cricket chirp. The frequency scales in the bottom two panes show the amount of bin offset in kHz and do not represent absolute frequencies.

IV.

MATHEMATICAL DERIVATION

To derive the technique presented in this paper, assume x[n] = Aexp(j2π(k0 + α)n/N) is a single tone signal over N samples with complex amplitude A, and a non-bin-centered frequency k0 + α where k0 Ԗ {0,ڮ, N−1} and α Ԗ [0,1) is the bin offset. Our objective is to estimate both k0 and α. In order to do this, we first calculate the discrete Fourier transform of the above non-bin-centered signal, which is:

We seek to solve the above equation for k. Rearranging terms gives us that:

k0 − k =

Nm − r ( N − 1)m + (m − r ) m−r = = m+ N −1 N −1 N −1

(6)

Since k0 − k and m are integers, then so must be the quotient (m − r)/(N − 1). This implies that m ≡ r (mod N − 1). Solving the above for k yields: m−r k = k0 − m − (7) N −1 Based on the modular relationship we just deduced, we know that m = r + q(N − 1) for some integer q. Substituting this into (7) gives:

k = k 0 − r − q( N − 1) −

r + q( N − 1) − r = k 0 − r − qN N −1

In other words, k ≡ k0 − r (mod N). Recalling that k0 is the location of the spectral peak, k is the location of the null, and

5 r is the amount of bin-offset modulo N − 1, we see that this relation is precisely equivalent to (3).

For a general α Ԗ [0,1), we find that the minimum value of |X(k) – x[0]| will occur approximately αN bins away from the bin where the maximum of the digital spectrum occurs. This suggests that the location of this minimum can be used to estimate the true frequency of the tone x[n] to within a factor of O(1/N2). In the following section, we use the Cramér-Rao Bound for frequency estimators to show that this is asymptotically the best super-resolution that we can hope to achieve. V.

RELATIONSHIP TO THE CRAMÉR-RAO BOUND

It is not difficult to show (see [5]) that any unbiased frequency estimator that is based on N uniformly spaced IQ samples of a complex sinusoid satisfies the following CramérRao Bound: ) 3σ 2 fS2 var( f ) ≥ 4π 2 A2 N (N + 1)(2 N + 1) (8) ⎛ 1 ⎞ = Θ⎜ 3 ⎟ ⎝N ⎠ where A is the signal amplitude, σ is the noise standard deviation, and fS is the IQ sample rate . Superficially, this seems to contradict the high SNR asymptotic error bound we calculated in the previous section, which implies that the error variance is O(1/N4). This is another example of the paradoxical behavior of the mismatched time window spectrogram. A quick glance at the problem seems to indicate that the frequency estimates obtained by our N samples seem to violate the Cramér-Rao bound. Alas, there is no magic being performed here. The increased accuracy stems from the fact that our methodology involves pre-filtering a signal in either the analog domain or in the full digital domain (not just one window). Either way, since we’re assuming the target signal modulation has bandwidth less than a single DFT bin-width, it follows that the initial filtering yields a linear processing gain over the SNR A/σ of ⎛ A⎞ ⎜ ⎟ = ⎝ σ ⎠ filt

fS ⎛ A⎞ ⎜ ⎟ bin width ⎝ σ ⎠ orig

=

fS ⎛ A⎞ ⎜ ⎟ f S /(CN ) ⎝ σ ⎠ orig

(9)

⎛ A⎞ = CN ⎜ ⎟ ⎝ σ ⎠ orig where the constant C is typically on the order of 0.5 to 1. Factoring the processing gain (9) into the CRB (8) yields: 2 ) 3 f S3 ⎛σ ⎞ var( f ) ≥ ⎜ ⎟ 4π 2CN 2 (N + 1)(2 N + 1) ⎝ A ⎠orig (10) ⎛ 1 ⎞ = Θ⎜ 4 ⎟ ⎝N ⎠ We can now conclude that our enhanced frequency estimator has a variance that is asymptotically equivalent to

the Cramér-Rao bound for high SNR and no further orders of super-resolution are possible. VI.

CONCLUSION

In this paper, we have proposed the MMTW spectrogram as a novel strategy for exploiting spectral leakage in order to recover fine frequency structure present in a signal. In additional to presenting a wide variety of interesting examples, we have exhibited a full mathematical justification of the methodology along with a Cramér-Rao bound analysis showing that it asymptotically achieves maximal frequency resolution. While admittedly not the fastest way to superresolve frequency information, the MMTW spectrogram does offer enhanced spectral visualization and yields incredible theoretical insight into the importance of signal spectral tails. REFERENCES [1] B. Boashash, “Estimate and Interpreting the Instantaneous Frequency of a Signal – Part 2: Algorithms and Applications,” Proc. of the IEEE, vol. 80, no. 4, Apr 1992. [2] J. Hansen, “Selected Approached to Estimation of Signal Phase,” Technical Report, University of Rhode Island, 2003. [3] E. Jacobsen, P. Kootsookos, “Fast, Accurate Frequency Estimators,” IEEE Signal Proc. Magazine DSP Tips & Tricks, pp. 123-125, May 2007. [4] D. Adamy, EW 101: A First Course in Electronic Warfare. Boston, MA: Artech House, 2001. [5] D. C. Rife, R. R. Boorstyn, “Single-Tone Parameter Estimation from Discrete-Time Observations,” IEEE Trans. Info Theory, vol. IT-20, pp. 591-598, 1974.

AZDOC.SITE | To ensure the functioning of the site, we use **cookies**. We share information about your activities on the site with our partners and Google partners: social networks and companies engaged in advertising and web analytics. For more information, see the Privacy Policy and Google Privacy & Terms. Your consent to our cookies if you continue to use this website. Accept