Look up table implementation of fast carry arithmetic and exclusive-or operations

Abstract

Look up tables for use in programmable logic devices are modified to facilitate use of those tables to provide adders (including subtracters) and various types of counters. Each look up table is effectively partitioned into smaller look up tables when an adder or counter is required. One portion of the partitioned table is used to provide a sum out signal, while the other portion of the partitioned table is used to provide a fast carry out signal for application to the next stage of the adder or counter. If desired, each logic module including such a look up table may further include logic circuitry for logically combining its normal output with the signal applied to its carry in input to facilitate the provision of wide fan in functions having more inputs than can be accepted by a single logic module.

The invention claimed is: 
     
       1. Programmable logic array apparatus comprising: a plurality of logic modules, each of which has a plurality of inputs and an output, and each of which is programmable to provide to said output an output signal, and each logic module having means to store an individual program for programming said module, the output signal being any of a plurality of logical functions of said inputs, a first of said logic modules including means for selectively receiving the output signal of a second of said logic modules, wherein a first of said plurality of inputs of said first of said logic modules provides an output signal of said second of said logic modules to said means for selectively receiving, and wherein said first logic module is programmable to provide a modified output signal to said output of said first logic module, said modified output signal being an EXCLUSIVE OR function of the unmodified Output signal of said first logic module and said output signal of said second logic module.   
     
     
       2. The apparatus defined in claim 1 wherein each of said logic modules includes means for outputting an arithmetic carry signal distinct from said output signal, wherein each of said logic modules is programmed to perform a place of binary arithmetic on said inputs of each of said logic modules, said apparatus further comprising an interconnection between and distinct from said first and second logic modules, wherein said second logic module includes means for selectively applying either the arithmetic carry signal or the output signal of said second logic module to said interconnection, and wherein said first logic module includes means for applying the signal provided by said interconnection to said means for selectively receiving of said first logic module so that said means for selectively receiving of said first logic module can receive either said arithmetic carry signal or said output signal of said second logic module via said interconnection. 
     
     
       3. The apparatus defined in claim 2 further comprising a second interconnection between and distinct from said first logic module and a third of said logic modules, wherein said first logic module further includes means for selectively applying either said arithmetic carry signal or said output signal of said first logic module to said second interconnection for application to said third logic module via said second interconnection. 
     
     
       4. The apparatus defined in claim 3 further comprising a third interconnection between and distinct from said second logic module and a fourth of said logic modules, wherein said fourth logic module includes means for selectively applying the arithmetic carry signal of said fourth logic module to said third interconnection and wherein said means for selectively applying the output signal of said second logic module to said interconnection is responsive to the signal on said third interconnection and comprises means for selectively tying said third interconnection to a predetermined logical value. 
     
     
       5. The apparatus defined in claim 4 wherein said predetermined logical value is logic 0. 
     
     
       6. Programmable logic array apparatus comprising: a plurality of logic modules, each of which has a means to store an individual program for programming said module, a plurality of inputs, a carry in input, a normal output, and a carry out output, each of said logic modules being programmable to provide to said normal output an output signal being any of a plurality of logical functions of said plurality of inputs and alternatively to perform a place of binary arithmetic on said plurality of inputs and carry in input and to produce as said output signal an arithmetic result signal for that place while also producing a carry out result signal for an adjacent place of said binary arithmetic on the carry out output, and   an interconnection for conveying a signal from the carry out output of a first of said logic modules to the carry in input of a second of said logic modules, said first logic module including means for selectively applying the signal on said normal output of said first logic module to said carry out output of said first logic module, and said second logic module including means for selectively logically combining the signal provided by said interconnection on the carry in input of said second logic module and the signal on the normal output of said second logic module to produce a combined output signal.   
     
     
       7. The apparatus defined in claim 6 wherein said means for logically combining produces a combined output signal which is an EXCLUSIVE OR of the signal on the carry in input of said second logic module and the signal on the normal output of said second logic module. 
     
     
       8. The apparatus defined in claim 7 wherein said second logic module further includes means for selectively applying said combined output signal to the carry out output of said second logic module. 
     
     
       9. The apparatus defined in claim 6 wherein said means for selectively applying the signal on said normal output of said first logic module to the carry out output of said second logic module comprises means for selectively tying the carry in input of said first logic module to a predetermined logical value. 
     
     
       10. The apparatus defined in claim 9 wherein said predetermined logical value is logic 0. .Iadd. 
     
     
       11.  In a programmable look up table apparatus which includes a plurality of programmable data storage cells, each of which produces a cell output signal indicative of the data stored in that cell, and normal selecting circuitry for normally selecting from all of said cell output signals any one of said cell output signals as a normal output signal on a normal output lead of said look up table apparatus, said normal selecting circuitry being responsive to a plurality of input signals such that each of said input signals normally controls a respective one of a plurality of successive selection subcircuits which collectively comprise said normal selecting circuitry, a first of said selection subcircuits selecting one of two mutually exclusive and collectively exhaustive subsets of said cell output signals, and each succeeding selection subcircuit selecting one of two mutually exclusive and collectively exhaustive subsets of the cell output signals selected by the preceding selection subcircuit until a final one of said selection subcircuits produces said normal output signal on said normal output lead, the improvement comprising: a first group of said programmable data storage cells for providing sum out digit signals;   a second group of said programmable data storage cells for providing carry out digit signals;   an auxiliary output lead separate from said normal output lead;   first selection circuitry comprised of a plurality of portions of said selection subcircuits and responsive to a carry in digit signal and two binary digit signals for providing on said normal output lead one of: (1) a sum out digit signal from said first group of said programmable data storage cells, and (2) a carry out digit signal from said second group of said programmable data storage cells when said lock up table apparatus is used to perform addition; and   second selection circuitry comprised of a plurality of portions of said selection subcircuits distinct from said plurality of portions of said selection subcircuits in said first selection circuitry and responsive to said carry in digit signal and said two binary digit signals for providing on the auxiliary output lead the other one of: (1) said sum out digit signal from said first group of said programmable data storage cells, and (2) said carry out digit signal from said second group of said programmable data storage cells when said look up table apparatus is used to perform addition. .Iaddend..Iadd.   
     
     
       12.  The apparatus defined in claim 11 wherein said second selection circuitry further comprises: a first lead connected to a predetermined one of said selection subcircuits, wherein said predetermined one of said selection subcircuits provides on said first lead a first signal indicative of a first logical function of two of said two binary digit signals and said carry in digit signal; and   a second lead connected to said predetermined one of said selection subcircuits, wherein said predetermined one of said selection subcircuits provides on said second lead a second signal indicative of a second logical function of said two of said two binary digit signals and said carry in digit signal. .Iaddend..Iadd.   
     
     
       13.  The apparatus defined in claim 12 wherein said first signal is indicative of the logical NOR of said two of said two binary digit signals and said carry in digit signal and said second signal is indicative of the logical NAND of said two of said two binary digit signals and said carry in digit signal, said second selection circuitry further comprising: a switch circuit for using the remaining one of said two binary digit signals and said carry in digit signal to select one of said first and second signals as said carry out digit signal. .Iaddend..Iadd.   
     
     
       14.  The apparatus defined in claim 13 wherein said two of said two binary digit signals and said carry in digit signal are said two binary digit signals. .Iaddend..Iadd.15. The apparatus defined in claim 11 wherein said look up table apparatus is a four-input look up table for selecting any one of 16 programmable cell output signals stored in said programmable data storage cells as the normal output signal on said normal output lead. .Iaddend..Iadd.16. The apparatus defined in claim 11 further comprising: a register for storing the output signal which appears on said normal output lead; and   a feedback path from said register for providing the output of said register as one of said input signals, wherein said look up table apparatus (10) forms one stage of a counter by accepting the carry in digit from a counter stage of lesser numerical significance as another of said input signals, said look up table apparatus combining the output of said resister and the carry in digit signal to produce a new count value on said normal output lead and the carry out digit signal for application   
     
     
        to a counter stage of greater numerical significance. .Iaddend..Iadd.17. The apparatus defined in claim 16, wherein a predetermined one of said selection subcircuits is divided into mutually exclusive first and second portions, said first portion receiving a first predetermined control signal and said second portion receiving a second predetermined control signal. .Iaddend..Iadd.18. The apparatus defined in claim 17, wherein said apparatus forms one stage of a binary up/down counter, said first predetermined control signal selectively enabling counting and said second predetermined control signal controlling the direction of counting. .Iaddend..Iadd.19. The apparatus defined in claim 18 further comprising: a data switch having an output connected as an input to said final selection subcircuit and first and second data switch inputs, said first data switch input normally receiving one of the two cell output signals from the selection subcircuit preceding said final selection subcircuit and said second data switch input receiving data for loading into said binary up/down counter when said data switch is switched to receive said   
     
     
        data from said second data switch input. .Iaddend..Iadd.20.  The apparatus defined in claim 17 wherein said apparatus forms one stage of a binary up counter, said first predetermined control signal selectively enabling counting and said second predetermined control signal controlling when the apparatus counts and when the apparatus is cleared. .Iaddend..Iadd.21. The apparatus defined in claim 20 further comprising: an AND gate having a gate output connected to said register and first and second gate inputs, said first gate input being connected to said normal output lead and said second gate input being connected to receive said second predetermined control signal, wherein said AND gate provides the signal from said normal output lead to said register during counting and said AND gate provides a logic 0 to said resister when a logic 0 is applied to said second gate input as said second predetermined control signal to clear said counter. .Iaddend.