LUT-based logic element with support for Shannon decomposition and associated method

• US 7,030,652 B1
• Filed: 04/23/2004
• Issued: 04/18/2006
• Est. Priority Date: 04/23/2004
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Lewis, David, Schleicher, James
• Primary Examiner(s): CHO, JAMES HYONCHOL
• Application Number:
  US10/830,819
• Time in Patent Office: 725 Days
• Field of Search: 326/41
• US Class Current: 326/41
• CPC Class Codes: H03K 19/1737 using multiplexers H03K19/1738 takes precedence
• CPC Class Codes: H03K 19/177 arranged in matrix form
• CPC Class Codes: H03K 19/17728 Reconfigurable logic blocks, e.g. lookup tables

Abstract

A logic circuit comprising: a plurality of logic elements; wherein at least one logic element includes, first and second LUT blocks that includes an output; an output multiplexer that includes first and second inputs, an output, and that includes a control output; a control input multiplexer circuit including a control input and including first and second data inputs that can be configured to receive first and second data outputs provided by one or more other logic elements of the plurality of logic elements and that includes a data output that can be connected to the control input of the output multiplexer; and multiple control inputs that can be shared by the first and second LUT blocks.

Claims

1. A logic circuit comprising:

a plurality of logic elements;

wherein at least one logic element includes,

first and second LUT blocks that include respective first and second outputs;

an output multiplexer that includes first and second inputs, an output that includes a control input;

a control input multiplexer circuit including a control input and including first and second data inputs that can be coupled to receive first and second data outputs provided by one or more other logic elements of the plurality of logic elements and that includes a data output that can be connected to the control input of the output multiplexer;

multiple control inputs that can be shared by the first and second LUT blocks;

a critical path signal x provided to the control input of the output multiplexor;

respective x-cofactors of control signal y as respective data inputs provided to the control input multiplexer circuit;

non-critical path dependent control signals provided to the multiple respective control inputs; and

the first and the second LUT blocks programmed to provide respective y-co-factors of an output signal z in response to provision of the non-critical path control signals.

2. The logic circuit of claim 1,

wherein the first and second LUT blocks are programmed to produce co-factors of a prescribed signal provided on an output of the output multiplexer when the multiple control inputs are connected to be shared by the first and second LUT blocks.

3. The logic circuit of claim 1,

wherein another logic element of the plurality of logic elements is programmed to produce the respective co-factors of a control signal provided on the output of the control multiplexer;

and

wherein the first and second data inputs of the control multiplexer are coupled to receive the respective control signal co-factors.

4. The logic circuit of claim 1,

wherein another logic element of the plurality of logic elements is programmed to produce the respective co-factors of a control signal provided on the output of the control multiplexer;

wherein the first and second data inputs of the control multiplexer are coupled to receive the respective control signal co-factors; and

wherein the first and second LUT blocks are programmed to produce co-factors of a prescribed output signal provided on an output of the output multiplexer when the multiple control inputs are connected to be shared by the first and second LUT blocks.

5. A logic circuit comprising:

a plurality of logic elements;

wherein at least one logic element includes,

a plurality of memory elements;

a plurality of multiplexers arranged in a plurality of levels including a highest multiplexer level, which includes a plurality of multiplexers with inputs connected to the memory elements and outputs connected to inputs of multiplexers of a next-to-highest multiplexer level and a first multiplexer level, which includes a k level multiplexer with inputs connected to outputs of multiplexer of a k+1 multiplexer level and at least one output;

a plurality of respective control inputs that can be connected to the respective multiplexers of the plurality of multiplexers; and

a control input multiplexer circuit including a control input and including first and second data inputs that can be configured to receive first and second data outputs provided by one or more other logic elements of the plurality of logic elements and that includes a data output that can be connected to a control input of the k level multiplexer of the plurality of multiplexers;

a critical path signal x provided to control the input multiplexer circuit;

x co-factors of signal y as data inputs provided to the control input multiplexer circuit; and

non-critical path control signals provided to the plurality of respective control inputs.

6. The logic circuit of claim 5,

wherein the plurality of multiplexers are arranged to form a first look-up table that provides a first k+1 level output and to provide a second look-up table that provides a second k+1 level output;

and

wherein the first and second look-up tables can share the plurality of respective control inputs.

7. The logic circuit of claim 5,

wherein the plurality of multiplexers are arranged to form a first look-up table that provides a first k+1 level output and to provide a second look-up table that provides a second k+1 level output;

and

wherein the first and second look-up tables can share the plurality of respective control inputs; and

wherein the k level multiplexer is a first level multiplexer and the k+1 level multiplexers are second level multiplexers.

8. The logic circuit of claim 5 comprising:

the memory elements programmed to cause k+1 level multiplexers of the plurality of multiplexers to produce y-co-factors of a signal z in response to provision of the non-critical path control signals.

9. A logic circuit comprising:

a plurality of logic elements;

wherein a first logic element of the plurality of logic elements includes,

a plurality of memory elements;

a plurality of multiplexers arranged in a plurality of levels including a highest multiplexer level, which includes a plurality of multiplexers with inputs connected to the memory elements and outputs connected to inputs of multiplexers of a next-to-highest multiplexer level and a first multiplexer level, which includes a k level multiplexer with inputs connected to outputs of multiplexers of a k+1 multiplexer level and at least one output; and

a plurality of respective control inputs that can be connected to the respective multiplexers of the plurality of multiplexers; and

a control input multiplexer circuit including a control input and including first and second data inputs that can be configured to receive first and second data outputs provided by one or more other logic elements of the plurality of logic elements and that includes a data output that can be connected to a control input of the k level multiplexer of the plurality of multiplexers;

wherein the control input multiplexer circuit is coupled to receive a first critical path signal x;

wherein respective data inputs to the control put multiplexer circuit are coupled to receive respective x-co-factors of a signal y;

wherein the plurality of multiplexers are arranged to form a first look-up table that provides a first k+1 level output and to provide a second look-up table that provides a second k+1 level output;

wherein the first and second look-up tables share the respective plurality of control inputs; and

wherein the memory elements are programmed to cause the respective first and second look-up tables to produce respective y-co-factors of a signal z on the first and second k+1 level outputs in response to provision of the control signals provided to the shared plurality of control inputs.

10. The logic circuit of claim 9,

wherein another logic element of the plurality of logic elements is programmed to produce the respective x-co-factors of signal y.

11. A logic circuit comprising:

a first LUT block that includes first LUT block output;

a second LUT block that includes second LUT block output;

an output multiplexer that includes fist and second data inputs, a data output and a control input;

a first interposed multiplexer that can be coupled to receive signals output by the respective fist and second outputs of the first and second LUT blocks and that includes a first intermediate multiplexer output that can be coupled to the first input of the output multiplexer and that includes a control input;

a second interposed multiplexer that can be coupled to receive signals output by the respective first and second outputs of the first and second LUT blocks and that includes a second intermediate multiplexer output that can be coupled to the second input of the output multiplexer and that includes a control input;

respective control inputs that can be shared by the first and second LUT blocks;

a critical path signal x provided to the control input of the output multiplexer;

respective x-c-factors of control signal y provided to respective control inputs of the first and second interposed multiplexers;

respective non-critical path dependent control signals provided to the respective control inputs; and

the first and second LUT blocks programmed to provide respective y-co-factors of an output signal z on respective first and second LUT block outputs in response to provision of the respective non-critical path control signals.

12. The logic circuit of claim 11,

wherein the first and second LUT blocks can be programmed to produce co-factors when the respective control inputs are connected to be shared by the first and second LUT blocks.

13. A logic circuit comprising:

a first LUT block that includes a first LUT block output;

a second LUT block that includes a second LUT block output;

a third LUT block that includes a third LUT block output;

a fourth LUT block that includes a fourth LUT block output;

an output multiplexer that includes first and second data inputs and first, a data output and a control input;

respective control inputs that can be shared by the first through fourth LUT blocks;

interposed means for receiving respective first, second, third and fourth LUT block output signals and for receiving first and second control signals and for providing a first intermediate output signal to the first data input of the output multiplexer and for receiving third and fourth input signals providing a second intermediate output signal to the second data input of the output multiplexer;

a critical path signal x provided to a control input of the at least one k level multiplexer;

respective x-co-factors of a critical path signal dependent control signal y provided to respective control inputs of the first and second interposed multiplexers; and

non-critical path dependent control signals provided as control input signals to one or more other control inputs of the plurality of multiplexers.

14. The logic circuit apparatus of claim 13 comprising:

the first and third LUT blocks programmed to provide respective z_y1y0 and z_{{overscore (y1)}y0} second-level co-factor outputs of an output signal z on respective first and third LUT block outputs in response to provision of the respective non-critical path control signals; and

the second and fourth LUT blocks programmed to provide respective z_{y1{overscore (y0)}} and z_{{overscore (y1y0)}} second-level co-factor outputs of the output signal z on respective second and fourth LUT block outputs in response to provision of the respective non-critical path control signals; and

a non-critical input signal provided to the first and third control inputs of the interposed means;

co-factors y_{{overscore (x0)}} and y_x0 provided to the second and fourth control inputs of the interposed means;

the interposed means providing one of the first and third LUT block outputs or one of the second and fourth LUT block outputs to the first data input of the output multiplexer in response to the first control signal and second control signals; and

the interposed means providing one of the first and third LUT block outputs or one of the second and fourth LUT block outputs to the second data input of the output multiplexer in response to the third and fourth control signals.

15. A logic circuit comprising:

a plurality of memory elements;

a plurality of multiplexers arranged in a plurality of levels including a highest multiplexer level, which includes a plurality of multiplexers with inputs connected to the memory elements and outputs connected to inputs of multiplexers of a next-to-highest multiplexer level and a first multiplexer level, which includes at least one multiplexer in a first level with inputs connected to outputs of multiplexers of a second multiplexer level and at least one output; and

at least one interposed level of multiplexers; and

wherein the at least one interposed level of multiplexers can be connected between k+1 level multiplexers and at least one k level multiplexer of the plurality of multiplexers;

respective control inputs can be connected to the respective multiplexers of levels k+1 or higher;

wherein the at least one interposed level of multiplexers includes first interposed multiplex circuitry and second interposed multiplex circuitry that can be connected to receive identical data input signals provided as data output signals of the k+1 level multiplexers; and

wherein the first interposed multiplex circuitry and the second interposed multiplex circuitry can be connected to first and second data inputs of the at least one k level multiplexer;

a critical path signal x provided to a control input of the at least one k level multiplexer;

respective x-co-factors of a critical path signal dependent control signal y provided to respective control inputs of the first and second interposed multiplexers; and

non-critical path dependent control signals provided as control input signals to one or more other control inputs of the plurality of multiplexers.

16. The logic circuit of claim 15,

wherein the plurality of multiplexers are arranged to include two first look-up tables that provides two fist k+1 level outputs and to include two second look-up tables that provide two second k+1 level outputs;

and

wherein the two first and two second look-up tables can share the control inputs.

17. The logic circuit of claim 15,

wherein the plurality of multiplexers are arranged to include two first look-up tables that provides two first k+1 level outputs and to include two second look-up tables that provide two second k+1 level outputs;

wherein the two first and two second look-up tables can share the control inputs; and

wherein the k level multiplexer is a first level multiplexer and the k+1 level multiplexers are second level multiplexers.

18. The logic circuit apparatus of claim 15 comprising:

a critical path signal x provided to a control input of the at least one k level multiplexer;

respective x-co-factors of a first critical path signal dependent signal y provided to respective control inputs of the first and second interposed multiplexers;

non-critical path dependent control signals provided to one or more other control inputs of the plurality of multiplexers; and

the memory elements to cause the k+1 level multiplexers programmed to produce at y-co-factors of a second critical path signal dependent signal z in response to provision of the non-critical path control signals.

19. A programmable logic device comprising:

a first logic element including a look up table programmed to produce a y_{{overscore (x0)}}=f(0,x1,x2, . . . ) value and a y_x0=f(1,x1,x2, . . . ) value;

a second logic element including a look up table programmed to produce a z_{{overscore (y0)}}=g(0,y1,y2, . . . ) value and a z_y0=g(1,y1,y2, . . . ) value;

a first multiplexer circuit in the second logic element coupled to receive the z_{{overscore (y0)}} value as a data input and coupled to receive the z_y0 value as a data input and coupled to receive the y_{{overscore (x0)}} value as a control input, wherein the first multiplexer circuit provides as an output one of a z_{{overscore (y0)}} received value or a received z_y0 value in response to a received y_{{overscore (x0)}} value;

a second multiplexer circuit in the second logic element coupled to receive the z_{{overscore (y0)}} value as a data input and coupled to receive the z_y0 value as a data input and coupled to receive the y₀ value as a control input, wherein the second multiplexer circuit provides as an output the other a received z_{{overscore (y0)}} value or a received z_y0 value in response to a received y_x0 value; and

a third multiplexer circuit in the second logic-element coupled to receive an output of the first multiplexer circuit as a data input and coupled to receive an output of the second multiplexer circuit as a data input and coupled to receive an x0 value as a control input, wherein the third multiplexer circuit provides as an output one of a received output of the first multiplexer or a received output of the second multiplexer in response to a received x0 value.