1    package math.transforms.fft; 
2     
3    //Title:        2-d mixed radix FFT. 
4    //Version: 
5    //Copyright:    Copyright (c) 1998 
6    //Author:       Dongyan Wang 
7    //Company:      University of Wisconsin-Milwaukee. 
8    //Description: 
9    //              . Use FFT1d to perform FFT2d. 
10    
11    
12   public class FFT2d { 
13    
14     // Input of FFT, 2-d matrix. 
15     float dataRe[][], dataIm[][]; 
16    
17     // Width and height of 2-d matrix inputRe or inputIm. 
18     int width, height; 
19    
20     // Constructor: 2-d FFT of Complex data. 
21     public FFT2d(float inputRe[], float inputIm[], int inputWidth) { 
22       // First make sure inputRe & inputIm are of the same length. 
23       if (inputRe.length != inputIm.length) { 
24         System.out.println("Error: the length of real part & imaginary part " + 
25                            "of the input to 2-d FFT are different"); 
26         return; 
27       } else { 
28         width = inputWidth; 
29         height = inputRe.length / width; 
30         dataRe = new float[height][width]; 
31         dataIm = new float[height][width]; 
32    
33         for (int i = 0; i < height; i++) 
34           for (int j = 0; j < width; j++) { 
35             dataRe[i][j] = inputRe[i * width + j]; 
36             dataIm[i][j] = inputIm[i * width + j]; 
37           } 
38    
39         // Calculate FFT for each row of the data. 
40         FFT1d fft1 = new FFT1d(width); 
41         for (int i = 0; i < height; i++) 
42           fft1.fft(dataRe[i], dataIm[i]); 
43    
44         // Tranpose data. 
45         // Calculate FFT for each column of the data. 
46         float temRe[][] = transpose(dataRe); 
47         float temIm[][] = transpose(dataIm); 
48    
49         FFT1d fft2 = new FFT1d(height); 
50         for (int j = 0; j < width; j++) 
51           fft2.fft(temRe[j], temIm[j]); 
52    
53         // Tranpose data. 
54         // Copy the result to input[], so the output can be 
55         // returned in the input array. 
56         for (int i = 0; i < height; i++) 
57           for (int j = 0; j < width; j++) { 
58             inputRe[i * width + j] = temRe[j][i]; 
59             inputIm[i * width + j] = temIm[j][i]; 
60           } 
61       } 
62     } 
63    
64     // Transpose matrix input. 
65     private float[][] transpose(float[][] input) { 
66       float[][] output = new float[width][height]; 
67    
68       for (int j = 0; j < width; j++) 
69         for (int i = 0; i < height; i++) 
70           output[j][i] = input[i][j]; 
71    
72       return output; 
73     } // End of function transpose(). 
74    
75    
76   }