## A computationally efficient moving average filter: Definition and implementation

As discussed in a previous article, the moving average (MA) filter is perhaps one of the most widely used digital filters due to its conceptual simplicity and ease of implementation. The realisation diagram shown below, illustrates that an MA filter can be implemented as a simple FIR filter, just requiring additions and a delay line.

Modelling the above, we see that a moving average filter of length $$\small\textstyle L$$ for an input signal $$\small\textstyle x(n)$$ may be defined as follows:

$$y(n)=\large{\frac{1}{L}}\normalsize{\sum\limits_{k=0}^{L-1}x(n-k)}\quad \text{for} \quad\normalsize{n=0,1,2,3….}\label{FIRdef}\tag{1}$$

This computation requires $$\small\textstyle L-1$$ additions, which may become computationally demanding for very low power processors when $$\small\textstyle L$$ is large. Therefore, applying some lateral thinking to the computational challenge, we see that a much more computationally efficient filter can be used in order to achieve the same result, namely:

$$H(z)=\displaystyle\frac{1}{L}\frac{1-z^{-L}}{1-z^{-1}}\tag{2}\label{TF}$$

with the difference equation,

$$y(n) =y(n-1)+\displaystyle\frac{x(n)-x(n-L)}{L}\tag{3}$$

Notice that this implementation only requires one addition and one subtraction for any value of $$\small\textstyle L$$. A further simplification (valid for both implementations) can be achieved in a pre-processing step prior to implementing the difference equation, i.e. scaling all input values by $$\small\textstyle L$$. If $$\small\textstyle L$$ is a power of two (e.g. 4,8,16,32..), this can be achieved by a simple binary shift right operation.

### Is it an IIR or actually an FIR?

Upon initial inspection of the transfer function of Eqn. $$\small\textstyle\eqref{TF}$$, it appears that the efficient Moving average filter is an IIR filter. However, analysing the pole-zero plot of the filter (shown on the right for $$\small\textstyle L=8$$), we see that the pole at DC has been cancelled by a zero, and that the resulting filter is actually an FIR filter, with the same result as Eqn. $$\small\textstyle\eqref{FIRdef}$$.

Notice also that the frequency spacing of the zeros (corresponding to the nulls in the frequency response) are at spaced at $$\small\textstyle\pm\frac{Fs}{L}$$. This can be readily seen for this example, where an MA of length 8, sampled at $$\small\textstyle 500Hz$$, results in a $$\small\textstyle\pm62.5Hz$$ resolution.

As a final point, notice that the our efficient filter requires a delay line of length $$\small\textstyle L+1$$, compared with the FIR delay line of length, $$\small\textstyle L$$. However, this is a small price to pay for the computation advantage of a filter just requiring one addition and one subtraction. As such, the MA filter of Eqn. $$\small\textstyle\eqref{TF}$$ presented herein is very attractive for very low power processors, such as the Arm Cortex-M0 that have been traditionally overlooked for DSP operations.

## Implementation

The MA filter of Eqn. $$\small\textstyle\eqref{TF}$$ may be implemented in ASN FilterScript as follows:


ClearH1;  // clear primary filter from cascade
interface L = {2,32,2,4}; // interface variable definition

Main()
Num = {1,zeros(L-1),-1}; // define numerator coefficients
Den = {1,-1}; // define denominator coefficients
Gain = 1/L; // define gain ## Practical noise reduction tips for biomedical ECG datasets

In ECG signal processing, the Removal of 50/60Hz powerline interference from delicate information rich ECG biomedical waveforms is a challenging task! The challenge is further complicated by adjusting for the effects of EMG, such as a patient limb/torso movement or even breathing. A traditional approach adopted by many is to use a 2nd order IIR notch filter:

$$\displaystyle H(z)=\frac{1-2cosw_oz^{-1}+z^{-2}}{1-2rcosw_oz^{-1}+r^2z^{-2}}$$

where, $$w_o=\frac{2\pi f_o}{fs}$$ controls the centre frequency, $$f_o$$ of the notch, and $$r=1-\frac{\pi BW}{fs}$$ controls the bandwidth (-3dB point) of the notch.

### What’s the challenge?

As seen above, $$H(z)$$ is simple to implement, but the difficulty lies in finding an optimal value of $$r$$, as a desirable sharp notch means that the poles are close to unit circle (see right).

In the presence of stationary interference, e.g. the patient is absolutely still and effects of breathing on the sensor data are minimal this may not be a problem.

However, when considering the effects of EMG on the captured waveform (a much more realistic situation), the IIR filter’s feedback (poles) causes ringing on the filtered waveform, as illustrated below:

Contaminated ECG with non-stationary 50Hz powerline interference (IIR filtering)

As seen above, although a majority of the 50Hz powerline interference has been removed, there is still significant ringing around the main peaks (filtered output shown in red). This ringing is undesirable for many biomedical applications, as vital cardiac information such as the ST segment cannot be clearly analysed.

The frequency reponse of the IIR used to filter the above ECG data is shown below.

IIR notch filter frequency response

Analysing the plot it can be seen that the filter’s group delay (or average delay) is non-linear but almost zero in the passbands, which means no distortion. The group delay at 50Hz rises to 15 samples, which is the source of the ringing – where the closer to poles are to unit circle the greater the group delay.

ASN FilterScript offers designers the notch() function, which is a direct implemention of H(z), as shown below:

ClearH1;  // clear primary filter from cascade
ShowH2DM;   // show DM on chart

interface BW={0.1,10,.1,1};

Main()

F=50;
Hd=notch(F,BW,"symbolic");
Num = getnum(Hd); // define numerator coefficients
Den = getden(Hd); // define denominator coefficients
Gain = getgain(Hd); // define gain


## Savitzky-Golay FIR filters

A solution to the aforementioned mentioned ringing as well as noise reduction can be achieved by virtue of a Savitzky-Golay lowpass smoothing filter. These filters are FIR filters, and thus have no feedback coefficients and no ringing!

Savitzky-Golay (polynomial) smoothing filters or least-squares smoothing filters are generalizations of the FIR average filter that can better preserve the high-frequency content of the desired signal, at the expense of not removing as much noise as an FIR average. The particular formulation of Savitzky-Golay filters preserves various moment orders better than other smoothing methods, which tend to preserve peak widths and heights better than Savitzky-Golay. As such, Savitzky-Golay filters are very suitable for biomedical data, such as ECG datasets.

### Eliminating the 50Hz powerline component

Designing an 18th order Savitzky-Golay filter with a 4th order polynomial fit (see the example code below), we obtain an FIR filter with a zero distribution as shown on the right. However, as we wish to eliminate the 50Hz component completely, the tool’s P-Z editor can be used to nudge a zero pair (shown in green) to exactly 50Hz.

The resulting frequency response is shown below, where it can be seen that there is notch at exactly 50Hz, and the group delay of 9 samples (shown in purple) is constant across the frequency band.

FIR  Savitzky-Golay filter frequency response

Passing the tainted ECG dataset through our tweaked Savitzky-Golay filter, and adjusting for the group delay we obtain:

Contaminated ECG with non-stationary 50Hz powerline interference (FIR filtering)

As seen, there are no signs of ringing and the ST segments are now clearly visible for analysis. Notice also how the filter (shown in red) has reduced the measurement noise, emphasising the practicality of Savitzky-Golay filter’s for biomedical signal processing.

A Savitzky-Golay may be designed and optimised in ASN FilterScript via the savgolay() function, as follows:

ClearH1;  // clear primary filter from cascade

interface L = {2, 50,2,24};
interface P = {2, 10,1,4};

Main()

Hd=savgolay(L,P,"numeric");  // Design Savitzky-Golay lowpass
Num=getnum(Hd);
Den={1};
Gain=getgain(Hd);


## Deployment

This filter may now be deployed to variety of domains via the tool’s automatic code generator, enabling rapid deployment in Matlab, Python and embedded Arm Cortex-M devices.

## Implementing Biquad IIR filters with the ASN Filter Designer and the Arm CMSIS-DSP software framework

Infinite impulse response (IIR) filters are useful for a variety of sensor measurement applications, including measurement noise removal and unwanted component cancellation, such as powerline interference. Although several practical implementations for the IIR exist, the Direct form II Transposed structure offers the best numerical accuracy for floating point implementation. However, when considering fixed point implementation on a microcontroller, the Direct Form I structure is considered to be the best choice by virtue of its large accumulator that accommodates any intermediate overflows. This application note specifically addresses IIR biquad filter design and implementation on a Cortex-M based microcontroller with the ASN Filter Designer for both floating point and fixed point applications via the Arm CMSIS-DSP software framework.

Details are also given (including a reference example project) regarding implementation of the IIR filter in Arm/Keil’s MDK industry standard Cortex-M microcontroller development kit.

## Introduction

ASN Filter Designer provides engineers with a powerful DSP experimentation platform, allowing for the design, experimentation and deployment of complex IIR and FIR (finite impulse response) digital filter designs for a variety of sensor measurement applications. The tool’s advanced functionality, includes a graphical based real-time filter designer, multiple filter blocks, various mathematical I/O blocks, live symbolic math scripting and real-time signal analysis (via a built-in signal analyser). These advantages coupled with automatic documentation and code generation functionality allow engineers to design and validate a digital filter within minutes rather than hours.

The Arm CMSIS-DSP (Cortex Microcontroller Software Interface Standard) software framework is a rich collection of over sixty DSP functions (including various mathematical functions, such as sine and cosine; IIR/FIR filtering functions, complex math functions, and data types) developed by Arm that have been optimised for their range of Cortex-M processor cores.

The framework makes extensive use of highly optimised SIMD (single instruction, multiple data) instructions, that perform multiple identical operations in a single cycle instruction. The SIMD instructions (if supported by the core) coupled together with other optimisations allow engineers to produce highly optimised signal processing applications for Cortex-M based micro-controllers quickly and simply.

ASN Filter Designer fully supports the CMSIS-DSP software framework, by automatically producing optimised C code based on the framework’s DSP functions via its code generation engine.

## Designing IIR filters with the ASN Filter Designer

ASN Filter Designer provides engineers with an easy to use, intuitive graphical design development platform for both IIR and FIR digital filter design. The tool’s real-time design paradigm makes use of graphical design markers, allowing designers to simply draw and modify their magnitude frequency response requirements in real-time while allowing the tool automatically fill in the exact specifications for them.

Consider the design of the following technical specification:

Graphically entering the specifications into the ASN Filter Designer, and fine tuning the design marker positions, the tool automatically designs the filter as a Biquad cascade (this terminology will be discussed in the following sections), automatically choosing the required filter order, and in essence – automatically producing the filter’s exact technical specification!

The frequency response of a 5th order IIR Elliptic Lowpass filter meeting the specifications is shown below:

This 5th order Lowpass filter will form the basis of the discussion presented herein.

The IIR filter implementation discussed herein is said to be biquad, since it has two poles and two zeros as illustrated below in Figure 1. The biquad implementation is particularly useful for fixed point implementations, as the effects of quantization and numerical stability are minimised. However, the overall success of any biquad implementation is dependent upon the available number precision, which must be sufficient enough in order to ensure that the quantised poles are always inside the unit circle.

Figure 1: Direct Form I (biquad) IIR filter realization and transfer function.

Analysing Figure 1, it can be seen that the biquad structure is actually comprised of two feedback paths (scaled by $$a_1$$ and $$a_2$$), three feed forward paths (scaled by $$b_0, b_1$$ and $$b_2$$) and a section gain, $$K$$. Thus, the filtering operation of Figure 1 can be summarised by the following simple recursive equation:

$$\displaystyle y(n)=K\times\Big[b_0 x(n) + b_1 x(n-1) + b_2 x(n-2)\Big] – a_1 y(n-1)-a_2 y(n-2)$$

Analysing the equation, notice that the biquad implementation only requires four additions (requiring only one accumulator) and five multiplications, which can be easily accommodated on any Cortex-M microcontroller. The section gain, $$K$$ may also be pre-multiplied with the forward path coefficients before implementation.

The ASN Filter Designer can design and implement a cascade of up to 50 biquads (Professional edition only).

### Floating point implementation

When implementing a filter in floating point (i.e. using double or single precision arithmetic) Direct Form II structures are considered to be a better choice than the Direct Form I structure. The Direct Form II Transposed structure is considered the most numerically accurate for floating point implementation, as the undesirable effects of numerical swamping are minimised as seen by analysing the difference equations.

Figure 2 – Direct Form II Transposed strucutre, transfer function and difference equations

The filter summary (shown in Figure 3) provides the designer with a detailed overview of the designed filter, including a detailed summary of the technical specifications and the filter coefficients, which presents a quick and simple route to documenting your design.

The ASN Filter Designer supports the design and implementation of both single section and Biquad (default setting) IIR filters. However, as the CMSIS-DSP framework does not directly support single section IIR filters, this feature will not be covered in this application note.

The CMSIS-DSP software framework implementation requires sign inversion (i.e. flipping the sign) of the feedback coefficients. In order to accommodate this, the tool’s automatic code generation engine automatically flips the sign of the feedback coefficients as required. In this case, the set of difference equations become,

$$y(n)=b_0 x(n)+w_1 (n-1)$$
$$w_1 (n)= b_1 x(n)+a_1 y(n)+w_2 (n-1)$$
$$w_2 (n)= b_2 x(n)+a_2 y(n)$$

Figure 3: ASN filter designer: filter summary.

### Automatic code generation to Arm processor cores via CMSIS-DSP

The ASN Filter Designer’s automatic code generation engine facilitates the export of a designed filter to Cortex-M Arm based processors via the CMSIS-DSP software framework. The tool’s built-in analytics and help functions assist the designer in successfully configuring the design for deployment.

All floating point IIR filters designs must be based on Single Precision arithmetic and either a Direct Form I or Direct Form II Transposed filter structure. As discussed in the previous section, the Direct Form II Transposed structure is advocated for floating point implementation by virtue of its higher numerically accuracy.

Quantisation and filter structure settings can be found under the Q tab (as shown on the left). Setting Arithmetic to Single Precision and Structure to Direct Form II Transposed and clicking on the Apply button configures the IIR considered herein for the CMSIS-DSP software framework.

Select the Arm CMSIS-DSP framework from the selection box in the filter summary window:

The automatically generated C code based on the CMSIS-DSP framework for direct implementation on an Arm based Cortex-M processor is shown below:

As seen, the automatic code generator generates all initialisation code, scaling and data structures needed to implement the IIR via the CMSIS-DSP library. This code may be directly used in any Cortex-M based development project – a complete Keil MDK example is available on Arm/Keil’s website. Notice that the tool’s code generator produces code for the Cortex-M4 core as default, please refer to the table below for the #define definition required for all supported cores.

Automatic code generation of complex coefficient IIR filters is currently not supported.

### Implementing the filter in Arm Keil’s MDK

As mentioned in the previous section, the code generated by the Arm CMSIS-DSP code generator may be directly used in any Cortex-M based development project tooling, such as Arm Keil’s industry standard μVision MDK (microcontroller development kit).

A complete μVision example IIR biquad filter project can be downloaded from Keil’s website, and as seen below is as simple as copying and pasting the code and making minor adjustments to the code.

The example project makes use of μVision’s powerful simulation capabilities, allowing for the evaluation of the IIR filter on M0, M3, M4 and M7 cores respectively. As an added bonus, μVision’s logic analyser may also be used, allowing for comparisons between the ASN Filter Designer’s signal analyser and the reality on a Cortex-M core.

## Fixed point implementation

As aforementioned, the Direct Form I filter structure is the best choice for fixed point implementation. However, before implementing the difference equation on a fixed point processor, several important data scaling considerations must be taken into account. As the CMSIS-DSP framework only supports Q15 and Q31 data types for IIR filters, the following discussion relates to an implementation on a 16-bit word architecture, i.e. Q15.

### Quantisation

In order to correctly represent the coefficients and input/output numbers, the system word length (16-bit for the purposes of this application note) is first split up into its number of integers and fractional components. The general format is given by:

Q Num of Integers.Fraction length

If we assume that all of data values lie within a maximum/minimum range of $$\pm 1$$, we can use Q0.15 format to represent all of the numbers respectively. Notice that Q0.15 (or simply Q15) format represents a maximum of $$\displaystyle 1-2^{-15}=0.9999=0x7FFF$$ and a minimum of $$-1=0x8000$$ (two’s complement format).

The ASN Filter Designer may be configured for Fixed Point Q15 arithmetic by setting the Word length and Fractional length specifications in the Q Tab (see the configuration section for the details). However, one obvious problem that manifests itself for Biquads is the number range of the coefficients. As poles can be placed anywhere inside the unit circle, the resulting polynomial needed for implementation will often be in the range $$\pm 2$$, which would require Q14 arithmetic. In order to overcome this issue, all numerator and denominator coefficients are scaled via a biquad Post Scaling Factor as discussed below.

### Post Scaling Factor

In order to ensure that coefficients fit within the Word length and Fractional length specifications, all IIR filters include a Post Scaling Factor, which scales the numerator and denominator coefficients accordingly. As a consequence of this scaling, the Post Scaling Factor must be included within the filter structure in order to ensure correct operation.

The Post scaling concept is illustrated below for a Direct Form I biquad implementation.

Figure 4: Direct Form I structure with post scaling.

Pre-multiplying the numerator coefficients with the section gain, $$K$$, each coefficient can now be scaled by $$G$$, i.e. $$\displaystyle b_0=\frac{b_0}{G}, b_1=\frac{b_1}{G}, a_1=\frac{a_1}{G}, a_2=\frac{a_2}{G}$$ and etc. This now results in the following difference equation:

$$\displaystyle y(n)=G \times\Big [b_0 x(n) + b_1 x(n-1) + b_2 x(n-2) – a_1 y(n-1)-a_2 y(n-2)\Big]$$

All IIR structures implemented within the tool include the Post Scaling Factor concept. This scaling is mandatory for implementation via the Arm CMSIS-DSP framework – see the configuration section for more details.

### Understanding the filter summary

In order to fully understand the information presented in the ASN Filter Designer filter summary, the following example illustrates the filter coefficients obtained with Double Precision arithmetic and with Fixed Point Q15 quantisation.

Applying Fixed Point Q15 arithmetic (note the effects of quantisation on the coefficient values):

### Configuring the ASN Filter Designer for Fixed Point arithmetic

In order to implement an IIR fixed point filter via the CMSIS-DSP framework, all designs must be based on Fixed Point arithmetic (either Q15 or Q31) and the Direct Form I filter structure.

Quantisation and filter structure settings can be found under the Q tab (as shown on the left): Setting Arithmetic to Fixed Point and Structure to Direct Form I and clicking on the Apply button configures the IIR considered herein for the CMSIS-DSP software framework.

The Post Scaling Factor is actually implemented in the CMSIS-DSP software framework as $$\log_2 G$$ (i.e. a shift left scaling operation as depicted in Figure 4).

Built in analytics: the tool will automatically analyse the cascade’s filter coefficients and choose an appropriate scaling factor. As seen above, as the largest minimum value is -1.63143, thus, a Post Scaling Factor of 2 is required in order to ‘fit’ all of the coefficients into Q15 arithmetic.

### Comparing spectra obtained by different arithmetic rules

In order to improve clarity and overall computation speed, the ASN Filter Designer only displays spectra (i.e. magnitude, phase etc.) based on the current arithmetic rules. This is somewhat different to other tools that display multi-spectra obtained by (for example) Fixed Point and Double Precision arithmetic. For any users wishing to compare spectra you may simply switch between arithmetic settings by changing the Arithmetic method. The designer will then automatically re-compute the filter coefficients using the selected arithmetic rules and the current technical specification. The chart will then be updated using the current zoom settings.

### Automatic code generation to the Arm CMSIS-DSP framework

As with floating point arithmetic, select the Arm CMSIS-DSP framework from the selection box in the filter summary window:

The automatically generated C code based on the CMSIS-DSP framework for direct implementation on an Arm based Cortex-M processor is shown below:

As with the floating point filter, the automatic code generator generates all initialisation code, scaling and data structures needed to implement the IIR via the CMSIS-DSP library. This code may be directly used in any Cortex-M based development project – a complete Keil MDK example is available on Arm/Keil’s website. Notice that the tool’s code generator produces code for the Cortex-M4 core as default, please refer to the table below for the #define definition required for all supported cores.

The main test loop code (not shown) centres around the arm_biquad_cascade_df2T_f32() function, which performs the filtering operation on a block of input data.

Complex coefficient IIR filters are currently not supported.

## Validating the design with the signal analyser

A design may be validated with the signal analyser, where both time and frequency domain plots are supported. A comprehensive signal generator is fully integrated into the signal analyser allowing designers to test their filters with a variety of input signals, such as sine waves, white noise or even external test data.

For Fixed Point implementations, the tool allows designers to specify the Overflow arithmetic rules as: Saturate or Wrap. Also, the Accumulator Word Length may be set between 16-40 bits allowing designers to quickly find the optimum settings to suit their application.

## Extra resources

1. Digital signal processing: principles, algorithms and applications, J.Proakis and D.Manoloakis
2. Digital signal processing: a practical approach, E.Ifeachor and B.Jervis.
3. Digital filters and signal processing, L.Jackson.
4. Step by step video tutorial of designing an IIR and deploying it to Keil MDK uVision.
5. Implementing Biquad IIR filters with the ASN Filter Designer and the Arm CMSIS-DSP software framework (ASN-AN025)
6. Keil MDK uVision example IIR filter project