2. Bubble Pushing and K-Maps

In this section, we will consider two techniques to formulate equivalent circuits.

1. The bubble pushing method to transform circuits using NANDs or NORs into a a circuit that uses AND and OR gates to make it more readable.

2. Using K-Maps to build a smaller circuit that is equivalent to the original circuit but uses less gates.

Both algorithm are based on the simple basic logic equivalence like double inversion

(2.1)

or de Morgans law

(2.2)

(2.3)

2.1. Equivalence of Basic Circuits

In the first experiment, we will use truth tables computed by the Digital tool to validate the three equivalences stated in (2.1), (2.2), and (2.3).

Tasks

1. Use the Digital tool to draw each of the three original circuits Fig. 2.1.1

   

   Fig. 2.1.1 NOT-NOT (left), NAND (middle), and NOR (right) circuit.

   and the three corresponding transformed circuits in Fig. 2.1.2

   

   Fig. 2.1.2 Transformed NOT-NOT (left), NAND (middle), and NOR (right) circuit.

   representing the left- and right-hand sides of the equations (2.1), (2.2), and (2.3), respectively.

   Hint

   You need to add labeled inputs and outputs to the circuits.

2. Use the analyze option (F9, Analyse/Analyse) from the Digital tool to derive the truth table for each circuit.

3. Compare the resulting truth tables for each circuit pair and validate their equivalence, i.e., check that the original and transformed circuits produce the same outputs.

4. Save and submit the circuits (as {NOT-NOT,NAND,NOR}_{orig,trans}.dig e.g., NOT-NOT_orig.dig and NOT-NOT_trans.dig) and the truth tables in corresponding csv-files (as NOT-NOT_orig.csv and NOT-NOT_trans.csv).

2.2. Bubble Pushing Algorithm I

The bubble pushing algorithm is a method to transform a combinational circuit that uses NAND, NOR, and NOT gates into an equivalent circuit that only uses AND, OR, and NOT gates.

The algorithm can be described by the following set of rules:

1. Begin at the output of the circuit and work toward the inputs

2. Push any bubbles on the final output back toward the inputs

3. Draw each gate so that bubbles cancel

Use the bubble pushing algorithm for the circuit shown in Fig. 2.2.1.

Fig. 2.2.1 Bubble Pushing Circuit 1

Tasks

1. Derive (by hand) an equivalent circuit for the circuit depicted in Fig. 2.2.1 that only uses AND, OR, and NOT gates.

2. Draw the original and transformed circuit in the Digital tool and derive their corresponding truth tables.

3. Use the truth tables to validate the equivalence of both circuits, i.e., check that the original and transformed circuit produce the same outputs.

4. Save and submit the equivalent boolean equation in SOP (as bubble1.txt) besides its circuit (as bubble1.dig) and truth table (in csv-format as bubble1.csv).

2.3. Bubble Pushing Algorithm 2

Use the bubble pushing algorithm to derive an equivalent equation in sum-of-product (SOP) form.

Fig. 2.3.1 Bubble Pushing Circuit 2

Tasks

1. Derive the equivalent boolean equation (in SOP) for the circuit in Fig. 2.3.1.

2. Draw the transformed circuit in the Digital tool and derive the corresponding truth tables.

3. Use the truth tables to validate the equivalence of both circuits.

4. Save and submit the equivalent boolean equation in SOP (as bubble2.txt) besides its circuit (as bubble2.dig) and truth table (in csv-format as bubble2.csv).

2.4. Bubble Pushing Algorithm 3

Use the bubble pushing algorithm to derive an equivalent equation in sum-of-product (SOP) form.

Fig. 2.4.1 Bubble Pushing Circuit 3

Tasks

1. Derive the equivalent boolean equation (in SOP) for the circuit in Fig. 2.4.1.

2. Draw the transformed circuit in the Digital tool and derive the corresponding truth tables.

3. Use the truth tables to validate the equivalence of both circuits.

4. Save and submit the equivalent boolean equation in SOP (as bubble3.txt) besides its circuit (as bubble3.dig) and truth table (in csv-format as bubble3.csv).

2.5. K-Maps 1

Simplify the following boolean equations using Boolean theorems. Check for correctness using a truth table or K-map.

Tasks

1. Simplify each of the given boolean equations.

2. Draw reasonably simple circuits for the simplified equations in the Digital tool.

3. Use truth tables to validate the correctness of the simplified circuits.

4. Save and submit the simplified circuits (as kmap1-{1,2,3}.dig) besides their truth tables (in csv-format as kmap1-{1,2,3}.csv).

2.6. K-Maps 2

Simplify the following boolean equations.

Tasks

1. Simplify each of the given boolean equations.

2. Draw reasonably simple circuits for the simplified equations in the Digital tool.

3. Use truth tables to validate the correctness of the simplified circuits.

4. Save and submit the simplified circuits (as kmap2-{1,2,3}.dig) besides their truth tables (in csv-format as kmap2-{1,2,3}.csv).

2.7. K-Maps 3

Simplify the following boolean equation using a K-map.

Tasks

1. Simplify the given boolean equation using a K-map.

2. Draw a reasonably simple circuit for the simplified equation in the Digital tool.

3. Use the truth table to validate the correctness of the simplified circuit.

4. Save and submit the simplified circuit (as kmap3.dig) besides its truth table (in csv-format as kmap3.csv).