Ternary CAM memory architecture and methodology

• US 5,841,874 A
• Filed: 08/13/1996
• Issued: 11/24/1998
• Est. Priority Date: 08/13/1996
• Status: Expired due to Term

• Current Assignee: General Dynamics C4 Systems Incorporated (General Dynamics Corporation)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: McAuley, Anthony J., Kempke, Robert Alan
• Primary Examiner(s): Gregory, Bernarr E.
• Application Number:
  US08/696,453
• Time in Patent Office: 833 Days
• Field of Search: 380/4, 380/9, 380/23, 380/25, 380/28, 380/49, 380/50, 380/59, 326/59, 341/57, 365/168, 371/37.04, 395/427, 395/428, 395/435
• US Class Current: 713/160
• CPC Class Codes: G06F 16/90339 by using parallel associative memories or content-addressable memories
• CPC Class Codes: G11C 15/04 using semiconductor elements

Abstract

The present invention encompasses a method of storing ternary data that includes the steps of (1) initializing a conversion register by storing binary-to-ternary mask data in a conversion register; (2) storing ternary data in a content addressable memory (CAM) by inputting a single bit binary data to the conversion register, and converting the binary data into two bits of ternary data using the conversion register; and (3) simultaneously storing the two bits of ternary data in first and second memory cells. For subsequent searching, the method further includes the steps of searching for a match of input search binary data to the stored contents of the CAM; providing a match valid output responsive to the input search binary bits matching any of the stored contents; and generating an address corresponding to a location in the CAM where the match is found.

Claims

1. A memory apparatus for coupling to an external device, the external device outputting (a) a plurality of data input signals to be processed in the memory apparatus, the plurality of data input signals comprising at least a first data input signal and a second data input signal, (b) mask select signals for specifying a data mask indicating desired locations of don'"'"'t care bits for the data input signals, and (c) opcode signals for specifying operations to be performed by the memory apparatus, the memory apparatus comprising:

a binary-to-ternary conversion subsystem that generates first and second ternary data outputs for each of the plurality of data input signals based upon the mask select signals, the plurality of data input signals, and the opcode signals; and

at least one memory subsystem, comprising;

a first memory cell for storing the first ternary data output for the first data input signal in response to the binary-to-ternary conversion subsystem and the opcode signals, said first memory cell having an output;

a second memory cell for storing the second ternary data output for the first data input signal in response to the binary-to-ternary conversion subsystem and the opcode signals, said second memory cell having an output; and

a comparator for comparing, in response to the opcode signals, the first and second ternary data outputs for the second data input signal to the outputs of the first and second memory cells, said comparator outputting a first match output.

2. The memory apparatus as in claim 1, further comprising:

means for supplying a periodic clock signal;

wherein the memory apparatus stores the first and second ternary data outputs for the first data signal within one period of the periodic clock signal.

3. The memory apparatus as in claim 1, wherein the binary-to-ternary conversion subsystem is further comprised of:

a mask register subsystem for selectively storing the data input signals during a setup cycle and for thereafter encoding the data input signals into the first and second ternary data outputs based on the mask select signals.

4. The memory apparatus as in claim 3, wherein the mask register subsystem is comprised of a plurality of mask registers that are addressable using the mask select signals.

5. The memory apparatus as in claim 1, wherein said at least one memory subsystem includes a plurality of memory subsystems that are arranged in rows to form a plurality of multiple bit words;

wherein the first match outputs for the memory subsystems forming each multiple bit word are connected together in a wired-OR connection, the logical-OR connections for the plurality of multiple bit words outputting a second match output.

6. The memory apparatus as in claim 5, wherein each of the plurality of multiple bit words has an associated address location, the memory apparatus further comprising:

means for outputting an address location corresponding to the second match output.

7. The memory apparatus as in claim 6, further comprising:

means for outputting a data output associated with the address location corresponding to the second match output.

8. A method of storing ternary data, comprising the steps of:

initializing a binary-to-ternary conversion register by storing binary-to-ternary mask data in the binary-to-ternary conversion register, wherein the binary-to-ternary mask data comprises information relating to the location of don'"'"'t care bits for input data;

inputting a single bit of binary data to the binary-to-ternary conversion register;

converting the single bit of binary data into first and second ternary data outputs using the binary-to-ternary conversion register; and

simultaneously storing as stored content addressable memory (CAM) data the first and second ternary data outputs in first and second memory cells forming a content addressable memory.

9. The method as in claim 8, further comprising the steps of:

providing input search binary data;

searching for a match of input search binary data to the stored CAM data; and

generating a match valid output when the input search binary data matches any of the stored CAM data.

10. The method as in claim 9, further comprising the step of:

generating an address corresponding to a location in the CAM where the match is found.

11. The method as in claim 9, wherein the step of searching for a match is further comprised of the steps of:

converting the input search binary data into ternary search data, using the binary-to-ternary conversion register; and

comparing the stored CAM data to the ternary search data.

12. A memory system comprising:

a binary-to-ternary conversion register; and

means for initializing the binary-to-ternary conversion register, comprised of;

means for storing binary-to-ternary mask data in the binary-to-ternary conversion register, said binary-to-ternary mask data comprising information relating to the location of don'"'"'t care bits for input data;

a content addressable memory (CAM) comprising at least first and second memory cells for storing ternary data;

means for storing the ternary data in the CAM, comprising;

means for inputting a single bit of binary data to the conversion register;

means for converting the binary data into two bits of ternary data using the conversion register; and

means for simultaneously storing as stored CAM data the two bits of ternary data in the

first and second memory cells of the CAM.

13. The memory system as in claim 12, further comprising:

means for supplying input search binary data;

means for searching for a match of input search binary data to the stored CAM data; and

means for generating a valid match output when the input search binary data matches any of the stored CAM data.

14. The system as in claim 13, further comprising:

address generator means for generating an address corresponding to a location in the CAM where the match is found.

15. The system as in claim 13, wherein the means for searching for a match is further comprised of:

means for converting the input search binary input into ternary search data, using the conversion register; and

means for comparing the contents of the CAM to the ternary search data.

16. A memory system for providing secure asynchronous transfer mode (ATM) communications for an ATM network that transmits a plurality of data cells, each of the plurality of data cells comprising payload data and header data comprised of virtual path identifier (VPI) address data and virtual channel identifier (VCI) address data, the memory system receiving a plurality of data input signals, encryption VPI and VCI addresses, and associate key data signals, the memory system comprising:

a ternary content addressable memory (TCAM) subsystem for storing a first one of the data input signals as stored ternary data, and for determining a match output address by comparing another one of the data input signals to the stored ternary data;

an addressable lookup table subsystem for storing the key data signals and selectively outputting the key data signals in accordance with the match output address;

wherein the TCAM subsystem and the addressable lookup table subsystem form a memory subsystem;

means for initializing the memory subsystem comprising;

means for storing the encryption VPI and VCI addresses in the TCAM subsystem;

means for storing the key data associated with the encryption VPI and VCI addresses in the lookup table;

means for separating the payload data from the header data for each of the data cells;

means for delivering the separated header data to the TCAM, wherein the TCAM selectively outputs the match output address when the separated header data matches one of the stored VPI and VCI addresses;

wherein the lookup table outputs the key data associated with the respective match output address;

means for encrypting the payload data in accordance with the key data; and

means for combining the encrypted payload data with the separated header data to form an encrypted data cell.

17. The memory system as in claim 16, further comprising means for transmitting the encrypted data cell to the ATM network.

18. A memory system for implementing a secure asynchronous transfer mode (ATM) communication system that transmits a plurality of signals comprising associated encryption key data, virtual path identifier (VPI) data, virtual channel identifier (VCI) data, and data cells, each data cell comprising payload data and header data, said header data comprised of VPI/VCI data, wherein respective ones of the encryption key data are associated with respective ones of the VPI/VCI data, the memory subsystem comprising:

a content addressable memory (CAM) subsystem for storing data therein;

an addressable lookup table;

a processor for storing VPI/VCI data into the CAM subsystem, each at a respective storage address, and for storing the respective associated encryption key data into the lookup table at a location mapped to the respective storage address;

a decoder for separating the header data from the payload data for each of the data cells;

wherein the CAM subsystem includes means for comparing the stored data therein to the separated header data to selectively determine a match address output when the separated header matches any of the stored data therein;

wherein the lookup table outputs the associated encryption key data based on the match address output;

an encryptor for encrypting the separated payload data based on the encryption key data output from the lookup table; and

a combiner for combining the encrypted payload data with the separated header to form an encrypted data cell.

19. The memory system as in claim 18, further comprising:

means for communicating the encrypted data cell through standard ATM infrastructure systems.

20. The memory system as in claim 19, further comprising:

means for receiving the communicated encrypted data cell;

a decoder for separating the header data from the payload data for each of the communicated data cells;

wherein the separated communicated header data is compared to the stored data in the CAM subsystem;

wherein the CAM subsystem compares the stored data therein to the communicated separated header data to selectively determine the match output when the communicated separated header matches any of the stored data therein;

a decrypter for de-encrypting the communicated encrypted separated payload data based on the encryption key data; and

means for communicating the de-encrypted separated payload data.

21. A memory apparatus, comprising:

a plurality of memory locations each capable of storing at least one data record having multiple bit positions;

means for receiving data records from an exterior environment for storage in said plurality of memory locations;

means for storing said received data records in said plurality of memory storage locations;

means for receiving a search data record from an exterior environment for comparison with data records stored in said plurality of memory locations;

means for comparing said search data record to multiple data records stored in said plurality of memory locations, to determine whether a record match exists between said search data record and one of the multiple data records, said comparing means comparing each bit position of said search data record to a corresponding bit position in each of said multiple data records;

means for storing first don'"'"'t care bits in selected bit positions within said multiple data records stored in said plurality of memory locations, said first don'"'"'t care bits each resulting in a bit match when compared with data bits in said search data record irrespective of the content of said search data record; and

means for adding second don'"'"'t care bits to selected bit positions in said search data record, said second don'"'"'t care bits each resulting in a bit match when compared to data bits in said multiple data records irrespective of the content of said multiple data records.