-3
$\begingroup$

I've come to realize what appears to be a hard limit in convolution theorem: to avoid time-domain aliasing, we must pad the signal/filter, but the padding distorts the spectrum.

Consider a minimalistic problem of a sum of perfect $f=1, 5$ signals. Recover $f=1$:

  • $s_1[n] = 10 \cos(2 \pi n/N)$; $s_2[n] = 1 \cos (10 \pi n/N)$
  • $s[n] = s_1[n] + s_2[n]$; $n=[0, ... , N-1]$, $N=128$ samples.
  • Goal: $\text{MAE}(r[n] - s_1[n]) < 1e\text{-}10$, where $r[n]$ is $s[n]$ filtered by $f[n]$.

Matter's complicated with the output signal being dilated - we cannot even compare these sample-by-sample.


This said, is it all a rough approximation game? If we can't unmix a trivially separable signal, what hope do we have of a more complex case? Further, shouldn't we be doing the math proactively for the filter - i.e., find the taps such that, when padded, yield the desired frequency response. This still wouldn't undo the signal's padding spectrum distortion.


Example: -- code (note; I use linspace(0, 1, N), which is the n/N defined above)

Note: s_1 and s_2 are not constants, read carefully, and the mods should remove that outdated comment claiming otherwise per site guidelines.

$\endgroup$
9
  • $\begingroup$ For the Mean Absolute Error we could instead compare DFT coefficients, up to as many as in s_1 - seems fair enough, unless the filtered signal has large coefficients for higher frequencies $\endgroup$ Sep 23 '20 at 6:29
  • 2
    $\begingroup$ I would suggest the use of the word "separate" rather than "unmix" as "mixing" is associated with "modulation". To your question, when you pad your $h$ you increase the order of the filter. Therefore, why pad and not actually re-generate your filter with higher resolution? Is it possible to share a bit more information about the motivation behind the question? $\endgroup$
    – A_A
    Sep 23 '20 at 7:53
  • 1
    $\begingroup$ Yes they can actually separate ( unmix ) superposed signals. In general it will not be perfect in the mathematical sense, but acceptable in the physical (engineering) one. The reason is the mismatch between ideal (mathematical) assumptions and practical (physical) reality... But the error could be minimized down to being unrecognized depending on the application.. $\endgroup$
    – Fat32
    Sep 23 '20 at 10:42
  • 3
    $\begingroup$ Has anyone noticed that $s_1[n]$ and $s_2[n]$ are constants, that is, have values 10 and 1 respectively for all $n$? $\endgroup$ Sep 23 '20 at 17:44
  • 3
    $\begingroup$ More nonsense. It is conventional that what is inside square brackets is an integer and it is NOT the reader’s job to read whatever you have hidden in the code; your posting must stand on its merits (or lack thereof) as are visible to the reader. $\endgroup$ Sep 23 '20 at 18:04
2
$\begingroup$

but the padding distorts the spectrum.

No, it doesn't. Zero padding just increases spectral resolution.

Consider a minimalistic problem of a sum of perfect f=1,5 signals.

I assume you mean ideal sine waves at 1Hz and 5 Hz ?

$N=128$ samples.

And here is where your problem is. Once you constrain the numnber of samples you don't have sine wave anymore, but a truncated sine wave and that has a significantly different spectrum than your orginal signal. Two truncated sine waves have (in general) overlapping spectra so they are not perfectly separable any more.

That has NOTING to do with filtering. The damage is done before you design or apply any filters. Sine waves are an interesting mathematical concept, but they DON'T EXIST in the real world. In order for a sine wave to be a sine wave with infinitely small spectral extension it needs to be infinitely long and that's simply not possible.

UPDATE:

Sorry, this sparked a lively discussion which I didnt intend. Let me try to rephrase by stating the question more formally. Let

$$x(t) = sin (\omega_1 t) + sin( \omega_2 t) $$

We can sample this $x[n] = x(nT)$ without loss of information at any sample interval $T < 1/pi \cdot max(\omega_1,\omega_2) $ The question (as I understand it): is there a set discrete filters with impulse responses $h_1[n]$ and $h_2[n]$ so that

$$x[n] \ast h_1[n] = sin(\omega_1 nT) $$ $$ x[n] \ast h_2[n] = sin(\omega_2 nT) $$

The answer to that question is definitely yes, there are many filters that will do this. Any filter with $H_1(\omega_1) = 1, H_1(\omega_2) = 0$ will work. Any brickwall filter with a cut off between $\omega_1$ and $\omega_2$ will work and you and can do this with just a 2 tap complex FIR filter (in most cases).

Now if the question is: can you write a computer program to do this, than the answer is no. The convolution is defined as $$y[n] = \sum_{k=-\infty}^{\infty}x[k] \cdot h[n-k]$$

You can't code this up since you need access to an infintely large number of past samples. The meta point here is that all signals you can actually process numerically have to have a beginning (and mostly an end as well). As such they can't be sine waves so the original question is purely a theoretical one.

One of the more obscure aspects of sampling "real world" signals is that you can't do it without loss of information. Any (physical) signal is finite in time and hence it has infinite bandwith. So you always have to live with some amount of aliasing. Obvioulsy you can make it so small that it's negligble or smaller than you noise floor anyway, but there is no such thing as "perfect sampling" and "perfect reconstruction".

$\endgroup$
9
  • 1
    $\begingroup$ My second or maybe third downvote ever. Sorry, but this is so wrong. See dsp.stackexchange.com/questions/69761/… for a counter example. You were okay-ish until the last paragraph. Where is the "spectrum of your original signal"? Some construction of an underlying continuous model? Multiple noiseless pure tones are theoretically exactly separable. Even intrabin separable, including ones that fall in between bins 0 and 1. However, this separability is extremely noise/precision sensitive. $\endgroup$ Sep 23 '20 at 13:15
  • 1
    $\begingroup$ @CedronDawg My only issue would be the first statement but that is semantics on what we refer to as resolution. But I didn't really see a problem with his last paragraph and the significance of the intended message. I would agree that noiseless pure tones are a mathematical concept and don't exist in "the real world" (whatever that is); importantly we do need to understand the implications of noise and how this effects the OP's question so I thought this was a good answer/ point about the requirement for infinitely long sine waves to have infinitely narrow frequency resolution. $\endgroup$ Sep 23 '20 at 15:28
  • $\begingroup$ You need to have an infinitely long DFT frame, with an infinitely long signal to get a bin width down to an infinitesimal size. (Not about resolution.) My experience with real world signals is that the duration of signal's resemblance to a pure tone is usually the dominant limiting factor. There is no "damage" being done. A truncated sine wave is still a sine wave. "Spectral extension" here appears to be a synonym for "leakage" (another misnomer applicable only in a few specific uses of the DFT) rather than the periodicity emphasized by RB-J. Overloading definitions is often used to obfuscate. $\endgroup$ Sep 23 '20 at 16:11
  • 1
    $\begingroup$ As Dan mentioned too, the only (minor) problem is the first statement on the zero padding vs frequency resolution increase... I'm pretty sure that Hilmar is aware of this more than I'm that zero padding does not increase the resolution but oversamples the same DTFT X(w) of x[n]. As long as x[n] stays as the same sequence, X(w) will be the same spectrum, and zero padding x[n] will only over sample X(w). Oversampling does not add information to the samples obtained at the critical rate, hence it cannot increase spectral resolution which would imply an increase in the information in X[k]. $\endgroup$
    – Fat32
    Sep 23 '20 at 16:23
  • 1
    $\begingroup$ I challenge you all to express and describe these same concepts using only the discrete model. It can be done, and I've done many times in many places to illustrate my larger theme above. Getting specific to this case, taking "resolution" to mean "precision" have a look at the "Multiple Tone Decomposition" section in dsprelated.com/showarticle/1365.php. Theoretical infinite precision frequency determination from a finite window should be abundantly clear. $\endgroup$ Sep 23 '20 at 16:55
1
$\begingroup$

It is trivial to separate the signals in a noise-free purely mathematical case: unless you have more information to bound it further, such a question boils down to "How many independent equations do you need, and therefore how many independent samples do you need, to solve for $n$ unknowns?" For noise free cases @Cedron has blog articles (https://www.dsprelated.com/blogs-1/nf/Cedron_Dawg.php) on minimum solutions and as @Amro has commented in another post, this article may be of interest: Karhunen, Juha T., and Jyrki Joutsensalo. "Sinusoidal frequency estimation by signal subspace approximation." IEEE Transactions on signal processing 40.12 (1992): 2961-2972. Specific to most signal processing applications we would be interested in separating the signals in the presence of noise for which approaches that consider noise would have the most practical use. This is applicable to digital filter design where frequency resolution is a driving concern.

As for the effects of padding; padding does nothing to distort the spectrum - When the time duration of the signal is finite, the spectrum is discrete (simplest example of this from the continuous time domain is the Fourier Series Expansion, and we see the same result with the DFT). Zero padding will not change any of the DFT samples which is the given spectrum based on those time domain samples, but will interpolate new samples in between (without adding any new information we didn't already have other than visual appearance). The original samples, which represents ALL our given information, will be unchanged hence there is no "distortion".

Zero padding does not increase frequency resolution, but interpolates more samples on the Discrete Time Fourier Transform (DTFT) which is a continuous function in frequency. To increase frequency resolution (which the DTFT reveals), we must increase the time duration of the actual signal (the number of samples if the sampling rate is not changed), assuming the signal is stationary in which case whatever we have in our short duration capture continues in reality for a longer time duration: capture a longer duration of that signal and you increase the frequency resolution.

These concepts are detailed further at these posts:

Smallest FFT buffer size given zero-padding

Why should I zero-pad a signal before taking the Fourier transform?

upsampling in the frequency domain

What happens when N increases in N-point DFT

Specific Frequency Resolution

Does downsampling increase the resolution of frequencies?


As for the OP's code example the signals are 1 Hz and 5 Hz and 14 dB apart, with a duration of 1 second (assuming a time axis in seconds). The dynamic range is small (14 dB), but large enough to compete with the sidelobes of the Dirichlet Kernel so windowing will be recommended. In this case we want a window that will reduce the sidelobe sufficient to see the signal 14 dB down, but still maintain a tight enough frequency resolution to discern the 1 Hz from the 5 Hz tone.

The OP also chose an integer number of cycles over the captured time duration resulting in no spectral leakage from the tones and as we see in the plot below, the noise floor given by the double-precision float that I used for the computation. But this is not a realistic assumption that we will be able to capture an exact integer number of cycles, so has little practical value.

DFT rectangular window

By zero-padding we can most easily see the effect of the spectral leakage for all cases of non-integer cycles as shown in this plot below and the zoomed in view below that showing the difficulty in making out the presence of the 5 Hz tone by using the FFT in non-integer cases without further windowing (this is not a "distortion" due to the zero-padding but shows us what would occur with or without padding when we consider all possible signals and motivates the reason for windowing):

DTFT

DTFT zoom

For example here is the similar plot without zero padding but using worst case frequencies of 1.5 and 5.5 Hz showing the FFT results landing on the peaks of the sidelobes predicted by the zero-padded FFT (in close agreement with the upper plot shifted to the right by 1/2 Hz).

1.5 and 5.5 Hz

However this is easily solved with judicious windowing such as this case below with a Kaiser window with $\beta = 6$. The zero padding is not needed but gives us confidence as a verification that we could work with any frequencies close to but not exactly 1 Hz and 5 Hz such that there is no longer the integer cycle condition. What is clear is we cannot allow the frequencies to be arbitrarily close and with this approach the only way to allow for further frequency resolution is to increase the total time duration of the signal. (This example had a $T=1$ second duration with a frequency resolution therefore of approximately $1/T = 1$ Hz, widened further due to the windowing. To allow for the resolution to be 10x better we would need to increase the time duration of the signal to 10 seconds.)

Kaiser Windowed

$\endgroup$
30
  • $\begingroup$ For all my questions ever, just take them as-is, without further context on noise and such. I am exploring the fundamentals here. As for all that material you linked (of which I've read much of) - can you use it to design a filter to separate the signals? $\endgroup$ Sep 23 '20 at 17:52
  • $\begingroup$ @OverLordGoldDragon I was debating your first sentence which I can't take as-is: to me it is a clear misunderstanding that may be the root of the rest of your question. (I didn't down-vote your question by the why). Yes the links are to the fundamentals on ability to separate signals using digital filters. This is similar to your other post where I focused on time duration. Zero padding does not affect the time duration and really doesn't serve any purpose for filter design (given we aren't necessarily using FFT's for filtering--- any FIR filter follows the principals of linear convolution). $\endgroup$ Sep 23 '20 at 20:22
  • $\begingroup$ I realize I have plenty to convey so I'm cooking up a thread at the moment; it's a shame that people here seem to vote by just what they agree with - no points for scrutinizing caveats or digging in fundamentals. Don't really care unless it discourages discussion; I'm here for knowledge. $\endgroup$ Sep 23 '20 at 20:27
  • $\begingroup$ The votes on the question are very specific if done right (if you hover over the down-vote it specifies the criteria used). Hopefully whoever down-votes also comments as the intention is to improve the question for the benefit of all. Best is to gain from that feedback and improve the question (then they should remove the down-vote). You didn't fix the first sentence I suggested so you either disagree or don't see that as distracting from your real question as I do? Regardless it is great you are asking questions and engaging with the community. $\endgroup$ Sep 23 '20 at 21:27
  • $\begingroup$ I appreciate the effort you devote to these Q&A's; done cooking - look forward to feedback. $\endgroup$ Sep 24 '20 at 2:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.