Bubble Pushing and K-Maps
=========================
In this section, we will consider two techniques to formulate equivalent circuits.

#. 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.
#. 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

.. math:: 
   \overline{\overline{B}} = B
   :label: NOTNOT
   
or de Morgans law

.. math::
  \overline{{B_0*B_1}}=\overline{B}_0+\overline{B}_1 
  :label: NAND

.. math::
  \overline{B_0+B_1}=\overline{B}_0*\overline{B}_1.
  :label: NOR

Equivalence of Basic Circuits
-----------------------------

In the first experiment, we will use truth tables computed by the `Digital <https://github.com/hneemann/Digital>`_ tool to
validate the three equivalences stated in :eq:`NOTNOT`, :eq:`NAND`, and :eq:`NOR`.

.. admonition:: Tasks

   #. Use the `Digital <https://github.com/hneemann/Digital>`_ tool to draw each of the three original circuits :numref:`fig:orig`

      .. figure:: /Bubble_KMaps/pics/NOTNOT1.svg
         :name: fig:orig
         :align: center

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

      and the three corresponding transformed circuits in :numref:`fig:trans`

      .. figure:: /Bubble_KMaps/pics/NOTNOT2.svg
         :name: fig:trans
         :align: center

         Transformed NOT-NOT (left), NAND (middle), and NOR (right) circuit.
      
      representing the left- and right-hand sides 
      of the equations :eq:`NOTNOT`, :eq:`NAND`, and :eq:`NOR`, respectively.

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


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

   #. 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.

   #. 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``).

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:

   #. Begin at the output of the circuit and work toward the inputs	
   #. Push any bubbles on the final output back	toward the inputs	
   #. Draw each	gate so that bubbles cancel	

Use the bubble pushing algorithm for the circuit shown in :numref:`fig:bubble1`.

   .. figure:: /Bubble_KMaps/pics/bubble1.svg
      :name: fig:bubble1
   
      Bubble Pushing Circuit 1

.. admonition:: Tasks

  #. Derive (by hand) an equivalent circuit for the circuit depicted
     in :numref:`fig:bubble1` that only uses AND, OR, and NOT gates.

  #. Draw the original and transformed circuit in the `Digital <https://github.com/hneemann/Digital>`_ tool and derive their corresponding truth tables.

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

  #. 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``). 


Bubble Pushing Algorithm 2
--------------------------

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

   .. figure:: /Bubble_KMaps/pics/bubble2.png
      :name: fig:bubble2
   
      Bubble Pushing Circuit 2
   
.. admonition:: Tasks

  #. Derive the equivalent boolean equation (in SOP) for the circuit in :numref:`fig:bubble2`.

  #. Draw the transformed circuit in the `Digital <https://github.com/hneemann/Digital>`_ tool and derive the corresponding truth tables.

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

  #. 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``). 


Bubble Pushing Algorithm 3
--------------------------

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

   .. figure:: /Bubble_KMaps/pics/bubble3.png
      :name: fig:bubble3
   
      Bubble Pushing Circuit 3
   
.. admonition:: Tasks

  #. Derive the equivalent boolean equation (in SOP) for the circuit in :numref:`fig:bubble3`.

  #. Draw the transformed circuit in the `Digital <https://github.com/hneemann/Digital>`_ tool and derive the corresponding truth tables.

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

  #. 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``). 


K-Maps 1
--------

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

.. math::
   :nowrap:

   \begin{eqnarray}
   Y &=& A*C +\overline{A}*\overline{B}*C\\
   Y &=& \overline{A}*\overline{B} + \overline{A}*B*\overline{C} +\overline{(A+\overline{C})}\\
   Y &=& \overline{A}*\overline{B}*\overline{C}*\overline{D}+A*\overline{B}*\overline{C}+A*\overline{B}*C*\overline{D}+A*B*D+\overline{A}*\overline{B}*C*\overline{D}+B*\overline{C}*D+\overline{A}
   \end{eqnarray}

.. admonition:: Tasks

  #. Simplify each of the given boolean equations.

  #. Draw reasonably simple circuits for the simplified equations in the `Digital <https://github.com/hneemann/Digital>`_ tool.

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

  #. 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``). 


K-Maps 2
---------

Simplify the following boolean equations.

.. math::
   :nowrap:

   \begin{eqnarray}
   Y  &=& B*C+\overline{A}*B*C+\overline{B*\overline{C}}\\
   Y  &=& A*D+B+\overline{A+B+C}*D\\
   Y  &=& \overline{A}*B*\overline{C}*D+A*B*C*D +\overline{(\overline{B}+D)}*E
   \end{eqnarray}   

.. admonition:: Tasks

  #. Simplify each of the given boolean equations.

  #. Draw reasonably simple circuits for the simplified equations in the `Digital <https://github.com/hneemann/Digital>`_ tool.

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

  #. 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``). 

K-Maps 3
--------

Simplify the following boolean equation using a K-map.

.. math::

   Y = A*\overline{B}*\overline{C}+A*\overline{B}*C+A*B*\overline{C}+A*B*C

.. admonition:: Tasks

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

  #. Draw a reasonably simple circuit for the simplified equation in the `Digital <https://github.com/hneemann/Digital>`_ tool.

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

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