Patent ID: 6615210
Filing Date: 2003-09-02
Classification: G06F,G11C,Y10S

Abstract:
A bit-stream ternary match scheme for searching an information table according to a match result of a rule table comprising the steps of:(a) determining the space of said rule table according to a maximum allowable bit-length (W) of a rule, and the number of maximum allowable rules (L); (b) dividing said maximum allowable bit-length (W) into N+1 sub-bit-streams, where N is a nonnegative integer; (c) determining N+1 memory table and N+1 selectors according to the number of sub-bit-streams of said step (b); (d) encoding a plurality of rules according to a pre-computation procedure and generating a plurality of encoded entries; (e) sequentially storing said plurality of encoded entries in said memory tables; (f-1) dividing to-be-matched information of bit-length (W) into N+1 to-be-matched sub-bit-streams, where N is a nonnegative integer; (f-2) inputting each of said to-be-matched sub-bit-streams to each of said N+1 selectors respectively, so that each of said N+1 selectors directly selects an output from said encoded entries in each of said memory tables according to each to-be-matched sub-bit-stream, and then sending the output of each of said N+1 selectors into a product module to compute an unencoded match result; (g) forwarding said unencoded match result of said product module to a priority encoder to perform priority encoding for generating an encoded match result and a match flag; and (h) determining if there is a hit for said match information according to said match flag; wherein when said match flag indicating a negative result, there is no match between said match information and said rule table; and when said match flag indicating a positive result, said encoded match result acts as an index for searching said information table.