FFT on PIC16F877A?
 

I am trying to calculate FFt on the PIC16F877A, since the PIC can't
provide enough RAM. I have store each caculation to the SRAM.

Here is the sample code.. I still can't get it to work though...
Any help would be great...

//Source code from here:
http://www.ee.washington.edu/class/4...FFT/brent_fft/

//the adc input data is 'OK'
//FFT is not working though.. writing to SRAM & read is back is
working


#include <16F877A.h>
#fuses HS,NOWDT,NOPROTECT,NOLVP
#use delay(clock=20000000)
#use rs232(baud=115200, xmit=PIN_C6, rcv=PIN_C7) // Jumpers: 8 to 11,
7 to 12
#include <MATH.h>
#include "header.h"
#include "tables.c"

void main() {
signed int zeroimag = 0;
long int SRAMpos = 0;
long int i, l2, l,l1, j;
char tempchar;
signed int real, imag, real1, imag1;
signed int tempval;
long int i1, t1, t2, u;
long z, h, tempr, tempi;

//signed int i, i1, j, l, l1, l2, t1, t2, u;

setup_port_a( AN0 );
setup_adc( ADC_CLOCK_INTERNAL );
set_adc_channel( 0 );


do {
printf(" \n\r press a to take analog sample \n\r");
do {
tempchar = getc();
} while (tempchar != 'a');


for (i=0; i<256; i++) {
setSRAMaddy(SRAMpos, 0);
real = Read_ADC();
real = (real-128)/4;
writeSRAM(real);
//printf("\n\r---> %d \n\r", real);
setSRAMaddy(SRAMpos, 1);
writeSRAM(zeroimag);
delay_us(2194);
SRAMpos++;
printf("%d ", real);
}

l2 = 128;
i=0;
for(l=0;l<255;l++) {
if(l < i) {
setSRAMaddy(l, 0);
j = readSRAM();

setSRAMaddy(i, 0);
real1 = readSRAM();

setSRAMaddy(l, 0);
writeSRAM(real1);

setSRAMaddy(i, 0);
writeSRAM(j);

}
l1 = l2;
while (l1 <= i){
i -= l1;
l1 >>= 1;
}
i += l1;
}

/* Compute the FFT */
u = 0;
l2 = 1;
for(l=0;l<8;l++){
l1 = l2;
l2 <<= 1;
for(j=0;j<l1;j++){
for(i=j;i<256;i+=l2){
i1 = i + l1;

setSRAMaddy(i, 0);
real = readSRAM();

setSRAMaddy(i, 1);
imag = readSRAM();

setSRAMaddy(i1, 0);
real1 = readSRAM();

setSRAMaddy(i1, 1);
imag1 = readSRAM();

t1 = (u1[u]*real1 - u2[u]*imag1)/32;
t2 = (u1[u]*imag1 + u2[u]*real1)/32;


setSRAMaddy(i1, 0);
writeSRAM((real-t1));

setSRAMaddy(i1, 1);
writeSRAM((imag-t2));

setSRAMaddy(i, 0);
writeSRAM((real+t1));

setSRAMaddy(i, 1);
writeSRAM((imag+t2));

}
u++;
}
}


for (i=124; i<133; i++){
setSRAMaddy((int8)i, 0);
real = readSRAM();
setSRAMaddy((int8)i, 1);
imag = readSRAM();
//printf("\n\r Value %ld: %d + i%d\n\r", i, real, imag);
}


/* Find the highest amplitude value */
/* start at index 1 because 0 can hold high values */
j=1;
l=0;
for ( i=1; i<128; i++ ) {
setSRAMaddy(i, 0);
real = readSRAM();

tempr = abs(real*real);

setSRAMaddy(i, 1);
imag = readSRAM();
tempi = abs(imag*imag);



l1 = tempr + tempi;

if (l1 > l) {
j = i;
l = l1;
}
}

setSRAMaddy(j, 0);
real = readSRAM();

setSRAMaddy(j, 1);
imag = readSRAM();

tempi = 1.5625*j;

printf("\n\r---> position %ld: %d + i %d value: %ld freq: %ld \n
\r", j, real, imag, l1,tempi);

u = 0;
l = 0;
l2 = 0;
l1 = 0;
j = 0;
i1 = 0;
SRAMpos = 0;
t1 = 0;
t2 = 0;
real = 0;
imag = 0;
real1 = 0;
imag1 = 0;
} while (TRUE);
}


signed int readSRAM(void) {
char temp_char = 0;
int i;

// Delay after seeing that data is available so that the
// data can be written to the SRAM.
//delay_us(4);

// Set the SRAM enables to READ.
//OE = 0;
//WE = 1;
//CS = 0;
output_low(OE_PIN);
output_high(WE_PIN);
//output_low(CS_PIN);

delay_us(1);

// Reads from the SRAM
temp_char = input_d();

delay_us(1);

// Stop READing by setting to IDLE state
//OE = 1;
//WE = 1;
//CS = 0;
output_high(OE_PIN);
output_high(WE_PIN);
//output_low(CS_PIN);

return temp_char;
}



/************************************************** *
* writeSRAM() *
* *
* Sets the correct enables and clocks the *
* counter to write to SRAM *
************************************************** */
void writeSRAM(signed int value) {
int i;
// Set SRAM to WRITE
//chartobin(value);

output_high(OE_PIN); // Enables WRITE
output_low(WE_PIN);
//output_low(CS_PIN);
delay_us(1);
//OE = 1;
//WE = 0;
//CS = 0;

output_d(value);

delay_us(1);

// Stop WRITING by setting to IDLE state
//OE = 1;
//WE = 1;
//CS = 1;
output_high(OE_PIN);
output_high(WE_PIN);
//output_high(CS_PIN);
delay_us(1);

// Clear I/O pins

input_d();
delay_us(1);
}


void setSRAMaddy (unsigned int pos, short img) {
output_b(pos);
if (img) { output_high(PIN_C3); }
else { output_low(PIN_C3); }
delay_us(1);
}