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.
| 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;
- define IN const pin_t *
- define OUT pin_t *
- define PIN(X) pin_t _##X; pin_t *X = & _##X;
- define V(X) (*(X))
/* a NOT that does not soil the rest of the host of the single bit */
- define NOT(X) (~(X)&1)
/* a shortcut to "implement" a XOR using only NOT, AND and OR gates, as
task requirements constrain */
- 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>
Go
<lang go>package main
import "fmt"
// A wire is modeled as a channel of booleans. // You can feed it a single value without blocking. // Reading a value blocks until a value is available. type Wire chan bool func MakeWire() Wire {
return make(Wire,1)
}
// A source for zero values. func Zero() Wire {
r := MakeWire()
go func() {
for {
r <- false
}
}()
return r
}
// And gate. func And(a,b Wire) Wire {
r := MakeWire()
go func() {
for {
x := <-a
y := <-b
r <- (x && y)
}
}()
return r
}
// Or gate. func Or(a,b Wire) Wire {
r := MakeWire()
go func() {
for {
x := <-a
y := <-b
r <- (x || y)
}
}()
return r
}
// Not gate. func Not(a Wire) Wire {
r := MakeWire()
go func() {
for {
x := <-a
r <- !x
}
}()
return r
}
// Split a wire in two. func Split(a Wire) (Wire,Wire) {
r1 := MakeWire()
r2 := MakeWire()
go func() {
for {
x := <-a
r1 <- x
r2 <- x
}
}()
return r1, r2
}
// Xor gate, composed of Or, And and Not gates. func Xor(a,b Wire) Wire {
a1,a2 := Split(a) b1,b2 := Split(b) return Or(And(Not(a1),b1),And(a2,Not(b2)))
}
// A half adder, composed of two splits and an And and Xor gate. func HalfAdder(a,b Wire) (sum,carry Wire) {
a1,a2 := Split(a) b1,b2 := Split(b) carry = And(a1,b1) sum = Xor(a2,b2) return
}
// A full adder, composed of two half adders, and an Or gate. func FullAdder(a,b,carryIn Wire) (result,carryOut Wire) {
s1,c1 := HalfAdder(carryIn,a) result,c2 := HalfAdder(b,s1) carryOut = Or(c1,c2) return
}
// A four bit adder, composed of a zero source, and four full adders. func FourBitAdder(a1,a2,a3,a4 Wire, b1,b2,b3,b4 Wire) (r1,r2,r3,r4 Wire, carry Wire) {
carry = Zero() r1,carry = FullAdder(a1,b1,carry) r2,carry = FullAdder(a2,b2,carry) r3,carry = FullAdder(a3,b3,carry) r4,carry = FullAdder(a4,b4,carry) return
}
func main() {
// Create wires
a1 := MakeWire()
a2 := MakeWire()
a3 := MakeWire()
a4 := MakeWire()
b1 := MakeWire()
b2 := MakeWire()
b3 := MakeWire()
b4 := MakeWire()
// Construct circuit
r1,r2,r3,r4, carry := FourBitAdder(a1,a2,a3,a4, b1,b2,b3,b4)
// Feed it some values
a4 <- false; a3 <- false; a2 <- true; a1 <- false // 0010
b4 <- true; b3 <- true; b2 <- true; b1 <- false // 1110
B := map[bool]int { false: 0, true: 1 }
// Read the result
fmt.Printf("0010 + 1110 = %d%d%d%d (carry = %d)\n",
B[<-r4],B[<-r3],B[<-r2],B[<-r1], B[<-carry])
}</lang>
Mini reference:
- "channel <- value" sends a value to a channel. Blocks if its buffer is full.
- "<-channel" reads a value from a channel. Blocks if its buffer is empty.
- "go function()" creates and runs a go-rountine. It will continue executing concurrently.
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
This example shows how you can make little languages in Tcl that describe the problem space. <lang tcl>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
}</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
One feature of the Tcl code is that if you change the definitions of and, or, not and GND (as well as of gate and pins, of course) you could have this Tcl code generate hardware for the adder. The bulk of the code would be identical.