Four bit adder: Difference between revisions

Content added Content deleted

Inline

Revision as of 13:47, 15 June 2010

The aim of this task is to "simulate" a four bits adder "chip". This "chip" can be realized using four 1 bit full adders. Each of these 1 bit full adders can be realized using two half adders and an or gate. And finally a half adder can be made using a xor gate and an and gate. The xor gate can be realized using two nots, two ands and one or.

Not, or and and, the only allowed "gates" for the task, can be "imitated" by the use of the bitwise operators of your language. If there is no a bit type in your language, to be sure that the not does not "invert" all the other bits of the basic type (e.g. a byte) we are not interested in, you can use an extra and with the constant 1.

Instead of optimizing and reducing the number of used gates for the final 4-bits-adder, build it in the most straightforward way, connecting the other "constructive blocks", in turn made of "simpler" and "smaller" one.

Schematics of these "constructive blocks" are here given.

Solutions should try to be as descriptive as possible, making as easy as possible to identify "connections" between higher-order "blocks". It is not mandatory to replicate the syntax of higher-order blocks in the atomic "gate" blocks, i.e. basic "gate" operations can be performed as usual bitwise operations, or they can be "wrapped" in a block in order to expose the same syntax of higher-order blocks, at implementers' choice.

To test the implementation, show the sum of two four-bits "number" (in binary).

C

<lang c>#include <stdio.h>

typedef char pin_t;

define IN pin_t *
define OUT pin_t *
define PIN(X) pin_t _##X; pin_t *X = & _##X;
define V(X) (*(X))

define NOT(X) (~(X)&0x01)
define XOR(X,Y) ((NOT(X)&(Y)) | ((X)&NOT(Y)))

void halfadder(IN a, IN b, OUT s, OUT c) {

 V(s) = XOR(V(a), V(b));
 V(c) = V(a) & V(b);

}

void fulladder(IN a, IN b, IN ic, OUT s, OUT oc) {

 PIN(ps); PIN(pc); PIN(tc);

 halfadder(/*INPUT*/a, b, /*OUTPUT*/ps, pc);
 halfadder(/*INPUT*/ps, ic, /*OUTPUT*/s, tc);
 V(oc) = V(tc) | V(pc);

}

void fourbitsadder(IN a0, IN a1, IN a2, IN a3, IN b0, IN b1, IN b2, IN b3, OUT o0, OUT o1, OUT o2, OUT o3, OUT overflow) {

 PIN(zero); V(zero) = 0;
 PIN(tc0); PIN(tc1); PIN(tc2);

 fulladder(/*INPUT*/a0, b0, zero, /*OUTPUT*/o0, tc0);
 fulladder(/*INPUT*/a1, b1, tc0,  /*OUTPUT*/o1, tc1);
 fulladder(/*INPUT*/a2, b2, tc1,  /*OUTPUT*/o2, tc2);
 fulladder(/*INPUT*/a3, b3, tc2,  /*OUTPUT*/o3, overflow);

}

int main() {

 PIN(a0); PIN(a1); PIN(a2); PIN(a3);
 PIN(b0); PIN(b1); PIN(b2); PIN(b3);
 PIN(s0); PIN(s1); PIN(s2); PIN(s3);
 PIN(overflow);

 V(a3) = 0; V(b3) = 1;
 V(a2) = 0; V(b2) = 1;
 V(a1) = 1; V(b1) = 1;
 V(a0) = 0; V(b0) = 0;

 fourbitsadder(a0, a1, a2, a3, /* INPUT */

b0, b1, b2, b3, s0, s1, s2, s3, /* OUTPUT */ overflow);

 printf("%d%d%d%d + %d%d%d%d = %d%d%d%d, overflow = %d\n",

V(a3), V(a2), V(a1), V(a0), V(b3), V(b2), V(b1), V(b0), V(s3), V(s2), V(s1), V(s0), V(overflow));

 return 0;

}</lang>

@@ Line 1: / Line 1: @@
 {{task}}
 The aim of this task is to "''simulate''" a four bits adder "chip". This "chip" can be realized using four [[wp:Adder_(electronics)#Full_adder|1 bit full adder]]s. Each of these 1 bit full adders can be realized using two [[wp:Adder_(electronics)#Half_adder|half adder]]s and an ''or'' [[wp:Logic gate|gate]]. And finally a half adder can be made using a ''xor'' gate and an ''and'' gate. The ''xor'' gate can be realized using two ''not''s, two ''and''s and one ''or''.
@@ Line 7: / Line 8: @@
 Instead of optimizing and reducing the number of used gates for the final 4-bits-adder, build it in the most straightforward way, ''connecting'' the other "constructive blocks", in turn made of "simpler" and "smaller" one.
-Schematics of these "constructive blocks" are here given (bottom-up):
+Schematics of these "constructive blocks" are here given.
-* [[Media:xor.png|Xor gate done with ands, ors and nots]]
+[[File:xor.png|thumb|Xor gate done with ands, ors and nots]]
-* [[Media:halfadder.png|A half adder]]
+[[File:halfadder.png|thumb|A half adder]]
-* [[Media:fulladder.png|A full adder]]
+[[File:fulladder.png|thumb|A full adder]]
-* [[Media:4bitsadder.png|A 4-bits-adder]]
+[[File:4bitsadder.png|thumb|A 4-bits-adder]]
 Solutions should try to be as descriptive as possible, making as easy as possible to identify "connections" between higher-order "blocks". It is not mandatory to replicate the syntax of higher-order blocks in the atomic "gate" blocks, i.e. basic "gate" operations can be performed as usual bitwise operations, or they can be "wrapped" in a ''block'' in order to expose the same syntax of higher-order blocks, at implementers' choice.