Improved Three Bin Exact Frequency Formula for a Pure Real Tone in a DFT

• Basics
• DFT_FFT
• Tutorials

Introduction

This is an article to hopefully give a better understanding of the Discrete Fourier Transform (DFT) by extending the exact two bin formulas for the frequency of a real tone in a DFT to the three bin case. This article is a direct extension of my prior article "Two Bin Exact Frequency Formulas for a Pure Real Tone in a DFT"[1]. The formulas derived in the previous article are also presented in this article in the computational order, rather than the indirect order they were derived in.

Martin Vicanek also has a three bin formula, which is an extension of his two bin formula. It used to be in an earlier version of his two bin formula paper[2], but it seems to be removed in his latest version as of the date of this blog article. His three bin formula is used as a comparison below, but not presented.

These formulas represent a significant improvement over my original three bin formulas[3] which is the discovery I made that prompted my study of DSP and more specifically the DFT.

A System of Equations In Vector Form

The system of equations derived in the two bin case are extended to the three bin case. Instead of two arbitrary bins, $j$ and $k$, three consecutive bins are used, $k-1$, $k$, and $k+1$. Three arbitrary bins could have been used, and the equations can be easily formulated as such, but in practice the three bins surrounding the peak should be used.

The complex bin values are split into real and imaginary parts: $$ Z_k = x_k + i \cdot y_k \tag {1} $$ The same applies for $k-1$ and $k+1$.

The following vectors then need to be constructed using the bin values. Vector $\vec C$ does not depend on the bin values. $$ \vec A = \begin{bmatrix} ( x_k - x_{k-1} ) / \sqrt{2} \\ ( x_k - x_{k+1} ) / \sqrt{2} \\ y_{k-1}\\ y_k \\ y_{k+1} \end{bmatrix} \tag {2} $$ $$ \vec B = \begin{bmatrix} [ \cos( \beta_k ) \cdot x_k - \cos( \beta_{k-1} ) \cdot x_{k-1} ] / \sqrt{2} \\ [ \cos( \beta_k ) \cdot x_k - \cos( \beta_{k+1} ) \cdot x_{k+1} ] / \sqrt{2} \\ \cos( \beta_{k-1} ) \cdot y_{k-1} \\ \cos( \beta_k ) \cdot y_k \\ \cos( \beta_{k+1} ) \cdot y_{k+1} \end{bmatrix} \tag {3} $$ $$ \vec C = \begin{bmatrix} [ \cos( \beta_k ) - \cos( \beta_{k-1} ) ] / \sqrt{2} \\ [ \cos( \beta_k ) - \cos( \beta_{k+1} ) ] / \sqrt{2} \\ \sin( \beta_{k-1} ) \\ \sin( \beta_k ) \\ \sin( \beta_{k+1} ) \end{bmatrix} \tag {4} $$ Where $$ \beta_k = k \cdot \frac{ 2\pi }{ N } \tag {5} $$ The same $\sqrt{2}$ adjustment done in the two bin case is made to the equations derived from the difference of two source equations to make the variance of the difference of the random variables have the same value as the variance of a single variable. Results with, and without, this adjustment are shown below.

Solving for the Frequency Term

Once the formulas are in vector form, the three bin case is identical to the two bin case. Here are the formulas derived in the two bin case presented in computational order.

First, a unit vector is made from $\vec C$. This calculation can be done ahead of time. $$ \vec P_{k} = \frac{ \vec C }{ \| \vec C \| } = \frac{ \vec C }{ \sqrt{ \vec C\cdot \vec C } } \tag {6} $$ Second, a compromise vector in the general direction of $\vec A$ and $\vec B$ is produced. This is the simplest version. Either $\vec A$ or $\vec B$, or any linear combination (other than zeroing) will give close to the same results because the two vectors are nearly collinear and its length doesn't matter. $$ \vec D = \vec A + \vec B \tag {7} $$ Third, the projection of the compromise vector onto the plane orthogonal to $\vec C$ is found. $$ \vec K = \vec D - ( \vec D \cdot \vec P_{k} ) \vec P_{k} \tag {8} $$ Finally the actual frequency, in units of cycles per frame, can be calculated. $$ f = \cos^{-1} \left( \frac{ \vec K \cdot \vec B }{ \vec K \cdot \vec A } \right) \cdot \frac{ N }{ 2\pi } \tag {9} $$

Some Numerical Results

These tests consist of taking a sweep of frequencies from the low end of a bin to the high end. For each frequency a real pure tone is generated. The phase is swept from zero to $2\pi$. The formulas are evaluated using the same data sets. The Unadjusted column does not have the $\sqrt{2}$ rescaling.

The numbers that are shown are the average and standard deviation of the distribution of frequency errors. The Target Noise Level is the standard deviation of the added noise. The error levels are shown multiplied by 100 for better presentation.

The sample count is 100
and the run size is 4000

Errors are shown at 100x actual value

Target Noise Level = 0.100

Freq   Original        Vicanek      Unadjusted      Improved
---- -------------  -------------  -------------  -------------
4.0  -0.008  1.019  -0.014  1.036  -0.011  1.108  -0.013  1.042
4.1   0.009  0.998  -0.006  1.025  -0.002  1.052  -0.004  0.990
4.2  -0.019  1.017  -0.037  1.007  -0.032  1.002  -0.034  0.944
4.3   0.025  1.102  -0.008  0.996  -0.010  0.963  -0.016  0.906
4.4   0.011  1.231  -0.020  0.995  -0.007  0.944  -0.004  0.892
4.5   0.004  1.394  -0.048  0.990  -0.044  0.947  -0.047  0.900
4.6   0.031  1.484   0.042  0.979   0.056  1.011   0.053  0.942
4.7   0.005  1.321   0.012  1.009   0.018  1.070   0.017  0.997
4.8  -0.010  1.146  -0.003  1.003  -0.002  1.090  -0.000  1.018
4.9   0.016  1.057   0.019  1.015   0.022  1.090   0.021  1.029

Similar to the two bin case, the new three bin formulas do best when the frequency is between two bins. In constrast, my original formula does best near the bins and worse between the two bins. This is because the original formula has a fixed weighting of the three bins and the new formulas are essentially weighted by the magnitude of the bins. So when the frequency is close to the center, the original formula weighs the third bin, which has a lower signal value and thus a higher SNR, too heavily.

Conclusion

Another solid formula for the calculation of the frequency of a single pure tone from DFT bin values has been presented. Like the two bin case, there is no guarantee that it is the optimal one.

References

[1] Dawg, Cedron, Two Bin Exact Frequency Formulas for a Pure Real Tone in a DFT

[2] Vicanek, Martin, Frequency Estimation from two DFT Bins

[3] Dawg, Cedron, Exact Frequency Formula for a Pure Real Tone in a DFT

Sign in