30.2 The DFT and FFT

30.2-1

Prove Corollary 30.4.

(Omit!)

30.2-2

Compute the \(\text{DFT}\) of the vector \((0, 1, 2, 3)\).

(Omit!)

30.2-3

Do Exercise 30.1-1 by using the \(\Theta(n\lg n)\)-time scheme.

(Omit!)

30.2-4

Write pseudocode to compute \(\text{DFT}_n^{-1}\) in \(\Theta(n\lg n)\) time.

(Omit!)

30.2-5

Describe the generalization of the \(\text{FFT}\) procedure to the case in which \(n\) is a power of \(3\). Give a recurrence for the running time, and solve the recurrence.

(Omit!)

30.2-6 \(\star\)

Suppose that instead of performing an \(n\)-element \(\text{FFT}\) over the field of complex numbers (where \(n\) is even), we use the ring \(\mathbb Z_m\) of integers modulo \(m\), where \(m = 2^{tn / 2} + 1\) and \(t\) is an arbitrary positive integer. Use \(\omega = 2^t\) instead of \(\omega_n\) as a principal nth root of unity, modulo \(m\). Prove that the \(\text{DFT}\) and the inverse \(\text{DFT}\) are well defined in this system.

(Omit!)

30.2-7

Given a list of values \(z_0, z_1, \dots, z_{n - 1}\) (possibly with repetitions), show how to find the coefficients of a polynomial \(P(x)\) of degree-bound \(n + 1\) that has zeros only at \(z_0, z_1, \dots, z_{n - 1}\) (possibly with repetitions). Your procedure should run in time \(O(n\lg^2 n)\). (\(\textit{Hint:}\) The polynomial \(P(x)\) has a zero at \(z_j\) if and only if \(P(x)\) is a multiple of \((x - z_j)\).)

(Omit!)

30.2-8 \(\star\)

The chirp transform of a vector \(a = (a_0, a_1, \dots, a_{n - 1})\) is the vector \(y = (y_0, y_1, \dots, y_{n - 1})\), where \(y_k = \sum_{j = 0}^{n - 1} a_jz^{kj}\) and \(z\) is any complex number. The \(\text{DFT}\) is therefore a special case of the chirp transform, obtained by taking \(z = \omega_n\). Show how to evaluate the chirp transform in time \(O(n\lg n)\) for any complex number \(z\). (\(\textit{Hint:}\) Use the equation

\[y_k = z^{k^2 / 2} \sum_{j = 0}^{n - 1} \Big(a_jz^{j^2 / 2}\Big) \Big(z^{-(k - j)^2 / 2}\Big)\]

to view the chirp transform as a convolution.)

(Omit!)

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用