Module ariths_gen.multi_bit_circuits.others.popcount

Classes

class UnsignedPopCount (a: Bus,
adder: GeneralCircuit | None = None,
prefix: str = '',
name: str = 'popcnt',
**kwargs)

Class representing unsigned popcount circuit.

Popcount circuit is a circuit that counts the number of 1s in a binary number.

Expand source code 
class UnsignedPopCount(GeneralCircuit):
    """Class representing unsigned popcount circuit.

    Popcount circuit is a circuit that counts the number of 1s in a binary number.

    """

    def __init__(self, a: Bus, adder : Optional[GeneralCircuit] = None, prefix : str = "", name : str = "popcnt", **kwargs):
        self.N = a.N
        outc = ceil(log2(self.N + 1))
        #print("outc", outc)
        super().__init__(name=name, prefix=prefix, inputs=[a], out_N=outc)

        self.a.bus_extend(2**(outc - 1), prefix=a.prefix)
        #print(self.a)
        self.adder = adder
        if not self.adder:
            self.adder = UnsignedRippleCarryAdder

        # tree reduction
        def create_tree(a: Bus, depth: int, branch="A"):
            #print(a)
            if a.N == 1:
                return a
            else:
                half = a.N // 2
                b_in = Bus(N=half, prefix=f"b_inn{branch}_{depth}A")
                c_in = Bus(N=a.N - half, prefix=f"c_inn{branch}_{depth}B")
                #print(a, half, a.N)
                for i, j in enumerate(range(half)):
                    b_in.connect(i, a.get_wire(j))
                for i, j in enumerate(range(half, a.N)):
                    c_in.connect(i, a.get_wire(j))

                b = create_tree(b_in, depth=depth + 1, branch = branch + "A")
                c = create_tree(c_in, depth= depth + 1, branch = branch + "B")
                d = self.adder(a=b, b=c, 
                               prefix = f"{self.prefix}_add{branch}_{depth}", inner_component=True,
                               parent_component=self)
                self.add_component(d)
                return d.out

        sumbus = create_tree(self.a,0, "X")
        #print(sumbus)
        self.out.connect_bus(sumbus)

Ancestors

Inherited members