🚀 go-pugleaf

> ...does anyone have some C code laying around to do the 2D FFT that I
> may obtain a copy of?

    Please send it to me, too, or better yet, post!

Tom Anderson    toma@hpsad.hp.com        "It's only hardware"
Opinions expressed here are not HP's

Try "Numerical Recipies in C" page 467 for the complete code.

(This one was easy..)

Steve Warwick

sdw@hpsad.HP.COM (Steve Warwick) writes:

>Try "Numerical Recipies in C" page 467 for the complete code.

>(This one was easy..)

>Steve Warwick
But don't plan to compile it on a 16 bit machine, and don't mind
wasting M+N elements of your N+1 by M+1 array ... Anyone actually
translate all the indices from 1 <= j <= N, to 0 <= j < N ?

				Michael Finegan
				mfinegan@uceng.uc.edu

In article <2576@uceng.UC.EDU> mfinegan@uceng.UC.EDU (michael k finegan) writes:
>>Try "Numerical Recipies in C" page 467 for the complete code.
>But don't plan to compile it on a 16 bit machine, and don't mind
>wasting M+N elements of your N+1 by M+1 array ... Anyone actually
>translate all the indices from 1 <= j <= N, to 0 <= j < N ?

No, Numerical Recipies does not waste elements in the array.  The vector
and the matrix routines all allocate arrays where the first element is
indexed by 1, just like Fortran.  They do this by carefully subtracting
an offset (generally 1) from the value returned by malloc.  Then the user
(the 2d fft routine, for example) can do things just like Fortran.  See
the vector() and matrix() routines described in the appendix.

If you are going to complain about wasted space you should talk about the 
double indirection they do for all two dimensional arrays.  But, this is a 
pretty good way to get around the inability to dimension two dimensional 
arrays at run time in C but it does cost N elements of storage.

All in all I recommend the Numerical Recipies book.  I wish I had the book 
back when I was doing my thesis.

								Malcolm

/* nrl is number of rows (low index)
   nrh is number of rows (high index), etc.
 */

float   **matrix(nrl, nrh, ncl, nch)
int     nrl, nrh, ncl, nch;
{
        int     i;
        float   **m;

        m = (float **)malloc((unsigned int) (nch-ncl+1)*sizeof(float *));
        if (!m) nrerror("Allocation failure in matrix()");
        m -= nrl;

        for (i=nrl;i<=nrh;i++) {
                m[i] = (float *) malloc((unsigned) (nch-ncl+1)*sizeof(float));
                if (!m[i]) nrerror("Allocation failure in matrix()");
                m[i] -= ncl;
        }
        return m;
}

void free_matrix(m, nrl, nrh, ncl, nch)
float   **m;
int     nrl, nrh, ncl, nch;
{
        int     i;

        for (i=nrh;i>=nrl;i--) free((char *) (m[i] + ncl));
        free((char *) (m+nrl));
}

In article <9520007@hpsad.HP.COM> toma@hpsad.HP.COM (Tom Anderson) writes:
>> ...does anyone have some C code laying around to do the 2D FFT that I
>> may obtain a copy of?
>
>    Please send it to me, too, or better yet, post!
>
>Tom Anderson    toma@hpsad.hp.com        "It's only hardware"
>Opinions expressed here are not HP's

Come on, guys. This is pretty trivial stuff. 

I don't have a proper shar utility, so here goes:

/* Simple 2D fft program.
 * This program assumes the existence of an in-place 1D FFT routine,
 * with the prototype
 * 	1D_fft(complex *data, int size)
 * 
 * size should be an integer power of 2.
 */
#include <stdio.h>
typedef struct {float re, im} complex;

main() {
	int i, j;
	complex image[y][x];
	complex temp[x]; /* Larger of x or y */

	read(fileno(stdin),image, sizeof(image));
	for (i = 0; i < y; i++)
		1D_fft(image[i], x);

	for (j = 0; j < x; j++) {
		for(i = 0; i < y; i++) temp[i] = image[i][j];
		1D_fft(temp, y);
		for(i = 0; i < y; i++) image[i][j] = temp[i];
	}
	write(fileno(stdout), image, sizeof(image));
}

And that's it. Since the 2D DFT is separable, it can be computed by taking
the 1D DFT of all of the rows, followed by a DFT of all of the columns.

Note: I wrote this program as an example. I haven't tested it for syntactic
correctness (I'm not sure if 1D_fft(image[i], x) will pass in the correct
pointer). For generality I'd declare image to be a pointer to pointer of
complex, and allocate a 2D array using malloc(). This gives you flexibility
on image size.

If you were looking for a true 2D FFT, I can't help you there.

Theo Smit (smit@enel.UCalgary.CA)

In article <5047@orca.WV.TEK.COM> mhorne@ka7axd.wv.tek.com writes:
>Before I go implement a 2D FFT or adapt my 1D FFT algorithm for the 2D case,
>does anyone have some C code laying around to do the 2D FFT that I may obtain
>a copy of?
>
>Mike
>mhorne@ka7axd.wv.tek.com
>...tektronix!mhorne%ka7axd.wv.tek.com

Try anonymous ftp from 

     zaphod.ncsa.uiuc.edu(128.174.20.20):pub/unsupported/viewit/89.9/*

this is an hp like calculator for digital signal and image processing
that provides 2D fft functions among many other operators.

AJ Annala, USC Neuroscience Program

p.s.  If anyone decides to assume maintenance responsibility for this
      piece of code I would be very interested in learning about their
      efforts.  I have been able to use small parts of the program ...
      but it would be nice if the whole program worked correctly.