12
$\begingroup$

This question is related to this other question of mine where I ask for derivations of the discrete-time Fourier transform (DTFT) of the unit step sequence $u[n]$. During my search for derivations I found one which is amazingly simple. I first saw it on page 138 of this book by B.A. Shenoi. I also came across it on mathematics.SE in this answer.

Since the argument is short and simple I will repeat it here for convenience.

The unit step sequence can be written as $$u[n]=f[n]+\frac12\tag{1}$$ with $$f[n]=\begin{cases}\frac12,\quad n\ge 0\\-\frac12,\quad n<0\end{cases}\tag{2}$$ Obviously, $$f[n]-f[n-1]=\delta[n]\tag{3}$$ Applying the DTFT on both sided of $(3)$ gives $$F(\omega)\left(1-e^{-j\omega}\right)=1\tag{4}$$ where $F(\omega)$ is the DTFT of $f[n]$. From $(4)$ we get $$F(\omega)=\frac{1}{1-e^{-j\omega}}\tag{5}$$ From $(5)$ and $(1)$ we get for the DTFT of $u[n]$ $$U(\omega)=F(\omega)+\pi\delta(\omega)=\frac{1}{1-e^{-j\omega}}+\pi\delta(\omega),\quad -\pi\le\omega <\pi\tag{6}$$ where I've used $\text{DTFT}\{1\}=2\pi\delta(\omega)$, $-\pi\le\omega <\pi$.

Eq. $(6)$ for the DTFT of $u[n]$ is no doubt correct. However, the derivation is flawed.

The question is: find and explain the flaw in above derivation.

Please prepend your answer with the spoiler tag >!.

$\endgroup$
8
  • 1
    $\begingroup$ what disturbs me is that $f[n]$ is a finite power signal, not a finite energy signal, which is what we get when we add these two infinite energy signals together. $\endgroup$ Jan 17, 2018 at 22:22
  • $\begingroup$ also, isn't $$ \text{DTFT}\{x[n]=1\} = 2\pi \sum_{k=-\infty}^{+\infty} \delta(\omega-2k\pi) $$ ? $\endgroup$ Jan 17, 2018 at 23:17
  • $\begingroup$ Thanks guys for your responses! I've upvoted all of them, and each one results in a nice discussion on not so well-known aspects of the DTFT of strange signals (i.e., the ones not in $\ell^1$ or $\ell^2$). I can only accept one, and I'll wait a bit longer for new answers or changes in existing answers. I'll also add my own answer later on. $\endgroup$
    – Matt L.
    Jan 18, 2018 at 12:24
  • 1
    $\begingroup$ Matt, $f[n]$ is decidedly not finite energy. an infinite number of samples that square to be $\tfrac14$ do not add to be a finite number. $\endgroup$ Jan 18, 2018 at 16:48
  • 1
    $\begingroup$ @robertbristow-johnson: What do you find disturbing about that? If the signals cancel each other everywhere except for a finite number of points, then that's what we get. $\endgroup$
    – Matt L.
    Jan 19, 2018 at 9:11

9 Answers 9

10
$\begingroup$

There are infinitely many signals that make the following equality hold: $$y[n]-y[n-1]=\delta[n] \qquad (1)$$ The only thing that matters is that $y[0]-y[-1]=1$, and then the rest of the coefficients of $y$ can be determined under the restriction that Eq. $(1)$ states (i.e. the substraction of consecutive samples must be $0$ for $n\neq 0$). In other words, Eq. $(1)$ will be achieved by any signal $y[n]$ such that $$y[0]=y[-1]+1 \land y[n]=y[n-1] \ \forall n\neq0$$ Another way to see this is that any function that is basically $u[n]$ with an offset (a constant value added) will satisfy $(1)$. This explains the statement made by robert bristow-johnson in his answer: differentiators destroy this information (such as taking a derivative in continuous time destroys evidence of any constant value in the original function).

To sum up, I believe that the proof is flawed because the procedure followed could use any function of the form $u[n]+C$ with $C\in\mathbb{R}$, and this would lead to many functions having the same Fourier transform, which is indeed wrong as the Fourier transform is a bijection. Maybe the author deliberately decided to ignore anything related to DC values, conscious that in order to show that $F(\omega)$ is the DTFT of $f[n]$ he would need the accumulation property (whose most popular proof is derived from the DTFT of the unit step - ergo, a pretty circular proof). The proof is not strictly wrong, as everything it states (the formulae for $F(\omega)$ and $U(\omega)$, the decomposition of the unit step, the difference equation) is true, but it would require the accumulation property to show why $F(\omega)$ doesn't have any Dirac deltas.

$\endgroup$
3
  • $\begingroup$ You're totally on the right track! Do you have an idea how this flaw could be resolved, i.e., how to do it right? $\endgroup$
    – Matt L.
    Jan 18, 2018 at 12:59
  • $\begingroup$ @MattL. Setting an initial condition for $y[n]$ would do the trick and determine the signal univocally. That initial condition would determine the DC value of the signal $y[n]$, which appears in the DTFT as a constant multiplying a Dirac impulse (according to the accumulation property). I think that in the given proof, this works because the signal $f[n]$ has no DC value as it's symmetric around $0$, and so the DTFT is correct just in that case. But the fact that the signal has no DC should be stated, as it's fundamental, I believe. $\endgroup$
    – Tendero
    Jan 18, 2018 at 13:05
  • $\begingroup$ There are many good answers and it's hard to choose which one to accept. But this one was appreciated most by the community, and also I think that it most clearly points out the error in the derivation. Thank you all! $\endgroup$
    – Matt L.
    Jan 20, 2018 at 12:20
6
$\begingroup$

I was overwhelmed by the number of responses I got (10 answers so far!). Of course, all of them got my upvote. This was fun, thanks guys for your thoughts, comments, etc. I know that by now most of you know what the flaw is, at least the one I meant. People express things differently, and there's always room for misunderstandings, so I will try to clearly formulate what I think is the most important flaw in that derivation. I'm aware of the fact that not everybody will agree and that's fine. I'm happy to be able to discuss this sort of esoteric DSP topics with such sharp minds as y'all are! Here we go.

My first claim is that each and every equation in my question is correct. However, the derivation and motivation of some of them is totally wrong and misleading, and that "derivation" can only exist because the author knew what the result was supposed to look like.

Eq. (3) in the question ($f[n]-f[n-1]=\delta[n]$) is correct for the given sequence $f[n]$ (Eq. $(2)$ in the question), but it is clearly also correct for all sequences of the form $$f[n]=u[n]+c\tag{1}$$ with some arbitrary constant $c$. So, according to the derivation, the resulting DTFT $F(\omega)$ should be the DTFT of all sequences of the form $(1)$, regardless of the value of the constant $c$. That's of course non-sense because the DTFT is unique. Specifically, using that very "proof" I could "show" that $F(\omega)$ as given in Eq. $(5)$ of my question (or Eq. $(3)$ below) is actually the DTFT of $u[n]$ that we're looking for. So why bother splitting up $u[n]$ as in Eq. $(1)$ of the question?

However, it is true that the DTFTs of all sequences $(1)$ do satisfy Eq. $(4)$ in the question (repeated here for convenience): $$F(\omega)\left(1-e^{-j\omega}\right)=1\tag{2}$$ But now comes the actual mathematical flaw: From Eq. $(2)$ it is incorrect to conclude $$F(\omega)=\frac{1}{1-e^{-j\omega}}\tag{3}$$ Eq. $(3)$ is only one of infinitely many possible solutions of $(2)$, and it conveniently happens to be the one needed by the author to arrive at the correct end result. Eq. $(3)$ is the DTFT of $f[n]$ in $(1)$ with $c=-\frac12$, but from the given derivation there is no way to know that.

So how can we avoid that mathematical error and use $(2)$ to derive the DTFTs of $all$ sequences $(1)$, with any constant $c$? The correct conclusion from $(2)$ is $$F(\omega)=\frac{1}{1-e^{-j\omega}}+\alpha\delta(\omega)\tag{4}$$ with some yet undetermined constant $\alpha$. Plugging $(4)$ into the left-hand side of $(2)$ gives $$1+\alpha (1-e^{-j\omega})\delta(\omega)=1+\alpha (1-e^{-j\omega})\Big{|}_{\omega=0}\cdot\delta(\omega)=1+0\cdot\delta(\omega)=1$$ So all functions $F(\omega)$ given by $(4)$ satisfy $(2)$, as required.

The constant $\alpha$ in $(4)$ can be determined from the value of $f[n]$ at $n=0$: $$f[0]=1+c=\frac{1}{2\pi}\int_{-\pi}^{\pi}F(\omega)d\omega=\frac{1}{2\pi}\int_{-\pi}^{\pi}\frac{d\omega}{1-e^{-j\omega}}+\frac{\alpha}{2\pi}\tag{6}$$ It can be shown, and also WolframAlpha agrees, that the Cauchy principal value of the integral in $(6)$ is $$PV\int_{-\pi}^{\pi}\frac{d\omega}{1-e^{-j\omega}}=\pi\tag{7}$$ From $(6)$ and $(7)$ we get $$\alpha=\pi (1+2c)\tag{8}$$ So for $c=-\frac12$ we get $\alpha=0$ (which corresponds to the original sequence $f[n]$ as used by the author of the proof), and for $c=0$ (i.e., for $f[n]=u[n]$) we have $\alpha=\pi$, which finally gives us the desired DTFT of $u[n]$: $$U(\omega)=\frac{1}{1-e^{-j\omega}}+\pi\delta(\omega)\tag{9}$$

$\endgroup$
3
  • $\begingroup$ "all functions $F(\omega)$ given by (4) satisfy (2)", but must we prove that "all functions $F(\omega)$ satisfy (2) have the form (4)" ? $\endgroup$
    – AlexTP
    Jan 20, 2018 at 12:29
  • 1
    $\begingroup$ @AlexTP: So you mean functions of the form $(4)$ could only be a subset of functions satisfying $(2)$? That's a valid point. But I think it's pretty clear that there can't be any other functions, because it's only at $\omega=0$ where we get the problem, so we need functions that have an additional contribution at $\omega=0$ which disappears when multiplied by $(1-e^{-j\omega})$. Such functions (actually distributions) are the Dirac delta impulse and its derivatives. However, the derivatives do not disappear when multiplied by $(1-e^{-j\omega})$, so it's only the Dirac delta impulse that's left $\endgroup$
    – Matt L.
    Jan 20, 2018 at 12:37
  • $\begingroup$ I am not really sure that there can't be any function other than Dirac delta impulse (and its derivatives) that has this property. But it is ok, your answer is well-written. I upvote. Thanks. $\endgroup$
    – AlexTP
    Jan 25, 2018 at 22:47
4
$\begingroup$

if you allow me to divide by zero, i can prove to you that $1=2$. when you say $$F(\omega)\left(1-e^{-j\omega}\right)=1$$ there is a problem about multiplying something by zero (when $\omega=2k\pi \text{ for } k \in \mathbb{Z}$) and expecting the product to equal one.

$\endgroup$
8
  • 3
    $\begingroup$ moral of the story: differentiators destroy information. a differentiator doesn't know the difference between $u[n]$ and $u[n]-\tfrac{1}{2}$. don't try dividing by zero to get that lost information. $\endgroup$ Jan 17, 2018 at 22:37
  • $\begingroup$ so should the author state that $w \neq 2\pi k$ to correct the flaw? $\endgroup$
    – Fat32
    Jan 17, 2018 at 22:43
  • $\begingroup$ well, the DTFT of $\delta[n]$ is equal to 1 for any $\omega$, even when $\omega=2k\pi$. $\endgroup$ Jan 17, 2018 at 22:50
  • $\begingroup$ why $\delta[n]$ ?... it's the domain of $1-e^{-j w}$ which restricts that of $F(w)$ ? $\endgroup$
    – Fat32
    Jan 17, 2018 at 22:55
  • $\begingroup$ because when Matt says $$f[n]-f[n-1]=\delta[n]$$ and says to integrate both sides to get $u[n]$ (which is what Matt says essentially in Eq.5), then we have a sorta "multiply and divide by the same quantity trick to get 1". but sometimes he is multiplying and dividing by zero. multiplying by zero destroys information. dividing that by zero will not get the information back. $\endgroup$ Jan 17, 2018 at 23:10
3
$\begingroup$

The Equation (4) should be written as $$\lim_{N \to \infty} \sum_{n=-N}^{n=N}f[n]e^{-j\omega n} (1-e^{-j\omega n})+(e^{j\omega N}f[N]+e^{-j\omega N}f[-N])e^{-j\omega}=1$$ For $f[n]=u[n]$, $$\lim_{N \to \infty} \sum_{n=-N}^{n=N}f[n]e^{-j\omega n} (1-e^{-j\omega n})+e^{j\omega N}e^{-j\omega}=1$$ that is not (5). I don't know how to fix the proof without avoiding (3).

$\endgroup$
11
  • 1
    $\begingroup$ someone might argue that $F(\omega)$ exists when $\omega \ne 2 k \pi$ for integer $k$. $\endgroup$ Jan 17, 2018 at 22:46
  • $\begingroup$ @robertbristow-johnson Thanks for editting. I mean that $F(\omega)$ does not exist not because $\omega = 2k\pi$ but because $\sum_{n=1}^\infty \sin(\omega n)$ does not converge for every $\omega$. For $\omega = 2k\pi$, it must be interpreted as a Cauchy principal value even for the correct formula of $U(\omega)$ $\endgroup$
    – AlexTP
    Jan 17, 2018 at 22:57
  • $\begingroup$ @AlexTP Why is divergence of that summation reason to say that $F(\omega)$ doesn't exist? Many signals are such that their "summation DTFTs" diverge, but they have a DTFT defined nevertheless (in terms of Dirac deltas). I'm not saying the reasoning its wrong, I'm just trying to understand (I'm not too familiar with distribution theory and that). $\endgroup$
    – Tendero
    Jan 18, 2018 at 0:16
  • $\begingroup$ You're right that the sums do not converge in the conventional sense, but nevertheless, the DTFTs exist in a distributional sense. After all, the same argument would hold for the DTFT of $u[n]$, which also exists in that sense. So there's another flaw which is less mathematically complex than the divergence problem, which we've kind of gotten used to. $\endgroup$
    – Matt L.
    Jan 18, 2018 at 7:12
  • 2
    $\begingroup$ @MattL. I dont know if it is obvious but I dont see the difference between $u[n]$ and $f[n]$ because we also have $u[n] - u[n-1] = \delta[n]$ ! $\endgroup$
    – AlexTP
    Jan 18, 2018 at 12:17
3
$\begingroup$

I think I have figured out the best way to express the flaw in this proof. So I am going to give it another stab.

The choice of $\frac{1}{2}$ in (1) is arbitrary. Let's replace it with $x$. Follow the proof through, and end up with:

$$ U(\omega)=\frac{1}{1-e^{-j\omega}}+2\pi x \delta(\omega) $$

There is nothing in the proof which constrains $x$ to be $\frac{1}{2}$, it can take any finite value and the proof works the same.

Furthermore, if you take the step I did in my last answer and find (4) is expressed as

$$ F( \omega )(1 - e^{-j\omega} ) = 1 + 2\pi x (1 - e^{-j\omega} ) \delta(\omega) $$

Followed by including it in (5) and (6) you get:

$$ U(\omega)=\frac{1}{1-e^{-j\omega}}+ 4\pi x \delta(\omega) $$

Which, as I pointed out earlier, is inconsistent with the definition to get there.

This proof fails to show that $ x = \frac{1}{2}$, and it seems to indicate that for any defined x, inconsistent results will follow. Therefore I go back to the statement in my first answer that the value of $ \pi $ for the coefficient of $ \delta(\omega) $ is a definitional act, not an mathematical truism.

Perhaps there is some other situation which makes $x=\frac{1}{2}$ the correct value, but this proof doesn't provide it.

Ced

$\endgroup$
2
$\begingroup$

The flaw follows the word "Obviously", if that is supposed to be the Dirac Delta Function.

Here is the draft of an answer for your other question that I never posted:

---------------------------------------------------------------

I don't think a proof is possible. This may be a case of a "functional definition" having desired properties.

$$ X_{2\pi} \left(\omega\right) = \sum\limits_{n=-\infty}^{+\infty} x[n] e^{-j \omega n} $$ $$ U = \sum\limits_{n=0}^{+\infty} e^{-j \omega n} $$ $$ U = \lim_{ N \to \infty } \sum\limits_{n=0}^{N-1} e^{-j \omega n} $$ $$ U = \lim_{ N \to \infty } \left[ \frac{ 1 - e^{-j \omega N} }{ 1 - e^{-j \omega } } \right] $$ $$ U = \frac{ 1 }{ 1 - e^{-j \omega } } - \lim_{ N \to \infty } \left[ \frac{ e^{-j \omega N} }{ 1 - e^{-j \omega } } \right] $$ Looking at the last limit value. For $ \omega = 0 $ it is clear that it acts like a Dirac Delta. Why the coefficient should be $ \pi $, I don't know. It may have to do with the area of the unit circle. When $ \omega \neq 0 $, the denominator can be factored out of the limit and the numerator just jumps along the unit circle and never reaches a limit. Setting it to zero is a definitional act.

Proving the definition works in a desirable way is a different matter.

The page 138 proof is wrong (at least) because:

$$ \delta(t) = \lim_{ a \to 0 } \frac{1}{2a} \left[ u(t + a) - u(t - a) \right] = \frac{du}{dt}$$ Which is not similar in any way to $ \delta(n) = u_2(n) - u_2(n-1) $ as they define it.

Interesting situation, I hope this helps. I am looking forward to what you have to say.

Ced

$\endgroup$
2
  • $\begingroup$ Thanks for your answer! But note that we're talking about discrete-time sequences here, not about the Dirac delta impulse. In discrete-time, $\delta[n]$ equals zero everywhere, except for $n=0$ where it is $1$. So no ugly stuff as in continuous-time. So Eq. (3) in my question is actually correct (in discrete time!). $\endgroup$
    – Matt L.
    Jan 18, 2018 at 7:26
  • $\begingroup$ Cedron, I think this equation: $$U = \frac{ 1 }{ 1 - e^{-j \omega } } - \lim_{ N \to \infty } \left[ \frac{ e^{-j \omega N} }{ 1 - e^{-j \omega } } \right]$$ may be of interest in this other question of @MattL.. Maybe you should consider giving it some more thought and posting it there if you want to. $\endgroup$
    – Tendero
    Jan 18, 2018 at 12:32
1
$\begingroup$

This is in response to the comments in my first answer. Because of the spoiler cloaking I am posting it as a separate answer.

I was going to post my other answer to the other question, but I didn't due to my lack of experience in this area. I posted it yesterday, deleted it, then undeleted, then figured out how to employ spoiler tags.

Clearly the $\delta$ function defined in the problem is not the Dirac Delta function. I looked up DTFT in Wikipedia and the DTFT for the Dirac Delta function is one. I will call the $\delta$ of the problem $\delta_p$.

$$ \delta_p[n] = f[n] - f[n-1] = u[n] - u[n-1] $$

Taking the DTFT of the left and right parts. I'm not sure I have the notations right, but the math should be clear. Using the definition that is being proved.

$$ F_p( \omega ) = F_u( \omega ) - F_u( \omega ) e^{-j\omega} $$

$$ F_p( \omega ) = \left[ \frac{1}{1-e^{-j\omega}}+\pi\delta(\omega) \right] - \left[ \frac{e^{-j\omega}}{1-e^{-j\omega}}+ ( \pi e^{-j\omega} ) \delta(\omega) \right] $$

$$ F_p( \omega ) = \frac{1-e^{-j\omega}}{1-e^{-j\omega}} + \pi (1 - e^{-j\omega} )\delta(\omega) $$

$$ F_p( \omega ) = 1 + \pi (1 - e^{-j\omega} ) \delta(\omega) \neq 1 $$

Thus the RHS of (4) is incorrect except when $\omega = 2k\pi $. [Edit: Doh, it's the Dirac Delta, so this statement is wrong. I guess it should be correct except "undefined" at $\omega = 2k\pi $. Real Analysis was my least favorite math. I am leaving this alone now.]

Ced

==============================

Followup:

It is clear that the DTFT of $\delta_p$ should be 1 when it is plugged into the definition of a DTFT. Therefore, since I got a different answer when using the definition to be proved means that the definition to be proved is not correct (in a mathematical sense). Furthermore, if you carry the correction through to the end of the proof you arrive at a different definition. Assuming the assertion to be true is used to prove that it is false.

$\endgroup$
1
  • $\begingroup$ You've actually shown that $F_p(\omega)=1$ because the term $(1-e^{-j\omega})\delta(\omega)$ equals zero. That's the case because for any function $f(\omega)$ that is continuous at $\omega=0$ you have $f(\omega)\delta(\omega)=f(0)\delta(\omega)$, and if $f(0)=0$ (which is the case here), the whole term disappears. $\endgroup$
    – Matt L.
    Jan 19, 2018 at 9:13
1
$\begingroup$

To me, a first flaw appears between (3) and (4): this is an instance of the classical careless integral/infinite sum splitting. Conditions are required to allow the equation: $$ \sum (a[n] - b[n])c_\omega[n] = \sum a[n]c_\omega[n]- \sum b[n]c_\omega[n] $$ Standard $\ell_1$ or $\ell_2$ conditions might not be sharp enough. This could be related here, due to the form $f[n]-f[n-1]$, to the Fubini derivation theorem, or: When can we exchange infinite sum and discrete derivative? Ways around could revolve around monotony or Cesaro-like sums, but I shall think about this longer.

$\endgroup$
1
$\begingroup$

so Matt,

i dunno why you don't think it's problematic comparing power signals to energy signals, but suppose we modify the definition of $f[n]$ slightly:

$$ f[n] \triangleq \begin{cases} \ \tfrac12 e^{-\alpha n} \qquad & n \ge 0 \\ -\tfrac12 e^{ \alpha n} \qquad & n < 0 \\ \end{cases} $$

for some $\alpha > 0$.

now we have finite energy signals and the DTFTs should all be comparable.

$$\begin{align} f[n]-f[n-1] &= \begin{cases} \tfrac12 (e^{-\alpha n} - e^{-\alpha (n-1)}) \qquad & n > 0 \\ \tfrac12 (1 + e^{ -\alpha })\qquad & n = 0 \\ -\tfrac12 (e^{\alpha n} - e^{\alpha(n-1)})\qquad & n < 0 \\ \end{cases} \\ \\ \\ &= \begin{cases} \tfrac12 (1 - e^{\alpha}) e^{-\alpha n} \qquad & n > 0 \\ \tfrac12 (1 + e^{ -\alpha }) \qquad & n = 0 \\ \tfrac12 (e^{-\alpha} - 1)e^{\alpha n} \qquad & n < 0 \\ \end{cases} \\ \end{align}$$

i wonder what the DTFTs are? and then what happens when we let $\alpha \to 0$ ? i think there is still the problem of differentiators destroying information (and the corresponding destruction of information by multiplying by 0 in the frequency domain) that is a problem. but maybe we can lose the problem of comparing signal classes that don't share the same Hilbert space.

but, alas, it's nearly 2 a.m. and i ain't gonna deal with it now.

$\endgroup$
1
  • $\begingroup$ That $\alpha$ thing is good, and it's one option to compute the DTFT of those non-decaying signals, by taking the limit $\alpha\rightarrow 0$. Try it, and I'm sure you'll succeed, but it's painful. There are easier ways to get the same result. The given proof can actually be modified such that it works IMHO (see my answer). $\endgroup$
    – Matt L.
    Jan 20, 2018 at 12:18

Your Answer

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

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