Digital Logic With Source [#2]

In this second tutorial we are going to look at building some useful logic functions (such as a function that will add two binary numbers for us and output the result). We are also going to look at logic implementation in the Hammer Editor.


Hammer Implementation

Hammer provides us with two entities with which we can form the base logic functions as described in the introductory tutorial:

  • logic_branch
  • logic_branch_listener

A logic_branch will act as an input or output. So we can set it’s initial value to 0 or 1, and in it’s Outputs window we can make it affect another logic_branch (or even another entity). However, it is made much simpler when using a logic_branch_listener. With this entity, if you have say 2,3 or even 4 inputs, you set the entity to listen to all inputs, and then affect the output accordingly. So for the AND function we would set the listener to listen to the inputs. Then in it’s Outputs we would have the following:

  • OnAllFalse | and2_gate_x | SetValueTest | 0
  • OnMixed    | and2_gate_x | SetValueTest | 0
  • OnAllTrue  | and2_gate_x | SetValueTest | 1

For the OR gate:

  • OnAllFalse | or2_gate_x | SetValueTest | 0
  • OnMixed    | or2_gate_x | SetValueTest | 1
  • OnAllTrue  | or2_gate_x | SetValueTest | 1

For the inverter we simply have two logic branches, where the output is the complement of the input.

For the XOR:

  • OnAllFalse | xor2_gate_x | SetValueTest | 0
  • OnMixed    | xor2_gate_x | SetValueTest | 1
  • OnAllTrue  | xor2_gate_x | SetValueTest | 0

For the logic_branch_listeners, “gatenamehere”_gate_x is the output of our functions. We end up having something like this for the AND gate in the Hammer Editor:

example_and_gate_inhammer

I also added sprites to visually be able to tell when a bit is high or low. I will be using the following textures in my Hammer logic implementation (feel free to use them):

and2_gate or2_gateinverter

I did not bother to make a NAND or NOR gate texture. To do that I will simply stick an inverter behind the AND or OR gate in the Hammer Editor. Similarly, I will abstract the XOR gate from the two inverters, two AND gates and one OR gate into the one XOR gate so it is easier to distinguish in our circuits. It’s texture will be:

xor2_gateAfter a quick compile we can see that they all work (open the spoilers to see a GIF of the gate in action):

(Hammer) AND gate

and_gate

(Hammer) OR gate

or_gate

(Hammer) NOT gate (INVERTER)

inverter

(Hammer) NAND gate
nand_gate

(Hammer) NOR gate
nor_gate

(Hammer) XOR gate

xor_gate


The Adder Function

Now that we have the Hammer implementation in place, we are ready to start working on some real useful logic functions.

We know how to add two numbers together. But how should we go about implementing it into a logic function? Well, we should start off by implementing a truth table. Remember how binary addition works:

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

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

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

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

Here C1 denotes carry 1.  Thus the corresponding truth table will be:

half_adder_truthtable

With inputs A and B and outputs S and C (sum and carry). Our corresponding logical expressions for the outputs would be:

Sum:

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

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

Carry:

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

Which as a circuit would look like this:

half_adder_circuit

However there is a problem. With this half adder there is no way for us to add together an n bit wide binary number. Suppose we wanted to add together two 4 bit numbers 0100 and 0011. As described in the previous tutorial any carry has to be carried across to the next bit in order to calculate what it’s value will be. In effect it ripples across. Similarly if we placed 4 of these half adders next to each other, we have no way of providing the carry from one half adder to be an input for the next half adder. Therefore we need a third input, a carry in. Again with truth tables we can represent this:

full_adder_truthtable

Extracting the Boolean logical expressions gives us:

Sum Expression

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

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

    \begin{align*}S = \overline{A}(B \oplus Cin) + A(\overline{B}.\overline{Cin} + B.Cin)\end{align*}

To minimise:

    \begin{align*}\overline{B}.\overline{Cin} + B.Cin\end{align*}

We can use DeMorgan’s theorem:

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

    \begin{align*}= (\overline{\overline{B}.\overline{Cin}}).(\overline{B.Cin})\end{align*}

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

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

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

    \begin{align*}= B \oplus Cin\end{align*}

However we can’t just apply DeMorgan’s to one side of the equation and not the other, hence:

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

So now we have:

    \begin{align*}S = \overline{A}.(B \oplus Cin) + A.(\overline{B \oplus Cin})\end{align*}

And if we substitute in a variable to denote the formula:

    \begin{align*}Y = B \oplus Cin\end{align*}

We now have:

    \begin{align*}S = \overline{A}.(Y) + A.(\overline{Y})\end{align*}

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

    \begin{align*}S = A \oplus Y\end{align*}

Then we can sub the semantic equivalent formula held by Y back in:

    \begin{align*}S = A \oplus (B \oplus Cin) = (A \oplus B) \oplus Cin\end{align*}

Carry Expression

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

Which we can then minimise:

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

    \begin{align*}Cout = Cin.(A \oplus B) + A.B(1)\end{align*}

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

Here we can see that Cin ANDed with A XOR B is part of the Cout expression. We can look at the expression for S and see that the XOR function is both associative and commutative so we can turn:

    \begin{align*}S = A \oplus (B \oplus Cin) = (A \oplus B) \oplus Cin\end{align*}

into:

    \begin{align*}S = (A \oplus B) \oplus Cin\end{align*}

Which we did do, this just explains why we did it. This makes it easier to distinguish and we can see that for both outputs we have the A XOR B contributing to its outcome. We can then construct a circuit for this addition function:

full_adder_circuit


We now have a 1 bit full adder constructed from two half adders. This means we can add together two 1 bit wide binary numbers (alongside a carry in) and get the correct sum and carry out. This is the desired behaviour as it means we can place the carry out to be the carry in of the next 1 bit calculation, as you do when calculating with n bit wide binary numbers on paper. Hence, to make an 8 bit full adder we just place them next to each other and feed the carry out of the previous 1 bit full adder to be the carry in input of the next 1 bit full adder. The circuit would be as follows for an 8 bit full adder (Click to maximise):

full_adder_circuit_8bit

 

Given that we have the logical function for a 1 bit full adder sorted out now, we can implement that into Hammer:

(Hammer) Full Adder

full_adder

We can then place 8 bit full adders together in Hammer to get an 8 bit full adder. Click on the following image to enlarge:

logic_map0006

It is probably really hard to make out, but with the Hammer implemented 8 bit full adder we are getting correct results. Above you can see the result 56 from adding A = 2 + 4 + 16 = 22, and B = 1 + 32 = 33, and Cin = 1. Hence, we get A + B + Cin giving us 56, which is correctly displayed as the sum at the top of the 8 bit adder.


What if we wanted to subtract two binary numbers? Again, as we previously covered in the introductory tutorial, binary subtraction is much the same, except that we simply add 2’s complemented numbers. We could make a separate subber logic function, but as we have found out, subtraction in binary still makes use of the addition operator. This means we can use our adder logic block, except with a few alterations to allow it to choose between addition and subtraction. We know the following:

    \begin{align*}A - B\end{align*}

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

This means operand B must simply be inversed, and the addition operation continues as normal. We remember that in binary in order to make a binary number hold a negative value, we convert it into a 2’s complement format. That is, we flip the bits and add 1. So we need some logic to flip the bits and add 1 to operand B. This can be done very easily. We add one extra input, the control bit, which dictates whether we are performing addition (0) or subtraction (1). The value set by this control bit can also be used and XORed against the operand B to be the new input of B into our 8 bit adder. Remember we are using 2’s complement so the MSB now determines whether a number is negative or not. Lets say we have 00000001 (which is +1) and we want to to subtract +2 from that to give us -1. That is, 1 – 2 = -1. 2 in binary is 00000010. To convert that into -2, we flip the bits, 11111101, and add 1 to give us 11111110. Now we simply add the two together to give us 11111111. However this is in 2s complement format, meaning if we want to know what the value of this negative number is, we need to apply it again. Flipping the bits and adding 1 gives us 00000001, however we know this is -1 as it is held in 2’s complement format in the form 11111111. In our 8 bit adder (soon to be subtractor & adder), we can place an XOR gate before the B input of our full adders. Each of the XOR gate’s inputs will be the control bit as well as (just as we had previously) the bit of the B (or second) operand. This means if the control input is set high (meaning subtraction is what we want to perform), well we know the characterisitcs of an XOR gate. If the bit is 1, and the control bit is 1, then the bit is flipped just like we want it to, because 1 XOR 1 = 0. However we still need to add 1 to the total B operand value, and we can simply do this by having the control input be the carry in of the first (LSB) bit.

Furthermore, as we are using 2’s complement we are able to determine a change of sign by looking at the MSB. This is helpful in detecting overflow. As our system works in 2’s complement, the MSB determines the sign of the current result. Our range of numbers in 8 bit 2’s complement is -128 to +127. Anything outside of this range can not be reached. Say we add two large positive numbers, like 115 + 44, this is above +127, this can be checked by XORing the carry in from bit 7 and the carry out from bit 7. If there is a change of sign between these two (checked with an XOR) we can detect whether an overflow has occurred or not. Overflow only occurs with signed numbers. So we just need an XOR gate with inputs carry in for bit 7 and carry out for bit 7 to set our overflow bit:

logic_map0008

As you can see in the above image we are trying to calculate -64 – 127. This gives us -191, but in our 8 bit system we cannot represent the number -191, it is too large. Thus, the overflow bit is set high. However if you look at the answer given, 01000001 (65) and take into account the Cout bit (giving us a 9 bit output), it represents -191 in binary. So even though we have an 8 bit system, we could make some sort of binary correction system that would still yield the correct result. However for now we will not, and we will only make use of 8 bit values in our system. The above system can now subtract and add two numbers together provided their result lies in the range -128 to 127, else the overflow flag is set high.

That is all for this tutorial. In the next tutorial we will be looking at other useful combinatorial logic functions.

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.