1
$\begingroup$

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

  • 0
    What's $u$?${}$2011-05-16
  • 0
    The only explanation I can think is you are doing something wrong. The inverse transform of the direct transform is the original sequence.2011-05-16
  • 0
    u should be the step function.2011-05-16
  • 0
    @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.2011-05-16
  • 0
    Are you certain there is no integration/summation that has to be performed in between the transforms?2011-05-16
  • 1
    @Raskolnikov added the question as it is2011-05-16
  • 0
    OK, it's clearer now. The DFT is squared before the inverse is taken.2011-05-16

1 Answers 1

1

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)

  • 0
    I have a problem finding the range $n_0$ where $y[n]$ is triangular. I mean, as long as x is not $u[n]-u[n]$, y is triangular in my oppinion. I found a site where it is easy to simulate: http://www.jhu.edu/signals/discreteconv2/index.html2011-05-20
  • 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.2011-05-20
  • 0
    Ah ok, so $[-n_0,n_0]$ is my range. But the question says "with possibly additional zeros". Well, in my oppinion there can't be any zeros because with this interval u have only values != zero.2011-05-21
  • 0
    And another question is, what would be a value of $n_0$ not complying with the triangular condition? Only $n_0 = 0$ ? Then i would have just one value non-zero. And that is not triangular in my oppinion.2011-05-21
  • 1
    About the zeros, they might have meant the values at the extremities of the interval, which are zero (if $n_0$]-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. – 2011-05-21
  • 0
    I think i forgot this statement: $0 < n_0 < N$, so i can't take $n_0=0$ and also not $n_0= N$.2011-05-22
  • 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.2011-05-22
  • 0
    Well, i have still some problems. When i take for $N = 25$ and $n_0=22$, i have an x where the first 3 values are 1 and the rest 0. So i make a convolution of that and i get $y[n]=[1,2,1,0,0,0,..]$. For me the result looks like a triangle ;-) But it is not in the range stated before.2011-05-22
  • 0
    Or is the N you stated, the length from y[n], so 2*25-1?2011-05-22
  • 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$.2011-05-22
  • 0
    Ah, thank you! But i don't understand it, i always get a triangle. Here is my matlab code: N = 25; n0 = 25; for n = 1 : N if n <= n0 b(n) = 1; else b(n) = 0; end end y = conv(b,b); When i have $N = n_0 = 25$, the amplitude of y = 25 and a triangle.2011-05-23
  • 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.2011-05-23
  • 0
    Yes, i know, i took n=1 because matlab's matrix indices start with 1. Just for testing. But thank you for your patience!2011-05-23