# Regarding acoustic echo cancellation using frequency domain LMS algorithm and subband LMS algorithm

Started by December 26, 2006
```Mr.Maury,

Glad to see the response from you.

Do you mean that all the weights of the filter are
updated per frame?

These days I have searched for the book that you
mentioned in the mailI found that but it costs more for me.If you have
that book in pdf form please send  me that.....

Regards,
Aparna Ram.K.

maury wrote:
> Aparna Ram wrote:
> > Dear all,
> >
> >                I am working on the acoustic echo cancellation.I have
> > implemented the time domain LMS algorithm for acoustic echo
> > cancellation and it is working fine only for some audio files and not
> > working for some other audio files which has the large eigen value
> > spread.So to avoid this eigen value spread now I am working on the
> > subband LMS algorithm in frequency domain for acoustic echo
> > cancellation.So now I am searching for the  documents of subband LMS
> > algorithm and frequency domain LMS algorithm in which it is mentioned
> > clearly which samples are to be considered and why.But I didnt find
> > those details.But I understood the overall view of frequency domain LMS
> > algorithm from the documents that I collected and its steps are as
> > follows:
> >
> > Step1:For every sample of a frame (ie., 10 m sec data), that sample and
> > its previous samples, a total of samples equal to number of weights of
> > the filter are taken(as a full band) and they are converted to
> > frequency domain using DFT.
> >
> > Step2:Initially all the weights of the filter are taken as zeros in
> > frequency domain.
> >
> > Step3:Then to get the echo sample of kth subsequent sample position its
> > corresponding input sample in frequency domain(farend in frequency
> > domain) are multiplied with its corresponding  weight in frequency
> > domain (its corresponding weight).
> >         N(k)  = X(k) * W(k)
> >
> > Step4:Then the corresponding error sample is obtained by subtracting
> > this echo sample from the desired sample in frequency domain.
> >        Ek  = Yk - Nk
> > where Yk is the desired signal sample in frequency domain.
> >
> > Step5:Using this error sample in frequency domain all the weights of
> > the filter are updated using the following formula:
> >
> >    Wk+1(i) = Wk(i) + 2 * muk * Ek * Xk
> >  where Xk is column vector containing the current sample and its
> > previous samples.
> >           Wk is the column vector of all the weights of the filter.
> >
> > Step6:All the above steps are repeated for each and every sample of the
> > frame untill the end of the frame and is repeated for all the frames of
> > the audio file.
> >
> >                 My doubt is in the calculation of desired samples in
> > frequency domain ie.,Yk .According to logic, I think these frequency
> > components are calculated using all the samples of desired signal of a
> > frame.But it is nowhere mentioned in the documents that which samples I
> > need to consider for this frequncy band desired samples Okay if we
> > generate frequency domain desired samples equal to number of desired
> > samples in time domain using all these time domain samples.If I
> > integrate this idea with the subband LMS algorithm then again I am
> > getting the doubt that for each subband of farend signal(ie., obtained
> > by dividing a full band  of farend signal consisting of current sample
> > of the frame and its previous samples to a particular number of
> > subbands)whether we need to have the same  desired signal frequency
> > component for all the subbands or different frequency component for
> > each subband and how it is calculated.I have these type of doubts and
> > if we think of that there may be several possibilities.
> >
> >                So I am searching for that, but I am not getting the
> > required points.
> >
> >                I think one solution for this is converting the code of
> > time domain LMS algorithm to frequency domain and checking the code for
> > all the possibilities by trial and error method and seeing that for
> > which combination we will get the perfect output.But I am not getting
> > the output.
> >
> >               Here I have converted the farend signal, desired signal
> > and weights of the filter are converted to freqency domain and after
> > performing the operation the error signal is reconverted to time
> > domain.And the convergence weight factor is given in different ways in
> > different documents.I am in total confusion to proceed further.
> >
> >               I am very greatful to you if any one give me suggestions
> > and guidence  regarding this.
> >
> >
> >
> > Regards,
> > Aparna Ram.K.
>
> Aparna,
> In the frequency-domain adaptive filter (FDAF), each frequency bin is
> treated as a separate 1-coefficient adaptive filter.  That is, if you
> have 20 frequency bins, then you essencially have 20 LMS algorithms
> using a 1-coefficient filter, each with their own error.  If Yk is the
> column vector of values for the frequency bins, Nk is the corresponding
> value from your predictor, then Ek = Yk - Nk is a vector where each
> element is the error for each corresponding frequency bin.  To make the
> up date, you must do one of two things.
>
> 1.  Make a diagonal matrix of Ek, then update using
>          Wk+1 = Wk + 2 * muk * Ek * Xk
>     Wk, Ek, and Yk are vectors
>
> or
>
> 2.  Update using
>        Wk+1(i) = Wk(i) + 2 * muk * Ek .* Xk
>
> this is Matlab code where Ek .* Xk means multiply element by element,
> not the dot product
> Ek_t * Xk  (Ek_t is Ek transpose)
>
> The same is true (in general) for other forms of sub-band adaptive
> filters.
>
> For a reference try
> "Optimal and Adaptive Signal Processing", Peter Clarkson
>
> There are papers on FDAF, but I can't put my finger on them at the
> moment.  I'm sure a Google search on frequency domain adaptive filter
> will result in many examples.
>
>
> Maurice Givens
> Gas Technology Institute

```
```Aparna Ram wrote:
> Mr.Maury,
>
>                Glad to see the response from you.
>
>                Do you mean that all the weights of the filter are
> updated per frame?
>
>                These days I have searched for the book that you
> mentioned in the mailI found that but it costs more for me.If you have
> that book in pdf form please send  me that.....
>
> Regards,
> Aparna Ram.K.
>
> maury wrote:
> > Aparna Ram wrote:
> > > Dear all,
> > >
> > >                I am working on the acoustic echo cancellation.I have
> > > implemented the time domain LMS algorithm for acoustic echo
> > > cancellation and it is working fine only for some audio files and not
> > > working for some other audio files which has the large eigen value
> > > spread.So to avoid this eigen value spread now I am working on the
> > > subband LMS algorithm in frequency domain for acoustic echo
> > > cancellation.So now I am searching for the  documents of subband LMS
> > > algorithm and frequency domain LMS algorithm in which it is mentioned
> > > clearly which samples are to be considered and why.But I didnt find
> > > those details.But I understood the overall view of frequency domain LMS
> > > algorithm from the documents that I collected and its steps are as
> > > follows:
> > >
> > > Step1:For every sample of a frame (ie., 10 m sec data), that sample and
> > > its previous samples, a total of samples equal to number of weights of
> > > the filter are taken(as a full band) and they are converted to
> > > frequency domain using DFT.
> > >
> > > Step2:Initially all the weights of the filter are taken as zeros in
> > > frequency domain.
> > >
> > > Step3:Then to get the echo sample of kth subsequent sample position its
> > > corresponding input sample in frequency domain(farend in frequency
> > > domain) are multiplied with its corresponding  weight in frequency
> > > domain (its corresponding weight).
> > >         N(k)  = X(k) * W(k)
> > >
> > > Step4:Then the corresponding error sample is obtained by subtracting
> > > this echo sample from the desired sample in frequency domain.
> > >        Ek  = Yk - Nk
> > > where Yk is the desired signal sample in frequency domain.
> > >
> > > Step5:Using this error sample in frequency domain all the weights of
> > > the filter are updated using the following formula:
> > >
> > >    Wk+1(i) = Wk(i) + 2 * muk * Ek * Xk
> > >  where Xk is column vector containing the current sample and its
> > > previous samples.
> > >           Wk is the column vector of all the weights of the filter.
> > >
> > > Step6:All the above steps are repeated for each and every sample of the
> > > frame untill the end of the frame and is repeated for all the frames of
> > > the audio file.
> > >
> > >                 My doubt is in the calculation of desired samples in
> > > frequency domain ie.,Yk .According to logic, I think these frequency
> > > components are calculated using all the samples of desired signal of a
> > > frame.But it is nowhere mentioned in the documents that which samples I
> > > need to consider for this frequncy band desired samples Okay if we
> > > generate frequency domain desired samples equal to number of desired
> > > samples in time domain using all these time domain samples.If I
> > > integrate this idea with the subband LMS algorithm then again I am
> > > getting the doubt that for each subband of farend signal(ie., obtained
> > > by dividing a full band  of farend signal consisting of current sample
> > > of the frame and its previous samples to a particular number of
> > > subbands)whether we need to have the same  desired signal frequency
> > > component for all the subbands or different frequency component for
> > > each subband and how it is calculated.I have these type of doubts and
> > > if we think of that there may be several possibilities.
> > >
> > >                So I am searching for that, but I am not getting the
> > > required points.
> > >
> > >                I think one solution for this is converting the code of
> > > time domain LMS algorithm to frequency domain and checking the code for
> > > all the possibilities by trial and error method and seeing that for
> > > which combination we will get the perfect output.But I am not getting
> > > the output.
> > >
> > >               Here I have converted the farend signal, desired signal
> > > and weights of the filter are converted to freqency domain and after
> > > performing the operation the error signal is reconverted to time
> > > domain.And the convergence weight factor is given in different ways in
> > > different documents.I am in total confusion to proceed further.
> > >
> > >               I am very greatful to you if any one give me suggestions
> > > and guidence  regarding this.
> > >
> > >
> > >                                         Thanking in advance.
> > >
> > > Regards,
> > > Aparna Ram.K.
> >
> > Aparna,
> > In the frequency-domain adaptive filter (FDAF), each frequency bin is
> > treated as a separate 1-coefficient adaptive filter.  That is, if you
> > have 20 frequency bins, then you essencially have 20 LMS algorithms
> > using a 1-coefficient filter, each with their own error.  If Yk is the
> > column vector of values for the frequency bins, Nk is the corresponding
> > value from your predictor, then Ek = Yk - Nk is a vector where each
> > element is the error for each corresponding frequency bin.  To make the
> > up date, you must do one of two things.
> >
> > 1.  Make a diagonal matrix of Ek, then update using
> >          Wk+1 = Wk + 2 * muk * Ek * Xk
> >     Wk, Ek, and Yk are vectors
> >
> > or
> >
> > 2.  Update using
> >        Wk+1(i) = Wk(i) + 2 * muk * Ek .* Xk
> >
> > this is Matlab code where Ek .* Xk means multiply element by element,
> > not the dot product
> > Ek_t * Xk  (Ek_t is Ek transpose)
> >
> > The same is true (in general) for other forms of sub-band adaptive
> > filters.
> >
> > For a reference try
> > "Optimal and Adaptive Signal Processing", Peter Clarkson
> >
> > There are papers on FDAF, but I can't put my finger on them at the
> > moment.  I'm sure a Google search on frequency domain adaptive filter
> > will result in many examples.
> >
> >
> > Maurice Givens
> > Gas Technology Institute

Yes

```
```Mr.Maury,

Are you having that which you mentioned in the mail in
pdf format?

If so, if you can, please send me that book to my mail
ID aparnaram84@gmail.com.

Regards,
Aparna Ram.K.

maury wrote:
> Aparna Ram wrote:
> > Mr.Maury,
> >
> >                Glad to see the response from you.
> >
> >                Do you mean that all the weights of the filter are
> > updated per frame?
> >
> >                These days I have searched for the book that you
> > mentioned in the mailI found that but it costs more for me.If you have
> > that book in pdf form please send  me that.....
> >
> > Regards,
> > Aparna Ram.K.
> >
> > maury wrote:
> > > Aparna Ram wrote:
> > > > Dear all,
> > > >
> > > >                I am working on the acoustic echo cancellation.I have
> > > > implemented the time domain LMS algorithm for acoustic echo
> > > > cancellation and it is working fine only for some audio files and not
> > > > working for some other audio files which has the large eigen value
> > > > spread.So to avoid this eigen value spread now I am working on the
> > > > subband LMS algorithm in frequency domain for acoustic echo
> > > > cancellation.So now I am searching for the  documents of subband LMS
> > > > algorithm and frequency domain LMS algorithm in which it is mentioned
> > > > clearly which samples are to be considered and why.But I didnt find
> > > > those details.But I understood the overall view of frequency domain LMS
> > > > algorithm from the documents that I collected and its steps are as
> > > > follows:
> > > >
> > > > Step1:For every sample of a frame (ie., 10 m sec data), that sample and
> > > > its previous samples, a total of samples equal to number of weights of
> > > > the filter are taken(as a full band) and they are converted to
> > > > frequency domain using DFT.
> > > >
> > > > Step2:Initially all the weights of the filter are taken as zeros in
> > > > frequency domain.
> > > >
> > > > Step3:Then to get the echo sample of kth subsequent sample position its
> > > > corresponding input sample in frequency domain(farend in frequency
> > > > domain) are multiplied with its corresponding  weight in frequency
> > > > domain (its corresponding weight).
> > > >         N(k)  = X(k) * W(k)
> > > >
> > > > Step4:Then the corresponding error sample is obtained by subtracting
> > > > this echo sample from the desired sample in frequency domain.
> > > >        Ek  = Yk - Nk
> > > > where Yk is the desired signal sample in frequency domain.
> > > >
> > > > Step5:Using this error sample in frequency domain all the weights of
> > > > the filter are updated using the following formula:
> > > >
> > > >    Wk+1(i) = Wk(i) + 2 * muk * Ek * Xk
> > > >  where Xk is column vector containing the current sample and its
> > > > previous samples.
> > > >           Wk is the column vector of all the weights of the filter.
> > > >
> > > > Step6:All the above steps are repeated for each and every sample of the
> > > > frame untill the end of the frame and is repeated for all the frames of
> > > > the audio file.
> > > >
> > > >                 My doubt is in the calculation of desired samples in
> > > > frequency domain ie.,Yk .According to logic, I think these frequency
> > > > components are calculated using all the samples of desired signal of a
> > > > frame.But it is nowhere mentioned in the documents that which samples I
> > > > need to consider for this frequncy band desired samples Okay if we
> > > > generate frequency domain desired samples equal to number of desired
> > > > samples in time domain using all these time domain samples.If I
> > > > integrate this idea with the subband LMS algorithm then again I am
> > > > getting the doubt that for each subband of farend signal(ie., obtained
> > > > by dividing a full band  of farend signal consisting of current sample
> > > > of the frame and its previous samples to a particular number of
> > > > subbands)whether we need to have the same  desired signal frequency
> > > > component for all the subbands or different frequency component for
> > > > each subband and how it is calculated.I have these type of doubts and
> > > > if we think of that there may be several possibilities.
> > > >
> > > >                So I am searching for that, but I am not getting the
> > > > required points.
> > > >
> > > >                I think one solution for this is converting the code of
> > > > time domain LMS algorithm to frequency domain and checking the code for
> > > > all the possibilities by trial and error method and seeing that for
> > > > which combination we will get the perfect output.But I am not getting
> > > > the output.
> > > >
> > > >               Here I have converted the farend signal, desired signal
> > > > and weights of the filter are converted to freqency domain and after
> > > > performing the operation the error signal is reconverted to time
> > > > domain.And the convergence weight factor is given in different ways in
> > > > different documents.I am in total confusion to proceed further.
> > > >
> > > >               I am very greatful to you if any one give me suggestions
> > > > and guidence  regarding this.
> > > >
> > > >
> > > >                                         Thanking in advance.
> > > >
> > > > Regards,
> > > > Aparna Ram.K.
> > >
> > > Aparna,
> > > In the frequency-domain adaptive filter (FDAF), each frequency bin is
> > > treated as a separate 1-coefficient adaptive filter.  That is, if you
> > > have 20 frequency bins, then you essencially have 20 LMS algorithms
> > > using a 1-coefficient filter, each with their own error.  If Yk is the
> > > column vector of values for the frequency bins, Nk is the corresponding
> > > value from your predictor, then Ek = Yk - Nk is a vector where each
> > > element is the error for each corresponding frequency bin.  To make the
> > > up date, you must do one of two things.
> > >
> > > 1.  Make a diagonal matrix of Ek, then update using
> > >          Wk+1 = Wk + 2 * muk * Ek * Xk
> > >     Wk, Ek, and Yk are vectors
> > >
> > > or
> > >
> > > 2.  Update using
> > >        Wk+1(i) = Wk(i) + 2 * muk * Ek .* Xk
> > >
> > > this is Matlab code where Ek .* Xk means multiply element by element,
> > > not the dot product
> > > Ek_t * Xk  (Ek_t is Ek transpose)
> > >
> > > The same is true (in general) for other forms of sub-band adaptive
> > > filters.
> > >
> > > For a reference try
> > > "Optimal and Adaptive Signal Processing", Peter Clarkson
> > >
> > > There are papers on FDAF, but I can't put my finger on them at the
> > > moment.  I'm sure a Google search on frequency domain adaptive filter
> > > will result in many examples.
> > >
> > >
> > > Maurice Givens
> > > Gas Technology Institute
>
> Yes

```