الإشكالية

لتكن { f_j } متتالية منتهية للأعداد العقدية بحيث 0 jn-1. 

تحويل فوريي اللامتصل مرتبط بالمتتالية { F_k } المعرفة كالتالي:

أحسب

بحيث 

(حالة التشابك الوقتي) 

المبدأ

تحويل فوريي اللامتصل لمتتالية {f_j } التي تحتوي على عدد من العناصر الزوجية يمكن حسابها بدلالة تحويل فوريي اللامتصل  لمتتاليتين ذات حدود لرتب زوجية وذات حدود لرتب فردية. يستعمل خوارزم كولي- توكي هذه الخاصية تراجعيا. 

الخوارزم 

نعتبر بالنسبة لـ n  قوة 2 أي: n = 2^r      

نكتب الإشارات في القاعدة 2: 

بحيث:

.............................................................................

.............................................................................

مثال 

أحسب تحويل فوريي اللامتصل للمتتالية {f_j } المعرفة كما يلي: 

f_j= j+1,  j=0,...,n-1 

الحساب اليدوي لتحويل فوريي اللامتصل  

 0 = 0+2*0+4*0 = (0,0,0)    1 = 1+2*0+4*0 = (1,0,0)
2 = 0+2*1+4*0 = (0,1,0)    3 = 1+2*1+4*0 = (1,1,0)
4 = 0+2*0+4*1 = (0,0,1)    5 = 1+2*0+4*1 = (1,0,1)
6 = 0+2*1+4*1 = (0,1,1)    7 = 1+2*1+4*1 = (1,1,1)

T₀(0,0,0) = f₀ = 1
T₀(1,0,0) = f₁ = 2
T₀(0,1,0) = f₂ = 3
T₀(1,1,0) = f₃ = 4
T₀(0,0,1) = f₄ = 5
T₀(1,0,1) = f₅ = 6
T₀(0,1,1) = f₆ = 7
T₀(1,1,1) = f₇ = 8

T₁(0,0,0) = T₀(0,0,0) + T₀(0,0,1) = 1 + 5 = 6
T₁(1,0,0) = T₀(1,0,0) + T₀(1,0,1) = 2 + 6 = 8
T₁(0,1,0) = T₀(0,1,0) + T₀(0,1,1) = 3 + 7 = 10
T₁(1,1,0) = T₀(1,1,0) + T₀(1,1,1) = 4 + 8 = 12
T₁(0,0,1) = T₀(0,0,0) - T₀(0,0,1) = 1 - 5 = -4
T₁(1,0,1) = T₀(1,0,0) - T₀(1,0,1) = 2 - 6 = -4
T₁(0,1,1) = T₀(0,1,0) - T₀(0,1,1) = 3 - 7 = -4
T₁(1,1,1) = T₀(1,1,0) - T₀(1,1,1) = 4 - 8 = -4

T₂(0,0,0) = T₁(0,0,0) + T₁(0,1,0) = 6 + 10 = 16
T₂(1,0,0) = T₁(1,0,0) + T₁(1,1,0) = 8 + 12 = 20
T₂(0,1,0) = T₁(0,0,0) - T₁(0,1,0) = 6 - 10 = -4
T₂(1,1,0) = T₁(1,0,0) - T₁(1,1,0) = 8 - 12 = -4
T₂(0,0,1) = T₁(0,0,1) - i T₁(0,1,1) = -4 -i(-4) = -4+4i
T₂(1,0,1) = T₁(1,0,1) - i T₁(1,1,1) = -4 -i(-4) = -4+4i
T₂(0,1,1) = T₁(0,0,1) + i T₁(0,1,1) = -4 +i(-4) = -4-4i
T₂(1,1,1) = T₁(1,0,1) + i T₁(1,1,1) = -4 +i(-4) = -4-4i

T₃(0,0,0) = T₂(0,0,0) + T₂(1,0,0) = 16 + 20 = 36 = F₀
T₃(1,0,0) = T₂(0,0,0) - T₂(1,0,0) = 16 - 20 = -4 = F₄
T₃(0,1,0) = T₂(0,1,0) - i T₂(1,1,0) = -4 -i (-4) = -4 + 4i = F₂
T₃(1,1,0) = T₂(0,1,0) + i T₂(1,1,0) = -4 +i (-4) = -4 - 4i = F₆
T₃(0,0,1) = T₂(0,0,1) + (√2/2)(1-i) T₂(1,0,1) = -4 + 4i + (√2/2)(1-i)(-4+4i) = -4 + 4(1+√2) i = F₁
T₃(1,0,1) = T₂(0,0,1) - (√2/2)(1-i) T₂(1,0,1) = -4 + 4i - (√2/2)(1-i)(-4+4i) = -4 + 4(1-√2) i = F₅
T₃(0,1,1) = T₂(0,1,1) - (√2/2)(1+i) T₂(1,1,1) = -4 - 4i - (√2/2)(1+i)(-4-4i) = -4 - 4(1-√2) i = F₃
T₃(1,1,1) = T₂(0,1,1) + (√2/2)(1+i) T₂(1,1,1) = -4 - 4i + (√2/2)(1+i)(-4-4i) = -4 - 4(1+√2) i = F₇

وبالتالي:

{F_k} ={36, -4+4(1+√2)i, -4+4i, -4-4(1-√2)i, -4, -4+4(1-√2)i, -4-4i, -4-4(1+√2)i}  

البرمجة

 #include <math.h>
#include <conio.h>
#define PI 3.14159265358989
#define NMAX 8
 
unsigned int tf_reversion(unsigned int indice,int nb);
void tf_cooley_tukey(int r,unsigned int n,double f[NMAX][2],double t[NMAX][2]);
 
main()
{
 int r;
 unsigned int n,i;
 double f[NMAX][2],t[NMAX][2];
 clrscr();
 printf("Méthode de Cooley-Tukey\n");
 f[0][0]=1;f[0][1]=0;
 f[1][0]=2;f[1][1]=0;
 f[2][0]=3;f[2][1]=0;
 f[3][0]=4;f[3][1]=0;
 f[4][0]=5;f[4][1]=0;
 f[5][0]=6;f[5][1]=0;
 f[6][0]=7;f[6][1]=0;
 f[7][0]=8;f[7][1]=0;
 r=3;
 n=1;
 for(i=1;i<=r;i++)
 n*=2;
 tf_cooley_tukey(r,n,f,t);
 printf("Transformation T%d :\n",r);
 for (i=0;i<n;i++)
 printf("F%u = ( %12.6e ) + ( %12.6e ) i\n",i,t[i][0],t[i][1]);
}

ملاحظة: بحذف التعليقات /*  و*/ ، لتظهر التحويلات  الوسيطية للدالةf_cooley_tukey  من خلال المتتالية البدئية. 

نتائج البرنامج

يظهر البرنامج في كل تحويل المتتاليات التي تم حسابها، ابتداء من المتتالية البدئية، حسب ترتيب الإشارات المعكوسة، إلى آخر متتالية حسب الترتيب الصحيح. 

التحويل    T0 :
 (  1.00000e+00 ) + (  0.00000e+00 ) i
 (  5.00000e+00 ) + (  0.00000e+00 ) i
 (  3.00000e+00 ) + (  0.00000e+00 ) i
 (  7.00000e+00 ) + (  0.00000e+00 ) i
 (  2.00000e+00 ) + (  0.00000e+00 ) i
 (  6.00000e+00 ) + (  0.00000e+00 ) i
 (  4.00000e+00 ) + (  0.00000e+00 ) i
 (  8.00000e+00 ) + (  0.00000e+00 ) i 

 التحويل T1   :
 (  6.00000e+00 ) + (  0.00000e+00 ) i
 ( -4.00000e+00 ) + (  0.00000e+00 ) i
 (  1.00000e+01 ) + (  0.00000e+00 ) i
 ( -4.00000e+00 ) + (  0.00000e+00 ) i
 (  8.00000e+00 ) + (  0.00000e+00 ) i
 ( -4.00000e+00 ) + (  0.00000e+00 ) i
 (  1.20000e+01 ) + (  0.00000e+00 ) i
 ( -4.00000e+00 ) + (  0.00000e+00 ) i 
التحويل T2   :
 (  1.60000e+01 ) + (  0.00000e+00 ) i
 ( -4.00000e+00 ) + (  4.00000e+00 ) i
 ( -4.00000e+00 ) + (  0.00000e+00 ) i
 ( -4.00000e+00 ) + ( -4.00000e+00 ) i
 (  2.00000e+01 ) + (  0.00000e+00 ) i
 ( -4.00000e+00 ) + (  4.00000e+00 ) i
 ( -4.00000e+00 ) + (  0.00000e+00 ) i
 ( -4.00000e+00 ) + ( -4.00000e+00 ) i 

 التحويل T3   :
 F0 = (  3.60000e+01 ) + (  0.00000e+00 ) i
 F1 = ( -4.00000e+00 ) + (  9.65685e+00 ) i
 F2 = ( -4.00000e+00 ) + (  4.00000e+00 ) i
 F3 = ( -4.00000e+00 ) + (  1.65685e+00 ) i
 F4 = ( -4.00000e+00 ) + (  0.00000e+00 ) i
 F5 = ( -4.00000e+00 ) + ( -1.65685e+00 ) i
 F6 = ( -4.00000e+00 ) + ( -4.00000e+00 ) i
 F7 = ( -4.00000e+00 ) + ( -9.65685e+00 ) i 

الدالة الرئيسية tf_cooley_tukey

يجب استدعاء دالتين مكملتين وهما:

 معايير الدالة tf_reversion :

indice : صحيح غير سالب
nb : عدد الأرقام الثنائية التي تمثل المؤشر في الأساس 2.

ترجع عدد صحيحا غير سالب المحصل عليه عند عكس الأرقام الممثلة في الأساس الثنائي للمؤشر.

معايير الدالة tf_cooley_tukey:

r : عدد صحيح يرتيط بعدد النماذج 2^r
n : عدد النماذج، الذي يجب أن يساوي 2^r
f : جدول ذي البعد NMAX*2 يحتوي على قيم النماذج قيمة في مل سطر, العمود الأول يحتوي على القيمة الحقيقية بينما العمود الثاني فيحتوي على القيمة التخيلية
t : جدول ذي البعد NMAX*2

ترجع الدالة الرئيسية في الجدول t تحويل فوريي اللمتصل لقيم f باستعمال طريقة كولي توكي (حيث أن كل قيمة ممثلة في سطر واحد, وأن العمود الأول لكل سطر يمثل القيمة الحقيقية بينما العود الثاني يمثل القيمة التخيليلة).

تساوي الثابتة الحقيقية PI القيمة 3.14159265358989.

 الثابتة الصحيحة NMAX تساوي العدد القصوي للنماذج.

unsigned int tf_reversion(unsigned int indice,int nb)
{
 unsigned int p,k,i;
 p=indice >> nb-1;
 for(i=1;i<nb;i++)
 {
 k=indice << i+16-nb;
 k=k >> 15;
 k=k << i;
 p+=k;
 }
 return(p);
}

void tf_cooley_tukey(int r,unsigned int n,double f[NMAX][2],double t[NMAX][2])
{
 int k;
 unsigned int ne,ns,n1,n2,i,j,tj;
 double arg,tr1,ti1,tr2,ti2,cr,ci;
 double tcos[NMAX],tsin[NMAX];
 n2=n/2;
 arg=PI/n2;
 for(i=0;i<n2;i++)
 {
 tcos[i]=cos(-arg*i);
 tcos[i+n2]=-tcos[i];
 tsin[i]=sin(-arg*i);
 tsin[i+n2]=-tsin[i];
 }
 for (i=0;i<n;i++)
 {
 j=tf_reversion(i,r);
 t[j][0]=f[i][0];
 t[j][1]=f[i][1];
 }
 ne=1;n1=2;ns=n;
 for (k=0;k<r;k++)
 {
 /*
 printf("Transformation T%d :\n",k);
 for (i=0;i<n;i++)
 printf("( %12.6e ) + ( %12.6e ) i\n",t[i][0],t[i][1]);
 */
 for (i=0;i<=n-n1;i+=n1)
 for(j=i;j<=i+ne-1;j++)
 {
 tj=j*n2;
 while (tj>=n) tj-=n;
 cr=tcos[tj];
 ci=tsin[tj];
 tr1=t[j][0]+cr*t[j+ne][0]-ci*t[j+ne][1];
 ti1=t[j][1]+cr*t[j+ne][1]+ci*t[j+ne][0];
 tj=(j+ne)*n2;
 while (tj>=n) tj-=n;
 cr=tcos[tj];
 ci=tsin[tj];
 tr2=t[j][0]+cr*t[j+ne][0]-ci*t[j+ne][1];
 ti2=t[j][1]+cr*t[j+ne][1]+ci*t[j+ne][0];
 t[j][0]=tr1;t[j][1]=ti1;
 t[j+ne][0]=tr2;t[j+ne][1]=ti2;
 }
 ne=n1;n1=2*ne;ns=n2;n2=ns/2;
 }
}

ملاحظة: إذا كنت تريد أن تجعل الدالة تظهر لك التحويلات البينية أيضا، فما عليك إلا أن تحذف رموز التعليقات لتفعيل سطور البرنامج الأخرى /* و */.