United States Patent (19)
`Nakabayashi et al.
`
`11
`(45)
`
`Patent Number:
`Date of Patent:
`
`4,975,873
`Dec. 4, 1990
`
`73 Assignee:
`
`54 CONTENT ADDRESSABLE MEMORY WITH
`FLAG STORAGE TO NOCATE MEMORY
`STATE
`75 Inventors: Takeo Nakabayashi; Harufusa
`Kondou, both of Hyogo, Japan
`Mitsubishi Denki Kabushiki Kaisha,
`Tokyo, Japan
`21 Appl. No.: 283,293
`22 Filed:
`Dec. 12, 1988
`30
`Foreign Application Priority Data
`Mar. 1, 1988 JP
`Japan .................................. 63-49092
`51) Int. Cl..........................
`... G11C 15/OO
`52 U.S. Cl. ................................. 365/.49365/189,01;
`364/200; 364/900
`58) Field of Search ................ 365/49, 189.01, 189.07;
`364/200 MS File, 900 MS File
`References Cited
`U.S. PATENT DOCUMENTS
`4,670,858 6/1987 Almy ..................................... 365/49
`4,888,731 12/1989 Chuang et al......................... 365/49
`FOREIGN PATENT DOCUMENTS
`118906 2/1978 Canada .
`2853926 6/1979 Fed. Rep. of Germany .
`57-74889 5/1982 Japan.
`74889 5/1982 Japan .
`OTHER PUBLICATIONS
`T. Ogura et al., "A 4 kb Associative Memory LSI',
`55083-78, pp. 45-52.
`C. V. Ramamoorthy et al., "A Design of a Fast Cellular
`Associateive Memory for Ordered Retrieval", pp.
`
`(56)
`
`800-815, IEEE Trans. on Computers, vol. C-27, No. 9,
`Sep. 1978, pp. 800-815.
`Hiroshi Kadota et al., "An 8-Kbit Content-Addressa
`ble and Reentrant Memory", IEEE Journal of Solid
`State Circuits, Oct. 1985, vol. SC-20, No. 5, pp.
`951-956.
`J. Of Institute of Electronics: "4 Kb Associative Mem
`ory LSI", by Takeshi Ogura et al., Dec. 1983, pp. 45-52.
`IEEE Transactions on Computers: "A Design of a Fast
`Cellular Associative Memory of Ordered Retrieval", by
`C. V. Ramamoorthy et al., vol. C-27, No. 9, 9/78, pp.
`800-815.
`IEEE J. of Sol.-St. Circuits: "An 8-kbit Content-Ad
`dressable and Reentrant Memory', by H. kadota et al.,
`vol. SC-20, No. 5, Oct. 1985, pp. 951-956.
`Primary Examiner-Glenn Gossage
`Attorney, Agent, or Firm-Lowe, Price, Leblanc, Becker
`& Shur
`ABSTRACT
`(57)
`A content addressable memory device capable of cor
`rect retrieval operation comprises a flag bit column (12)
`provided in a memory cell array. The flag bit column
`(12) stores a flag signal indicating whether a word is in
`a data written state or an empty state for each word in
`a data array (2). In the retrieval operation, the data
`written in the data array (2) and a flag bit column (12)
`are simultaneously retrieved, providing a correct re
`trieval result. In addition, since the flag bit column (12)
`is provided in the memory cell array, it can be con
`trolled in a manner similar to controlling the data array
`(2).
`
`10 Claims, 13 Drawing Sheets
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FLA 3
`CNTro
`FORTION
`
`O
`
`
`
`
`
`S CONTROLLER
`5. --- 152
`: E. --INSTR:
`53.
`- - - - - - - -
`INSTR.
`REG.
`
`154
`INST. DECODER
`
`
`
`g5 TO WORD LINE
`CCNTro
`CT is
`
`A CONTROL ORTION
`R
`
`
`
`
`
`
`
`Bz. 2
`
`
`
`
`
`OAA ARRA
`
`
`
`
`
`"
`
`"
`
`...
`
`(bs
`
`CNTROL CRCT
`
`
`
`IPR2022-00600
`Apple EX1024 Page 1
`
`

`

`U.S. Patent Dec. 4, 1990
`F IG.1
`PRIOR ART
`
`Sheet 1 of 13
`
`4,975,873
`
`BIT LINE SIGNAL
`PROCESSING
`SYSTE
`
`
`
`DATA
`INPUT/OUTPUT
`
`OPERNTION ODE
`DESIGNAT
`INSTRUCTION
`
`ADDRESS
`INPUT/OUTPUT
`
`DATA INPUTAOUTPUT
`CIRCUIT
`DATA REGISTER
`GROUP
`MASK FUNCTION
`CIRCUIT
`
`CELL ARRAY
`
`WORD LINE SIGNAL
`PROCESSING SYSTEM
`
`ADDRESS
`INPUT?
`OUTPUT
`CIRCUIT
`
`s:
`C
`8
`A
`
`ADDRESS
`SYSTE
`
`E-
`H
`H
`St
`22
`2. 3
`
`3 H
`H
`
`St
`2
`E.
`
`-
`
`2
`
`2 H
`g.
`
`g H
`
`H
`
`SELECTED SELECTED
`WORD
`ORD
`PRESENCE/ PRESENCE/
`ABSENCE
`ABSENCE
`SIGNAL INPUT SIGNAL OUTPUT:
`
`EIG SPEED
`EXTENSION
`CIRCUIT
`
`IPR2022-00600
`Apple EX1024 Page 2
`
`

`

`US. Patent
`
`Dec. 4, 1990
`
`Sheet 2 of 13
`
`4,975,873
`
`||\1|J
`
`ADTARd AYOWNIW
`
`waAtosad
`snodsau SIdLLIAn
`
`wALSTOAY aSNodsaa
`
`
`
`9LINOYTODIOMINOO
`
`SNITGYOMOL
`
`et
`4300930“ISI
`
`GYaATIONLNOOWout 7
`ap
`
`AWauywWiwd
`
`Nwatoo Lid ovid
`
`€9Ols
`
`IPR2022-00600
`Apple EX1024 Page 3
`
`IPR2022-00600
`Apple EX1024 Page 3
`
`

`

`Sheet 3 of 13
`U.S. Patent Dec. 4, 1990
`FIG. 3A
`
`4,975,873
`
`
`
`X DENOTES UNKNOWN
`CONTENT
`B1 B2 B3 B4, B5 B6 B7 B8 B9 Big
`RRARSAR PRR
`Exxx xxxx xxxw
`-xxxx xxx xxx, W2
`xxxx xxx xxx W3
`ws W6
`
`
`
`r
`
`FIG.3B
`BB2B3B4, B5 BB7B989 BC -2
`xx xxx xxxx x. Wi
`xxx xxxx xxxw
`xxx xxxx xxx. W3
`xxxx xxx xxx. W4
`xxx xxxx xxxws
`xxxxx xxx xxws
`xxx xxxxx xx w7
`XXXIXXXXXXIX."
`
`
`
`O -
`
`IPR2022-00600
`Apple EX1024 Page 4
`
`

`

`U.S. Patent
`
`Dec. 4, 1990
`
`Sheet 4 of 13
`
`4,975,873
`
`2
`RRRRRR RARRRRS -
`
`FIG.3C
`Oooooooooow
`Ooooo 11
`W3
`xxx xxx xxxx
`1 W4
`xx xxxx xxxx
`W5
`xxx xxxx xxxws
`xxx xxxx xxx w7
`xxx xxx xxxx
`
`2
`
`FIG. 3D
`B B2 B3 B4, B5 B6 B7, B8, B9 BO
`AAAAEA1
`loooooooooow
`111111
`w? w
`110 oooows,
`xxxx xxxx xxws
`0 1 0 1 01001 w8
`xxx xxxx xxxw
`0 1 0 1 0 1 01 ow8
`assessences
`
`
`
`
`
`
`
`:
`
`39
`
`B :
`
`2
`
`IPR2022-00600
`Apple EX1024 Page 5
`
`

`

`U.S. Patent De
`. 4, 1990
`
`Sheet 5 of 13
`
`4,975,873
`
`FIG.3E
`
`O
`
`RARRAR PRESPERE
`
`oooooooooow,
`1111111111W
`0000011111 wa
`11111 Ooooow,
`OO 1001100W5
`0101010101. W6
`11001100 11-w
`TOIOTIOTIOTTO."
`
`2
`
`B O
`
`-- so-n - a ura aro was a win a sm or air uro was a -a war -a- -1
`
`FIG.3F
`oooooooooow,
`-1111111111 w?
`Ooooo 11111: W3
`1111. Ooooowa
`0 0 1 1 001100:ws
`0.101010101 w8
`1100110011 wi
`101 oooows s
`
`
`
`IPR2022-00600
`Apple EX1024 Page 6
`
`

`

`Sheet 6 of 13
`
`4,975,873
`
`US. Patent
`
`Dec. 4, 1990
`
`oe
`
`IPR2022-00600
`Apple EX1024 Page 7
`
`IPR2022-00600
`Apple EX1024 Page 7
`
`

`

`Dec. 4, 1990
`
`Sheet 7of13.
`
`4,975,873
`
`US. Patent
`
` 71D(asa)Et=(TwagrarazyTION)
`
`tlm(CIOHWINGALIYM)
`
`
`LUDCTWASTSLSYGeOMAldWa)
`
`lag(QIOHVLIWTWASTULaH)
`
`Gi@(NOTLVGITWANIquam)
`C2D(awa)
`zim(ALTIUM)
`
`GOls
`
`1G
`
`IPR2022-00600
`Apple EX1024 Page 8
`
`IPR2022-00600
`Apple EX1024 Page 8
`
`

`

`3(_) ,LL10Sa4
`ZOMacat
`
`
`asnodsaa_\[ALWATLOWNI((ay)(YAATOSTaaidLLINHAATOSHYTWASTULSTWASTNLSY
`SLVALIOWLasm@id
`icsf
`
`a || ||| J
`
`|t.ees
`
`Na >
`
`IPR2022-00600
`Apple EX1024 Page 9
`
`U.S. Patent
`US. Patent
`
`Dec. 4, 1990
`Dec. 4, 1990
`
`
`
`Sheet 8 of 13
`
`4,975,873
`
`(
`
`a
`
`(_\
`
`
`
`5I
`
`\ |
`
`
`
`10HLinsaaNOLLOOIXS
`
`Y
`
`IPR2022-00600
`Apple EX1024 Page 9
`
`

`

`U.S. Patent Dec. 4, 1990
`
`Sheet 9 of 13
`
`4975,873
`
`FIG.7
`
`
`
`b51
`(WRITE)
`(WORD INVALIDATION) b52
`(READ)
`d54
`W 1
`
`qbs a go 12
`qb52 = p 15
`d53 = db 14,
`qb54 = Gb23
`
`WC
`
`W2
`
`IPR2022-00600
`Apple EX1024 Page 10
`
`

`

`Sheet 10 of 13
`U.S. Patent Dec. 4, 1990
`FG.8A
`RESET
`
`4975,873
`
`Apply RESET SIGNAL
`
`(qba, , qp53 = H)
`
`H.
`
`to
`in lin
`
`ALL WORD LINE ( , l\-Wm)
`
`FLAG BIT LINE (b0)
`Flag BIT LINE (b0)
`
`
`
`
`
`
`
`PPLY EMPTY WORD
`RETRIEVAL SIGNAL
`(d1 = H)
`
`on
`
`in on
`
`DATA BIT LINE (b1bn)
`Data BIT LINE (birbn)
`FLAG BIT LINE (b0)
`FLAG BIT LINE (b0)
`
`IPR2022-00600
`Apple EX1024 Page 11
`
`

`

`Sheet 11 of 13
`U.S. Patent Dec. 4, 1990
`FIG.8C
`DATA WRITING
`
`4,975,873
`
`301
`
`DETECT EMPTY WORD
`(SAFE AS FIG. 8B)
`
`
`
`EXECUTE MULTIPLE
`RESPONSE RESOLUTION
`
`
`
`(b43 = H, bl. 2, p.4 = H)
`
`NO
`
`303
`
`IS
`COINCIDENCE RESPONSE
`OBTANED?
`
`
`
`
`
`
`
`
`
`
`
`INPUT DATN TO BE
`WRITTEN
`
`(qb22 = H, D1 - Dn)
`
`EXECUTE
`WRTE OPERATION
`
`(qb 12, qos = H)
`
`- as
`
`"DATA" R/W CONTROL PORTION (l)
`
`"DATA"
`
`DATA BIT LINE (brvbn)
`
`"DATA"
`
`DATA BIT LINE (birton)
`
`il
`"0"
`
`FLAG BIT LINE (b0)
`FLNG BIT LINE (b0)
`SELECTED WORD LINE
`
`L
`
`OTHER ORD LINES
`
`IPR2022-00600
`Apple EX1024 Page 12
`
`

`

`U.S. Patent Dec. 4, 1990
`FIG.8D
`
`Sheet 12 of 13
`
`4,975,873
`
`DATA RETRIEWAL
`
`
`
`
`
`
`
`
`
`
`
`INPUT DATA TO BE
`RETRIEVED
`(qb21s H, D1 a-Din )
`
`"DATA"
`
`R/W CONTROL PORTION (l)
`
`"DATA"
`
`OPERATION
`
`-- "DATA"
`
`(b 13, b31 = H)
`
`nor
`
`DNTA BIT LINE (bla-bn)
`DATA BIT LINE (bribn)
`FLAG BIT LINE (b0)
`FLAG BIT LINE (b0)
`
`STORE RETRIEVAL RESULTS
`
`( Gib32 = H)
`
`
`
`
`
`FIG.8F
`
`WORD
`
`NVALIDATION
`
`--
`EXECUTE DATA RETRIEVA,
`IT UNNECESSARY DATA
`(SAME NS FIG. 8D)
`
`--
`
`(60
`
`J
`
`EXECUTE ORD INVAiDATION
`(qba, , qp15, bs 2 = H)
`
`"O"
`
`FLAG BIT LINE (b0)
`FLAG BIT LINE (b0)
`
`SELECTED WORD INE
`
`OTHER WORD INES
`
`IPR2022-00600
`Apple EX1024 Page 13
`
`

`

`Sheet 13 of 13
`U.S. Patent Dec. 4, 1990
`FIG.8E
`DATA READING
`
`4,975,873
`
`SO
`
`EXECUTE RETRIEVA. OPERATION
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`t
`
`(SAME AS FIG. 8D)
`
`L
`
`502
`
`EXECUTE MULTIPLE RESPONSE
`RESOLUTION
`
`v
`
`S
`OOINCIDENSE RESPONSE
`OBTALNED
`
`SO3
`
`SELECTED JORD LINE
`
`OTHER WORD NES
`
`IPR2022-00600
`Apple EX1024 Page 14
`
`

`

`1.
`
`CONTENT ADDRESSABLE MEMORY WITH FLAG
`STORAGE TO INDICATE MEMORY STATE
`
`5
`
`O
`
`BACKGROUND OF THE INVENTION
`1. Field of the Invention
`The present invention relates generally to a content
`addressable memory and, more specifically, it relates to
`a content addressable memory in which the retrieval
`operation can be more correctly carried out.
`2. Description of the Prior Art
`As is generally known, the content addressable mem
`ory device (hereinafter abbreviated as CAM) is a mem
`ory device which is also called an associative memory.
`15
`Data is retrieved from a CAM using a part of the data
`content to find a position in which the content is stored,
`and designating part of the content to take out the re
`maining content.
`More specifically, the CAM compares the data stored
`in each memory cell of the CAM with the retrieval data
`used for the retrieval and when they coincide with each
`other, it outputs required information from that address
`where the coincidence occurs.
`Usually, data is written by external normal writing
`operation in the memory cell array of the CAM. In
`25
`some cases, however, some data stored in the memory
`cell array of the CAM cannot be known externally. The
`existence of such unknown data is not desirable.
`Namely, when the retrieval data is applied to the mem
`ory cell array, the stored data may possibly coincide
`30
`with the retrieval data. In that case, correct retrieval
`information cannot be obtained.
`Even if all memory cells in the array of the CAM are
`reset by a signal "0" in order to solve the problem,
`when the retrieval data having all signals being "0" is
`applied to the memory cell array, these data coincide
`with each other, causing incorrect result of retrieval.
`As described above, a conventional CAM has a disad
`vantage that the result of the retrieval is not always
`correct. In addition, complicated control of the CAM is
`required in order to avoid the above mentioned disad
`vantage.
`Prior Arts of particular interest to solve these prob
`lems will be briefly described in the following.
`FIG. 1 is a block diagram showing an associative
`45
`memory LSI disclosed in the Journal of Institute of
`Electronics and Communication Engineers of Japan by
`Takeshi (semiconductor transistor) on Dec. 1, 1983, pp.
`45-52 by Takeski Ogura et al.
`Referring to FIG. 1, the associative memory com
`50
`prises a cell array 90, a bit line signal processing system
`91 connected to the cell array 90 and a word line signal
`processing system 92 connected to the cell array 90.
`The word line signal processing system 92 comprises a
`write enable tag 93 for indicating whether the data of
`55
`the word is necessary or not for each of the words in the
`cell array 90. By retrieving the write enable tag 93, a
`word which can be written (i.e. there is no need of
`holding the data) can be found from the cell array 90.
`Therefore, when new data should be written, the word
`60
`to be written can be easily found without designation or
`administration of the address of the cell array by the
`CPU. Namely, in this operation, the address need not be
`controlled from outside of the associative memory.
`The disclosed prior art associative memory simplifies
`the control in the writing operation, but does not solve
`the above described problems in the retrieval operation.
`Although the write enable tag 93 is not described in
`
`4,975,873
`2
`detail, it seems to be a collection of registers provided
`separately from the cell array 90, and a control circuit
`for controlling the write enable tag may be separately
`required.
`Japanese Patent Laying-Open Gazette No. 57-74889
`discloses a content similar to the prior art of FIG. 1.
`An example of the prior art of particular interest is
`also disclosed in "Design of a Fast Cellular Associative
`Memory for Ordered Retrieval" by C. V. RAMA
`MOORTHY et al. published in September 1978 (IEEE
`TRANSACTIONS ON COMPUTERS, VOL. C-27,
`No. 9, pp. 800-815). This article also shows a flag regis
`ter for each word provided separately from the memory
`cell array. As described above, when a register is em
`ployed as an element constituting the flag, a separate
`control circuit must be provided for controlling the
`Sage,
`Another example of the prior art of particular interest
`is disclosed in "An 8-K bit Content-Addressable and
`Reentrant Memory” by HIROSHI KADOTA et al.
`published in October 1985 (IEEE JOURNAL OF SO
`LID-STATE CIRCUITS, VOL. SC-20, No. 5, pp.
`951-956). In this article, the memory region of the mem
`ory cell array is divided into an occupied region in
`which data are written and a non-occupied region in
`which no data is written. A method for effectively ad
`ministering the memory region of the CAM by control
`ling the writing operation into the occupied and non
`occupied regions is disclosed.
`SUMMARY OF THE INVENTION
`One object of the present invention is to carry out a
`retrieval operation correctly in a content addressable
`memory (hereinafter simply referred to as CAM) de
`Vice,
`Another object of the present invention is to carry
`out a retrieval operation correctly in a CAM device
`utilizing a flag signal indicating whether each word is in
`a data written state or in an empty state.
`A further object of the present invention is to carry
`out a retrieval operation correctly in a CAM device by
`storing a flag signal indicating the word data written
`state or the empty state in a CAM cell array.
`A still further object of the present invention is to
`carry out a retrieval operation correctly in a CAM
`device without providing additional complicated con
`trol circuit means.
`Briefly stated, the present invention comprises: a
`predetermined column in a CAM cell array forming a
`flag storing circuit; a first input/output control circuit
`inputting and outputting data to the CAM cell array; a
`second input/output control circuit inputting a signal
`indicating whether each word in the CAM cell array is
`in a data written state or an empty state to the flag
`storing circuit; a reset circuit for writing the flag signal
`indicating the empty state for all words of the flag stor
`ing circuit; an empty word retrieving circuit for detect
`ing an empty word by making a retrieval in the flag
`storing circuit by the flag signals from the second input
`Moutput control circuit; a data writing circuit for writ
`ing in the empty word of the CAM cell array the data
`from the first input/output control circuit and for simul
`taneously writing in the corresponding portion of the
`flag storing circuit the flag signal indicating the data
`written state; and specified word retrieving circuit for
`detecting a specified word by making a retrieval in the
`CAM cell array with the retrieval data from the first
`
`35
`
`65
`
`IPR2022-00600
`Apple EX1024 Page 15
`
`

`

`O
`
`15
`
`4,975,873
`3
`4.
`input/output control circuit and simultaneously making
`data array for illustrating the operation of the memory
`retrieval in the flag storing circuit with the flag signal
`of FIG. 1;
`FIG. 4 is a schematic diagram showing one example
`from the second input/output control circuit.
`of the flag bit column and the data array employed in
`In a reset operation, the flag signal indicating the
`one embodiment of the present invention;
`empty state from the second input/output control cir
`FIG. 5 is a schematic diagram showing one example
`cuit is written for all the words in the flag storing circuit
`of a flag bit control portion and a reading/writing con
`by the reset circuit. In the writing operation, the empty
`trol portion employed in one embodiment of the present
`word retrieving circuit detects the empty word. The
`invention;
`data writing circuit writes the data from the first input
`FIG. 6 is a schematic diagram showing one example
`voutput control circuit in the empty word in the CAM
`of a response register and a multiple response resolver
`cell array and simultaneously writes the flag signal indi
`employed in one embodiment of the present invention;
`cating the data written state in the corresponding por
`FIG. 7 is a schematic diagram showing one example
`tion of the flag storing circuit. In the retrieval operation,
`of a word line control circuit employed in one embodi
`the specified word retrieving circuit makes a retrieval in
`ment of the present invention; and
`the CAM cell array with the data from the first input
`FIGS. 8A to 8F are flow charts showing flow of
`Moutput control circuit and simultaneously makes a
`control of the content addressable memory shown in
`retrieval in the flag storing circuit with the flag signal
`FG, 2.
`from the second input/output control circuit. There
`fore, a specified word can be correctly detected from
`DESCRIPTION OF THE PREFERRED
`20
`words with a flag signal indicating the data written state
`EMBODIMENTS
`stored in the flag storing circuit. In addition, since the
`FIG. 2 is a block diagram showing one embodiment
`first and second input/output control circuits are pro
`of a content addressable memory device (hereinafter
`vided for accessing the CAM cell array, there is no need
`abbreviated as CAM) in accordance with the present
`to provide additional complicated circuits as the second
`invention.
`25
`input/output control circuit.
`Referring to FIG. 2, the CAM comprises a data array
`In another aspect, the present invention is a method
`2 in which the reading and writing of data is carried out;
`for operating a CAM device comprising a predeter
`a read/write control portion 1 for inputting/outputting
`mined column provided in a CAM cell array forming a
`data and the retrieval data with the timing controlled to
`flag storing circuit, a first input/output control circuit
`and from the data array 2 through data bit lines B1 to
`inputting and outputting data to the CAM cell array,
`Bn; a flag bit column 12 for storing a flag signal indicat
`and a second input/output control circuit inputting a
`ing the state of writing of each word; and a flag bit
`signal indicating whether each word in the CAM cell
`control portion 11 coupled to the read/write control
`array is in a data written state or in an empty state to the
`portion 1 for inputting/outputting a flag signal with the
`flag storing circuit, comprising the steps of writing a
`timing controlled to the flag bit column 12 through a
`35
`flag signal indicating an empty state for all the words in
`flag bit line B0. The data array 2 and the flag bit column
`the flag storing circuit for resetting; detecting the empty
`12 are provided in a memory cell array of the CAM.
`word by making a retrieval in the flag storing circuit
`The CAM further comprises a response register 3
`with the flag signal from the second input/output con
`which receives the retrieval signals outputted from the
`trol circuit; writing in the empty word in the CAM cell
`flag bit 12 and from the data array 2 for carrying out the
`array the data from the first input/output control circuit
`retrieval and temporrily stores the result; a multiple
`and simultaneously writing in the corresponding por
`response resolver 4 which determines one out of a plu
`tion in the flag storing circuit the flag signal indicating
`rality of results obtained from the retrieval in accor
`the data written state; and detecting a specified word by
`dance with a predetermined logic; a word line control
`making a retrieval in the CAM cell array with the re
`circuit 6 for driving and controlling word lines W1 to
`45
`trieval data from the first input/output control circuit
`Wn; and a controller 5 which outputs timing control
`and simultaneously making a retrieval in the flag storing
`signals db to bs.
`A.
`circuit with the flag signal from the second input/out
`The controller 5 comprises, for example, a host pro
`put control circuit.
`cessor, which has a program counter 51, an instruction
`According to this method, a specified word can be
`ROM 52, an instruction register 53 and an instruction
`50
`correctly detected in the retrieval operation as de
`decoder 54. The control signals b1 to dos are outputted
`scribed above. In addition, there is no need to provide
`from the instruction decoder 54 based on the program
`an additional complicated circuit as the second input
`stored in the instruction ROM 52.
`Moutput control circuit.
`In FIG. 2, the memory device 7 is connected through
`These objects and other objects, features, aspects and
`word lines W1 to Wn as shown by the dotted line, and
`55
`advantages of the present invention will become more
`the input/output of the data is carried out through an
`apparent from the following detailed description of the
`input/output buffer 8 for the word determined by the
`present invention when taken in conjunction with the
`CAM.
`accompanying drawings.
`The control signals bi to dis respectively comprise
`various control signals, which are generally denoted by
`BRIEF DESCRIPTION OF THE DRAWINGS
`the reference characters b to dis in FIG. 1. The word
`FIG. 1 is a block diagram showing a conventional
`lines W1 to Win comprise, the respective word lines and
`associative memory LSI;
`signal lines incidental thereto, however, the signal lines
`FIG. 2 is a block diagram showing a content address
`are omitted in the figure. The details will be made clear
`in the detailed description of each block which will be
`able memory in accordance with one embodiment of 65
`given later with reference to FIGS. 4 to 7.
`the present invention;
`The general operation will be described in the follow
`FIGS. 3A to 3F are schematic diagrams showing the
`change of the data written in the flag bit column and the
`Ig.
`
`30
`
`IPR2022-00600
`Apple EX1024 Page 16
`
`

`

`10
`
`15
`
`25
`
`4,975,873
`5
`6
`First, when a reset signal dis is applied to the word
`lines B1 to B10 (that is, n = 10) and eight word lines W1
`to W8 (that is, m=8) for the purpose of simplicity.
`line control circuit 6 from the control circuit 5, all word
`lines W1 to Win are selected. At this time, the flag bit
`FIG. 3A shows the state of the flag bit column 12 and
`control portion 11 applies binary data "O' (flag signal
`the data array 2 before the resetting. The reference
`for resetting) onto the bit line B0 in response to the
`character X shows that the stored content is unknown.
`control signal d1. The flag bit column 12 connected to
`Therefore, in FIG. 3A, all of the contents stored in the
`the flag bit control portion 11 through the bit line BO
`memory cells are unknown.
`FIG. 3B shows the state after resetting. The flag bit
`receives the data "O' to be reset with the data "O' writ
`ten therein. Thus the resetting operation is completed.
`column 12 is reset by the data "0'. Meanwhile, the
`On this occasion, the data written in the data array 2 is
`contents in the data array 2 remain unknown.
`unknown, but it has no influence in the succeeding
`If the retrieval of empty words for writing the re
`operation as will be described later.
`trieval data is carried out at this time, all words response
`The data writing operation will be described in the
`coincidentally, since the retrieval of the empty word is
`following. Immediately after the completion of the
`carried out by retrieving the flag bit line B0 with the
`resetting operation, all words are in the empty state (the
`data 'O'.
`required data are not written); however, in general,
`FIG. 3C shows the state in which the data
`busy words (in which the necessary data are written)
`"0000000000', the data “1111111111", the data
`and empty words exist together when the CAM is en
`"0000011111” are written respectively in the first, sec
`ployed. Therefore, in the reading operation, the detec
`ond and third words of the data array 2. Simultaneously
`tion of the empty word is carried out in the beginning.
`with the writing of the retrieval data for each word, "1'
`is written in the corresponding word in the flag bit
`The detection of the empty word is carried out with
`the data "0" being applied to the flag bit column 12
`column 12.
`from the flag bit control portion 11 with the data array
`FIG. 3D shows the state in which data are written in
`being masked. Consequently, the word holding the data
`the first, second, third, fourth, sixth and eighth words,
`"0" in the flag bit column 12, that is, the empty word is
`respectively. In this state, if further retrieval data
`detected by the response register 3. In this case, a plural
`should be written, the flag bit column 12 is retrieved
`ity of results of the retrieval exist in general, so that the
`with the data "O' at first. Therefore, the fifth and the
`multiple response resolver 4 selects one word there
`seventh words are detected as the empty words.
`from.
`FIG. 3E shows the state in which the retrieval data
`The word line control circuit 6 selects the word line
`are written in all words. When the retrieval of data is
`carried out, the data "1" is applied to the flag bit line B0
`of the selected word. On this occasion, the read/write
`control portion 1 outputs the data to be written on the
`and the retrieval data are applied to the data bit lines B1
`data bit lines B1 to Bn, while the flag bit control portion
`to B10, respectively. When the retrieval data is
`1 outputs the data "1" (the data "1" is a flag signal
`"1111100000", for example, the data coincides in the
`indicating that the word has been written) onto the flag
`fourth word. Therefore, that word is the result of the
`bit line B0. Consequently, the data is written in the data
`retrieval.
`array 2, and, simultaneously, the data '1' is written in
`FIG, 3F shows that the third and sixth words are in
`the flag bit column 12 for the above described selected
`the empty state. In order to make the third and sixth
`words empty, the word invalidating operation is carried
`word.
`In the retrieval operation, first, the flag bit control
`out. In FIG. 3F, the value of the flag bit column 12 for
`portion 11 outputs the data "1" on the bit line B0 and,
`the third and the sixth words is 'O', so that the words
`simultaneously, the read/write control portion 1 out
`do not respond coincidentally in the data retrieval.
`puts the retrieval data on the bit lines B1 to Bn. Conse
`Since the third and sixth words are detected as the
`quently, the retrieval operation is carried out simulta
`empty words, new retrieval data can be written in these
`neously for the flag bit column 12 and for all bit lines BO
`words.
`45
`Although the retrieval operation is carried out for all
`to Bn in the data array. Now, the retrieval for the flag
`bit column 12 is carried out by the data '1', so that the
`bits (10 bits) of each word in the data array 2 in the
`word holding the data "0", that is, the empty word in
`foregoing, the retrieval operation can be carried out
`with a portion being masked. For example, in FIG. 3E,
`the flag bit column 12 is not retrieved even if a data
`if the retrieval data such as "MMMMM00000” is ap
`which coincides with the retrieval data is stored in the
`data array 2.
`plied (M shows that the bit is masked), the retrieval data
`Since a plurality of words are retrieved in general,
`coincides in the first and fourth words.
`the response register 3 temporarily holds the results of
`Although the value "O' of the flag bit column 12
`denotes the empty word and the value "1' denotes the
`the retrieval and one result of the retrieval is determined
`by the multiple response resolver 4.
`busy word in the foregoing, the same effect can be
`In the word invalidating operation, the word to be
`obtained when the value is reversed.
`FIG. 4 is a schematic diagram showing one example
`invalidated is retrieved at first. The retrieval operation
`of the flag bit column and the data array employed in
`is carried out in the similar manner as the above de
`the present invention.
`scribed retrieval operation. However, when all of the
`Referring to FIG. 4, the flag bit column 12 comprises
`words retrieved should be invalidated, the above de
`scribed operation of the multiple response resolver 4 is
`memory cells Mo1 to Mon respectively connected to
`flag bit lines b0 and bo and to word lines W1 to Wn. The
`omitted. Thereafter, the data "0" is written in the flag
`data array 2 comprises memory cells M1 to Man re
`bit column 12 of the word obtained by the retrieval
`operation.
`spectively connected to data bit lines b1 and b1 to bn
`andbnand to the word lines W1 to Wn. In the example
`FIGS. 3A to 3F are schematic diagrams showing the
`of FIG. 4, the memory cells included in the flag bit
`change of the contents in the flag bit column and the
`data array with the CAM shown in FIG. 2 applied
`column 12 and in the data array 2 have the same circuit
`thereto. The data array 2 is connected to ten data bit
`structure.
`
`30
`
`SO
`
`55
`
`65
`
`IPR2022-00600
`Apple EX1024 Page 17
`
`

`

`O
`
`15
`
`20
`
`4,975,873
`7
`8
`For example, the memory cell Mol comprises a series
`simplicity, only the portions related to the word lines
`W1 and W2 are shown in the figure.
`connection of an N channel MOS transistor Q1, a flip
`The response register 3 comprises a retrieval execut
`flop F1 constituted by two inverters and an N channel
`ing portion 31 responsive to a retrieval execution signal
`MOS transistor Q2 connected between the bit line b0
`db3 for executing the retrieval for the word, and a result
`and b0; a series connection of N channel MOS transis
`holding portion 32 responsive to the retrieval result
`tors. Q3 and Q4; and an N channel MOS transistor Q5
`holding signal db32 for holding the result of the retrieval.
`connected between a retrieval output line WA1 and a
`The multiple response resolver 4 comprises a preset
`common line WB1.
`circuit responsive to a preset signal db.43 for presetting
`The gates of the transistors Q1 and Q2 are connected
`the resolver, and a resolving circuit responsive to a
`to the word line W1. The gate of the transistor Q3 is
`multiple response resolving signal dba2 for multiple re
`connected to a node between the transistor Q1 and the
`sponse resolving the plurality of retrieval results. The
`flip flop F1. The gate of the transistor Q4 is connected
`retrieval result signal is outputted through the output
`to a node between the flip flop F1 and the transistor Q2.
`signal lines WC1 and WC2. The signal dba is a resolver
`The gate of the transistor Q5 is connected to a node
`inactivating signal and the signal p-4 is a resolver acti
`between the transistors Q3 and Q4.
`wating signal, which are the inversion of each other.
`Other memory cells are also connected to the corre
`FIG. 7 is a schematic diagram showing one example
`sponding bit lines, word lines, retrieval output lines and
`of the word line control circuit employed in the present
`common lines in the similar manner as the memory cell
`invention. In the figure, only the portions connected to
`Mo1.
`the word lines W1 and W2 are shown for the purpose of
`The writing operation and the retrieval operation for
`simplicity.
`the memory cell will be described in the following,
`Referring to FIG. 7, the word line control circuits 6
`taking the memory cell Mol as an example.
`is connected to the word lines W1 and W2 and to the
`In the writing operation, the word line W1, for exam
`output signal lines WC1 and WC2 of the multiple re
`ple, is brought to a high level and, simultaneously, the
`sponse resolver 4. A write signal b51 (= d2), a word
`25
`bit line bois brought to a low level, for example, and the
`invalidating signal dis2 (= db15), a reset signal b53 (= db 14)
`bit line b0 is brought to a high level. Consequently, the
`and a read signal db54 (= db23) are applied to the word
`flip flop F holds the data supplied from the bit line.
`line control circuit 6.
`In the retrieval operation, all word lines are brought
`The control for operating the CAM will be described
`to low level. Now, if the data which is the same as the
`in the following the reference to FIGS. 4 to 7.
`written data is applied to the bit line, that is, the bit line
`FIGS. 8A to 8F are flow charts showing the control
`b0 is brought to a low level and the bit line b0 is brought
`flow for operating the CAM. The control flow for
`to a high level, that transistor Q5 turns on. Meanwhile,
`resetting is shown in FIG. 8A. High level reset signals
`if data opposed to the written data is applied, namely,
`d14 and b53 are applied from the controller 5 to the
`the bit line b0 is brought to the high level and the bit line