Circuit Design

A gate is an electronic device that computes a Boolean function.

• A gate has one or more inputs (which are simply voltage levels) and produces an output (voltage level).

• AND, OR, NOT, NAND, and NOR gates are particularly easy to implement electronically (with any number of inputs), and therefore are the gates used in practice.

A circuit is a combination of gates, where the outputs of some gates are the inputs of others.

• Each circuit may have one or more inputs, which are actually inputs to the gates in the circuit.

• A circuit may have one or more outputs.

Combinational vs Sequential Circuits

• produce an output that is a boolean function (combination) of the input values.

• are acyclic in that there are no cycles between the inputs of a gate and its outputs.

• have no memory; there is no way to remember previous inputs or outputs.

• are used to decode instructions and perform arithmetic.

Sequential circuits:

• produce an output that depends not only on the current input values, but also on the previous sequence of input values.

• are cyclic; the output of a gate at some moment in time eventually feeds into the input of that gate at some future time.

• can remember results of previous operations, and use those results as input.

• are used to build registers and memory units.

Combinational Circuit for an Encoder
for a 7 Segment Display

Consider a 7-segment display such as those used in most calculators:

  	       A
  	    -------
  	    |     |
  	  F |     | B
  	    |  G  |
  	    -------
  	    |     |
  	  E |     | C
  	    |     |
  	    -------
  	       D
  

We would like to design a combinational circuit that takes 10 different inputs (corresponding to the decimal digits 0-9) labeled i0..i9 and lights up the display segments A-G as needed to display the decimal digit specified in the input.

In particular, if input i0 is 1, then outputs A, B, C, D, E, and F should be 1 (producing a 0 on the display).

The boolean expressions describing each of the outputs are:

      A = i0 + i2 + i3 + i5 + i7 + i8 + i9
      B = i0 + i1 + i2 + i3 + i4 + i7 + i8 + i9
      C = i0 + i1 + i3 + i4 + i5 + i6 + i7 + i8 + i9
      D = i0 + i2 + i3 + i5 + i6 + i8
      E = i0 + i2 + i6 + i8
      F = i0 + i4 + i5 + i6 + i8 + i9
      G = i2 + i3 + i4 + i5 + i6 + i8 + i9
  

We can build this circuit with 7 OR gates (one for each segment in the display) some of which take up to 9 inputs.

A Sequential Circuit

The following is a sequential circuit, because the output of the AND gate is an input to the OR gate and vice versa.

      x------------->|   )
  		   |AND)---*---> z
  	       *-->|   )   |
  	       |           |
  	    *--|-----------*
  	    |  |
  	    |  *-----------*
  	    |              |
  	    *----->)       |
  		   )OR>----*
      y ------------>)
  

What does this circuit do?

• If x = y = 1, then z=1.

• If x=0, then z=0.

• If x=1, and y=0, then the circuit depends on the previous value of z.

The output of the circuit (z) is 1 if at some point in the past x and y were 1, and x has remained 1 ever since.

Constraints on Circuit Design

In designing efficient digital circuits there are numerous constraints to be considered, all of which impact the cost or speed of the resulting circuit.

• Circuit speed: every gate in the circuit introduces a delay (which may be as small as 10^-9 seconds), so the number of gates on the path between the input and output determine how quickly the output will be computed.

• Size limitations: the more gates we use in a circuit, the larger it will be. Large circuits are more expensive (in part because they have a higher failure rate) and slower, since signals must propagate from one end of the circuit to another, and the propagation speed is limited by the speed of light.

• Fan-in and Fan-out: The fan-in and fan-out of a gate is the number of inputs and outputs, respectively. Large fan-in or fan-out makes for slower gates.

A Ripple-Carry Adder

We have already seen how to construct a one-bit adder, which takes two input operands (x and y) and a carry-in bit (ci), and produces the sum (z) and a carry-out bit (co).

      x    y   ci    z   co
      ---------------------
      0    0    0    0    0
      0    0    1    1    0
      0    1    0    1    0
      0    1    1    0    1
      1    0    0    1    0
      1    0    1    0    1
      1    1    0    0    1
      1    1    1    1    1
  

The logical expression for z is:

  (NOTx y ci)+(x NOTy ci)+(x y NOTci)+(x y ci)
  

The logical expression for co is:

  (NOTx NOTy ci)+(NOTx y NOTci)+(x NOTy NOTci)+(x y ci)
  

A 32-bit ripple-carry adder is simply a sequence of 32 one-bit adders, where the carry-out bit from adder[i] provides the carry-in bit for adder[i+1]. The carry-in[0] is 0, and the sum is carry-out[31], z[31], z[30],..., z[0].

In a ripple-carry adder, the carry bits ripple through the circuit from adder[0] up to adder[31]. Thus, the delay of a ripple-carry adder of N bits is proportional to N.

We would like to design an adder with a smaller delay, especially given trends towards larger word sizes (64 bits).

Design of a Divide-and-Conquer Adder

To add two N-bit numbers, we can use a divide-and-conquer approach in which we build a circuit that adds two N/2-bit numbers, and then use two such circuits and combine their results.

To build a 32-bit adder, we would use two 16-bit adders to add the left and right halves of the operands in parallel, and then we would combine the results.

• Each 16-bit adder would be composed of two 8-bit adders.
• Each 8-bit adder would be composed of two 4-bit adders.
• Each 4-bit adder would be composed of two 2-bit adders.
• Each 2-bit adder would be composed of two 1-bit adders.

Since we cannot know whether the lower half of the operands will result in a "carry" into the upper half, how can the two adders function in parallel?

• we compute two sums for the upper half of the operands; one assuming there is a carry, and the other assuming there is no carry.

• we use additional circuitry to select which of the two sums to use in the result.

Design of an N-Adder

Suppose we have two N-bit operands, expressed in binary form as x1..xN and y1..yN.

We will design an N-adder that computes:

• the sum without carry, s1..sN, the N-bit sum of x1..xN and y1..yN assuming no carry into the sum of xN and yN.

• the sum with carry, t1..tN, the N-bit sum of x1..xN and y1..yN assuming there is a carry into the sum of xN and yN.

• the carry-propagate bit, p, which is 1 if there is a carry out of the leftmost place (x1 and y1), on the assumption there is a carry into the rightmost place.

• the carry-generate bit, g, which is 1 if there is a carry out of the leftmost place (x1 and y1) regardless of whether there is a carry into the rightmost place.

We will first show how to build a 1-bit adder component, and then show how to build an N-adder out of 1-bit adders.

A 1-bit Adder

A 1-adder computes the following Boolean functions:

      x    y    s    t    p    g    
      --------------------------
      0    0    0    1    0    0
      0    1    1    0    1    0
      1    0    1    0    1    0
      1    1    0    1    1    1
  

The corresponding logical expressions are:

      s = (NOTx y) + (x NOTy)
      t = (NOTx NOTy) + (xy)
      p = x + y
      g = xy
  

A 2-bit Adder from 1-bit Adders

We can build a 2-bit adder using two 1-bit adders.

            --------
  x1 ------>| Low  | -----> sL --------------------> s1
            | Order| -----> tL --------------------> t1
  y1 ------>| 1-bit| -----> gL -------*
            | Adder| -----> pL ----*  |
  	  --------               |  |
  			         |  |
  				 |  |
  				 |  *--->|F|-----> g
            --------               *------>|I|-----> p
  x2 ------>| High | -----> sH ----------->|X|-----> s2
            | Order| -----> tH ----------->|I|-----> t2
  y2 ------>| 1-bit| -----> gH ----------->|T|
            | Adder| -----> pH ----------->| |
  	  --------
  

The sum of the low-order bits (s1 or t1) doesn't depend on whether there is a carry from the low-order bits to the high-order bits, so we compute the sum of x1 and y1 into sL and tL, and produce those values as the resulting sum of the low-order bits (with different assumptions about carry-in bits).

The sum of the high-order bits (s2 and t2) does depend on whether there is a carry (gL and pL), so we take the carry bits from the first adder, and the summation results from the second adder, and combine them together in the circuit labeled FIXIT to get the final result.

Combining the Results of 1-bit Adders

FIXIT computes its outputs using the following expressions:

• p = gH + pHpL: that is, if there is a carry into the low-order part of the circuit, there is a propagation carry out of the high-order part of the circuit if both the lower-order and high-order bits propagate a carry (pHpL) or if there is a carry out of the high-order bits (gH).

• g = gH + pHgL: that is, if there is no carry into the low-order part of the circuit, there is a carry out of the high-order part if there is a carry out of the high-order bits anyway (gH) or if there is a carry from the low-order bits (gL), and the high-order bits propagate that carry (pH).

• s2 = (sH NOTgL) + (tH gL): that is, the sum of the high order bits (under the assumption of no carry in from the right end of the circuit) is sH if there is no carry generated from the low-order bits, and tH otherwise.

• t2 = (sH NOTpL) + (tH pL): that is, the sum of the high order bits (under the assumption of a carry in from the right end of the circuit) is tH if there is a carry propagated through the low-order bits, and sH otherwise.

We can generalize this construction to N bits, and create an N-adder where the circuit delay is 3(log N + 1), rather than the O(N) delay in the ripple-carry adder.

Sequential Circuits for Memory Elements

A memory element is a collection of gates capable of producing its last input as output.

Memory elements are sequential circuits; that is, circuits whose behavior depends not only on the current inputs, but also on the past history.

A flip-flop is a 1-bit memory element. A typical flip-flop circuit takes two inputs and produces a single output.

• Input data-in is the binary data value to be stored in the memory element.

• Input load determines whether the circuit is being asked to load a new binary value. Whenever load=0, the circuit produces as output the stored value (which is the last value loaded into the memory element). Whenever load=1, the circuit stores the value of data-in and produces it as output.

Flip-Flop Circuit

Here is a sequential circuit for a binary flip-flop:

                  *----------------------*
                  |                      |
                  *-->|AND|              |
  load----->|NOT|---->| 1 |------>|OR|---*--- data-out
        |                     *-->| 1|
        |                     |
        |                     |
        *------------>|AND|---*
  data-in ----------->| 2 |
  

When load is 0:

• the gate labeled AND2 produces a zero, and therefore doesn't affect data-out.

• the gate labeled AND1 produces the previous value of the flip-flop as its output, which becomes data-out.

• so, the circuit simply outputs the previous stored value.

When load is 1:

• the gate labeled AND1 produces a zero, and therefore doesn't affect data-out.

• the gate labeled AND2 produces the value of data-in, which becomes data-out.

• so, the circuit simply outputs data-in.