Digital Logic With Source [#1]

Welcome to the first part of this tutorial, which is mainly an introduction to digital logic.


As this is the first introductory part of the tutorial, I will be going over some of the basics of digital logic before implementing it into a map using the Hammer Editor.

A computer is able to process billions of bits of data and transform them into sounds, images and countless other things. We are going to work from the ground up to understand how a computer basically does this.


Binary Digits

A bit is a binary digit, able to take on the values {0, 1}, as opposed to a decimal digit which can take on the values {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. In decimal we have units such as ones, tens, hundreds etc, and we can form any number from this by placing a value 0-9 inclusive in this unit category, eg:

decimal_units_table

In the middle row we can see each unit, where starting from the right most column with 10⁰, each consecutive column is 10⁽ⁿ⁻¹⁾ where n is the column number. From this we can extract the number 9263, which is (9 * 1000) + (2 * 100) + (6 * 10) + (3 * 1). Decimal digits are in base 10, hence we use 10ⁿ. Binary digits are in base 2 , so for that we need to use 2ⁿ per unit. Furthermore, as binary digits only have values {0, 1}, each category can only contain either a 0 or a 1. Thus:

binary_units_table

From this we can extract the number 1001, which in base 10 is (1 * 8) + (0 * 4) + (0 * 2) + (1* 1), or 8 + 0 + 0 + 1 = 9. Hence, 1001 in base 2 is 9 in base 10. Now we have a way of representing all positive integers from 0 onward using just two values {0, 1} in base 2 for n amount of bits. These are known as unsigned binary numbers, where for a number that is n bits long, we can have 2ⁿ different values, and the range is 0 to ((2ⁿ)-1) inclusive. However this means we cannot represent any negative numbers. To represent negative numbers we need to introduce signed binary numbers, where the most significant bit (left most bit) determines whether the number is negative or positive. The right most bit is known as the least significant bit. With signed binary numbers we use the MSB (most significant bit) to determine whether a number is positive or negative. A 0 denotes it is positive and a 1 denotes it is negative. To obtain the base 10 value of a signed binary number such as 1001 we need to apply 2’s complement to it. To do this we:

1 – Flip the bits

2 – Add 1 to the flipped bits

By then working out the base 10 value of this modified number we can find out what negative number it represents. For example with 1001, we flip the bits giving us 0110. We then add 1 to it giving us 0111, which in base 10 is equal to (0 * 8) + (1 * 4) + (1 * 2) + (1 * 1) = 7, but this is -7 as it was a signed binary number. 9 in signed binary would now be the equivalent to 01001, 5 bits long as opposed to 4. When the MSB is 0 there is no need to apply 2’s complement to it. We only do that when the MSB is 1. If however we want to know how to represent say, -18 in binary then we construct 18 in normal unsigned form, then apply 2’s complement to obtain -18 in binary. A note on binary addition here:

    \begin{align*}0 + 1 = 1\end{align*}

    \begin{align*}1 + 1 = 0 + C1\end{align*}

C1 is carry 1. For example if you did 1 + 1 you would expect two which is 10, where the 0 is 0 because 1 + 1 = 0 and the carry is 1 (remember in binary you work stuff out right to left).

    \begin{align*}1 + 1 + C1 = 1 + C1\end{align*}

In regards to subtraction, we convert the number we want to subtract using 2’s complement (to turn it into a negative binary number). Then add the 2’s complement binary number to the other number. This will result in getting the correct binary number.


Why Binary?

Now you might be wondering why computers use base 2, and not base 10, or even other bases or symbols (such as the alphabet). This is for a number of reasons, such as binary (base 2) being easier, and we can use transistors as simple on or off switches to represent the values {0, 1}, as opposed to more complex ten state objects. Also it is easiest to represent different voltage levels (such as 0v and +5v, or 2v and 6v) as discrete numbers, 0 being the lower voltage and 1 being the higher voltage, despite voltage being continuous in nature. It makes more sense to have only two cases, where the value is 0 when it is below a certain voltage, and 1 when it is above. This means we do not have to worry about analogue precision. So a 0 and a 1 can represent false or true respectively, or off and on (like a switch, and transistors are basically like switches).


Binary Functions

Computers use base 2, but we need to be able to do operations on them, or in other words, logic functions will manipulate the binary inputs to produce a desired binary output.

Having established the language of the computer, bits, we can now look at the circuitry, which are the logic functions.

Any logical function can be represented using truth tables which indicate all the possible states it can have. Each logic gate/function also has a symbol associated with it. The foundational logic gates/functions with their respective properties are as follows:

AND function:

and_gate_symbol

The AND function takes two or more inputs. The output is only ever true (or set to 1) if all inputs are true.


OR function:

or_gate_symbol

The OR function takes two or more inputs. The output is only ever true (or set to 1) if one or more inputs are true.


NOT function:

inverter_symbol

The NOT function only ever takes one input. The output is always the inverse of the input. The NOT gate/symbol is also called an INVERTER.


From these three functions we can construct a further three functions:

NAND function:

nand_gate_symbol

The NAND function is an INVERTER attached to the output of an AND gate. You can see the inverter is denoted by adding a little circle at the end of the AND gate.


NOR function:

nor_gate_symbol

The NOR function is an INVERTER attached to the output of an OR gate. You can see the inverter is denoted by adding a little circle at the end of the OR gate.


XOR function:

xor_gate_symbol

The XOR function (exclusive-or) is a function that is only true (set to 1) when ONLY one of the inputs is true. If more than one input is true then the output is false (unlike with an OR function where one or more inputs being true sets the output to true).


As well as being able to show these functions graphically (using truth tables), we can characterise them using boolean aglebra. This is much more useful because when we start creating more complex truth tables for desired functions, we can then manipulate these equations using the laws of boolean algebra to minimise them. It is similar to simplifying your final answer to a maths question, except that in this case it means less gates which translates to less cost and less propagation delay in the circuitry.

There are 3 symbols to denote the 3 base logic functions (AND, OR, NOT). Multiplication denotes AND, addition denotes OR and a line above the variable denotes NOT. So the boolean equations are:

AND gate:

    \begin{align*}X = A.B\end{align*}

OR gate:

    \begin{align*}X = A + B\end{align*}

NOT gate:

    \begin{align*}X = \overline{A} \end{align*}

Like before, we can construct the other three functions by using multiplication, addition and a bar above any variables (or even gates) to denote their complement (NOT):

NAND gate:

    \begin{align*}X = \overline{A.B} \end{align*}

NOR gate:

    \begin{align*}X = \overline{A + B} \end{align*}

XOR gate:

    \begin{align*}X = A.\overline{B} + \overline{A}.B\end{align*}

Which is usually written as

    \begin{align*}X = A \oplus B\end{align*}

Notice how for the NOR and NAND gates their entire equation has a bar over it to denote that the output from that gate goes through an INVERTER. So to clarify:

    \begin{align*}X = \overline{A.B} \neq \overline{A}.\overline{B}\end{align*}

    \begin{align*}X = \overline{A + B} \neq \overline{A} + \overline{B}\end{align*}


Some Examples

Now that we have covered the basics, we can get started on some examples to show you how we can construct logical expressions from truth tables, and implement them into minimised circuits. The following example might not make sense (why would the sprinkler activate in those conditions?), but the point is to demonstrate being able to construct truth tables from a given problem, and from that being able to extract the logical expression, and implementing it into a circuit.

Let’s say someone wanted to implement an automated sprinkler system for their garden. The sprinkler system has the following sensors:

  1. Sensor A: Goes high when the humidity goes above 85%, low otherwise
  2. Sensor B: Goes high when the temperature goes above 25 degrees Celsius, low otherwise
  3. Sensor C: Goes high when it is a weekday, low otherwise

The owner of the sprinkler system wants the sprinkler to activate depending on a variety of combinations of the sensors going high:

Combination A

  • It is a weekday and the humidity goes above 85%, or
  • The temperature is above 25 degrees Celsius, or
  • It is NOT a weekday and the humidity goes below 85%

Combination B

  • It is a weekday and the temperature is below 25 degrees Celsius

Combination C

  • The temperature goes above 25 degrees Celsius and the humidity goes above 85%

The owner wants the sprinkler to go high if combination A and combination B are true or combination C is true.

From this, we can construct a truth table to graphically represent our logical function (please click on the image to enlarge, it opens in a new tab):

example_problem_truthtable

As you can see, with 3 inputs we have 2³ = 8 possible combinations for the sensors. From those 8 combinations, we can create the three combinations specified, where in each combination we can look at what the conditions are and look for the row in the table with those conditions and set it to 0 or 1 according to the  condition. Then lastly, from the three combination blocks we can set the truth values of X according to “[…] sprinkler to go high if combination A and combination B are true or combination C is true”. We extract Boolean equations from the output and where their truth values are one. Because X depends on combinations A, B and C, we shall extract the combinations first and then put those together in accordance with X’s truth values after. Thus the expression for the different combinations as extracted from the table are:

Combination A Expression

    \begin{align*}Combination A = \overline{A}.\overline{B}.\overline{C} + \overline{A}.B.\overline{C} + \overline{A}.B.C + A.\overline{B}.C + A.B.\overline{C} + A.B.C\end{align*}

Then simplified:

    \begin{align*}Combination A = \overline{A}.\overline{C}(\overline{B} + B) + \overline{A}.B.C + A.\overline{B}.C + A.B.\overline{C} + A.B.C\end{align*}

    \begin{align*}Combination A = \overline{A}.\overline{C}(1) + \overline{A}.B.C + A.\overline{B}.C + A.B.\overline{C} + A.B.C\end{align*}

    \begin{align*}Combination A = \overline{A}.\overline{C} + \overline{A}.B.C + A.C(\overline{B} + B) + A.B.\overline{C}\end{align*}

    \begin{align*}Combination A = \overline{A}.\overline{C} + \overline{A}.B.C + A.C(1) + A.B.\overline{C}\end{align*}

    \begin{align*}Combination A = \overline{A}.\overline{C} + \overline{A}.B.C + A.C + A.B.\overline{C}\end{align*}

    \begin{align*}Combination A = \overline{A}(\overline{C} + B.C) + A(C + B.\overline{C})\end{align*}

Now how would we calculate the following:

    \begin{align*}\overline{A}(\overline{C} + B.C) = ???\end{align*}

Well we know that:

    \begin{align*}\overline{C} + B.\overline{C} = \overline{C}\end{align*}

So:

    \begin{align*}\overline{C} = \overline{C} + B.\overline{C}\end{align*}

Which we can substitute in for not C to get:

    \begin{align*}\overline{A}(\overline{C} + B.\overline{C} + B.C)\end{align*}

    \begin{align*}= \overline{A}(\overline{C} + B(\overline{C} + C))\end{align*}

    \begin{align*}= \overline{A}(\overline{C} + B(1))\end{align*}

    \begin{align*}= \overline{A}(\overline{C} + B)\end{align*}

Similarly:

    \begin{align*}A(C + B.\overline{C}) = A(C + B)\end{align*}

So now we have:

    \begin{align*}Combination A = \overline{A}(\overline{C} + B) + A(C + B)\end{align*}

    \begin{align*}Combination A = \overline{A}.\overline{C} + \overline{A}.B + A.C + A.B\end{align*}

    \begin{align*}Combination A = \overline{A}.\overline{C} + A.C + B(\overline{A} + A)\end{align*}

    \begin{align*}Combination A = \overline{A}.\overline{C} + A.C + B(1)\end{align*}

    \begin{align*}Combination A = \overline{A}.\overline{C} + A.C + B\end{align*}


Combination B Expression

    \begin{align*}Combination B = \overline{A}.\overline{B}.C + A.\overline{B}.C\end{align*}

Then simplified:

    \begin{align*}Combination B = \overline{A}.\overline{B}.C + A.\overline{B}.C\end{align*}

    \begin{align*}Combination B = \overline{B}.C(\overline{A} + A)\end{align*}

    \begin{align*}Combination B = \overline{B}.C(1)\end{align*}

    \begin{align*}Combination B = \overline{B}.C\end{align*}


Combination C Expression

    \begin{align*}Combination C = A.B.\overline{C} + A.B.C\end{align*}

Then simplified:

    \begin{align*}Combination C = A.B.\overline{C} + A.B.C\end{align*}

    \begin{align*}Combination C = A.B(\overline{C} + C)\end{align*}

    \begin{align*}Combination C = A.B(1)\end{align*}

    \begin{align*}Combination C = A.B\end{align*}


So we have the following:

    \begin{align*}Combination A = \overline{A}.\overline{C} + A.C + B\end{align*}

    \begin{align*}Combination B = \overline{B}.C\end{align*}

    \begin{align*}Combination C = A.B\end{align*}

As you can see, these equations could have easily been derived by looking at the specification and setting the correct truth values, meaning you would not need to derive it from a truth table and minimise, rather you could get the expressions for each combination from the bullet points within each combination by looking at what makes the sensors A, B and C go high or low. Regardless, all that is now left is to turn it into a circuit. We know that:

    \begin{align*}X = ((Combination A).(Combination B)) + Combination C\end{align*}

    \begin{align*}X = ((\overline{A}.\overline{C} + A.C + B).(\overline{B}.C)) + A.B\end{align*}

Which means we simply place AND, OR and NOT gates corresponding to that equation, keeping in mind the order of parentheses:

example_problem_circuit

I coloured the combinations so it would be easy to distinguish them. Lastly, as you could see we had some pretty long logical expressions which I managed to minimise down so that we used less gates. To do that we apply the laws of Boolean algebra.


Laws of Boolean Algebra

    \begin{align*}A.0 = 0\end{align*}

    \begin{align*}A.1 = A\end{align*}

    \begin{align*}A+ 0 = A\end{align*}

    \begin{align*}A+ 1 = 1\end{align*}

    \begin{align*}A.\overline{A} = 0\end{align*}

    \begin{align*}A + \overline{A} = 1\end{align*}

    \begin{align*}\overline{(\overline{A})} = A\end{align*}

    \begin{align*}A.A = A\end{align*}

    \begin{align*}A + A = A\end{align*}

    \begin{align*}A.B = B.A\end{align*}

    \begin{align*}A + B = B + A\end{align*}

    \begin{align*}A.(A + B) = A\end{align*}

    \begin{align*}A + A.B = A\end{align*}

    \begin{align*}A + \overline{A}.B = A + B\end{align*}

    \begin{align*}A.(B + C) = A.B + A.C\end{align*}

    \begin{align*}A + (B.C) = (A + B).(A + C)\end{align*}

    \begin{align*}A + B + C = (A + B) + C = A + (B + C)\end{align*}

    \begin{align*}A.B.C = (A.B).C = A.(B.C)\end{align*}

    \begin{align*} \overline{A + B + C} = \overline{A}.\overline{B}.\overline{C}\end{align*}

    \begin{align*} \overline{A.B.C} = \overline{A} + \overline{B} + \overline{C}\end{align*}


That will be all for the introductory part. As you can see, we can create truth tables, logical expressions and circuits for given problems. 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.