Generating sines and decaying sines

In this article, I will describe a simple algorithm that can be used to generate sine waves and decaying sine waves of a fixed frequency without computing any trigonometric functions. This algorithm is ideal for microcontrollers, where computing sines and cosines may be inefficient and storing tables of values may be impractical. The algorithm also involves no floating-point arithmetic.

Theory

The goal of this algorithm is to produce a series of values \(s_i=\sin\left(2\pi\frac{if}{f_s}\right)\), where \(f\) is the desired frequency of the sine wave, \(f_s\) is the sampling frequency, and \(i\ge 0\) is an integer. If this series of values is fed into a DAC at \(f_s\) samples per second, then the output of the DAC would be a sine wave with a frequency of \(f\).

Recall that \(e^{j\theta}=\cos\theta + j\sin\theta\), where \(j\) is the imaginary unit. Thus, if we can compute the value of \(e^{2\pi j\frac{if}{f_s}}\), we would have not only \(s_i=\sin\left(2\pi\frac{if}{f_s}\right)\), but also \(c_i=\cos\left(2\pi\frac{if}{f_s}\right)\). Note that: $$ \frac{c_{i+1}+js_{i+1}}{c_i + js_i} = \frac{e^{2\pi j\frac{\left(i+1\right)f}{f_s}}}{e^{2\pi j\frac{if}{f_s}}} = e^{2\pi j\frac{f}{f_s}} $$ $$ c_{i+1}+js_{i+1} = \left(c_{i}+js_{i}\right) e^{2\pi j\frac{f}{f_s}} $$ If we let \(c_0=k\) and \(s_0=0\), then we will get a sine and cosine wave with amplitude \(k\). Furthermore, if the frequency and sample rate are known ahead of time, the real and imaginary parts of \(e^{2\pi j\frac{f}{f_s}}\) can be precomputed, allowing for more efficient evaluation: $$ c_{i+1}+js_{i+1} = \left(c_{i}+js_{i}\right) \left(C + jS\right) $$

Limited precision

Theoretically, we can repeat the above recursive step infinitely many times and the sine wave will still have the same amplitude. However, since the precision of the stored value of \(s_i\) and \(c_i\) is limited, precision loss will cause the sine wave to either decay or grow exponentially. Suppose \(s_i\), \(c_i\), \(S\), and \(C\) are stored as \(n\)-bit signed integers. This means that these values must be scaled up by a factor of \(2^{n-1}\) in order to take advantage of all of the bits we have. In order for the iterative formula to still be true, we must divide each value by \(2^{n-1}\) $$ \frac{c_{i+1}}{2^{n-1}}+j\frac{s_{i+1}}{2^{n-1}} = \left(\frac{c_{i}}{2^{n-1}}+j\frac{s_{i}}{2^{n-1}}\right) \left(\frac{C}{2^{n-1}} + j\frac{S}{2^{n-1}}\right) $$ $$ c_{i+1}+js_{i+1} = \frac{\left(c_{i}+js_{i}\right) \left(C + jS\right)}{2^{n-1}} $$ The division by \(2^{n-1}\) can be efficiently implemented as a bitshift.

Complex multiplication

Normally, multiplying two complex numbers would require four multiplications. However, there is a trick that can be used to reduce this to three multiplications: $$ \begin{aligned} c_{i+1}+js_{i+1} &= \frac{\left(c_{i}+js_{i}\right) \left(C + jS\right)}{2^{n-1}} \\ &=\frac{\left(c_iC - s_iS\right) + \left(c_iS + s_iC\right)j}{2^{n-1}} \\ &=\frac{\left(c_iC + s_iC - s_iS - s_iC\right) + \left(c_iS - c_iC + c_iC + s_iC\right)j}{2^{n-1}} \\ &=\frac{\left(C\left(c_i + s_i\right) - s_i\left(C + S\right)\right) + \left(C\left(c_i + s_i\right) - c_i\left(C - S\right)\right)j}{2^{n-1}} \end{aligned}$$ Instead of requiring four multiplications and two additions, complex multiplication only requires three multiplications and three additions. The values of \(C + S\) and \(C - S\) can also be precomputed.

Analysis

As the algorithm runs, loss of precision will cause the sine wave to decrease or increase in amplitude. This is because the magnitude of \(C + Sj\) is not necessarily equal to \(2^{n-1}\). This will cause the magnitude of \(c_i + s_ij\) to change by a factor of \(\frac{\sqrt{C^2+S^2}}{2^{n-1}}\) per step. For given values of \(C\) and \(S\), we expect the amplitude to have changed by a factor of \(\left(\frac{\sqrt{C^2+S^2}}{2^{n-1}}\right)^{i}\). Since the elapsed time is equal to the sample number \(i\) divided by the sampling rate, the exponential decay or growth rate is \(f_s\ln\left(\frac{\sqrt{C^2+S^2}}{2^{n-1}}\right)\). This effect can also be exploited by deliberately increasing or decreasing the values of \(S\) and \(C\). For example, a decaying sine could be used to emulate a bell sound.

With every step of the algorithm, we expect the phase of \(c_i + s_ij\) to increase by the phase of \(C + Sj\), which is equal to \(\arctan\frac{S}{C}\). Since this happens \(f_s\) times per second, the frequency is \(f=\frac{\omega}{2\pi}=\frac{f_s\arctan\frac{S}{C}}{2\pi}\)

Calculator

Use this calculator to determine and compare values of \(C\) and \(S\) for a given expected frequency and decay rate.
Precision:
Sampling frequency:
Frequency:
Decay rate: (negative for decay, positive for growth)
Value of S
00
Value of C0
0

Comments

Post a Comment

Popular posts from this blog

Improving and calibrating the capacitive water sensor

Image
In a previous article, I explained a type of water level sensor that works capactitively and therefore passes no direct current through the water. When I wrote that article, I had already made two of these sensors and installed one in each of the two sump pump wells in my basement. These sensors have been working quite well for a long time, but they have a few issues. In this article, I will describe the improvements I have made to the sensor design and how I calibrated the sensors to allow me to determine the water flow rate and the volume of water the sump pump pumps each time it comes on. Introduction The two water level sensors I installed in the sump pump wells were equipped with nRF24L01 wireless modules. They transmitted measurements every 30 seconds to a Raspberry Pi, which recorded them to a database. This allowed me to visualize the water level in the sump-pumps in real time and see roughly how often the sump pumps came on. However, the water level followed this interest
Read more

Controlling a ceiling fan and light with an Arduino

Image
In this article I will describe how a wireless ceiling fan/light can be controlled by an Arduino. I will also describe the communication protocol used by the remote control to control the ceiling fan. How the remote control works The remote control is typically mounted on the wall and has several buttons that can be used to adjust the brightness of the light and the speed of the fan, as well as a set of switches that can be used to identify the remote control. When the user presses one of the buttons, a microcontroller inside the remote control generates a stream of ones and zeros based on the setting of the switches and the button pressed. For example, the code to toggle the state of the light is 1111111111111110000011010 . Each one is then encoded as a short pulse, and each zero is encoded as a long pulse. This waveform is then output to the RF oscillator. When the output signal is high, the RF oscillator is oscillating at around 304 MHz, and when the signal is low, the oscil
Read more

Turn a buck converter module into a buck-boost converter with only two components

Image
In this article I will show how you can turn a buck converter module (like the one shown below), which can only output a voltage lower than the input voltage, into a buck-boost converter module, which can output a voltage that is either lower or higher than the input voltage. Buck converter theory The schematic of a buck converter is shown below: Link to simulation The components in the box, in addition to the feedback loop (not shown), are usually integrated into a single chip. A regular buck-converter works by switching current into the output capacitor through an inductor. When the transistor in the box is on, current can flow from the supply to the output via the inductor. The voltage across the inductor is \(V_{in}-V_{out}\) and the rate of change of the current is \(\frac{V_{in}-V_{out}}{L}\). When the transistor in the box switches off, the current in the inductor continues to flow, but now through the diode. The voltage across the inductor is \(V_{out}\) and the rate of
Read more