Logic Synthesis with a Minimum Number of Negative Gates:Algorithm DIMN

By -
Algorithm DIMN

Compared with the problem (1) of Procedure 35.1, problem (2) presents a far more serious difficulty. Thus, Algorithm DIMN (an acronym for Design of Irredundant Minimal Network) was developed to design a MOS network in single-rail input logic such that the number of gates is minimized and every connection among cells is irredundant (i.e., if any connection among logic gates is removed, the network output will be changed) [2,3]. Algorithm DIMN is powerful but is far more complex than the minimal labeling procedure (i.e., Phases 1 and 2 of Procedure 35.1). So, let us only outline it.

Procedure 35.2: Outline of Algorithm DIMN

1. All the nodes of a lattice are labeled by the minimal labeling procedure (i.e., Phases 1 and 2 of Procedure 35.1), starting with the top node and moving downward. Let the number of bits of each label be R. Then all the nodes are labeled by a procedure similar to the minimal labeling procedure, starting with the bottom node which is now labeled with the largest binary number of R bits, and moving upward on the lattice. Then, the first negative gate with irredundant MOSFETs is designed after finding as many don’t-cares as possible by comparing two labels at each node which are derived by these downward and upward labelings.

2. The second negative gate with irredundant MOSFETs is designed after downward and upward labelings to find as many don’t-cares as possible. This process is repeated to design each gate until the network output gate with irredundant MOSFETs is designed. D Unlike the minimal labeling procedure where the downward labeling is done only once and then the entire network is designed, Algorithm DIMN repeats the downward and upward labelings for designing each negative gate. The network derived by DIMN for the function x1x2x3x4 ∨ x1x2x3x4 ∨ x1x2x3x4 ∨ x1x2x3x4 , for example, has three negative gates, the same as that of the network derived by the minimal labeling procedure for the same function. The former, however, has only 12 n-channel MOSFETs, whereas the latter has 20 n-channel MOSFETs. DIMN usually yields networks that are substantially simpler than those designed by the minimal labeling procedure, but it has the same problems as Procedure 35.1 when the number of input variables of the function becomes large.

The computational efficiency of DIMN was improved [4]. Also, a version of DIMN specialized to two- level networks was developed [1].

Comments

Post a Comment

Popular posts from this blog

Square wave oscillators and Op-amp square wave oscillator.

By -
Image
Square wave oscillators If Fourier analysis is performed on a square wave it is found that the waveform is composed of many harmonics of the fundamental frequency. This rich harmonic content makes the square wave particularly useful as a quick test of amplifier performance. Examples of possible results are shown. The simplest way to produce a square wave is to make a sine wave oscillator in one of the ways described earlier, then feed the output to some form of squaring circuit such as a Schmitt trigger. This is the method adopted in most commercial sine/square wave generators. There are, however, several circuits for square wave oscillators and a description of the most common follows. Multivibrator Technically the multivibrator is a relaxation oscillator, working on the charging of a capacitor through a resistor. If a negative edge is applied to the circuit in (a), transistor TR 1 turns off the for time taken for the base voltage to return to 0 V. If the voltage step is
Read more

Adders:Carry Look-Ahead Adder.

By -
Image
Carry Look-Ahead Adder As previously stated, the carry, c i +1, produced at the i -th position is calculated as c i +1 = x i · y i ∨ c i ·( x i ⊕ y i ). This means that a carry is generated if both x i and y i are 1, or an incoming carry is propagated if one of x i and y i is 1 and the other is 0. Therefore, letting g i denote x i y i , we have c i +1 = g i ∨ c i p i , where p i = x i ⊕ y i . Here, g i is the formula for the carry generation condition at the i -th position, i.e., when g i is 1, a carry is generated at this position. Substituting g i –1 ∨ p i –1 c i –1 for c i , we get A carry look-ahead adder can be realized according to this expression, as illustrated in Figure 41.10 for the case of four bits [21]. According to this expression, c i +1’s are calculated at all positions in parallel. It is hard to realize an n -bit carry look-ahead adder precisely according to this expression, unless n is small, because maximum fan-in and fan-out restriction is violated at higher
Read more