Trie-type memory device with a compression mechanism

Details Trie-type memory device with a compression mechanism Trie-type memory device with a compression mechanism

2006-04-27

2008-10-28

Kerveros, James C (Department: 2117)

Error detection/correction and fault detection/recovery

Pulse or data error handling

Memory testing

C714S763000

Reexamination Certificate

active

07444562

ABSTRACT:
The invention relates to a tri-type memory device comprising a compression mechanism. According to the invention, the memory stores binary patterns that are associated with respective references. Data chains are analyzed by successive section of K bits (K>1) in order to extract one of the references when there is a match with a stored binary pattern associated with said reference. The memory is organized into several successive memory cell states, the analysis of the (i+1)-th section of a chain providing access to a cell of stage i≧0. Each non-empty cell of a stage i≧0 contains one of the following: a register-type analysis tracking pointer designating a register of 2Kcells of stage i+1; a linear-type analysis tracking pointer designating a zone of one or two cells forming a reduced register of stage i+1; or a reference associated with a stored binary pattern.

REFERENCES:
patent: 5781772 (1998-07-01), Wilkinson et al.
patent: 5909440 (1999-06-01), Ferguson et al.
patent: 6014659 (2000-01-01), Wilkinson et al.
patent: 6425099 (2002-07-01), Lattmann et al.
patent: 6505206 (2003-01-01), Tikkanen et al.
patent: 6691171 (2004-02-01), Liao
patent: 6704313 (2004-03-01), Duret et al.
patent: 0 989 502 (2000-03-01), None
patent: 0 458 698 (2000-08-01), None
patent: 1 030 493 (2000-08-01), None
patent: WO 00/75804 (2000-12-01), None
Masui, T., “Keyword Dictionary Compression Using Efficient Trie Implementation”, IEEE Comput. Soc., (1991), p. 438.
Pei, Tong-Bi, “Putting Routing Tables in Silicon”, IEEE Network, vol. 6, No. 1, (1992), pp. 42-50.
Fredkin, E., “Trie Memory”, Communications of The ACM, vol. 3, No. 9, (1960), pp. 490-499.
Aoe, Jun-Ichi, “An Efficient Implementation of Static String Pattern Matching Machines”, IEEE Transactions On Software Engineering, vol. 15, No. 9 (1989), pp. 1010-1016.
Livonen, J.P., “An Experimental Study of Compression Methods For Functional Tries”, Conference WAAPL (1999).

Affiliated with

Also associated with

Rating

Trie-type memory device with a compression mechanism does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Trie-type memory device with a compression mechanism, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Trie-type memory device with a compression mechanism will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3990063