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

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

Self-starting inverter

Image
In this article, I will explain a circuit that can be used to automatically start an inverter when a load is connected to it and turn it off once the load is disconnected. This circuit works by biasing the output of the inverter with a low-current signal from the battery and waiting for a change in that signal. The circuit then uses a current transformer to monitor the current through the load. If there is no current in the load for a few seconds, the inverter is switched off. The inverter The inverter I am using is a modified square wave inverter. The voltage between the live and neutral terminals at the output looks like this: However, this diagram misses out on an important fact: the neutral of the output is not connected to the negative battery terminal. In fact, the modified square wave is generated by alternately switching the live and neutral terminals of the output to an internal high-voltage rail. As a result, both live and neutral are always positive relative to the nega
Read more