Compression of an electronic programming guide

• US 5,548,338 A
• Filed: 06/07/1995
• Issued: 08/20/1996
• Est. Priority Date: 06/07/1995
• Status: Expired due to Term

• Current Assignee: UV Corporation (Adeia Inc.), TCI-TVGOS INC
• Original Assignee: News American Publishing Incorporated, Telecommunications Of Colorado, Inc.
• Inventors: Ellis, Michael D., Lazarus, David B.
• Primary Examiner(s): Kostak, Victor R.
• Application Number:
  US08/476,208
• Time in Patent Office: 440 Days
• Field of Search: 348/906, 348/12, 348/13, 348/460, 348/465, 348/467, 348/468, 348/473, 348/384, 375/253
• US Class Current: 725/54
• 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
• CPC Class Codes: H04N 21/2353 specifically adapted to content descriptors, e.g. coding, compressing or processing of metadata
• CPC Class Codes: H04N 21/26283 for associating distribution time parameters to content, e.g. to generate electronic program guide data
• CPC Class Codes: H04N 21/84 Generation or processing of descriptive data, e.g. content descriptors systems specially adapted for using meta-information in broadcast systems H04H60/73
• CPC Class Codes: H04N 5/445 for displaying additional information H04N5/50 takes precedence
• CPC Class Codes: H04N 7/025 Systems for the transmission of digital non-picture data, e.g. of text during the active part of a television frame transmission of digital non-picture data during the vertical blanking interval only H04N7/088
• CPC Class Codes: H04N 7/08 Systems for the simultaneous or sequential transmission of more than one television signal, e.g. additional information signals, the signals occupying wholly or partially the same frequency band , e.g. by time division H04N7/007 takes precedence

Abstract

Television programming information comprising an electronic programming guide is compressed by more than fifty percent, and decompressed in environments with only moderate processing power and storage space. The coding scheme of the present invention is based on Huffman coding of characters comprising the electronic programming guide and replacement character strings occurring in the data that have high savings values. A look-up table and binary tree are constructed from the Huffman codes for use in compressing and decompressing the electronic programming guide, and a set-top box for use in the decompression operation is provided.

Claims

1. A method for compressing an electronic programming guide, comprising:

assembling data representative of said electronic programming guide and comprising a plurality of characters;

determining a number of bits required to represent each of said characters in Huffman code;

selecting a plurality of candidate character strings from said data, said candidate character strings occurring more than a threshold number of times in said data and comprising at least two said characters;

calculating a savings value for each of said candidate character strings using at least said number of bits required to represent in Huffman code each of said characters comprising said candidate character string;

selecting at least one replacement character string from said candidate character strings based on said savings values;

preparing a Huffman table comprising Huffman codes for each of said plurality of characters and each of said at least one replacement character strings; and

compressing said electronic programming guide using said Huffman table.

2. The method of claim 1, wherein said threshold number for each of said candidate character strings equals a median frequency of said plurality of characters, divided by the number of characters in said candidate character string.

3. The method of claim 1, wherein at least 10 but no more than 50 replacement character strings are selected.

4. The method of claim 1, wherein each of said savings values is equal to the number of times said candidate character string occurs in said data multiplied by the difference between said number of bits required to represent in Huffman code each of said characters comprising said candidate character string and an estimated number of bits comprising a Huffman code for said candidate character string.

5. The method of claim 1, wherein said data comprises said electronic programming guide.

6. A set-top box for receiving and decompressing a signal comprising an electronic programming guide in compressed form, said electronic programming guide comprising a plurality of characters, said set-top box comprising:

means for receiving said signal and providing data comprising a digital representation of said electronic programming guide in compressed form;

a first storage space for storing a Huffman tree, said Huffman tree including at least one terminal branch representing a character string, said character string comprising at least two characters;

a second storage space for storing application software for use with said Huffman tree to perform a decompression operation;

a third storage space for storing said data; and

a microcontroller connected to said receiver means and to said first, second, and third storage spaces for causing said application software to perform said decompression operation on said data to obtain said electronic programming guide in decompressed form.

7. The set-top box of claim 6, wherein said receiver means comprises a receiver, a demodulator, and a buffer.

8. The set-top box of claim 6, wherein said first, second, and third storage spaces and said microcontroller comprise an integrated circuit chip.

9. The set-top box of claim 6, wherein said first and second storage spaces comprise a non-volatile memory and said third storage space comprises a volatile memory.

10. The set-top box of claim 9, wherein said first storage space is a ROM, said second storage space is an EEPROM, and said third storage space is a RAM.

11. The set-top box of claim 9, wherein said first and second storage spaces comprise a battery backed-up static RAM.

12. The set-top box of claim 9, wherein said first and second storage spaces comprise a flash memory.

13. The set-top box of claim 6, wherein said data is provided serially and said microcontroller further comprises an input pin on which to receive said serial data.

14. The set-top box of claim 6, wherein said data is provided in parallel and said microcontroller further comprises a plurality of input pins on which to receive said parallel data.

15. The set-top box of claim 6 further comprising an analog tuner.

16. The set top box of claim 6 further comprising a digital demultiplexer.