Four bit adder

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>

J

Example use: <lang j> 1 1 1 1 add 0 1 1 1 1 0 1 1 0</lang>

Glossary

  ~: xor
  {. first
  }. rest
  {: last
  [  left
  ]  right
  0: function which always has the result 0
  ,  combine sequences

Meta glossary

  u v w   verbs such as and or or not
  x y     nouns such as 1 or 0
  u@v     function composition
  x u~ y  reverse arguments for u (y u x)
  u/ y    reduction (u is verb between each item in y)
  u"0     u applies to the smallest elements of its argument

Also:

  x (u v) y

produces the same result as

  x u v y

while

  x (u v w) y

produces the same result as

  (x u y) v (x w y)

See also: "A Formal Description of System/360” by Adin Falkoff