A gate is an electronic device that computes a Boolean function.
A circuit is a combination of gates, where the outputs of some gates are the inputs of others.
Sequential circuits:
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.
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?
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.
In designing efficient digital circuits there are numerous constraints to be considered, all of which impact the cost or speed of the resulting circuit.
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).
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.
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?
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:
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-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
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.
FIXIT computes its outputs using the following expressions:
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.
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.
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:
When load is 1: