9
$\begingroup$

From text books we know that the DTFT of $u[n]$ is given by

$$U(\omega)=\pi\delta(\omega)+\frac{1}{1-e^{-j\omega}},\qquad -\pi\le\omega <\pi\tag{1}$$

However, I haven't seen a DSP textbook that at least pretends to give a more or less sound derivation of $(1)$.

Proakis [1] derives the right half of the right-hand side of $(1)$ by setting $z=e^{j\omega}$ in the $\mathcal{Z}$-transform of $u[n]$, and says that it is valid except for $\omega=2\pi k$ (which is of course correct). He then states that at the pole of the $\mathcal{Z}$-transform we have to add a delta impulse with an area of $\pi$, but that appears more like a recipe to me than anything else.

Oppenheim and Schafer [2] mention in this context

Although it is not completely straightforward to show, this sequence can be represented by the following Fourier transform:

which is followed by a formula equivalent to $(1)$. Unfortunately, they didn't take the trouble to show us that "not completely straightforward" proof.

A book that I actually didn't know, but which I found when looking for a proof of $(1)$ is Introduction to Digital Signal Processing and Filter Design by B.A. Shenoi. On page 138 there's a "derivation" of $(1)$, but unfortunately it is wrong. I asked a "DSP-puzzle" question to have people show what is wrong with that proof.]

So my question is:

Can anybody provide a proof/derivation of $(1)$ that is sound or even rigorous while being accessible for mathematically inclined engineers? It doesn't matter if it's just copied from a book. I think it would be good to have it on this site anyway.

Note that even on math.SE almost nothing relevant is to be found: this question has no answers, and that one has two answers, one of which is wrong (identical to Shenoi's argument), and the other one uses the "accumulation property", which I would be happy with, but then one needs to proof that property, which puts you back to the start (because both proofs basically prove the same thing).

As a final note, I did come up with something like a proof (well, I'm an engineer), and I will also post it as an answer some days from now, but I would be happy to collect other published or unpublished proofs that are simple and elegant, and, most importantly, that are accessible for DSP engineers.

PS: I do not doubt the validity of $(1)$, I would just like to see one or several relatively straightforward proofs.


[1] Proakis, J.G. and D.G. Manolakis, Digital Signal Processing: Principles, Algorithms, and Applications, 3rd edition, Section 4.2.8

[2] Oppenheim, A.V. and R.W. Schafer, Discrete-Time Signal Processing, 2nd edition, p. 54.



Inspired by a comment by Marcus Müller, I'd like to show that $U(\omega)$ as given by Eq. $(1)$ satisfies the requirement

$$u[n]=u^2[n]\rightarrow U(\omega)=\frac{1}{2\pi}(U\star U)(\omega)$$

If $U(\omega)$ is the DTFT of $u[n]$, then

$$V(\omega)=\frac{1}{1-e^{-j\omega}}$$

must be the DTFT of

$$v[n]=\frac12\text{sign}[n]$$

(where we define $\text{sign}[0]=1$), because

$$V(\omega)=U(\omega)-\pi\delta(\omega)\Longleftrightarrow u[n]-\frac12=\frac12\text{sign}[n]$$

So we have

$$\frac{1}{2\pi}(V\star V)(\omega)\Longleftrightarrow \left(\frac12\text{sign}[n]\right)^2=\frac14$$

from which it follows that

$$\frac{1}{2\pi}(V\star V)(\omega)=\text{DTFT}\left\{\frac14\right\}=\frac{\pi}{2}\delta(\omega)$$

With this we get

$$\begin{align}\frac{1}{2\pi}(U\star U)(\omega)&=\frac{1}{2\pi}\left[(\pi\delta(\omega)+V(\omega))\star (\pi\delta(\omega)+V(\omega))\right]\\&=\frac{1}{2\pi}\left[\pi^2\delta(\omega)+2\pi V(\omega)+(V\star V)(\omega)\right]\\&=\frac{\pi}{2}\delta(\omega)+V(\omega)+\frac{\pi}{2}\delta(\omega)\\&=U(\omega)\qquad\text{q.e.d.}\end{align}$$

$\endgroup$
  • $\begingroup$ waaah. Don't break my world. Doubt in that formula introduces a realm of chaos. For example, $u^2(t) = u(t)$, and hence (with a cont. FT definition prefactor depending constant $c$), $$\begin{align}\text{DTFT}(u^2)(\omega) &=c\,\cdot\, U(\omega)*U(\omega) \\&=c\pi U(\omega)+ \frac{c}{1+e^{-j\omega}}*U(\omega)\\&=c\pi \left(\pi\delta(\omega)+\frac{1}{1-e^{-j\omega}}\right)+\frac{c\pi}{1+e^{-j\omega}}+c\frac{1}{1+e^{-j\omega}}*\frac{1}{1+e^{-j\omega}}\\&=c\pi^2\delta(\omega)+\frac{2c\pi}{1+e^{-j\omega}} + c\frac{1}{1+e^{-j\omega}}*\frac{1}{1+e^{-j\omega}}\\&\overset{\text{magic?}}=U\end{align}$$ $\endgroup$ – Marcus Müller Jan 16 '18 at 13:29
  • $\begingroup$ @MarcusMüller: No doubt about that formula, it's correct. The question is just how to show it in a way that a simple minded engineer can understand. And $u^2[n]=u[n]$ works out for the given DTFT, no problem. $\endgroup$ – Matt L. Jan 16 '18 at 13:33
  • $\begingroup$ I consider myself very simple-minded, and that means I worry when things don't feel "safe" when I can't see how they are derived. $\endgroup$ – Marcus Müller Jan 16 '18 at 13:47
  • 1
    $\begingroup$ I see that what you're after is not to prove whether the equation is correct or not, but rather it's to rigorously and directly derive $U(w)$ from first principles and definition of DTFT. Then whenever one wants to make a rigorous proof involving impulses then I guess one should better refer to the cited books from generalized function theory: Lighthill-1958 is cited in Opp&Schafer for a discussion of impulse function and its use in Fourier transforms. All other proofs will inevitably rely on the proofs made on those references and will be insufficient to replace a rigorous proof. $\endgroup$ – Fat32 Jan 16 '18 at 16:07
  • 1
    $\begingroup$ @Fat32: That's a valid viewpoint. I think, however, that a reasonably sound derivation is possible if we accept basic transforms such as $\text{DTFT}\{1\}=2\pi\delta(\omega)$, and if we're content to define integrals by their Cauchy principal value. $\endgroup$ – Matt L. Jan 16 '18 at 17:05
3
+50
$\begingroup$

Cedron Dawg posted an interesting initial point in this answer. It begins with these steps:

$$ \begin{align} U(\omega) &= \sum\limits_{n=0}^{+\infty} e^{-j \omega n} \\ &= \lim_{ N \to \infty } \sum\limits_{n=0}^{N-1} e^{-j \omega n}\\ &= \lim_{ N \to \infty } \left[ \frac{ 1 - e^{-j \omega N} }{ 1 - e^{-j \omega } } \right] \\ &= \frac{ 1 }{ 1 - e^{-j \omega } } - \lim_{ N \to \infty } \left[ \frac{ e^{-j \omega N} }{ 1 - e^{-j \omega } } \right] \end{align} $$

It turns out the term inside the limit can be expanded as follows:

$$\begin{aligned} \frac{ e^{-j \omega N} }{ 1 - e^{-j \omega } } ={} &\frac{1}{\sin^2(\omega)+(1-\cos(\omega))^2} \cdot \\ &\left[-\cos(\omega)\cos(N\omega)+\cos(N\omega)-\sin(\omega)\sin(N\omega)+ \\ j(-\sin(\omega)\cos(N\omega)+\cos(\omega)\sin(\omega)-\sin(N\omega))\right] \end{aligned} $$

The common factor outside the brackets can be expressed as:

$$\frac{1}{\sin^2(\omega)+(1-\cos(\omega))^2} = \frac{1}{4\sin^2(\omega/2)}$$

The real part inside the brackets also equals:

$$-\cos(\omega)\cos(N\omega)+\cos(N\omega)-\sin(\omega)\sin(N\omega)= 2\sin(\omega/2)\sin[\omega(-N+1/2)]$$

On the other hand, the imaginary part can be rewritten as:

$$-\sin(\omega)\cos(N\omega)+\cos(\omega)\sin(\omega)-\sin(N\omega)=-2\sin(\omega/2)\cos[\omega(-N+1/2)]$$

Rewritting the original term we get that:

$$\begin{align} \frac{ e^{-j \omega N} }{ 1 - e^{-j \omega } } &=\frac{2\sin\left(\frac \omega 2\right)}{4\sin^2\left(\frac \omega 2\right) } \left( \sin[\omega(-N+1/2)] - j\cos[\omega(-N+1/2)]\right) \\ &=-\frac{\sin[\omega(M+1/2)]}{2\sin\left(\frac \omega 2\right)} - j\frac{\cos[\omega(M+1/2)]}{2\sin\left(\frac \omega 2\right)} \end{align} $$

where I used $M=N-1$ and the limit stays unaffected as $M\to \infty$ as well.

According to the 7th definition in this site:

$$\lim_{M\to \infty} -\frac{1}{2\sin(\omega/2)}\sin[\omega(M+1/2)] = -\pi \delta(\omega)$$

So far we have that:

$$\lim_{ M \to \infty } \frac{ e^{-j \omega (M+1)} }{ 1 - e^{-j \omega } } =-\pi\delta(\omega) -j\lim_{M\to \infty} \frac{\cos[\omega(M+1/2)]}{2\sin(\omega/2)} $$

If we could prove that the second term on the right of the equality is $0$ in some sense, then we are done. I asked it at math.SE and, indeed, that sequence of functions tends to the zero distribution. So, we have that:

$$ \begin{align} U(\omega) &= \frac{ 1 }{ 1 - e^{-j \omega } } - \lim_{ N \to \infty } \left[ \frac{ e^{-j \omega N} }{ 1 - e^{-j \omega } } \right] \\ &=\frac{ 1 }{ 1 - e^{-j \omega } }+\pi\delta(\omega) +j\lim_{M\to \infty} \frac{\cos[\omega(M+1/2)]}{2\sin(\omega/2)} \\ & =\frac{ 1 }{ 1 - e^{-j \omega } }+\pi\delta(\omega) \end{align} $$

$\endgroup$
  • $\begingroup$ This is very nice! I checked it and everything seems to be correct, so that imaginary part must tend to zero in some sense. I'll think about it for a bit. $\endgroup$ – Matt L. Jan 19 '18 at 10:37
  • $\begingroup$ @MattL. Let me know if you are able to make any progress! $\endgroup$ – Tendero Jan 19 '18 at 17:11
  • $\begingroup$ @MattL. The proof is finally complete! $\endgroup$ – Tendero Jan 23 '18 at 2:43
  • $\begingroup$ Good work! I had figured out that the cosine term would tend to zero due to the Riemann-Lebesgue lemma, but my problem was the case $\omega=0$. Because the very first formula is based on the geometric sum, which is only valid for $\omega\neq 0$. It all somehow works out after all, but that's still a minor flaw. I have another derivation that does not split out the term $1/(1-e^{-j\omega})$, in which the case $\omega=0$ is handled with a bit more care, but it's still an "engineer's proof". I might post it when I have more time. $\endgroup$ – Matt L. Jan 23 '18 at 8:11
2
$\begingroup$

I'll provide two relatively simple proofs that do not require any knowledge of distribution theory. For a proof that computes the DTFT by a limit process using results from distribution theory, see this answer by Tendero.

I will only mention (and not elaborate on) the first proof here, because I've posted it as an answer to this question, the purpose of which was to show that a certain published proof is faulty.

The other proof goes as follows. Let's first write down the even part of the unit step sequence $u[n]$:

$$u_e[n]=\frac12\left(u[n]+u[-n]\right)=\frac12+\frac12\delta[n]\tag{1}$$

The DTFT of $(1)$ is

$$\text{DTFT}\{u_e[n]\}=\pi\delta(\omega)+\frac12\tag{2}$$

which equals the real part of the DTFT of $u[n]$:

$$U_R(\omega)=\text{Re}\{U(\omega)\}=\pi\delta(\omega)+\frac12\tag{3}$$

Since $u[n]$ is a real-valued sequence we're done because the real and imaginary parts of $U(\omega)$ are related via the Hilbert transform, and, consequently, $U_R(\omega)$ uniquely determines $U(\omega)$. However, in most DSP texts, these Hilbert transform relations are derived from the equation $h[n]=h[n]u[n]$ (which is valid for any causal sequence $h[n]$), from which it follows that $H(\omega)=\frac{1}{2\pi}(H\star U)(\omega)$. So in order to show the Hilbert transform relation between the real and imaginary parts of the DTFT we need the DTFT of $u[n]$, which we actually want to derive here. So the proof becomes circular. That's why we'll choose a different way to derive the imaginary part of $U(\omega)$.

For deriving $U_I(\omega)=\text{Im}\{U(\omega)\}$ we write the odd part of $u[n]$ as follows:

$$u_o[n]=\frac12\left(u[n]-u[-n]\right)=u[n-1]-\frac12+\frac12\delta[n]\tag{4}$$

Taking the DTFT of $(4)$ gives

$$\begin{align}jU_I(\omega)&=e^{-j\omega}U(\omega)-\pi\delta(\omega)+\frac12\\&=e^{-j\omega}(U_R(\omega)+jU_I(\omega))-\pi\delta(\omega)+\frac12\\&=e^{-j\omega}\left(\pi\delta(\omega)+\frac12\right)+e^{-j\omega}jU_I(\omega)-\pi\delta(\omega)+\frac12\\&=\frac12(1+e^{-j\omega})+e^{-j\omega}jU_I(\omega)\tag{5}\end{align}$$

where I've used $(3)$. Eq. $(5)$ can be written as

$$jU_I(\omega)(1-e^{-j\omega})=\frac12(1+e^{-j\omega})\tag{6}$$

The correct conclusion from $(6)$ is (see this answer for more details)

$$jU_I(\omega)=\frac12\frac{1+e^{-j\omega}}{1-e^{-j\omega}}+c\delta(\omega)\tag{7}$$

But since we know that $U_I(\omega)$ must be an odd function of $\omega$ (because $u[n]$ is real-valued), we can immediately conclude that $c=0$. Hence, from $(3)$ and $(7)$ we finally get

$$\begin{align}U(\omega)&=U_R(\omega)+jU_I(\omega)\\&=\pi\delta(\omega)+\frac12+\frac12\frac{1+e^{-j\omega}}{1-e^{-j\omega}}\\&=\pi\delta(\omega)+\frac12\left( 1+\frac{1+e^{-j\omega}}{1-e^{-j\omega}}\right)\\&=\pi\delta(\omega)+\frac{1}{1-e^{-j\omega}}\tag{8}\end{align}$$

$\endgroup$

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.