betaFeedback

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 NN coefficients for a N−1N-1 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 kk indexes the signal samples. An input signal x(k)x(k) is filtered, resulting in the output signal y(k)y(k). The output signal is then subtracted from the desired signal d(k)d(k) resulting in the error signal e(k)e(k). 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

(MSE=E[∣e(k)∣2])(\mathrm{MSE} = E[|e(k)|^2])

at the filter output as kk increases by computing a simplification of the gradient vector derived using an appropriate change on the objective function [21]. For the LMS,

y(k)=xT(k)w(k),(1)y(k) = x^T(k)w(k), \tag*{(1)}
e(k)=d(k)−y(k),(2)e(k) = d(k) - y(k), \tag*{(2)}
w(k+1)=w(k)+2μe(k)x(k),(3)w(k+1) = w(k) + 2\mu e(k)x(k), \tag*{(3)}

where w(k)w(k) is an NN-length column-vector containing the adaptive filter coefficients for the kk-th iteration, x(k)=[x(k)  x(k−1) ⋯ x(k−N+1)]Tx(k) = [x(k)\ \ x(k-1)\ \cdots\ x(k-N+1)]^T is the tapped delay line for the input signal in the kk-th iteration also represented as an NN-length column vector. (3) is the update rule and μ\mu is the step-size, which is used to adjust the convergence speed and stability of the algorithm and TT 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

w(k+1)=w(k)+μne(k)x(k)γ+xT(k)x(k),(4)w(k+1) = w(k) + \frac{\mu_n e(k)x(k)}{\gamma+ x^T(k)x(k)}, \tag*{(4)}

where μn\mu_n is the NLMS convergence factor defined in the interval (0,1](0,1] and the parameter γ\gamma is a constant introduced to avoid division by zero [22].

RLS Algorithm

The RLS algorithm aims to minimize, ξd(k)\xi^d(k), the sum of the squared error (difference between the desired signal d(k)d(k) and the filter output y(k)y(k)) using a recursive method, given by

ξd(k)=∑i=0kλk−i[d(i)−xT(i)w(k)]2,(5)\xi^d(k) = \sum_{i=0}^{k} \lambda^{k-i}\left[d(i)-x^T(i)w(k)\right]^2, \tag*{(5)}

where λ\lambda is defined as an exponential weighting factor, ranging from 0≪λ≤10 \ll\lambda\leq1, also called forgetting factor since the distant past effect is turned negligible with the constant updating (as kk 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

y(k)=xT(k)w(k−1),(6)y(k) = \mathbf{x}^{T}(k)\mathbf{w}(k-1), \tag*{(6)}
e(k)=d(k)−y(k),(7)e(k) = d(k) - y(k), \tag*{(7)}
Ψ(k)=SD(k−1)x(k),(8)\mathbf{\Psi}(k) = \mathbf{S}_{D}(k-1)\mathbf{x}(k), \tag*{(8)}
SD(k)=1λ[SD(k−1)−Ψ(k)ΨT(k)λ+ΨT(k)x(k)],(9)\mathbf{S}_{D}(k) = \frac{1}{\lambda}\left[\mathbf{S}_{D}(k-1)-\frac{\mathbf{\Psi}(k)\mathbf{\Psi}^{T}(k)}{\lambda+\mathbf{\Psi}^{T}(k)\mathbf{x}(k)}\right], \tag*{(9)}
w(k)=w(k−1)+e(k)SD(k)x(k),(10)\mathbf{w}(k) = \mathbf{w}(k-1)+e(k)\mathbf{S}_{D}(k)\mathbf{x}(k), \tag*{(10)}

where SD\mathbf{S}_{D} estimates the inverse Hessian, it is initialized with SD(−1)=δI\mathbf{S}_{D}(-1)=\delta\mathbf{I} and Ψ\mathbf{\Psi} 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 LL-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 vv is

v≈a^=∑l=0L−1αl2βl,(11)v \approx\hat{a}=\sum_{l=0}^{L-1}\alpha_l 2^{\beta_l}, \tag*{(11)}

where, LL is the word-length (bit-plane depth) of the numerical representation, αl\alpha_l is −1, 0 or 1, and βl\beta_l defines the bit-plane. Figure 2 illustrates (11). If v\mathbf{v} is an NN-length vector v=[v0 v1 ⋯ vN−1]T\mathbf{v}=[v_0\ v_1\ \cdots\ v_{N-1}]^T, the nn-th element is approximated by the SOPOT,

Figure 2. A SOPOT representation, where LL is the word-length, 2D2^D is the highest absolute value that an SPT term can assume, and 2−B2^{-B} the lowest (in Equation (11), βl∈{−B, 1−B, …, D−1, D}\beta_l \in\{-B,\,1-B,\,\ldots,\,D-1,\,D\}).

v^n=∑l=0L−1αl,n2βl,n.(12)\hat{v}_n=\sum_{l=0}^{L-1}\alpha_{l,n}2^{\beta_{l,n}}. \tag*{(12)}

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 v\mathbf{v} is approximated as

v≈∑i=1K2kicji,(13)\mathbf{v}\approx\sum_{i=1}^{K}2^{k_i}\mathbf{c}_{j_i}, \tag*{(13)}

where cj\mathbf{c}_j is a code-word from a dictionary D={c1,c2,…,cj,…,c#D}\mathcal{D}=\{\mathbf{c}_1,\mathbf{c}_2,\ldots,\mathbf{c}_j,\ldots,\mathbf{c}_{\#D}\} and #D\#D is the cardinality of the dictionary. In Equation (13), jij_i is the selected code-word index in the ii-th decomposition iteration. Defining code-words having coordinates −1, 0 and 1, one has that 2kicji2^{k_i}\mathbf{c}_{j_i} has coordinates that value −2ki-2^{k_i}, 0 or 2ki2^{k_i}. Furthermore, representations employing less terms are obtained if the number of non-null coordinates PP per code-word (cj\mathbf{c}_j) equals ⌊N⌋\lfloor\sqrt{N}\rfloor [10], the operator ⌊⋅⌋\lfloor\cdot\rfloor 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 2ki2^{k_i} conjointly. Algorithm 1 illustrates this approximation process for the vector v\mathbf{v}. One can set up the algorithm to use at most MM SPT terms (active bits limitation) or the deepest bit-plane value Bmax⁡B_{\max} (the largest numeric precision).

Given that 2k+2k=2k+12^k+2^k=2^{k+1}, 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 v′v' and u′u' provides

v′u′=v0u02bv0+bu0+v0u12bv0+bu1+⋯+v1u02bv1+bu0+⋯+vM−1uM−12bvM−1+buM−1(14)v'u' = v_0u_0 2^{b_{v_0}+b_{u_0}} + v_0u_1 2^{b_{v_0}+b_{u_1}} + \cdots+ v_1u_0 2^{b_{v_1}+b_{u_0}} + \cdots+ v_{M-1}u_{M-1}2^{b_{v_{M-1}}+b_{u_{M-1}}} \tag*{(14)}

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 MM 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 v′=[v(0)′,v(1)′,…,v(N−1)′]T\mathbf{v}' = [v(0)', v(1)', \ldots, v(N-1)']^{T} and u′=[u(0)′,u(1)′,…,u(N−1)′]T\mathbf{u}' = [u(0)', u(1)', \ldots, u(N-1)']^{T} be two SOPOT-represented line vectors of length NN, then v′Tu′\mathbf{v}'^{T}\mathbf{u}' accumulates NN sums as the one in equation (14). The product of N×NN \times N matrix by an NN-length vector and the product between two N×NN \times N matrices are implemented using NN and N2N^2 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 ll-terms in the Maclaurin Series for vv

v−1=∑l=0∞(1−v)l,{v∈R∣−2<v<2},(15)v^{-1} = \sum_{l=0}^{\infty}(1-v)^l,\quad\{v \in\mathbb{R}\mid-2 < v < 2\}, \tag*{(15)}

one can approximate the inversion for a given denominator vv. 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 v=±2i±2j±⋯±2kv = \pm2^i \pm2^j \pm\cdots\pm2^k, with i>j>ki > j > k, the approximation results in v−1≈±2−iv^{-1} \approx\pm2^{-i}, the greater the difference between ii and jj, the better this approximation is.

Complexity Constraint

One can limit the word length LL by limiting BB (which denotes the lowest exponent of the sum) and the quantity MM 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, BB limits the lowest exponent of the SPT term to be an integer within [D,−B][D,-B], DD limits its highest exponent, and LL is defined as the equation L=D+B−1L = D + B - 1. Although, in each operation, the least significant SPT terms are ignored, keeping only the MM 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 NN-length filter, we define M/NM/N, 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 v∈V\mathbf{v} \in\mathcal{V}, the expected value of the quantization error eq\mathbf{e}_q is

E[eq]=E[v−v^].(16)E[\mathbf{e}_q] = E[\mathbf{v} - \hat{\mathbf{v}}]. \tag*{(16)}

If the expected value for each coordinate in v\mathbf{v} is zero and the vector v\mathbf{v} is approximated using the MPGBP algorithm, then

E[eq]=−E[∑i2βici].(17)E[\mathbf{e}_q] = -E\left[\sum_i 2^{\beta_i}\mathbf{c}_i\right]. \tag*{(17)}

where each ci\mathbf{c}_i has P=⌊N⌋P = \lfloor\sqrt{N}\rfloor non zero coordinates (consisting of −1-1 and 11). If the probability of the codewords coefficients is the same independently of the exponent βi\beta_i, i.e., independently of the magnitude 2βi2^{\beta_i} of the vector to be approximated [29], thus

E[eq]=−∑iE[2βi]E[ci].(18)E[\mathbf{e}_q] = -\sum_i E\left[2^{\beta_i}\right]E[\mathbf{c}_i]. \tag*{(18)}

By definition/construction of the codewords, E[ci]=0E[\mathbf{c}_i] = \mathbf{0} if the vector source V\mathcal{V} is uniformly distributed in RN\mathbb{R}^{N} [29].

A numerical analysis is now presented. In this analysis, the MPGBP algorithm is used to approximate a series of NN-length random vectors following Gaussian (zero mean and unitary variance) distribution using at most MM SOPOT in the vector approximation. The process is repeated exhaustively (ensemble=105ensemble = 10^{5}) 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,

NN
(M/N)(M/N)41216
3μeq\mu_{e_q} 1.99 ×10−5\times10^{-5}1.29 ×10−5\times10^{-5}2.06 ×10−5\times10^{-5}
σeq2\sigma^2_{e_q} 7.02 ×10−5\times10^{-5}1.22 ×10−5\times10^{-5}1.03 ×10−5\times10^{-5}
5μeq\mu_{e_q} 1.02 ×10−6\times10^{-6}3.33 ×10−7\times10^{-7}3.74 ×10−7\times10^{-7}
σeq2\sigma^2_{e_q} 3.48 ×10−8\times10^{-8}4.09 ×10−9\times10^{-9}3.27 ×10−9\times10^{-9}
7μeq\mu_{e_q} 1.58 ×10−8\times10^{-8}6.92 ×10−9\times10^{-9}9.10 ×10−9\times10^{-9}
σeq2\sigma^2_{e_q} 1.74 ×10−10\times10^{-10}1.30 ×10−12\times10^{-12}9.78 ×10−13\times10^{-13}
10μeq\mu_{e_q} 7.88 ×10−11\times10^{-11}2.29 ×10−11\times10^{-11}1.38 ×10−11\times10^{-11}
σeq2\sigma^2_{e_q} 1.89 ×10−16\times10^{-16}7.78 ×10−18\times10^{-18}5.24 ×10−18\times10^{-18}

Table I. Expected value (μ\mu) and variance (σ2\sigma^2) of the quantization error stemming from the MPGBP approximation algorithm.

E[eq]=μeq=1105∑k=1105(v−v^)k,(19)E[\mathbf{e}_q] = \boldsymbol{\mu}_{e_q} = \frac{1}{10^{5}}\sum_{k=1}^{10^{5}}(\mathbf{v}-\hat{\mathbf{v}})_k, \tag*{(19)}

where kk indexes the trials. In Table I the expected values correspond to the largest absolute value among the means of the coordinates of eq\mathbf{e}_q. The variance vector is estimated using

σeq2=E[(eq−E[eq])2].(20)\sigma^2_{e_q} = E\left[(\mathbf{e}_q-E[\mathbf{e}_q])^2\right]. \tag*{(20)}

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 (N=4N = 4) vector source stemming from SOPOT approximation using the MPGBP algorithm with complexities M/N=1M/N = 1, 2, 3 and 4. For high restraint in complexity (M/N<3M/N < 3), 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.

Histogram of the quantization error distributions for four complexity levels

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 M/N=1M/N = 1, 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 MM 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 ci\mathbf{c}_i sustains values −1-1 or 11 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 x(k)x(k) 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 x(k)x(k) is a vector following a Gaussian distribution. The additive noise n(k)n(k) 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 y(k)y(k) is an estimate for d(k)d(k). Since x(k)x(k) and n(k)n(k) are uncorrelated, the adaptive filter is not able to nullify its effects, thus the error signal e(k)e(k) is limited by the SNR in its reduction. The filters are of 3rd order, i.e., they are also 4-elements vectors, N=4N = 4. The SNR is set by adjusting the noise power as follows

n(k)=(1K∑k=1K∣x(k)∣2)10−SNRdB/101K∑k=1K∣n′(k)∣2 n′(k),(21)n(k) = \sqrt{\frac{\left(\frac{1}{K}\sum_{k=1}^{K}|x(k)|^2\right)10^{-\mathrm{SNR}_{\mathrm{dB}}/10}}{\frac{1}{K}\sum_{k=1}^{K}|n'(k)|^2}}\,n'(k), \tag*{(21)}

where SNRdB\mathrm{SNR}_{\mathrm{dB}} is the desired signal to noise ratio, in dB, n′(k)n'(k) is the misadjusted noise signal, and the noise signal n(k)n(k) 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 μ=0.075\mu= 0.075, μn=0.13\mu_n = 0.13, γ=1e−4\gamma= 1\mathrm{e}{-4}, λ=0.9987\lambda= 0.9987 and δ=0.06\delta= 0.06. The SPT filters and the fixed-point filters use different values for λ\lambda 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

  1. 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,

MSE⁡(k)=10log⁡10(∑i=1150ei2(k)150),(22)\operatorname{MSE}(k) = 10\log_{10}\left(\frac{\sum_{i=1}^{150}e_i^2(k)}{150}\right), \tag*{(22)}

where ei(k)e_i(k) is the error signal for kk-th iteration of the ii-th Monte Carlo repetition (there are 150 repetitions). The MSE curves of SPT-LMS, SPT-NLMS and SPT-RLS algorithms for different SOPOT complexities (M/NM/N) 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.

MSE curve evolution for SPT-LMS and fixed-point LMS

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

MSE curve evolution for SPT-NLMS and fixed-point NLMS

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

MSE curve evolution with SNR = 10 dB for different complexities and word lengths

Figure 7. MSE curve evolution with SNR = 10 dBdB (a) for different complexities, M/NM/N, in the SPT-RLS and (b) for different word lengths in the fixed-point RLS.

M/NM/NLMS μ\muNLMS μn\mu_nγ\gammaRLS λ\lambdaδ\delta
12−42^{-4} (0.075)2−32^{-3} (0.13)0 (1e−41\mathrm{e}{-4})202^{0} (0.975)2−12^{-1} (0.06)
22−4+2−62^{-4}+2^{-6} (0.075)2−3+2−82^{-3}+2^{-8} (0.13)0 (1e−41\mathrm{e}{-4})20−2−52^{0}-2^{-5} (0.975)2−1+2−32^{-1}+2^{-3} (0.06)
32−4+2−6−2−82^{-4}+2^{-6}-2^{-8} (0.075)2−3+2−8+2−102^{-3}+2^{-8}+2^{-10} (0.13)0 (1e−41\mathrm{e}{-4})20−2−5−2−72^{0}-2^{-5}-2^{-7} (0.96)2−1+2−3−2−52^{-1}+2^{-3}-2^{-5} (0.06)
42−4+2−6−2−8+2−102^{-4}+2^{-6}-2^{-8}+2^{-10} (0.075)2−3+2−8+2−102^{-3}+2^{-8}+2^{-10} (0.13)0 (1e−41\mathrm{e}{-4})20−2−5−2−7−2−102^{0}-2^{-5}-2^{-7}-2^{-10} (0.96)2−1+2−3−2−5+2−72^{-1}+2^{-3}-2^{-5}+2^{-7} (0.06)
52−4+2−6−2−8+2−10−2−122^{-4}+2^{-6}-2^{-8}+2^{-10}-2^{-12} (0.075)2−3+2−8+2−102^{-3}+2^{-8}+2^{-10} (0.13)0 (1e−41\mathrm{e}{-4})20−2−5−2−6+2−92^{0}-2^{-5}-2^{-6}+2^{-9} (0.955)2−1+2−3−2−5+2−7−2−92^{-1}+2^{-3}-2^{-5}+2^{-7}-2^{-9} (0.06)
62−4+2−6−2−8+2−10−2−122^{-4}+2^{-6}-2^{-8}+2^{-10}-2^{-12} (0.075)2−3+2−8+2−102^{-3}+2^{-8}+2^{-10} (0.13)0 (1e−41\mathrm{e}{-4})20−2−5−2−6+2−102^{0}-2^{-5}-2^{-6}+2^{-10} (0.954)2−1+2−3−2−5+2−7−2−9+2−112^{-1}+2^{-3}-2^{-5}+2^{-7}-2^{-9}+2^{-11} (0.06)
72−4+2−6−2−8+2−10−2−122^{-4}+2^{-6}-2^{-8}+2^{-10}-2^{-12} (0.075)2−3+2−8+2−102^{-3}+2^{-8}+2^{-10} (0.13)0 (1e−41\mathrm{e}{-4})20−2−5−2−7−2−102^{0}-2^{-5}-2^{-7}-2^{-10} (0.96)2−1+2−3−2−5+2−7−2−9+2−112^{-1}+2^{-3}-2^{-5}+2^{-7}-2^{-9}+2^{-11} (0.06)
82−4+2−6−2−8+2−10−2−122^{-4}+2^{-6}-2^{-8}+2^{-10}-2^{-12} (0.075)2−3+2−8+2−102^{-3}+2^{-8}+2^{-10} (0.13)0 (1e−41\mathrm{e}{-4})20−2−5−2−6+2−102^{0}-2^{-5}-2^{-6}+2^{-10} (0.954)2−1+2−3−2−5+2−7−2−9+2−112^{-1}+2^{-3}-2^{-5}+2^{-7}-2^{-9}+2^{-11} (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 ℓ2\ell_2-norm and the unknown system’s coefficients ℓ2\ell_2-norm through the Mote Carlo process. It presents the deviation between adaptive filters and unknown system coefficient norm and can be calculated as

MSD⁡(k)=10log⁡10(∑i=1150(∥wi(k)∥2−∥h∥2)2150)(23)\operatorname{MSD}(k)=10\log_{10}\left(\frac{\sum_{i=1}^{150}(\lVert\mathbf{w}_i(k)\rVert_2-\lVert\mathbf{h}\rVert_2)^2}{150}\right) \tag*{(23)}

where wi(k)\mathbf{w}_i(k) is a NN-element vector representing the adaptive filter coefficients in the kk-th iteration for the ii-th repetition of the Monte Carlo and h\mathbf{h} 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 (M/NM/N) with a fixed-point of 16-bit fixed-point precision. In this case, filters are trained for SNR = −3-3 and 10 dBdB. 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.

MSD for the SPT-LMS with different complexities

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

MSD for the SPT-NLMS with different complexities

Figure 9. MSD for the SPT-NLMS with different complexities, M/NM/N (SPT terms per coefficient), compared with a 16-bit fixed-point NLMS, for (a) SNR = −3-3 dBdB and (b) SNR = 10 dBdB.

Figure 10. MSD for the SPT-RLS with different complexities, M/NM/N (SPT terms per coefficient), compared with a 16-bit fixed-point RLS, for (a) SNR = −3-3 dB and (b) SNR = 10 dB.

SPT-based and Fixed-Point Filters on Equal Terms

The complexity of the RLS algorithm is proportional to N2N^2. On the other hand, the complexities of the LMS and NLMS algorithms are proportional to 2N2N and 3N3N, respectively.

Let the fixed-point word length be BFB_F 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 2BF2B_F-bit word (rounded accordingly to return a BFB_F-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 BF/2B_F/2. This reduces the complexity of the multiplication between two fixed-point numbers to BF/2B_F/2 shifts of BFB_F-bit words and BF/2−1B_F/2-1 additions of possibly 2BF2B_F-bit words.

On the other hand, a SOPOT representation using MM SPT terms and BB-bit exponents requires at most M2M^2 additions (distributive property) of BB-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 BF2−2BFB_F^2-2B_F sums while the SOPOT multiplication uses BM2BM^2 sums.

Therefore, to evaluate SOPOT and fixed-point filters under similar computational complexities, the value

BF=1+1+BM2≈⌈1+MB⌉(24)B_F = 1 + \sqrt{1+BM^2} \approx\left\lceil1+M\sqrt{B}\right\rceil \tag*{(24)}

presents the fixed-point word length counterpart for a given number of SPT terms MM.

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.

MSD for the SPT-LMS with different complexities

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

MSD for the SPT-NLMS with different complexities

Figure 12. MSD for the SPT-NLMS with different complexities, M/NM/N (SPT terms per coefficient) compared with fixed-point of estimated similar complexity, for (a) SNR = −3-3 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 hh 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 M/N=3M/N=3 SPT per coefficient, using a 16-SPT wordlength with the maximum exponent of 3, i.e., 232^3 is the highest value an SPT can get.

MSD for the SPT-RLS with different complexities

Figure 13. MSD for the SPT-RLS with different complexities, M/NM/N (SPT terms per coefficient) compared with fixed-point of estimated similar complexity, for (a) SNR =−3=-3 dB and (b) SNR =10=10 dB.

ParameterSOPOT (Value)
μ\mu2−5−2−7+2−92^{-5}-2^{-7}+2^{-9}
μn\mu_n2−2−2−4+2−62^{-2}-2^{-4}+2^{-6}
γ\gamma2−102^{-10}
λ\lambda20−2−5+2−72^{0}-2^{-5}+2^{-7}
δ\delta2−4−2−9−2−112^{-4}-2^{-9}-2^{-11}

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 kHzkHz. 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 HzHz. 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 (N=4N = 4) 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 2−8+2−10+2−122^{-8} + 2^{-10} + 2^{-12} to 2−6−2−8−2−122^{-6} - 2^{-8} - 2^{-12} in steps of 2−122^{-12}. 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.

Change detection output using fixed point and SOPOT implementations

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

Portrait of 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

Portrait of 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

Portrait of 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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [21]P. S. R. Diniz, Adaptive Filtering. Springer International Publishing, 5 ed., 2020.
  22. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [36]F. Gustafsson, Adaptive Filtering and Change Detection. John Wiley & Sons, 1 ed., 2000.DOI

Paper details

vlnc:W_akwkh2jg
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Engineering

Not recorded for this paper

View statement
Looking for related papers…
Contents