Patent Translate Powered by EPO and Google Notice This translation is machine-generated. It cannot be guaranteed that it is intelligible, accurate, complete, reliable or fit for specific purposes. Critical decisions, such as commercially relevant or financial decisions, should not be based on machine-translation output. DESCRIPTION JP2000323962 [0001] FIELD OF THE INVENTION The present invention relates to the art of adaptive identification. In particular, but not exclusively, it is suitable for use with echo cancelers used for telecommunications. [0002] BACKGROUND OF THE INVENTION The linear adaptive identification featured by impulse response has been widely studied and many algorithmic solutions have been proposed in expert writing. [0003] The general problems that apply in many cases of practical application when identifying directly by transversal adaptive filtering are considered. [0004] FIG. 1 illustrates a system 10 to be identified, which is provided with a signal xt that changes over time. The response of system 10 to input signal xt is written as zt. 15-04-2019 1 The measurement of the response zt is necessarily performed by adding an interference component bt called observation noise. This observation noise bt, although it may contain noise (for example, white noise or traffic noise) to be precise, also includes a useful signal. The component bt interferes with the observation of the response zt and is called observation noise. The adder 12 in the drawing represents that the component bt considered to be an additive is overlapped with the component zt. The measured observation signal yt is thus the response of the real system 14 with the system 10 to be identified and the adder 12. [0005] The adaptive identification device 16 receives an input signal xt at a first input E1 and receives an observation signal yt at a second input E2. The signals xt and yt are amplified, filtered and digitized at the input of the device 16 by conventional elements not shown. The adaptive identification unit 16 comprises an identification filter comprising a programmable filter having a finite impulse response (FIR) expressed as Ht-1T = (ht-10, ht-11, ..., ht-1L-1). There are 18 and here (. ) T represents a transposed matrix. (In the present specification, the above-described formula represents, and the same applies hereinafter. The coefficients of the identification filter 18 are adapted such that this impulse response Ht-1T is representative of the impulse response of the system 10 to be identified. The filter 18 receives the digitized input signal xt and estimates the response zt of the system 10 * zt (herein the above expression represents and so on) give. [0006] The subtractor 20 removes the estimate * zt from the digitized observation signal yt, which gives an error signal et, which can be viewed as an estimate of the interference component bt. [0007] The updating unit 22 of the identification filter adapts the coefficients of the filter 18 based on the input signal xt and the error signal et, generally taking into account the adaptation phase μ. [0008] A number of algorithms have been proposed to automatically determine the coefficients of adaptive filter 18. 15-04-2019 2 For practical use, the creators of these devices have often been forced to seek a compromise between algorithmic speed, which is easy to control and implement, and mathematical complexity and numerical stability. . [0009] The LMS (least squares method) algorithm is the most widely used algorithm to adapt the impulse response of the FIR identification filter continuously over time. Such an algorithm efficiently implements a Wiener filter with L coefficients, which minimizes the average value of the power of the filter error in the stochastic approximation. It is defined by the following equation. et = yt−XtTHt−1 (1) Ht = Ht−1 + μetXt (2) where Xt = (xt, xt−1,..., xt−L + 1) T is the last L pieces of the input signal Represents a vector of samples of and μ represents the adaptation phase of the algorithm. The main advantages of this algorithm are that it is numerically less complex, easy to implement and robust against errors. Unfortunately, when highly interrelated signals (such as speech signals) are used to excite unknown systems, this algorithm rapidly degrades in convergence speed. [0010] To avoid these problems, special ones of the LMS algorithm are often used, incorporating an adaptive phase that can modify the parameters. This algorithm corresponds to LMS normalized or NLMS (<< Least Normalized Least Squares>), where the coefficients of the adaptive filter are updated according to the following equation. [0011] The optimum filter H opt of the unknown system 10 is an FIR filter of an order lower than L but equal, and equation (3) becomes the following equation. ΔHt = [I-μXt (XtTXt) -1XtT] ΔHt-1TμXt (XtTXt) -1 bt where Ht = Hopt-Ht represents an error in the estimated value of the filter coefficient at repetition t . This equation corresponds to the geometrical interpretation of the NLMS algorithm. In the case of μ 式, Eq. (4) spans the affine subspace, which is entirely 15-04-2019 3 determined by the matrix between the brackets and knowing the first shift given by the last term of Eq. (4) , Corresponding to the relaxed projection of the vector ΔHt−1. [0012] Several attempts have been presented with non-table materials (frequency domain and subband filter implementations) to derive new algorithms that converge faster than the NLMS algorithm. In the following, as in the case based on using a fluorescence filter, we will see the case based on changing the direction of projection of the NLMS. [0013] The convergence of the NLMS can be improved by changing the direction of projection, as described above. This analysis is based on the affine projection algorithm (APA), which is based on projections of many orders equal to P. As a result, the algorithm obtains better convergence properties for interrelated signals compared to the NLMS algorithm (corresponding to the special case of P = 1). P. Next APA algorithm (K. Oseki et al., Telecommunication Journal in Japan, 1984, 67-A, n. The characteristics are determined by updating the coefficients of the identification filter 18 according to the following equation: see p. 19-27 "Adaptive algorithm using orthogonal projection to affine subspace and its characteristics". et, P = Yt, P-& Xt, PHt-1 (5) Ht = Ht-1 + μ & Xt, P # et, P (6) where & Xt, P = (Xt, Xt-1, ..., Xt- P + 1) T (7) Yt, P = (yt, yt-1, ..., yt-P + 1) T (8) (In the present specification, the above & X represents , And the same expression below. In the above, et, P denotes a leading error vector, & Xt, P # = X X PT PT PT PT (& Xt, P & Xt, PT) -1 is the inverse of the Moore-Penrose matrix of L × P in general. Represents With these equations for updating the coefficients of the identification filter, the estimates of the subsequent error vectors et, Ppost are then equal. et, Ppost = Yt, P- & Xt, PHt = (1-μ) et, P (9) [0014] Assuming that the adaptation phase of the algorithm is single, the Pth-order affine projection algorithm cancels out the P subsequent errors defined in equation (9). This latter property explains whether the convergence behavior of the algorithm is very good. Unfortunately, in the basic one described in equations (5), (6), the theoretical complexity of such an algorithm is of the order of 2 LP + KinvP2, where Kinv is the equation (6) And the parameters L and P represent the number of coefficients of the identification filter and the order of the projection, respectively. 15-04-2019 4 [0015] In order to reduce this initial complexity, several fast versions of these algorithms are presented, which deal with splitting up similar autocorrelation matrices in a manner similar to the fast recursive least squares algorithm. Have. Such techniques can reduce the initial complexity to a more reasonable value of 2L + 20P next (see below). Steven L. Gay 高速 Fast Convergence and Low Complexity Adaptive Filter Algorithm Proc Proceedings of the 3rd International Workshop on Acoustic and Noise Control, Plestin-Les-Greves, France 1993-223-226, Steven L. Gay G Speech Projection Algorithm Applied to the Echo Cancellation of Speech》 Ph.D. Dissertion of the State University of New Jersy 1994, Steven L. Gay et al. 高速 High-speed affine projection algorithm》 ICASSP '95 Proceedings, pp. 3023-3026, 1995 Year, by M. Montazeri, “Une Famille d'algorithmes adaptatifs comprenant les algorithmes NLMS et RLS: application a l'annulation d'echo acoustique”, These de Doctorat de l'Universite de Paris Sud, 1994, M. Tanaka et al. Reduction of computation for high-order projection algorithm》 The Fall Seminar of the Institute of Electronics, Information and Communication Engineers, Tokyo, 1993) [0016] Numerous research papers have been submitted on how to improve the performance of adaptive identification systems using predictive composition. (See below M. Mbup et al. “LMS coupled adaptive prediction and system identification: statistical models and transition analysis” IEEE Transactions on signal processing, 42 n. 10, October, 2607-2615, S. Benjebara, Caracteristiques des signaux et capacite de poursuite des non-stationnarites aleatoires: apport des schemas predictifs et multiresolutions TheThese de l'Ubiversite des Sciences, des Techniques et de Medecines II, Tunis, 1997). Case studies have been able to illustrate two main configurations (symmetrical or asymmetric) for prewhitening the filter's excitation signal using adaptive filter techniques. The general principle as to whether an asymmetric configuration is processed is illustrated in FIG. [0017] This type of configuration essentially changes the signal used to update the coefficients of the adaptive filter and adjusts the autocorrelation matrix (the maximum and minimum of the eigenvalues of the autocorrelation matrix of this signal). Based on empirical methods aimed at 15-04-2019 5 converting to reduce the ratio). As a result, the coefficients are updated by the adaptation module 22 with the signal available at the output of the linear prediction circuit 24, where a prediction is performed from the M coefficients. The algorithm provided by the module 22 to update the L coefficient of the identification filter 18 corresponds to LMS (eq. 2) or NLMS (eq. 3). Similarly, the prediction circuit 24 is implemented as an adaptive filter with M coefficients obtained and updated with the LMS algorithm. [0018] Studies to analyze the performance obtained from this type of configuration particularly emphasize that there is a very strong correlation between the prediction module and the adaptation module of the system. In particular, this leads to an adaptation of the coefficient adaptive formula of the adaptive predictor 24 and that of the identification filter 18. This strong link also appears in the choice between the two adaptation stages, μP and μH, which creates regions of very low stability of the overall configuration. [0019] As a result, the author mentions the instability of the overall predictive configuration identification system, but it limits the prediction order used when always using values less than 4 to ensure relative stability. In addition, therefore, identification performance is limited. It is necessary to choose low adaptation stages μP and μ which are not compatible with the purpose of improving the convergence speed. [0020] The following conclusions can be drawn when looking at the solutions presented in the literature for improving the convergence speed of adaptive identification algorithms. One is that the algorithm based on updating the projection direction is still complicated, in that many mathematical processes are needed to update the filter coefficients when the projection order P is high The other is in terms of controlling and providing a reduced gain in convergence since the prediction order M actually used is low to ensure that the overall configuration remains relatively stable. Predictive configuration identification is still very cumbersome. 15-04-2019 6 [0021] The object of the present invention is to provide a method of adaptive identification which has good convergence properties and which is relatively easy to realize, but of limited mathematical complexity. [0022] SUMMARY OF THE INVENTION Accordingly, the present invention provides an adaptive identification method for estimating the response of a system to an input signal, comprising the steps of: Receiving, on the one hand, the input signal and, on the other hand, the observation signal which is partly a response to the input signal, and, at the time t, determining the error signal et according to the equation et = yt-XtTHt-1; Adapting the L coefficient of the discrimination filter taking into account the input signal and the error signal, where yt represents the value of the observed signal at time t, and Ht-1 is the value of the system A column vector consisting of L coefficients of an identification filter (18) having a typical finite impulse response of an impulse response, and XtT = (xt, xt-1,..., Xt-L + 1) represents time t and It is a row vector consisting of values xt, xt-1,..., Xt-L + 1 of input signals at preceding time L-1. By means of the invention, the prediction parameters of the input signal are observed, where the energy of the prediction residue on successive frames of the input signal is minimized and the L coefficient of the discrimination filter is {et / (XtTUt + λ)} Ut. Is adapted to be applied by adding it to a column vector Ht-1 proportional to where Ut is a column vector consisting of the L values of the predicted residual of the input signal at time t and the time L-1 preceding it, Is a positive or zero coefficient. [0023] In the preferred embodiment that provides this method,-the frame of the input signal has a duration of at least 5 ms. The frames of the input signal have mutual overlap. The input signal is analyzed by P-1 linear prediction, preferably equal to 5 or more orders, and the column vector U t is given by: where the term aq is the linear of the above analysis It represents the prediction factor. The order P-1 of linear prediction is also a function of the constancy of the input signal by guessing. The input signal is a speech signal reconstructed by the decoder from the input binary sequence, the prediction parameters of the input signal being extracted by the decoder from the input binary sequence, and the identification filter It is also possible to provide a prediction 15-04-2019 7 residue to adapt the L factor of. [0024] Another aspect of the invention relates to an adaptive identification device for a system, to which the input signal is provided, the first input receiving the input signal, and one of the elements therein being the input signal A second input receiving the observed signal, the identification filter having a finite impulse response of the system, and a subtractor producing the error signal et represented by equation (1) above; , Where the energy of the predicted residual on successive frames of the input signal is minimized, means for obtaining the prediction parameters from the input signal, and the column vector Ht-1 proportional to {et / (XtTUt + λ)} Ut And adaptation means for updating the L coefficient of the identification filter. [0025] Another aspect of the invention relates to an adaptive echo canceler for removing the echo component of a direct signal from a return signal, the first input receiving the direct signal as an input signal, and the observation signal as a return signal. , And a second input, the error signal being characterized in that it constitutes the output signal of the echo canceler. [0026] Other features and advantages of the present invention will become apparent from the following example of embodiment. The features are given by way of example and are not limiting in any respect, and reference is made to the accompanying drawings in which: -Figures 1 and 2 described above are block diagrams of adaptive identification devices known from the prior art. -Figure 3 is a block diagram of an echo canceler which can be combined with the adaptive identification device presented by the present invention. -Figure 4 is a block diagram of another embodiment of the echo canceller presented by the present invention. [0027] In the case of a stationary signal, the P-1 linear prediction coefficients a 1,. The following equation can be defined among (the matrix & Xt, P is defined by equation (7)). 15-04-2019 8 [0028] Assuming that an APA algorithm of order P, defined above, has an adaptation stage μ = 1, by canceling the following error (equation (9)) the leading vector (5): et, P = (et, 0, ..., 0) Simplify T, and the adaptive formula (6) of the identification filter is as follows, considering equation (10). Ht = Ht-1 + (et / XtTUt) Ut (12) [0029] Based on this, a variant of the APA algorithm of order P can be defined, hereinafter called “provisional APA algorithm of order P”, where the adaptation stage μ is selectively positive normalization constant λ Will be reintroduced. The error signal in the tentative APA algorithm is defined by equation (1), and the identification filter is updated according to: Ht = Ht-1 + {μet / (XtTUt + λ)} Ut (13) [0030] The adaptation phase μ is usually between 0.1 and 1 and λ ≧ 0. There are two differences in the provisional APA algorithm of order P compared to the linear reference identification scheme described above. The prediction factor aq is not evaluated at the speed of the sample but at the speed of the block. They correspond to minimizing linear prediction energy on a frame with N sample sizes. Predictor filter coefficient set {aq; q = 1,. . . , P-1}, effective implementation techniques can be used. The equation (13) used to update the coefficients of the identification filter Ht-1 does not correspond to that used in the studies already performed. In fact, it relies on an empirical approach aimed at whitening the excitation signal to improve the rate of mode convergence, which corresponds to the adjustment of the autocorrelation matrix of the excitation signal. As a result, the LMS or NLMS algorithm presented by the author as a means of updating the coefficients of the identification filter (and also of the predictor) does not correspond to that of equation (13). These algorithms depend on the normalization period included in the equation used to update the filter coefficients, and the term expressed as (UtTUt) -1 in LMS is decoded in equation (13) It is replaced by the term (XtTUt) -1 or (XtTUt + λ) -1. 15-04-2019 9 [0031] The method presented by the present invention solves the problems often caused by the strong correlation of the signals to be processed. In fact, in the latter case, conventional algorithms tend to lose good convergence properties. By means of the method presented by the present invention, these good convergence properties can be uniquely preserved and occur in fact frequently, even with very highly correlated signals. Limited arithmetic complexity to be stored is also possible, and implementing these identification algorithms in real time by a digital signal processor is a great advantage. [0032] The tentative APA algorithm forms the basis of a new set of adaptive identification devices that can be used in various fields (echo canceller, propagation channel equalizer automatic processing control, etc). In the case of automatic echo cancellation, this will be discussed below using a nonlimiting example. [0033] DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT FIG. 3 illustrates an adaptive echo canceler in combination with the adaptive identification device 16 proposed by the present invention. The echo canceler is combined with a hands-free telephone system. The input signal xt received at the input E1 of the device is a direct signal aimed at the loudspeaker 11 of the handfree system. The observation signal yt received at the input E2 of the device is a return signal picked up by the microphone 13 of the hand-free system. The observed signal yt contains the reverberation component from the direct signal and the disturbance component bt which may contain noise and speech emitted by the loudspeaker. This is the case if the system to be identified consists of an echo path or a path between the loudspeaker 11 and the microphone 13. [0034] The output signal from the echo canceler is the error signal et provided by the subtractor 20 from the observed signal yt and the echo estimate * zt produced by the discrimination filter 18. 15-04-2019 10 [0035] The time window of the input signal xt is at least the last L samples xt, xt-1,. . . , Xt−L + 1 are managed by the module 30. These L samples forming the vector Xt are (i) an identification filter 18 which filters according to the last term of equation (1), and (ii) an adaptation which updates the coefficients of filter 18 according to equation (13) The module 22 and (iii) the last L values of the prediction residual are provided to the prediction filter 32 which provides the adaptation module 22 with the vector Ut defined by equation (11). [0036] At each time t, the filter 32 only has to produce the first component of the vector Ut, i.e. the current value of the residue is and the other components have received the preceding samples Sometimes it was calculated and stored. [0037] In the example illustrated in FIG. 3, the prediction filter 32 is a conventional trellis configuration, and the prediction coefficients aq (1 ≦ q ≦ P) have reflection coefficients r1,. . . , RP-1 is represented by P-1. The reflection coefficient ri follows, for example, the well-known Levinson-Durbin algorithm based on the autocorrelation φ (i) of the input signal obtained by the module 34 and calculated by the module 36. The Levinson-Durbin algorithm implemented by module 34 can be expressed as: [0038] The reflection coefficient r i given to the filter 32 is obtained after the repetition P-1 in the same manner as the coefficient aq (aq = aqP-) of the equation (11). The quantity E (P-1) is the energy of the remaining misprediction. 15-04-2019 11 [0039] The correlation coefficient φ (i) is calculated by module 36 as follows. Represents an input signal multiplied by a conventional window function, such as a rectangle, Hamming, or other function. [0040] The calculation of the coefficients φ (i) and Levinson-Durbin's algorithm, equivalent to minimizing the prediction energy E (P−1), is performed on a frame of N samples of the input signal, where N is The number of the same order as the length L of the impulse response of the identification filter 18. [0041] As an example, if the signal is sampled at frequency Fe = 8 kHz, then filter 18 will have L = 256 coefficients and the frame size will be N = 160, ie the frame is 20 ms. It is a length. In the field of telephony, over such a period, the speech signal is almost fixed, demonstrating the justification of one of the assumptions in deriving the tentative APA algorithm from the APA algorithm. Generally, this frame period will be longer than 5 ms. [0042] The frames of the input signal processed by the predictive analysis module 34, 36 preferably overlap and allow non-stationary features of the signal to be considered. The prediction analysis is then performed every K samples of the input signal while K <N. As an example, the overlapping period between two consecutive frames would be on the order of 15 ms. In the case of the numerical example above, this corresponds to K = 40, and each frame constitutes four consecutive blocks. [0043] 15-04-2019 12 If N is a multiple of K, this will further simplify the calculation of the correlation coefficient by module 36. After receiving each block of K values of the input signal xt, calculating the partial correlation of each i corresponding to the recent K terms of equation (14), and the calculation has just been taken from It is sufficient to update the correlation φ (i) by adding a partial correlation such that the partial correlation previously calculated N / K blocks is removed. [0044] It should be pointed out that other techniques can be used to implement the prediction filter. For example, methods other than Levinson-Durbin's algorithm can be used to calculate different configurations for prediction filters based on reflection coefficient ri or reflection coefficient ri. Directly based on the prediction coefficient aq or LAR coefficient ("Log-Area-Ratio", LARi = log 10 [(1-ri) / (1 + ri)]) or alternatively LSP coefficient ("Line Spectrum Pair"), ... It is also possible to use other known configurations of the prediction filter. [0045] The device presented by the present invention shows the possibility to change the P-1 order of the prediction as a function of the simultaneous characteristics of the input signal. In particular, the stationarity of the signal xt is calculated by the module 36 to take a relatively high prediction order P-1 when the input signal is stationary and a lower prediction order when there is nonstationarity Correlation or partial correlation coefficients can be assessed by analysis. [0046] It is possible to evaluate the computational complexity of the tentative APA algorithm. The relevant features are illustrated in Table 1, where the features are compared to the exact algorithm of the N LMS or APA of order P, the configuration of which is typical of echo cancelers. In this table, P indicates the maximum order of the tentative APA algorithm that the circuit 16 can execute and the order of P that is effectively used in the comparative example. [0047] 15-04-2019 13 The computational complexity of the tentative APA algorithm is essentially that the discrimination filter has L = 256 coefficients, and every 5 ms of a 20 ms frame (K = 40, N = 160). ) Equal to the complexity of the coefficients to be evaluated with the prediction filter. Thus, the present invention presents an algorithm that determines the performance of the high-order affine control algorithm (generally 5 or more) at lower complexity than the order 2 exact affine projection algorithm. [0048] In terms of hardware, the identification unit 16 is configured from a commercially available circuit, in particular from a real time digital signal processor (DSP) with commonly used floating point arithmetic (eg sold by Texas Instruments, Inc. TMS320C3X or TMS320C4X, or AD21061 sold by Analog Devices. Fixed point arithmetic processors may also be used, at which time care should be taken regarding proper framing of the data being processed. [0049] In another embodiment illustrated in FIG. 4, the input signal xt is an audio signal reconstructed by the decoder 40 from the input binary stream Φ. This binary stream Φ is made in two towards the decoder 40 by the encoder and placed at the terminal used by the communication network or by remote speakers. [0050] As an example, the encoder / decoder corresponds to the RPE-LTP encoder used in the GSM cellular radiotelephone system (European Telecommunications Standards Institute = specification GSM 06.01 published by <European Telecommunications Standards Institute> reference). As used by most digital speech coders, this coder operates on the basis of linear prediction on the frame of the speech signal corresponding to the almost stationary area of the signal, and the requirements of the present invention Will meet. In the case of GSM, the frame is 20 ms. In the binary stream 中 among these, the encoder incorporates, on the one hand, the quantization parameters for the LAR coefficients described above which characterize the 10th-order linear prediction filter of the speech signal, and on the other hand the linear prediction residuals. Incorporate the quantization parameter of the excitation signal corresponding to. 15-04-2019 14 [0051] The decoder 40 has a circuit for recovering the excitation signal from the quantization parameter read from the stream Φ, and a synthesis filter which is the inverse of the 10th-order prediction filter to which the coefficient extracted by the quantized LAR is given. have. The synthesis filter receives the excitation signal and emits a composite audio signal xt. Thus, the decoder 40 can obtain linear prediction parameters from the stream Φ instead of the modules 34, 36 of the device illustrated in FIG. The prediction module (corresponding to the excitation signal of the synthesis filter) can also be provided to make the adaptation module 22 produce the components of the vector Ut required. [0052] It will be appreciated that in a device combined with a speech decoder and an adaptive echo canceler, using the tentative APA algorithm as illustrated in FIG. 4 does not add complexity compared to the NLMS regardless of the order P. I will. 15-04-2019 15

1/--страниц