Electrical computers and digital processing systems: memory – Storage accessing and control – Specific memory composition
Reexamination Certificate
1999-09-02
2002-09-17
Lane, Jack A. (Department: 2185)
Electrical computers and digital processing systems: memory
Storage accessing and control
Specific memory composition
C711S202000, C711S203000
Reexamination Certificate
active
06453382
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to content addressable memories, and more particularly to content addressable memories that have associated circuitry for enabling the memory to be used to perform sum-of-products logic.
Commonly assigned Heile U.S. Pat. No. 6,020,759 (which is hereby incorporated by reference herein in its entirety), shows programmable logic array integrated circuit devices that include large blocks of memory that can be used to perform product term (“p-term”) or sum-of-products logic if desired. Alternatively, these large blocks of memory can be used as random access memory (“RAM”) or read-only memory (“ROM”). Commonly assigned Veenstra et al. U.S. Pat. No. 6,160,419 and Heile U.S. Pat. No. 6,144,573 (both of which are hereby incorporated by reference herein in their entireties), show another possible use of such blocks of memory as content addressable memory. However, both of the just-mentioned references contemplate that significant circuitry will be devoted to providing the output signals that are generally required from a content addressable memory. Such output signals typically include (1) a Match signal for indicating whether or not any data word stored in the content addressable memory has been found to match an applied data word, and (2) address signals (e.g., in binary code) indicating the address of the word in the memory found to match the applied data word. In the Veenstra reference, for example, a second memory block may be programmed to encode addresses and provide a match signal for a first memory block acting as a content addressable memory. In the last-mentioned Heile reference separate match and address encoding circuitry is shown for providing such content addressable memory output signals.
Because it may be desired to provide content addressable memory capability on general-purpose devices (e.g., programmable logic array integrated circuit devices) which may only occasionally need to have such capability, it would be desirable not to have to dedicate too many circuit resources to providing a content addressable memory option.
In view of the foregoing, it is an object of this invention to provide improved content addressable memory capability, especially for multi-purpose circuitry such as programmable logic devices.
It is a more particular object of this invention to make it possible for a block of memory that can operate in p-term mode and that has sum-of-products output capability to be used as a content addressable memory with little or no additional circuitry being required.
SUMMARY OF THE INVENTION
These and other objects of the invention are accomplished in accordance with the principles of the invention by storing the data words to be matched in addresses in a memory block so that when a match with an applied data word is found, the p-term outputs of the memory block can be logically combined by the associated sum-of-products circuitry to provide an encoded “virtual” address of the matching, stored data word. For example, each word to be matched has an associated unique virtual address in the content addressable memory. In order for the sum-of-products circuitry to encode that virtual address, each word to be matched is stored at one or more actual addresses in the memory block. The actual addresses chosen for a data word are such that when that data word matches an applied data word, the resulting one or more p-term output signals from the memory occur within groups that correspond to the code for the virtual address associated with the matching data word. For example, the virtual address code may be binary code. In that case all data words with odd virtual addresses will be stored in actual addresses that produce p-terms that feed sum-of-products circuitry for producing the least significant bit of the encoded virtual address. Continuing with this example, all data words with virtual addresses that need to be encoded using a
1
in the next-to-least-significant place of the binary-encoded virtual address will be stored in actual addresses that produce p-terms feeding sum-of-products circuitry for producing the next-to-least-significant bit of the encoded virtual address. A very small amount of additional circuitry (e.g., one programmable logic module in a programmable logic device that includes the memory block) can be used to form the logical OR of the encoded virtual address signals to provide a Match output signal for the content addressable memory feature.
Further features of the invention, its nature and various advantages will be more apparent from the accompanying drawings and the following detailed description of the preferred embodiments.
REFERENCES:
patent: 3473160 (1969-10-01), Wahlstrom
patent: 3634829 (1972-01-01), Campi et al.
patent: 3849638 (1974-11-01), Greer
patent: 4608629 (1986-08-01), Nagel
patent: 4740917 (1988-04-01), Denis et al.
patent: 4876466 (1989-10-01), Kondou et al.
patent: 4912345 (1990-03-01), Steele et al.
patent: 4975601 (1990-12-01), Steele
patent: 5027011 (1991-06-01), Steele
patent: 5099150 (1992-03-01), Steele
patent: 5121006 (1992-06-01), Pedersen
patent: 5128559 (1992-07-01), Steele
patent: 5144582 (1992-09-01), Steele
patent: RE34363 (1993-08-01), Freeman
patent: 5270587 (1993-12-01), Zagar
patent: 5282163 (1994-01-01), Shibata
patent: 5302865 (1994-04-01), Steele et al.
patent: 5362999 (1994-11-01), Chiang
patent: 5383146 (1995-01-01), Threewitt
patent: 5386155 (1995-01-01), Steele et al.
patent: 5408434 (1995-04-01), Stansfield
patent: 5450608 (1995-09-01), Steele
patent: 5473267 (1995-12-01), Stansfield
patent: 5532957 (1996-07-01), Malhi
patent: 5550782 (1996-08-01), Cliff et al.
patent: 5557218 (1996-09-01), Jang
patent: 5559747 (1996-09-01), Kasamizu-gami et al.
patent: 5574930 (1996-11-01), Halverson et al.
patent: 5611064 (1997-03-01), Maund et al.
patent: 5689195 (1997-11-01), Cliff et al.
patent: 5809281 (1998-09-01), Steele et al.
patent: 5815726 (1998-09-01), Cliff
patent: 5909126 (1999-06-01), Cliff et al.
patent: 5946704 (1999-08-01), Yoneda et al.
C. Barre, “L′utilisation du FPLA; Evaluez les Applications d′un Composant Puissant qui Peut se Reveler trés Economique”, Electronique & Applications Industrielles, EAI 250, Apr. 1, 1978, pp. 21-25.
D. Bursky, “Combination RAM/PLD Opens New Application Options”, Electronic Design, May 23, 1991, pp. 138-140.
“iFX8160 10ns FLEXlogic FPGA with SRAM Option; Advance Information”, Intel Corporation, Oct. 1993, pp. 2-47 through 2-56.
“iFX780 10ns FLEXlogic FPGA with SRAM Option; Preliminary”, Intel Corporation, Nov. 1993, Order No. 290459-004, pp. 2-24 through 2-46.
T. K-K. Ngai, “An SRAM-Programmable Field-Reconfigurable Memory”, Master of Applied Science degree thesis submitted to the Department of Electrical Engineering of the University of Toronto, 1994.
A. Stansfield et al., “The Design of a New FPGA Architecture”, Proceedings Field Programmable Logic (FPL) 1995, Springer Lecture Notes in Computer Science 975, pp. 1-14.
A. Kaviani et al., “Hybrid FPGA Architecture”, Proceedings 4th International Symposium on FPGAs (FPGA 96), Feb. 1996.
“Next Generation FPGAs; Xilinx Next Generation FPGAs Deliver World-Class Performance”,The Power of Innovation 1997, Xilinx, Inc., San Jose, CA, p. 7-7.
“Altera Enables System-Level Integration with Raphael Family of Embedded PLDs”, Altera Corporation, San Jose, California, Aug. 31, 1998.
“Apex 20K Programmable Logic Device Family; Advance Product Brief”, Altera Corporation, San Jose, California, Oct. 1998, pp. 1, 2, and 9.
“Altera Unveils New Name for Raphael: Advanced Programmable Embedded Matrix (APEX)”, Altera Corporation, San Jose, California, Oct. 7, 1998.
“Apex 20K Device Family; The Embedded PLD Family for System-Level Integration”, Altera Corporation, San Jose, California, after Aug. 31, 1998.
“Apex 20K Device Family; Breakthrough MultiCore Architecture”, Altera Corporation, San Jose, California, after Aug. 31, 1998.
F. Heile et al., “Hybrid Product Term and LUT Based Architecture Using Embedded Memory Blocks”, Proceedings of FPGA 1999 Conference, Feb. 21-23, 199
Altera Corporation
Fish & Neave
Jackson Robert R.
Lane Jack A.
LandOfFree
Content addressable memory encoded outputs does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Content addressable memory encoded outputs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Content addressable memory encoded outputs will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2897951