configurable_conditional_sum_adder.v

/* verilator lint_off DECLFILENAME */
/* verilator lint_off UNOPTFLAT */
/* verilator lint_off EOFNEWLINE */
/* verilator lint_off GENUNNAMED */

/**
 * Configurable Conditional-Sum Adder
 * 
 * This module implements a conditional-sum adder, which is similar to a carry-select
 * adder but uses a hierarchical approach. It precomputes sums for both possible
 * carry-in values (0 and 1) at each level, then conditionally selects the correct
 * result based on the actual carry-in.
 * 
 * Algorithm Overview:
 * The adder divides the operands into blocks. For each block, it precomputes two
 * results: one assuming carry-in = 0, and another assuming carry-in = 1. When the
 * actual carry from the previous block arrives, the correct result is selected.
 * This eliminates carry propagation delay between blocks.
 * 
 * Key Features:
 * - Configurable data width via DATA_WIDTH parameter
 * - Configurable block size via BLOCK_SIZE parameter
 * - O(n/k) delay where k is the block size (faster than ripple-carry)
 * - Similar to carry-select but with a different internal structure
 * 
 * Design Trade-offs:
 * - Larger BLOCK_SIZE: Faster but significantly more area (each block needs 2 adders)
 * - Smaller BLOCK_SIZE: Less area but slower (more blocks to chain)
 * - Typical BLOCK_SIZE: 4-8 bits
 * 
 * How It Works:
 * 1. Divide operands into blocks of BLOCK_SIZE bits
 * 2. For each block, compute two results in parallel:
 *    - Result assuming carry-in = 0
 *    - Result assuming carry-in = 1
 * 3. When carry from previous block arrives, select correct result
 * 4. Chain blocks together using selected carry-outs
 * 
 * @param DATA_WIDTH Width of input operands and output sum (default: 32 bits)
 * @param BLOCK_SIZE Number of bits per conditional-sum block (default: 4 bits)
 *                   Typical values: 4, 8, or 16.
 * 
 * @input a[DATA_WIDTH-1:0] First operand to be added
 * @input b[DATA_WIDTH-1:0] Second operand to be added
 * @input cin Carry-in bit (allows chaining multiple adders)
 * @output sum[DATA_WIDTH-1:0] Sum of a + b + cin
 * @output cout Carry-out bit (indicates overflow when DATA_WIDTH bits are insufficient)
 */
module configurable_conditional_sum_adder #(
    parameter DATA_WIDTH = 32,    // Width of the operands
    parameter BLOCK_SIZE = 4      // Size of each initial block
) (
    input wire [DATA_WIDTH-1:0] a,    // First operand
    input wire [DATA_WIDTH-1:0] b,    // Second operand
    input wire cin,                   // Carry-in
    output wire [DATA_WIDTH-1:0] sum, // Sum output
    output wire cout                  // Carry-out
);

    // Initial block ripple-carry adders
    genvar i, j;
    
    // Round up the number of blocks
    localparam NUM_BLOCKS = (DATA_WIDTH + BLOCK_SIZE - 1) / BLOCK_SIZE;
    
    // Pre-compute sums and carries for each block for both carry-in 0 and 1
    wire [NUM_BLOCKS-1:0][BLOCK_SIZE-1:0] sum_cin_0;  // Sum when carry-in = 0
    wire [NUM_BLOCKS-1:0][BLOCK_SIZE-1:0] sum_cin_1;  // Sum when carry-in = 1
    wire [NUM_BLOCKS-1:0] cout_cin_0;                 // Carry-out when carry-in = 0
    wire [NUM_BLOCKS-1:0] cout_cin_1;                 // Carry-out when carry-in = 1
    
    // Intermediate carries
    wire [NUM_BLOCKS:0] carry;
    assign carry[0] = cin;
    assign cout = carry[NUM_BLOCKS];
    
    // Generate the ripple-carry adders for each block
    generate
        for (i = 0; i < NUM_BLOCKS; i = i + 1) begin : blocks
            // Calculate the width of this block (handle the case where the last block might be smaller)
            localparam CURRENT_BLOCK_SIZE = ((i+1)*BLOCK_SIZE <= DATA_WIDTH) ? 
                                            BLOCK_SIZE : 
                                            DATA_WIDTH - (i*BLOCK_SIZE);
            
            // Calculate start and end indices for this block
            localparam START_IDX = i * BLOCK_SIZE;
            localparam END_IDX = START_IDX + CURRENT_BLOCK_SIZE - 1;
            
            // Block inputs
            wire [CURRENT_BLOCK_SIZE-1:0] block_a = a[END_IDX:START_IDX];
            wire [CURRENT_BLOCK_SIZE-1:0] block_b = b[END_IDX:START_IDX];
            
            // Compute sum and carry for carry-in = 0
            wire [CURRENT_BLOCK_SIZE-1:0] block_sum_cin_0;
            wire block_cout_cin_0;
            
            cond_sum_rca #(
                .WIDTH(CURRENT_BLOCK_SIZE)
            ) rca_cin_0 (
                .a(block_a),
                .b(block_b),
                .cin(1'b0),
                .sum(block_sum_cin_0),
                .cout(block_cout_cin_0)
            );
            
            // Compute sum and carry for carry-in = 1
            wire [CURRENT_BLOCK_SIZE-1:0] block_sum_cin_1;
            wire block_cout_cin_1;
            
            cond_sum_rca #(
                .WIDTH(CURRENT_BLOCK_SIZE)
            ) rca_cin_1 (
                .a(block_a),
                .b(block_b),
                .cin(1'b1),
                .sum(block_sum_cin_1),
                .cout(block_cout_cin_1)
            );
            
            // Store the results
            if (CURRENT_BLOCK_SIZE == BLOCK_SIZE) begin : full_block
                // This is a full block
                assign sum_cin_0[i] = block_sum_cin_0;
                assign sum_cin_1[i] = block_sum_cin_1;
            end
            else begin : partial_block
                // This is a partial block (last block)
                // We still need to assign all bits for consistency
                for (j = 0; j < BLOCK_SIZE; j = j + 1) begin : pad_bits
                    if (j < CURRENT_BLOCK_SIZE) begin : valid_bit
                        assign sum_cin_0[i][j] = block_sum_cin_0[j];
                        assign sum_cin_1[i][j] = block_sum_cin_1[j];
                    end
                    else begin : padding_bit
                        // Pad with zeros
                        assign sum_cin_0[i][j] = 1'b0;
                        assign sum_cin_1[i][j] = 1'b0;
                    end
                end
            end
            
            assign cout_cin_0[i] = block_cout_cin_0;
            assign cout_cin_1[i] = block_cout_cin_1;
            
            // Select the correct output based on carry
            assign carry[i+1] = carry[i] ? cout_cin_1[i] : cout_cin_0[i];
            
            // Determine which sum to use based on the carry-in to this block
            for (j = 0; j < CURRENT_BLOCK_SIZE; j = j + 1) begin : block_sum_select
                assign sum[START_IDX + j] = carry[i] ? sum_cin_1[i][j] : sum_cin_0[i][j];
            end
        end
    endgenerate

endmodule

/**
 * Ripple-Carry Adder for Conditional-Sum Computation
 * 
 * This is a simple ripple-carry adder used as a building block within the
 * conditional-sum adder. It computes the sum and carry-out for a block
 * given a specific carry-in value.
 * 
 * Design Notes:
 * - Simple and area-efficient
 * - Delay is O(n) where n is the width
 * - Used within blocks where the delay is acceptable
 * - Two instances are used per block (one for cin=0, one for cin=1)
 * 
 * @param WIDTH Width of the adder (number of bits)
 * 
 * @input a[WIDTH-1:0] First operand
 * @input b[WIDTH-1:0] Second operand
 * @input cin Carry-in bit
 * @output sum[WIDTH-1:0] Sum result
 * @output cout Carry-out bit
 */
module cond_sum_rca #(
    parameter WIDTH = 4
) (
    input wire [WIDTH-1:0] a,
    input wire [WIDTH-1:0] b,
    input wire cin,
    output wire [WIDTH-1:0] sum,
    output wire cout
);
    // Internal carry chain: carry[i] is the carry into bit position i
    wire [WIDTH:0] carry;
    assign carry[0] = cin;        // Initialize with external carry-in
    assign cout = carry[WIDTH];   // Final carry-out
    
    // Chain full adders together
    genvar i;
    generate
        for (i = 0; i < WIDTH; i = i + 1) begin : full_adders
            // Sum computation: sum = a XOR b XOR carry_in
            assign sum[i] = a[i] ^ b[i] ^ carry[i];
            
            // Carry computation: cout = (a AND b) OR (a AND cin) OR (b AND cin)
            // This is the standard full-adder carry equation
            assign carry[i+1] = (a[i] & b[i]) | (a[i] & carry[i]) | (b[i] & carry[i]);
        end
    endgenerate
endmodule

/* verilator lint_on DECLFILENAME */
/* verilator lint_on UNOPTFLAT */
/* verilator lint_on EOFNEWLINE */
/* verilator lint_on GENUNNAMED */