An Adaptive Line Tracker in Java
Java Programming Notes # 2356
- General Background Information
- Discussion and Sample Code
- Run the Program
- What's Next?
- Complete Program Listings
DSP and adaptive filtering
With the decrease in cost and the increase in speed of digital devices, Digital Signal Processing (DSP) is showing up in everything from cell phones to hearing aids to rock concerts. Many applications of DSP are static. That is, the characteristics of the digital processor don't change with time or circumstances. However, a particularly interesting branch of DSP is adaptive filtering. This is a scenario where the characteristics of the digital processor change with time, circumstances, or both.
Fourth in a series
This is the fourth lesson in a series designed to teach you about adaptive filtering in Java. The first lesson, entitled Adaptive Filtering in Java, Getting Started, introduced you to the topic by showing you how to write a Java program to adaptively design a time-delay convolution filter with a flat amplitude response and a linear phase response using an LMS adaptive algorithm.
An adaptive whitening filter
The second lesson in the series, entitled An Adaptive Whitening Filter in Java showed you how to write an adaptive whitening filter program in Java.
That lesson showed you how to use the whitening filter to extract wide-band signal from a channel in which the signal was corrupted by one or more components of narrow-band noise. The material in this lesson extends what you learned in that lesson, using similar concepts for an entirely different purpose.
A general-purpose adaptive engine
The third lesson in the series, entitled A General-Purpose LMS Adaptive Engine in Java, backtracked a bit. The first two lessons were primarily intended to gain your interest in the topic of adaptive filtering. They provided some working sample programs without getting too heavily involved in an explanation of the adaptive process. As a result of that approach, it was a little difficult to separate the adaptive behavior of those sample programs from the behavior designed solely to manage the data and to display the results.
In the third lesson, I presented and explained a general-purpose LMS adaptive engine written in Java that can be used to solve a wide variety of adaptive problems. I applied that engine to three different adaptive signal processing problems, emphasizing the separation of the code that provides the adaptive behavior from the code that is used simply to manage data and to display results.
An adaptive line tracker
In this lesson, I will use the general-purpose LMS adaptive engine to develop an adaptive spectral line tracker in Java. The line tracker will adapt in the time domain and track spectral lines in the frequency domain.
You may find it useful to open another copy of this lesson in a separate browser window. That will make it easier for you to scroll back and forth among the different listings and figures while you are reading about them.
I recommend that you also study the other lessons in my extensive collection of online Java tutorials. You will find those lessons published at Gamelan.com. However, as of the date of this writing, Gamelan doesn't maintain a consolidated index of my Java tutorial lessons, and sometimes they are difficult to locate there. You will find a consolidated index at www.DickBaldwin.com.
In preparation for understanding the material in this lesson, I recommend that you also study the lessons identified in the References section of this document.
Why track spectral lines?
At this point, you may be asking why a person would want to track spectral lines. There are a variety of good reasons that a person involved in signal processing would want to do such a thing, most of them fairly boring. In an attempt to avoid putting you to sleep, I will justify the need to track spectral lines by giving an explanation in the style of Tom Clancy and The Hunt for Red October.
An underwater acoustics listening post
Assume that you are stationed at an underwater acoustics listening post with the task of listening for and identifying enemy submarines. At any point in time, there may be hundreds or even thousands of vessels within range of your listening post, each emitting acoustic energy into the water. Your task is to separate the acoustic energy emitted by the enemy submarine from the acoustic energy emitted by the other vessels in the area.
An acoustic signature
In order to separate the two, you must have some information about the signature of the acoustic energy emitted by the submarine. This information may have been gained from clandestine sources.
Suppose you know, for example, that the particular submarine of interest has a pump with a two-speed motor that is responsible for maintaining water pressure in the system that provides water for the sailors to take personal showers. When several showers are being used, the pump runs at a high speed to maintain the required water pressure. When the showers are not being used, the pump motor automatically switches to a lower speed to conserve energy.
If you were to listen to the sound emitted by that pump, it might sound like a high-frequency whine when running at high speed, and it might sound like a low-frequency whine when running at low speed. (At least, that is what the two-speed pump on my swimming pool sounds like.)
The spectral signature
If you were to record the sound emitted by the pump and perform a spectral analysis on the recorded data, there would be a peak in the spectrum at a high frequency when the pump is running at high speed, and there would be a peak in the spectrum at a low frequency when the pump is running at low speed. Assuming that those two speeds are the only speeds at which the pump is capable of running, knowledge of those two frequencies could be a small part of a useful acoustic signature for the submarine.
(Most of the other vessels in the area probably wouldn't have an onboard motor that runs at exactly those two speeds.)
A graphic output
If you were to perform the spectral analysis at uniform time intervals and plot the spectral results one below the other, the plotted output might look something like Figure 1.
The graphic format
Figure 1 shows increasing time going down the page and increasing frequency going across the page from left to right. Zero frequency is shown at the extreme left. The frequency at the extreme right is one-half the sampling frequency.
Two spectral peaks
The high-frequency peak in the top-half of Figure 1 represents the acoustic energy emitted by the pump during the time interval when the pump is running at high speed. The low-frequency peak in the bottom-half of Figure 1 represents the acoustic energy emitted by the pump during the time interval when the pump is running at low speed.
Just for the record
Although it isn't important at this point in the discussion, the parameters shown in Figure 2 were used to produce the plot shown in Figure 1. (You can simply ignore Figure 2 for now. It will have more meaning when you see the code that produced Figure 1.)
Using following values: feedbackGain: 1.0E-5 numberIterations: 3375 filterLength: 15 wideBandNoiseScale: 20.0 fmSignalScale: 20.0 fmSignalCase: 2 freqSlideConst: 4.0E-4 freqShiftFactorLow: 0.5 freqShiftFactorHigh: 1.5 spectralWidth: 222 lengthMultiplier: 2 Conventional data length: 32
Now consider another scenario. Assume that the submarine, (or some other vessel in the vicinity), is running at a very low speed and that the screw is turning very slowly.
(In this case, the screw would emit relatively narrow-band acoustic energy at a low frequency.)
Assume that the skipper of that vessel decides to accelerate in a very controlled manner by slowly increasing the rotational speed of the screw. If the acoustic energy emitted by the propulsion system were recorded and subjected to spectral analysis as before, the plotted results might look something like Figure 3.
Narrow-band acoustic energy
Because the propulsion system that drives the screw is a rotating machine, it could be expected to emit acoustic energy in a very narrow band of frequencies. As the screw turns faster, the position of that narrow band of frequencies could be expected to move toward the right (higher) in the spectrum of the emitted acoustic energy.
Figure 3 represents the spectrum of the acoustic energy emitted by the propulsion system as the speed of the screw advances from a low speed to a high speed at a uniform rate. Of course, any vessel in the area could do that, so there is little or nothing in Figure 3 by itself that identifies the energy as being emitted by the submarine.
The program parameters
For the record, the parameters in Figure 4 were used to produce the output shown in Figure 3.
Using following values: feedbackGain: 1.0E-5 numberIterations: 3375 filterLength: 15 wideBandNoiseScale: 20.0 fmSignalScale: 20.0 fmSignalCase: 1 freqSlideConst: 4.0E-4 freqShiftFactorLow: 0.5 freqShiftFactorHigh: 1.5 spectralWidth: 222 lengthMultiplier: 2 Conventional data length: 32
A third scenario
Assume that during the period that the submarine is moving very slowly, many of the sailors have been excused from their duty stations. Many of those sailors decided to take advantage of the break to get a much-needed shower. As a result, the shower pump is running at high speed working to keep the pressure up in the shower system.
Then the captain decides to perform a well-controlled acceleration of the submarine to deal with some situation that has him concerned. At the same time, he orders all of the sailors to report to their duty stations. Those sailors who are in the showers exit quickly and no other sailors enter the showers. As a result, the shower pump breathes a sigh of relief and switches to low speed.
A more complex acoustic signature
If you were to record the acoustic emissions from the submarine during that period and perform the same sort of spectral analysis on the recorded data as before, the output might look something like Figure 5.
Aha! you say to yourself
You have seen that signature before. When the screw starts speeding up, the shower pump starts to loaf. That might be the important piece of information that lets you conclude with a high degree of confidence that you are looking at the signature of an enemy submarine and not the signature of a fishing trawler.
(And, of course, you turn out to be the hero of the novel who saves the world from destruction and marries the heroine.)
Once again, just for the record, the parameters shown in Figure 6 were used to produce the output shown in Figure 5.
Using following values: feedbackGain: 1.0E-5 numberIterations: 3375 filterLength: 15 wideBandNoiseScale: 20.0 fmSignalScale: 20.0 fmSignalCase: 3 freqSlideConst: 4.0E-4 freqShiftFactorLow: 0.5 freqShiftFactorHigh: 1.5 spectralWidth: 222 lengthMultiplier: 2 Conventional data length: 32
An important capability
All joking aside, the capability to track moving spectral lines in wide-band background noise is an important capability for many applications as far flung as sonar and voice analysis. Furthermore, the ability to estimate the actual frequency of the spectral lines to a high degree of accuracy is usually very important.
A side-by-side comparison
Now I am going to show you a comparison between two different approaches to tracking spectral lines. The approach you have been seeing so far is based on adaptively developing and analyzing a whitening filter of the sort that you learned about in the earlier lesson entitled An Adaptive Whitening Filter in Java. The other approach involves the use of conventional spectral analysis.
The left panel
The output in the left panel of Figure 7 was produced by:
- Updating the coefficients in a whitening filter having 16 coefficients each time a new sample of signal plus noise is received.
- Computing the frequency response of the whitening filter at the end of every 75th adaptive iteration.
- Displaying the frequency response formatted in such a way that the notches (nulls) in the whitening filter are converted to peaks that provide an indication of the location of the spectral lines in the spectrum of signal plus noise.
As you can see, the peaks in the left panel are relatively sharp and the background noise is fairly low.
The right panel
The output in the right panel of Figure 7 was produced by:
- Grabbing the 32 previous samples of signal plus noise at the end of every 75th adaptive iteration.
- Performing a Fourier transform on those 32 samples to provide an estimate of the spectral content of the signal plus noise.
- Displaying the amplitude spectrum in such a way that the peaks in the spectrum provide an indication of the location of the spectral lines in the spectrum of signal plus noise.
As you can see, the peaks in the right panel are relatively broad, and the background noise is relatively high.
The panel on the left in Figure 7 requires a modest computation for every sample of signal plus noise. In addition, it performs a Fourier transform on the 16-coefficient whitening filter at the end of every 75th iteration.
The panel on the right doesn't require any computations until time comes to perform the spectral analysis. Then it is required to perform a Fourier transform on a time series having 32 samples (as opposed to a whitening filter having on only 16 coefficients). I elected to use twice as many samples for the conventional approach as for the whitening approach in order to end up with roughly a comparable amount of arithmetic required for both approaches.
Resolution and background noise
As you can see, the resolution of the conventional approach is much poorer than the resolution of the adaptive whitening approach. In addition, there is much more noise between the peaks for the conventional approach.
The reason that the adaptive whitening approach provides better resolution has to do with the fact that it depends on the nulls in the response of the whitening filter to indicate the locations of the spectral lines rather than depending on the peaks. In many signal processing areas, nulls are much sharper than peaks and better resolution can be obtained through a process often referred to as "null steering". Of course, there are always tradeoffs, but in this case the tradeoff appears to be advantageous.
A radio direction finder
I'm going to illustrate this point by describing a completely different, but somewhat related technology.
At one point in my career, I was responsible for using radio direction finding (RDF) equipment to determine the location of radio transmitters. Many types of equipment were available for this task. The simplest was a van with a directional radio antenna mounted on the top. The person inside the van could turn a knob to rotate the radio antenna.
A directional response pattern
The radio antenna had a directional response pattern that looked something like a figure 8. The lobes on the top and the bottom of the figure 8 were approximately the same size, and nearly round.
In operation, the user would listen to a radio transmitter with a pair of headphones while manually rotating the antenna. He would note the two positions of the antenna that resulted in the strongest or loudest signal, and the weakest signal. Having calibrated the antenna, could then estimate the bearing (direction) to the transmitter with an ambiguity of 180 degrees.
The response pattern
By directional response pattern, I mean the effectiveness with which the antenna can successfully receive signals from a transmitter. For a directional response pattern, this depends on the direction to the transmitter relative to the rotational position of the antenna.
Transmitters located on a line that intersects the figure 8 along its long dimension (the vertical dimension relative to this figure 8) would be received the strongest. Transmitters located on a line that intersects the figure 8 along its narrow dimension (the horizontal dimension relative to this figure 8) would be poorly received if they are received at all. This is because the directional response pattern has a null response for radio signals received along the direction of the narrow dimension.
How does the system work?
Now envision what happens when the radio transmitter is fixed in a particular location and the antenna (and its response pattern) is rotated. When the antenna is rotated to the point where the long dimension of the figure 8 is aligned with the direction of the transmitter, the signal is strong. When the antenna is rotated by ninety degrees in either direction, the signal becomes weaker and weaker until it may no longer be discernable. At that point, it can be concluded that the transmitter is somewhere along a line that intersects the figure 8 along its narrow dimension.
There is still an ambiguity of 180 degrees because it isn't possible to determine which side of the antenna the transmitter is on. However, that ambiguity can be resolved by moving the van containing the antenna to a different location and taking another directional reading on the same transmitter.
The null is narrow
As I mentioned above, the two lobes in the antenna response pattern are nearly circular (probably more so than the typographical figure 8 that you see here). Thus, the angular width of the null is very narrow. As a result, rotating the antenna by only a few degrees produces a significant change in the loudness of the transmitter when the direction is near the null.
On the other hand, the main lobes of the figure 8 are very broad. Rotating the antenna by the same number of degrees produces very little change in the loudness of the signal when the direction is along the long dimension of the figure 8. Consequently, a much more accurate estimate of the bearing to the transmitter can be made by rotating the signal through the null in the pattern than can be made by rotating the signal through the peak in the pattern.
This is null steering
This well-known process is often referred to as null-steering. This is the general principle by which the adaptive spectral line tracking approach provides a more accurate estimate of the frequency of the line than does the conventional spectral analysis approach.
In effect, the null steering (adaptive line tracking) approach sacrifices accuracy in the estimate of the strength of the spectral line for better accuracy in the frequency of the line. (As you will recall from the earlier lesson entitled An Adaptive Whitening Filter in Java, the whitening filter used in the adaptive line tracker places nulls at the locations of the lines in the spectrum.)
In the case of radio direction finding, the null steering approach sacrifices accuracy in the estimate of the strength of the transmitter for better accuracy in the estimate of the direction to the transmitter.
What about the signal-to-noise ratio?
Although the adaptive approach provides better frequency resolution than the conventional approach in Figure 7, the existence of the spectral lines is apparent in both displays. The peak-to-peak amplitude of each of the narrow-band signals in Figure 7 was equal to the peak-to-peak amplitude of the wide-band noise. It is important to ask what happens when the signal-to-noise ratio is reduced.
Figure 8 shows the result of decreasing the signal-to-noise ratio by a factor of three relative to that for Figure 7. In Figure 8, the peak-to-peak amplitude of the wide-band noise is three times greater than the peak-to-peak amplitude of each of the narrow-band signals.
The program parameters
The parameters shown in Figure 9 were used to produce the output shown in Figure 8. The signal and noise level information is provided by the two boldface lines in Figure 9.
Using following values: feedbackGain: 1.25E-6 numberIterations: 3375 filterLength: 15 wideBandNoiseScale: 60.0 fmSignalScale: 20.0 fmSignalCase: 3 freqSlideConst: 4.0E-4 freqShiftFactorLow: 0.5 freqShiftFactorHigh: 1.5 spectralWidth: 222 lengthMultiplier: 2 Conventional data length: 32
Which approach is best?
You can judge for yourself, but it looks to me like the existence and location of the spectral lines in the adaptive (left) panel in Figure 8 is much better than the conventional (right) panel.
Increase conventional spectrum data length
The right panel of Figure 10 shows the result of keeping the signal-to-noise ratio the same as in Figure 8 while increasing to 80 samples the amount of signal plus noise data included in each conventional Fourier transform. (This significantly increases the computational requirement for the conventional approach.) In this case, each chunk of data subjected to conventional spectrum analysis overlaps the previous chunk by five samples.
Which is best now?
Once again, you can be the judge. Although the existence and location of the spectral lines in the right panel of Figure 10 is more obvious than the existence and location of the spectral lines in the right panel of Figure 8, it still looks to me like the adaptive approach in the left panel in Figure 10 is superior. Furthermore, the left panel in Figure 10 is much less computationally demanding than the right panel.
The program parameters
Figure 11 shows the parameters that were used to produce the output shown in Figure 10. The increased length of data used for conventional spectral analysis is shown by the boldface lines in Figure 11.
Input values were provided. Using following values: feedbackGain: 1.25E-6 numberIterations: 3375 filterLength: 15 wideBandNoiseScale: 60.0 fmSignalScale: 20.0 fmSignalCase: 3 freqSlideConst: 4.0E-4 freqShiftFactorLow: 0.5 freqShiftFactorHigh: 1.5 spectralWidth: 222 lengthMultiplier: 5 Conventional data length: 80
Enough talk, let's see some code!
Now let's see the code that produced these results.
The program named Adapt05
The adaptive line tracker program named Adapt05 can be viewed in its entirety in Listing 20 near the end of the lesson.
The purpose of the program is to use the general purpose LMS adaptive engine provided by AdaptEngine01 (see an explanation of the AdaptEngine01 class in the lesson entitled A General-Purpose LMS Adaptive Engine in Java) to implement an adaptive spectral line tracker. The line tracker is designed to track the frequency of frequency-modulated signals buried in wide-band noise. Adaptive processing takes place in the time domain. The signals are tracked in the frequency domain.
Comparison with conventional methods
Experimental results produced by the adaptive line tracker are compared with results produced by conventional spectrum analysis.
A whitening filter is used
The program develops a whitening filter (see the lesson entitled An Adaptive Whitening Filter in Java) performing one adaptive iteration for each incoming sample. In addition, the program computes the amplitude frequency response of the whitening filter at the end of every 75th iteration. The notches in the whitening filter are converted to peaks and provide an indication of the frequencies of the FM signals.
The result of computing each amplitude response on a whitening filter is displayed as one of the plots in the left panel of Figure 10. The plots are stacked one below the other with increasing time going down the page. The peaks in the plots in Figure 10 show the frequencies of the FM signals in the time period immediately preceding each plot. Frequency increases from left to right with zero at the left and one-half the sampling frequency at the right.
A demonstration of the program capability is accomplished by processing time series consisting of wide-band noise plus FM signals. Three different experimental cases can be specified by the user:
- A single FM sweep from a low frequency to a high frequency. The user specifies the rate at which the signal sweeps.
- A single FM signal that switches back and forth between two frequencies. The user specifies each of the two frequencies.
- An additive combination of the two cases described above.
User input to control a variety of experimental parameters is provided by way of command-line parameters. The command-line parameters are:
- double feedbackGain: This is a multiplicative factor that is used in the feedback loop of the LMS adaptive algorithm.
- int numberIterations: This is the number of iterations that the adaptive algorithm is allowed to execute before terminating and displaying the results. In Figure 10, the number of iterations was chosen so as to fill one page with plotted results.
- int filterLength: This is the length of the prediction filter that is developed within the adaptive algorithm. Note that this length is one less than the length of the whitening filter mentioned above. As you learned in the lesson entitled An Adaptive Whitening Filter in Java, the whitening filter consists of the prediction filter with a -1 concatenated onto its end.
- double wideBandNoiseScale: This is a scale factor that is applied to the wide band noise before it is added to the FM signal.
- double fmSignalScale: This is a scale factor that is applied to each FM signal before it is added to the wide-band noise.
- int fmSignalCase: This parameter specifies the test case described above. The value must be 1, 2, or 3.
- double freqSlideConst: This value specifies the rate at which the FM sweep signal changes frequency. The higher the value of this parameter, the faster will be the change in frequency.
- double freqShiftFactorLow: The base frequency for the frequency switching signal is one-fourth of the sampling frequency. This multiplicative factor is applied to the base frequency to establish the low frequency for the frequency-switching signal. For example, a value of 0.5 for this parameter results in a frequency that is one-eighth of the sampling frequency.
- double freqShiftFactorHigh: This parameter is applied as a multiplicative factor to the base frequency to establish the upper frequency for the frequency shifting signal.
- int lengthMultiplier: This parameter specifies the length of each chunk of data that is analyzed using conventional spectral analysis. This value is a multiple of the length of the whitening filter.
If the user doesn't provide the required ten command-line parameters, parameter values are used.
See the default-value comments in the code for an indication of the approximate values that might be appropriate for any particular parameter.
A marker at zero frequency
The program puts a marker at zero frequency in each spectral plot. This makes it possible to visually confirm that the spectral plots are properly aligned, with one spectral plot shown above the other.
If the plots are properly aligned, this results in the thin black vertical line shown at a frequency of zero in Figure 10. If the plots are not properly aligned, this marker will appear to walk across the page, probably in a fairly regular fashion.
The program was tested using J2SE 5.0 and WinXP. J2SE 5.0 or later is required.
The class named PlotALot08
This program uses a new version of a plotting class from the PlotALot family of plotting classes. You can view a complete listing of the PlotALot08 class in Listing 21. By now, you should be very familiar with the general construct of the classes in the PlotALot family, so I won bore you with an explanation of the class.The adaptive engine named AdaptEngine01
The adaptive engine named AdaptEngine01 provides all of the required adaptive behavior for this program. You learned about the adaptive engine in the lesson entitled A General-Purpose LMS Adaptive Engine in Java, so I won't repeat the explanation of that class in this lesson.