United States Patent
`
`[19]
`
`[11] Patent Number:
`
`5,841,874
`
`Kempke et al.
`
`[45] Date of Patent:
`
`Nov. 24, 1998
`
`USOO5841874A
`
`[54] TERNARY CAM MEMORY ARCHITECTURE
`AND METHODOLOGY
`
`OTI-IER PUBLICATIONS
`
`[75]
`
`Inventors: Robert Alan Kempke, Tempe, Ariz.;
`Anthony J. McAuley, Bloomfield, N.J.
`
`[73] Assignce: Motorola, Inc., Schauinburg, 111.
`
`[21] App1- N0-l 696,453
`[22]
`Filed:
`Aug‘ 13’ 1996
`
`An article entitled “Design of a Key Agile Cryptographic
`System for OC—12c Rate ATM” by Daniel Stevenson,
`Nathan Hillery, Greg Byrd, Fengmin Gong and Dan Winkel-
`stein, from 1995 IEEE.
`
`An article entitled “A Design Of A High—Density Multi-
`—Level Matching Array Chip For Associative Processing”,
`IEICE Transactions, vol. E. 74, No. 4 Apr. 1991.
`
`Int. Cl.6 ...................................................... .. H04L 9/00
`[51]
`[52] U.s. Cl.
`..................................... 330/50; 380/4; 380/9;
`380/23; 380/25; 380/49; 380/59; 326/59;
`355/163
`
`.
`‘
`E~ G“‘~g°rY
`PWWJ’ EWmm€’—B“—T11a“
`Attorney, Agent, 0!‘ Firm—James A. Coffingg Bradley J.
`Botsch; John C. Scott
`
`]
`[
`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 ternarv data usin
`the conversion
`,
`,
`-
`.
`3
`_
`register; and (3) simultaneously stoiing the two bits of
`ternary data in first and second memory cells. For subse-
`quell]; searching’ the method further includes the steps of
`searching for a match of input search binary data to the
`Stored Contents ofthe CAM; providing a match Valid output
`.
`.
`.
`.
`.
`_
`_
`responsive to the input search binary bits matching any of
`the Stored Contents; and generatlng 3" addrefis C0FT<°«SP0"dl"g
`to a location in the CAM where the match is found.
`
`9, 23, 25,
`Of Search ............................. ..
`380/28, 49, 50, 59; 326/59; 341/57; 365/168;
`371/37-04; 395/427: 428, 435
`C_ ed
`R f
`It
`e erences
`U_3_ PATENT DOCUMENTS
`341/57
`8/1971 C
`l_
`t
`1
`3 599 205
`6/1972 Aifiiuls e a‘ """"""""""""" 341,57
`3’671’959
`""""""""""""""""""""""
`'
`-
`’
`’
`_
`12/1972 Dailey et al. .
`3,706,971
`9/1973 whang "
`3,760,277
`3/1974 Norman
`3,798,544
`4,23l,023 10/1980 Warner
`43961475 10/1981 N"'d°fl°f ct “L '
`4,809,224
`2/1989 Suzuki et al.
`........................... 305/103
`4,910,750
`3/1990 Fisher
`5,432,735
`7/19.95 Parks et al.
`365/168
`3/1996 Bowles ................................ .. 326/'59 X
`5,498,980
`FOREIGN PATENT DOCUMENTS
`
`
`
`_341/57X
`380/9 X
`341/57
`
`5
`[ 6]
`
`650167A 10/1994 European Pat. Off. .
`
`21 Claims, 9 Drawing Sheets
`
`COMBINED
`NEW HEADER 1:
`ENCRYFTED DAM
`
`ENCRYPTION
`PARAMETERS
`
`1
`
`ARISTA 1014
`
`1
`
`ARISTA 1014
`
`

`
`U.S. Patent
`
`Nov. 24, 1998
`
`Sheet 1 of 9
`
`5,841,874
`
`CLOCK
`
`MASK
`SELECT CODE
`
`DATA INPUT
`
`OPCODE
`INPUT
`
`CAM SEARCH
`
`160
`
`COMPARATOR
`(XOR)
`
`FIG. 1
`
`2
`
`

`
`U.S. Patent
`
`Nov. 24, 1998
`
`Sheet 2 of 9
`
`5,841,874
`
`3
`
`

`
`U.S. Patent
`
`Nov. 24, 1998
`
`Sheet 3 of9
`
`5,841,874
`
`CLOCK
`105
`
`PC
`
`A
`
`|
`
`I
`
`I
`
`l
`
`WRITE "0"
`
`WRITE "1"
`
`BJ?
`
`RA
`
`r
`
`Ra___r——”—1_
`
`m
`
`m
`
`WRITE CYCLE
`
`FIG. 3
`
`4
`
`

`
`U.S. Patent
`
`Nov. 24, 1998
`
`Sheet 4 of 9
`
`5,841,874
`
`CLOCK I
`
`I
`
`I
`
`I
`
`I
`
`PC
`
`I
`
`I
`
`I
`
`I
`
`A
`
`B
`
`X
`
`X
`
`SEARCH FOR "9
`
`PULL MATCH LINE HIGH
`
`ISEARCH FOR "0"
`
`I
`
`K
`
`MATCH
`
`)( /
`
`MATCH
`
`\ NO MATCH
`
`LOGIC 1
`
`"STORED"
`
`RA
`
`RB
`
`CLOCK
`
`MULTI-
`MATCH
`BUFFER
`
`
`
`I
`
`I
`
`I
`
`I
`
`SEARCH CYCLE
`
`FIG. 4
`
`5
`
`

`
`U.S. Patent
`
`Nov. 24, 1998
`
`Sheet 5 of 9
`
`5,841,874
`
`MA
`
`325
`
`ADDRESS
`
`ADDRESS
`
`320
`
`370
`
`ID
`CH
`
`DECIMAL
`TO BINARY
`ENCODER
`
`6
`
`

`
`U.S. Patent
`
`Nov. 24, 1998
`
`Sheet 6 of 9
`
`5,841,874
`
`CASCADE
`INPUT
`A
`
`Z >
`5
`SYSTEM
`OPCODE
`DATA
`El E
`E‘
`INPUT
`INPUT
`INPUT
`3 ml
`.-—«—a é+-—« 5
`r-*-
`:2 E: E
`:22:
`2:
`£2
`< <
`< 3
`I
`3 > > 5 °'
`33 Zfigg Z;
`I SEBBB
`3% 5:
`E3
`55 as B)
`EEEE
`E3
`E§i:'§§ EEEE
`C) 0:
`Ln. 2 O O
`(J Lu
`C:
`3 Q: < < <1:
`
`‘:13’
`
`500
`
`CASCADE
`LOGIC
`
`2K WORD
`X
`16 BIT RAM
`
`£29
`
`SELF—TESTER
`
`INPUT BUFFER
`
`RAM
`
`:5
`2
`§
`F;
`J
`
`O(
`
`MARK REGISTER
`BINARY—TO—TERNARY
`CONVERTER
`2K woRD
`X
`64 ELEMENT
`TERNARY CAM
`
`WORD FINDER
`
`MULTI—MATCH BUFFER
`MATCH SORTER
`
`ADDRESS ENCODER
`
`OUTPUT BUFFER
`
`405
`
`410
`
`440
`
`300
`
`405
`
`410
`453
`
`455
`
`460
`
`; E E E E
`'a‘_"
`‘if E ‘at’
`'5'."
`3.‘
`'5 % % % '2'
`E E E E
`E '33
`LUT 3| 5| Lu] my
`’_l
`'_| El Lul
`‘El <I
`§ E E § Q
`§ E 5.2
`3 3
`2
`>1 ,,,' g
`Zn 05' % I-I4
`2' 2'
`_;
`5 Q
`E E,
`g
`<5 Fé
`E
`g 3
`u. 2
`+,—-I
`3
`2 T:
`DATA S’
`OUTPUT
`OPCODE B
`OUTPUT
`CASCADE
`OUTPUT
`
`S 3
`E %
`cg 2|
`5
`‘—v—’
`SYSTEM
`OUTPUT
`
`FIG- 6
`
`7
`
`

`
`U.S. Patent
`
`Nov. 24, 1998
`
`Sheet 7 of 9
`
`5,841,874
`
`2K BIT INPUT FROM
`MULTI—MATCH BUFFER
`
`
`IT
`
`WIRED—OR RAM
`
`510
`
`UT
`
`DE
`
`T0 C
`LOGIC
`
`520
`
`MULTI—
`INDIC
`CASCADE
`
`CH
`TO
`
`1!!!! ”’‘”°
`SELECTOR
`540
`
`
`
`K BI
`UT T0
`ESS
`DER
`
`550
`
`H BIT ADDRESS
`(OF WRITTEN/MATCHED/DETECTED WORD)
`
`4l7T1F(C3F.
`
`17’
`
`8
`
`

`
`U.S. Patent
`
`Nov. 24, 1998
`
`Sheet 8 of 9
`
`5,841,874
`
`0P—CODES
`
`“ASK WRITE
`
`CAM WRITE
`
`CAM SEARCH
`
`LATCHES
`MATCH CONDITIONS
`
`
`
`
`
`LOAD MASK
`REGISTER
`
`
`
`WRITE
`CAM WORDS
`
`CAM—DATA
`
`MARK
`SELECT BIT
`
`CAM—DATA INPUTS
`
`SELECT
`MASK REGISTER
`[GENERATES AB]
`
`CAM—DATA
`SELECTED MR.
`l
`
`AB
`
`FIG. 8
`
`9
`
`

`
`U.S. Patent
`
`Nov. 24, 1998
`
`Sheet 9 of 9
`
`5,841,874
`
`COMBINED
`NEW HEADER &
`ENCRYPTED DATA
`
`I II I I I I I I I I I
`
`.
`
`II I I I I I I I I I I I I I
`
`ENCRYPTION
`PARAMETERS
`
`(VP
`
`)
`
`10
`
`10
`
`

`
`5,841,874
`
`1
`TERNARY CAM MEMORY ARCHITECTURE
`AND METHODOLOGY
`
`FIEID OF THE INVENTION
`
`The present invention relates generally to semi-conductor
`memory, and more particularly,
`to a cascadable content
`addressable memory device, and a system using 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-defined 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
`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 beoomes
`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.
`
`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
`
`FIG. 1 illustrates a memory cell in accordance with the
`present invention for a ternary CAM cell semiconductor;
`
`5
`
`10
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`60
`
`65
`
`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
`
`In accordance with the present invention, a ternary 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 st.orage, and inde-
`pendently 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 (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) simulta-
`neously storing the two bits of ternary 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
`
`11
`
`11
`
`

`
`5,841,874
`
`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 120 and a second memory cell 130,
`which are utilized to store the ternary data for that CAM ceH
`location. Memory cell 120 stores the 1 or 0 data values,
`While memory cell 130 stores a 1 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
`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
`outputs A 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
`
`10
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`60
`
`65
`
`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 B) in the CAM cell 100, in parallel,
`within a single period of the clock’s 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 TCAM system is useful
`in a multitude of applications, such as filtering, address
`resolution, mapping, Vrrtual 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-
`
`ment of the present invention. The first and second ternary
`data outputs (A and B) 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 A signal to the storage element portion
`of the memory cell 120, as appropriately 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 130. 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 130. The output RB 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-OR 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
`
`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 five
`transistor memory cell is utilized that provides a single
`ended input structure, which is driven by the A line 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 made, 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 1 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 Oonversion Table}
`
`Ternary
`“N"
`
`“X”
`
`A
`0
`0
`1
`1
`
`B
`O
`1
`0
`1
`
`RA
`1
`1
`0
`0
`
`RB
`1
`0
`1
`0
`
`As shown, Table 1 depicts the ternary symbol (N,l,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
`
`Matching Table Write = 0
`
`Ternary
`‘‘X‘’
`“1”
`
`“D”
`
`“N”
`
`A
`0
`0
`
`1
`
`1
`
`B
`O
`1
`
`O
`
`1
`
`RA
`X
`X
`
`O
`1
`0
`
`ELSE
`
`RB
`X
`0
`1
`X
`
`0
`
`MA
`1
`1
`0
`1
`O
`1
`0
`
`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 pre-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-OR
`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.
`However, the pre-charge period is relevant in that the A and
`B 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 A and 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=1 and B=0, are provided, as
`illustrated in FIG. 3. The RA and RB signal lines are initially
`at a 0 level, and upon the Write CAM signal (115 of FIG. 2)
`being clocked high, the 0 write data is clocked into the
`
`10
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`SO
`
`60
`
`65
`
`13
`
`13
`
`

`
`5,841,874
`
`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-charge
`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 1, 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 0 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 RA/RB (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 illustrated 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 ternary 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 diagam of FIG. 4 illustrates first a search for a 1 and
`then a search for 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=1 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 bulfer clock signal occurs at the end of each of the
`Clock cycles, clocking the match status into a Match Buffer.
`
`10
`
`15
`
`25
`
`30
`
`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 subsystems are coupled together to create a 64 bit
`word, all 64 of these match lines are coupled together in a
`wired-OR structure, so that any element on the match line
`has the capability of pulling the match line low. Thus, all 64
`bits would have to match in order for the final Match output
`for that word to be valid (high).
`Since the comparator 150 is an exclusive-OR type device,
`the inverted outputs RA and RB are compared to the
`non-inverted ternary code outputs A and B so that inverted
`stored ternary code data is compared by the comparator to
`the non-inverted ternary code search data. The effect of the
`exclusive-OR is to utilize the inverted to non-inverted
`comparison to affect a comparison that utilizes an in