PopCount8

In this tutorial, we show how to construct a circuit to compute an 8-bit PopCount (population count).



In [1]:

    
import magma as m

In this example, we are going to use the built-in fulladder from Mantle.



In [2]:

    
from mantle import FullAdder

A common name for a full adder is a carry-sum adder, or csa. Let's define two csa functions to help us construct the popcount.



In [3]:

    
# 2 input 
def csa2(I0, I1):
    return m.bits(FullAdder()(I0, I1, 0))

# 3 input
def csa3(I0, I1, I2):
    return m.bits(FullAdder()(I0, I1, I2))

To construct the 8-bit popcount, we first use 3 csa's to sum bits 0 through 2, 3 through 5, and 6 through 7. This forms 3 2-bit results. We can consider the results to be two columns, one for each place. The first column is the 1s and the second column is the 2s.

We then use two fulladders to sum these columns. We continue summing 3-bits at a time until we get a single bit in each column.

A common way to show these operations is with Dadda dot notation which shows how many bits are in each colum.



In [4]:

    
def popcount8(I):
    # Dadda dot notation (of the result)
    # o o     csa0_0_21 - row 0, bits 2 and 1
    # o o     csa0_1_21 - row 1, bits 2 and 1
    # o o     csa0_2_21 - row 2, bits 2 and 1
    csa0_0_21 = csa3(I[0], I[1], I[2])
    csa0_1_21 = csa3(I[3], I[4], I[5])
    csa0_2_21 = csa2(I[6], I[7])

    #   o o   csa1_0_21 - row 0, bits 2 and 1
    # o o     csa1_1_43 - row 1, bits 4 and 2
    csa1_0_21 = csa3(csa0_0_21[0], csa0_1_21[0], csa0_2_21[0])
    csa1_1_42 = csa3(csa0_0_21[1], csa0_1_21[1], csa0_2_21[1])

    # o o     csa2_0_42 - row 0, bits 4 and 2
    csa2_0_42 = csa2(csa1_0_21[1], csa1_1_42[0])

    # o o     csa3_0_84 - row 0, bits 8 and 4 
    csa3_0_84 = csa2(csa1_1_42[1], csa2_0_42[1])
    
    return m.bits([csa1_0_21[0], csa2_0_42[0], csa3_0_84[0], csa3_0_84[1]])

Test bench

Let's test this using fault



In [5]:

    
import fault

class Main(m.Circuit):
    io = m.IO(I=m.In(m.Bits[8]), O=m.Out(m.Bits[4]))
    io.O @= popcount8(io.I)

tester = fault.PythonTester(Main)
assert tester(0xFF) == 8
assert tester(0xF0) == 4
assert tester(0xEE) == 6



In [6]:

    
m.compile('build/popcount8', Main, inline=True)
!cat build/popcount8.v









    



module fold_xor3None (
    input I0,
    input I1,
    input I2,
    output O
);
assign O = (I0 ^ I1) ^ I2;
endmodule

module Or3xNone (
    input I0,
    input I1,
    input I2,
    output O
);
assign O = | ({I2,I1,I0});
endmodule

module FullAdder (
    input I0,
    input I1,
    input CIN,
    output O,
    output COUT
);
Or3xNone Or3xNone_inst0 (
    .I0(I0 & I1),
    .I1(I1 & CIN),
    .I2(I0 & CIN),
    .O(COUT)
);
fold_xor3None fold_xor3None_inst0 (
    .I0(I0),
    .I1(I1),
    .I2(CIN),
    .O(O)
);
endmodule

module Main (
    input [7:0] I,
    output [3:0] O
);
wire FullAdder_inst0_O;
wire FullAdder_inst0_COUT;
wire FullAdder_inst1_O;
wire FullAdder_inst1_COUT;
wire FullAdder_inst2_O;
wire FullAdder_inst2_COUT;
wire FullAdder_inst3_O;
wire FullAdder_inst3_COUT;
wire FullAdder_inst4_O;
wire FullAdder_inst4_COUT;
wire FullAdder_inst5_O;
wire FullAdder_inst5_COUT;
wire FullAdder_inst6_O;
wire FullAdder_inst6_COUT;
FullAdder FullAdder_inst0 (
    .I0(I[0]),
    .I1(I[1]),
    .CIN(I[2]),
    .O(FullAdder_inst0_O),
    .COUT(FullAdder_inst0_COUT)
);
FullAdder FullAdder_inst1 (
    .I0(I[3]),
    .I1(I[4]),
    .CIN(I[5]),
    .O(FullAdder_inst1_O),
    .COUT(FullAdder_inst1_COUT)
);
FullAdder FullAdder_inst2 (
    .I0(I[6]),
    .I1(I[7]),
    .CIN(1'b0),
    .O(FullAdder_inst2_O),
    .COUT(FullAdder_inst2_COUT)
);
FullAdder FullAdder_inst3 (
    .I0(FullAdder_inst0_O),
    .I1(FullAdder_inst1_O),
    .CIN(FullAdder_inst2_O),
    .O(FullAdder_inst3_O),
    .COUT(FullAdder_inst3_COUT)
);
FullAdder FullAdder_inst4 (
    .I0(FullAdder_inst0_COUT),
    .I1(FullAdder_inst1_COUT),
    .CIN(FullAdder_inst2_COUT),
    .O(FullAdder_inst4_O),
    .COUT(FullAdder_inst4_COUT)
);
FullAdder FullAdder_inst5 (
    .I0(FullAdder_inst3_COUT),
    .I1(FullAdder_inst4_O),
    .CIN(1'b0),
    .O(FullAdder_inst5_O),
    .COUT(FullAdder_inst5_COUT)
);
FullAdder FullAdder_inst6 (
    .I0(FullAdder_inst4_COUT),
    .I1(FullAdder_inst5_COUT),
    .CIN(1'b0),
    .O(FullAdder_inst6_O),
    .COUT(FullAdder_inst6_COUT)
);
assign O = {FullAdder_inst6_COUT,FullAdder_inst6_O,FullAdder_inst5_O,FullAdder_inst3_O};
endmodule

There is a more general version of PopCount in the Mantle library util.compressor.



In [ ]: