Development of Partitioned Block Frequency- Domain Adaptive Filter (PBFDAF) Methods Approach for Acoustic Echo Cancellation

Development of Partitioned Block Frequency- Domain Adaptive Filter (PBFDAF) Methods Approach for Acoustic Echo Cancellation

Shreyas H. Gopalaiah

Student, M.Tech 4th Semester, Associate Professor,

Department of Instrumentation Technology, Department of Instrumentation Technology,

Dayananda Sagar College of Engineering, Dayananda Sagar College of Engineering, Bangalore, India Bangalore, India

Abstract The adaptive Filter Acoustic Echo cancellation algorithms (AECA) is proposed in this paper. The Matlab simulation results of the Metric performance are presented. According to the comparison of the results, and performance especially the usage of resource, Good Tracking Capability Convergence speed and rate and effects of cancellation, for the LMS and NLMS adaptive echo cancellation algorithm and frequency-domain block LMS algorithm are selected, which are suitable for the further design on FPGA. By simulating the functions by ISE Simulator, and analyzing the PSD curve and the constellation of output signals, the adaptive interference cancellation algorithm system based on frequency-domain block LMS have achieved expected effect. The frequency-domain block LMS adaptive echo interference cancellation system has better flatness on the in-band PSD curve and better convergence effect on the groups. Therefore, frequency-domain block LMS and NLMS adaptive filter echo cancellation algorithm is chosen as the design with high performance- aspect ratio. it will performing where all frequencies have the same energy, the NLMS performs well. But the human speech has more energy in low frequencies than in high frequencies. Therefore, a NLMS gives good echo cancellation for low frequencies and poor echo cancellation for high frequencies.

KeywordsAdaptive Filter algorithms; LMS, NLMS; Frequency-domain block LMS, FPGA

1. INTRODUCTION

   A hands-free telephone or full-duplex intercom system has a feedback or echo problem because the output from the loudspeaker feeds into the microphone. Echo is a delayed and distorted version of an original sound or electrical signal which is reflected back to the source. In data communication, the echo can incur a big data transmit error. In applications like hands-free telecommunications, the echo, in extreme conditions, can make the conversation impossible. The echo has been a big issue in communication networks. Hence there is a need for the development of an effective way to control the acoustic echo in hands-free communications. In modern communication systems, receiver should have a wider frequency range and D i g i t a l s i g n a l processing capabilities in complex signal. An adaptive digital filter is the best option that can improve the receiver sensitivity

   under the condition of low signal to noise ratio (SNR). Adaptive filters can process data without any prior information about signal environment and the received signals. The study of adaptive digital filters with high- speed data processing capabilities is currently an important issue in signal processing fields and the rapid advancement in digital technologies has supported the implementation of sophisticated digital signal processing algorithms for real-time applications. Especially, with the development of FPGA (Field Program Gate Array), many signal processing algorithms can be implemented, which are theoretically reasonable but could not be implemented for the hardware design previously. It is urgent that more complex, larger amount of high-speed data signals be processed on FPGA chip. In communication system, repeater plays an Big role in the coverage and optimization of net-works. The weak received signals will first be amplified by a repeater, and then are emitted to potential coverage area by the transmitting antenna, so as to realize the extension and coverage of communication networks. However, due to the same-frequency transmitting characteristics, without taking effective measures, the signals emitted by the transmitting antenna will be caught by the receiving antenna from the same repeater some time later, which may lead to the strong interference to the effective signals, which is echo interference. The interference will have a bad influence on the communication. It may even cause the impossibility of communication in severe case. To deal with the problem of echo interference, traditional methods involve keeping some distance between the receiving antenna and the transmitting antenna when installing the repeater so as to effectively isolate signals. With the development of digital signal processing technology and large scale programmable devices, the adaptive echo interference cancellation technology has become the effective method to cancel echo interference in repeater systems. It can figure out the problem of spatial isolation of a repeater; meanwhile, it can greatly improve the quality of communication. This study focuses on the WCDMA repeater, under the tool of

   MATLAB. It carries out the model building and simulation research on echo interference cancellation system on the basis of LMS (Least Mean Squares) a n d NLMS (normalized LMS) adaptive filtering algorithm, symbolic LMS adaptive filtering algorithm, delay LMS adaptive filtering algorithm, frequency-domain block LMS adaptive filtering algorithm, and RLS (Recursive Least Squares) adaptive filtering algorithm. In the light of the easiness of hardware implementation and high-speed processing, comparisons are made between six kinds of adaptive filtering algorithm. Finally, the NLMS adaptive filtering algorithm and the frequency-domain block LMS adaptive filtering algorithm are chosen for further hardware design and programming realization. And, the performance of the filter system is verified.

2. BASIC PRINCIPLES OF ADAPTIVE FILTER ALGORITHM OF ACOUSTIC ECHO

   CANCELLATION

   Echo Cancellation the kind of time-varying, unknown with multi channel echo interference. This characteristic requires the filter can automatically track the changes of signals, and respond to the changes by adjusting the filter weight coefficient quickly. with the functions of the adaptive filter . Thus, the adaptive filter is what to be chosen for the echo in the channel interference cancellation. The principles of adaptive filtering echo interference cancellation is shown in Figure 1. In Figure 1, the signals emitted by the transmitting antenna will produce echo interference after multipath echo channel. The echo interference, superposed with the weak signals from the base station, enters into the receiving antenna and causes the echo interference to the repeater. The adaptive filtering algorithm uses the signals from the transmitting antenna as reference to adjust the weight coefficient of the filter so that the interference estimated value of echo channel is simulated by the filtering processing unit. Then the estimated value is subtracted from the receiving signals superposed with echo interference, thus the cancellation of echo interference is fulfilled. If only the transfer function of adaptive filter can fit well with the transfer function of the echo channel, reflecting the actual echo channel more truthfully, it will be possible to realize the complete cancellation of echo interference from receiving signals and get comm. signals of high-quality. Therefore, the key of realizing echo interference cancellation is adaptive filter.

   Fig. 1. The principle diagram of Acoustic echo cancellation of adaptive filter

   An adaptive digital filter can filter the time variant echo interference signals which exist in the communication channels; thereby high quality communication signals can be obtained. May researchers focus on the development of adaptive algorithm in mobile communication systems. Figure 2 shows the block diagram of an adaptive digital filter, where d(n) is a desired signal, y(n) filters output signal, and error e(n) adjusts the adaptive digital filter coefficients in a weight vector.

   In order to determine the optimal weight vectors, some algorithms have been studied. Among all the algorithms, Least Mean Square (LMS) is the most common. The others are the improvement based on the LMS algorithm.

   Fig. 2. An Basic digital adaptive filter block diagram

3. ADAPTIVE FILTER ALGORITHM ANALYSIS

   1. LMS Algorithm

      In 1960 Widrow and Hoff presented the LMS algorithm. LMS algorithm was Discuss based on Minimum Mean Square Error (MMSE) and the steepest descent algorithm.

      From LMS algorithm we know that

      y(n) =(i)x(n i + 1) = T X(n). (1)

      Where y(n) is the output at time n. The input signal x(n) is multiplied with the coefficients in a weight vector (n + 1) is estimated according to the following recursion:

      (n + 1) = (n) + x (n) e(n), (2)

      Where is a small positive constant, called the step

      size, which controls system stability and convergence rate. Because is a constant, convergence rate is slower, and maladjustment coefficient is still bigger when the system reaches steady state. It could be expressed as:

      = MPin. (3)

      M is filter order, Pin is input signal power. As can be seen from Equation (3), when the step size , input signal power Pin, or filter order M is large, the misadjustment coefficient is large. LMS algorithm cannot achieve both rapid convergence and small steady-state error simultaneously.

   2. Normalized LMS Algorithm

      Normalized LMS algorithm is an improved algorithm of LMS. NLMS algorithm will be easy to implement with faster convergence speed and accurate tracking capability [8]. Equation (3) shows misadjustment coefficient is constant if and

      Pin are inversely proportional to the change. Thus NLMS algorithm will be converged faster than LMS algorithm. (n + 1) is estimated according to the following simple recursion [8]:

      (n +1) = (n) + e(n)x(n), (4)

      xH (n)x(n) +

      xH (n)x(n) + = (n). (5)

      Where is a small positive constant, called the step size, whose value is between 0 and 1. A small constant is used to modify the algorithm to avoid the possible large step size which may result that the NLMS algorithm will be diverged when xH (n)x(n) is very small. As can be seen from equation (5), the step size (n) varies adaptively by following the changes in the input signal level. This prevents the update weights from diverging and makes the algorithm more stable and faster converging than when a fixed step size is used Figure 3 shows the MSE (Mean square error) plot or convergence for the LMS and the NLMS algorithm respectively, which have the same filter orders. As shown in Figure 3, for the same adaptation size or iterations, the NLMS algorithm can achieve much faster convergence than the LMS algorithm.

      Fig. 3. MSE plot for the LMS and NLMS algorithm respectively

   3. Recursive Least Squares Algorithm

      The Recursive Least Squares (RLS) algorithm is based on the least square criterion; difference square sum is to be minimized between reference signals and output signals of filter as the ultimate objective. The iterative equation of filter can be expressed as equation (6).

      (n) = (n 1) + R1(n 1)e(n)x(n), (6)

      where 0 <n 1 is genetic factor,

      R(n1) = E{x(n1)xT (n 1) the autocorrelation matrix at time n1 of input signals.

   4. Delay LMS algorithm

      Considering the slow convergence process, and the contradiction between step factor and convergence rate, Long and Herzberg proposed the delay LMS (DLMS) algorithm which is derived from the traditional LMS algorithm. Comparing with LMS algorithm, the delayed cycle number d in figure 4 used in updating the coefficients of DLMS algorithm is to generate the co- efficient at the next

      clock. Thus, the throughput of DLMS algorithm data is twice as that of LMS, which is more suitable for the high-speed signal processing[9]

      Fig. 4. Block diagram of DLMS algorithm

      The iterative equation of filter can be expressed as equation (7).

      (n) =(n 1) + 2 e(n d)x(n d), (7)

      Where the parameter d is the delayed cycle number, which is introduced when the weight coefficients are updated.

4. ADAPTIVEINTERFERENCECANCELLATION

   SYSTEM SIMULATION COMPARISON

   Figure 5 shows the simulation model block diagram, which indicates WCDMA source, echo interference Cancellation block, Wiener Baseband Power Amplifier (PA), synchronization module and multipath channel. The signals from the WCDMA source are in- putted to the system. Output signals from the echo cancellation block (Point C) are amplified by the power amplifier and then fed back via multipath channel to the input terminal as interference signal. The interference signals mix with the WCDMA source signals and together enter the echo cancellation block. Mean- while, the output signals of the power amplifier serve as the reference signal of the cancellation block (Point G). The cancellation of echo interference is processed in the baseband. The original bandwidth of WCDMA source is

   3.84 MHz, and the stop band bandwidth becomes 4.6848 MHz via a shaping filter with roll off factor 0.22. The cancellation block adopts several algorithms, including LMS adaptive filtering algorithm, NLMS adaptive filtering algorithm, sign LMS adaptive filtering algorithm, DLMS adaptive filtering algorithm, frequency-domain block LMS adaptive filtering algorithm, and RLS adaptive filtering algorithm. In the simulation process, the multipath echo interference is three-path, and the order of the filter is 128, and the step size of the simulation 0.00008. For each kind of adaptive algorithm, echo interference cancellation simulation is implemented to input signals with the signal to interference ratio -10, 0, 10, respectively.

   Fig. 5. Adaptive echo interference cancellation system simulation model block diagram

   In analyzing the PSD curve and the constellation of simulation results, it turns out that there is some

   improvement in the distribution on constellation for the sign LMS adaptive filtering algorithm. The output signals are not flat enough on the in-band PSD curve, which varies from the PSD curve of the source signals. Moreover, the attenuation of out-band does not reach the objective of 40dB when the signal to interference ratio is -10. This shows that sign LMS adaptive filtering algorithm does perform some inhibiting ability to multipath echo interference. However, the effect is not satisfying while the other five sorts of adaptive filtering algorithm perform excellent echo cancellation ability judging from the PSD curve and the constellation of simulation results and it can meet the design requirement of the echo cancellation system. In the view of the easiness to implementation on FPGA chips, this paper discusses the convergence rate and the usage of resource of five adaptive algorithms-LMS, NLMS, DLMS, frequency- domain block LMS and RLS, and the one that best fit for high-speed signal processing and implementation on FPGA is chosen.

   As for the convergence rate, on the same condition of 128 order and 0.00008 step size, RLS has the highest convergence rate, followed by frequency-domain block LMS, NLMS, DLMS, and LMS in sequence. When the tap number of filter M is 512, frequency- domain block LMS is

   8.8 times faster than LMS, and 16 times faster when M is 1024 and the usage of resource: if the length of the data blocks to be processed is M, LMS will need to operate corresponsive 2M2 times multiplication operation; sign LMS will need M2 times multiplication operation; frequency- domain block LMS will need 10M× log2 M + 26M times multiplication operation; RLS will need (2M2 + 4M)M times multiplication operation and twice division operation; and NLMS wll need multiplier little more than LMS when adopts optimization algorithm.

   RLS has the highest convergence rate but huge us- age of resource. Sign LMS has the least usage of re- source, but it cannot give satisfying filtering effect. LMS is too slow at the convergence to satisfy the requirement of the high-speed signal processing, though the usage of resource is relatively small and satisfying filtering effect. Therefore, this paper adopts NLMS adaptive algorithm and frequency-domain block LMS adaptive algorithm to design the adaptive echo interference cancellation system.

5. NLMS ADAPTIVE ALGORITHM FILTER IMPLEMENTATION ON FPGA

   In this work, we considered a NLMS algorithm adaptive filter with 17 orders. T he filter has 16-bit- wide input data and output data. The FPGA chips supported by Xilinx Company are the Virtex5 series. The program was written by verilog HDL language. The ISE s imulation software was used to run simulation for the designed system. Equation (5) shows that (n) can be expressed by a division formula. Because the value of is between 0 and 1, the product of (n) and e(n) can be obtained by shift operation to reduce the computational complexity. According to segmentation and approximation method, shift operation was adopted instead of division. In addition, appropriate expansion and interception

   must be considered for every calculating result to prevent data overflow. NLMS algorithm adaptive filter structure is shown in Figure 6.

   Fig. 6. NLMS algorithm adaptive filter structure

   In Figure 6, each block represents a computing node. The adaptive algorithm parts consist of multiplier, decision device, and shifter.. The decision device which is based on

   case select structure chooses shift factor according to the

   different range of xH (n)x(n). The shifter implements shifting and interception for error e(n). The multiplier,

   decision device, and shifter delays 1 clock period respectively, so x(n) must be delayed 3 clock periods to avoid time sequential con- fusion. It reduces 17 clock periods and speeds up data processing that the multiplier, decision device, and shifter replace a divider. The parallel

   adder will adds up the weight coefficient of each tap to the

   corresponding product of x(n). The function of Z3 will produce 3 clock periods of delay to input signal x(n).

   Fig. 7. The Comparison between the PSD curves before and after the interference cancellation when the signal to interference ratio is -10. (a).Before (b). After the interference cancellation

6. PERFORMANCEANALYSISOFTHE NLMS ADAPTIVE ECHO CANCELLATION

   SYSTEM

   With the help of verilog HDL hardware programming language, program for the NLMS adaptive filter algorithm,

   synthesize in the environment of ISE, and achieve function simulation using ISE simulator. Based on the adaptive algorithm above, echo interference cancellation was implemented to the signals with the signal to interference ratio -10, 0, 10 respectively. Then the output data from Modelsim were imported to Matlab. By analyzing the PSD curve and the constellation of the imported data, estimate the performance of the adaptive echo interference cancellation system [10].

   Figure 7 and Figure 8 show the performance analy sis of NLMS adaptive echo interference cancellation system when the signal to interference ratio is -10. Before interference cancellation, the in-band PSD curve has wider fluctuation, and the distribution of the constellation is dispersal. While after interference cancellation, the in-band PSD curve becomes more flat and the out-band attenuation exceeds 40dB. This indicates that the NLMS adaptive echo interference cancellation system has remarkable inhibition ability to multipath echo interference.

   Fig. 8. The comparison between the constellation before and after the interference cancellation when the signal to interference ratio is -10. (a) Before the interference cancellation (b) After the interference cancellation

7. FREQUENCY-DOMAIN BLOCK LMS

   ADAPTIVE

   ALGORITHM FILTER IMPLEMENTATIONON FPGA

   Frequency-domain Block LMS adopts the 1/2 over- lapping- reserving method in the operation process. The number of the coefficients equals to the size of the data block, so as to get the highest computational efficiency. The frequency- domain block LMS algorithm overlapping based 1/2 reserving method cascades the input signals and the expected signals, con- ducts FFT, and then operates multiplication in frequency domain, which needs to be operated with fast convolution and relative calculation in time domain [12]. The basic block diagram of algorithm is shown in Figure 9 consists of 4 parts.

   1. ) Every M input signals x(n) in the time domain make

      up a block; every two cascaded data blocks con- duct N point fast Fourier transformation, and get transferred X (k) in the frequency domain. X (k) is the input of the adaptive filter. N is twice as much as M the number of the filter tap.

   2. ) Update the weight coefficient W (k) according to the input signal X (k) and error signal E (k) and obtain the estimated value of interference Y (k).

   3. ) Carry out inverse fast fourier transformation (IFFT) for the output signal of adaptive filter Y (k), and get the time domain signals interference estimated value y(n).

   4. ) Calculate the differences between the interfered signal d(n) and y(n), and get the signal e(n) in which the interference is removed. Transforming the signal e(n) by Fourier transformation will get the frequency domain value E (k), which can serve for generation filter tap coefficient of the next iteration.

   Fig. 9. The basic block diagram of frequency domain LMS algorithm

8. PERFORMANCEANALYSISOFTHEBLOCK FREQUENCY DOMAIN LMS ADAPTIVE

   FILTER

   Figure 10 and Figure 11 show the performance analysis of the frequency-domain block LMS adaptive echo interference cancellation system when the signal to interference ratio is –

   10. Before interference cancellation, the in-band PSD curve has wider fluctuation, and the distribution of the constellation is dispersal. While after interference cancellation, the in-band PSD curve becomes more flat and the out-band attenuation exceeds 40dB. This indicates that the frequency- domain block LMS adaptive echo interference cancellation system has remarkable inhibition ability to multipath echo interference.

   Fig. 10. The comparison between the PSD curve before and after the interference cancellation when the signal to interference ratio is -10 (a). Before the interference cancellation. (b). After the interference cancellation.

   Fig. 11. The comparison between the constellation before and after the interference cancellation when the signal to interference ratio is -10. (a) Before the interference cancellation (b) After the interference cancellation

9. CONCLUSION

After simulation research on six kinds of adaptive echo interference cancellation system on the basis of LMS adaptive filtering algorithm, NLMS adaptive filtering algorithm, DLMS adaptive filtering algorithm, sign LMS adaptive filtering algorithm, frequency do- main block LMS adaptive filtering algorithm, and RLS adaptive filtering algorithm, and the comparison between the performance of the effects of cancellation, convergence rate and the usage of resource, this pa- per selected NLMS adaptive filtering algorithm and the frequency-domain block LMS algorithm for further hardware design on FPGA.

Based on the analysis and comparison of the PSD curve and the constellation of NLMS and the frequency-domain block LMS adaptive echo interference cancellation system, it concludes that the frequency-domain block LMS adaptive echo interference cancellation sys- tem has better flatness on the in-band PSD curve and better convergence effect on the constellation. There- fore, frequency-domain block LMS adaptive interference cancellation algorithm is chosen as the design with high performance-price ratio. The more pints there exist, the more obvious advantages it will perform.

REFERENCES

1. Liu Mingchun and Li Guojin, Research on the application of self- adaptive frequency-domain LMS algorithm on interference cancellation, World Technology Research and Development, 1:pp57- 58, 2009.

2. Y. H. Gong, Adaptive filtering (Second Edition) time- domain adaptive filtering and smart antennas, Publishing House of Electronics Industry, BeiJing, 2003.

3. Y. Tian, W. B. Xu, and Y. W. Zhang, Wireless FPGA Design, Publishing House of Electronics Industry, BeiJing, 2008.

4. J.F. Meng and X.B. Hou, The simulation and realization of LMS adaptive filter, Electronic Component & Device Applications, Vol. 11(9), pp.67-73, 2009.

5. M. T. Islam and Z. A. A. Rashid, MI-NLMS adaptive beam forming algorithm for smart antenna sys- tem applications, Journal of Zhejiang University SCIENCE A, Vol.7(10), pp.1709-1716, 2006.

6. C. So, Modified LMS algorithm for unbiased im- pulse response estimation in nonstationary noise, Electronics Letters, Vol.35(10), pp.791-792, 1999.

7. J. Pesquet, G. Tziritas, and O. Macchi, Modified LMS algorithms for robust ADPCM, Proc. IEEE Acoustics Speech and Signal Processing(1990), IEEE Press, Mar. pp.1405-1408, doi:10.1109/ICASSP.1990.115652, 1990..