Abstract:
A product-term array that may allow for the implementation of product terms requiring less silicon area than conventional designs. The product terms may also have a shorter propagation delay when compared with conventional designs. A multiplexer, which may be programmed with a configuration bit or signal, may select the polarity of an input signal to the product-term array. Duplicating a number of the initial inputs to the array may accommodate particular design constraints that may require both polarities (i.e., both positive and negative) of a given signal or set of signals. Even with the duplication of certain inputs, the total number of product-term inputs to the array will generally be reduced when compared with conventional designs, that duplicate the polarity of every input internally to the array.

Description:
FIELD OF THE INVENTION 
     The present invention relates to product-term arrays generally and, more particularly, to reduced area product-term arrays. 
     BACKGROUND OF THE INVENTION 
     A complex programmable logic device (CPLD) has a number of logic blocks each containing a number of individual programmable macrocells. CPLDs can be easily programmed by engineers in the field and later erased and re-programmed. This allows the designer to make any changes to their system very late in the development cycle, thus realizing a competitive design advantage. 
     Product-term arrays inside a CPLD are created by providing both a positive and negative polarity of a number of signals that are presented as inputs to the product-term array. FIG. 1 illustrates a product-term array  10  having such a configuration. The product-term array  10  generally comprises a number of inputs  12   a-   12   n  and a number of outputs  14   a-   14   n.  Each of the inputs  12   a-   12   n  is presented to one of a number of buffers  16   a-   16   n . Each of the buffers  16   a-   16   n  presents both a true and a complement output of the signal received at the respective input  12   a-   12   n.  For example, the buffer  16   a  has a true output  18   a  and a complement output  20   a.  The outputs  18   a-   18   n  and  20   a-   20   n  are presented to a number of product-term input lines  22   a-   22   n  and  24   a-   24   n , respectively. The product-term input lines  22   a-   22   n  and  24   a-   24   n  are extended in a vertical direction by a number of vertical lines  30   a-   30   n . The vertical lines  30   a-   30   n  generally cross a number of product-term lines  32   a-   32   n,  which are generally presented to a number of logic gates  34   a-   34   n.  The logic gates  34   a-   34   n  generally present signals to the outputs  14   a-   14   n.    
     The disadvantages of providing both the positive and negative polarities (i.e., the true and complement signals) of each input signal  12   a-   12   n  include (i) an increased area needed to implement the outputs  22   a-   22   n  and  24   a-   24   n  for each of the buffers  16   a-   16   n  and (ii) longer overall propagation delays due to the increased length of the product-term lines  32   a-   32   n.  By increasing the length of the product-term lines  32   a-   32   n,  additional silicon die area is required. An increased capacitance on the product-term lines  32   a-   32   n  and the product-term input lines  22   a-   22   n  (and  24   a-   24   n ) increases the propagation delays through the product-term array  10 . 
     SUMMARY OF THE INVENTION 
     The present invention concerns a product-term array that may allow for the implementation of product terms requiring less silicon area than conventional designs. The product terms may also have a shorter propagation delay when compared with conventional designs. A multiplexer, which may be programmed with a configuration bit or signal, may select the polarity of an input signal to the product-term array. Duplicating a number of the initial inputs to the array may accommodate particular design constraints that may require both polarities (i.e., both positive and negative) of a given signal or set of signals. Even with the duplication of certain inputs, the total number of product-term inputs to the array will generally be reduced when compared with conventional designs that duplicate the polarity of every input internally to the array. 
     The objects, features and advantages of the present invention include providing a product-term array that (i) reduces the silicon area required for implementation, (ii) reduces the propagation delays through the product-term array, (iii) provides a similar logic capability as a conventional product-term array, and (iv) allows AND-terms to be created from signals or inputs to the array. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     These and other objects, features and advantages of the present invention will be apparent from the following detailed description and the appended claims and drawings in which: 
     FIG. 1 is a circuit diagram illustrating a conventional product-term array; 
     FIG. 2 is a circuit diagram of a product-term array illustrating a preferred embodiment of the present invention; 
     FIG. 3 is a circuit diagram of a product-term array illustrating an alternate embodiment of the present invention; 
     FIG. 4 is a circuit diagram of a product-term array illustrating a second alternate embodiment of the present invention; and 
     FIG. 5 is a block diagram illustrating the product-term array of the present invention implemented in the context of a programmable logic device or complex programmable logic device (CPLD). 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     Referring to FIG. 2, a circuit diagram of a product-term array  100  is shown in accordance with a preferred embodiment of the present invention. The product-term array  100  includes a number of inputs  102   a-   102   n,  a number of outputs  104   a-   104   n  and a number of multiplexers  106   a-   106   n.  Each of the multiplexers  106   a-   106   n  generally receives one of a number of true inputs  108   a-   108   n  (e.g., inputs having a positive polarity compared with the inputs  102   a-   102   n ) and one of a number of complement inputs  110   a-   110   n  (e.g., inputs having a negative polarity when compared with the inputs  102   a-   102   n ). The inputs  108   a-   108   n  generally have a complement polarity to the inputs  110   a-   110   n.  The multiplexers  106   a-   106   n  may each be connected to one of a number of product-term input lines  112   a-   112   n  that may each be extended by one or more of a number of vertical lines  114   a-   114   n.  A number of product-term lines  120   a-   120   n  generally cross the vertical lines  114   a-   114   n  and may or may not provide an electrical connection. Each of the product-term lines  120 - 120   n  are generally presented to one of a number of gates (or product terms)  122   a-   122   n.  The gates  122   a-   122   n  generally present the outputs  104   a-   104   n.    
     The multiplexers  106   a-   106   n  also receive a configuration input (not shown) that may select between either the inputs  108   a-   108   n  or the inputs  110   a-   110   n.  Each of the multiplexers  106   a-   106   n  may have a unique configuration bit. As a result, each of the multiplexers  106   a-   106   n  may provide independent polarity control of the signals presented to the product-term input lines  112   a-   112   n . Since a multiplexer  106   a-   106   n  is generally provided for each of the inputs  102   a-   102   n  presented to the product-term array  100 , either the positive or negative polarity of the input signal may be propagated into the product-term array  100 . An example of such a polarity selection multiplexer may be found in co-pending U.S. application Ser. No. 08/626,043, which is hereby incorporated by reference in its entirety. The additional delay added by the multiplexers  106   a-   106   n  is generally less than or equal to the delay provided by the buffers  16   a-   16   n  described in connection with FIG.  1 . 
     In general, for a given number of inputs  102   a-   102   n,  half the number of product-term input lines  112   a-   112   n  may be required when compared with the example described in connection with FIG.  1 . To accommodate the use of both a positive and negative polarity on the single product-term input lines  112   a-   112   n,  additional inputs to the product-term array  100  may be provided. For example, if both polarities of a particular signal are required, the signal may be presented (by the programmable interconnect matrix to be described in connection with FIG. 5) to both the inputs  102   a  and  102   b.  In such an example, the multiplexer  106   a  may present the true version of the input to the product-term input line  112   a,  while the multiplexer  106   b  may present the complement version of the signal to the product-term input line  112   b.  Software is generally implemented to route signals requiring only one polarity to one of the inputs  102   a-   102   n  and to route signals requiring both polarities to two of the inputs  102   a-   102   n.  The software may comprise a medium that stores a series of instructions used to route the opposite polarity signals to the inputs  102   a-   102   n.  For one embodiment, the software may be stored in a RAM including SRAM, DRAM, VRAM or other types of RAM memory. For another embodiment, the software may be stored in FLASH memory. For another embodiment, the software may be accessed by a microprocessor, a microcontroller, etc. The number of product terms  122   a-   122   n  presented to the outputs  104   a-   104   n , the number of product-term lines  120   a-   120   n  and the number of inputs  102   a-   102   n  may each be individually adjusted (e.g., increased or decreased) to meet the design criteria of a particular implementation of a product-term array  100 . 
     The reduction of both the number of lines  114   a-   114   n  and the size of the product-term input lines  112   a-   112   n  may reduce the silicon area required to implement the product-term array  100 . As a result, the overall cost in manufacturing a device containing the product-term array  100  may be reduced. In addition, since there is less capacitance on both the product-term input lines  112   a-   112   n  and the product-term lines  120   a-   120   n,  the overall delay through the product-term array  100  may be reduced. 
     Design examples that may benefit from the product-term array  100  include multiplexers, shift registers, counters, state machines or other logic functions. When implementing a multiplexer, only one polarity of the input lines is generally required. For example, a 16-to-1 multiplexer may require one polarity for 16 signals and may require two polarities for only the four selection signals. As a result, the multiplexer may be implemented as follows:              x   =                    a   —        0   *     /     s   —          3   *     /     s   —          2   *     /     s   —          1   *     /     s   —          0     +                                  a   —        8   *     s   —        3   *     /     s   —          2   *     /     s   —          1   *     /     s   —          0     +                                  a   —        4   *     /     s   —          3   *     s   —        2   *     /     s   —          1   *     /     s   —          0     +                                  a   —        12   *     s   —        3   *     s   —        2   *     /     s   —          1   *     /     s   —          0     +                                  a   —        2   *     /     s   —          3   *     /     s   —          2   *     s   —        1   *     /     s   —          0     +                                  a   —        10   *     s   —        3   *     /     s   —          2   *     s   —        1   *     /     s   —          0     +                                  a   —        6   *     /     s   —          3   *     s   —        2   *     s   —        1   *     /     s   —          0     +                                  a   —        14   *     s   —        3   *     a   —        2   *     s   —        1   *     /     s   —          0     +                                  a   —        1   *     /     s   —          3   *     /     s   —          2   *     /     s   —          1   *     s   —        0     +                                  a   —        9   *     s   —        3   *     /     s   —          2   *     /     s   —          1   *     s   —        0     +                                  a   —        5   *     /     s   —          3   *     s   —        2   *     /     s   —          1   *     s   —        0     +                                             a   —        13   *     s   —          3   **     s   —          2   *     /     s   —          1   *     s   —        0     +                                  a   —        3   *     /     s   —          3   *     /     s   —          2   *     s   —        1   *     s   —        0     +                                  a   —        11   *     s   —        3   *     /     s   —          2   *     s   —        1   *     s   —        0     +                                  a   —        7   *     /     s   —          3   *     s   —        2   *     s   —        1   *     s   —        0     +                                a   —        15   *     s   —        3   *     s   —        2   *     s   —        1   *     s   —        0                                  
     Where s — 0, s — 1, s — 2 and s — 3 are the selection signals and a — 0-a — 15 are the input signals, * represents a logical AND function and + represents a logical OR function. 
     Thus, the product-term array  100  of the present invention provides a much more efficient solution to implementing a multiplexer. 
     When implementing a serial shift register, only one polarity for each of the shift register and data bits is generally required. Both polarities are generally only needed for the load signal. Similar to the multiplexer implementation, the present invention provides a more efficient implementation of a shift register with less delay than a conventional product-term array (e.g., the array  10  in FIG.  1 ). 
     When implementing a counter, such as a synchronous counter with a synchronous or asynchronous reset, synchronous enable and load, only the true polarity of the counter and data bits and the appropriate active polarity of the reset, enable and load control signals are generally required. As a result, the product-term array  100  may provide a more efficient implementation of a counter than a conventional product-term array. 
     State machines may require both true and complement state signals. However, when implementing a state machine, the resource limitation is generally found to be in the number of product-terms rather than the number or polarity of inputs. As a result, the present invention may provide a more efficient implementation of a state machine than conventional methods. 
     Referring to FIG. 3, a circuit diagram of a product-term array  100 ′ is shown in accordance with an alternate embodiment of the present invention. The product-term array  100 ′ has similar features as the product-term array  100 . Similar features include the multiplexers  106   a-   106   n,  the inputs  102   a-   102   n  and the outputs  104   a-   104   n.  In addition, the product-term array  100 ′ adds a number of multiplexers  130   a-   130   n.  The multiplexer  130   a  is shown receiving an input  132   a  that may receive the signal from the input  102   a  and an input  134   a  that may receive a signal from the input  102   b.  As a result, the multiplexer  130   a  may present the true version of either the signal received from the input  102   a  or  102   b  to the input product-term line  112   f.  Similarly, the multiplexer  130   b  has an input  132   b  that may receive a signal from the input  102   c  and an input  134   b  that may receive a signal from the input  102   d.  The multiplexer  130   b  may present the true version of the signal received at the input  102   c  or  102   d  to the product-term input line  112   g.  The multiplexer  130   n  may have an input  132   n  that may receive the signal presented at the input  102   a  and an input  134   n  that may receive the signal presented at the input  102   n.  The multiplexer  130   n  may present the true signal of the input  102   a  or the true version of the signal  102   n  to the product-term input line  112   n.  The particular signals presented to the multiplexers  130   a-   130   n  are for illustrative purposes only and may be adjusted accordingly to meet the design criteria of a particular implementation. For example, more than two signals may be presented to one or more of the multiplexers  130   a-   130   n.    
     Since the multiplexers  130   a-   130   n  generally receive the true version of the signals received at the inputs  102   a-   102   n,  a reduced number of inputs  102   a-   102   n  may result in design applications that require both a true and complement of an input signal. Specifically, if the multiplexer  130   a  presents the true version of the input  102   a,  the multiplexer  106   a  may present the complement version of the signal at the product-term input line  112   a.  The product-term array  100  reduces the number of inputs  102   a-   102   n  and may be useful in design applications that require both the true and complement of a smaller number of input signals. Since the multiplexers  130   a-   130   n  each present only a single signal to a respective one of the product-term input lines  112   f-   112   n,  the overall number of product-term input lines  112   a-   112   n  may still be minimized, similar to the product-term array  100  described in connection with FIG.  2 . 
     Referring to FIG. 4, a circuit diagram of a product-term array  100 ″ is shown in accordance with an alternate embodiment of the present invention. The product-term array  100 ″ has similar features as the product-term array  100 ′. The similar features include the multiplexers  106   a-   106   n , the inputs  102   a-   102   n  and the outputs  104   a-   104   n . In addition, the product-term array  100 ″ adds a number of buffers  140   a-   140   n.  The buffer  140   a  is shown receiving an input  142   a  that may receive the signal from an input  144   a.  The buffer  140   a  may present an output  146   a  to an input product-term line  149   b  that may represent a true version of the signal received at the input  144   a  or an output  148   a  to an input product-term line  149   a  that may represent a complement version of the signal received at the input  144   a.  The buffers  140   b-   140   n  have similar connections with one of a number of inputs  144   b-   144   n  and a number of outputs  146   b-   146   n  and  148   b-   148   n.    
     The array  100 ″ may provide flexible solutions where a number of inputs (e.g.,  144   a-   144   n ) require both the true and complement signals. The multiplexers  102   a-   102   n  provide a similar flexibility for signals that require either the true or the complement signals at the product-term input lines  112   a-   112   n.  If a number of signals require both a true and complement signal, the hardwiring of the buffers  140   a-   140   n  may reduce the overall complexity of the array  100 ″. 
     In each of FIGS. 2,  3  and  4 , the letter n is used to represent a variable number of a particular device. For example the number of product-term input lines  112   a-   112   n  may be a variable number of lines. However, each of the devices (e.g., the multiplexers  106   a-   106   n,  the product-term input lines  112   a-   112   n,  the product-term lines, etc.) may be independently varied to meet the design criteria of a particular implementation. 
     Referring to FIG. 5, a block diagram of a programmable logic device  200  is shown implementing the present invention. The programmable device  200  generally comprises a programmable interconnect matrix  202 , a number of input/outputs  204   a  and  204   b , and a number of logic blocks  206   a-   206   n.  A more detailed view of the logic block  206   b  is shown to include a product-term array  210 , a product-term matrix  212  and a macrocell block (or circuit)  214 . The product-term array  210  generally incorporates the features described in connection with FIGS. 2-4 of the present invention. 
     While the invention has been particularly shown and described with reference to the preferred embodiments thereof, it will be understood by those skilled in the art that various changes in form and details may be made without departing from the spirit and scope of the invention.