优先编码器及优先编码方法

摘要

本发明的优先编码器,从含将要对地址编码的信号的多个输入信号中按预定优先度依次输出上述地址,包括:多个第一编码电路,分别输出第一编码信号和除该预定数之外表示是否存在将要对上述地址进行编码的信号的第一启动信号;多个多路复用器,用于仅输出优先度最高的将要对上述地址进行编码的信号的编码结果;第二编码电路,输出把上述第一启动信号作为输入而作为与该输入数相对应的位数的编码结果的第二编码信号和除该输入之外表示是否存在将要对该地址进行编码的信号的第二启动信号。

说明书

本发明涉及一种优先编码器，从包含将要对地址进行编码的信号的多个输入信号按照预先设定的优先度依次输出地址，特别是涉及进行从相联存储器的各存储单元所输出的一致信号的编码的优先编码器。

通常的存储器指定地址来进行数据的读出/写入，与此相对，在相联存储器(associative memory)即CAM(Content Addressable Memory)中，除了通常的RAM功能之外，还能输入检索数据，而输出关于与其相同或者类似的数据的有无以及该数据属于的字的其他数据和地址等信息。由于与检索数据相一致的字不限于一个，因此，当多个字与检索数据相一致的情况下，由通常的编码器不能得到正确的编码输出。因此，在CAM中需要优先编码器，来对从存储单元所输出的一致信号(表示与检索数据相一致的情况的信号)进行编码，按照预定的优先顺序依次输出地址信号。

作为现有的这种优先编码器，在日本专利公开公报特开平5-189979号中记载了该技术。图6是表示该特开平5-189979号中记载的优先编码器的构成的方框图。

在图6中，现有的优先编码器分层地设置最后位的层、中位的层和最前位的层这3层。最后位的层由从与被输入最前位的层(在图6中上侧是前位)的一致信号相对应的输出依次输出“1”的16个第一层优先电路11₀～11₁₅所构成，中位的层由与最后位的层相同的4个第二层优先电路12₀～12₃所构成。最前位的层由与最后位的层和中间的层相同的一个第三层优先电路13所构成。在第一层优先电路11₀～11₁₅的输出、第二层优先电路12₀～12₃的输出和第三层优先电路13的输出上连接从各自的输出信号输出编码结果(2位)的地址编码器14。

其中，第一层优先电路11₀～11₃的输出信号OR分别输入第二层优先电路12₀，同样，第一层优先电路11₄～11₇的输出信号OR分别输入第二层优先电路12₁，第一层优先电路11₈～11₁₁的输出信号OR分别输入第二层优先电路12₂，第一层优先电路11₁₂～11₁₅的输出信号OR分别输入第二层优先电路12₃，第二层优先电路12₀～12₃的输出信号OR分别输入第三层优先电路13。输出信号OR是4个输入信号的逻辑和输出，当输入信号中的任一个成为一致信号“1”时，输出“1”。

接着，第二层优先电路12₀的输出信号被依次(按照从前位到后位的顺序)反馈到第一层优先电路11₀～11₃的各个启动输入端子EN上，同样，第二层优先电路12₁的输出信号被依次反馈到第一层优先电路11₄～11₇的各个启动输入端子EN上，第二层优先电路12₂的输出信号被依次反馈到第一层优先电路11₈～11₁₁的各个启动输入端子EN上，第二层优先电路12₃的输出信号被依次反馈到第一层优先电路11₁₂～11₁₅的各个启动输入端子EN上。第三层优先电路13的输出信号被依次反馈到第一层优先电路12₀～12₃的各个启动输入端子EN上。

第一层优先电路11₀～11₁₅、第二层优先电路12₀～12₃和第三层优先电路13分别由相同的电路构成。由于在最后位的层中设有16个四输入的第一层优先电路，因此，图6所示的优先编码器是输出64个输入信号的编码结果的电路。因此，编码结果以6位(A0～5)输出。

另一方面，地址编码器14由按照第一层优先电路11₀～11₁₅、第二层优先电路12₀～12₃和第三层优先电路13的各个输出信号被ON/OFF的多个MOSFET 15所构成，在每个优先电路中设置4个MOSFET 15。地址编码器14从第一层优先电路11₀～11₁₅的输出信号来决定地址的后2位(A0、A1)，从第二层优先电路12₀～12₃的输出信号来决定地址中间2位(A2、A3)，从第三层优先电路13的输出信号来决定地址前2位(A4、A5)。

在这样的构成中，地址编码器14由按照第一层优先电路11₀～11₁₅、第二层优先电路12₀～12₃和第三层优先电路13分别动作，以便于仅在与被输入最上侧的输入端子的一致信号“1”相对应的输出端子上输出“1”。

把第三层优先电路13的输出信号和第二层优先电路12₀～12₃的输出信号在处于各自支配下的后位的层的优先电路中反馈给启动输入端子EN，由此，在输入信号中没有一致信号(全部为“0”)的第一层优先电路11₀～11₁₅的输出信号和把其输出信号作为输入的第二层优先电路12₀～12₃的输出信号全被无效化，即使在存在多个一致信号的情况下，从优先度最高的一致信号的编码结果(地址)依次输出给A5～A0端子。

在近年来的CAM中，存在其存储容量增大而优先存储器的输入数增加的倾向。

在上述这样的现有优先编码器中通过把优先电路分层化来谋求高速化，但是，由于把处于前位的层的优先电路的输出信号反馈给处于后位的层的优先电路的启动输入端子EN，则在优先编码器的输入数变得非常多的近年来的大容量CAM中，存在需要花费输出编码结果之前的时间(延迟时间)的问题。

本发明的目的就是为了解决上述这样的现有技术存在的问题，而提供一种适合于大容量CAM的高速工作的优先编码器。

为了实现上述目的，本发明的优先编码器，从包含将要对地址进行编码的信号的多个输入信号中按照预先设定的优先度依次输出上述地址，其特征在于，包括：

多个第一编码电路，分别输出第一编码信号和除该预定数之外表示是否存在将要对上述地址进行编码的信号的第一启动信号，该第一编码信号把上述多个输入信号按预定数进行分割，把该预定数的输入信号分别作为输入信号，而作为与该预定数相对应的位数的编码结果；

多个多路复用器，用于在上述第一编码信号中仅输出优先度最高的将要对上述地址进行编码的信号的编码结果；

第二编码电路，输出把上述第一启动信号作为输入而作为与该输入数相对应的位数的编码结果的第二编码信号和除该输入之外表示是否存在将要对该地址进行编码的信号的第二启动信号。

此时，上述多路复用器，

把上述第一启动信号的供给方的第一编码信号作为第一输出信号、优先度低于该第一输出信号的第一编码信号作为第二输出信号分别作为输入；

在存在将要对上述地址进行编码的信号的情况下，从该第一启动信号输出上述第一输出信号，在不存在将要对上述地址进行编码的信号的情况下，输出上述第二输出信号。

并且，可以包括多个上述优先编码器，

在该优先编码器的输出上分层地设有至少一段扩展电路，该扩展电路具有：    

至少一个扩展用编码电路，输出把来自前段的启动信号作为输入并作为与该输入数相对应的位数的编码结果的第三编码信号和除该输入外表示是否存在将要对上述地址进行编码的信号的第三启动信号；

多个扩展用多路复用器，用于在前段的编码结果中仅输出优先度最高的将要对上述地址进行编码的信号的编码结果。

可以包括多个上述优先编码器，

在该优先编码器的输出上分层地设有至少一段扩展电路，用于从多个输入该优先编码器的全部输入信号中按照预先设定的优先度依次输出上述地址；

当使第一编码电路和第二编码电路的输入信号数为m，使上述扩展电路的段数为n，使k为0至n-1的整数时，在第n-k段的上述扩展电路中，具有：

m^k个扩展用编码电路，输出第三编码信号和除该输入外表示是否存在将要对上述地址进行编码的信号的第三启动信号，该第三编码信号是输入信号数为m，把来自前段的启动信号作为输入，与该输入数相对应的位数的编码结果；

至少(n+1)(m-1)个扩展用多路复用器，用于在前段的编码结果中仅输出优先度最高的将要对上述地址进行编码的信号的编码结果。

此时，上述第一编码电路、上述第二编码电路和上述扩展用编码电路从4个输入信号输出2位的编码结果，

上述多路复用器和扩展用多路复用器输出两个2位的编码结果中的任一方。

另一方面，本发明的优先编码方法，从包含将要对地址进行编码的信号的多个输入信号中按照预先设定的优先度依次输出上述地址，其特征在于，包括：

第一步骤，分别输出第一编码信号和除该预定数之外表示是否存在将要对上述地址进行编码的信号的第一启动信号，该第一编码信号把上述多个输入信号按预定数进行分割，把该预定数的输入信号分别作为输入信号，而作为与该预定数相对应的位数的编码结果；

第二步骤，在上述第一编码信号中仅输出优先度最高的将要对上述地址进行编码的信号的编码结果；

第三步骤，输出把上述第一启动信号作为输入而作为与该输入数相对应的位数的编码结果的第二编码信号和除该输入之外表示是否存在将要对该地址进行编码的信号的第二启动信号。

此时，上述第二步骤，

把上述第一启动信号的供给方的第一编码信号作为第一输出信号、优先度低于该第一输出信号的编码信号作为第二输出信号分别作为输入；

在存在将要对上述地址进行编码的信号的情况下，从该第一启动信号输出上述第一输出信号，在不存在将要对上述地址进行编码的信号的情况下，输出上述第二输出信号。

本发明的优先编码方法，对于由上述优先编码方法所输出的多个信号，分层地处理至少一段扩展步骤，该扩展步骤具有：

至少一个第一扩展步骤，输出把来自前段的启动信号作为输入并作为与该输入数相对应的位数的编码结果的第三编码信号和除该输入外表示是否存在将要对上述地址进行编码的信号的第三启动信号；

多个第二扩展步骤，用于在前段的编码结果中仅输出优先度最高的将要对上述地址进行编码的信号的编码结果。

本发明的优先编码方法，对于由上述优先编码方法所输出的多个信号，按照预先设定的优先度依次输出上述地址，分层地处理至少一段扩展步骤，

当使第一步骤和第二步骤的输入信号数为m，使上述扩展步骤的段数为n，使k为0至n-1的整数时，第n-k段的上述扩展步骤具有：

并行处理的m^k的第一扩展步骤，输出第三编码信号和除该输入外表示是否存在将要对上述地址进行编码的信号的第三启动信号，该第三编码信号是输入信号数为m，把来自前段的启动信号作为输入，与该输入数相对应的位数的编码结果；

并行处理的至少(n+1)(m-1)的第二扩展步骤，用于在前段的编码结果中仅输出优先度最高的将要对上述地址进行编码的信号的编码结果。

此时，在上述第一步骤、上述步骤和上述第一扩展步骤中，从4个输入信号输出2位的编码结果，

在上述第二步骤和上述第二扩展步骤中，输出两个2位的编码结果中的任一方。

上述这样构成的优先编码器分层地设置形成输出输入信号的编码结果的多个编码电路和用于仅输出优先度高的编码结果的多个多路复用器，由此，能够与输入信号数的对数值成比例地减少信号传输的段数。

本发明的这些和其他的目的、优点及特征将通过结合附图对本发明的实施例的描述而得到进一步说明。在这些附图中：

图1表示本发明的优先编码器的一个实施例构成的方框图；

图2表示本发明的优先编码器的构成的图，是表示能够对应于多输入的优先编码器的一个实施例的方框图；

图3表示在本发明的优先编码器中使用的编码电路的一个实施例的构成电路图；

图4表示在本发明的优先编码器中使用的多路复用器的一个实施例的构成电路图；

图5表示在本发明的优先编码器中使用的编码电路的另一个实施例的构成电路图；

图6表示在本发明的优先编码器中使用的多路复用器的另一个实施例的构成电路图；

图7表示现有的优先编码器的构成的方框图。

下面参照附图来对本发明进行说明。

图1是表示本发明的优先编码器的一个实施例构成的方框图。图1所示的的优先编码器表示从16个输入信号输出4位编码结果的电路的构成例子。

在图1中，优先编码器分层地设置最后位的层、中间位的层和最前位的层这3层。最后位的层分别由输出4个输入信号的编码结果(2位)和作为逻辑和输出的启动信号EN的4个第一层编码电路1₀～1₃所构成。中间位的层由按照从第一层编码电路1₀～1₃所输出的启动信号EN而输入到输入端子A0、A1或者输入端子B0、B1任一方的信号的3个第二层多路复用器2₀～2₂所构成。而且，最前位的层由输出与最后位的层相同的4个输入信号的编码结果(2位)和作为逻辑和输出的启动信号EN的1个第三层编码电路3所构成。第一层编码电路1₀～1₃和第三层编码电路3分别是相同电路。

第一层编码电路1₀～1₃和第三层编码电路3，在4个输入端子D、C、B、A中，对应于一致信号所输入的输入端子，向Y0、Y1输出2位的编码结果，在输入端子D、C、B、A任一个为“0”的情况下，输出“0”作为启动信号EN。在图1所示的优先编码器中，在与第一层编码电路1₀～1₃相对应的输入信号ML0～MLF中，优先度最高的输入信号是ML0。优先度的顺序并不一定是ML0是最高的，MLF也可以是最高的。

第二层编码电路2₀～2₂当在控制端子C上输入“1”时分别从输出端子Y0、Y1输出被输入到输入端子A0、A1上信号，当在控制端子C上输入“0”时，从输出端子Y0、Y1输出被输入到输入端子B0、B1上信号。其中，提供启动信号EN的第一层优先电路的输出信号被输入到输入端子A0、A1上，处于其后位的第一层优先电路的输出信号被输入到输入端子B0、B1上(存在通过第二层多路复用器的情况和不通过的情况)。

在这样的构成中，第一层编码电路1₀～1₃，当在输入端子D、C、B、A任一个上输入了一致信号“1”时，输出“1”作为启动信号EN，当输入端子D、C、B、A全都输入“0”时，输出“0”作为启动信号EN。

第二层编码电路2₀～2₂当在控制端子C上输入“1”时，从输出端子Y0、Y1输出该启动信号EN的供给方的第一层优先电路的输出。当在控制端子C上输入“0”时，从输出端子Y0、Y1原封不动地输出处于其后位的第二层多路复用器的输出信号或者第一层优先电路的输出信号。

因此，从处于最前位的第二层编码电路2₂输出从第一层编码电路1₀～1₃所输出的编码结果中的优先度最高的编码结果(地址的后2位)。

从第三层编码电路3输出第一层编码电路1₀～1₃的各启动信号EN的编码结果(地址的后2位)。

下面参照图2来对能够输出更多输入信号的编码结果的优先编码器的构成进行说明。

图2是表示本发明的优先编码器的构成的图，是表示能够适应与多输入的优先编码器的一个实施例的方框图。图2表示进行64个输入信号的编码的优先编码器的构成。

在图2中，当使输入信号的数量为64个时，准备4个图1所示的优先编码器。在每个图1所示的优先编码器中分别设置2个用于输出地址的前两位的扩展编码电路(未图示)和用于输出地址的其余位的扩展用多路复用器，由此来进行分层化。编码结果增加2位而以6位输出。

当具体说明此时的构成时，在每个图1所示的优先编码器中分别设置两个扩展用多路复用器4₁、4₂，连接第二层多路复用器2₂的输出端子和扩展用多路复用器的输入端子A0、A1，连接第三层编码电路3的输出端子和扩展用多路复用器4₂的输入端子A0、A1。扩展用多路复用器4₁的输入端子B0、B1与处于其后位侧的扩展用多路复用器4₁的输出端子Y0、Y1相连接。因此，在各个扩展用多路复用器4₁的输入端子B0、B1上分别输入来自前段(后位侧)的信号IA0、IA1，从输出端子Y0、Y1输出与下段(前位侧)相对应的信号OA0、OA1。

同样，在扩展用多路复用器4₂的输入端子B0、B1上分别输入来自前段(后位侧)的信号IA2、IA3，从输出端子Y0、Y1输出与下段(前位侧)相对应的信号OA2、OA3。

接着，把各优先编码器的第三层编码电路3的启动信号EN分别输入与第一编码电路同样构成的未图示的扩展编码电路中。

此时，从处于最前位的扩展用多路复用器4₁输出地址的最后2位，从处于最前位的扩展用多路复用器4₂输出地址的中间2位，从未图示的扩展编码电路输出地址的最前2位。

在构成能够对更多的输入信号进行编码的优先编码器的情况下，配合输入信号数而准备多个图1所示的优先编码器，相对应地分层地设置由至少一个扩展编码电路(未图示)和多个扩展用多路复用器组成的多个扩展电路。

此时，第n-k段的上述扩展电路具有m^k个扩展用编码电路和至少(n+1)(m-1)个扩展用多路复用器。其中，m为第一编码电路和第二编码电路的输入信号数，n为上述扩展电路的段数，k为0至n-1的整数。

因此，优先编码器可以仅由逻辑门构成。此时，当使逻辑门每一段的延迟时间为a时，优先编码器的总延迟时间Tpd’在最差的情况下为a×w(w：字数)。

另一方面，在由图1所示的编码电路和多路复用器进行了分层化的优先编码器的情况下，每一层的延迟时间增加为a的n倍(n：每一层的逻辑门的段数)。因此，由于传输的段数为从w到log4(w)，则总延迟时间Tpd最大为a×n×log4(w)。

即使在仅由逻辑门构成优先编码器的情况下，如果使用多个输入的逻辑门来构成优先编码器，把逻辑门的段数减到w以下。但是，由于逻辑门的输入数是有极限的，则特别是在对多个输入信号进行编码的情况下，不可能把逻辑门的段数从分层化的优先编码器减少。

因此，在存在字数增加倾向的近年来的大容量CAM中，如果使用本发明的优先编码器，就能大幅度降低其延迟时间。

本发明的优先编码器仅在从后位的层到前位的层的一个方向上传输信号，如现有例子那样，由于前位的层的输出信号不会向后位的层反馈，则编码结果以更高速输出。

下面参照图3～图6来说明作为图2所示的优先编码器的构成要素的第一层编码电路、第三层编码电路、第二层多路复用器和扩展用多路复用器的具体构成。由于第一层编码电路与第三层编码电路具有相同的构成，则下面总称为编码电路。由于第二层多路复用器和扩展用多路复用器具有相同的构成，则下面总称为多路复用器。

图3是表示在本发明的优先编码器中使用的编码电路的一个实施例的构成的电路图，图4是表示在本发明的优先编码器中使用的多路复用器的一个实施例的构成的电路图。图5是表示在本发明的优先编码器中使用的编码电路的另一个实施例的构成的电路图，图6是表示在本发明的优先编码器中使用的多路复用器的另一个实施例的构成的电路图。

图3所示的编码电路和图4所示的多路复用器分别是组合逻辑门而构成电路，是按照从表示各自的动作的真值表而得到的逻辑动作来组合反向和NAND门等的电路。

另一方面，图5所示的优先电路和图6所示的多路复用器分别是把有MOSFET组成的开关和逻辑门进行组合而构成的电路，与图3或图4所示的电路相比，能够减少逻辑门的数量。因此，能够进一步降低优先编码器的延迟时间。

由于本发明按上述那样构成，而具有以下的效果：

在输入信号数变多的情况下，能够大幅度降低编码所需要的延迟时间。

信号仅在从后位的层到前位的层的一个方向来进行传输，如现有例子那样，由于前位的层的输出信号不会向后位的层进行反馈，则编码结果以更高速被输出。