Technology mapping techniques for incomplete lookup tables

A method for converting a circuit design into an equivalent circuit that includes incomplete lookup tables, the method comprising:

• identifying a function that is implemented by a portion of the circuit design, the function having input signals;
• determining whether an incomplete lookup table (LUT) implements the function in the circuit design, wherein determining whether the incomplete LUT implements the function further comprises:
• comparing outputs of the function with outputs of the incomplete LUT for each binary value of the input signals;
• and
• determining if the incomplete LUT generates the same outputs as the function for each of the binary values of the input signals, wherein the incomplete LUT has N inputs and less than 2N bits of storage;
• and
• replacing the portion of the circuit design that implements the function with the incomplete LUT if the incomplete LUT implements the function.

A system for determining whether an incomplete lookup table (LUT) implements a function, wherein the incomplete LUT has N inputs and less than 2N bits of storage, the system comprising:

• means for comparing outputs of the function with outputs of the incomplete LUT using an XOR function, for each binary value of the input signals;
• means for evaluating outputs of the XOR functions using an OR function to determine if the incomplete LUT generates the same outputs as the function for each of the binary values of the input signals;
• means for creating a binary decision diagram for the XOR functions and the OR function;
• means for determining if a path exists through the binary decision diagram to a zero end point of the binary decision diagram;
• and
• means for swapping the input signals of the function with respect to the inputs of the incomplete lookup table, if the incomplete lookup table is asymmetric.