התמרות פורייה ולפלס

DFT והתמרת פורייה המהירה

The Discrete and Fast Fourier Transforms

ה־DFT מחליף N דגימות ב־N מקדמי תדר. פיצול למיקומים זוגיים ואי־זוגיים ממחזר חישובים ומוריד את העלות מ־N² ל־N log₂N.

יחידת לימוד עצמאיתשיעור 2 מתוך 6כ־75 דקות כולל תרגול3 מטרות למידה

1
נקודת פתיחהמה כבר ידוע ומה השאלה?
2
ניבוימה יקרה במקרה הפשוט?
3
המחשהמה באמת משתנה בתמונה?
4
ניסוח והצדקהשם, נוסחה ולמה היא נכונה
5
בדיקהדוגמה, תרגול ומשוב
6
העברהמקרה חדש והמשך המסלול

שאלה לפני נוסחה

מה אנחנו מנסים לראות?

לעבור מדגימות למקדמי תדר בעזרת DFT, לפרש גודל ופאזה, ולגזור את פיצול ה־FFT שמחשב אותה התמרה בדיוק בעלות O(N log N).

ה־DFT שואל עד כמה N הדגימות דומות לכל אחד מ־N גלגלים מרוכבים שמסתובבים במהירויות שונות. ה־FFT אינו קירוב חדש: הוא מבחין שחצי מן הגלגלים חוזרים בתוך בעיות קטנות יותר וממחזר אותם.

לפני ההמחשה: קראו רק את הכותרת “אותן דגימות בשני בסיסים”. מה לדעתכם ישתנה, מה יישאר קבוע, ואיזה סימן בתמונה יוכל להפריך את הניבוי?

לראות לפני שמחשבים · המקרה הפשוט ביותר

אותן דגימות בשני בסיסים

עקבו מהצורה הראשונית אל התוצאה

החלק העליון מציג שמונה דגימות בזמן, והתחתון את גדלי שמונת מקדמי ה־DFT.

מה כדאי לגלות: בחרו הלם מוזז: הגדלים נשארים שווים, אך המקדמים המרוכבים מחליפים פאזה. גודל לבדו אינו מספיק לשחזור.

אחרי שראינו

בסוף השיעור תוכלו

לחשב DFT ו־DFT הפוכה בדוגמאות קצרות באמצעות שורשי יחידה.
לפרש הזזה, תדר נייקוויסט ו־aliasing מתוך הדגימות והספקטרום.
לגזור שלב פרפר של Cooley–Tukey ולהשוות N² פעולות ל־N log₂N.

נותנים שמות למה שראינו

מושגים שנשתמש בהם

DFT: שינוי בסיס הפיך מ־N דגימות xⱼ אל N מקדמים מרוכבים Xₖ.
שורש יחידה ωₙ: המספר e^(−2πi/N); חזקותיו הן N נקודות שוות־מרחק על מעגל היחידה.
פאזה: זווית המקדם המרוכב, הקובעת היכן הגל מיושר ביחס לדגימות.
תדר נייקוויסט: התדר הגבוה ביותר שניתן להבחין בו בדגימה אחידה: חצי מתדר הדגימה.
aliasing: מצב שבו תדרים שונים נותנים אותן דגימות ולכן אינם ניתנים להפרדה.
פרפר FFT: הפעולה המשלבת פלט זוגי ואי־זוגי ל־Eₖ±ωₙᵏOₖ.

מהמילים אל הסימנים

כותבים את הפעולה שכבר ראינו

פתחו את הנוסחה רק אחרי שאתם יכולים לומר במילים מה כל פעולה אמורה לעשות. בשלב הבא נצדיק אותה צעד אחר צעד.

להצגת נוסחת המפתח

קראו כל סימן כפעולה, לא כמשהו שצריך לשנןXₖ=Σⱼxⱼe^(−2πijk/N); FFT=O(N log N)

מרכיבים את הפעולות

מהתמונה אל הנוסחה — הגזירה, בלי לדלג על הצעדים

מגדירים את ההתמרה
לכל תדר k כופלים את הדגימה j במעריכי בעל פאזה הפוכה ומחברים. הסימן השלילי הוא מוסכמה של ההתמרה קדימה.
Xₖ=Σⱼ₌₀^(N−1)xⱼe^(−2πijk/N)
מוכיחים אורתוגונליות בדידה
סכום חזקות של שורש יחידה הוא טור גאומטרי. אם ההפרש בין התדרים אינו כפולה של N, המונה מתאפס והמכנה לא.
Σⱼe^(2πij(k−m)/N)=Nδₖₘ
מקבלים התמרה הפוכה
האורתוגונליות מחזירה כל דגימה ומותירה גורם N, ולכן מחלקים ב־N בכיוון ההפוך.
xⱼ=(1/N)ΣₖXₖe^(2πijk/N)
מפצלים זוגי ואי־זוגי
מפרידים את הסכום לדגימות x₂r ולדגימות x₂r+1. כל חלק הוא DFT בגודל N/2.
Xₖ=Eₖ+ωₙᵏOₖ
משתמשים באותם חצאים פעמיים
מאחר ωₙ^(k+N/2)=−ωₙᵏ, אותו Eₖ ואותו Oₖ נותנים גם את החצי השני של הספקטרום באמצעות חיסור.
Xₖ₊ₙ/₂=Eₖ−ωₙᵏOₖ
סופרים עלות
בכל אחת מ־log₂N רמות מבצעים N/2 פרפרים. לכן מספר הפעולות גדל כמו N log₂N במקום N².
T(N)=2T(N/2)+O(N)=O(N log₂N)
מזהים את גבול הדגימה
בדגימות j=0,…,N−1, התדרים k ו־k+N נותנים אותן חזקות. בלי הגבלת רוחב פס, תדר גבוה עלול להתחפש לתדר נמוך.
e^(2πi(k+N)j/N)=e^(2πikj/N)

עכשיו רואים את השיטה בפעולה

דוגמאות פתורות, צעד אחר צעד

דוגמה 1

הלם בדיד

חשבו את ה־DFT של x=(1,0,0,0).

בכל Xₖ רק האיבר j=0 אינו אפס.
הגורם המעריכי שם הוא e⁰=1 לכל k.
לכן X₀=X₁=X₂=X₃=1.
הגדלים זהים, וההתמרה ההפוכה מחזירה את ההלם לאחר חלוקה ב־4.

התוצאה ומה היא אומרת

DFT(1,0,0,0)=(1,1,1,1).

דוגמה 2

תדר נייקוויסט בארבע דגימות

חשבו את ה־DFT של x=(1,−1,1,−1).

האות הוא xⱼ=(−1)ʲ=e^(iπj).
ב־N=4, התדר k=2 נותן e^(2πi·2j/4)=e^(iπj).
האורתוגונליות מאפסת את k=0,1,3.
ב־k=2 כל ארבע התרומות שוות 1 ולכן סכומן 4.

התוצאה ומה היא אומרת

X=(0,0,4,0); זהו תדר נייקוויסט.

איפה זה פוגש את העולם

יישום

FFT מאפשרת ספקטרוגרמות שמע, כפל פולינומים, קונבולוציה מהירה ופתרון משוואות על רשתות מחזוריות. עבור מיליון דגימות, הפער בין N² לבין N log N הוא ההבדל בין חישוב מעשי לחישוב שאינו מעשי.

מלכודת נפוצה

מה כדאי לבדוק

לחשוב שה־FFT מחזירה רק ספקטרום מקורב או מוחקת תדרים. האלגוריתם מחשב את אותה DFT בדיוק; הבדלים זעירים נובעים רק מסדר פעולות ועיגול. סינון הוא שלב נפרד.

בודקים שהרעיון יושב

תרגול ומשוב

בדיקת הבנה

בחרו תשובה ורק אז בדקו את עצמכם

מה משתנה בספקטרום כאשר מזיזים הלם מדגימה 0 לדגימה 1?

הפאזה משתנה אך הגדלים נשארים 1כל המקדמים מתאפסיםרק X₀ משתנה

בחרו אחת מהאפשרויות כדי להמשיך.

עכשיו אתם

אתגר קצר

חשבו את ה־DFT של x=(0,1,0,0) לפי מוסכמת הסימן השלילי, והסבירו כיצד התוצאה מקודדת הזזה.

רמז ראשון

רק j=1 תורם, ולכן Xₖ=e^(−2πik/4). עברו על k=0,1,2,3 על מעגל היחידה.

הצגת דרך הפתרון

ל־k=0 מתקבל 1.
ל־k=1 מתקבל e^(−iπ/2)=−i.
ל־k=2 מתקבל e^(−iπ)=−1, ול־k=3 מתקבל e^(−3iπ/2)=i.
לכן X=(1,−i,−1,i); כל הגדלים 1 והפאזה לינארית ב־k.

מימוש הנושא

קוד שאפשר לקחת לניסוי

הקוד מיישם את אותו רעיון מתמטי. ב־JavaScript אפשר להריץ אותו כאן; גרסת Python זמינה להשוואה ולהעתקה.

הקשר למתמטיקה

הקוד מממש FFT רקורסיבית: מפריד דגימות זוגיות ואי־זוגיות ומחבר אותן בפרפרים עם שורשי יחידה.

פלט צפוי

עבור (1,−1,1,−1) יתקבלו מקדמים הקרובים ל־(0,0,4,0), וההתמרה ההפוכה תחזיר את הקלט.

ניסוי המשך

החליפו את הקלט בהלם מוזז ובדקו שהגדלים זהים אך החלקים הממשיים והמדומים משתנים.

מהרעיון אל הקוד

מימוש חישובי

function fft(values) {
  const N=values.length;
  if(N===1) return [values[0]];
  const even=fft(values.filter((_,i)=>i%2===0));
  const odd=fft(values.filter((_,i)=>i%2===1));
  const out=Array(N);
  for(let k=0;k<N/2;k++) {
    const angle=-2*Math.PI*k/N;
    const w={re:Math.cos(angle),im:Math.sin(angle)};
    const o=typeof odd[k]==="number"?{re:odd[k],im:0}:odd[k];
    const e=typeof even[k]==="number"?{re:even[k],im:0}:even[k];
    const t={re:w.re*o.re-w.im*o.im,im:w.re*o.im+w.im*o.re};
    out[k]={re:e.re+t.re,im:e.im+t.im};
    out[k+N/2]={re:e.re-t.re,im:e.im-t.im};
  }
  return out;
}

console.log(fft([1,-1,1,-1]));

from cmath import exp, pi

def fft(values):
    N=len(values)
    if N==1:
        return [complex(values[0])]
    even=fft(values[0::2])
    odd=fft(values[1::2])
    out=[0j]*N
    for k in range(N//2):
        term=exp(-2j*pi*k/N)*odd[k]
        out[k]=even[k]+term
        out[k+N//2]=even[k]-term
    return out

print(fft([1,-1,1,-1]))

לפני שממשיכים

מה לוקחים מהשיעור

ה־DFT הוא שינוי בסיס אורתוגונלי בדיד והפיך.
גודל ופאזה יחד דרושים לשחזור האות.
FFT מפצלת זוגי־אי־זוגי וממחזרת שתי התמרות בגודל חצי.
דגימה מגבילה את התדרים שניתן להבחין ביניהם ויוצרת aliasing.

משימת מעבדה לשיעור הזה

תחנה 2 — מדגימות לתדרים

עברו בין אותות בני שמונה דגימות, נבאו את מיקום הפסגות והשוו DFT ישיר לפרפרי FFT.

לפתיחת התחנה

מקורות להעמקה בלבד — השיעור עומד בפני עצמו

מדריך המרצים: עמ׳ 223–225

ספר הלימוד: עמ׳ 446–454