A General-Purpose LMS Adaptive Engine in Java

November 29, 2005
By Richard G. Baldwin

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 AdaptEngine01

I 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

Listing 1

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

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;

Listing 3

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.

Listing 4

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

Listing 5

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

Listing 6

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);

Listing 7

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

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

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);

Listing 10

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

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

Listing 12

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);

Listing 13

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]);

Listing 14

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

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