Al-Khwarizmi Engineering Journal Al-Khwarizmi Engineering Journal, Vol. 7, No. 1, PP 13 - 21 (2011) Noise Removal of ECG Signal Using Recursive Least Square Algorithms Noor K. Muhsin Department of Biomedical Engineering/ Al-Khwarizmi College of Engineering/ University of Baghdad Email: Noorbmemsc81@yahoo.com (Received 11 May 2010; Accepted 17 February 2011) Abstract This paper shows an approach for Electromyography (ECG) signal processing based on linear and nonlinear adaptive filtering using Recursive Least Square (RLS) algorithm to remove two kinds of noise that affected the ECG signal. These are the High Frequency Noise (HFN) and Low Frequency Noise (LFN). Simulation is performed in Matlab. The ECG, HFN and LFN signals used in this study were downloaded from ftp://ftp.ieee.org/uploads/press/rangayyan/, and then the filtering process was obtained by using adaptive finite impulse response (FIR) that illustrated better results than infinite impulse response (IIR) filters did. Keywords: Adaptive filters, RLS algorithms, noise, ECG signals, signal processing. 1. Introduction Adaptive digital filters are successfully used in many practical systems such as echo, noise canceling, line enhancers, speech coding, and equalizers etc. It operates by adjusting its coefficients in response to its input so as to effectively process that input. Thus the filter coefficients are a function of the actual data they process. RLS adaptive algorithms operate by adjusting the filter coefficient vector so as to converge to the optimum Wiener coefficient vector. This is one of the primary advantages of an adaptive filter. Another primary advantage of adaptive filters is that they can be used in nonstationary environments. Since an adaptive filter is continuously self-designing, it can adapt to statistical changes in the data. [1] Kevin M. Buckley illustrated the application of filtering to biomedical signals such as ECG, in fetal heart monitor to remove power-line (50 or 60 Hz) interference noise. [1] Kiyoshi Nishikawa and Hitoshi Kiya proposed a method for increasing the throughput of recursive least squares (RLS) adaptive filters when only a few processing elements (PEs) are available.[3] This paper shows method to remove two types of noise that corrupted the ECG signal, which are the HFN and LFN downloaded as HFN-ECG and LFN-ECG from internet with sampling frequency of 1000 Hz.[2] The RLS algorithm is used because it has much faster convergence rate than the least mean square (LMS) algorithm. 2. Adaptive Filter for Noise Cancelling Adaptive signal processing system has been used in several biomedical applications. The RLS learning algorithm that are used in both linear and nonlinear adaptive filters. When the input process of an adaptive system is (quasi-) stationary, the best steady state performance results from slow adaptation. However, when the input statistics are time-variant (nonstationary), the best performance is obtained by a compromise between fast adaptation (necessary to track variations in the input process) and slow adaptation (necessary to limit the noise in the adaptive process). The LMS adaptation algorithm is a simple and efficient 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. 7, No. 1, PP 13 - 21 (2011) approach for adaptive noise canceling (ANC); however, it is not appropriate for fast-varying signals due to its slow convergence, and due to the difficulty in selecting the correct value for the step size µ. An alternative approach based on the exact minimization of the least-squares criterion is the RLS method .The RLS algorithm has been widely used in real-time system identification and noise cancellation because of its fast convergence, which is about an order of magnitude higher than that of the LMS method. An important feature of the RLS algorithm is that it utilizes information contained in the input data, and extends it back to the instant of time when the algorithm was initiated. Given the least- squares estimate of the tap-weight vector of the filter at time n - 1, the updated estimate of the vector at time n is computed upon the arrival of new data.[4]. Fig. 1. General Structure of the Adaptive RLS Filter[2] In the derivation of the RLS algorithm, the instantaneous error e [n] can be calculated from the following equation: e[n] = x[n] - h′[n] y[n] = x[n] - y′[n] h[n] …(1) where y[n] is the output of the filter, y′[n] is the output of the filter vector, and h[n] is the filter parameter, h′[n] is the filter parameter vector. The RLS algorithm considers all the available data for determining the filter parameters. The filter should be optimum with respect to all the available data in certain sense. Minimizes the cost function ][][ 2 0 ken n k kn    …(2) with respect to the filter parameter vector             ][ ][ ][ ][ 1 1 0 nh nh nh nh M …(3) where λ is the weighing factor known as the forgetting factor, recent data is given more weightage, for stationary case λ = 1 can be taken, λ=0.99 is effective in tracking local nonstationarity, the minimization problem is Minimize 2' 0 ])[][][(][ nhkykxn n k kn     with respect to h[n] the minimum is given by 0 )( )(    nh n 0])[][][][][(2 ' 0    nhkykykykx n k kn …(4) ][][][][][ 0 1 ' 0 kykxkykynh n k kn n k kn               …(5) Let us define ][][][ ' 0 kykynR n k kn yy      …(6) which is an estimator for the autocorrelation matrix Ryy . similarity ][][][ 0 kykxnr n k kn XY      …(7) is the estimator for the crosscorrelation vector ][nrXY  hence   ][][][ 1 nrnRnh XYXY     …(8) is the matrix inversion is involved which makes the direct solution difficult. We look forward for a recursive solution.[4] 2.1. Recursive Representation of ][nRyy  ][nRyy  can be written as follows 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. 7, No. 1, PP 13 - 21 (2011) 15 ][][][][][ '' 1 0 nynykykynR n k kn yy       ][][]1[ ][][][][ ' '' 1 0 1 nynynR nynykyky yy n k kn          …(9) This shows that the autocorrelation matrix can be recursively computed from its previous values and the present data vector.[4] Similarly ][][]1[][ nynxnrnr xyxy        ][][][]1[ ][][][ 1' 1 nrnynynR nrnRnh xyxy xyyy        …(10) For the matrix inversion above the matrix inversion lemma will be useful. 2.2. Matrix Inversion Lemma If A, B, C and D are matrices of proper orders, A and C nonsingular   11111 )(   DACBDABAABCDA …(11) Taking ],1[  nRA yy   ],[nyB  C=1 and ][' nyD  we will have   ]1[][1][]]1[[ 1 ][][]1[ 1 ]1[ 1 ][ 1' 1 1'1 11             nRnynynRnynynR nRnR YYYYYY YYyy                 ][]1[][ ]1[][][]1[ ]1[ 1 1' 1'1 1 nynRny nRnynynR nR YY YYYY YY     …(12) Rename P[n]= ][1 nRYY   . Then ])1[][][]1[( 1 P[n] '  nPnynKnP  …(13) where K[n] is called the "gain vector" and given by ][]1[][ ][]1[ ][ ' nynPny nynP nK     …(14) K[n] important to interpret adaptation is also related to the current data vector y[n] by K[n]=P[n]y[n] To establish the above relation consider P[n] =  1 1(P[n −1] − k[n]y′[n]P[n −1]) …(15) multiplying by λ and post-multiplying by y[n] and simplifying we get ][])1[][][]1[(][][ ' nynPnynKnPnynP  =P[n-1]y[n]-K[n]y'[n]P[n-1]y[n] =λK[n] …(16) Therefore ][][][ ^1^ nrnRnh XYYY        =P[n](λ nr XY [ ^ -1]+x[n]y[n]) =λP[n] nr XY [ ^ -1]+x[n]P[n]y[n] n]x[n]P[n]y[+]1[r1]]-[n]P[nK[n]y'-1]-[P[n 1 = ^ XY n  = h[n-1]+K[n]y'[n]h[n-1]+x[n]K[n] =h[n-1]+K[n](x[n]-y'[n]h[n-1]) …(17) 2.3. RLS Algorithm Operation The RLS algorithm can be motivated and derived as the exact solution to a well-defined estimation problem with a least-squares cost function.[5] The RLS algorithm operation was: For 1 to n = Final 1. Get x[n], y[n] 2. Get e[n] = x[n] − h′[n −1]y[n] 3. Calculate gain vector ][]1[][ ][]1[ ][ ' nynPny nynP nK     4. Update the filter parameters h[n] = h[n −1] + k[n]e[n] 5. Update the P matrix 1])-[n]P[n[n]y-( 1 P[n] 'KnP   end 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. 7, No. 1, PP 13 - 21 (2011) Fig.2. Block Diagram of the Proposed System. 3. Methodology From the following bloke diagram, this section is divided in to three steps as follows: 3.1. 1st Step Noisy ECG Data Acquisition The ECG is the electrical manifestation of the contractile activity of the heart, and can be recorded fairly easily with surface electrodes on the limbs or chest. The corrupted ECG signals with HFN and LFN are a real data down loaded from internet[1], these contaminated ECG of 500 µ sec (2000 samples) data length with sampling frequency of 1000Hz. 3.2. 2nd Step Filteration Process The noisy ECG signals in this step were passing through the adaptive FIR and IIR filters, the adaptation process were done using RLS algorithm to remove the HFN and LFN from the ECG signals. The selected parameters were illustrated in table 1: Table 1, Parameters of the Proposed System. FIR IIR System order 5 10 λ 0.999 0.9995 The selected order for the FIR type is half of the IIR filter and illustrated more pleasant results with more sharpness compared with the IIR filter that required higher order to illustrated a familiar results. The weighting factor λ (also known as the forgetting factor) with 0 < λ < 1. The values of λn-i < 1 give more “weight” to the more recent error values. Such weighting is desired in the case of nonstationary data, where changes in the signal statistics make the inclusion of past data less appropriate [6]. So that the smaller forgetting factor λ give an indication of the smaller contribution of previous samples. This makes the filter more sensitive to recent samples, which means more fluctuations in the filter coefficients. The λ = 1 case is referred to as the growing window RLS algorithm.[7] 3.3. Results and Discussion A. Noise Removal To verify the algorithm suggested in this paper, the ECG signals were filtered and evaluated the overall error of the signal and the optimal filter order. In this paper, MATLAB was used to estimate the performance of the proposed filters, and experimented with two kinds of filters. The mean  X and standard std deviation were calculated. The mean which is 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 ixNX …(18) std: standard deviation the standard deviation s of a data vector X: 2/1 1 0 2 1                   n i i x N std x …(19) Where     n i ixN x 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. 7, No. 1, PP 13 - 21 (2011) 17 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 table (2): Table 2, FIR and IIR Filter Results. HFN removal LFN removal Output (RLS) Output (RLS) Output (RLS) Output (RLS) FIR IIR FIR IIR Mean desired signal -0.528 -0.176 -0.798 -0.435 output signal -0.489 0.023 -0.713 -0.034 Std desired signal 0.774 0.723 0.785 0.772 output signal 0.776 0.536 0.847 0.787 From the above table the means of both FIR filter causes to remove the HFN and LFN is smaller value and approach to the desired values of the output as shown in figure 3 and 4 respectively. While IIR filter means of the output are small values and less than the desired signals values as shown in figure 5 and 6. To compare between the standard deviation of the two outputs the results shown that std of FIR output of HFN is approximately similar to std of the desired signal and less than of IIR output std but approximately similar to std of desired signal that mean that the deviation of the results from the true curve is smaller in case of FIR filters to remove both noises than the IIR filters. Fig.3. FIR Filter Results to Remove HFN. Fig.4. FIR Filter Results to Remove LFN. 0 20 40 60 80 100 120 140 160 180 200 -2.5 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2 2.5 System output Samples T ru e a n d e s ti m a te d o u tp u t desired signal output signal 0 20 40 60 80 100 120 140 160 180 200 -3 -2 -1 0 1 2 3 4 System output Samples T ru e a n d e s ti m a te d o u tp u t 0 20 40 60 80 100 120 140 160 180 200 -2 -1 0 1 2 3 4 System output Samples T ru e a n d e s ti m a te d o u tp u t 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. 7, No. 1, PP 13 - 21 (2011) Fig.5. IIR Filter Results to Remove HFN. Fig.6. IIR Filter Results to Remove LFN. B. Error Calculations The error curves were calculated as and ploted as shown in figures 6,7,8 and 9, respectively. (The logarithmic scale is used to display better the minor differences between the spectrograms.) It is seen that the frequency components of the HFN have been suppressed by using FIR filter rather than the IIR filter according to the following calculations of mean and std that shown in table 3. Table 3, Error Curves Calculations. HFN removal LFN removal Error (RLS) Error (RLS) Error (RLS) Error (RLS) FIR IIR FIR IIR Mean -0.547 -0.1283 -0.0592 -0.4115 Std 0.2879 0.4973 0.2609 0.6174 Fig.7. Error Curve of HFN Removal Using FIR Filter. Fig.8. Error Curve of HFN Removal Using IIR Filter. Fig.9. Error Curve of LFN Removal Using FIR Filter. 0 20 40 60 80 100 120 140 160 180 200 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 System output Samples T ru e a n d e s ti m a te d o u tp u t 0 20 40 60 80 100 120 140 160 180 200 10 -4 10 -3 10 -2 10 -1 10 0 10 1 Error curve E rr or v al ue 0 20 40 60 80 100 120 140 160 180 200 10 -4 10 -3 10 -2 10 -1 10 0 10 1 Error curve Samples E rr o r v a lu e 0 20 40 60 80 100 120 140 160 180 200 10 -4 10 -3 10 -2 10 -1 10 0 10 1 Error curve Samples E rr o r v a lu e 0 20 40 60 80 100 120 140 160 180 200 10 -4 10 -3 10 -2 10 -1 10 0 10 1 Error curve Samples E rr o r v a lu e 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. 7, No. 1, PP 13 - 21 (2011) Fig.10. Error Curve of LFN Removal Using IIR Filter. C. Comparison of the Filter Weights and Estimated Weights According to the order of the filter the following figures shows a comparison between the filter weights and estimated weights for both FIR and IIR filters. As illustrated in section 3.1 and table 1 the FIR filter order (5) while IIR filter order (10) because FIR filter output is calculated using the current and past input, but not previous values of the output and produce more placental results at the selected order but IIR filters are recursive filters that use the surrounding input and previous output values together and the selected order introduce good results. Fig.11. Comparison of the FIR Filter Weights and Estimated Weights (HFN Removal). Fig.12. Comparison of the IIR Filter Weights and Estimated Weights (HFN Removal). Fig.13. Comparison of the FIR Filter Weights and Estimated Weights (LFN Removal). Fig.14. Comparison of the IIR Filter Weights and Estimated Weights (LFN Removal). 4. Conclusions The ECG is perhaps the most commonly known, recognized, and used biomedical signal that corrupted with several types of noise such as HFN and LFN. Excessive filtering results in a distorted signal were evaluated the performance of the RLS algorithm for these signals. This paper can be illustrated that the means of both FIR filter causes to remove the HFN and LFN is smaller value and approach to the desired values of the output, while IIR filter means of the output are small values and less than the desired 1 1.5 2 2.5 3 3.5 4 4.5 5 -0.4 -0.2 0 0.2 0.4 0.6 0.8 1 Samples W e ig h ts v a lu e Comparison of the filter weights and estimated weights Filter weights Estimated filter weights 1 2 3 4 5 6 7 8 9 10 -0.15 -0.1 -0.05 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 Comparison of the filter weights and estimated weights filter weights Estimated filter weights 1 1.5 2 2.5 3 3.5 4 4.5 5 -1 -0.5 0 0.5 1 1.5 2 Comparison of the filter weights and estimated weights Filter weights Estimated filter weights 1 2 3 4 5 6 7 8 9 10 -0.05 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 Comparison of the filter weights and estimated weights filter weights Estimated filter weights 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. 7, No. 1, PP 13 - 21 (2011) 20 signals values, but the standard deviation of the two outputs (FIR output of HFN) is approximately similar to std of the desired signal and less than of IIR output std which is similar to std of desired signal that mean that the deviation of the results from the true curve is smaller in case of FIR filters to remove both noises than the IIR filters. The FIR adaptive filter using RLS algorithm is illustrated more perfect results compared with IIR filters. Notation s[n] desired signal n[n] interference signal x[n] the input of the adaptive filter e[n] error signal y[n] the output of the adaptive filter y'[n] the output of the adaptive filter vector h'[n] filter parameter vector h[n] filter parameter n,k,M length of the signal k[n] gain vector A,B,C,D matrices of proper order ][nRyy  an estimator for the autocorrelation matrix an estimator for the autocorrelation matrix P[n] inversion of an estimator for the autocorrelation matrix nr XY [ ^ ] an estimator for the autocorrelation vector Greek letters λ the forgetting factor δ positive number ε[n] cost function 5. References [1]. Kevin Buckley., " ECE5251 Biomedical Signal Processing", 2009 [2]. Kiyoshi Nishikawa and Hitoshi Kiya, "Noval Implementation Technique of Rls Algorithm for Improving Throughtput of Adaptive Filters, 1999. [3]. ftp://ftp.ieee.org/uploads/press/rangayyan/ [4]. P.K. Bora, "statistical signal processing", John Wiley and Sons, inc., 1996. [5]. ALI H. SAYED, "Adaptive Filters",2008 [6]. Rangarai M. Rangayyan., "Biomedical Signal Analysis a case-stady approach", John Wiley and Sons, inc., 2002. [7]. Hayes, Monson H., “Statistical Digital Signal Processing and Modeling", John Wiley and Sons, inc., 1996. This page was created using Nitro PDF trial software. To purchase, go to http://www.nitropdf.com/ http://www.nitropdf.com/ 21 ، صفحة1، العدد 7مجلة الخوارزمي الھندسیة المجلد نور كمال محسن - 13 )2011( 21 َتستعمُل أقّل تكراریًة الخوارزمیاِت المرّبعِةإزالة ضوضاِء التي نور كمال محسن جامعة بغداد/ كلیة الھندسھ الخوارزمي/ قسم ھندسة الطب الحیاتي noorbmemsc81@yahoo.com: االلكتروني البرید الخالصة لّ ة أق تعمُل خوارزمی ذي َیس يِّ ال ِي والخط ِي الالخّط یح التكیف ى الَتْرش تندة عل ِع ھذا البحث یبحث نظرًة لمعالجِة إشارات تخطیط القلب مس ًة المرب تكراری اءَ الي و ضوض ذب الع اَء التذب واطئ إلزالة إثنان ِمْن أنواِع الضوضاِء الذي المؤثره على إشارِة تخطیط القلب و المتمثلھ بضوض ذب ال ة . التذب اة ُمَؤّدی المحاك ك عملی د ذل ِت ، وبع ْن اإلنترن ْت ِم ِة ُحّمل ذه الدراس ي ھ تعملْھ ف واطئَ المس ذب ال اَء التذب الي و ضوض ذب الع تعمال بأستخدام ال ضوضاَء التذب یح بإس ة الَتْرش !!!ز الالنھائياستجابة الحافالذي صّوَر َنتاِئَج افضل ِمْن مرشحاِت استجابة الحافز المحدود !! This page was created using Nitro PDF trial software. To purchase, go to http://www.nitropdf.com/ http://www.nitropdf.com/