אלגוריתם גרצל

אלגוריתם גרצל הוא אלגוריתם עיבוד אותות ספרתי (DSP) המזהה מרכיבי תדר באות. האלגוריתם פורסם על ידי ד"ר ג'רלד גרצל ב-1958.

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

המדד להעדפת אלגוריתם הFFT יהיה כאשר M הוא מספר פסי התדר הנדרשים. במקרה שלנו M שווה לכל היותר 8 ועבור 777 דגימות האלגוריתם של גרצל כבר יותר יעיל. כמו כן FFT מחייב כמות דגימות שהיא בדיוק חזקה שלמה של 2 ואחסון של טבלאות ערכים של פונקציות הקוסינוס והסינוס הדרושות לחישוב, ובכך המימוש שלו מורכב יותר ודורש יותר שורות קוד.

אחד השימושים החשובים של אלגוריתם גרצל הוא זיהוי טונים בטלפוניה (DTMF), על ידי איתור מרכיבי התדר שמכיל האות.

פירוט האלגוריתם

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

(s(n) = x(n)+2cos(2πω)s(n−1)−s(n−2

כאשר, ערכי הדגימות (s(-2) ,s(-1 שווים לאפס. עבור ערך ידוע של ω מדובר בחיבור אחד חיסור אחד והכפלה אחת. האלגוריתם מממש מסנן IIR מסדר שני כאשר במוצא אמורים להתקבל ערכי ה DFT של האות. צורת העבודה היא כדלהלן: התמרת Z של המשוואה תהיה:

${\frac {S(z)}{X(z)}}={\frac {1}{1-2\cos(2\pi \omega )z^{-1}+z^{-2}}}={\frac {1}{(1-e^{+2\pi i\omega }z^{-1})(1-e^{-2\pi i\omega }z^{-1})}}$

אם נעביר את התוצאה במסנן הבא:

${\frac {Y(z)}{S(z)}}=1-e^{-2\pi i\omega }z^{-1}$

התוצאה לאחר שני המסננים תהיה:

${\frac {S(z)}{X(z)}}{\frac {Y(z)}{S(z)}}={\frac {Y(z)}{X(z)}}={\frac {(1-e^{-2\pi i\omega }z^{-1})}{(1-e^{+2\pi i\omega }z^{-1})(1-e^{-2\pi i\omega }z^{-1})}}={\frac {1}{1-e^{+2\pi i\omega }z^{-1}}}$

בחזרה למישור הזמן נקבל:

$y(n)=x(n)+e^{+2\pi i\omega }y(n-1)=\sum _{k=-\infty }^{n}x(k)e^{+2\pi i\omega (n-k)}=e^{+2\pi i\omega n}\sum _{k=-\infty }^{n}x(k)e^{-2\pi i\omega k}$,

או בעצם DFT מוכפל בגודל קבוע.

כדי לקבל רק את ה DFT במוצא נגדיר:

{(X(ω) = y(N − 1)e^{−2πiω(N − 1)} = (s(N − 1) – e^{−2πiω}s(N − 2))e^{−2πiω (N − 1

כאשר (y(N-1 הוא מוצא המסנן עבור N דגימות בשימוש עם הגדרת המסנן השני. מכיוון ש ω הוא התדר הדיגיטאלי ביחידות של מחזורים הנדרשים למטרת דגימה אחת, אזי ωN הוא גודל שלם, k. נובע מכך שניתן לפשט את המשוואה ל:

(X(ω) = (s(N − 1) – e^{−2πiω}s(N − 2))e^{+2πiω} = e^{+ 2πiω}s(N − 1) − s(N − 2

אם נחשב את הערך המוחלט של המוצא נקבל:

(X(ω)X'(ω) = s(N − 2)² + s(N − 1)² − 2cos(2πω)s(N − 2)s(N − 1