automatic detection of aliasing?

Started by Vista June 2, 2007
Hi all,

I need your help on the following difficulties:

I am designing something like "automatic" detection of aliasing, 
programmatically.

For a given signal discrete time signal x(n), possibly infinite support, we 
know its values are all positive, they are absolutely summable, so DTFT 
exists and we know that the signal die down for large n, and it can be 
roughly deemed as zero for some N and for all n>=N.

Now suppose we don't have the signal x(n) in the time domain, so we don't 
know N, but we have its DTFT available, called X(w).

The problem is to decide the smallest number of sampling point needed to 
sample the X(w) in the frequency domain.

Sampling X(w) will lead to aliasing and periodic overlapping of x(n). But 
for a suitable number of sampling points (related to the unknown N), the 
aliasing error can be controlled under a prespecified threshold epsilon.

Let's say we start with 128 sampling points, and by eye inspection of the 
reconstructed signal x_hat(n) in the time domain, we found aliasing, so we 
decide to move to 256 sampling points, so on and so forth.

How to automate the above eye inspection process? How to let computer 
decide, programmatically, what is an aliased reconstruction and what is not 
an aliased reconstruction? I hope to find a "quality" function, which costs 
minimal amount of computations, based on which the program can decide 
whether there is aliasing or not. The added computational overhead has to be 
small because we have to run millions of this type of "automatic" aliasing 
detector in real time...

Any thoughts?

Thanks a lot! 


Vista wrote:
> Hi all, > > I need your help on the following difficulties: > > I am designing something like "automatic" detection of aliasing, > programmatically. > > For a given signal discrete time signal x(n), possibly infinite support, we > know its values are all positive, they are absolutely summable, so DTFT > exists and we know that the signal die down for large n, and it can be > roughly deemed as zero for some N and for all n>=N. > > Now suppose we don't have the signal x(n) in the time domain, so we don't > know N, but we have its DTFT available, called X(w). > > The problem is to decide the smallest number of sampling point needed to > sample the X(w) in the frequency domain. > > Sampling X(w) will lead to aliasing and periodic overlapping of x(n). But > for a suitable number of sampling points (related to the unknown N), the > aliasing error can be controlled under a prespecified threshold epsilon. > > Let's say we start with 128 sampling points, and by eye inspection of the > reconstructed signal x_hat(n) in the time domain, we found aliasing, so we > decide to move to 256 sampling points, so on and so forth.
You can't detect aliasing by eye or any other way if you don't know the original signal. Every set of samples represents one non-aliased signal and an infinite number of aliased ones.
> How to automate the above eye inspection process? How to let computer > decide, programmatically, what is an aliased reconstruction and what is not > an aliased reconstruction? I hope to find a "quality" function, which costs > minimal amount of computations, based on which the program can decide > whether there is aliasing or not. The added computational overhead has to be > small because we have to run millions of this type of "automatic" aliasing > detector in real time...
Are you sampling in time or frequency? If you have the DTFT, then you have the highest significant frequency by inspection (once you decide what "significant" is). Jerry -- Engineering is the art of making what you want from things you can get. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
"Jerry Avins" <jya@ieee.org> wrote in message 
news:haOdndxyQrQpR_zbnZ2dnUVZ_gSdnZ2d@rcn.net...
> Vista wrote: >> Hi all, >> >> I need your help on the following difficulties: >> >> I am designing something like "automatic" detection of aliasing, >> programmatically. >> >> For a given signal discrete time signal x(n), possibly infinite support, >> we know its values are all positive, they are absolutely summable, so >> DTFT exists and we know that the signal die down for large n, and it can >> be roughly deemed as zero for some N and for all n>=N. >> >> Now suppose we don't have the signal x(n) in the time domain, so we don't >> know N, but we have its DTFT available, called X(w). >> >> The problem is to decide the smallest number of sampling point needed to >> sample the X(w) in the frequency domain. >> >> Sampling X(w) will lead to aliasing and periodic overlapping of x(n). But >> for a suitable number of sampling points (related to the unknown N), the >> aliasing error can be controlled under a prespecified threshold epsilon. >> >> Let's say we start with 128 sampling points, and by eye inspection of the >> reconstructed signal x_hat(n) in the time domain, we found aliasing, so >> we decide to move to 256 sampling points, so on and so forth. > > You can't detect aliasing by eye or any other way if you don't know the > original signal. Every set of samples represents one non-aliased signal > and an infinite number of aliased ones. >
Why not? If I see 256 and 512 sample points do not yield visual difference, then I know 256 is a good number.
>> How to automate the above eye inspection process? How to let computer >> decide, programmatically, what is an aliased reconstruction and what is >> not an aliased reconstruction? I hope to find a "quality" function, which >> costs minimal amount of computations, based on which the program can >> decide whether there is aliasing or not. The added computational overhead >> has to be small because we have to run millions of this type of >> "automatic" aliasing detector in real time... > > Are you sampling in time or frequency? If you have the DTFT, then you have > the highest significant frequency by inspection (once you decide what > "significant" is). >
As you see, I am sampling the DTFT X(w). And this is the sampling in frequency. I want to detect the aliasing of time domain signal x(n) due to frequency domain sampling on X(w).
Vista wrote:
> "Jerry Avins" <jya@ieee.org> wrote in message > news:haOdndxyQrQpR_zbnZ2dnUVZ_gSdnZ2d@rcn.net... >> Vista wrote: >>> Hi all, >>> >>> I need your help on the following difficulties: >>> >>> I am designing something like "automatic" detection of aliasing, >>> programmatically. >>> >>> For a given signal discrete time signal x(n), possibly infinite support, >>> we know its values are all positive, they are absolutely summable, so >>> DTFT exists and we know that the signal die down for large n, and it can >>> be roughly deemed as zero for some N and for all n>=N. >>> >>> Now suppose we don't have the signal x(n) in the time domain, so we don't >>> know N, but we have its DTFT available, called X(w). >>> >>> The problem is to decide the smallest number of sampling point needed to >>> sample the X(w) in the frequency domain. >>> >>> Sampling X(w) will lead to aliasing and periodic overlapping of x(n). But >>> for a suitable number of sampling points (related to the unknown N), the >>> aliasing error can be controlled under a prespecified threshold epsilon. >>> >>> Let's say we start with 128 sampling points, and by eye inspection of the >>> reconstructed signal x_hat(n) in the time domain, we found aliasing, so >>> we decide to move to 256 sampling points, so on and so forth. >> You can't detect aliasing by eye or any other way if you don't know the >> original signal. Every set of samples represents one non-aliased signal >> and an infinite number of aliased ones. >> > > Why not? If I see 256 and 512 sample points do not yield visual difference, > then I know 256 is a good number.
What are you sampling if you have only the DTFT?
>>> How to automate the above eye inspection process? How to let computer >>> decide, programmatically, what is an aliased reconstruction and what is >>> not an aliased reconstruction? I hope to find a "quality" function, which >>> costs minimal amount of computations, based on which the program can >>> decide whether there is aliasing or not. The added computational overhead >>> has to be small because we have to run millions of this type of >>> "automatic" aliasing detector in real time... >> Are you sampling in time or frequency? If you have the DTFT, then you have >> the highest significant frequency by inspection (once you decide what >> "significant" is). >> > > As you see, I am sampling the DTFT X(w). And this is the sampling in > frequency. I want to detect the aliasing of time domain signal x(n) due to > frequency domain sampling on X(w).
You can construe the frequency data as a time series and anti-alias filter it. Jerry -- Engineering is the art of making what you want from things you can get. &macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;
"Jerry Avins" <jya@ieee.org> wrote in message 
news:-OydnVWHs_4Kc_zbnZ2dnUVZ_hOdnZ2d@rcn.net...
> Vista wrote: >> "Jerry Avins" <jya@ieee.org> wrote in message >> news:haOdndxyQrQpR_zbnZ2dnUVZ_gSdnZ2d@rcn.net... >>> Vista wrote: >>>> Hi all, >>>> >>>> I need your help on the following difficulties: >>>> >>>> I am designing something like "automatic" detection of aliasing, >>>> programmatically. >>>> >>>> For a given signal discrete time signal x(n), possibly infinite >>>> support, we know its values are all positive, they are absolutely >>>> summable, so DTFT exists and we know that the signal die down for large >>>> n, and it can be roughly deemed as zero for some N and for all n>=N. >>>> >>>> Now suppose we don't have the signal x(n) in the time domain, so we >>>> don't know N, but we have its DTFT available, called X(w). >>>> >>>> The problem is to decide the smallest number of sampling point needed >>>> to sample the X(w) in the frequency domain. >>>> >>>> Sampling X(w) will lead to aliasing and periodic overlapping of x(n). >>>> But for a suitable number of sampling points (related to the unknown >>>> N), the aliasing error can be controlled under a prespecified threshold >>>> epsilon. >>>> >>>> Let's say we start with 128 sampling points, and by eye inspection of >>>> the reconstructed signal x_hat(n) in the time domain, we found >>>> aliasing, so we decide to move to 256 sampling points, so on and so >>>> forth. >>> You can't detect aliasing by eye or any other way if you don't know the >>> original signal. Every set of samples represents one non-aliased signal >>> and an infinite number of aliased ones. >>> >> >> Why not? If I see 256 and 512 sample points do not yield visual >> difference, then I know 256 is a good number. > > What are you sampling if you have only the DTFT?
As I said, I am sampling the DTFT in frequency domain in [0, 2*pi], and then apply IFFT to reconstruct x(n) in time domain. And there is aliasing depending on how many samples I use in sampling.
> >>>> How to automate the above eye inspection process? How to let computer >>>> decide, programmatically, what is an aliased reconstruction and what is >>>> not an aliased reconstruction? I hope to find a "quality" function, >>>> which costs minimal amount of computations, based on which the program >>>> can decide whether there is aliasing or not. The added computational >>>> overhead has to be small because we have to run millions of this type >>>> of "automatic" aliasing detector in real time... >>> Are you sampling in time or frequency? If you have the DTFT, then you >>> have the highest significant frequency by inspection (once you decide >>> what "significant" is). >>> >> >> As you see, I am sampling the DTFT X(w). And this is the sampling in >> frequency. I want to detect the aliasing of time domain signal x(n) due >> to frequency domain sampling on X(w). > > You can construe the frequency data as a time series and anti-alias filter > it. >
Good idea. Yes, filter in the frequency domain. However I first have to decide how many samples do I use for [0, 2*pi]. So you are talking about an analog filter or digital filter?
Vista wrote:
> "Jerry Avins" <jya@ieee.org> wrote in message > news:-OydnVWHs_4Kc_zbnZ2dnUVZ_hOdnZ2d@rcn.net... >> Vista wrote: >>> "Jerry Avins" <jya@ieee.org> wrote in message >>> news:haOdndxyQrQpR_zbnZ2dnUVZ_gSdnZ2d@rcn.net... >>>> Vista wrote: >>>>> Hi all, >>>>> >>>>> I need your help on the following difficulties: >>>>> >>>>> I am designing something like "automatic" detection of aliasing, >>>>> programmatically. >>>>> >>>>> For a given signal discrete time signal x(n), possibly infinite >>>>> support, we know its values are all positive, they are absolutely >>>>> summable, so DTFT exists and we know that the signal die down for large >>>>> n, and it can be roughly deemed as zero for some N and for all n>=N. >>>>> >>>>> Now suppose we don't have the signal x(n) in the time domain, so we >>>>> don't know N, but we have its DTFT available, called X(w). >>>>> >>>>> The problem is to decide the smallest number of sampling point needed >>>>> to sample the X(w) in the frequency domain. >>>>> >>>>> Sampling X(w) will lead to aliasing and periodic overlapping of x(n). >>>>> But for a suitable number of sampling points (related to the unknown >>>>> N), the aliasing error can be controlled under a prespecified threshold >>>>> epsilon. >>>>> >>>>> Let's say we start with 128 sampling points, and by eye inspection of >>>>> the reconstructed signal x_hat(n) in the time domain, we found >>>>> aliasing, so we decide to move to 256 sampling points, so on and so >>>>> forth. >>>> You can't detect aliasing by eye or any other way if you don't know the >>>> original signal. Every set of samples represents one non-aliased signal >>>> and an infinite number of aliased ones. >>>> >>> Why not? If I see 256 and 512 sample points do not yield visual >>> difference, then I know 256 is a good number. >> What are you sampling if you have only the DTFT? > > As I said, I am sampling the DTFT in frequency domain in [0, 2*pi], and then > apply IFFT to reconstruct x(n) in time domain. And there is aliasing > depending on how many samples I use in sampling. > >>>>> How to automate the above eye inspection process? How to let computer >>>>> decide, programmatically, what is an aliased reconstruction and what is >>>>> not an aliased reconstruction? I hope to find a "quality" function, >>>>> which costs minimal amount of computations, based on which the program >>>>> can decide whether there is aliasing or not. The added computational >>>>> overhead has to be small because we have to run millions of this type >>>>> of "automatic" aliasing detector in real time... >>>> Are you sampling in time or frequency? If you have the DTFT, then you >>>> have the highest significant frequency by inspection (once you decide >>>> what "significant" is). >>>> >>> As you see, I am sampling the DTFT X(w). And this is the sampling in >>> frequency. I want to detect the aliasing of time domain signal x(n) due >>> to frequency domain sampling on X(w). >> You can construe the frequency data as a time series and anti-alias filter >> it. >> > > > Good idea. Yes, filter in the frequency domain. However I first have to > decide how many samples do I use for [0, 2*pi]. > > So you are talking about an analog filter or digital filter?
Digital. I didn't imagine you had an analog DTFT. Is there such a thing? Jerry -- Engineering is the art of making what you want from things you can get. &macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;&macr;
"Jerry Avins" <jya@ieee.org> wrote in message 
news:6MqdnVa99MXmYPzbnZ2dnUVZ_sWdnZ2d@rcn.net...
> Vista wrote: >> "Jerry Avins" <jya@ieee.org> wrote in message >> news:-OydnVWHs_4Kc_zbnZ2dnUVZ_hOdnZ2d@rcn.net... >>> Vista wrote: >>>> "Jerry Avins" <jya@ieee.org> wrote in message >>>> news:haOdndxyQrQpR_zbnZ2dnUVZ_gSdnZ2d@rcn.net... >>>>> Vista wrote: >>>>>> Hi all, >>>>>> >>>>>> I need your help on the following difficulties: >>>>>> >>>>>> I am designing something like "automatic" detection of aliasing, >>>>>> programmatically. >>>>>> >>>>>> For a given signal discrete time signal x(n), possibly infinite >>>>>> support, we know its values are all positive, they are absolutely >>>>>> summable, so DTFT exists and we know that the signal die down for >>>>>> large n, and it can be roughly deemed as zero for some N and for all >>>>>> n>=N. >>>>>> >>>>>> Now suppose we don't have the signal x(n) in the time domain, so we >>>>>> don't know N, but we have its DTFT available, called X(w). >>>>>> >>>>>> The problem is to decide the smallest number of sampling point needed >>>>>> to sample the X(w) in the frequency domain. >>>>>> >>>>>> Sampling X(w) will lead to aliasing and periodic overlapping of x(n). >>>>>> But for a suitable number of sampling points (related to the unknown >>>>>> N), the aliasing error can be controlled under a prespecified >>>>>> threshold epsilon. >>>>>> >>>>>> Let's say we start with 128 sampling points, and by eye inspection of >>>>>> the reconstructed signal x_hat(n) in the time domain, we found >>>>>> aliasing, so we decide to move to 256 sampling points, so on and so >>>>>> forth. >>>>> You can't detect aliasing by eye or any other way if you don't know >>>>> the original signal. Every set of samples represents one non-aliased >>>>> signal and an infinite number of aliased ones. >>>>> >>>> Why not? If I see 256 and 512 sample points do not yield visual >>>> difference, then I know 256 is a good number. >>> What are you sampling if you have only the DTFT? >> >> As I said, I am sampling the DTFT in frequency domain in [0, 2*pi], and >> then apply IFFT to reconstruct x(n) in time domain. And there is aliasing >> depending on how many samples I use in sampling. >> >>>>>> How to automate the above eye inspection process? How to let computer >>>>>> decide, programmatically, what is an aliased reconstruction and what >>>>>> is not an aliased reconstruction? I hope to find a "quality" >>>>>> function, which costs minimal amount of computations, based on which >>>>>> the program can decide whether there is aliasing or not. The added >>>>>> computational overhead has to be small because we have to run >>>>>> millions of this type of "automatic" aliasing detector in real >>>>>> time... >>>>> Are you sampling in time or frequency? If you have the DTFT, then you >>>>> have the highest significant frequency by inspection (once you decide >>>>> what "significant" is). >>>>> >>>> As you see, I am sampling the DTFT X(w). And this is the sampling in >>>> frequency. I want to detect the aliasing of time domain signal x(n) due >>>> to frequency domain sampling on X(w). >>> You can construe the frequency data as a time series and anti-alias >>> filter it. >>> >> >> >> Good idea. Yes, filter in the frequency domain. However I first have to >> decide how many samples do I use for [0, 2*pi]. >> >> So you are talking about an analog filter or digital filter? > > Digital. I didn't imagine you had an analog DTFT. Is there such a thing? >
If you apply a digital filter in the frequecy domain on the sampled X(w) values, treating it as a time series, then you already sample it before you apply the anti-aliasing filter. And our original question was exactly how many samples do we need to sample the X(w) at the first place. That's why I felt there is a problem with applying the digital filter... Any more thoughts?
On Sat, 2 Jun 2007 14:18:55 -0700, "Vista" <abc@gmai.com> wrote:

> >"Jerry Avins" <jya@ieee.org> wrote in message >news:haOdndxyQrQpR_zbnZ2dnUVZ_gSdnZ2d@rcn.net... >> Vista wrote: >>> Hi all, >>> >>> I need your help on the following difficulties: >>> >>> I am designing something like "automatic" detection of aliasing, >>> programmatically. >>> >>> For a given signal discrete time signal x(n), possibly infinite support, >>> we know its values are all positive, they are absolutely summable, so >>> DTFT exists and we know that the signal die down for large n, and it can >>> be roughly deemed as zero for some N and for all n>=N. >>> >>> Now suppose we don't have the signal x(n) in the time domain, so we don't >>> know N, but we have its DTFT available, called X(w). >>> >>> The problem is to decide the smallest number of sampling point needed to >>> sample the X(w) in the frequency domain. >>> >>> Sampling X(w) will lead to aliasing and periodic overlapping of x(n). But >>> for a suitable number of sampling points (related to the unknown N), the >>> aliasing error can be controlled under a prespecified threshold epsilon. >>> >>> Let's say we start with 128 sampling points, and by eye inspection of the >>> reconstructed signal x_hat(n) in the time domain, we found aliasing, so >>> we decide to move to 256 sampling points, so on and so forth. >> >> You can't detect aliasing by eye or any other way if you don't know the >> original signal. Every set of samples represents one non-aliased signal >> and an infinite number of aliased ones. >> > >Why not? If I see 256 and 512 sample points do not yield visual difference, >then I know 256 is a good number.
Unless they're both aliased with the aliased energy falling within the first 256 points. I don't see how that gets resolved until you've accumulated an infinite number of points. Theoretically, of course. In any practical system there will be natural, unavoidable bandlimiting at some point. The number of samples needed may still be completely impractical, though. Eric Jacobsen Minister of Algorithms Abineau Communications http://www.ericjacobsen.org
On Jun 3, 12:50 am, Eric Jacobsen <eric.jacob...@ieee.org> wrote:
> > Unless they're both aliased with the aliased energy falling within the > first 256 points. > > I don't see how that gets resolved until you've accumulated an > infinite number of points. > > Theoretically, of course. In any practical system there will be > natural, unavoidable bandlimiting at some point. The number of > samples needed may still be completely impractical, though. > > Eric Jacobsen > Minister of Algorithms > Abineau Communicationshttp://www.ericjacobsen.org
What Eric is getting at here, I think, is whether you have any prior knowledge of your signal of interest. If you do not, then how can you "know" when there is aliasing? For *parametric* signals, there are methods for automatic detection of aliasing without having to resort back to the analog domain, but you don't say what your signal is. Julius

julius wrote:

> > For *parametric* signals, there are methods for automatic > detection of aliasing without having to resort back to the > analog domain, but you don't say what your signal is. >
If the signal is sampled with the proper rate then adding the extra samples is not going to add any new information. For example, we can make a polynomial interpolation of the signal and integrate the squared difference between the polynoms for the different sample rates. This can be a measure of the amount of aliasing. Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com