שאלת מבחן באלגוריתמים - האוניברסיטה הפתוחה 2021 - התמרת פורייה מהירה

מהו הפלט של טרנספורם פורייה הדיסקרטי $\text{DFT}_n$ מסדר $n$, כאשר הקלט הוא $(1,1,\dots,1)$ — כלומר וקטור המקדמים של הפולינום $p(x)=1+x+x^2+\cdots+x^{n-1}$?

רמז: הבע את ערך הפלט $y_k$ כסכום של סדרה הנדסית. הפרד למקרים: המקרה שבו מנת הסדרה היא 1, והמקרה שבו היא שונה מ-1.

פתרון: הפלט של **טרנספורם פורייה הדיסקרטי** ($DFT_n$) הוא וקטור $y = (y_0, y_1, ..., y_{n-1})$ המוגדר על ידי הערכת הפולינום $p(x)$ בנקודות שהן **שורשי היחידה** מסדר $n$. הקלט הוא וקטור המקדמים $a = (1, 1, ..., 1)$ של הפולינום $p(x) = \sum_{j=0}^{n-1} x^j$. לפי הגדרת ה-DFT, הרכיב ה-$k$ של וקטור הפלט $y$ נתון על ידי: $y_k = p(\omega_n^k) = \sum_{j=0}^{n-1} a_j (\omega_n^k)^j$ כאשר $\omega_n = e^{2\pi i / n}$ הוא שורש היחידה הפרימיטיבי מסדר $n$. במקרה שלנו, כל המקדמים $a_j$ שווים ל-1, ולכן: $y_k = \sum_{j=0}^{n-1} 1 \cdot (\omega_n^k)^j = \sum_{j=0}^{n-1} (\omega_n^k)^j$ זהו סכום של **סדרה הנדסית** עם איבר ראשון $a_1=1$, מנה $q = \omega_n^k$ ו-$n$ איברים. ננתח את ערך הסכום הזה עבור ערכים שונים של $k$ בתחום $0 \le k < n$. **מקרה 1: $k=0$** במקרה זה, מנת הסדרה היא $q = \omega_n^0 = (e^{2\pi i / n})^0 = 1$. הסכום הוא סכום של $n$ פעמים המספר 1: $y_0 = \sum_{j=0}^{n-1} (1)^j = \sum_{j=0}^{n-1} 1 = n$ **מקרה 2: $1 \le k < n$** במקרים אלו, מנת הסדרה היא $q = \omega_n^k \neq 1$. ניתן להשתמש בנוסחה לסכום סדרה הנדסית: $S_n = a_1 \frac{q^n - 1}{q - 1}$. $y_k = \frac{(\omega_n^k)^n - 1}{\omega_n^k - 1}$ נפשט את המונה: $(\omega_n^k)^n = (\omega_n^n)^k = ((e^{2\pi i / n})^n)^k = (e^{2\pi i})^k = 1^k = 1$ לכן, המונה הוא $1-1=0$. המכנה, $\omega_n^k - 1$, שונה מאפס מכיוון שהנחנו $k \neq 0$ (ולא כפולה של $n$). לפיכך, לכל $1 \le k < n$: $y_k = \frac{0}{\omega_n^k - 1} = 0$ **סיכום:** שילוב שני המקרים נותן את וקטור הפלט: $y_0 = n$ $y_k = 0$ עבור $k = 1, 2, ..., n-1$ ולכן, הפלט של הטרנספורם הוא הווקטור $(n, 0, 0, ..., 0)$. $\blacksquare$