2
\$\begingroup\$

I always thought that combinational logic circuits could only solve problems that didn't require memory, but then something struck me.
Whenever we are modelling a binary adder with a Finite State Machine, we consider it as a problem that requires memory ( we need to know whether the previous digit addition led to a carry or not ) . That's why we need two states, "no carry" and "carry".

enter image description here

But then we can easily see how binary adders with carriers can be solved by combinational logic circuits, which seemingly don't have memory.

enter image description here

It seems to me that the memory is somehow encoded in the way we put the individual adders in serial ( C_out of the last adder goes into the C_in of the current adder )

Comparing the Finite State Machine solution to the problem with the Combinational Logic solution to the problem , it seems like the former decides to do one digit addition at a time, regulated by a clock and that's why the memory needs to be in form of states . And it seems like the latter decides to do all digit additions at the same time, so there is no need for clocks and somehow the memory for the previous carriers is implemented via a serial cascading connection between the adders.

Just like we can have a FSM as well as a Combinational Logic version for the problem of arithmetic addition with carriers, i'm thinking whether we can actually convert ANY finite state machine into a Combinational Logic Circuit that does the same job, provided we arrange one subcircuit for every possible job that is done in the FSM in one clock ( one digit addition in the last case ) , put all those in parallel, and somehow encode the memory in a serial cascading connection.

Is it true ?

This doubt came because i'm trying to link all concepts i have recently learned in Theory of Computation ( Automata, Turing Machines, Computational Complexity : Time Complexity and Space complexity ) with combinational logic circuits .

Thanks a lot in advance.

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

That's because modeling the adder as a FSM is convenient, but ultimately false. There are no states; what is shown as a "state" is merely the output rather than the result of a state-based transition.

\$\endgroup\$
  • \$\begingroup\$ This seems deep and i really want to grasp it but i couldn't completely understand. Is there a kind of a method, or hint, to get a FSM and check whether it is a true FSM or not, that is, check whether it states are really outputs, or if they genuinely represent the result of a state-based transition ? Could you recommend me any material to read ? Thansk a lot \$\endgroup\$ – nerdy Feb 1 '15 at 21:10
  • \$\begingroup\$ A FSM requires some sort of memory in order to store the current state as well as some sort of clock in order to determine when transitions should be performed (i.e., it can only exist for sequential logic). An adder (being purely combinational logic) has neither. \$\endgroup\$ – Ignacio Vazquez-Abrams Feb 1 '15 at 21:16
1
\$\begingroup\$

No, you can not translate a (nontrivial) circuit that has memory to a combinatorial (feedback-less) circuit.

The outputs of a combinatorial circuit are by definition a function of its inputs (and nothing else).

Take the simplest non-combinatorial circuit: the Set-Rest memory cell (two cross-couples NANDS or NORS). When the inputs have the 'remember' value the outputs are a function of the past. This is simply not possible with any combinatorial circuit.

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

If the design needs state then it must have some way of storing that state, that is memory.

The output of an adder (or multiplier, etc.) is completely determined by the inputs, so can be implemented completely in combinatorial logic.

A single bit memory cannot be implemented in combinatorial logic, otherwise it would not be memory.

\$\endgroup\$
0
\$\begingroup\$

In my opinion I feel whether a combinational circuit can be extracted from a sequential circuit will depend on the functionality of the circuit.A lot (but not all) of sequential logic circuits can be unpacked and implemented as purely combinational circuits (I feel this is especially true for Moore machines) but there are a lot of timing and area specifications that would be very difficult to meet if we decided to implement them in this way.Also as the number of states gets large it becomes increasing impractical and too costly to develop a system in this way.

I am not sure I agree with the stance that representing an adder with the diagram you provided is necessarily false as another poster has stated.Maybe it is false in context of the ripple adder circuitry you provided but an N bit adder can be in fact be modelled as going through two states, carry-1 and carry-0, and a sequential circuit such as the one below extracted.

Sequential Adder

A lot of sequential (Synchronous / Clocked) circuits can also be replaced by purely combinational (Asynchronous / Clock-less) circuits in a lot of situations.These asynchronous circuits use bundle data protocols such as the 4-phase dual rail protocol to communicate with each other and essentially have state information encoded in their outputs.

\$\endgroup\$
0
\$\begingroup\$

Basically we do consider carry for next operation (not state) but don't care what it will be it may be 1 or 0 and final output will be decided by the value and the combination all logic , we can't model it using state machine because the entire circuit doesn't go through multiple states unlike for example a counter

\$\endgroup\$
0
\$\begingroup\$

The state diagram shown in the the question is a serial adder. It has only one full adder and a memory element in it. And it requires N clock cycles to produce the result of addition of two N-bit numbers.

The block diagram shown in figure is a 4-bit ripple carry adder that requires 4 full adder blocks. This will add two 4-bit numbers in parallel and will produce the result in no time (propagation delays neglected). The logic here is purely combinational and it has no memory in it.

In short, the given state diagram does not corresponds to the block diagram given. They are two different digital systems. The serial adder has two single bit inputs and one bit output. Whereas a ripple carry adder has two N-bit inputs and one N+1-bit output.

Sequential machines can not be replaced with combinational logic. But combinational circuits can be replaced with sequential circuits. Usually it is done to reduce the hardware complexity. What we saw in your question is an example of that. The circuits like counters, shift registers, etc, can never be replaced with combinational logic.

\$\endgroup\$
  • \$\begingroup\$ In terms of computational complexity, the serial adder separates the steps of computation in time, reusing the hardware. The ripple adder separates the steps in space, using separate copies of the hardware to do the separate steps. \$\endgroup\$ – Austin Feb 23 '15 at 10:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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