Patent Description:
In an electronic device such as a smartphone, when audio data generated by executing an application is played out through the speaker, the audio data goes through software modules asynchronously where audio data is processed and finally arrives at the speaker. Due to these asynchronous transmission characteristics, there is a delay until audio data generated from the application is played out through the speaker, and this delay varies with the operating environment of the electronic device, for example, the hardware characteristics of the electronic device, the type or number of applications that are executed, the characteristics of the software module provided for audio data processing, the status of a platform, or the like. Accordingly, the delays, one delay occurring in an audio output process when music is played on the electronic device at a specific time point and, another delay occurring when the same music is played at a different time point may be different from each other.

Meanwhile, in the operating environment of an electronic device, it may be required to collect audio signals for recognizing a user's speech even while playing music or operating a navigation function. In the process of simultaneously playing out the audio data and collecting the user's speech signal, the audio signal output through the sapeaker may be fed back to the microphone in the form of an echo. Because the audio signal played out through the speaker corresponds to an interfering signal from the standpoint of a speech recognition function, there is a need to cancel the interfering signal. In order to cancel the interfering signal, the sound fed back to the microphone in the form of an echo must be removed using an echo canceller including an adaptive filter.

The above-described adaptive filter estimates an echo using a signal played out through the speaker as a reference signal and using a signal collected at the microphone as a target signal, and cancels the echo by subtracting the estimated signal from the microphone input signal during a filtering procedure. In this case, when variation in the time difference or time delay between the two signals is large, the length of the filter should be increased to cope with the large time delay variation. When this operation is described in detail, the time delay may be classified into two factors, as illustrated in <FIG>. The two factors include a pure time delay tr, occurring while an audio signal generated by an application passes through a non-acoustic path, and a time delay td, occurring while the audio signal passes through an acoustic path. For example, the delay tr occurring in the non-acoustic path may include a delay occurring during a procedure for copying/transferring an audio signal between adjacent software blocks, a delay occurring due to the delay inherent in the filter that is used in the sample rate conversion procedure, and the low-pass/high-pass filtering procedure, , or the like. Further, a pure delay may also occur when an audio signal is moved in the form of a digital signal in the physical hardware path. The pure delay tr causes only a time delay without transforming the moving sounds. In an impulse response of an echo path, a portion corresponding to a period of the pure time delay tr may ideally have a value of <NUM>.

The delay td occurring in the acoustic path may include a delay occurring in a procedure during which sound played out from the speaker flows in the microphone through the process of dispersion and reflection in the air. The delay td may occur along with changes in the amplitude and phase of sound. Here, td does not greatly vary within a range of about several tens of ms, but tr varies according to the product (e.g., the type of smartphone), and the range of variation may extend to several hundreds of ms. In particular, considering also the situation in which the audio connection path changes, that is, an environment in which the microphone of a vehicle is used while audio data from a smartphone is played out through the speaker of the vehicle via Bluetooth connection, variation in the delay time may further increase. Generally, an adaptive filter adopts the filter length that is about the sum of tr and td, and if the delay variation is large, the filter length of the adaptive filter should be increased, thus this causes problems in which the convergence time of the filter becomes longer, an error signal of filter is increased, and a computational load is also increased. The following publications discloses different solutions for acoustic echo cancellation that remain non-satisfactory:.

The present disclosure has been made keeping in mind the above problems and is intended to provide an adaptive filter, and a method for operating the adaptive filter, which can efficiently cancel an echo signal regardless of variation in a time delay occurring between a microphone input signal, which is the target of the adaptive filter, and a speaker output signal, which is a reference.

The present disclosure is intended to provide an adaptive filter, and a method for operating the adaptive filter, which can more efficiently support echo signal cancellation in a process for configuring a single smartphone application to be installed in multiple smartphone products.

Further, the present disclosure is intended to provide an adaptive filter, and a method for operating the adaptive filter, which can be operated efficiently even when a large change in time delay between a reference signal and a target signal occurs due to a change in the signal travel path.

Furthermore, the present disclosure is intended to provide an adaptive filter, and a method for operating the adaptive filter, which realize a short convergence time and a small error by utilizing an adaptive filter to which a short filter length corresponding to about td, which is a time delay on an actual acoustic path, is applied even in the situation in which variation in a pure time delay (pure delay) tr is large.

Furthermore, when the variation of the time delay is large, the number of sub-filters should be designed to be large. The present disclosure is intended to provide an adaptive filter, and a method for operating the adaptive filter, which can manage a computational load so that the computational load is not increased above a certain level by allowing sub-filters to share the calculated values of calculation formula required for calculating filter coefficient values and by further limiting or gradually reducing the number of active sub-filters using a pruning method.

Additional embodiments are defined by the dependent claims.

In accordance with the apparatus of the present disclosure, the present disclosure may provide an echo canceller using an adaptive filter, which may perform echo cancellation while adjusting or minimizing a computational load together with the realization of excellent convergence characteristics even if variation in a time delay between two signals is large when a signal played through the speaker is used as a reference signal of the echo canceller and a signal captured at the microphone is used as a target signal of the echo canceller.

Further, in a general signal transmission environment as well as an audio environment where a transmit signal transmitted from a transmitting end is modified while passing through the transmission path and is then received as a received signal at a receiving end, an adaptive filter may be used to estimate the impulse response of a transmission path or to estimate the desired signal using the transmit signal as a reference signal and the reception signal as a target signal of the adaptive filter. In this case, the present disclosure may perform efficient estimation even if variation in a time delay between the two signals is large.

Various other effects of the present disclosure will be additionally described with reference to the following embodiments.

In the following description, it should be noted that only parts required for understanding of embodiments of the present disclosure will be described, and explanation of other parts will be omitted so as to avoid making the gist of the present disclosure unclear.

It should be noted that the terms and words used in the specification and the claims, which will be described below, should not be construed as being limited to ordinary meanings or dictionary definitions, and an inventor can appropriately define the concepts of terms in order to best describe his or her invention. Meanwhile, the embodiments described in the present specification and the configurations illustrated in the drawings are merely preferable embodiments and do not exhaustively present the technical spirit of the present disclosure. Accordingly, it should be appreciated that there may be various equivalents and modifications that can replace the embodiments and the configurations at the time at which the present application is filed.

<FIG> is a diagram illustrating the normal form of the impulse response of a corresponding transmission path when a signal transmitted from a transmitting end of an electronic device moves through a transmission path and is then received at a receiving end.

In <FIG>, tr indicates an interval during which the impulse response has a value of <NUM> in an initial stage, and is a factor, which simply causes only a time delay when the transmitted signal is received and which occurs due to, for example, a transfer process attributable to signal copying. td is a factor, which causes signal modification as well as a time delay, and which occurs, for example, when a signal is moved in physical space, and is a principal portion of the impulse response.

The present disclosure relates to a method for efficiently estimating a system, which has an impulse response with large tr variation, through the use of an adaptive filter whenever an impulse response is measured. In particular, the present disclosure presents a method for yielding the same effect as that obtained when estimating the entire period of the impulse response by estimating a td interval using a small sub-filter, instead of directly estimating the entire period of the impulse response.

<FIG> illustrates an example of the configuration of an electronic device according to an embodiment of the present disclosure, and <FIG> is a diagram illustrating an example of configuration of a portion of an electronic device including an audio-processing unit according to an embodiment of the present disclosure.

Referring to <FIG>, an electronic device <NUM> according to an embodiment of the present disclosure may include memory <NUM>, a processor <NUM>, an audio-processing unit <NUM>, a speaker <NUM>, a microphone <NUM>, a display unit <NUM>, a communication circuit <NUM>, and an input unit <NUM>. Additionally, the electronic device <NUM> may further include a sensor module (e.g., a camera, an acceleration sensor, a position information collection sensor, or the like) which can collect various sensor signals.

The memory <NUM> may store various programs and various types of data related to the operation of the electronic device. For example, the memory <NUM> may store an operating system related to the operation of the electronic device <NUM>, applications related to various user functions provided based on the electronic device <NUM>, and various types of data related to execution of the applications. In an example, the memory <NUM> may store a music playback application related to music playback and a speech (voice) recognition application related to speech recognition. Further, the memory <NUM> may store applications for supporting various functions, such as a recording function, a video playback function, and a remote control function for an external electronic device. The memory <NUM> may store an echo canceller including an adaptive filter according to an embodiment of the present disclosure, and may provide the echo canceller to the audio-processing unit <NUM> under the control of the processor <NUM>. Alternatively, the echo canceller may be mounted in the audio-processing unit <NUM> in an embedded manner. Alternatively, the echo canceller may be implemented as at least one hardware processor or at least one software module.

The processor <NUM> may perform various types of signal processing related to the operation of the electronic device <NUM>, e.g., transfer and processing of audio data. The processor <NUM> may be implemented using multiple sub-processors, or may be implemented to allow one processor to process multiple functions. In an example, the audio-processing unit <NUM> may be integrated into the processor <NUM>. Here, the audio-processing unit <NUM> may be understood to be a component of the processor <NUM>. The processor <NUM> may be supplied with power from a battery included in the electronic device <NUM> or an external power source connected thereto, and may perform various user functions using the corresponding power. For example, the processor <NUM> may perform various types of processing, such as playing music based on user input that is received through the input unit <NUM> or preset scheduling information, searching for an external electronic device and establishing a communication channel therewith, playing video, or accessing a server and receiving and outputting content provided by the server. In the present disclosure, the processor <NUM> may manage the application of an echo cancellation function to audio data produced during a specific application execution procedure by controlling the audio-processing unit <NUM>.

The speaker <NUM> may be connected to the audio-processing unit <NUM>, and may convert received audio data into an audio signal and output the audio signal, under the control of the audio-processing unit <NUM>.

The microphone <NUM> may be connected to the audio-processing unit <NUM>, and may be activated under the control of the audio-processing unit <NUM>, after which the microphone <NUM> may collect an external audio signal, convert the external audio signal into audio data, and transfer the audio data to the audio-processing unit <NUM>.

The display unit <NUM> may output various screens related to the operation of the electronic device <NUM>. For example, the display unit <NUM> may output various screens, such as a screen related to music playback, a screen related to a speech recognition function, and a video playback screen. As an example, the display unit <NUM> may include a touch function, and in which case the display unit <NUM> may be operated as a component of the input unit.

The communication circuit <NUM> may support at least one communication function of the electronic device <NUM>. For example, the communication circuit <NUM> may establish a base station communication channel in relation to a connection to a server. Alternatively, the communication circuit <NUM> may establish a short-range communication channel with an external electronic device. In relation to this, the communication circuit <NUM> may include at least one of a network communication module and a short-range communication module. As an example, the communication circuit <NUM> may receive audio data (e.g., sound source information) provided by a server (e.g., a sound source provision server) under the control of the processor <NUM>, and may output the audio data to the speaker <NUM> through the audio-processing unit <NUM>. Alternatively, the communication circuit <NUM> may receive audio data from an additional electronic device connected through the short-range communication channel and transfer the audio data to the audio-processing unit <NUM>, or may transmit played audio data to the additional electronic device under the control of the processor <NUM>. Further, the communication circuit <NUM> may also transmit speech data required in order for the server to perform speech recognition to the server, under the control of the processor <NUM>. Furthermore, the communication circuit <NUM> may transmit the results of speech recognition to the server or to an external electronic device under the control of the processor <NUM>.

The input unit <NUM> may support an input function of the electronic device <NUM>. For example, the input unit <NUM> may include a keypad, a key button or the like. Alternatively, the electronic device <NUM> may include the configuration of the microphone <NUM>, which is capable of performing a voice command function, as the input unit <NUM>. A user may request the execution or termination of various user functions provided by the electronic device <NUM> through the input unit <NUM>. For example, the input unit <NUM> may collect an input signal for executing a music playback function, an input signal for playback control during music playback, an input signal for establishing or releasing a connection to the server, a voice command input signal related to a speech recognition function, etc., and may transfer the collected input signals to the processor <NUM>.

The audio-processing unit <NUM> may support the execution of applications related to audio-data processing, and may control at least one of the speaker <NUM> and the microphone <NUM> to output audio data or collect an audio signal during the application execution support procedure. The audio-processing unit <NUM> may perform function processing depending on execution of a specific application under the control of the processor <NUM>, or may be authorized by the processor <NUM> to control the execution and function processing of a specific application. As described above, the audio-processing unit <NUM> may be implemented as a partial component of the processor <NUM>, or may be implemented as a component independent of the processor <NUM> to communicate with the processor <NUM>, thus performing function processing depending on execution of a specific application. Due to this implementation scheme, the audio-processing unit <NUM> may be regarded as a single processor. The audio-processing unit <NUM> may process the functions to be performed depending on the type of application that is requested to be executed or execution of the application, and various tasks or various tasks related to processing of audio data by applications currently being executed. For example, the audio-processing unit <NUM> may perform control such that the speaker <NUM> is activated in response to a request received from a music playback application and such that various types of audio processing are performed on audio data to be played, and thereafter processed audio data is output through the speaker <NUM>.

Further, when a recording function or an application for controlling an external electronic device is executed, the audio-processing unit <NUM> may support audio processing such that the microphone <NUM> is activated to collect user speech information and various types of audio processing are performed on audio signals collected through the microphone <NUM>, after which the processed audio signals are stored in the memory <NUM> or are transmitted to an external electronic device through the communication circuit <NUM>.

In particular, when audio signals are collected through the microphone <NUM> during an audio data output process, the audio-processing unit <NUM> according to the present disclosure may perform echo cancellation on the collected audio signals by performing echo cancellation using an adaptive delay diversity filter, and thereafter may perform speech recognition on the corresponding audio signals. For example, the adaptive delay diversity filter may be configured such that at least a portion thereof is implemented in the form of hardware or at least a portion thereof is implemented in the form of a software module. When at least a portion of the adaptive delay diversity filter is implemented as a software module, the present disclosure may include memory, which stores the software module forming at least the portion of the adaptive delay diversity filter and a hardware processor component, which accesses the memory and executes the operation of the adaptive delay diversity filter.

Such a speech recognition process may be performed using, for example, a speech recognition database (DB) stored in the memory <NUM> or a speech recognition DB stored in the server, and may be configured to process various user functions based on the results of speech recognition. Referring to <FIG>, such an audio-processing unit <NUM> may include an application block <NUM> and an audio input/output processing block <NUM>.

The application block <NUM> may include an audio output unit 131a, a speech recognizer 131b, and an echo canceller 131c.

The audio output unit 131a may collect audio data according to execution of a music playback application stored in the memory <NUM>, and may transfer the collected audio data to a sound source playback processing block 132a. Alternatively, the audio output unit 131a may transfer audio data received from the outside through the communication circuit <NUM> to the sound source playback processing block 132a. The audio output unit 131a may be activated according to execution of the sound source application, and may perform processing of the collected audio data.

The speech recognizer 131b may be activated according to execution of a specific application, and may control the supply of power to the microphone <NUM>. For example, when an application supporting a speech recognition function (e.g., a music playback application, a navigation program or the like) is executed, the speech recognizer 131b may be activated, and may control the supply of power to the microphone <NUM> to collect audio signals. The speech recognizer 131b may analyze audio data transferred from a sound source collection processing block 132b, and may transfer the results of analysis of the audio data to the processor <NUM>. Alternatively, the speech recognizer 131b may control the execution of a user function (e.g., playback control for a music playback program, or the like) corresponding to the results of analysis of the audio data.

The echo canceller 131c may collect first audio data transferred from the audio output unit 131a to the sound source playback processing block 132a and second audio data transferred from the sound source collection processing block 132b to the speech recognizer 131b. The echo canceller 131c may estimate and subtract an echo contained in the second audio data using the collected first audio data, and may provide the result of the estimation and subtraction to the speech recognizer 131b. During this process, the echo canceller 131c may perform filtering by operating an adaptive filter composed of a plurality of sub-filters. During this process, the echo canceller 131c may set a value corresponding to the acoustic path length (e.g., a physical distance or an acoustic distance between the speaker and the microphone) of the electronic device <NUM> to the filter length value of a sub-filter, and may configure the adaptive delay diversity filter using a plurality of such sub-filters. Through the configuration of the adaptive delay diversity filter using the plurality of sub-filters, whenever new input is received, respective sub-filters may generate output values through filtering, and the best output value among the output values of the plurality of sub-filters may be selected as a final output value.

Also, the echo canceller 131c may allow respective sub-filters to share calculation values (e.g., an inverse matrix of a correlation matrix in the case of a Wiener filter) used to compute filter coefficients of the adaptive filter, thus reducing the computational load required by respective sub-filters to compute coefficients. The echo canceller 131c may finally select one sub-filter by gradually reducing the number of sub-filters that are in an active state using a pruning method, thus reducing a computational load.

The audio input/output processing block <NUM> may include at least one sound source playback processing block 132a and at least one sound source collection processing block 132b. The sound source playback processing block 132a may be disposed between the speaker <NUM> and the audio output unit 131a. The sound source playback processing block 132a may include one or more blocks for providing various acoustic effects required for sound source playback. The sound source collection processing block 132b may be disposed between the microphone <NUM> and the speech recognizer 131b.

<FIG> is a diagram illustrating the impulse response of an echo path for an audio signal and a single large filter for covering the impulse response.

The impulse response of the echo path illustrated in <FIG> shows the change occurring in a process in which a signal output through the speaker <NUM> flows in the microphone <NUM>. Here, an acoustic time delay td, may be a time delay occurring due to dispersion and reflection of sound produced in a pure acoustic path, and a non-acoustic time delay tr may be a time delay occurring in a non-acoustic path, may be mainly caused in a software processing procedure (e.g., copying/transfer of transmission data), and may also occur when an audio signal is moved in the form of a digital signal through a hardware path. Large variation in the non-acoustic time delay tr may appear when the electronic device changes or when an audio connection path changes, and thus there is a need to estimate an echo using an adaptive filter having a large filter length. That is, in an audio signal environment, when an echo path is composed of the non-acoustic time delay tr and the acoustic time delay td, and variation in tr at this time is large, a long filter may be used to estimate an echo. In this case, due to the excessively large filter length, the time required to estimate an echo signal is longer, and an error is also increased. In order to solve this problem, the adaptive delay diversity filter according to the present disclosure may be used.

When the signal transmission environment is regarded as being extended to a general signal transmission environment, without being limited to an audio environment, the impulse response of a transmission path from the transmission of a signal from a transmitting end to the reception of the signal at a receiving end in the environment may be similarly generalized, as illustrated in <FIG>, wherein the time intervals tr and td at this time may be changeably referred to as general terms, such as a pure time delay tr and a modulation time delay td, respectively. The term "modulation" used here is introduced to mean an operation of causing a modification in the waveform of a signal, and is used to temporarily designate the interval td. Further, in the case of the pure time delay tr, only a time delay is simply caused, without modification of a transmitted signal, and an example of occurrence of the pure delay may be a process for transferring a signal between adjacent software blocks or a process for transmitting a signal in the form of a digital signal between hardware blocks. In the overall impulse response, a portion corresponding to the pure delay interval tr ideally has a value of <NUM>. The modulation time delay td may occur in a transmission interval during which the waveform of a signal is modified, and may occur, for example, in an interval during which a signal is transmitted in the form of an analog signal, or may also occur even in the case where a signal modification procedure is included in a software block. When the impulse response of an arbitrary system is divided into the interval of the pure time delay tr and the interval of the modulation time delay td in this way, the adaptive delay diversity filter according to the present disclosure may be used to effectively estimate the impulse response or a signal modified in the transmission procedure when variation in the pure time delay tr is large.

<FIG> illustrates an example of an array structure of sub-filters of an adaptive delay diversity filter according to an embodiment of the present disclosure, wherein respective sub-filters forming the adaptive delay diversity filter are arranged such that respective time areas covered thereby do not overlap each other.

Referring to <FIG>, in consideration of both a non-acoustic time delay tr and an acoustic time delay td, the echo canceller 131c may use multiple sub-filters. For example, as illustrated in the drawing, four sub-filters (sub-filter <NUM>, sub-filter <NUM>, sub-filter <NUM>, and sub-filter <NUM>) may be used. When the respective sub-filters (sub-filter <NUM>, sub-filter <NUM>, sub-filter <NUM>, and sub-filter <NUM>) cover different time intervals of an impulse response, the time difference or time shift D between the time intervals covered by two adjacent sub-filters may be designed to be the same as the filter length L of each sub-filter. Here, the filter length L of each sub-filter may be set in association with the acoustic time delay td. The acoustic time delay td may be collected through experimental results or statistical results depending on the physical distance between the speaker <NUM> and the microphone <NUM>. The sub-filters (sub-filter <NUM>, sub-filter <NUM>, sub-filter <NUM>, and sub-filter <NUM>) may be disposed to be directly successive to each other so that time intervals covered by respective sub-filters do not overlap those of adjacent sub-filters (e.g., so that the time shift between respective sub-filters is D = L). For example, the second sub-filter (sub-filter <NUM>) may be disposed adjacent to the first sub-filter (sub-filter <NUM>), the third sub-filter (sub-filter <NUM>) may be disposed adjacent to the second sub-filter (sub-filter <NUM>), and the fourth sub-filter (sub-filter <NUM>) may be disposed adjacent to the third sub-filter (sub-filter <NUM>). The total length of the first to fourth sub-filters (sub-filter <NUM>, sub-filter <NUM>, sub-filter <NUM>, and sub-filter <NUM>) may be set to be longer than a length corresponding to the sum of the non-acoustic time delay tr and the acoustic time delay td. Alternatively, the length corresponding to the sum of the non-acoustic time delay tr and the acoustic time delay td may be used to determine the number of sub-filters.

<FIG> is a diagram illustrating another example of an array structure of sub-filters of an adaptive delay diversity filter according to an embodiment of the present disclosure, wherein the lengths of respective sub-filters forming the adaptive delay diversity filter are L and are identical to each other, and wherein time areas covered by respective sub-filters are arranged at regular intervals (e.g., D) and such that time areas covered by two adjacent sub-filters partially overlap each other.

Referring to <FIG>, in order to cope with the non-acoustic time delay tr and the acoustic time delay td together, shown in <FIG>, the echo canceller 131c of the present disclosure may use multiple sub-filters and operate the multiple sub-filters so that time areas covered by respective sub-filters are arranged to partially overlap each other. For example, as illustrated in the drawing, when four sub-filters (sub-filter <NUM>, sub-filter <NUM>, sub-filter <NUM>, and sub-filter <NUM>) cover different time intervals of the impulse response, the sub-filters may be designed and operated such that the time difference or time shift between time intervals covered by two adjacent sub-filters is identical to D for all sub-filters and D has a value falling within a range of <NUM><D<L. Here, the filter lengths L of respective sub-filters may be set in association with the value of the acoustic time delay td. For example, the echo canceller 131c is intended to estimate an interval corresponding to the acoustic time delay td, in the entire echo path, using the first to fourth sub-filters (sub-filter <NUM>, sub-filter <NUM>, sub-filter <NUM>, and sub-filter <NUM>), and respective sub-filters may be arranged such that time intervals covered by each sub-filter and an adjacent sub-filter partially overlap each other. As described above, the echo canceller 131c may support the performance of more robust filtering by arranging the two adjacent sub-filters so that the time intervals covered thereby partially overlap each other.

Here, the filter length formed by all of the sub-filters may be set to a length equal to or greater than the length of the echo path (e.g., the sum of the non-acoustic time delay tr and the acoustic time delay td).

<FIG> and <FIG> illustrate special examples of the structure of the adaptive delay diversity filter according to an embodiment of the present disclosure, and show an example in which filter lengths of respective sub-filters are identical to each other and distances between time intervals covered by two adjacent sub-filters are uniform. Unlike this example, depending on the circumstances, multiple sub-filters may cover different time intervals of the impulse response, but they may be configured such that the spaces between the distances between time intervals covered by adjacent sub-filters are not uniform, or such that the filter lengths of the sub-filters are different from each other.

Meanwhile, respective sub-filters forming the adaptive delay diversity filter are implemented in the form of an adaptive filter, may adopt and use an arbitrary adaptive filter algorithm, and may perform adaptation independently of each other.

<FIG> is a diagram illustrating an example of an echo cancellation method according to an embodiment of the present disclosure, and is a diagram in which respective sub-filters are assumed to use a Wiener filter as an adaptive filter algorithm.

Referring to <FIG>, the echo canceller 131c (or the processor <NUM> or the audio-processing unit <NUM>) may process input buffering at step <NUM>. For example, at step <NUM>, the echo canceller 131c may collect a reference signal played through the speaker and collect a target signal input into the microphone <NUM>, and may then store the collected signals in a buffer.

At step <NUM>, the echo canceller 131c computes the inverse matrix of a correlation matrix for the first sub-filter. This inverse matrix is used to compute filter coefficients through adaptation of the first sub-filter at step 309_1. Delayed values of the inverse matrix are used for adaptation of the second sub-filter, the third sub-filter,. , at steps 309_2,.

Next, the echo canceller 131c may perform an adaptation and filtering procedure on respective sub-filters. For example, the echo canceller 131c may allocate an ID for computation of the first sub-filter (e.g., sub-filter ID = <NUM>) at step 305_1, and may check whether the first sub-filter is in an active state may be checked at step 307_1. If the first sub-filter is in an inactive state, the echo canceller 131c may stop computation for the first sub-filter. If the first sub-filter is in an active state, the echo canceller 131c computes filter coefficients through adaptation using the inverse matrix, obtained at step <NUM>, at step 309_1, and performs filtering at step 311_1.

The echo canceller 131c may perform the above-described ID allocation, checking of activation or deactivation, application of the correlation matrix, and filtering for other sub-filters in the same manner. In this operation, the echo canceller 131c may simultaneously perform computations for respective sub-filters in parallel. For example, the echo canceller 131c may perform allocation of an ID to the second sub-filter (e.g., sub-filter = <NUM>, at step 305_2), check activation or deactivation of the second sub-filter (e.g., active? at step 307_2), perform adaptation using the delayed values of the inverse matrix of the correlation matrix directly computed for the first sub-filter (at step 309_2) and perform filtering (at step 311_2) while performing processing of computation for the first sub-filter. Furthermore, the echo canceller 131c may perform allocation of an ID to an M-th sub-filter (e.g., sub-filter = M, at step 305_M), check activation or deactivation of the M-th sub-filter (e.g., active? at step 307_M), perform adaptation using the delayed values of the inverse matrix of the correlation matrix (at step 309_M) and perform filtering (at step 311_M) so as to perform computation for the M-th sub-filter.

Next, the echo canceller 131c may select the best filter at step <NUM>. For example, the echo canceller 131c may select the sub-filter having the best result by comparing the results of filtering by the first to M-th sub-filters with each other.

Next, the echo canceller 131c may reduce a computational load related to the operation of sub-filters by performing pruning for reducing the total number of active sub-filters at step <NUM>. With using the pruning function, as illustrated in <FIG>, the specific sub-filter may transition from the active state to an inactive state. The sub-filter transitioning to the inactive state may be excluded from all subsequent processing procedures.

As described above, respective sub-filters of the adaptive delay diversity filter are implemented and operated as adaptive filters, and the adaptive delay diversity filter selects the output of the sub-filter having the best result as final output while the sub-filters compete with each other whenever input is received for each time period. At this time, the inverse matrix of the correlation matrix used to obtain filter coefficients may be computed only for the first sub-filter, rather than for all sub-filters, and values obtained by delaying the values computed for the first sub-filter may be used by second and subsequent sub-filters. This is intended to exemplify the case where a Wiener filter is used, and computations may be reduced using a time delay relational expression such as that shown in Equation <NUM> or Equation <NUM>, even when other algorithms are used.

Henceforth, equations will be introduced to help understand the detailed structure of the adaptive delay diversity filter, wherein, in equations, symbols written in lowercase italics denote scalars, symbols written in bold lowercase italics denote vectors, and symbols written in bold uppercase italics denote matrixes. In the following equations, j is used as a sub-filter number, wherein j = <NUM>, <NUM>,. , M may be given. M is the number of sub-filters present in the adaptive delay diversity filter. In the following equations, n is a sample number in the time domain, and m is the number of a frame used in an algorithm for calculating filter coefficients by collecting samples in frame (or block) units, or in an algorithm operating in the frequency domain.

Considering an echo canceller operating in an audio signal environment when a reference signal of the adaptive delay diversity filter is denoted by x(n) and a target signal thereof is indicated by y(n), x(n) may be a signal output from the speaker, and y(n) may be a signal input to the microphone <NUM>, wherein y(n) may contain an echo, noise, user speech, or the like. Considering a normal signal transmission environment, x(n) may be a transmit signal that is transmitted from a transmitting end, and y(n) may be a received signal at a receiving end, and y(n) may contain a modified signal of x(n), noise, an external interference signal, or the like.

When the reference signal of each sub-filter included in the adaptive delay diversity filter is indicated by xj(n) (where j = <NUM>,. ,M), xj(n) may have the form of a time-delayed signal of x(n), and may be represented by the following Equation <NUM>.

Here, the time delay Dj is an integer satisfying <NUM> ≤ D<NUM> < D<NUM> < ··· < DM.

When the impulse response of the echo path is estimated using the adaptive delay diversity filter, respective sub-filters use delayed signals xj(n), obtained by applying different time delay values Dj to x(n), as shown in Equation <NUM>, as respective reference signals, and thus the respective sub-filters may be arranged to cover different partial time areas of the impulse response.

If the reference signal vector of the j-th sub-filter is noted by xj(n) assuming that the filter length of each sub-filter included in the adaptive delay diversity filter is Lj (where j = <NUM>,. ,M), xj(n) may be represented by the following Equation <NUM>.

For example, in the case where an adaptive filter algorithm operating in the time domain is used, an echo estimate signal or a target estimate signal ŷj(n) and an error signal ej(n) of the j-th sub-filter yjnmay be computed using the following Equation <NUM>.

wj,i denotes an i-th value among filter coefficients of the j-th sub-filter, and the filter coefficient vector wj of the j-th sub-filter may be defined by the following Equation <NUM>.

After the target estimate signal ŷj(n) and the error signal ej(n) of each sub-filter are computed, the target estimate signal ŷ(n) and the error signal e(n) of the adaptive delay diversity filter may be computed using the following Equation (<NUM>).

As shown in Equation <NUM>, the best value among the target estimate signals {ŷ<NUM>(n),. , ŷM(n)} of the M sub-filters may be selected as the target estimate signal ŷ(n) of the adaptive delay diversity filter, and the best value among the error signals {e<NUM>(n),. , eM(n)} of the M sub-filters may be selected as the error signal e(n) of the adaptive delay diversity filter. Here, the object used as a criterion for selecting the best value is a performance metric pj(n) (where j = <NUM>,. The performance metric pj(n) is a value indicating the estimation performance of each sub-filter, and may be designed in various forms. Each sub-filter may perform adaptation using every new input signal, and may then compute the performance metric pj(n) , wherein the input signal y(n) and the target estimate signal ŷj(n) or the error signal ej(n) of each sub-filter may be used to compute pj(n). The pj(n) may be used as a criterion for selecting the best sub-filter from among multiple sub-filters and the best output. In Equation <NUM>, best{-} means the value obtained from the sub-filter having the best performance metric value among the performance metric values {p<NUM>(n),. , pM(n)} of the respective sub-filters.

<FIG> is a diagram for explaining the structure and output selection of an adaptive delay diversity filter according to an embodiment of the present disclosure.

The echo canceller 131c may be implemented using the adaptive delay diversity filter, wherein, in the situation in which the adaptive delay diversity filter is operated, filter coefficients of all sub-filters are updated for each time period, after which the output of the sub-filter (e.g., the best filter or best sub-filter) having the best estimation performance among the sub-filters may be selected as the output of the adaptive delay diversity filter.

Referring to <FIG>, the adaptive delay diversity filter used in the echo canceller 131c may include M sub-filters, each of which is implemented as an adaptive filter. In order to obtain the reference signal xj(n) (where j = <NUM>,. ,M) of each sub-filter, an operation of delaying x(n) is performed, as shown in Equation <NUM>, and is illustrated as being z-D<NUM>,. , z-DM in the drawing. The filter coefficient vector wj of each sub-filter is a value that causes E {|ej(n)|<NUM>} to be minimized, and that can be obtained independently between respective sub-filters and can be obtained in the same manner as that used in a normal adaptive filter. Also, an adaptive filter algorithm adopted by each sub-filter is not limited to a specific algorithm.

Each sub-filter may generate the echo estimate signal ŷj(n) by filtering the reference signal xj(n), as shown in Equation <NUM>, and may generate the error signal ej(n) of each sub-filter by subtracting the estimate signal ŷj(n) from the microphone input signal y(n).

When the error signals ej(n) (where j = <NUM>,. ,M) of respective sub-filters are obtained, the echo canceller 131c may obtain the performance metric values pj(n) (where j = <NUM>,. ,M) of respective sub-filters using ej(n) and the input signal y(n), select the ID of the sub-filter corresponding to the maximum value (or minimum value), among the pj(n) values of the multiple sub-filters, as the best filter ID best_sub_filter_id, and thereafter determine the output value ej=best_sub_filter_id(n) of the selected sub-filter to be the output value e(n) of the adaptive delay diversity filter. The echo canceller may perform a pruning operation of deactivating a sub-filter having a relatively worse performance metric value, among the multiple sub-filters, so as to reduce a computational load.

In the adaptive delay diversity filter, whenever a new input is received, the multiple sub-filters generate outputs through filtering, and the best output is selected from among the outputs and is used as the output of the adaptive delay diversity filter. In this way, from the concept in which the best output is selected as the final filter output from among the outputs of respective sub-filters while respective sub-filters cover different time delay intervals of an echo path, the term "adaptive delay diversity filter" has been adopted.

As described above, the adaptive delay diversity filter uses the sub-filters having a filter length set to be less than the total length tr + td of the entire echo path, but a sub-filter for best-estimating the impulse response in the interval td, which is an interval having a substantially significant meaning in the entire echo path, may be found. That is, because the filter length of the sub-filter of the adaptive delay diversity filter may be tightly set in conformity with the delay value td occurring in the acoustic path, the convergence time may be shorter than that of the case where one large filter is used as in a conventional method, and error occurring in the results of the filter may be reduced by preventing unnecessary filter coefficients from participating in computation.

Because a computational load occurring when M sub-filters are always operating in the adaptive delay diversity filter is considerable, a method for allowing some of the values computed for the first sub-filter to be shared with other sub-filters is proposed as a method for reducing the computational load. Here, the value to be shared is the result of a calculation formula including portions associated only with the reference signal x(n) in the equation for calculating filter coefficients.

In the above Equation <NUM>, when the time delay Dj, used to obtain the reference signal xj(n) of each sub-filter from x(n), and the filter length Lj of each sub-filter satisfy the following Equation <NUM> and Equation <NUM>, respectively, the time delay relational expression in the following Equation <NUM> is established, and some values, computed through the calculation formula required for computation of filter coefficients, are shared between respective sub-filters using the time delay relational expression, and thus a computational load may be reduced.

Here, D is a constant having a positive integer value, and Dconst is a constant having an integer value.

The above Equation <NUM> indicates that reference signals used between adjacent sub-filters are time-delayed at regular intervals of D.

The following Equation <NUM> indicates that filter lengths of all sub-filters forming the adaptive delay diversity filter are identical to each other.

Based on the above Equation <NUM> and Equation <NUM>, the following Equation <NUM> is established.

In Equation <NUM>, xj(n) is the reference signal of the j-th sub-filter.

When the condition of Equation <NUM> is added to the above Equation <NUM>, the time delay relational expression of the following Equation <NUM> is established.

In Equation <NUM>, xj(n) is the reference signal vector of the j-th sub-filter and is as defined in Equation <NUM>.

Therefore, when the filter lengths of respective sub-filters have the same value (e.g., L), as shown in the above Equations <NUM> and <NUM>, and all of the time differences between reference signals used by respective sub-filters are identical to D, the relational expression of Equation <NUM> or Equation <NUM>, which will be described later, may be obtained based on the above Equation <NUM>, and a computational load may be reduced using the relational expression.

<FIG> is a diagram illustrating an example in which sub-filters forming the adaptive delay diversity filter are limited to satisfy the above Equations <NUM> and <NUM>, and this example may be regarded as the case that is mainly used when the performance and computational load of the filter are taken into consideration.

In <FIG>, <FIG>, and <FIG>, a method for reducing a computational load based on a time delay relational expression is described using, by way of example, three adaptive filter algorithms, wherein the conditions of the above Equations <NUM> and <NUM> are assumed. The reason for describing the following three adaptive filter algorithms as examples is to describe a method for, when a well-known adaptive filter algorithm is applied to and used in the adaptive delay diversity filter, reducing a computational load by skipping some computations of the filter coefficient calculation formula for the remaining sub-filters other than the one sub-filter among multiple sub-filters, rather than to derive a new algorithm.

<FIG> is a diagram for explaining a filter coefficient calculation for reducing a computational load in each sub-filter of an adaptive delay diversity filter according to an embodiment of the present disclosure, and illustrates an example in which each sub-filter is operated based on a Wiener filter algorithm.

For example, when the solution of each sub-filter is obtained based on the Wiener filter, wj(n) may be computed using the following Equation <NUM>.

In the above Equation <NUM>, λ is a forgetting factor.

In order to obtain wj(n) from Equation <NUM>, <MAT> of each sub-filter must be computed, wherein only xj(n) defined in the above Equation <NUM> is used as a variable value in the calculation formula of Rj(n) in the above Equation <NUM>. As illustrated in the above Equation <NUM>, the reference signal of each sub-filter is a time-delayed version of the reference signal of the preceding sub-filter, and thus a time delay relational expression, such as that shown in the following Equation <NUM>, may be obtained for Rj(n) and <MAT> based on the time delay relational expression of the above Equation <NUM>.

Therefore, <MAT> may be directly obtained through computation, and the values of <MAT> may be obtained with reference to the past value of <MAT> without being computed. Therefore, because w<NUM>(n) may be obtained using <MAT>, which is directly obtained through computation, and w<NUM>(n),. , wM(n) may be obtained with reference to the past value of <MAT>, the filter coefficients of respective sub-filters from the second sub-filter, other than the first sub-filter, may be efficiently calculated through the structure illustrated in <FIG> without needing to directly compute the inverse matrix of a correlation matrix while filter coefficients are obtained. By means of this structure, computation of the inverse matrix of the correlation matrix is performed only once, rather than M times, for each time period so as to obtain the filter coefficients of M sub-filters, thus reducing a computational load. In this way, a method for sharing required calculation values when calculating filter coefficients between sub-filters may also be applied to the following Recursive Least Square (RLS) algorithm, in addition to the Wiener filter. This will be described below with reference to <FIG>.

<FIG> is a diagram for explaining another example of a filter coefficient calculation for reducing a computational load in each sub-filter of an adaptive delay diversity filter according to an embodiment of the present disclosure, and illustrates an example in which each sub-filter is operated based on a Recursive Least Square (RLS) algorithm.

For example, when the filter coefficients of respective sub-filters are calculated using the Recursive Least Square (RLS) algorithm, a formula for updating the RLS algorithm for the j-th sub-filter is represented by the following Equation <NUM>.

Here, kj(n) is the Kalman gain vector of the j-th sub-filter, and <MAT> may be the inverse matrix of the correlation matrix for the j-th sub-filter.

As shown in the above Equation <NUM>, the reference signal of each sub-filter is a time-delayed version of the reference signal of the preceding sub-filter, and thus the following Equation <NUM> may be established.

Accordingly, when the filter coefficient of the first sub-filter is obtained, k<NUM>(n) and <MAT> must be directly computed using a formula present in the update equation of the RLS algorithm, but, when the filter coefficients of second and subsequent sub-filters are obtained, the filter coefficients may be calculated using the delayed values of k<NUM>(n) and <MAT> calculated by the first sub-filter. That is, by means of the structure illustrated in the drawing, calculation of the Kalman gain vector and the inverse matrix of the correlation matrix is performed only once, rather than M times, for the M sub-filters, thus reducing a computational load.

<FIG> is a diagram for explaining another example of a filter coefficient calculation for reducing a computational load in each sub-filter of an adaptive delay diversity filter according to an embodiment of the present disclosure, and illustrates an example in which each sub-filter is operated based on a Partitioned Block Frequency Domain Adaptive Filter (PBFDAF) algorithm.

Even in an adaptive filter operating in the frequency domain, some calculations may be skipped using the time delay relationship, as in the case of the previous examples in which the two algorithms are used. The case where the Partitioned Block Frequency Domain Adaptive Filter (PBFDAF) algorithm is applied to each sub-filter is described by way of example. The PBFDAF adaptive filter algorithm is well known to those skilled in the art, and is implemented such that, when a filter having a filter length of L=P x N is partitioned into P filters, each of which has a partition size of N samples in the time domain, the original filter may be regarded as the sum of the partitioned filters. Accordingly, the estimate signal ŷ(n) of the filter may be represented by the total sum of the estimation values of the P filters, as represented by the following Equation <NUM>.

An error signal e(n) in the time domain and an error signal vector e(m) in an m-th frame (or block) may be defined by the following Equation <NUM>.

Here, m is a frame number, and one frame may be composed of N input samples. When the equation is converted into the frequency domain and is then arranged so as to obtain the filter coefficient for minimizing the error signal e(n), the PBFDAF algorithm operating in the frequency domain may be derived. As is well known to those skilled in the art, the basic update formula of the PBFDAF adaptive filter algorithm is given by the following Equation <NUM>.

Here, X(m) is generated using only the reference signal, and may be defined, as shown in Equation <NUM>. F may be a Discrete Fourier Transform (DFT) matrix used to perform a DFT. In the above Equation <NUM>, G<NUM> and G<NUM> are matrixes having constant values, which are matrixes related to the DFT matrix F, and may be defined by the following Equation <NUM>.

In the above Equation, K(m) may be a Kalman gain in the frequency domain.

The underlined symbols of values e(m) and y(m) in the time domain indicate values in the frequency domain, and may be defined by the following Equation <NUM>.

As described above, when the PBFDAF algorithm is adopted and used by the adaptive delay diversity filter, the PBFDAF algorithm may be applied to each sub-filter of the adaptive delay diversity filter. Here, assuming that the number of partition blocks of the adaptive filter using the PBFDAF algorithm is P, the number of new input samples required to configure one frame is N, and a time shift or time delay D between reference signals used by respective sub-filters forming the adaptive delay diversity filter is an integer multiple of N, D may be defined by the following Equation <NUM>.

Here, D may be a time delay value between reference signals used by adjacent sub-filters, as defined in the above Equation <NUM>, and B may be construed as a time delay value in frame (or block) units, and may typically have values within a range of <NUM><B≤P. When X(m) and K(m), obtained when the update equation for the PBFDAF algorithm of Equation <NUM> is applied to each sub-filter, are denoted by Xj(m) and Kj(m) (j = <NUM>,. , M), X(m) is a matrix including only values associated with DFT values of the reference signals x(n), without including additional variables, and reference signals by two adjacent sub-filters have the time delay relationship, such as that shown in Equation <NUM>, and thus the matrix Xj(m) may be represented by the following Equation <NUM>.

Here, m is a frame number, and B is the time delay value between reference signals used by adjacent sub-filters, and has a value in frame units. That is, since the reference signals used by the two adjacent sub-filters have a time delay relationship corresponding to B frames, Xj(m) having values associated with the DFT values of the reference signals may have the time delay relationship corresponding to the B frames. In the update Equation <NUM>, variables participating in the Kalman gain K(m) are also associated only with the reference signal x(n), and thus the following Equation <NUM> may be established.

Therefore, the first sub-filter directly calculates X<NUM>(m) and K<NUM>(m) thereafter obtains an error signal vector e<NUM>(m) and a filter coefficient vector h<NUM>(m), and sub-filters from the second sub-filter may calculate ej(m) and hj(m) using delayed values of X<NUM>(m) and K<NUM>(m) calculated by the first sub-filter. That is, through the use of a structure such as that illustrated in <FIG>, calculation of Xj(m) and Kj(m) may be performed only once, rather than M times, for the M sub-filters, and thus a computational load may be reduced.

The forgoing examples of three types of algorithms are summarized below. When a formula v(n) represented only by the reference signals x(n) is present in the equation for calculating filter coefficients in a certain adaptive filter algorithm in the case where the certain adaptive filter algorithm is adopted and applied to each sub-filter of the adaptive delay diversity filter having the structure satisfying Equation <NUM> and Equation <NUM>, the formula v(n) may be represented by a function f(·) of x(n), as given by the following Equation <NUM>. Here, v(n) may be one of a scalar, a vector, and a matrix.

When v(n), obtained when the algorithm is applied to each sub-filter present in the adaptive delay diversity filter, is represented by vj(n) (where j = <NUM>,. , M), v<NUM>(n) of the first sub-filter (j=<NUM>) may be directly obtained through calculation, and vj(n) at j =<NUM>,. , M may be obtained using the time delay relational expression, such as that shown in the following Equation <NUM>.

In the above Equation <NUM>, D is a value defined in Equation <NUM> and is a value indicating the time shift or the delay between the reference signals used by adjacent sub-filters, and n is also the value in sample units.

In an algorithm for updating filter coefficients in frame (or block) units, for example, an algorithm for updating filter coefficients in block units in the time domain, or an algorithm operating in the frequency domain, the following Equation <NUM> may be applied.

In Equation <NUM>, m is a frame number, and B is a value that is defined in Equation <NUM>, indicates the time difference between reference signals used by adjacent sub-filters, and is the value in frame units.

<FIG> is a diagram for explaining an initial stage of operation of sub-filters of an adaptive delay diversity filter according to an embodiment of the present disclosure.

The adaptive delay diversity filter is composed of a total of M sub-filters, and in the initial stage, all sub-filters are initiated in an active state, switch to an inactive state through a pruning operation, and sub-filters in the inactive state are excluded from all computation procedures. <FIG> illustrates a process in which one active sub-filter is operated. Referring to <FIG>, in the initial stage of the operation of the filter, while a reference signal having values other than <NUM> starts to be input from a 1st sub-filter (first sub-filter), subsequent sub-filters also take on reference signal values other than <NUM> with the lapse of time. Respective sub-filters are initially in an active state, but sub-filters that have not yet started adaptation have a filter coefficient of <NUM>, and may then be considered to perform a bypass operation of presenting the input target signal as output without change. Therefore, it may be considered that the sub-filters are initially in an active state, but subsequent sub-filters that have not yet started adaptation have hardly any influence on a computational load.

When a description is made with reference to the attached drawings, sub-filters in an active state (active sub-filters) may acquire (shift in) target signals and reference signals, which are used as input data, at step <NUM>, and may check whether all reference signals are <NUM> at step <NUM>. When data in which at least some of the reference signals are not '<NUM>' is input, the corresponding sub-filter performs adaptation at step <NUM>. Here, adaptation refers to updating of coefficients of sub-filters to minimize an estimation error, and the method of adaptation is determined depending on the type of the adaptive filter algorithm that is adopted by the corresponding sub-filter. At step <NUM>, filtering <MAT>, and ej(n) = y(n) - ŷj(n)) may be performed using the filter coefficients obtained at step <NUM>. At step <NUM>, when the entire reference data is <NUM>, the corresponding sub-filter may branch to step <NUM> where bypassing of the input signals (ej(n) = ŷj(n)) may be performed.

In the adaptive delay diversity filter, only sub-filters in an active state, among M sub-filters, are operated for each time period, one sub-filter having the best performance metric value is selected as the best filter, and the output of the selected sub-filter is selected as the output of the adaptive delay diversity filter. This process is illustrated in <FIG>.

<FIG> is a diagram for explaining an example in which the best filter is selected from among multiple sub-filters so as to determine a final output signal and in which the output of the selected sub-filter is selected as the final output.

Referring to <FIG>, in order to perform adaptation and generate filter outputs only for active filters among a total of M sub-filters, whether a corresponding sub-filter is in an active state is checked at step <NUM> while the sub-filter ID is increased from <NUM> to M (steps <NUM>, <NUM>, <NUM>). When the corresponding sub-filter is in an active state, the echo canceller 131c may update the filter coefficient of the sub-filter at step <NUM>, which is an adaptation step. Next, the echo canceller 131c may calculate the output ej(n) of the sub-filter and the performance metric pj of the sub-filter at step <NUM>.

At steps <NUM> and <NUM>, the echo canceller 131c saves the ID of the sub-filter having the best performance metric to best_sub_filter_id, and saves the output value of the sub-filter to ebest(n). When comparisons between all sub-filters are completed, the value of ebest(n) is determined to be the final filter output e(n) at step <NUM>. At step <NUM>, the value of nbest[ ] is the value in which the frequency at which each of the sub-filters was selected as the best filter is recorded, and may be used later for a final filter selection procedure, as illustrated in <FIG>.

Meanwhile, at step <NUM>, when the j-th sub-filter is not in an active state, the echo canceller 131c may skip subsequent steps, for example, steps <NUM>, <NUM>, <NUM>, and <NUM>.

In this way, whenever new input is received, the adaptive delay diversity filter allows multiple active sub-filters to generate respective outputs through filtering, selects the best output from among the outputs of the sub-filters, and uses the selected output as the final output of the adaptive delay diversity filter.

<FIG> is a diagram for explaining the initial stage of pruning according to an embodiment of the present disclosure.

As described above, the echo canceller 131c (or the audio-processing unit <NUM> or the processor <NUM>) may reduce a computational load by performing computation related to a formula required for calculation of filter coefficients only once, rather than M times, during a process for calculating filter coefficients of M sub-filters, and may further decrease a computational load by additionally applying a pruning method. For example, in the adaptive delay diversity filter, a maximum of M sub-filters may simultaneously perform adaptation, in which case a required computational load is increased, and thus the echo canceller 131c checks the performance of each sub-filter for each time period, and removes a sub-filter, the performance of which is deteriorated, using a pruning method, with the result that a computational load may be reduced.

In relation to this, referring to <FIG>, the echo canceller 131c (or the adaptive delay diversity filter) may set a predefined value Tp for the start time of the pruning operation at step <NUM> (Set Tp to a predefined value).

Next, at step <NUM>, the echo canceller 131c may read the time t<NUM> elapsed since the time at which the first sub-filter started adaptation to the current time.

Next at step <NUM>, the echo canceller 131c may determine whether the elapsed time t<NUM> is greater than the predefined pruning start time Tp. If it is determined that the elapsed time t<NUM> is greater than the pruning start time Tp, the echo canceller 131c may call a program (or an algorithm or a function) for starting pruning at step <NUM>. Meanwhile, at step <NUM>, if it is determined that the elapsed time t<NUM> is less than the predefined pruning start time Tp, the echo canceller 131c may skip pruning at step <NUM>.

<FIG> is a diagram for explaining an example of a method for deactivating one sub-filter during a pruning operation according to an embodiment of the present disclosure. This method may be used to gradually reduce the number of active sub-filters by one while being repeatedly utilized.

Referring to <FIG>, the echo canceller 131c (or the audio-processing unit <NUM> or the processor <NUM>) calls a function (or a program or an algorithm) for performing a pruning operation, and thereafter checks whether the situation occurs in which one of sub-filters in an active state (active sub-filters) needs to be deactivated at step <NUM>. When the corresponding situation occurs, the echo canceller 131c may find a sub-filter having the worst performance metric pj among active filters at step <NUM>, and may allocate the ID of the found sub-filter to the worst filter ID worst_sub_filter_id.

Next, the echo canceller 131c may perform control such that the sub-filter corresponding to the worst filter ID is excluded from a computation procedure such as adaptation and filtering by deactivating the sub-filter corresponding to the worst filter ID at step <NUM>. At step <NUM>, when the situation in which one active filter needs to be deactivated does not occur, the echo canceller 131c may skip steps <NUM> and <NUM>.

<FIG> is a diagram illustrating an example of a method for limiting the number of sub-filters that perform adaptation according to an embodiment of the present disclosure.

The adaptive delay diversity filter used in the echo canceller 131c is composed of multiple sub-filters, wherein, when all of the multiple sub-filters perform adaptation to update filter coefficients, a computational load is greatly increased, and thus the peak computational load may be controlled by limiting the number of sub-filters that perform adaptation.

Referring to <FIG>, the echo canceller 131c checks whether the situation occurs in which the number of filters that perform an adaptation process needs to be limited at step <NUM>. For example, the echo canceller 131c may check whether a predefined condition is satisfied in association with at least some of various factors related to performance for echo cancellation, such as the performance of a computer, the type of application currently being executed or the amount of resources used by the application. Alternatively, the echo canceller 131c may check whether the number of sub-filters is to be limited depending on the status of the current system performance using information in which (e.g., a lookup table) settings of the number of sub-filters to be used depending on the performance of the system (e.g., CPU) are stored. When the condition in which the number of filters that perform the adaptation operation is to be limited is satisfied, the echo canceller 131c may read the number of filters that are allowed to perform simultaneous adaptation (i.e., N_allowed_filters) at step <NUM>. The number of filters allowed to perform simultaneous adaptation may be stored in advance in, for example, the memory <NUM> or may be calculated according to the performance of a CPU that is used in real time.

Thereafter, at step <NUM>, the echo canceller 131c may count the number of filters n_adapt_filters that currently perform the adaptation operation.

Next, at step <NUM>, the echo canceller 131c may check whether the number of filters n_adapt_filters that perform the adaptation operation is greater than the number of filters N_allowed_filters that are allowed to perform simultaneous adaptation. If the number of filters n_adapt_filters that perform the adaptation operation is greater than the number of filters N_allowed_filters that are allowed to perform simultaneous adaptation, the echo canceller 131c may find the filter having the worst performance metric pj among the active filters at step <NUM>, and may save the ID of the corresponding filter to the worst filter ID worst_sub_filter_id.

At step <NUM>, the echo canceller 131c may deactivate the sub-filter corresponding to the worst filter ID, and may then exclude the corresponding sub-filter so that the sub-filter does not participate in computation any further. Meanwhile, when the limit condition set at step <NUM> is not satisfied, the echo canceller 131c may skip the procedure from steps <NUM> to <NUM>. In this way, the echo canceller 131c may perform filtering in the state in which a number of sub-filters less than or equal to the allowed number of sub-filters (N_allowed_filters), among the multiple sub-filters, are active.

<FIG> is a diagram illustrating an example of a method for removing sub-filters using pruning according to an embodiment of the present disclosure, and is a diagram showing an example that can be used when it is desired to remove only sub-filters having performance less than or equal to a certain level compared to the best filter, and to maintain sub-filters having performance equal to or greater than the certain level in an active state.

Referring to <FIG>, the echo canceller 131c may check whether a condition in which a marginal pruning operation needs to be performed is satisfied at step <NUM>. The setting of the marginal pruning operation may be adjusted depending on, for example, the performance of a system, the type of application, user's settings, or the like. Alternatively, the marginal pruning operation may be automatically applied through the execution of an echo cancellation program.

When the performance of the marginal pruning operation is requested, the echo canceller 131c may read a predefined marginal threshold value Pmargin at step <NUM>. The marginal threshold value Pmargin may be stored in advance in the memory <NUM>.

Next, the echo canceller 131c may find the best performance metric value pbest among the performance metric values for active sub-filters at step <NUM>. Thereafter, the echo canceller 131c may find sub-filters satisfying the following Equation <NUM> at step <NUM>.

The echo canceller 131c may deactivate the sub-filters satisfying the above equation. The marginal threshold value may be a preset constant value, and the speed at which the sub-filters switch to an inactive state may be controlled by adjusting the marginal threshold value. Meanwhile, the electronic device may change the marginal threshold value depending on the system performance or may change the marginal threshold value depending on the frequency at which an error occurred in a specific application (e.g., a speech recognition function). For example, when the frequency of error occurrence is high, the marginal threshold value may rise (or fall).

Respective methods for limiting sub-filters, described above with reference to <FIG>, may be independently applied or may be used together in combination. The adaptive delay diversity filter may use a method for maintaining only one sub-filter having the best performance in an active state and deactivating the remaining sub-filters after a predetermined time has elapsed. This method is illustrated in <FIG>.

<FIG> is a diagram for explaining an example of an initial setting method for finally selecting the best filter according to an embodiment of the present disclosure.

Referring to <FIG>, the echo canceller 131c (or the audio-processing unit <NUM> or the processor <NUM>) may set a final filter selection time Tf to a predefined value at step <NUM>.

Next, the echo canceller 131c may read the time t<NUM> elapsed since the first sub-filter started adaptation to the current time point at step <NUM>, and may determine whether the elapsed time t<NUM> is greater than the final filter selection time Tf at step <NUM>. If it is determined that t<NUM> is greater than Tf, the echo canceller 131c may call a function (or a program or an algorithm) for final filter selection at step <NUM>. Meanwhile, if it is determined at step <NUM> that t<NUM> is less than Tf, step <NUM> may be skipped.

<FIG> is a diagram for explaining an example of a best filter selection method according to an embodiment of the present disclosure.

Referring to <FIG>, as described above with reference to <FIG>, when the preset final filter selection time has elapsed, the echo canceller 131c may find performance metric values pj for all active filters at step <NUM>.

Next, the echo canceller 131c may select a filter having the best performance metric value pj from among the active filters, and may save the ID of the selected filter as the best filter ID best_sub_filter_id at step <NUM>.

Next, the echo canceller 131c may perform filtering by operating only the sub-filter corresponding to the best filter ID, best_sub_filter_id and deactivating the remaining sub-filters other than the best sub-filter at step <NUM>.

<FIG> is a diagram illustrating another example of a final filter selection method according to an embodiment of the present disclosure.

Next, the echo canceller 131c may calculate accumulated values pacc,j of the performance metric values for the active filters at step <NUM>.

Then, the echo canceller 131c may select the best accumulated performance metric value best pacc,j from among the active filters, and may save the ID of a sub-filter having the selected best accumulated value to the best filter ID best_sub_filter_id at step <NUM>.

<FIG> is a diagram illustrating a further example of a final filter selection method according to an embodiment of the present disclosure.

Referring to <FIG>, as described above with reference to <FIG>, when the preset final filter selection time has elapsed, the echo canceller 131c may read the frequency (the number of times) nbest[j] at which each of active sub-filters was previously selected as the best sub-filter at step <NUM>. The nbest[j] is calculated at step <NUM> of <FIG>.

Next, the echo canceller 131c may find the maximum value among the nbest[j] values of all active sub-filters, and may save the ID of the sub-filter corresponding to the maximum value to the best filter ID best_sub_filter_id at step <NUM>.

Next, the echo canceller 131c may perform filtering by operating only the sub-filter corresponding to the best filter ID, best_sub_filter_id and deactivating all of the remaining sub-filters other than the best sub-filter at step <NUM>.

By means of the above-described pruning function, a structure for allowing the final winner to remain while respective sub-filters compete with each other may be formed, and a better output signal may be obtained using a low computational load.

Meanwhile, the method for limiting the number of sub-filters that perform adaptation so as to reduce a computational load includes additional methods other than the pruning method. For example, there is a method for reducing a computational load by allowing respective sub-filters to sequentially perform adaptation in time, instead of a scheme in which all sub-filters perform adaptation for each time period. This method may be used to reduce a computational load while accommodating the deterioration in performance that occurs as the number of times that each sub-filter performs adaptation is decreased.

As described above, the adaptive delay diversity filter included in the echo canceller 131c may be configured such that the number of sub-filters participating in adaptation does not exceed a predefined value, and may then manage a computational load so that the peak computational load does not exceed a certain level. Further, the adaptive delay diversity filter may have imposed thereon a computational load corresponding to one sub-filter by finally selecting one sub-filter through a pruning operation.

Due to the characteristics of the adaptive filter, if a target signal and a reference signal, which are input signals of the filter, are not time-aligned therebetween, and then time reversal in which the target signal is ahead of the reference signal in time occurs or if a time delay between the two signals is too large for the filter to estimate, then the filter may diverge or produce a large error signal value. Due to these characteristics, in the electronic device according to the present disclosure, as the pruning operation is continuously performed with the lapse of time, many of the sub-filters participating in adaptation have poor performance and may be quickly deactivated. For example, at the initial stage, when pieces of target and reference data, which are input for the adaptive filter, start to flow in the adaptive filter, respective sub-filters sequentially participate in adaptation, but the number of sub-filters that simultaneously participate in adaptation does not exceed a defined value due to the pruning function, wherein the sub-filters having poor performance are deactivated, and the number of active sub-filters is gradually decreased since the last sub-filter participates in adaptation, with the result that one sub-filter finally remains as a survivor. Alternatively, a predefined number of sub-filters may remain as survivors. Accordingly, the echo canceller 131c may manage a computational load so that, even if the number M of sub-filters forming the adaptive delay diversity filter is increased, the adaptive delay diversity filter has a computational load at a certain level or less, regardless of the number of sub-filters.

The present disclosure may effectively solve the situation in which variation in a time delay between speaker data and microphone data is large when it is desired to apply one echo canceller engine to all smartphone products. In particular, considering various connection cases, such as the case where the speaker and microphone of a smartphone are used as standalone, the case where a smartphone and a Bluetooth headset are connected to each other and are then used, or the case where a smartphone and Audio, Video, and Navigation (AVN) devices in a vehicle are used via Bluetooth connection, variation in the time delay may be further increased. In such an environment, the present disclosure may provide an adaptive processing method. For example, time delay values in the case where a smartphone is operated as standalone have a range from about several tens to <NUM>, but, in the case where the smartphone and the Audio, Video, and Navigation (AVN) devices in the vehicle are connected via Bluetooth, the speaker and the microphone of the vehicle are used, the time delay at this time has a range from about <NUM> to <NUM> or more due to the addition of new transmission path. In order to effectively cancel echoes in all such cases, the adaptive filter of the echo canceller must be designed to cover a wide range of time delay. For this purpose, the present disclosure avoids setting the filter length to a large value as in conventional methods and sets the length of a filter to a value approximately corresponding to the length of an acoustic path, thus realizing a short convergence time and a small error value. Further, because values calculated through a calculation formula that is used when the filter coefficients of respective sub-filters are obtained can be shared between sub-filters using a time delay relational expression, the values are calculated only for the first sub-filter, and delayed versions of these values are used in all remaining sub-filters, and thus a computational load may be reduced. Furthermore, because the present disclosure can limit the number of filters participating in adaptation while removing sub-filters having deteriorated performance through a pruning method, rather than obtaining filter coefficient values of all sub-filters for each time period, the peak computational load may be maintained at a certain level or less even in the case where the number of sub-filters M used is increased to a very large value so as to cover large variation in time delay. Further, only one sub-filter may also be finally activated, and since then the same computational load as that when one sub-filter operates may be required. Furthermore, even in additional systems other than an audio system, when a signal transmission environment has large variation in a time delay between a target signal and a reference signal, the present disclosure may have a structure efficient for estimating of the impulse response of the transmission path or estimating of a target signal that is received after undergoing deformation.

Claim 1:
An adaptive filter, comprising:
a transmit signal x(n) transmitted from a transmitting end;
an input signal y(n) collected at a receiving end;
a desired signal included in the y(n); and
an adaptive delay diversity filter for estimating the desired signal using the x(n) as a reference signal and using the y(n) as a target signal;
wherein the adaptive delay diversity filter comprises a plurality of sub-filters;
wherein the plurality of sub-filters is composed of M sub-filters, where M is a natural number greater than <NUM>;
wherein each sub-filter of the plurality of sub-filters is implemented as an adaptive filter;
wherein each of the sub-filters uses the y(n) as a target signal;
wherein each of the sub-filters uses signals xj(n), j=<NUM>, ...,M, obtained by time-delaying the x(n) using different delay values for respective sub-filters, as respective reference signals;
wherein each of the signals xj(n) is configured to satisfy Equation <NUM>;
wherein Equation <NUM> is xj(n) = x (n - Dj), j=<NUM>,..., M, where a time delay value Dj is an integer satisfying <NUM> ≤ D<NUM> < D<NUM> < ··· < DM ; and
wherein the adaptive delay diversity filter computes output values of respective sub-filters through filtering with respect to each input value, and selects one of the computed multiple output values as an output value of the adaptive delay diversity filter.