חסימות בתדר
איך חוסמים את התדירות של פונקציה
כאשר נתונה לנו פונקציה על הישר $f:\RR \to \RR$ , הרבה פעמים יש לה יחסית “מעט מסה” בקצוות של הישר. למשל, אם האינטגרל $\int_{-\infty} ^\infty |f(x)|\dx < \infty$ הוא סופי, אז לכל $\varepsilon>0$ נוכל למצוא $M_\varepsilon$ כך שהאינטגרל מחוץ ל $[-M_\varepsilon,M_\varepsilon]$ הוא קטן, כלומר $\int_{|x|< M_\varepsilon} |f(x)|\dx < \varepsilon$ . במקרים כאלו הרבה פעמים נסתכל על הפונקציה $f(x)\chi_{[-M_\varepsilon, M_\varepsilon]}(x)$ שמכילה את “רב האינפורמציה” מהפונקציה המקורית ויש לה תומך סופי (היא שווה לאפס מחוץ לקטע הסופי $[-M_\varepsilon,M_\varepsilon]$ .)
כאשר אנחנו עובדים עם התמרות פורייה, אז הלמה של רימן לבג מבטיחה לנו ש $\hat{f}(\omega)\to 0$ כש $\abs{\omega} \to \infty$ , כלומר במובן מסוים כדי להבין את $\hat{f}$ לא צריך להתרחק יותר מדיי מהראשית (לעיתים חושבים על זה כאילו ה”אנרגיה” של הפונקציה נמצאת בתדרים נמוכים). האם נוכל לעשות תהליך דומה למה שתואר למעלה, ולנקות לחלוטין את התדרים הגובים, או בצורה יותר פורמלית, האם עבור $M>0$ קיימת פונקציה $f_M$ כך ש $$? \;\;\;\widehat{f_M}(\omega)=\cases{\hat{f}(\omega) & |\omega|\leq M \\ 0 & |\omega|>M}$$
נשים לב, שהדרישות על $\widehat{f_M}$ בעצם אומרות שההתמרה שלה צריכה להיות $\widehat{f_M}=\hat{f}\cdot \chi_{[-M,M]}$ ופה נוכל להעזר במשפט הקונבולוציה. נזכיר ש $\cf[\chi_{[-M,M]}](\omega)=\frac{\sin(\omega M)}{\omega \pi}$ , ואם נשתמש בהתמרה ההפוכה (עבור פונקציות ב $E^2$ ) נקבל ש $\cf[\frac{2\sin(xM)}{x}] = \chi_{[-M,M]}$ ולכן $$\cf\left[ f*\frac{\sin(xM)}{\pi x}\right](\omega) = \cf\left[ f\right](\omega) \cdot \cf\left[ \frac{2\sin(xM)}{x}\right]= \cf\left[ f\right](\omega) \cdot \chi_{[-M,M]}(\omega)$$
למה פונקציות שחסומות בתדר מעניינות?
אחת הסיבות שנרצה לעבוד עם פונקציות שחסומות בתדר היא המשפט הבא:
תהא $f\in E^1(\RR)$ ו $\hat{f}(\omega)=0$ לכל $|\omega|\geq L$ אז כמעט לכל $x$ מתקיים:
$$.f(x)=\sum_{-\infty}^\infty f\left(\frac{n\pi}{L}\right)\frac{\sin(Lx-n\pi)}{Lx-n\pi}$$
לפני שנוכיח את המשפט, מה בעצם הוא אומר?
המשפט בעצם שואל האם אפשר לעשות אינטרפולציה לפונקציה $f$ , כלומר אם אנחנו יודעים את הערך של $f$ בנקודות $f(\frac{n\pi}{L})$ , האם נוכל למצוא את הערכים $f(x)$ לכל $x\in \RR$ . באופן כללי זה כמובן לא נכון, למשל אם אנחנו דוגמים גל בנקודות השחורות למטה, אז אנחנו לא יודעים אם הגל היה עם תדירות נמוכה (הגל האדום) או תדירות גבוהה יותר (הכחול), או אפילו עוד יותר גבוהה:
משפט הדגימה שאם אנחנו יודעים שהתדירות לא יכולה להיות גדולה מדיי (כלומר $f(\omega)=0$ עבור $|\omega|$ מספיק גדול) והדגימה היא על נקודות במרווחים מתאימים, אז אפשר ממש לשחזר את הפונקציה המקורית. המרווח בין הדגימות בדוגמא למעלה הוא לא אחיד, אבל אפשר גם להצטמצם לדגימות ב $x=\frac{\pi n}{4}$ .
אנחנו בעצם מכירים מקרה דומה עם אינטרפולציה של פולינומים. אם רוצים לשחזר פולינום מדרגה $d$ אז צריך לדעת את הערכים שלו ב $d+1$ נקודות שונות. אם יודעים פחות נקודות, אז פתאום יש יותר מפולינום אחד שיתאים לדגימה.
לא נכנס לזה פה, אבל אם כל המטרה שלנו היא רק לשחזר את הגל המקורי, אז עדיף דווקא לקחת דגימות רנדומיות, אבל עדיין יש מקום חשוב למשפט עצמו, כי למשל במקרים רבים הדגימות הן במרווחים קבועים בצורה “טבעית”, במיוחד כאשר מדובר על דגימות דיגיטליות, ואז לרב קוראים לבעיה הזאת Aliasing, והפתרון שלה הן שיטות Anti-Aliasing.
למשל אשלייה שאפשר לראות הרבה פעמים כאשר מסתכלים על גלגלים מסתובבים זה שאם הם מסתובבים במהירויות מסויימות אז פתאום נראה כאילו המהירות שונה לחלוטין, ולפעמים הם אפילו מסתובבים בכיוון ההפוך:
מה שקורה זה שבעצם אנחנו רואים פריימים מתוך האנימציה, והמוח שלנו מנסה להשלים אותם לפונקציה רציפה, ובדרך כלל עושה את זה באמצעות אינטרפולציה לתדירות הנמוכה יותר.
דוגמא נוספת יותר סטטית היא למשל כאשר אנחנו מנסים להציג תמונה עם משבצות. אם הרזולוזציה לא מספיק גבוהה יחסית לגודל משבצות אז נראה את התופעה הבאה:
נניח שאנחנו רוצים להציג משבצות שחורות-לבנות, אבל הן מאוד קטנות (מתאים לפונקציה עם תדר מאוד גבוה) והרזולוציה שלנו לא מספיק גדולה (אין מספיק דגימות) . למשל נניח שכל פיקסל שמיוצג בתמונה למטה ע”י מסגרת כחולה מכסה כמה משבצות:
כאשר נרצה לצבוע את הפיקסל אז יש כמה אפשרויות לעשות את זה. אפשר למשל לעשות סוג של ממוצע, אבל דרך אחרת מאוד פשוטה זה להסתכל על הצבע שאמור להיות במרכז הפיקסל ולהשתמש בו עבור כל הפיקסל. הבעיה עם הדרך הזאת היא שלמשל למעלה כל הפיקסלים יצבעו בשחור.
כדי לראות את הבעיה הזאת בפעולה, בתכנה למטה יש תמונת משבצות שחורות-לבנות בגודל 50 על 50, אבל, ניתן לשלוט על ה”רזולוציה” ע”י הסליידר בצד שמאל למעלה:
הוכחת משפט הדגימה
-
נרמול הפונקציה: כדי לפשט קצת את הסימונים, ולא לעבוד עם $L$ כללית, נסתכל על הפונקציה $g(x):=f(\frac{\pi}{L}x)$ . היתרון בפונקציה הזאת היא שההתמרה שלה היא $\hat{g}(\omega)=\frac{L}{\pi}\hat{f}(\frac{L}{\pi}\omega)$ ולכן הנתון מתרגם ל $\hat{g}(\omega)=0$ לכל $|\omega|\geq \pi$ וצריך להראות ש
$$.g(\frac{L}{\pi}x) = \sum_{-\infty}^\infty g\left(n\right)\frac{\sin(Lx-n\pi)}{Lx-n\pi}$$
מאחר וזה נכון לכל $x$ , זה שקול להראות שזה נכון לכל $y=\frac{L}{\pi}x$ ולכן צריך להראות ש
$$.g(y) = \sum_{-\infty}^\infty g\left(n\right)\frac{\sin(\pi(y-n))}{\pi(y-n)}$$
-
מעבר לפונקציות מחזוריות: הפונקציה $\hat{g}(\omega)$ היא אפס מחוץ לקטע $[-\pi,\pi]$ ולכן נוכל להגדיר פונקציה חדשה $\hat{g}_P(\omega)$ שהיא השלמה $2\pi$ מחזורית של $\hat {g}(\omega)$ , או בצורה פורמלית:
$$.\hat{g}_P(\omega + 2\pi k) := \hat{g}(\omega) \;\; ; \;\; \forall w\in [-\pi,\pi],\;k\in \ZZ$$
אם נרצה לחזור אחורה, מהפונקציה המחזורית להתמרה עצמה, אז
$$.\hat{g}(\omega)=\hat{g}_P(\omega)\chi_{[-\pi, \pi]}(\omega)$$
-
טור פורייה: נשים לב שהתמרת פורייה היא תמיד רציפה, ולכן $\hat{g}_P$ היא פונקציה רציפה ומחזורית, ולכן קיים לה טור פורייה שמתכנס אליה בנורמת $\norm{\cdot}_2$ ונקודתית. בסימונים של אקספוננטים נקבל ש:
$$\hat{g}_P(\omega) = \sum_{-\infty}^\infty c_n\cdot e^{in\omega},\; \; c_n=\angles{\hat{g}_P,e^{in\omega}} = \frac{1}{2\pi}\int_{-\pi}^\pi \hat{g}_P(\omega)e^{-in\omega}\dom$$
-
התמרה הפוכה: בתחום $[-\pi, \pi]$ אנחנו יודעים ש $\hat{g}_P(\omega)=\hat{g}(\omega)$ ולכן נוכל להחליף את הפונקציה באינטגרנד, וגם נוכל להגדיל את גבולות האינטגרציה, אבל אז מה שנקבל זה פחות או יותר ההתמרה ההפוכה:
$$.c_n=\frac{1}{2\pi}\int_{-\infty}^\infty \hat{g}(\omega)e^{-in\omega}\dom=\frac{1}{2\pi}g(-n)$$
סה”כ קיבלנו ש
$$.\hat{g}(\omega) = \hat{g}_P(\omega)\chi_{[-\pi, \pi]}(\omega) = \frac{1}{2\pi}\sum_{-\infty}^\infty g(-n)\cdot e^{in\omega}\chi_{[-\pi, \pi]}(\omega) = \sum_{-\infty}^\infty \cf\left[g(-n)\cdot\frac{\sin((x+n)\pi)}{(x+n)\pi}\right](\omega)$$
ההתכנסות עצמה היא בנורמת $\norm{\cdot}_2$ והתמרת פורייה היא רציפה יחסית לנורמה הזאת (לא הוכחנו את זה, אך זה נכון) ולכן אפשר להחליף סדר סכימה והתמרה. לבסוף, בגלל היחידות של ההתמרה נקבל את השוויון (כמעט לכל $x$ ):
$$.g(x) =\frac{1}{2\pi}\sum_{-\infty}^\infty g(-n)\cdot\frac{\sin((x+n)\pi)}{(x+n)\pi} = \sum_{-\infty}^\infty g(n)\cdot\frac{\sin((x-n)\pi)}{(x-n)\pi}$$