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

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 Ram wrote:
> Dear all,
> 
>                I am working on the acoustic echo cancellation.

This is a fairly tough problem because of the nonlinearities, double 
talk and the long impulse response.


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.

How do you know?


So to avoid this eigen value spread now I am working on the
> subband LMS algorithm in frequency domain for acoustic echo
> cancellation.

The primary purpose of the subband processing is in the reduction of the 
complexity.


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.

10ms is way too short for the acoustic echo, and, of course, it can't 
compensate for it. Somewhat 100...200ms is what is generally required.



> 
>                 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.

I can't get it. Can you restate this in more sensible manner?



>                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.

You probably got a trivial bug somewhere.


> 
> I am very greatful to you if any one give me suggestions
> and guidence  regarding this.
> 

The LMS algorithm is fairly simple and it should work unless there is a 
trivial mistake.


Vladimir Vassilevsky

DSP and Mixed Signal Design Consultant

http://www.abvolt.com

Vladimir Vassilevsky wrote:
> Aparna Ram wrote:
> > Dear all,
> >
> >                I am working on the acoustic echo cancellation.
>
> This is a fairly tough problem because of the nonlinearities, double
> talk and the long impulse response.
>
>
> 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.
>
> How do you know?

> > >Time domain LMS algorithm is working fine for individual audio files.Ie.,when both farend and desired signals without any near end speech signal and the volume of the echo signal is less than the actual farend signal.And the convergence rate depends on decrease in the volume of the farend signal in the desired signal compared to actual farend signal.ie., if the decrease in volume is less it will take little more time than that in which the decrease in volume is high.

> > >Also it is working fine for some audio files.But for some other audio files which is having abrupt changes in the speech ie.,which is having sudden high pitch and sudden low pitch.This is because, as we know that convergence of the farend signal mainly depends on the convergence weight factor, in other words on the signal energy.So if the signal energy changes from very high for a full band in which there exists very very less valued samples and very very high valued samples, the same signal energy is used for their convergence. So the low valued samples gets converged very fastly and the high valued samples are not converged at that time. and also the converged low valued samples gets diverged.So I have gone for subband approach in which each subband energy is independent of the other also the computational complexity is reduced.

> > >So the time domain  LMS algorithm is working for some recorded audio files and it is not working fine for some other audio files-for this other audio files the signal is converging  with some residue and some noise also occuring.
>
> So to avoid this eigen value spread now I am working on the
> > subband LMS algorithm in frequency domain for acoustic echo
> > cancellation.
>
> The primary purpose of the subband processing is in the reduction of the
> complexity.

> > >Subband processing is used to reduce the computational complexity and to use its previlage of energy independence of each subband.
>
>
> 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.
>
> 10ms is way too short for the acoustic echo, and, of course, it can't
> compensate for it. Somewhat 100...200ms is what is generally required.

> > >But Mr.Vladimir Vassilevsky it is mentioned that usually it is cosidered 10msec or 20msec data as a frame.
>
>
>
> >
> >                 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.
>
> I can't get it. Can you restate this in more sensible manner?
>
> > > Usually in time domain to calculate estimate echo the formula is as follows:

                                                           nk  =  SUM w
k(i )xk-i      =  WkT Xk
Where k takes the values from 0 to M - 1 ( M = 80 ie., 10 msec data)
and i takes the values from 0 to N - 1 (N = 1024 ie.,for 128msec echo
path delay).

         ie., to estimate echo sample current farend sample and its
prvious samples are considered.On the whole they are 1024(ie., the
umber of weights of the filter) and all the weights of the filter are
considered

> > >But infrequency domain  to estimate echo sample of that frequency, here I am using the following formula:
                  N(k)  = X(k) * W(k)
 where k is the subsequent frequency poition,
           X(k) is the DFT of the farend signal calculated usig the
present sample and its previous samples(a total equal to number of
weights of the filter).
         W(k) is the DFT of the weight at the frequency k using all the
weights of the filter in time domain.
        This is the data that I got after observing many documents.

> > >But the main problem that I am facing is with calculation of desired sample in frequency domainie.,Yk.How to calculate this?I didnt get any document clearly mentioning which samples I have to consider for the desired sample calculation in frequency domain.I have calculated this in frequency domain considering all the 1024 samples(ie., current sample and its previous samples) in time domain to  calculate each frequency component.

> > > I have many doubts regarding this if we integrate this frequency domain LMS algorithm for subband approach.In subband approach this  1024 frequency components obtained from 1024 time samples(ie.,the current sample and its previous samples) is divided into subbands and then echo sample (in frequency domain)is estimated need to be subtracted from the desired signal frequency component.If it is a single band the estimated echo frequency component of this fullband is subtracted from the corresponding desired signal frequency component.My doubt is there exists only one desired signal frequency component for this entire subband, so if we go for subband for this fullband for all the subbands of this full band did we need to take the same frequency component of the desired signal or anything else.And if it is the same frequency component of the desired signal is considered after calculating the error component for each subband we need to combine them to get a single error sample for that full band.To get this did we need to add all the error samples?

> > >Also in different documents I found different formulas for weight updation and among them the following is one of them and I am using this:

                        Wk+1(i) = Wk(i) + 2 * muk * Ek * Xk
 where Xk is column vector containing the frequency components of
current sample and its
previous samples.
          Wk is the column vector of all the weights of the filter.

              Is it right????

> > >Can we follow this subband approach in time domain also??????

> > >Since in frequency domain farend signal frequency components are having the real part and imaginary part I have calculated the signal energy as the summation of (square of real part) + (square of imaginary part) of all the frequency components.Is it right????



>
> >                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.
>
> You probably got a trivial bug somewhere.

> > >What is meant by trivial bug? Here where is the possibility of getting this?Can you give me some idea regarding this?
>
>
> >
> > I am very greatful to you if any one give me suggestions
> > and guidence  regarding this.
> >
>
> The LMS algorithm is fairly simple and it should work unless there is a
> trivial mistake.
>
>
> Vladimir Vassilevsky
> 
> DSP and Mixed Signal Design Consultant
> 
> http://www.abvolt.com

Aparna,


Can you please explain your problem distinctly, short and clear? It is 
very difficult to dig through all of that quoted flow of words.

You can do the LMS either in time or in the frequency domain. You can 
take the full band or split it into the subbands. Either way is pretty 
straightforward. What is the problem?

VLV



Aparna Ram wrote:

> Vladimir Vassilevsky wrote:
> 
>>Aparna Ram wrote:
>>
>>>Dear all,
>>>
>>>               I am working on the acoustic echo cancellation.
>>
>>This is a fairly tough problem because of the nonlinearities, double
>>talk and the long impulse response.
>>
>>
>>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.
>>
>>How do you know?
> 
> 
>>>>Time domain LMS algorithm is working fine for individual audio files.Ie.,when both farend and desired signals without any near end speech signal and the volume of the echo signal is less than the actual farend signal.And the convergence rate depends on decrease in the volume of the farend signal in the desired signal compared to actual farend signal.ie., if the decrease in volume is less it will take little more time than that in which the decrease in volume is high.
> 
> 
>>>>Also it is working fine for some audio files.But for some other audio files which is having abrupt changes in the speech ie.,which is having sudden high pitch and sudden low pitch.This is because, as we know that convergence of the farend signal mainly depends on the convergence weight factor, in other words on the signal energy.So if the signal energy changes from very high for a full band in which there exists very very less valued samples and very very high valued samples, the same signal energy is used for their convergence. So the low valued samples gets converged very fastly and the high valued samples are not converged at that time. and also the converged low valued samples gets diverged.So I have gone for subband approach in which each subband energy is independent of the other also the computational complexity is reduced.
> 
> 
>>>>So the time domain  LMS algorithm is working for some recorded audio files and it is not working fine for some other audio files-for this other audio files the signal is converging  with some residue and some noise also occuring.
>>
>>So to avoid this eigen value spread now I am working on the
>>
>>>subband LMS algorithm in frequency domain for acoustic echo
>>>cancellation.
>>
>>The primary purpose of the subband processing is in the reduction of the
>>complexity.
> 
> 
>>>>Subband processing is used to reduce the computational complexity and to use its previlage of energy independence of each subband.
>>
>>
>>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.
>>
>>10ms is way too short for the acoustic echo, and, of course, it can't
>>compensate for it. Somewhat 100...200ms is what is generally required.
> 
> 
>>>>But Mr.Vladimir Vassilevsky it is mentioned that usually it is cosidered 10msec or 20msec data as a frame.
>>
>>
>>
>>>                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.
>>
>>I can't get it. Can you restate this in more sensible manner?
>>
>>
>>>>Usually in time domain to calculate estimate echo the formula is as follows:
> 
> 
>                                                            nk  =  SUM w
> k(i )xk-i      =  WkT Xk
> Where k takes the values from 0 to M - 1 ( M = 80 ie., 10 msec data)
> and i takes the values from 0 to N - 1 (N = 1024 ie.,for 128msec echo
> path delay).
> 
>          ie., to estimate echo sample current farend sample and its
> prvious samples are considered.On the whole they are 1024(ie., the
> umber of weights of the filter) and all the weights of the filter are
> considered
> 
> 
>>>>But infrequency domain  to estimate echo sample of that frequency, here I am using the following formula:
> 
>                   N(k)  = X(k) * W(k)
>  where k is the subsequent frequency poition,
>            X(k) is the DFT of the farend signal calculated usig the
> present sample and its previous samples(a total equal to number of
> weights of the filter).
>          W(k) is the DFT of the weight at the frequency k using all the
> weights of the filter in time domain.
>         This is the data that I got after observing many documents.
> 
> 
>>>>But the main problem that I am facing is with calculation of desired sample in frequency domainie.,Yk.How to calculate this?I didnt get any document clearly mentioning which samples I have to consider for the desired sample calculation in frequency domain.I have calculated this in frequency domain considering all the 1024 samples(ie., current sample and its previous samples) in time domain to  calculate each frequency component.
> 
> 
>>>>I have many doubts regarding this if we integrate this frequency domain LMS algorithm for subband approach.In subband approach this  1024 frequency components obtained from 1024 time samples(ie.,the current sample and its previous samples) is divided into subbands and then echo sample (in frequency domain)is estimated need to be subtracted from the desired signal frequency component.If it is a single band the estimated echo frequency component of this fullband is subtracted from the corresponding desired signal frequency component.My doubt is there exists only one desired signal frequency component for this entire subband, so if we go for subband for this fullband for all the subbands of this full band did we need to take the same frequency component of the desired signal or anything else.And if it is the same frequency component of the desired signal is considered after calculating the error component for each subband we need to combine them to get a single error sample
 for that full band.To get this did we need to add all the error samples?
> 
> 
>>>>Also in different documents I found different formulas for weight updation and among them the following is one of them and I am using this:
> 
> 
>                         Wk+1(i) = Wk(i) + 2 * muk * Ek * Xk
>  where Xk is column vector containing the frequency components of
> current sample and its
> previous samples.
>           Wk is the column vector of all the weights of the filter.
> 
>               Is it right????
> 
> 
>>>>Can we follow this subband approach in time domain also??????
> 
> 
>>>>Since in frequency domain farend signal frequency components are having the real part and imaginary part I have calculated the signal energy as the summation of (square of real part) + (square of imaginary part) of all the frequency components.Is it right????
> 
> 
> 
> 
>>>               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.
>>
>>You probably got a trivial bug somewhere.
> 
> 
>>>>What is meant by trivial bug? Here where is the possibility of getting this?Can you give me some idea regarding this?
>>
>>
>>>I am very greatful to you if any one give me suggestions
>>>and guidence  regarding this.
>>>
>>
>>The LMS algorithm is fairly simple and it should work unless there is a
>>trivial mistake.
>>
>>
>>Vladimir Vassilevsky
>>
>>DSP and Mixed Signal Design Consultant
>>
>>http://www.abvolt.com
> 
> 

Vladimir Vassilevsky wrote:
> Aparna,
>
>
> Can you please explain your problem distinctly, short and clear? It is
> very difficult to dig through all of that quoted flow of words.
>
> You can do the LMS either in time or in the frequency domain. You can
> take the full band or split it into the subbands. Either way is pretty
> straightforward. What is the problem?

> > >  > Okay Mr.Vladimir Vassilevsky I will explain this briefly:

doubt1: Can we apply the subband apprach in time domaini e.,converting
a full band of time samples to             subbands in time domain?

doubt2:To express this doubt needs some explanation as below:

             In time domain all the weights of the filter are updated
for each sample of farend and desired signal and in farend signal along
with current sample its previous samples are also considered.

            Like wise while converting the samples from time domain to
frequency domain using DFT how they are calculated ?

           To explain this clearly I have attached a figure to the mail
that I sent to your mail ID.According to the figure of subband adaptive
filter the input signals are x[n] and d[n].

           My doubt is what is this x[n]???Is it consists of the
current sample and its previous samples ??? or is it consists of the
entire 80 samples(ie.,10 msec data)???

           What is this d[n]???Is it consists of the entire 80 samples
of the desired signal???

           I hope that I explained my doubts clearly.If not please send
me the mail once again I will try to explain that in a different
way..............



Aparna Ram.K.



>
> VLV
>
>
>
> Aparna Ram wrote:
>
> > Vladimir Vassilevsky wrote:
> >
> >>Aparna Ram wrote:
> >>
> >>>Dear all,
> >>>
> >>>               I am working on the acoustic echo cancellation.
> >>
> >>This is a fairly tough problem because of the nonlinearities, double
> >>talk and the long impulse response.
> >>
> >>
> >>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.
> >>
> >>How do you know?
> >
> >
> >>>>Time domain LMS algorithm is working fine for individual audio files.Ie.,when both farend and desired signals without any near end speech signal and the volume of the echo signal is less than the actual farend signal.And the convergence rate depends on decrease in the volume of the farend signal in the desired signal compared to actual farend signal.ie., if the decrease in volume is less it will take little more time than that in which the decrease in volume is high.
> >
> >
> >>>>Also it is working fine for some audio files.But for some other audio files which is having abrupt changes in the speech ie.,which is having sudden high pitch and sudden low pitch.This is because, as we know that convergence of the farend signal mainly depends on the convergence weight factor, in other words on the signal energy.So if the signal energy changes from very high for a full band in which there exists very very less valued samples and very very high valued samples, the same signal energy is used for their convergence. So the low valued samples gets converged very fastly and the high valued samples are not converged at that time. and also the converged low valued samples gets diverged.So I have gone for subband approach in which each subband energy is independent of the other also the computational complexity is reduced.
> >
> >
> >>>>So the time domain  LMS algorithm is working for some recorded audio files and it is not working fine for some other audio files-for this other audio files the signal is converging  with some residue and some noise also occuring.
> >>
> >>So to avoid this eigen value spread now I am working on the
> >>
> >>>subband LMS algorithm in frequency domain for acoustic echo
> >>>cancellation.
> >>
> >>The primary purpose of the subband processing is in the reduction of the
> >>complexity.
> >
> >
> >>>>Subband processing is used to reduce the computational complexity and to use its previlage of energy independence of each subband.
> >>
> >>
> >>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.
> >>
> >>10ms is way too short for the acoustic echo, and, of course, it can't
> >>compensate for it. Somewhat 100...200ms is what is generally required.
> >
> >
> >>>>But Mr.Vladimir Vassilevsky it is mentioned that usually it is cosidered 10msec or 20msec data as a frame.
> >>
> >>
> >>
> >>>                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.
> >>
> >>I can't get it. Can you restate this in more sensible manner?
> >>
> >>
> >>>>Usually in time domain to calculate estimate echo the formula is as follows:
> >
> >
> >                                                            nk  =  SUM w
> > k(i )xk-i      =  WkT Xk
> > Where k takes the values from 0 to M - 1 ( M = 80 ie., 10 msec data)
> > and i takes the values from 0 to N - 1 (N = 1024 ie.,for 128msec echo
> > path delay).
> >
> >          ie., to estimate echo sample current farend sample and its
> > prvious samples are considered.On the whole they are 1024(ie., the
> > umber of weights of the filter) and all the weights of the filter are
> > considered
> >
> >
> >>>>But infrequency domain  to estimate echo sample of that frequency, here I am using the following formula:
> >
> >                   N(k)  = X(k) * W(k)
> >  where k is the subsequent frequency poition,
> >            X(k) is the DFT of the farend signal calculated usig the
> > present sample and its previous samples(a total equal to number of
> > weights of the filter).
> >          W(k) is the DFT of the weight at the frequency k using all the
> > weights of the filter in time domain.
> >         This is the data that I got after observing many documents.
> >
> >
> >>>>But the main problem that I am facing is with calculation of desired sample in frequency domainie.,Yk.How to calculate this?I didnt get any document clearly mentioning which samples I have to consider for the desired sample calculation in frequency domain.I have calculated this in frequency domain considering all the 1024 samples(ie., current sample and its previous samples) in time domain to  calculate each frequency component.
> >
> >
> >>>>I have many doubts regarding this if we integrate this frequency domain LMS algorithm for subband approach.In subband approach this  1024 frequency components obtained from 1024 time samples(ie.,the current sample and its previous samples) is divided into subbands and then echo sample (in frequency domain)is estimated need to be subtracted from the desired signal frequency component.If it is a single band the estimated echo frequency component of this fullband is subtracted from the corresponding desired signal frequency component.My doubt is there exists only one desired signal frequency component for this entire subband, so if we go for subband for this fullband for all the subbands of this full band did we need to take the same frequency component of the desired signal or anything else.And if it is the same frequency component of the desired signal is considered after calculating the error component for each subband we need to combine them to get a single error sample
>  for that full band.To get this did we need to add all the error samples?
> >
> >
> >>>>Also in different documents I found different formulas for weight updation and among them the following is one of them and I am using this:
> >
> >
> >                         Wk+1(i) = Wk(i) + 2 * muk * Ek * Xk
> >  where Xk is column vector containing the frequency components of
> > current sample and its
> > previous samples.
> >           Wk is the column vector of all the weights of the filter.
> >
> >               Is it right????
> >
> >
> >>>>Can we follow this subband approach in time domain also??????
> >
> >
> >>>>Since in frequency domain farend signal frequency components are having the real part and imaginary part I have calculated the signal energy as the summation of (square of real part) + (square of imaginary part) of all the frequency components.Is it right????
> >
> >
> >
> >
> >>>               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.
> >>
> >>You probably got a trivial bug somewhere.
> >
> >
> >>>>What is meant by trivial bug? Here where is the possibility of getting this?Can you give me some idea regarding this?
> >>
> >>
> >>>I am very greatful to you if any one give me suggestions
> >>>and guidence  regarding this.
> >>>
> >>
> >>The LMS algorithm is fairly simple and it should work unless there is a
> >>trivial mistake.
> >>
> >>
> >>Vladimir Vassilevsky
> >>
> >>DSP and Mixed Signal Design Consultant
> >>
> >>http://www.abvolt.com
> > 
> >

Aparna Ram wrote:

> 
> doubt1: Can we apply the subband apprach in time domaini e.,converting
> a full band of time samples to             subbands in time domain?

Yes, of course. If the leakage between the subbands is sufficiently low, 
you can break a fullband LMS into a set of independent subband LMS.

> 
> doubt2:To express this doubt needs some explanation as below:
> 
>              In time domain all the weights of the filter are updated
> for each sample of farend and desired signal and in farend signal along
> with current sample its previous samples are also considered.
> 
>             Like wise while converting the samples from time domain to
> frequency domain using DFT how they are calculated ?

1. Take the Fourier of the input signal.
2. Take the Fourier of the reference signal.
3. Estimate the responce of the channel using those Fouriers
4. Convert the response into the time domain using IFT.
5. Multiply the response by the adaptation factor.
6. Add the responce to the weigths of the filter.


> 
>  To explain this clearly I have attached a figure to the mail
> that I sent to your mail ID.

I didn't receive anything.

According to the figure of subband adaptive
> filter the input signals are x[n] and d[n].
> 
>            My doubt is what is this x[n]???Is it consists of the
> current sample and its previous samples ??? or is it consists of the
> entire 80 samples(ie.,10 msec data)???
> 
>            What is this d[n]???Is it consists of the entire 80 samples
> of the desired signal???
> 


Vladimir Vassilevsky

DSP and Mixed Signal Design Consultant

http://www.abvolt.com

Vladimir Vassilevsky wrote:
> Aparna Ram wrote:
>
> >
> > doubt1: Can we apply the subband apprach in time domaini e.,converting
> > a full band of time samples to             subbands in time domain?
>
> Yes, of course. If the leakage between the subbands is sufficiently low,
> you can break a fullband LMS into a set of independent subband LMS.

> > > > Query1:How can we know the amount of leakage between subbands???
             Query2:In time domain the full band consists of current
sample of a frame of farend signal and its previous samples are
considered (a total of number of weights of the filter) and for this to
process the current sample of desired signal is considered.When this
full band is subbdivided into subbands, is we need to use the same
desired signal sample(ie., is used for the full band) for all the
subbands?????If so is we need to add all the error samples of all the
subbands to get the error sample of the full band???
>
> >
> > doubt2:To express this doubt needs some explanation as below:
> >
> >              In time domain all the weights of the filter are updated
> > for each sample of farend and desired signal and in farend signal along
> > with current sample its previous samples are also considered.
> >
> >             Like wise while converting the samples from time domain to
> > frequency domain using DFT how they are calculated ?
>
> 1. Take the Fourier of the input signal.
> 2. Take the Fourier of the reference signal.
> 3. Estimate the responce of the channel using those Fouriers
> 4. Convert the response into the time domain using IFT.
> 5. Multiply the response by the adaptation factor.
> 6. Add the responce to the weigths of the filter.
>
> > > > > Is all the steps are repeated for each sample of the frame???/?
> >
> >  To explain this clearly I have attached a figure to the mail
> > that I sent to your mail ID.

> > > > > Yes I got the failure mail delivery notice Please send your mail ID sothat I can express the doubt with the help of figures.
>
> I didn't receive anything.
>
> According to the figure of subband adaptive
> > filter the input signals are x[n] and d[n].
> >
> >            My doubt is what is this x[n]???Is it consists of the
> > current sample and its previous samples ??? or is it consists of the
> > entire 80 samples(ie.,10 msec data)???
> >
> >            What is this d[n]???Is it consists of the entire 80 samples
> > of the desired signal???
> >
>
>
> Vladimir Vassilevsky
> 
> DSP and Mixed Signal Design Consultant
> 
> http://www.abvolt.com

Arapna,

Can you please quit using that freaking quoting marks?

>>>doubt1: Can we apply the subband apprach in time domaini e.,converting
>>>a full band of time samples to subbands in time domain?
>>
>>Yes, of course. If the leakage between the subbands is sufficiently low,
>>you can break a fullband LMS into a set of independent subband LMS.
> 
> 
>>>>>Query1:How can we know the amount of leakage between subbands???

You should ask the one who designed the filterbank.

> 
>  Query2:In time domain the full band consists of current
> sample of a frame of farend signal and its previous samples are
> considered (a total of number of weights of the filter) and for this to
> process the current sample of desired signal is considered.When this
> full band is subbdivided into subbands, is we need to use the same
> desired signal sample(ie., is used for the full band) for all the
> subbands?????If so is we need to add all the error samples of all the
> subbands to get the error sample of the full band???

Will you please have some mercy to the people who do have to read this?

As for your question, the subbands should operate independently. I.e. 
each subband has its own error signal.

> 
>>>doubt2:To express this doubt needs some explanation as below:
>>>
>>>             In time domain all the weights of the filter are updated
>>>for each sample of farend and desired signal and in farend signal along
>>>with current sample its previous samples are also considered.
>>>
>>>            Like wise while converting the samples from time domain to
>>>frequency domain using DFT how they are calculated ?
>>
>>1. Take the Fourier of the input signal.
>>2. Take the Fourier of the reference signal.
>>3. Estimate the responce of the channel using those Fouriers
>>4. Convert the response into the time domain using IFT.
>>5. Multiply the response by the adaptation factor.
>>6. Add the responce to the weigths of the filter.
>>
>>
>>>>>>Is all the steps are repeated for each sample of the frame???/?

You can do the update at every sample (either in time or in frequency 
domain) however you don't have to do it that way. Once per several msec 
is good enough. See block update LMS for the reference.


>>>
>>> To explain this clearly I have attached a figure to the mail
>>>that I sent to your mail ID.
> 
> 
>>>>>>Yes I got the failure mail delivery notice Please send your mail ID sothat I can express the doubt with the help of figures.
>>
>>I didn't receive anything.
>>
>>According to the figure of subband adaptive
>>
>>>filter the input signals are x[n] and d[n].
>>>
>>>           My doubt is what is this x[n]???Is it consists of the
>>>current sample and its previous samples ??? or is it consists of the
>>>entire 80 samples(ie.,10 msec data)???
>>>
>>>           What is this d[n]???Is it consists of the entire 80 samples
>>>of the desired signal???
>>>
>>

Arapha,

My email is on our web site.
Please note that the consulting rate will be asserted for all of the 
subsequent requests.

With Best Regards,

Vladimir Vassilevsky, Ph.D.

AbVolt, Ltd.
718 Delaware
Perry OK 73077 USA

Email:  vlv@abvolt.com
WWW:    http://www.abvolt.com
Phone:  (580)336-7227

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

Vladimir Vassilevsky wrote:
> Arapna,
>
> Can you please quit using that freaking quoting marks?

Ok.
>
> >>>doubt1: Can we apply the subband apprach in time domaini e.,converting
> >>>a full band of time samples to subbands in time domain?
> >>
> >>Yes, of course. If the leakage between the subbands is sufficiently low,
> >>you can break a fullband LMS into a set of independent subband LMS.
> >
> >
> >>>>>Query1:How can we know the amount of leakage between subbands???
>
> You should ask the one who designed the filterbank.
>
> >
> >  Query2:In time domain the full band consists of current
> > sample of a frame of farend signal and its previous samples are
> > considered (a total of number of weights of the filter) and for this to
> > process the current sample of desired signal is considered.When this
> > full band is subbdivided into subbands, is we need to use the same
> > desired signal sample(ie., is used for the full band) for all the
> > subbands?????If so is we need to add all the error samples of all the
> > subbands to get the error sample of the full band???
>
> Will you please have some mercy to the people who do have to read this?

Ok
>
> As for your question, the subbands should operate independently. I.e.
> each subband has its own error signal.
>
> >
> >>>doubt2:To express this doubt needs some explanation as below:
> >>>
> >>>             In time domain all the weights of the filter are updated
> >>>for each sample of farend and desired signal and in farend signal along
> >>>with current sample its previous samples are also considered.
> >>>
> >>>            Like wise while converting the samples from time domain to
> >>>frequency domain using DFT how they are calculated ?
> >>
> >>1. Take the Fourier of the input signal.
> >>2. Take the Fourier of the reference signal.
> >>3. Estimate the responce of the channel using those Fouriers
> >>4. Convert the response into the time domain using IFT.
> >>5. Multiply the response by the adaptation factor.
> >>6. Add the responce to the weigths of the filter.
> >>
> >>
> >>>>>>Is all the steps are repeated for each sample of the frame???/?
>
> You can do the update at every sample (either in time or in frequency
> domain) however you don't have to do it that way. Once per several msec
> is good enough. See block update LMS for the reference.

Do you mean, updation per every frame?
>
>
> >>>
> >>> To explain this clearly I have attached a figure to the mail
> >>>that I sent to your mail ID.
> >
> >
> >>>>>>Yes I got the failure mail delivery notice Please send your mail ID sothat I can express the doubt with the help of figures.
> >>
> >>I didn't receive anything.
> >>
> >>According to the figure of subband adaptive
> >>
> >>>filter the input signals are x[n] and d[n].
> >>>
> >>>           My doubt is what is this x[n]???Is it consists of the
> >>>current sample and its previous samples ??? or is it consists of the
> >>>entire 80 samples(ie.,10 msec data)???
> >>>
> >>>           What is this d[n]???Is it consists of the entire 80 samples
> >>>of the desired signal???
> >>>
> >>
>
> Arapha,
>
> My email is on our web site.
> Please note that the consulting rate will be asserted for all of the
> subsequent requests.

I have sent you that mail once again but its not going properly.
Do you mean that I have to pay you for subsequent requests?
>
> With Best Regards,
>
> Vladimir Vassilevsky, Ph.D.
>
> AbVolt, Ltd.
> 718 Delaware
> Perry OK 73077 USA
>
> Email:  vlv@abvolt.com
> WWW:    http://www.abvolt.com
> Phone:  (580)336-7227