Universal Dyadic Boolean Operator

by GateForge Consulting Ltd.

Without going into the theory as to why, there are 222 = 24 = 16 possible Boolean operations on two variables. Said otherwise, there are 16 possible dyadic Boolean functions.

(I'm using the Greek "dyadic" rather than the Latin "binary", as the latter is confusing, and it will be even more so when we extend this example to 3 variables: "ternary" usually refers to 3-valued logic, so we will use "triadic" instead later on.)

Rather than simply hard-coding a particular dyadic Boolean operation, it can be handy to specify it dynamically: it's obviously useful as part of an ALU, or it can allow changing the fixed relationship between two variables via a module parameter (where we can expect the logic to optimize down to a minimal form).

First, we can enumerate and encode all 16 operations:

`ifndef DYADIC_OPERATIONS
`define DYADIC_OPERATIONS

    // Number of bits to define dyadic operations, never changes.
    `define DYADIC_CTRL_WIDTH       4
    `define DYADIC_CTRL_ADDR_WIDTH  2

    // These assume A op B, where A is the MSB into the dyadic operator.

    `define DYADIC_ALWAYS_ZERO 4'b0000
    `define DYADIC_A_AND_B     4'b1000
    `define DYADIC_A_AND_NOT_B 4'b0100
    `define DYADIC_A           4'b1100
    `define DYADIC_NOT_A_AND_B 4'b0010
    `define DYADIC_B           4'b1010
    `define DYADIC_A_XOR_B     4'b0110
    `define DYADIC_A_OR_B      4'b1110
    `define DYADIC_A_NOR_B     4'b0001
    `define DYADIC_A_XNOR_B    4'b1001
    `define DYADIC_NOT_B       4'b0101
    `define DYADIC_A_OR_NOT_B  4'b1101
    `define DYADIC_NOT_A       4'b0011
    `define DYADIC_NOT_A_OR_B  4'b1011
    `define DYADIC_A_NAND_B    4'b0111
    `define DYADIC_ALWAYS_ONE  4'b1111

`endif

We choose this particular encoding to match the following implementation of a Universal Dyadic Boolean Operator, which we can describe as a "transposed" 4:1 multiplexer: Each bit of the two variables act as selectors, and the particular Boolan operation is described by the (constant) bits fed to the multiplexer data inputs. We build the dyadic operator as a vector of 4:1 multiplexers, using our previously defined Addressed_Mux. Since a 4:1 mux naturally maps to a 6-LUT on an FPGA, it's quite efficient and predictable.

// Based on control input, implements one of the 16 possible two-variable
// (dyadic) Boolean operators, as o = a op b.

module Dyadic_Boolean_Operator
#(
    parameter WORD_WIDTH                        = 0
)
(
    input   wire    [`DYADIC_CTRL_WIDTH-1:0]    op,
    input   wire    [WORD_WIDTH-1:0]            a,
    input   wire    [WORD_WIDTH-1:0]            b,
    output  wire    [WORD_WIDTH-1:0]            o
);

    // One mux per bit, where the inputs select the op bits.

    generate
        genvar i;
        for(i = 0; i < WORD_WIDTH; i = i+1) begin: per_bit
            Addressed_Mux
            #(
                .WORD_WIDTH     (1),
                .ADDR_WIDTH     (`DYADIC_CTRL_ADDR_WIDTH),
                .INPUT_COUNT    (`DYADIC_CTRL_WIDTH)
            )
            Operator
            (
                .addr           ({a[i],b[i]}),    
                .in             (op),
                .out            (o[i])
            );
        end
    endgenerate

endmodule

fpgacpu.ca