 ## Bluestein’s Algorithm or Fourier Transform as Linear Chirp FIR Filter. C Implementation Using the Octave GNU Tool

### 2. Introduction

##### We need to find spectral estimates for M frequencies: ##### See the Figure 1-1: Figure 2-1: The location of M frequencies for calculating the signal spectrum

##### It is required to calculate the signal spectrum for M frequencies: ##### Here the description uses the normalized angular frequency ω, which is related to the real angular frequency by the formula: ##### Bluestein has done the algorithm in the form of a FIR filter with a chirp signal as an impulse response. I described chirp signal already in the article: “Matched Filter Using Octave GNU Tool“: ##### Sampling of the signal (4): ##### Such a signal has an argument n^2. Moving on to the complex exponent, we get: ### 3. Bluestein’s Algorithm

##### Substituting (1) into (2): ##### Introducing the notation: ##### Then: ##### We use the obvious equality: ##### Substituting (10) into (9): ##### Let’s introduce a new notation for the input signal: ##### Then substituting (12) into (11): ##### It is obvious that (13) is a convolution. See the (14): ##### Then (13) can be rewritten as: ##### Thus the Fourier Transform for M frequencies from an input signal with a length of N samples can be calculated using a filter having a pulse response in the form of a chirp signal: ##### We need only the first M values of X(0),…, X(M-1) at the output of the filter (15). Also given that the input signal has a finite number of N input samples, then in this case a finite pulse response (16) of length N+M-1 samples is required. That is a FIR filter. Then (16) can be written in a simpler (refined) form: ##### (17) determines the impulse response of the filter for negative samples (negative time), which complicates the filter implementation. To correct this shortcoming we redefine (17) for positive time: ##### Then in this case (13) and (15) can be rewritten as: ##### Figure 3-1: Bluestein’s Algorithm

### 4. Estimation of the Bluestein’s Algorithm Complexity

##### Thus Bluestein’s algorithm requires: ##### On the other hand the calculation of the spectrum for M frequencies by the formula (2) requires less cost: ### 5. Bluestein’s Algorithm using Fast Convolution

##### Let’s define: ##### Thus Blustein’s algorithm with fast convolution requires: ##### Next for simplicity I will compare the algorithms only by the number of multiplications. Now let’s compare the complexity of (23) and (37). Obviously the above algorithm (Bluestein using fast convolution) makes sense to use if the condition (23) > (37): ### 6. Example of the Bluestein’s Algorithm with the Fast Convolution

##### Consider the example I used in demo SW: Bluestein_Support.m and Bluestein_float.c/h. Let us have an input signal of length N = 199 and we need to calculate the spectrum at M = 58 points: ##### See the Figure 6-1: Figure 6-1: Example. The location of M = 58 frequencies for calculating the signal spectrum

##### Using (24): ##### Now let’s check the (38): 