Al-Khwarizmi Engineering Journal Al-Khwarizmi Engineering Journal, Vol. 6, No. 2, PP 51- 61 (2010) Comparison of the RLS and LMS Algorithms to Remove Power Line Interference Noise from ECG Signal Noor K. Muhsin Department of Biomedical Engineering/ Al-Khwarizmi College of Engineering/ Baghdad University Email: noorbmemsc81@yahoo.com (Received 19 July 2009; accepted 31 March 2010) Abstract Biomedical signal such as ECG is extremely important in the diagnosis of patients and is commonly recorded with a noise. Many different kinds of noise exist in biomedical environment such as Power Line Interference Noise (PLIN). Adaptive filtering is selected to contend with these defects, the adaptive filters can adjust the filter coefficient with the given filter order. The objectives of this paper are: first an application of the Least Mean Square (LMS) algorithm, Second is an application of the Recursive Least Square (RLS) algorithm to remove the PLIN. The LMS and RLS algorithms of the adaptive filter were proposed to adapt the filter order and the filter coefficients simultaneously, the performance of existing LMS algorithm of the adaptive filters cause completely removing of the PLIN comparing with the RLS algorithm that reducing the noise level only. Keywords: Filters, adaptive filters, LMS algorithm, RLS algorithm, power line interference noise, ECG signals. 1. Introduction The most vital informative signals used to diagnose patients are the electrocardiogram (ECG), which is generated from heart activity. The ECG signal, measured with an electrocardiograph, is a biomedical electrical signal occurring on the surface of the body due to the contraction and relaxation of the heart. This signal represents an extremely important measure for doctors, as it provides vital information about a patient’s cardiac condition and general health [1]. Generally, the frequency band of the ECG signal is 0.05 to 100Hz, and the ECG signal includes 50Hz power line interference noise[2]. 50Hz power line noise can affect the Q- and P- waves of the ECG signal, generating errors during the diagnosis of arrhythmia or myocardial infarction. Power line noise can cause errors by distorting the ECG signal during the measurement of the QRS complex interval or the QT interval, which are important parameters in diagnosis. In order to remove 50Hz power line noise, an LMS and RLS adaptive filter can be applied by setting the notch filter of the 50Hz band or the 50Hz- component as a reference signal, so as to adjust the filter coefficient until the error is minimized from the input signal where the 50Hz-component is included [3]. These biomedical signals vary in time and are nonlinear, so the least mean square (LMS, RLS) algorithms of the adaptive filter is mainly used. The LMS, RLS algorithms of the adaptive filter, however, removes noise or obtains the desired signal features by adapting the filter coefficients according to a given filter order; as a result, from time to time, the output error of the filter cannot be minimized in a noisy environment [4]. The algorithms of the adaptive filter were proposed to adapt the filter coefficients simultaneously, thus improving the performance of existing LMS, RLS algorithms of the adaptive filters in processing biomedical signals. This page was created using Nitro PDF trial software. To purchase, go to http://www.nitropdf.com/ http://www.nitropdf.com/ Noor K. Muhsin Al-Khwarizmi Engineering Journal, Vol. 6, No. 2, PP 51-61 (2010) 52 2. ECG Signal, Noise, and Adaptive Filtering Electrocardiography (ECG) This is well known as ECG, which is used to measure the electrical activity of the heart. Inside the heart there is a specialized electrical conducting system that ensures the heart to expand and contract (as a pump) this action is produced by a sinoatrial node (SA) located below the right atrium in the heart. SA node is called as pacemaker because it has the ability to initiate electrical pulses at a faster rate of 100 per minute [4]. Figure1 clearly illustrates the SA & AV nodes. Fig. 1. Electrical Activity of Heart [4]. Four waves are detected while measuring the electrocardiography they are P, Q, R, S and T waves as shown in figure 2. An impulse sent from a SA node starts the heart to beat, and then the electrical current will flow down to the lower chambers of the heart or atria and produce the P wave. Then the electrical current will flow down to the lower chambers of the heart or ventricles producing the Q, R and S wave. As the electrical current spreads back over the ventricles in the opposite direction it will produce the T waves [5]. If the rate of the heart is fast then the repolarization will be fast these results shorter the Q-T interval. With slow heart rates, the Q-T interval is longer. The Q-T interval represents about 40% of the total time between the QRS complexes (the R-R interval). Fig. 2. PQRST Complex Wave [5]. Noise in ECG During the recording of any signal, it is inevitable that some undesirable signal loosely termed Noise is also picked up such as (PLIN).[6] PLIN consists of 50 Hz fundamental sinusoidal and its harmonics. This type of noise amplitude randomly modeled. The sampling frequency was 200 Hz.[7]. Adaptive Filters The main purpose of this filter is to change (adapt) the coefficients of an FIR filter to match as closely as possible to the response of an unknown system. The unknown system and the adapting filter process the same input signal and have the outputs. Adaptive filters are self designing filters based on an algorithm which allows the filter to “learn” the initial input statistics and to track them if they are time varying. These filters estimate the deterministic signal and remove the noise uncorrelated with the deterministic signal [8]. The major advantage of these filters is they do not require prior knowledge of the signal or noise characteristics as it is used in normal filters. Adaptive techniques is mainly used in filtering of 50Hz line frequency from ECG signals, enhancing P waves and improves the time duration of QRS wave. 2.3.1. Basic Adaptive Filter Structure Adaptive technique is widely used in eliminating noise interference.[8] The adaptive impulse correlated filter is considered which requires the primary signal This page was created using Nitro PDF trial software. To purchase, go to http://www.nitropdf.com/ http://www.nitropdf.com/ Noor K. Muhsin Al-Khwarizmi Engineering Journal, Vol. 6, No. 2, PP 51-61 (2010) 53 and a reference signal as an input. In the signal enhancement application, the reference signal consists of a desired signal s(k) that is corrupted by an additive noise n(k). The input signal of the adaptive filter is a noise signal x(k) that is correlated with the interference signal n(k), but uncorrelated with s(k). Figure 3 illustrate the configuration of the signal enhancement application[9]. Fig. 3. Noise Cancellation [10]. 2.3.2. Adaptive Algorithms Adaptive algorithms are used to adjust the coefficients of the digital filter such that the error signal, e(k), is minimized according to some criterion, for example the least squares sense. Common algorithms that have found widespread application are the least mean square (LMS), the recursive least squares (RLS).[11] They gradually reduce the mean square error between the input signal and some reference signal. The main features that attach the use of the LMS algorithm are low computational complexity, proof of convergence in stationary environment, unbiased convergence in the mean to the Wiener solution, and stable behavior when implemented with finite_ precision arithmetic[11]. It does not suffer from the numerical instability problem inherent in other two algorithms. A ) LMS Algorithm The least mean square algorithm is used to adjust the weights of the adaptive filter in order to minimize the error and to estimate the deterministic component through filter output. This algorithm is well known and can be expressed by the following equation: )()(2)()1( kxkekwkw  …(1) Where )(kw is the weight vector, and )(kx is the reference input and μ is the convergence factor, and )(ke is the error signal. The selection of the convergence factor μ becomes a trade off between convergence rate and the steady state mean square error. Adaptive Tapped-Delay-Line Filter In this paper the method of least squares will be used to derive a recursive algorithm for automatically adjusting the coefficients of a tapped-delay-line filter (Adaptive transversal), allow for elimination of noise while maintaining of optimal signal-to-noise ratio for nonstationary process,[blue book] as shown in figure 4, without invoking assumptions on the statistics of the input signals. This procedure, called the recursive least- squares (RLS) algorithm, is capable of realizing a rate of convergence that is much faster than the LMS algorithm, because the RLS algorithm utilizes all the information contained in the input data from the start of the adaptation up to the present. Fig. 4. (Tapped-Delay-line Filter) [9] 2.4.1. The Deterministic Normal Equations The requirement is to design the filter in such a way that it minimizes the residual sum of squares of the error. …(2) The filter output is the convolution sum: …(3)    n i ienJ 1 2 )()(    M k nikiunkhiy 1 ,...,2,1)1(),()( This page was created using Nitro PDF trial software. To purchase, go to http://www.nitropdf.com/ http://www.nitropdf.com/ Noor K. Muhsin Al-Khwarizmi Engineering Journal, Vol. 6, No. 2, PP 51-61 (2010) 54 where h(k,n) is the filter weight, u(n) is the input vector which upon substituting becomes …(4) Where ,e(n) the error of the filter, d(i) the desired signal, and y(n) the filter output. the deterministic correlation between the input signals at taps k and m, summed over the data length n, as ...(5) Where Ф(n) the deterministic correlation matrix of the tap input. We define the deterministic correlation between the desired response and the input signal at tap k, summed over the data length n, as …(6) θ(n) the deterministic cross-correlation vector We define the energy of the desired response as …(7) The residual sum of squares is now written as …(8) We may treat the tap coefficients as constants for the duration of the input data, from 1 to n. Hence, differentiating Eq. (8) with respect to h(k, n), we get …(9) Let denote the value of the kth tap coefficient for which the derivative is zero at time n. Thus, from Eq. (9) we get …(10) This set of M simultaneous equations constitutes the deterministic normal equations whose solution determines the “least-squares filter”. Vector form of the least-squares filter …(11) The deterministic correlation matrix of the tap inputs …(12) and the deterministic cross-correlation vector …(13) With these definitions the normal equations are expressed as …(14) Assuming (n) is nonsingular …(15) and for the resulting filter the residual sum of squares attains the minimum value [12]: …(16) )()()( iyidie           n i M k M m n i n i M k miukiunmhnkh kiuidnkhidnJ 11 1 11 1 2 )1()1(),(),( )1()(),(2)()( nM     n i Mmkmiukiumkn 1 1,...,1,0,)()(),;(    n i Mkkiuidkn 1 1,...,1,0)()();(    n i d idnE 1 2 )()( )1,1;(),(),( )1;(),(2)()( 1 1 1        mknnmhnkh knnkhnEnJ M k M m M k d   Mk mknnmhkn nkh nJ M m 1,2,..., )1,1;(),(2)1;(2 ),( )( 1        ),(ˆ nkh ),()/( nkhnJ  Mkknmknnmh M m 1,2,...,)1;()1,1;(),(ˆ 1     TnMhnhnhn ),(ˆ),...,,2(ˆ),,1(ˆ)(ˆ h                     )1,1;(..)1,1;()0,1;( ..... ..... )1,1;(..)1,1;()0,1;( )1,0;(..)1,0;()0,0;( )( MMnMnMn Mnnn Mnnn n    Φ  TMnnnn )1;(),...,1;(),0;()(  θ )()(ˆ)( nnn θh Φ )()()(ˆ -1 nnn θh Φ )()(ˆ)()(min nnnEnJ T d θh This page was created using Nitro PDF trial software. To purchase, go to http://www.nitropdf.com/ http://www.nitropdf.com/ Noor K. Muhsin Al-Khwarizmi Engineering Journal, Vol. 6, No. 2, PP 51-61 (2010) 55 1,...,1,0, )()(),;1(),;(   Mmk knumnumknmkn  1,...,1,0, )()(),;1(),;(   Mmk knumnumknmkn  2.4.2. Properties of the Least-Squares Estimate 1. The least-squares estimate of the coefficient vector approaches the optimum Wiener solution as the data length n approaches infinity, if the filter input and the desired response are jointly stationary ergodic processes. 2. The least-squares estimate of the coefficient vector is unbiased if the error signal e(i) has zero mean for all i. 3. The covariance matrix (is a measure of the linear coupling between two variables). To calculate the covariance matrix of the least- squares estimate h^ equals Ф-1, except for a scaling factor, if the error vector e0 has zero mean and its elements are uncorrelated. 4. If the elements of the error vector are statistically independent and Gaussian- distributed, then the least-squares estimate is the same as the MMT maximum-likelihood estimate.[12] 2.4.3. The Matrix-Inversion Lemma Let A and B be two positive definite, M by M matrices related by …(17) where D is another positive definite, N by N matrix and C is an M by N matrix. According to the matrix-inversion lemma, we may express the inverse of the matrix A as follows: …(18) B ) The Recursive Least-Squares (RLS) Algorithm The deterministic correlation matrix is now modified term by term as …(19) where c is a small positive constant and mk is the Kronecker delta; …(20) This expression can be reformulated as …(21) where the first term equates yielding …(22) Note that this recursive equation is independent of the arbitrarily small constant c. Defining the M-by-1 tap input vector ….(23) we can express the correlation matrix as …(24) and make the following associations to use the matrix inversion lemma Thus the inverse of the correlation matrix gets the following recursive form …(25) For convenience of computation, let …(26) And …(27) Then, we may rewrite Eq. (25) as follows: …(28) TCCDBA -1-1  )(nΦ    n i mkckiumiumkn 1 )()(),;(        km km mk 0 1            1 1 )()()()(),;( n i mkckiumiuknumnumkn  ),;1( mkn  TM-nu-nunun 1)(1),...,(),()( u )()()()( nnnn TuuΦΦ  1)( 1)()( -1   DuC BA n -nn ΦΦ )(1)()(1 1)()()(1)( 1)()( 1- -1-1 1-1- n-nn -nnn-n --nn T T uu uu Φ ΦΦ ΦΦ   )()( -1 nn ΦP )(1)()(1 )(1)( )( n-nn n-n n T uPu uP k   1)()()(-1)()( -nnn-nn T PukPP    BCBCCDBC-BA TT -11-  This page was created using Nitro PDF trial software. To purchase, go to http://www.nitropdf.com/ http://www.nitropdf.com/ Noor K. Muhsin Al-Khwarizmi Engineering Journal, Vol. 6, No. 2, PP 51-61 (2010) 56 The M-by-1 vector k(n) is called the gain vector. Postmultiplying both sides of Eq.(28) by the tap-input vector u(n) we get …(29) Rearranging Eq. (27) we find that …(30) Therefor substituting Eq. (30) in Eq. (29) and simplifying we get …(31) Reminding that the recursion requires not only updates for as given by Eq. (28) but also recursive updates for the deterministic cross-correlation defined by equation (6) which can be rewritten as …(32) yielding the recursion …(33) As a result …(34) With the suitable substitutions we get …(35) which can be expressed as …(36) where (n) is a “true” estimation error defined as …(37) Equations (36) and (37) constitute the recursive least-squares (RLS) algorithm.[12] 3. Methodology To verify the algorithms suggested in this paper, the normal ECG signal (down loaded from internet ftp://ftp.ieee.org/uploads/press/rangayyan/). was added to the PLIN (PLIN consists of 50 Hz fundamental sinusoidal and its harmonics, This type of noise amplitude randomly modeled. The sampling frequency was 200 Hz.[1,2]) then filtered the noisy ECG signals and evaluated the overall error of the signal and the optimal filter order. In this experiment, Matlab package (version 8) was used in writing the programming code of the proposed system and estimate the performance of the adaptive filter, the noisy ECG signal was filtered with two algorithms as shown in the block diagram. Fig. 5. Block Diagram of the Proposed System. The parameters of the implemented algorithms are as follows: A ) LMS Algorithm A notch adaptive filter was used with the aid of the below LMS algorithm specifications: Order of the FIR filter: 2nd Stability factor or step size parameter (μ), is a convergence factor that controls stability as well as the rate of adaptation, μ=.9 was selected to produce the best adaptation results. Initial weight vector: 0 B ) RLS Algorithm RLS algorithm specifications: Order of the FIR filter: 5th λ=0.999 Initial weight vector: 0 )(1)()()(-)(1)()()( n-nnnn-nnn T uPukuPuP  )()(1)()(1)()()( n-n-nn-nnn T kuPuPuk  )()()( nnn uPk  )()()(ˆ -1 nnn θh Φ )()(-1 nn PΦ );1()()( )()()()();( 1 1 knknund kiuidknundkn n i        )()()1()( nndnn uθθ    )()()1()( )()()()1()( )()()1()()()()(ˆ ndnnn ndnnnn ndnnnnnn kθP uPθP uθPθPh    )1(ˆ)()()(  nnndn T hu    )1()1()()()()1()1( )()()1()1()()()1()(ˆ   nnnndnnn ndnnnnnnn T T θPukθP kθPukPh   )()()1(ˆ )1(ˆ)()()()1(ˆ)(ˆ nnn nnndnnn T kh hukhh   This page was created using Nitro PDF trial software. To purchase, go to http://www.nitropdf.com/ http://www.nitropdf.com/ Noor K. Muhsin Al-Khwarizmi Engineering Journal, Vol. 6, No. 2, PP 51-61 (2010) 57 The reference signal of the adaptive filter used these noise signals with sampling frequency of the input and the reference signals are 200Hz. Fig.6. Multidimensional Signal-Flow Graph (a) RLS Algorithm (b) LMS Algorithm [12]. 4. Results The filtered results (the outputs of the adaptive filter) are shown in Figures (7-14), where the filter order is converged to minimize the distortion of ECG signal. By calculating the maximum, minimum, mean and standard deviation for both output curves and errors curves using Matlab programs where (max: Largest elements, min: Smallest elements, mean: the average value of a signal. It is found by adding all of the samples together, and divide by N. It looks like this in mathematical     1 0 1 N i ixN mean In words, sum the values in the signal, x , by letting the index, i, run from 0 to N-1. Then finish the calculation by dividing the sum by N.[13] std: standard deviation the standard deviation s of a data vector X: 2/1 1 2 1                  n i i x n std x Where     n i ixn x 1 1 and is the n number of elements in the sample. The two forms of the equation differ only in n-1 versus n in the divisor. The results are shown in the following table: Table 1, The results of the adaptive filter Output(LMS) Error(LMS) Max1 3.0774 3.8246 Min1 -1.1664 -1.9172 Mean1 0.0872 0.0996 Std1 0.4819 0.8577 Output(RLS) Error(RLS) Max2 2.8932 2.1723 Min2 -2.5815 -1.9836 Mean2 -0.1137 -0.0027 Std2 0.9287 0.3605 From the above tables to compare between the standard deviation of the (LMS algorithm) output and the (RLS algorithm) output the result shown that (Std1