خوارزمية غورتزل

خوارزمية غورتزل هي تقنية في معالجة الإشارات الرقمية (DSP) لتقييم حدود تحويل فورييه المنفصل (DFT) بكفاءة. وهي مفيدة في بعض التطبيقات العملية، مثل التعرف على نغمات الإشارة متعددة الترددات ثنائية النغمة (DTMF) الصادرة عن أزرار لوحة مفاتيح الهاتف التناظري التقليدي. وقد وصف جيرالد غورتزل هذه الخوارزمية لأول مرة عام 1958. ^{[ 1 ]}

على غرار تحويل فورييه المنفصل (DFT)، تحلل خوارزمية غورتزل مكونًا تردديًا واحدًا قابلًا للتحديد من إشارة منفصلة . ^{[ 2 ] [ 3 ] [ 4 ]} وعلى عكس حسابات DFT المباشرة، تطبق خوارزمية غورتزل معاملًا واحدًا ذا قيمة حقيقية في كل تكرار، مستخدمةً العمليات الحسابية ذات القيم الحقيقية لتسلسلات الإدخال ذات القيم الحقيقية. ولتغطية طيف كامل (باستثناء استخدام تدفق البيانات المستمر حيث يُعاد استخدام المعاملات في الحسابات اللاحقة، والتي يكون تعقيدها الحسابي مكافئًا لـ DFT المنزلق )، فإن خوارزمية غورتزل تتميز برتبة تعقيد أعلى من خوارزميات تحويل فورييه السريع (FFT)، ولكنها أكثر كفاءة عددية عند حساب عدد قليل من المكونات الترددية المختارة. ويجعلها هيكلها البسيط مناسبة تمامًا للمعالجات الصغيرة والتطبيقات المدمجة.

يمكن أيضًا استخدام خوارزمية جورتزل "بشكل عكسي" كدالة توليف جيبية، والتي تتطلب عملية ضرب واحدة وطرح واحد فقط لكل عينة مُولَّدة. ^{[ 5 ]}

تتخذ العملية الحسابية الرئيسية في خوارزمية غورتزل شكل مرشح رقمي ، ولهذا السبب تُسمى الخوارزمية غالبًا بمرشح غورتزل . يعمل المرشح على سلسلة إدخال.${\displaystyle x[n]}$في سلسلة من مرحلتين مع معلمة${\displaystyle \omega _{0}}$، مما يعطي التردد المراد تحليله، مع تعديله إلى راديان لكل عينة.

تقوم المرحلة الأولى بحساب تسلسل وسيط،${\displaystyle s[n]}$:

${\displaystyle s[n]=x[n]+2\cos(\omega _{0})s[n-1]-s[n-2].}$

1

تُطبّق المرحلة الثانية الفلتر التالي على${\displaystyle s[n]}$، مما ينتج عنه تسلسل الإخراج${\displaystyle y[n]}$:

${\displaystyle y[n]=s[n]-e^{-j\omega _{0}}s[n-1].}$

2

يمكن ملاحظة أن مرحلة الترشيح الأولى هي مرشح IIR من الدرجة الثانية ذو بنية مباشرة . تتميز هذه البنية تحديدًا بأن متغيرات حالتها الداخلية تساوي قيم الخرج السابقة من تلك المرحلة. قيم الإدخال${\displaystyle x[n]}$ل${\displaystyle n<0}$يُفترض أن جميع القيم تساوي صفرًا. وذلك لتحديد حالة المرشح الأولية بحيث يمكن بدء التقييم عند العينة.${\displaystyle x[0]}$يتم تعيين القيم الأولية لحالات المرشح${\displaystyle s[-2]=s[-1]=0}$لتجنب مخاطر التداخل ، التردد${\displaystyle \omega _{0}}$غالبًا ما يقتصر النطاق على القيم من 0 إلى π (انظر نظرية نايكويست-شانون لأخذ العينات )؛ استخدام قيمة خارج هذا النطاق ليس بلا معنى، ولكنه يُكافئ استخدام تردد مُستعار داخل هذا النطاق، لأن الدالة الأسية دورية بفترة 2π في${\displaystyle \omega _{0}}$.

يمكن ملاحظة أن مرشح المرحلة الثانية هو مرشح FIR ، حيث أن حساباته لا تستخدم أيًا من مخرجاته السابقة.

يمكن تطبيق طرق تحويل Z لدراسة خصائص سلسلة المرشحات. تحويل Z للمرحلة الأولى من المرشحات الموضحة في المعادلة (1) هو

${\displaystyle {\begin{محاذاة}}}}\\&={\frac {1}{(1-e^{+j\omega _{0}}z^{-1})(1-e^{-j\omega) _{0}}z^{-1})}}.\end{محاذاة}}}$

3

التحويل Z لمرحلة الترشيح الثانية الموضحة في المعادلة (2) هو

${\displaystyle {\frac {Y(z)}{S(z)}}=1-e^{-j\omega _{0}}z^{-1}.}$

4

تكون دالة النقل المجمعة لتسلسل مرحلتي الترشيح هي

${\displaystyle {\begin{aligned}{\frac {S(z)}{X(z)}}{\frac {Y(z)}{S(z)}}={\frac {Y(z)}{X(z)}}&={\frac {(1-e^{-j\omega _{0}}z^{-1})}{(1-e^{+j\omega _ {0}}z^{-1})(1-e^{-j\omega _{0}}z^{-1})}}\\&={\frac {1}{1-e^{+j\omega _{0}}z^{-1}}}.\end{محاذاة}}}$

5

يمكن تحويل هذا مرة أخرى إلى متتالية مكافئة في المجال الزمني، ويتم فك الحدود وصولاً إلى حد الإدخال الأول عند الفهرس${\displaystyle n=0}$:

${\displaystyle {\begin{aligned}y[n]&=x[n]+e^{+j\omega _{0}}y[n-1]\\&=\sum _{k=-\infty}^{n}x[k]e^{+j\omega _{0}(nk)}\\&=e^{j\omega _{0}n}\sum _ {k=0}^{n}x[k]e^{-j\omega _{0}k}\qquad {\text{منذ }}\forall k<0,x[k]=0.\end{محاذاة}}}$

6

يمكن ملاحظة أن أقطاب تحويل Z للمرشح تقع عند${\displaystyle e^{+j\أوميغا _{0}}}$و${\displaystyle e^{-j\أوميغا _{0}}}$، على دائرة نصف قطرها وحدة واحدة، مركزها نقطة الأصل في مستوى التحويل Z المركب. تشير هذه الخاصية إلى أن عملية الترشيح مستقرة بشكل هامشي وعرضة لتراكم الأخطاء العددية عند حسابها باستخدام حسابات منخفضة الدقة ومتواليات إدخال طويلة. ^{[ 6 ]} وقد اقترح كريستيان راينش نسخة مستقرة عدديًا . ^{[ 7 ]}

في الحالة المهمة لحساب مصطلح DFT، يتم تطبيق القيود الخاصة التالية.

• تنتهي عملية التصفية عند الفهرس${\displaystyle n=N}$، أين${\displaystyle N}$يمثل عدد الحدود في تسلسل الإدخال لتحويل فورييه المنفصل (DFT).
• تقتصر الترددات المختارة لتحليل غورتزل على الشكل الخاص

${\displaystyle \omega _{0}=2\pi {\frac {k}{N}}.}$

7

• رقم الفهرس${\displaystyle k}$يشير هذا إلى اختيار "نطاق التردد" الخاص بتحويل فورييه المنفصل من مجموعة أرقام الفهرس

${\displaystyle k\in \{0,1,2,...,N-1\}.}$

8

بإجراء هذه التعويضات في المعادلة (6) وملاحظة أن الحد${\displaystyle e^{+j2\pi k}=1}$وبالتالي، تأخذ المعادلة (6) الشكل التالي:

${\displaystyle y[N]=\sum _{n=0}^{N}x[n]e^{-j2\pi {\frac {nk}{N}}}.}$

9

يمكننا أن نلاحظ أن الجانب الأيمن من المعادلة (9) مشابه للغاية للصيغة التعريفية لمصطلح DFT${\displaystyle X[k]}$مصطلح DFT لرقم الفهرس${\displaystyle k}$لكن ليس تمامًا. يتطلب الجمع الموضح في المعادلة (9)${\displaystyle N+1}$مصطلحات الإدخال، ولكن فقط${\displaystyle N}$تتوفر حدود الإدخال عند تقييم تحويل فورييه المنفصل (DFT). ومن الحلول البسيطة، وإن كانت غير أنيقة، توسيع تسلسل الإدخال.${\displaystyle x[n]}$مع قيمة اصطناعية أخرى${\displaystyle x[N]=0}$[ ^{8 ] يمكننا أن نرى من المعادلة (} 9) أن التأثير الرياضي على النتيجة النهائية هو نفسه تأثير حذف الحد${\displaystyle x[N]}$من المجموع، وبالتالي تقديم قيمة DFT المقصودة.

مع ذلك، توجد طريقة أكثر أناقة تتجنب تمريرة التصفية الإضافية. من المعادلة (1)، يمكننا ملاحظة أنه عندما يكون حد الإدخال الموسع${\displaystyle x[N]=0}$يتم استخدامه في الخطوة الأخيرة،

${\displaystyle s[N]=2\cos(\omega _{0})s[N-1]-s[N-2].}$

10

وبالتالي، يمكن إكمال الخوارزمية على النحو التالي:

• قم بإنهاء مرشح IIR بعد معالجة مصطلح الإدخال${\displaystyle x[N-1]}$،
• قم بتطبيق المعادلة (10) لإنشاء${\displaystyle s[N]}$من المخرجات السابقة${\displaystyle s[N-1]}$و${\displaystyle s[N-2]}$،
• قم بتطبيق المعادلة (2) مع القيم المحسوبة${\displaystyle s[N]}$قيمة ومع${\displaystyle s[N-1]}$تم إنتاجه من خلال الحساب المباشر النهائي للمرشح.

يتم تبسيط العمليتين الرياضيتين الأخيرتين من خلال دمجهما جبرياً:

${\displaystyle {\begin{aligned}y[N]&=s[N]-e^{-j2\pi {\frac {k}{N}}}s[N-1]\\&=(2\cos(\omega _{0})s[N-1]-s[N-2])-e^{-j2\pi {\frac {k}{N}}}s[N-1]\\&=e^{j2\pi {\frac {k}{N}}}s[N-1]-s[N-2].\end{aligned}}}$

11

لاحظ أن إيقاف تحديثات الفلتر عند نهاية المدة${\displaystyle N-1}$وتطبيق المعادلة (2) مباشرة بدلاً من المعادلة (11) يؤدي إلى تفويت تحديثات حالة المرشح النهائية، مما ينتج عنه نتيجة ذات طور غير صحيح. ^{[ 9 ]}

يُعدّ هيكل الترشيح المُختار لخوارزمية غورتزل مفتاحًا لحسابات DFT الفعّالة. نلاحظ وجود قيمة خرج واحدة فقط.${\displaystyle y[N]}$يُستخدم لحساب تحويل فورييه المنفصل (DFT)، لذا تُحذف حسابات جميع حدود الإخراج الأخرى. وبما أن مرشح FIR غير محسوب، فإن حسابات مرحلة IIR تُجرى تلقائيًا.${\displaystyle s[0],s[1]}$يمكن التخلص من العناصر الأخرى فور تحديث الحالة الداخلية للمرحلة الأولى.

يبدو هذا وكأنه يُثير مفارقة: لإكمال الخوارزمية، يجب تقييم مرحلة مرشح FIR مرة واحدة باستخدام آخر مُخرجين من مرحلة مرشح IIR، بينما تُهمل تكرارات مرشح IIR قيم مُخرجاته لتحسين الكفاءة الحسابية. هنا تبرز خصائص بنية المرشح ذات الشكل المباشر. يُوفر متغيرا الحالة الداخليان لمرشح IIR آخر قيمتين لمُخرج مرشح IIR، وهما الحدّان المطلوبان لتقييم مرحلة مرشح FIR.

• وفقًا لنظرية التعقيد الحسابي ، فإن حساب مجموعة من${\displaystyle M}$مصطلحات DFT باستخدام${\displaystyle M}$تطبيقات خوارزمية جورتزل على مجموعة بيانات مع${\displaystyle N}$القيم التي تبلغ "تكلفة العملية الواحدة"${\displaystyle K}$تتسم بالتعقيد${\displaystyle O(KNM)}$.

لحساب خانة DFT واحدة${\displaystyle X(f)}$بالنسبة لتسلسل إدخال معقد بطول${\displaystyle N}$، تتطلب خوارزمية غورتزل${\displaystyle 2N}$الضرب و${\displaystyle 4\ N}$عمليات الجمع/الطرح داخل الحلقة، بالإضافة إلى 4 عمليات ضرب و4 عمليات جمع/طرح نهائية، ليصبح المجموع${\displaystyle 2N+4}$الضرب و${\displaystyle 4N+4}$عمليات الجمع/الطرح. يتم تكرار ذلك لكل منها${\displaystyle M}$الترددات.

• في المقابل، استخدام تحويل فورييه السريع على مجموعة بيانات مع${\displaystyle N}$تتسم القيم بالتعقيد${\displaystyle O(KN\log _{2}(N))}$.

يصعب تطبيق ذلك بشكل مباشر لأنه يعتمد على خوارزمية تحويل فورييه السريع المستخدمة، ولكن المثال النموذجي هو تحويل فورييه السريع ذو الأساس 2، والذي يتطلب${\displaystyle 2\log _{2}(N)}$الضرب و${\displaystyle 3\log _{2}(N)}$عمليات الجمع/الطرح لكل خانة من خانات DFT ، لكل منها${\displaystyle N}$صناديق القمامة.

في تعابير ترتيب التعقيد، عندما يكون عدد الحدود المحسوبة${\displaystyle M}$أصغر من${\displaystyle \log N}$تتضح ميزة خوارزمية غورتزل. ولكن نظرًا لأن كود FFT معقد نسبيًا، فإن عامل "تكلفة وحدة العمل"${\displaystyle K}$غالبًا ما يكون حجم البيانات أكبر بالنسبة لخوارزمية تحويل فورييه السريع (FFT)، والميزة العملية ترجح كفة خوارزمية جورتزل حتى بالنسبة لـ${\displaystyle M}$أكبر بعدة مرات من${\displaystyle \log _{2}(N)}$.

كقاعدة عامة لتحديد ما إذا كانت خوارزمية تحويل فورييه السريع ذات الأساس 2 أو خوارزمية جورتزل أكثر كفاءة، قم بتعديل عدد الحدود.${\displaystyle N}$في مجموعة البيانات، قم بتقريبها إلى أقرب قوة دقيقة للعدد 2، وأطلق على هذا اسم${\displaystyle N_{2}}$ومن المرجح أن تكون خوارزمية جورتزل أسرع إذا

${\displaystyle M\leq {\frac {5N_{2}}{6N}}\log _{2}(N_{2})}$

تؤثر تطبيقات تحويل فورييه السريع (FFT) ومنصات المعالجة بشكل كبير على الأداء النسبي. تقوم بعض تطبيقات FFT ^{[ 11 ]} بإجراء حسابات داخلية للأعداد المركبة لتوليد المعاملات أثناء التنفيذ، مما يزيد بشكل ملحوظ من "تكلفة K لكل وحدة عمل". يمكن لخوارزميات FFT وDFT استخدام جداول قيم المعاملات المحسوبة مسبقًا لتحسين الكفاءة العددية، ولكن هذا يتطلب المزيد من عمليات الوصول إلى قيم المعاملات المخزنة مؤقتًا في الذاكرة الخارجية، مما قد يؤدي إلى زيادة التنازع على الذاكرة المؤقتة، الأمر الذي يقلل من بعض المزايا العددية.

يحقق كلا الخوارزميتين زيادة في الكفاءة بمقدار الضعف تقريبًا عند استخدام بيانات إدخال ذات قيم حقيقية بدلًا من بيانات إدخال ذات قيم مركبة. مع ذلك، تُعد هذه الزيادة طبيعية لخوارزمية غورتزل، لكنها لن تتحقق لخوارزمية تحويل فورييه السريع (FFT) إلا باستخدام متغيرات خوارزمية مُخصصة لتحويل البيانات ذات القيم الحقيقية .

• خوارزمية بلوستين لتحويل فورييه السريع (chirp-Z)
• مفتاح إزاحة التردد (FSK)
• مفتاح إزاحة الطور (PSK)

• بروكيس، جي جي؛ مانولاكيس، دي جي (1996)، معالجة الإشارات الرقمية: المبادئ والخوارزميات والتطبيقات ، أبر سادل ريفر، نيوجيرسي: برنتيس هول، ص 480-481 ، رمز Bibcode : 1996dspp.book.....P 

• خوارزمية غورتزل في موقع Wayback Machine (تمت أرشفة بتاريخ 28-06-2018)
• خوارزمية معالجة الإشارات الرقمية لتحليل التردد
• خوارزمية جورتزل لكيفن بانكس
• تحليل خوارزمية غورتزل من قِبل أوفه بيس، حيث يقارنها بمرشح تشيبيشيف التناظري منخفض التمرير من الدرجة الثانية