[sdiy] analog convolution with just one multiplication cell

[cheater00 cheater00]

hi everyone,

first of all, sorry about the typos, I'm typing on my phone.

I've just stumbled upon a fairly unusual and cumbersome method of doing
convolution in pure analog. it's like a rube goldberg machine, but some
might find it fun to read, or even implement. the final design is similar
to a fixed filter bank, with an added single-quadrant multiplication cell,
and some buffers.

i have just been reading about the Schönhage-Strasse theorem:

https://en.wikipedia.org/wiki/Sch%C3%B6nhage%E2%80%93Strassen_algorithm

the article relates long multiplication with the standard algorithm to
linear convolution. basically, as you do long multiplication, in the end
you add the numbers from tge various rows, and then carry. If you do not
carry, what you get is a sequence of numbers that may not be within 0-9
(but higher), and that is the output of convolution of your two inputs with
each other, if you look at the input numbers as sequences of numbers within
0-9.

it never occured to me that the standard multiplication algorithm is a
combination of an operation that is linear in the input digits, and to see
the carry operation as a well behaved non-linearity. carry is like a hard
shaper with an overflow tank lpf.

if you manage to "uncarry" the output somehow, or not carry in the first
place, you're done. one way to do the latter might be to multiply in a
higher base. eg if your base is 100, your numbers could have digits from 0
to 99. if your input numbers have digits from 0 to 9, then multiplying two
of them together will be in the range 0-81, this needs to be scaled by the
number of digits in the smaller number. for example, when multiplying a
three-digit and four-digit number,, we will be summing three rows up:

1234
122
×
=======
123400
024680
002468
+
=======
15 0548

this means in this case you will have three numbers, each up to 9*9=81, so
their sum will be up to 243, so you need at least base 244.



one complication in this design is you will need to encode your inputs and
decode your outputs.

encoding the input signals is pretty funny. using a base where you don't
use all digits creates interesting patterns. this means you don't use all
numbers. for example, if you have base 10 numbers that only use digits from
0 to 3, then subsequent numbers from 0 to 12 (in normal base 10) will look
like this:

0: 0
1: 1
2: 2
3: 3
4: 10
5: 11
6: 12
7: 13
8: 20
9: 21
10: 22
11: 23
12: 30

i'll call the left column base ten, and the right column base four in ten.

now let's look at some signals. I'll draw signals with the time axis
pointing downwards and the amplitude pointing right. this would be how i
would draw a sinewave in this email:

o
o
oo
ooooo
ooooooo
oooooooo
oooooooo
ooooooo
ooooo
oo
o
o
oo
ooooo
ooooooo
oooooooo
oooooooo


so now let's see what encoding a signal from normal base ten to base four
in ten would look like:

input, base 10:

o
oo
ooo
oooo
ooooo
oooooo
ooooooo
oooooooo
ooooooooo
oooooooooo
ooooooooooo
oooooooooooo

output, base 4 in 10:

o
oo
ooo
oooooooooo
ooooooooooo
oooooooooooo
ooooooooooooo
oooooooooooooooooooo
ooooooooooooooooooooo
oooooooooooooooooooooo
ooooooooooooooooooooooo
oooooooooooooooooooooooooooooo

as one can see, there's a clear pattern: in base "n in m", every n codes we
add m-n codes. this can be done by using eg an adc on the input, then
adding its digital output converted to unary to that analog input.

(yes, that's just one weird thing about this design). i wonder if someone
has a better idea for how to create this non-linearity. however, this is
only for purpose of explanation, as we don't actually need to perform this
encoding in analog. this is explained further down.

it bears repeating that each digit of the input numbers is an encoded value
of the input stream, sorted by time. meaning that at each point in time,
the signal coming in carries the current time value, the value "one sample
forward", the value "two samples forward", and so on, until you get to the
kth digit, which is "k-1 samples into the future". since we only need that
for the impulse response, the actual dry signal input doesn't need that
encoding.

this has several consequences. first, the dry signal input must fit within
a single-digit number in the base we choose. however, we also have
"fractional digits", so signal fidelity is retained. second, the impulse
response - if it is fixed in time - is just a fixed control voltage; this
can be pre-calculated in digital. it can also be dialled in by hand - and
whatever you've dialled in, that's your impulse response. it'll be pretty
random but always interesting.



after we've multiplied the inputs wothout carrying we have an output that
looks like this:

3
x 231
========
693

this needs to be decoded.

we have three digits in the output, and they each represent a sequence of:
current value, next value, the value after that. so in essence, at this
point in time, we decide the current output will have 6 added to it, the
next output will have 9 added to it, and the one after that will have 3
added to it.

a good way to do this would be an adc style design.

specifically if we have eg base "32 in 1024", we can use one adc to output
eg 20 bits, and then group those into 4 groups of 5 bits, and then we can
have 4 "samples" of output, each output again by 4 dacs each with a bit
depth of 5.

however, since we're doing this in analog, we could use analog conparators
which still let through the signal unaltered - meaning it retains
"fractional codes". so our "bit depth" is actually much hugher than 5 bits.

it also bears to think about what a "sample" here means. since all signals
are continuous rather than discrete, we have the full time resolution of
the input, but our impulse response is quantised to a grid of points in
time equally spaced one after another. so this is essentially as if we
sampled the impulse response from a physical space that has features that
are multiples of (e.g.) 5 meters away from us: a wall at 5m, another at
15m, another at 20m, and that's it. the more "samples" we have, the more
spatial resolution we have.

now we can take the decoded signal and perform the final overlapping step
of convolution. this is when at the output, we get the current output, the
"next output" from the previous input, and the "next next" output from the
inout two moments ago.

we could do this by delaying the decoded outputs. so we can use a phase
shifting filter, eg a single pole filter, per each sample, and then sum the
samples up. do it with inductors, capacitors, etc. each sample gets a
single filter or "tap".

so in the end we have a multiplication cell fed the input signal and a
specially prepared cv, then a decoder, and a fixed filter bank, and a
summer. the fixed filter bank, done with RC filters, could be really small
even for moderately sized impulse responses. i have no simple design for
the decoder, but i bet one exists.

depending on how the tap delay is realized (in analog with filters, with
tape, in digital with ram) we could get different max delay times. a fully
analog tap delay will be able to create very short reverbs, instrument body
simulations, equalizers, etc. a long delay will be able to create more
noticeable reverbs.

phew, that's it. i wonder what you all think about this crazy idea.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://synth-diy.org/pipermail/synth-diy/attachments/20180905/27a5ba3f/attachment.htm>