The present invention relates to methods of and apparatuses for identifying unknown systems such as transmission lines and spatial acoustical coupling.
As applications of identification of unknown systems with adaptive filters, echo cancellers, noise cancellers, hauling cancellers and adaptive equalizers are well known in the art. Pertaining prior art technique will now be described in connection with an echo canceller as an example, which cancels echo leaking from the transmitting side to the receiving side on the 4-line side of a 2-to4-wire hybrid transformer.
An echo canceller uses an adaptive filter having tap coefficients equal to more than those of the impulse response of the echo path. In operation, the echo canceller generates a psuedo echo (or echo replica) corresponding to the transmitted signal, and thus suppresses echo leaking from the transmitting circuit to the receiving circuit on the 4-line side of the 2-to4-wire hybrid transformer. Each tap coefficient of the adaptive filter is corrected by taking correlation between an error signal, obtained by subtracting the echo replica from the mixed signal including the echo and the received signal, and the transmitted signal. Typical examples of the tap coefficient adaptation algorithm of such an adaptive filter, are the LMS algorithm as disclosed in Proceedings of IEEE, Vol. 63, No. 12, December 1975, pp. 1962-1716 (Literature 1) and a learning identification method (LIM) disclosed in IEEE Transactions on Automatic Control, Vol. 12, No. 3, March 1967, pp. 282-287 (literature 2).
When a fixed delay is present between the point on the 4-line side, where the echo canceller is inserted, and the point where the hybrid transformer is located, the echo canceller requires a sufficient number of taps for covering both the maximum estimated fixed delay and the actual significant part of the impulse response. Thus, when the fixed delay is long, an enormous number of taps are necessary, thereby increasing the hardware size and the convergence time due to mutual interference of the coefficients. To solve this problem, an adaptive control method of coefficient arrangement is disclosed in IEEE Transactions on Circuits and Systems-11, xe2x80x9cAnalog and Digital Signal Processingxe2x80x9d, Vol.43, No.9, September 1996, pp. 629-636 (Literature 3). In this method, the position of the significant part of the impulse response is estimated, around which tap coefficient of the adaptive filter are adaptively located.
The gist of the method shown in Literature 3 is to roughly estimate the position of part position and arrange the tap coefficients in a limited neighborhood of the estimated position, thus reducing the convergence time. The convergence time until the taps are arranged at right positions is also reduced by dividing a queue, in which the indexes of taps without any coefficient are stored, into two queue, one corresponding to the waveform response part neighborhood and the other corresponding to the significant part and the other part than the significant part. The position of the significant is estimated from the absolute maximum value of the tap coefficients, and only a single tap coefficient arrangement range is estimated. Therefore, where a plurality of significant parts are present (these parts being collectively called multi-echo when echoes are concerned), the tap coefficient arrangement range should be expanded so as to cover all these parts. Therefore, where a long fixed delay is involved between two parts, the limiting effect on the coefficient arrangement is reduced, inevitably increasing the convergence time. To solve this problem, methods which permit fast convergence even with multi-echoes and concentration tap coefficients in the significant parts, are disclosed in Japanese Patent Disclosure No. 7-202766 (Literature 4) and IEEE Proceedings of International Conference on Acoustics, Speech and Signal Processing, Vol. III, pp. 41-44, April 1994 (Literature 5).
FIG. 24 is a block diagram showing the construction of the echo canceller proposed in Literature 4. In the adaptive filter shown in FIG. 24, (Nxe2x88x921) delay elements 201 to 20Nxe2x88x921 are provided for delaying a transmitted signal supplied from a transmitted signal input terminal 1. The taps provided are N in number including the one zero delay. L (N greater than L) coefficient generators 301 to 30L are provided for generating tap coefficients of the adaptive filter. Specifically, the adaptive FIR filter shown in FIG. 24, unlike the usual adaptive FIR filters, has a sufficient number of tap coefficients for realizing the substantial waveform response part excluding the flat delay part or parts, and adaptively arranges the tap coefficients therein. A routing switch 7 is provided for switching the connection between the delay elements and the coefficient generators. A tap control circuit 9 is provided for controlling the routing switch 7. Specifically, the routing switch 7 selectively transmits the outputs of L delay elements to the coefficient generators according to the data received from an output terminal 900 of the tap control circuit 9. The routing switch 7 supplies the outputs of L delay elements with the tap coefficient generators 301 to 30L and also to multipliers 401 to 40L, respectively. The multipliers 401 to 40L multiply tap coefficient values provided from the coefficient generators 301 to 30L and the delayed signals from the routine switch 7, and supplies the products to an adder 8. The adder 8 adds together the products from the multipliers 401 to 40L and provides the sum as an echo replica. The tap control circuit 9 supplies from its output terminals 9011 to 901L step size, which are used for coefficient adaptation. The tap control circuit 9 also supplies coefficient-clear signals from its output terminals 9021 to 902L to the coefficient generators 301 to 31L for clearing, i.e., zero resetting, the coefficients therein. Furthermore, the tap control circuit 9 receives from its input terminals 9031 to 903L tap position control signals, and uses these signals for generating the step size and the coefficient-clear signals.
The transmitted signal supplied from the transmitted signal input terminal 1 is transmitted from a transmitted signal output terminal 2 via a transmission line to a hybrid transformer 3, is coupled to the 2-line side thereof. Due to impedance mismatch, the transmitted signal partly leaks as an echo to the receiving side. The echo from a received signal input terminal 4 is supplied to a subtracter 5. The subtracter 5 subtracts the echo replica from the adder 8, and transmits the difference result to a received signal output terminal 6. The difference is also supplied as an error signal for coefficient adaptation to the tap coefficient generators 301 to 30L.
Assuming as the coefficient adaptation algorithm the LMS algorithm shown in xe2x80x9cAdaptive Signal Processingxe2x80x9d, 1985, Prentice-Hall Inc., USA (Literature 6), the value ci(k+1) of i-th tap coefficient after the (k+1)-th adaptation is given, using value ci(k) after k-th adaptation, as:
ci(k+1)=ci(k)+xcexcie(k)xc3x97(kxe2x88x92a(i))xe2x80x83xe2x80x83(1)
where xcexci is the step size corresponding to the i-th coefficient, e(k) is the residual echo, x(kxe2x88x92a(i)) is the input signal sample at (kxe2x88x92a(i) )-th coefficient adaptation, a(i) is a set of indexes to the delay elements selected by the routing switch 7, and L is the number of delay elements.
The coefficient generators 30i (i being 1 to L) may have a construction as shown in FIG. 25. As shown, a multiplier 31 multiplies the error signal and the step size by each other. A multiplier 32 multiplies the product output of the multiplier 31 and delayed signal supplied from the routing switch 7. An adder 33 adds the output of the multiplier 32, which represents a coefficient correction amount, and a coefficient value stored in a memory 34. The sum result of the adder 33 is fed back to the memory 34. The memory 34 delays the input coefficient value, and thus provides an adapted coefficient value. The memory 34 function to reset the coefficient value held therein to zero when it receives a coefficient-clear signal supplied from output terminal 902i (i being 1 to L) of the tap control circuit 9.
As is seen from the above description, the coefficients of the adaptive filter are coupled to only the delay elements which are selected by the routing switch 7. The taps which coefficients are coupled to, are referred to as active taps, and those without any tap coefficient coupled thereto are referred to as inactive taps. In actual adaptive coefficient arrangement, taps which are less in number than the actual total number are arranged as initial values at an uniform interval, for instance. The taps with these coefficients arranged for them in this way are active taps, and those without any coefficient arranged are inactive taps. Initially, the active taps may be arranged in the order of their indexes or randomly.
FIG. 26 is a block diagram showing the construction of the tap control circuit 9. The indexes to (Nxe2x88x92L) inactive taps are stored in memories 1101 to 110M, respectively, which constitute an FIFO (first-in-first-out) construction having a length of N/M. The indexes to the inactive taps are stored in groups, which are obtained by uniformly dividing the total taps and each consisting of N/M taps. These groups are referred to as tap groups. In the case with a total number of 20 taps and number of 5 tap groups, the number M/M of taps belonging to each tap group is 4. Representing the number of the tap index belonging to G(n) in braces, the tap groups G(n) (n being 1 to 5) are represented as:
G(1)={1, 2, 3, 4}
G(2)={5, 6, 7, 8}
G(3)={9,10, 11, 12}
G(4)={13, 14, 15, 16}
G(5)={17, 18, 19, 206}
of these indexes, those being inactive at present are stored in the corresponding memories. In the instant example, elements in group G(n) (n being 1 to 5) are stored in memory 110n.
For every Q coefficient adaptation, an index selecting circuit 112 selects one of the memories 1101 to 110L according to the tap group select signal supplied from a selection order memory 150, takes the index stored atop in the selected memory, and supplies the index as a new or updated active tap index to a tap index memory 114. In the tap index memory 114, indexes to L active taps which are not stored in the memories 1101 to 110L are stored. The tap index memory 114 supplies the active tap indexes as tap position control signal to the output terminal 900. The active tap indexes may be set initially in any order, that is, the tap index memory 114 may provide any initial index order. For example, the L indexes may be set initially in the order of their values or at random. As an example, a case will be considered, in which indexes to L taps, among the all indexes, are successively selected in the order of their values. In the example noted earlier, the indexes are arranged in the order of 1, 2, . . . , 20. Assuming that the number L of the active taps is L=3 and the number (N-L) of the inactive taps is N-L=17, three numbers of 1, 2 and 3 are selected in the order of their values as the active tap indexes, and are stored as the initial indexes in the index memory 114. The initial indexes in the memories 1101 to 110L involve indexes other than those in the index memory 114. In the above example, the indexes 4, 5, . . . , 20 among all indexes, other than the indexes 1 to 3, are selected and stored as the initial indexes in the corresponding memories of 1101 to 110L. After the initial index setting as described above, coefficients corresponding to the active tap indexes selected by the routing switch 7 are updated. The coefficient arrangement is updated by updating active taps for every Q coefficient adaptation. Coefficient rearrangement is made in the following way.
The minimum coefficient detecting circuit 116 receives the active tap indexes supplied from the index memory 114 and the outputs of the coefficient generators, i.e., coefficients, supplied to its input terminals 9031 to 903L, and detects the active tap index corresponding to the minimum absolute valued coefficient. The detected active tap index is supplied to the index memory 114, a distributing circuit 118, an evaluation circuit 120 and a coefficient clearing circuit 122. The coefficient clearing circuit 122 generates a coefficient-clear signal for coefficient generator corresponding to the supplied tap index, and transmits this signal to a corresponding one of the output terminals 9021 to 902L. The transmitted coefficient-clear signal is supplied to the corresponding coefficient generator to clear or reset the coefficient therein to zero. The evaluation circuit 120 determines the tap group, which includes the tap index supplied from the minimum coefficient detecting circuit 116, and supplies the index to the corresponding tap group to the distributing circuit 118. The distributing circuit 118 selects a memory among the memories 1101 to 110L, which corresponds to the tap group index supplied from the evaluation circuit 120, and transmits the tap index corresponding to the minimum coefficient supplied from the minimum coefficient detecting circuit 116. The transmitted tap index is stored in a memory 110i designated by the distributing circuit 118. The index memory 114 deletes, from its memory contents, the tap index supplied from the minimum coefficient detecting circuit 116, and stores the active tap index supplied from the tap index selecting circuit 112. In this way, the index memory 114 updates the stored active tap indexes.
A coefficient evaluation circuit 130 receives the coefficients supplied from the coefficient generators and the active tap indexes from the index memory 114, and calculates the sum of the absolute coefficient values for each tap group. The circuit 130 then rearranges these M sums of absolute coefficients in the order of greater values, and supplies the corresponding indexes to the tap groups in the rearranged order thereof as an xe2x80x9corderxe2x80x9d to a tap group selection data updating circuit 140. The coefficient evaluation circuit 130 also supplies sums of the absolute coefficient values as xe2x80x9ccoefficient sumxe2x80x9d to the tap group selection data updating circuit 140. The tap group selection data updating circuit 140 calculates a tap group selection order according to the received data, and supplies a xe2x80x9cselection orderxe2x80x9d representing the calculated selection tap group order to the selection order memory 150. The selection order memory 150 stores the xe2x80x9cselected orderxe2x80x9d, i.e., the tap group indexes rearranged in the order of selection, and supplies these tap group indexes successively in the selection order to the tap index selecting circuit 112. The tap group indexes may be initially set in any order in the selection order memory; for example, they may be set in the order of their values or at random. Representing the tap group indexes held in the selection order memory 150 by Z(n) (n being 1 to M), in the case of setting the tap group indexes in the order of their values as in the above example, Z(n) is initially set as:
Z(1)=1, Z(2)=2, Z(n)=3, Z(4) and Z(5)=5.
Read address pointer which prescribes the read address of the selection order memory 150 for reading data therefrom, is initially set at the forefront address thereof. That is, the forefront tap group index, i.e., Z(1)=1 in the above example, is supplied as the initial read address pointer to the tap index selecting circuit 112. According to this read address pointer, supplied as tap group selection signal, the tap index selecting circuit 112 first selects the memory 1101, takes out the forefront tap index stored therein, and supplies this tap index to the index memory 114. The read address pointer is updated according to an xe2x80x9cupdate signalxe2x80x9d provided from the tap group selection data updating circuit 140. Whenever an xe2x80x9cupdate signalxe2x80x9d is provided from the tap group selection data updating circuit 140, the selection order memory 150 increments the read address pointer designating a stored tap group index by one.
The coefficient evaluation circuit 130 takes the absolute values of the supplied coefficients, and sums up these absolute values for each tap group. The coefficient evaluation circuit 130 further calculates the ratio of the maximum value Cmax among the sums of absolute coefficient values for each tap group to each sum. Denoting the absolute coefficient values for the j-th tap group by Cj,max (M being the number of the tap groups and 1xe2x89xa6jxe2x89xa6M), the ratio is calculated as Rj=Cj,max/Cmax. The calculated ratio is supplied to a step size generator 160. The same result as above is also obtainable by defining the sum of absolute coefficient value in all tap groups as Cmax. The step size generator 160 generates step sizes according to Rj supplied from the tap coefficient evaluation circuit 130, the generated step size being transmitted to the corresponding output terminal 901i (i being 1 to L). The step size xcexcj is obtained as the product xcexcj=xcexcxc3x97Rj of Rj and a predetermined constant. The mapping between j and i (1xe2x89xa6ixe2x89xa6L) is calculated according to the tap position control signal supplied from the index memory 114 such that the step size used for coefficient adaptation in the j-th tap group is xcexcj. The step size xcexcj is transmitted to the tap coefficient generator 30i according to the calculated mapping. The step size calculation method as described above, permits an increased step size for the coefficients in tap groups consisting of large absolute value coefficients and reducing the convergence time of the adaptive filter.
FIG. 27 is a block diagram showing the internal construction of the tap group selection data updating circuit 140. The xe2x80x9ccoefficient sumsxe2x80x9d from the coefficient evaluation circuit 130 is supplied to a selection time calculating circuit 1401. The selection time calculating circuit 1401 calculates a selection time, during which the tap group selection is continued, according to the xe2x80x9ccoefficient sumsxe2x80x9d. Specifically, the selection time is set to be long for a tap group with a large sums of absolute coefficient values, so that new active tap setting is done only in that tap group. For example, it is described in Literature 5 that the selection time Tj (j being 1 to 5) of j-th tap group in the above example can be expressed as:                     Tj        =                                            Aj                              A                max                                      ·                          (                                                T                  max                                -                                  T                  min                                            )                                +                      T            min                                              (        2        )            
where Aj is the sum of absolute coefficient values in the j-th tap group, Amax is the maximum value among the sums of absolute coefficient values in each tap groups, and Tmax and Tmin are the maximum and minimum selection times, respectively. Specifically, the selection time is set to Tmin for the tap group with the minimum sum of absolute coefficient values, Tmax with the maximum absolute tap coefficient value sum tap group, and to a time corresponding to the sum of absolute coefficient values for the other tap groups.
The selection time Tj is generally expressed in units of number of coefficient adaptation times. This value is supplied to a counter 1402. The counter 1402 counts coefficient adaptations, and whenever the number of tap coefficient adaptation times reaches Tj, it supplies a read address updating signal to a counter 1403. The counter 1403 counts read address signals supplied from the counter 1402, until its count reaches the total number M of tap groups, and supplies a tap group selection order update signal to a switch 1402, while resetting its count to zero. Upon reception of the tap group selection order update signal, the switch 1404 is closed to pass the tap group indexes, which are supplied as xe2x80x9corderxe2x80x9d from the tap coefficient evaluation circuit 130, in the supplied order as a xe2x80x9ctap group selection orderxe2x80x9d. The output signal of the tap group selection order updating circuit 140 is written in the group order memory 150 from the forefront address thereof. As a result of this writing operation, the tap group selection order held in the selection order memory 150 is updated.
As is obvious from the above description, the tap control range is successively shifted over the entire taps, and it is thus possible, even when substantially a plurality of significant response parts are present as multi-echoes, to obtain fast convergence and arrange the tap coefficients only in the significant response parts. In addition, tap indexes taken out from one of the memories 1101 to 110L always becomes active, thus leading to no waste of operation. Furthermore, when the tap index selecting circuit 112 determines the index to a tap to be newly arranged, the longest time is selected for a memory corresponding to the most significant tap group, is first selected. The coefficients thus can be arranged at the correct taps in a short period of time, permitting reduction of the convergence time. Moreover, it is possible to vary the step size in coefficient adaptation according to the importance of the tap group including each coefficient, thus further reducing the convergence time.
However, when a highly nonstationary signal such as a speech signal is supplied to the prior art adaptive filter as described above, errors in coefficient values and positions result from adaptation thereof executed while the input signal amplitude is small. This is attributable to the facts that the low input signal amplitude is readily disturbed by additive noise or the like and that adaptation of coefficients and positions executed with such an input signal is inaccurate.
An object of the present invention is to provide a method of and an apparatus for unknown system identification with an adaptive filter, which is free from errors in coefficient values or their positions even when a highly nonstationary signal is supplied.
According to an aspect of the present invention, there is provided a method of unknown system identification with adaptive filter comprising the steps of storing, as active tap indexes, active tap indexes provided with coefficients used for multiplying and adding operations, among the taps of and adaptive filter, arranging coefficients for only the active taps, storing, as inactive indexes in a queue, tap indexes without provision of any coefficient used for multiplying or adding operation, making, after updating the coefficients corresponding to the active tap, the tap indexes provided with coefficients of small absolute values to be inactive, storing the inactive tap indexes at the end of the queue, obtaining, when identifying an unknown system by using the adaptive filter for adaptively controlling tap positions by taking out the forefront inactive tap index in the queue and making the taken-out tap index active, evaluation function values corresponding to input signal samples of the adaptive filter, and stopping the coefficient adaptation and adaptive tap position control according to the result of comparison of the obtained evaluation function values with a predetermined threshold value.
According to another aspect of the present invention, there is provided a system of unknown system identification with an adaptive filter for making tap coefficient adaptation by using an error signal obtained by subtracting an identifying signal provided from the adaptive filter from the output of the unknown system, comprising a plurality of cascade-connected delay elements for delaying the input signal of the unknown system, a routing switch for selectively passing some of the delayed signals from the delay elements, a plurality of coefficient generators for generating tap coefficients by receiving the output signal of the routing switch, the error, a coefficient-clear signal and step size, a plurality of multipliers for multiplying the coefficient values provided from the coefficient generators and output signals of the routing switch by one another, an adder for adding together the outputs of the multipliers and thus providing the identifying signal, a subtracter for subtracting the identifying signal from the output of the unknown system and thus obtaining the error, and a tap control circuit for generating a tap position control signal for controlling the routing switch, the coefficient-clear signal and the step size by receiving the input signal samples, the outputs of the delay elements and the coefficient values provided from the coefficient generators, the tap control circuit including an input signal evaluation circuit for setting the step sizes to zero and also stopping the updating of the tap position control signal according to the input signal samples and evaluation function values corresponding to the outputs of the delay elements.
According to other aspect of the present invention, there is provided a system of unknown system identification with an adaptive filter for making coefficient adaptation by using an error obtained by subtracting an identifying signal provided from the adaptive filter from the output of the unknown system, comprising a plurality of cascade-connected delay elements for delaying the input signal of the unknown system, a routing switch for selectively passing some of the delayed signals from the delay elements, a power level evaluation circuit for evaluating the power level of the input signal by receiving the output signal of the routing switch, a plurality of coefficient generators for generating coefficients by receiving the output signal of the routing switch, an error, a coefficient-clear signal, step sizes and the input signal power level, a plurality of multipliers for multiplying the coefficients provided from the tap coefficient generators and output signals of the routing switch by one another, an adder for adding together the outputs of the multipliers and thus providing the identifying signal, a subtracter for subtracting the identifying signal from the output of the unknown system and thus obtaining the error, and a tap control circuit for generating a tap position control signal for controlling the routing switch, the coefficient-clear signal and the step sizes by receiving the input signal samples, the outputs of the delay elements and the coefficient values provided from the coefficient generators, the tap control circuit including an input signal evaluation circuit for setting the step sizes to zero and also stopping the updating of the tap position control signal according to the input signal samples and evaluation function values corresponding to the outputs of the delay elements.
Other objects and features will be clarified from the following description with reference to attached drawings.