116
int iter,i,k;
int k1,inc1;
int k2,j,k3,k4;
char *buff1,*buff2,tmp;
long loc;

buff1=(char *)malloc(N*sizeof(char));
buff2=(char *)malloc(N*sizeof(char));
N1=N/2;
inc=1;
inc1=2; 00 02 04 06
11 13 15 17
20 22 24 26
01 03 05 07
10 12
14
16
21 23 25 27
30 32 34 36
41 43 45 47
50 52
54 56
31 33 35 37
40 42 44 46
51 53 55 57
61 63 65 67

14
16
25
27
34
36
35
37
00
02
11
13
20
22
01
03
10
12
21
23
30
32
31
33
45
47
54
56
44
46

21
23
25
27
30
32
34
36
41
43
45
47
50
52
54
56
31
33
35
37
40
42
44
46
51
53
55
57
61
63

21
30
31
22
23
32
33
24
25
34
35
26
27
36
37
41
50
40
51
43
52
42
53
45
5444
55
47
56
46
57

{
perror("fseek failed");
exit(1);
}
else
{
gotoxy(1,3);
printf("Reading row # %4d",i);
for(k4=0;k4<N;k4++)
*(buff1+k4)=fgetc(fptr);
{
loc=(long)(N)*(long)(i+inc);
}
if(fseek(fptr,loc,SEEK_SET)!=0)
{
perror("fseek failed");
exit(1) ;
}
else
{
gotoxy(1,4);
printf("Reading row # %4d",i+inc);
for(k4=0;k4<N;k4++)
*(buff2+k4)=fgetc(fptr);
}
k3=0;
for(k2=0;k2<N1;k2++)
{

118

gotoxy(1,4);
printf("writing row # %4d",i+inc);
for(k4=0;k4<N;k4++)
putc((char)(*(buff2+k4)),fptr);
}
}

k1+=inc1 ;
}

inc*=2;

119
inc1*=2;
N1/=2;
}

Để kiểm tra chương trình 6.5 chúng ta sẽ áp dụng thuật toán này lên ảnh cho
trong hình 6.11. ảnh này chứa trên đĩa đi kèm theo cuốn sách này dưới file có tên
là “MOHSEN.IMG”.

Chương trình 6.6 “ FFT2D.C” 2-D FFT

/******************************
* Program developed by: *
* M.A.Sid-Ahmed. *
* ver. 1.0 1992. *
* @ 1994 *
******************************/



clrscr();
printf(" Enter name of input file-> ");
scanf("%s",file_name);
if((fptr=fopen(file_name,"rb"))==NULL)
{
printf("file %s does not exist.\n");
exit(1);
}
nsq=(double)filelength(fileno(fptr));
N=sqrt(nsq);
m=(int)(log10((double)N)/log10((double)2.0));
k=1 ;

121
for(i=0;i<m;i++)
k<<=1 ;
if (k!=N)
{
printf("Length of file has to be multiples of 2.\n
");
exit(1);
}
Hình 6.12 Ảnh dịch chuyển của “MOHSEN.IMG”.
printf(" Enter file name for output file >");
scanf("%s",file_name);
fptro=fopen(file_name,"wb+");

/* Allocating memory for bit reversal LUT. */
L=(unsigned int *)malloc(N*sizeof(unsigned int));

=1 for 2-D IFFT.
For FFT (sign= 1) the input data is assumed to be
real.
The result of the FFT has its origin shifted to
(N/2,N/2).*/

int N2,i,j,k,kk;
long loc,NB;
float *xr,*xi,*buff;

N2=N<<1;
NB=sizeof(float)*N2;

/* Allocating memory for FFT arrays ( real and imag.)
*/
xr=(float *)malloc(N*sizeof(float));
xi=(float *)malloc(N*sizeof(float));
buff=(float *)malloc(NB); 123
/* First stage. */
gotoxy(1,3);
printf(" First stage. ");
for(j=0;j<N;j++)
{
gotoxy(1,4);
printf("FFT of row %4d",j);
if(sign==(int)1)
{

/* Transpose. */
gotoxy(1,5);

124
printf(" Transposing of intermediate file. ");
rewind(fptro);
transpose(fptro,N,m);
rewind(fptro);

/* Second stage. */
printf("\n Second stage.");
for(j=0;j<N;j++)
{
gotoxy(1,7);
printf("FFT of row %4d",j);
loc=(long)j*NB;
fseek(fptro,loc,SEEK_SET);
fread(buff,NB,1,fptro);
for(i=0;i<N;i++)
{
k=L[i] ;
kk=i<<1 ;
xr[k]=buff[kk];
xi[k]=buff[kk+1];
}
FFT(xr,xi,wr,wi,m,N);
for(i=0;i<N;i++)
{
k=i<<1 ;
if((sign==(int)1)&&((i+j)%2)==(int)0)

Note:
1. N=2 to the power of m.
2. The input arrays are assumed to be rearranged in
bit-reverse order.
You will need to use routine "bit-reversal" for
that purpose.
3. The twiddle factors are assumed to be stored in
LUT's wr[] and wi[].
You will need to use routine LUT for calculating
and storing twiddle factors.
*/

int ip,k,kk,l,incr,iter,i,j;
float Tr,Ti;

ip=1;
kk=(N>>1);
incr=2 ;

for(iter=0; iter<m; iter++)
{
for(j=0; j<N; j+=incr)
{
i=j+ip;
Tr=xr[i] ;
Ti=xi[i] ;
xr[i]=xr[j]-Tr;
xi[i]=xi[j]-Ti;