USOOS841874A
`
`United States Patent
`
`5,841,874
`[11] Patent Number:
`
`[45] Date of Patent:
`Nov. 24, 1998
`Kempke et al.
`
`[19]
`
`[54]
`
`I75]
`
`TERNARY CAM MEMORY ARCHITECTURE
`AND METHODOLOGY
`
`Inventors: Robert Alan Kempke, Tempe, Ariz;
`Anthony .1. McAuley, Bloomfield, NJ.
`
`Assignee: Motorola, Inc., Schaumburg, Ill.
`
`App]. No.: 696,453
`
`Filed:
`
`Aug. 13, 1996
`
`Int. C153 ........................................................ H04L 9/00
`US. Cl.
`..................................... 380/50; 380/4; 380/9;
`380/23; 380/25; 380/49; 380/59; 326/59;
`365/168
`........ 380/4, 9, 23, 25,
`Field of Search ........
`
`380/28, 49, 50, 59, 326/59; 341/57; 365/168;
`371/3704; 395/427, 428, 435
`
`[56]
`
`References Cited
`
`US, PATENT DOCUMENTS
`
`.......................... 341/57
`8/1971 Cornelis el al,
`3,599,205
`6/1972 Amano ...................................... 341/57
`3,671,959
`3,706,977 12/1972 Dailey et al
`
`3,760,277
`9/1973 Whang
`.. 34157 X
`3,798,544
`3/1974 Norman
`380/9 X
`
`4,231,023 10/1980 W'amer
`......................... 341/57
`4,296,475 10/1981 Nederlof et al.
`.
`2/1989 Suzuki et al.
`........................... 365/168
`4,809,224
`4,910,750
`3/1990 Fisher .................................... 341/57 X
`
`5,432,735
`7/1995 Parks et al.
`365/168
`3/1996 Bowles .................................. 326/59 X
`5,498,980
`
`FOREIGN PATENT DOCUMENTS
`
`OTHER PUBLICATIONS
`
`An article entitled “Design of a Key Agile Cryptographic
`System for OC—l 2c Rate ATM” by Daniel Stevenson,
`Nathan IIillery, Greg Byrd, Fengmin Gong and Dan Winkel-
`stein, from 1995 TEEE.
`
`An article entitled “A Design Of A High—Density Militi-
`—Level Matching Array Chip For Associative Processing”,
`IEICE Transactions, vol. E. 74, No. 4 Apr. 1991.
`
`Primary Examirzer—Be-rnarr E. Gregory
`Attorney, Agent, or Firm—James A. Cofling; Bradley J.
`Botsch; John C. Scott
`
`[57]
`
`ABSTRACT
`
`invention encompasses a method of storing
`The present
`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 subse-
`quent 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.
`
`650167A 10/1994 European Pat. Off. .
`
`21 Claims, 9 Drawing Sheets
`
`COMBINED
`NEW HEADER It
`
`ENCRYPTED DATA
`
`
`
`
`900
`M
`______________ ¢__,
`
`VPI/VCI
`
`a: HEADER
`
`815
`
`
`
`CLOCK
`
`OP-CODE
`
`MASK SELECT
`PAYLOAD
`
`DATA
`
`IIlIIIIIIIlII
`
`IlIIIIIIIIl|l
`
`
`
`ENCRYPTION
`PARAMETERS
`
`KEYS
`CAM DATA
`701
`
`
`(vpr/vcr)
`ADDRESS
`
`745
`
`ENCRYPTED
`DATA
`
`
`
`
`
`
`
`
`
`ARISTA-1017
`
`1
`
`ARISTA-1017
`
`

`

`US. Patent
`
`Nov. 24, 1998
`
`Sheet 1 0f 9
`
`5,841,874
`
`CLOCK
`
`MASK
`SELECT CODE
`
`DATA INPUT
`
`MASK WRITE
`OPCODE
`INPUT _ BINARY TO— TERNARY
`DECODE _ CONVERTER
`
`CAM SEARCH
`
`(XOR)
`
`160
`
`COMPARATOR
`
`FIG. 1
`
`2
`
`

`

`US. Patent
`
`Nov. 24, 1998
`
`Sheet 2 0f 9
`
`5,841,874
`
`
`
`3
`
`

`

`US. Patent
`
`Nov. 24, 1998
`
`Sheet 3 0f9
`
`5,841,874
`
`CLOCK105
`
`PC
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`WRITE "1"
`
`a ___l——
`
`RA
`
`RB
`
`WRITE
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`WRITE CYCLE
`
`FIG. 3
`
`4
`
`

`

`US. Patent
`
`Nov. 24, 1998
`
`Sheet 4 0f 9
`
`5,841,874
`
`CLOCK I
`
`I
`
`I
`
`I
`
`I
`
`PC
`
`I
`
`I
`
`I
`
`I
`
`SEARCH FOR "C
`
`A
`
`X
`
`PULL MATCH LINE HIGH
`
`ISEARCH FOR "0"
`
`B 3<_/——\___
`
`MATCH
`
`x /
`
`MATCH
`
`\ N0 MATCH
`
`LOGIC 1
`"STORED"
`RAJ———————
`
`RB
`
`CLOCK
`
`MULTI—
`MATCH
`BUFFER
`
`
`
`f
`
`I
`
`f
`
`I
`
`SEARCEICYCLE
`
`FIG. 4
`
`5
`
`

`

`US. Patent
`
`Nov. 24, 1998
`
`Sheet 5 0f 9
`
`5,841,874
`
`|
`
`MATCH (o)
`
`I
`I
`
`I
`I
`
`:
`
`310
`
`I
`|
`
`MULTI—
`
`MATCH
`BUFFER
`REGISTER
`
`325
`
`ADDRESS
`
`ADDRESS
`GENERATOR
`
`
`
`(ENCODER)
`
`320
`
`I
`
`I
`'
`
`.
`
`I
`
`r _____________ -.
`'
`MEME
`
`I | | :
`
`MMMMI
`I
`I
`I
`I MATCH (D
`
`I
`I
`
`I I
`
`i
`
`:
`
`.
`
`;
`
`I
`I
`
`Immmw
`I _ _ __
`__ I
`:
`I MATCH (N)
`I. ______ 7. ______ J
`300
`
`370
`
`VALID
`MATCH
`
`DECIMAL
`TO BINARY
`ENCODER
`
`.17U{(EF; £5
`
`6
`
`

`

`US. Patent
`
`N0v.24,1998
`
`Shcct6 0f9
`
`5,841,874
`
`
`ADII
`numm<H<o=<o
`mmA53.2;
`
`OPCODE
`INPUT
`
`SYSTEM
`INPUT
`
`Hm<pw-QIMHE
`
`_om4mm-xm<=
`
`m;m<zm-mo
`
`z<o-mo
`
`QHIQ-MIm<zm
`
`x0040
`
`Hmmmm
`
`CASCADE
`INPUT
`
`>mzm-m4m<mHg-thm;
`
`>mmm-=<x
`
`>mzm-QHI<>-mmmon<
`
`>mmm-mmozlwmmmao<
`
`>mm¢-mwmmaa<
`
`SELF—
`
`TESTER
`
`INPUT BUFFER
`
`MARK REGISTER
`BINARY—TO—TERNARY
`CONVERTER
`
`2K WORD
`X
`64 ELEMENT
`TERNARY CAM
`
`WORD FINDER
`
`MULTI—MATCH BUFFER
`
`MATCH SORTER
`
`ADDRESS ENCODER
`
`054
`
`410
`
`440
`
`300
`
`405
`
`410
`
`453
`
`455
`
`460
`
`500
`
`m0p<m<mzoo
`
`CASCADE
`LOGIC
`
`26
`
`RR0WVAT.IKB
`
`MDA
`
`OUTPUT BUFFER
`
`m¢H¢-<H<Q-=<U
`$2-53-};WmAD
`
`OUTPUT
`
`mmHm-Hx<Pm-QIMHI
`
`mmHl-HUMImm-xm<=
`
`mmHl-z<o-mo
`
`mmHl-MAm<ZM-mo
`
`>Q<mm
`
`osz-=<z
`
`SYSTEM
`OUTPUT
`
`OPCODE
`OUTPUT
`
`mez-=<z
`
`_xmz-MIm<mHQ-MEHx;
`
`mez-mmmx0o<
`
`mez-eH4<>-mmmzoa<
`
`mez-mmo=-mmmxoo<
`
`CASCADE
`OUTPUT
`
`42771T(:35-
`
`(E?
`
`7
`
`

`

`US. Patent
`
`Nov. 24, 1998
`
`Sheet 7 0f 9
`
`5,841,874
`
`2K BIT INPUT FROM
`MULTI—MATCH BUFFER
`
`
`
`510
`
`WIRED—OR RAM
`
`RAM OUTPUT
`To CASCADE
`LOGIC
`
` 16 BIT
`
`2K
`BIT RESULT
`FROMFMM
`COMPARATOR
`
`530
`
`2K BIT
`ouwuwTo
`ADDRESS
`
`ENCODER
`
`ADDRESS DISABLER
`
`520
`
`MULTI—MATCH
`INDICATOR To
`CASCADE
`LOGIC
`
`SELECTOR
`
`540
`
`ADDRESS ENCODER
`
`550
`
`H BIT ADDRESS
`(OF WRITTEN/MATCHED/DETECTED WORD)
`
`FIG. 7
`
`8
`
`

`

`US. Patent
`
`Nov. 24, 1998
`
`Sheet 8 0f 9
`
`5,841,874
`
`OP-CODES
`
`MASK WRITE
`
`CAM WRITE
`
`CAM SEARCH
`
`LATCHES
`MATCH CONDITIONS
`
`LOAD MASK
`REGISTER
`
`
`
`WRITE
`CAM WORDS
`
`640
`
`CAM—DATA
`
`SELECTMQIT
`
`CAM—DATA INPUTS
`
`SELECT
`MASK REGISTER
`[GENERATES A,B]
`
`CAM—DATA
`SELECTED MR.
`
`l A
`
`B
`
`FIG. 8
`
`9
`
`

`

`US. Patent
`
`Nov. 24, 1998
`
`Sheet 9 0f 9
`
`5,841,874
`
`COMBINED
`NEW HEADER &
`ENCRYPTED DATA
`
`
`
`
`
`
`
`
`CLOCK
`720
`OP—CODE
`
`
`MASK SELECT PAYLOAD
`
`
`DATA
`
`
`
`
`
`ENCRYPTION
`CAM DATA
`
`PARAMETERS
`701
`(VPI/VCI)
`
`
`
`ADDRESS
`723
`
`730
`
`
` ENCRYPTED
`DATA
`
`
`
`
`10
`
`10
`
`

`

`5,841,874
`
`5
`
`10
`
`2
`FIG. 2 illustrates a fourteen transistor Static ternary CAM
`cell, corresponding to the memory cell 100 of FIG. 1,
`illustrated in further detail;
`FIG. 3 illustrates the timing waveforms for the write
`cycles to the CAM memory, in accordance with the coding
`provided as illustrated by Table 1;
`FIG. 4 illustrates the operation of the memory system
`during a search cycle, corresponding to FIGS. 1 and 2 and
`Table 2;
`FIG. 5 illustrates a memory array in accordance with the
`present invention, comprised of multiple memory storage
`subsystems 100 of FIG. 1;
`FIG. 6 illustrates a functional block diagram of a CAM
`memory system in accordance with the present invention,
`and illustrates external inputs and outputs to the memory
`system;
`FIG. 7 illustrates a detailed diagram of the match sorter
`and address encoder of FIG. 6 in further detail;
`FIG. 8 illustrates a state flow chart of the operation of the
`CAM memory system in accordance with the present inven-
`tion; and
`FIG. 9 illustrates a system embodiment of the CAM
`memory system of the present invention in an ATM data
`encrypting embodiment.
`DETAILED DESCRIPTION OF A PREFERRED
`EMBODIMENT
`
`1
`TERNARY CAM MEMORY ARCHITECTURE
`AND METHODOLOGY
`
`FIEI.D OF THE INVENTION
`
`The present invention relates generally to semi-conductor
`memory, and more particularly,
`to a cascadable content
`addressable memory device, atrd a systetrr usitrg a plurality
`of such cascaded devices.
`
`BACKGROUND OF THE INVENTION
`
`Content addressable memory devices (CAMS) are
`extremely valuable in providing associative look-up based
`on contents of the data. By pre-loading a CAM with a
`pre—defitted data set, including the data to be compared and
`optionally data to be output when a match is found for a
`corresponding CAM location, the address where the match
`is found can be output as an index to the requesting device,
`or both the address and data can be output for each match.
`One problem incurred in using CAMS is that the construc-
`tion of CAM chips requires multiples of the number of
`transistors needed to implement the CAM memory that a
`standard read/write random access memory (RAM) would
`require. Thus, CAM chips are usually much smaller in depth
`size than RAM chips. Therefore, the capacity of a single
`CAM chip is frequently inadequate to provide for
`the
`necessary associative look-ups. Accordingly,
`it becomes
`necessary to use multiple CAM chips in some sort of
`cascaded or interconnected manner to provide greater depth.
`Thus, while a single CAM chip, for example, might provide
`1k words of 32 bits of CAM capacity, the system’s require-
`ments may require 8k or 64k or even 1 megaword of CAM
`capacity.
`Prior system designs have attempted to resolve the depth
`capacity problem by cascading chips in a seriatim manner
`where each CAM performed a look up function, and if no
`match was found, then the next CAM in the cascade chain
`would attempt its look-up and so forth, looking until a match
`was found. A major problem with this approach is that there
`is a variable latency in this architecture, where the time
`taken to find a match is widely variable from associative
`look-up to associative look-up, due to the fact that there is
`uncertainty as to how many CAM chips in the chain will
`have to be accessed, one at a time in turn, until a match is
`found. CAM Data Input lines must be run in parallel to all
`of the chips in the cascade chain, and control logic and
`intercoupling must be provided between the multiple chips
`in the cascade chain.
`
`30
`
`35
`
`40
`
`45
`
`In accordance with the present invention, a tertiary CAM
`architecture is provided, comprising a binary-to-ternary con-
`version subsystem for providing first and second ternary
`data outputs responsive to binary data input, a memory for
`simultaneously storing the first and second ternary outputs
`and providing a content addressable memory, and a com-
`parator for providing a match output responsive to the
`comparison of binary data currently being input for com-
`parison as compared to the stored first and second ternary
`data outputs in the memory. In the preferred embodiment,
`there are a plurality of memory cells, forming a plurality of
`multiple bit storage words for storing the first and second
`ternary data outputs for a plurality of words. Furthermore, in
`the preferred embodiment, a mask register subsystem is
`provided that is utilized in performing the binary-to-ternary
`data conversion of data input signals, both for purposes of
`storing the ternary data outputs in the memory and for
`purposes of providing ternary data input for comparison to
`the stored ternary data.
`In the preferred embodiment, a
`plurality of addressable mask registers provide for the
`selection of any one of a plurality of binary-to-ternary
`conversion options, both for purposes of storage, and inde-
`pendetrtly for purposes of input data conversion for purposes
`of comparison.
`In accordance with one aspect of the present invention, a
`_, method of storing ternary data is provided, comprising the
`steps of (l) 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
`tertiary data using the conversion register; and (3) simulta-
`neously storing the two bits of temary data in first and
`second memory cells.
`In one embodiment, for subsequent searching, the method
`is further comprised of 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
`
`Binary CAM architectures, which store 1 and 0 data, have
`been the predominant technology used for content addres-
`sable memory (CAM) applications because of their speed ~
`and density advantages over theoretical
`ternary CAM
`architectures, which store 1, 0, and don’t care “x” data. This
`is because each ternary CAM data element contains two
`memory storage elements, and where static RAM-type
`memory cells are used, which require data and complement
`data, two clock cycles are required to write both the data and
`mask memory elements for each of the ternary CAM cells.
`Therefore, a need exists for a ternary CAM memory
`which can operate in a single clock cycle. With no speed
`disadvantage over binary CAMS, ternary CAMS could be
`used for such things as address resolution,
`filtering,
`mapping, virtual LANs, Asynchronous Transfer Mode
`(ATM) communications and systems, etc.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`60
`
`FIG. 1 illustrates a memory cell in accordance with the
`present invention for a ternary CAM cell semiconductor;
`
`11
`
`11
`
`

`

`3
`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. 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
`conversion register; and comparing the contents of the CAM
`to the ternary search data.
`Referring to FIG. 1, there is illustrated a memory cell for
`a ternary CAM cell 100 in CAM memory subsystem 160, in
`accordance with the present invention. An externally pro-
`vided Opcode input is decoded by decoder 110 to provide
`control signals for Mask Write, CAM Write, and other
`control signals to other areas of the chip, as will be described
`in greater detail hereafter. The CAM cell 100 is comprised
`of a first memory cell [20 and a second memory cell 130,
`which are utilized to store the ternary data for that CAM cell
`location. Memory cell 120 stores the l or 0 data values,
`While memory cell 130 stores a l for a don’t care “X” value
`selection, and a 0 to indicate that the memory cell contains
`data that should be utilized. An external clock is provided to 1
`the subsystem 160, where the clock signal 105 is utilized to
`synchronize operations Within the CAM memory.
`Additionally, external Mask Select code signals and Data
`Input signals are provided to the CAM memory 160 and are
`coupled to a binary-to-ternary converter 140 that converts
`the binary Data Input into appropriate ternary data signal
`outputsA and B, which respectively couple to memory cells
`120,130. The Mask Write, CAM Write, and CAM Search
`outputs from the decode logic 110 are coupled to the
`binary-to-ternary converter 140. These outputs from the
`decode logic 110 selectively control ('1) the writing of the
`Data Input into the mask registers and into the binary-to-
`ternary converter, responsive to the Mask Select code; (2)
`the conversion of the Data Input by the binary-to-ternary
`converter into ternary code; (3) the writing of the ternary
`code into the memory cells 120 and 130 responsive to the
`CAM Write decode output; and (4) the activation of a CAM
`search for comparing the ternary code for the then present
`current Data Input to the CAM cell contents by a comparator
`150, which is clocked at
`the appropriate time to do the
`comparison.
`The Mask Select code, Data Input, Clock, and Opcode
`inputs are provided to the CAM memory '160 from an
`external device or subsystem, such as a processor, which
`controls and establishes the loading of the mask registers in
`the binary-to-ternary converter 140, the loading of the CAM
`data contents into the memory cells 120,130 and the setup
`and request for comparison. The comparator 150 provides a
`Match output indicating that the Data Input either matches
`or doesn’t match the contents of the CAM memory. The ..
`binary-to-ternary conversion subsystem 140 provides the
`first and second ternary data outputs (A and B) responsive to
`the Mask Select signals, the Data Input signals, and the
`Opcode signals. The memory cell 120 stores and selectively
`outputs the first ternary data output A, responsive to the
`binary-to-ternary conversion subsystem 140 and to the
`Opcode signals. The memory cell 130 stores the second
`ternary data output B, responsive to the binary-to-ternary
`conversion subsystem 140 and the Opcode signals. The
`comparator 150 performs an exclusive-OR comparison in
`the preferred embodiment, and provides a match output
`responsive to comparing the first and second ternary outputs
`provided by the binary-to-ternary converter 140 for the then
`current Data Inputs, to the outputs of the first and second
`memory cells. Since the data storage to memory cells
`120,130 is performed in parallel,
`that
`is,
`the binary-to-
`ternary converter provides outputAto memory cell 120, and
`
`60
`
`12
`
`5,841,874
`
`4
`
`output B to memory cell 130, the memory (CAM memory
`subsystem) device 160 is able to store the first and second
`ternary outputs (A and R) in the CAM cell 100, in parallel,
`within a single period of the clocks signal. This advanta-
`geously provides for single cycle ternary data conversion,
`comparison, and write cycles. The ternary CAM storage and
`retrieval system (“TCAM”) is inherently superior to binary
`CAMs in masking operations, and useful in storage and/or
`conversion, and/or comparison. The 'I‘CAM system is useful
`in a multitude of applications, such as filtering, address
`resolution, mapping, Virtual LANS, etc.
`Referring to FIG. 2, a fourteen transistor static ternary
`CAM cell, corresponding to the CAM cell 100 of FIG. 1, is
`illustrated in further detail in accordance with one embodi-
`
`10
`
`30
`
`35
`
`40
`
`45
`
`ment of the present invention. 'Ihe first and second ternary
`data outputs (A and R) from the binary-to-ternary converter
`140, are coupled to the CAM cell 100. The memory cell 120
`receives the A input and, responsive to the CAM Write
`signal, is output from the decode logic 110, enables transis-
`tor 210 to couple the Asignal to the storage element portion
`of the memory cell 120, as appropriate-1y timed and clocked
`responsive to the external Clock, as discussed in further
`detail With reference to FIG. 3 for the timing diagrams for
`the write cycle. Transistors 220—223 form the static memory
`cell storage element 120. The output RA from the memory
`cell 120, representing an inversion of the originally input
`signal A, is coupled to one input of the comparator 150, as
`is described in greater detail hereinafter.
`Similarly, the second ternary data output B is coupled to
`the memory cell 130 of the CAM cell 100 and is coupled via
`transistor 230, responsive to the CAM Write signal output
`from the decode logic, Via transistor 230, to the memory
`storage cell 130 comprised of transistors 230—233, forming
`the storage element portion of the memory cell I30. The
`storage cell output
`from memory cell 130, output RB,
`provides an output corresponding to the inverted value of B
`as stored initially to the memory cell I30. The output RE is
`coupled to a separate input of the comparator 150.
`In a preferred embodiment, the comparator 150 is com-
`prised of a four transistor exclusive-0R comparator. The
`comparator 150 is comprised of two subportions, subportion
`one comprised of transistors 251 and 252, and a second
`subportion comprised of transistors 253 and 254. On a CAM
`search cycle, the then current search Data Input is converted
`by the binary-to-ternary converter to provide the first and
`second ternary data outputs A and B, which are coupled to
`the comparator 150 transistor gates for transistors 251 and
`254, respectively. Correspondingly, the CAM memory cell
`outputs RA and RB are coupled to the gates of transistors
`252 and 253, respectively. Thus, the ternary data for a search
`is coupled to the gates of one transistor of each portion of the
`comparator and the corresponding stored ternary data output
`from the CAM cell 100 is coupled to the gates of the other
`transistor of the corresponding portions of the comparator.
`., Each portion forms a transistor series tree, having one side
`coupled to ground (e.g., the source of transistors 251 and
`254) and having the other side of the tree coupled to a Match
`line output 170. The transistors on each side of the series tree
`are series connected, that is the other side (the drain) of
`transistor 251 is coupled to the source of transistor 252, and
`the drain of transistor 252 is coupled to the Match line 170
`and to the drain of transistor 253, which has its source
`coupled to the drain of transistor 254, which has its source
`coupled to ground. The Match line is pre-charged during the
`first portion of each clock cycle to a high level, and
`thereafter is pulled to ground, or low level, if no match is
`found, thus indicating no match. If there is a match, none of
`
`12
`
`

`

`5,841,874
`
`5
`the transistors in the comparator 150 are enabled and the
`match line stays at a high level.
`It is important to note that the ternary converter outputs,
`A and B signals, are not bit and bit bar, but are rather the
`encoded two-bit state to be written into the two memory
`element CAM cells 120,130. Thus, the standard six transis-
`tor static RAM cell, which writes bit and bit bar into both
`sides of the memory element, is not utilized, but rather a live
`transistor memory cell
`is utilized that provides a single
`ended input structure, which is driven by the A litre for
`memory cell 120 or the B line for memory cell 130.
`The comparison circuit 150, as illustrated, is comprised of
`four N-channel transistors. On one side (one portion) of the
`comparator, the gates of each of the two transistors are tied
`to the Aline and RA lines (transistors 251 and 252). On the
`other side (the other portion) of the comparator, the gates are
`tied to the B line and the RB line (transistors 254 and 253,
`respectively). On one side of the comparator, a comparison
`is tirade, between the incoming decoded A signal and the
`memory cell output RA signal (by transistors 251 and 252)
`and on the other side of the comparator, a comparison is
`made between the B signal and the RB signal (transistors
`254 and 253, respectively). The binary-to-ternary converter
`'140 performs a code conversion as provided in Table l for
`a writing table (Where the Write line equals one), and as
`provided in Table 2 for a matching table, where the Write
`line equals 0. For either a write or search operation, the
`binary Data Input is encoded by the binary-to-ternary con-
`verter 140 to corresponding A and B outputs. The Tables 1
`and 2 show four ternary codes for conversion. In a preferred
`embodiment, the null state “N” is not used for writing or
`searching, and is used for pre-charge and test functions only.
`Table 1 illustrates the writing table where the write line
`equals one, providing the logic for the binary to the ternary
`converter 140 performing code conversion;
`
`TABLE 1
`
`[‘B —> T Conversion Table)
`
`Ternary
`“N"
`“1’"
`“0"
`'X
`
`A
`U
`U
`1
`1
`
`B
`0
`1
`0
`1
`
`RA
`l
`1
`U
`0
`
`RB
`1
`0
`1
`0
`
`10
`
`15
`
`30
`
`35
`
`40
`
`45
`
`As shown, Table 1 depicts the ternary symbol (N,1,0,X)
`and the corresponding ternary data outputs A and B, and the
`corresponding memory cell outputs RA and RB.
`Table 2 provides the code conversion for the matching .,
`operation for the binary-to-ternary converter 140 performing
`code conversion;
`
`TABLE 2
`
`Matchina= Table Write = 0
`
`Ternary
`X
`“1”
`
`“'0”
`
`“N”
`
`A
`0
`O
`
`1
`
`1
`
`B
`0
`1
`
`0
`
`1
`
`RA
`X
`X
`
`0
`1
`D
`
`ELSE
`
`RB
`X
`0
`1
`X
`
`0
`
`MA
`1
`1
`U
`1
`O
`1
`0
`
`_,
`
`60
`
`65
`
`As shown, Table 2 illustrates the matching table, showing
`the ternary symbol (N,0,1,X) and the corresponding ternary
`
`6
`data outputs A and B, plus showing the Match output 170
`resulting from a comparison of the ternary code for the input
`data to the stored memory cell output data (RA and RB).
`By way of example, and referring to Table 2, in conjunc-
`tion with reference to the comparator 150 of FIG. 2, the
`search data A is compared to the stored cell output RA, and
`if they are exclusive of each other, that is, if only one of them
`is logic high, this will inhibit that side of the comparator
`(transistors 251 and 252) from pulling the match line low.
`Similarly, if RB and B (the search data B) are compared, and
`only one of them is high, indicating that there is a match,
`then that side of the transistor series tree will not be able to
`pull the match line low. When neither one of the sides of the
`transistor series trees 251 and 252, or 254 and 253, are able
`to pull the match line low, this indicates that there is a match
`in the cell. Conversely, if there is not a match in the cell, for
`example, if both A and RA are high, this would turn on both
`transistors 251 and 252, which would connect the output
`point coupling 252 and 253 to ground,
`thus pulling the
`match line low, thus indicating there is not a match. Where
`there are a number of memory cells corresponding to a
`single memory word, the match line for each memory cell is
`coupled to other match lines for that single word in a
`wired-OR structure, such that a number of memory elements
`can be cascaded together to form a word, and if any of the
`memory cells forming the multiple bit word don’t match, it
`will pull the match line low, indicating no match.
`Referring to FIG. 3,
`the timing waveforms for write
`cycles to the CAM memory is illustrated for a write zero
`cycle and a write one cycle. First, it is noted that the coding
`of the A and B lines, as indicated in Tables 1 and 2, are such
`that only one of the A or B lines will transition at a time
`during write and search operation.
`As illustrated in FIG. 3, there is a Clock (i.e., the Clock
`signal 105 of FIG. 1) which periodically cycles at a system
`clock rate. During the first portion of the clock cycle, a
`pre-charge (or setup) cycle occurs (i.e., a pre-charge signal
`goes high) to pro-charge the match line, and both the A and
`B lines are forced to an active low state, putting 0 on the A
`and B lines during pre-charge. This guarantees that inde-
`pendent of Whatever data is stored in the memory cells 120
`and 130, that the match line can be pre-charged to a logic
`one without having any DC path in the exclusive-0R
`circuitry of the comparator 150. After the pre-charge cycle
`is over (i.e., the pre-charge signal goes low), the A and B
`lines are allowed to change. The match line must be pre-
`charged, since if the match line is pulled low, it will remain
`low, since there is no active device to pull it up. Thus, the
`match line has to be reestablished at a high level each cycle,
`to establish a base level of one for a match each time. After
`the pre-charge signal goes low, a search operation can begin.
`This will be discussed in further detail with reference to FIG.
`
`4. The pre-charge is not directly used in the write cycle, and
`is used directly for the search cycle, as illustrated in FIG. 4.
`Ilowever, the pre-charge period is relevant in that the A and
`R lines are forced low during the pre-charge cycle time.
`As illustrated in FIG. 3, after the pre-charge cycle (the
`pre-charge clock signal goes from 1 to 0), a write operation
`may be performed. As illustrated in FIG. 3, a write “0” cycle
`occurs after the first pre-charge cycle during the first Clock
`cycle. The Aand B signals are set up by the binary-to-ternary
`converter 140 and coupled to the memory cells 120 and 130
`as illustrated in FIG. 1. Thus, as set forth in Table 1, to write
`a 0, the ternary code outputs A=l and B=0, are provided, as
`illustrated in FIG. 3. The RA and RB signal lines are initially
`at a (I level, and upon the Write CAM signal (115 of FIG. 2)
`being clocked high,
`the 0 write data is clocked into the
`
`13
`
`13
`
`

`

`5,841,874
`
`10
`
`15
`
`30
`
`7
`memory cells 120 and 130 and correspondingly, output
`RA=0 and output RB =1, as illustrated in FIGS. 2 and 3, and
`Table 1. Referring to the Clock signal of FIG. 3, the Clock
`then transitions from 1 to 0, again initiating the pre-chargc
`pulse to initiate the pre-charge cycle, forcing the A and B
`lines to a 0 level, and thereafter, when the pre-charge pulse
`goes back to a 0 level, the A and B ternary code outputs are
`set up for writing a 1. As shown in FIG. 3, consistent with
`the writing table of Table l, the ternary code for a “1” is A=0
`and B=1. Upon the Write clock 115 of FIG. 2 clocking active
`high, the ternary code is written into the memory cells 120
`and 130, respectively, storing inputs A and B, and the
`memory cell outputs provide for an output of RA=1 and
`RB=0, consistent with Table 1, illustrating the operation of
`the CAM cell 100 of FIG. 2. The writing of a “don’t care”
`would be similar to that illustrated for the writing of a O and
`1, except that in this case, both the A and B signals would
`be at a high level (i.e., A=B=1), which would be clocked
`upon the Write clock signal going high into the memory cells
`120 and 130, correspondingly thereafter providing outputs
`RA=RB=0. Similarly, writing an “N” into the memory cell
`would write a 0/0 (A=B=0), providing a corresponding 1/1
`output from RARE (i.e., RA=RB=1),
`leaving it
`to the
`incoming A and B to determine if there's a match, since
`transistors 252 and 253 of comparator 150 would already be
`enabled (by RA=RB=1) for a comparison.
`Referring to FIG. 4, a search cycle is illustrate-d in
`accordance with a preferred embodiment of the present
`invention. This assumes that the memory cells 120 and 130
`have already been written to during a previous write opera-
`tion. FIG. 4 illustrates only the search operation. The exter-
`nal input of Data Inputs and Mask Select inputs, in con-
`junction with the Opcode input, cause the binary-to-ternary
`converter 140 to provide temary code data A and B outputs,
`which are ultimately fed to the comparator 150, appropri-
`ately timed as illustrated in FIG. 4. Analogous to FIG. 3,
`FIG. 4 illustrates the periodic Clock signal, Pre-charge clock
`signal, the ternary code outputs A and B, and the memory
`cell outputs RA and RB, and also illustrates the Match line
`output 170, corresponding to FIGS. 1 and 2 and Table 2. The
`timing diagram of FIG. 4 illustrates first a search for a l and
`then a search [or a 0. During the first portion of the Clock
`cycle, illustrated as the first quarter of the Clock cycle, the
`A and B lines are forced low, and the pre-charge line is
`charged to a high level (which high level indicates a Match
`if it still exists after a search is done). At the end of the
`pre-charge clock, the A and B signal lines are set up with the
`appropriate data, and since this is a search for 1, A=0 and
`B=1, in accordance with Table 2. This is compared to the
`stored memory cell outputs RA and RB by the comparator .,
`150 as illustrated and described with reference to FIG. 2, and
`at the end of the first clock cycle, the Match line status is
`clocked into a buffer, and the buffer output is then decoded
`to determine the address where the match occurred (where
`there are multiple memory words in the CAM).
`When the Clock goes low to start the next Clock cycle, the
`pre-charge signal goes high, forcing the A and B ternary
`code outputs low, to permit the Match line to pre-charge
`back to 1 if needed. Then, when the pre-charge clock signal
`goes low, a search for 0 is set up, with A=1 and B=0, as set
`forth in Table 2. Since the stored memory cell output RA=1
`and RB=0, then both A=l and RA=1, thus causing transis-
`tors 251 and 252 of FIG. 2 to couple the Match line to
`ground, thus forcing the Match signal low as illustrated in
`FIG. 4, indicating no match has occurred. As illustrated in
`FIG. 4, a buffer clock signal occurs at the end of each of the
`Clock cycles, clocking the match status into a Match Buffer.
`
`35
`
`40
`
`45
`
`.,
`
`60
`
`65
`
`8
`The Buffer stores the match state for each Match line word
`location in the CAM memory.
`Also, note that if RA and RB are low, regardless of what
`A and B are on subsequent search cycles, there will always
`be a Match output. Additionally, if the external system Data
`Input is converted into a ternary code of 0/0 for A and B (i.e.,
`A=B=0) for a search,
`indicating a don’t care,
`then the
`comparator will provide a Match output no matter what is
`stored in the memory cells. This permits a global don’t care
`search. Thus, two don’t care search options are provided.
`Initially, the system can process the data coming in and store
`don’t cares into the memory. Subsequent to that, the system
`can also mask out certain bits of information in the CAM,
`using a don’t care ternary code input for the search data.
`Thus, a “don’t care” search data input ignores what’s stored
`in the CAM cell, and causes the respective don’t care bit
`locations to always match. It is to be understood that there
`are multiple bits in the word (64 bits in the preferred
`embodiment), and thus individual bits can be masked for
`don’t cares during search in real time, or can be pre-stored
`as don’t cares when loading and writing the CAM memory
`cells, so that a match is found irrespective of the search data
`for that bit.
`
`In a preferred embodiment, as illustrated in FIG. 5, the
`CAM memory 300 is comprised of a plurality of CAM cells
`100 cascaded both in rows as words (of 64 bits each), and
`as multiple rows comprising multiple (64 bit) words. Each
`word is comprised of 64 CAM cells 100. Thus, where 64
`memory subsy