The DFT and Counting Cycles

I've spent the last few days implementing the Discrete Fourier Transform on a AVR microcontroller. I ran into several issues along the way and as a result learned a lot about AVR timers and the ADC.

I ran into the most trouble with the timers. I was too lazy to set up a ATmega328 on a breadboard and just decided to use an Arduino for testing purposes (and because it already has a serial communication library for relaying results). I wanted to use timer0 to trigger at 16 kHz and set when the ADC should sample. However, I didn't know that timer0 was used by the Arduino core. I spent several hours wondering my bins were only 30 Hz apart when they should have been 500 Hz apart (determined by using a Youtube hearing test video). I finally figured it out and switched over to timer2.

Now my bins were much wider, but they were still only ~300 Hz apart. I was somehow still not sampling at the right rate. I soon realized that the ADC conversion time was longer than the time between each sample. I had set the ADC prescaler to 128, and with a 16 MHz system clock and each ADC conversion taking 13 ADC clock cycles, each ADC conversion would have taken 1,664 system clock cycles. But with a 16 kHz sampling rate, there was only 1,000 system clock cycles between each sample. The 300 Hz bin spacing is now clearly explained, since (16,000,000 cycles/sec)/(1,664 cycles/sample) = 9,615 samples/sec. With 32 bins, the bins are 300 Hz apart at this sampling rate. I lowered the ADC prescaler to 8 and now the ADC conversion only takes 104 system clock cycles.

I thought I fixed everything until I realized that now my bins were nearly 2 kHz apart! The reduction in ADC conversion time must have caused this, but I couldn't figure how. Timer2 should have been regulating the sampling speed to 16 kHz. I looked back at the AVR timer tutorial and saw that in the tutorial CTC mode was set first, the compare value next, and finally the prescaler. I looked into the datasheet and realized that setting the prescaler started the timer. My code set the compare value last, after I set the prescaler. I moved the prescaler settings after the compare value was set and the bins were finally 500 Hz apart. Order does matter.

I'll be moving my code off of the Arduino platform and will likely be putting this into some sort of visualization project.

Code (I left out the lookup tables [I wrote a simple Java program to create them]):

void DFT(void){
    uint16_t angle = 0;
    for(uint16_t i=0; i<Nsize/2; i++){ //each bin
        Re[i] = 0; //reset from last time
        Im[i] = 0;
        for(uint16_t j=0; j<Nsize; j++){ //each sample in the bin
            angle = (uint16_t)pgm_read_word_near(&(angleTable[i*32+j]));
            Re[i] += samples[j]*(int16_t)pgm_read_word_near(&(cosTable[angle]));
            Im[i] += -samples[j]*(int16_t)pgm_read_word_near(&(sinTable[angle])); //negative unncessary (only for consistency with complex DFT)
        }
        //Re[i] /= Nsize;
        Re[i] = Re[i]/4096; //divide by 4096
        //Im[i] /= Nsize;
        Im[i] = Im[i]/4096;
    }
}

void timerInit(){
    TCNT2 = 0;
    TCCR2A = (1<<WGM21); //CTC
    OCR2A = 125; //for 16kHz sampling
    TCCR2B = (1<<CS21); //8x prescaler
}

void adc_init(){
    ADMUX = (1<<REFS0); 
    ADCSRA = (1<<ADEN)|(1<<ADPS1)|(1<<ADPS0); //enable; 2 MHz, 8 prescaler
}

uint16_t adc_read(void){
    ADCSRA |= (1<<ADSC);
    while(ADCSRA & (1<<ADSC)); //wait for A2D conversion
    return (ADC);
}

void setup(){
    Serial.begin(115200);
    timerInit();
    adc_init();
}

void loop(){
    for(int i = 0; i < Nsize; i++){
        while((TIFR2 & (1 <<OCF2A)) == 0); //wait for next time to sample
        samples[i] = (int16_t)adc_read();
        TIFR2 = 1<<OCF2A; //clears CTC flag by writing a one to it
    }
    
    DFT();
  
    uint16_t mag = 0;
    for(uint8_t j = 1;j<Nsize/2; j++){ //ignore first bin since it only contains the dc bias
        mag = sqrt(Re[j]*Re[j] + Im[j]*Im[j]);
        Serial.print(mag);
        if(j!=Nsize/2-1)    Serial.print(",");
    }
    Serial.println();
}

Helpful Links:
DFT Explanation
DFT on AVR Example
Hearing Test Video (for creating sine waves)
Data Visualization (I modified this to show the values of the DFT from the Arduino)
AVR Freak's Timer and ADC tutorials
ATmega328 Datasheet
Op-amp Circuit (for shifting an audio signal to 0-5 V)