MEMORY SYSTEM FOR SEARCHING A LONGEST MATCH

摘要

A method and circuit to be applied in content addressable memories for finding a word with the longest match to the searched data. A word (Wi) of data is stored in each memory cell, the word of data is composed of a group of sub words (Bij) in a predefined order and each sub word is composed of one or more bits of memory. All sub words having the same position within the sub word sequence of their respective words are associated with the same tranversal line (Tj), and the method comprises the steps of a) setting a match signal (Mij) for a first subword (Bij) that matches the searched data b) setting a still match signal (SMij) for a subword in the event that all the previous still match signals, for all subwords of the same word in a pre - defined order have been set, the said still match signal being the AND logic combination of the associated sub-word match signal and all the preceding, in the said predefined order, still match signals c) setting the transversal line (Tj) to logical (1) if a still match is set for any of the subwords to which the said transversal line is associated d) setting a longest match signal (LMij) at the last consecutive matching subword of a word if the conditions are satisfied that: i) - the still match signal of that sub-word is set, and ii)- the transversal line at the next sub-word position in the word is not set. e) Setting a word match signal (WMi) if any of the longest match signals for any subword of the said word is set.