WO1992018981A1 - Device for detecting a certain logical value and decoding device for decoding the priority of address locations from a cam - Google Patents

Abstract

Device for detecting a certain value of a digital signal from two or more digitally supplied digital signals, for determining whether two or more of these digital signals have said certain value and/or which of the digital signals have said certain value, wherein the device comprises: means for performing a logic AND process on the two or more digital signals; means for generating a signal when two or more of the digital signals have said certain logical value; and means for passing that number or address that is assigned to each digital signal and of which the value or priority is the highest.

Description

DEVICE FOR DETECTING A CERTAIN LOGICAL VALUE AND DECODING DEVICE FOR DECODING THE PRIORITY OF ADDRESS LOCATIONS FROM A CAM.

Particularly when decoding the priority of address locations from a content addressable memory (CAM) wherein the content of address locations is compared simultaneously with the content of a reference register, problems occur 5 when the content of more than one address location corres¬ ponds with the content of the reference register. Such problems can considerably delay the transmission of data packages in a network to an end station to which the data have to be led. A reference part of the data word for trans-

10 mission is led for this purpose into said reference register of the CAM and compared with the content of the various address locations of the CAM, which determine the destina¬ tion of the data package. When this part corresponds with the content of more than one address location the data

15 package has to be transmitted to the destination with the highest priority, in practice usually the address location with the highest (or lowest) address.

One of the few CAMs already on the market is made commercially available by applicant under the type name

20 MU9C1480. Herein, when the content of more than one address location corresponds with the content of the reference register, a so-called multiple match flag is generated, whereafter, in the worst case, all other address locations of the CAM must be searched in order to be certain that the

25 destination with the highest priority is selected.

In the article "A Fault-Tolerant Associative Memory with High Speed Operation" by Harald Bergh et al, IEEE, Journal of Solid-state Circuits, Vol. 25, No. 4, August 1990, use is made of "carry look-ahead" in order to

30 accelerate this search to the corres^ponding address location i of highest priority.

The present invention provides a device for de¬ tecting a certain logical value of at least one signal from two or more digital signals, for determining whether two or more of these digital signals have said certain logical value, and/or which of the digital signals have said certain logical value, wherein the device comprises: - means for performing a logic AND process on the two or more digital signals;

- means for generating a signal when two or more of the digital signals have said certain logical value; and

- means for passing that number or address that is assigned to each digital signal and of which the value or priority is the highest.

Preferably a number of devices according to the present invention connected in tree structure are applied so that the desired information becomes available in extremely rapid manner, information such as whether or not a match has taken place, or more than one match has taken place, and the address (priority) of the match with the highest priority.

With a content of a CAM of 1024 locations, instead of 1024 sequential comparisons, or about 80 with carry look-ahead, an improvement to only 5 comparisons is obtained. If such a tree structure is embodied in CMOS, a decoding time of for instance 12 nsec or less can remain.

The present invention further provides a circuit for generating a digital signal when two or more digital input signals have a determined value, wherein the circuit comprises:

- six or more OR gates placed in parallel; and

- a NAND gate connected to the outputs of the OR gates. This circuit provides a multiple match flag when two or more input signals have said certain logical value (0 or

1).

Further advantages, features and details of the present invention will be elucidated in the light of a description of a preferred embodiment thereof, with refe¬ rence to the annexed drawing, in which:

Fig. 1 shows a block diagram of a preferred embo¬ diment of a device according to the present invention; Fig. 2A shows a logic diagram of a circuit according t_ he present invention which can be used with the preferred embodiment of fig. 1; and

Fig. 2B shows the logic diagram relating to the logic circuit of fig. 2A.

With the input of digital signals (I₀-I₃) , such as the match flags originating in the CAM process, to the four outputs, a flag is generated by the device according to the present invention as an output thereof, if one or more of these signals has a predetermined or certain digital value (0 or 1) , by means of a logic AND process. An output signal 0₂ further indicates whether more than one input signal has the determined digital value. The output signal A then indicates the address (in the present case of two bits) of the input signal of the said digital value with the highest priority, usually the highest or lowest address value of the one, two or more input signals with this determined value. A preferred embodiment of a circuit for obtaining the signal 0 is shown for example in fig. 2A where six OR gates G-_i-G₆ are connected in parallel to four input signals X, Y, Z, W, wherein the outputs of the OR gates are con¬ nected to a NAND gate. Fig. 2B shows that if two or more signals have a value 0 (X = don't care, i.e. 0 and 1 are both possible) , the output signal then generates the value 1.

When for example 1024 match flags have to be compared for priority, a tree structure with a first stage is formed from for example 256 of the devices shown in fig. 1 which are connected in parallel, a second stage of 64 of such devices, a third stage of 32 thereof etc., wherein at each stage address bits are added to the address designated with A in fig. 1.

The present invention is not of course limited to the described embodiment with four input signals, nor to the said tree structure of 1024 match flags. In the future greater numbers than 1024 are to be expected in large networks.

Claims

1. Device for detecting a certain value of a digital signal from two or more digitally supplied digital signals, for determining whether two or more of these digital signals have said certain value and/or which of the digital signals have said certain value, wherein the device comprises:

- means for performing a logic AND process on the two or more digital signals;

- means for generating a signal when two or more of the digital signals have said certain logical value; and - means for passing that number or address that is assigned to each digital signal and of which the value or priority is the highest.

2. Device as claimed in claim 1, provided with four inputs for four digital input signals.

3. Series of devices as claimed in claim 1 or 2, which are connected in a tree structure, i.e. wherein an output of a first device serves as an input for a device connected thereafter.

4. Circuit for generating a digital signal when two or more digital input signals have a determined value, wherein the circuit comprises:

- six or more OR gates placed in parallel; and

- a NAND gate which is connected to the outputs of the OR gates.

5. Decoding device for decoding the priority of address locations from a content addressable memory (CAM) when the content of multiple address locations corresponds with a reference data word entered in the reference register of the CAM.