-2
\$\begingroup\$

Can all digital design problems theoretically be solved using only combinational logic, or are there specific examples that have to be solved sequentially? I read that sequential logic is only required due to hardware limitations.

EDIT: Maybe a better phrasing of the question would be: Can any algorithm or circuit be theoretically solved using only combinational logic, even though practically you would want registers or events happening each clock cycle? If not, what would a specific example be?

EDIT2: Another way to phrase the question would be to say: Is there any circuit that can't theoretically be solved using only combinational components like AND/OR gates and MUX's?

EDIT3: I'm thinking the only real problem requiring sequential logic is the problem of combinational loops. That can only be solved with a FF as far as I know.

\$\endgroup\$

closed as unclear what you're asking by pjc50, Daniel Grillo, nidhin, Rev1.0, akellyirl Apr 16 '15 at 15:57

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    \$\begingroup\$ How do you store memory in a combinational circuit? \$\endgroup\$ – Shamtam Apr 10 '15 at 0:56
  • \$\begingroup\$ I'm not sure but don't you just need to store something as an intermediate step before the eventual output? \$\endgroup\$ – Arewfawe Waefadffawe Apr 10 '15 at 1:02
  • 1
    \$\begingroup\$ If you are not a troll, then please provide a reference telling where you read that sequential logic is only required due to hardware limitations. \$\endgroup\$ – mkeith Apr 10 '15 at 5:17
  • 1
    \$\begingroup\$ Next pedantry: you can build a flip-flop out of NAND gates, so long as they are real gates and not theoretical/ideal gates. However, almost every designer would call this "sequential" logic now that you have a flop. How are you defining this case? \$\endgroup\$ – pjc50 Apr 10 '15 at 16:14
  • 1
    \$\begingroup\$ Analog to digital converter. Fast Fourier Transform. Modulo. Divide. Left Shift. Right Shift. Anything anywhere that has dependencies on the time domain. You don't get to look ahead or behind without sequential logic. Combinational logic is what it is, right now, without exception. You have your examples. No more magic inputs that change with respect to time when it's convenient. \$\endgroup\$ – Sean Boddy Apr 10 '15 at 16:15
0
\$\begingroup\$

The size of a combinatorial circuit is a function of its input. The more input a circuit can use in figuring its output, the larger the circuit must be. Suppose, for example, one needed to design a circuit that would determine whether an input had an even or odd number of rising edges within the last second, if every high and low time was guaranteed to be at least 100ms. One could use a chain of purely-combinatorial buffers with a 91ms propagation time to generate twelve inputs to a circuit that could then count the number of "01" sequences within the bit stream. Such a circuit would be rather large, but not impossible.

If one wanted to make a circuit which could say whether the input had pulsed high an even or odd number of times in the last minute, one could use the same principle, but the result would be rather unwieldy. If one has some clock signal available that may help stabilize timings and prevent the circuit from becoming quite so totally impractical(*), even without feedback (note that combinatorial circuits can use clock signals, but can't generate them). Clock-facilitated optimizations may help prevent a circuit from becoming totally unworkable, but it would still be large. Increasing the time in question to a day, year, decade, or century would likewise grow the machine. If one didn't need the machine to last more than 100 years, one could in theory build a purely-combinatorial machine to report whether the number of pulses in the last 100 years was even or odd, and then use that for up to 100 years, but doing so would be monstrously impractical.

By contrast, using sequential logic, the task could be accomplished using a single D flip flop with an inverted output. Even though in the course of a year the device would be accepting millions of seconds' worth of "input", that would be no problem since a single flip flop will suffice to hold state derived from an unlimited quantity of input.

(*) It's possible to build a D flop without using feedback if one can guarantee that the time between clock pulses will not exceed some limit, though unfortunately this simulator can't handle monolithic MOSFETs.

schematic

simulate this circuit – Schematic created using CircuitLab

The "resistors" are actually depletion-mode pull-ups to VDD, and the MOSFETs are monolithic, with their bases tied to VSS rather than to the source. While PHI1 is high, whatever is on IN will be transferred to the gate of M2, and the inverse of it will appear on the M2 drain. When PHI1 is low, whatever was on the gate and drain of M2 will remain there, at least for awhile, because of M2's gate capacitance. When PHI2 is high, whatever is on the drain of M2 will be transferred to the gate of M4, and the inverse of it will appear on the M4 drain. When PHI2 is low, whatever was on the gate and drain of M4 will remain there for awhile because of M4's gate capacitance. Provided that PHI1 and PHI2 do not overlap and are fast enough to reload gate the capacitors before leakage disturbs their values, this circuit may be used reliably as a D flop. Indeed, circuits of this type were very common in 1970s LSI logic.

Further, even if one views this style of circuit as "cheating", it's possible to use clocking to stabilize propagation delays of purely sequential logic by having a clock select between logic paths with shorter or longer propagation times.

schematic

simulate this circuit Unlike the MOSFET circuit, the one above will simulate. Each buffer has a 700ns propagation time, and each mux outputs will change on the rising edge of the clock and no other time provided that rising edges of the clock occur between 700ns and 1400ns after an input change, and the falling edges do not occur until at least 1400ns after an input change. The above circuit initially meets the timing constraints, but because the clock and data are not exact multiples drifts to violate it, showing the consequent behavior.

\$\endgroup\$
1
\$\begingroup\$

If you have some set of boolean inputs S, and some function f that maps S to a set of boolean outputs R, then yes: any f can be represented with pure combinational logic, and you can derive which logic you need from the Karnaugh map etc. The process of filling in the Karnaugh map may be difficult: you're manually pre-computing all the answers.

This has two big limitations:

  1. All the input must be available at the same time
  2. There must be a defined finite maximum number of inputs

You can't use pure combinational logic for e.g. the classic lift controller state machine, because you can't record whether a button has been pressed or not. You can't use it for signal processing because you need to record previous values of the signal. It also makes for awkward and expensive implementation: if you want to find which of a billion records matches a particular input, you have to have a billion comparators.

I think this strays into Turing-completeness territory as well. The function that outputs 1 if a Turing tape halts and 0 if it doesn't isn't theoretically computable by either kind of logic.

\$\endgroup\$
  • \$\begingroup\$ Technically, couldn't you use the previous values of a signal as other inputs? When the circuit is being solved, all of the possible previous values, however far back you want to keep a record of, would be additional inputs to the circuit. I realize this is impractical but the questions is whether there is a problem that can't be solved using only combinational logic. \$\endgroup\$ – Arewfawe Waefadffawe Apr 10 '15 at 14:11
  • \$\begingroup\$ @ArewfaweWaefadffawe But if you remove the previous values as you describe, then the problem can't be solved using only combinational logic. It can only be solved if you also implement the bits you removed. It's like saying you can make a coffee using only a cup, because the coffee beans, water and milk are additional inputs. More specifically for your example, the outputs you propose feeding back as inputs don't yet exist because everything happens at once. \$\endgroup\$ – Roger Rowland Apr 10 '15 at 14:30
  • \$\begingroup\$ Right, but what I'm saying is that within your list of inputs and outputs, some of the inputs would be labeled as past signal values. Now you would solve the truth table for all possible values using a value you designate to represent no previous value, like 0. Implementing inputs that represent past signal values isn't cheating as you imply. The question is simply if the circuit can be solved using only combinational logic. \$\endgroup\$ – Arewfawe Waefadffawe Apr 10 '15 at 14:46
  • \$\begingroup\$ Allowing storage of past inputs raises the question of why you can't store intermediate results as well; it's "cheating" because it wasn't mentioned in the initial question. How many past inputs are you able to store? Can this number grow without limit? Is the number of inputs finite? I think I'm also going to ask you to define "solved" so we can make sure there aren't any traps there either. \$\endgroup\$ – pjc50 Apr 10 '15 at 15:11
  • \$\begingroup\$ (It's not unreasonable to think of digital design in terms of "clouds" of sequential logic from register outputs to register inputs, and design simulators in this way, but the way you have phrased this question sounds like a trick question or pointless argument over definitions that aren't specified) \$\endgroup\$ – pjc50 Apr 10 '15 at 15:14
0
\$\begingroup\$

Sequential logic was developed out of a necessity to be able to accurately predict when a certain value or set of values was in a certain place, so that other logic could decide to then do something with that information. Many logical problems can be resolved using only combinational logic, but a problem arises when you need to use the output of one function as an input to another function. In order to create general purpose hardware, it is necessary to be able to copy and reroute binary values at will throughout the system so that different functions can be performed in an arbitrary order. Without this ability, we have to add logic for every possible order of operations that could ever happen anywhere, which is not possible.

Also, if you can build a working multiplexer without a single flip-flop, you really need to go file a patent, like, right now.

\$\endgroup\$
  • \$\begingroup\$ A mux? I don't understand why you need a FF for a mux... \$\endgroup\$ – Arewfawe Waefadffawe Apr 10 '15 at 2:03
  • \$\begingroup\$ Because you need a counter. \$\endgroup\$ – Sean Boddy Apr 10 '15 at 2:04
  • \$\begingroup\$ I don't see why you need a counter. Can you just give me one, simple set of inputs and outputs that can't be obtained combinationally? \$\endgroup\$ – Arewfawe Waefadffawe Apr 10 '15 at 2:38
  • \$\begingroup\$ A = !A. Try it some time. It's indeterminate. Unless of course you use a flip flop to hold the state. \$\endgroup\$ – Sean Boddy Apr 10 '15 at 3:23
  • 1
    \$\begingroup\$ alex.forencich: I think that Sean considers a "multiplexer" to be a "time-division multiplexer" for sending a sequence of multiplexed values over time, as opposed to just a simple combinatorial "mux" gate. \$\endgroup\$ – David Smith Apr 10 '15 at 13:22
0
\$\begingroup\$

All digital problems that are inherently combinatorial can be solved using combinatorial logic. For example AES-encryption would normally be done using sequential logic, but it could theoretically be done combinatorially provided you had all the available inputs ready simultaneously, and unrolled all the loops by duplicating logic. Of course, it'd be hideously inefficient with all those duplicated logic blocks, but still possible.

However, some problems are inherently time-based. If your problem description contains any kind of "do this, then afterwards do that", you will need to use sequential logic.

\$\endgroup\$
  • \$\begingroup\$ Maybe a better phrasing of the question would be: Can any algorithm or circuit be theoretically solved using only combinational logic, even though practically you would want registers or events happening each clock cycle? If not, what would a specific example be? \$\endgroup\$ – Arewfawe Waefadffawe Apr 10 '15 at 13:40
  • \$\begingroup\$ The requirement for sequential elements comes from the problem specification. For example: if you want to search a list of integers to find out if any of them are equal to zero, then that can theoretically be done combinatorially, provided you have all of the values in the list available at the same time, in parallel. However, the more likely scenario is that the list will be a memory which needs to be accessed sequentially (because the memory will only return one value at a time), and therefore you will need to use sequential logic to remember at least the address. \$\endgroup\$ – David Smith Apr 10 '15 at 15:00
  • \$\begingroup\$ An alternative example is a digital clock. Provided someone is telling you what the current time is, then you can use purely combinatorial logic to decode that time value into something useful to put on the display. However, the thing that is telling you what the current time is needs sequential logic to be able to tell you what the current time is. \$\endgroup\$ – David Smith Apr 10 '15 at 15:08
  • \$\begingroup\$ David Smith: Regardless of where the input to the combinational logic entity comes from, the alrgorithm or logic that is needed to produce the correct output is combinational. Whether you want to use the position of the sun or some object making a tick pusle every second, or some other form of input, the logic is still combinational. \$\endgroup\$ – Arewfawe Waefadffawe Apr 10 '15 at 15:29
  • \$\begingroup\$ But you have to store a (potentially unbounded) tick count somewhere? Or are we back to "apart from storage, everything is combinational"? \$\endgroup\$ – pjc50 Apr 10 '15 at 15:35
0
\$\begingroup\$

Any realtime system using digital filters or controllers will necessarily require memory elements fulfilling the delay requirements of discrete-time difference equations. Batch data that could theoretically provide all relevant input data, is not available in realtime systems. In a control system you usually at least require an Integrator which requires a memory in a digital implementation.

Examples include: realtime Audio processing, Sigma-Delta ADCs and DACs, realtime control systems.

Also, any state machine requires memory elements to represent the states.

\$\endgroup\$
  • \$\begingroup\$ Although impractical, couldn't the real-time audio processing example, along with your other examples, be done combinationlly if you have solved for all of the possible inputs? The inputs to the combinational circuit would include the current audio signal value, and the the past signal values back to a specified time. Although I'm using the word 'time' here, the combinational circuit doesn't know any better. \$\endgroup\$ – Arewfawe Waefadffawe Apr 10 '15 at 14:35
  • \$\begingroup\$ No. The ADC that provides the realtime data only outputs the present value. Previous values would need to be stored. \$\endgroup\$ – akellyirl Apr 10 '15 at 14:53
  • 1
    \$\begingroup\$ In which case, your answer depends on the scope of your question. You need to remember the previous inputs somewhere, so do you define the function as including that memory or not? If your question is whether the required function can be implemented without any memory elements provided that the memory elements that you need are provided elsewhere, then yes, it can. :) \$\endgroup\$ – David Smith Apr 10 '15 at 15:04
  • \$\begingroup\$ I'm not understanding why outputs within the circuit representing past signal values could not be fed into inputs within the circuit. Each different current input value would combinationally/immediately change the other signals representing past inputs. To handle the situation where the same input signal value was coming in but at a different 'time', you would add an input that would alternate like a clock signal. The circuit is still combinational though because you only need combinational components like AND/OR gates and MUX's. \$\endgroup\$ – Arewfawe Waefadffawe Apr 10 '15 at 15:44
  • \$\begingroup\$ "Each different current input value would combinationally/immediately change the other signals representing past inputs" - Loops are not allowed in combinational logic. \$\endgroup\$ – pjc50 Apr 10 '15 at 15:55

Not the answer you're looking for? Browse other questions tagged or ask your own question.