the two end states s 3 or s 5 is reached for state machines that have too many states implementation issues e g memory width timing can make it impossible to store all transition rule entries in one memory location or to test all entries in parallel in this case the preferred embodiment uses the bart compression scheme to distribute the transition rule entries over multiple memory locations the bart compression scheme has been disclosed in a conference paper by jan van lunteren published in the proceedings of ieee globecom volume 3 pages 1615 1619 november 2001 under the title u2018 searching very large routing tables in wide embedded memory u2019 the bart compression scheme is based on a special hash function for exact prefix and ternary match searches the hash index which is called compressed index comprises a selected subset of the input bits in this case the current state and input character these bits are chosen such that the number of collisions for each compressed index value is bounded by a value n in other words for any given value of the compressed index at most n entries can possibly match the input these entries are then stored at the location within the hash table which is called compressed state transition rule table in the preferred embodiment corresponding to that compressed index value this concept will now be explained by.