Semiconductor device manufacturing: process – With measuring or testing – Electrical characteristic sensed
Reexamination Certificate
2001-05-31
2003-04-08
Nelms, David (Department: 2818)
Semiconductor device manufacturing: process
With measuring or testing
Electrical characteristic sensed
C716S030000
Reexamination Certificate
active
06544806
ABSTRACT:
TECHNICAL FIELD
The present invention relates generally to programmable logic devices, and more particularly to computation of truth tables in programmable logic devices.
BACKGROUND ART
Combinational logic functions are basic building blocks of digital electronic circuits. As is well known, any combinational function can be specified as a Boolean logic function of its inputs, and this function can be implemented in a logic circuit. By expressing Boolean logic functions in sum of products (SOP) or product of sums (POS) form, it becomes a straightforward task to implement them with two-stage logic circuits (e.g., AND-OR, NAND-NAND, or NOR-NOR circuits). These two-stage circuits can be classified as product-term or Pterm-based circuits and can be implemented directly by electrically connecting those logic gates that are required to produce a desired function.
Programmable logic arrays (PLAs) are integrated circuits that can include multiple general-purpose product-term cells, which a designer can configure to implement specific combinational logic circuits. PLAs can be mask-based arrays that are permanently configured during semiconductor processing to form application-specific integrated circuits (ASICs). Alternatively, they can be field-programmable, which means that they can be electrically programmed, and reprogrammed with relative ease away from a manufacturing plant. These field-programmable logic devices are known as field programmable gate arrays (FPGAs).
FPGAs are revolutionizing the way digital electronics system designers implement logic. By radically reducing the development costs and the turnaround time for implementing thousands of gates of logic, FPGAs provide new capabilities that affect the semiconductor industry. FPGAs are changing the way digital systems will be designed in the future.
A FPGA typically includes an array of programmable logic blocks that can be programmably interconnected to each other to provide the logic function desired by the digital electronics designer. Each of the programmable logic blocks may be individually programmed to perform any one of a number of different logic functions. The FPGA has configurable routing matrices for coupling the programmable logic blocks together according to a desired configuration. The FPGA also includes configuration memory cells. The configuration memory cells are coupled to the programmable logic blocks for specifying the function performed by each programmable logic block, and to the configurable routing matrices for specifying the coupling of the inputs and the outputs of the programmable logic blocks. Each programmable logic block is coupled to several configuration memory cells. Each configuration routing matrix is coupled to several configuration memory cells. By storing different values in the configuration memory cells, each programmable logic block may be individually programmed as to its function and coupling.
Each programmable logic block and configurable routing matrix includes a plurality of programmable switch elements. The settings of the programmable switch elements define the logic function comprised within each programmable logic block and the coupling of the inputs and the outputs of the programmable logic blocks. The settings of the programmable switch elements are determined by the information stored within the configuration memory cells. Presently, each configuration memory cell corresponds to a particular programmable switch element. To modify the setting of a programmable switch element and thereby modify the logic defined by a logic block, the information within the configuration memory cells must be modified.
FPGAs have several significant advantages over hardware designed for a single specific purpose integrated circuit, such as ASICs. First, FPGAs offer a faster time-to-market. In contrast, ASICs require considerable time for development, testing and prototyping, which potentially delaying of products incorporating them.
Second, FPGAs involve less non-recurring engineering costs. In contrast, ASICs require significant expenses in both design expertise as well as mask design, fabrication costs, etc., that must be amortized over the life of a product.
Third, FPGAs offer flexibility as it can be easily upgraded in the field. On the other hand, an ASIC cannot be cheaply upgraded in the field to correct design defects or to add features.
Fourth, FPGAs provide economy of scale since one FPGA can implement the functionality of many ASICs, thus spreading non-recurring development costs over a larger number of products.
A truth table is often used in digital logic systems to implement a logical function consisting of several inputs signals and one output signal. These truth tables are particularly important in programmable logic devices such as FPGAs where the desired behavior of a hardware circuit is not known at the time the hardware is designed, but instead is configured by the user. FPGAs are becoming increasingly popular as their capacities, i.e., the number of programmable truth tables, increases and their costs decrease.
Since FPGAs contain a large number of truth tables (more than 50,000 at present), it becomes important to be able to map logic equations into truth tables efficiently, especially in runtime reconfigurable systems that use them for accelerating computation, as is done in Firefly or BRASS. In the case of BRASS, it splits an application into multiple pieces, some of which are intended to be executed on a conventional sequential processor and others that are to be executed in reconfigurable hardware. The conventional processor and the reconfigurable hardware work together to implement the entire application, with various pieces of the application mapped to the reconfigurable hardware at the appropriate times. If this is done carefully, the application will run faster than it would if it had been executed solely on the sequential processor.
In the past, the most common way of computing truth tables was to construct and interconnect software data structures representing the logic circuit to be mapped to a truth table, and then to use the data structures to evaluate the output of the logic circuit for all possible combinations of inputs. For example, a truth table with N inputs will have 2
N
bits. Therefore, 2
N
evaluations are required since one evaluation is required for each bit in the truth table.
One problem associated with the prior art method of computing truth tables was that it was complicated and costly to construct and interconnect software data structures to represent the desired logic circuit. The problem worsened when the number of input increased. Another problem associated with the prior art method of computing truth tables was that was slow and time-consuming because each bit had to be evaluated sequentially. As the number of bits increased due to the increase in the number of inputs, so the time it took to evaluate them increased.
There has long been a need therefore, for an improved method for computation of truth tables that is fast, simple and inexpensive.
DISCLOSURE OF THE INVENTION
The present invention provides a method of computing a truth table with N input variables. The method includes: (a) providing N basis tables; (b) associating each one of the N basis tables with a corresponding one of the N input variables; and (c) performing logic operations on the N basis tables using a processor. This provides a method for computation of truth tables that is fast, simple and inexpensive.
The present invention further provides a method for fast computation of truth tables with N input variables. The method includes: (a) providing basis tables having 2
N
bits; and (b) performing logic operations on each bit of each of the basis tables simultaneously. This provides a method for computation of truth tables that is fast, simple and inexpensive.
Furthermore, the method for computation of truth tables according to the present invention is simple and inexpensive because it eliminates the need for allocating and interconnecting data structures to represent a
Hewlett--Packard Company
Hoang Quoc
Nelms David
LandOfFree
Fast computation of truth tables does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast computation of truth tables, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast computation of truth tables will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3101059