• Home
• CLSLP Tools
• PES Tools
• Technical Info
• Contact Info

Constrained Least-Squares Linear Phase (CLSLP) FIR Filter Synthesis Algorithm

CLSLP Software Download at the End of Page — Press Here to Jump

Outline

• The CLSLP algorithm is a weighted least-squares technique for the efficient generation of linear-phase FIR filters

  • Filter response is defined by multiple filter-interval definitions

    • 4 standard line interval types are provided:  LinAbs, LinRel, ExpAbs, AbsRel

    • Interval start and stop amplitudes are specified as well as a auxiliary weight factor (default 1)

  • Filter phase is assumed linear by default so is not specified in the filter-segment definitions

  • The filter synthesis operation is computationally efficient

  • Linear-phase filters have a constant time delay of (N-1)/2 samples where N is number of filter coefficients

  • Filters are designed by a series of Frequency-Interval Definition statements.  Each statement is employed in synthesizing a filter in that they represent a weighted square error.  CLSLP algorithm's job is to find the filter coefficient set that minimizes cumulative weighted square fit error.  That is the best linear-phase FIR filter using this criteria.  Any number of filter segments can be specified up to the memory limits of the host processor.

• CLSLP software distribution and installation

  • The CLSLP download is at the end of this web page as a zip-file of source code, CMAKE build scripts, and documentation

  • CLSLP software is written to the C++20 standard and should run efficiently on any platform or (major) operating system that ports C++: certainly Linux (GCC) and MS Windows.  SIMD is also use if the platform supports it for runtime builds (-O3 on Linux).

  • The GSL math library is needed by CLSLP for real-time operation though this is a fairly standard library and easy to install

  • Additionally, the following libraries are used in the code examples below:  GSL Math Library, FFTW, and GNUPLOT.

• The CLSLP algorithm synthesizes real or complex-valued linear-phase FIR filters

  • Real-valued filter frequencies are specified in the 0 to .5 Normalized Hz (NHz) range as -.5 to 0 is symmetric in amplitude (phase is linear by assumption)

  • Complex-valued filter frequencies are specified in the 0 to 1. Normalized Hz (NHz) range

• Computationally efficient filter synthesis

  • e.g. a 501-coeffcient real-valued linear-phase FIR filter synthesized in 1.65 ms on standard desktop PC (-O3 Linux)

• The CLSLP filter synthesis solution problem is in the form of a linear equation M c = d solved for c

  • M is a complex-valued Hermitian-Toeplitz matrix [function of ONLY sample times]

  • d is a complex-valued vector [function of BOTH sample times AND desired filter segment end amplitudes]

  • c is the CLSLP calculated filter coefficient vector of real or complex-valued FIR filter coefficients as appropriate

• The CLSLP filter synthesis algorithm is itself a linear operator  M^-1 d = c

  • This is useful for generating composite filters using the relation M^-1 (d+e) = M^-1 d + M^-1 e

  • Partial CLSLP filter-coefficient sets can be added together to form a new CLSLP filter as long as the sample timing pattern is identical (M matrix invariant)

  • This approach could be useful in adaptive filtering applications where filters are modified by merely adding a correction filter's coefficients enabling fast filter updates

• Filter interval defintions:  Add() for complex-valued filters and AddSymmetric() for real-valued filters

  • For example Filt.Add( CLSLP::eLin_AbsErr,  0, 1, 0, 0, 1e-16 )

    • First parameter is the amplitude segment type:  above, linear with absolute square-error weighting

      • eLin_AbsErr:  Filter amplitude response is modeled as a linear segment, a straight line on a non-log amplitude graph.

      • eLin_RelErr:  Filter amplitude response is modeled as a linear segment, a straight line on a non-log amplitude graph, with relative error measure employed.  With relative error measure, you divide the square-error by the design amplitude squared.  This approach sometimes improves the design of heavily-sloped amplitude responses as it normalizes the error evenly from high to low amplitudes.  NOTE: Amplitudes cannot be 0 with relative-amplitude error measure as this would be division by zero!

      • eExp_AbsErr:  Filter amplitude response is modeled as a exponential segment, a straight line on a log (dB) amplitude plot.

      • eExp_RelErr:  Filter amplitude response is modeled as a exponential segment, a straight line on a log (dB) amplitude plot, with relative error measure employed.  With relative error measure, you divide the square-error by the design amplitude squared.   This approach sometimes improves the design of heavily-sloped amplitude responses as it normalizes the error so that lower-amplitude segments have a reasonable fit.  NOTE: Amplitudes cannot be 0 with relative-amplitude error measure as this would be division by zero!

    • Parameters 2 and 3 are the starting and ending interval frequencies (mod 1.) in NHz.  Best to keep these in the -1 to 1 range though any should work as they end up multiplied by 2π in trigonometric functions during synthesis

    • Parameters 4 and 5 are the starting and ending filter interval amplitudes.  NOTE: design amplitudes of 0 are acceptable for non-relative (absolute) modes ONLY.

    • Parameter 6 is an auxiliary weight that multiplies the calculated square error of this interval (1 is default).  If omitted in the C++ software it is assumed equal to 1.  Obviously 0 will caused the rule to be ignored in optimization.

    • For example AddSymmetric( xx, aa, bb, yy, zz, tt ) is the same as adding the following 2 rules:

      • Add( xx, aa, bb, yy, zz, tt )

      • Add( xx, 1.-bb, 1.-aa, zz, yy, tt )

• NOTE:  A common mistake in using the CLSLP algorithm is leaving frequency intervals undefined.  The CLSLP algorithm is fast though at the expense of testing for errors such as undefined frequency intervals.  A safe workaround for this problem is to add a statement such as the one below to your list of filter segments.  This will draw all frequency intervals toward zero with a low weight making zero the default value.  The reason this happens is that CLSLP is a weighted least-squares optimization technique that requires a linear system solution.  If portions of the frequency domain are undefined, the matrix equations cannot be solved uniquely.  A false flag is returned from GenFilter() if the linear system can not be uniquely solved.

 Filt.Add( CLSLP::eLin_AbsErr,  0, 1, 0, 0, 1e-16 );       // Safety amplitude pull-down

Introduction

The Constrained Least-Squares Linear-Phase (CLSLP) FIR Filter algorithm is a computationally efficient filter synthesis technique distributed here in the form of C++ source code.  CLSLP is not a universal acronym and is used here as the name of the associated software package and as a convenient moniker in general.  CLSLP LPFIR (Linear-Phase FIR) filters are, as the name implies, linear phase.  This means that CLSLP phase response is a constant time delay of (N-1)/2 samples where N is the number of filter coefficients.  It's easy to show that cascaded linear-phase FIR filters are themselves linear phase so this quality is preserved even in arbitrarily large filtering networks when this discipline is employed.  With the inherent speed of the CLSLP Filter Synthesis Algorithm exotic processing schemes such as adaptive filtering systems are practical even on modest processing platforms.

Examples of CLSLP Algorithm Use

The following software snippets should illustrate use of this software by example.  This download includes a full source-code build and test in subdirectory CLSLP/ as well as source-code builds for the examples used in the documentation.  This code, as it's written in C++20, should run on most major operating systems.  Additionally, if the CPU supports the SIMD instruction set, then the release mode (-O3) build should employ it if possible.

Example 1

Example 1 is a 501-coefficient, real-valued, linear-phase FIR (LPFIR) filter synthesized by CLSLP in 1.65 ms, or about 3.30 μS/coef, on a standard desktop PC.  The C++ commands used to synthesize this real-valued CLSLP filter are

The amplitude response of this filter is

Example 2

Example 2 is a 1024-coefficient, complex-valued, linear-phase FIR (LPFIR) filter synthesized by CLSLP in 6.01 ms, or about 5.87 μS/coef, on a standard desktop PC.  The C++ commands used to synthesize this CLSLP filter are

The amplitude response of this filter is

Example 3

Example 3 is a 2049-coefficient, complex-valued, linear-phase FIR (LPFIR) filter synthesized by CLSLP in 21.31 ms, or about 11.85 μS/coef, on a standard desktop PC.  The C++ commands used to synthesize this CLSLP filter are

The amplitude response of this filter is

Undefined Frequency intervals

A common mistake using the CLSLP algorithm is leaving frequency intervals undefined.  The entire frequency interval from 0 to 1 NHz must be specified in order to get a unique (valid) filter solution.  If AddSymmetric() commands are used it is only necessary to cover 0 to .5 NHz.  It's fine to define frequency intervals multiple times.  Unusually one definition will have a larger weight therefore will take precedence in the coefficient solution.  The default command in the next paragraph is an excellent example.  If any frequency interval is undefined, the amplitude will tend to zero with a error weight factor of 1e-16 (see example in next paragraph).  Any other specific interval definition will take precedence as it will have a normal weight of 1 (default) thus dominating the optimization.

The CLSLP algorithm is fast though at the expense of testing for errors such as undefined frequency intervals.  A safe workaround for this problem is to add a statement such as the one below to your list of filter segments.

Filt.Add( CLSLP::eLin_AbsErr,  0, 1, 0, 0, 1e-16 );         // Safety amplitude pull-down

This will draw all frequency intervals toward zero with a low weight making zero the default amplitude value.

CLSLP Software Download

The zip file below contains a sample filter synthesis example as well as all the source code to embed CLSLP in your own design.  This software is written in the C++20 language and should run on any major operating system (new C++ feature).  A standard CMAKE build scheme is used.  Sample Linux command files are included if you need a refresher on CMAKE builds.  This download should have everything you need to embed this algorithm for your own application.  All this code is released on a Standard BSD 3-Clause License. 

The Original Asilomar Paper on CLSLP Algorithm [most math detail]

During the conversion of the MATLAB code to C++, an error was made in converting the indices from MATLAB's 1-based to the C++ 0-based numbering. Change n to (n-1) in example equations (30), (33), (37), (39), (41), and (43).

Constrained Least-Squares Design and Characterization of Affine Phase Complex FIR Filters (CLSLP).pdf

Additional Documentation

Documentation for CLSLP is provided in either of the two documents below.  The first file is a basic PDF file describing the algorithm in general in general terms

   CLSLP FIR Filter Synthesis.pdf

This second document contains the same information as the first document plus additional material: the published paper on the technique (math details), annotated C++ listings, as well as filter synthesis examples

   CLSLP FIR Filter Synthesis Software and Docs.pdf