From Equation to Code


Both periodic signals and digital signal generation are well defined mathematically and the necessary equations can be found in any DSP text. What is not always well described in those texts, and may at first seem incomprehensible, is how to convert those equations into a working synthesizer program. As you will see, the program functions are usually short and simple. A few general rules for conversion can be developed that will work in almost all situations.

Many algebraic equations can be directly converted into program steps. In general, we replace the variables in the equations with program variables and convert the operators into the program equivalents. For some equations, especially periodic functions and series, we must write several statements to implement the equation.

For basic operators, such as addition, subtraction, multiplication and division, we can replace the operator in the equation with the programming language equivalent. Some operators used in the equations may not be defined by the programming language, but are usually available as a library function. For example, exponentiation of the form y=an is implemented in C++ as y=pow(a,n). Likewise, trigonometric functions and logarithms convert into built-in function calls, usually with the same name. Some symbols used in mathematics don't have a direct equivalent in most programming languages and we must write a series of statements to implement them. For example, summation (∑) must be implemented by a loop. 

Many signal processing equations involve a series. Although the series can be calculated directly, when possible we should convert a series to a recursive form. The recursive form will almost always produce a more efficient program. Conversion from the algebraic to recursive form is done by expanding the series, regrouping the terms, and substituting a group with a prior value. For example, consider a simple arithmetic series y = nx, n=0...m. This is converted by first expanding the series for each successive value of y.

y0 = 0
y1 = x
y2 = x + x
y3 = x + x + x

We then group terms and substitute the equivalent prior value, and reduce to the general recursive form:

y3 = x + (x + x) = x + y2
yn = x + yn-1

The original form of the equation can be implemented as:

for (n = 0; n < m; n++)
    y = n * x;

while the recursive form is:

y = 0;
for (n = 0; n < m; n++)
    y += x;

or, if we need to store the whole series of values:

y[0] = 0;
for (n = 1; n < m; n++)
  y[n] = x + y[n-1];

The recursive form replaces a multiply operation with addition and will have better performance. A similar expansion can be done for exponential series: y = xn. Direct implementation would be: 

for (n = 0; n < m; n++)
    y = pow(x, n);

while the recursive form is:

y = x;
for (n = 0; n < m; n++)
    y *= x;

 

Links:

Dan Mitchell's Personal Website