If you want optimized code, you will most probably have to write it yourself. Most code cannot be optimized to any useful degree without considering the specifics of the application.

For example, if you have a code designed for 4 bytes of data per loop, find out where only 2 bytes are needed. This will depend on the practical range of values that your application will be working with. Modifying certain parts of the code to work with only 2 bytes instead of 4 will result in some reduction of clock cycles. Try to reduce the cycle count of subroutines by using opcodes requiring less clock cycles (e.g. use left shift instead of multiplication by multiples of 2)

Another step would be to minimize the code in the main loop. For example you don't have to calculate the order for scrambling of the data everytime you run the fft. Obvious really. In fact you might try to maximise re-order the data at the input/output stage itself (depending on whether it is Decimation in Time / Frequency)

One more trick is to use look-up tables wherever possible (and avoid on-the-fly calculations) . This will be a trade-off, increasing memory size for reduced calculation cycles.

In your context, maybe CORDIC (Co-ordinate Rotation digital Computer) would be a good idea. I am not very familiar with it though, and am just guessing here.

Now lets look at your specifications:
256 point FFT would mean that you need at least 2*256*n bytes of RAM (n = number of bytes per point of data, 2 = for input + output)

Now for the 200 256-point calculations (8 butterflies). Assuming you are running at 24MHz exclusively for the purpose of FFT calculation...you will get (24*10^6)/(12*200)= 10000 cycles/per second per FFT. That comes to about 10000/8 = 1250 cycles per butterfly, max.

Also you will have a minimum of 256*LOG2(256)=2048 complex multiplications and additions (MAC) per FFT computation. That gives you an average of 10000/2048 = 4.8 cycles per complex operation. Even if we assume 5 cycles per MAC operation, I guess it still isnt enough time. And all this without considering the overheads involved in looping and byte-moving operations.

24 MHz is the fastest crystal I have used, and its the fastest in the AT89c51 series. So either you try to find a faster variant, or use another core entirely.

If I've made a mistake in my calculations/ assumptions, please do rectify :D

kundi