Deadline: 2022-12-15 14:00 (21 days ago)
Tomáš Domes — 2022-12-04 17:03 (31 days ago) — reply
Mějme vektor $y$ délky $n$, který vznikl rotací vektoru $x$ o $c$ pozic. Tedy $y_j = x_{(j+c) \,\text{mod}\, n}$.
Vyjádřete Fourierův obraz $F(y)$ pomocí Fourierova obrazu $F(x)$.
*Řešení úlohy by tedy mohlo být například následující tvrzení včetně důkazu (následující výraz je pouze příklad a neplatí, nesnažte se ho, prosím, dokázat):* $F(y)_j = (j+c)^8F(x)_{(j^3+c-2) \,\text{mod}\, n} \, \forall j \in \{0, 1, \dots, n\}$
Tomáš Domes — 2022-12-22 20:34 (13 days ago) — reply
**Řešení:**
Rozepíšeme si $F(y)_k = \sum_{j = 0}^{n-1} y_j \omega^{kj} = \sum_{j = 0}^{n-1} x_{(j+c) \,\text{mod}\, n} \omega^{kj} = \sum_{j = 0}^{n-1} x_{(j+c) \,\text{mod}\, n}\omega^{kj + ck - ck} = \omega^{-ck} \sum_{j = 0}^{n-1} x_{(j+c) \,\text{mod}\, n}\omega^{(j+c)k}$. Zároveň platí $F(x)_k = \sum_{j = 0}^{n-1} x_j \omega^{kj}$. Když si nyní uvědomíme, že exponenty u $\omega$ můžeme počítat modulo $n$, vidíme, že sumy se liší pouze permutací sčítanců. To nám dává $F(y)_k = \omega^{-ck}F(x)_k$.