10 ms·

Can an electric circuit do recursion?

105 points by dustingetz 4y ago

imglorp 4y ago
Not exactly a circuit, but a coworker once wrote a recursive macro in VHDL that would generate a unanimous vote detector (an N-input AND gate) from a cascade of 2-input AND gates.
- xodjmk 4y ago
  How is this not a circuit? Those AND gates will be built out of multiple transistors that require VCC and GND and current etc. It's absolutely a circuit.
mikewarot 4y ago
Positive feedback loops are recursion, in many cases the skill in electronics engineering is avoiding positive feedback. Sometimes you can use a bit of positive feedback to suppress noise, as in a Schmidt trigger, which is bistable. Sometimes you can use it under manual control as in a Super-regenerative receiver. Mostly, it is used in oscillators to produce sine waves.
- dreamcompiler 4y ago
  In that sense negative feedback is recursion too because it's taking part of the output signal and feeding it back into the input again. Negative feedback is closer in spirit to a typical recursive function where you often want each iteration to process a "smaller" argument than the last and thus be closer to some fixed point.
  - mikewarot 4y ago
    I do vaguely recall that the first time I saw an OP-amp circuit it seemed insane. It's only after you learn about negative feedback, and forcing a virtual ground that you can work with the things and not think they're black magic. That was decades ago, I'd forgotten about it.
- ilyt 4y ago
  > Mostly, it is used in oscillators to produce sine waves. Well technically to get sine you need a gain of exactly 1, anything above that will increase distortion. Now to get it to start oscillate in the first place you need above 1 so old school low distortion sine generators usually have some kind of automatic gain control
  - mikewarot 4y ago
    Once upon a time, the #47 panel lamp served that function.
- namibj 4y ago
  Also useful to reduce drive power in hard-switched field-effect-device cascodes: with some mild tricks, stacked cascodes in particular benefit from compensating miller effect with positive feedback. It still all falls down again when the bottom node/switch is turned back on, and the only arguably difficult part is minimizing the extend of damping needed to prevent the positive feedback from oscillating, like it happily does with inductive load. The approach appears to be of relevance for MVDC power supply applications, as well-compensated capacitances in a stacked cascode can minimize driving/switching power in hard-switched SiC JFET based switches (at around 1~2 kV per JFET, stacked as high as needed), with usefully low loss up to the MHz range of e.g. PWM frequencies. Switched capacitance converters obviate the need for poorly-scaling higher-frequency magnetics, at the mild cost of needing some more switches (only divide-by-2 seems to be truly effective/ideal, while transformers can do arbitrary ratios), and the arguably massive gain of power density reachable in below-substation power classes (pole transformers, up to electric trains, the latter benefitting especially from skipping both the transformer and the AC filtering needs w.r.t. power-to-weight aspects).
- mikewarot 4y ago
  It took me a while to find it... but here it is, a motor generator that can give a gain of 10,000 or more using a bit of recursion https://en.wikipedia.org/wiki/Amplidyne https://en.wikipedia.org/wiki/Amplidyne ----- An earlier circuit that gets gain out of Motor Generators is the Ward-Leonard control https://en.wikipedia.org/wiki/Ward_Leonard_control https://en.wikipedia.org/wiki/Ward_Leonard_control At the US Steel works in Gary, Indiana, they have a 6 stand cold rolling mill. This uses pairs of 19,000 Horsepower motors on each stand to pull a cold slab of steel 6 inches thick like taffy to reduce its thickness. The electronics of the day (early 1960s) couldn't drive things directly, but they did have SCR packs big enough to drive the fields of DC generators in the Ward-Leonard configuration. I rebuilt many of those SCR packs in the 1980s.
bfung 4y ago
The key insight is that a recursive function can be transformed into an iterative function. From there, convert the iterative function to a circuit w/clock cycles.
- anonymousiam 4y ago
  Discreetization (what you are referring to) always involves loss, and, rather than instantly getting the "correct" result from your calculations, you will need to wait for enough clock cycles to progress until the remaining error value is less than the (ever present) noise.
dreamcompiler 4y ago
Logic gates are not recursive i.e. you typically don't feed a gate's output back to its input. Gates are asynchronous and stateless; their outputs only change when their inputs change and they don't retain information. But if you do feed gate outputs back to their inputs (usually indirectly), then it's a recursive circuit and now it can remember state. This is called a flip-flop, or single-bit memory. https://en.m.wikipedia.org/wiki/Flip-flop_(electronics) https://en.m.wikipedia.org/wiki/Flip-flop_(electronics)
- userbinator 4y ago
  then it's a recursive circuit and now it can remember state. ...or oscillate, depending on the phase of the feedback: https://en.wikipedia.org/wiki/Ring_oscillator https://en.wikipedia.org/wiki/Ring_oscillator
  - deleted 4y ago
    [deleted]
0b01 4y ago
The simplest mutual recursion is a Set-Reset flip flop circuit.
contingencies 4y ago
Intermediate electronics designer here, not classically trained, coming from software (also not classically trained). I would say absolutely. If we define recursion as the deterministic variance of function output over time, given a single known input, then for a given circuit-implemented function simply use a timer to take the output of that function and feed it in as input thereafter. Gotchas: this probably requires state buffering, and the control flow implications with respect to parallelism and synchronization are essentially why we have MCUs.
kilgnad 4y ago
People are talking about logic gates and computing. While these things are associated with electric circuits, strictly speaking, they don't have to be. It's sort of a separate domain all together. For something strictly an electric circuit that uses recursion take a look at an op-amp: https://en.wikipedia.org/wiki/Operational_amplifier https://en.wikipedia.org/wiki/Operational_amplifier. Normal operation of an op amp basically involves a feedback loop which is the analog equivalent of recursion. Basically anything with a feedback loop is recursion.
- elevaet 4y ago
  Resonant filters, like the classic Moog ladder filter, are another great example of recursive/feedback circuit designs. As someone coming from a computing background, it always seems magical how the recursion in these types of analogue circuits happens instantaneously.
  - raverbashing 4y ago
    > how the recursion in these types of analogue circuits happens instantaneously. Yeah, theoretically instantaneous, in practice not. (There's a measure for that but I can't remember how's it called) Even funnier that the feedback actually increases the bandwidth of the system, compared to the open loop amplifier.
    - Cloudly 4y ago
      >There's a measure for that but I can't remember how's it called Slew rate for opamps I believe Also worth noting that the "recursion" without negative feedback will hit a limit when the op-amp is saturated. Similar to a "stack overflow" I guess. Things mostly won't break but you'll get a flat output at the positive or negative rails of the op-amp - which causes some of the pain of analog signal processing.
    - hex4def6 4y ago
      >Even funnier that the feedback actually increases the bandwidth of the system, compared to the open loop amplifier. The reason for this is because of how bandwidth is defined, which is basically the point at which the amplifier gain starts dropping the higher the frequency you go. Adding feedback is effectively clipping the low frequency/ high gain area with the net effect that the gain versus frequency plot is a lot flatter (but now, instead of being able to get say 10,000x gain at 1Hz, you're clipping it to 100x, since you're unable to get 10,000x at 1Mhz)
olalonde 4y ago
It's a strange question given that we know that computers can do recursion and that computers are essentially made from electric circuits.
- avereveard 4y ago
  He clarifies in the answer what he means, and it's basically about analog circuitry. But yes you only need a feedback and possibly a time delay and you can do both in analog.
- rapjr9 4y ago
  Here's a related question, can an analog computer be Turing complete?
artemonster 4y ago
I am a very big layman in math, but I couldnt find any real descriptions of what „state“ actually is. Usually its just assumed to be a variable something out of a set of something values and be done with it. In electronics state imply recursion (and some stability condition). For example, two inverters that feed each other. Then what is a state in this sense? These are two possible configurations of space? Also how state relates to time? Since FSMs are exactly THE constructs to recognize sequences (the things that define „time“) and how time relates to all of that? I feel that there is a deeper connection, but I cannot seem to find anything related to this discussion. Any help?
- artemonster 4y ago
  Another way to view this: try building a stateful recursive circuit out of 2 normally closed relays. Basically it boils down to two separate circuits „folded over each other“
- AstixAndBelix 4y ago
  > two inverters that feed each other If there is no sync mechanism then they oscillate indefinitely with behavior dictated by their physical specification. At any point in time you can measure their outputs and that would be the current state. Two inverters that feed eachother is one of the worst examples to understand state and feedback loops because it's not stable and messes with your head.
  - artemonster 4y ago
    Ehm, what sync mechanism? An even incerter chain has a stable state
    - AstixAndBelix 4y ago
      A state is stable if, given the same input it took to reach it, it remains in that state indefinitely. Two inverters cannot be stable as their state constantly oscillates
sideshowb 4y ago
Well I made one back in 2003, in simulation at least. It was part of an EU funded project called poetic, which in short was making an fpga that could reprogram itself for evolvable hardware purposes. (Alas the fabrication went off track a bit). At the suggestion of the designer Yann I made a growing delay line. The cpu would poke one cell of our fpga asking for a delay line N units long. This would create a single unit, then that cell would poke an adjacent cell and ask for a delay N-1 units long. Etc. The units could be anywhere on the chip and formed connections to one another with a hardware implementation of dijkstra's algorithm, iirc. When it was all connected you could start using the delay line. Not an efficient way to make a delay line, but definitely recursion. (Cross post from the se thread as I just noticed that's 7 years old) Update: here's a video I made of the simulation running. It's all verilog or vhdl under the hood. https://users.cs.cf.ac.uk/CooperCH/ontoroute.avi https://users.cs.cf.ac.uk/CooperCH/ontoroute.avi
H8crilA 4y ago
IIR filters are awesome, but they can have some crazy behavior. If you want a neat mathematical framework to understand them check out the z-transform, which maps IIR filters to the space of rational functions (a polynomial divided by another polynomial). You can extract filter's behavior from this function. For example the complex zeros of the polynomials are crucial and have names ("poles" for zeros of the denominator, "zeros" for zeros of the numerator). The special case when the denominator disappears corresponds to FIR filters. IIR filters have decades of research behind them, and are used in all radio equipment. IIR filters cannot compute in the Turing sense, though. They're linear operators which is particularly evident in the Fourier basis. Complex exponentials (i.e. simple rotations) are their eigenvectors. Much like with neural networks you also need a non-linear operator to get the "real deal".
analog31 4y ago
Interestingly, here's a switched capacitor filter IC from National Semiconductor: https://www.ti.com/lit/ds/symlink/mf10-n.pdf https://www.ti.com/lit/ds/symlink/mf10-n.pdf
naasking 4y ago
Very apropos this site: what is the circuit equivalent of the Y combinator?
xodjmk 4y ago
I have done several FPGA algorithms using HLS C++ Templates using tail-recursion. It works very well. Although it is a high-level abstraction, and the underlying logic gate structure is not easily accessible. HLS generates hard to read 'machine' VHDL or Verilog. Though if you really wanted to it is possible to reverse engineer and get the actual logic. The HLS (Synthesizable C++) is only a few lines and easily verifiable, so there is no real need to ever reverse engineer. Also, I assuming we are talking about actual recursive algorithms, not something obvious like feedback, or IIR filters..

105 points by dustingetz 4y ago

Not exactly a circuit, but a coworker once wrote a recursive macro in VHDL that would generate a unanimous vote detector (an N-input AND gate) from a cascade of 2-input AND gates.

xodjmk 4y ago
How is this not a circuit? Those AND gates will be built out of multiple transistors that require VCC and GND and current etc. It's absolutely a circuit.

mikewarot 4y ago

Positive feedback loops are recursion, in many cases the skill in electronics engineering is avoiding positive feedback. Sometimes you can use a bit of positive feedback to suppress noise, as in a Schmidt trigger, which is bistable. Sometimes you can use it under manual control as in a Super-regenerative receiver. Mostly, it is used in oscillators to produce sine waves.

dreamcompiler 4y ago
In that sense negative feedback is recursion too because it's taking part of the output signal and feeding it back into the input again. Negative feedback is closer in spirit to a typical recursive function where you often want each iteration to process a "smaller" argument than the last and thus be closer to some fixed point.
- mikewarot 4y ago
  I do vaguely recall that the first time I saw an OP-amp circuit it seemed insane. It's only after you learn about negative feedback, and forcing a virtual ground that you can work with the things and not think they're black magic. That was decades ago, I'd forgotten about it.
ilyt 4y ago
> Mostly, it is used in oscillators to produce sine waves. Well technically to get sine you need a gain of exactly 1, anything above that will increase distortion. Now to get it to start oscillate in the first place you need above 1 so old school low distortion sine generators usually have some kind of automatic gain control
- mikewarot 4y ago
  Once upon a time, the #47 panel lamp served that function.
namibj 4y ago
Also useful to reduce drive power in hard-switched field-effect-device cascodes: with some mild tricks, stacked cascodes in particular benefit from compensating miller effect with positive feedback. It still all falls down again when the bottom node/switch is turned back on, and the only arguably difficult part is minimizing the extend of damping needed to prevent the positive feedback from oscillating, like it happily does with inductive load. The approach appears to be of relevance for MVDC power supply applications, as well-compensated capacitances in a stacked cascode can minimize driving/switching power in hard-switched SiC JFET based switches (at around 1~2 kV per JFET, stacked as high as needed), with usefully low loss up to the MHz range of e.g. PWM frequencies. Switched capacitance converters obviate the need for poorly-scaling higher-frequency magnetics, at the mild cost of needing some more switches (only divide-by-2 seems to be truly effective/ideal, while transformers can do arbitrary ratios), and the arguably massive gain of power density reachable in below-substation power classes (pole transformers, up to electric trains, the latter benefitting especially from skipping both the transformer and the AC filtering needs w.r.t. power-to-weight aspects).
mikewarot 4y ago
It took me a while to find it... but here it is, a motor generator that can give a gain of 10,000 or more using a bit of recursion https://en.wikipedia.org/wiki/Amplidyne https://en.wikipedia.org/wiki/Amplidyne ----- An earlier circuit that gets gain out of Motor Generators is the Ward-Leonard control https://en.wikipedia.org/wiki/Ward_Leonard_control https://en.wikipedia.org/wiki/Ward_Leonard_control At the US Steel works in Gary, Indiana, they have a 6 stand cold rolling mill. This uses pairs of 19,000 Horsepower motors on each stand to pull a cold slab of steel 6 inches thick like taffy to reduce its thickness. The electronics of the day (early 1960s) couldn't drive things directly, but they did have SCR packs big enough to drive the fields of DC generators in the Ward-Leonard configuration. I rebuilt many of those SCR packs in the 1980s.

bfung 4y ago

The key insight is that a recursive function can be transformed into an iterative function. From there, convert the iterative function to a circuit w/clock cycles.

anonymousiam 4y ago
Discreetization (what you are referring to) always involves loss, and, rather than instantly getting the "correct" result from your calculations, you will need to wait for enough clock cycles to progress until the remaining error value is less than the (ever present) noise.

dreamcompiler 4y ago

Logic gates are not recursive i.e. you typically don't feed a gate's output back to its input. Gates are asynchronous and stateless; their outputs only change when their inputs change and they don't retain information. But if you do feed gate outputs back to their inputs (usually indirectly), then it's a recursive circuit and now it can remember state. This is called a flip-flop, or single-bit memory. https://en.m.wikipedia.org/wiki/Flip-flop_(electronics) https://en.m.wikipedia.org/wiki/Flip-flop_(electronics)

userbinator 4y ago
then it's a recursive circuit and now it can remember state. ...or oscillate, depending on the phase of the feedback: https://en.wikipedia.org/wiki/Ring_oscillator https://en.wikipedia.org/wiki/Ring_oscillator
- deleted 4y ago
  [deleted]

0b01 4y ago

The simplest mutual recursion is a Set-Reset flip flop circuit.

contingencies 4y ago

Intermediate electronics designer here, not classically trained, coming from software (also not classically trained). I would say absolutely. If we define recursion as the deterministic variance of function output over time, given a single known input, then for a given circuit-implemented function simply use a timer to take the output of that function and feed it in as input thereafter. Gotchas: this probably requires state buffering, and the control flow implications with respect to parallelism and synchronization are essentially why we have MCUs.

kilgnad 4y ago

People are talking about logic gates and computing. While these things are associated with electric circuits, strictly speaking, they don't have to be. It's sort of a separate domain all together. For something strictly an electric circuit that uses recursion take a look at an op-amp: https://en.wikipedia.org/wiki/Operational_amplifier https://en.wikipedia.org/wiki/Operational_amplifier. Normal operation of an op amp basically involves a feedback loop which is the analog equivalent of recursion. Basically anything with a feedback loop is recursion.

elevaet 4y ago
Resonant filters, like the classic Moog ladder filter, are another great example of recursive/feedback circuit designs. As someone coming from a computing background, it always seems magical how the recursion in these types of analogue circuits happens instantaneously.
- raverbashing 4y ago
  > how the recursion in these types of analogue circuits happens instantaneously. Yeah, theoretically instantaneous, in practice not. (There's a measure for that but I can't remember how's it called) Even funnier that the feedback actually increases the bandwidth of the system, compared to the open loop amplifier.
  - Cloudly 4y ago
    >There's a measure for that but I can't remember how's it called Slew rate for opamps I believe Also worth noting that the "recursion" without negative feedback will hit a limit when the op-amp is saturated. Similar to a "stack overflow" I guess. Things mostly won't break but you'll get a flat output at the positive or negative rails of the op-amp - which causes some of the pain of analog signal processing.
  - hex4def6 4y ago
    >Even funnier that the feedback actually increases the bandwidth of the system, compared to the open loop amplifier. The reason for this is because of how bandwidth is defined, which is basically the point at which the amplifier gain starts dropping the higher the frequency you go. Adding feedback is effectively clipping the low frequency/ high gain area with the net effect that the gain versus frequency plot is a lot flatter (but now, instead of being able to get say 10,000x gain at 1Hz, you're clipping it to 100x, since you're unable to get 10,000x at 1Mhz)

olalonde 4y ago

It's a strange question given that we know that computers can do recursion and that computers are essentially made from electric circuits.

avereveard 4y ago
He clarifies in the answer what he means, and it's basically about analog circuitry. But yes you only need a feedback and possibly a time delay and you can do both in analog.
rapjr9 4y ago
Here's a related question, can an analog computer be Turing complete?

artemonster 4y ago

I am a very big layman in math, but I couldnt find any real descriptions of what „state“ actually is. Usually its just assumed to be a variable something out of a set of something values and be done with it. In electronics state imply recursion (and some stability condition). For example, two inverters that feed each other. Then what is a state in this sense? These are two possible configurations of space? Also how state relates to time? Since FSMs are exactly THE constructs to recognize sequences (the things that define „time“) and how time relates to all of that? I feel that there is a deeper connection, but I cannot seem to find anything related to this discussion. Any help?

artemonster 4y ago
Another way to view this: try building a stateful recursive circuit out of 2 normally closed relays. Basically it boils down to two separate circuits „folded over each other“
AstixAndBelix 4y ago
> two inverters that feed each other If there is no sync mechanism then they oscillate indefinitely with behavior dictated by their physical specification. At any point in time you can measure their outputs and that would be the current state. Two inverters that feed eachother is one of the worst examples to understand state and feedback loops because it's not stable and messes with your head.
- artemonster 4y ago
  Ehm, what sync mechanism? An even incerter chain has a stable state
  - AstixAndBelix 4y ago
    A state is stable if, given the same input it took to reach it, it remains in that state indefinitely. Two inverters cannot be stable as their state constantly oscillates

sideshowb 4y ago

Well I made one back in 2003, in simulation at least. It was part of an EU funded project called poetic, which in short was making an fpga that could reprogram itself for evolvable hardware purposes. (Alas the fabrication went off track a bit). At the suggestion of the designer Yann I made a growing delay line. The cpu would poke one cell of our fpga asking for a delay line N units long. This would create a single unit, then that cell would poke an adjacent cell and ask for a delay N-1 units long. Etc. The units could be anywhere on the chip and formed connections to one another with a hardware implementation of dijkstra's algorithm, iirc. When it was all connected you could start using the delay line. Not an efficient way to make a delay line, but definitely recursion. (Cross post from the se thread as I just noticed that's 7 years old) Update: here's a video I made of the simulation running. It's all verilog or vhdl under the hood. https://users.cs.cf.ac.uk/CooperCH/ontoroute.avi https://users.cs.cf.ac.uk/CooperCH/ontoroute.avi

H8crilA 4y ago

IIR filters are awesome, but they can have some crazy behavior. If you want a neat mathematical framework to understand them check out the z-transform, which maps IIR filters to the space of rational functions (a polynomial divided by another polynomial). You can extract filter's behavior from this function. For example the complex zeros of the polynomials are crucial and have names ("poles" for zeros of the denominator, "zeros" for zeros of the numerator). The special case when the denominator disappears corresponds to FIR filters. IIR filters have decades of research behind them, and are used in all radio equipment. IIR filters cannot compute in the Turing sense, though. They're linear operators which is particularly evident in the Fourier basis. Complex exponentials (i.e. simple rotations) are their eigenvectors. Much like with neural networks you also need a non-linear operator to get the "real deal".

analog31 4y ago

Interestingly, here's a switched capacitor filter IC from National Semiconductor: https://www.ti.com/lit/ds/symlink/mf10-n.pdf https://www.ti.com/lit/ds/symlink/mf10-n.pdf

naasking 4y ago

Very apropos this site: what is the circuit equivalent of the Y combinator?

xodjmk 4y ago

I have done several FPGA algorithms using HLS C++ Templates using tail-recursion. It works very well. Although it is a high-level abstraction, and the underlying logic gate structure is not easily accessible. HLS generates hard to read 'machine' VHDL or Verilog. Though if you really wanted to it is possible to reverse engineer and get the actual logic. The HLS (Synthesizable C++) is only a few lines and easily verifiable, so there is no real need to ever reverse engineer. Also, I assuming we are talking about actual recursive algorithms, not something obvious like feedback, or IIR filters..