System and method for compressing data

• US 6,839,624 B1
• Filed: 09/09/2003
• Issued: 01/04/2005
• Est. Priority Date: 12/20/2001
• Status: Active Grant

• Current Assignee: Garmin Limited
• Original Assignee: Garmin Limited
• Inventors: Liu, Chunyen, Childs, Michael, Beesley, Darin J., Robinson, Stephen C.
• Primary Examiner(s): Zanelli, Michael J.
• Application Number:
  US10/657,972
• Time in Patent Office: 483 Days
• Field of Search: 701/200, 701/208, 707/100, 707/101, 707/104, 340/995.12, 342/357.09, 342/357.1, 342/357.13, 341/65, 341/106
• US Class Current: 701/200
• CPC Class Codes: G01C 21/20 Instruments for performing navigational calculations G01C21/24, G01C21/26 take precedence
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• CPC Class Codes: H03M 7/42 using table look-up for the coding or decoding process, e.g. using read-only memory H03M7/4006 takes precedence

Abstract

Systems, devices and methods are provided to compress data, and in particular to code and decode data. One aspect of the present subject matter is a data structure. The data structure includes a field representing a decoding structure to decode canonical Huffman encoded data, and a field representing a symbol table. The decoding structure includes a field representing an accelerator table to provide a 2^N-deep direct-index lookup to provide high-frequency symbols for high-frequency data and to provide bracketing indices for low-frequency data. The decoding structure also includes a field for a binary search table to provide a low-frequency symbol index using a binary search bounded by the bracketing indices provided by the accelerator table. The symbol table is adapted to provide a symbol associated with the low-frequency index.

Claims

1. A method for receiving a signal that includes canonical Huffman encoded data, the method comprising:

performing a 2^N-deep direct-index lookup using N bits from the canonical Huffman encoded data to extract high-frequency symbols and to provide bracketing indices for low-frequency symbols; and

performing a binary search bounded by the bracketing indices to extract the low-frequency symbols.

2. The method of claim 1, wherein, for each low frequency symbol, performing a binary search bounded by the bracketing indices includes:

providing a low-frequency symbol index; and

extracting a low-frequency symbol from a symbol table associated with the low-frequency symbol index.

3. The method of claim 1, wherein, for each low frequency symbol, performing a binary search bounded by the bracketing indices includes:

retrieving L bits from the canonical Huffman encoded data to provide an L-bit compare value, wherein the L bits includes the N bits;

identifying a base Huffman code and a base symbol index for the L-bit compare value, a comparison index from the L-bit compare value and the base Huffman code, and a symbol index from the comparison index and the base symbol index; and

extracting a symbol associated with the symbol index.

4. The method of claim 1, wherein the canonical Huffman encoded data includes text data.

5. The method of claim 1, wherein the canonical Huffman encoded data includes image data.

6. The method of claim 1, wherein the canonical Huffman encoded data includes audio data.

7. The method of claim 1, wherein the canonical Huffman encoded data includes a combination of at least two of text data, image data and audio data.

8. The method of claim 1, wherein the canonical Huffman encoded data includes text data, image data and audio data.

9. A computer-readable medium having computer-executable instructions for performing a method for decoding canonical Huffman encoded data, the method comprising:

performing a 2^N-deep direct-index lookup using N bits from the encoded data;

extracting a high frequency symbol from the encoded data based on the 2^N-deep direct-index lookup;

identifying bracketing indices for a low-frequency symbol based on the 2^N-deep direct-index lookup; and

performing a binary search bounded by the bracketing indices to extract the low-frequency symbol.

10. The computer-readable medium of claim 9, further having a data structure for use to decode canonical Huffman encoded data, the data structure comprising:

a field representing an accelerator table for use to perform the 2^N-deep direct-index lookup of the canonical Huffman encoded data; and

a field representing a binary search table for use to perform the binary search of the canonical Huffman encoded data, the binary search being bounded by the bracketing indices.

11. The computer-readable medium of claim 10, further comprising a field representing a symbol table that includes symbols, wherein the field representing a binary search table includes symbol indices that are associated with the symbols in the symbol table.

12. The computer-readable medium of claim 10, wherein:

the accelerator table has an accelerator table size;

an increased value of N corresponds to an increased accelerator table size, provides more high-frequency symbols and decodes the canonical Huffman encoded data more quickly; and

a decreased value of N corresponds to a decreased accelerator table size, provides fewer high-frequency symbols and decodes the canonical Huffman encoded data less quickly.

13. The computer-readable medium of claim 10claim 9, wherein the data decoded by the data structure includes one or more data types selected from the group consisting of canonical Huffman encoded text data, canonical Huffman encoded image data and canonical Huffman encoded audio data.

14. A device, comprising:

means to perform a 2^N-deep direct-index lookup using N bits from canonical Huffman encoded data to extract high-frequency symbols from the canonical Huffman encoded data and to provide bracketing indices for low-frequency symbols from the canonical Huffman encoded data; and

means to perform a binary search bounded by the bracketing indices to extract the low-frequency symbols from the canonical Huffman encoded data.

15. The device of claim 14, wherein the device includes a navigation device, and the canonical Huffman encoded data includes navigation data.

16. A device, comprising:

a processor; and

a memory connected to the processor, the memory including a field representing an accelerator table for use to perform a 2^N-deep direct-index lookup of canonical Huffman encoded data to extract high-frequency symbols and to identify bracketing indices for low-frequency symbols, and a field representing a binary search table for use to perform a binary search of the data bounded by the bracketing indices.

17. The device of claim 16, wherein:

the memory has a finite amount of available memory space for use to decode the canonical Huffman encoded data;

the accelerator table has an accelerator table size that uses a portion of the finite amount of available memory;

an increased value of N corresponds to an increased accelerator table size, provides more high-frequency symbols and decodes the canonical Huffman encoded data more quickly; and

a decreased value of N corresponds to a decreased accelerator table size, provides fewer high-frequency symbols and decodes the canonical Huffman encoded data less quickly.

18. The device of claim 16, wherein the device includes a portable electronic navigational aid device.

19. The device of claim 16, wherein the device includes a personal digital assistant (PDA).

20. The device of claim 16, wherein the device includes a wireless communication device.

21. The device of claim 16, wherein the canonical Huffman encoded data includes navigation data, the device further comprising means to communicate with and retrieve the navigation data from a server.

22. A device, comprising:

a processor;

a memory connected to the processor, the memory including a field representing an accelerator table for use to perform a 2^N-deep direct-index lookup of canonical Huffman encoded data to extract high-frequency symbols and to identify bracketing indices for low-frequency symbols, and a field representing a binary search table for use to perform a binary search of the data bounded by the bracketing indices;

a speaker connected to the processor; and

a cellular antenna and a cellular transceiver operably connected to the cellular antenna and to the processor, wherein the device is adapted to receive the canonical Huffman encoded data through the cellular antenna and the cellular transceiver using cellular communication technology.

23. The device of claim 22, wherein:

the memory has a finite amount of available memory space for use to decode canonical Huffman encoded data;

the accelerator table has an accelerator table size that uses a portion of the finite amount of available memory;

an increased value of N corresponds to an increased accelerator table size, provides more high-frequency symbols and decodes the canonical Huffman encoded data more quickly; and

a decreased value of N corresponds to a decreased accelerator table size, provides fewer high-frequency symbols and decodes the canonical Huffman encoded data less quickly.

24. The device of claim 22, wherein the canonical Huffman encoded data includes audio data.

25. The device of claim 22, further comprising a display screen connected to the processor to display a decoded representation of the canonical Huffman encoded data.

26. The device of claim 25, wherein the canonical Huffman encoded data includes at least one of text data and image data.

27. The device of claim 22, wherein the canonical Huffman encoded data includes any combination of at least one of audio data, text data and image data.

28. The device of claim 22, wherein the canonical Huffman encoded data includes navigation data.

29. The device of claim 22, further comprising a Global Positioning System (GPS) antenna and a GPS receiver operably connected to the GPS antenna and the processor, wherein the device is adapted to receive GPS satellite signals through the GPS antenna and GPS receiver and calculate a position of the device, wherein the canonical Huffman encoded data includes navigation data.

30. The device of claim 22, wherein the device is adapted to receive an audio signal through the cellular antenna using cellular communication technology, and to provide a signal representative of the audio signal to the speaker.

31. A personal digital assistant (PDA), comprising:

a processor;

a memory connected to the processor, the memory including a field representing an accelerator table for use to perform a 2^N-deep direct-index lookup of canonical Huffman encoded data to extract high-frequency symbols and to identify bracketing indices for low-frequency symbols, and a field representing a binary search table for use to perform a binary search of the data bounded by the bracketing indices; and

a display screen connected to the processor to display a decoded representation of the canonical Huffman encoded data.

32. The PDA of claim 31, wherein:

the memory has a finite amount of available memory space for use to decode canonical Huffman encoded data;

the accelerator table has an accelerator table size that uses a portion of the finite amount of available memory;

an increased value of N corresponds to an increased accelerator table size, provides more high-frequency symbols and decodes the canonical Huffman encoded data more quickly; and

a decreased value of N corresponds to a decreased accelerator table size, provides fewer high-frequency symbols and decodes the canonical Huffman encoded data less quickly.

33. The PDA of claim 31, further comprising a cartridge bay connected to the processor, the cartridge bay to receive a map data cartridge that includes canonical Huffman encoded navigation data.

34. The PDA of claim 31, further comprising a cellular antenna and a cellular transceiver operably connected to the cellular antenna and to the processor, wherein the PDA is adapted to receive the canonical Huffman encoded data through the cellular antenna and the cellular transceiver using cellular communication technology.

35. The PDA of claim 34, wherein the canonical Huffman encoded data includes navigation data.

36. The PDA of claim 31, further comprising a Global Positioning System (GPS) antenna and a GPS receiver operably connected to the GPS antenna and the processor, wherein the PDA is adapted to receive GPS satellite signals through the GPS antenna and GPS receiver and calculate a position of the GPS receiver, and wherein the canonical Huffman encoded data includes navigation data.