WorksEngineering
Adaptive Filtering With Reduced Computational Complexity Using SOPOT Arithmetic
Abstract
Implementing finite impulse response (FIR) adaptive filters by employing the sums of signed-powers-of-two (SOPOT) arithmetic may lead to simpler hardware and consequently reduced power consumption. In this paper, one evaluates the effects of SOPOT arithmetic on the adaptive filter's recursion algorithms. The filters' coefficients and algorithms' underlying variables are fully operated using SOPOT arithmetic in the whole iterative process. More specifically, one evaluates convergence rate, numerical stability, and accuracy since using few signed-powers-of-two (SPT) terms propagates numerical errors during the adaptive cycle that may impair the algorithm behavior. The SOPOT approximations are obtained through the technique known as Matching Pursuits with Generalized Bit-Plane (MPGBP) algorithm, with notable cost-performance trade-off and low computational complexity. Results are provided for the Least-Mean-Squares (LMS), the Normalized Least-Mean-Squares (NLMS) and the Recursive-Least-Squares (RLS) algorithms, considering adaptive filters employed for system identification and change detection.
Introduction
The urge for more efficient resource management drives many research fields of engineering. This work explores a way to reduce power consumption in adaptive filtering. This is relevant for the development of more power-efficient devices for smart cities scenarios [1] and IoT (Internet-of-Things) applications for healthcare, smart building, and automotive purposes [2, 3].
In particular, representing filter coefficients as sums of signed powers-of-two (SOPOT) instead of using high-precision floating-point coefficients allows efficient hardware implementation [4, 5, 6, 7, 8]. This is due to the multiplierless nature of SOPOT arithmetic, which allows filter coefficients to be generated from a combination of shifts, additions, and subtractions of signed powers-of-two (SPT) terms, i.e., no multiplier is required whereas still letting to program/update the filter coefficients on the fly [9]. Moreover, SOPOT representation has been applied in the
This work was partially supported by Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) and by Fundação Carlos Chagas Filho de Amparo à Pesquisa do Estado do Rio de Janeiro (FAPERJ).
implementation of several finite impulse response (FIR) filters [4, 5, 6, 7, 8, 10]. In addition to the aforementioned examples, a 2D wavelet transform was designed using SPT in [11]. In this work, we consider using SPT for implementing the Least Mean Squares (LMS), the Normalized Least Mean Squares (NLMS) and the Recursive Least Squares (RLS) with low complexity (a proxy for energy efficiency) FIR adaptive filters.
Work on energy-efficient FIR adaptive filter approximations has begun around using many different strategies. Recently, in [12], approximately distributed arithmetic circuits were employed for fixed-point finite impulse response adaptive filter design. The so-called Delayed LMS (DLMS), presented in [13], uses registers between the FIR and the learning part, reducing some demands. In [14], authors represent the error signal using sign-modulus representation to reduce the adaptive feedback switching activity in DLMS. An LMS-based algorithm using SPT terms was proposed in [15]. In [16], some hardware considerations for SPT-based sign-LMS algorithms were discussed. One sees that a long period has passed without many advances in this matter. This paper generalizes previous initiatives using a common design procedure for SOPOT implementation in adaptive filters. We employ the Matching Pursuits with Generalized Bit-Planes (MPGBP) [10] algorithm not only for the SOPOT approximation of coefficients originated from adaptive filtering but also for the auxiliary variables that take part in the iterative numerical process for the design of the SPT-based adaptive filter. The MPGBP algorithm has the capability of limiting the amount of SPT terms employed to approximate a vector and also the bit-plane depth of its numeric representation, thus presenting advantages when dealing with low-complexity designs. A comparison between different methods for the acquisition of multiplier-less non-uniform channel filters is presented in [17], and among them, the MPGBP algorithm has resulted in designs of smaller complexity using fewer resources. The SOPOT representation is effective for the design of multiplier-less fixed FIR filters [10], and for RLS adaptive filters [18].
This paper unveils the effects of the SOPOT approximations on adaptive filtering, leading to the so-called SPT-based adaptive filters. This work broadens the framework of SPT-based adaptive filtering proposed in [18] by extending it to LMS and NLMS algorithms and providing deeper and more comprehensive performance analysis. It also includes the change detection scenario, which is applicable in spectrum sensing, more specifically in spectrum hole detection [19, 20]. Filter coefficients evolve/adapt using SOPOT arithmetic. The adaptive filter is designed using SOPOT arithmetic, differently from the approach in [10] where approximation takes place after filter design. This might present numerical instability due to the inherent finite precision of the SOPOT representation. Consequently, this issue is investigated in this work. In principle, the fewer SPT terms are employed (i.e., the less dense are the SOPOT approximations), the more coarsely are the value approximations, and the larger is the expected impairment. Thus, the quantization/approximation effects are assessed using the three well-known adaptive filters, the LMS, NLMS, and RLS. The resulting adaptive filters fully operate in SOPOT arithmetic and are referred to as Signed Power-of-Two Least Mean Squares (SPT-LMS), Signed Power-of-Two Normalized Least Mean Squares (SPT-NLMS), and Signed Power-of-Two Recursive Least Squares (SPT-RLS). Results for system identification and change detection applications are provided and are compared with the high precision numeric representation and complexity equivalent fixed-point versions.
This work is organized as follows. Section II brings the adaptive filters used. Section III discusses the SOPOT numeric representation and the MPGBP algorithm used for obtaining SOPOT approximations, as well as some preliminary results on the impact of these approximations upon adaptive filters performance. In Section IV, the SPT-based adaptive filters are presented along with their implementation aspects, issues, and proposed solutions. In § 7, simulation results are presented in two different applications: system identification and change detection. Section VI presents the concluding remarks.
The Adaptive Filters
Digital filters are commonly represented by a vector containing the coefficients for a order filter. Filters may have fixed coefficients, but some applications require filters whose coefficients may change, i.e., adapt. These are called adaptive filters. A diagram for adaptive filtering is presented in Figure 1, where indexes the signal samples. An input signal is filtered, resulting in the output signal . The output signal is then subtracted from the desired signal resulting in the error signal . An adaptive algorithm governs the update process of the filter coefficients to minimize the error power.
Figure 1. Block diagram for a general adaptive filter, where the filter coefficients are updated using an adaptive algorithm based on the error signal.
There are many well-known adaptive algorithms [21]. In this work, we consider the LMS, NLMS, and RLS adaptive filters, which are briefly presented in the following.
LMS Algorithm
The LMS is one of the most used algorithms for adaptive filtering. It reduces the mean squared error
at the filter output as increases by computing a simplification of the gradient vector derived using an appropriate change on the objective function [21]. For the LMS,
where is an -length column-vector containing the adaptive filter coefficients for the -th iteration, is the tapped delay line for the input signal in the -th iteration also represented as an -length column vector. (3) is the update rule and is the step-size, which is used to adjust the convergence speed and stability of the algorithm and stands for the transpose operator.
NLMS Algorithm
Aiming primarily at faster convergence in the LMS algorithm a variable step-size is employed, this is achieved with a normalization of the tapped delay line in (3). The resulting update rule for the NLMS algorithm is
where is the NLMS convergence factor defined in the interval and the parameter is a constant introduced to avoid division by zero [22].
RLS Algorithm
The RLS algorithm aims to minimize, , the sum of the squared error (difference between the desired signal and the filter output ) using a recursive method, given by
where is defined as an exponential weighting factor, ranging from , also called forgetting factor since the distant past effect is turned negligible with the constant updating (as increases). Despite the fast convergence, the RLS algorithm has higher computational complexity [21] and some stability problems in limited-precision implementations [23, 24]. The RLS algorithm is
where estimates the inverse Hessian, it is initialized with and is an auxiliary column-vector introduced to reduce the computational burden [21].
The SOPOT Representation via MPGBP
The SOPOT numerical representation is similar to the well-known canonical-signed-digit (CSD) representation. The CSD representation consists of a ternary system that minimizes the number of non-zero digits by assuring that no non-zero CSD is adjacent to one another. In this representation, there is a higher probability of employing fewer non-zero digits (active bits) than in a usual 2’s complement representation for -bit word length [25]. However, in the SOPOT approximation, only a certain number of non-zero terms are kept, thus further reducing the number of active bits. The number of active bits defines the computational complexity of the multiplication operation. Since it bounds the number of shift operations required for the multiplication process, the greater the number of active bits, the greater the multiplication’s computational burden.
The SOPOT approximation of a number is
where, is the word-length (bit-plane depth) of the numerical representation, is −1, 0 or 1, and defines the bit-plane. Figure 2 illustrates (11). If is an -length vector , the -th element is approximated by the SOPOT,
Figure 2. A SOPOT representation, where is the word-length, is the highest absolute value that an SPT term can assume, and the lowest (in Equation (11), ).
There are many techniques to obtain SOPOT approximations. But the MPGBP algorithm [10] presents the advantages of being fast and of low complexity to approximate vectors (a set of coefficients). At the same time, it allows imposing both the word length and, if desired, also a maximum number of non-null terms for the whole vector. In the MPGBP algorithm, described in Algorithm 1, a vector is approximated as
where is a code-word from a dictionary and is the cardinality of the dictionary. In Equation (13), is the selected code-word index in the -th decomposition iteration. Defining code-words having coordinates −1, 0 and 1, one has that has coordinates that value , 0 or . Furthermore, representations employing less terms are obtained if the number of non-null coordinates per code-word () equals [10], the operator returns the highest integer smaller than the operand. Thus, the MPGBP algorithm is a fast technique to approximate vectors (and matrices [26]) successively. In our results, we use the MPGBP to obtain the initial representations of the input and filters for the adaptive processes.
(13) is a particular case of (12), the code-words determine the weights for all the vector coordinates in each bit-plane conjointly. Algorithm 1 illustrates this approximation process for the vector . One can set up the algorithm to use at most SPT terms (active bits limitation) or the deepest bit-plane value (the largest numeric precision).
Given that , numeric representation in SOPOT are not unique. Since the objective is acquiring the approximation using the least SPT terms, a post-processing operation reduces the number of SPT terms. More details on this so-called common-terms reduction step are presented in [10].
SPT-Based Adaptive Filtering
Adaptive filters that use only the SOPOT arithmetic are evaluated. They are referred to as SPT-LMS (Signed Power-of-Two Least Mean Squares), SPT-NLMS (Signed Power-of-Two Normalized Least Mean Squares), and SPT-RLS (Signed Power-of-Two Recursive Least Squares). The SOPOT representation imposes some numeric restrictions due to its finite accuracy and precision characteristics (accuracy is limited by the maximum number of active SPT terms and precision by the deepest bit plane). These characteristics grant the computational restriction. Thus the trade-off analysis is necessary. In our proposition, Algorithm 1 is used to approximate the input signal in the tapped delay line, and the SOPOT arithmetic is preserved through the hole adaptive filtering process, including the coefficient update step. This implementation is better detailed in the following subsection.
Algorithm 1 MPGBP for Vector Approximation
input: vector $\mathbf{v}$ of length $N$, and a maximum number of SPT terms $M_{\max}$, maximum bit-depth $B_{\max}$
output: the pairs of $\mathbf{c}_{j_i}$ (code-word) and $k_i$ (its associated bit-plane), the bit-depth $B$ and the number of total SPT terms $M$
initialization:
1: $i \gets 1$, $\mathbf{r}_1 \gets \mathbf{v}$, $M \gets 0$, $B \gets 0$, $P \gets \left\lceil\sqrt{N}\right\rceil$
2: while $M < M_{\max}$ and $B < B_{\max}$ do
code-word search:
3: Sort coordinates of $\mathbf{r}_i$ in decreasing order of their absolute values in $\mathcal{I}_P$
code-word update:
4: $\mathbf{c}_{j_i} \gets 0$
5: for $p \in \mathcal{I}_P$ do
6: if $r_{j,p} > 0$ then
7: $\mathbf{c}_{j_i,p} \gets 1$
8: else
9: $\mathbf{c}_{j_i,p} \gets -1$
10: end if
11: end for
MPGBP data update:
12: $k_i \gets \left\lceil-\log_2\left(\frac{4}{3}\sum_{k\in\mathcal{I}_P}|r_i(k)|\right)\right\rceil$
13: $\mathbf{r}_{i+1} \gets \mathbf{r}_i - 2^{-k_i}\mathbf{c}_{j_i}$
14: $i \gets i+1$
15: $B \gets \max_i k_i$
16: $M \gets \sum_i\sum_n |c_{j_i,n}|$
17: end while
18: Common-terms reduction (for details see {citep}`[10]`)
Implementation Aspects
Input Signal Representation
If the input signal of an adaptive filter is represented correctly, then it is possible to obtain a reduction on the computational burden of the process [15, 27, 28]. Furthermore, the SOPOT approximation via MPGBP is proposed in this work. Thus Algorithm 1 applies to the tapped delay line that inputs the adaptive filters. Then, SOPOT arithmetic applies to the whole process.
Multiplications
Using the notation in equation (11) one clearly sees that the multiplication of two SOPOT scalars and provides
and the multiplication process turns into additions of SPT terms exponents. In order for the multiplication of two SOPOT-represented scalars having the same amount of SPT terms as its predecessors, the highest exponents resulting from equation (14) are retained.
Inner Product
An inner product is the sum of element-wise multiplications of vectors. Therefore, this element-wise multiplication is defined as the key-operation in the inner and matrix products. As one observes from (1) to (10), the LMS, NLMS and RLS algorithms require computing inner products between matrices and vectors. Let and be two SOPOT-represented line vectors of length , then accumulates sums as the one in equation (14). The product of matrix by an -length vector and the product between two matrices are implemented using and inner products, respectively.
Denominator Inversion
Equations (4) and (9) require division operations for the NLMS and RLS algorithms. Performing division when the denominator is in SOPOT is not trivial. Therefore, we propose to approximate the inverted denominator and obtain the division by means of a multiplication. Using a limited number of the -terms in the Maclaurin Series for
one can approximate the inversion for a given denominator . If the denominator is not in the valid interval of the Maclaurin Series, we propose to consider only the most significant SPT term for the inversion, i.e., for a given scalar , with , the approximation results in , the greater the difference between and , the better this approximation is.
Complexity Constraint
One can limit the word length by limiting (which denotes the lowest exponent of the sum) and the quantity of SPT terms. These restrictions are key elements for the complexity reduction and the representation precision, therefore having a major influence on the quantization error. For example, when representing a value, limits the lowest exponent of the SPT term to be an integer within , limits its highest exponent, and is defined as the equation . Although, in each operation, the least significant SPT terms are ignored, keeping only the largest terms. This truncation maintains the complexity restriction but may produce numerical errors on the adaptive filtering process [23, 24]. Therefore, to measure the complexity of different SOPOT approximations of an -length filter, we define , the ratio between the number of active SPTs and the filter length.
SOPOT Quantization Effects on Adaptive Filters
Aiming to certify that the SOPOT quantization used in the RLS algorithm does not jeopardize stability, some analyses are presented that evaluate the impact of the numerical restriction of the approximations in the adaptive filter.
Limited-precision Effects
Quantized adaptive filtering implementations are only possible if the quantization error has zero mean [23, 24]. For some quantization methods, this result is trivial, although it is not evident for the SOPOT implementation, and thus, some analyses are required.
For a given vector source , the expected value of the quantization error is
If the expected value for each coordinate in is zero and the vector is approximated using the MPGBP algorithm, then
where each has non zero coordinates (consisting of and ). If the probability of the codewords coefficients is the same independently of the exponent , i.e., independently of the magnitude of the vector to be approximated [29], thus
By definition/construction of the codewords, if the vector source is uniformly distributed in [29].
A numerical analysis is now presented. In this analysis, the MPGBP algorithm is used to approximate a series of -length random vectors following Gaussian (zero mean and unitary variance) distribution using at most SOPOT in the vector approximation. The process is repeated exhaustively () in a Monte Carlo method. Table I presents some statistical analyses of the quantization error for different lengths and complexity constraints. Endorsed by the Law of Large Numbers (LLN), one can estimate the mean vector of the distribution using,
| 4 | 12 | 16 | |
| 3 | 1.99 | 1.29 | 2.06 |
| 7.02 | 1.22 | 1.03 | |
| 5 | 1.02 | 3.33 | 3.74 |
| 3.48 | 4.09 | 3.27 | |
| 7 | 1.58 | 6.92 | 9.10 |
| 1.74 | 1.30 | 9.78 | |
| 10 | 7.88 | 2.29 | 1.38 |
| 1.89 | 7.78 | 5.24 |
Table I. Expected value () and variance () of the quantization error stemming from the MPGBP approximation algorithm.
where indexes the trials. In Table I the expected values correspond to the largest absolute value among the means of the coordinates of . The variance vector is estimated using
Table I also presents the more significant value among the coordinates of the variance vector.
The values in Table I are very small, and the more SPT terms, the smaller the variance. These results suggest that the MPGBP algorithm is capable of approximating vectors without bias. Figure 3 presents the distribution of the quantization error in each element of a 4-element () vector source stemming from SOPOT approximation using the MPGBP algorithm with complexities , 2, 3 and 4. For high restraint in complexity (), one can observe that the distribution tends to a uniform, and the mean does not tend to zero. However, as we allow more SPT terms, the quantization error mean approaches zero, and the variance decreases.

Figure 3. Histogram, with 10000 bins, of the quantization error originated from the SOPOT approximation using the MPGBP algorithm. Considering the approximation of a 4-element vector source with , 2, 3 and 4.
Maximum Complexity Restriction
In order for the adaptive filter to converge, the zero-mean quantization error must be kept throughout the iterations. To constraint complexity, approximations are truncated after every operation, preserving only the most significant SPT terms of the SOPOT. Arguably, the elimination of SPT terms that are randomly negative or positive does not change the zero-mean quantization error. Since i) the construction of the codewords sustains values or in every coordinate; and ii) for a uniformly distributed vector source, the residues of each MPGBP iteration result in symmetric distributions. Therefore, it is expected that the complexity constraint spreads the quantization error distribution shown in Figure 3 without changing its mean.
Simulation Results
The proposed SOPOT adaptive filters are applied in two different scenarios. Firstly, the SOPOT filters are implemented, along with fixed-point (another hardware known for its low computational complexity) filters, in a classical system identification scenario (Figure 4), it is intended to evaluate gaps in the performance between both implementations. Secondly, a change detection application evaluates the impact of the approximation on the detector’s performance.
Figure 4. System identification scenario block diagram: the adaptive filter tries to mimic the effects of the unknown system in and therefore can be used to identify it.
System Identification Application
In this application, adaptive filters are used to identify a randomly generated normalized vector, which represents a FIR filter and is used as the unknown system. This classical application can help evaluating the filter’s convergence according to the imposed complexity restraint and the achievable accuracy in the system identification problem. As in Figure 4, the input signal is a vector following a Gaussian distribution. The additive noise is Gaussian white noise, with adjustable SNR. The adaptive filter will try to mimic the unknown system’s effects in the input signal, and therefore the output signal is an estimate for . Since and are uncorrelated, the adaptive filter is not able to nullify its effects, thus the error signal is limited by the SNR in its reduction. The filters are of 3rd order, i.e., they are also 4-elements vectors, . The SNR is set by adjusting the noise power as follows
where is the desired signal to noise ratio, in dB, is the misadjusted noise signal, and the noise signal is the adjusted noise signal.
The adaptive filters are exhaustively trained with 10000 (ten thousand) iterations each, and a Monte Carlo method is applied with 150 repetitions. The experiments require configuring the parameters of the adaptive filters. The parameters for the SPT-based implementation are shown Table II, while for the fixed-point the parameters are , , , and . The SPT filters and the fixed-point filters use different values for in the RLS algorithm. The difference arises from the need to have all values expressed as SOPOTs for the SPT filters. For both the SPT and fixed-point algorithms, the parameter values were empirically adjusted for best performance, i.e., the smallest MSE (equation (22)). We note that this parameters are for fixed step-size algorithms; further work is necessary to tune them for variable step-size algorithms.
Performance Evaluation
Performance Evaluation: To evaluate the algorithm’s convergence after the numeric approximation, one can evaluate the mean squared error (MSE) curve, which is an estimate for the MSE using the filter’s error signal through the Monte Carlo process. This curve is calculated as follows,
where is the error signal for -th iteration of the -th Monte Carlo repetition (there are 150 repetitions). The MSE curves of SPT-LMS, SPT-NLMS and SPT-RLS algorithms for different SOPOT complexities () and fixed-point word lengths are presented in Figure 5, Figure 6 and Figure 7, respectively. In this case, filters are trained for SNR = 10 dB. Observe that these curves are two-dimensional since, besides complexity or word length, there is also the iteration axis. They allow us to verify that the error signal evolution is stable throughout the iterations, i.e., the filter does not diverge through the entire process. One may also notice that the fixed-point performance degrades in word lengths under 7 bits, while the SPT variation can already perform quite well with only 3 SPT terms.

Figure 5. MSE curve evolution with SNR = 10 dB (a) for different complexities, , in the SPT-LMS and (b) for different word lengths in the fixed-point LMS.

Figure 6. MSE curve evolution with SNR = 10 dB (a) for different complexities, , in the SPT-NLMS and (b) for different word lengths in the fixed-point NLMS.

Figure 7. MSE curve evolution with SNR = 10 (a) for different complexities, , in the SPT-RLS and (b) for different word lengths in the fixed-point RLS.
| LMS | NLMS | RLS | |||
| 1 | (0.075) | (0.13) | 0 () | (0.975) | (0.06) |
| 2 | (0.075) | (0.13) | 0 () | (0.975) | (0.06) |
| 3 | (0.075) | (0.13) | 0 () | (0.96) | (0.06) |
| 4 | (0.075) | (0.13) | 0 () | (0.96) | (0.06) |
| 5 | (0.075) | (0.13) | 0 () | (0.955) | (0.06) |
| 6 | (0.075) | (0.13) | 0 () | (0.954) | (0.06) |
| 7 | (0.075) | (0.13) | 0 () | (0.96) | (0.06) |
| 8 | (0.075) | (0.13) | 0 () | (0.954) | (0.06) |
Table 2. TABLE II. Parameters used in the SPT-based adaptive filter algorithms. The original floating-point values are shown in parentheses.
The MSD is calculated as the average squared distance between the filter coefficients -norm and the unknown system’s coefficients -norm through the Mote Carlo process. It presents the deviation between adaptive filters and unknown system coefficient norm and can be calculated as
where is a -element vector representing the adaptive filter coefficients in the -th iteration for the -th repetition of the Monte Carlo and is the 4-element vector representing the unknown system’s impulse response.
Figures 8, 9 and 10 compare the SPT-based adaptive filters with different complexities () with a fixed-point of 16-bit fixed-point precision. In this case, filters are trained for SNR = and 10 . These results compare the capability of the different SOPOT complexity setups to represent numbers. Despite the limitation in the number of SPT terms, the active terms can move freely through the allowed bit-plane range enabling higher numerical precision with low computational complexity implementations. Filters with lower complexity present slightly inferior performance, but this difference is mitigated under low SNR.

Figure 8. MSD for the SPT-LMS with different complexities, (SPT terms per coefficient), compared with a 16-bit fixed-point LMS, for (a) SNR = and (b) SNR = 10 .

Figure 9. MSD for the SPT-NLMS with different complexities, (SPT terms per coefficient), compared with a 16-bit fixed-point NLMS, for (a) SNR = and (b) SNR = 10 .
Figure 10. MSD for the SPT-RLS with different complexities, (SPT terms per coefficient), compared with a 16-bit fixed-point RLS, for (a) SNR = dB and (b) SNR = 10 dB.
SPT-based and Fixed-Point Filters on Equal Terms
The complexity of the RLS algorithm is proportional to . On the other hand, the complexities of the LMS and NLMS algorithms are proportional to and , respectively.
Let the fixed-point word length be bits. The multiplication between two fixed-point numbers requires that one be shifted depending on the non-null terms of the other. Then, the resulting shifted binary words must be added, resulting in a -bit word (rounded accordingly to return a -bit word). Assuming a sufficient long word and that the encoded values are distributed symmetrically over the fixed-point range, the average number of active bits per fixed-point word is . This reduces the complexity of the multiplication between two fixed-point numbers to shifts of -bit words and additions of possibly -bit words.
On the other hand, a SOPOT representation using SPT terms and -bit exponents requires at most additions (distributive property) of -bit words – this is a worst-case scenario analysis – for the same multiplication operation. Regardless of storage requirements, one may compare the complexities of both representations for the multiplication of two numbers using the amount of necessary “1-bit sums”. Consequently, the fixed-point multiplication uses sums while the SOPOT multiplication uses sums.
Therefore, to evaluate SOPOT and fixed-point filters under similar computational complexities, the value
presents the fixed-point word length counterpart for a given number of SPT terms .
Figures 11, 12 and 13 present a comparison of SOPOT filters and its fixed-point counterparts of same estimated complexity. The complexity is estimated considering only the multiplications. As expected, the SPT adaptive filters outperform their fixed-point counterparts. The difference
increases at lower complexities, as in the cases involving the 3-SPT filters and the 7-bit fixed-point filters. For the LMS and RLS algorithms, the fixed-point variation cannot adapt itself while the SPT filters have reasonable performance.

Figure 11. MSD for the SPT-LMS with different complexities, (SPT terms per coefficient) compared with fixed-point of estimated similar complexity, for (a) SNR = dB and (b) SNR = 10 dB.

Figure 12. MSD for the SPT-NLMS with different complexities, (SPT terms per coefficient) compared with fixed-point of estimated similar complexity, for (a) SNR = dB and (b) SNR = 10 dB.
Sparse System Identification
In many scenarios, such as channel equalization, echo cancellation and system identification, the unknown systems can present sparse impulse response, containing only few large valued coefficients among many zero (or near zero) valued coefficients [30], [31]. Thus, we show results for a sparse system identification problem. In this scenario, depicted in Figure 4, the unknown system is a FIR filter with 16 coefficients, from which only 4 are non-zero and randomly set. The SNR is set to 30 dB, and the filter parameter settings are presented in Table III. The filters are constrained to SPT per coefficient, using a 16-SPT wordlength with the maximum exponent of 3, i.e., is the highest value an SPT can get.

Figure 13. MSD for the SPT-RLS with different complexities, (SPT terms per coefficient) compared with fixed-point of estimated similar complexity, for (a) SNR dB and (b) SNR dB.
| Parameter | SOPOT (Value) |
Table 3. Parameter settings for the different adaptive filters used in the identification of the sparse system.
The results are displayed in Figure 14 and Figure 15, these are averages using 50 Monte Carlo repetitions. One can observe in Figure 14 the evolution of the MSE through the iterations. The SPT-RLS filter shows slightly faster convergence while there is no visible difference between the SPT-LMS and SPT-NLMS convergence time. In the previous section, similar behavior was observed in the MSD values for the SPT-LMS, SPT-NLMS, and SPT-RLS, with the latter attaining the smaller MSD. The SPT implementation still grants to the RLS relative gains to the LMS and NLMS.
Figure 14. MSE evolution for identifying a sparse unknown system using the SPT-based adaptive filters, the results correspond to a Monte Carlo process of 50 repetitions.
Figure 15. Filter coefficients over the last iteration. The presented values are the average of the coefficients resulting in the last iteration in each of the 50 repetitions of the Monte Carlo process.
One observes a small difference between the results for the SPT-LMS and SPT-NLMS in Figure 14. This indicates that the condition number of the input correlation matrix is not large enough to induce a significant difference in their convergence rates [32]. A larger condition number would speed up the convergence of the SPT-RLS algorithm, with the risk of increasing the misalignment in the system identification or, in the worst-case scenario, leading to numerical instability problems due to ill-conditioning [33], [34].
Figure 15 compares the resulting filter coefficients of each SPT-based adaptive filter and the unknown system. This phenomenon is accentuated in the fifth element of the coefficient vector. One expects a mismatch in the values of the coefficients due to the high constraint in complexity. It is noticeable that despite that, the SPT-based filters are capable of mimicking the unknown system’s impulse response.
Change Detection Application
Change detection is applicable in different engineering areas, ranging from network traffic monitoring [35] to fault detection of a system [36]. Change detection can be approached using adaptive filters as in Figure 16. By using the SOPOT approximations, precision is compromised for the least costly hardware. Nevertheless, this presents possible applications in devices with a limited power source, demanding less energy in calculations. To evaluate possible impacts on change detection applications, one considers adaptive-filters-based spectrum sensing [20]. One considers the sensing of a band-limited signal in the baseband. The signal originates from a discrete white Gaussian noise signal at 1 Msamples/sec, low-pass filtered using the time-truncated sinc resulting in a limited-band of 142.9 . This signal is a model for generic baseband signals, such as OFDM signals. It is transmitted through a Rayleigh fading channel modeled by Jakes’ model with a Doppler frequency of 104.2 . We highlight that this results in a correlated signal. At last, we consider a varying SNR in the detector input.
Figure 16. Change detection block diagram: the adaptive filter is used as a predictor, the prediction error signal is then fed to the change detector block.
Following the previous analyses, we compare the performances of fixed point and SOPOT adaptive filters having different complexities. The filters have a short length () and the same complexity (or number density) restrictions as in the previous section. The SOPOT filters employ 3 (low number density), 4 (medium number density), and 5 (high number density) SPTs. The corresponding fixed point word lengths are 7, 9, and 11. Figure 16 shows that for the change detection, it is necessary to fix a threshold. Based on preliminary tests, we test the change detection framework using 27 different values from to in steps of . Therefore, forcing its representation to be within the considered arithmetic restrictions. This experiment does not aim to find the best change detector but instead evaluate the performance compromises using the different implementations.
Figure 17 shows the output for the fixed point and SOPOT change detectors variations under the three complexity constraints. The three graphs on the top correspond to the fixed point implementation and the bottom to the SOPOT implementation. As one notes, the SOPOT implementation delivers an output that is more similar to the actual state of the channel (its occupancy). That is, the SOPOT implementation detects channel occupancy better than the fixed-point implementation does. We apply this procedure to an ensemble of 20 signals (drawn as previously explained, the graphs in Figure 17 correspond to the 18th signal). Figure 18 synthesizes the results in terms of true positive (correct channel occupancy), true negative (correct channel vacancy), false positive (channel vacant and detected as occupied), and false negative (channel occupied and detected as vacant). The values depend on the threshold (horizontal-axis). The performances of the fixed point implementations of low and medium complexities are the same and incapable of providing any useful detection results. On the other hand, the SOPOT implementation provides useful results even at low number density. As the number density increases, the SOPOT implementation has a smoother behavior with the detection threshold.

Figure 17. Example of the change detection output using fixed point (top) and SOPOT (bottom) implementations.
Figure 18. Performance of the change detectors using fixed point and SOPOT implementations.
Conclusion
Low computational complexity adaptive filters are feasible using the SOPOT arithmetic. Despite the SOPOT approximation of the signal in the filter’s tapped delay line and the maintenance of the numeric restriction through the calculations, the adaptive filters converge with better results than the fixed-point counterparts under similar computational costs. Exhaustive testing of the filters strengthens this claim. The proposed SPT adaptive filters were tested in different scenarios and presented optimistic results compared with other low-cost alternatives. The numerical issues amplified using fewer bits in the numeric representation did not destabilize the adaptive filtering algorithm.
[32] P. E. An, B. Brown, and C. J. Harris, “On the convergence rate performance of the normalized least-mean-square adaptation,” IEEE transactions on neural networks, vol. 8, no. 5, pp. 1211–1214, 1997.
[33] J. Benesty and T. Gansler, “A recursive estimation of the condition number in the RLS algorithm [adaptive signal processing applications],” in Proceedings.(ICASSP’05). IEEE International Conference on Acoustics, Speech, and Signal Processing, 2005., vol. 4, pp. iv–25, IEEE, 2005.
[34] D. J. Pierce and R. J. Plemmons, “Tracking the condition number for RLS in signal processing,” Mathematics of Control, Signals and Systems, vol. 5, no. 1, pp. 23–39, 1992.
[35] E. Ahmed, A. Clark, and G. Mohay, “A novel sliding window based change detection algorithm for asymmetric traffic,” in 2008 IFIP International Conference on Network and Parallel Computing, pp. 168–175, IEEE, 2008.
[36] F. Gustafsson, Adaptive Filtering and Change Detection. John Wiley & Sons, 1 ed., 2000.
Biographies
Michel Pompeu Tcheou

Figure 19.
Michel Pompeu Tcheou was born in Rio de Janeiro, Brazil. He received the Engineering degree in electronics from Federal University of Rio de Janeiro (UFRJ) in 2003, the M.Sc. and D.Sc. degrees in Electrical Engineering from COPPE/UFRJ in 2005 and 2011, respectively. He has worked at the Electric Power Research Center (Eletrobras Cepel) in Rio de Janeiro, Brazil, from 2006 to 2011. Since 2012 he has been with the Department of Electronics and Telecommunications Engineering at Rio de Janeiro State University (UERJ). He has also been with the Postgraduate Program in Electronics Engineering (PEL). His research interests are in signal processing, communications, data compression, and numerical optimization.
Luiz Felipe Silveira Coelho

Figure 20.
Luiz Felipe Silveira Coelho was born in Brasília, Brazil. He obtained the degree in Electrical Engineering with an emphasis in Telecommunications from Rio de Janeiro State University (UERJ) in 2019. Currently (2021) he is pursuing the M.Sc. degree in Electrical Engineering from the Alberto Luiz Coimbra Institute for Graduate Studies and Research in Engineering at the Federal University of Rio de Janeiro (COPPE/UFRJ). His main interests are in the areas of signal processing, communication systems and machine learning applications.
Lisandro Lovisolo

Figure 21.
Lisandro Lovisolo is an associate professor at the Department of Electronic and Telecommunications Engineering (DETEL) of the State University of Rio de Janeiro (UERJ). At UERJ since 2003, he teaches undergraduate and graduate level courses and has founded PROSAICO (Laboratory of Signal Processing, Intelligent Applications and Communications - www.prosaico.uerj.br) in 2007. His main interests are in the areas of signal processing, image and video, communications systems and networks and the underlying technologies, and computing machinery and its applications. His main interests are in signal processing, wireless communications systems and multimedia communications. He obtained his doctorate in Electrical Engineering from the Federal University of Rio de Janeiro (UFRJ) in 2006. He was born in Neuquen, Argentina in 1974, but feels Brazilian and native from Rio de Janeiro.
References
- [1]I. Yaqoob, I. A. T. Hashem, Y. Mehmood, A. Gani, S. Mokhtar, and S. Guizani, “Enabling communication technologies for smart cities,” IEEE Communications Magazine, vol. 55, no. 1, pp. 112–120, 2017.DOI
- [2]J. Henkel, S. Pagani, H. Amrouch, L. Bauer, and F. Samie, “Ultra-low power and dependability for IoT devices,” in Design, Automation & Test in Europe Conference & Exhibition, pp. 954–959, 2017.DOI
- [3]F. Samie, L. Bauer, and J. Henkel, “IoT technologies for embedded computing: A survey,” in 2016 International Conference on Hardware/Software Codesign and System Synthesis (CODES+ISSS), pp. 1–10, IEEE, 2016.DOI
- [4]H. Samueli, “An improved search algorithm for the design of multiplierless FIR filters with powers-of-two coefficients,” IEEE Transactions on Circuits and Systems, vol. 36, no. 7, pp. 1044–1047, 1989.
- [5]J. B. Evans, “Efficient FIR filter architectures suitable for FPGA implementation,” IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, vol. 41, no. 7, pp. 490–493, 1994.DOI
- [6]M. D. Macleod and A. G. Dempster, “Multiplierless FIR filter design algorithms,” IEEE Signal Processing Letters, vol. 12, no. 3, pp. 186–189, 2005.DOI
- [7]Y. C. Lim, R. Yang, D. Li, and J. Song, “Signed power-of-two term allocation scheme for the design of digital filters,” IEEE Transactions on Circuits and Systems II: Analog and Digital Signal Processing, vol. 46, no. 5, pp. 577–584, 1999.
- [8]J. Yli-Kaakinen and T. Saramäki, “A systematic algorithm for the design of multiplierless FIR filters,” in ISCAS 2001. The 2001 IEEE International Symposium on Circuits and Systems (Cat. No. 01CH37196), vol. 2, pp. 185–188, IEEE, 2001.
- [9]K. S. Yeung and S. C. Chan, “Multiplier-less FIR digital filters using programmable sum-of-power-of-two (SPOT) coefficients,” in 2002 IEEE International Conference on Field-Programmable Technology, 2002.(FPT). Proceedings., pp. 78–84, IEEE, 2002.
- [10]E. A. B. da Silva, L. Lovisolo, A. J. S. S. Dutra, and P. S. R. Diniz, “FIR filter design based on successive approximation of vectors,” IEEE Transactions on Signal Processing, vol. 62, no. 15, pp. 3833–3848, 2014.DOI
- [11]M. Iwahashi, T. Orachon, T. M. Aye, T. Yoshida, and H. Kiya, “Optimum SPT allocation for multipliers of minimum lifting 2D wavelet transform,” in 2016 IEEE International Symposium on Circuits and Systems (ISCAS), pp. 2543–2546, IEEE, 2016.DOI
- [12]H. Jiang, L. Liu, P. P. Jonker, D. G. Elliott, F. Lombardi and, J. Han, “A high-performance and energy-efficient FIR adaptive filter using approximate distributed arithmetic circuits,” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 66, no. 1, pp. 313–326, 2018.DOI
- [13]P. K. Meher and S. Y. Park, “Critical-path analysis and low-complexity implementation of the LMS adaptive algorithm,” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 61, no. 3, pp. 778–788, 2013.DOI
- [14]G. Di Meo, D. De Caro, G. Saggese, E. Napoli, N. Petra, and A. G. M. Strollo, “A novel module-sign low-power implementation for the DLMS adaptive filter with low steady-state error,” IEEE Transactions on Circuits and Systems I: Regular Papers, 2021.
- [15]D. Li and Y. C. Lim, “Multiplierless realization of adaptive filters by nonuniform quantization of input signal,” Proceedings of IEEE International Symposium on Circuits and Systems-ISCAS’94, vol. 2, pp. 457–459, IEEE, 1994.
- [16]S. Choudhary, P. Mukherjee, M. Chakraborty, and S. S. Rath, “A SPT treatment to the realization of the sign-LMS based adaptive filters,” IEEE Transactions on Circuits and Systems I: Regular Papers, vol. 59, no. 9, pp. 2025–2033, 2012.DOI
- [17]K. Baboj and S. Sridevi, “Optimal design of multiplier-less non-uniform channel filters with successive approximation of vectors,” Circuits, Systems, and Signal Processing, vol. 38, no. 10, pp. 4597–4620, 2019.
- [18]L. F. da S. Coelho, L. Lovisolo, and M. P. Tcheou, “A Proposal for Multiplierless RLS Adaptive Filters with Implementation Complexity Constraint,” in 2020 IEEE International Symposium on Circuits and Systems (ISCAS), pp=1–5, 2020.
- [19]S. Haykin, “Cognitive radio: brain-empowered wireless communications,” IEEE journal on selected areas in communications, vol.23, no. 2, pp. 201–220, 2005.DOI
- [20]M. B. Sousa e Silva and A. N. Barreto, “Spectrum sensing in cognitive radio networks through change detection technique,” in 2014 International Telecommunications Symposium (ITS), pp. 1–5, IEEE, 2014.
- [21]P. S. R. Diniz, Adaptive Filtering. Springer International Publishing, 5 ed., 2020.
- [22]J. Benesty, C. Paleologu, and S. Ciochina, “On regularization in adaptive filtering,” IEEE Transactions on Audio, Speech, and Language Processing, vol. 19, no. 6, pp. 1734–1742, 2010.DOI
- [23]J. Cioffi, “Limited-precision effects in adaptive filtering,” IEEE Transactions on circuits and systems, vol. 34, no. 7, pp. 821–833, 1987.DOI
- [24]S. Ardalan, “Floating-point error analysis of recursive least-squares and least-mean-squares adaptive filters,” IEEE Transactions on Circuits and Systems, vol. 33, no. 12, pp. 1192–1208, 1986.DOI
- [25]R. M. Hewlitt and E. S. Swartzlantler, “Canonical signed digit representation for FIR digital filters,” in 2000 IEEE Workshop on Signal Processing Systems. SiPS 2000. Design and Implementation (Cat. No. 00TH8528), pp. 416–426, IEEE, 2000.
- [26]M. O. K. Mendonça, P. S. R. Diniz, T. N. Ferreira, and L. Lovisolo, “Antenna selection in massive MIMO based on greedy algorithms,” IEEE Transactions on Wireless Communications, vol. 19, no. 3, pp. 1868–1881, 2019.DOI
- [27]S. Ameer and B. Shahravva, “Multiplier-free NLMS for adaptive IIR filtering,” in Canadian Conference on Electrical and Computer Engineering, 2005., pp. 1237–1240, IEEE, 2005.DOI
- [28]C.-L. Chen, K.-Y. Khoo, and A. N. Willson, “A simplified signed powers-of-two conversion for multiplierless adaptive filters,” in 1996 IEEE International Symposium on Circuits and Systems. Circuits and Systems Connecting the World. ISCAS 96, vol. 2, pp. 364–367, IEEE, 1996.
- [29]L. Lovisolo, E. A. B. da Silva, and P. S. R. Diniz, “On the statistics of matching pursuit angles,” Signal Processing, vol. 90, no. 12, pp. 3164–3184, 2010.DOI
- [30]Y. Chen, Y. Gu, and A. O. Hero, “Sparse LMS for system identification,” in 2009 IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 3125–3128, 2009.DOI
- [31]M. V. S. Lima, T. N. Ferreira, W. A. Martins, and P. S. R. Diniz, “Sparsity-aware data-selective adaptive filters,” IEEE Transactions on Signal Processing, vol. 62, no. 17, pp. 4557–4572, 2014.
- [32]P. E. An, B. Brown, and C. J. Harris, “On the convergence rate performance of the normalized least-mean-square adaptation,” IEEE transactions on neural networks, vol. 8, no. 5, pp. 1211–1214, 1997.pubmed.ncbi.nlm.nih.gov/18255724
- [33]J. Benesty and T. Gansler, “A recursive estimation of the condition number in the RLS algorithm [adaptive signal processing applications],” in Proceedings.(ICASSP’05). IEEE International Conference on Acoustics, Speech, and Signal Processing, 2005., vol. 4, pp. iv–25, IEEE, 2005.DOI
- [34]D. J. Pierce and R. J. Plemmons, “Tracking the condition number for RLS in signal processing,” Mathematics of Control, Signals and Systems, vol. 5, no. 1, pp. 23–39, 1992.DOI
- [35]E. Ahmed, A. Clark, and G. Mohay, “A novel sliding window based change detection algorithm for asymmetric traffic,” in 2008 IFIP International Conference on Network and Parallel Computing, pp. 168–175, IEEE, 2008.DOI
- [36]F. Gustafsson, Adaptive Filtering and Change Detection. John Wiley & Sons, 1 ed., 2000.DOI







