Difference between Combinational and Sequential Logic

Introduction

Combinational logic circuits implement Boolean functions. Boolean functions are mappings of input bitstrings to output bitstrings. These circuits are functions of input only.

What does that mean? It means that if you feed in an input to a circuit, say, 000, then look at its output, and discover it is, say, 10, then the output will always be 10 for that circuit, if 000 is the input. 000 is mapped to 10.

If that value were not the same every single time, then the output must not completely depend on 000. Something else must be affecting the output. Combinational logic circuits always depend on input.

Another way to define something that is a function of input is to imagine that you are only allowed to use input variables xk-1,...,x0, i.e. data inputs, cm-1,...,c0, i.e., control inputs, to write the function. This function can not depend on global variables or other variables.

Example: Coke machine

Let's consider a Coke machine to see if it is functional (i.e., behaves like a mathematical function). We want to see if its output is solely dependent on the input.

Imagine this Coke machine only sells Coke, and that the price of a Coke is 75 cents. Furthemore, assume that it can only take quarters. Once 75 cents is deposited, a Coke is dispensed. You don't even have to press a button.

You see this Coke machine, and think "I want a Coke", and you happen to be holding several quarters. You place the first quarter in the machine, and out comes...nothing! Undaunted, you put another quarter in, and out comes....nothing! Frustrated, you decide to put in yet another quarter, and out comes a Coke! Smooth, refreshing, bubbly Coke! You drink, and are content.

Then, envigorated by both caffeine and sugar, you begin to think "Is this Coke machine a function?" To answer the question, think about how the machine behaved. You gave the same input, three times in a row, but it did not produce the same output, three times in a row.

A mathematical function maps inputs to outputs. Thus, once you know what the input maps to, that should be it. In this case, the input (a quarter) mapped to nothing, nothing, and soda. So, clearly, this does not behave like a function.

What's happening? Clearly, the machine is storing some information. In particular, it's records how much money you have entered so far. The output is determined not only by the input, but also by this stored information.

This stored information is an example of state. State is basically internal information. Imagine, for example, that you have a linked list called list. You call list.size(). Does that method call always return the same value?

The answer is no. The method call will return the current size of the linked list, which may change over time, as elements are added or removed from the list. Thus, the method is computing its value not only on the input (and there is none, since the size() method requires no arguments), but also based on the number of nodes in the object.

You can think of the data members as state. It is internal information recorded by the object. Any method does its computation based on the arguments passed in and based on the values of the data members.

Sequential Circuits

For this course, we represent states by a k-bit UB number. Given k bits, we can have up to 2k different states.

Here are some of the key things to notice:

For example, suppose you are currently in state 00, and see an input of 1. This may produce an output of, say, 10, and then produce feedback that tells the state box to update to state 01 by the next clock edge.

Summary

A sequential circuit uses flip flops. Unlike combinational logic, sequential circuits have state, which means basically, sequential circuits have memory.

The diagram shown earlier is one way to model sequential circuits. They can be modelled as finite state machines. We'll describe those in more detail in a future set of notes, so if you don't understand it, that's OK. It should be clearer in a future set of notes.

The main difference between sequential circuits and combinational circuits is that sequential circuits compute their output based on input and state, and that the state is updated based on a clock. Combinational logic circuits implement Boolean functions, so they are functions only of their inputs, and are not based on clocks.