Units (units.py)
This page explains the inner logic gate setup of the Arithmetic and Logic Unit. To understand information on this page requires a basic understanding of truth tables and logic gates.
Logic Gates
This is the most fundamental section in the CPU. All logic gates can be derived from the NAND gate.
NAND GATE
A |
B |
OUT |
|---|---|---|
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
The simplest way in which this is implemented in Python is:
Is the use of the & binary operator:
INVERTED GATE
This gate can be created by taking NAND where a is both a and b.
A |
OUT |
|---|---|
0 |
1 |
1 |
0 |
AND GATE
The AND gate is an inverted NAND.
A |
B |
OUT |
|---|---|---|
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
OR GATE
The OR gate is created by inverting both inputs then passing the inverted inputs into a NAND gate.
A |
B |
OUT |
|---|---|---|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
EXCLUSIVE OR GATE (XOR)
The XOR gate discriminates based on the input side. To create one, inputs are fed into a NAND gate. The output of this gate is discriminated against the NAND of either A or B where the final bit is then inverted in and AND.
A |
B |
OUT |
|---|---|---|
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
16-Bit Variants
Implementing a 16-bit versions of the logic gates is as simple as taking two 16-bit binary numbers and comparing each index of each value with a respective logic gate. Look in units.py at line 40 to see the implementation.
A 16 in the signature means that method uses 16-bit numbers.
Half-Adder
The Half-Adder is a logical unit that adds two bits together. This will allow us to get a maximum value of 3:
A Half-Adder will produce a high and low bit. Where high is 1 if both values
are 1 (1 + 1 = 2 which is 0b10 in binary). Which can be constructed by process
of elimination of bits.
HALF-ADDER TRUTH TABLE
A |
B |
HIGH |
LOW |
|---|---|---|---|
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
Full-Adder
A Full-Adder are two Half-Adders linked together where the value is allowed to overflow. This overflow is called a carry indicating that the number it too large to fit in the current buffer.
The Full-Adder takes in three bits; A, B, Carry. And will produce a high and low bit.
FULL-ADDER TRUTH TABLE
A |
B |
CARRY |
HIGH |
LOW |
|---|---|---|---|---|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
Multi-Bit-Adder
The Multi-Bit-Adder are two or more Full-Adders linked where the carry bit of the previous Full-Adder is piped into the current Full-Adder; unless it’s the last adder, in-that-case the bit is dropped.
MULTI-BIT-ADDER TRUTH TABLE
These are all the possible inputs for two 2-bit numbers and a 1-bit number.
A1 |
A2 |
B1 |
B2 |
CARRY |
|---|---|---|---|---|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
DATA BREAKDOWN
The maximum value of a 3-bit number is 7;
The binary number is being broken-down into individual bits sorted right to left starting at O2. The decimal header is there to help understand the numbering.
O1 is the expected output for the low bits
O2 is the expected output for the high bits
CARRY is the expected carry output.
SUM OF ALL 3 in binary |
DECIMAL |
CARRY |
O1 |
O2 |
|---|---|---|---|---|
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
10 |
2 |
0 |
1 |
0 |
11 |
3 |
0 |
1 |
1 |
100 |
4 |
1 |
0 |
0 |
101 |
5 |
1 |
0 |
1 |
110 |
6 |
1 |
1 |
0 |
111 |
7 |
1 |
1 |
1 |
This table then corresponds with the following output below
First we add the low bits. If there are any carry bits add these to the high bits. If there is an overflow change the bit to 1.
Output all low bits because the values will not change if more numbers are added.
Low bit sum = A2+B2+CARRY |
High bit sum = A1+B1+(Low bit sum) |
||
|---|---|---|---|
HIGH |
LOW - O2 |
HIGH - CARRY OUT |
LOW - O1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
16-Bit-Adder
The 16-Bit-Adder functions in the same way the Multi-Bit-Adder works; where the high bit is carried over from the previous Full-Adder. Chaining 16 Full-Adders together gives you a 16-Bit-Adder. The last high value is dicarded.
To use the BitAdder16 class call it’s method add.
It takes in two 16-bit binary number arguments.
The return value is the added result 16-bit tuple result.
bitadder_16.add(0b11, 0b101)
Output: (0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1)
Attention
The output of the basic 16-bit units will return tuple values as it keeps the virtual pins separate. A utility function is implemented to convert tuples to binary values. Tuple to Binary
16-Bit-Incrementer
A 16-bit increment can be built be connecting a 16-Bit-Adder to a constant signal; 1. Then we need to take in a 16-bit binary number (optionally) to tell the incrementer where to start.
To use the Increment16 class call it’s method inc.
It takes in an optional argument of a 16-bit binary number.
The return value is the incremented tuple value.
Hint
A full 16-bit number is not required. The inc method implements the BitAdder16
class which implements 16 Full-Adders. If you recall, there is a utility function in
this method to generate 16 bits where the bits are n < 17.
increment_16.inc()
Output: (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1)
increment_16.inc(0b101)
Output: (0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0)
16-Bit-Subtracter
The 16-Bit-Subtracter subtracts two 16-bit numbers. It supports negative numbers. If a binary number starts with a ‘1’ that signals that this binary number is negative. This is known as “Two’s Complement” (Learn more about Two’s Complement)
In order to implement this method we need follows:
From the equation above we need an inverted number added to a normal binary number.
SUBTRACTION TRUTH TABLE
A |
B |
NOT B |
A + NOT B + 1 |
|---|---|---|---|
01 |
01 |
10 |
00 |
01 |
00 |
11 |
01 |
10 |
11 |
00 |
11 |
11 |
10 |
01 |
01 |
The high bit (most significant bit) indicates if the number is negative.
To use the Subtract16 class call it’s method sub.
It takes in the 16-bit binary number arguments.
The return value is the subtracted result 16-bit tuple result.
subtract_16.sub(0b10, 0b1)
Output: (0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1)
subtract_16.inc(0b11, 0b100)
Output: (1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1)
Switches
A switch is required to choose between different inputs and outputs.
The select method in the Switch class controls which input to choose.
This is done by inverting the first stream then discriminating against each
input. Although callable, the single bit select should not be used directly; opt
in to using the 16 bit variant.
The 16-bit variant of select is called select_16 and requires to 16-bit
binary values and a 1-bit stream value.
The arguments required are two 16-bit binary numbers and a one 1-bit stream bit.
The return value of the 16-bit variant is a 16-bit binary number.
Attention
Due the implementation of the Generate X Bits utility function, the stream
bit needs to be 16-bits long therefore the stream bit it used to generate
16 stream bits using the generateStreamBits function.
Logic Unit
A Logic Unit determines various truths or outputs of supplied values.
OP1 |
OP2 |
OUTPUT |
|---|---|---|
0 |
0 |
X and Y |
0 |
1 |
X or Y |
1 |
0 |
X xor Y |
1 |
1 |
invert X |
To use the LogicUnit class call it’s method calc.
It takes in two 16-bit binary number arguments and two operation codes.
The return result is a 16-bit binary number.
logic_unit.calc(0, 0, 0b1, 0b1)
Output: 1
logic_unit.calc(0, 1, 0b11, 0b100)
Output: 7
logic_unit.calc(1, 1, 0b100, 0b0)
Output: 65531
Hint
The output values are numbers. The representation does not matter. Python will display them as base-10 decimal. The only thing that matters with the output is that it is of type int (meaning it is an instance of the base integer class in Python).
Arithmetic Unit
The Arithmetic Unit functions in much the same way as the Logic Unit except it’s opcodes correspond to different actions.
OP1 |
OP2 |
OUTPUT |
|---|---|---|
0 |
0 |
X + Y |
0 |
1 |
X - Y |
1 |
0 |
X - 1 |
1 |
1 |
X - 1 |
To use the ArithmeticUnit class call it’s method calc.
It takes in two 16-bit binary number arguments and two operation codes.
The return result is a 16-bit binary number.
arithmetic.calc(0, 0, 0b101, 0b100)
Output: 9
arithmetic.calc(1, 0, 0b101, 0b100)
Output: 1
ALU
The ALU stands for Arithmetic and Logic Unit. As you may have guessed, this combines the functionality of the Arithmetic Unit and the Logic Unit.
This is done by using the Switch class method select_16.
Arithmetic or Logic |
OP1 |
OP2 |
16-bits |
16-bits |
OUTPUT |
|---|---|---|---|---|---|
0 |
0 |
0 |
ANY |
ANY |
X AND Y |
0 |
0 |
1 |
ANY |
ANY |
X OR Y |
0 |
1 |
0 |
ANY |
ANY |
X XOR Y |
0 |
1 |
1 |
ANY |
ANY |
INVERT X |
1 |
0 |
0 |
ANY |
ANY |
X + Y |
1 |
0 |
1 |
ANY |
ANY |
X - Y |
1 |
1 |
0 |
ANY |
ANY |
X + 1 |
1 |
1 |
1 |
ANY |
ANY |
X - 1 |
A zero-replace and swap are added in.
Swap, switch the places of X and Y
Zero-Replace, switches the output of the first operand to 0
It takes in two 16-bit binary number arguments, four operation codes, and one 1-bit stream bit to choose between the Logic Unit and the Arithmetic Unit.
The return result is a 16-bit binary number.
# alu.calc(logic_or_arith, op1, op2, zero_replace, swap, binary_number, binary_number)
alu.calc(1, 1, 0, 0, 0, 0b11, 0b1)
Output: 2
alu.calc(0, 1, 1, 0, 0, 0b0, 0b0)
Output: 65535
Conditional Unit
The Conditional Unit checks if a 16-bit binary number is:
Less than zero
Greater than zero
Equal to zero
or any combination in-between. Whether or not the condition is true will influence the Program Counter starting value (if the value is 1 then the current address at reigster ‘a’ is used as the starting value).