Module `ariths_gen.multi_bit_circuits.multipliers.dadda_multiplier`

Classes

class SignedDaddaMultiplier (a: Bus, b: Bus, prefix: str = '', name: str = 's_dadda_cla', unsigned_adder_class_name: str = ariths_gen.multi_bit_circuits.adders.carry_lookahead_adder.UnsignedCarryLookaheadAdder, **kwargs)

Class representing signed dadda multiplier.

Signed dadda multiplier represents fast N-bit multiplier which utilizes the functionality of reduction algorithm proposed by Luigi Dadda and uses Baugh-Wooley algorithm to perform signed multiplication.

First partial products are calculated for each bit pair that form the partial product multiplication columns. At last the reduced pairs are inserted into chosen multi bit unsigned adder to execute their summation and obtain the final output bits, additional XOR gate serve the necessary sign extension.

Dadda algorithm is described more in detail here: https://en.wikipedia.org/wiki/Dadda_multiplier

It is composed of much less inner components (half/full adders, AND/NAND gates) as opposed to e.g. wallace and array multipliers.

Description of the init method.

Args

a : Bus: First input bus.
b : Bus: Second input bus.
prefix : str, optional: Prefix name of signed dadda multiplier. Defaults to "".
name : str, optional: Name of signed dadda multiplier. Defaults to "s_dadda_cla".
unsigned_adder_class_name : str, optional: Unsigned multi bit adder used to obtain final sums of products. Defaults to UnsignedCarryLookaheadAdder.

Expand source code

class SignedDaddaMultiplier(MultiplierCircuit):
    """Class representing signed dadda multiplier.

    Signed dadda multiplier represents fast N-bit multiplier which utilizes
    the functionality of reduction algorithm proposed by Luigi Dadda and uses Baugh-Wooley algorithm
    to perform signed multiplication.

    First partial products are calculated for each bit pair that form the partial product multiplication columns.
    At last the reduced pairs are inserted into chosen multi bit unsigned adder to execute their summation and obtain the final output bits,
    additional XOR gate serve the necessary sign extension.

    Dadda algorithm is described more in detail here:
    https://en.wikipedia.org/wiki/Dadda_multiplier

    It is composed of much less inner components (half/full adders, AND/NAND gates) as opposed
    to e.g. wallace and array multipliers.

    Description of the __init__ method.

    Args:
        a (Bus): First input bus.
        b (Bus): Second input bus.
        prefix (str, optional): Prefix name of signed dadda multiplier. Defaults to "".
        name (str, optional): Name of signed dadda multiplier. Defaults to "s_dadda_cla".
        unsigned_adder_class_name (str, optional): Unsigned multi bit adder used to obtain final sums of products. Defaults to UnsignedCarryLookaheadAdder.
    """
    def __init__(self, a: Bus, b: Bus, prefix: str = "", name: str = "s_dadda_cla", unsigned_adder_class_name: str = UnsignedCarryLookaheadAdder, **kwargs):
        self.N = max(a.N, b.N)
        super().__init__(inputs=[a, b], prefix=prefix, name=name, out_N=self.N*2, signed=True, **kwargs)

        # Bus sign extension in case buses have different lengths
        self.a.bus_extend(N=self.N, prefix=a.prefix)
        self.b.bus_extend(N=self.N, prefix=b.prefix)

        # Get starting stage and maximum possible column height
        self.stage, self.d = self.get_maximum_height(initial_value=min(self.a.N, self.b.N))
        # Initialize all columns partial products forming AND/NAND gates matrix based on Baugh-Wooley multiplication
        self.columns = self.init_column_heights()

        # Not used for 1 bit multiplier
        if self.N != 1:
            # Adding constant wire with value 1 to achieve signedness based on Baugh-Wooley multiplication algorithm
            # (adding constant value bit to last column (with one bit) to combine them in XOR gate to get the correct final multplication output bit at the end)
            self.columns[self.N].insert(1, ConstantWireValue1())
            self.update_column_heights(curr_column=self.N, curr_height_change=1)

        # Perform reduction until stage 0
        for stage in range(self.stage, 0, -1):
            col = 0
            while col < len(self.columns):
                if self.get_column_height(col) == self.d + 1:
                    # Add half adder and also AND/NAND gates if neccesarry (via add_column_wire invocation) into list of circuit components
                    obj_adder = HalfAdder(self.add_column_wire(column=col, bit=0), self.add_column_wire(column=col, bit=1), prefix=self.prefix+"_ha"+str(self.get_instance_num(cls=HalfAdder)))
                    self.add_component(obj_adder)

                    # Update the number of current and next column wires
                    self.update_column_heights(curr_column=col, curr_height_change=-1, next_column=col+1, next_height_change=1)

                    # Update current and next column wires arrangement
                    #   add ha's generated sum to the bottom of current column
                    #   add ha's generated cout to the top of next column
                    self.update_column_wires(curr_column=col, next_column=col+1, adder=self.get_previous_component(1))
                elif self.get_column_height(col) > self.d:
                    # Add full adder and also AND/NAND gates if neccesarry (via add_column_wire invocation) into list of circuit components
                    obj_adder = FullAdder(self.add_column_wire(column=col, bit=0), self.add_column_wire(column=col, bit=1), self.add_column_wire(column=col, bit=2), prefix=self.prefix+"_fa"+str(self.get_instance_num(cls=FullAdder)))
                    self.add_component(obj_adder)

                    # Update the number of current and next column wires
                    self.update_column_heights(curr_column=col, curr_height_change=-2, next_column=col+1, next_height_change=1)

                    # Update current and next column wires arrangement
                    #   add fa's generated sum to the bottom of current column
                    #   add fa's generated cout to the top of next column
                    self.update_column_wires(curr_column=col, next_column=col+1, adder=self.get_previous_component(1))
                    # Next iteration with same column in case there is need for further reduction
                    col -= 1
                col += 1
            # Update maximum possible column height
            _, self.d = self.get_maximum_height(stage)

        # Output generation
        # First output bit from single first pp AND gate
        self.out.connect(0, self.add_column_wire(column=0, bit=0))
        # Final addition of remaining bits
        # 1 bit multiplier case (no sign extension)
        if self.N == 1:
            self.out.connect(1, ConstantWireValue0())
            return
        # 2 bit multiplier case
        elif self.N == 2:
            obj_ha = HalfAdder(self.add_column_wire(column=1, bit=0), self.add_column_wire(column=1, bit=1), prefix=self.prefix+"_ha"+str(self.get_instance_num(cls=HalfAdder)))
            self.add_component(obj_ha)
            self.out.connect(1, obj_ha.get_sum_wire())

            obj_fa = FullAdder(self.get_previous_component().get_carry_wire(), self.add_column_wire(column=2, bit=0), self.add_column_wire(column=2, bit=1), prefix=self.prefix+"_fa"+str(self.get_instance_num(cls=FullAdder)))
            self.add_component(obj_fa)
            self.out.connect(2, obj_fa.get_sum_wire())
            self.out.connect(3, obj_fa.get_carry_wire())

        # Final addition of remaining bits using chosen unsigned multi bit adder
        else:
            # Obtain proper adder name with its bit width (columns bit pairs minus the first alone bit)
            adder_name = unsigned_adder_class_name(a=a, b=b).prefix + str(len(self.columns)-1)
            adder_a = Bus(prefix=f"a", wires_list=[self.add_column_wire(column=col, bit=0) for col in range(1, len(self.columns))])
            adder_b = Bus(prefix=f"b", wires_list=[self.add_column_wire(column=col, bit=1) for col in range(1, len(self.columns))])
            final_adder = unsigned_adder_class_name(a=adder_a, b=adder_b, prefix=self.prefix, name=adder_name, inner_component=True, **kwargs)
            self.add_component(final_adder)

            [self.out.connect(o, final_adder.out.get_wire(o-1), inserted_wire_desired_index=o-1) for o in range(1, len(self.out.bus))]

        # Final XOR to ensure proper sign extension
        obj_xor = XorGate(ConstantWireValue1(), self.out.get_wire(self.out.N-1), prefix=self.prefix+"_xor"+str(self.get_instance_num(cls=XorGate)), parent_component=self)
        self.add_component(obj_xor)
        self.out.connect(self.out.N-1, obj_xor.out)

Ancestors

Inherited members

MultiplierCircuit:
- add_column_wire
- add_column_wires
- add_component
- add_row_wires
- get_blif_code_flat
- get_blif_code_hier
- get_c_code_flat
- get_c_code_hier
- get_cgp_code_flat
- get_circuit_blif
- get_circuit_c
- get_circuit_def
- get_circuit_gates
- get_circuit_v
- get_circuit_wire_index
- get_circuit_wires
- get_column_height
- get_column_wire
- get_component_types
- get_declaration_blif
- get_declaration_c_flat
- get_declaration_c_hier
- get_declaration_v_flat
- get_declaration_v_hier
- get_declarations_c_hier
- get_declarations_v_hier
- get_function_blif_flat
- get_function_block_blif
- get_function_block_c
- get_function_block_v
- get_function_blocks_blif
- get_function_blocks_c
- get_function_blocks_v
- get_function_out_blif
- get_function_out_c_flat
- get_function_out_c_hier
- get_function_out_python_flat
- get_function_out_v_flat
- get_function_out_v_hier
- get_hier_subcomponent_def
- get_includes_c
- get_init_c_flat
- get_init_c_hier
- get_init_python_flat
- get_init_v_flat
- get_init_v_hier
- get_instance_num
- get_invocation_blif_hier
- get_invocations_blif_hier
- get_maximum_height
- get_multi_bit_components
- get_one_bit_components
- get_out_invocation_c
- get_out_invocation_v
- get_outputs_cgp
- get_parameters_cgp
- get_previous_component
- get_previous_partial_product
- get_prototype_blif
- get_prototype_c
- get_prototype_python
- get_prototype_v
- get_python_code_flat
- get_triplets_cgp
- get_unique_types
- get_v_code_flat
- get_v_code_hier
- init_column_heights
- init_row_lengths
- save_wire_id
- update_column_heights
- update_column_wires

class UnsignedDaddaMultiplier (a: Bus, b: Bus, prefix: str = '', name: str = 'u_dadda_cla', unsigned_adder_class_name: str = ariths_gen.multi_bit_circuits.adders.carry_lookahead_adder.UnsignedCarryLookaheadAdder, **kwargs)

Class representing unsigned dadda multiplier.

Unsigned dadda multiplier represents fast N-bit multiplier which utilizes the functionality of reduction algorithm proposed by Luigi Dadda.