Task

"Simulate" a four-bit adder.

This design can be realized using four 1-bit full adders.
Each of these 1-bit full adders can be built with two half adders and an   or   gate. ;

Finally a half adder can be made using an   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 the "constructive blocks"


(Xor gate 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).




package require Tcl 8.5
 
# 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"
}
 
# Fundamental gates; these are the only ones that use Tcl math ops
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}]
}
gate GND pin {
    set pin 0
}
 
# 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
}
 
# Composite gates: half adder
gate halfadd {a b sum carry} {
    xor a b  sum
    and a b  carry
}
 
# 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
}
 
# 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
 
    GND c0
    fulladd a0 b0 c0  s0 c1
    fulladd a1 b1 c1  s1 c2
    fulladd a2 b2 c2  s2 c3
    fulladd a3 b3 c3  s3 v
}