Patent ID: 7486110

Claim:
A look-up table (LUT) based multiplexer having multiplexer input data lines and a multiplexer final output, comprising: input select lines; input data lines, each input data line having a respective index; a first multiplexer stage having an input and receiving multiplexer input data lines at its input, the first multiplexer stage comprising a set of muxlets, each muxlet having an input and all the muxlets receiving a subset of the multiplexer input data lines at its input, the first multiplexer stage having an output and output data lines at its output; a second multiplexer stage having an input and input data lines at its input, the output data lines of the first multiplexer stage being connected directly to the input data lines of the second multiplexer stage, the second multiplexer stage having an output and a single data line at its output, the second multiplexer stage comprising a muxlet; and a LUT based logic architecture adapted to: select a muxlet size by selecting a largest size muxlet from a bank of available muxlets of more than one size, such that the muxlet size R selected is less than or equal to N, where N is the number of select lines and 2 N is the number of input data lines, identify a number of tiles required for the input data lines, for each tile, identify inputs to the tile, assign a number from 1 to 2 N−R to each tile, for each input data line, generate a binary number Z equal to the respective index minus 1, generate a number X formed by masking the R most significant bits of Z, wherein X+1 is a tile number to which the input data line is connected, and generate a number Y equal to the R most significant bits of Z right shifted by N−R, wherein Y+1 is the index of a tile input to which the input data line is connected, assign an output line index as the number of the corresponding tile, generate a muxlet by making connections as identified in the preceding steps, and generating new output lines, assign to input data lines of a next muxlet the data output lines of a preceding muxlet and respective index values, decrease value of N by R, and repeat the preceding steps until no additional muxlet is required to implement the multiplexer; whereby the first and second stages cascaded together form a tree structure in which all the inputs to the first stage are roots of the LUT based multiplexer and the second stage produces a final output of the LUT based multiplexer at the multiplexer final output.