0
$\begingroup$

Consider two sequences $x[n]$ and $y[n]$ being simultaneously sampled from a real-world signal.

Let $x[n]$ be a sequence of length $N$ sampled for duration of $T_x$ at rate $f_x$

$n = 0, ..., N-1$

Denote $\mathscr{F}$ the Discrete Fourier Transform operator and $X[k] = \mathscr{F}\{x[n]\}$

$k = 0, ..., N-1$

For simplicity, I would just consider the first half components so $k = 0, ..., N / 2$.

Let $y[n]$ be a sequence of length $L$ sampled for duration of $T_y$ at rate $f_y$.

$n = 0, ..., L-1$

Denote $\mathscr{F}$ the Discrete Fourier Transform operator and $Y[k] = \mathscr{F}\{y[n]\}$

$k = 0, ..., L-1$

For simplicity, I would just consider the first half components so $k = 0, ..., L / 2$.

If $L = N$, $T_x = T_y$ , and $f_x = f_y$, then $x[n] = y[n]$. I will introduce two factors $m_t$ = $T_y / T_x$ and $m_f = f_y / f_x$, from which $L/N = m_t m_f$ can also be drawn. Now, consider two cases for when $L > N$.

Case 1: $m_t > 1$ and $m_f = 1$ (meaning that $y[n]$ was sampled for longer duration than $x[n]$ but at the same rate). In frequency domain, $Y[k]$ can be said to be an interpolated version of $X[k]$

case 2: $m_f > 1$ and $m_t = 1$ (meaning that $y[n]$ was sampled at higher rate than $x[n]$ but for the same duration) In frequency domain, $Y[k]$ can be said to be an extrapolated version of $X[k]$

Here my question is.

Is there a mathematical expression, way, derivation, or anything using the $DTFT$ and $DFT$ that shows that $m_t$ is related to frequency interpolation and $m_f$ is related to frequency extrapolation? For example, is giving a mathematical expression that shows how $X[k]$ is related to $X_{padded}[k]$, where $X_{padded}[k]$ is DFT of zero-padded $x[n]$, a valid way to show that having the case of $m_t>1$ is related to frequency interpolation? Or it is simply not necessary to show anything to say that $m_t>1$ is related to frequency interpolation and $m_f>1$ is related to frequency extrapolation?

$\endgroup$
12
  • 1
    $\begingroup$ Welcome to our SE! I think your question needs some clarification. Is $g(t)$ bandlimited and, if so, how does the band limit related to $f_x$ and $f_y$? Does $g(t)$ has finite length and, if so, how does that length relates to $T_x$ and $T_y$. In general if $T_x \neq T_y$ you won't be able to derive any meaningful relationships between $X[k]$ and $Y[k[$ . A trivial example is $g(t) = \delta(t-\Delta)$ with $T_x < \Delta < T_y$. In this case $Y[k] = 1$ and $X[k] = 0$ for all k regardless of $m_f$ and $m_t$ other than $m_t > 1$. $\endgroup$
    – Hilmar
    Commented Jan 17 at 2:57
  • 1
    $\begingroup$ I don't think you got it right about what happens in the time domain to $x[n]$ when you interleave zeros between adjacent values of $X[k]$. $\endgroup$ Commented Jan 17 at 2:59
  • $\begingroup$ Hi, thank you for the comments!. Let me clarify some of points Hilmar asked. Yes, $g(t)$ is bandlimited and I will assume that $f_x$ and $f_y$ are both well above the limit. To simplify my question (hopefully this way, it helps people not to get confused), all I need to show is the $m_t (when \neq 1)$ and $m_f (when \neq 1)$ are related to interpolating (e.g., interleaving) and extrapolating (e.g., zero padding) in frequency domain. I am assuming the case where $L \geq N$ either due to $m_t \geq 1$ or $m_f \geq 1$. For $T_x \neq T_y$, we can assume that $y[n]$ is padded version of $x[n]$ $\endgroup$
    – auckydocky
    Commented Jan 17 at 4:16
  • $\begingroup$ Hi, robert. I am guessing the interleaving may have put some confusion. What I am looking after is not necessarily about interleaving $x[n]$ with zeros, but what i need to show is having a case of $m_t \geq 1$ (i.e., going from x[n] to y[n] through some mapping) is related to increasing spectral resolution of $X[k]$ (i.e., the spectral information of X[k] will present at Y[m] where $m = m_t * k$, supposing $m_t * k$ an positive integer). For Y[m] where $m \neq m_t * k$, we will have something other than zeros, thus i am referring the whole process as interpolating. $\endgroup$
    – auckydocky
    Commented Jan 17 at 4:35
  • $\begingroup$ For the above comments, I must have said that $y[n]$ is an extension of $x[n]$ (i.e., $x \in y$) $\endgroup$
    – auckydocky
    Commented Jan 17 at 4:42

2 Answers 2

1
$\begingroup$

I'll try to answer my questions as best as I can using the DFT, since zero-padding in the context of the DTFT doesn't really have a mathematical purpose.

The fundamental frequency of the DFT is $\frac{f_{s}}{N}$, which is equal to $\frac{1}{\tau}$ where $\tau$ is the total duration of the sampling window (not to be confused with the sample-sample period). The DFT can be viewed as a sampling of the DTFT, where the DFT sample points lie at integer multiples of the fundamental frequency, ie

\begin{equation} \frac{kf_{s}}{N},\: k \in [0,N-1]\end{equation}

If you increase the time duration of the signal without changing the sample rate, you have decreased your fundamental frequency. This means that your DFT sample points are more tightly spaced. For example, say we have a 10 Hz sample rate. If we let $\tau = 1$, we can show that we have 10 samples. This means our DFT frequencies are spaced every 1 Hz. Now if we let $\tau = 2$, we can see that we have 20 samples. This means that our fundamental frequency has now decreased to 0.5 Hz. This is not an interpolation, upsampling, extrapolation, etc. This is a legitimate increase in the frequency resolution as we have increased the region of support for our time domain function. So, with $m_{t}>1$ and $m_{f} = 1$, this is not an interpolation, but a legitimate decrease in the fundamental frequency.

Now, for the case where $m_{t} = 1$ and $m_{f} > 1$, something interesting happens. Since we have the relationship \begin{equation} \frac{1}{\tau} = \frac{f_{s}}{N}\end{equation} we find that the fundamental frequency cannot change for $m_{t}=1$, so anything that happens to $f_{s}$ must also happen to $N$. This means that the spacing of the DFT sample points hasn't changed, however, in equal time periods, the higher sample rate will accumulate more samples. This means that our DFT sample points sample a wider region of the DTFT, ie we have more frequencies available to us because we have an "upsampled" region of support in the time domain. So, this also isn't an interpolation as we haven't estimated frequencies between our DFT sample points, and it isn't extrapolation since we are not estimating the frequencies outside the original domain, but we have a legitimate computation of the values of those frequencies since we have more information available to us.

This now leads to a discussion of zero-padding and DFTs. We have to remember that when taking the DFT of a time-domain signal, it is assumed infinitely periodic. By appending zeros onto the end of $x[n]$, we artificially increase $\tau$. This means that our DFT frequencies are more tightly spaced when we sample the DTFT, however, because the region of support of $x[n]$ hasn't increased, there isn't any new information available for the DFT to use. So, it estimates the values at this new set of fundamental frequencies provided by artificially extending $\tau$, and this is an interpolation. We can also do this for the IDFT, however, the middle of the DFT output has to be padded with zeros. The easiest way to do this is to $\mathcal{F}$ $\rightarrow$ FFTshift $\rightarrow$ zero-pad each end $\rightarrow$ IFFTshift $\rightarrow$ $\mathcal{F}^{-1}$.

Now if we want to interleave zeros between samples of either $x[n]$ or $X[k]$, as I mentioned in the comments, this is theoretically the first step in upsampling. As I mentioned, upsampling in the time domain results in a replicated spectrum, which is why we need the second step of low-pass filtering. This also works the other way as well, however, as I also mentioned, if $x[n]$ is not periodic in the DFT window, you will have a discontinuity between the original and replicated copies of $x[n]$.

Lastly, with respect to extrapolation, I don't see how this makes sense in the context of the DFT. Extrapolation, as I mentioned in the comments, involves estimating values at sample points outside the region of support using values at sample points within the region of support. In the context of the DFT, anything outside the region of support is an aliased frequency, so I don't see how this would work in particular. Hopefully this answers your questions!

$\endgroup$
5
  • $\begingroup$ Hi Baddioes. I appreciate your answers, but I do have a few things to check. 1) In the second paragraph (the lines right after the 1st eq), i am not following why that is not interpolation? In the case, the spectrum of Y[K] can be seen as a spectrum interpolated from X[k]. For example (suppose $m_t = 2$), like you said, the information in X[1] now will be in Y[2] where there of course is some additional information. In other words, if we were to model relationship or mapping between $X[k]$ and $Y[k]$, we essentially need to estimate some coefficients of interpolation. $\endgroup$
    – auckydocky
    Commented Jan 17 at 23:55
  • $\begingroup$ Much the same way for the case of $m_f > 1$. Note that, I know that going or relating $X[k]$ to $Y[k]$ (importantly, their information contents or total energy would not necessarily equal!) involves some estimation, and I am referring such estimation as frequency interpolation and extrapolation. $\endgroup$
    – auckydocky
    Commented Jan 18 at 0:03
  • $\begingroup$ Interpolation and extrapolation are, as you mention, estimation concepts. Ie, you don't have knowledge of the signal at some location. When you increase the duration of your signal, you are adding additional information that you don't have to estimate. You also do this when increasing the sample rate. This is the point of the region of support discussion. With interpolation and extrapolation, you estimate without improving the region of support. But the cases you mention result in an improvement in the region of support in some way. $\endgroup$
    – Baddioes
    Commented Jan 18 at 3:46
  • $\begingroup$ "When you increase the duration of your signal, you are adding additional information that you don't have to estimate. " I don't think I am following you on this. we can simply see (x,y) as a pair of observations, and in my question we are talking about a problem of eventually estimating y from new x. And, i am calling a mapping for such estimation as interpolation and extrapolation depending on the cases above. I still do not see any reason why we should not consider the estimation as frequency interpolation or extrapolation? $\endgroup$
    – auckydocky
    Commented Jan 19 at 0:42
  • $\begingroup$ Are you estimating $y[n]$ from $x[n]$? Or are you sampling $g(t)$ to get $x[n]$, and then sampling $g(t)$ again with different parameters to get $y[n]$? Or are you wanting something else? I don't think I am following what you are actually looking for. $\endgroup$
    – Baddioes
    Commented Jan 19 at 3:38
0
$\begingroup$

To have a cleaner notation we'll call the number of samples $N_x$ and $N_y$ (instead of $N$ and $L$) and the original continuous signal $g(t)$. We also assume that there is no aliasing, i.e. $g(t)$ is bandlimited at $f_g$ and $2f_g < f_x,f_y$

Case 1: $m_t > 1$ and $m_f = 1$ (meaning that $y[n]$ was sampled for longer duration than $x[n]$ but at the same rate). In frequency domain, $Y[k]$ can be said to be an interpolated version of $X[k]$

Incorrect. That highly depends on the contents of $g(t), T_x < T_y$. In general there is no statement we can make about the relationship between $X[k]$ and $Y[k]$ unless we constrain this somehow.

An interpretation as "interpolation" is only valid if $g(t) \approx 0, T_x < t < T_y$ in which case sampling over a longer interval is essential same as appending zeros. However, for something like sine wave that's not a good assumption and appending zeros to a sine wave gets really messy.

case 2: $m_f > 1$ and $m_t = 1$ (meaning that $y[n]$ was sampled at higher rate than $x[n]$ but for the same duration) In frequency domain, $Y[k]$ can be said to be an extrapolated version of $X[k]$

Not really. While $Y[k]$ includes indeed higher frequencies than $X[k]$ the extra frequencies are all zeros. So it's not really extrapolation, it's, again, just appending zeros.

Since your initial assumptions are somewhat flawed, the actual questions don't make much sense.

$\endgroup$
5
  • $\begingroup$ Hi Hilmar, let me please clarify a few things of your (which i might have misunderstood). In the new question, I assume the signal is some real-world signal (i meant it aperiodic). With the newly edited question, i am essentially looking after a way to show that $m_t >1$ is related to frequency interpolation (more precisely, i am trying to model a function that maps $X$ to $Y$, so estimating an interpolated frequency spectrum). My question is essentially nothing to do with zero-paddings anywhere in time or frequency domain, but i only use it to exemplify an answer I am looking for. $\endgroup$
    – auckydocky
    Commented Jan 17 at 23:38
  • $\begingroup$ For the frequency extrapolation, my question is purposed exactly the same way I mentioned as in the above comment. I am trying to estimate an extrapolated frequency spectrum given $x$ and $y$ and their DFT. Here, I must need to mention again I am referring some real-world signal for which I guess it is not proper to have the bandlimit assumption but timelimited (within the sampling duration) $\endgroup$
    – auckydocky
    Commented Jan 17 at 23:46
  • $\begingroup$ @auckydocky " i am essentially looking after a way to show that $m_t>1$ is related to frequency interpolation". You can't show this because in the general case it is NOT related to frequency interpolation. You are starting with the wrong assumption. $\endgroup$
    – Hilmar
    Commented Jan 18 at 17:27
  • $\begingroup$ @auckydocky: " it is not proper to have the bandlimit assumption". If you do not assume band-limiting, that you have to deal with aliasing which will be quite different for $f_x \neq f_y$ and complicates the matter a whole lot more. $\endgroup$
    – Hilmar
    Commented Jan 18 at 17:31
  • $\begingroup$ "You can't show this because in the general case it is NOT related to frequency interpolation. You are starting with the wrong assumption. ". Can you please explain how this is NOT related to or can't be seen as frequency interpolation? $\endgroup$
    – auckydocky
    Commented Jan 19 at 0:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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