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).
Ada
<lang Ada> type Four_Bits is array (1..4) of Boolean;
procedure Half_Adder (Input_1, Input_2 : Boolean; Output, Carry : out Boolean) is begin
Output := Input_1 xor Input_2; Carry := Input_1 and Input_2;
end Half_Adder;
procedure Full_Adder (Input_1, Input_2 : Boolean; Output : out Boolean; Carry : in out Boolean) is
T_1, T_2, T_3 : Boolean;
begin
Half_Adder (Input_1, Input_2, T_1, T_2); Half_Adder (Carry, T_1, Output, T_3); Carry := T_2 or T_3;
end Full_Adder;
procedure Four_Bits_Adder (A, B : Four_Bits; C : out Four_Bits; Carry : in out Boolean) is begin
Full_Adder (A (4), B (4), C (4), Carry); Full_Adder (A (3), B (3), C (3), Carry); Full_Adder (A (2), B (2), C (2), Carry); Full_Adder (A (1), B (1), C (1), Carry);
end Four_Bits_Adder; </lang> A test program with the above definitions <lang Ada> with Ada.Text_IO; use Ada.Text_IO;
procedure Test_4_Bit_Adder is
-- The definitions from above
function Image (Bit : Boolean) return Character is
begin
if Bit then
return '1';
else
return '0';
end if;
end Image;
function Image (X : Four_Bits) return String is
begin
return Image (X (1)) & Image (X (2)) & Image (X (3)) & Image (X (4));
end Image;
A, B, C : Four_Bits; Carry : Boolean;
begin
for I_1 in Boolean'Range loop
for I_2 in Boolean'Range loop
for I_3 in Boolean'Range loop
for I_4 in Boolean'Range loop
for J_1 in Boolean'Range loop
for J_2 in Boolean'Range loop
for J_3 in Boolean'Range loop
for J_4 in Boolean'Range loop
A := (I_1, I_2, I_3, I_4);
B := (J_1, J_2, J_3, J_4);
Carry := False;
Four_Bits_Adder (A, B, C, Carry);
Put_Line
( Image (A)
& " + "
& Image (B)
& " = "
& Image (C)
& " "
& Image (Carry)
);
end loop;
end loop;
end loop;
end loop;
end loop;
end loop;
end loop;
end loop;
end Test_4_Bit_Adder; </lang> Sample output:
0000 + 0000 = 0000 0 0000 + 0001 = 0001 0 0000 + 0010 = 0010 0 0000 + 0011 = 0011 0 0000 + 0100 = 0100 0 0000 + 0101 = 0101 0 0000 + 0110 = 0110 0 0000 + 0111 = 0111 0 0000 + 1000 = 1000 0 0000 + 1001 = 1001 0 0000 + 1010 = 1010 0 0000 + 1011 = 1011 0 0000 + 1100 = 1100 0 0000 + 1101 = 1101 0 0000 + 1110 = 1110 0 0000 + 1111 = 1111 0 0001 + 0000 = 0001 0 0001 + 0001 = 0010 0 0001 + 0010 = 0011 0 0001 + 0011 = 0100 0 0001 + 0100 = 0101 0 0001 + 0101 = 0110 0 0001 + 0110 = 0111 0 0001 + 0111 = 1000 0 0001 + 1000 = 1001 0 0001 + 1001 = 1010 0 0001 + 1010 = 1011 0 0001 + 1011 = 1100 0 0001 + 1100 = 1101 0 0001 + 1101 = 1110 0 0001 + 1110 = 1111 0 0001 + 1111 = 0000 1 0010 + 0000 = 0010 0 0010 + 0001 = 0011 0 0010 + 0010 = 0100 0 0010 + 0011 = 0101 0 0010 + 0100 = 0110 0 0010 + 0101 = 0111 0 0010 + 0110 = 1000 0 0010 + 0111 = 1001 0 0010 + 1000 = 1010 0 0010 + 1001 = 1011 0 0010 + 1010 = 1100 0 0010 + 1011 = 1101 0 0010 + 1100 = 1110 0 0010 + 1101 = 1111 0 0010 + 1110 = 0000 1 0010 + 1111 = 0001 1 0011 + 0000 = 0011 0 0011 + 0001 = 0100 0 0011 + 0010 = 0101 0 0011 + 0011 = 0110 0 0011 + 0100 = 0111 0 0011 + 0101 = 1000 0 0011 + 0110 = 1001 0 0011 + 0111 = 1010 0 0011 + 1000 = 1011 0 0011 + 1001 = 1100 0 0011 + 1010 = 1101 0 0011 + 1011 = 1110 0 0011 + 1100 = 1111 0 0011 + 1101 = 0000 1 0011 + 1110 = 0001 1 0011 + 1111 = 0010 1 0100 + 0000 = 0100 0 0100 + 0001 = 0101 0 0100 + 0010 = 0110 0 0100 + 0011 = 0111 0 0100 + 0100 = 1000 0 0100 + 0101 = 1001 0 0100 + 0110 = 1010 0 0100 + 0111 = 1011 0 0100 + 1000 = 1100 0 0100 + 1001 = 1101 0 0100 + 1010 = 1110 0 0100 + 1011 = 1111 0 0100 + 1100 = 0000 1 0100 + 1101 = 0001 1 0100 + 1110 = 0010 1 0100 + 1111 = 0011 1 0101 + 0000 = 0101 0 0101 + 0001 = 0110 0 0101 + 0010 = 0111 0 0101 + 0011 = 1000 0 0101 + 0100 = 1001 0 0101 + 0101 = 1010 0 0101 + 0110 = 1011 0 0101 + 0111 = 1100 0 0101 + 1000 = 1101 0 0101 + 1001 = 1110 0 0101 + 1010 = 1111 0 0101 + 1011 = 0000 1 0101 + 1100 = 0001 1 0101 + 1101 = 0010 1 0101 + 1110 = 0011 1 0101 + 1111 = 0100 1 0110 + 0000 = 0110 0 0110 + 0001 = 0111 0 0110 + 0010 = 1000 0 0110 + 0011 = 1001 0 0110 + 0100 = 1010 0 0110 + 0101 = 1011 0 0110 + 0110 = 1100 0 0110 + 0111 = 1101 0 0110 + 1000 = 1110 0 0110 + 1001 = 1111 0 0110 + 1010 = 0000 1 0110 + 1011 = 0001 1 0110 + 1100 = 0010 1 0110 + 1101 = 0011 1 0110 + 1110 = 0100 1 0110 + 1111 = 0101 1 0111 + 0000 = 0111 0 0111 + 0001 = 1000 0 0111 + 0010 = 1001 0 0111 + 0011 = 1010 0 0111 + 0100 = 1011 0 0111 + 0101 = 1100 0 0111 + 0110 = 1101 0 0111 + 0111 = 1110 0 0111 + 1000 = 1111 0 0111 + 1001 = 0000 1 0111 + 1010 = 0001 1 0111 + 1011 = 0010 1 0111 + 1100 = 0011 1 0111 + 1101 = 0100 1 0111 + 1110 = 0101 1 0111 + 1111 = 0110 1 1000 + 0000 = 1000 0 1000 + 0001 = 1001 0 1000 + 0010 = 1010 0 1000 + 0011 = 1011 0 1000 + 0100 = 1100 0 1000 + 0101 = 1101 0 1000 + 0110 = 1110 0 1000 + 0111 = 1111 0 1000 + 1000 = 0000 1 1000 + 1001 = 0001 1 1000 + 1010 = 0010 1 1000 + 1011 = 0011 1 1000 + 1100 = 0100 1 1000 + 1101 = 0101 1 1000 + 1110 = 0110 1 1000 + 1111 = 0111 1 1001 + 0000 = 1001 0 1001 + 0001 = 1010 0 1001 + 0010 = 1011 0 1001 + 0011 = 1100 0 1001 + 0100 = 1101 0 1001 + 0101 = 1110 0 1001 + 0110 = 1111 0 1001 + 0111 = 0000 1 1001 + 1000 = 0001 1 1001 + 1001 = 0010 1 1001 + 1010 = 0011 1 1001 + 1011 = 0100 1 1001 + 1100 = 0101 1 1001 + 1101 = 0110 1 1001 + 1110 = 0111 1 1001 + 1111 = 1000 1 1010 + 0000 = 1010 0 1010 + 0001 = 1011 0 1010 + 0010 = 1100 0 1010 + 0011 = 1101 0 1010 + 0100 = 1110 0 1010 + 0101 = 1111 0 1010 + 0110 = 0000 1 1010 + 0111 = 0001 1 1010 + 1000 = 0010 1 1010 + 1001 = 0011 1 1010 + 1010 = 0100 1 1010 + 1011 = 0101 1 1010 + 1100 = 0110 1 1010 + 1101 = 0111 1 1010 + 1110 = 1000 1 1010 + 1111 = 1001 1 1011 + 0000 = 1011 0 1011 + 0001 = 1100 0 1011 + 0010 = 1101 0 1011 + 0011 = 1110 0 1011 + 0100 = 1111 0 1011 + 0101 = 0000 1 1011 + 0110 = 0001 1 1011 + 0111 = 0010 1 1011 + 1000 = 0011 1 1011 + 1001 = 0100 1 1011 + 1010 = 0101 1 1011 + 1011 = 0110 1 1011 + 1100 = 0111 1 1011 + 1101 = 1000 1 1011 + 1110 = 1001 1 1011 + 1111 = 1010 1 1100 + 0000 = 1100 0 1100 + 0001 = 1101 0 1100 + 0010 = 1110 0 1100 + 0011 = 1111 0 1100 + 0100 = 0000 1 1100 + 0101 = 0001 1 1100 + 0110 = 0010 1 1100 + 0111 = 0011 1 1100 + 1000 = 0100 1 1100 + 1001 = 0101 1 1100 + 1010 = 0110 1 1100 + 1011 = 0111 1 1100 + 1100 = 1000 1 1100 + 1101 = 1001 1 1100 + 1110 = 1010 1 1100 + 1111 = 1011 1 1101 + 0000 = 1101 0 1101 + 0001 = 1110 0 1101 + 0010 = 1111 0 1101 + 0011 = 0000 1 1101 + 0100 = 0001 1 1101 + 0101 = 0010 1 1101 + 0110 = 0011 1 1101 + 0111 = 0100 1 1101 + 1000 = 0101 1 1101 + 1001 = 0110 1 1101 + 1010 = 0111 1 1101 + 1011 = 1000 1 1101 + 1100 = 1001 1 1101 + 1101 = 1010 1 1101 + 1110 = 1011 1 1101 + 1111 = 1100 1 1110 + 0000 = 1110 0 1110 + 0001 = 1111 0 1110 + 0010 = 0000 1 1110 + 0011 = 0001 1 1110 + 0100 = 0010 1 1110 + 0101 = 0011 1 1110 + 0110 = 0100 1 1110 + 0111 = 0101 1 1110 + 1000 = 0110 1 1110 + 1001 = 0111 1 1110 + 1010 = 1000 1 1110 + 1011 = 1001 1 1110 + 1100 = 1010 1 1110 + 1101 = 1011 1 1110 + 1110 = 1100 1 1110 + 1111 = 1101 1 1111 + 0000 = 1111 0 1111 + 0001 = 0000 1 1111 + 0010 = 0001 1 1111 + 0011 = 0010 1 1111 + 0100 = 0011 1 1111 + 0101 = 0100 1 1111 + 0110 = 0101 1 1111 + 0111 = 0110 1 1111 + 1000 = 0111 1 1111 + 1001 = 1000 1 1111 + 1010 = 1001 1 1111 + 1011 = 1010 1 1111 + 1100 = 1011 1 1111 + 1101 = 1100 1 1111 + 1110 = 1101 1 1111 + 1111 = 1110 1
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>
C++
Remarks before we start:
- '...aim of this task is to simulate a four-bit adder chip.' According to this,
the class design is laid out like this: starting with 'I/O pins' of our 'chip', we represent its 'inner circuit' by a 'logic block'. Logic blocks have a transfer function which creates signals for the output pins from the signals at the input pins (and the inner state of the block, if necessary). Logic blocks may be connected to form a more complex logic block; thereby we work our way up from the simple gates (AND, OR etc.) via more complex circuits (XOR, half adder, etc.) to the four bit adder. In order to avoid the tedious work of encoding numbers to bits and vice versa, we added conveniency blocks: a source (logic block without input pins) which sets its output pins according to a given decimal number, and a sink (logic block without output pins) which calculates a decimal number from the state of its input pins.
- '... gates ... can be imitated by using the bitwise operators...' I decided to use a boolean for a bit - firstly because
the largest 'numbers' in this example are 5 bits wide and secondly because this is should become rather a prove of concept than highly efficient code.
- As C++ provides nice operator overloading and sophisticated templates, we'll make heavy use of these features - just for fun and elegance of syntax!
A Pin just stores just its signal value; declared as follows (Pin.h)... <lang cpp>#if !defined __PIN_H__
- define __PIN_H__
namespace rosetta
{
namespace fourBitAdder
{
namespace detail
{
class Pin
{
protected:
Pin();
Pin& Signal(bool value);
bool Signal()const;
private:
bool signal;
};
} //namespace detail } //namespace fourBitAdder } //namespace rosetta
- endif //!defined __PIN_H__</lang>
... and defined like that (Pin.cpp): <lang cpp>#include "Pin.h" using rosetta::fourBitAdder::detail::Pin;
Pin::Pin()
:signal(false)
{}
Pin& Pin::Signal(bool value)
{
signal = value;
return *this;
}
bool Pin::Signal()const
{
return signal;
}</lang>
An input pin is a Pin which a value may be assigned to and can be got from; also, the input pin may be connected to a signal source which then determines the input pin's value. Obviously, in our simple world, such a signal source needs to be an output pin (PinIn.h): <lang cpp>#if !defined __PININ_H__
- define __PININ_H__
- include "Pin.h"
namespace rosetta
{
namespace fourBitAdder
{
class PinOut;
class PinIn
:public detail::Pin
{
friend void operator>>(const PinOut&, PinIn&);
public:
PinIn();
PinIn& operator=(bool signal);
operator bool()const;
void Disconnect();
private:
void Connect(const PinOut& output);
const PinOut* signalSource;
};
} //namespace fourBitAdder } //namespace rosetta
- endif //!defined __PININ_H__</lang>
The input pin's definition (PinIn.cpp): <lang cpp>#include <memory>
- include <cassert>
- include "PinIn.h"
- include "PinOut.h"
using rosetta::fourBitAdder::PinIn; using rosetta::fourBitAdder::PinOut;
PinIn::PinIn()
:detail::Pin()
,signalSource(NULL)
{}
PinIn& PinIn::operator=(bool signal)
{
assert(signalSource == NULL); //otherwise, this will not have any effect
return static_cast<PinIn&>(Signal(signal));
}
PinIn::operator bool()const
{
if(signalSource == NULL)
return Signal();
else
return *signalSource;
}
void PinIn::Disconnect()
{
signalSource = NULL;
}
void PinIn::Connect(const PinOut& output)
{
signalSource = &output;
}</lang>
An output pin is a Pin which a value may be assigned to and can be got from; also, the output pin may be get its signal from the transfer function of a (logic) block. For this to work out properly, it is necessary that an output pin knows to which block ('chip') it belongs to and what position it has there. Being the bridge between a chip's inner circuits (the logic block) and the outside world, an output pin may be connected to an input pin (PinOut.h): <lang cpp>#if !defined __PINOUT_H__
- define __PINOUT_H__
- include "Pin.h"
namespace rosetta
{
namespace fourBitAdder
{
namespace detail
{
class Block;
template<int, int> class LogicBlock;
}
class PinIn;
class PinOut
:public detail::Pin
{
friend void operator>>(const PinOut&, PinIn&);
template<int, int> friend class detail::LogicBlock;
public:
PinOut();
operator bool()const;
PinOut& operator=(bool signal);
private:
PinOut(detail::Block& container, int indexOfPinInContainer);
detail::Block*const container;
int indexOfPinInContainer;
};
void operator>>(const PinOut& output, PinIn& input);
} //namespace fourBitAdder } //namespace rosetta
- endif //!defined __PINOUT_H__</lang>
The output pin's definition (PinOut.cpp): <lang cpp>#include "cassert"
- include "BaseLogic.h"
using rosetta::fourBitAdder::detail::Block;
- include "PinOut.h"
using rosetta::fourBitAdder::PinOut;
PinOut::PinOut()
:detail::Pin()
,container(NULL)
{}
PinOut::PinOut(Block& container, int indexOfPinInContainer)
:detail::Pin()
,container(&container)
,indexOfPinInContainer(indexOfPinInContainer)
{}
PinOut::operator bool()const
{
if(container == NULL)
return Signal();
else
return container->TransferFunction(indexOfPinInContainer);
}
PinOut& PinOut::operator=(bool signal)
{
assert(container == NULL); //otherwise, this will not have any effect
return static_cast<PinOut&>(Signal(signal));
}
void rosetta::fourBitAdder::operator>>(const PinOut& output, PinIn& input)
{
input.Connect(output);
}</lang>
Now, we define a block which has no more than a pure virtual transfer function. The block serves as a base for a logic block which adds a certain number of input and output pins to the transfer function. Note how the numbers of input and output pins come in as template parameters (BaseLogic.h): <lang cpp>#if !defined __BASELOGIC_H__
- define __BASELOGIC_H__
- include<memory>
- include<stdexcept>
- include<vector>
- include "PinIn.h"
- include "PinOut.h"
namespace rosetta
{
namespace fourBitAdder
{
namespace detail
{
class Block
{
public:
virtual bool TransferFunction(unsigned indexOfOutput)=0;
};
template<int NumIn, int NumOut>
class LogicBlock
:Block
{
public:
PinIn& In(unsigned i = 0)const
{
if(i >= NumIn)
throw std::out_of_range("Index of input pin is out of range!");
return *in[i];
}
const PinOut& Out(unsigned i = 0)
{
if(i >= NumOut)
throw std::out_of_range("Index of output pin is out of range!");
return *out[i];
}
protected:
LogicBlock()
{
for(int i =0; i < NumIn; i++)
in.push_back(std::auto_ptr<PinIn>(new PinIn()));
for(int i =0; i < NumOut; i++)
out.push_back(std::auto_ptr<PinOut>(new PinOut(*this, i)));
}
enum
{
NumInputs = NumIn,
NumOutputs = NumOut
};
private:
std::vector<std::auto_ptr<PinIn> > in;
std::vector<std::auto_ptr<PinOut> > out;
};
} //namespace detail } //namespace fourBitAdder } //namespace rosetta
- endif //!defined __BASELOGIC_H__</lang>
Defining a gate as a logic block with just one output, we declare such a base class. Then, definition of the basic AND, OR and NOT gates with an arbitrary number of input pins is as easy as writing down the appropriate transfer function. <lang cpp>#if !defined __GATES_H__
- define __GATES_H__
- include"PinIn.h"
- include"BaseLogic.h"
namespace rosetta
{
namespace fourBitAdder
{
namespace detail
{
template<int NumIn>
class Gate
: public LogicBlock<NumIn, 1>
{
protected:
Gate()
:LogicBlock()
{}
};
} //namespace detail
template<int NumIn>
class AndGate
: public detail::Gate<NumIn>
{
public:
bool TransferFunction(unsigned indexOfOutput)
{
bool result = true;
for(unsigned i = 0; i < NumIn; i++)
result = result && In(i);
return result;
}
};
template <int NumIn>
class OrGate
: public detail::Gate<NumIn>
{
public:
bool TransferFunction(unsigned indexOfOutput)
{
bool result = false;
for(unsigned i = 0; i < NumIn; i++)
result = result || In(i);
return result;
}
};
class NotGate
: public detail::Gate<1>
{
public:
bool TransferFunction(unsigned indexOfOutput)
{
return !In(0);
}
};
} //namespace fourBitAdder } //namespace rosetta
- endif //!defined __GATES_H__</lang>
Now we are ready for our first circuit built from several gates: the XOR gate, following the schematic given with this task, consists of two AND, two NOT and one OR gates (XorGate.h). <lang cpp>#if !defined __XORGATE_H__
- define __XORGATE_H__
- include "Gates.h"
namespace rosetta
{
namespace fourBitAdder
{
class XorGate
: public detail::Gate<2>
{
public:
XorGate();
bool TransferFunction(unsigned indexOfOutput);
private:
AndGate<2> andA, andB;
NotGate notA, notB;
OrGate<2> or;
};
} //namespace fourBitAdder } //namespace rosetta
- endif //!defined __XORGATE_H__</lang>
The XOR gate's definition needs to set up the internal connections of the constituting gates and to write down the transfer function which infers the XOR's output signal from its input signals. <lang cpp>#include "XorGate.h" using namespace rosetta::fourBitAdder;
XorGate::XorGate()
:Gate()
{
notA.Out()>>andB.In(1);
notB.Out()>>andA.In(1);
andA.Out()>>or.In(0);
andB.Out()>>or.In(1);
}
bool XorGate::TransferFunction(unsigned indexOfOutput)
{
andA.In(0) = In(0);
notA.In(0) = In(0);
andB.In(0) = In(1);
notB.In(0) = In(1);
return or.Out();
}</lang>
A half adder has two inputs (bits A and B) and two outputs (sum and carry); it consists of an AND and a XOR gate (HalfAdder.h): <lang cpp>#if !defined __HALFADDER_H__
- define __HALFADDER_H__
- include "XorGate.h"
- include "Gates.h"
- include "BaseLogic.h"
namespace rosetta
{
namespace fourBitAdder
{
class PinOut;
class PinIn;
template<int> class AndGate;
class HalfAdder
: public detail::LogicBlock<2,2>
{
public:
bool TransferFunction(unsigned indexOfOutput);
PinIn& BitA();
PinIn& BitB();
const PinOut& Sum();
const PinOut& Carry();
private:
AndGate<2> and;
XorGate xor;
};
} //namespace fourBitAdder } //namespace rosetta
- endif //!defined __HALFADDER_H__</lang>
Internal wiring is not required for the half adder; we just write down the transfer function which is able to provide the values for either of the two outputs (HalfAdder.cpp): <lang cpp>#include <stdexcept> using std::out_of_range;
- include "HalfAdder.h"
using namespace rosetta::fourBitAdder;
bool HalfAdder::TransferFunction(unsigned indexOfOutput)
{
switch(indexOfOutput)
{
case 0: // sum
xor.In(0) = BitA();
xor.In(1) = BitB();
return xor.Out();
case 1: // carry
and.In(0) = BitA();
and.In(1) = BitB();
return and.Out();
default:
throw new out_of_range("There are only two output pins.");
}
}
PinIn& HalfAdder::BitA() {return In(0);}
PinIn& HalfAdder::BitB() {return In(1);}
const PinOut& HalfAdder::Sum() {return Out(0);}
const PinOut& HalfAdder::Carry() {return Out(1);} </lang> A full adder has three inputs (bits A and B as well as carry) and two outputs (sum and carry); it consists of an OR gate and two half adders (FullAdder.h): <lang cpp>#if !defined __FULLADDER_H__
- define __FULLADDER_H__
- include "BaseLogic.h"
- include "Gates.h"
- include "HalfAdder.h"
namespace rosetta
{
namespace fourBitAdder
{
class PinOut;
class PinIn;
class FullAdder
: public detail::LogicBlock<3,2>
{
public:
FullAdder();
bool TransferFunction(unsigned indexOfOutput);
PinIn& CarryInput();
PinIn& BitA();
PinIn& BitB();
const PinOut& Sum();
const PinOut& CarryResult();
private:
OrGate<2> or;
HalfAdder bitAHalfAdder;
HalfAdder bitBHalfAdder;
};
} //namespace fourBitAdder } //namespace rosetta
- endif //!defined __FULLADDER_H__</lang>
The full adder's definition consists of setting up the internal connections of writing down the proper transfer function (FullAdder.cpp): <lang cpp>#include <stdexcept> using std::out_of_range;
- include "FullAdder.h"
using namespace rosetta::fourBitAdder;
FullAdder::FullAdder()
{
bitAHalfAdder.Sum()>>bitBHalfAdder.BitA();
bitAHalfAdder.Carry()>>or.In(0);
bitBHalfAdder.Carry()>>or.In(1);
}
bool FullAdder::TransferFunction(unsigned indexOfOutput)
{
bitAHalfAdder.BitA() = CarryInput();
bitAHalfAdder.BitB() = BitA();
bitBHalfAdder.BitB() = BitB();
switch(indexOfOutput)
{
case 0: //sum
return bitBHalfAdder.Sum();
case 1: //carry bit
return or.Out();
default:
throw new out_of_range("There are only two output pins.");
}
}
const PinOut& FullAdder::Sum() {return Out(0);}
const PinOut& FullAdder::CarryResult() {return Out(1);}
PinIn& FullAdder::CarryInput(){return In(0);}
PinIn& FullAdder::BitA(){return In(1);}
PinIn& FullAdder::BitB(){return In(2);}</lang> Finally, we arrive at the four bit adder, a circuit boasting 8 inputs (2 four bit numbers) and five outputs (4 bit number plus carry, or just a five bit number) (FourBitAdder.h): <lang cpp>#if !defined __FOURBITADDER_H__
- define __FOURBITADDER_H__
- include "BaseLogic.h"
- include <memory>
- include <vector>
- include "FullAdder.h"
namespace rosetta
{
namespace fourBitAdder
{
class PinOut;
class PinIn;
class FourBitAdder
: public detail::LogicBlock<8,5>
{
public:
FourBitAdder();
bool TransferFunction(unsigned indexOfOutput);
PinIn& BitA(unsigned index);
PinIn& BitB(unsigned index);
const PinOut& Sum(unsigned index);
const PinOut& Carry();
private:
std::vector<std::auto_ptr<FullAdder> > fullAdder;
};
} //namespace fourBitAdder } //namespace rosetta
- endif //!defined __FOURBITADDER_H__</lang>
The four bit adder consists of four full adders; the internal connections are simple: the LSB full adder's carry input is always false, and carry outputs are connected to carry inputs of the next full adder (the MSB full adder's carry output is the four bit adders carry output). The other input and output pins of our full adders are related to the four bit adders input and output by the transfer function (FourBitAdder.cpp): <lang cpp>#include <stdexcept> using std::out_of_range;
- include <memory>
using std::auto_ptr;
- include <cassert>
- include "FourBitAdder.h"
using namespace rosetta::fourBitAdder;
FourBitAdder::FourBitAdder()
{
assert(NumInputs == 8);
for(int i =0; i < NumInputs/2; i++)
fullAdder.push_back(auto_ptr<FullAdder>(new FullAdder()));
fullAdder[0]->CarryInput() = false;
for(int i = 1; i < NumInputs/2; i++)
fullAdder[i-1]->CarryResult()>>fullAdder[i]->CarryInput();
}
bool FourBitAdder::TransferFunction(unsigned indexOfOutput)
{
int numBits = NumInputs/2;
for(int i = 0; i < numBits; i++)
{
fullAdder[i]->BitA() = In(i);
fullAdder[i]->BitB() = In(i+numBits);
}
assert(NumOutputs == 5);
switch(indexOfOutput)
{
case 0:
case 1:
case 2:
case 3:
return fullAdder[indexOfOutput]->Sum(); //bits of resulting sum
case 4:
return fullAdder[indexOfOutput - 1]->CarryResult(); //carry bit
default:
assert(false);
return false;
}
}
PinIn& FourBitAdder::BitA(unsigned index)
{
if(index < NumInputs/2)
return In(index);
else
throw new out_of_range("Input A does not have that much bits.");
}
PinIn& FourBitAdder::BitB(unsigned index)
{
if(index < NumInputs/2)
return In(index + NumInputs/2);
else
throw new out_of_range("Input A does not have that much bits.");
}
const PinOut& FourBitAdder::Sum(unsigned index)
{
if(index < (NumOutputs - 1))
return Out(index);
else
throw new out_of_range("Sum output does not have that much bits.");
}
const PinOut& FourBitAdder::Carry()
{return Out(4);}
</lang> Note how the complexity of the code for the XOR, half adder, full adder and four bit adder remained comparable and quite simple, despite the fact that the number of basic gates involved increased from 5 (XOR) to 6 (half adder) to 13 (full adder) and finally to 52 (four bit adder).
In order to avoid fiddling around with single bits, we provide two conveniency circuits. For input, there is the source, a logic block providing an arbitrary number of outputs, but no inputs. Instead, it accepts a simple decimal number as input and sets the signal at its outputs accordingly. A source may be connected to (some of) the inputs of a logic block and thus allows easy control of the latter (Source.h): <lang cpp>#if !defined __SOURCE_H__
- define __SOURCE_H__
- include <stdexcept>
- include <string>
- include <sstream>
- include <ostream>
- include "BaseLogic.h"
namespace rosetta
{
namespace fourBitAdder
{
template<int NumSources>
class Source
: protected detail::LogicBlock<0, NumSources>
{
public:
Source()
:LogicBlock()
,maxSourceStateDecimal((1<<NumSources) - 1)
,sourceStateDecimal(0)
{}
Source& operator=(unsigned sourceStateDecimal)
{
if(sourceStateDecimal > maxSourceStateDecimal)
this->sourceStateDecimal = maxSourceStateDecimal;
else
this->sourceStateDecimal = sourceStateDecimal;
return *this;
}
operator unsigned()const
{
return sourceStateDecimal;
}
const PinOut& Bit(int i = 0)
{
return detail::LogicBlock<0, NumSources>::Out(i);
}
template<typename LogicBlock>
LogicBlock& operator>>(LogicBlock& consumer)
{
for(unsigned i = 0; i < NumSources; i++)
Out(i)>>consumer.In(i);
return consumer;
}
operator std::string()
{
std::stringstream s;
for(int i = (NumSources - 1); i >= 0; i--)
s << Out(i);
return s.str();
}
protected:
bool TransferFunction(unsigned i)
{
return (sourceStateDecimal & 1<<i) == 1<<i;
}
private:
const unsigned maxSourceStateDecimal;
unsigned sourceStateDecimal;
};
template <int NumSources>
std::ostream& operator<<(std::ostream& os, Source<NumSources>& src)
{
os<<(std::string)src;
return os;
}
} //namespace fourBitAdder } //namespace rosetta
- endif //!defined __SOURCE_H__</lang>
In order to interpret output, there is the sink: a logic block providing an arbitrary number of inputs, but no outputs. Instead, from its input signals the sink calculates a decimal number. A sink may be connected to (some of) the outputs of a logic block and thus allows easy access to that state of the latter (Sink.h): <lang cpp>#if !defined __SINK_H__
- define __SINK_H__
- include <stdexcept>
- include <string>
- include <sstream>
- include <ostream>
- include <cassert>
- include "BaseLogic.h"
namespace rosetta
{
namespace fourBitAdder
{
template<int NumSinks>
class Sink
: protected detail::LogicBlock<NumSinks, 0>
{
template<typename LogicBlock, int NumSinks>
friend void operator>>(const LogicBlock&, Sink<NumSinks>&);
public:
Sink()
:LogicBlock()
{}
operator unsigned()const
{
unsigned sinkStateDecimal = 0;
for(unsigned i = 0; i < NumSinks;i++)
if(In(i))
sinkStateDecimal += 1<<i;
return sinkStateDecimal;
}
PinIn& In(int i = 0)const
{
return detail::LogicBlock<NumSinks, 0>::In(i);
}
operator std::string()const
{
std::stringstream s;
for(int i = (NumSinks - 1); i >= 0; i--)
s << In(i);
return s.str();
}
protected:
bool TransferFunction(unsigned i)
{
assert(false);
return false;
}
};
template<typename LogicBlock, int NumSinks>
void operator>>(LogicBlock& producer, Sink<NumSinks>& sink)
{
for(unsigned i = 0; i < NumSinks; i++)
producer.Out(i)>>sink.In(i);
}
template <int NumSinks>
std::ostream& operator<<(std::ostream& os, Sink<NumSinks>& src)
{
os<<(std::string)src;
return os;
}
} //namespace fourBitAdder } //namespace rosetta
- endif //!defined __SINK_H__</lang>
Now, using the four bit adder with two sources of input and one sink for the result is quite simple: We create the four necessary objects and connect them properly. With these preparations, making the four bit adder do its calculation is just a matter of setting the sources to the desired numbers and reading their sum from the sink. There's main.cpp: <lang cpp>#include <iostream> using std::cout; using std::endl;
- include "FourBitAdder.h"
- include "Source.h"
- include "Sink.h"
using namespace rosetta::fourBitAdder;
int main(int argc, char** argv)
{
//create four bit adder, 'input numbers' and 'output display'
Source<4>
fourBitAdderInputA,
fourBitAdderInputB;
FourBitAdder fba;
Sink<5> fourBitAdderResult;
//connect inputs, four bit adder and output
for(int i = 0; i < 4; i++)
{
fourBitAdderInputA.Bit(i)>>fba.BitA(i);
fourBitAdderInputB.Bit(i)>>fba.BitB(i);
}
fba>>fourBitAdderResult;
//do (and check) all possible additions of two four bit numbers and print the results
for(unsigned a = 0; a < 16; a++)
for(unsigned b = 0; b < 16; b++)
{
fourBitAdderInputA = a;
fourBitAdderInputB = b;
cout<<fourBitAdderInputA<<" + "<<fourBitAdderInputB<<" = "<<fourBitAdderResult<<endl;
assert(fourBitAdderInputA + fourBitAdderInputB == fourBitAdderResult);
}
return 0; }</lang>
Output (source code is compiled by MS Visual C++ 10.0 (WinXP 32 bit) compiler):
0000 + 0000 = 00000 0000 + 0001 = 00001 0000 + 0010 = 00010 0000 + 0011 = 00011 0000 + 0100 = 00100 0000 + 0101 = 00101 0000 + 0110 = 00110 0000 + 0111 = 00111 0000 + 1000 = 01000 0000 + 1001 = 01001 0000 + 1010 = 01010 0000 + 1011 = 01011 0000 + 1100 = 01100 0000 + 1101 = 01101 0000 + 1110 = 01110 0000 + 1111 = 01111 0001 + 0000 = 00001 0001 + 0001 = 00010 0001 + 0010 = 00011 0001 + 0011 = 00100 0001 + 0100 = 00101 0001 + 0101 = 00110 0001 + 0110 = 00111 0001 + 0111 = 01000 0001 + 1000 = 01001 0001 + 1001 = 01010 0001 + 1010 = 01011 0001 + 1011 = 01100 0001 + 1100 = 01101 0001 + 1101 = 01110 0001 + 1110 = 01111 0001 + 1111 = 10000 0010 + 0000 = 00010 0010 + 0001 = 00011 0010 + 0010 = 00100 0010 + 0011 = 00101 0010 + 0100 = 00110 0010 + 0101 = 00111 0010 + 0110 = 01000 0010 + 0111 = 01001 0010 + 1000 = 01010 0010 + 1001 = 01011 0010 + 1010 = 01100 0010 + 1011 = 01101 0010 + 1100 = 01110 0010 + 1101 = 01111 0010 + 1110 = 10000 0010 + 1111 = 10001 0011 + 0000 = 00011 0011 + 0001 = 00100 0011 + 0010 = 00101 0011 + 0011 = 00110 0011 + 0100 = 00111 0011 + 0101 = 01000 0011 + 0110 = 01001 0011 + 0111 = 01010 0011 + 1000 = 01011 0011 + 1001 = 01100 0011 + 1010 = 01101 0011 + 1011 = 01110 0011 + 1100 = 01111 0011 + 1101 = 10000 0011 + 1110 = 10001 0011 + 1111 = 10010 0100 + 0000 = 00100 0100 + 0001 = 00101 0100 + 0010 = 00110 0100 + 0011 = 00111 0100 + 0100 = 01000 0100 + 0101 = 01001 0100 + 0110 = 01010 0100 + 0111 = 01011 0100 + 1000 = 01100 0100 + 1001 = 01101 0100 + 1010 = 01110 0100 + 1011 = 01111 0100 + 1100 = 10000 0100 + 1101 = 10001 0100 + 1110 = 10010 0100 + 1111 = 10011 0101 + 0000 = 00101 0101 + 0001 = 00110 0101 + 0010 = 00111 0101 + 0011 = 01000 0101 + 0100 = 01001 0101 + 0101 = 01010 0101 + 0110 = 01011 0101 + 0111 = 01100 0101 + 1000 = 01101 0101 + 1001 = 01110 0101 + 1010 = 01111 0101 + 1011 = 10000 0101 + 1100 = 10001 0101 + 1101 = 10010 0101 + 1110 = 10011 0101 + 1111 = 10100 0110 + 0000 = 00110 0110 + 0001 = 00111 0110 + 0010 = 01000 0110 + 0011 = 01001 0110 + 0100 = 01010 0110 + 0101 = 01011 0110 + 0110 = 01100 0110 + 0111 = 01101 0110 + 1000 = 01110 0110 + 1001 = 01111 0110 + 1010 = 10000 0110 + 1011 = 10001 0110 + 1100 = 10010 0110 + 1101 = 10011 0110 + 1110 = 10100 0110 + 1111 = 10101 0111 + 0000 = 00111 0111 + 0001 = 01000 0111 + 0010 = 01001 0111 + 0011 = 01010 0111 + 0100 = 01011 0111 + 0101 = 01100 0111 + 0110 = 01101 0111 + 0111 = 01110 0111 + 1000 = 01111 0111 + 1001 = 10000 0111 + 1010 = 10001 0111 + 1011 = 10010 0111 + 1100 = 10011 0111 + 1101 = 10100 0111 + 1110 = 10101 0111 + 1111 = 10110 1000 + 0000 = 01000 1000 + 0001 = 01001 1000 + 0010 = 01010 1000 + 0011 = 01011 1000 + 0100 = 01100 1000 + 0101 = 01101 1000 + 0110 = 01110 1000 + 0111 = 01111 1000 + 1000 = 10000 1000 + 1001 = 10001 1000 + 1010 = 10010 1000 + 1011 = 10011 1000 + 1100 = 10100 1000 + 1101 = 10101 1000 + 1110 = 10110 1000 + 1111 = 10111 1001 + 0000 = 01001 1001 + 0001 = 01010 1001 + 0010 = 01011 1001 + 0011 = 01100 1001 + 0100 = 01101 1001 + 0101 = 01110 1001 + 0110 = 01111 1001 + 0111 = 10000 1001 + 1000 = 10001 1001 + 1001 = 10010 1001 + 1010 = 10011 1001 + 1011 = 10100 1001 + 1100 = 10101 1001 + 1101 = 10110 1001 + 1110 = 10111 1001 + 1111 = 11000 1010 + 0000 = 01010 1010 + 0001 = 01011 1010 + 0010 = 01100 1010 + 0011 = 01101 1010 + 0100 = 01110 1010 + 0101 = 01111 1010 + 0110 = 10000 1010 + 0111 = 10001 1010 + 1000 = 10010 1010 + 1001 = 10011 1010 + 1010 = 10100 1010 + 1011 = 10101 1010 + 1100 = 10110 1010 + 1101 = 10111 1010 + 1110 = 11000 1010 + 1111 = 11001 1011 + 0000 = 01011 1011 + 0001 = 01100 1011 + 0010 = 01101 1011 + 0011 = 01110 1011 + 0100 = 01111 1011 + 0101 = 10000 1011 + 0110 = 10001 1011 + 0111 = 10010 1011 + 1000 = 10011 1011 + 1001 = 10100 1011 + 1010 = 10101 1011 + 1011 = 10110 1011 + 1100 = 10111 1011 + 1101 = 11000 1011 + 1110 = 11001 1011 + 1111 = 11010 1100 + 0000 = 01100 1100 + 0001 = 01101 1100 + 0010 = 01110 1100 + 0011 = 01111 1100 + 0100 = 10000 1100 + 0101 = 10001 1100 + 0110 = 10010 1100 + 0111 = 10011 1100 + 1000 = 10100 1100 + 1001 = 10101 1100 + 1010 = 10110 1100 + 1011 = 10111 1100 + 1100 = 11000 1100 + 1101 = 11001 1100 + 1110 = 11010 1100 + 1111 = 11011 1101 + 0000 = 01101 1101 + 0001 = 01110 1101 + 0010 = 01111 1101 + 0011 = 10000 1101 + 0100 = 10001 1101 + 0101 = 10010 1101 + 0110 = 10011 1101 + 0111 = 10100 1101 + 1000 = 10101 1101 + 1001 = 10110 1101 + 1010 = 10111 1101 + 1011 = 11000 1101 + 1100 = 11001 1101 + 1101 = 11010 1101 + 1110 = 11011 1101 + 1111 = 11100 1110 + 0000 = 01110 1110 + 0001 = 01111 1110 + 0010 = 10000 1110 + 0011 = 10001 1110 + 0100 = 10010 1110 + 0101 = 10011 1110 + 0110 = 10100 1110 + 0111 = 10101 1110 + 1000 = 10110 1110 + 1001 = 10111 1110 + 1010 = 11000 1110 + 1011 = 11001 1110 + 1100 = 11010 1110 + 1101 = 11011 1110 + 1110 = 11100 1110 + 1111 = 11101 1111 + 0000 = 01111 1111 + 0001 = 10000 1111 + 0010 = 10001 1111 + 0011 = 10010 1111 + 0100 = 10011 1111 + 0101 = 10100 1111 + 0110 = 10101 1111 + 0111 = 10110 1111 + 1000 = 10111 1111 + 1001 = 11000 1111 + 1010 = 11001 1111 + 1011 = 11010 1111 + 1100 = 11011 1111 + 1101 = 11100 1111 + 1110 = 11101 1111 + 1111 = 11110
C#
<lang csharp> using System; using System.Collections.Generic; using System.Linq; using System.Text;
namespace RosettaCodeTasks.FourBitAdder { public struct BitAdderOutput { public bool S { get; set; } public bool C { get; set; } public override string ToString ( ) { return "S" + ( S ? "1" : "0" ) + "C" + ( C ? "1" : "0" ); } } public struct Nibble { public bool _1 { get; set; } public bool _2 { get; set; } public bool _3 { get; set; } public bool _4 { get; set; } public override string ToString ( ) { return ( _4 ? "1" : "0" ) + ( _3 ? "1" : "0" ) + ( _2 ? "1" : "0" ) + ( _1 ? "1" : "0" ); } } public struct FourBitAdderOutput { public Nibble N { get; set; } public bool C { get; set; } public override string ToString ( ) { return N.ToString ( ) + "c" + ( C ? "1" : "0" ); } }
public static class LogicGates { // Basic Gates public static bool Not ( bool A ) { return !A; } public static bool And ( bool A, bool B ) { return A && B; } public static bool Or ( bool A, bool B ) { return A || B; }
// Composite Gates public static bool Xor ( bool A, bool B ) { return Or ( And ( A, Not ( B ) ), ( And ( Not ( A ), B ) ) ); } }
public static class ConstructiveBlocks { public static BitAdderOutput HalfAdder ( bool A, bool B ) { return new BitAdderOutput ( ) { S = LogicGates.Xor ( A, B ), C = LogicGates.And ( A, B ) }; }
public static BitAdderOutput FullAdder ( bool A, bool B, bool CI ) { BitAdderOutput HA1 = HalfAdder ( CI, A ); BitAdderOutput HA2 = HalfAdder ( HA1.S, B );
return new BitAdderOutput ( ) { S = HA2.S, C = LogicGates.Or ( HA1.C, HA2.C ) }; }
public static FourBitAdderOutput FourBitAdder ( Nibble A, Nibble B, bool CI ) {
BitAdderOutput FA1 = FullAdder ( A._1, B._1, CI ); BitAdderOutput FA2 = FullAdder ( A._2, B._2, FA1.C ); BitAdderOutput FA3 = FullAdder ( A._3, B._3, FA2.C ); BitAdderOutput FA4 = FullAdder ( A._4, B._4, FA3.C );
return new FourBitAdderOutput ( ) { N = new Nibble ( ) { _1 = FA1.S, _2 = FA2.S, _3 = FA3.S, _4 = FA4.S }, C = FA4.C }; }
public static void Test ( ) { Console.WriteLine ( "Four Bit Adder" );
for ( int i = 0; i < 256; i++ ) { Nibble A = new Nibble ( ) { _1 = false, _2 = false, _3 = false, _4 = false }; Nibble B = new Nibble ( ) { _1 = false, _2 = false, _3 = false, _4 = false }; if ( (i & 1) == 1) { A._1 = true; } if ( ( i & 2 ) == 2 ) { A._2 = true; } if ( ( i & 4 ) == 4 ) { A._3 = true; } if ( ( i & 8 ) == 8 ) { A._4 = true; } if ( ( i & 16 ) == 16 ) { B._1 = true; } if ( ( i & 32 ) == 32) { B._2 = true; } if ( ( i & 64 ) == 64 ) { B._3 = true; } if ( ( i & 128 ) == 128 ) { B._4 = true; }
Console.WriteLine ( "{0} + {1} = {2}", A.ToString ( ), B.ToString ( ), FourBitAdder( A, B, false ).ToString ( ) );
}
Console.WriteLine ( ); }
} }
</lang>
Clojure
<lang clojure> (ns rosettacode.adder
(:use clojure.test))
(defn xor-gate [a b]
(or (and a (not b)) (and b (not a))))
(defn half-adder [a b]
"output: (S C)" (cons (xor-gate a b) (list (and a b))))
(defn full-adder [a b c]
"output: (C S)"
(let [HA-ca (half-adder c a)
HA-ca->sb (half-adder (first HA-ca) b)]
(cons (or (second HA-ca) (second HA-ca->sb))
(list (first HA-ca->sb)))))
(defn n-bit-adder
"first bits on the list are low order bits
1 = true 2 = false true 3 = true true 4 = false false true..."
can add numbers of different bit-length
([a-bits b-bits] (n-bit-adder a-bits b-bits false))
([a-bits b-bits carry]
(let [added (full-adder (first a-bits) (first b-bits) carry)]
(if(and (nil? a-bits) (nil? b-bits))
(if carry (list carry) '())
(cons (second added) (n-bit-adder (next a-bits) (next b-bits) (first added)))))))
- use
(n-bit-adder [true true true true true true] [true true true true true true]) => (false true true true true true true) </lang>
D
From the C version. An example of SWAR (SIMD Within A Register) code, that performs 32 or 64 4-bit adds in parallel. 128 adds in parallel are possible using XMM registers. <lang d>import std.stdio: writefln;
pure nothrow void fourBitsAdder(T)(in T a0, in T a1, in T a2, in T a3,
in T b0, in T b1, in T b2, in T b3,
out T o0, out T o1,
out T o2, out T o3,
out T overflow) {
// A XOR using only NOT, AND and OR, as task requires
static pure nothrow T xor(in T x, in T y) {
return (~x & y) | (x & ~y);
}
static pure nothrow void halfAdder(in T a, in T b,
out T s, out T c) {
s = xor(a, b);
// s = a ^ b; // a natural XOR in D
c = a & b;
}
static pure nothrow void fullAdder(in T a, in T b, in T ic,
out T s, out T oc) {
T ps, pc, tc;
halfAdder(/*input*/a, b, /*output*/ps, pc);
halfAdder(/*input*/ps, ic, /*output*/s, tc);
oc = tc | pc;
}
T zero, tc0, tc1, 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);
}
void main() {
alias size_t T;
enum T one = T.max,
zero = T.min,
a0 = zero, a1 = one, a2 = zero, a3 = zero,
b0 = zero, b1 = one, b2 = one, b3 = one;
T s0, s1, s2, s3, overflow;
fourBitsAdder(/*input*/ a0, a1, a2, a3,
/*input*/ b0, b1, b2, b3,
/*output*/s0, s1, s2, s3, overflow);
writefln(" a3 %032b", a3);
writefln(" a2 %032b", a2);
writefln(" a1 %032b", a1);
writefln(" a0 %032b", a0);
writefln(" +");
writefln(" b3 %032b", b3);
writefln(" b2 %032b", b2);
writefln(" b1 %032b", b1);
writefln(" b0 %032b", b0);
writefln(" =");
writefln(" s3 %032b", s3);
writefln(" s2 %032b", s2);
writefln(" s1 %032b", s1);
writefln(" s0 %032b", s0);
writefln("overflow %032b", overflow);
}</lang> Output:
a3 00000000000000000000000000000000
a2 00000000000000000000000000000000
a1 11111111111111111111111111111111
a0 00000000000000000000000000000000
+
b3 11111111111111111111111111111111
b2 11111111111111111111111111111111
b1 11111111111111111111111111111111
b0 00000000000000000000000000000000
=
s3 00000000000000000000000000000000
s2 00000000000000000000000000000000
s1 00000000000000000000000000000000
s0 00000000000000000000000000000000
overflow 11111111111111111111111111111111
Fortran
<lang fortran>module logic
implicit none
contains
function xor(a, b)
logical :: xor logical, intent(in) :: a, b
xor = (a .and. .not. b) .or. (b .and. .not. a)
end function xor
function halfadder(a, b, c)
logical :: halfadder logical, intent(in) :: a, b logical, intent(out) :: c
halfadder = xor(a, b) c = a .and. b
end function halfadder
function fulladder(a, b, c0, c1)
logical :: fulladder logical, intent(in) :: a, b, c0 logical, intent(out) :: c1 logical :: c2, c3
fulladder = halfadder(halfadder(c0, a, c2), b, c3) c1 = c2 .or. c3
end function fulladder
subroutine fourbitadder(a, b, s)
logical, intent(in) :: a(0:3), b(0:3) logical, intent(out) :: s(0:4) logical :: c0, c1, c2
s(0) = fulladder(a(0), b(0), .false., c0) s(1) = fulladder(a(1), b(1), c0, c1) s(2) = fulladder(a(2), b(2), c1, c2) s(3) = fulladder(a(3), b(3), c2, s(4))
end subroutine fourbitadder end module
program Four_bit_adder
use logic implicit none logical, dimension(0:3) :: a, b logical, dimension(0:4) :: s integer, dimension(0:3) :: ai, bi integer, dimension(0:4) :: si integer :: i, j
do i = 0, 15
a(0) = btest(i, 0); a(1) = btest(i, 1); a(2) = btest(i, 2); a(3) = btest(i, 3)
where(a)
ai = 1
else where
ai = 0
end where
do j = 0, 15
b(0) = btest(j, 0); b(1) = btest(j, 1); b(2) = btest(j, 2); b(3) = btest(j, 3)
where(b)
bi = 1
else where
bi = 0
end where
call fourbitadder(a, b, s)
where (s)
si = 1
elsewhere
si = 0
end where
write(*, "(4i1,a,4i1,a,5i1)") ai(3:0:-1), " + ", bi(3:0:-1), " = ", si(4:0:-1)
end do
end do
end program</lang> Selected output
1100 + 1100 = 11000 1100 + 1101 = 11001 1100 + 1110 = 11010 1100 + 1111 = 11011 1101 + 0000 = 01101 1101 + 0001 = 01110 1101 + 0010 = 01111 1101 + 0011 = 10000
Go
Bytes
Go does not have a bit type, so byte is used. This is the straightforward solution using bytes and functions. <lang go>package main
import "fmt"
func xor(a, b byte) byte {
return a&(^b) | b&(^a)
}
func ha(a, b byte) (s, c byte) {
return xor(a, b), a & b
}
func fa(a, b, c0 byte) (s, c1 byte) {
sa, ca := ha(a, c0) s, cb := ha(sa, b) c1 = ca | cb return
}
func add4(a3, a2, a1, a0, b3, b2, b1, b0 byte) (v, s3, s2, s1, s0 byte) {
s0, c0 := fa(a0, b0, 0) s1, c1 := fa(a1, b1, c0) s2, c2 := fa(a2, b2, c1) s3, v = fa(a3, b3, c2) return
}
func main() {
// add 10+9 result should be 1 0 0 1 1 fmt.Println(add4(1, 0, 1, 0, 1, 0, 0, 1))
}</lang> Output
1 0 0 1 1
Channels
Alternative solution is a little more like a simulation. <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.
Haskell
Basic gates: <lang haskell>import Control.Arrow
bor, band :: Int -> Int -> Int bor = max band = min bnot :: Int -> Int bnot = (1-)</lang> Gates built with basic ones: <lang haskell>nand, xor :: Int -> Int -> Int nand = (bnot.).band xor a b = uncurry nand. (nand a &&& nand b) $ nand a b</lang> Adder circuits: <lang haskell>halfAdder = uncurry band &&& uncurry xor fullAdder (c, a, b) = (\(cy,s) -> first (bor cy) $ halfAdder (b, s)) $ halfAdder (c, a)
adder4 as = foldr (\(f,a,b) (cy,bs) -> second(:bs) $ f (cy,a,b)) (0,[]). zip3 (replicate 4 fullAdder) as</lang>
Example using adder4 <lang haskell>*Main> adder4 [1,0,1,0] [1,1,1,1] (1,[1,0,0,1])</lang>
J
Implementation
<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>
To produce all results: <lang j> add"1/~#:i.16</lang>
This will produce a 16 by 16 by 5 array, the first axis being the left argument (representing values 0..15), the second axis the right argument and the final axis being the bit indices (carry, 8, 4, 2, 1). Alternatively, the fact that add was designed to operate on lists of bits could have been incorporated into its definition:
<lang j>add=: ((({.,0:)@[ or {:@[ hadd {.@]), }.@])/@hadd"1</lang>
Then to get all results you could use: <lang j> add/~#:i.16</lang>
Compare this to a regular addition table: <lang j> +/~i.10</lang> (this produces a 10 by 10 array -- the results have no further internal structure.)
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 these letters represent verbs such as and or or not x y these letters represent 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
JavaScript
Error Handling
In order to keep the binary-ness obvious, all operations will occur on 0s and 1s. To enforce this, we'll first create a couple of helper functions.
<lang JavaScript> function acceptedBinFormat(bin) {
if (bin == 1 || bin === 0 || bin === '0')
return true;
else
return bin;
}
function arePseudoBin() {
var args = [].slice.call(arguments), len = args.length;
while(len--)
if (acceptedBinFormat(args[len]) !== true)
throw new Error('argument must be 0, \'0\', 1, or \'1\', argument ' + len + ' was ' + args[len]);
return true;
} </lang>
Implementation
Now we build up the gates, starting with 'not' and 'and' as building blocks. Those allow us to construct 'nand', 'or', and 'xor' then a half and full adders and, finally, the four bit adder.
<lang JavaScript> // basic building blocks allowed by the rules are ~, &, and |, we'll fake these // in a way that makes what they do (at least when you use them) more obvious // than the other available options do.
function not(a) {
if (arePseudoBin(a))
return a == 1 ? 0 : 1;
}
function and(a, b) {
if (arePseudoBin(a, b))
return a + b < 2 ? 0 : 1;
}
function nand(a, b) {
if (arePseudoBin(a, b))
return not(and(a, b));
}
function or(a, b) {
if (arePseudoBin(a, b))
return nand(nand(a,a), nand(b,b));
}
function xor(a, b) {
if (arePseudoBin(a, b))
return nand(nand(nand(a,b), a), nand(nand(a,b), b));
}
function halfAdder(a, b) {
if (arePseudoBin(a, b))
return { carry: and(a, b), sum: xor(a, b) };
}
function fullAdder(a, b, c) {
if (arePseudoBin(a, b, c)) {
var h0 = halfAdder(a, b),
h1 = halfAdder(h0.sum, c);
return {carry: or(h0.carry, h1.carry), sum: h1.sum };
}
}
function fourBitAdder(a, b) {
if (typeof a.length == 'undefined' || typeof b.length == 'undefined')
throw new Error('bad values');
// not sure if the rules allow this, but we need to pad the values
// if they're too short and trim them if they're too long
var inA = Array(4),
inB = Array(4),
out = Array(4),
i = 4,
pass;
while (i--) {
inA[i] = a[i] != 1 ? 0 : 1;
inB[i] = b[i] != 1 ? 0 : 1;
}
// now we can start adding... I'd prefer to do this in a loop, // but that wouldn't be "connecting the other 'constructive blocks', // in turn made of 'simpler' and 'smaller' ones" pass = halfAdder(inA[3], inB[3]); out[3] = pass.sum; pass = fullAdder(inA[2], inB[2], pass.carry); out[2] = pass.sum; pass = fullAdder(inA[1], inB[1], pass.carry); out[1] = pass.sum; pass = fullAdder(inA[0], inB[0], pass.carry); out[0] = pass.sum; return out.join();
} </lang>
Example Use
<lang JavaScript>fourBitAdder('1010', '0101'); // 1111 (15)</lang>
all results:
<lang JavaScript> // run this in your browsers console var outer = inner = 16, a, b;
while(outer--) {
a = (8|outer).toString(2);
while(inner--) {
b = (8|inner).toString(2);
console.log(a + ' + ' + b + ' = ' + fourBitAdder(a, b));
}
inner = outer;
} </lang>
LabVIEW
LabVIEW's G language is a kind of circuit diagram based programming. Thus, a circuit diagram is pseudo-code for a G block diagram, which makes coding a four bit adder trivial.
Half Adder
Full Adder
4bit Adder
MATLAB
The four bit adder presented can work on matricies of 1's and 0's, which are stored as characters, doubles, or booleans. MATLAB has functions to convert decimal numbers to binary, but these functions convert a decimal number not to binary but a string data type of 1's and 0's. So, this four bit adder is written to be compatible with MATLAB's representation of binary. Also, because this is MATLAB, and you might want to add arrays of 4-bit binary numbers together, this implementation will add two column vectors of 4-bit binary numbers together.
<lang MATLAB>function [S,v] = fourBitAdder(input1,input2)
%Make sure that only 4-Bit numbers are being added. This assumes that
%if input1 and input2 are a vector of multiple decimal numbers, then
%the binary form of these vectors are an n by 4 matrix.
assert((size(input1,2) == 4) && (size(input2,2) == 4),'This will only work on 4-Bit Numbers');
%Converts MATLAB binary strings to matricies of 1 and 0
function mat = binStr2Mat(binStr)
mat = zeros(size(binStr));
for i = (1:numel(binStr))
mat(i) = str2double(binStr(i));
end
end
%XOR decleration
function AxorB = xor(A,B)
AxorB = or(and(A,not(B)),and(B,not(A)));
end
%Half-Adder decleration
function [S,C] = halfAdder(A,B)
S = xor(A,B);
C = and(A,B);
end
%Full-Adder decleration
function [S,Co] = fullAdder(A,B,Ci)
[SAdder1,CAdder1] = halfAdder(Ci,A);
[S,CAdder2] = halfAdder(SAdder1,B);
Co = or(CAdder1,CAdder2);
end
%The rest of this code is the 4-bit adder
binStrFlag = false; %A flag to determine if the original input was a binary string
%If either of the inputs was a binary string, convert it to a matrix of
%1's and 0's.
if ischar(input1)
input1 = binStr2Mat(input1);
binStrFlag = true;
end
if ischar(input2)
input2 = binStr2Mat(input2);
binStrFlag = true;
end
%This does the addition S = zeros(size(input1));
[S(:,4),Co] = fullAdder(input1(:,4),input2(:,4),0);
[S(:,3),Co] = fullAdder(input1(:,3),input2(:,3),Co);
[S(:,2),Co] = fullAdder(input1(:,2),input2(:,2),Co);
[S(:,1),v] = fullAdder(input1(:,1),input2(:,1),Co);
%If the original inputs were binary strings, convert the output of the
%4-bit adder to a binary string with the same formatting as the
%original binary strings.
if binStrFlag
S = num2str(S);
v = num2str(v);
end
end %fourBitAdder</lang>
Sample Usage: <lang MATLAB>>> [S,V] = fourBitAdder([0 0 0 1],[1 1 1 1])
S =
0 0 0 0
V =
1
>> [S,V] = fourBitAdder([0 0 0 1;0 0 1 0],[0 0 0 1;0 0 0 1])
S =
0 0 1 0
0 0 1 1
V =
0
0
>> [S,V] = fourBitAdder(dec2bin(10,4),dec2bin(1,4))
S =
1 0 1 1
V =
0
>> [S,V] = fourBitAdder(dec2bin([10 11],4),dec2bin([1 1],4))
S =
1 0 1 1 1 1 0 0
V =
0 0
>> bin2dec(S)
ans =
11 12</lang>
MUMPS
<lang MUMPS>XOR(Y,Z) ;Uses logicals - i.e., 0 is false, anything else is true (1 is used if setting a value)
QUIT (Y&'Z)!('Y&Z)
HALF(W,X)
QUIT $$XOR(W,X)_"^"_(W&X)
FULL(U,V,CF)
NEW F1,F2 S F1=$$HALF(U,V) S F2=$$HALF($P(F1,"^",1),CF) QUIT $P(F2,"^",1)_"^"_($P(F1,"^",2)!($P(F2,"^",2)))
FOUR(Y,Z,C4)
NEW S,I,T FOR I=4:-1:1 SET T=$$FULL($E(Y,I),$E(Z,I),C4),$E(S,I)=$P(T,"^",1),C4=$P(T,"^",2) K I,T QUIT S_"^"_C4</lang>
Usage:
USER>S N1="0110",N2="0010",C=0,T=$$FOUR^ADDER(N1,N2,C) USER>W N1_" + "_N2_" + "_C_" = "_$P(T,"^")_" Carry "_$P(T,"^",2) 0110 + 0010 + 0 = 1000 Carry 0 USER>S N1="0110",N2="1110",C=0,T=$$FOUR^ADDER(N1,N2,C) USER>W T 0100^1 USER>W N1_" + "_N2_" + "_C_" = "_$P(T,"^")_" Carry "_$P(T,"^",2) 0110 + 1110 + 0 = 0100 Carry 1
MyHDL
To interpret and run this code you will need a recent copy of Python, and the MyHDL library from myhdl.org. Both examples integrate test code, and export Verilog and VHDL for hardware synthesis.
Verbose Code - With integrated Test & Demo
<lang python>#!/usr/bin/env python
""" http://rosettacode.org/wiki/Four_bit_adder
Demonstrate theoretical four bit adder simulation
using And, Or & Invert primitives
2011-05-10 jc
"""
from myhdl import always_comb, ConcatSignal, delay, intbv, Signal, \
Simulation, toVerilog, toVHDL
from random import randrange
""" define set of primitives
------------------------ """
def inverter(z, a): # define component name & interface
""" z <- not(a) """
@always_comb # define asynchronous logic
def logic():
z.next = not a
return logic # return defined logic, named 'inverter'
def and2(z, a, b):
""" z <- a and b """
@always_comb
def logic():
z.next = a and b
return logic
def or2(z, a, b):
""" z <- a or b """
@always_comb
def logic():
z.next = a or b
return logic
""" build components using defined primitive set
-------------------------------------------- """
def xor2 (z, a, b):
""" z <- a xor b """ # define interconnect signals nota, notb, annotb, bnnota = [Signal(bool(0)) for i in range(4)] # name sub-components, and their interconnect inv0 = inverter(nota, a) inv1 = inverter(notb, b) and2a = and2(annotb, a, notb) and2b = and2(bnnota, b, nota) or2a = or2(z, annotb, bnnota) return inv0, inv1, and2a, and2b, or2a
def halfAdder(carry, summ, in_a, in_b):
""" carry,sum is the sum of in_a, in_b """ and2a = and2(carry, in_a, in_b) xor2a = xor2(summ, in_a, in_b) return and2a, xor2a
def fullAdder(fa_c1, fa_s, fa_c0, fa_a, fa_b):
""" fa_c0,fa_s is the sum of fa_c0, fa_a, fa_b """ ha1_s, ha1_c1, ha2_c1 = [Signal(bool(0)) for i in range(3)] halfAdder01 = halfAdder(ha1_c1, ha1_s, fa_c0, fa_a) halfAdder02 = halfAdder(ha2_c1, fa_s, ha1_s, fa_b) or2a = or2(fa_c1, ha1_c1, ha2_c1) return halfAdder01, halfAdder02, or2a
def Adder4b_ST(co,sum4, ina,inb):
assemble 4 full adders
c = [Signal(bool()) for i in range(0,4)]
sl = [Signal(bool()) for i in range(4)] # sum list
halfAdder_0 = halfAdder(c[1],sl[0], ina(0),inb(0))
fullAdder_1 = fullAdder(c[2],sl[1], c[1],ina(1),inb(1))
fullAdder_2 = fullAdder(c[3],sl[2], c[2],ina(2),inb(2))
fullAdder_3 = fullAdder(co, sl[3], c[3],ina(3),inb(3))
# create an internal bus for the output list
sc = ConcatSignal(*reversed(sl)) # create internal bus for output list
@always_comb
def list2intbv():
sum4.next = sc # assign internal bus to actual output
return halfAdder_0, fullAdder_1, fullAdder_2, fullAdder_3, list2intbv
""" define signals and code for testing
----------------------------------- """
t_co, t_s, t_a, t_b, dbug = [Signal(bool(0)) for i in range(5)] ina4, inb4, sum4 = [Signal(intbv(0)[4:]) for i in range(3)]
def test():
print "\n b a | c1 s \n -------------------"
for i in range(15):
ina4.next, inb4.next = randrange(2**4), randrange(2**4)
yield delay(5)
print " %2d %2d | %2d %2d " \
% (ina4,inb4, t_co,sum4)
assert t_co * 16 + sum4 == ina4 + inb4
print
""" instantiate components and run test
----------------------------------- """
Adder4b_01 = Adder4b_ST(t_co,sum4, ina4,inb4) test_1 = test()
def main():
sim = Simulation(Adder4b_01, test_1) sim.run() toVHDL(Adder4b_ST, t_co,sum4, ina4,inb4) toVerilog(Adder4b_ST, t_co,sum4, ina4,inb4)
if __name__ == '__main__':
main()
</lang>
Professional Code - with test bench
<lang python>#!/usr/bin/env python
from myhdl import *
def Half_adder(a, b, s, c):
@always_comb
def logic():
s.next = a ^ b
c.next = a & b
return logic
def Full_Adder(a, b, cin, s, c_out):
s_ha1, c_ha1, c_ha2 = [Signal(bool()) for i in range(3)] ha1 = Half_adder(a=cin, b=a, s=s_ha1, c=c_ha1) ha2 = Half_adder(a=s_ha1, b=b, s=s, c=c_ha2)
@always_comb
def logic():
c_out.next = c_ha1 | c_ha2
return ha1, ha2, logic
def Multibit_Adder(a, b, s):
N = len(s)-1 # convert input busses to lists al = [a(i) for i in range(N)] bl = [b(i) for i in range(N)] # set up lists for carry and output cl = [Signal(bool()) for i in range(N+1)] sl = [Signal(bool()) for i in range(N+1)] # boundaries for carry and output cl[0] = 0 sl[N] = cl[N] # create an internal bus for the output list sc = ConcatSignal(*reversed(sl))
# assign internal bus to actual output
@always_comb
def assign():
s.next = sc
# create a list of adders
add = [None] * N
for i in range(N):
add[i] = Full_Adder(a=al[i], b=bl[i], s=sl[i], cin=cl[i], c_out=cl[i+1])
return add, assign
- declare I/O for a four-bit adder
N=4 a = Signal(intbv(0)[N:]) b = Signal(intbv(0)[N:]) s = Signal(intbv(0)[N+1:])
- convert to Verilog and VHDL
toVerilog(Multibit_Adder, a, b, s) toVHDL(Multibit_Adder, a, b, s)
- set up a test bench
from random import randrange def tb():
dut = Multibit_Adder(a, b, s)
@instance
def check():
yield delay(10)
for i in range(100):
p, q = randrange(2**N), randrange(2**N)
a.next = p
b.next = q
yield delay(10)
assert s == p + q
return dut, check
- the entry point for the py.test unit test framework
def test_Adder():
sim = Simulation(tb()) sim.run()
</lang>
OCaml
<lang ocaml> (* File blocks.ml
A block is just a black box with nin input lines and nout output lines, numbered from 0 to nin-1 and 0 to nout-1 respectively. It will be stored in a caml record, with the operation stored as a function. A value on a line is represented by a boolean value. *)
type block = { nin:int; nout:int; apply:bool array -> bool array };;
(* First we need function for boolean conversion to and from integer values, mainly for pretty printing of results *)
let int_of_bits nbits v = if (Array.length v) <> nbits then failwith "bad args" else (let r = ref 0L in for i=nbits-1 downto 0 do r := Int64.add (Int64.shift_left !r 1) (if v.(i) then 1L else 0L) done; !r);;
let bits_of_int nbits n = let v = Array.make nbits false and r = ref n in for i=0 to nbits-1 do v.(i) <- (Int64.logand !r 1L) <> Int64.zero; r := Int64.shift_right_logical !r 1 done; v;;
let input nbits v = let n = Array.length v in let w = Array.make (n*nbits) false in for i=0 to n-1 do Array.blit (bits_of_int nbits v.(i)) 0 w (i*nbits) nbits done; w;;
let output nbits v = let nv = Array.length v in let r = nv mod nbits and n = nv/nbits in if r <> 0 then failwith "bad output size" else let w = Array.make n 0L in for i=0 to n-1 do w.(i) <- int_of_bits nbits (Array.sub v (i*nbits) nbits) done; w;;
(* We have a type for blocks, so we need operations on blocks.
assoc: make one block from two blocks, side by side (they are not connected) serial: connect input from one block to output of another block parallel: make two outputs from one input passing through two blocks block_array: an array of blocks linked by the same connector (assoc, serial, parallel) *)
let assoc a b = { nin=a.nin+b.nin; nout=a.nout+b.nout; apply=function bits -> Array.append (a.apply (Array.sub bits 0 a.nin)) (b.apply (Array.sub bits a.nin b.nin)) };;
let serial a b = if a.nout <> b.nin then failwith "[serial] bad block" else { nin=a.nin; nout=b.nout; apply=function bits -> b.apply (a.apply bits) };;
let parallel a b = if a.nin <> b.nin then failwith "[parallel] bad blocks" else { nin=a.nin; nout=a.nout+b.nout; apply=function bits -> Array.append (a.apply bits) (b.apply bits) };;
let block_array comb v = let n = Array.length v and r = ref v.(0) in for i=1 to n-1 do r := comb !r v.(i) done; !r;;
(* wires
map: map n input lines on length(v) output lines, using the links out(k)=v(in(k)) pass: n wires not connected (out(k) = in(k)) fork: a wire is developped into n wires having the same value perm: permutation of wires forget: n wires going nowhere sub: subset of wires, other ones going nowhere *)
let map n v = { nin=n; nout=Array.length v; apply=function bits -> Array.map (function k -> bits.(k)) v };;
let pass n = { nin=n; nout=n; apply=function bits -> bits };;
let fork n = { nin=1; nout=n; apply=function bits -> Array.make n bits.(0) };;
let perm v = let n = Array.length v in { nin=n; nout=n; apply=function bits -> Array.init n (function k -> bits.(v.(k))) };;
let forget n = { nin=n; nout=0; apply=function bits -> [| |] };;
let sub nin nout where = { nin=nin; nout=nout; apply=function bits -> Array.sub bits where nout };;
let transpose n p v = if n*p <> Array.length v then failwith "bad dim" else let w = Array.copy v in for i=0 to n-1 do for j=0 to p-1 do let r = i*p+j and s = j*n+i in w.(r) <- v.(s) done done; w;;
(* line mixing (a special permutation) mix 4 2 : 0,1,2,3, 4,5,6,7 -> 0,4, 1,5, 2,6, 3,7 unmix: inverse operation *)
let mix n p = perm (transpose n p (Array.init (n*p) (function x -> x)));;
let unmix n p = perm (transpose p n (Array.init (n*p) (function x -> x)));;
(* basic blocks
dummy: no input, no output, usually not useful const: n wires with constant value (true or false) encode: translates an Int64 into boolean values, keeping only n lower bits bnand: NAND gate, the basic building block for all the other basic gates (or, and, not...) *)
let dummy = { nin=0; nout=0; apply=function bits -> bits };;
let const b n = { nin=0; nout=n; apply=function bits -> Array.make n b };;
let encode nbits x = { nin=0; nout=nbits; apply=function bits -> bits_of_int nbits x };;
let bnand = { nin=2; nout=1; apply=function [| a; b |] -> [| not (a && b) |] | _ -> failwith "bad args" };;
(* block evaluation : returns the value of the output, given an input and a block. *)
let eval block nbits_in nbits_out v = output nbits_out (block.apply (input nbits_in v));;
(* building a 4-bit adder *)
(* first we build the usual gates *)
let bnot = serial (fork 2) bnand;;
let band = serial bnand bnot;;
(* a or b = !a nand !b *) let bor = serial (assoc bnot bnot) bnand;;
(* line "a" -> two lines, "a" and "not a" *) let a_not_a = parallel (pass 1) bnot;;
let bxor = block_array serial [| assoc a_not_a a_not_a; perm [| 0; 3; 1; 2 |]; assoc band band; bor |];;
let half_adder = parallel bxor band;;
(* bits C0,A,B -> S,C1 *) let full_adder = block_array serial [| assoc half_adder (pass 1); perm [| 1; 0; 2 |]; assoc (pass 1) half_adder; perm [| 1; 0; 2 |]; assoc (pass 1) bor |];;
(* 4-bit adder *) let add4 = block_array serial [| mix 4 2; assoc half_adder (pass 6); assoc (assoc (pass 1) full_adder) (pass 4); assoc (assoc (pass 2) full_adder) (pass 2); assoc (pass 3) full_adder |];;
(* 4-bit adder and three supplementary lines to make a multiple of 4 (to translate back to 4-bit integers) *) let add4_io = assoc add4 (const false 3);;
(* wrapping the 4-bit to input and output integers instead of booleans plus a b -> (sum,carry)
- )
let plus a b = let v = Array.map Int64.to_int (eval add4_io 4 4 (Array.map Int64.of_int [| a; b |])) in v.(0), v.(1);; </lang>
Testing
<lang ocaml>
- open Blocks;;
- plus 4 5;;
- : int * int = (9, 0)
- plus 15 1;;
- : int * int = (0, 1)
- plus 15 15;;
- : int * int = (14, 1)
- plus 0 0;;
- : int * int = (0, 0) </lang>
An extension : n-bit adder, for n <= 64 (n could be greater, but we use Int64 for I/O)
<lang ocaml> (* general adder (n bits with n <= 64) *) let gen_adder n = block_array serial [| mix n 2; assoc half_adder (pass (2*n-2)); block_array serial (Array.init (n-2) (function k -> assoc (assoc (pass (k+1)) full_adder) (pass (2*(n-k-2))))); assoc (pass (n-1)) full_adder |];;
let gadd_io n = assoc (gen_adder n) (const false (n-1));;
let gen_plus n a b = let v = Array.map Int64.to_int (eval (gadd_io n) n n (Array.map Int64.of_int [| a; b |])) in v.(0), v.(1);; </lang>
And a test
<lang ocaml>
- gen_plus 7 100 100;;
- : int * int = (72, 1)
- gen_plus 8 100 100;;
- : int * int = (200, 0) </lang>
PARI/GP
<lang parigp>xor(a,b)=(!a&b)|(a&!b); halfadd(a,b)=[a&b,xor(a,b)]; fulladd(a,b,c)=my(t=halfadd(a,c),s=halfadd(t[2],b));[t[1]|s[1],s[2]]; add4(a3,a2,a1,a0,b3,b2,b1,b0)={ my(s0,s1,s2,s3); s0=fulladd(a0,b0,0); s1=fulladd(a1,b1,s0[1]); s2=fulladd(a2,b2,s1[1]); s3=fulladd(a3,b3,s2[1]); [s3[1],s3[2],s2[2],s1[2],s0[2]] }; add4(0,0,0,0,0,0,0,0)</lang>
Perl 6
<lang perl6>sub xor ($a, $b) { ($a and not $b) or (not $a and $b) }
sub half-adder ($a, $b) {
return xor($a, $b), ($a and $b);
}
sub full-adder ($a, $b, $c0) {
my ($ha0_s, $ha0_c) = half-adder($c0, $a); my ($ha1_s, $ha1_c) = half-adder($ha0_s, $b); return $ha1_s, ($ha0_c or $ha1_c);
}
sub four-bit-adder ($a0, $a1, $a2, $a3, $b0, $b1, $b2, $b3) {
my ($fa0_s, $fa0_c) = full-adder($a0, $b0, 0); my ($fa1_s, $fa1_c) = full-adder($a1, $b1, $fa0_c); my ($fa2_s, $fa2_c) = full-adder($a2, $b2, $fa1_c); my ($fa3_s, $fa3_c) = full-adder($a3, $b3, $fa2_c);
return $fa0_s, $fa1_s, $fa2_s, $fa3_s, $fa3_c;
}
{
use Test;
is four-bit-adder(1, 0, 0, 0, 1, 0, 0, 0), (0, 1, 0, 0, 0), '1 + 1 == 2'; is four-bit-adder(1, 0, 1, 0, 1, 0, 1, 0), (0, 1, 0, 1, 0), '5 + 5 == 10'; is four-bit-adder(1, 0, 0, 1, 1, 1, 1, 0)[4], 1, '7 + 9 == overflow';
}</lang>
Output:
ok 1 - 1 + 1 == 2 ok 2 - 5 + 5 == 10 ok 3 - 7 + 9 == overflow
PicoLisp
<lang PicoLisp>(de halfAdder (A B) #> (Carry . Sum)
(cons
(and A B)
(xor A B) ) )
(de fullAdder (A B C) #> (Carry . Sum)
(let (Ha1 (halfAdder C A) Ha2 (halfAdder (cdr Ha1) B))
(cons
(or (car Ha1) (car Ha2))
(cdr Ha2) ) ) )
(de 4bitsAdder (A4 A3 A2 A1 B4 B3 B2 B1) #> (V S4 S3 S2 S1)
(let
(Fa1 (fullAdder A1 B1)
Fa2 (fullAdder A2 B2 (car Fa1))
Fa3 (fullAdder A3 B3 (car Fa2))
Fa4 (fullAdder A4 B4 (car Fa3)) )
(list
(car Fa4)
(cdr Fa4)
(cdr Fa3)
(cdr Fa2)
(cdr Fa1) ) ) )</lang>
Output:
: (4bitsAdder NIL NIL NIL T NIL NIL NIL T) -> (NIL NIL NIL T NIL) : (4bitsAdder NIL T NIL NIL NIL NIL T T) -> (NIL NIL T T T) : (4bitsAdder NIL T T T NIL T T T) -> (NIL T T T NIL) : (4bitsAdder T T T T NIL NIL NIL T) -> (T NIL NIL NIL NIL)
PL/I
<lang PL/I> /* 4-BIT ADDER */
TEST: PROCEDURE OPTIONS (MAIN);
DECLARE CARRY_IN BIT (1) STATIC INITIAL ('0'B) ALIGNED;
declare (m, n, sum)(4) bit(1) aligned;
declare i fixed binary;
get edit (m, n) (b(1)); put edit (m, ' + ', n, ' = ') (4 b, a);
do i = 4 to 1 by -1;
call full_adder ((carry_in), m(i), n(i), sum(i), carry_in);
end;
put edit (sum) (b);
HALF_ADDER: PROCEDURE (IN1, IN2, SUM, CARRY);
DECLARE (IN1, IN2, SUM, CARRY) BIT (1) ALIGNED;
SUM = ( ^IN1 & IN2) | ( IN1 & ^IN2);
/* Exclusive OR using only AND, NOT, OR. */
CARRY = IN1 & IN2;
END HALF_ADDER;
FULL_ADDER: PROCEDURE (CARRY_IN, IN1, IN2, SUM, CARRY);
DECLARE (CARRY_IN, IN1, IN2, SUM, CARRY) BIT (1) ALIGNED; DECLARE (SUM2, CARRY2) BIT (1) ALIGNED;
CALL HALF_ADDER (CARRY_IN, IN1, SUM, CARRY); CALL HALF_ADDER (SUM, IN2, SUM2, CARRY2); SUM = SUM2; CARRY = CARRY | CARRY2;
END FULL_ADDER;
END TEST; </lang>
PowerShell
Using Bytes as Inputs
<lang Powershell>function bxor2 ( [byte] $a, [byte] $b ) {
$out1 = $a -band ( -bnot $b ) $out2 = ( -bnot $a ) -band $b $out1 -bor $out2
}
function hadder ( [byte] $a, [byte] $b ) {
@{
"S"=bxor2 $a $b
"C"=$a -band $b
}
}
function fadder ( [byte] $a, [byte] $b, [byte] $cd ) {
$out1 = hadder $cd $a
$out2 = hadder $out1["S"] $b
@{
"S"=$out2["S"]
"C"=$out1["C"] -bor $out2["C"]
}
}
function FourBitAdder ( [byte] $a, [byte] $b ) {
$a0 = $a -band 1
$a1 = ($a -band 2)/2
$a2 = ($a -band 4)/4
$a3 = ($a -band 8)/8
$b0 = $b -band 1
$b1 = ($b -band 2)/2
$b2 = ($b -band 4)/4
$b3 = ($b -band 8)/8
$out1 = fadder $a0 $b0 0
$out2 = fadder $a1 $b1 $out1["C"]
$out3 = fadder $a2 $b2 $out2["C"]
$out4 = fadder $a3 $b3 $out3["C"]
@{
"S"="{3}{2}{1}{0}" -f $out1["S"], $out2["S"], $out3["S"], $out4["S"]
"V"=$out4["C"]
}
}
FourBitAdder 3 5
FourBitAdder 0xA 5
FourBitAdder 0xC 0xB
[Convert]::ToByte((FourBitAdder 0xC 0xB)["S"],2)</lang>
PureBasic
<lang PureBasic>;Because no representation for a solitary bit is present, bits are stored as bytes.
- Output values from the constructive building blocks is done using pointers (i.e. '*').
Procedure.b notGate(x)
ProcedureReturn ~x
EndProcedure
Procedure.b xorGate(x,y)
ProcedureReturn (x & notGate(y)) | (notGate(x) & y)
EndProcedure
Procedure halfadder(a, b, *sum.Byte, *carry.Byte)
*sum\b = xorGate(a, b) *carry\b = a & b
EndProcedure
Procedure fulladder(a, b, c0, *sum.Byte, *c1.Byte)
Protected sum_ac.b, carry_ac.b, carry_sb.b halfadder(c0, a, @sum_ac, @carry_ac) halfadder(sum_ac, b, *sum, @carry_sb) *c1\b = carry_ac | carry_sb
EndProcedure
Procedure fourbitsadder(a0, a1, a2, a3, b0, b1, b2, b3 , *s0.Byte, *s1.Byte, *s2.Byte, *s3.Byte, *v.Byte)
Protected.b c1, c2, c3 fulladder(a0, b0, 0, *s0, @c1) fulladder(a1, b1, c1, *s1, @c2) fulladder(a2, b2, c2, *s2, @c3) fulladder(a3, b3, c3, *s3, *v)
EndProcedure
- // Test implementation, map two 4-character strings to the inputs of the fourbitsadder() and display results
Procedure.s test_4_bit_adder(a.s,b.s)
Protected.b s0, s1, s2, s3, v, i Dim a.b(3) Dim b.b(3) For i = 0 To 3 a(i) = Val(Mid(a, 4 - i, 1)) b(i) = Val(Mid(b, 4 - i, 1)) Next
fourbitsadder(a(0), a(1), a(2), a(3), b(0), b(1), b(2), b(3), @s0, @s1, @s2, @s3, @v) ProcedureReturn a + " + " + b + " = " + Str(s3) + Str(s2) + Str(s1) + Str(s0) + " overflow " + Str(v)
EndProcedure
If OpenConsole()
PrintN(test_4_bit_adder("0110","1110"))
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit")
Input()
CloseConsole()
EndIf</lang> Sample output:
0110 + 1110 = 0100 overflow 1
Python
Individual boolean bits are represented by either 1, 0, True (interchangeable with 1), and False (same as zero). a bit of value None is sometimes used as a place-holder.
Python functions represent the building blocks of the circuit: a function parameter for each block intput and individual block outputs are either a return of a single value or a return of a tuple of values - one for each block output. A single element tuple is not returned for a block with one output.
Python lists are used to represent bus's of multiple bits, and in this circuit, bit zero - the least significant bit of bus's, is at index zero of the list, (which will be printed as the left-most member of a list).
The repetitive connections of the full adder block, fa4, are achieved by using a for loop which could easily be modified to generate adders of any width. fa4's arguments are interpreted as indexable, ordered collections of values - usually lists but tuples would work too. fa4's outputs are the sum, s, as a list and the single bit carry.
Functions are provided to convert between integers and bus's and back; and the test routine shows how they can be used to translate between the normal Python values and those of the simulation.
<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>
REXX
(A copy of the Fortran example)
Programming note: REXX subroutines/functions are call by value, not call by name,
so REXX has to EXPOSE a variable and set/define it with that mechanism.
REXX programming syntax:
the && symbol is the exclusive OR function (XOR).
the | symbol is a logical OR.
the & symbol is a logical AND.
<lang rexx>
/*REXX program shows (all) the sums of a full 4-bit adder (with carry).*/
call hdr1; call hdr2
do j=0 for 16
do m=0 for 4; a.m=bit(j,m); end
do k=0 for 16
do m=0 for 4; b.m=bit(k,m); end
sc=4bitAdder(a.,b.)
z=a.3 a.2 a.1 a.0 '_+_' b.3 b.2 b.1 b.0 '_=_' sc ',' s.3 s.2 s.1 s.0
say translate(space(z,0),,'_')
end /*k*/
end /*j*/
call hdr2; call hdr1 exit
/*─────────────────────────────────────subroutines/functions────────────*/
hdr1: say 'aaaa + bbbb = c, sum [c=carry]'; return
hdr2: say '==== ==== ======';return
bit: procedure; arg x,y; return substr(reverse(x2b(d2x(x))),y+1,1)
halfAdder: procedure expose c; parse arg x,y; c=x & y; return x && y
fullAdder: procedure expose c; parse arg x,y,fc _1=halfAdder(fc,x); c1=c _2=halfAdder(_1,y); c=c | c1; return _2
4bitAdder: procedure expose s. a. b.; carry.=0
do j=0 for 4; n=j-1 s.j=fullAdder(a.j, b.j, carry.n); carry.j=c end
return c </lang> Output (most lines were elided):
aaaa + bbbb = c, sum [c=carry] ==== ==== ====== 0000 + 0000 = 0,0000 0000 + 0001 = 0,0001 0000 + 0010 = 0,0010 0000 + 0011 = 0,0011 0000 + 0100 = 0,0100 0000 + 0101 = 0,0101 0000 + 0110 = 0,0110 0000 + 0111 = 0,0111 0000 + 1000 = 0,1000 0000 + 1001 = 0,1001 ∙ ∙ ∙ 0101 + 0100 = 0,1001 0101 + 0101 = 0,1010 0101 + 0110 = 0,1011 0101 + 0111 = 0,1100 0101 + 1000 = 0,1101 0101 + 1001 = 0,1110 0101 + 1010 = 0,1111 0101 + 1011 = 1,0000 0101 + 1100 = 1,0001 0101 + 1101 = 1,0010 0101 + 1110 = 1,0011 0101 + 1111 = 1,0100 0110 + 0000 = 0,0110 0110 + 0001 = 0,0111 0110 + 0010 = 0,1000 0110 + 0011 = 0,1001 0110 + 0100 = 0,1010 0110 + 0101 = 0,1011 0110 + 0110 = 0,1100 0110 + 0111 = 0,1101 0110 + 1000 = 0,1110 0110 + 1001 = 0,1111 0110 + 1010 = 1,0000 0110 + 1011 = 1,0001 0110 + 1100 = 1,0010 0110 + 1101 = 1,0011 ∙ ∙ ∙ 1110 + 1110 = 1,1100 1110 + 1111 = 1,1101 1111 + 0000 = 0,1111 1111 + 0001 = 1,0000 1111 + 0010 = 1,0001 1111 + 0011 = 1,0010 1111 + 0100 = 1,0011 1111 + 0101 = 1,0100 1111 + 0110 = 1,0101 1111 + 0111 = 1,0110 1111 + 1000 = 1,0111 1111 + 1001 = 1,1000 1111 + 1010 = 1,1001 1111 + 1011 = 1,1010 1111 + 1100 = 1,1011 1111 + 1101 = 1,1100 1111 + 1110 = 1,1101 1111 + 1111 = 1,1110 ==== ==== ====== aaaa + bbbb = c, sum [c=carry]
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. Currently can make -- hard the implementation of a latch 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>
Scala
<lang scala>object FourBitAdder {
type Nibble=(Boolean, Boolean, Boolean, Boolean)
def xor(a:Boolean, b:Boolean)=(!a)&&b || a&&(!b)
def halfAdder(a:Boolean, b:Boolean)={
val s=xor(a,b)
val c=a && b
(s, c)
}
def fullAdder(a:Boolean, b:Boolean, cIn:Boolean)={
val (s1, c1)=halfAdder(a, cIn)
val (s, c2)=halfAdder(s1, b)
val cOut=c1 || c2
(s, cOut)
}
def fourBitAdder(a:Nibble, b:Nibble)={
val (s0, c0)=fullAdder(a._4, b._4, false)
val (s1, c1)=fullAdder(a._3, b._3, c0)
val (s2, c2)=fullAdder(a._2, b._2, c1)
val (s3, cOut)=fullAdder(a._1, b._1, c2)
((s3, s2, s1, s0), cOut)
}
}</lang>
A test program using the object above. <lang scala>object FourBitAdderTest {
import FourBitAdder._
def main(args: Array[String]): Unit = {
println("%4s %4s %4s %2s".format("A","B","S","C"))
for(a <- 0 to 15; b <- 0 to 15){
val (s, cOut)=fourBitAdder(a,b)
println("%4s + %4s = %4s %2d".format(nibbleToString(a),nibbleToString(b),nibbleToString(s),cOut.toInt))
}
}
implicit def toInt(b:Boolean):Int=if (b) 1 else 0 implicit def intToBool(i:Int):Boolean=if (i==0) false else true implicit def intToNibble(i:Int):Nibble=((i>>>3)&1, (i>>>2)&1, (i>>>1)&1, i&1) def nibbleToString(n:Nibble):String="%d%d%d%d".format(n._1.toInt, n._2.toInt, n._3.toInt, n._4.toInt)
}</lang> Output
A B S C 0000 + 0000 = 0000 0 0000 + 0001 = 0001 0 0000 + 0010 = 0010 0 0000 + 0011 = 0011 0 0000 + 0100 = 0100 0 ... 1111 + 1011 = 1010 1 1111 + 1100 = 1011 1 1111 + 1101 = 1100 1 1111 + 1110 = 1101 1 1111 + 1111 = 1110 1
SystemVerilog
In SystemVerilog we can define a multibit adder as a parameterized module, that instantiates the components: <lang SystemVerilog> module Half_Adder( input a, b, output s, c );
assign s = a ^ b; assign c = a & b;
endmodule
module Full_Adder( input a, b, c_in, output s, c_out );
wire s_ha1, c_ha1, c_ha2;
Half_Adder ha1( .a(c_in), .b(a), .s(s_ha1), .c(c_ha1) ); Half_Adder ha2( .a(s_ha1), .b(b), .s(s), .c(c_ha2) ); assign c_out = c_ha1 | c_ha2;
endmodule
module Multibit_Adder(a,b,s);
parameter N = 8; input [N-1:0] a; input [N-1:0] b; output [N:0] s;
wire [N:0] c;
assign c[0] = 0; assign s[N] = c[N];
generate genvar I; for (I=0; I<N; ++I) Full_Adder add( .a(a[I]), .b(b[I]), .s(s[I]), .c_in(c[I]), .c_out(c[I+1]) ); endgenerate
endmodule </lang>
And then a testbench to test it -- here I use random stimulus with an assertion (it's aften good to separate the stimulus generation from the results-checking):
<lang SystemVerilog> module simTop();
bit [3:0] a; bit [3:0] b; bit [4:0] s;
Multibit_Adder#(4) adder(.*);
always_comb begin $display( "%d + %d = %d", a, b, s ); assert( s == a+b ); end
endmodule
program Main();
class Test; rand bit [3:0] a; rand bit [3:0] b; endclass
Test t = new; initial repeat (20) begin #10 t.randomize; simTop.a = t.a; simTop.b = t.b; end
endprogram
</lang>
The output looks something like this:
0 + 0 = 0 7 + 0 = 7 11 + 3 = 14 9 + 15 = 24 7 + 3 = 10 1 + 4 = 5 9 + 7 = 16 10 + 6 = 16 15 + 9 = 24 9 + 3 = 12 2 + 3 = 5 14 + 5 = 19 1 + 8 = 9 0 + 4 = 4 13 + 9 = 22 15 + 7 = 22 3 + 15 = 18 7 + 4 = 11 13 + 4 = 17 10 + 7 = 17 1 + 2 = 3 $finish at simulation time 200
A quick note on the use of random stimulus. You might think that, with an input space of only 2**8 (256) distinct inputs, that exhaustive testing (i.e. just loop through all the possible inputs) would be appropriate. In this case you might be right. But as a HW verification engineer I'm used to dealing with coverage spaces closer to 10**80 (every state element -- bit of memory) increases the space). It's not practical to verify such hardware exhaustively -- indeed, it's hard to know where the interesting cases are -- so we use constrained random verification. If you want to, to can work thought the statistics to figure out the probability that we missed a bug when sampling 20 cases from a space of 2**8 -- it's quite scary when you realize that every complex digital chip that you ever bought (cpu, gpu, networking, etc.) was 0% verified (zero to at least 50 decimal places).
For a problem this small, however, we'd probably just whip out a "formal" tool and statically prove that the assertion can never fire for all possible sets of inputs.
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.