3
\$\begingroup\$

New here :D

I've been reading David M. & Sarah Harris's book "Digital Design and Computer Architecture" and came to wonder about the role of sequential logic. To me, it seems that the significance of sequential logic is primarily in its ability to store signals (HIGH/LOW, ON/OFF, 0/1, etc.). However, I've also noticed that the characteristic property of sequential logic is its dependence on past inputs in generating outputs.

Now as a rookie EE student, this confuses me. As I understand it, memory (in the electronics sense) is just the ability to store and retrieve past signals. With this in mind, signal storage doesn't seem like a hard task at all; ROM, for example, is (from what I've heard) purely combinational and stores signals - ie. memory. If we can make memory with combinational circuits, why are sequential elements so highly regarded as fundamental to memory? There must be a reason for this that I haven't read about yet (probably something with computer organization I'm assuming?).

I'm sorry if this post seems extremely naive and/or presumptuous :[ I haven't been taught formally on sequential logic :/

\$\endgroup\$
7
\$\begingroup\$

You're post is naive, but that is not necessarily a bad thing for two reasons: 1. There are others in your position that can benefit from your question. And 1. Sometimes people with decades of experience need to revisit these sorts of subjects from time to time to refresh their memory of what is important in circuits.

There are some terms that EE's use that are taught in school and in textbooks, but are rarely used professionally. Sequential logic is one of them. The professional term is "state machine". A state machine is essentially the guts of what you think of as sequential logic.

A "state" is simply the current condition of something. The state of a counter is the count value itself. A state of a stoplight is Red, Yellow, or Green.

When you say "memory is the ability to store and retrieve past signals", you are correct-- but nobody talks like that. We say that the state is stored. It is a minor point, but an important one. Storing a past signal implies that you are storing a signal that changes over time. Storing a state is storing the instantaneous value of the state. Take that little bit of knowledge and tuck it away in your brain for later, when it will make sense to you.

For us, there are two basic types of logic circuits: combinatorial and memory. Combinatorial logic is just logic where the outputs are dependent only on the inputs. It is a cluster of gates with no feedback paths (where gates downstream do not feed inputs of upstream gates). Memory is the opposite of combinatorial logic, in that it stores a value or state for use later. Basic building blocks for memory are the flip-flops and latches. Actual RAM can also be used to store state values, but that is more advanced use.

The core of a state machine (or what you are calling sequential logic) consists of a single block of combinatorial logic, and a chunk of memory to store the output of the combinatorial logic. The output of the memory is fed back into the combinatorial logic. If you are designing a counter, then the combinatorial logic might take the input and add 1 to it. The memory will save that +1 value for the next clock.

Usually connected to state machines is another chunk of combinatorial logic and possibly some more memory to handle the outputs of the state machine (different from the state value itself). An example of this would be an extra signal from our counter that goes high every time the counter is equal to 4.

Where this extra combinatorial logic (and maybe more memory) is in relation to the core combinatorial/memory logic is what determines if this is a Mealey or Moore state machine. I bring up the Mealey and Moore terms only because this is another example of something that is only taught in schools and is almost never used professionally.

But with all this talk about "memory", we have a problem. The way this term is used in this discussion is different than how it is normally used. When you say "memory" to most people they think of RAM and ROM. But memory in this context is normally flip-flops and latches. Usually D-Flip-Flops. The DFF's in a counter will hold one word, and only one word. RAM, on the other hand, will store many words at a time. It is hard to tell from your question, but I think that you are confusing RAM with Flip-Flops and Latches.

Now on to your question: If we can make memory with combinational circuits, why are sequential elements so highly regarded as fundamental to memory?

You can make memory with gates, and you can make combinatorial logic with gates. But combinatorial logic is not memory. In fact, the definition of combinatorial logic is "logic without memory". But almost every useful circuit is made from both memory and combinatorial logic.

What I do not understand from your question is what kind of memory are you referring to. But ultimately it doesn't matter because sequential elements is not fundamental to either kind of memory. It is the opposite, in fact. Memory is fundamental to Sequential logic (a.k.a. state machines).

When looking at state machines, sequential logic, synchronous logic, and the like it can be useful to break up the logic into combinatorial logic and flip-flops. Don't break it up in the actual design, but break up how you think of the circuit. This will help you in identifying the parts that matter. It will also help you later on when you have to start thinking about signal timing, clocks, and all of that stuff.

I also advise that you ignore RAM/ROM for now until you understand the rest of this. There is no sense in complicating things at this stage.

\$\endgroup\$
3
  • \$\begingroup\$ "The professional term is 'state machine'" -- This statement is not correct. Sequential logic is used to construct finite state machines, but they are different levels of abstraction. Otherwise, excellent! \$\endgroup\$ – DrFriedParts Jan 26 '13 at 8:14
  • \$\begingroup\$ @DrFriedParts Geez, I thought that someone would get after me for basically saying that distinguishing between Mealey/Moore state machines was pointless-- but I was wrong. Yes, "sequential logic" and "state machines" are not completely interchangeable. But except in certain academic circles, the differences are a lot like the differences between centrifugal and centripetal-- real, but it doesn't matter at the end of the day. \$\endgroup\$ – user3624 Jan 26 '13 at 13:46
  • \$\begingroup\$ Dude... centrifugal and reactive centrifugal forces are opposite in direction to the centripetal force... so... kinda important ;-) As to the original point, your statement that they are the same is false. If you want to note the difference as having little practical implication -- just say that. \$\endgroup\$ – DrFriedParts Jan 26 '13 at 23:19
3
\$\begingroup\$

Combinational logic is an instantaneous lookup table, simply a function. A black box whose outputs depend solely on the current input values. It is always a one-to-one relationship. In a way, a read-only memory (ROM) that once defined will never change.

The output of sequential logic depends on the sequence of inputs, not just the current inputs. So it needs a way of remembering what has happened before, and this is typically done using flip-flops and/or latches as memory blocks.

Typical uses are pipelines, clocked data-paths and finite state machines. Finite state machines are sequential circuits where the sequence of inputs are memorized and abstracted as a state, so the next state depends on the current state and the current inputs. It is a Markov chain at its purest. It has usually an associated clock that tells it when to sample the current inputs and its own current state in order to change to its next state. But not always, because there is asynchronous sequential logic, but let's leave that for another discussion. The outputs may depend solely on its internal state (Moore finite state machine) or also on the current inputs (Mealy finite state machine).

So, to remember its current state, it requires memory blocks. Because the contents of this "memory" changes, it is not a ROM, which is at most what a purely combinational circuit can offer.

Hopefully this clears up why the ability of storing signals is required in sequential logic, its relationship to keeping an internal state that is solely the result of the past sequence of inputs, and that this "memory" is different than a combinational read-only memory.

Last but not least, note that there is always combinational logic, it is the "glue logic" that makes up your circuit, sequential or not. For example, in a finite state machine the logic that determines what the next state should be according to the current state and the current inputs is nothing more than a combinational block. Simply when you add statefulness using feedback and memory elements, the circuit as a whole acquires the broader term "sequential". In the end, it is all gates and flip-flops.

\$\endgroup\$
2
\$\begingroup\$

The other answers all make good points, but they're not really getting to the core of your question, which is how do you get from combinatorial logic to sequential logic to "memory". Let me try to address that.

One of the points that is being glossed over is that there are two kinds of sequential logic, asynchronous and synchronous. Asynchronous sequential logic can change state if any of its inputs changes, while synchronous sequential logic only changes state when given a clock edge (or pulse) occurs.

A combinatorial circuit has no feedback, and its output(s) are always a function of its current inputs. One example is the AND-OR combination shown below (a). If you add feedback (b), you now have a simple set-reset latch. Let's assume the S input is low and the R' input is high. If the S input is pulsed high, the Q output will be driven high, and it will remain high even after S goes low again, because of the feedback through the AND gate. If R' is pulsed low, Q will be driven low, and it will stay low after R' goes high again.

Figures (a) and (b)

If we convert the OR gate to its DeMorgan equivalent we can redraw the latch as shown in (c). Let's make the "set" input active-low and rearrange the bubbles a bit, and we get the classic latch made with two NAND gates (d). Note that we can use the output of the other gate as a complementary output (Q').

Figures (c) and (d)

To create a memory that can remember the state of a signal at a particular time, we can add a few more gates to our latch (e). When the enable (E) input is high, the output will follow the data (D) input, and when E goes low, Q will hold the value that D had at that time. This collection of logic can be represented by the latch symbol (f). A static RAM (random-access memory) is simply a collection of latches like these, along with a lot of combinatorial logic to decode the latch enables and multiplex the outputs.

Figures (e) and (f)

Designing aynchronous state machines is not difficult for simple cases like this, but quickly becomes unwieldy for more complex cases. As a result, it becomes desirable to have a memory element that updates itself on a clock edge rather than a latch enable pulse. This is why the concept of a master-slave flip-flop was developed. It consists of two latches cascaded as shown in (g), and their enables are complements of each other — when one is enabled, the other is disabled. When the clock is low, the first latch is enabled, and when the clock goes high, the first latch is disabled (holding the value of D) and the second latch is enabled, propogating that value to the output. This collection of logic is represented by the DFF (D-type Flip-Flop) symbol (h).

Figures (g) and (h)

Now it becomes simple to build more complex state machines such as counters, shift registers, and even complete CPUs.

Note that ROM (read-only memory) is not really memory in this sense; it's just another exmaple of combinatorial logic, where the outputs are a fixed function of the inputs.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Although modern trends favor edge-triggered latches, a very common pattern historically was for a circuit to use asynchronous latches which were divided into two (or more) groups; one clock wire operated all the latches in the first group and one operated all the latches in the second. In situations which don't need the maximum possible speed, such an approach can sometimes offer considerable savings in circuitry. \$\endgroup\$ – supercat Jan 27 '13 at 0:33
  • \$\begingroup\$ Thank you so much. Although this answer didn't really answer the posed question, it answered the next question that I had: "how do you go from combinatorial logic to sequential logic to 'memory'"? At first, the design of sequential logic seemed like a huge leap from combinatorial logic; reading your post showed that it is indeed a very intuitive progression :-) Thank you \$\endgroup\$ – chevestong Feb 6 '13 at 14:15

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.