Please see the attachment

The Fast Fourier Transform (or FFT) is a major numerical algorithm. It belongs to the family of Fourier analysis, concerned with the way general functions may be represented or approximated

by sums of simpler trigonometric functions1.

FFT are particularly relevant to build the spectral decomposition of a sinusoidal wave. For a sinusoidal wave, the FFT returns the decomposition of the signal as a linear combination of sine functions.

In this homework, we want to study the interplay between time (e.g. for sampling), accuracy of computations and the usability of the result for further processing.

• The FFT operates over a window of the last 2n samples. As part of this homework, we provide a simulator that simulate the following system, with blocks on separate threads:

In the implementation provided, we assumed that we need N = 24 = 16 samples to compute the FFT. We assume a periodic sampling to ensure a strict compatibility with the hypothesis of the FFT algorithm. The sampling period is defined by the C macro ACQUIRE_PERIOD and

� �

� � � set to 250ms. The PROCESSING_PERIOD controls the period of activation of the block in charge of the computation of the FFT.

The system operates as follows:

• Every ACQUIRE_PERIOD, a sample is produced and stored in the buffer

• Every PROCESSING_PERIOD, N samples are read from the buffer and the FFT is computed

Question 1: What is the corresponding period of activation of the FFT Computation and Display blocks after the buffer is completely filled from a cold start? Period of activation is the interval of time between two activations. We assume that Display block can be activated iff the FFT Computation has finished its operation, i.e. it has correctly processed one set of samples (N samples). Question 2: What are the necessary conditions to allow for a correct synchronization between each block? You may express them either as OS abstractions, or in plain text. Question 3: The system is processing a data stream, from acquisition to display. Each stage is performed after the previous one has completed. One can define the end-to-end latency of the system as the time necessary to display the output after we started sampling an element. From the previous questions, propose an analytical equation that reports the end-to-end latency of the system. You may formulate a best-case and/or worst-case scenario to support your claim. An analogy to the process is package delivery. A package can be delivered when it is ready or at the end of the business day. This creates two scenarios for evaluating delays. Question 4: The quality of the results of the FFT depends on the period of sampling. The lower the period, the wider the spectrum analyzed. We aim at porting our software to the STM32F401 micro- controller, a Cortex M4 controller. The datasheet (Table 66, section 6.3.20) indicates the key parameters of the ADC. The total conversion time for the ADC consists of sampling time (ts) and bit conversion time. For example, the minimum total conversion time for 12-bit resolution is 15 cycles (3 cycles for

sampling and 12 cycles for bit conversion). At fADC = 30 MHz, 15 cycles are equivalent to 0.5 us, which matches the corresponding tCONV entry in the table.

Let us assume we plan to sample at the maximum resolution and rate with the single ADC mode, what would be the time necessary to build 16 samples?