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

Python

<lang python>def xor(a, b): return (a and not b) or (b and not a)

def ha(a, b): return xor(a, b), a and b # sum, carry

def fa(a, b, ci):

   s0, c0 = ha(ci, a)
   s1, c1 = ha(s0, b)
   return s1, c0 or c1     # sum, carry

def fa4(a, b):

   width = 4
   ci = [None] * width
   co = [None] * width
   s  = [None] * width
   for i in range(width):
       s[i], co[i] = fa(a[i], b[i], co[i-1] if i else 0)
   return s, co[-1]

def int2bus(n, width=4):

   return [int(c) for c in "{0:0{1}b}".format(n, width)[::-1]]

def bus2int(b):

   return sum(1 << i for i, bit in enumerate(b) if bit)

def test_fa4():

   width = 4
   tot = [None] * (width + 1)
   for a in range(2**width):
       for b in range(2**width):
           tot[:width], tot[width] = fa4(int2bus(a), int2bus(b))
           assert a + b == bus2int(tot), "totals don't match: %i + %i != %s" % (a, b, tot)

if __name__ == '__main__':

  test_fa4()</lang>

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>

Tcl

<lang tcl>package require Tcl 8.5 namespace path tcl::mathop

1. Create our little language

proc pins args {

   # Just declaration...
   foreach p $args {upvar 1 $p v}

} proc gate {name pins body} {

   foreach p $pins {

lappend args _$p append v " \$_$p $p"

   }
   proc $name $args "upvar 1 $v;$body"

}

1. Fundamental gates

gate not {x out} {set out [expr {1&~$x}]} gate and {x y out} {set out [expr {$x&$y}]} gate or {x y out} {set out [expr {$x|$y}]}

1. Composite gates: XOR

gate xor {x y out} {

   pins nx ny x_ny nx_y

   not x          nx
   not y          ny
   and x ny       x_ny
   and nx y       nx_y
   or  x_ny nx_y  out

}

1. Composite gates: half adder

gate halfadd {a b sum carry} {

   xor a b  sum
   and a b  carry

}

1. Composite gates: full adder

gate fulladd {a b c0 sum c1} {

   pins sum_ac carry_ac carry_sb

   halfadd c0 a          sum_ac carry_ac
   halfadd sum_ac b      sum carry_sb
   or carry_ac carry_sb  c1

}

1. Composite gates: 4-bit adder

gate 4add {a0 a1 a2 a3 b0 b1 b2 b3 s0 s1 s2 s3 v} {

   pins c0 c1 c2 c3

   set c0 0; # Force to zero

   fulladd a0 b0 c0  s0 c1
   fulladd a1 b1 c1  s1 c2
   fulladd a2 b2 c2  s2 c3
   fulladd a3 b3 c3  s3 v

}</lang>

<lang tcl># Simple driver for the circuit proc 4add_driver {a b} {

   lassign [split $a {}] a3 a2 a1 a0
   lassign [split $b {}] b3 b2 b1 b0
   lassign [split 00000 {}] s3 s2 s1 s0 v

   4add a0 a1 a2 a3  b0 b1 b2 b3  s0 s1 s2 s3  v

   return "$s3$s2$s1$s0 overflow=$v"

} set a 1011 set b 0110 puts $a+$b=[4add_driver $a $b]</lang>

Produces this output:

1011+0110=0001 overflow=1