Дискретное преобразование Фурье

Вычислите следующие свёртки (используя свёртку $\odot$ двух векторов, как определено в этом разделе: для $a = (\alpha_{0},\ldots ,\alpha_{n-1})^{T}$, $b=(\beta_{0},\ldots ,\beta_{n-1})^{T}$, вектор $a \odot b$ размера $2n$, $k$-й элемент которого равен $\sum_{j=0}^{k} \alpha_{j}\beta_{k-j}$, с дополнением $\alpha_{i},\beta_{i}=0$ при $i \geq n$).

Проверьте непосредственно, что $F_{4} = \begin{pmatrix} F_{2} & D_{2}F_{2} \\ F_{2} & -D_{2}F_{2} \end{pmatrix} P_{4}$, где $F_{4}, P_{4}, D_{2}$ определены, как в разложении матрицы Фурье (5.8.15): для $n=2^{r}$, $F_{n} = \begin{pmatrix} F_{n/2} & D_{n/2}F_{n/2} \\ F_{n/2} & -D_{n/2}F_{n/2} \end{pmatrix}P_{n}$, где $D_{n/2} = \operatorname {diag}(1,\xi ,\xi^{2},\ldots ,\xi^{n/2-1})$ ($\xi$ — первообразный корень $n$-й степени из единицы, используемый на протяжении всего раздела) и $P_{n}^{T} = \left[e_{0}\; e_{2}\; e_{4}\; \cdots \; e_{n-2} \mid e_{1}\; e_{3}\; e_{5}\; \cdots \; e_{n-1}\right]$ — матрица перестановки чётных-нечётных индексов.

Используя следующие векторы, выполните указанные вычисления: $a = \begin{pmatrix} \alpha_{0} \\ \alpha_{1} \end{pmatrix}$, $b = \begin{pmatrix} \beta_{0} \\ \beta_{1} \end{pmatrix}$, $\hat{a} = \begin{pmatrix} \alpha_{0} \\ \alpha_{1} \\ 0 \\ 0 \end{pmatrix}$, $\hat{b} = \begin{pmatrix} \beta_{0} \\ \beta_{1} \\ 0 \\ 0 \end{pmatrix}$.

Для $p(x) = 2x-3$ и $q(x) = 3x-4$ вычислите произведение $p(x)q(x)$, используя теорему о свёртке.

Используя свёртки, образуйте следующие произведения.

Пусть $a$ и $b$ — векторы размера $n \times 1$, где $n$ — степень двойки.

Волновая форма, заданная конечной суммой $x(\tau ) = \sum_{k} (\alpha_{k}\cos 2\pi f_{k}\tau + \beta_{k}\sin 2\pi f_{k}\tau )$, в которой $f_{k}$ — целые числа и $\max \left\{ f_{k}\right\} \leq 3$, отсчитывается в восьми равноотстоящих точках между $\tau =0$ и $\tau =1$. Пусть $x = \begin{pmatrix} x(0/8) & x(1/8) & x(2/8) & x(3/8) & x(4/8) & x(5/8) & x(6/8) & x(7/8) \end{pmatrix}^{T}$, и пусть

Каково уравнение волновой формы?

Докажите, что $a \odot b = b \odot a$ для всех $a, b \in \mathbb {C}^{n}$ — то есть свёртка является коммутативной операцией.

Для $p(x) = \sum_{k=0}^{n-1} \alpha_{k}x^{k}$ и корней $n$-й степени из единицы $\xi^{k}$ пусть $a = \begin{pmatrix} \alpha_{0} & \alpha_{1} & \cdots & \alpha_{n-1} \end{pmatrix}^{T}$ и $p = \begin{pmatrix} p(1) & p(\xi ) & \cdots & p(\xi^{n-1}) \end{pmatrix}^{T}$. Объясните, почему $F_{n}a = p$ и $a = F_{n}^{-1}p$.

Для двух многочленов $p(x) = \sum_{k=0}^{n-1}\alpha_{k}x^{k}$ и $q(x) = \sum_{k=0}^{n-1}\beta_{k}x^{k}$ пусть $p = \begin{pmatrix} p(1) & p(\xi ) & \cdots & p(\xi^{2n-1}) \end{pmatrix}^{T}$ и $q = \begin{pmatrix} q(1) & q(\xi ) & \cdots & q(\xi^{2n-1}) \end{pmatrix}^{T}$, где $1,\xi ,\xi^{2},\ldots ,\xi^{2n-1}$ теперь — корни $2n$-й степени из единицы. Объясните, почему коэффициенты произведения $p(x)q(x) = \gamma_{0}+\gamma_{1}x+\cdots +\gamma_{2n-2}x^{2n-2}$ должны задаваться формулой

Циркулянтной матрицей называется квадратная матрица вида $C = \begin{pmatrix} c_{0} & c_{n-1} & c_{n-2} & \cdots & c_{1} \\ c_{1} & c_{0} & c_{n-1} & \cdots & c_{2} \\ c_{2} & c_{1} & c_{0} & \cdots & c_{3} \\ \vdots & \vdots & \vdots & & \vdots \\ c_{n-1} & c_{n-2} & c_{n-3} & \cdots & c_{0} \end{pmatrix}_{n\times n}$ — то есть элементы каждого столбца совпадают с элементами предыдущего столбца, но сдвинуты на одну позицию вниз с циклическим переносом наверх; $(j,k)$-й элемент равен $c_{jk} = c_{j-k \pmod{n}}$.

Для невырожденного циркулянта $C_{n\times n}$ объясните, как использовать алгоритм БПФ для эффективного выполнения следующих операций.

Для векторов $a = \begin{pmatrix} \alpha_{0} \\ \alpha_{1} \\ \vdots \\ \alpha_{n-1} \end{pmatrix}$, $b = \begin{pmatrix} \beta_{0} \\ \beta_{1} \\ \vdots \\ \beta_{n-1} \end{pmatrix}$, $\hat{a} = \begin{pmatrix} \alpha_{0} \\ \vdots \\ \alpha_{n-1} \\ 0 \\ \vdots \\ 0 \end{pmatrix}_{2n \times 1}$ и $\hat{b} = \begin{pmatrix} \beta_{0} \\ \vdots \\ \beta_{n-1} \\ 0 \\ \vdots \\ 0 \end{pmatrix}_{2n \times 1}$, пусть $C$ — циркулянтная матрица размера $2n\times 2n$ (упражнение 5.8.12), первый столбец которой равен $\hat{a}$.

Кронекеровым произведением двух матриц $A_{m\times n}$ и $B_{p\times q}$ называется матрица размера $mp \times nq$ вида $A \otimes B = \begin{pmatrix} a_{11}B & a_{12}B & \cdots & a_{1n}B \\ a_{21}B & a_{22}B & \cdots & a_{2n}B \\ \vdots & \vdots & & \vdots \\ a_{m1}B & a_{m2}B & \cdots & a_{mn}B \end{pmatrix}$, удовлетворяющая $A\otimes (B\otimes C) = (A\otimes B)\otimes C$ и $(A\otimes B)(C\otimes D) = AC\otimes BD$ (когда $AC$ и $BD$ определены).

Для $p(x) = \alpha_{0}+\alpha_{1}x+\alpha_{2}x^{2}+\cdots +\alpha_{n-1}x^{n-1}$ докажите, что

где $1,\xi ,\xi^{2},\ldots ,\xi^{n-1}$ — корни $n$-й степени из единицы.

Рассмотрим сигнал, заданный конечной суммой $x(\tau ) = \sum_{k}(\alpha_{k}\cos 2\pi f_{k}\tau + \beta_{k}\sin 2\pi f_{k}\tau )$, в которой $f_{k}$ — различные целые числа, и пусть $x = \sum_{k}(\alpha_{k}\cos 2\pi f_{k}t + \beta_{k}\sin 2\pi f_{k}t)$ — вектор, содержащий значения $x(\tau )$ в $n > 2\max \left\{ f_{k}\right\}$ равноотстоящих точках между $\tau =0$ и $\tau =1$ (пример 5.8.3). Используя дискретное преобразование Фурье, докажите, что

Пусть $\eta$ — произвольный скаляр, и пусть $c = \begin{pmatrix} 1 \\ \eta \\ \eta^{2} \\ \vdots \\ \eta^{2n-1} \end{pmatrix}$ и $a = \begin{pmatrix} \alpha_{0} \\ \alpha_{1} \\ \vdots \\ \alpha_{n-1} \end{pmatrix}$. Докажите, что $c^{T}(a \odot a) = \left(c^{T}\hat{a}\right)^{2}$.

Примените алгоритм БПФ к вектору $x_{8} = \begin{pmatrix} x_{0} \\ x_{1} \\ \vdots \\ x_{7} \end{pmatrix}$, а затем проверьте, что ваш ответ согласуется с результатом, полученным непосредственным вычислением $F_{8}x_{8}$.