Patent ID: 6215327
Filing Date: 2001-04-10
Classification: H03K,Y10S

Abstract:
A field programmable gate array (FPGA) having an m-input (m is an odd integer greater than 1) Boolean look-up-table-based (m-LUT-based) architecture analogous to a universal one-dimensional (1-D) binary cellular automata (CA) wherein a 1-D universal CA network in converted into a spatially unraveled two-dimensional (2-D) feedforward network, said FPGA comprising:a. one or more arrays (tiles), each comprised of a plurality of LUTs arranged in a directed, repeatable x-column, y-row grid propagating in the positive y direction, with each LUT having only nearest neighbor connections to other LUTs and not any other bridging structures except at the boundaries, the definition of each LUT behavior in a tile being allowed to be distinct and individually programmable for a particular logic function;b. each of said tiles having no specialized routing structures, since logic functions can imitate wiring from any LUT input to an output, allowing the LUTs to emulate both logic and (virtual) wiring;c. identical and fixed neighborhood templates for all LUTs in a particular tile;d. robust, periodic wire input/output attachments to any edge of said tile to bordering LUT termini, subject to cone of influence effects;e. means to test each tile to locate defective LUTs by using diagnostic (temporary) test personalities;f. means for mapping around a finite number of LUTs having a defective data path;g. linear register array means inserted at the end of a tile and between tiles on any edge, whereby synchronous behavior is produced by registering signals between tiles in synchronization with an overall clock;h. means to achieve sequential feedback behavior in the 1-D architecture by combining tiles in a way that can produce synchronous or asynchronous loops in signal propagation;i. means to program the tiles through serial bitstream patterns that are shifted through each LUT in succession using dedicated termini on each LUT, as a minimum containing a shift-in and a shift out with the possibility of one or more clocking signals to drive the shifting of said patterns through the tile; andj. means to improve the reliability of a tile due to potential defects in the bitstream shifting structures within and between LUTs by propagating the shift patterns in the direction of array propagation and by using multiple serial streams, such that single point defects will not result in the loss of an entire tile.