Which frequency corresponds to which bin in the Fourier Transform?

Ok, so what I want to do is record samples with a microphone, perform a Fourier-Hartley Transform with the ArduinoFHT Library, then use the different values in the bins, which correspond to certain frequencies (right?) to perform further actions.

My problem is that I need to know which bin corresponds to which frequency.
There are 128 Bins when the FHT is performed.

I've read somewhere that the first bin corresponds to the frequency (sampling rate/2), the second to (sampling rate/4). However, I don't even know the sampling rate, plus this doesn't make sense in my opinion.

This is the example code when the FHT is downloaded. I added the for loop to print out each bin with its value.

/*
fht_adc.pde
guest openmusiclabs.com 9.5.12
example sketch for testing the fht library.
it takes in data on ADC0 (Analog0) and processes them
with the fht. the data is sent out over the serial
port at 115.2kb.  there is a pure data patch for
visualizing the data.
*/

#define LOG_OUT 1 // use the log output function
#define FHT_N 256 // set to 256 point fht

#include <FHT.h> // include the library

void setup() {
  Serial.begin(115200); // use the serial port
  TIMSK0 = 0; // turn off timer0 for lower jitter
  ADCSRA = 0xe5; // set the adc to free running mode
  ADMUX = 0x40; // use adc0
  DIDR0 = 0x01; // turn off the digital input for adc0
}

void loop() {
  while(1) { // reduces jitter
    cli();  // UDRE interrupt slows this way down on arduino1.0
    for (int i = 0 ; i < FHT_N ; i++) { // save 256 samples
      while(!(ADCSRA & 0x10)); // wait for adc to be ready
      ADCSRA = 0xf5; // restart adc
      byte m = ADCL; // fetch adc data
      byte j = ADCH;
      int k = (j << 8) | m; // form into an int
      k -= 0x0200; // form into a signed int
      k <<= 6; // form into a 16b signed int
      fht_input[i] = k; // put real data into bins
    }
    fht_window(); // window the data for better frequency response
    fht_reorder(); // reorder the data before doing the fht
    fht_run(); // process the data in the fht
    fht_mag_log(); // take the output of the fht
    sei();
    Serial.println(">>>Start");
    for (int i = 2; i < FHT_N/2; i++) { //Print out every bin with its value. The first 2 bins seem to be pink noise, which is the reason why they arent printed out.
      Serial.print(fht_log_out[i]);
      Serial.print(", ");     
    }
    Serial.println();
  }
}

Example Serial Bin Output:

60, 44, 30, 53, 32, 16, 24, 38, 43, 8, 16, 24, 27, 19, 19, 0, 42, 25, 38, 25, 19, 24, 19, 33, 16, 41, 0, 30, 16, 38, 24, 19, 30, 0, 25, 16, 24, 19, 0, 27, 8, 8, 33, 0, 0, 8, 8, 30, 8, 25, 19, 16, 16, 25, 0, 16, 8, 33, 19, 19, 8, 27, 0, 8, 27, 0, 0, 33, 8, 0, 0, 19, 16, 0, 0, 0, 8, 19, 8, 27, 0, 0, 25, 8, 8, 8, 0, 25, 0, 16, 0, 19, 19, 19, 16, 8, 16, 19, 0, 8, 35, 19, 19, 16, 0, 30, 8, 0, 19, 19, 0, 19, 8, 16, 0, 8, 19, 8, 0, 0, 16, 0, 19, 0, 0, 0,

Thanks for your help

However, I don't even know the sampling rate, plus this doesn't make sense in my opinion.

So despite your opinion this is correct and so without knowing the sampling frequency you can’t calculate what frequency range is in what bin.

Also it is not as simple as that because you get bleed through into adjacent bins caused by your sample period not being a whole cycle of all the waveforms. That is the start and end points in a sequence of samples must begin and end at the same point.

This is mitigated by applying a window function but it does not totally remove the effect of having a glitch if the input buffer were to be repeated.

then use the different values in the bins, which correspond to certain frequencies (right?) to perform further actions.

It is not as simple as that either, due to noise and harmonics there will always be values in all the bins. The output means nothing without knowing what your input waveform was.

The center frequency of each bin is nominally i*Fs / N where i is the index in your print loop, Fs is the sample rate, and N is the number of samples in the transform.

Thus the i=0 bin is nominally 0 Hz or (mostly) the DC offset of the input signal. Per the Nyquist sampling theorem the magnitude of the i-th bin and the N - i-th bin will have the same power for real valued input signals.

Fs in your code is roughly 9615 38461 Hz which is the continuous sample rate of the ADC with the standard Arduino ADC clock divider setting prescaler setting of 32. N is your FHT_N = 256.

MrMark:
Fs in your code is roughly 9615 Hz which is the continuous sample rate of the ADC with the standard Arduino ADC clock divider setting. N is your FHT_N = 256.

Since my ADC is running in Free Running Mode, the sample rate is higher no?
http://www.optiloading.be/willem/Arduino/speeding.pdf here it reads that it's a 76.8 KHz sampling rate. So a eightfold increase in speed.

What is making the bulk of the difference is reducing the prescaler to 16. I have found that the accuracy tends to drop off with a prescaler under 32, so while it might appear faster there is a lot more noise in the result.

Grumpy_Mike:
What is making the bulk of the difference is reducing the prescaler to 16. I have found that the accuracy tends to drop off with a prescaler under 32, so while it might appear faster there is a lot more noise in the result.

Can you tell me where/how to change this prescaler?

brateboi:
Since my ADC is running in Free Running Mode, the sample rate is higher no?
http://www.optiloading.be/willem/Arduino/speeding.pdf here it reads that it's a 76.8 KHz sampling rate. So a eightfold increase in speed.

Free Running Mode just means the ADC starts the next conversion as soon as the previous one is complete. The conversion rate is determined by the prescaler setting which is in the ADCSRA register. In the setup portion of the original post ADCSRA is set to 0xE5. The prescaler is the three LSBs of ADCSRA, so it is set to binary 101. This is a prescaler value of 32 vs the default Arduino setting of 128.

The conversion speed, assuming a 16 MHz Arduino, is 16e6 / (13 * prescaler) or 16e6 / (13 *32) = 38461.5 Hz in the OP.

See this for full description of ADC registers: http://maxembedded.com/2011/06/the-adc-of-the-avr/

Now it makes sense. Basically, in my case its scaled linearly from 0Hz (first bin) to 19230Hz (last bin -> 128*38461/256). Middle bin being somewhere of 9600Hz.
This scaling makes absolutely sense as we hear from about 20Hz - 20000Hz.

Thanks a lot MrMark for your useful information.

brateboi:
Ok, so what I want to do is record samples with a microphone, perform a Fourier-Hartley Transform with the ArduinoFHT Library

FHT = Fast Hartley Transform, not Fourier Hartley... Hartley and Fourier transforms are two different transforms.