تحويل Z للتردد

يُعدّ تحويل Z المُعدَّل ( CZT ) تعميمًا لتحويل فورييه المنفصل (DFT). فبينما يأخذ تحويل فورييه المنفصل عينات من المستوى Z عند نقاط متباعدة بانتظام على طول دائرة الوحدة ، يأخذ تحويل Z المُعدَّل عينات على طول أقواس حلزونية في المستوى Z، والتي تُقابل خطوطًا مستقيمة في المستوى S. ^{[ 1 ] [ 2 ]} ويمكن حساب تحويل فورييه المنفصل، وتحويل فورييه المنفصل الحقيقي، وتحويل فورييه المنفصل المُكبَّر كحالات خاصة من تحويل Z المُعدَّل.

على وجه التحديد، يقوم تحويل Z المتغير بحساب تحويل Z عند عدد محدود من النقاط z _k على طول محيط حلزوني لوغاريتمي ، كما هو محدد على النحو التالي: ^{[ 1 ] [ 3 ]}

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x(n)z_{k}^{-n}}$

${\displaystyle z_{k}=A\cdot W^{-k},k=0,1,\dots ,M-1}$

حيث A هي نقطة البداية المعقدة، و W هي النسبة المعقدة بين النقاط، و M هو عدد النقاط المراد حسابها.

على غرار تحويل فورييه المنفصل (DFT)، يمكن حساب تحويل Z للتردد المتغير في O( n log n ) عملية حيث$n=\max(M,N)$تم وصف خوارزمية O( N log N ) لتحويل Z العكسي للتردد (ICZT) في عام 2003، ^{[ 4 ] [ 5 ]} وفي عام 2019. ^{[ 6 ]}

خوارزمية بلوستين ^{[ 7 ] [ 8 ]} تعبر عن CZT على شكل التفاف وتنفذها بكفاءة باستخدام FFT /IFFT.

بما أن تحويل فورييه المنفصل (DFT) حالة خاصة من تحويل Z-T، فإن هذا يسمح بحساب تحويل فورييه المنفصل (DFT) بكفاءة عالية لأحجام عشوائية، بما في ذلك الأحجام الأولية . (تعمل خوارزمية رادر ، وهي خوارزمية أخرى لتحويل فورييه السريع (FFT) للأحجام الأولية ، أيضًا عن طريق إعادة كتابة تحويل فورييه المنفصل (DFT) على شكل التفاف). وقد طُورت هذه الخوارزمية عام 1968 على يد ليو بلوستاين . ^{[ 7 ]} ويمكن استخدام خوارزمية بلوستاين لحساب تحويلات أكثر عمومية من تحويل فورييه المنفصل (DFT)، استنادًا إلى تحويل Z (أحادي الجانب) (رابينر وآخرون ، 1969).

تذكر أن تحويل فورييه المنفصل (DFT) يُعرَّف بالصيغة التالية

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}e^{-{\frac {2\pi i}{N}}nk}\qquad k=0,\dots ,N-1.}$

إذا استبدلنا حاصل الضرب nk في الأس بالعنصر المحايد

${\displaystyle nk={\frac {-(kn)^{2}}{2}}+{\frac {n^{2}}{2}}+{\frac {k^{2}}{2}}}$

وبذلك نحصل على:

${\displaystyle X_{k}=e^{-{\frac {\pi i}{N}}k^{2}}\sum _{n=0}^{N-1}\left(x_{n}e^{-{\frac {\pi i}{N}}n^{2}}\right)e^{{\frac {\pi i}{N}}(kn)^{2}}\qquad k=0,\dots ,N-1.}$

هذا المجموع هو بالضبط عملية التفاف للمتتاليتين a _n و b _n المعرفتين على النحو التالي:

${\displaystyle a_{n}=x_{n}e^{-{\frac {\pi i}{N}}n^{2}}}$

${\displaystyle b_{n}=e^{{\frac {\pi i}{N}}n^{2}},}$

مع ضرب ناتج عملية الالتفاف في N من عوامل الطور b _k ^* . أي:

${\displaystyle X_{k}=b_{k}^{*}\left(\sum _{n=0}^{N-1}a_{n}b_{kn}\right)\qquad k=0,\dots ,N-1.}$

يمكن إجراء هذا الالتفاف، بدوره، باستخدام زوج من تحويلات فورييه السريعة (بالإضافة إلى تحويل فورييه السريع المحسوب مسبقًا لتردد التردد المعقد b _n ) عبر نظرية الالتفاف . النقطة الأساسية هي أن هذه التحويلات ليست بنفس الطول N : لا يمكن حساب هذا الالتفاف بدقة من تحويلات فورييه السريعة إلا بإضافة أصفار إلى طول أكبر من أو يساوي 2 N – 1. على وجه الخصوص، يمكن إضافة أصفار إلى قوة العدد اثنين أو أي حجم مركب آخر ، حيث يمكن إجراء تحويل فورييه السريع بكفاءة باستخدام خوارزمية كولي-توكي، على سبيل المثال، في زمن O( N log N ). بالتالي، توفر خوارزمية بلوستين طريقة O( N log N ) لحساب تحويلات فورييه المنفصلة ذات الحجم الأولي، على الرغم من أنها أبطأ بعدة مرات من خوارزمية كولي-توكي للأحجام المركبة. ^{[ 9 ]}

يستحق استخدام التصفير في عملية الالتفاف في خوارزمية بلوستين بعض التوضيح. لنفترض أننا قمنا بتصفير المصفوفة حتى طول M ≥ 2N – 1. هذا يعني أن a _{_n} تُمدد إلى مصفوفة A _n بطول M ، حيث A _{_n} = a_{_n} عندما 0 ≤ n < N، و A _{_n} = 0 فيما عدا ذلك - وهو المعنى المعتاد لـ "التصفير". مع ذلك، وبسبب وجود الحد b_{_{k – n}} في عملية الالتفاف، فإن قيم n الموجبة والسالبة مطلوبة لـ b _{_n} (مع ملاحظة أن b_{k _{– n}} = b_{_n} ). تعني الحدود الدورية التي يفرضها تحويل فورييه المنفصل للمصفوفة المُصفّرة أن – n يكافئ M – n . بالتالي، تُمدد b_{_n} إلى مصفوفة B_n بطول M ، حيث B _₀ = b _₀ ، و B _{_n} = B_{_{M – n}} = b_n عندما 0 < n < N ، و B _{_n} = 0 فيما عدا ذلك. ^{[ 9 ]} ثم يتم تطبيق تحويل فورييه السريع (FFT) على A و B ، وضربهما نقطة بنقطة، ثم تطبيق تحويل فورييه السريع العكسي عليهما للحصول على التفاف a و b ، وفقًا لنظرية الالتفاف المعتادة. ^{[ 9 ]}

دعونا نوضح بدقة أكبر نوع الالتفاف المطلوب في خوارزمية بلوستاين لتحويل فورييه المنفصل. إذا كانت المتتالية b_{_n} دورية في n بفترة N ، فسيكون الالتفاف دوريًا بطول N ، وستكون إضافة الأصفار لأغراض حسابية فقط. مع ذلك، ليس هذا هو الحال عمومًا.

${\displaystyle b_{n+N}=e^{{\frac {\pi i}{N}}(n+N)^{2}}=b_{n}\left[e^{{\frac {\pi i}{N}}(2Nn+N^{2})}\right]=(-1)^{N}b_{n}.}$

لذا، عندما يكون N زوجيًا، تكون عملية الالتفاف دورية، ولكن في هذه الحالة يكون N عددًا مركبًا ، وعادةً ما يُستخدم خوارزمية تحويل فورييه السريع (FFT) أكثر كفاءة مثل خوارزمية كولي-توكي. أما عندما يكون N فرديًا، فإن b _{_n} تكون دورية عكسية ، ولدينا من الناحية التقنية عملية التفاف سالبة دورية بطول N. تختفي هذه الفروقات عند إضافة أصفار إلى a _{_n} ليصل طولها إلى 2^{N - 1} على الأقل كما هو موضح أعلاه. ولعل من الأسهل، بالتالي، اعتبارها مجموعة فرعية من مخرجات عملية التفاف خطية بسيطة (أي بدون "امتدادات" مفاهيمية للبيانات، دورية أو غير دورية). ^{[ 9 ]}

يمكن أيضًا استخدام خوارزمية بلوستين لحساب تحويل أكثر عمومية استنادًا إلى تحويل z (أحادي الجانب) (رابينر وآخرون ، 1969) ^{[ 9 ]} . وعلى وجه الخصوص، يمكنها حساب أي تحويل من الشكل التالي:

${\displaystyle X_{k}=\sum _{n=0}^{N-1}x_{n}z^{nk}\qquad k=0,\dots ,M-1,}$

لأي عدد مركب z ولأعداد مختلفة N و M من المدخلات والمخرجات. بالنظر إلى خوارزمية بلوستاين ^{[ 9 ]} ، يمكن استخدام هذا التحويل، على سبيل المثال، للحصول على استيفاء أدق لجزء من الطيف (على الرغم من أن دقة التردد لا تزال محدودة بوقت أخذ العينات الكلي، على غرار تحويل فورييه السريع المكبر)، أو لتحسين الأقطاب العشوائية في تحليلات دالة النقل، وما إلى ذلك.

أُطلق على الخوارزمية اسم خوارزمية تحويل التردد المتغير (chirp z-transform) لأنه في حالة تحويل فورييه (| z | = 1)، فإن المتتالية b _n المذكورة أعلاه هي دالة جيبية مركبة ذات تردد متزايد خطيًا، والتي تسمى ( التردد المتغير الخطي) في أنظمة الرادار . ^{[ 9 ]}

• تحويل فورييه الجزئي

• خوارزمية معالجة الإشارات الرقمية لتحليل التردد - تحويل Chirp-Z (CZT)
• حل لغز عمره 50 عامًا في معالجة الإشارات، الجزء الثاني