Filter coefficient estimation apparatus

Description Submit all comments and votes

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to an improvement of an apparatus for estimating coefficients for an adaptive filter which emulates signal transmission characteristics from a known signal, which is sent to a signal transmission system of unknown characteristics, and the response thereto.

A filter coefficient estimation apparatus according to the present invention can be applied, for example, to an apparatus which updates the coefficients of an adaptive filter used in an acoustic echo canceler or an active noise control system. The adaptive algorithm used to implement these apparatuses must, in addition to having convergence speed and stability and require a small amount of processing, must have low cost when its commercial use is considered.

2. Description of the Related Art

FIG. 1 and FIG. 2 show typical examples of apparatuses in which an improvement in operation is expected by the application of the present invention. The descriptions to follow use the examples of these apparatuses.

First, the apparatus shown in FIG. 1 is an apparatus known as a hands-free telephone which makes use of an acoustic echo canceler 200 which has the effect of reducing the acoustic coupling between a speaker 201 and a microphone 202, thereby enabling hands-free two-way communication. Specifically, this apparatus is made up of the acoustic echo canceler 200 and a signal transmission system 100, the signal transmission system 100 including a speaker 201, a microphone 202 which inputs the voice of the near-end talker, and the acoustic echo canceler 200 including an adaptive filter 220 which emulates the signal transmission system 100, a subtractor 210 which eliminates the echo from the signal picked up by the microphone 202, and a coefficient updating circuit 230 which performs updating of the coefficients of the adaptive filter 220.

In the apparatus shown in FIG. 1, the far-end talker's signal (corresponding to the above-noted known signal) Xj, which is sent to the signal transmission system, which includes the speaker 201, is the echo (corresponding to the above-noted response of the above-noted signal transmission system), which is fed back to the microphone 202.

gj=.SIGMA.hj(i)Xj(i) (1)

In the above equation:

j: Time (sample time index, iteration)

.SIGMA.: Summation from i-1 to I

hj(i): i-th sample value of the impulse response hj (impulse response at the time i) of the signal transmission system (echo path) from the speaker to the microphone

Xj: i-th sample value of the far-end talker's signal Xj which is the echo (far-end talker's signal at the time j)

I: Delay time given by the largest sampling period detected as an echo

The acoustic echo canceler cancels out this echo gj by subtracting from it an echo replica Gj expressed by equation (2), this being synthesized by a nonrecursive (Finite Impulse Response) adaptive filter 220, using the subtractor 210.

Gj=.SIGMA.Hj(i)Xj(i) (2)

In doing this, the number of taps on the adaptive filter is equal to the maximum echo delay I.

The degree to which the echo is canceled as a result of this subtraction can be measured by the error between the filter coefficient Hj (i) of the adaptive filter, which is computed by the coefficient updating circuit 230, and the impulse response hj (i) which is established by the transmission characteristics of the signal transmission system 100, this error being expressed as given in equation (3).

.DELTA.j(i)=hj(i)-Hj(i) (3)

The effect of using the acoustic echo canceler is maximum when the following difference (residual echo) is minimized.

Ej=.SIGMA..DELTA.j(i)Xj(i)+Nj (4)

In the above equation, Nj is periodic noise.

In the configuration example shown in FIG. 1, the coefficient updating circuit 230 is equivalent to the filter coefficient estimation apparatus of the present invention, this coefficient updating circuit 230 being configured as a filter having an impulse response which describes the characteristics of the signal transmission system 100, this being achieved by adjusting the filter coefficients Hj(i) of the adaptive filter 220 so that the above-noted difference Ej is a minimum.

The apparatus shown in FIG. 2 is known as an active noise control system, which eliminates, within a duct 300, the noise generated by a fan 305, the configuration of this apparatus including a detection sensor microphone 302 which collects noise, a noise-control filter 320 which generates pseudo-noise, a speaker 303 which outputs pseudo-noise, an error-sensor microphone 304 which collects the error which is the noise not eliminated, a feedback control filter 310 which emulates a feedback system, a coefficient updating circuit 340 which performs updating of the coefficients of the noise control filter 320, and an error path filter 330 which emulates the system from the noise control filter 320 to the coefficient updating circuit 340 via the error sensor microphone 304.

The principle of this active noise control system is that of outputting from the speaker 303 a pseudo-noise that has the same amplitude as, but the reverse phase to, the noise flowing in the duct 300 at the position of the error-sensor microphone 304, thereby canceling out the noise at the position of this microphone and reducing the noise that flows to the outside of the duct. However, in the description herein, it will be assumed that the feedback of pseudo-noise occurring in the system formed from the speaker 303 to the detection sensor microphone 302, this system being not directly related to the present invention, is completely canceled out by the output of the feedback control filter 310.

In this apparatus, the above-noted "signal transmission system of unknown characteristics" corresponds to the noise transmission system from the detection sensor microphone 302 to the error-sensor microphone 304, the signal being sent to the signal transmission system corresponds to the fan noise Xj that is collected by the detection sensor microphone 302, the filter that emulates the characteristics of the signal transmission system is the noise control filter 320, and the coefficient updating circuit 340 corresponds to the filter coefficient prediction apparatus of the present invention.

In this active noise control system, the coefficient updating circuit 340 adjusts the coefficients Hj of the noise control filter 320 so that the output ej of the microphone 304 is a minimum. In this condition, the radiation of noise to the outside of the duct is also a minimum.

The problem is the configuration of the coefficient updating circuit which computes the filter coefficients Hj. There have been, of course, a variety of proposed methods, each with its own characteristics. However, in considering the practical implementation of the apparatus, the configuration method should have the following characteristics.

Specifically, the configuration should be such that:

(a) each intermediate computation result should be neither larger than nor smaller than a limit imposed by the computation word length,

(b) stable operation should be guaranteed,

(c) the amount of computation performed should be small, and

(d) if possible, convergence should be fast.

In the past, the most typical algorithm for predicting coefficients for an adaptive filter which emulates the signal transmission characteristics from a known signal and the response thereto which are sent to a signal transmission system of unknown characteristics is the LMS method, shown below.

H.sub.j+1 (m)=Hj(m)+.mu.Ej Xj(m) (5)

m: Indicates the m-th tap on the adaptive filter

In the above relationship, .mu. is known as the step gain, the range of which is established in terms of the power function of the signal Xj which is sent to the signal transmission system. For example, when this power of the signal is large, the upper limit of .mu. for which coefficient updating can be performed stably becomes small, and when this power is small, this upper limit becomes large. Therefore, in practical applications, the value of .mu. is fixed at a value which does not exceed the upper limit in the case of the largest envisioned power. The convergence speed is known to be faster the larger the step gain is. For this reason, when the step gain is set in accordance with the maximum power of the signal Xj, since in normal operation the power of this signal is not maximum, the convergence speed results in unnecessarily slow convergence for the great majority of time during which the power of this signal is small.

This problem is solved by the application of a normalized learning identification method (the normalized least mean square (NLMS) method) in which the second term of Equation (5) is normalized with respect to the norm [.SIGMA.Xj.sup.2 (i)] of the signal sent to the signal transmission system, this being expressed by Equation (6).

H.sub.j+1 (m)=Hj(m)+KEj Xj(m)/.SIGMA.Xj.sup.2 (i) (6)

This learning identification method is widely known as an algorithm that is suitable for application to an apparatus, such as the acoustic echo canceler shown in FIG. 1, in which a voice signal having sharp amplitude variations is sent to the signal transmission system.

The applicability of an adaptive algorithm to the implementation of an acoustic echo canceler or active noise control system as described above is judged based on such performance parameters as high-speed convergence, stability, and small amount of computation performed, and at present the above-described learning identification algorithm is an algorithm which has a performance in these areas which allows practical use. However, study and work on improving the performance of this learning identification algorithm, and in particular in achieving fast convergence, is continuing.

Once satisfactory performance is achieved, and the development of these apparatuses reach the product stage, another factor, that of low cost, becomes significant. With respect to the demand for low cost, the approach of implementing the learning identification algorithm with fixed-point processing provides an effective solution. Firstly, it enables the use of a low-cost signal processor, and secondly, the significant improvement in processing speed enables a reduction in production costs by enabling the duct used for noise reduction to be made even smaller.

The problem that arises is one of whether the updated quantities that are computed and added to the adaptive filter coefficients each sampling period are smaller or larger than the limits imposed by the word length used for fixed-point processing. In the learning identification algorithm, this problem arises because, due to the normalization by the norm value, the coefficient updating values are held to within the reciprocal of the tap number (when the step gain K is less than 1, K times that value). That is, the problem occurs because of the facts that, in Equation (6), the norm [.SIGMA.Xj2 (i)] increases proportionally with an increase in the number of the tap I, and the numerator Ej Xj (m) decreases as the coefficient updating proceeds. When using a low-cost processor or computing filter coefficients Hj using fixed-point quantities in order to achieve fast computation (reduction in the number of processors), a large denominator and a small numerator cause the second term of Equation (6) to be smaller than the word length limit, thereby making the updating invalid.

If the update value is smaller than the word length limit, of course, the coefficient of the adaptive filter will not be updated. The possibility of this occurring is large if the number of taps on the adaptive filter becomes large or if the step gain is set to a small value because of a high level of ambient noise, and the larger this possibility is, the slower will be the convergence. In addition, if the error becomes small as the coefficient updating proceeds, there can be a loss of digits in the update values, so that further updating is impossible, thereby imposing a limit on the improvement of the estimation accuracy.

What follows is a further detailed description, in accordance with Equation (6), of the problems associated with using fixed-point processing with the learning identification algorithm in predicting adaptive filter coefficients. In Equation (6), the errors occurring when this equation is executed using fixed-point processing are separated into the component caused by the first term and the component caused by the second term. Specifically, the component associated with the first term, Hj(m) is equal to the part smaller than the word length limit which is discarded when the impulse response hj(i) (I=1 to I) of the echo path is converted to fixed point. Therefore, it is possible to limit the associated error component by carefully adjusting the gain of the amplifier, which is related to the far-end talker's signal Xj and the microphone output Yj (=gj+Sj+Nj, where Sj is the near-end talker's signal) thereby achieving an amplitude distribution so that the adaptive filter coefficients Hj(m) are sufficiently larger than the word length limit. If this level distribution is properly achieved, the influence of implementing the computation of the coefficients Hj of the adaptive filter using fixed-point processing can be ignored from a practical standpoint.

The problem lies with the component associated with the second term. To clearly identify the influence of fixed-point processing of the second term on the prediction error, first the residual echo Ej of Equation (4) is calculated from the echo gj of Equation (1) and the echo replica Gj of Equation (2), after which the m-th tap component is separated from the residual echo, and the numerator of the second term of Equation (6) is changed as follows. ##EQU1##

It is clear that update value for the m-th tap coefficient of the adaptive filter to be computed is given by the difference between the impulse response hj(m) of the echo path and the coefficient Hj(m) of the adaptive filter, this difference being expressed as follows.

.DELTA.j(m)=hj(m)-Hj(m)

However, in the learning identification algorithm, the quantity Dj(m)=.DELTA.j(m) KXj.sup.2 (m)/.SIGMA.Xj.sup.2 (i), which is obtained by substituting the above-noted Ej Xj (m) into Equation (6), is treated as the coefficient updating value. This causes a problem. Specifically, in fixed-point processing in which the smallest quantity expressible is 2.sup.-M, if the coefficient updating value becomes Dj(m)<2.sup.-M, it is clear that the coefficient updating will not be executed. The smaller the step gain k becomes and the greater the number of taps I the adaptive filter has, the greater is the probability that the coefficient updating value Dj(m) is smaller than the word length limit. If this probability becomes large, of course, convergence is delayed, and if because of the above-noted Dj(m)<2.sup.-M limitation only large estimation errors Dj(m) are used in updating, it is not possible to achieve high estimation accuracy.

FIG. 3 shows the convergence in the case in which all computations for Equation (6) are performed as floating-point operations, and a comparison with the convergence behavior for the case in which, after computing the second term using floating-point processing conversion is made to 16-bit fixed-point form before adding to the coefficient Hj(m). In the cases of both characteristics, the conversion between the analog signal and the digital is done as a linear 16-bit conversion, the number of taps I of the adaptive filter is 512, the step gains are the three values 0.01, 0.005, and 0.0025, and the power ratio of the echo to the environmental noise is 10 dB. The conversion from floating point to fixed point is performed by truncating the part of the values below the word length limit.

As is clear from the results shown in FIG. 3, in spite of the fact that the simplest computing method, that of "converting to fixed point after doing a floating-point processing of the second term," is used, the coefficient updating by fixed-point operations using the learning identification algorithm caused delay in convergence, given an example of a case in which it would not be possible to achieve a high estimation accuracy. From these results, it is verified that the selection of a small step gain has, on the contrary, a reverse effect with respect to the echo cancellation amount.

These phenomena occur in the same manner in the filtered-X LMS algorithm which is used in the active noise control system shown in FIG. 2, and are expressed as follows.

H.sub.j+1 (m)=Hj(m)+.mu.ej Yj(m) (7)

Yj: Prediction dispersion filter 330 output

ej: Microphone 304 output

They also occur in the same manner the filtered-X NLMS algorithm in which normalization to the output norm from the error path filter 330 is performed, and are expressed as follows.

H.sub.j+1 (m)=Hj(m)+KejYj(m)/.SIGMA.Yj.sup.2 (i) (8)

Because the above-noted normalization by a norm value is intrinsic to the principle configuration of the learning identification algorithm, it is difficult to solve problems which derive from this principle by merely performing scaling operations. Therefore, a solution in terms of an improvement in the algorithm itself is desirable.

SUMMARY OF THE INVENTION

In consideration of the above-described problems with the prior art, an object of the present invention is to enable the implementation of a filter coefficient updating apparatus for an adaptive filter which is capable of executing updating without processing invalid updating, even when there is a limit to the length of the word used in the computations.

FIG. 4 illustrates the principle of the present invention.

To solve the above-noted problems, the present invention provides a prediction apparatus which estimates filter coefficients for a filter with a response that is equivalent to the signal transmission characteristics from a known signal, and the response thereto, which are sent to a signal transmission system of unknown characteristics, this apparatus comprising a sum of products calculating means 110 which accumulates, over a prescribed period of time, the product of the difference between the above-noted signal transmission system response and the above-noted filter response and the above-noted signal sent to the signal transmission system, a sum of the squares calculating means 120 which accumulates, over the above-noted prescribed period of time, the sum of the squares of the above-noted signal sent to the signal transmission system, and a updating amount calculating means 130 which calculates the above-noted filter coefficient updating amounts from the results of the sum of the products calculating means and the results of the sum of the squares calculating means, the filter coefficient updating amounts calculated by the above-noted updating amount calculating means being used to update the filter coefficients.

The prediction apparatus of the present invention estimates coefficients by focusing on the fact that the value to be extracted as a coefficient updating value is the "difference between the impulse response of the unknown signal transmission system to be identified and the estimated value thereof." That is, utilization is made of the fact that, if coefficient updating values can be added as is, without the differences becoming small as in the identification method, the number of significant digits of the updating values can coincide with the number of significant digits of the adaptive filter, even if fixed-point processing is done, that is, the fact that problems do not arise because of lost digits. Specifically, in the present invention, this is determined as the ratio of the sums obtained by integrating both the product of the above-noted "difference between the impulse response and the predicted value thereof" and the signal sent to the signal transmission system, and the square of the signal sent to the signal transmission system, with respect to time. By doing this, the term of the expression used to calculate the coefficient updating which causes estimation error can be reduced, by the effect of arithmetic averaging, to a degree that is the reciprocal of the number of integrations, while in comparison with the previous learning identification method, the term corresponding to the coefficient updating value, because the division by means of the sum of the squares calculation is not included, does not of course exhibit a reduction in the number of significant digits caused by such a division, thereby eliminating the possibility that the coefficient updating will not be executed.

In the above-described prediction apparatus, the above-noted sum of the squares calculating means is configured to have a shift register which sequentially stores the squares of the signal sent to the above-noted signal transmission system, each output tap of this shift register being accumulation summed to calculate the filter coefficients at each tap.

By using this type of configuration, there is a reduction of one sum of the squares calculation of the signal sent to the signal transmission system per sampling period, enabling a reduction in the amount of computation required.

In the above-described predicting apparatus, the configuration can be made such that the filter coefficient updating is performed for the filter coefficient for one tap for each sampling period of a prescribed number of filter updates (for example 1).

By using the above-noted configuration, because it is possible to perform the updating of adaptive filter coefficients in the above-noted units of time, it is possible, for example, to change the configuration to one in which one configuration updating is performed each sampling period, thereby distributing the calculation processing for coefficient updating over each sampling period, this reducing the amount of calculation done at any one time.

Furthermore, in the above-noted prediction apparatus, the above-noted sum of the squares calculating means can be configured so as to have a shift register which stores the accumulated sum of the squares of the above-noted signal only at times corresponding to the taps of the above-noted filter, the filter coefficients for each tap of the above-noted filter being updated based on the contents of the above-noted shift register.

By using this type of configuration, it is not necessary to perform the calculation of the sum of the square of the signal sent to the signal transmission system at each sampling period, thereby reducing the amount of processing performed at each sampling period.

In addition, in the above-noted prediction apparatus, it is possible to have a configuration in which, rather storing the sum of the squares of the signal sent to the signal transmission system, the reciprocals thereof are stored in the above-noted shift register.

By using this type of configuration, by multiplying the reciprocals it is possible to perform an operation equivalent to division, thereby eliminating the division, and because multiplication involves less calculation that division, this reduces the amount of calculations performed.

In the above-described prediction apparatus, the configuration can be made such that the above-noted prescribed period of time for execution of the sum of the products is established as the time at which the sum of the squares of the signal sent to the signal transmission system reaches a pre-established value.

By using the above-noted configuration, it is possible to achieve the required echo reduction amount, even if the power of the signal sent to the signal transmission system is reduced, and the prescribed time period over which the summation is performed can be shortened (that is, updating of coefficients can be performed frequently) within the range in which this echo reduction amount can be achieved, this enabling a increase in the speed of convergence.

Additionally, in the above-described prediction apparatus, the configuration can be made such that the product of the step gain and the adaptive filter number of taps can be established as the lower limit with respect to the number of summations appropriate to the above-noted prescribed time for accumulation of the sum of the squares of the signal sent to the signal transmission system.

In the above-described prediction apparatus, it is possible to have a configuration that has a shift register which stores values related to the sum of the squares calculated by the above-noted sum of the squares calculating means and a means for performing writing control of the values related to the above-noted sum of the squares when a non-execute command (for example, 0) is encountered in the above-noted shift register in the case in which the sum of the squares calculated by the above-noted sum of the squares calculating means does not reach a prescribed value, the updating of the coefficients of each of the taps of the above-noted filter being executed by monitoring the tap outputs of the shift register, execution being done when the contents thereof are a value related to the sum of the squares, and execution not being done when the contents thereof are a non-execute command. In the above, a value related to the sum of the square can be the sum of the squares itself, a prescribed reference value, or the reciprocal thereof.

By using this type of configuration, it is possible to simplify the calculation of the sum of the squares of the signal sent to the signal transmission system.

Furthermore, in the above-described prediction apparatus, the configuration can be such that a shift register is provided as a device to provide notification of the time to execute the sum of the product accumulation, this shift register storing a flag that is set at the point at which the sum of the squares of the above-noted signal reaches a pre-established value, this flag enabling the determination the timing for the updating of the filter coefficients, the coefficients being updated by dividing by the pre-established value of the sum of the squares or by multiplying by the reciprocal thereof.

By using this type of configuration, it is possible to simplify the calculation of the sum of the squares of the signal sent to the signal transmission system, and to simplify, for example, the hardware configuration.

In addition, in this prediction apparatus, it is possible to have a configuration such that the constants for multiplication or division are given in the form 2.sup.k or 2.sup.-k.

By using this configuration, it is possible to execute the calculation by a shift operation, thereby reducing the amount of processing performed.

Furthermore, in the above-described prediction apparatus, it is desirable to have the configuration such that the step gain is established such that the ratio of the maximum value of the result of summing of the squares of the signal sent to the signal transmission system a number of times which is equal to the number of taps of the adaptive filter to the product of the expected sum of the squares for the desired prediction accuracy and the step gain is an integer, a register being provided for writing the sum of the squares of the signal sent to the signal transmission system required for the coefficient updating or the reciprocal thereof, the contents of this register being updated every I sampling periods which corresponds to the number of taps I of the above-noted adaptive filter, and the execution being executed in the case in which, at the time of the updating of the register contents, the sum of the squares of the signal sent to the signal transmission system has either reached or exceeded the above-noted maximum value.

In addition, in this prediction apparatus, it is desirable to have the configuration such that all of the sums of the squares stored into the above-noted register are given as multiples of the above-noted maximum value.

In the above-described prediction apparatus, it is desirable to have the configuration, in which such overflow monitoring is performed of the sum of the products of the products calculating means and the sum of the squares of the sum of the squares calculating means, or of the above-noted sum of the squares only, the sum of the products and the sum of the squares being halved when overflow of a monitored quantity is either predicted or detected, subsequent components to be added being multiplied by 1/2.sup.k that is established by the number of predicted or detected times k.

By using this configuration, it is possible to avoid erroneous operation caused by an overflow of accumulated values.

BRIEF DESCRIPTION OF THE DRAWINGS

The present invention will be more clearly understood form the description as set forth below, with reference being made to the accompanying drawings in which:

FIG. 1 is a drawing which shows an example of the configuration of a hands-free telephone

FIG. 2 is a drawing which shows an example of the configuration of an active noise control apparatus;

FIG. 3 is a drawing which illustrates the influence on convergence speed of using floating-point computation;

FIG. 4 is a drawing which illustrates the principle of the present invention;

FIG. 5 is a drawing which shows an embodiment of the filter coefficient prediction apparatus of the present invention in the form of a coefficient prediction circuit of an acoustic echo canceler;

FIG. 6 is a drawing which shows the results of a simulation which compares the convergence characteristics of the apparatus of an embodiment of the present invention with those of the learning identification algorithm of the prior art;

FIG. 7 is a drawing which shows the convergence characteristics of the embodiment apparatus obtained using fixed-point computation;

FIG. 8 is a drawing which shows the expression of a 1st-order recursive filter of the type of the present invention;

FIG. 9 shows an example of a coefficient updating circuit in the case in which the configuration is a simple implementation in accordance with the operating principle of the coefficient updating circuit of the present invention;

FIG. 10 shows an example of a coefficient updating circuit according to the learning identification algorithm of the prior art;

FIG. 11 shows an example of a circuit which performs a calculation of the far-end talker's signal power and can reduce the amount of computation in the present invention;

FIG. 12 shows an example of a circuit which updates I coefficients each sampling period and can reduce the amount of computation in the present invention;

FIG. 13 shows a comparison of the amount of computation in the learning identification algorithm and the present invention;

FIG. 14 is a drawing which shows an example of the convergence characteristics of the present invention with distributed updating;

FIG. 15 is a drawing which shows, for the present invention and the learning identification algorithm, the variation characteristics of the echo reduction amount with respect to the reduction in the ratio of the echo to ambient noise;

FIG. 16 is a drawing which shows, for the present invention and the learning identification algorithm, the difference in convergence characteristics with respect to the increase in the ratio of the echo to ambient noise;

FIG. 17 is a drawing which shows an example of a simplified circuit for performing normalized power calculation; and

FIG. 18 is a drawing which shows an example of a circuit which performs normalization using a constant as the normalizing power.

DESCRIPTION OF THE PREFERRED EMBODIMENT

A preferred embodiment of the present invention will be described in detail below, with reference being made to the related accompanying drawings.

FIG. 5 shows an embodiment of the present invention in the form of a filter coefficient prediction apparatus. In the apparatus of this embodiment, the above-noted example of the application of the present invention to an acoustic echo canceler of a hands-free telephone is shown, the coefficient updating circuit 230 of the hands-free telephone being implemented using the present invention. Therefore, in the apparatus of this embodiment, the far-end talker's signal Xj and the residual echo Ej from the subtractor 210 are input as input signals, and the updated coefficient H.sub.n+1 is output as the output signal to the adaptive filter 220.

In FIG. 5, the basic configuration of the coefficient updating circuit is such that Ej is the residual echo from the subtractor 210, which is the difference between the echo gj from the signal transmission system and the echo replica G.sub.1 which is synthesized by the adaptive filter 220, and Xj is the far-end talker's signal Xj from the circuit side. In this drawing, the reference numeral 11 denotes a sum of the products circuit which, over a fixed period of time only, sums the products of the above-noted residual echo Ej and the far-end talker's signal Xj sent to the signal transmission system, 12 is a sum of the squares circuit which, over the above-noted fixed period of time only, sums the squares of the far-end talker's signal Xj which is sent to the signal transmission system, 13 is an updating quantity calculating circuit which calculates updating am