三级内容寻址存储器单元

摘要

公开一种具有三比特存储的三级CAM单元。三比特存储配置成支持可以从CAM单元读出而不需要电荷恢复操作的三种稳定状态。三种稳定状态是指以下状态：当三比特中一个比特处于第一逻辑状态时，其余两个比特处于第二逻辑状态。这三种稳定状态可以用来对三进制CAM中所使用的三种逻辑状态进行编码。

说明书

本申请要求美国临时申请No.60/324462(2001年9月25日提交)的权利，所述申请的内容作为参考全部包括在本文内。

发明领域

本发明一般涉及数据半导体存储器，更具体地说，涉及三级内容寻址存储器(CAM)单元。

发明背景

许多应用要求高速搜索信息。在许多网络装置中，例如交换机或路由器，数据包是根据嵌入的地址信息的内容来传输的。因此，为了获得高数据传输率，网络系统必需能够进行非常高速的搜索和比较。对此功能有用的一类电路是内容寻址存储器或CAM。应当指出，虽然以下进行的讨论是在网络系统的范围内，但有许多其它应用也要求高速的搜索和比较，因此也可从本发明受益。例如，超高速缓缓冲存储器的标志字段也要求高速搜索，也可利用CAM来实现。

比较一下CAM和传统的存储器件例如随机存取存储器(RAM)是有用的。在某种程度上，CAM和RAM器件的工作是相反的。例如，通过向RAM提供读出指令和地址来读出RAM。RAM通过输出在规定地址中存储的数据作为响应。但在读出CAM时，向CAM提供一个数据样值，而CAM返回一个匹配信号，表明所述数据样值是否存储在CAM中，如果是，则返回CAM中含有与所述样值匹配的数据的地址。

网络交换机和路由器通常采用匹配功能，其中，将数据包的一部分例如地址字段与数据表目列表进行比较。所述列表常称为数据库。图1是示范的CAM装置100的方框图，CAM装置100包括：CAM阵列110，用于存储数据库；匹配检测电路120，用于检测匹配；任选的优先级编码器130，用于在适当的时候按优先级顺序选择和输出匹配地址。CAM装置还包括控制器140，用于控制CAM阵列110、匹配检测逻辑120和优先级编码器130的工作并且用于通过数据线150a、地址线150b和控制线150c使CAM装置100与其它装置连接。例如，市售CAM装置可支持对具有多达16384表目的数据库搜索136比特宽的数据样值。可以用高达每秒1亿次的搜索速率对市售CAM装置进行搜索。CAM这种以高速对较大数据库快速搜索较宽数据字的能力使它们在诸如网络路由选择和交换等应用中非常有用。

有两种类型的搜索值得注意，即，准确匹配搜索和部分匹配搜索。在准确匹配搜索中，仅当数据样值和存储在CAM中的某表目逐个比特都匹配时，所述表目才算与数据样值匹配。在部分匹配搜索中，仅在字的子集比特上进行搜索。就是说，除了逻辑“0”和“1”状态外，还允许CAM表目规定第三个“随意”状态。在进行部分匹配搜索时，只要以逻辑“0”或“1”状态设置的表目中每个比特与数据样值的相应部分匹配，则表目CAM就与数据样值匹配。

具有仅支持逻辑“0”和逻辑“1”状态的表目的CAM称为二进制CAM，仅能支持准确匹配搜索。具有也支持使用“随意”状态的表目的CAM称为三进制CAM，可以用于部分匹配搜索中。(当表目不含有任何“随意”状态时，这些CAM也支持准确匹配搜索。)

在三进制CAM中，存储在CAM阵列110中的数据库的每个比特必需以至少两个比特来代表，以便对三个所需的逻辑状态(“0”，“1”和“随意”)进行编码。虽然可以用许多不同的技术来构建CAM阵列110，但现代CAM装置使用基于其中数据存储在触发器中的静态随机存取存储器(SRAM)的存储元件，或者使用基于其中数据以电容器上电荷的形式存储的动态随机存取存储器(DRAM)的存储元件。图2示出基于DRAM技术的CAM单元200。

单元200包括晶体管202和电容器203，二者串联在位线201和地电位206之间，如图2所示。选择线连接到晶体管202的栅极。此外，单元200固有地具有寄生电容，在图2中以电容器204表示，连接在位线201和地206之间。接通晶体管202(通过线205)，迫使位线201到高或低状态，数据就可存储在单元200中。这就导致电容器203充电或放电，直到节点207的电位等于位线的电位。然后晶体管202断开(通过线205)，节点207的电位由存储在电容器203中的电荷维持。

为了读出存储在单元200中的数据，将位线201预充电到高电平。这可确保寄生电容204也充电。然后接通晶体管202(通过线205)。如果电容器203存储的电荷使节点207的电位为高，则节点207和位线201的电位没有变化。电容器203的电荷电平也不改变。但如果电容器203存储的电荷使节点207的电位为低，那么，电荷就会从位线201经过晶体管202流入电容器203。这就导致位线201的电位降低而节点207处的电位增加。电容器203的电荷电平也增加。可以检测位线201中和/或节点207处的电压变化，以便确定电容器202中存储的逻辑状态。

图2所示的CAM单元存储一比特数据，所以只能对两种状态进行编码。如前所述，三进制CAM需要能对三种状态进行编码的单元。图3所示的300电路类似于图2所示的200电路，但包括两个存储元件。这样使单元300可以存储两个比特，能对四种状态进行编码，其中三种就足以满足三进制CAM单元的存储要求。

和动态CAM单元200、300相关联的一个问题是读出操作可能是破坏性的。例如，在单元200中，当在电容器202存储有低电荷电平的单元上进行读出操作时，来自位线201的电荷流在读出操作时改变了电容器202的电荷电平。于是，在CAM 200、300中，在每次读出操作后都需要有电荷恢复操作。每次读出后都需要进行电荷恢复操作就限制了CAM装置的速度。电荷恢复电路(未示出)还要求附加的组件，并增加了功耗。

图4示出另一CAM单元400。和前述的CAM单元300比较，CAM单元400包括两个附加的晶体管402a和402b，它们分别和数据存储电容器203a和203b并联。晶体管402a的栅极连接到节点207b，而晶体管402b的栅极连接到节点207a。这两个晶体管402a和402b为电路400提供了防止破坏性读出的有限保护形式。更具体地说，仅在电容器203a和203b存储有相反的电荷(即“0”+“1”或“1”+“0”)时，CAM单元400才可无破坏地读出。这样，如果CAM单元400和仅允许在CAM单元400中存储这两种相反的电荷状态的控制电路(例如图1的控制器140)一起使用，则CAM单元400就可以用作动态二进制CAM单元，读出后不需要电荷恢复。遗憾的是，CAM单元400不适合使用三进制CAM单元，因为三进制CAM单元必需能够存储至少三种状态。所以，需要一种方法和装置，用于在每次读出操作后不需要电荷恢复的有效动态CAM单元体系结构。

发明概述

本发明针对一种三进制CAM单元，其存储电荷的方式类似于DRAM单元，但可以无破坏地读出。就是说，读出操作后不需要有电荷恢复操作来维持数据的完整性。三进制CAM的三种所需状态(逻辑“0”，逻辑“1”和“随意”)可以利用三比特存储进行存储。使用每个CAM单元三比特存储就允许使用包括可以无破坏地读出的三种状态的电路拓扑。

附图简要说明

从以下参阅附图对本发明的示范实施例所作的详细说明，本发明的上述和其它优点和特征就可一目了然，附图中：

图1为内容寻址存储器的方框图；

图2为二进制CAM单元的电路图；

图3为基于图2的二进制CAM的三进制CAM单元的电路图；

图4为具有两比特存储的CAM单元的电路图，所述CAM单元可用作能无破坏读出的二进制CAM单元；

图5为三级存储元件的电路图；

图6为具有每单元三比特存储的三进制CAM的电路图；

图7为利用图6所示的三进制CAM单元阵列的CAM装置的方框图；

图8为采用图7所示的CAM装置的网络装置的方框图。

发明的详细说明

本发明的CAM单元体系结构示于图6的CAM单元600，利用具有特殊性质的三级存储元件以支持不需电荷恢复操作的读出。但在详细讨论本发明的CAM单元体系结构的构造和工作之前，先分析一下图5的三级存储电路500的工作会有所帮助，因为电路500和单元600之间有许多相似之处。

三级存储电路500(图5)包括三个“与非”门501、502、503，它们分别将三个输入端D0、D1、D2连接到三个输出端Q0、Q1、Q2。每个”与非”门501、502、503的输出也作为输入连接到其它的“与非”门。例如，“与非”门501的输出Q0作为输入提供到“与非”门502、503。用这种方式使用反馈限制了电路500的稳定输入/输出状态数。具体地说，电路500支持三种稳定状态，其中电路500的三个输入端D0、D1、D2中只有一个是逻辑“1”(其余的输入端每个都是逻辑“0”)，且三个输出端Q0、Q1、Q2中只有一个是逻辑“0”(其余的输出端每个都是逻辑“1”)。这三种稳态示于以下真值表中。

       输入       输出D0 D1 D2 Q0 Q1 Q2 1 0 0 0 1 1 0 1 0 1 0 1

 0 0 1 1 1 0

上述真值表的一个重要方面是当一个输出端(例如Q1)是逻辑“0”状态时，由于“与非”门501、502、503的连接方式，其余的输出端(例如Q2，Q3)就被迫取逻辑“1”状态。

本发明的CAM单元600(图6)基于上述电路的稳态特性。CAM单元600是动态CAM单元，包括形式为电容器203a、203b、203c的三个存储元件。每个电容器与各自的位线201a、201b、201c相关联。在位线201a、201b、201c和电容器203a、203b、203c之间的存取受晶体管202a、202b、202c控制，这三个晶体管每个的栅极都连接到线205。

电容器203a、203b、203c各自与两个放电装置相关联。在图示的实施例中，放电装置为晶体管。例如，电容器203a、203b、203c分别与第一组晶体管402a、402b、402c并联。晶体管402a、402b的栅极连接到节点207c。晶体管402c的栅极连接到节点207b。电容器203a、203b、203c还分别与晶体管602a、602b、602c并联。晶体管602a的栅极连接到节点207b。晶体管602b、602c的栅极连接到节点207a。

利用类似于三级存储电路500的原理来设计上述电路拓扑，因为上述电路拓扑支持三稳态，其中三个电容器203a、203b、203c中仅一个存储高电平电荷(例如逻辑“1”)，而其余两个电容器放电(例如逻辑“0”)。具体地说，节点207a、207b、207c分别与电容器203a、203b、203c相关联并且其作用非常类似于电路500的反馈特性。这是因为一个电容器的电荷电平通过所述节点之一连接成控制连接到其它电容器的放电装置。例如，如果电容器203a存储了高电荷，则节点207a就会处于高电位。节点207a连接到晶体管602b的栅极和晶体管602c的栅极，于是这两个晶体管602b、602c就会导通。当晶体管602b导通时，电荷就会从电容器203b流经晶体管602b到地206。同理，当晶体管602c导通时，电容器203c会通过晶体管602c放电到地206。

可以通过将位线201a、201b、201c中的一条设定为高逻辑电平(例如逻辑“1”)而将其余两条位线保持在低逻辑电平(例如逻辑“0”)来对单元600进行写入。一旦位线201a、201b、201c被设定到适当的电压电平，逻辑高信号就置于线205上，导致晶体管202a、202b、202c的栅极导电，从而将对应于高逻辑电平的电荷传输到与设定为高逻辑电平的位线201a、201b、201c相关联的电容器203a、203b、203c之一，并将对应于低逻辑电平的电荷传输到与设定为低逻辑电平的位线201a、201b、201c相关联的电容器203a、203b、203c中的两个电容器。

可以通过将位线201a、201b、201c预充电到高电平，接通存取晶体管202a、202b、202c并观察位线201a-201c上的电位变化来对单元600进行读出。如前所述，当一个电容器存储有高电平电荷时，读出过程不会降低所述电容器的电荷电平。于是，处于高逻辑状态的电容器在读出过程中将保持高逻辑状态。在单元600中，当一个电容器处于低逻辑状态时，在读出过程中也将保持此逻辑状态，因为其它的电容器之一将处于高逻辑状态，确保与具有低逻辑状态的电容器并联的晶体管之一会放电到地。因此，所以单元600可以用作在每次读出操作后不需要电荷恢复步骤的CAM阵列的标准部件。

所以，本发明是针对三级CAM单元600的。CAM单元600(图6)包括配置成9晶体管体系结构的三比特存储。所述体系结构包括三种稳态，其中，三个比特中只有一个比特为逻辑“0”，其它两个比特为逻辑“1”。这三种稳态足以对三进制CAM所需的逻辑“0”，“1”和”随意”状态编码。这三种稳态也可读出，而不需要电荷恢复过程，而能维持存储的完整性。

图7示出利用本发明的CAM单元600的阵列110’的CAM装置700。匹配检测电路120’连接到阵列110。CAM装置700还可以任选地包括连接到匹配检测电路120的优先级编码器130。控制电路140’连接到阵列110’、匹配检测电路120、优先级编码器130以及数据线150a、地址线150b和控制信号线150c。控制电路140’和匹配检测电路120’与传统的对应的部件类似，但已适合于处理将CAM单元的三种稳态(即100，010，001)映象到三进制CAM的“0”、“1”和“随意”状态的编码操作。例如，状态100可对应于逻辑“0”、状态010可对应于逻辑“1”、而状态001可对应于“随意”状态。优先级编码器130可以连接到匹配检测电路，对CAM装置700的输出作优先选择，如果装置700中有多条表目与数据样值匹配的话。

图8说明CAM装置700如何用在网络装置800中。网络装置800可以是例如网络路由器800，它检验从输入端口801接收到的每个数据包并将每个数据包路由到多个输出端口805之一。从每个输入端口801接收数据包后，将它们暂时存储在输入缓冲器802中。输入缓冲器802可以编制成队列并由控制逻辑803读出。每个数据包都包括地址字段。通常，地址字段的一部分规定了网络或子网地址，地址字段的另一部分规定了网络或子网上的节点。控制逻辑803检验队列802开头处的数据包，并确定所述多个输出端口(每个对应例如一个不同的网络或子网)中哪一个将接收所述数据包。控制逻辑803还可存储在CAM装置700中成对的每对新分辨的网络/子网地址-输出端口。当控制逻辑703检验新的数据包时，CAM装置700从数据包中搜索并提取网络或子网地址，用于以前已分辨的路由。在匹配的情况下，数据包被快速地传输到正确的输出端口，不需任何附加处理。

虽然已结合示范实施例对本发明作了详细的说明，但应理解本发明不限于上述公开的实施例。相反，可以修改本发明以便包括此文未说明的各种改型、更迭、替代或等效配置，但它们应是与本发明的精神和范围相当的。所以，本发明不限于以上的描述或附图，而仅受所附权利要求书的限制。