We assume that the student knows everything that will be detailed in this chapter. The purpose is not to teach, but a quick review.

There are two kinds of digital circuit: Combinatorial and Sequential. Combinatorial Circuits have no memory, therefore they can described by a truth table. Sequential Circuits have memory therefore they are described by finite state machines (FSM).

1.1 Combinatorial Circuits

Combinatorial circuits have no memory. Therefore for a given input, they always give the same output. This means that they can be represented by a truth table.

Example: If we have a combinatorial circuits with 3 inputs, i1,i2, i3, and 2 outputs o1,o2, the input-output relation of a combinatorial circuit can be represent by following truth table.

In combinatorial circuits “every combination of inputs corresponds a row of a truth table. Hence, this circuits are known as “Combinatorial Circuits”

The basic combinatorial circuit elements are AND, OR and NOT Gates. Any combinatorial circuits can be constructed by using them. We will sometimes use XOR Gates in addition to this for practicality. The schematics of these circuit elements shown below.

For convenience, NOT Gates are usually compress into small circles. An example is shown below

1.1.1 Realization of Combinatorial Circuits

Given its truth table, any combinatorial circuit can be constructed as a two level AND\OR circuit by using a technique known as “Karnaugh Maps.” or complicated circuitry can be constructed by using Queen-McCluskey method. You should know at least Karnaugh maps from your digital design lectures..

Surprisingly, microprocessor design is not a very complicated topic. We will not design circuits complicated enough to require Karnaugh maps. In the department of combinatorial circuitry, all we’ll need are MSI circuits and simple gates.

1.1.2 Medium Scale Integration (MSI) Circuits

MSI Circuits are the next level of combinatorial circuits, as they can be constructed by using AND, OR and NOT gates. The MSI chips we will use are decoders, encoders, multiplexers, demultiplexers.

Decoders

Note that small arrows are placed on the wires indicate signal flow direction: Arrows on input lines points towards to decoder. Arrows on output lines points away from decoder. We will follow this convention thoughtout the book.

Encoders

Encoders are usually considered as just the reverse of decoders. But in actuality, they are much more complicated, as unlike decoders they have many ambiguous cases to solve. The case below is very simple.

But consider the case where there are multiple 1’s entering to the encoder.

Or what will be the output if all inputs are zero?

The problem of more than single 1’s as input is resolved by adding a priority mechanism to the encoder: If there is more than single 1 entering to the encoder, the encoder will only consider the input with highest index. For example, in the above figure, the priority encoder will only consider i6 as 1 and all the rest of the input lines will be assumed to be 0.

The problem of all-0 input is resolved by adding an “active” (A) output to the priority encoder. When all inputs are 0, the encoder is considered to be inactive and the active output becomes 0. In this case, the output of the encoder are undefined (or, “don’t care”, indicated by a letter d with a slash in the truth tables and diagrams). If any of the inputs is 1, the encoder is considered active and the “active” output becomes 1.

Below, a priority encoder with an active line is drawn and some examples of its operation is given. Active output is indicated with the capital letter “A”.

Here is the truth table for a 8X3 priority encoder with an active line. As usual, the active line is indicated by capital “A”.

Multiplexers

Demultiplexers

Demultiplexers are just the reverse of the multiplexers. If we make inputs outputs and outputs inputs then we will obtain demultiplexers from multiplexer.

1.1.3 Arithmetic and logical circuits

In this section, we will develop hardware circuits for various arithmetical and logical operations: Adding, Subtracting, Incrementing, Decrementing, bitwise and, bitwise or, bitwise xor, bitwise not.

Half Adders

The truth table for adding two 1-bit binary numbers is

number 1 number 2 result msb of result lsb of result

Number1         Number2         Result        MSB of Result          LSB of Result
    0               0              00               0                      0
    0               1              01               0                      1
    1               0              10               0                      1
    1               1              10               1                      0

Or, shown in a diagrammatical way,

Obviously,

the “least significant bit(lsb) of the result” is the xor is the XOR of number1 and number2
the “most significant bit(msb) of the result” is the AND of number1 and number2

Hence we can realize this adder as a two-gate circuit..

The circuit above is known as “half adder”. As mentioned above, it adds two 1-bit numbers. It has two inputs and two outputs..

Full Adders

Normally, we are not interested with adding 1-bit numbers. We are interested with adding arbitrary length numbers. Let us add 101101 and 011101 and see how the operation differs from the addition of single bit numbers:

As can be seen, the same thing happens in each vertical column (one such vertical column is circled in red for clarity): If we consider column i:

The most significant bit of the calculation from the previous vertical column (column i-1) is taken as carry-in
Three 1-bit numbers are added: ith bit of first number, ith bit of the second number, and carry-in
The result will be a 2-bit number. The most significant bit will be sent to the next column (column i+1) as carry-out, the least significant bit will be output.

In the table below, all the possible combinations that can occur in a column is shown..

Therefore, what we need is some digital circuit which can add three 1-bit numbers. We can construct such a circuit with two half-adders and a single or-gate.

Incrementer

Subtractor

In two’s complement arithmetic, it is very easy to obtain a subtractor from an adder:

Decrementer

Bitwise logical operations

1.2 Sequential Circuits

Sequential Circuits are circuits with memory. Therefore they cannot be represented by a truth table. A Sequential Circuits are usually defined as a finite state machine (FSM). The transition between the states is controlled by a clock. At every clock edge, FSM checks its inputs, and, depending on its inputs and on the state its currently in, transitions to a new state.

A FSM can be described by two equivalent representations: the state transition diagram and the state transition table.

1.2.1 An example FSM

The state transition diagram of an example FSM is given below:

FSM always starts at the start state, which is indicated by a double circle. In our diagram the start state is the state B. The state transition table for the same FSM is

Example: Let us consider, the input

          1010 0101 1001 0001

We assume that our FSM works with a 4HZ clock, ie changes state at every 0.25 seconds.

(CORRECT: in the figure above, at time=3.75 (0,C) must yield A as next state, not B)

1.2.2 State Assignment

Before realizing our circuit, we have to assign a unique binary number to each state. If we have n states, this number must be log2(n) [Round] bits long. State Assignment can be done arbitrarily, but some state assignments can be realized with lesser number of gates than the others, hence are more economical. To find the most economical state assignment is known as “State Assignment Problem”. Unfortunately, this problem is NP-complete.

For the above FSM, some of the possible state assignments are given below.

As our FSM consist of 3 states, we assign two-bit numbers to each state. We will use Assignment 1 (Ie: Blue Assigment) for the rest of this example. After the state assignment, the FSM diagram becomes

and the state transition table becomes

And the above example becomes

1.2.3 Timing Diagram

Before giving timing diagram of our example FSM, let us define conventions we will use. In timing diagram, x-axis defines time and y-axis defines voltage: 5 volts define logic 1 and 0 volts define logic 0. Further conventions given in figure below.

Before t=2 seconds, the above signal is logical 1. Between t=2 and t=4 seconds, it is logical 0. Between t=4 and t=6, it is unimportant(Ie, it can be both 1 and 0, this situation is known as “Don’t Care” in digital circuit designs) etc..

Now we can consider the timing diagram of our FSM. Our FSM is paced with a clock signal. There are two sorts of “edge”s in a clock signal: The positive edge and the negative edge. The positive edge occurs when the clock transitions from 0 to 1. The negative edge occurs when the clock transitions from 1 to 0. These are shown in the figure below.

The timing diagram is given below. Note that the input is only needed to be defined at the positive edges. The FSM does not respond to the input when there is no positive edge. States also change only when there is a positive edge. They don’t change and remain steady out of positive edges.

1.3 SR Flip Flops

Sequential circuits are realized by using flip-flops (FF’s) together with AND\/OR\/NOT gates. There are many different kinds of FF’s. Some examples are: SR-FF’s, D-FF’s, T-FF’s, JK-FF’s etc. In these lecture notes, we will only use SR_FF’s. We will review the theory of SR-FF’s below:

SR-FF is a 1-bit memory. Its state is indicated by its output, Q (Most flip flops also provide the negation of the state, Q-bar). It has two inputs: Set (S) and Reset (R). Its state transition table and FSM are given below:

(in the figure above, 5th line is wrong and must be corrected. Q_new must be 1)

SR FF has two states: 0 and 1. It changes its state only at the positive clock edges and keeps its state at other times.

To set the SR-FF (ie, to make its state 1), we make the inputs S=1, R=0 and wait for the positive clock edge.
To reset the SR-FF (ie, make its state 0), we the inputs S=0, R=1 and wait for the positive clock edge.
If we keep the inputs as S=0, R=0, the SR-FF will continue to “remember” its state. ie, if its state is Q=0, it will continue to have Q=0 or if its state is Q=1, it will continue to have Q=1.
The input S=1, R=1 is illegal. We should design our circuits to guarantee never to apply this input to an SR-FF.

Note that the above table can be compressed into

A sample run of the SR-FF is given below:

Note that the inputs (i,e S and R) are only important at the instant of positive clock edge. In all other times, FF completely disregards the inputs. Only at the positive clock edges, FF samples inputs and decides about the state (Q). In between the positive clock edges, the the input can change in any possible manner without affecting the state. It can even became illegal. For example, between clock edges 5 and 6, we have S=R=1, which is defined as “illegal”. This won’t affect FF behaviour as long as it doesn’t occur at positive clock edges.

1.4 Definition of an FSM state by an SR FF

1.5 Constructing a sequential circuit by using SR FF’s.

We will use the FSM given above to illustrate the procedure. First, we will slightly modify its state transition table as

Note that we have assigned every bit of the state to a flip-flop (ie, Q1 and Q0). Hence we have two FF’s representing the states. Also, as we do not have a state 11, we mark its next state as don’t care (d with a bar).

Next, we will add the inputs of the FF’s Q1 (S1 and R1) and Q0 (S0 and R0) to achieve the desired state transitions: