Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Can someone explain to me why y[n] has a triangular shape? From what I have found, there is a specific range $n_0$ where y[n] is triangular. But right now I have no clue where to start.

enter image description here

$^2$ Search in a table of Fourier transform properties

share|improve this question
    
What's $u$?${}$ –  J. M. May 16 '11 at 0:29
    
The only explanation I can think is you are doing something wrong. The inverse transform of the direct transform is the original sequence. –  leonbloy May 16 '11 at 0:47
    
u should be the step function. –  madmax May 16 '11 at 7:57
    
@leonbloy Yes, i was thinking the same but the question is like that: Considering the properties of the DFT, explain why the sequence y[n] has in general a triangular shape. –  madmax May 16 '11 at 8:02
1  
@Raskolnikov added the question as it is –  madmax May 16 '11 at 9:52
show 2 more comments

1 Answer 1

up vote 1 down vote accepted

A simple way to see this: taking the square of a Fourier transform is just multiplying its Fourier transform with itself. Now, taking the inverse transform of a product of two Fourier transforms is the same as convolving the two original functions. Here you are convolving a step function with itself. Now, think about how convolutions work and it should be evident that the result is a triangle function. But if you don't see it, just work out the convolution product of two step functions.

EDIT: Here's a detailed worked out solution. Using the definition from wikipedia for the DFT:

$$\text{DFT}(x[n])=\sum_{n=0}^{N-1}(u[n]-u[n-n_0])e^{-\frac{2\pi i}{N}k n} = \sum_{n=0}^{n_0-1}e^{-\frac{2\pi i}{N}k n} \; .$$

If you multiply this DFT with itself, you get the following sum

$$(\text{DFT}(x[n]))^2= \left(\sum_{n=0}^{n_0-1}e^{-\frac{2\pi i}{N}k n}\right)\left(\sum_{m=0}^{n_0-1}e^{-\frac{2\pi i}{N}k m}\right) = \sum_{n=0}^{n_0-1}\sum_{m=0}^{n_0-1}e^{-\frac{2\pi i}{N}k (m+n)} \; .$$

With a change of variables $t=m+n$, you can now write this as

$$(\text{DFT}(x[n]))^2 = \sum_{t=0}^{2(n_0-1)} z[t] e^{-\frac{2\pi i}{N}k t} \; .$$

where $z[t]$ is

$$z[t]=\begin{cases}1, \text{ if } t=0=0+0,\\ 2, \text{ if } t=1=1+0=0+1,\\ 3, \text{ if } t=2=2+0=1+1=0+2,\\ \ldots\\ 2, \text{ if } t=2n_0-3=n_0-1+n-0-2=n_0-2+n_0-1,\\ 1, \text{ if } t=2n_0-2=n_0-1+n_0-1,\\ \end{cases}$$

which is a triangular function. Note however that if $2(n_0-1)\geq N$, then because of periodicity, $z[t]\neq y[t]$. You'll have to add the $z[t]$'s corresponding to a same frequency to obtain the correct expression for $y[t]$, since $y[t]$ is only defined over the range $[0,N-1]$ just like $x[n]$.

So the range they are talking about in the question is $0\leq2(n_0-1)<N$.

share|improve this answer
1  
The breadth of the interval over which the function is triangular should be twice $n_0$. So, on the interval $[-n_0,n_0]$. Outside of this interval, the convolution product will be zero since the step function and the shifted step function will not overlap. –  Raskolnikov May 20 '11 at 19:02
1  
About the zeros, they might have meant the values at the extremities of the interval, which are zero (if $n_0<N/2$). If you choose to work on the open interval $]-n_0,n_0[$, you don't include them. To your second question, I'd say yes. Also, since you are working with the discrete transform, your interval is capped off at $0$ and $N$, So if $n_0>N/2$, I think you'll get a triangle as well, but it will not start at height $0$. If $n_0=N$ You'll get a constant function. –  Raskolnikov May 21 '11 at 11:30
1  
@madmax: I'm kind of working with a continuous Fourier transform in my mind, so I forget about the differing details in the case of a DFT, but the principles are really the same. I'll add a detailed calculation to make thing clear. –  Raskolnikov May 22 '11 at 10:24
1  
You got your $x$ wrong. When $N=25$ and $n_0=22$, the last three values at $22, 23 \text{ and } 24$ are $0$, all the others are $1$. –  Raskolnikov May 22 '11 at 21:14
1  
First, following the definition in the OP, your range should be n=0:N-1. Second, there is indeed always a "triangle", but the base level is not always 0, and I suppose the question doesn't count these as real "triangles". But I have to say that is a bit silly. I didn't write the question however. –  Raskolnikov May 23 '11 at 8:49
show 8 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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