Delivery and acquisition of data segments with optimized inter-arrival time

• US 6,173,330 B1
• Filed: 09/17/1996
• Issued: 01/09/2001
• Est. Priority Date: 09/17/1996
• Status: Expired due to Term

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: General Instrument Corporation (CommScope Holding Company, Inc.), Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Guo, Zicheng, Eyer, Mark K.
• Primary Examiner(s): Dinh, Dung C.
• Application Number:
  US08/718,636
• Time in Patent Office: 1,575 Days
• Field of Search: 709/230, 709/231, 709/232, 709/234, 709/236, 341/61, 341/81, 348/7, 348/17, 348/473, 348/461
• US Class Current: 709/232
• CPC Class Codes: H04N 21/2353 specifically adapted to content descriptors, e.g. coding, compressing or processing of metadata
• CPC Class Codes: H04N 21/2362 Generation or processing of Service Information [SI]
• CPC Class Codes: H04N 21/2665 Gathering content from different sources, e.g. Internet and satellite
• CPC Class Codes: H04N 21/426 Internal components of the client ; Characteristics thereof H04N5/44 takes precedence
• CPC Class Codes: H04N 21/4345 Extraction or processing of SI, e.g. extracting service information from an MPEG stream
• CPC Class Codes: H04N 21/4351 involving reassembling additional data, e.g. rebuilding an executable program from recovered modules
• CPC Class Codes: H04N 7/17318 Direct or substantially direct transmission and handling of requests
• CPC Class Codes: H04N 7/17354 in an intermediate station common to a plurality of user terminals

Abstract

Data pages of an interactive program guide (IPG) for television are transmitted according to a shuffle function which allows different television receivers to retrieve particular segments of the data pages based on the day and time of program listings which a viewer wishes to see. A page of data, which corresponds to a full-screen image, is divided into segments and retrieved by the receivers over time. The segments are shuffled to provide an optimal separation in the data stream. The optimal separation corresponds to the receiver'"'"'s input buffer size and processing speed. The pages may be arranged sequentially, or with the even-numbered pages separated from the odd-numbered pages. The pages are partitioned into a number of subsets, and, within the pages of each subset, the segments are shuffled according to a perfect shuffle function such that respective adjacent segment pairs are arranged in an order which maximizes a minimum of their inter-segment distance after shuffling. The minimum inter-segment distance of all the subsets is used to determine a characteristic inter-segment arrival time, which must be large enough to correspond to the receiver'"'"'s processing capability. The required input buffer size and processing speed of the receivers is reduced, yet data page acquisition speed is increased for all viewers.

Claims

1. A method for communicating a data stream which includes a plurality of data segments to at least one receiver, comprising the step of:

shuffling said segments from a first segment order, in which adjacent ones of the segments are ordered in accordance with a graphical display order, to provide said segments in said data stream in a second segment order that is arranged to accommodate a maximum speed at which said at least one receiver can receive data.

2. The method of claim 1, wherein:

in said second segment order, respective pairs of segments which were adjacent in said first segment order are separated by corresponding inter-segment distances; and

said shuffling step maximizes a minimum of said inter-segment distances such that a data rate corresponding to the minimum inter-segment distance is within said maximum speed.

3. The method of claim 1, wherein said data segments are arranged as a plurality of pages in a first page order which corresponds to said first segment order, comprising the further step of:

providing said pages in said data stream in a second page order such that alternate pages in said first page order are grouped in said second page order.

4. The method of claim 1, wherein said segments are grouped in a plurality of blocks including at least first and second types of blocks, comprising the further step of:

arranging said first and second types of blocks over a first transmission cycle of said data stream and subsequent transmission cycles which follow thereafter such that said first and second types of blocks are provided at different respective frequencies in said data stream.

5. The method of claim 1, wherein said data segments are arranged as a plurality of pages in a first page order which corresponds to said first segment order, comprising the further step of:

partitioning said plurality of pages into at least first and second subsets thereof;

wherein;

said shuffling of segments occurs separately within each of said subsets.

6. The method of claim 5, wherein in said second segment order, respective pairs of segments which were adjacent in said first segment order are separated by corresponding inter-segment distances;

and

said shuffling step maximizes the minimum of said inter-segment distances for each of said subsets.

7. The method of claim 6, comprising the further steps of:

determining a characteristic inter-segment arrival time which corresponds to the minimum of said inter-segment distances of said subsets; and

determining whether said characteristic inter-segment arrival time is within said maximum speed of said at least one receiver.

8. The method of claim 1, wherein:

the maximum speed of the at least one receiver is a function of at least one of an input buffer size and a processing speed.

9. The method of claim 1, wherein:

the data segments comprise television program guide data.

10. The method of claim 1, wherein:

said data segments are arranged as a plurality of pages; and

each page comprises an associated graphical image for a television program guide.

11. The method of claim 3, wherein:

the plurality of pages are arranged sequentially in said first page order, and odd-numbered pages are grouped with one another, and even-numbered pages are grouped with one another, in said second page order.

12. The method of claim 3, wherein:

said second page order enables the plurality of pages to be carried in the data stream according to a common packet identifier.

13. The method of claim 3, wherein:

in the second page order, data segments from neighboring pages in said first page order are carried in non-adjacent pages.

14. The method of claim 4, wherein:

the plurality of blocks comprise at least one of foundation blocks, schedule listing blocks, and description blocks for a television program guide.

15. The method of claim 14, wherein:

the frequency of the description blocks in the data stream is less than the frequency of the schedule listing blocks.

16. The method of claim 14, wherein:

the frequency of the foundation blocks in the data stream is greater than the frequency of the schedule listing blocks.

40. The receiver of claim 15, wherein:

the data segments comprise television program guide data.

17. An apparatus for communicating a data stream which includes a plurality of data segments to at least one receiver, comprising:

means for shuffling said segments from a first segment order, in which adjacent ones of the segments are ordered in accordance with a graphical display order, to provide said segments in said data stream in a second segment order that is arranged to accommodate a maximum speed at which said at least one receiver can receive data.

18. The apparatus of claim 17, wherein:

in said second segment order, respective pairs of segments which were adjacent in said first segment order are separated by corresponding inter-segment distances; and

said shuffling means maximizes a minimum of said inter-segment distances such that a data rate corresponding to the minimum inter-segment distance is within said maximum speed.

19. The apparatus of claim 17, wherein said data segments are arranged as a plurality of pages in a first page order which corresponds to said first segment order, further comprising:

means for providing said pages in said data stream in a second page order such that alternate pages in said first page order are grouped in said second page order.

20. The apparatus of claim 17, wherein said segments are grouped in a plurality of blocks including at least first and second types of blocks, further comprising:

means for arranging said first and second types of blocks over a first transmission cycle of said data stream and subsequent transmission cycles which follow thereafter such that said first and second types of blocks are provided at different respective frequencies in said data stream.

21. The apparatus of claim 17, wherein said data segments are arranged as a plurality of pages in a first page order which corresponds to said first segment order, further comprising:

means for partitioning said plurality of pages into at least first and second subsets thereof;

wherein;

said shuffling means shuffles said segments separately within each of said subsets.

22. The apparatus of claim 21, wherein in said second segment order, respective pairs of segments which were adjacent in said first segment order are separated by corresponding inter-segment distances;

and

said shuffling step maximizes the minimum of said inter-segment distances for each of said subsets.

23. The apparatus of claim 22, further comprising:

means for determining a characteristic inter-segment arrival time which corresponds to the minimum of said inter-segment distances of said subsets; and

means for determining whether said characteristic inter-segment arrival time is within said maximum speed of said at least one receiver.

24. The apparatus of claim 19, wherein:

the plurality of pages are arranged sequentially in said first page order, and odd-numbered pages are grouped with one another, and even-numbered pages are grouped with one another, in said second page order.

25. The apparatus of claim 19, wherein:

said second page order enables the plurality of pages to be carried in the data stream according to a common packet identifier.

26. The apparatus of claim 19, wherein:

in the second page order, data segments from neighboring pages in said first page order are carried in non-adjacent pages.

27. The apparatus of claim 20, wherein:

the plurality of blocks comprise at least one of foundation blocks, schedule listing blocks, and description blocks for a television program guide.

28. The apparatus of claim 27, wherein:

the frequency of the description blocks in the data stream is less than the frequency of the schedule listing blocks.

29. The apparatus of claim 27, wherein:

the frequency of the foundation blocks in the data stream is greater than the frequency of the schedule listing blocks.

30. The apparatus of claim 17, wherein:

said data segments are arranged as a plurality of pages; and

each page comprises an associated graphical image for a television program guide.

31. The apparatus of claim 17, wherein:

the maximum speed of the at least one receiver is a function of at least one of an input buffer size and a processing speed.

32. The apparatus of claim 17, wherein:

the data segments comprise television program guide data.

33. A receiver for processing a data stream which includes a plurality of data segments, said receiver having a maximum speed at which it can receive and process data, comprising:

means for retrieving particular ones of said segments;

wherein;

said segments are provided in a shuffled order in accordance with said maximum speed; and

said shuffled order is obtained by shuffling the segments from a first segment order in which adjacent ones of the segments are ordered in accordance with a graphical display order.

34. The receiver of claim 33, wherein:

when the data segments are shuffled from the first segment order, respective pairs of segments which were adjacent in said first order are separated by corresponding inter-segment distances in said shuffled order; and

a minimum of said inter-segment distances is maximized such that a data rate corresponding to the minimum inter-segment distance is within said maximum speed.

35. The receiver of claim 33, wherein:

said data segments are arranged as a plurality of pages; and

said pages are shuffled from a first page order to a second page order which corresponds with said shuffled segment order such that alternate pages in said first page order are grouped in said second page order.

36. The receiver of claim 33, wherein:

said segments are grouped in a plurality of blocks including at least first and second types of blocks; and

said first and second types of blocks are arranged in a first transmission cycle of said data stream and subsequent transmission cycles which follow thereafter such that said first and second types of blocks are provided at different respective frequencies in said data stream.

37. The receiver of claim 33, further comprising:

an input buffer having a characteristic capacity for receiving said data stream; and

a processor having a characteristic processing speed for processing data received via said input buffer;

wherein;

said characteristic capacity and said characteristic processing speed are indicative of said maximum speed.

38. The receiver of claim 33, wherein:

said segments are grouped in a plurality of pages;

said pages are partitioned into at least first and second subsets thereof; and

said segments are shuffled separately within each of said subsets.

39. The receiver of claim 38, wherein:

within each of said subsets, said data segments are shuffled from a first segment order to achieve said shuffled order such that respective pairs of segments which were adjacent in said first order are separated by corresponding inter-segment distances in said shuffled order; and

the minimum of said inter-segment distances for said subsets is maximized.

41. The receiver of claim 33, wherein:

said data segments are arranged as a plurality of pages; and

each page comprises an associated graphical image for a television program guide.

42. The receiver of claim 35, wherein:

the plurality of pages are arranged sequentially in said first page order, and odd-numbered pages are grouped with one another, and even-numbered pages are grouped with one another, in said second page order.

43. The receiver of claim 35, wherein:

said second page order enables the plurality of pages to be retrieved from the data stream according to a common packet identifier.

44. The receiver of claim 35, wherein:

in the second page order, data segments from neighboring pages in said first page order are carried in non-adjacent pages.

45. The receiver of claim 36, wherein:

the plurality of blocks comprise at least one of foundation blocks, schedule listing blocks, and description blocks for a television program guide.

46. The receiver of claim 45, wherein:

the frequency of the description blocks in the data stream is less than the frequency of the schedule listing blocks.

47. The receiver of claim 45, wherein:

the frequency of the foundation blocks in the data stream is greater than the frequency of the schedule listing blocks.