Question

The exercises for the lecture Real-Time Systems concern approaches from hardware-related software development, in particular performance-optimized software development. For this purpose, a problem is set here in which a partial algorithm for calculating a discrete Fourier transformation is implemented accordingly. The discrete Fourier transform (DFT) calculates the frequencies inherent in a function over time. One can imagine that a tone, e.g. of a musical instrument, is recorded and then – after the recording – analyzed, which fundamental tones (= "height of the tone") and which harmonics (= "timbre") are contained in it. The discrete (and fast) Fourier transform (DFT, FFT) are now suitable algorithms to perform this via digital computer. The DFT now uses the sine and cosine functions and can therefore be implemented classically with floating point data types (float, double). However, the calculations with such data types are very timeconsuming if no hardware support (co-processor) is available. Especially in embedded systems, this is often missing, and for performance reasons one likes to choose the implementation in the form of integer data types. This is exactly your task: to find a solution for the integration of the sine and cosine functions for integration into algorithms that compute with data exclusively in integer format. To anticipate it right away: A simple "casting" like x = (int)(100. * sin ( y )) is NOT sufficient at all, because this only means that first in double format is calculated and then converted to Integer. However, they should replace the invoice itself. In detail:

Task 1: Capture the algorithm behind the discrete Fourier transform. As a basis, you can find some information in the script "Embedded Systems Engineering Manual V0.67", which is available for download on the server, but please use more information to understand the algorithm.
Task 2: Please focus exclusively on the implementation of the sine and cosine functions in integer format. For the calculation of the DFT, it is assumed that the fundamental vibration has a maximum period of 2048 measuring points. Thus, you need the sine function with a period of 2048 points, but you must also be able to calculate a sine function with e.g. 977 or 638 points as a period. Please discuss your approach to calculating such a function with varying scores with as little effort as possible. Accuracy is considered to be a precision of 16 bits in the function values.
Task 3: Please now implement the calculation of the sine and cosine functions for any number of points (< 2048) per period and test your implementation so that the error does not exceed +/- 1 lsb

Answer 1

remember to rephrase!

Step-by-step explanation:

Task 1: The discrete Fourier transform (DFT) is an algorithm used to convert a discrete time signal from the time domain to the frequency domain. The goal of the DFT is to determine the amplitudes of different frequency components present in a signal. The algorithm behind the DFT is based on the fact that any periodic signal can be represented as a sum of complex exponentials. The time domain signal is first multiplied by the complex exponential function exp(-jt2pif), where t is the time, f is the frequency, and j is the imaginary unit. The result of the multiplication is then summed over all time values, which yields the frequency domain representation of the signal. The DFT is used in various applications such as signal processing, communication, and control systems.

Task 2: To implement the sine and cosine functions in integer format for the calculation of DFT, we need to replace the floating point calculations with integer operations. One approach is to use a lookup table to store the values of the sine and cosine functions at specific points and then use interpolation to obtain the values at other points. For instance, we can pre-compute a table of values for sine and cosine functions with a period of 2^N points (where N is a positive integer) stored in two separate arrays. We can then use linear interpolation to calculate the values of the functions at any point between 0 and 2^N-1. However, this approach requires a large amount of memory for larger N values, which can be impractical for embedded systems.

Alternatively, we can use a numerical approximation of the sine and cosine functions based on a series expansion. For example, we can use a Chebyshev series expansion to approximate the sine and cosine functions with a desired accuracy. Chebyshev series can be obtained by evaluating the Chebyshev polynomial at specific points and summing the terms of the corresponding Chebyshev series. The advantage of using a Chebyshev series expansion is that it requires fewer operations than other series expansions, such as the Taylor series, and only a small number of terms are required to obtain the desired accuracy.

Another approach is to use the CORDIC algorithm, which is a simple and efficient algorithm for numerically evaluating trigonometric functions. The CORDIC algorithm uses a sequence of shifts and additions to construct a rational approximation of the trigonometric function. It is particularly useful in implementations that do not have the floating-point multiplication instruction. The CORDIC algorithm can be implemented as an integer program with a small number of multiply-add operations, making it an efficient choice for implementing trigonometric functions in embedded systems.

Task 3: To implement and test the calculation of the sine and cosine functions for any number of points (< 2048) per period, we can use one of the above mentioned approaches. We will start with the CORDIC algorithm as it is simple and efficient.

First, we need to determine the number of bits required to store the result. The maximum value of the sine or cosine function with a period of 2048 points is approximately 1962. If we want to obtain a precision of 16 bits, we will need a 32-bit integer to store the result.

Next, we need to find the number of multiply-add operations required for the CORDIC algorithm. The CORDIC algorithm uses a sequence of shifts and additions to construct a rational approximation of the trigonometric function. The number of multiply-add operations required for a single trigonometric calculation can be bounded by the number of bits required to store the result. Therefore, we need 32 multiply-add operations to calculate the sine or cosine function with a period of 2048 points.

If the period of the function is smaller than 2048 points, we can simply use a smaller number of bits to store the result. If the period of the function is greater than 2048 points, we can use the same approach as before, but with a larger number of bits to store the result.

To test the implementation, we need to ensure that the resulting values are accurate and that the error does not exceed +/- 1 lsb. We can generate a random sequence of periods and apply the CORDIC algorithm to calculate the sine and cosine functions for each period. Then, we can compare the results with the actual values of the sine and cosine functions and verify that the error Does not exceed +/- 1 lsb.