DSPRelated.com
Forums

how, if at all, do AMDF & ASDF relate to fourier transforms?

Started by ben April 18, 2005
hello,

can anyone tell me how or if AMDF & ASDF relates to fourier transforms
please? -- do AMDF & ASDF make use of fourier transforms? or are part
of their logic based on fourier transforms in some way? or are AMDF &
ASDF, and fourier transforms entirely different logic/algorithms? or
maybe some AMDF & ASDF implementions use fourier transforms and some
don't -- it's the implemetor of AMDF & ASDF's choice?

i understand that pitch detection, which both AMDF & ASDF carry out,
extracts frequencies, then does some further work with those
frequencies as necessary (that extra works seems to be, if it's
necessary: amalgomation of frequencies and a kind of error-correction).

the first part of AMDF & ASDF, frequency extraction, i've read on here
a description of that, and it's exactly as you'd imagine doing it
logically yourself, (very simply): finding evenly spaced spikes and
measuring the gap length. is that part of AMDF & ASDF's logic done with
fourier transforms?

thanks, ben.
in article 180420052120194542%x@x.x, ben at x@x.x wrote on 04/18/2005 16:22:

> can anyone tell me how or if AMDF & ASDF relates to fourier transforms > please? -- do AMDF & ASDF make use of fourier transforms? or are part > of their logic based on fourier transforms in some way? or are AMDF & > ASDF, and fourier transforms entirely different logic/algorithms? or > maybe some AMDF & ASDF implementions use fourier transforms and some > don't -- it's the implemetor of AMDF & ASDF's choice? > > i understand that pitch detection, which both AMDF & ASDF carry out, > extracts frequencies, then does some further work with those > frequencies as necessary (that extra works seems to be, if it's > necessary: amalgomation of frequencies and a kind of error-correction). > > the first part of AMDF & ASDF, frequency extraction, i've read on here > a description of that, and it's exactly as you'd imagine doing it > logically yourself, (very simply): finding evenly spaced spikes and > measuring the gap length. is that part of AMDF & ASDF's logic done with > fourier transforms?
geez, i s'pose, since i've been the person using these acronyms recently here, this is kinda directed toward me. i dunno exactly how to answer the question relating AMDF or ASDF to the Fourier transform. first, this is what kinda motivates the AMDF or ASDF measurement for determining the period of a quasi-periodic waveform which is the reciprocal of the fundamental frequency which, when logged, is a measure of "pitch". suppose you make a sorta comb-filter like this: x(t) ----.------>[ delay of Tau ]---->[-1]---->(+)-------> e(t) | ^ | | | | '--------------------------------------' so e(t) = x(t) - x(t-Tau) can be thought of as a sorta "error" signal. the parameter Tau is something that can be varied (pretend there is a knob on that parameter) and if x(t) is quasi-periodic with period T, then x(t+T) ~= x(t) at least around the present time (we might call that "t0"). if Tau happens to get set to the same value as T, then e(t) will be nearly zero. the amplitude of e(t) will be at a null. but e(t) is an AC kindof signal (the DC component of x(t) gets subtracted out) and, even when e(t) is large, the positive now, if you measure the amplitude of e(t) the same way that old AC voltmeters used to do it, with a full-wave rectifier and some sort of low-pass filter, the whole device would be computing the AMDF. but if instead, you were measuring the amplitude of e(t) by squaring e(t) and low-pass filtering that, it would be computing the ASDF. how one actually computes this on discrete-time samples of x(t) is an implementation issue which i don't really wanna get into now. so you adjust Tau so that the output of this comb filter is null and that setting for Tau is going to be some integer times T, the period of x(t). another implementation detail is worrying about making sure you have T and not 2T or 3T or 4T and if there is a (false) null at T/2, that you don't pick that one either. now, you *can* relate this to the frequency domain a little but i don't think it gains you much. if e(t) = x(t) - x(t-Tau) then E(f) = X(f) - exp(-j*2*pi*f*Tau)*X(f) = H(f) * X(f) where H(f) = 1 - exp(-j*2*pi*f*Tau) = 2*j*exp(-j*pi*f*Tau)*sin(pi*f*Tau) |H(f)| = 2*|sin(pi*f*Tau)| H(f) is clearly a comb filter with nulls in the frequency response at every integer multiple of 1/Tau. if x(t) is quasi-periodic with period T, then X(f) will have a pretty empty spectrum except for spikes at integer multiples of its fundamental frequency 1/T. if 1/Tau gets adjusted so that it is the same at 1/T (or 1/(2T) or 1/(3T)...), then the spikes in X(f) will get killed by the nulls in H(f) and the spectrum leftover in X(f) will have little energy in it. that's one way to relate the time-domain AMDF or ASDF to the frequency domain. i dunno if that helps with anything (i surely wouldn't choose to compute the ASDF in the frequency domain), but maybe it can help visualize what is going on. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
In article <BE89E74C.64CC%rbj@audioimagination.com>, robert
bristow-johnson <rbj@audioimagination.com> wrote:

> in article 180420052120194542%x@x.x, ben at x@x.x wrote on 04/18/2005 16:22: > > > can anyone tell me how or if AMDF & ASDF relates to fourier transforms > > please? -- do AMDF & ASDF make use of fourier transforms? or are part > > of their logic based on fourier transforms in some way? or are AMDF & > > ASDF, and fourier transforms entirely different logic/algorithms? or > > maybe some AMDF & ASDF implementions use fourier transforms and some > > don't -- it's the implemetor of AMDF & ASDF's choice? > > > > i understand that pitch detection, which both AMDF & ASDF carry out, > > extracts frequencies, then does some further work with those > > frequencies as necessary (that extra works seems to be, if it's > > necessary: amalgomation of frequencies and a kind of error-correction). > > > > the first part of AMDF & ASDF, frequency extraction, i've read on here > > a description of that, and it's exactly as you'd imagine doing it > > logically yourself, (very simply): finding evenly spaced spikes and > > measuring the gap length. is that part of AMDF & ASDF's logic done with > > fourier transforms? > > geez, i s'pose, since i've been the person using these acronyms recently > here, this is kinda directed toward me. i dunno exactly how to answer the > question relating AMDF or ASDF to the Fourier transform. > > first, this is what kinda motivates the AMDF or ASDF measurement for > determining the period of a quasi-periodic waveform which is the reciprocal > of the fundamental frequency which, when logged, is a measure of "pitch". > > suppose you make a sorta comb-filter like this: > > > > x(t) ----.------>[ delay of Tau ]---->[-1]---->(+)-------> e(t) > | ^ > | | > | | > '--------------------------------------' > > > so e(t) = x(t) - x(t-Tau) can be thought of as a sorta "error" signal. > > the parameter Tau is something that can be varied (pretend there is a knob > on that parameter) and if x(t) is quasi-periodic with period T, then > > x(t+T) ~= x(t) > > at least around the present time (we might call that "t0"). if Tau happens > to get set to the same value as T, then e(t) will be nearly zero. the > amplitude of e(t) will be at a null. but e(t) is an AC kindof signal (the > DC component of x(t) gets subtracted out) and, even when e(t) is large, the > positive > > now, if you measure the amplitude of e(t) the same way that old AC > voltmeters used to do it, with a full-wave rectifier and some sort of > low-pass filter, the whole device would be computing the AMDF. but if > instead, you were measuring the amplitude of e(t) by squaring e(t) and > low-pass filtering that, it would be computing the ASDF. > > how one actually computes this on discrete-time samples of x(t) is an > implementation issue which i don't really wanna get into now. > > so you adjust Tau so that the output of this comb filter is null and that > setting for Tau is going to be some integer times T, the period of x(t). > another implementation detail is worrying about making sure you have T and > not 2T or 3T or 4T and if there is a (false) null at T/2, that you don't > pick that one either. > > now, you *can* relate this to the frequency domain a little but i don't > think it gains you much. > > if e(t) = x(t) - x(t-Tau) > > > then E(f) = X(f) - exp(-j*2*pi*f*Tau)*X(f) = H(f) * X(f) > > > where H(f) = 1 - exp(-j*2*pi*f*Tau) = 2*j*exp(-j*pi*f*Tau)*sin(pi*f*Tau) > > |H(f)| = 2*|sin(pi*f*Tau)| > > > H(f) is clearly a comb filter with nulls in the frequency response at every > integer multiple of 1/Tau. if x(t) is quasi-periodic with period T, then > X(f) will have a pretty empty spectrum except for spikes at integer > multiples of its fundamental frequency 1/T. if 1/Tau gets adjusted so that > it is the same at 1/T (or 1/(2T) or 1/(3T)...), then the spikes in X(f) will > get killed by the nulls in H(f) and the spectrum leftover in X(f) will have > little energy in it. > > that's one way to relate the time-domain AMDF or ASDF to the frequency > domain. i dunno if that helps with anything (i surely wouldn't choose to > compute the ASDF in the frequency domain), but maybe it can help visualize > what is going on.
right, thanks very much for the explenation but i'm still a bit stuck. it's not so much AMDF & ASDF that i'm interested in but just the first stage of AMDF & ASDF: frequency extraction, the comb filter bit. maybe linking this question to AMDF & ASDF was misleading -- it's more the just the comb filter aspect. comb filters tell you what frequencies exist in a particular bit of sound -- the kind of logic that you've described with comb filters (integer multiples) is exactly what i (without expert maths/dsping knowledge) would come up with using only common sense to go about extracting frequencies from sound. but when i previously asked about frequency extraction i was unanimously told "fourier transforms" and i'm thinking comb filters and fourier transforms must be pretty different things. it's the gap/connection/relation or non-relation between comb filters and fourier transforms i'm trying to get at and understand. both seem to be able to do the same thing: extract frequencies. say you wanted to simulate (on a computer) the human ear (just the first stage of hearing -- the ear itself) (i believe it has many small "ears", receptors, that are tuned to various small ranges of frequencies that overlap each other -- so splits up/extracts frequencies basically). for each little "ear" (particular frequency range) would you use a fourier transform or a comb filter? - fourier transforms can be used to extract frequencies from a sound. - comb filters can be used to extract frequencies from a sound. - logically, and without any pre expert maths knowledge, comb filters seem like a good, and maybe only, solution to extracting frequencies out of a sound to me. - when asking about frequency extraction everyone said fourier transforms. - the first stage of AMDF & ASDF is to use comb filters and not fourier transforms the main problem/contradiction i have is: i like the idea of comb filters because they fit with how i'd imagine going about frequency extraction, but on the other hand when i asked about frequency extraction, fourier transforms was the answer i got (from maths / dps experts), not comb filters. i'd like to use what's best for the job. comb filters or fourier transforms. for inner ear receptor simpulation: which? either? neither? any advice much appreciated. thanks, ben.
Ben,

Ok, first of all, if you crack open a signal processing or DSP
textbook, you'll learn that Fourier Transforms are used to convert a
time domain signal to a frequency domain.  What this does, and why
people are telling you this is important, is, like what you're wanting
to do "finding evenly spaced spikes and
measuring the gap length", but rather than doing this, you can do an
FFT (so it's quicker on O(something I can't recall right now)), and
find the frequency components in the signal you're concerned with.

Now, if you do this in psuedo-real time, like taking an FFT of every
100 or 1000 samples or something, finding what frequencies have the
largest amplitudes, or if the frequencies that you don't want in there,
are...you can filter them out using a comb filter, or any other filter.


I know you keep stating that you don't want to delve into the math of
it, but for what you're doing, I suggest you give it a go.  If you're
interested at first, it will start to make tons of sense once you're
done getting through all of the hell (technical reading)...and you can
apply it affectively for your intended application.

Hope this helps a bit.

Regards,
Ben



ben wrote:
> In article <BE89E74C.64CC%rbj@audioimagination.com>, robert > bristow-johnson <rbj@audioimagination.com> wrote: > > > in article 180420052120194542%x@x.x, ben at x@x.x wrote on
04/18/2005 16:22:
> > > > > can anyone tell me how or if AMDF & ASDF relates to fourier
transforms
> > > please? -- do AMDF & ASDF make use of fourier transforms? or are
part
> > > of their logic based on fourier transforms in some way? or are
AMDF &
> > > ASDF, and fourier transforms entirely different logic/algorithms?
or
> > > maybe some AMDF & ASDF implementions use fourier transforms and
some
> > > don't -- it's the implemetor of AMDF & ASDF's choice? > > > > > > i understand that pitch detection, which both AMDF & ASDF carry
out,
> > > extracts frequencies, then does some further work with those > > > frequencies as necessary (that extra works seems to be, if it's > > > necessary: amalgomation of frequencies and a kind of
error-correction).
> > > > > > the first part of AMDF & ASDF, frequency extraction, i've read on
here
> > > a description of that, and it's exactly as you'd imagine doing it > > > logically yourself, (very simply): finding evenly spaced spikes
and
> > > measuring the gap length. is that part of AMDF & ASDF's logic
done with
> > > fourier transforms? > > > > geez, i s'pose, since i've been the person using these acronyms
recently
> > here, this is kinda directed toward me. i dunno exactly how to
answer the
> > question relating AMDF or ASDF to the Fourier transform. > > > > first, this is what kinda motivates the AMDF or ASDF measurement
for
> > determining the period of a quasi-periodic waveform which is the
reciprocal
> > of the fundamental frequency which, when logged, is a measure of
"pitch".
> > > > suppose you make a sorta comb-filter like this: > > > > > > > > x(t) ----.------>[ delay of Tau ]---->[-1]---->(+)------->
e(t)
> > | ^ > > | | > > | | > > '--------------------------------------' > > > > > > so e(t) = x(t) - x(t-Tau) can be thought of as a sorta "error"
signal.
> > > > the parameter Tau is something that can be varied (pretend there is
a knob
> > on that parameter) and if x(t) is quasi-periodic with period T,
then
> > > > x(t+T) ~= x(t) > > > > at least around the present time (we might call that "t0"). if Tau
happens
> > to get set to the same value as T, then e(t) will be nearly zero.
the
> > amplitude of e(t) will be at a null. but e(t) is an AC kindof
signal (the
> > DC component of x(t) gets subtracted out) and, even when e(t) is
large, the
> > positive > > > > now, if you measure the amplitude of e(t) the same way that old AC > > voltmeters used to do it, with a full-wave rectifier and some sort
of
> > low-pass filter, the whole device would be computing the AMDF. but
if
> > instead, you were measuring the amplitude of e(t) by squaring e(t)
and
> > low-pass filtering that, it would be computing the ASDF. > > > > how one actually computes this on discrete-time samples of x(t) is
an
> > implementation issue which i don't really wanna get into now. > > > > so you adjust Tau so that the output of this comb filter is null
and that
> > setting for Tau is going to be some integer times T, the period of
x(t).
> > another implementation detail is worrying about making sure you
have T and
> > not 2T or 3T or 4T and if there is a (false) null at T/2, that you
don't
> > pick that one either. > > > > now, you *can* relate this to the frequency domain a little but i
don't
> > think it gains you much. > > > > if e(t) = x(t) - x(t-Tau) > > > > > > then E(f) = X(f) - exp(-j*2*pi*f*Tau)*X(f) = H(f) * X(f) > > > > > > where H(f) = 1 - exp(-j*2*pi*f*Tau) =
2*j*exp(-j*pi*f*Tau)*sin(pi*f*Tau)
> > > > |H(f)| = 2*|sin(pi*f*Tau)| > > > > > > H(f) is clearly a comb filter with nulls in the frequency response
at every
> > integer multiple of 1/Tau. if x(t) is quasi-periodic with period
T, then
> > X(f) will have a pretty empty spectrum except for spikes at integer > > multiples of its fundamental frequency 1/T. if 1/Tau gets adjusted
so that
> > it is the same at 1/T (or 1/(2T) or 1/(3T)...), then the spikes in
X(f) will
> > get killed by the nulls in H(f) and the spectrum leftover in X(f)
will have
> > little energy in it. > > > > that's one way to relate the time-domain AMDF or ASDF to the
frequency
> > domain. i dunno if that helps with anything (i surely wouldn't
choose to
> > compute the ASDF in the frequency domain), but maybe it can help
visualize
> > what is going on. > > right, thanks very much for the explenation but i'm still a bit
stuck.
> it's not so much AMDF & ASDF that i'm interested in but just the
first
> stage of AMDF & ASDF: frequency extraction, the comb filter bit.
maybe
> linking this question to AMDF & ASDF was misleading -- it's more the > just the comb filter aspect. > > comb filters tell you what frequencies exist in a particular bit of > sound -- the kind of logic that you've described with comb filters > (integer multiples) is exactly what i (without expert maths/dsping > knowledge) would come up with using only common sense to go about > extracting frequencies from sound. but when i previously asked about > frequency extraction i was unanimously told "fourier transforms" and > i'm thinking comb filters and fourier transforms must be pretty > different things. > > it's the gap/connection/relation or non-relation between comb filters > and fourier transforms i'm trying to get at and understand. both seem > to be able to do the same thing: extract frequencies. > > say you wanted to simulate (on a computer) the human ear (just the > first stage of hearing -- the ear itself) (i believe it has many
small
> "ears", receptors, that are tuned to various small ranges of > frequencies that overlap each other -- so splits up/extracts > frequencies basically). for each little "ear" (particular frequency > range) would you use a fourier transform or a comb filter? > > > - fourier transforms can be used to extract frequencies from a
sound.
> - comb filters can be used to extract frequencies from a sound. > - logically, and without any pre expert maths knowledge, comb > filters seem like a good, and maybe only, solution to extracting > frequencies out of a sound to me. > - when asking about frequency extraction everyone said fourier > transforms. > - the first stage of AMDF & ASDF is to use comb filters and not > fourier transforms > > the main problem/contradiction i have is: i like the idea of comb > filters because they fit with how i'd imagine going about frequency > extraction, but on the other hand when i asked about frequency > extraction, fourier transforms was the answer i got (from maths / dps > experts), not comb filters. i'd like to use what's best for the job. > > comb filters or fourier transforms. for inner ear receptor
simpulation:
> which? either? neither? > > any advice much appreciated. > > thanks, ben.
In article <1113924254.083701.262530@g14g2000cwa.googlegroups.com>,
Benry <henrybg@gmail.com> wrote:

> Ben, > > Ok, first of all, if you crack open a signal processing or DSP > textbook, you'll learn that Fourier Transforms are used to convert a > time domain signal to a frequency domain. What this does, and why > people are telling you this is important, is, like what you're wanting > to do "finding evenly spaced spikes and > measuring the gap length", but rather than doing this, you can do an > FFT (so it's quicker on O(something I can't recall right now)), and > find the frequency components in the signal you're concerned with.
right. so what you're saying is comb filtering and fourier transforming, or fft'ing as you say, can and do achieve much the same results, apart from fft does it much more efficiently? fft are a shortcut version of comb filters? is that basically correct? (assuming reasonably clever well worked out implementations of both comb filtering and fft's) -- comb filters and fft's can and do give much the same results (ignoring efficiency)?
> you'll learn that Fourier Transforms are used to convert a > time domain signal to a frequency domain
i have learnt that already (but not the internal details, the how part), but then i learnt that AMDF & ASDF don't use fourier transforms, they use comb filters. i found this surprising because i though ft's were *the* answer to frequency extraction. so i'm thinking, and that's what this question's all about, what's the pros and cons and what are the differences between the two methods? if comb filters are good for AMDF & ASDF then they're good for me maybe. comb filters appeal to me because their logic fits in with my common sense -- how i'd imagine you'd go about it. but then fourier transforms appeal to me because that's what everyone has said i should use -- it's the "official" method as it were. i'm quite prepared to learn about fourier transforms -- if they're the best thing to use that is, but i don't want to if it's not necessary. in particular i'm wondering if comb filters, so far as frequency extraction goes, can and do amount to the same thing as a fourier transform (ignoring effiency)? it seems to me at the moment that comb filtering and fft's (ignoring efficiency) can and do amount to the same results but just get there by different routes? (different routes as in different internal, operational logic -- different algorithms).
> Now, if you do this in psuedo-real time, like taking an FFT of every > 100 or 1000 samples or something, finding what frequencies have the > largest amplitudes, or if the frequencies that you don't want in there, > are...you can filter them out using a comb filter, or any other filter. > > > I know you keep stating that you don't want to delve into the math of > it,
unecessarily that is. will if necessary. i think if i were to start implementing a good, well thought out comb filtering scheme it'd quickly get just as complicated as using going the fft's way anyway, but complicated in a different way i think. in fact in some ways i can see fft's being an easier route possibly in the end. i'm still drawn to comb filters though because right now i'm not so fussed about efficiency and comb filters are intuitive -- that's a big plus point for me.
> but for what you're doing, I suggest you give it a go. If you're > interested at first, it will start to make tons of sense once you're > done getting through all of the hell (technical reading)...and you can > apply it affectively for your intended application. > > Hope this helps a bit.
yes i think so -- it certainly hinted that comb filters and fft's amount to much the same thing (ignoring efficiency). not a lot of difference in the actual end results? (depending on a good implementation that is)
> Regards, > Ben
thanks-a-lot, ben.
Hi Ben!

>fft are a shortcut version of comb filters?
No. FFT stands for "Fast Fourier Transform" and is simply a technical method to compute the Fourier transform of discrete signals. So "Fourier transform", "FT", or "FFT" basically mean the same thing here.
>comb filters and
fft's can and do give much the same results (ignoring efficiency)? Not quite right. A Fourier transform transforms a given signal from time domain to frequency domain, so what you get is just another representation of that same signal, not showing you its behaviour over time but its frequency spectrum at a specific time (or over a specific period of time).
>but then i learnt that AMDF & ASDF don't use fourier transforms, they
use comb filters.
>From my understanding, these comb filters are just the spectral
equivalent to the difference terms of time-delayed signals in the time domain.
>in particular i'm wondering if comb filters, so far
as frequency extraction goes, can and do amount to the same thing as a fourier transform (ignoring effiency)? A Fourier transform gives you the spectral view of the signal. I wouldn't call that "extraction". What you want is pitch detection, is it not? So you need to extract the fundamental frequency (a.k.a pitch). Visual or manual extraction of the wanted fundamental frequency just from simply looking at the spectrum (=product of FT), searching for peaks etc. will not always yield best results. That's where ADMF/ASDF comes in. AMDF works in time-domain. It basically computes the difference of the signal itself and time-delayed copies of it. If the delay meets the fundamental period (or multiples of it), this difference in minimized. So searching for these minima gives you the fundamental period, which gives you the fundamental frequency. Best regards, Alex Nagel -- www.alex-nagel.de

hello Alex,

it's actually comb filters i'm asking about not ADMF & ASDF i now
realise -- very sorry about that confusion. also it's raw frequency
extraction, not pitch detection i'm asking about -- again sorry about
that confusion.

In article <1113997108.134296.51030@g14g2000cwa.googlegroups.com>,
<"mail@alex-nagel.de"> wrote:

> >comb filters and > fft's can and do give much the same results (ignoring efficiency)? > > Not quite right. A Fourier transform transforms a given signal from > time domain to frequency domain, so what you get is just another > representation of that same signal, not showing you its behaviour over > time but its frequency spectrum at a specific time (or over a specific > period of time).
right so so you can use that to find out what frequencies occur in a piece of sound. ok. also, alternatively, you can use comb filters to tell you what frequencies occur in a piece of sound (i think -- please correct me if i'm wrong). and my question is, what's the difference between going those two different routes? will they give much the same results or not? (and this is just regarding going from time domain sound data to frequency domain data, one way, and nothing else). thanks, ben.
ben <x@x.x> writes:

> hello Alex, > > it's actually comb filters i'm asking about not ADMF & ASDF i now
What is ASDF? I think you mean "AMDF" and not "ADMF". I found AMDF is "average mean distance function," but also "American Macular Degeneration Foundation. -- Randy Yates Sony Ericsson Mobile Communications Research Triangle Park, NC, USA randy.yates@sonyericsson.com, 919-472-1124
Randy Yates wrote:

> What is ASDF? I think you mean "AMDF" and not "ADMF". I found AMDF > is "average mean distance function," but also "American Macular > Degeneration Foundation.
A,S,D, and F are the first four left-hand letters of the middle row of the letters on the keyboard. :-) Ciao, Peter K.
In article <xxpvf6hd2ok.fsf@usrts005.corpusers.net>, Randy Yates
<randy.yates@sonyericsson.com> wrote:

> ben <x@x.x> writes:
> > it's actually comb filters i'm asking about not ADMF & ASDF i now
> What is ASDF? I think you mean "AMDF" and not "ADMF". I found AMDF is "average > mean distance function," but also "American Macular Degeneration Foundation.
Average Magnitude (or Squared) Difference Function (AMDF or ASDF)