Logic basic cell and logic basic cell arrangement Number:7,386,812 from the United States Patent and Trademark Office (PTO) owispatent

Title: Logic basic cell and logic basic cell arrangement

Abstract: Logic basic cell and logic basic cell arrangement having a plurality of logic basic cells. A logic basic cell includes at least six data signal inputs, a first logic function block and a second logic function block, at least one logic function configuration input, a first multiplexer and a second multiplexer.

Patent Number: 7,386,812 Issued on 06/10/2008 to Gliese,   et al.

---

Inventors:	Gliese; Jorg (Munich, DE), Sauermann; Mirko (Neubiberg, DE)
Assignee:	Infineon Technologies AG (DE)
Appl. No.:	10/995,960
Filed:	November 22, 2004

---

Foreign Application Priority Data

---

Nov 21, 2003 [DE]			103 54 499
May 25, 2004 [DE]			10 2004 025 579

Current U.S. Class:	716/1 ; 716/16; 716/17
Field of Search:	716/1,16-18

---

References Cited [Referenced By]

---

U.S. Patent Documents

5386156	January 1995	Britton et al.
6178541	January 2001	Joly et al.
6331789	December 2001	Or-Bach
6505337	January 2003	Wittig et al.
6529040	March 2003	Carberry et al.
2002/0010902	January 2002	Chen et al.
2002/0043988	April 2002	Or-Bach et al.
2002/0162078	October 2002	Boppana et al.
2003/0206036	November 2003	Or-Bach
2004/0049759	March 2004	Osann et al.

Foreign Patent Documents

	0 701 328		Mar., 1996		EP
	1 150 431		Oct., 2001		EP
	WO-02/093745		Nov., 2002		WO

Other References

Wannemacher, M; "Das FPGA-Kochbuch", ("The FPGA Cookbook"), fig. 7.36: logic block (CLB) of the XC4000 families, 1st edition, International Thomson Publishing Company, Bonn, 1998, p. 197. cited by other.

Primary Examiner: Dinh; Paul
Attorney, Agent or Firm: Dickstein, Shapiro, LLP

---

Claims

---

The invention claimed is:

1. A logic basic cell for forming at least one output signal from at least three input signals in accordance with a predeterminable logic function, comprising: a first unit for realizing a first decomposition of the logic function into a plurality of logic subfunctions; and a second unit for realizing a second decomposition of the logic function into a plurality of logic subfunctions; wherein each of the first unit and the second unit is set up for realizing a Shannon decomposition, or for realizing an iterative decomposition, or for realizing a disjoint decomposition, wherein the first unit is set up as a Shannon decomposition unit for realizing a Shannon decomposition of a logic function into a plurality of logic subfunctions, further comprising: at least eight data signal inputs, it being possible for a data signal to be provided at each of the data signal inputs; a first logic function block, which is coupled to a first data signal input and a second data signal input of the data signal inputs, and is located within the first unit; a second logic function block, which is coupled to a third data signal input and a fourth data signal input of the data signal inputs, and is located within the second unit; at least one logic function configuration input, by means of which it is possible to predetermine a logic subfunction which can be realized by the respective logic function block from a plurality of logic subfunctions which can be realized for combining the data signals present at the respective logic function block; the Shannon decomposition unit having a first multiplexer, the first data input of which is coupled to an output of the first logic function block and the second data input of which is coupled to an output of the second logic function block and the control input of which is coupled to a fifth data signal input of the data signal inputs; and a first data signal output coupled to the output of the first logic function block, a second data signal output coupled to the output of the second logic function block, and a third data signal output coupled to an output of the first multiplexer, at which data signal outputs it is possible to tap off separately in each case a signal at the output of the first logic function block, a signal at the output of the second logic function block and a signal at the output of the first multiplexer, respectively, wherein the second unit which realizes an additional decomposition of the logic function into a plurality of logic subfunctions comprises a second multiplexer, the control input of which is coupled to a sixth data signal input of the data signal inputs, the first data input of which is coupled to a seventh data signal input of the data signal inputs and the second data input of which is coupled to an eighth data signal input of the data signal inputs.

2. The logic basic cell as claimed in claim 1, wherein the first data signal input is coupled to the third data signal input and/or the second data signal input is coupled to the fourth data signal input.

3. The logic basic cell as claimed in claim 1, wherein at least one of the logic function blocks comprises: a first signal path having a plurality of transistors of a first conduction type, said first signal path being coupled to at least a portion of the data signal inputs of the respective logic function block, it being possible for the transistors to be connected to one another such that they realize the logic subfunction which can be realized by the respective logic function block from all possible logic subfunctions for combining the data signals present at the respective logic function block, so that an output signal representing a result of the logic subfunction is provided; and a second signal path having a plurality of transistors of a second conduction type complementary to the first conduction type, said second signal path being coupled to at least a portion of the data signal inputs of the respective logic function block, it being possible for the transistors to be connected to one another such that they realize an inverse logic subfunction with respect to that of the transistors of the first signal path from all possible logic subfunctions for logically combining the two data signals, so that an output signal representing a result of the logic subfunction is provided.

4. The logic basic cell as claimed in claim 1, wherein at least one of the logic function blocks is formed as programmable logic device, field-programmable gate array, mask-programmed application-specific integrated circuit, logic gate or arrangement of a plurality of logic gates, or look-up table.

5. The logic basic cell as claimed in claim 1, wherein the logic subfunction which can be realized is predetermined for the respective logic function block in an invariable fashion at the at least one logic function configuration input.

6. The logic basic cell as claimed in claim 5, further comprising a storage device which is coupled to the at least one logic function configuration input and in which the information for predetermining the logic subfunction which can be realized can be stored.

7. The logic basic cell as claimed in claim 1, wherein the logic subfunction which can be realized is predetermined for the respective logic function block in a variable fashion by means of a signal which can be applied at the at least one logic function configuration input.

8. The logic basic cell as claimed in claim 1, set up for processing digital data signals.

9. The logic basic cell as claimed in claim 1, further comprising at least one register which is connected downstream of the first and second logic function blocks and the first and second multiplexers and serves for tapping off signals which can be provided at at least one output of the logic basic cell.

10. The logic basic cell arrangement as claimed in claim 9, wherein the output of the first multiplexer of a first logic basic cell is coupled to the first data input of the second multiplexer of a second logic basic cell.

11. The logic basic cell arrangement as claimed in claim 10, wherein the output of the first multiplexer of a third logic basic cell is coupled to the second data input of the second multiplexer of the second logic basic cell.

12. The logic basic cell arrangement as claimed in claim 11, wherein at least one of the data inputs of the second multiplexer of the first and/or of the third logic basic cell is free of a coupling to other logic basic cells.

13. The logic basic cell arrangement as claimed in claim 12, wherein the first and/or the second logic function block and/or the first multiplexer of the second logic basic cell are free of a coupling to other logic basic cells.

14. The logic basic cell arrangement as claimed in claim 13, wherein at least a portion of the at least one logic function block and/or multiplexer free of a coupling to other logic basic cells can be connected to an additional circuit such that the at least one logic function block and/or multiplexer contributes to the functionality of the additional circuit.

15. The logic basic cell as claimed in claim 1, wherein the second unit which realizes an additional decomposition is set up for realizing an iterative decomposition, and realizes the iterative decomposition by means of a first logic function block, having at least two data signal inputs, to which at least two input signals can be applied, and having a data signal output for providing a logic combination of the at least two input signals realized in accordance with a predeterminable logic subfunction.

16. The logic basic cell as claimed in claim 15, wherein the second unit which realizes an additional decomposition furthermore realizes the iterative decomposition by means of a multiplexer, having a first and having a second data signal input and having a data signal output, the data signal output of the first logic function block being coupled to the first data signal input of the multiplexer, it being possible for an additional input signal to be provided at the second data signal input of the multiplexer.

17. The logic basic cell as claimed in claim 15, wherein at least one of the logic function blocks is formed as logic gate or arrangement of a plurality of logic gates, or look-up table.

18. The logic basic cell as claimed in claim 15, wherein the logic subfunction which can be realized is predetermined for the respective logic function block in an invariable fashion at at least one logic function configuration input.

19. The logic basic cell as claimed in claim 15, wherein the logic subfunction which can be realized is predetermined for the respective logic function block in a variable fashion by means of a signal which can be applied at at least one logic function configuration input.

20. The logic basic cell as claimed in claim 1, wherein the second unit which realizes an additional decomposition is set up for realizing an iterative decomposition and for realizing a disjoint decomposition.

21. The logic basic cell as claimed in claim 1, set up as an application-specific integrated circuit.

22. The logic basic cell as claimed in claim 1, set up as programmable logic device, field-programmable gate array, or mask-programmed application-specific integrated circuit.

23. The logic basic cell as claimed in claim 1, set up as a CMOS logic basic cell.

24. A logic basic cell arrangement having a plurality of logic basic cells as claimed in claim 1 that are connected to one another.

25. A logic basic cell for forming at least one output signal from at least three input signals in accordance with a predeterminable logic function, comprising: a first unit for realizing a first decomposition of the logic function into a plurality of logic subfunctions; and a second unit for realizing a second decomposition of the logic function into a plurality of logic subfunctions; wherein each of the first unit and the second unit is set up for realizing a Shannon decomposition, or for realizing an iterative decomposition, or for realizing a disjoint decomposition, wherein the second unit which realizes an additional decomposition is set up for realizing a disjoint decomposition, and realizes the disjoint decomposition by means of a first logic function block, a second logic function block and a third logic function block, the second logic function block realizing a first logic subfunction of at least two input signals, the third logic function block realizing a second logic subfunction of at least two input signals, and the third logic function block realizing a logic combination of the output signals of the first and of the second logic function block, wherein the second unit which realizes an additional decomposition realizes the disjoint decomposition by means of a multiple function device that selectively realizes a multiplex functionality of at least two input signals or the functionality of forming a logic subfunction of at least two input signals.

26. The logic basic cell as claimed in claims 25, wherein a changeover is made between the multiplexer of the Shannon decomposition unit and the multiple function device by means of an invariable hardware element and the function of the multiple function device is likewise realized by an invariable hardware element.

27. The logic base cell as claimed in claim 26 wherein the multiplexer and/or the multiple function device are realized by means of a plurality of metallization planes and/or by means of vias.

28. A logic basic cell for forming at least one output signal from at least three input signals in accordance with a predeterminable logic function, comprising: a first unit for realizing a first decomposition of the logic function into a plurality of logic subfunctions; and a second unit for realizing a second decomposition of the logic function into a plurality of logic subfunctions; wherein each of the first unit and the second unit is set up for realizing a Shannon decomposition, or for realizing an iterative decomposition, or for realizing a disjoint decomposition, wherein the first unit is set up as a Shannon decomposition unit for realizing a Shannon decomposition of a logic function into a plurality of logic subfunctions, and wherein the Shannon decomposition unit realizes the Shannon decomposition by means of a first logic function block, a second logic function block and a multiplexer, the first logic function block realizing a first logic subfunction of at least two input signals, the second logic function block realizing a second logic subfunction of at least two input signals, and the multiplexer combining the output signals of the two logic function blocks with one another and with an additional input signal.

---

Description

---

CROSS-REFERENCE TO RELATED APPLICATION

This application claims priority to German Patent Application Serial No. 103 54 499.2 filed Nov. 21, 2003, and German Patent Application Serial No. 10 2004 025 579.2 filed May 25, 2004.

FIELD OF THE INVENTION

The invention relates to a logic basic cell and a logic basic cell arrangement.

BACKGROUND OF THE INVENTION

The advent of digital technology and the rapid development of microprocessor technology gave rise to a demand for programmable logic. A PLD ("programmable logic device") is an integrated circuit whose logic function is defined by the user by means of programming. A PLD is an architecture for digital logic operations with a plurality of switches that enable a multiplicity of signal paths. The logic function assigned to a PLD in a user-specific fashion is defined by means of configuration of the PLD.

PLDs include, inter alia, field-programmable gate arrays (FPGA), the functionality of which can be assigned to them by the user, mask-programmable gate arrays (MPGA, also called "structured ASICs"), which can be allocated a logic function by means of hardware configuration. Via-programmable gate arrays (VPGAs) are included among MPGAs.

Basic cells for a field-programmable gate array (FPGAs) and a structured ASIC (sASIC) provide combinatorial functionality and registers for implementing a design. A basic cell is intended to ensure a good mappability both of simple and of complex logic functions without generating unnecessary overhead.

A digital logic cell maps n input signals onto an output signal. The number of possible mapping functions is 2.sup.2.sup.n. A circuit group as a digital logic cell is realized in accordance with the prior art for example using so-called look-up tables (LUT). For this purpose, function values of the logic function are set by means of a data word of 2.sup.n bits. In other words, the respectively logic function is coded into a data word. n input signals a.sub.0, a.sub.1 . . . a.sub.n-1 are combined with one another in accordance with the selected logic function. Consequently, the logic input signals of the logic function y=f (a.sub.0, a.sub.1, . . . , a.sub.n-1) may be regarded as a binary address.

An FPGA based on a look-up table (LUT) is disclosed in U.S. Pat. No. 6,529,040 B1, for example.

A logic basic cell for field-programmable gate arrays (FPGA) and "structured ASICs" provide combinatorial functionality for implementing a logic design.

The prior art discloses fine-granularity and coarse-granularity approaches for logic basic cells.

In the case of a fine-granularity basic cell, it is often not possible to realize all the possible 2.sup.2.sup.n logic functions of n input signals, so that in some scenarios logic functions of low complexity already have to be realized in a manner distributed over a plurality of basic cells. Interconnect resources are blocked in this way, which leads to a less effective utilization of resources. Furthermore, in the case of such fine-granularity basic cells, long signal paths are disadvantageous in the case of more complex functions. Furthermore, the software for the partitioning of such fine-granularity basic cell arrangements is complex.

A coarse-granularity approach involves realizing a complex basic cell by means of which it is often possible for logic functions also of medium complexity to be realized completely. On the other hand, if a short data path is intended to be mapped onto such a coarse-granularity basic cell, large portions of the combinatorial resources of the basic cell are unutilized, with the result that the mapping is inefficient. Furthermore, the scalability of known basic cells is often unsatisfactory, particularly if a logic function to be mapped does not match a basic cell.

U.S. Pat. No. 6,331,789 B2 discloses a logic array apparatus with an array of programmable logic cells, having a plurality of inputs and a plurality of outputs and adapted connecting structures which are superposed on a portion of the programmable cell.

Inputs may serve as control inputs for a multiplexer tree, see Wannemacher, M "Das FPGA-Kochbuch", ["The FPGA Cookbook"], fig. 7.36: logic block (CLB) of the XC4000 families, 1st edition, International Thomson Publishing Company, Bonn, 1998, p. 197. The multiplexers may be realized in a logic-based fashion and/or on the basis of transmission gates.

U.S. 2003/0206036 A1 discloses a user-defined configurable and programmable logic basic cell arrangement based on an interconnection of look-up tables and multiplexers.

U.S. 2002/0043988 A1 discloses a programmable logic basic cell arrangement having 5 data signal inputs and also a first logic function block and a second logic function block, implemented as a look-up table, a logic function configuration input and also a first multiplexer. At the data signal outputs, it is possible to tap off separately a signal at the output of the first logic function block, a signal at the output of the second logic function block and a signal at the output of the multiplexer.

EP 0 701 328 A2 discloses a field-programmable gate array (FPGA) having a decoder circuit arrangement for increasing the number of inputs for each programmable logic cell. The decoder circuit arrangement couples the respective desired look-up table of a respective logic cell.

EP 1 150 431 A1 discloses another FPGA with look-up tables.

U.S. Pat. No. 5,386,156 describes a programmable function unit set up for use in an FPGA, so-called ripple logic being used in the programmable function unit.

Furthermore, WO 02/093745 A2 discloses a reconstructable logic apparatus with a look-up table.

Many logic basic cells disclosed in the prior art are based on Boolean logic. Such logic basic cells make use of the fact that a function f(a.sub.n, a.sub.n-1, . . . , a.sub.0) of n+1 input signals a.sub.i, in accordance with Boolean logic, can be reduced to two functions f.sub.0, f.sub.1 of in each case n input signals a.sub.i as follows: f: IB.sup.n+1.fwdarw.IB: f(a.sub.n, a.sub.n-1, . . . , a.sub.1, a.sub.0)= .sub.nf.sub.0(a.sub.n-1, . . . , a.sub.0)a.sub.nf.sub.1(a.sub.n-1, . . . , a.sub.0)=f.sub.s(f.sub.1, f.sub.0, a.sub.n) (1)

The decomposition of f into f.sub.1 and f.sub.0 in accordance with equation (1) is referred to as so-called Shannon decomposition. In this case, a.sub.n is the logic inverse of the data signal a.sub.n. For the case n=2, that is to say where a function of n+1=3 input signals, the logic overall function f as a function of three input signals is thus reduced to two (simpler) logic subfunctions f.sub.0 and f.sub.1 of two input signals. Each of the logic subfunctions f.sub.0, f.sub.1 can be realized by one of the logic function blocks of a logic basic cell.

For the special case of n+1=4 input signals, using equation (1), the logic overall function can be reduced to two functions of three input signals, it being possible for each function of three input signals once again to be divided into two logic subfunctions with two inputs by applying equation (1) again. In other words, a logic overall function of four data signals can be decomposed into four logic subfunctions which can be realized by four logic function blocks, that is to say two logic basic cells. This consideration can be continued for an arbitrary number of input signals; by way of example, the realization of a logic overall function of five data signals requires 2*2*2=8 logic function blocks, that is to say four logic basic cells having in each case two logic function blocks.

However, a logic basic cell realized in accordance with the Shannon decomposition in accordance with equation (1) is not well suited to many applications requiring a high degree of flexibility.

SUMMARY OF THE INVENTION

The invention is based on the problem, in particular, of providing a logic basic cell which provides an increased degree of flexibility.

The problem is solved by means of a logic basic cell and by means of a logic basic cell arrangement having the features in accordance with the independent patent claims.

Preferred configurations of the invention emerge from the dependent patent claims.

A logic basic cell for forming at least one output signal from at least three input signals in accordance with a predeterminable logic function has a first logic decomposition unit for realizing a first decomposition of the logic function into a plurality of logic subfunctions and also a second logic decomposition unit for realizing a second decomposition of the logic function into a plurality of logic subfunctions. The first logic decomposition unit and the second logic decomposition unit are set up for realizing a Shannon decomposition, or for realizing an iterative decomposition, or for realizing a disjoint decomposition. In accordance with one configuration of the invention, the first unit is a Shannon decomposition unit for realizing a Shannon decomposition of a logic function into a plurality of logic subfunctions.

A logic basic cell arrangement contains a plurality of logic basic cells having the features mentioned above.

In accordance with one aspect of the invention, a logic basic cell has at least five data signal inputs, it being possible for a data signal to be provided at each data signal input. Furthermore, the logic basic cell contains a first logic function block, which is coupled to a first data signal input and a second data signal input of the data signal inputs, and a second logic function block, which is coupled to a third data signal input and a fourth data signal input of the data signal inputs. Furthermore, at least one logic function configuration input is provided, by means of which it is possible to predetermine a logic subfunction which can be realized by the respective logic function block from a plurality of logic subfunctions which can be realized for combining the data signals present at the respective logic function block. The logic basic cell contains a first logic decomposition unit, the first data input of which is coupled to an output of the first logic function block, the second data input of which is coupled to an output of the second logic function block and the control input of which is coupled to a fifth data signal input of the data signal inputs. Furthermore, the logic basic cell contains a first data signal output coupled to the output of the first logic function block, a second data signal output coupled to the output of the second logic function block and a third data signal output coupled to an output of the first logic decomposition unit, at which data signal outputs it is possible to tap off separately in each case a signal at the output of the first logic function block, a signal at the output of the second logic function block and a signal at the output of the first logic decomposition unit.

One aspect of the invention may be seen in connecting up two logic function blocks and a first logic decomposition unit to one another in such a way, and applying data signals to the inputs thereof in such a way, that a logic subfunction can be realized as part of a logic overall function to be realized by a logic basic cell arrangement comprising a plurality of logic basic cells. Clearly, a partly processed signal is provided at an output of the first logic decomposition unit, which signal may be provided as an input signal for example to an input of a second logic decomposition unit of another logic basic cell of the logic basic cell arrangement. One or a plurality of input signals for a second logic decomposition unit of a logic basic cell of a logic basic cell arrangement may be provided by another logic basic cell which fulfills another logic subfunction of the logic overall function.

By virtue of the logic basic cell being set up in such a way that it is possible to tap off separately in each case a signal at the output of the first logic function block, a signal at the output of the second logic function block and a signal at the output of the first logic decomposition unit at first to third data signal outputs, these partly processed signals may be provided or fed separately in each case to other components of a more complex circuit. If a logic subfunction such as is generated by each of the logic function blocks from data signals is required elsewhere in such a more complex circuit, then this does not necessitate separate resources. In the same way, separate resources are not necessary if the output signal of the first logic decomposition unit is required at an arbitrary point in the circuit since the output signal can be tapped off separately at the third data signal output. These partly processed signals can be fed to other components of the circuit with low outlay. The tapping off of output signals of the logic function blocks which simultaneously serve as input signals of the first logic decomposition unit thus enables an optimized utilization of logic resources and leads to a high degree of flexibility and also a small required chip area.

Consequently, the logic basic cell according to the invention and a logic basic cell arrangement formed on the basis thereof make it possible simultaneously to reduce logic functions of high complexity to logic functions of lower complexity for the purpose of better processability and to tap off logic intermediate results at the outputs of the individual components of the logic basic cell separately for provision to other resources. The signals at the three data signal outputs can thus be tapped off at external terminals of the logic basic cell.

Furthermore, a logic overall function which is e.g. very complicated or depends on a large number of input signals can be divided, by means of the logic basic cell according to the invention, into a plurality of logic subfunctions which are less complicated or depend on a smaller number of input signals, it being possible for the logic subfunctions to be realized by different logic basic cells. As a result, a complex logic basic function is reduced to a plurality of simpler logic subfunctions, which can be realized in a modular interconnection of individual logic basic cells.

To put it another way, according to the invention, by means of an interconnection of logic basic cells with one another, an arbitrary complicated logic overall function that is dependent on a multiplicity of input signals can be reduced to simpler logic subfunctions of a smaller number of inputs by virtue of a preferably semiconductor-technological circuit architecture being created on the basis of Boolean logic.

The basic cell realizes a good mappability both of simple and of more complex logic functions without generating an unnecessary overhead. Consequently, a partitioning-improved or partitioning-optimized basic cell that can be used in an FPGA or a structured ASIC has clearly been created.

Consequently, a logic basic cell is provided which enables an uninterrupted improved partitionability for logic functions of n inputs, a high degree of flexibility and user-friendliness being achieved by means of the isolated tappability of partly processed signals at outputs of the logic function blocks. If a function of n inputs can be realized in precisely one logic basic cell, the invention makes it possible to realize a function of (n+1) inputs with at most two logic basic cells or a function of (n+i) inputs with at most 2.sup.i logic basic cells. In this case, a logic basic cell is preferably realized in such a way that its combinatorics is likewise scaled. A basic cell with a combinatorial function of n inputs can also be constructed within the basic cell from two functions of (n-1) inputs, which two functions are realized by means of the two logic function blocks.

It should be noted that the logic results of the logic subfunctions of the logic function blocks are not only provided to inputs of the first logic decomposition unit, rather it is also possible to independently tap off output signals in accordance with these logic subfunctions. Consequently, such subfunctions are also available individually.

The selection of a logic subfunction (for example AND combination, OR combination, exclusive-OR combination, NAND combination, NOR combination, exclusive-NOR combination, etc.) of a logic function block is preferably effected by means of configuration of the logic function configuration input or inputs of the respective logic function block. In the circuitry realization, a logic function block may have transistors connected up to one another, in which case, by means of the application of logic function signals to the logic function configuration inputs of the logic function blocks, specific paths within the transistors can be activated, so that input signals can be processed in accordance with these selected paths in accordance with a predeterminable logic subfunction.

An explanation is given below of the logic basic cell on the basis of Boolean logic. Clearly, a statement of Boolean logic is used as a basis for a circuit architecture which is expressed in the logic basic cell according to the invention.

A function f(a.sub.n, a.sub.n-1, . . . , a.sub.0) of n+1 input signals a.sub.i can be reduced, in accordance with Boolean logic, to two functions f.sub.0, f.sub.1 of in each case n input signals a.sub.i as follows: f(a.sub.n, a.sub.n-1, . . . , a.sub.1, a.sub.0)= a.sub.nf.sub.0(a.sub.n-1, . . . , a.sub.0)a.sub.nf.sub.1(a.sub.n-1, . . . , a.sub.0) (2)

in this case, a.sub.n is the logic inverse of the data signal a.sub.n. For the case n=2, that is to say for a function of n+1=3 input signals, the logic overall function f as a function of three input signals is thus reduced to two logic subfunctions f.sub.0 and f.sub.1 with two input signals. Each of the logic subfunctions f.sub.0, f.sub.1 can be realized by one of the logic function blocks of a logic basic cell.

For the special case of n+1=4 input signals, using equation (2), the logic overall function can be reduced to two functions of three input signals, it being possible for each function of three input signals once again to be divided into two logic subfunctions with two inputs by applying equation (2) again. In other words, a logic overall function of four data signals can be decomposed into four logic subfunctions which can be realized by four logic function blocks, that is to say two logic basic cells according to the invention. This consideration can be continued for an arbitrary number of input signals; by way of example, the realization of a logic overall function of five data signals requires 2*2*2=8 logic function blocks, that is to say four logic basic cells having in each case two logic function blocks. These considerations illustrate the modular construction of the logic basic cell arrangement according to the invention.

In the case of the logic basic cell, the first data signal input may be coupled to the third data signal input and/or the second data signal input may be coupled to the fourth data signal input. In accordance with this interconnection, two data signals are processed in accordance with the first logic subfunction by the first logic function block and the same two data signals are processed in accordance with the second logic subfunction by the second logic function block. The combination of the output signals of the two logic function blocks then enables the generation of a more complex logic processing of the two data signals with additional data signals.

In accordance with a preferred configuration of the invention, a second logic decomposition unit is provided, the control input of which is coupled to a sixth data signal input of the data signal inputs, the first data input of which is coupled to a seventh data signal input of the data signal inputs and the second data input of which is coupled to an eighth data signal input of the data signal inputs. A logic basic cell in accordance with the configuration described thus has at least eight data signal inputs.

A logic basic cell in accordance with this development thus contains an additional second logic decomposition unit that can be electrically decoupled from the remaining components of the logic basic cell. The second logic decomposition unit forms a free resource which (depending on the interconnection, for example using the output signal of the first logic decomposition unit or using signals which are provided to the logic decomposition unit from other logic basic cells of the logic basic cell arrangement according to the invention) can be used for arbitrary logic tasks in a user-defined manner.

One aspect of the invention is the coupling of two logic function blocks and the first logic decomposition unit of a first logic basic cell to a second logic decomposition unit of a second logic basic cell.

Logic functions of arbitrary complexity can be constructed with only little additional outlay. Combinatorial resources that are not used or not necessary for realizing a logic overall function remain free and can be allocated to other functions. In other words, the interconnection of logic basic cells in order to form a logic basic cell arrangement makes it possible for such components of the logic basic cells which are not required for a specific application not to be left unexploited and unutilized but rather to be concomitantly used for other functions of a circuit. This enables an optimum utilizability of the resources of a logic circuit. Consequently, a very good capacity utilization of the logic combinatorics is achieved in conjunction with very high scalability.

To put it another way, the logic basic cell is constructed from the interconnected two logic function blocks and the first logic decomposition unit, on the one hand, and also the second logic decomposition unit, on the other hand. These two subblocks of the logic basic cell may be provided such that they are electrically insulated from one another. As seen from its external consideration, the logic basic cell has a multiplicity of data inputs which are provided as inputs of the logic function blocks and of the logic decomposition unit.

Furthermore, the logic basic cell has at least four, preferably exactly four, independent combinatorial outputs and two combinatorial outputs that are negated with respect to two independent combinatorial outputs, and at least one sequential output. The four independent combinatorial outputs correspond to the outputs of the two logic decomposition units and the outputs of the logic function blocks. The negated combinatorial outputs are the additional negated outputs of the logic decomposition units. The sequential output may optionally be one of the six combinatorial outputs that have been delayed in a register by a clock cycle. Of course, instead of one register it is also possible to use two, three, four, five or six registers which can be occupied by the combinatorial output signals in any desired manner.

Therefore, a universally usable component has clearly been created, which is merely fed data signals to be processed externally, which is defined in accordance with the interconnection within the logic basic cell and between a plurality of logic basic cells of a logic basic cell arrangement.

One important aspect of the invention may be seen in the fact that a (free) logic decomposition unit of a logic basic cell can be used jointly with logic blocks from other logic basic cells, whereby the logic complexity that can be achieved is increased. Other components of the logic basic cell of the logic decomposition unit connected up in this way can then be incorporated into other logic functions, so that a high degree of design freedom is combined with an efficient and space-saving utilization of the resources of the logic basic cell.

At least one of the logic function blocks of the logic basic cell may have a first signal path having a plurality of transistors of a first conduction type, the signal path being coupled to at least a portion of the data signal inputs of the respective logic function block, it being possible for the transistors to be connected up to one another in such a way that they realize the logic subfunction which can be realized by the respective logic function block from all the possible logic subfunctions for combining the data signals present at the respective logic function block, so that an output signal representing the result of the logic subfunction is provided. Furthermore, at least one of the logic function blocks may have a second signal path having a plurality of transistors of a second conduction type complementary to the first conduction type, the signal path being coupled to at least a portion of the data signal inputs of the respective logic function block, it being possible for the transistors to be connected up to one another in such a way that they realize an inverse logic subfunction with respect to that of the transistors of the first signal path from all the possible logic subfunctions for logically combining the two data signals, so that an output signal representing the result of the logic subfunction is provided.

In accordance with this configuration, a universally configurable logic cell is used for a logic function block, by means of which logic cell data signals which can be provided at the data signal inputs can be combined with one another in accordance with a predeterminable logic function. The transistors of the first conduction type (for example n-MOS transistors or p-MOS transistors) and the transistors of the second conduction type (for example p-MOS transistors or n-MOS transistors) may be realized e.g. using CMOS technology. In the case of this configuration of the logic function blocks, neither look-up tables nor gate arrangements are necessary for realizing an arbitrary logic basic function. With the transistor network which is thereby provided and is formed from the two signal paths with mutually complementary transistor types, it is possible, by means of predetermining the interconnection of the transistors, to realize any arbitrary logic function of all the possible logic functions for the respective number of input signals. Mathematically, the product terms of a logic function that result from the Boolean logic may be formed as series paths of the n-channel transistors or p-channel transistors. In each case mutually exclusive product terms can be combined using a switch. This configuration of the logic function blocks is distinguished by high interference immunity. Furthermore, only a small chip area is necessary for realizing the logic operation, and this is in conjunction with a very low power loss and a high switching speed. Moreover, high interference immunity and flexible scalability for an arbitrary number of data inputs and data outputs are made possible.

In accordance with one configuration of the invention, at least one of the logic function blocks may be formed in the structure of a programmable logic device (PLD), a field-programmable gate array (FPGA), a mask-programmed application-specific integrated circuit (mASIC), as a logic gate or an arrangement of a plurality of logic gates or as a look-up table. According to the invention, it is possible, in principle, to choose any desired configuration for the logic function blocks. In the case of the configuration of a logic function block as a look-up table, it is possible, by way of example, to implement the architecture disclosed in [1] in the logic basic cell of the invention. In the case of the realization of a logic function block as a mask-programmed application-specific integrated circuit or as "structured ASIC", it is possible to realize a desired logic subfunction of a logic function block by means of the hardwiring of transistors within the logic function block.

In other words, using vias or other coupling elements, it is possible to select a specific signal path or a plurality of signal paths within the transistor arrangement of such a "structured ASIC", whereby a fixed logic function is assigned to the logic function block.

The logic subfunction which can be realized may be predetermined for the respective logic function block in an invariable fashion at the at least one logic function configuration input. In accordance with this configuration, the logic function block always fulfills the logic subfunction that is fixedly and invariably allocated to it since the logic subfunction is fixedly set by means of the application of predetermined signals (or operating voltages) at the logic configuration inputs. The predetermined logic subfunction may also be realized in a hardwired fashion by means of short-circuiting or corresponding hardware coupling of the transistors of the logic function block. Predetermined electrical potentials (e.g. operating voltage, ground potential) can then be applied via one or a plurality of terminals of the logic function block to the transistors that are connected up to one another in a defined manner.

In the case of a fixedly predetermined logic subfunction of a logic function block, a storage device coupled to the at least one logic function configuration input may be provided, in which storage device the information for predetermining the logic subfunction which can be realized can be stored. Consequently, such a storage device can store a data word in which the logic subfunction of the logic function block is coded, for example as a binary data word.

As an alternative to the configuration described, the logic subfunction which can be realized may be predetermined for the respective logic function block in a variable fashion by means of a signal which can be applied at the at least one logic function configuration input. In the case of this configuration of a logic function block, the latter can implement any desired logic function which is predetermined for the logic basic cell by means of an electrical potential that is variable (for example with respect to time) at control inputs of transistors within the logic function block. In this scenario, the logic function block can be connected up as a variable logic component in the superordinate logic basic cell or the logic basic cell arrangement that is superordinate thereto, which enables a flexible circuit architecture.

The logic basic cell is preferably set up for processing digital data signals which have a logic value "1" or "0".

Furthermore, the logic basic cell may be provided with at least one register which is connected downstream of the first and second logic function blocks and the first and second logic decomposition unit and serves for tapping off signals which are provided at outputs of the logic basic cell. In order to enable signals to be applied externally to the logic basic cell or signals to be tapped off externally from the logic basic cell, a register (for example using flip-flops) is preferably connected downstream of the outputs of the logic decomposition unit, thereby clearly creating a register-to-register path between input signals and output signals, whereby a standardized circuit design is facilitated.

The logic basic cell arrangement having logic basic cells is described in more detail below. Configurations of the logic basic cell also hold true for the logic basic cell arrangement having logic basic cells, and vice versa.

In the case of the logic basic cell arrangement, the output of the first logic decomposition unit of a first logic basic cell is preferably coupled to the first data input of the second logic decomposition unit of a second logic basic cell. Furthermore, the output of the first logic decomposition unit of a third logic basic cell may be coupled to the second data input of the second logic decomposition unit of the second logic basic cell.

In accordance with this configuration, a logic function of four variables can be processed using logic function blocks together with a first logic decomposition unit of two logic basic cells and a second logic decomposition unit of a third logic basic cell. Each logic function block within the first and second logic basic cells can process a function of two variables, a processing of a logic subfunction of three variables being made possible by means of further processing of the output signals of the two logic function blocks by means of the associated first logic decomposition unit in each of the first and second logic basic cells in accordance with equation (2). In accordance with the interconnection described, the output signals of the function of in each case three variables of the first and second logic basic cells are brought together in the data inputs of the second logic decomposition unit of the third logic basic cell, so that a logic function of at least four variables can be processed. This arrangement of the first to third logic basic cells may be interpreted as a basis structure of a logic basic cell arrangement, it being possible for a plurality of such basis structures in turn to be connected up to one another in order to combine even more complex logic functions, i.e. logic functions with five or more data signals, with one another.

At least one data input of the second logic decomposition unit of the first and/or of the third logic basic cell may be free of a coupling to other logic cells. Furthermore, the first and/or the second logic function block and/or the first logic decomposition unit of the second logic basic cell may be free of a coupling to other logic basic cells. At least a portion of the at least one logic function block and/or of the logic decomposition unit free of a coupling to other logic basic cells may be connected up to an additional circuit in such a way that this at least one component can contribute to the functionality of the additional circuit. That is to say that of the first and second and third logic basic cells, in each case only a portion of the components can be used for implementing the intended logic function, whereas the remaining resources are not required for the logic function and are therefore made available for other applications. To put it another way, for combining the output signals of the first logic decomposition units of the first and second logic basic cell, it is possible to use a free second logic decomposition unit of a third logic basic cell, the remaining blocks of which remain free of a logic functionality. The second logic decomposition units of the first and second logic basic cells likewise remain free of a logic function in the context of the logic basic cell arrangement and can be used for other applications. Improved or optimized utilization of resources is thereby made possible.

The logic basic cell and the logic basic cell arrangement may be realized as an integrated circuit.

One aspect of the invention may be seen in the fact that a logic basic cell is set up or connected up in such a way that it implements the Shannon decomposition described above with reference to equation (2), but supplemented by at least one additional decomposition (e.g. an iterative decomposition or a disjoint decomposition), with the result that the flexibility of the basic cell according to the invention is significantly increased by the addition of at least one additional decomposition.

An uninterrupted partitionability of a logic function of n inputs is made possible with the at least two decompositions that are made possible in the basic cell according to the invention, namely with the Shannon decomposition and at least one additional decomposition. If a function of n inputs (i.e. a function that depends on n data signals to be combined in accordance with a predeterminable logic function, e.g. AND combination) can be realized in a basis cell, it is possible according to the invention to realize a function of at least (n+1) inputs with two basis cells and a function of at least (n+i) inputs with 2' basis cells. A basis cell is configured in such a way that its combinatorics are likewise scaled. A basic cell having a combinatorial function of n inputs can be constructed from two function blocks of (n-1) inputs, it being possible for these subfunctions also to be available individually. In this way, logic functions of arbitrary complexity can be constructed virtually without any additional outlay. Unused combinatorial resources remain free and can be allocated to other functions. The invention enables virtually an optimum capacity utilization of the combinatorics of a logic cell array. Combinatorics and registers of a cell can be used jointly, but also wholly independently of one another, which further increases the flexibility of the cell according to the invention.

One aspect of the invention is based on the decomposition of logic functions. Such a decomposition may be realized in an sASIC basic cell with maximum flexibility in the construction of logically complex functions.

In order to realize a logic function, that is to say in order to implement a logic combination of n data signals for forming an output signal, according to the invention a decomposition of the logic function into a plurality of simpler logic subfunctions with a lower degree of complexity is performed such that the composition of the logic subfunctions as a whole realizes the logic function. The manner of the decomposition comprises, according to the invention, not only the Shannon decomposition in accordance with equation (1), but at least one additional decomposition which is more favorable than the Shannon decomposition for the realization of some logic functions. Depending on the logic function that is to be realized in the specific case of application, it is then possible to resort selectively to the resources of the Shannon decomposition unit and/or the unit for realizing the at least one additional decomposition, depending on whether e.g. a particularly space-saving or a particularly fast or resource-preserving configuration is striven for.

The logic basic cell according to the invention is provided with a Shannon decomposition unit which can be used to reduce a function f of n+1 variables into two subfunctions f.sub.1 and f.sub.0 which in each case depend only on n variables. This principle corresponds to equation (1) in mathematical notation.

The two functions f.sub.1, f.sub.0 can be interpreted as a mapping IB.sub.n.fwdarw.IB since their definition range has the dimensionality n.

The Shannon decomposition, which, according to the invention, is realized by means of the Shannon decomposition unit, provides a solution for the general case which can be applied at any time and enables a complex logic function of n+1 variables to be reduced to a plurality of logic subfunctions with a smaller number of variables. If however--as in accordance with the prior art--only the Shannon decomposition were offered as sole decomposition in a logic basic cell, it may happen for specific applications that a sufficiently short gate transit time or a sufficiently small number of gates is not made possible. Such a short gate transit time or a minimal number of gates is advantageous, however, in specific applications. The Shannon decomposition alone, however, yields circuits having the depth O(n) and may accordingly yield suboptimum results in many cases.

For this reason, the invention provides the logic basic cell not only with a Shannon decomposition unit for realizing the Shannon decomposition described above, but additionally with at least one unit for realizing an additional decomposition of a logic function into a plurality of logic subfunctions. Depending on whether e.g. the gate transit time is intended to be minimized or whether the number of gates required is intended to be minimized, e.g. an iterative decomposition or a disjoint decomposition may be used as additional decomposition. However, any other mathematical decomposition by means of which a logic function can be reduced to less complex logic functions is also possible.

The iterative decomposition can be represented by equation (3): f: IB.sup.n+1.fwdarw.IB: f(a.sub.n, a.sub.n-1, . . . , a.sub.1, a.sub.0)=f.sub.0(f.sub.1(Q), R) (3)

where: Q, R.OR right.(a.sub.n, a.sub.n-1, . . . , a.sub.1, a.sub.0)Q.andgate.R=0 (4)

In equations (3), (4), f represents a function of n+1 variables a.sub.n, a.sub.n-1, . . . , a.sub.0 which is reduced to a function f.sub.0, which in turn depends on a function f.sub.1(Q) and on R. Q and R are in each case sets, each of which has one or a plurality of the variables a.sub.i where i=0, 1 . . . , n as elements.

The following relationship holds true: f.sub.0: IB.sup.|R|+1.fwdarw.IB und f.sub.1: IB.sup.|Q|.fwdarw.IB (5)

The recursive application of the iterative decomposition clearly yields circuits having a pipeline-like structure and, given a depth of O(n), requires only n gates. The iterative decomposition capability is not a general property of a Boolean function.

In a circuitry realization, an iterative decomposition may be realized by virtue of the fact that an output of a logic function block in which a first logic subfunction is realized is coupled for example to the input of a multiplexer, the output of which may then be coupled to a second logic function block. In this case, the second input of the multiplexer leads to a data input and the third input of the multiplexer controls the selection between the data signal input and the output of the first logic function block. Using the iterative decomposition, it is possible, in particular, to keep down the number of gates required.

The invention's combination of iterative decomposition with Shannon decomposition ensures that even in a scenario in which a logic function is not accessible to an iterative decomposition or for which an iterative decomposition is not desired or is not advantageous, a realization which is always possible can be effected in any event by means of the Shannon decomposition.

A description is given below, with reference to equations (6), (7), of a disjoint decomposition as a further example of a decomposition which can be realized in addition to the Shannon decomposition in the logic basic cell according to the invention. The disjoint decomposition is based on the decomposition in accordance with equation (6): f: IB.sup.n+1.fwdarw.IB: f(a.sub.n, a.sub.n-1, . . . , a.sub.1, a.sub.0)=f.sub.0(f.sub.1(Q.sub.1), f.sub.2(Q.sub.2)) (6)

where Q.sub.1.orgate.Q.sub.2=(a.sub.n, a.sub.n-1, . . . , a.sub.1, a.sub.0)Q.sub.1.andgate.Q.sub.2=0 (7)

In the case of the disjoint decomposition, a function f of n+1 variables a.sub.i is reduced to a function f.sub.0, which depends on less complex subfunctions f.sub.1, f.sub.2, where f.sub.1 depends on one subset of the variables a.sub.i and f.sub.2 depends on another subset of the variables a.sub.i.

If the disjointness is not assumed, then any Boolean function can be decomposed in accordance with (6), (7). The requirement of disjointness makes it possible, however, to construct circuits having the depth O(log n), which leads to a particularly short gate transit time.

Clearly, the invention's architecture of the logic basic cell makes use of the concept that with the provision of a Shannon decomposition and at least one other additional decomposition (in particular a disjoint decomposition and/or an iterative decomposition), the flexibility in the circuit design can be significantly increased, and parameters such as gate transit time and number of gates can be optimized. It is possible to reuse complete logic functions or individual parts thereof in other logic functions, for which reason every combinatorial path in a logic basic cell can be provided as an output thereof. By means of a structural multiplexer, an arbitrary combinatorial path within a basic cell can be connected to the input of a cell-internal register. In order to be able to operate registers and combinatorics independently of one another, it is possible to provide a combinatorial dummy path to the register, which can be switched via the same structural multiplexer. In this way, it is possible e.g. to connect the registers of adjacent cells to form a shift register without taking up the combinatorial resources of the cells involved.

The at least one additional decomposition in the logic basic cell may be an iterative decomposition. This circuitry realization is based in particular on the mathematical repres