Convolution DSP

[Moderator note: Topic split from http://forum.audacityteam.org/viewtopic.php?p=186807#p186807 ]

Yes, and my language is sometimes teribly faulty too.
Anyway, here’s some code that excessively uses the “convolve”-function. Its fun to play with. the Kernel-function is loosely based on a basic listing from chapter 16 in Steven W. Smith’s book

The Scientist and Engineer’s Guide to
Digital Signal Processing

http://www.dspguide.com/ch16.htm

There could a lot of other window-functions be implemented, and with dtf, the calculation time will be 100 times faster.
Apropos terrible slowness, is there any way to measure the speed of a code execution? a System function or variable, that can be read out? That’s maybe something for the Nyquist-Xmas-wishlist.

``````(set-sound-srate *sound-srate*); reset environment
;; Converts a list into a sound
;; Either a list or the unquoted sample-values can be given
(defun s-list (samplerate &rest args)
(let*
((samples (if (listp (car args))
(car args) args))
(vec (eval (read (make-string-input-stream (format NIL "#~a" samples))))))
(snd-from-array 0 samplerate vec)))
;;
;; returns a filter-kernel of length m (+1) for convolution
;; m (even) determinates the roll-off quality and behaviour.
;; f-cut is the cut-off-frequency from 0.0  to 0.5
;; where 0.5 is half the sample-rate (e. g. 22050 hz)
;; If :Hp is true, the filter is highpass, otherwise lowpass.
(defun kernel (f-cut m &key hp (win t)  &aux h-t i (sum 0))
(setq m (* (truncate (/ m 2)) 2))
(dotimes (cnt  (1+ m))
(setq i (float cnt))
(if (= (- i (/ m 2)) 0)
(setf h-t (cons
(* 2 pi f-cut
;; multiply with Hamming-window or 1 (=square)
(if win (- 0.54 (* 0.46 (cos (/ (* 2 pi i) m)))) 1.0)) h-t))
(setf h-t (cons
(* (/ (sin (* 2 pi f-cut (- i (/ m 2)))) (- i (/ m 2)))
;; multiply with Hamming-window or 1 (=square)
(if win (- 0.54 (* 0.46 (cos (/ (* 2 pi i) m)))) 1.0)) h-t)))
(setf sum (+ sum (car h-t))))
;; normalize so that the sum is 1 (LP) or 0 (HP)
(if hp
(progn (setq sum (- sum))
(setf (nth (truncate (/ m 2)) h-t )
(+ (nth (truncate (/ m 2)) h-t) sum))
nil)); nothing to return from progn
;; increase temporarily precision for conversion
(progv '(*float-format*) '("%#.21f")
;(print sum)
;(print (nth (truncate (/ m 2)) h-t))
(mult (/ sum)(s-list 44100 h-t))))
;;
;; test our code
(setf sig (mult 0.1 (noise 1.5)))
(setq k-len 750)
(setq freq 1320)
(setq cutoff (* freq (/ *sound-srate*)))
(setf LP (kernel cutoff k-len ))
(setf HP (kernel cutoff k-len :hp t ))
(setf BP (convolve LP HP))
(setq norm (/ 0.3 (peak bp ny:all)))
(setf BP-sq (convolve (kernel cutoff k-len :win nil) (kernel cutoff  k-len :hp t :win nil)))
(setf norm2 (/ 0.3 (peak bp-sq  ny:all)))
(seq
sig
(convolve sig LP); Lowpass
(convolve sig hp); Highpass
(mult norm2 (convolve sig bp-sq)); Bandpass & square-window
(mult norm (convolve sig bp)); Bandpass & hamming-window
;;; "abuses" convolution as a correlation at *control-srate*
(mult 0.1 (convolve sig (lfo (/ freq 20))))
(stretch 1.5  (mult 0.2 (hzosc freq)))); control tone
``````

No worries, your writing is clear and comprehensible.

Not that I know of, but if a piece of code is particularly slow it is often possible to devise a simple test to compare the speed of alternative versions of the code.

Interesting code snippets. I’ve not done much with dft (or fft) but yes a dft function would probably be a nice addition.

A little convolution experiment that I did a while ago - it’s a simple (but very slow) reverb:

``````(defun reverb (s-in mix bw)
(setf response (abs-env
(sum 1 (mult -1 (s-min 1 (mult 100 (snd-abs (noise 1.4))))))))
(setf env  (abs-env (pwlv 1 0.1 0.4 0.2 0.25 0.3 0.125 0.4 0.06 0.5 0.03 0.7 0.015 0.8 0.008 0.9 0.004 1 0)))
(setf response (mult env response))
(sim
(mult (- 1 mix) s-in)
(mult mix (lp (convolve s-in response) bw))))

;; (reverb sound mix bandwidth)
(multichan-expand #'reverb s 0.3 2000)
``````

Well, I am sure, this code could be transferred to fft. There are already some functions defined. Alas, this whole object-oriented programming gives me headaches and all sorts of pain. I am writing code very intuitively and this exchange of messages and answers is not my thing. My IT-Teacher in school, 30 years ago was a mate of Niklaus Wirth, http://en.wikipedia.org/wiki/Niklaus_Wirth the Inventor of Pascal and Modula and so we could all day long define constants and variables in order to produce a endless loop, that prints “Hallo Welt…”.
I prefer to program within a easy language, where you get an immediate result (without compiling and linking and so on). Five minutes for code writing and a week long bug-searching, that is it…
The other question is whether fft yields the proper results on my 64-bit machine or if there’s still a bug lingering on. I am still waiting for a convolution (-reverb) plug-in that is accessible. Thats why I’ve begun to learn Nyquist in the first place.
I am recently trying to write some oscillators that produce fractal noise, that can afterwards be used as impulse responses in a Convolution plug-in. See http://forum.audacityteam.org/viewtopic.php?f=39&t=66957
But as usual, I found some bugs beforehand, so I didn’t get very far yet.

I’ve recently started looking at that side of Nyquist and I know exactly what you mean (though it can give tremendous speed improvement over Lisp loop structures).

This came up a while ago.

There’s two issues here:

Yes there’s a bug in Nyquists FFT function on 64 bit machines. Nyquist assumes a 32-bit architecture.
Roger Dannenberg is aware of the problem but it doesn’t appear to be an easy fix.
You’ll find some information about it here: http://bugzilla.audacityteam.org/show_bug.cgi?id=336

FFT was updated in Nyquist a while ago but the documentation wasn’t, so there are examples in the documentation that do not match the current version of FFT (for example the figures in this FFT tutorial are not what happens now: http://www.audacity-forum.de/download/edgar/nyquist/nyquist-doc/examples/rbd/03-fft-tutorial.htm )

FFT seems to work on 32 bit systems correctly as far as I can tell because performing IFFT on FFT data produces the expected results. I’ve abandoned looking at FFT any further until it is correctly documented as I just don’t know enough about it to work out what should be happening without documentation.

Let’s face some facts:

• convolution is slow
• it calculates, even if the argument is 0
• the response can’t be greater than 100000 samples
• fft is complicated and may not work on all machines

I’ve stumbled over an interesting alternative. Let us say that we want to produce a reverb according to a delay-line we provide as IR, then the following code will produce the exact same result:

``````(setf sig (snd-from-array 0 44100 (vector 2 3 4)))
(setf ir  (snd-from-array 0 44100 (vector 1 0 0 0 1 0 0 1 0 1)))
(print (snd-samples (convolve sig ir)ny:all))
(print (snd-samples (trigger ir sig) ny:all))
``````

Certainly, the trigger-function was never intended for such an application, but who cares? I’ve started to write a simple reverb function and it looks promising (in comparison to convolution a dozen times faster). There are of course also some drawbacks.
the example above wouldn’t produce the same results, if we chose other values than 1 in the IR-signal, since trigger puts allways the original sig in the result and doesn’t multiply it with the actual value in IR. But there are also some workarounds. As an example:
For a convolution, we would multiply our delay line with noise to produce a random result.
For trigger, we would multiply the sig with a real random number to get the same result. The last two lines would be as follows:

``````(print (snd-samples (convolve sig (mult (noise) ir))ny:all))
(print (snd-samples (trigger ir (mult (real-random -1.0 1)sig)) ny:all))
``````

Hopefully, I can soon post a more sophisticated code example.

Let’s try to adapt the trigger trick to Steve’s function from above:

``````(defun reverb (s-in mix bw)
(setf response (abs-env(sum 1 (mult -1 (s-min 1 (mult 20  (snd-abs (noise 1.4))))))))
(sim
(mult (- 1 mix) s-in)
(mult mix (lp (trigger response
(mult (real-random -0.1  0.1)s-in)) bw))))
(reverb s 0.3 300)
``````

It took about 15-20 seconds for 1 minute of speech to calculate, thats a huge progress (convolution needed 40 seconds for 6 sec sound…). Besides, I raised the resolution by a factor of 5, that’s the number 20 in the response definition (is that right steve?.
I had to omit the envelope, because this won’t work in the same way. Instead, we could either change the distribution in the noise response (sweeping bandpass or so) or construct a lookup table for the real random numbers. Feel free to experiment.

Unfortunately (mult (real-random -0.1 0.1) s-in)) is not evaluated each time it is triggered. It is evaluated once at the start only.

I don’t know exactly what you mean. As far as I can see, real-random is each time evaluated anew. If this wasn’t the case, the code from above would produce the same number triple at the first and the fifth place.

``````(setf *float-format* "%#.1f")
(setf sig (snd-from-array 0 44100 (vector 2 3 4)))
(setf ir  (snd-from-array 0 44100 (vector 1 0 0 0 1 0 0 1 0 1)))
(print (snd-samples (convolve sig (mult (noise) ir))ny:all))
(print (snd-samples (trigger ir (mult (real-random -1.0 1.0) sig)) ny:all))
``````

trigger means, (mult (real-random … is evoked each time the IR changes from <= 0 to a positive number. That’s 4 times the case (sample before start is also 0), so 4 random numbers are produced and multiplied with our signal (which consists of 3 numbers). convolve doesn’t behave differently, because we’ve multiplied IR with noise and only the 4 samples with value 1 are modified or to be exact, weighted.
We could of course multiply sig every time with noise, but this would destroy the original signal (only zero crossings remain). Mixing in a random signal may produce interesting effects but it slows down the calculation. It’s probably more appropriate to apply a Lp filter to the signal because that’s how reflections act in nature. They are attenuated at high frequencies, the more the longer they travel.

You’re right.
Sorry about that, I did some tests last night that suggested the opposite, but it was very late, and running some new tests today confirms that it is re-evaluated on each instance. (not sure what I did wrong last night

Taking your first example where SIG is a behaviour: (snd-from-array 0 1 (vector 2 3 4))
we can see that it works as expected:

``````(setf sig (snd-from-array 0 1 (vector 2 3 4)))
(setf ir  (snd-from-array 0 1 (vector 1 0 0 0 1 0 1)))

(print (snd-samples (trigger ir sig) ny:all))
``````

(any sample rate will do here as long as it’s the same for IR and SIG, so “1” for simplicity)

The sound SIG is triggered each time that IR rises above zero.
For each value of IR we get the following table:

``````1 2 (SIG triggered)
0 3
0 4
0 0
1 2 (SIG triggered)
0 3
1 6 (SIG triggered, 4+2)
nil 3
nil 4
``````

Modify the code a little:

``````(setf sig (snd-from-array 0 1 (vector 2 3 4)))
(setf ir  (snd-from-array 0 1 (vector 1 0 0 0 1 0 1)))
(print (snd-samples (trigger ir (mult (rrandom) sig)) ny:all))
``````

Example of returned values:
#(1.1301 1.69515 2.2602 0 1.29829 1.94744 4.45808 2.79224 3.72299)

``````1 1.1301 (SIG triggered)
0 1.69515
0 2.2602
0 0
1 1.29829 (SIG triggered)
0 1.94744
1 4.45808 (SIG triggered, 4+2)
nil 2.79224
nil 3.72299
``````

We can calculate the value of (rrandom) by dividing the returned value from the second table by the returned value from the first table:

``````1.1301 / 2 = 0.56505
1.69515 / 3 = 0.56505
2.2602 / 4 = 0.56505
0 / 0 not defined
1.29829 / 2 = 0.649145
1.94744 / 3 = 0.649146667
4.45808 / 6  - this is actually (4 * r1) + (2 * r2)
2.79224 / 3 = 0.930746667
3.72299 / 4 = 0.9307475
``````

Looking at the 7th value, we can see that r1 = 0.649146667 and r2 = 0.930746667
(4 * 0.649146667) + (2 * 0.930746667) = 4.458080002

I’ll split this to a new post as it’s getting rather long.

Now trying it with a “real” sound.

I created a track with the sample rate set to 1 Hz then ran this code to generate a sound with 3 samples, values 0.1, 0.5 and 0.9

``````(snd-from-array 0 1 (vector 0.1 0.5 0.9))
``````

Then modifying the trigger code to use that sound:

``````(setf ir  (snd-from-array 0 1 (vector 1 0 0 0 1 0 1)))
(print (snd-samples (trigger ir (mult (rrandom) (cue s))) ny:all))
``````

and the results:
#(0.098681 0.493405 0.888129 0 0.0969973 0.484987 0.904319 0.156715 0.282086)

``````0.098681 / 0.1 = 0.98681
0.493405 / 0.5 = 0.98681
0.888129 / 0.9 = 0.98681
0 / 0
0.0969973 / 0.1 = 0.969973
0.484987 /  0.5 = 0.969974
0.904319 / 1
0.156715 / 0.5 = 0.31343
0.282086 / 0.9 = 0.313428889
``````

So all looking good

So now trying it with “normal” sounds with a sample rate of 44100 Hz.
For this I generated a short click track and used the following code:

``````(setf sig s)
(setf ir  (abs-env (osc (hz-to-step 10) 0.3)))
(trigger ir sig)
``````

IR gives three predictable triggers at t=0, 0.1 and 0.2

The result is as expected, each click occurs three times.

So now to do something a bit more interesting and give the echoes an “decay envelope”:

``````(setq pk 1)

(defun env ()
(case pk
(1 (setq pk (* pk 0.7)) 1)
(T (setq pk (* pk 0.7)))))

(setf sig s)
(setf ir  (abs-env (osc (hz-to-step 10) 0.5)))
(trigger ir (mult (env) sig))
``````

Or we can give it a more interesting trigger signal.
Using a low-pass filter on noise reduces how often it crosses zero.
(abs-env) is required so that the signal IR does not get stretch to the same duration as the selection.
We probably want an initial pre-delay, so we can add a bit of silence to the beginning of the noise.

Example IR signal:

``````(setf ir (abs-env (mult
(pwlv 0 0.02 0 0.02 2 1 2)
(cue (lowpass8 (abs-env (noise 1)) 500)))))
``````

And a bit of tweaking to the trigger code:

``````(setq pk 1)

(defun env ()
(case pk
(1 (setq pk (* pk 0.2)) pk)
(T (setq pk (* pk 0.98)))))

(setf sig s)
(setf ir (abs-env (mult
(pwlv 0 0.02 0 0.02 2 1 2)
(cue (lowpass8 (abs-env (noise 1)) 500)))))

(sim s (trigger ir (mult (env) sig)))
``````

A pretty neat little function, isn’t it? Once you got the hang of it you’re going to be addicted to it. It offers a whole bunch of new possibilities. you can control a whole decay line with echoes at the start and any combinations of allpass or comb filters at the end. You could also think of a granular synthesis, where trigger separates the original signal into little pieces i. e. it gives you the indices, which can be read out by sref-inverse and on and on (the only limit is one’s patience in applying complicated functions…). I’ll try your code when I’ve got the time.

It’s neat, and certainly an inventive use of the trigger function, but it doesn’t seem to be noticeably faster than a conventional DO loop.

For example, in the final example from my last post, there are probably around 300 random triggers in 1 second.
Converting this to a conventional DO loop would be something like:

``````(setq pk 1)
(defun env ()
(case pk
(1 (setq pk (* pk 0.2)) pk)
(T (setq pk (* pk 0.98)))))

(setq time 0.02)
(setf sig s)
(do ((i 0 (1+ i))
(time 0.02 (+ time (/ (rrandom) 150))))
((= i 300) sig)
(setf sig (sim
sig
(at-abs time (cue (mult (env) s))))))

sig
``````

Both code snippets run at about the same speed on my machine, and create very similar effects.
(also, this version will work with stereo tracks)