Making Arithmetic function from Logical function ( Pascal, C )

When I was in 12th Grade High School, I asked myself how a computer can do arithmetic. I had already programming Pascal since I was in Grade 7th, and I don’t know much about logic gates, yet at that time. But I know that in its very basic form, computer can only do logical operation such as AND, OR, NOT, XOR, SHL and SHR, so I asked myself, how can I make a function in capable to do addition without the use of the sign “+” in the program. These are the steps I take :

First, I make a truth table for basic binary addition in order to know what is needed in the function :
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 10

Then I realize that the right hand side of the addition process above must be two bits long instead of only one bit, so I rewrite them in the form below
0 + 0 = 00
0 + 1 = 01
1 + 0 = 01
1 + 1 = 10

Later, I compare the truth table for several logic gates with the result I got above, it turn out that :
- the least significant bit, which I called R, show XOR logical relationship with the input.
R = A xor B .…(E1)

- the most significant bit, which I called C, show AND logical relationship with the input.
C = A and B ….(E2)

Since in its basic form the equation must be in the form of :
A + B = C shl 1 + R ….(E3)

By substituting E1 and E2 to equation E3 we got equation E4, below :
A + B = (A and B) shl 1 + (A xor B) ….(E4)

Then I write a Pascal recursive function capable of doing addition without using the sign “+”.

function AddLogic(const A : integer, B : integer) : integer;
var R,C : integer;
begin
R:=A xor B;
C:=(A and B) shl 1;

if (R=0) then R:=C;
else R:=AddLogic(R,C);

AddLogic:=VN;
end;

I realize later that I can do away with the recursive bit, by using repetition.

function AddLogic(const A : integer, B : integer) : integer;
var A1,B1,R,C : integer;
begin
A1:=A;
B1:=B;
repeat
R:=A1 xor B1;
C:=(A1 and B1) shl 1;
A1:=R;
B1:=C;
until (C=0) or (R=0);
if (R=0) then R:=C;
AddLogic:=VN;
end;

Which later I translate to C.

int AddLogic( int A, int B)
{ int A1,B1,R,C;
A1=A;
B1=B;
do
{ R=A1^B1;
C=(A1&B1)<<1;
A1=R;
B1=C;
} while (C&R);
if C R=C;
return R;
}

These programs didn't run as fast as if I just use the sign "+", which is a proof that something is still missing from my understanding. Later I realize that this level of detail is done in hardware layer instead of software layer. I will tell you what is missing in later posting.

Half Adder, Full Adder and Multiple Bit Adder

Just like I told before in my previous posting titled “Making Arithmetic function from Logical function ( Pascal, C )”, there is something missing from my knowledge about how arithmetic function is performed by computers using their basic logical function. The missing part as I realized later, is the fact that the things done by programming functions I wrote in my previous posting, is not done at software level, but instead embedded as a firmware inside a computer’s Arithmetic Logic Unit.

Half Adder

I will rewrite Equation E1,E2,E3, and E4 from my previous posting stated above.
R = A xor B .…(E1)
C = A and B ….(E2)
A + B = C shl 1 + R ….(E3)
A + B = (A and B) shl 1 + (A xor B) ….(E4)

One of the basic function of a computer’s Arithmetic Logic Unit is Addition, which most basic part is a Half Adder. A Half Adder is a logic gate structure derived from equation E1 and E2, the C is actually an abbreviation for Carry, which means additional bit carried by the addition function to the More Significant Bit. Here is the structure of a Half Adder.

Several Symbol for Logic IO structure of a Half Adder

Full Adder

There is almost no use for us if computer is only capable of doing one bit addition. The Arithmetic function must be extended to Multiple Bit Addition. In order to add multiple bits, the Carry bit from Less Significant Bit must also be accommodated; this is why we have to make something called a Full Adder. A Full adder unit, have three inputs A,B,CI (Carry In) and two outputs FR (Full Result) and CO(Carry Out).

The relationship in a Full Adder is extended into equation E5 and E6 below :
FR = R xor CI ….(E5)
CO = (R and CI) or C ….(E6)

Several Symbol for Logic IO structure of a Full Adder

Multiple Bit Parallel Full Adder

Once the basic is in place, it is easy to make more advanced logical structure. Multiple Bit Parallel Full Adder is simply a structure made by connecting several Full Adder. The CO from a Less Significant Bit is connected as input for the CI of a More Significant Bit.

The input are vectors of bit, A (A0,A1,A2,A3) and B (B0,B1,B2,B3), with the result of vector R(R0,R1,R2,R3,R4), note that the A0,B0 and R0 are Least Significant Bits, while A3,B3 and R4 are Most Significant Bits.

Several Symbol for Logic IO structure of a 4 bits Parallel Full Adder
(click to view detail)

I realize later that Multiple Bit Full Adder is a basic component for other arithmetic function such as subtraction, multiplication and division. I will present the detail on how subtraction is done logically in the next posting in this blog.

Representation of Negative Number and Subtraction

Representation of negative number

I was confused the first time I saw a 4 bits Parallel Full Adder, There is also some possibility that you may share the same confusion that I had. My confusion was, “What is that symbol H in a Parallel Full Adder ?”, “What is it for ?”. Later it turned out that Parallel Full Adder can also be used for subtraction, so Parallel Full Adder is somehow equivalent to a Parallel Full Subtractor.
Lets suppose that there is a positive number represented as 4 bits binary or 8 bits binary, the negative binary form of the number, is included in the table below :

Positive	4 bits	8 bits	Negative	4 bits	8 bits
0	0000	00000000	0	0000	00000000
1	0001	00000001	-1	1111	11111111
2	0010	00000010	-2	1110	11111110
3	0011	00000011	-3	1101	11111101
4	0100	00000100	-4	1100	11111100
5	0101	00000101	-5	1011	11111011
6	0110	00000110	-6	1010	11111010
7	0111	00000111	-7	1001	11111001
8	NONE	00001000	-8	1000	11111000

Table of binary representation

From the table above it can be inferred that all negative number’s binary representation have the value of 1 in its Most Significant Bits, which often called Sign Bit. So Sign Bit = 0, means that the number is positive, while Sign Bit = 1, means that the number is negative.

Parallel Full Subtractor

By doing some observation on the relationship between positive and negative number’s binary representation it is not hard, to arrive at equation E7 :
-B = not B +1 ….(E7)

Equation E8, is common arithmetic sense :
A - B = A + (-B) ….(E8)

By substituting equation E7 to equation E8, we can get equation E9 :
A – B = A + not B + 1 ….(E9)

Equation E9 is the basic thought required in order to understand how to use a Parallel Full Adder as a Parallel Full Subtractor, here is the logic in equation E10 and E11 :
{A + B = A + B + H, H = 0} ….(E10)
A – B = A + (-B) = A + not B + 1, which if H =1, is equivalent with equation E11 below
{A – B = A + not B + H, H = 1} ….(E11)

From Equation E0 and E11, it can be inferred that to make a Parallel Full Adder to become a Parallel Full Subtractor, we only need to add (not B+1) with A instead of B.

The input are vectors of bit, A (A0,A1,A2,A3) and B (B0,B1,B2,B3), with the result of vector R(R0,R1,R2,R3,R4), note that the A0,B0 and R0 are Least Significant Bits, while A3,B3 and R4 are Most Significant Bits.

Using 4bit Parallel Full Adder as 4 bit Parallel Full Subtractor.

Full Adder/Subtractor Hybrid

Full Adder/Subtraction Hybrid is a generalized use of a Parallel Full Adder as both Adder or Subtractor, depending on the Sign Bit (H). A Full Adder/Subtraction Hybrid is in fact one of the most simple Arithmetic Logic Unit in existence, with capability of Addition and Subtraction.

The logic construction of a Full Adder/Subtractor Hybrid

This is the most simple part of a Arithmetic Logic Unit

Since H is the Sign Bit, If H is true(1) the system output will be R = A - B, while if H is false(0) the system output will be R = A + B. This is done by placing XOR gates between (B0,B1,B2,B3), and the Sign Bit H, which work due to the fact that :
B xor H = B, if H=0
B xor H = not B, if H =1

More explanation on why this result in a Full Adder/Subtractor Hybrid is given in Equation E1 and E11
{A + B = A + B + H, H = 0} ….(E10)
{A – B = A + not B + H, H = 1} ….(E11)

In my later study it turn out that Full Adder is the basic part of many arithmetic logic application, including basic arithmetic like Parallel Multiplication, Parallel Division, or more advanced application (with Multiplexer and Demultiplexer included) like Float Adder, Float Subtractor, Float Multiplication and Float Division.

I will add these applications in my later posting.

Multiplexer and Demultiplexer

Multiplexer and Demultiplexer are simple device made from basic logic gates. The devices are basic parts of Read Only Memory (ROM), Random Access Memory (RAM), and Arithmetic Logic Unit(ALU).

Multiplexer is a device used to select one of several input as the output of the device (Out).
The device works by selecting the input choosen by S1,S2,S3.

Demultiplexer is a device used to select one of several output line, to which it must transfer an input (In) value.
The device works by selecting the output choosen by S1,S2,S3.

Basic Logic Gate

Logic gates are the basic parts of binary computers. Basically what logic gates do is mapping one, two or more digital signal into a digital output. There are basically 8 kinds of logic gates, they are AND, OR, NOT, NAND, NOR, XOR, NXOR, and BUF.

AND logic gate gives true (1) output, if and only if, all of its input are true (1).
OR logic gate gives true (1) output, if and only if, at least one of its input are true (1).
NOT logic gate is a single input single output logic gate, which output is the negation of its input.
NAND logic gate gives false (0) output, if and only if, all of its input are true(1).
Basically it can be thought as if a NAND logic gate is a combination of an AND and a NOT logic gate.
NOR logic gate gives false (0) output, if and only if, at least one of its input are true (1).
Basically it can be thought as if a NOR logic gate is a combination of an OR and a NOT logic gate.

XOR logic gate gives true (1) output, if and only if, the number of its true (1) input are odd.


NXOR logic gate gives true (1) output, if and only if, the number of its true (1) input are even.
BUF logic gate is a single input single output logic gate, which output is the same as its input.
Probably it doesn't make sense that there is such gate, but actually it have its own application in digital electronics as signal amplifier.