Binary Decision Diagrams:Remarks

By -
Remarks

Several groups developed BDD packages, and some of them are open to the public. For example, the CUDD package [12] is well-known to BDD researchers in the U.S. Many other BDD packages may be found on the Internet. BDD packages, in general, are based on the quick search of hash tables and linked- list data structures. They greatly benefit from the property of the random access machine model [2], where any data in main memory can be accessed in constant time.

Presently, considerable research is in progress. Detection of total or partial symmetry of a logic function with respect to variables has been a very time-consuming problem, but now it can be done in a short time by BDDs [26,29]. Also, decomposition of a logic function, which used to be very difficult, can be quickly solved with BDD [5,21]. A number of new types of BDDs have been proposed in recent years. For example, the Zero-Suppressed BDD (ZBDD) [23] is useful for solving covering problems, which are used in deriving a minimal sum and other combinatorial problems. The Binary Moment Diagram (BMD) [7] is another type of BDD that is used for representing logic functions for arithmetic operations. For those who are interested in more detailed techniques related to BDDs, several good surveys [11,24,28] are available.

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