Four bit adder

Four bit adder
You are encouraged to solve this task according to the task description, using any language you may know.

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

Not, or and and, the only allowed "gates" for the task, can be "imitated" by using the bitwise operators of your language. If there is not 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 nand (and then not) with the constant 1 on one input.

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

Schematics of these "constructive blocks" are given here.

Xor gate done with ands, ors and nots

A half adder

A full adder

A 4-bit adder

Solutions should try to be as descriptive as possible, making it 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-bit numbers (in binary).

C

<lang c>#include <stdio.h>

typedef char pin_t;

1. define IN const pin_t *
2. define OUT pin_t *
3. define PIN(X) pin_t _##X; pin_t *X = & _##X;
4. define V(X) (*(X))

/* a NOT that does not soil the rest of the host of the single bit */

1. define NOT(X) (~(X)&1)

/* a shortcut to "implement" a XOR using only NOT, AND and OR gates, as

  task requirements constrain */

1. 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

<lang j>and=: *. or=: +. not=: -. xor=: (and not) or (and not)~ hadd=: and ,"0 xor add=: ((({.,0:)@[ or {:@[ hadd {.@]), }.@])/@hadd</lang>

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 (result is left argument)
  ]  right (result is right argument)
  0: verb which always has the result 0
  ,  combine sequences

Grammar

  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)

and

  x (u1 u2 u3 u4 u5) y

produces the the same result as

  x (u1 u2 (u3 u4 u5)) y

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

Sather

<lang sather>-- a "pin" can be connected only to one component -- that "sets" it to 0 or 1, while it can be "read" -- ad libitum. (Tristate logic is not taken into account) -- This class does the proper checking, assuring the "circuit" -- and the connections are described correctly. class PIN is

 private attr v:INT;
 readonly attr name:STR;
 private attr connected:BOOL;

 create(n:STR):SAME is -- n = conventional name for this "pin"
   res ::= new;
   res.name := n;
   res.connected := false;
   return res;
 end;
 
 val:INT is
   if self.connected.not then
      #ERR + "pin " + self.name + " is undefined\n";
      return 0; -- could return a random bit to "simulate" undefined
                -- behaviour
   else
      return self.v;
   end;
 end;

 -- connect ...
 val(v:INT) is
   if self.connected then
      #ERR + "pin " + self.name + " is already 'assigned'\n";
   else
      self.connected := true;
      self.v := v.band(1);
   end;
 end;

 -- connect to existing pin
 val(v:PIN) is
    self.val(v.val);
 end;

end;

-- XOR "block" class XOR is

 readonly attr xor :PIN;

 create(a, b:PIN):SAME is
   res ::= new;
   res.xor := #PIN("xor output");
   l   ::= a.val.bnot.band(1).band(b.val);
   r   ::= a.val.band(b.val.bnot.band(1));
   res.xor.val := r.bor(l);
   return res;
 end;

end;

-- HALF ADDER "block" class HALFADDER is

 readonly attr s, c:PIN;

 create(a, b:PIN):SAME is
   res ::= new;
   res.s := #PIN("halfadder sum output");
   res.c := #PIN("halfadder carry output");
   res.s.val := #XOR(a, b).xor.val;
   res.c.val := a.val.band(b.val);
   return res;
 end;

end;

-- FULL ADDER "block" class FULLADDER is

 readonly attr s, c:PIN;

 create(a, b, ic:PIN):SAME is
   res ::= new;
   res.s := #PIN("fulladder sum output");
   res.c := #PIN("fulladder carry output");
   halfadder1 ::= #HALFADDER(a, b);
   halfadder2 ::= #HALFADDER(halfadder1.s, ic);
   res.s.val := halfadder2.s;
   res.c.val := halfadder2.c.val.bor(halfadder1.c.val);
   return res;
 end;

end;

-- FOUR BITS ADDER "block" class FOURBITSADDER is

 readonly attr s0, s1, s2, s3, v :PIN;
 
 create(a0, a1, a2, a3, b0, b1, b2, b3:PIN):SAME is
   res ::= new;
   res.s0  := #PIN("4-bits-adder sum outbut line 0");
   res.s1  := #PIN("4-bits-adder sum outbut line 1");
   res.s2  := #PIN("4-bits-adder sum outbut line 2");
   res.s3  := #PIN("4-bits-adder sum outbut line 3");
   res.v   := #PIN("4-bits-adder overflow output");
   zero ::= #PIN("zero/mass pin");
   zero.val := 0;
   fa0 ::= #FULLADDER(a0, b0, zero);
   fa1 ::= #FULLADDER(a1, b1, fa0.c);
   fa2 ::= #FULLADDER(a2, b2, fa1.c);
   fa3 ::= #FULLADDER(a3, b3, fa2.c);
   res.v.val  := fa3.c;
   res.s0.val := fa0.s;
   res.s1.val := fa1.s;
   res.s2.val := fa2.s;
   res.s3.val := fa3.s;
   return res;
 end;

end;

-- testing --

class MAIN is

 main is
   a0 ::= #PIN("a0 in"); b0 ::= #PIN("b0 in");
   a1 ::= #PIN("a1 in"); b1 ::= #PIN("b1 in");
   a2 ::= #PIN("a2 in"); b2 ::= #PIN("b2 in");
   a3 ::= #PIN("a3 in"); b3 ::= #PIN("b3 in");
   ov ::= #PIN("overflow");

   a0.val := 1; b0.val := 1;
   a1.val := 1; b1.val := 1;
   a2.val := 0; b2.val := 0;
   a3.val := 0; b3.val := 1;

   fba ::= #FOURBITSADDER(a0,a1,a2,a3,b0,b1,b2,b3);
   #OUT + #FMT("%d%d%d%d", a3.val, a2.val, a1.val, a0.val) +
   	   " + " + 
          #FMT("%d%d%d%d", b3.val, b2.val, b1.val, b0.val) +
          " = " +
          #FMT("%d%d%d%d", fba.s3.val, fba.s2.val, fba.s1.val, fba.s0.val) + 
          ", overflow = " + fba.v.val + "\n";
 end;

end;</lang>