TECHNICAL FIELD

The present invention relates to an associative memory having a minimum distance search function.

BACKGROUND ART

In the field of image compression and image recognition, associative memories with a minimum distance search function have attracted attention. The associative memory stores R pieces of reference data each having a bit width W (W and R are natural numbers). When a data string (search data) is input, the associative memory searches the plurality of reference data pieces for the most similar data piece (having the shortest distance).

It is basic processing in pattern matching to find the most similar reference data to the input data string (see Non-Patent Document 1). Therefore, the minimum distance search associative memory is useful in information processing such as image compression and image recognition. The minimum distance search associative memory is for example disclosed in Patent Document 1. Furthermore, fully parallel associative memories having search capability for Hamming distance, Manhattan distance and Euclidian distance are disclosed by Patent Document 2 and Non-patent Documents 2 and 3.

PRIOR ART DOCUMENTPatent Document

Patent Document 1: JP 2002-288985 A
Patent Document 2: JP 2005-209317 A

Non-Patent Documents

Non-Patent Document 1: D. R. Tveter, â€œThe Pattern Recognition Basis of Artificial Intelligence,â€ Los Alamitos, Calif.: IEEE computer society, 1998.
Non-Patent Document 2: H. J. Mattausch, T. Gyohten, Y. Soda, and T. Koide, â€œCompact Associative-Memory Architecture with Fully-Parallel Search Capability for the Minimum Hamming Distance,â€ IEEE Journal of Solid-State Circuits, Vol. 37, pp. 218-227, 2002.
Non-Patent Document 3: H. J. Mattausch, N. Omori, S. Fukae, T. Koide and T. Gyohten, â€œFully-Parallel Pattern-Matching Engine with Dynamic Adaptability to Hamming or Manhattan Distance,â€ 2002 Symposium on VLSI Circuits Digest of Technical Papers, pp. 252-255, 2002.
Non-Patent Document 4: M. Ikeda, et al., â€œTime-domain minimum-distance detector and its application to low-power coding schema on chip-interface,â€ Proc. of ESSCIRC '97, pp. 464-467, 1998.

SUMMARY OF THE INVENTIONProblems to be Solved by the Invention

A conventional associative memory includes a memory array portion, a Winner Line-up amplifier (hereinafter referred to as â€œWLAâ€ ) circuit and a Winner Take All (hereinafter referred to as â€œWTAâ€ ) circuit. The memory array portion includes memory cells arranged in a matrix of rows and columns. A plurality of memory cells arranged in the same row of the memory array portion store W-bit width reference data. The memory array portion further includes a plurality of comparator circuits each corresponding to a row. The comparator circuit generates a comparison current signal depending on the distance between reference data stored in memory cells in a corresponding row and externally input search data.

The WLA circuit includes a plurality of current-voltage converter circuits each corresponding to a comparator circuit. The current-voltage converter circuits each convert a comparison current signal output from a corresponding comparator circuit into a voltage. The WLA circuit amplifies a voltage with the lowest voltage level among the plurality of converted voltages into a prescribed voltage V_Was Winner and amplifies the other voltages into a prescribed voltage V_Las Loser. Here, the Winner corresponds to reference data that is the most similar to the search data and the Loser corresponds to reference data other than the most similar reference data to the search data. The WTA circuit further amplifies the voltage received from the WLA circuit for output. In the associative memory, the reference data stored in a memory cell in a row amplified into the voltage V_Wis determined as the most similar reference data to the search data.

In order to amplify the plurality of converted voltages into the voltages V_Wand V_L, the WLA circuit determines whether each voltage is greater than a prescribed threshold voltage V_refusing a transistor element provided corresponding to each row. Voltages smaller than the threshold voltage V_refare amplified into voltage V_Wand voltages greater than the threshold voltage V_refare amplified into voltage V_L.

The transistor elements used for the above-described voltage determination must have matched characteristics for each row. However, the transistors inevitably have varied characteristics. If transistors with different characteristics are used for voltage determination, a voltage in a row that should not be amplified into a voltage V_Wmay inadvertently be amplified into a voltage V_W. In short, the conventional associative memory that searches for reference data by converting a comparison current signal in each row into a voltage is prone to erroneous searches.

DISCLOSURE OF THE INVENTION

An object of the present invention is to provide an associative memory capable of reducing erroneous searches.

According to the present invention, an associative memory includes storing means, comparing means, pulse generating means, and determining means. The storing means stores a plurality of reference data pieces. The comparing means compares input search data and each of the plurality of reference data pieces in parallel and obtains the distance between the search data and the reference data pieces for each of the reference data pieces. The pulse generating means generates a pulse signal having a frequency corresponding to the obtained distance for each of the reference data pieces. The determining means that determines a most similar reference data piece to the search data among the plurality of reference data pieces based on the frequencies of the plurality of generated pulse signals.

The associative memory according to the present invention does not convert the distance between the reference data and the search data into a current value or a voltage value and generates a pulse signal having an oscillating frequency corresponding to the distance. Analog processing such as conversion of the distance into a current value or a voltage value is not included, so that erroneous searches attributable to characteristic variations of transistor devices are less likely to take place.

The pulse generating means preferably includes a plurality of oscillating means corresponding to the plurality of reference data pieces. Each of the oscillating means outputs a pulse signal with a higher frequency as the distance between the search data and the corresponding reference data piece is reduced. The determining means determines a reference data piece corresponding to oscillating means that has output a pulse signal with a highest oscillating frequency as the most similar reference data piece to the search data.

The determining means more preferably further includes a plurality of determining means corresponding to the plurality of oscillating means. The determining means determines the most similar reference data to the search data based on the determining means that receives a pulse signal earliest from oscillating means among the plurality of determining means.

In this case, the most similar reference data to the search data is determined based on the difference in timing to receive a pulse signal instead of the current/voltage difference. Therefore, the result is less affected by characteristic variations of the transistor devices.

The associative memory preferably further includes a plurality of frequency-dividing means corresponding to the oscillating means. Each of the frequency-dividing means frequency-divides a pulse signal output from corresponding oscillating means with a prescribed frequency-dividing ratio and outputting a result to corresponding determining means.

In this case, the determining means can specify an earliest received pulse signal with higher precision.

The determining means preferably further includes a latch instruction node connected to the plurality of determining means and charging means for charging the latch instruction node. Each of the determining means includes discharging means and latch means. The discharging means receives an output signal from corresponding oscillating means and discharges the latch instruction node when the output signal is a pulse signal. The latch means latches the output signal received by the discharging means when the latch instruction node is discharged.

In this case, the determining means that receives the pulse signal earliest can make the level of an output signal to be output by the determining means different from the level of an output signal to be output from the other determining means.

The determining means preferably includes a plurality of judgment means connected in a tournament manner. Each of the plurality of judgment means provided in a first stage includes a plurality of first pulse judgment means, a pulse reception judgment node, and charging means. The first pulse judgment means receives an output signal from corresponding oscillating means. The first pulse judgment means receives an output signal from corresponding oscillating means. The pulse reception judgment node is connected to the plurality of first pulse judgment means. The charging means charges the pulse reception judgment node. The first pulse judgment means includes first discharging means and latch means. The first discharging means discharges the pulse reception node upon receiving a pulse signal as an output signal from the corresponding oscillating means. The latch means latches the output signal received by the first discharging means upon receiving a clock signal. The tournament judgment means arranged in a second stage and thereafter include a plurality of second pulse judgment means, the pulse reception judgment means, and charging means. The second pulse judgment means is connected to a pulse reception determining node in corresponding tournament judgment means in the preceding stage. The pulse reception judgment node is connected with the plurality of second pulse judgment means. The second pulse judgment means includes second charging means. The second charging means charges the pulse reception node when a pulse reception judgment node in corresponding judgment means in the preceding stage is discharged. The judgment means in the uppermost stage further includes clock signal generating means. The clock generating means outputs a clock signal when the pulse reception judgment node is discharged.

In this case, the load capacity at each of the pulse reception judgment node can be reduced. Therefore, the time required for a clock signal to be output after receiving a pulse clock can be reduced.

The oscillating means preferably includes a plurality of inverters connected in series and stage number selecting means. The stage number selecting means selects the number of stages of inverters according to the distance between search data and corresponding reference data piece.

In this case, an oscillating frequency can be adjusted according to the number of stages of inverters.

The determining means preferably includes a plurality of counter means corresponding to the plurality of oscillating means. The counter means receives a pulse signal from corresponding oscillating means and generates an activated output signal upon receiving a prescribed number of pulses.

In this case, reference data similar to search data can be determined sequentially based on the order of degrees of similarity to the search data.

The associative memory preferably further includes pulse invalidating means. The pulse invalidating mean invalidates a pulse signal output from oscillating means corresponding to reference data determined by the determining means until (jâˆ’1)-th search in the j-th search where j is an integer satisfying 1<jâ‰¦k and k is an integer equal to or more than 2.

In this case, reference data similar to search data can be determined sequentially based on the order of degrees of similarity to the search data.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a functional diagram of an overall structure of an associative memory according to an embodiment of the present invention.

FIG. 2 is a circuit diagram of a unit data storage circuit and a unit data comparator circuit in FIG. 1.

FIG. 3 is a functional block diagram of a structure of an oscillating circuit in FIG. 1.

FIG. 4 is a circuit diagram of a delay circuit in FIG. 3.

FIG. 5 is a circuit diagram of a WTA circuit in FIG. 1.

FIG. 6 is a graph showing a relation between the number of stages of inverters in the oscillating circuit shown in FIG. 3 and variations in the oscillating frequency.

FIG. 7 is a functional block diagram of an overall structure of an associative memory according to a second embodiment of the present invention.

FIG. 8 is a chart for illustrating changes in the waveforms of pulse signals when a frequency divider circuit in FIG. 7 is used.

FIG. 8 is a chart for illustrating change in the waveform of a pulse signal when the frequency divider circuit in FIG. 7 is used.

FIG. 9 is a circuit diagram of a WTA circuit in an associative memory according to a third embodiment of the present invention.

FIG. 10 is a functional block diagram of a configuration of an oscillating circuit in an associative memory according to a fourth embodiment of the invention.

FIG. 11 is a circuit diagram of a delay circuit in FIG. 10.

FIG. 12 is a circuit diagram of another delay circuit different from that in FIG. 11.

FIG. 13 is a circuit diagram of another delay circuit different from those shown in FIGS. 11 and 12.

FIG. 14 is a circuit diagram of another delay circuit different from those in FIGS. 11 to 13.

FIG. 15 is a functional block diagram of an overall structure of an associative memory according to a fifth embodiment of the present invention.

FIG. 16 is a functional block diagram of an overall structure of an associative memory according to a sixth embodiment of the present invention.

FIG. 17 is a functional block diagram of an overall structure of an associative memory according to a seventh embodiment of the present invention.

FIG. 18 is a functional block diagram of a structure of a storage circuit, a comparator circuit, and an oscillating circuit in the first row in the memory array portion in FIG. 17.

FIG. 19 is a functional block diagram of a structure of the oscillating circuit in FIG. 18.

FIG. 20 is a functional block diagram of a structure of a delay circuit in FIG. 19.

FIG. 21 is a functional block diagram of a structure of a storage circuit, a comparator circuit, and an oscillating circuit in the first row in an associative memory according to an eighth embodiment of the present invention.

FIG. 22 is a functional block diagram of a structure of a WTA circuit in an associative memory according to a ninth embodiment of the present invention.

BEST MODE FOR CARRYING OUT THE INVENTION

Hereinafter, embodiments of the present invention will be described in detail in conjunction with the accompanying drawing in which the same or corresponding portions are designated by the same reference characters, and their description will not be repeated.

First EmbodimentOverall Structure

Referring to FIG. 1, an associative memory 100 according to an embodiment of the present invention includes a memory array portion 10 and a WTA (Winner Take All) circuit 20.

The memory array portion 10 includes a memory portion 1, a row decoder 2, a column decoder 3, a Read/Write circuit 4, and a search data storage circuit 5.

The memory portion 1 includes unit data storage (Unit Storage: US) circuits US₁₁to US_1W, US₂₁to US_2W, . . . , and US_R1to US_RW. Here, W and R are both natural numbers equal to or greater than 2. In the following description, an arbitrary unit data storage circuit will be designated with US_ij(1â‰¦iâ‰¦W, 1â‰¦jâ‰¦R).

The unit data storage (Unit Storage: US) circuits US₁₁to US_1W, US₂₁to US_2W, . . . , and US_R1to US_RWare arranged in a matrix of rows and columns. A plurality of unit data storage circuits US_ijarranged in the same row form a storage circuit S_i. For example, the unit data storage circuit US₁₁to US_1Warranged in a first row form a storage circuit S₁. Similarly, the unit data storage circuits US₂₁to US_2Warranged in a second row form a storage circuit S₂and the unit data storage circuits US_R1to US_RWarranged in the R-th row form a storage circuit S_R.

A storage circuit S_iin each row stores W bit width reference data. More specifically, the storage circuit S₁corresponding to the first row stores W bit width reference data. The storage circuit S₂corresponding to the second row stores other reference data different from the reference data stored by the storage circuit S₁. A plurality of unit data storage circuit US_ijin the storage circuit S_ieach store a corresponding one-bit data piece of the reference data.

The memory portion 1 further includes a plurality of comparator circuits C₁to C_Rcorresponding to the storage circuits S₁to S_R. The comparator circuit C₁corresponds to the storage circuit S₁arranged in the first row. The comparator circuit C₂corresponds to the storage circuit S₂arranged in the second row. Similarly, the comparator circuit C_Rcorresponds to the storage circuit S_Rarranged in the R-th row.

The comparator circuit C₁includes a plurality of unit data comparator (Unit Comparator: UC) circuits UC₁₁to UC_1W. Similarly, the comparator circuit C₂corresponding to the second row includes a plurality of unit data comparator circuits UC₂₁to UC_2W. Similarly, the comparator circuits C₃to C_Rcorresponding to the third row to the R-th row include a plurality of unit data comparator circuits UC₃₁to UC_3W, . . . , and UC_R1to UC_RW.

The unit data comparator circuits UC₁₁to UC_1Ware arranged corresponding to the unit data storage circuits US₁₁to US_1W. The unit data comparator circuits UC₂₁to UC_2Ware arranged corresponding to the unit data storage circuits US₂₁to US_2W, respectively. Hereinafter, in the same manner, unit data comparator circuits UC₃₁to UC_3W, . . . , and UC_R1to UC_RWare arranged corresponding to the unit data storage circuits US₃₁to US_3W, . . . , and US_R1to US_RW, respectively.

In the following description, an arbitrary comparator circuit will be designated with C_iand an arbitrary unit data comparator circuit with UC_ij.

A comparator circuit C_iin each row receives externally applied search data with a W bit width. The search data and W bit width reference data stored in a corresponding storage circuit S_iare compared. More specifically, the comparator circuit C_iobtains the distance between the search data and the reference data (the Hamming distance in this example). The comparison between the reference data in each row and the search data is executed in parallel. More specifically, each comparator circuit C_iexecutes comparison between a reference data in a corresponding i-th row and the search data in parallel (simultaneously).

The memory portion 1 further includes a pulse generator circuit. The pulse generator circuit includes a plurality of oscillating (OC) circuits OC₁to OC_R. Hereinafter, an arbitrary oscillating circuit will be referred to as OC_i.

Each oscillating circuit OC_iis arranged in a row. More specifically, the oscillating circuit OC₁corresponds to the storage circuit S₁and the comparator circuit C₁. The oscillating circuit OC₂corresponds to the storage circuit S₂and the comparator circuit C₂. Similarly, the oscillating circuit OC_Rcorresponds to the storage circuit S_Rand the comparator circuit C_R.

The oscillating circuit OC_ioutputs a pulse signal P_ihaving an oscillating frequency based on the Hamming distance obtained by the comparator circuit C_i. More specifically, the oscillating circuit OC₁, outputs a pulse signal P₁having an oscillating frequency based on the Hamming distance between reference data stored in the first row (storage circuit S₁) and the search data. The oscillating circuit OC₂outputs a pulse signal P₂having an oscillating frequency based on the Hamming distance between reference data in the second row and the search data. Similarly, the oscillating circuit OC_Routputs a pulse signal P_Rhaving an oscillating frequency based on the Hamming distance between the reference data in the R-th row and the search data.

In short, the plurality of oscillating circuits OC₁to OC_Rgenerate pulse signals P₁to P_Reach corresponding to reference data in a corresponding row. The oscillating frequency of a pulse signal Pi corresponds to the Hamming distance between reference data in a corresponding row (i-th row) and search data. More specifically, as the Hamming distance decreases, the oscillating frequency increases whereas as the Hamming distance increases, the oscillating frequency decreases.

The row decoder 2 specifies a row-wise address in the memory portion 1. The column decoder 3 specifies a column-wise address in the memory portion 1. The Read/Write circuit 4 writes reference data in unit data storage circuits US₁₁to US_1W, US₂₁to US_2W, . . . , and US_R1to US_RWspecified by the row decoder 2 and the column decoder 3. The Read/Write circuit 4 further writes search data in the search data storage circuit 5.

The search data storage circuit 5 stores the search data written by the Read/Write circuit 4.

The WTA circuit 20 receives a plurality of pulse signals P₁to P₁generated by the pulse generator circuits (oscillating circuits OC₁to OC_R). The WTA circuit 20 determines reference data that is the most similar to the search data based on the oscillating frequencies of the pulse signals P₁to P_R. The WTA circuit 20 specifies a pulse signal P_ihaving the largest oscillating frequency among the pulse signals P₁to P_R. Then, reference data stored in a row corresponding to the specified pulse signal P_i(the i-th row) is determined as the most similar reference data to the search data.

The WTA circuit 20 includes a plurality of judgment circuits JC₁to JC_Rcorresponding to the plurality of oscillating circuits OC₁to OC_R. Hereinafter, an arbitrary judgment circuit will be designated with JC_i. The plurality of judgment circuits JC₁to JC_Rreceive corresponding pulse signals P₁to P_R. Among the pulse signals P₁to P_R, the voltage level of the pulse signal P_ihaving the greatest oscillating frequency changes earliest. Among the judgment circuits JC₁to JC_R, the judgment circuit JC_ithat receives the pulse signal P_ithat has changed in level earliest outputs an activated judgment signal JS_i. The other judgment circuits JC_ithat receive level-changed signals P_isecond earliest and afterwards output an inactivated judgment signal JS_i. The activated judgment signal JS indicates â€œ1â€ and is made of voltage VDD. The inactivated judgment signal JS_iindicates â€œ0â€ and is made of voltage Vref (Vref<VDD). The activated judgment signal JS_iindicates that reference data in a corresponding row (the i-th row) is the most similar reference data to the search data (hereinafter this reference data will be referred to as Winner). The inactivated judgment signal JS_iindicates that the reference data in the corresponding row is not the most similar reference data to the search data (hereinafter this reference data will be referred to as Loser).

Assume that reference data stored in the storage circuit S₂is for example the most similar data to the search data among a plurality of reference data pieces stored in the memory portion 1. In this case, the pulse signal P₂has the highest oscillating frequency among the pulse signals P₁to P_R. Therefore, the WTA circuit 20 activates only the judgment signal JS₂among the judgment signals JS₁to JS_R, and inactivates the other judgment signals JS_i.

As described above, the associative memory 100 does not convert the difference in distance between reference data and search data into current and voltage difference unlike the conventional associative memory. Instead, the differential distance is replaced by the difference between the oscillating frequencies of the pulses. If the distances are different, the oscillating frequencies are different. If the oscillating frequencies are different, the pulses rise (or fall) initially in different timings, so that the distance difference is replaced by time difference. The associative memory 100 determines the most similar reference data to search data based on the time difference. When the distance difference is converted into current and voltage differences, analog processing is carried out. In this case, transistor devices used to determine Winner and Loser may have varied characteristics, which may result in erroneous searches. In contrast, the associative memory 100 determines Winner by replacing the distance difference by the oscillating frequency difference (time difference). More specifically, Winner is determined by digital processing. In this way, the processing is less likely to be affected by varied characteristics of the transistor devices and therefore erroneous searches can be reduced.

Now, a unit data storage circuit US_ijin a storage circuit S_i, a unit data comparator circuit UC_ijin a comparator circuit C_i, the oscillating circuit OC_iin the pulse generator circuit, and the WTA circuit 20 will be described in detail. In the following description, each of the bit data pieces that form reference data with a W bit width will be referred to as reference bit data. Each of the bit data pieces that form search data with a W bit width will be referred to as search bit data. More specifically, the reference data has W reference bit data pieces and the search data has W search bit data pieces corresponding to the reference bit data pieces.

Unit Data Storage Circuit and Unit Data Comparator Circuit

Referring to FIG. 2, the unit data storage circuit US₁₁forms an SRAM device. The unit data storage circuit US₁₁includes a latch circuit 210 that latches data and n-type MOS transistors 201 and 202. The n-type MOS transistors 201 and 202 are connected in series. The latch circuit 210 is connected between the n-type MOS transistors 201 and 202. The n-type MOS transistors 201 and 202 have their gates connected to a word line WL₁.

The word line WL₁is connected to the row decoder 2. When the row decoder 2 selects the word line WL₁, the n-type MOS transistors 201 and 202 turn on. At the time, the n-type MOS transistor 201 supplies the latch circuit 210 with externally input 1-bit reference bit data D that forms reference data. The n-type MOS transistor 202 receives reference bit data DQ as an inverted signal of the reference bit data D and supplies the received data to the latch circuit 210.

The latch circuit 210 includes two inverters I1 and I2. The inverter I1 has its input terminal connected to the output terminal of the inverter I2. The inverter I1 has its output terminal connected to the input terminal of the inverter I2. The inverter I1 receives the reference bit data D from the n-type MOS transistor 201. The inverter I2 receives the reference bit data DQ from the n-type MOS transistor 202. Therefore, the latch circuit 210 latches the 1-bit reference bit data D. The reference bit data D is either â€œ1â€ or â€œ0â€ . When the reference bit data D is â€œ1â€ , a signal supplied from the n-type MOS transistor 201 to the latch circuit 210 is in an H level, and when the reference bit data D is â€œ0â€ , the signal is in an L level.

External search bit data CAM is input to the unit data comparator circuit UC₁₁. The search bit data CAM is 1-bit data that forms search data and corresponds to the unit data storage circuit US₁₁. The unit data comparator circuit UC₁₁compares the reference bit data D stored in the unit data storage circuit US₁₁and the search bit data CAM to obtain a distance (Hamming distance). The obtained distance is output to the corresponding oscillating circuit OC₁.

The unit data comparator circuit UC₁₁includes two transfer gates TG1 and TG2 and an inverter I3.

The transfer gates TG1 and TG2 are each made of an n-type MOS transistor and a p-type MOS transistor. The gate of the p-type MOS transistor in the transfer gate TG1 receives the reference bit data D from the latch circuit 210 and the gate of the n-type MOS transistor receives the reference bit data DQ from the latch circuit 210. The gate of the p-type MOS transistor in the transfer gate TG2 receives the reference bit data DQ from the latch circuit 210 and the gate of the n-type MOS transistor receives the reference bit data D from the latch circuit 210.

In response to the level (â€œ1â€ or â€œ0â€ ) of the reference bit data D, one of the transfer gates TG1 and TG2 turns on and the other turns off. The transfer gate TG1 receives externally applied search bit data CAM. The transfer gate TG2 receives externally applied search bit data CAMQ that is an inverted signal of the search bit data CAM.

A node N1 outputs a signal output from the transfer gate TG1 or TG2 that has been turned on as a path enable signal path_ena. The inverter I3 outputs the inverse of the path enable signal path_ena as a path enable signal path_enaq. More specifically, the unit data comparator circuit UC₁₁outputs these two signals path_ena and path_enaq. The two signals path_ena and path_enaq are a result of comparison between the reference bit data D and the search bit data CAM and corresponds to the Hamming distance.

When the reference bit data D and the search bit data CAM match, the signal path_ena attains an L level, and the signal path_enaq attains an H level. For example, when the reference bit data D and the search bit data CAM are both â€œ1â€ , the transfer gate TG1 is turned off and the TG2 is turned on. When the reference bit data D and the search bit data CAM are both â€œ0â€ , the transfer gate TG1 turns on and the transfer gate TG2 turns off. As a result, the signal path_ena attains an L level and the signal path_enaq attains an H level.

On the other hand, when the reference search bit data D and the search bit data CAM do not match, the signal path_ena attains an H level and the signal path_enaq attains an L level. For example, when the reference bit data D is â€œ1â€ and the search bit data CAM is â€œ0â€ , the transfer gate TG1 turns off and the transfer gate TG2 turns on. When the reference bit data D is â€œ0â€ and the search bit data CAM is â€œ1â€ , the transfer gate TG1 turns on and the transfer gate TG2 turns off. As a result, the signal path_ena attains an H level and the signal path_enaq attains an L level.

The signals path_ena and path_enaq determine the oscillating frequency of the pulse signal P₁generated by the oscillating circuit OC₁.

Unit data storage circuits US₁₂to US_1W, US₂₁to US_2W, . . . and US_R1to US_RWhave the same configuration as that of the unit data storage circuit US₁₁. Unit data comparator circuits UC₁₂to UC_1W, UC₂₁to UC_2W, . . . and UC_R1to UC_RWhave the same configuration as that of the unit data comparator circuit UC₁₁.

Oscillating Circuit

The oscillating circuit OC₁outputs a pulse signal P₁with an oscillating frequency in response to the distance (Hamming distance) between W-bit width reference data and W-bit width search data stored in the storage circuit S₁. More specifically, as the distance between the reference data and the search data is reduced, in other words, as the reference data is more similar to the search data, the oscillating circuit OC₁outputs the pulse signal P₁with a higher frequency.

FIG. 3 is a functional block diagram of the oscillating circuit OC₁. Referring to FIG. 3, the oscillating circuit OC₁includes a plurality of delay circuits DC₁₁to DC_1W. The delay circuits DC₁₁to DC_1Wcorrespond to the unit data comparator circuits UC₁₁to UC_1W.

The delay circuits DC₁₁to DC_1Ware connected in series. In the series connection of the plurality of delay circuits DC₁₁to DC_1W, the delay circuit DC₁₁positioned at an end has its output terminal connected to the output node N10. The delay circuit DC_1Wpositioned at the other end has its input terminal connected to the output terminal of an NAND gate 300. The NAND gate 300 serves to activate the oscillating circuit OC₁. One input terminal of the NAND gate 300 receives an enable signal ENA as an input used to activate the oscillating circuit OC₁. The other input terminal is connected to the output node N10.

When the enable signal ENA is activated (into an H level), the NAND gate 300 serves as an inverting circuit that inverts an input signal for output. On the other hand, the delay circuits DC₁₁to DC_1Weach invert a received signal and outputs the inverted signal to the outside. More specifically, the delay circuits DC₁₁to DC_1Walso serve as the inverting circuit as described above. Therefore, the oscillating circuit OC₁includes an odd number of inverting circuits coupled in a ring shape (the NAND gate 300 and the delay circuits DC₁₁to DC_1Wduring activation).

FIG. 4 is a circuit diagram of the delay circuit DC₁₁. The delay circuit DC₁₁includes a plurality of inverters I10 to I14 and a stage number selecting circuit SE that selects the number of stages of inverters. The stage number selecting circuit SE includes two transfer gates TG10 and TG11. The transfer gate TG10 turns on upon receiving an H level signal path_ena and an L level signal path_enaq. More specifically, when reference bit data D and search bit data CAM output from the corresponding unit data comparator circuit UC₁₁do not match, the transfer gate TG10 turns on.

The transfer gate TG11 turns on upon receiving an L level signal path_ena and an H level signal path_enaq. More specifically, when the reference bit data D and the search bit data CAM match, the transfer gate TG11 turns on.

The plurality of inverters I10 to I14 are connected in series. The transfer gate TG10 is connected between the inverters I13 and I14. The transfer gate TG11 is connected between the input terminal of the inverter I10 and the input terminal of the inverter I14.

The stage number selecting circuit SE selects the number of stages of inverters based on a comparison result from a corresponding unit data comparator circuit UC₁₁. If the reference bit data D and the search bit data CAM match based on the result of comparison at the unit data comparator circuit UC₁₁, the transfer gate TG10 turns off and TG11 turn on. Therefore, an input signal at the delay circuit DC₁₁is externally output through the single stage of inverter I14.

On the other hand, when the reference bit data D and the search bit data CAM are different, the transfer gate TG10 turns on and the TG11 turns off. Therefore an input signal to the delay circuit DC is externally output through five stages of inverters. More specifically, when the reference bit data D and the search bit data do not match, the delay time is prolonged.

In short, the delay circuit DC₁₁includes a path with less inverter stages (short path), a path with more inverter stages (long path), and the stage number selecting circuit that selects between the short path and the long path depending on the Hamming distance between reference bit data and search bit data.

The other delay circuits DC₁₂to DC_1Whave the same configuration as that of the delay circuit DC₁₁. Therefore, in the oscillating circuit OC₁, as reference data with a W bit width stored in the storage circuit S₁is more similar to search data with a W bit width, in other words, as the distance between the reference data and the search data is smaller, the number of stages of inverters is reduced. This is because the number of data unit comparator circuit UC_ijthat outputs an L level signal path_ena and an H level signal path_equ is relatively greater in this case. As the number of stages of inverters is reduced, the delay time is reduced. Therefore, the oscillating circuit OC₁outputs a pulse signal P₁with a high oscillating frequency.

On the other hand, as the distance between the reference data stored in the storage circuit S₁and the search data is greater, the number of stages of inverters to be used in the oscillating circuit OC₁increases. Therefore, the oscillating circuit OC₁outputs a pulse signal P₁with a low oscillating frequency.

As in the foregoing, the oscillating circuit OC₁outputs a pulse signal P₁with an oscillating frequency depending on the distance between the reference data in the storage circuit S₁and search data. As the distance between the reference data and the search data is smaller, the oscillating circuit OC₁reduces the number of stages of inverters to be used. Therefore, as the reference data is more similar to the reference data, a pulse signal P₁with a higher oscillating frequency is output.

The oscillating circuits OC₂to OC_Rhave the same configuration as that of the oscillating circuit OC₁. Therefore, among the oscillating circuits OC₁to OC_R, reference data that is the most similar to the search data is stored in a storage circuit S_icorresponding to an oscillating circuit OCi that has output a pulse signal P_iwith the highest oscillating frequency.

The NAND gate 300 receives a signal on the node N10 and an enable signal ENA and outputs a result of NAND logical operation to the delay circuit DC_1w. As described above, the NAND gate 300 activates or stops the oscillating circuit OC₁in response to the enable signal ENA. When the enable signal ENA is inactive (in an L level), the NAND gate 300 always outputs an H level signal. Therefore, the signal output from the oscillating circuit OC₁is constantly in an H level. More specifically, the oscillating circuit OC₁does not output a pulse signal.

WTA Circuit

The WTA circuit 20 receives pulse signals P₁to P_Rfrom the oscillating circuits OC₁to OC_R. The reference data (Winner) that is the most similar to search data is determined based on the oscillating frequencies of the pulse signals P₁to P_R.

Referring to FIG. 5, the WTA circuit 20 includes a plurality of judgment circuits JC₁to JC_R, a pre-charge circuit 30, and a latch instruction node N40. The judgment circuits JC₁to JC_Rare each connected to the latch instruction node N40.

The pre-charge circuit 30 supplies the latch instruction node N40 with charge and charges the node upon receiving an enable signal ENAQ that is an inverted signal of the enable signal ENA. This causes voltage at the latch instruction node N40 to rise to an H level (VDD).

The judgment circuit JC₁receives an output signal from the corresponding oscillating circuit OC₁. The judgment circuit JC₂receives an output signal from the oscillating circuit OC₂. Similarly, the judgment circuits JC₃to JC_Rreceive output signals from the oscillating circuits OC₃to OC_R, respectively.

The judgment circuit JC₁includes an inverter I20, a delay circuit 251, a latch circuit 252, a discharge circuit 250, and a clock generator circuit 253.

An inverter I20 receives an output signal from the oscillating circuit OC₁and inverts the received signal for output to a node N30. The discharge circuit 250 is made of an n-type MOS transistor. The n-type MOS transistor is connected between the latch instruction node N40 and a GND node to which ground voltage is supplied and has its gate connected to the node N30. The discharge circuit 250 discharges the latch instruction node N40 when an H level signal is input to the gate of the n-type MOS transistor. More specifically, the judgment circuit JC₁lowers the voltage level at the latch instruction node N40 to the ground voltage level (L level) by the discharge circuit 250 upon receiving a pulse signal P₁.

The clock generator circuit 253 outputs a clock signal CLK when the latch instruction node N40 attains an L level. The clock generator circuit 253 is made of an inverter I21. The inverter I21 has its input terminal connected to the latch instruction node N40. The clock generator circuit 253 outputs an H level clock signal CLK when the latch instruction node N40 attains an L level.

The latch circuit 252 is made of a D flip-flop. The latch circuit 252 latches an output signal from the inverter I20 and externally outputs a judgment signal JS₁upon receiving an H level clock signal CLK.

In response to a pulse signal P₁output from the oscillating circuit OC₁, the delay circuit 251 makes such an adjustment that an inverted signal of the pulse signal P₁is input to the latch circuit 252 when the clock generator circuit 253 outputs a clock signal. The delay circuit 251 however does not have to be provided.

The judgment circuits JC₂to JC_Reach have the same configuration as that of the judgment circuit JC₁. The discharge circuit 250 and the clock generator circuit 253 each in judgment circuits JC₁to JC_Rare both connected to the latch instruction node N40. Therefore, when the discharge circuit 250 of any of the judgment circuits JC discharges the latch instruction node N40, the clock generator circuits 253 of all the judgment circuits JC₁to JC_Routput an H level clock signal CLK.

When a pulse is not formed in output signals from the oscillating circuits OC₁to OC_R, in other words, before an oscillating circuit OCi outputs a pulse signal P_i, the pulse signals P₁to P_Rare constantly in an H level. Now assume that among the oscillating circuits OC₁to OC_R, the oscillating circuit OC₂outputs a pulse signal P₂with the highest oscillating frequency.

In this case, an output signal from the oscillating circuit OC₂has its voltage level changed from an H level to an L level earlier than the outputs signals from the other oscillating circuits OCi. Therefore, the discharge circuit 250 in the judgment circuit JC₂operates earliest among the discharge circuits 250 in the judgment circuits JC_iand pulls the latch instruction node N40 to an L level.

At the time, the latch circuit 252 in the judgment circuit JC₂receives an H level signal. However, the latch circuits 252 in the other judgment circuits JC₁and JC3 to JC_Rreceive an L level signal. When the latch instruction node N40 attains an L level, the clock generator circuits 253 in judgment circuits JC_ieach output an H level clock signal CLK at a time. Therefore, only the latch circuit 252 in the judgment JC₂latches the H level signal and the latch circuits 252 in the other judgment circuits JC₁, and JC₃to JC_Reach latch an L level signal.

Through the above described process, the judgment circuit JC₂outputs an H level judgment signal JS₂that indicates Winner and the other judgment circuits JC₁, and JC₃to JC_Routput L level judgment signals JS₁, JS₃to JS_Rthat indicates Loser.

As in the foregoing, the associative memory 100 according to the embodiment generates a pulse signal with an oscillating frequency corresponding to the distance between reference data and search data. Then, reference data to be Winner is determined based on the oscillating frequency of a pulse signal.

When the distance between the reference data and the search data is converted into an oscillating frequency, erroneous search that would otherwise be caused because of varied characteristics using the conventional associative memory is less likely to take place. The oscillating circuit OC_iincludes a plurality of stages of inverters. If transistors that form inverters have varied characteristics, the plurality of stages of inverters reduce the effect of the varied characteristics. More specifically, if the transistors have varied characteristics, resulting oscillating frequencies can be less varied.

FIG. 6 is a graph showing a relation between the number of stages of inverters in an oscillating circuit OCi and varied oscillating frequencies. The graph in FIG. 6 was obtained by the following method. To start with, oscillating circuits having 17 stages of inverters, 33 stages of inverters, 65 stages of inverters and 129 stages of inverters were produced. CMOS transistors used each had a gate length of 90 nm.

Pulse signals were generated using various kinds of power supply voltage in the produced oscillating circuits. Oscillating frequencies of the generated pulse signals were measured. The measured oscillating frequencies were normalized with respect to its average as 1, and a standard deviation was produced. The ordinate in FIG. 6 represents the standard deviation (%) of each of the oscillating circuits. As can be understood from FIG. 6, as the number of stages of inverters is greater, variations in the oscillating frequencies are reduced.

Second Embodiment

As described above, in the associative memory 100 according to the first embodiment, the WTA circuit 20 determines reference data to be Winner based on the oscillating frequencies of the pulse signals P₁to P_R. Therefore, as the difference in the oscillating frequency between the pulse P_iwith the highest oscillating frequency and the pulse signal P_iwith the second highest oscillating frequency is greater, erroneous detection of Winner is less likely to occur.

Referring to FIG. 7, an associative memory 110 according to the second embodiment includes a frequency dividing portion 35 between the memory portion 10 and the WTA circuit 20 in addition to the associative memory 100. The other structure of the associative memory 110 is the same as that of the associative memory 100.

The frequency dividing portion 35 includes a plurality of frequency dividers circuits FD₁to FD_R. The other structure of the associative memory 110 is the same as that of the associative memory 100.

The frequency divider circuit FD₁receives a pulse signal P₁from the oscillating circuit OC₁. Then, the circuit frequency-divides the frequency of the pulse signal P₁with a prescribed frequency dividing ratio. In this example, the frequency divider circuit FD₁frequency-divides the pulse signal P₁by 1.5. The frequency dividing ratio is however not limited to 1.5. The other frequency divider circuits FD₂to FD_Rfrequency divide the pulse signals P₂to P_Rwith the same ratio as that of the frequency divider circuit FD₁.

The judgment circuits JC₁to JC_Rin the WTA circuit 20 receive frequency-divided pulse signals P₁to P_R. The WTA circuit 20 determines Winner based on the frequency-divided pulse signals P₁to P_R.

When the pulse signal P_iis frequency-divided with a prescribed frequency-dividing ratio, the waveform change difference between the pulse signal P_iwith the highest oscillating frequency and the pulse signal P_iwith the second highest oscillating frequency can be increased. This will be described in conjunction with FIG. 8.

FIG. 8 is a waveform chart showing the waveforms of the pulse signals P₁and P₂when each frequency divider circuit FD_ifrequency-divides the pulse signal P_iwith a frequency dividing ratio of 1.5. In the chart, P₁(FD₁) represents the pulse signal P₁output from the frequency divider circuit FD₁. In the chart, P₂(FD₂) represents the pulse signal P₂output from the frequency divider circuit FD₂. In the chart, P₁represents the pulse signal P₁input to the frequency divider circuit FD₁and P₂represents the pulse signal P₂input to the frequency divider circuit FD₂.

Here, assume that the pulse signal P₁has the highest frequency and the pulse signal P₂has the second highest frequency. As shown in FIG. 8, the time difference between the pulse signals P₁and P₂in initial waveform change before they are input to the frequency divider circuits is Td1.

On the other hand, the time difference between the frequency-divided pulse signals P₁(FD₁) and P₂(FD₂) in initial waveform change is Td2. The time difference Td2 is greater than the time difference Td1. In short, the frequency divider circuits FD₁to FD_Rincreases the time difference between initial waveform change in the pulse signal to be Winner and initial waveform change in the pulse signal with the second highest frequency. This allows the WTA circuit 20 to determine Winner more surely.

Third Embodiment

As shown in FIG. 5, in the WTA circuit 20 in the associative memory 100, all the judgment circuits JC₁to JC_Rare connected to the one latch instruction node N40. The latch instruction node 40 in the WTA circuit 20 is long because it is connected to all the judgment circuits JC₁to JC_R. Therefore, the latch instruction node N40 has a large load capacity. Therefore, it also takes long until the latch instruction node N40 has its voltage level pulled to the ground voltage after the n-type MOS transistor in the discharge circuit 250 is turned on. If it takes long to lower the voltage level at the latch instruction node N40, it takes long to determine Winner.

Therefore, an associative memory according to the present embodiment includes a new WTA circuit 25 shown in FIG. 9 instead of the WTA circuit 20. The other structure is the same as that of the associative memory 100.

Referring to FIG. 9, the WTA circuit 25 includes a plurality of judgment blocks JB. The plurality of judgment blocks JB are connected in a plurality of stages in a tournament manner. In FIG. 9, they are in an n-stage tournament arrangement from the first stage as the lowermost stage to the n-th stage as the uppermost stage (n; a natural number equal to or greater than 2).

A plurality of judgment blocks JB1 arranged in the first stage as the lowermost stage include R first pulse judgment circuits PJC₁to PJC_R. Stated differently, the R first pulse judgment circuits PJC₁to PJC_Rare divided into the plurality of judgment blocks JB1.

The judgment circuits JB1 each include less than R first pulse judgment circuits PJC_iand a pulse reception judgment node N50. The first pulse judgment circuits PJC₁to PJC_Rdo not have the clock generator circuit 253 unlike the judgment circuits JC₁to JC_Rin FIG. 5. The other structure is the same as that of the judgment circuits JC₁to JC_R. The first pulse judgment circuits PJC₁to PJC_Rreceive pulse signals P₁to P_Rfrom corresponding oscillating circuits OC₁to OC_R.

Each of the judgment blocks JB1 further includes a pulse reception judgment node N50 and a pre-charge circuit 30. The pre-charge circuit 30 charges the pulse reception judgment node N50 upon receiving an enable signal ENAQ.

The pulse reception judgment node N50 is connected to a plurality of (less than R) first pulse judgment circuits PJC_iincluded in the judgment block JB1. More specifically, the node is connected to a discharge circuit 250 in each of the first pulse judgment circuits PJC_i.

There are R judgment circuits JC_iconnected to the latch instruction node N40 in FIG. 5. In contrast, the number of first pulse judgment circuits PJC_iconnected to the latch instruction node N50 in FIG. 9 is less than R. The pulse reception judgment node N50 has a load capacity smaller than that of the latch instruction node N40.

Among the judgment blocks connected in the tournament manner, the structure of the judgment blocks JB2 to JBnâˆ’1 arranged in the second to the (nâˆ’1)-th stages will be described. Referring to FIG. 9, the plurality of judgment blocks JB2 arranged in the second stage each include a pre-charge circuit 30, a pulse reception judgment node N50, and a plurality of second pulse judgment circuits PJ.

The second pulse judgment circuits PJ are each connected to a pulse reception judgment node N50 in a corresponding judgment block JB1. The second pulse judgment circuit PJ includes an inverter I20 and a discharge circuit 250. The second pulse judgment circuit PJ is connected to the pulse reception judgment node N50 in the judgment block JB2 to which it belongs. More specifically, the discharge circuit 250 in the second pulse judgment circuit PJ is connected to the pulse reception judgment node N50. The pre-charge circuit 30 charges the pulse reception judgment node N50 upon receiving an enable signal ENAQ.

The judgment blocks JB arranged in the third to (nâˆ’1)-th stages each have the same structure. A second pulse judgment circuit PJ in a judgment block JB provided in the (nâˆ’1)-th stage is connected to a pulse reception judgment node N50 in a corresponding judgment block JB among a plurality of judgment blocks JB arranged in the preceding stage, i.e., the (nâˆ’2)-th stage.

One judgment block JBn is provided in the n-th stage as the uppermost stage. The judgment block JBn newly includes a clock generator circuit 31 in addition to the judgment block JB2. The other structure is the same as that of the judgment block JB2.

The clock generator circuit 31 outputs a clock signal CLK when the pulse reception judgment node N50 attains an L level. The internal configuration of the clock generator circuit 31 is the same as that of the clock generator circuit 253 in FIG. 5. In other words, the clock generator circuit 31 includes an inverter circuit I21.

As described above, the WTA circuit 25 includes judgment blocks JB1 to JBn connected in a plurality of stages including the first to the n-th stages in a tournament manner. The number of the first or second pulse judgment circuits connected to each of the pulse reception judgment node N50 is smaller than the number of judgment circuits connected to the latch instruction node N40 in FIG. 5. Therefore, the load capacity of each pulse reception judgment node N50 is smaller than that of the latch instruction node N40. Therefore, it takes a shorter period of time to lower the level at the pulse reception judgment node N50 from its H level to its L level than for the latch instruction node N40.

In short, the arrangement of the judgment blocks JB1 to JBn in the tournament manner allows the load capacity of the pulse reception judgment node N50 to be small. Therefore, the time after the pulse signal P_iwith the highest frequency is received in the judgment block JB1 until a clock signal CLK is output can be shortened. Stated differently, it takes less time to determine Winner.

Fourth Embodiment

According to the first embodiment, a delay circuit DC_ijis provided for each data unit storage circuit US_ij. However, in such a configuration, a large number of transistor devices are necessary. Therefore, a single delay circuit may be arranged corresponding to a plurality of data unit storage circuits.

An associative memory according to the embodiment includes new oscillating circuits OSC₁to OSC_Rin place of the oscillating circuits OC₁to OC_R. The other structure is the same as that of the associative memory 100.

Referring to FIG. 10, the oscillating circuit OSC₁includes delay circuit DLC₁₁, DLC₁₂, . . . , and DC_1T(T: a natural numberâ‰§1) in place of delay circuits DC₁₁, DC₁₂, . . . , DC_1Wand distance judgment circuits DJ₁₁to DJ_1Tcompared to the oscillating circuit OC₁. The distance judgment circuits DJ₁₁to DJ_1Tcorrespond to the delay circuits DLC₁₁to DLC_1T. The other structure is the same as that of the oscillating circuit OC₁.

An activated NAND gate 300 inverts an input signal. The delay circuits DLC₁₁to DLC_1Teach invert an input signal. Therefore, the NAND gate 300 and the delay circuits DLC₁₁to DLC_1Tserve as inverting circuits. More specifically, the oscillating circuit OSC₁includes an odd number of inverting circuits. Therefore, there are an even number of delay circuits DLC₁₁to DLC_1T. The odd number of inverting circuits (NAND gate 300 and the delay circuits DLC₁₁to DLC_1T) are coupled in series in a loop shape.

The delay circuits DLC₁₁to DLC_1Teach determine the oscillating frequency of a pulse signal P₁based on comparison results by the two data unit comparator circuits UC_ij.

The distance judgment circuits DJ₁₁to DJ_1Treceive comparison results from the two data unit comparator circuits UC_ij(two signals path_ena and path_enaq). The Hamming distance is obtained based on these comparison results. Then, a signal corresponding to the obtained Hamming distance is output to corresponding delay circuits DLC₁₁to DLC_1T.

More specifically, the distance judgment circuit DJ₁₁receives comparison results from the unit data comparator circuits UC₁₁and UC₁₂. If all reference bit data pieces D stored in the unit data storage circuits US₁₁to US₁₂match corresponding search bit data pieces CAM (in other words, if the Hamming distance equals zero), the distance judgment circuit DJ₁₁outputs an H level signal S0. Then, L level signals S₁and S₂are output. Inverted signals /S0, /S1, and /S2 of the signals S0, S1 and S2 are output.

If one of the reference data pieces matches corresponding search bit data piece (in other words, if the Hamming distance equals one), the distance judgment circuit DJ₁₁outputs an H level signal S1 and low level signals S0 and S2.

If none of the two reference bit data pieces matches corresponding search bit data (if the distance equal two), the distance judgment circuit DJ₁₁outputs an H level signal S2 and L level signals S0 and S1.

As described above, the delay circuits DLC₁₁to DCL_1Tand the NAND gate 300 are connected in series in a loop shape. Among the plurality of delay circuits DLC₁₁to DLC_1T, the delay circuit DLC₁₁positioned at an end has its output terminal connected to an output node N10. The delay circuit DLC_1Tpositioned at the other end has its input terminal connected to the output terminal of the NAND gate 300.

The configuration of the delay circuit DLC₁₁is shown in FIG. 11. The delay circuit DLC₁₁includes a first delay stage 70, a second delay stage 71, an inverter I71, and a stage number selecting circuit 72. The stage number selecting circuit 72 includes transfer gates TG71, TG72 and TG73. The stage number selecting circuit 72 selects the number of stages of inverters to be used in response to signals S0 to S2 from the distance judgment circuit DJ₁₁. Stated differently, the stage number selecting circuit 72 selects delay time (oscillating frequency) in response to the Hamming distance.

The first and second delay stages 70 and 71 each include an even number of inverters connected in series. The first delay stage 70 receives an output from the delay circuit DLC₁₂in the preceding stage and delays it. The second delay stage 71 receives an output from the first delay stage 70 and delays it.

Transfer gates TG71 to TG73 in the stage number selecting circuit 72 are connected in parallel. The transfer gates TG71 to TG73 are made of an n-type MOS transistor and a p-type MOS transistor. The transfer gate TG71 turns on upon receiving an H level output signal S0 and an L level output signal /S0 from a corresponding distance judgment circuit DJ₁₁. Here, the output signal /S0 is an inverted signal of the signal S0. In short, the transfer gate TG71 turns on if reference data stored in the data unit storage circuits US₁₁and US₁₂both match search data (if the distance equals zero). At the time, the delay circuit DLC₁₁passes an input signal through the transfer gate TG71 for output to the inverter I71.

The transfer gate TG72 turns on upon receiving an H level signal S1 and an L level signal /S1 (an inverted signal of the signal S₁). More specifically, it turns on when the distance=1. At the time, the delay circuit DLC₁₁supplies the first delay stage 70 with an input signal. Then, an output from the first delay stage 70 is supplied to the inverter I71.

The transfer gate TG73 turns on upon receiving an H level signal S2 and an L level signal/S2 (an inverted signal of the signal S2). More specifically, it turns on when the distance=2. At the time, the transfer gate TG13 supplies the inverter I71 with an output from the second delay stage 71.

In short, the oscillating circuit DLC₁₁includes three paths (a short path with no delay stage, a middle path having the delay stage 71, and a long path having the delay stages 71 and 72) and the stage number selecting circuit 72 that selects one of the three paths. The paths are provided with different kinds of delay time. The oscillating circuit DLC₁₁selects one of the three paths in response to a comparison result between two reference bit data pieces and search bit data piece. In the above-described example, when the distance=0, the delay circuit DLC₁₁selects the short path. At the time, the number of stages of inverters to be used is one (the inverter I171 only). When the distance=1, the delay circuit DLC₁₁selects the middle path. At the time, the number of stages of inverters is five (the first delay stage 70 plus the inverter I71). When the distance=2, the delay circuit DLC₁₁selects the long path. At the time, the number of stages of inverters is nine (the first delay stage 70, the second delay stage 71 and the inverter I71).

Note that the delay circuits DLC₁₂to DLC_1Thave the same structure as that of the delay circuit DLC₁₁.

As described above, the delay circuit DLC changes the number of stages of inverters depending on a plurality of comparison results. Therefore, the oscillating circuit DLC₁₁can reduce the number of transistor devices to use in comparison with the oscillating circuit DC₁₁. Furthermore, when reference data and search data match (when the distance=0), the number of stages of inverters can be reduced. Therefore, a pulse signal with a higher frequency can be output. Consequently, the time required for the WTA circuit 20 to determine Winner can be shortened.

In the above-described example, the delay circuit DLC includes two delay stages and can set three kinds of delay time according to the number of delay stages to use. The delay circuit DLC selects the number of delay stages based on two comparison results obtained from two reference bit data pieces and two search bit data pieces. As a result, one of the three kinds of delay time is selected.

The delay circuit DLC can set delay time according to results of comparison between L (which is a natural number equal to or more than 2) pieces of reference bit data and search bit data. More specifically, the delay circuit DLC includes a plurality of delay stages and can set L+1 kinds of delay time according to the number of delay stages to use. The delay circuit DLC selects one kind of delay time (path) among L+1 kinds of delay time (paths) according to L results of comparison. A signal input to the delay circuit DLC is delayed by a selected kind of delay time and output to a delay circuit DLC in the next stage. In short, when L pieces of reference bit data and search bit data are compared, the delay circuit DLC includes L+1 paths. Different kinds of delay time are set for the paths.

Note that as shown in FIG. 12, inverters in the first stage in each of the first delay stage 70 and the second delay stage 71 may be tri-state inverters. A tri-state inverter I701 is activated upon receiving an H level signal S1 or S2. A tri-state inverter I702 is activated upon receiving an H level signal S2. When the distance=0 the first and second delay stages 70 and 71 do not operate, and when=1 the second delay stage 71 does not operate, so that power consumption can be reduced.

When the tri-state inverters I701 and I702 are inactive, the input nodes of the inverters in the second stage in each of the delay stages 70 and 71 attain a floating state. Therefore, the node level fluctuates by the effect of noise or the like, which could cause the inverter to operate. As shown in FIG. 13, using NOR gates 721 and 722 in place of the tri-state inverters I701 and I702, the input nodes of the inverters in the second stage do not attain a floating state. Therefore, the inverters in the second stage and on can be prevented from operating by the effect of noise and the like.

The NOR gate 721 operates as an NOT gate (inverter) upon receiving an L level signal /S1 or /S2. The NOR gate 722 operates as an NOT gate upon receiving an L level signal /S2.

Furthermore, as shown in FIG. 14, a dummy NOR gate 722 may be provided between the second delay stage 71 and the transfer gate TG73. In this way, the capacitances according to lines for each path can be equalized. Therefore, delay circuits for the paths can have the same design during designing.

Fifth Embodiment

The above-described associative memory 100 searches for the most similar reference data to search data. However, it is preferable to search for a plurality of similar data pieces to search data in some cases.

Referring to FIG. 15, an associative memory 200 according to this embodiment includes a new feedback circuit 50 in addition to the associative memory 100. The other structure is the same as that of the associative memory 100.

The feedback circuit 50 includes a plurality of feedback circuits 51 to 5R. The feedback circuits 51 to 5R are each activated upon receiving a control signal CON.

The feedback circuit 51 outputs an H level feedback signal upon receiving an H level judgment signal JS₁. The output node of the oscillating circuit OC₁is charged upon receiving the H level feedback signal. More specifically, the feedback circuit 51 charges the output node of the oscillating circuit OC₁upon receiving the H level judgment signal JS₁. Therefore, the output signal of the oscillating circuit OC₁is fixed at the H level. If a pulse signal P₁is output, it is invalidated.

The feedback circuit 51 does not charge the output node of the oscillating circuit OC₁when the judgment signal JS₁is in an L level. However, once the judgment signal JS₁attains an H level, the circuit continues to supply the output node of the oscillating circuit OC₁with an H level feedback signal thereafter.

Similarly, the feedback circuits 52 to 5R do not charge the output nodes of the oscillating circuits OC₂to OC_Runtil corresponding judgment signals JS₂to JS_Rattain an H level. However, once the judgment signals JS₂to JS_Rattain an H level, the circuit continues to charge the outputs nodes of the oscillating circuits OC₂to OC_Rthereafter.

The associative memory 200 having the above-described structure operates as follows.

The associative memory 200 initiates first search to start with. At the time, the associative memory 200 searches for reference data that is the most similar to search data.

First, search data is input to each of the comparator circuits C₁to C_R. Then, an enable signal ENA attains an H level, which starts the operation of the oscillating circuits OC₁to OC_R. Now, assume that reference data stored in the storage circuit S₂is the most similar data to the search data. In this case, a judgment signal JS₂attains an H level, and the other judgment signals JS₁and JS₃to JS_Rattain an L level.

The feedback circuits 51 to 5R are activated upon receiving a control signal CON. The feedback circuit 52 charges the output node of the oscillating circuit OC₂upon receiving the H level judgment signal JS₂. As a result, the voltage level at the output node of the oscillating circuit OC₂is maintained in an H level. Therefore, a pulse signal P₂output from the oscillating circuit OC₂is invalidated.

When the first search is complete, the enable signal ENA input to the oscillating circuits OC₁to OC_Ris inactivated (pulled to an L level).

Then, the associative memory 200 carries out the second search. At the time, the enable signal ENA attains an H level again. The oscillating circuits OC₁to OC_Routput pulse signals P₁to P_Rbased on the same comparison result as the result for the first search.

The output node of the oscillating circuit OC₂is however kept in the H level by the feedback circuit 52. Therefore, the pulse signal P₂is invalidated, so that the output signal of the oscillating circuit OC₂is kept in the H level. Therefore, the WTA circuit 20 determines reference data that is the most similar to the search data based on the signals P₁and P3 to P_Rother than the pulse signal P₂. Now assume that reference data stored in the storage circuit S₁is the most similar data to the search data. In this case, the judgment signal JS₁attains an H level and the signals JS₂to JS_Rattain an L level.

Reference data corresponding to the signal JS₁that has attained an H level by the second search (in other words, the reference data stored in the storage circuit S₁) corresponds to the reference data that is the second most similar to the search data.

When the judgment signal JS₁attains an H level, the feedback circuit 51 charges the output node of the oscillating circuit OC₁. In short, the feedback circuit 51 invalidates the pulse signal P₁of the oscillating circuit OC₁. During the third search, the oscillating circuits OC₁and OC₂cannot output a pulse signal. Therefore, reference data that is the most similar to the search data is searched among the reference data other than the reference data that has already been subjected to the searches (the reference data in the storage circuit S₁and S₂). The reference data found by the search corresponds to the third most similar data to the search data.

As in the foregoing, In the j-th search (j is an integer that satisfies 1<jâ‰¦k, and k is an integerâ‰§2), the associative memory 200 invalidates outputs from the oscillating circuits OC_icorresponding to the judgment circuits JC_ithat have output an H level judgment signal JS_iuntil the (jâˆ’1)-th search. In this way, every time search processing is carried out, reference data similar to search data can be found in the order of degrees of similarity to the search data.

Sixth Embodiment

The associative memory 200 according to the fifth embodiment can search for a plurality of reference data pieces in the order of degrees of similarity to the search data by invalidating the output of the oscillating circuit OC_iusing the feedback circuit 50. However, only one reference data piece can be searched for by one search processing. Therefore, when a plurality of pieces of reference data similar to the search data are searched for, the search processing must be carried out as many times as the number of necessary reference data pieces.

FIG. 16 is a functional block diagram of an associative memory 300 according to the embodiment. Referring to FIG. 16, the associative memory 300 includes a counter portion 40 instead of the WTA circuit 20 when it is compared to the associative memory 100.

The counter portion 40 includes a plurality of counter circuits 41 to 4R. The counter circuit 41 receives a pulse signal P₁from the oscillating circuit OC₁and counts the pulses of the pulse signal P₁. If the count number reaches a prescribed number CT (such as 10), the count circuit 41 outputs an H level judgment signal JS₁.

Similarly, the counter circuits 42 to 4R receive pulse signals P₂to P_Rfrom the oscillating circuits OC₂to OC_R, respectively and then count the pulses of the pulses signals P₂to P_R. When the count number reaches a prescribed number CT, the counter circuits 42 to 4R sequentially output H level judgment signals JS₂to JS_R.

As described above, the oscillating circuits OC₁to OC_Rraise the oscillating frequencies of the pulse signals P₁to P_Ras corresponding reference data pieces are more similar to the search data. As the oscillating frequencies of received pulse signals P₁to P_Rare higher, the counter circuits 41 to 4R output H level judgment signals JS₁to JS_Rearlier. In the other words, the judgment signals JS₁to JS_Rrise to H level sequentially in the order of the degrees of how corresponding reference data is similar to the search data. The counter portion 40 can determine reference data in the order of degrees of similarity to the search data based on the order of output of the H level judgment signals JS₁to JS_R.

As in the foregoing, the associative memory 300 can search for a plurality of pieces of reference data that are similar to search data by single search processing.

Seventh Embodiment

In the above-described embodiments, the Hamming distance is applied to the associative memory. However, the associative memory according to the present invention can also be applied with the Manhattan distance.

Referring to FIG. 17, an associative memory 400 includes a memory array portion 10 and a WTA circuit 20 similarly to the associative memory 100.

The memory array portion 10 includes a memory portion 1, a row decoder 2, a column decoder 3, a Read/Write circuit 4, and a search data storage circuit 5 similarly to FIG. 1.

The unit data storage circuits US₁₁to US_1W, US₂₁to US_2W, . . . , and US_R1to US_RWin the memory portion 1 each store reference data on a K-bit basis.

Now, assume that a unit data storage circuit US_ij(1â‰¦jâ‰¦W) is arranged in the i-th row (1â‰¦iâ‰¦R). Among reference data REF_istored in the storage circuit S_iin the i-th row, data stored in the unit data storage circuit US_ijis reference data REF_ij. More specifically, reference data REF_istored in the i-th row includes data REF_i1, REF_i2, . . . REF_ij, . . . , and REF_iw. Search data input from the outside is data SW. The search data SW includes data SW₁, SW₂, . . . SW_j, . . . , and SW_w.

The Manhattan distance between the search data SW and reference data REF_iis indicated by the following expression (1):

$\begin{matrix} D_{Manh, i} = {âˆ‘}_{j = 1}^{w} î¢ž î¢ž ï˜ƒ SWj - REFij ï˜„ & (1) \end{matrix}$

As described above, the unit data storage circuit US_ijstores k-bit reference data REF_ij. Therefore, the unit data storage circuit US_ijincludes k storage circuits (such as SRAM devices). The storage circuits each store reference bit data in each digit position of the reference data REF_ij(reference bit data in the first digit position to reference bit data in the most significant digit (k-th digit) position).

The unit data comparator circuit UC_ijcalculates the Manhattan distance between the reference data REF_ij(k bits) stored in a corresponding unit data storage circuit US_ijand search data SW_j(k bits).

FIG. 18 is a functional block diagram showing a unit data storage circuit, a unit data comparator circuit, and an oscillating circuit arranged in the first row (i=1).

The unit data storage circuit US₁₁includes K storage circuits SRAM₁₁to SRAM_1K. The storage circuit SRAM₁₁stores reference bit data in the first digit position of the reference data REF₁₁. Similarly, the storage circuit SRAM_1Kstores reference bit data in the K-th digit position of the reference data REF₁₁.

The unit data comparator circuit UC₁₁includes a K bit subtracter 410 and an absolute value operation circuit 420. The K bit subtracter 410 and the absolute value operation circuit 420 calculate the absolute value of the difference between the search data SW₁and the reference data REF₁₁.

More specifically, the K bit subtracter 410 obtains the difference between reference bit data in the first digit position of the reference data REF₁₁and search bit data in the first digit position of the search data SW₁. The absolute value operation circuit 420 converts the differential value into an absolute value and outputs the value as output signals OJ1 and /OJ1. The output signal /OJ1 is an inverted signal of the output OJ1.

Similarly, the K bit subtracter 410 obtains the difference between reference bit data in the second digit position of the reference data REF₁₁and search bit data in the second digit position of the search data SW₁. The absolute value operation circuit 420 converts the differential value into an absolute value and outputs the result as output signals OJ2 and /OJ2. The K bit subtracter 410 and the absolute value operation circuit 420 carry out calculation about bit data in the third digit position and on of the reference data REF₁₁in the same manner and output signals OJ3 to OJK and /OJ3 to /OJK.

Comparison results (output signals OJ1 to OJK multiplied by W) between the reference data REF₁₁to REF_1Wstored in the data unit storage circuits US₁₁to US_1Win the same first row and search data SW₁to SW_ware all input to the same oscillating circuit OCM₁.

The oscillating circuit OCM₁determines an oscillating frequency for a pulse signal P₁to be output based on a comparison result by the comparator circuit C₁, in other words in response to the obtained Manhattan distance between the reference data REF₁and the search data SW.

FIG. 19 is a functional block diagram of the oscillating circuit OCM₁. The oscillating circuit OCM₁includes an even number of delay circuits DL101 to DL 10W and a NAND gate 300. The even number of delay circuits DL101 to DL10W and the NAND gate 300 function as an inverting circuit that inverts an input signal in operation. Therefore, the oscillating circuit OCM₁includes a plurality of inverting circuits coupled in series in a loop shape. The output of the delay circuit DL101 is output externally and input to the NAND gate 300 as well. More specifically, the delay circuits DL101 to DL10W and the NAND gate 300 form a ring oscillator.

The delay circuit DL 101 corresponds to the data unit storage circuit US₁₁. The delay circuit DL102 corresponds to the data unit storage circuit US₁₂. Hereinafter, the delay circuits DL103 to DSL10W correspond similarly to the data unit storage circuit US₁₃to US_1W, respectively.

FIG. 20 shows the configuration of the delay circuit DL101. The delay circuit DL101 includes a plurality of delay circuits DJ₁to DJ_Kand an inverter I50. The delay circuits DJ₁to DJ_Kand the inverter I50 are connected in series.

The delay circuit DJ₁includes a delay stage DEL1 and a stage number selecting circuit 55. The delay stage DEL1 includes a plurality of inverters connected in series. The delay circuit DJ₁selects the number of stages of inverters to be used in response to an output signal OJ1. Stated differently, the delay circuit DJ₁selects whether or not to use the delay stage DEL1 in response to the signal OJ1.

The distance judgment circuit DJ₁receives an output from the delay circuit DL102 and obtains the distance of the reference bit data in the first digit position in the reference data REF₁₁stored in the unit data storage circuit US₁₁based on the signals OJ1 and /OJ1 output from the unit data comparator circuit UC₁₁. When the reference bit data in the first digit position of the reference data REF₁₁matches search bit data in the first digit position of the search data SW₁, the signal OJ1 attains an H level and the signal /OJ1 attains an L level. On the other hand, when reference bit data in the first digit position of the reference data REF₁₁does not match the search bit data in the first digit position of the search data SW₁, the signal OJ1 attains an L level and the signal /OJ1 attains an H level.

The stage number selecting circuit 55 includes transfer gates TG10 and TG11. The transfer gates TG10 and TG11 are connected in parallel. The delay stage DEL1 is connected between an input terminal of the delay circuit DJ₁and the transmission gate TG10.

When the reference bit data in the first digit position of the reference data REF₁₁matches the search bit data in the first digit position of the search data SW₁, the transfer gate TG11 turns on and the transfer gate TG10 turns off. In this case, an input signal passes through the transfer gate TG11 without passing through the delay stage DEL1 and output to the outside.

On the other hand, when the reference bit data in the first digit position of the reference data REF₁₁does not match the search bit data in the first digit position of the search data SW₁, the transfer gate TG10 turns on. In this case, an input signal is delayed by delay time Î”T1 set at the delay stage DEL1 and output externally.

In short, the delay circuit DJ₁can set two kinds of delay time and selects the longer delay time of the two kinds of delay time when the reference bit data and the search bit data are different.

The delay circuits DJ₂to DJ_Koperate similarly to the delay circuit DJ₁. The delay circuits DJ₂to DJ_Kcan set two kinds of delay time and select one of the two kinds of delay time in response to a comparison result between the reference bit data and the search bit data. Therefore, the delay circuit DL101 can set 2^Kkinds of delay time based on a comparison result between k bit reference bit data and k bit search bit data. Stated differently, the delay circuit DL101 includes 2^kdifferent kinds of delay time and select a path in response to the Manhattan distance between k pieces of reference bit data and k pieces of search bit data.

Delay time at the delay stage in the delay circuit DJ₂is twice as long as that of the delay stage DEL₁. More specifically, every time the digit is shifted up, the delay time Î”T is set longer. In this way, as the digit is closer to the most significant bit, the delay time is prolonged. More specifically, as the Manhattan distance increases, the delay time is prolonged.

The delay circuits DL102 to DL10W have the same configuration as that of the delay circuit DL101 and operates in the same manner. Therefore, the oscillating circuit OCM₁outputs a signal with an oscillating frequency according to the Manhattan distance between the reference data and the search data stored in the storage circuit S1. More specifically, as the Manhattan distance between the reference data and the search data is shorter, a signal with a higher oscillating frequency is output.

The foregoing description is about the structure and operation of the storage circuit S₁, the comparator circuit C₁and the oscillating circuit OCM₁in the first row. The structure and operation of the storage circuits S₂to S_R, the comparator circuits C₂to C_R, and the oscillating circuits OCM₂to OCM_Rin the second row and on are the same as those of the storage circuit S₁, the comparator circuit C₁and the oscillating circuit OCM.

Therefore, the associative memory 400 can change the oscillating frequency depending on the distance similarly to the associative memory 100.

Eighth Embodiment

An associative memory according to the present invention can be applied not only to the Hamming distance and the Manhattan distance but also to the Euclidean distance.

The structure of the associative memory 400 applied to the Euclidean distance is the same as that of the associative memory 400. The unit data storage circuits US₁₁to US_1W, US₂₁to US_2W, . . . , and US_R1to US_RWeach store reference data on a K-bit basis. In the reference data REFi stored in the storage circuit S_iin the i-th row, data stored in the unit data storage circuit US_ijis reference data REF_ij. More specifically, the reference data REF_istored in the i-th row includes REF_i1, REF_i2, . . . , REF_ij, . . . , and REF_iw. Externally input search data is SW. The search data SW includes SW₁, SW₂, . . . , SW_j, . . . , and SW_w.

The Euclidean distance between the search data SW and the reference data REF_iis indicated by the following expression (2):

$\begin{matrix} D_{Eucl, i} = \sqrt{{âˆ‘}_{j = 1}^{w} î¢ž î¢ž ï˜ƒ SWj - REFij ï˜„} & (2) \end{matrix}$

The unit data storage circuit US^ijstores k-bit reference data REF_ij. Therefore, the unit data storage circuit US_ijincludes K storage circuits (SRAM devices). The storage circuits store bit data in respective digit positions of the reference data REF_ij(bit data in the first digit position to the most significant bit data (in the k-th digit position)).

The unit data comparator circuit UC, calculates the Euclidean distance between the reference data REF_ij(k bits) stored in a corresponding unit data storage circuit US_ijand search data SW_i(k bits).

FIG. 21 is a functional block diagram of a unit data storage circuit, a unit data comparator circuit, and an oscillating circuit arranged in the first row (i=1).

The unit data storage circuit US₁₁includes K storage circuits SRAM₁₁to SRAM_1K. The storage circuit SRAM₁₁stores bit data in the first digit position of the reference data REF₁₁. Similarly, the SRAM_1Kstores bit data in the K-th digit position of the reference data REF₁₁.

The unit data comparator circuit UC₁₁includes a K bit subtracter 410, an absolute value operation circuit 420, a comparison current signal generator circuit 430, an analog square circuit 440, and an A/D converter 450.

The K bit subtracter 410 and the absolute value operation circuit 420 calculate the absolute value of the difference between the search data SW₁and the reference data REF₁₁. The calculation result is converted into analog current in a value corresponding to the absolute value by a corresponding comparison current signal generator circuit 430.

The converted analog current is squared at the analog square circuit 440. In this way, the Euclidean distance between the reference data REF₁₁and the search data SW₁is output as an analog current value.

The A/D converter 450 digitally converts an output analog current. In this way, the Euclidean distance is output as n-bit digital data.

The oscillating circuit OCE₁outputs a pulse signals P₁with an oscillating frequency corresponding to the Euclidean distance similarly to the oscillating circuits OC₁and OCM₁. The oscillating circuit OCE₁includes a delay stage including a plurality of inverters and a stage number selecting circuit. The stage number selecting circuit in the oscillating circuit OCE₁selects a smaller number of stages of inverters to use as the Euclidean distance is smaller. Therefore, a pulse signal P₁with a higher oscillating frequency is output as the Euclidean distance is smaller.

The unit data storage circuits US₁₂to US_1Wand the unit data comparator circuits UC₁₂to UC_1Win the storage circuit S₁in the first row operate similarly to the above. The structure and operation of the storage circuits S₂to S_R, the comparator circuits C₂to C_Rand the oscillating circuits OCE₂to OCE_Rin the second row and on are the same as those of the storage circuit S₁, the comparator circuit C₁and the oscillating circuit OCE₁. Therefore, the associative memory to which the Euclidian distance is applied can change its oscillating frequency in response to the distance similarly to the associative memory 100.

Ninth Embodiment

The WTA circuit 20 (FIG. 5) and the WTA circuit 25 (FIG. 9) are described in conjunction with the above embodiments. However, the WTA circuit is not limited to those shown in FIGS. 5 and 9.

FIG. 22 shows another example of the WTA circuit. Referring to FIG. 22, the WTA circuit 350 includes a detector circuit 351 and a plurality of judgment circuits JC₁₁to JC_1R. The judgment circuit JC₁₁corresponds to the oscillating circuit OC₁and receives an output from the oscillating circuit OC₁. Similarly, the judgment circuit JC₁₂corresponds to the oscillating circuit OC₂and the oscillating circuit JC_1Rcorresponds to the oscillating circuit OC_R.

The judgment circuit JC₁₁does not have a discharge circuit 250 and a clock generator circuit 253 when it is compared to the judgment circuit JC₁. The other structure is the same as that of the judgment circuit JC₁. The judgment circuits JC₁₂to JC_1Rhave the same structure as that of the judgment circuit JC₁₁.

The detector circuit 351 receives outputs from the oscillating circuits OC₁to OC_Rand detects the earliest output pulse signal. The detector circuit 351 outputs a detection signal upon receiving the earliest output pulse signal. More specifically, the detector circuit 351 receives an output from an inverter I20 in each of the judgment circuits JC₁₁to JC_1Rand outputs a detection signal upon receiving a pulse signal from any of the inverters I20 for the first time.

A latch circuit 252 in each of the judgment circuits JC₁₁to JC₁₂receives an output from the inverter I20. More specifically, the circuit receives an output signal from a corresponding one of the oscillating circuits OC₁to OC_R. Then the circuit latches an output signal from the oscillating circuits OC₁to OC_Rupon receiving a detection signal.

When the judgment circuit JC₁₁receives the earliest output pulse signal (i.e., when the oscillating circuit OC₁outputs a pulse signal with the highest frequency), the latch circuit 252 in the judgment circuit JC₁₁latches an H level signal. The latch circuits 252 in the other judgment circuits JC₁₂to JC_1Rlatch an L level signal. Consequently, the judgment circuit JC₁₁outputs an H level judgment signal representing Winner and the other judgment circuits JC₁₂to JC_1Routput judgment signals JS₂to JS_Rrepresenting Loser.

The detection circuit 350 may be a wired OR circuit that receives an output from an inverter I20 in each of the judgment circuits JC₁₁to JC_1Ror may include a plurality of stages of OR circuits.

While preferred embodiments of the present invention have been described, it is to be understood that the same is simply by way of illustration and is not restrictive. The above described embodiments can be carried out with variations and modifications without departing the scope and spirit of the present invention.