A General-Purpose LMS Adaptive Engine in Java
Java Programming Notes # 2354
- Preface
- General Background Information
- Preview
- Discussion and Sample Code
- Run the Programs
- Summary
- What's Next?
- References
- Complete Program Listings
Preface
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 situation where the characteristics of the digital processor change with time, circumstances, or both.
Third in a series
This is the third lesson in a series designed to teach you about adaptive filtering in Java.
Getting started
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. That was a relatively simple time-adaptive filtering problem for which the correct solution was well known in advance. That made it possible to check the adaptive solution against the known solution.
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 project was conceptually more difficult than the filter that I explained in the first lesson.
That lesson also 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.
Will backtrack a bit
I will backtrack a bit in this lesson. 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.
A general-purpose LMS adaptive engine
In this lesson, I will present and explain a general-purpose LMS (Least-Mean Squares) adaptive engine written in Java that can be used to solve a wide variety of adaptive problems.
To illustrate how this adaptive engine can be used to solve different problems, I will begin by applying the adaptive engine to the simplest adaptive problem that I can devise.
Following that, I will apply the adaptive engine to more complex problems similar to the problems that were addressed in the first two lessons in the series.
In all three cases, I will completely separate the part of the program that exhibits adaptive behavior from the part of the program that is used simply to manage data and to display results.
Viewing tip
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.
Supplementary material
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 particular, in preparation for understanding the material in this lesson, I recommend that you study the lessons identified in the References section of this document.
General Background Information
The LMS adaptive engine
The LMS adaptive engine is deceptively simple. In fact, once you have an LMS adaptive engine available, the use of that engine reminds me of an old story about an automobile mechanic and a screw.
The automobile mechanic and the screw
As the story goes, a customer watched the mechanic doing his job and then complained that the charges were two high for the small amount of effort that the mechanic had spent turning a screw to fix the problem. The mechanic's response was that he doesn't get paid for turning the screw, he gets paid for knowing which screw to turn, why that particular screw should be turned, and how far to turn it.
Deceptively simple
Working with the adaptive engine is a similar situation. As mentioned above, the LMS adaptive engine is deceptively simple. The same engine can be used to solve a wide variety of different adaptive problems. Once you know the mechanics of how the engine behaves, the real challenge is in knowing how and what to feed to the engine in order to solve a particular adaptive problem.
AdaptEngine01
The adaptive engine that I will provide in this lesson is an object of the class named AdaptEngine01. (You can view a complete listing of that class in Listing 15 near the end of the lesson.) An object of this class is a general purpose adaptive engine that implements a classical LMS adaptive algorithm.
The adapt method
The adaptive algorithm is implemented by the instance method named adapt belonging to an AdaptEngine01 object. Each time the adapt method is called it receives one sample from each of two different time series. One time series is considered to be data that is to be filtered using an evolving convolution filter. The other time series is considered to be an adaptive target.
Transform the data into the target
The purpose of the adapt method is to adaptively create a convolution filter which, when applied to the data time series, will transform it into the target time series.
Adjusting the coefficients
Each time the adapt method is called it performs a dot product between the current version of the filter and the contents of a delay line in which historical data samples have been saved. The result of that dot product is compared with the target sample to produce an error value.
(The error value is produced by subtracting the value of the target sample from the result of the dot product.)
The error value is then used in a classical LMS adaptive algorithm to adjust the coefficients of the convolution filter.
(The adjustment process is very straightforward. However, rather than to attempt to explain the mechanics of the adjustment process at this point, I will explain it later while discussing the actual code.)
Drive the error to zero
The purpose of the adjustment is to produce a set of filter coefficients that will drive the error to zero over time. If the error goes to zero, the time series representing the data will have been transformed into the time series representing the target.
The constructor
The constructor for the AdaptEngine01 class receives two parameters:
- filterLength
- feedbackGain
The filterLength value is used to construct two arrays whose size is equal to the value of filterLength. One array is used later to contain the filter coefficients. The other array is used later as a tapped delay line to contain the historical data samples and to shift them by one element each time the method is called.
The delay line
In other words, each time the adapt method is called, each value currently stored in the delay line is shifted by one element and the new data value is inserted at the end of the delay line.
The feedback gain
The feedbackGain value is used in the LMS adaptive algorithm to compute the new filter coefficients.
(You will see how the value of feedbackGain is used in the computation of the updated filter coefficients later.)
The returned values
In order to make it possible for the adapt method to return more than one value each time it is called, the source code in Listing 15 defines a simple wrapper class named AdaptiveResult. Each time the adapt method is called, it instantiates, populates, and returns a reference to an object of type AdaptiveResult. This object is populated with the following values:
- double[] filterArray: A reference to the array object containing the current filter coefficients.
- double output: The result of performing the dot product between the filter and the historical data.
- double err: The result of comparing the output of the dot product with the target value.
Different adaptive applications will make use of none, one, or more of the returned values.
Program testing
All of the classes provided in this lesson were tested using J2SE 5.0 and WinXP. J2SE 5.0 or later is required.
Preview
AdaptEngine01
I will begin by presenting and explaining the code for the general-purpose adaptive engine class named AdaptEngine01, as explained above. You can view a complete listing of this class in Listing 15.
Adapt06
Then I will present and explain the code for the simplest sample program that I was able to devise to illustrate the use of the adaptive engine. This program is named Adapt06. You can view a complete listing of this program in Listing 16 near the end of the lesson. In this program, the code that controls the adaptive behavior is clearly separated from the code that manages the data and displays the results.
Transforming sinusoids
This program named Adapt06 adaptively designs a convolution filter that transforms a cosine function into a sine function having the same amplitude and frequency.
There are no input parameters. You can just compile and run the program.
Graphic output
The following time series are plotted in color showing the convergence of the adaptive algorithm for the program named Adapt06:
- black: input to the filter - the cosine function
- red: output from the filter
- blue: adaptive target - a sine function
- green: error
Two coefficients
The filter has only two coefficients, each of which is initialized to a value of 0. The final values of the two filter coefficients are listed on the command-line screen after the specified number of adaptive iterations has been performed.
Purely deterministic
Note that because the time series used in this program do not contain random components, this is a purely deterministic problem that can easily be solved by writing and solving a pair of simultaneous equations.
Matrix equations
Thus, in this case, the adaptive solution is an adaptive approach to finding the roots of a pair of simultaneous equations. In fact, for many adaptive problems, an alternative non-adaptive solution can be written in terms of matrices involving autocorrelation and cross-correlation functions between the data time series and the target time series. In those cases, the adaptive solution provides a relatively simple adaptive approach to solving what may otherwise be a difficult matrix inversion problem.
Coefficient values
For the specific sinusoidal frequencies used by this program, when the program is allowed to run for 1000 iterations so as to fully converge, the values for the two coefficients converge to:
- 1.4142064344006575
- -0.9999927187203118
(You might recognize these two values as being very close to the square root of two and minus one.)
For other frequencies, however, the coefficients converge to different values.
Other classes required
This program requires the following classes in addition to Adapt06:
- AdaptEngine01
- AdaptiveResult
- PlotALot05
Adapt01a and Adapt02a
After I explain the program named Adapt06, I will present and briefly discuss the application of the adaptive engine to two other problems that are very similar to the two problems that I explained in the lessons entitled Adaptive Filtering in Java, Getting Started and An Adaptive Whitening Filter in Java.
These two programs are named Adapt01a and Adapt02a. The purpose of these two programs is to present solutions to the two problems using a structure where the adaptive code is clearly separated from the code required to manage the data and to display the results.
I will defer further discussion of these two programs until later in the lesson.
Discussion and Sample Code
The adaptive engine named AdaptEngine01I will discuss the code for the adaptive engine in fragments. You can view the source code for the entire class in Listing 15 near the end of the lesson.
The beginning of the class and the constructor for the class are shown in Listing 1.
class AdaptEngine01{ double[] filterArray;//filter coefficients stored here double[] dataArray;//historical data is stored here double feedbackGain;//used in LMS adaptive algorithm //Constructor public AdaptEngine01(int filterLength, double feedbackGain){ //Construct the two arrays and save the feedback gain. filterArray = new double[filterLength]; dataArray = new double[filterLength]; this.feedbackGain = feedbackGain; }//end constructor |
Note that the constructor constructs two separate array objects. One array object, referred to by filterArray, will be used to contain the filter coefficients. The other array object, referred to by dataArray will be used as a tapped delay line to store historical values from the data time series that is to be filtered.
The constructor also receives and saves the value for feedbackGain.
The method named adapt
The method named adapt implements a classical LMS adaptive algorithm. This method creates and applies a convolution filter to an input data time series. The filter is adaptively adjusted to drive the difference between the filtered time series and a target time series to zero.
The filter output, the error, and a reference to the array object containing the filter coefficients are encapsulated in an object of type AdaptiveResult and returned to the calling method.
Two incoming parameters
The adapt method begins in Listing 2. The method receives two incoming parameters. One parameter is a single sample from a sampled time series that is to be filtered by the convolution filter. The other parameter is a single sample from the target time series mentioned above.
AdaptiveResult adapt(double rawData,double target){ flowLine(dataArray,rawData); |
Listing 2 invokes the flowLine method to insert the data sample into the tapped delay line.
(I have used and explained the flowLine method in several previous lessons, and won't repeat that explanation here. You can view the method in Listing 15 near the end of the lesson.)
Apply the filter and compute the error
The code in Listing 3 invokes the dotProduct method to apply the current coefficient values to the data time series.
double output = dotProduct(filterArray,dataArray); double err = output - target; |
Then Listing 3 subtracts the target value from the dot product output to compute the error value.
(I have used and explained the dotProduct method in several previous lessons and won't repeat that explanation here. You can view the method in Listing 15 near the end of the lesson.)
Adjust the filter coefficient values
Listing 4 applies the classical LMS adaptive algorithm in a for loop to adjust the value of each filter coefficient using the following values:
- The current coefficient value.
- The current error value.
- The value of the data time series that was aligned with the filter coefficient when the dot product was computed (the computation that resulted in the current error value).
- A feedback constant that controls the adaptation rate.
for(int ctr = 0;ctr < filterArray.length;ctr++){ filterArray[ctr] -= err*dataArray[ctr]*feedbackGain; }//end for loop. |
All that remains ...
That's really all there is to it. All that remains is to return the appropriate values to the calling method.
I told you that the algorithm would be deceptively simple. It's somewhat amazing that such a simple algorithm can be used to solve so many different complex problems.
Return the results
Listing 5 constructs, populates, and returns a reference to an object of the class AdaptiveResult.
return new AdaptiveResult(filterArray,output,err); }//end adapt |
As you can see, the object that is returned is populated with:
- A reference to the array containing the filter.
- The output from the filter.
- The value of the error.
These are the only values that change under the control of the adaptive algorithm.
You can view the class definition for the simple AdaptiveResult class in Listing 15.
End of the method
Listing 5 also signals the end of the adapt method, and will signal the end of my discussion of the LMS adaptive engine encapsulated in the class named AdaptEngine01. The remainder of the lesson will concentrate on how an object of this class can be used to solve three different adaptive problems.
The program named Adapt06
As mentioned earlier, the purpose of this program is to illustrate the use of the general-purpose LMS adaptive engine named AdaptEngine01. This is the simplest program that I could devise to illustrate the use of the adaptive engine. This program adaptively designs a convolution filter that transforms a cosine function into a sine function having the same amplitude and frequency.
Before getting into the details of the code, I will show you some graphic output from the program. The following time series are plotted in color showing the convergence of the adaptive algorithm:
- black: input to the filter - the cosine function
- red: output from the filter
- blue: adaptive target - a sine function
- green: error
The first ninety iterations
The top panel in Figure 1 shows the four time series identified above for the first ninety adaptive iterations. The filter is applied to the black trace producing the red trace as the filter output. The filter coefficients are being adjusted in an attempt to cause the filter output (red trace) to look like the target (blue trace). As the adaptive process converges toward a solution, the error (green trace) should approach zero.
As you can see, by the end of the first ninety iterations, the red trace is beginning to look like the blue (target) trace and the green (error) trace is getting smaller.
Figure 1 |
Iterations 181 through 270
The bottom panel in Figure 1 shows the results for iterations in the range from 181 to 270. As you can see, by this point, the adaptive process has nearly converged to a solution with the red trace nearly matching the blue trace and the error trace having been reduced to near zero.
Final coefficient values
As mentioned earlier, the filter consists of two coefficients, which are both initialized to a value of zero. When convergence is achieved, the coefficient values have converged to the two values shown in Figure 2.
Final filter coefficients: 1.4142064344006575 -0.9999927187203118 Figure 2 |
This solution is peculiar to the frequency that I selected for the sinusoids. Had I selected a different frequency, convergence would still have been achieved, but the final values of the two coefficients would have been different.
The Adapt06 class
Listing 6 shows the beginning of the Adapt06 class and the main method.
class Adapt06{ public static void main(String[] args){ double feedbackGain = 0.0002; int numberIterations = 1000; int filterLength = 2; //Instantiate an object of the class and execute the // adaptive algorithm using the specified feedbackGain. new Adapt06().process(feedbackGain, numberIterations, filterLength); }//end main |
The most important thing to note in Listing 6 is the invocation of the method named process on an object of the Adapt06 class.
The process method
The process method begins in Listing 7.
void process(double feedbackGain, int numberIterations, int filterLength){ AdaptEngine01 adapter = new AdaptEngine01(filterLength,feedbackGain); |
The code in Listing 7 instantiates an object of the AdaptEngine01 class, which will be used to provide the adaptive behavior for the program. As you can see, the filter length and the feedback gain values are passed to the constructor for the object.
Instantiate a plotting object and declare working variables
Listing 8 begins by instantiating a plotting object of the PlotALot05 class to produce the graphic output shown in Figure 1.
(I have presented and explained objects from the PlotALot family of classes in several previous lessons and won't repeat that explanation here.)
//Instantiate a plotting object for four data channels. // This object will be used to plot the time series // data. PlotALot05 plotObj = new PlotALot05( "Time Series",460,155,25,5,4,4); //Declare and initialize working variables. double output = 0; double err = 0; double target = 0; double input = 0; double dataScale = 20;//Default data scale AdaptiveResult result = null; |
Listing 8 also declares and initializes some working variables.
Execute the adaptive iterations
Listing 9 shows the beginning of a for loop that executes the specified number of adaptive iterations.
for(int cnt = 0;cnt < numberIterations;cnt++){ //Generate the data to be filtered and the adaptive // target on the fly. input = dataScale * cos(2*cnt*PI/8); target = dataScale * sin(2*cnt*PI/8); |
Listing 9 also shows the code that creates the cosine and sine values used as the data to be filtered and the target respectively. The purpose of the adaptive process is to transform the time series produced by the cos method into a match for the time series produced by the sin method.
Execute the adaptive behavior
Now we come to the most important statement in the entire program. Listing 10 invokes the adapt method on the adaptive engine object to provide the adaptive behavior for the program. Note that the two values generated in Listing 9 are passed to the adapt method.
result = adapter.adapt(input,target); |
All of the adaptive behavior in the entire program is confined to this method call. All of the other code in the program simply manages objects and data and displays results.
The adapt method instantiates and populates an object of the AdaptiveResult class and returns a reference to that object. The code in Listing 10 stores that reference in the reference variable named result to make the adaptive results available for use later.
Feed the plotting object
The code in Listing 11 extracts the error and the filter output values from the AdaptiveResult object and feeds those values, along with the input and target values, to the plotting object. Eventually these values are plotted in the format shown in Figure 1.
(The values fed to the plotting object aren't actually plotted until the end of the program when the plotData method is invoked on the plotting object.)
//Get the results of the adaptive behavior for // plotting. err = result.err; output = result.output; //Feed the time series data to the plotting object. plotObj.feedData(input,output,target,err); }//end for loop |
Listing 11 also signals the end of the for loop that began in Listing 9.
Cleanup code
The code in Listing 12 causes all of the values that have been fed to the plotting object referred to by plotObj to actually be plotted on the screen.
//Cause the data to be plotted. plotObj.plotData(); //List the values of the filter coefficients. System.out.println("nFinal filter coefficients:"); double[] filter = result.filterArray; for(int cnt = 0;cnt < filter.length;cnt++){ System.out.println(filter[cnt]); }//end for loop }//end process method }//end class Adapt06 |
The code in Listing 12 also displays the final values for the filter coefficients on the command-line screen.
Listing 12 also signals the end of the process method and the end of the Adapt06 class.
The program named Adapt01a
The program named Adapt01a is an update to the program that was presented and explained in the earlier lesson entitled Adaptive Filtering in Java, Getting Started. The purpose of this updated version of the program is to clearly separate the code that is responsible for the adaptive behavior from the code that is responsible for data management and the plotting of results.
This new version of the program is shown in its entirety in Listing 17 near the end of the lesson.
There are two major differences between this version and the earlier version of the program:
- This version was simplified somewhat by reducing the number of parameters that are provided by the user.
- All of the adaptive behavior was removed from the program and consolidated into the single statement shown in Listing 13.
AdaptiveResult result = adapter.adapt(input,target); |
I explained the earlier version of the program in detail in the lesson entitled Adaptive Filtering in Java, Getting Started. If you understood that explanation, and you understand the adaptive engine presented in this lesson, you will surely understand the new version of the program named Adapt01a. Therefore, I won't repeat an explanation of the program in this lesson.
The program named Adapt02a
The program named Adapt02a is an update to the program that was presented and explained in the earlier lesson entitled An Adaptive Whitening Filter in Java. As was the case above, the purpose of this version of the program is to clearly separate the code that is responsible for the adaptive behavior from the code that is responsible for data management and the plotting of results.
This new version of the program is shown in its entirety in Listing 18 near the end of the lesson.
There are two major differences between this version and the earlier version of the program:
- This version was simplified by eliminating all user input.
- All of the adaptive behavior was removed from the program and consolidated into the single statement shown in Listing 14.
AdaptiveResult result = adapter.adapt(rawData[0], rawData[1]); |
As before, I explained the earlier version of this program in detail in the lesson
entitled An
Adaptive Whitening Filter in Java. If you understood that
explanation, and you understand the adaptive engine presented in this lesson,
you will also understand the new version of the program named Adapt02a.
Therefore, I won't repeat an explanation of the program in this lesson.
Run the Programs
I encourage you to copy the code from the programs in the section entitled Complete Program Listings. Compile and execute the programs. Experiment with the code. Make changes to the code, recompile, execute, and observe the results of your changes.
As I mentioned earlier, for the program named Adapt06, you will need the following class files in addition to the class file for the class named Adapt06:
- AdaptEngine01
- AdaptiveResult
- PlotALot05
For the program named Adapt01a, you will need the following class files in addition to the class file for the class named Adapt01a:
- AdaptEngine01
- AdaptiveResult
- ForwardRealToComplex01
- PlotALot01
- PlotALot03
- PlotALot05
For the program named Adapt02a, you will need the following class files in addition to the class file for the class named Adapt02a:
- AdaptEngine01
- AdaptiveResult
- ForwardRealToComplex01
- PlotALot01
- PlotALot03
- PlotALot07
The source code for the following classes can be found in the lessons indicated:
- ForwardRealToComplex01: Spectrum Analysis using Java, Sampling Frequency, Folding Frequency, and the FFT Algorithm
- PlotALot01: Plotting Large Quantities of Data using Java
- PlotALot03: Plotting Large Quantities of Data using Java
- PlotALot05: Adaptive Filtering in Java, Getting Started
- PlotALot07: An Adaptive Whitening Filter in Java
Summary
In this lesson, I showed you how to write a general-purpose LMS adaptive engine in Java, and how to demonstrate the use of the engine for three different adaptive programs of increasing complexity.
What's Next?
The next lesson in this series will teach you how to write an adaptive line tracking program in Java.
References
In preparation for understanding the material in this lesson, I recommend that you study the material in the following previously-published lessons:
- 100 Periodic Motion and Sinusoids
- 104 Sampled Time Series
- 108 Averaging Time Series
- 1478 Fun with Java, How and Why Spectral Analysis Works
- 1482 Spectrum Analysis using Java, Sampling Frequency, Folding Frequency, and the FFT Algorithm
- 1483 Spectrum Analysis using Java, Frequency Resolution versus Data Length
- 1484 Spectrum Analysis using Java, Complex Spectrum and Phase Angle
- 1485 Spectrum Analysis using Java, Forward and Inverse Transforms, Filtering in the Frequency Domain
- 1487 Convolution and Frequency Filtering in Java
- 1488 Convolution and Matched Filtering in Java
- 1492 Plotting Large Quantities of Data using Java
- 2350 Adaptive Filtering in Java, Getting Started
- 2352 An Adaptive Whitening Filter in Java
Page 1 of 2