خوارزميات سريعة للإشارات متعددة الأبعاد

المصدر: ^{[ 3 ]}

مجموع DFT${\displaystyle X\left(k_{1},k_{2}\right)}$يمكن كتابة المعادلة السابقة أيضًا بالشكل التالي

${\displaystyle X\left(k_{1},k_{2}\right)=\sum _{n_{1}=0}^{N_{1}-1}\left[\sum _{n_{2}=0}^{N_{2}-1}x(n_{1},n_{2})W_{N_{2}}^{n_{2}k_{2}}\right]W_{N_{1}}^{n_{1}k_{1}}}$

يترك ${\displaystyle G\left(n_{1},k_{2}\right)}$تشير إلى الكمية الموجودة داخل الأقواس ويتم تحديدها بواسطة:

${\displaystyle G\left(n_{1},k_{2}\right)=\sum _{n_{2}=0}^{N_{2}-1}x(n_{1},n_{2})W_{N_{2}}^{n_{2}k_{2}}}$

${\displaystyle X\left(k_{1},k_{2}\right)=\sum _{n_{1}=0}^{N_{1}-1}G\left(n_{1},k_{2}\right)W_{N_{1}}^{n_{1}k_{2}}}$

باستخدام هذه الطريقة، يتم تطبيق DFT${\displaystyle X}$يمكن حسابها على شكل تحويلات متعددة أحادية البعد (DFT). أي أن كل عمود من${\displaystyle G}$يمكن اعتبارها بمثابة تحويل فورييه أحادي البعد للعمود المقابل من${\displaystyle x}$(${\displaystyle n_{1}}$= ثابت). وكل صف من${\displaystyle X}$هو تحويل فورييه أحادي البعد للصف المقابل من ${\displaystyle G}$(${\displaystyle n_{2}}$= ثابت). لذا، نقوم بحساب تحويل فورييه المنفصل ثنائي الأبعاد عن طريق تقسيمه إلى تحويل فورييه المنفصل للصفوف والأعمدة.

يتم استخدام نفس المبدأ لتقييم تحويل فورييه المنفصل متعدد الأبعاد لإشارة ذات أبعاد M.

والآن دعونا نتحدث عن التوفير الحسابي الذي نحصل عليه باستخدام هذا النهج. يُلاحظ أننا نحتاج إلى${\displaystyle N_{1}N_{2}(N_{1}+N_{2})}$عمليات الجمع والضرب المعقدة. علاوة على ذلك، إذا تم حساب كل من هذه التحويلات المنفصلة أحادية البعد باستخدام تحويل فورييه السريع أحادي البعد، فيمكن تقليل عدد عمليات الضرب المعقدة إلى ${\displaystyle N_{1}N_{2}{\frac {\log _{2}N_{1}N_{2}}{2}}}$

المصدر: ^{[ 3 ]}

كما هو الحال في تحويل فورييه السريع أحادي البعد، يمكن تحقيق تقليل عدد العينات في الوقت نفسه في حالة الإشارات ثنائية الأبعاد. يمكن التعبير عن تحويل فورييه المنفصل أحادي البعد لإشارة طولها قوة من قوى العدد 2، بدلالة تحويلين من نوع DFT بنصف الطول، ويمكن التعبير عن كل منهما بدوره كمزيج من تحويلات DFT بربع الطول، وهكذا.

في حالة الإشارات ثنائية الأبعاد، يمكننا التعبير عن${\displaystyle (N_{1}{\text{ x }}N_{2})}$DFT من حيث أربعة${\displaystyle {\frac {N_{1}}{2}}{\text{ x }}{\frac {N_{2}}{2}}}$تحويلات فورييه المنفصلة (بافتراض${\displaystyle N_{1}}$و${\displaystyle N_{2}}$(قوى العدد 2). ولتبسيط الأمر، لنفترض أن${\displaystyle N_{1}=N_{2}=N}$يمكن تقسيم مجموع DFT المزدوج إلى أربعة مجاميع منفصلة، ​​واحد منها على عينات من${\displaystyle x}$والتي من أجلها كلاهما${\displaystyle n_{1}}$و${\displaystyle n_{2}}$زوجية، واحدة منها${\displaystyle n_{1}}$زوجي و${\displaystyle n_{2}}$أمر غريب، وهو أمر${\displaystyle n_{1}}$غريب و${\displaystyle n_{2}}$زوجي وآخر واحد له${\displaystyle n_{1}}$و${\displaystyle n_{2}}$غريب.

يُكتب هذا على النحو التالي  :

${\displaystyle X\left(k_{1},k_{2}\right)=S_{00}(k_{1},k_{2})+S_{01}(k_{1},k_{2})W_{N}^{k_{2}}+S_{10}(k_{1},k_{2})W_{N}^{k_{1}}+S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}}$

أين

${\displaystyle S_{00}(k_{1},k_{2})\equiv \sum _{m_{1}=0}^{N/2-1}\sum _{m_{2}=0}^{N/2-1}x(2m_{1},2m_{2})W_{N}^{2m_{1}k_{1}+2m_{2}k_{2}}}$

${\displaystyle S_{01}(k_{1},k_{2})\equiv \sum _{m_{1}=0}^{N/2-1}\sum _{m_{2}=0}^{N/2-1}x(2m_{1},2m_{2}+1)W_{N}^{2m_{1}k_{1}+2m_{2}k_{2}}}$

${\displaystyle S_{10}(k_{1},k_{2})\equiv \sum _{m_{1}=0}^{N/2-1}\sum _{m_{2}=0}^{N/2-1}x(2m_{1}+1,2m_{2})W_{N}^{2m_{1}k_{1}+2m_{2}k_{2}}}$

${\displaystyle S_{11}(k_{1},k_{2})\equiv \sum _{m_{1}=0}^{N/2-1}\sum _{m_{2}=0}^{N/2-1}x(2m_{1}+1,2m_{2}+1)W_{N}^{2m_{1}k_{1}+2m_{2}k_{2}}}$

جميع المصفوفات${\displaystyle S_{00}S_{01}S_{10}}$و ${\displaystyle S_{11}}$كل منها دوري في${\displaystyle (k_{1},k_{2})}$بفترات أفقية ورأسية${\displaystyle {\frac {N}{2}}}$باستخدام هذه الحقيقة، وكذلك حقيقة أن${\displaystyle W_{N}^{N/2}=-1,}$يمكننا الحصول على المتطابقات التالية  :

${\displaystyle X\left(k_{1},k_{2}\right)=S_{00}(k_{1},k_{2})+S_{01}(k_{1},k_{2})W_{N}^{k_{2}}+S_{10}(k_{1},k_{2})W_{N}^{k_{1}}+S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}}$

${\displaystyle X\left(k_{1}+{\frac {N}{2}},k_{2}\right)=S_{00}(k_{1},k_{2})+S_{01}(k_{1},k_{2})W_{N}^{k_{2}}-S_{10}(k_{1},k_{2})W_{N}^{k_{1}}-S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}}$

${\displaystyle X\left(k_{1},k_{2}+{\frac {N}{2}}\right)=S_{00}(k_{1},k_{2})-S_{01}(k_{1},k_{2})W_{N}^{k_{2}}+S_{10}(k_{1},k_{2})W_{N}^{k_{1}}-S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}}$

${\displaystyle X\left(k_{1}+{\frac {N}{2}},k_{2}+{\frac {N}{2}}\right)=S_{00}(k_{1},k_{2})-S_{01}(k_{1},k_{2})W_{N}^{k_{2}}-S_{10}(k_{1},k_{2})W_{N}^{k_{1}}+S_{11}(k_{1},k_{2})W_{N}^{k_{1}+k_{2}}}$

توضح لنا المعادلة أعلاه كيفية حساب نقاط DFT الأربع${\displaystyle X\left(k_{1},k_{2}\right)X\left(k_{1}+{\frac {N}{2}},k_{2}\right)X\left(k_{1},k_{2}+{\frac {N}{2}}\right){\text{ and }}X\left(k_{1}+{\frac {N}{2}},k_{2}+{\frac {N}{2}}\right)}$لقيمة معينة من${\displaystyle (k_{1},k_{2})}$من النقاط الأربع ${\displaystyle S_{00}(k_{1},k_{2})S_{01}(k_{1},k_{2})S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})}$.${\displaystyle S_{00}(k_{1},k_{2})}$يمكن الحصول عليها من خلال تقييم أ${\displaystyle \left({\frac {N}{2}}\times {\frac {N}{2}}\right)}$-نقطة DFT (وبالمثل غيرها)${\displaystyle S_{ij}}$(يمكن الحصول عليها).

وهكذا نرى أن${\displaystyle N\times N}$يمكن التعبير عن DFT بدلالة أربعة${\displaystyle {\frac {N}{2}}\times {\frac {N}{2}}}$DFTs.

قياسًا على الحالة أحادية البعد، تُسمى العملية الحسابية الموضحة في الشكل أدناه بـ${\displaystyle {\text{butterfly}}}$أو بتعبير أدق${\displaystyle radix-(2\times 2){\text{ butterfly}}}$.

تتطلب كل فراشة ثلاث عمليات ضرب معقدة وثماني عمليات جمع معقدة لحساب المخرجات من المدخلات. ولحساب جميع عينات${\displaystyle X}$من${\displaystyle S_{00}(k_{1},k_{2}),S_{01}(k_{1},k_{2}),S_{10}(k_{1},k_{2}){\text{ and }}S_{11}(k_{1},k_{2})}$يتطلب ذلك حسابات لـ${\displaystyle {\frac {N^{2}}{4}}}$الفراشات.

يتم تنفيذ عملية التخفيض هذه ${\displaystyle \log _{2}N}$أوقات عندما${\displaystyle N}$هو قوة للعدد 2. تتكون كل مرحلة من مراحل الإبادة من${\displaystyle {\frac {N^{2}}{4}}}$الفراشات، وكل فراشة تتضمن ثلاث عمليات ضرب معقدة وثماني عمليات جمع معقدة، ومن ثم عدد عمليات الضرب المعقدة التي يجب إجراؤها أثناء حساب${\displaystyle (N\times N)}$-جذر النقطة${\displaystyle (2\times 2)}$يُعطى تحويل فورييه السريع (FFT) بواسطة

${\displaystyle C_{vectorRadix(2\times 2)}={\frac {3N^{2}}{4}}\log _{2}N}$