Data compression having improved compression speed
AssigneeBTG International Limited
InventorsSimon Richard Jones, Jose Luis Nunez Yanez
Life of this patent
Estimating the term…
Abstract
A lossless data compression system comprising a dictionary (30) based on content addressable memory and a coder (40) having between them a critical path including a feedback loop forming a dictionary adaption path, in which circuit means (42) is connected in the feedback loop so that the dictionary can be updated using data from a previous comparison cycle at the same time as the coder codes a current comparison cycle. The circuit means (42) has a current adaptation vector (58, 62, 66) and a next adaption vector (60, 64, 68); at leach search step the current adaptation vector updates data in the dictionary and also rearranges the next adaptation vector. Compression speed is increased.
Claims11
A lossless data compression system comprising a dictionary 30 based on content addressable memory and a coder 40 having between them a critical path including a feedback loop forming a dictionary adaptation path, characterised by circuit means 42 connected in the feedback loop whereby the dictionary can be updated using data from a previous comparison cycle at the same time as the coder codes a current comparison cycle.
A system according to any preceding claim in which the dictionary 30 is arranged so that at each step a previous search tuple is loaded into the top/front address 50 of the dictionary 30.
A system according to any preceding claim in which the dictionary 30 is arranged to hold data elements which are all of precisely equal length.
A system according to any preceding claim in which the dictionary 30 is arranged to indicate the address of a full match or a partial match to a search tuple.
A lossless data decompression system comprising a content addressable memory dictionary 30 and a decoder 126, having between them a feedback loop forming a dictionary adaptation path characterised by circuit means 42 connected in the feedback loop, whereby the dictionary can be updated using data from a previous comparison cycle at the same time as the coder codes a current comparison cycle.
A lossless method of compressing data comprising the steps of;
- comparing a search tuple of fixed length with a plurality of tuples of said fixed length stored in a dictionary;
- indicating the location in the dictionary of a full or partial match or matches;
- selecting a best match of any plurality of matches;
- and
- coding the match location and the match type;
- characterised by the further steps of
- providing the dictionary with a current adaptation vector and a next adaptation vector;
- and after comparison of each search tuple
- (a) updating the contents of the dictionary in accordance with the current adaptation vector, and
- (b) updating the next adaptation vector in according with the current adaptation vector.
Dependencies are inferred from the claim text.