Module `ariths_gen.multi_bit_circuits.adders.kogge_stone_adder`

Classes

class SignedKoggeStoneAdder (a: Bus, b: Bus, prefix: str = '', name: str = 's_ksa', **kwargs)

Class representing signed Kogge-Stone adder (using valency-2 logic gates).

The Kogge-Stone adder belongs to a type of tree (parallel-prefix) adders. Tree adder structure consists of three parts of logic: 1) PG logic generation, 2) Parallel PG logic computation, 3) Final sum and cout computation The main difference between each tree adder lies in the implementation of the part 2).

Along with Brent-Kung and Sklansky it is considered to be a fundamental tree adder architecture.

Kogge-Stone achieves log(N,2) stages and fanout of 2 at each stage inside 2). The circuit contains more PG cells than the other tree adder architectures.

Main building components are GreyCells and BlackCells that appropriately encapsulate the essential logic used for PG computation. For further circuit characteristics see the book CMOS VLSI Design.

The implementation performs the 1) and 3) (sum XORs) parts using one bit three input P/G/Sum logic function blocks. The 2) part is then composed according to the parallel-prefix adder characteristics. At last XOR gates are used to ensure proper sign extension.

  B3 A3         B2 A2       B1 A1       B0 A0
  │  │          │  │        │  │        │  │
┌─▼──▼─┐      ┌─▼──▼─┐    ┌─▼──▼─┐    ┌─▼──▼─┐
│  PG  │  C3  │  PG  │ C2 │  PG  │ C1 │  PG  │
│  SUM │◄────┐│  SUM │◄──┐│  SUM │◄──┐│  SUM │◄──0
│      │     ││      │   ││      │   ││      │
└─┬──┬┬┘     │└─┬┬┬──┘   │└─┬┬┬──┘   │└─┬┬┬──┘
  │  ││G3P3S3│  │││G2P2S2│  │││G1P1S1│  │││G0P0S0
  │ ┌▼▼──────┴──▼▼▼──────┴──▼▼▼──────┴──▼▼▼──┐
  │ │            Parallel-prefix             │
  │ │               PG logic                 │
  │ └─┬───────┬──────────┬──────────┬────────┘
  │   │S3     │S2        │S1        │S0
┌─▼───▼───────▼──────────▼──────────▼────────┐
│                Sum + Cout                  │
│           with sign extension              │
└┬────┬───────┬──────────┬──────────┬────────┘
 │    │       │          │          │
 ▼    ▼       ▼          ▼          ▼
Cout  S3      S1         S0         S0

Description of the init method.

Args

a : Bus: First input bus.
b : Bus: Second input bus.
prefix : str, optional: Prefix name of signed ksa. Defaults to "".
name : str, optional: Name of signed ksa. Defaults to "s_ksa".

Expand source code

class SignedKoggeStoneAdder(UnsignedKoggeStoneAdder, GeneralCircuit):
    """Class representing signed Kogge-Stone adder (using valency-2 logic gates).

    The Kogge-Stone adder belongs to a type of tree (parallel-prefix) adders.
    Tree adder structure consists of three parts of logic: 1) PG logic generation, 2) Parallel PG logic computation, 3) Final sum and cout computation
    The main difference between each tree adder lies in the implementation of the part 2).

    Along with Brent-Kung and Sklansky it is considered to be a fundamental tree adder architecture.

    Kogge-Stone achieves log(N,2) stages and fanout of 2 at each stage inside 2). The circuit contains more PG cells
    than the other tree adder architectures.

    Main building components are GreyCells and BlackCells that appropriately encapsulate the essential logic used for PG computation.
    For further circuit characteristics see the book CMOS VLSI Design.

    The implementation performs the 1) and 3) (sum XORs) parts using one bit three input P/G/Sum logic function blocks.
    The 2) part is then composed according to the parallel-prefix adder characteristics.
    At last XOR gates are used to ensure proper sign extension.

    ```
      B3 A3         B2 A2       B1 A1       B0 A0
      │  │          │  │        │  │        │  │
    ┌─▼──▼─┐      ┌─▼──▼─┐    ┌─▼──▼─┐    ┌─▼──▼─┐
    │  PG  │  C3  │  PG  │ C2 │  PG  │ C1 │  PG  │
    │  SUM │◄────┐│  SUM │◄──┐│  SUM │◄──┐│  SUM │◄──0
    │      │     ││      │   ││      │   ││      │
    └─┬──┬┬┘     │└─┬┬┬──┘   │└─┬┬┬──┘   │└─┬┬┬──┘
      │  ││G3P3S3│  │││G2P2S2│  │││G1P1S1│  │││G0P0S0
      │ ┌▼▼──────┴──▼▼▼──────┴──▼▼▼──────┴──▼▼▼──┐
      │ │            Parallel-prefix             │
      │ │               PG logic                 │
      │ └─┬───────┬──────────┬──────────┬────────┘
      │   │S3     │S2        │S1        │S0
    ┌─▼───▼───────▼──────────▼──────────▼────────┐
    │                Sum + Cout                  │
    │           with sign extension              │
    └┬────┬───────┬──────────┬──────────┬────────┘
     │    │       │          │          │
     ▼    ▼       ▼          ▼          ▼
    Cout  S3      S1         S0         S0
    ```

    Description of the __init__ method.

    Args:
        a (Bus): First input bus.
        b (Bus): Second input bus.
        prefix (str, optional): Prefix name of signed ksa. Defaults to "".
        name (str, optional): Name of signed ksa. Defaults to "s_ksa".
    """
    def __init__(self, a: Bus, b: Bus, prefix: str = "", name: str = "s_ksa", **kwargs):
        super().__init__(a=a, b=b, prefix=prefix, name=name, signed=True, **kwargs)

        # Additional XOR gates to ensure correct sign extension in case of sign addition
        self.add_component(XorGate(self.a.get_wire(self.N-1), self.b.get_wire(self.N-1), prefix=self.prefix+"_xor"+str(self.get_instance_num(cls=XorGate)), parent_component=self))
        self.add_component(XorGate(self.get_previous_component().out, self.get_previous_component(2).get_generate_wire(), prefix=self.prefix+"_xor"+str(self.get_instance_num(cls=XorGate)), parent_component=self))
        self.out.connect(self.N, self.get_previous_component().out)

Ancestors

UnsignedKoggeStoneAdder
GeneralCircuit

Inherited members

UnsignedKoggeStoneAdder:
- add_component
- 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_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_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_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
- save_wire_id

class UnsignedKoggeStoneAdder (a: Bus, b: Bus, prefix: str = '', name: str = 'u_ksa', **kwargs)

Class representing unsigned Kogge-Stone adder (using valency-2 logic gates).

Along with Brent-Kung and Sklansky it is considered to be a fundamental tree adder architecture.

Kogge-Stone achieves log2(N) stages and fanout of 2 at each stage inside 2). The circuit contains more PG cells than the other tree adder architectures.

Main building components are GreyCells and BlackCells that appropriately encapsulate the essential logic used for PG computation. For further circuit characteristics see the book CMOS VLSI Design.

  B3 A3         B2 A2       B1 A1       B0 A0
  │  │          │  │        │  │        │  │
┌─▼──▼─┐      ┌─▼──▼─┐    ┌─▼──▼─┐    ┌─▼──▼─┐
│  PG  │  C3  │  PG  │ C2 │  PG  │ C1 │  PG  │
│  SUM │◄────┐│  SUM │◄──┐│  SUM │◄──┐│  SUM │◄──0
│      │     ││      │   ││      │   ││      │
└─┬──┬┬┘     │└─┬┬┬──┘   │└─┬┬┬──┘   │└─┬┬┬──┘
  │  ││G3P3S3│  │││G2P2S2│  │││G1P1S1│  │││G0P0S0
  │ ┌▼▼──────┴──▼▼▼──────┴──▼▼▼──────┴──▼▼▼──┐
  │ │            Parallel-prefix             │
  │ │               PG logic                 │
  │ └─┬───────┬──────────┬──────────┬────────┘
  │   │S3     │S2        │S1        │S0
┌─▼───▼───────▼──────────▼──────────▼────────┐
│                Sum + Cout                  │
│                   logic                    │
└┬────┬───────┬──────────┬──────────┬────────┘
 │    │       │          │          │
 ▼    ▼       ▼          ▼          ▼
Cout  S3      S1         S0         S0

Description of the init method.

Args

a : Bus: First input bus.
b : Bus: Second input bus.
prefix : str, optional: Prefix name of unsigned ksa. Defaults to "".
name : str, optional: Name of unsigned ksa. Defaults to "u_ksa".

Expand source code

class UnsignedKoggeStoneAdder(GeneralCircuit):
    """Class representing unsigned Kogge-Stone adder (using valency-2 logic gates).

    The Kogge-Stone adder belongs to a type of tree (parallel-prefix) adders.
    Tree adder structure consists of three parts of logic: 1) PG logic generation, 2) Parallel PG logic computation, 3) Final sum and cout computation
    The main difference between each tree adder lies in the implementation of the part 2).

    Along with Brent-Kung and Sklansky it is considered to be a fundamental tree adder architecture.

    Kogge-Stone achieves log2(N) stages and fanout of 2 at each stage inside 2). The circuit contains more PG cells
    than the other tree adder architectures.

    Main building components are GreyCells and BlackCells that appropriately encapsulate the essential logic used for PG computation.
    For further circuit characteristics see the book CMOS VLSI Design.

    The implementation performs the 1) and 3) (sum XORs) parts using one bit three input P/G/Sum logic function blocks.
    The 2) part is then composed according to the parallel-prefix adder characteristics.

    ```
      B3 A3         B2 A2       B1 A1       B0 A0
      │  │          │  │        │  │        │  │
    ┌─▼──▼─┐      ┌─▼──▼─┐    ┌─▼──▼─┐    ┌─▼──▼─┐
    │  PG  │  C3  │  PG  │ C2 │  PG  │ C1 │  PG  │
    │  SUM │◄────┐│  SUM │◄──┐│  SUM │◄──┐│  SUM │◄──0
    │      │     ││      │   ││      │   ││      │
    └─┬──┬┬┘     │└─┬┬┬──┘   │└─┬┬┬──┘   │└─┬┬┬──┘
      │  ││G3P3S3│  │││G2P2S2│  │││G1P1S1│  │││G0P0S0
      │ ┌▼▼──────┴──▼▼▼──────┴──▼▼▼──────┴──▼▼▼──┐
      │ │            Parallel-prefix             │
      │ │               PG logic                 │
      │ └─┬───────┬──────────┬──────────┬────────┘
      │   │S3     │S2        │S1        │S0
    ┌─▼───▼───────▼──────────▼──────────▼────────┐
    │                Sum + Cout                  │
    │                   logic                    │
    └┬────┬───────┬──────────┬──────────┬────────┘
     │    │       │          │          │
     ▼    ▼       ▼          ▼          ▼
    Cout  S3      S1         S0         S0
    ```

    Description of the __init__ method.

    Args:
        a (Bus): First input bus.
        b (Bus): Second input bus.
        prefix (str, optional): Prefix name of unsigned ksa. Defaults to "".
        name (str, optional): Name of unsigned ksa. Defaults to "u_ksa".
    """
    def __init__(self, a: Bus, b: Bus, prefix: str = "", name: str = "u_ksa", **kwargs):
        self.N = max(a.N, b.N)
        super().__init__(inputs=[a, b], prefix=prefix, name=name, out_N=self.N+1, **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)
        cin = ConstantWireValue0()

        # Lists of list containing all propagate/generate wires
        self.propagate_sig = []
        self.generate_sig = []
        # Cin0 used as a first generate wire for obtaining next carry bits
        self.generate_sig.append([cin])

        # For each bit pair proceed with three stages of PPAs (Generate PG signals, Prefix computation (PG logic), Computation and connection of outputs)
        # NOTE In the implementation below, both the first and third stages are handled by the PG FAs
        for i_wire in range(self.N):
            # 1st + 3rd stage: Generate PG signals + Computation and connection of outputs
            self.add_component(PGSumLogic(self.a.get_wire(i_wire), self.b.get_wire(i_wire), self.generate_sig[i_wire][-1], prefix=self.prefix+"_pg_sum"+str(self.get_instance_num(cls=PGSumLogic))))
            self.generate_sig.append([self.get_previous_component().get_generate_wire()])
            self.propagate_sig.append([self.get_previous_component().get_propagate_wire()])

            self.out.connect(i_wire, self.get_previous_component().get_sum_wire())
            if i_wire == self.N-1:
                self.add_component(GreyCell(self.generate_sig[i_wire+1][-1], self.propagate_sig[i_wire][0], self.generate_sig[i_wire][-1], prefix=self.prefix+"_gc"+str(self.get_instance_num(cls=GreyCell))))
                self.out.connect(self.N, self.get_previous_component().get_generate_wire())
            # 2nd stage: Prefix Computation (PG logic)
            # For all bit indexes expect for the last one, proceed with the parralel prefix PG logic
            else:
                index_stages = math.ceil(math.log(i_wire+2, 2))  # +1 because indexes start from 0 and additional +1 because the first generated carry is actually the second carry after cin (the previous cin has 0 stages)
                for stage in range(index_stages):
                    # Grey cell
                    if stage == index_stages-1:
                        if stage == 0:  # Bit index with only one stage
                            self.add_component(GreyCell(self.generate_sig[i_wire+1][0], self.propagate_sig[i_wire][0], self.generate_sig[i_wire][0], prefix=self.prefix+"_gc"+str(self.get_instance_num(cls=GreyCell))))
                        else:  # Bit index contains multiple stages, GC is its last stage
                            self.add_component(GreyCell(self.get_previous_component().get_generate_wire(), self.get_previous_component().get_propagate_wire(), self.generate_sig[(i_wire+1)-(2**stage)][-1], prefix=self.prefix+"_gc"+str(self.get_instance_num(cls=GreyCell))))
                    # Black cell
                    else:  # If bit index contains more than one stage, every stage except for the last one contains a Black cells
                        self.add_component(BlackCell(self.generate_sig[i_wire+1][-1], self.propagate_sig[i_wire][-1], self.generate_sig[(i_wire+1)-(2**stage)][stage], self.propagate_sig[i_wire-(2**stage)][stage], prefix=self.prefix+"_bc"+str(self.get_instance_num(cls=BlackCell))))
                        self.propagate_sig[i_wire].append(self.get_previous_component().get_propagate_wire())
                    self.generate_sig[i_wire+1].append(self.get_previous_component().get_generate_wire())

Classes

Args

Ancestors

Inherited members

Args

Ancestors

Subclasses

Inherited members