הצגת המקור של הדף "אלגוריתם גרצל"

{{לשכתב|נושא=מחשוב|נושא2=מדעי הטבע|כל הערך=כן}} 

'''אלגוריתם גרצל''' הוא [[אלגוריתם]] [[עיבוד אותות ספרתי]] (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]] של המשוואה תהיה:
:<math>\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})}</math>
אם נעביר את התוצאה במסנן הבא:
:<math>\frac{Y(z)}{S(z)} = 1 - e^{-2 \pi i \omega}z^{-1}</math>

התוצאה לאחר שני המסננים תהיה:
:<math>\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}}</math>

בחזרה למישור הזמן נקבל:
:<math>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}</math>, 

או בעצם 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

[[קטגוריה:עיבוד אותות ספרתי]]