Combinational Logic Design
==========================
Boolean expressions can be represented in three different ways:
#. as a logical formula,
#. as a truth table, or
#. as a logical circuit build from the list of symbols given in :numref:`fig:logic_symbols`.
.. figure:: /Boolean_Basics/pics/logic_symbols.svg
:name: fig:logic_symbols
Logical gate symbols to draw combinational circuits
For example, the simple boolean expression with three variables
.. math::
Y = \overline{B}*\overline{C}+A*\overline{B}
:label: simpleexample
is also represented by the logical circuit depicted in :numref:`fig:simpleexample` and the truth values stated in :numref:`tab:simpleexample`.
.. figure:: /Boolean_Basics/pics/simple_example.svg
:name: fig:simpleexample
Circuit for the expression in Eq. :eq:`simpleexample` and the values stated in :numref:`tab:simpleexample`.
.. _tab:simpleexample:
.. table:: Truth-table for the simple example given by Eq. :eq:`simpleexample` with minterms.
:align: center
:widths: 20 20 20 20 20 20 20 20 20
+----------+-------------------------------+--------------------------+-------------------------+------------------+-------------------------+-------------------+-------------------+-------------+
| A | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
+----------+-------------------------------+--------------------------+-------------------------+------------------+-------------------------+-------------------+-------------------+-------------+
| B | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
+----------+-------------------------------+--------------------------+-------------------------+------------------+-------------------------+-------------------+-------------------+-------------+
| C | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
+----------+-------------------------------+--------------------------+-------------------------+------------------+-------------------------+-------------------+-------------------+-------------+
| Y | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
+----------+-------------------------------+--------------------------+-------------------------+------------------+-------------------------+-------------------+-------------------+-------------+
| minterms | :math:`\bar{A}\bar{B}\bar{C}` | :math:`\bar{A}\bar{B}C` | :math:`\bar{A}B\bar{B}` | :math:`\bar{A}BC`| :math:`A\bar{B}\bar{C}` | :math:`A\bar{B}C` | :math:`AB\bar{C}` | :math:`ABC` |
+----------+-------------------------------+--------------------------+-------------------------+------------------+-------------------------+-------------------+-------------------+-------------+
.. hint:: Note that a logical formula is derived from the truth table by summing all minterms, i.e.,
.. math::
Y = \overline{B}*\overline{C}+A*\overline{B}=\bar{A}\bar{B}\bar{C}+A\bar{B}\bar{C}+A\bar{B}C.
:label: simpleexamplenf
Min-Term
--------
In the first example, we will derive logical expressions that yields the same output for values given in a truth table.
.. _tab:Min-Term:
.. table:: Truth-table for the unknown circuit.
:align: center
+------+---+---+---+---+
| A | 0 | 0 | 1 | 1 |
+------+---+---+---+---+
| B | 1 | 0 | X | X |
+------+---+---+---+---+
| C | X | X | 0 | 1 |
+------+---+---+---+---+
| Y1 | 1 | 0 | 1 | 0 |
+------+---+---+---+---+
| Y2 | 0 | 0 | 1 | 1 |
+------+---+---+---+---+
| Y3 | 0 | 0 | 0 | 1 |
+------+---+---+---+---+
.. hint:: X are `Don't cares`, i.e. values that can be either true (1) or false (0).
.. admonition:: Tasks
#. Derive an equivalent logical expressions for the outputs `Y1`,`Y2`, and `Y3` from the truth table stated in :numref:`tab:Min-Term`.
#. Evaluate the three expressions for all possible inputs to derive a new truth table.
#. Use both truth tables to validate the correctness of your expressions.
#. Save your truth table (in csv-format as ``min_term.csv``) and formula (as ``min_term.txt``)
DIGITAL
-------
In this experiment, we will draw and inspect our first combinational circuit using the `Digital <https://github.com/hneemann/Digital>`_ tool.
The circuit represents the simple XOR expression of two inputs and one output given by
.. math::
Y = A \bigoplus B.
:label: XOR
The truth values for this expression are stated in :numref:`tab:XOR`.
.. _tab:XOR:
.. table:: Truth-table for the XOR expression stated in Eq. :eq:`XOR`.
:align: center
+-----+---+---+---+---+
| A | 0 | 0 | 1 | 1 |
+-----+---+---+---+---+
| B | 0 | 1 | 0 | 1 |
+-----+---+---+---+---+
| Y | 0 | 1 | 1 | 0 |
+-----+---+---+---+---+
.. admonition:: Tasks
#. Open the `Digital <https://github.com/hneemann/Digital>`_ tool draw the circuit. Therefore, add
one XOR gate, two inputs and one output to the workspace by choosing the correct items from the menu
(Bauteile/Logisch and Bauteile/IO) - compare :numref:`fig:Digital1`.
.. figure:: /Boolean_Basics/pics/Digital1.png
:name: fig:Digital1
:align: center
Workspace to draw circuits and menu to add items.
#. Use the mouse (left-click) to connect the XOR gate with the inputs and output - compare :numref:`fig:Digital2`.
.. figure:: /Boolean_Basics/pics/Digital2.png
:name: fig:Digital2
:align: center
Drawing connections between the XOR gate and the in-/outputs.
#. Label the inputs and outputs (right-click on the item) and insert an appropriate
name for the item - compare :numref:`fig:Digital3`.
.. figure:: /Boolean_Basics/pics/Digital3.png
:name: fig:Digital3
:align: center
Assigning labels to the in-/outputs.
#. Run your circuit (press play button)
and test if it produces the correct results by activating different combinations of the inputs
- compare :numref:`fig:Digital4`.
.. figure:: /Boolean_Basics/pics/Digital4.png
:name: fig:Digital4
:align: center
Running and testing the circuit.
#. The `Digital <https://github.com/hneemann/Digital>`_ tool also provides various options to analyse, synthesise,...
a drawn circuit - compare :numref:`fig:Digital5`.
.. figure:: /Boolean_Basics/pics/Digital5.png
:name: fig:Digital5
:align: center
Menu to analyse, synthesis,... the circuit.
#. Use the analyse option to derive the truth table for your circuit - compare :numref:`fig:Digital6`.
.. figure:: /Boolean_Basics/pics/Digital6.png
:name: fig:Digital6
:align: center
Truth table of the circuit derived by the analyse option.
#. Save and submit the circuit besides the truth table (as csv-file) using the names ``XOR.dig`` and ``XOR.csv``, respectively.
XOR
---
In this experiment, we will draw a reformulated combinational circuit using the `Digital <https://github.com/hneemann/Digital>`_ tool.
The original circuit represents the simple XOR expression of two inputs and one output
given by the XOR expression in :eq:`XOR` with the truth table stated in :numref:`tab:XOR`.
.. admonition:: Tasks
#. Use the truth table to design a logical circuit that only consists of AND, OR, and NOT gates.
#. Draw your circuit in the `Digital <https://github.com/hneemann/Digital>`_ tool.
#. Use the analyse option to derive the truth table for your circuit.
#. Use the truth tables to validate that your circuit yields the correct results.
#. Save and submit the circuit using the name ``XOR_new.dig`` besides its formula (as ``XOR_new.txt``).
XOR3
----
In this experiment, we will develop a combinational circuit for the XOR3 expression
.. math::
Y = A \bigoplus B \bigoplus C
:label: XOR3
with the following truth table:
.. _tab: XOR3:
.. table:: Truth-table for the XOR3 expression stated in Eq. :eq:`XOR3`.
:align: center
+-----+---+---+---+---+---+---+---+---+
| A | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
+-----+---+---+---+---+---+---+---+---+
| B | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
+-----+---+---+---+---+---+---+---+---+
| C | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
+-----+---+---+---+---+---+---+---+---+
| Y | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 |
+-----+---+---+---+---+---+---+---+---+
.. admonition:: Tasks
#. Use the truth table to design a logical circuit that only consists of AND, OR, and NOT gates.
#. Use the analyse option (F9, Analyse/Analyse) from the `Digital <https://github.com/hneemann/Digital>`_ tool to
derive the truth table for your circuit.
#. Use the truth tables to validate that your circuit yields the correct results, i.e.,
check that the original and new circuit produce the same outputs.
#. Save and submit the circuit using the name ``XOR3_new.dig`` besides its formula (as ``XOR3_new.txt``).
Half Adder Circuit
------------------
In this experiment, we will derive a logical circuit for the half adder logic shown in :numref:`fig:half_adder`.
In contrast to the depicted circuit, the new circuit will only uses AND, OR, and NOT gates.
.. figure:: /Boolean_Basics/pics/half_adder_orig.svg
:name: fig:half_adder
:align: center
Half Adder circuit using an XOR gate
.. admonition:: Tasks
#. Draw the circuit depicted in :numref:`fig:half_adder` using the `Digital <https://github.com/hneemann/Digital>`_ tool.
#. Use the analyse option to derive the truth table for the circuit.
#. Based on this truth table, design a new equivalent circuit that only uses AND, OR, and NOT gates.
#. As before, use the truth tables to validate the equivalence of both circuits.
#. Save and submit both circuits (as ``half_adder_orig.dig`` and ``half_adder_new.dig``) besides
their truth tables (in csv-format as ``half_adder_orig.csv`` and ``half_adder_new.csv``).
Full Adder Circuit
------------------
Similar to the half adder, we will derive a logical circuit for the full adder logic shown in :numref:`fig:full_adder`
that only uses AND, OR, and NOT gates.
.. figure:: /Boolean_Basics/pics/full_adder_orig.svg
:name: fig:full_adder
:align: center
Full Adder Circuit using XOR gates
.. admonition:: Tasks
#. Draw the circuit depicted in :numref:`fig:full_adder` using the `Digital <https://github.com/hneemann/Digital>`_ tool.
#. Use the analyse option to derive the truth table for the circuit.
#. Based on this truth table, design a new circuit that only uses AND, OR, and NOT gates.
#. As before, use the truth tables to validate the equivalence of both circuits.
#. Save and submit both circuits (as ``full_adder_orig.dig`` and ``full_adder_new.dig``) besides
their truth tables (in csv-format as ``full_adder_orig.csv`` and ``full_adder_new.csv``).
2-Bit Adder
-----------
In this experiment, we will develop a combinational circuit for a 2-Bit adder that has four inputs (A1, A0, B1, B0) and three outputs (Y1, Y0, C)
with the truth values stated in :numref:`tab:2BitAdder`.
.. _tab:2BitAdder:
.. table:: Truth-table for the 2-bit adder circuit to be designed.
:align: center
+------+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| A1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
+------+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| A0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
+------+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| B1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
+------+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| B0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
+------+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| Y1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
+------+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| Y0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 |
+------+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
| C | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
+------+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+---+
.. admonition:: Tasks
#. Use several copies of the full adder circuit from the previous experiment to design
the 2-bit adder circuit using the `Digital <https://github.com/hneemann/Digital>`_ tool
as indicated in the schematic
.. figure:: /Boolean_Basics/pics/2bit_adder.svg
:name: fig:2bit_adder
:align: center
2-bit adder schematic using full adder circuits.
Hint: You can select (parts of) a circuit on the workspace
(click the left mouse button, hold the mouse button, adapt selection square and then release the mouse button) and copy-paste items
using the menu (Bearbeiten/Kopieren and Bearbeiten/Einfügen) or keyboard short-cuts (CTRL-C and CTRL-V).
#. Use the analyse option to derive the truth table for your designed circuit and validate its correcntess.
#. Save and submit the circuit (as ``2bit_adder.dig``) besides
its truth table (in csv-format as ``2bit_adder.csv``).