Arithmetic Logic Unit
Now we are ready to do the binary addition in Hardware, that is, in
logic gates. Let's start by introducing some gates and their
properties.
We use the following notation, a,b.. a single letter is the name of
input/output "wire" of a gate. and, or, not, xor are the
name of the function of a gate. Let our goal be a gate with two inputs
and two outputs to do add, called an "adder". a,b are
inputs. sum, carry are outputs. A wire can take either
value 0 or 1 (a binary value). We want the adder to have the following
properties (it is called a truth table). This table lists all
possible input values and output values of our "adder".
a
b s c
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
s is the sum of a and b.
c is the carry bit.
We break down the job into two gates: one for s and one for c.
Let call the s, "sum" gate and c, "carry" gate. How do we achieve
the property of "sum"?
Let we define some elementary gates: and, or, not. An "and", "or" gate
has two inputs and one output. The "and" gate has the following
property:
z
= x and y
x y z
0 0 0
0 1 0
1 0 0
1 1 1
That is the output will be 1 only when "both" inputs are 1.
The "or" gate has the property:
z
= x or y
x y z
0 0 0
0 1 1
1 0 1
1 1 1
The "or" gate will output 1 when either input is 1. Finally a "not"
gate, it has one input and one output with this property:
z
= not x
x z
0 1
1 0
That is the output is the flip of the input.
With these elementary gates I will show you the following construction
of our "sum" gate.
s
= (a and (not b)) or ((not a) and b)
a b (a and (not
b)) ((not a) and b) s
0 0
0
0
0
0 1
0
1
1
1 0
1
0
1
1 1
0
0
0
It has exactly the property we want. Can you recognise how to do
the "carry" gate? Draw a picture of the "sum" gate and "carry"
gate to compose into an "adder" gate.
You may notice that this is only half the job. As our "adder" has
only two inputs so it cannot receive a carry bit as input. To
cascade an adder together to form a larger adder, we will need to a
full job. Here is the "full adder" property, where a, b are inputs, i
is the carry-in, s, c are outputs.
i
a b s c
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1
You can see that the first half of the table where the carry-in is 0
has the same property as our "adder". The second half is
different. A bonus point will be given to a clever lad (or laddy)
who can construct a "full adder" (Hint: make it from half adder
and a bit of something).
End