Four bit adder: Difference between revisions

From Rosetta Code
Content added Content deleted
Line 1,482: Line 1,482:


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


=={{header|Tcl}}==
=={{header|Tcl}}==

Revision as of 17:57, 2 September 2010

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

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

Not, or and and, the only allowed "gates" for the task, can be "imitated" by using the bitwise operators of your language. If there is not a bit type in your language, to be sure that the not does not "invert" all the other bits of the basic type (e.g. a byte) we are not interested in, you can use an extra nand (and then not) with the constant 1 on one input.

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

Schematics of the "constructive blocks"
Xor gate done with ands, ors and nots A half adder A full adder A 4-bit adder
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;

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

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

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

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

  task requirements constrain */
  1. define XOR(X,Y) ((NOT(X)&(Y)) | ((X)&NOT(Y)))

void halfadder(IN a, IN b, OUT s, OUT c) { 

 V(s) = XOR(V(a), V(b));
 V(c) = V(a) & V(b);

}

void fulladder(IN a, IN b, IN ic, OUT s, OUT oc) { 

 PIN(ps); PIN(pc); PIN(tc);

 halfadder(/*INPUT*/a, b, /*OUTPUT*/ps, pc);
 halfadder(/*INPUT*/ps, ic, /*OUTPUT*/s, tc);
 V(oc) = V(tc) | V(pc);

}

void fourbitsadder(IN a0, IN a1, IN a2, IN a3, IN b0, IN b1, IN b2, IN b3, OUT o0, OUT o1, OUT o2, OUT o3, OUT overflow) { 

 PIN(zero); V(zero) = 0;
 PIN(tc0); PIN(tc1); PIN(tc2);

 fulladder(/*INPUT*/a0, b0, zero, /*OUTPUT*/o0, tc0);
 fulladder(/*INPUT*/a1, b1, tc0,  /*OUTPUT*/o1, tc1);
 fulladder(/*INPUT*/a2, b2, tc1,  /*OUTPUT*/o2, tc2);
 fulladder(/*INPUT*/a3, b3, tc2,  /*OUTPUT*/o3, overflow);

}


int main() { 

 PIN(a0); PIN(a1); PIN(a2); PIN(a3);
 PIN(b0); PIN(b1); PIN(b2); PIN(b3);
 PIN(s0); PIN(s1); PIN(s2); PIN(s3);
 PIN(overflow);

 V(a3) = 0; V(b3) = 1;
 V(a2) = 0; V(b2) = 1;
 V(a1) = 1; V(b1) = 1;
 V(a0) = 0; V(b0) = 0;

 fourbitsadder(a0, a1, a2, a3, /* INPUT */

b0, b1, b2, b3, s0, s1, s2, s3, /* OUTPUT */ overflow); 

 printf("%d%d%d%d + %d%d%d%d = %d%d%d%d, overflow = %d\n",

V(a3), V(a2), V(a1), V(a0), V(b3), V(b2), V(b1), V(b0), V(s3), V(s2), V(s1), V(s0), V(overflow)); 

 return 0;

}</lang>

C#

Works with: C# version 3+

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

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;

/// A XOR using only NOT, AND and OR, as task requires T xor(T)(in T x, in T y) { return (~x & y) | (x & ~y); }

void halfAdder(T)(in T a, in T b, out T s, out T c) { 

   s = xor(a, b);
   c = a & b;

}

void fullAdder(T)(T a, T b, 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;

}

void fourBitsAdder(T)(T a0, T a1, T a2, T a3, 

                     T b0, T b1, T b2, T b3,
                     out T o0, out T o1, out T o2, out T o3,
                     out T overflow) {
   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;
   enum T zero = T.min;
   T a3 = zero; T b3 = one;
   T a2 = zero; T b2 = one;
   T a1 = one; T b1 = one;
   T a0 = zero; T b0 = zero;
   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

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.

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

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

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>

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>

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>

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

  1. Create our little language

proc pins args { 

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

} proc gate {name pins body} { 

   foreach p $pins {

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

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

}

  1. Fundamental gates; 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

}

  1. Composite gates: XOR

gate xor {x y out} { 

   pins nx ny x_ny nx_y

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

}

  1. Composite gates: half adder

gate halfadd {a b sum carry} { 

   xor a b  sum
   and a b  carry

}

  1. Composite gates: full adder

gate fulladd {a b c0 sum c1} { 

   pins sum_ac carry_ac carry_sb

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

}

  1. Composite gates: 4-bit adder

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

   pins c0 c1 c2 c3

   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.

Retrieved from "https://rosettacode.org/wiki/Four_bit_adder?oldid=149798"