Iterative Design: A Design Example
First, it is worth reviewing the points made in the document Iterative Design: A First Approach as to when it is appropriate or inappropriate to embark upon an iterative design for some system:
· Iterative design works when the all of the equations in a set of equations operate in the same fashion, or in some fashion that corresponds to their position in a set of equations. The only real difference in each equation is the position of the output in the set. Further, we are assuming that each equation depends on a well-defined subset of the input set – each one in the same fashion
· Based on these assumptions, we hypothesize that if we can complete the design of a general equation describing one arbitrary output, we can then iterate that equation over the range of precision required by the output set, considering boundary conditions where appropriate.
· Begin by trying to form the equation for some arbitrary state or output. (yi+, zi, etc.)
· Look for an input or inputs that partition the operation of the equation into distinct (and perhaps mutually exclusive) modes. In [the shift register], the mode select inputs determine what the circuit does for any combination of that pair of inputs. Since one of the four combinations of S1 and S0 is always present, designing the circuit amounts to determining what the output does for each combination of S1 and S0.
· After you have fully derived the general equation, iterate the equation for each valid value of i.
· Check each equation for a boundary problem; boundary problems exist when iterating the general equation requires a bit that doesn’t exist. Solving the boundary problem amounts to establishing a boundary question that accounts for the undefined bit in a manner that is consistent with the specification. Just as it is in the process of deriving the general equation, establishing boundary conditions is a matter of studying the specification and understanding the behavior of the circuit.
The design problem is that it isn’t always easy to find the way in which a specification satisfies the assumptions that allow us to apply the hypothesis described above. Here is one such design example:
Specification
A comparator circuit takes in two n-bit inputs called A (which consists of An – 1An – 2…A1A0) and B (which consists of Bn – 1Bn – 2…B1B0) and provides three outputs, G, E, and L. If A and B are taken to represent unsigned binary numbers, the three mutually-exclusive outputs operate as follows:
G = 1 if and only if A > B
L = 1 if and only if A < B
E = 1 if and only if A = B
Implement the comparator circuit using an iterative design.
The Iterative Design Principle
Imagine that each of the equations being designed represents one cell of a multi-cell machine. Each of the cells represents a logic circuit that is identical to all of the other cells. But the cells do not really represent identical logic functions, as each one takes in a different subset of the inputs:
x0 x1 xi xn – 2 xn – 1
a0 a1 a2 ai ai+1 an – 2 an – 1 an
z0 z1 zi zn – 2 z n – 1
Figure 1: The Unilateral Iterative Network
In this unilateral iterative network, each cell is driven by a set of inputs, and provides a set of outputs. Specifically, this circuit has n primary inputs labeled as xk, k Î{0,1,…,n – 1} and n primary outputs labeled as zk, k Î {0,1,…,n – 1}.
Symbolically, rather than representing each primary output as being a function of all of the primary inputs:
zk = f(x0, x1,…, xn – 1) for all k Î{0,1,…,n – 1}
We instead represent each primary output as being a function of some subset of the primary inputs. In this case, the cell that provides each primary output zk is receiving only the primary input xk. This doesn’t always have to be the case – it could be appropriate for each cell to receive multiple primary inputs, or even all of them. It depends on how complex the system is.
The system is not such that even a subset of the primary inputs is sufficient to define each primary output. But if each cell had the capacity to communicate with other cells, then this additional information taken together with the subset of primary inputs could be used to implement each function.
We define a set of secondary inputs ak k Î {0,1,…,n – 1}. In addition to receiving its primary input(s), a cell also receives some number of secondary inputs. In this case, each cell is receiving one secondary input. Each primary output is therefore expressed as function of one primary input, which represents external information, and one secondary input, which represents information communicated from another cell:
zk = f(xk, ak) for all k Î{0,1,…,n – 1}
Each circuit also generates a secondary output. This secondary output, when made available to another cell, becomes a secondary input to that cell. So every cell’s secondary output(s) are another cell’s secondary input(s).
Just like the primary outputs, the secondary outputs are expressed as functions of that cell’s primary input(s) and secondary input(s):
ak+1 = f(xk, ak) for all k Î{0,1,…,n – 1}
We can imagine that each cell in the network is similar to a sequential circuit. When the circuit is in some initial present state (a0) and receives an input (x0), it supplies an output (z0) and a next state (a1). But the next state eventually becomes a present state to the same sequential circuit. When a new input (x1) is supplied with the new present state, the circuit produces an output (z1) and a new next state (a2). This process repeats until the “final” input (xn – 1) is applied to the “final” present state (an – 1) to produce the “final” output (zn – 1) and a “final” next state (an),
What makes an iterative circuit different from a sequential circuit is that as opposed to applying the inputs and states in a time sequence, the primary inputs and secondary inputs are applied in a “space” sequence, where all of the circuits exist simultaneously. In this fashion, a set of secondary inputs applied in parallel results in a set of outputs that are derived in series.
Incidentally, the iterative network shown in Figure 1 is unilateral because the information communicated by the secondary inputs moves in one direction. We could conceive of a bilateral network, where secondary information is communicated in both directions. Perhaps not surprisingly, the bidirectional shift register is an example of such a circuit. The secondary outputs (which are actually the same as the primary outputs) must be able to move in either direction for the purpose of performing either a left-shift or a right-shift.
Interlude: The Ripple-Carry Adder
Really, this is the principle behind a ripple-carry adder. Take the adder to have two sets of n-bit addends A
(An – 1An – 2…A1A0) and B (Bn – 1Bn – 2…B1B0). The circuit derives an n-bit sum S(Sn – 1Sn – 2…S1S0).
Each full-adder receives the bits of the addends that correspond to that adder’s place of significance. When the addends are applied in parallel, the least-significant full adder supplies the first output to be derived – S0. On the face of it, this sum bit is a function of its addend bits (A0 and B0) only. This sum bit is a primary output.
The same “cell” of the adder that derives S0 also derives a carry-out that we will call C1. C1 (a secondary output) becomes the carry-in of the next cell. This carry-in, taken together with a new set of primary inputs (the addend bits of that full adder, namely A1 and B1) produces the sum bit S1 and a new carry-out C2. C2 is the carry-in of the next cell; along with A2 and B2, the circuit derives S2 and C3. And so forth.
Assuming that the addition mechanism doesn’t depend on the place of precision, we can design the adder iteratively by obtaining functions for primary output Si and secondary output Ci+1 in terms of primary inputs Ai and Bi, and secondary input Ci. These two output functions can be used to construct a full adder that, when interconnected in the function indicated here, produces an adder of arbitrary precision consisting of n identical unit cells.
Before we return to the original example, we can observe a boundary condition. The least significant cell (the one producing S0 and C1) does not have a corresponding cell of lesser significance to supply it with C0. There can be no cell of lesser significance than the cell of least significance. C0 therefore represents a boundary condition – one that must be accounted for if we are to say that all of the cells are identical. It is trivial to demonstrate that if C0 is made to equal zero, then the least significant cell will operate correctly.
Compare what we’ve done to the alternative – eliminating the carries as parameters by making each sum bit a function of all of the inputs instead of a subset of them. On the face of it, we would have to express all n sum outputs as functions of the 2n inputs – all of the input bits of both A and B. The iterative design only requires us to express two 3-variable functions as opposed to n 2n-variable functions. The work is simpler, and the equations are simpler. Have we really gotten something for nothing? (I’ll answer this question in class.)
The Comparator Design
Back to the comparator circuit. To perform this iterative design, we’ll try a different approach. We’re going to implement a one-bit comparator cell, and then institute the connections that will allow the individual cells to communicate.
Let’s start by making a simple truth table that expresses such a one bit comparator:
A0 / B0 / G0 / L0 / E00 / 0 / 0 / 0 / 1
0 / 1 / 0 / 1 / 0
1 / 0 / 1 / 0 / 0
1 / 1 / 0 / 0 / 1
We can infer the following equations from this truth table:
G0 = A0B0¢
L0 = A0¢B0
E0 = A0¢B0¢ + A0B0 = A0 Ä B0
So far, so good.
Now let’s try to implement a two-bit comparator. We’ll use the logic that we’ve just designed as the basis for each of the individual cells and embark on a thought experiment.
Which of these two 2-bit numbers is larger, A or B? (The number heading each column indicates the bit of precision in each of the two numbers.)
1 / 0A / 1
B / 0
I apologize for spilling ink over the bit of higher-significance of each number. Now, which number is larger?
Surely you said that A > B, since A0 is equal to 1 and B0 is equal to 0. Of course, this is a lie. The only way that A is larger than B under these conditions is if A1 = B1. If A1 is 0 and B1 is 1, then A0 and B0 play no role in determining which of the numbers is larger. The decision that A < B was already made in bit position 1. If A1 is 1 and B1 is 0, then A0 and B0 again play no role in determining which of the numbers is larger. This time, the decision that A > B is the one that was already made in bit position 1.
We have the makings of an iterative principle: A decision as to whether A > B, A < B, or A = B can be made in a particular cell, unless one of the first two decisions was already made in the previous cell.
Let’s return to the equation for G0, L0, and E0. Gi, Li, and Ei represent indicators that a decision has been made about the number at bit i. So let’s use the information provided from bit 1 to “help” bit 0 make a decision. We’ll even describe them as sentences:
G0 = 1 if G1 = 1 (a decision was already made in the upper bit), or if E1 = 1 (a decision was not made in the upper bit) and A0 = 1 and B0 = 0.
L0 = 1 if L1 = 1 (a decision was already made in the upper bit), or if E1 = 1 (a decision was not made in the upper bit) and A0 = 0 and B0 = 1.
E0 = 1 if E1 = 1 (a decision was already made in the upper bit), and if A0 and B0 are equal.
These statements can be easily converted into logic equations:
G0 = G1 + E1(A0B0¢)
L0 = L1 + E1(A0¢B0)
E0 = E1(A0¢B0¢ + A0B0)
And now for the iterative step: The above sentences can be applied to any bit of precision, regardless of where it is (subject to a boundary condition that we will address shortly). This gives:
Gi = Gi+1 + Ei+1(AiBi¢)
Li = Li+1 + Ei+1(Ai¢Bi¢)
Ei = Ei+1(Ai¢Bi¢ + AiBi)
Thus, each cell is producing a set of primary outputs (Gk, Lk, Ek) that is also acting as a set of secondary outputs. The secondary outputs of one cell are the secondary inputs of the next cell. It might seem as though we’d need more information than what is shown here, but keep in mind that the outputs G, L, and E are mutually exclusive.