001/*******************************************************************************
002 * This software is provided as a supplement to the authors' textbooks on digital
003 *  image processing published by Springer-Verlag in various languages and editions.
004 * Permission to use and distribute this software is granted under the BSD 2-Clause 
005 * "Simplified" License (see http://opensource.org/licenses/BSD-2-Clause). 
006 * Copyright (c) 2006-2016 Wilhelm Burger, Mark J. Burge. All rights reserved. 
007 * Visit http://imagingbook.com for additional details.
008 *******************************************************************************/
009
010package imagingbook.pub.dft;
011
012import imagingbook.lib.math.Complex;
013
014public class Dft1d {
015
016        double[] cosTable;
017        double[] sinTable;
018        Complex[] G;                    // TODO: clean up creation of G (made instances of Complex immutable)!
019        
020        Dft1d(int M){ //Constructor
021                makeCosTable(M);
022                makeSinTable(M);
023                G = new Complex[M];     //this is done only ONCE when object is created!
024                for (int i = 0; i < M; i++) {
025                        G[i] = new Complex(0,0);
026                }
027        }
028        
029        void makeCosTable(int M){
030                cosTable = new double[M];
031                for (int i=0; i<M; i++){
032                        cosTable[i]= Math.cos(2*Math.PI*i/M);
033                }
034        }
035        
036        void makeSinTable(int M){
037                sinTable = new double[M];
038                for (int i=0; i<M; i++){
039                        sinTable[i]= Math.sin(2*Math.PI*i/M);
040                }               
041        }
042        
043        public Complex[] DFT(Complex[] g, boolean forward) {
044                int M = g.length;
045                double s = 1 / Math.sqrt(M); //common scale factor
046                for (int u = 0; u < M; u++) {
047                        double sumRe = 0;
048                        double sumIm = 0;
049                        for (int m = 0; m < M; m++) {
050                                double gRe = g[m].re();
051                                double gIm = g[m].im();
052                                int k = (u * m) % M;
053                                double cosPhi = cosTable[k];
054                                double sinPhi = sinTable[k];
055                                if (forward)
056                                        sinPhi = -sinPhi;
057                                //complex multiplication: (gRe + i gIm) * (cosPhi + i sinPhi)
058                                sumRe += gRe * cosPhi - gIm * sinPhi;
059                                sumIm += gRe * sinPhi + gIm * cosPhi;
060                        }
061//                      G[u].re = s * sumRe;    
062//                      G[u].im = s * sumIm;
063                        G[u] = new Complex(s * sumRe, s * sumIm);
064                }
065                return G;
066        }
067}