-10

Consider a simple lock circuit built using a 4-bit, active HIGH digital comparator. The first input is variable; it is the input that unlocks the lock. All the bits of the second input are tied to ground. The lock is in the unlocked state when both inputs are equal. The lock is in the locked state when both inputs are not equal.

This circuit contains purely combinational elements with zero loops, since it has only a comparator.

In some resources such as this one, it states that there are two types of circuits:

  1. Stateless combinational circuits (&,|,~)
  2. Stateful circuits (eg. registers)

In this other resource, https://computationstructures.org/notes/fsms/notes.html, the block diagram of FSM shows the presence of flip-flops as state registers.

My circuit does not contain any registers or flip-flops. Does this circuit have any memory or state?

Shashank V M
  • 2,279
  • 13
  • 47
  • 1
    By "lock circuit," do you mean a circuit whose purpose is to be part of a device similar to a padlock? – Cassie Swett Nov 28 '21 at 18:09
  • 3
    Does this answer your question? [Is a combinational logic circuit a Finite State Machine?](https://electronics.stackexchange.com/questions/596753/is-a-combinational-logic-circuit-a-finite-state-machine) – Elliot Alderson Nov 28 '21 at 19:11
  • 2
    I think it's incorrect to say that: any Combinational circuit without a feedback from its present output, has memory. It breaks the paradigm in digital circuits, where they get broadly classified into: Sequential and Combinational circuits. Every circuit will be then Combinational circuit, if you claim this particular lock has memory. There will be no distinction whatsover. Reference: first para of automata theory in https://en.m.wikipedia.org/wiki/Combinational_logic . "Sequential logic has memory while Combinational logic does not." – Mitu Raj Nov 28 '21 at 20:16
  • @TannerSwett yes, that's right. – Shashank V M Sep 14 '22 at 14:26
  • @MituRaj combinational logic is ROM. – Shashank V M Sep 14 '22 at 14:38

3 Answers3

6

Does this circuit have any memory or state?

If you ignore glitches or other transient phenomenon then no, it has no memory or state. The output is a fixed function of the input only, not on prior inputs.

A state in any system is a value that persists from one moment to the next -- this applies whether we're talking about a computer-science sort of enumerated "state", a digital circuits "what are the flip-flops at" sort of "state", or a dynamic systems state such as capacitor voltage, inductor current, liquid level in a vessel, or whatever.

So if you're modeling your digital system with all combinatorial logic with no loops that cause latching to happen and you're modeling it at a level where the gates are assumed to respond instantaneously, then there are no states, and the circuit as described has no memory.

TimWescott
  • 44,867
  • 1
  • 41
  • 104
  • Can you add one citation to your answer that says state change cannot happen instantaneously? What does it mean for a state change to not be instantaneous? A logic circuit can be in only one state at an instance in time. I argue that state changes *are* instantaneous in the real world. – Shashank V M Sep 14 '22 at 15:51
  • 1
    Argue all you want, but a quick consultation with any logic datasheet will tell you that flip-flops take time to switch state. If you can't believe engineers, consult with Dr. Einstein -- a state is a physical phenomenon, it's spread out over space, and _nothing_ that takes up space is really instantaneous because information transfer is limited by the speed of light. – TimWescott Sep 14 '22 at 20:21
  • 1
    The output of a real flip flop is a voltage which starts in one state and transitions, over time, to another. Only in books, and imaginations, is the transition instantaneous. – TimWescott Sep 15 '22 at 06:05
  • 4
    I think you need to learn some basic physics. Why don't you ask a **separate question** whether digital logic can change state instantaneously without going through an indeterminate middle state while its internal electronics settle. When you do so, it may help to **accept that other people may know more on a subject than you do**, even if, overall, you may be the smartest person in the entire world. – TimWescott Sep 15 '22 at 14:38
  • You are right and I was wrong about the state transitions taking finite time. I accept that state transitions take time after reading an article about researchers at Yale institute concluding quantum leaps are not instantaneous. – Shashank V M Sep 17 '22 at 06:58
4

If, and only if, the eventual stable output of a system depends only on the current input, that system is by definition memoryless.

vicatcu
  • 22,499
  • 13
  • 79
  • 155
  • A diode matrix has memory but its output depends only on the current input. There are no previous inputs since it is a ROM that cannot be modified. The definition provided by you applies to control systems, not to ROMs. – Shashank V M Sep 14 '22 at 16:01
  • The digital design and computer architecture electronic book that I purchased recently has memory because it remembers everything that was written to it. Yet its output depends only on the input, i.e. it displays only the page that you go to. The page number is the input, the page is the output here. – Shashank V M Sep 14 '22 at 16:06
3

The circuit as described is not a state machine. Far from it.

It has one output which the result of a combinatorial comparison. Any change of input produces an immediate change of output. And that change is not dependent on any state memory elements, only the inputs.

The circuit as currently described is the same circuit as a single combinatorial address decoder, for example. Address decoders are not state machines.

TonyM
  • 21,742
  • 4
  • 39
  • 62
  • What you describe as a "state machine" is called a synchronous finite state machine because you imply that a state machine needs to have state memory elements. That is only true for synchronous finite state machines. – Shashank V M Sep 14 '22 at 16:03