Severe Fourier Help: Solve Problems by Monday

[BustedBreaks]

Okay so I have the following problems to figure out by Monday morning. I'm very behind so I am going to spend some time trying to work them out on my own tonight and tomorrow so don't think I am asking for the specific answers, but I thought I would post this here so when I have some trouble figuring out a problem I can refer to which one and which part quickly. I thank you for all of your help in advance!


1) In this exercise you will analyze a recursive algorithm for computing the discrete Fourier transform of a complex vector $$f:=(f_{0}, f_{1},...,f_{N-1}$$ when $$N = 2^{m}$$ = 0,1, ... . We define

$$even (f_{0}, f_{1},...,f_{N-1} := (f_{0}, f_{2}, f_{4}...,f_{N-2})$$
$$odd (f_{0}, f_{1},...,f_{N-1} := (f_{1}, f_{3}, f_{5}...,f_{N-1})$$
$$two (f_{0}, f_{1},...,f_{N-1} := \frac{1}{2} (f_{0}, f_{1},...,f_{N-1},f_{0}, f_{1},...,f_{N-1})$$
$$mod (f_{0}, f_{1},...,f_{N-1}):= (f_{0},\omega f_{1},...,\omega^{N-1},f_{N-1}), \omega :=e^{\frac{2\pi i}{N}}$$

We use these mappings to define $$rfft$$ recursively by writing:

If N = 1, then
$$rfft(f):=f$$
else
$$rfft(f):=mod(two(rfft(odd(f))))+(two(rfft(even(f))).$$

(a) Write down the operator identity that underlies this computation of f^ =rfft(f).
Hint. Examine Figs 6.1, 6.2, 6.7, and observe that the macros two, mod are based on the repeat and exponential modulation operators.

(b) How many times will rfft be "called" in the process of computing the DFT of a vector $$N = 2^{m}$$ components?

(c) How many simultaneously active copies of rfft must be used during the computation of (b), i.e., how deep is the recursion?





2) Let $$f_{k}$$ be $$\sigma _{k}$$-bandlimited, k =1,2,...,K. How must T>0 be chosen to ensure that we can recover $$f$$ from the samples $$f(nT), n=0,\pm 1,\pm 2, ...$$ when

(a) $$f:=f_{1}\cdot f_{2}\cdot ... \cdot f_{K}?$$

(b) $$f:=f_{1}\ast f_{2}\ast ... \ast f_{K}?$$

Note: An additional regularity is needed to ensure that the convolution product is well defined, e.g., you may assume that $$F_{1}, F_{2}, ... , F_{K}$$ are piecewise smooth ordinary functions on R.


3) Let f,g be $$\sigma$$ -bandlimited functions with G, G', G'', ... being continuous. Let T>0 and assume that $$0<2\sigma T<1.$$ Show that

$$(g\ast f)(t) = \sum^{\infty}_{n=-\infty} Tf(nT)g(t-nT).$$


4) Write down the Fourier series of f(x) = x2, consider as a 2−periodic function in the interval [−1,1). Plot both f and the Kth partial sum of its Fourier series for k = 1,2,5,7. Plot the same graphs over the interval [−2, 2).


5) Repeat problem 2) with the 2−periodic function f defined by f(x) = 1 for x ∈ (−1/2,1/2], and f(x) = 0 if x ∈ (−1,−1/2] ∪ (1/2,1]. Plot both f and the Kth partial sum of its Fourier series with K = 5, 10, 20, 40. Observe how slow the convergence is in this case.

 

[lippyka]

6) Consider a sequence of functions f_{n} defined on [0,2\pi] which are f_{n}(x) = \frac{1}{\sqrt{2\pi}} + \frac{1}{2n}\cos (nx) + \frac{1}{2n}\sin (nx). Find the value of the limit lim_{n\to\infty}f_{n}(x).