# Identifying 40Hz frequency shift

I have a signal that is at 4 kHz. This signal shifts by 40 Hz depending on some user input. I like to detect this change in software as fast as I can. What should be the ADC frequency I should use?

I currently plan to sample at 40 kHz and use a window of 10 ms to do an FFT to find out this shift. But before I build the system, I like to get a second opinion.

• A FFT is gross overkill and won't give you reasonable resolution without a lot of cycles. Commented Jun 9, 2015 at 11:46

To restate your problem, you have a input signal in the frequency range of 3960-4040 Hz, and want to determine this frequency on the fly. Many microcontrollers can do this quite simply.

The highest frequency of interest is 4.04 kHz, which has a period of 248 µs. That's a "long" time for even a small and cheap micro. At the other end, 1/3.96kHz = 253 µs, so you want to determine the period of the signal over a range of 5 µs. You didn't say what resolution you want, so let's say 1 part in 50, which means you can get what you want if you can measure the period down to 100 ns.

This is all quite doable in many microcontrollers, which have the ability to take a snapshot of a free running timer on a particular edge of a input signal. On 8 bit PICs, this is one of the things the CCP (Compare, Capture, Pulse-width modulation) module can do. On 16 bit PICs it's called the "Input Capture" module. Either way, you end up with a 16 bit timer snapshot every cycle of your incoming signal.

To determine the period of the previous cycle, simply do a unsigned subtract of the new capture value minus the previous. This works whether the timer wrapped around during that cycle or not, as long as the period doesn't exceed the timer's wrap time. If you clock the timer at 10 MHz, then you will get values from 2475 to 2525, with the subtract yielding the period in units of 100 ns.

You don't say what you want the freqency for, but perhaps you can use this period directly. If you really need frequency (think about it carefully, you may not), then you do the divide. Even with the micro only running at 10 MHz, you have over 2000 instruction cycles per input cycle, which is plenty for a divide. On a 16 bit PIC, you can do the divide in hardware in only 18 cycles.

Either way, I'd do a little low pass filtering on the measured periods before doing any other processing. This will make your system less susceptible to jitter and can even reduce the quantization noise a bit. Keep in mind that a band-limited 3960-4040 Hz signal can't change its frequency that fast. Apparent changes in frequency above some limit are guaranteed to be noise.

I would think that the easiest way and quickest way to note the frequency shift of the input signal is to simply measure it directly!! Here is what I would do.

Provide for a digital signal levels version of your signal. If the signal is some low level sinusoid or similar this may require some amplification and then squaring of the signal to digital signal swings.

Get yourself a simple microcontroller that has some 16 bit timers that can be gated to count the period of your input signal from rising edge to rising edge. There are a plethora of microcontrollers that can support this requirement.

With a signal that has a basic frequency of 4KHz you are dealing with a period of 0.25 msec. If you setup your microcontroller with a 16-bit timer being clocked at say 8 MHz you can count 2000 counter ticks in one period of the input signal. When the frequency of the input signal shifts up to 4.04KHz then you would be counting ~1980 counter ticks in one period of the input signal. Say that the input signal shifted down to 3.96KHz then one period of the input signal would gate the timer to count ~2020 counts.

This is really probably the fastest way to detect the frequency change within one cycle of the input signal. It is also extremely easy to achieve with even some of the simplest and lowest cost MCU components.

In the past I have used this very technique to decode a low frequency FSK signal that was sending modulated data at similar frequencies down extremely long wires without using any RF carrier. At that time some general 8051 MCU running at 8 or 16 MHz did the trick nicely. In my case with the FSK decoder it was necessary to be watching the timing of every signal period coming down the wire. As such I set up the MCU with two timers to measure the signal period on alternate cycles of the input signal. This allowed the measurement of one period to be analyzed and computed while the next period was being measured. (On older processors one could loose a number of counts in the timer if trying to re-arm the use of the same timer for each period and when dealing with only 20 counts out of 2000 that can get pretty serious).

A nice advantage of this approach is that you can detect a range of captured counts per period as a valid input range as opposed to looking for one distinct count value. This will allow for some small frequency drift to not upset your decoding of the input. Also with cycle by cycle measurement it is possible to measure the width of the FSK modulation envelope to verify that it is within the proper range for whatever protocol is in use for sending information down the wire.

All this with no PLLs, no FFTs, no filters. Just simple.

• This is a good suggestion, but it does depends on the nature of the signal he has. Zero crossing detection will modulate out of band noise into the FSK signal which will significantly degrade performance even at moderate noise levels.
– Jon
Commented Jun 9, 2015 at 11:51

The signal spectrum only extends up to 4.04kHz, so 40kHz will be more than enough as explained by the Nyquist Theorem. Note that the sampling interval resolution does not limit the frequency resolution you can detect in the signal unless you are quantising it at 1-bit. As long as the quantisation errors do not swamp your signal, twice the highest frequency component plus some anti-aliasing filter margin is all you need. Anything higher is not actually adding any useful information.

Regarding your algorithm, it seems quite excessive to do an FFT simply to extract a narrowband frequency offset. If the signal frequency is stable enough I would look at having a couple of notch filters at 4.04kHz and 4.00kHz, calculating the output magnitude from them, and using the largest one to determine where the signal is. You can use a multi-rate filter to produce an extremely efficient algorithm.

Note that this is actually mathematically equivalent to doing a DFT with up-sampling and windowing to give the required frequency discrimination, then discarding all the coefficients except the two that correspond to the notch filter locations. This is the algorithm you are essentially talking about doing, but as you have so much blank spectrum there is little point in calculating out all the other coefficients which is why a time domain solution should be more efficient.

Since you want a frequency resolution of at least 40 Hz I would think that you need a window of at least 1/40 Hz = 25 ms

Are you familiar/willing to learn Matlab (or Octave, a free Matlab clone) ? Then you could easly try this out and see what you get.

10 milliSeconds won't do. A simple FFT at 40kHz with a block size equivalent to 10 milliSeconds will give you a frequency resolution of 100Hz.

50milliSeconds will give you a resolution of 40Hz, which will just barely allow you to "see" the difference. At that resolution, there will be one "bin" between 4040 and 4000 - that's 4000, 4020, 4040.

To calculate the resolution, do this:

1. Calculate number of bins: (block length in seconds)*(sampling rate)/2
2. Calculate resolution: ((sampling rate)/2)/(number of bins)

An FFT may not be the correct choice, though. An FFT can only use block sizes that are powers of 2 (512, 1024, etc.) The bins won't line up with your desired frequencies at the needed block sizes, which will get you into having to interpolate between bins and other fun stuff.

A DFT isn't limited to particular block sizes, but is generally much slower. You could jigger block sizes to get exactly the bins you want, but it may be a lot slower to compute (more steps, more CPU cycles.)

It might be faster (from the CPU point of view) to use a much higher resolution FFT rather than a DFT with exactly the bins you want. Then, you could use the sums of selected bins to approximate the true value for 4000 and 4040.

If you are restricted in CPU cycles, you might want to look into the Goertzel algorithm. A simple microprocessor can run it and do realtime detection of selected frequencies. It can easily be tuned to give the needed separation. In the linked code, use the tandemRTgoertzelFilter method. The variable "RESETSAMPLES" can be used to control the selectivity - a higher number will separate better, but take more samples to compute.

• A common misunderstanding: You can do a FFT at any blocksize. Powers of two just happen to be the fastest and leanest to implement. I agree with you other conclusions though :-) Commented Jun 9, 2015 at 8:31
• Most FFT implementations do only use powers of 2. Some of the FFT libraries I've seen will accept any blocksize, but may switch to a DFT internally or use some other method of achieving the given block size. I'm not enough of a mathematician to argue whether or not the FFT can actually use other block sizes, I just know that it isn't generally done.
– JRE
Commented Jun 9, 2015 at 8:37
• There are fast algorithms for all powers of two and for all prime numbers. Every block-size N can be handled by doing a FFT-chain based on N's prime-factors. Most FFT-libs out there only deal with pow2 as you said, and that makes people think that pow2 is required. If you want a block-size of 1280 for example you can start with FFTs of size 5 followed by FFTs with block-size 256. That'll be faster than rounding up to the next power of two. Commented Jun 9, 2015 at 8:47
• OK. Cool. Learn something new every day.
– JRE
Commented Jun 9, 2015 at 8:48
• To be more accurate: you can do a DFT (discrete Fourier Transform) for any length input. The time-saving "collapses" that Cooley-Tukey and many enhancements thereof require powers of 2 length, or products of powers of small primes. Commented Jun 9, 2015 at 12:53

You could also use a hardware PLL (phase-locked-loop) to detect and demodulate frequency (phase) variance (FSK or frequency-shift keying) of the signal, provided you have a good carrier or reference freq. No extensive sampling, subtraction or FFT needed, and the output could be a logic state for "frequency match" and "frequency mismatch."