WO 94129811
`
`2154608
`
`PCTIUS94/06361
`
`-5-
`
`respect to those figures is for explanatory purposes only and
`is not intended in any way to limit the scope of the
`
`invention.
`
`For example, while a cable television system is
`
`shown and described,
`
`the present
`
`invention may also be used
`
`in a satellite, over-the—air broadcast, subscription
`
`television system or other television system known in the
`Also,
`
`art.
`
`while the present invention is described for use
`those
`
`in the provision of sports and weather text channels,
`
`10
`
`15
`
`20
`
`25
`
`30
`
`skilled in the art will appreciate that these text channels
`
`are only examples of the limitless types of text channels
`
`which may be provided to a viewer in accordance with the
`
`invention. Accordingly, any questions regarding the scope of
`
`the invention should be resolved by referring to the appended
`claims.
`
`Figure 1 illustrates an EPG and text information
`service in accordance with the invention.
`As shown,
`the
`
`local cable television company's billing vendor 10
`
`communicates via a billing link to an RS-232 port of a system
`
`manager 12 located at the cable head end. Billing vendor 10
`
`includes a subscriber database and generates a monthly bill
`
`,for the subscribers in the system based on the level of
`
`service and any pay-per—view purchases. Billing vendor 10
`
`may comprise a personal computer or other data processing
`
`device known in the art. Billing vendor 10 informs system
`
`manager 12 as to which cable television subscribers are
`authorized to receive the available cable television
`
`channels.
`
`System manager 12 is also a personal computer or
`
`other processing device which receives viewer authorization
`
`transactions from billing vendor 10 and generates
`
`transactions for delivery to the distribution apparatus or
`
`the subscribers.
`
`Such transactions include text channel
`
`definition transactions which instruct the subscriber's tuner
`
`which group of channels it is entitled to receive, which
`
`frequency to tune for a particular text data channel, whether
`to mute the audio for that text channel,
`the pagination delay
`
`35
`
`between pages, and the like.
`
`Page 001137
`
`

`
`WO 94129811
`
`2164608
`
`PCT/US94/06361
`
`-7-
`
`System manager 12 also communicates via a head end
`
`link to an RS—232 port of a head end controller (HEC) 14
`
`which controls the transmission of television programming to
`the subscribers. As will be described in more detail with
`
`respect to Figure 2, HEC 14 communicates via a control link
`
`to an RS-232 port of an information services processor (or
`
`data controller) 16 which manages the flow of EPG and text
`
`data in accordance with the invention. As shown by dotted
`
`line in Figure 1,
`
`information services processor
`
`(ISP) 16 is
`
`preferably located at the cable head end with system manager
`
`12, HEC 14 and the signal scramblers.
`
`However,
`
`those skilled
`
`in the art will appreciate that all of the head end equipment
`need not be located at one site.
`
`As shown in Figure 1, EPG data is supplied from one
`
`or more local or remote EPG suppliers 18 via a satellite
`
`link, modem link or other communication link to an RS-232
`
`port of ISP 16. Similarly,
`
`channel suppliers 20 is provided via a satellite link,
`
`text data from one or more text
`modem
`
`link, or other communication link to another RS-232 port of
`
`ISP 16.
`
`In preferred embodiments,
`
`ISP 16 has a plurality of
`
`identical RS-232 ports for accepting data from a plurality of
`as
`
`EPG suppliers 18 and text channel suppliers 20. Also,
`
`shown,
`
`one of these RS-232 ports is preferably used for a
`control link to HEC 14 as well. As will be described in more
`
`detail below with respect to Figure 2,
`
`ISP 16 manages EPG and
`
`text source databases in response to control signals from HEC
`
`14 in order to provide EPG data and/or text channel data to
`selected viewers.
`
`As shown in Figure 1, HEC 14 also provides control
`
`data directly to the viewer's television tuner via an RS-485
`
`the control data from HEC 14
`output port.
`Preferably,
`includes the aforementioned text channel definition
`
`transactions as well as EPG definition transactions for
`
`instructing the tuner at which frequency to tune for the EPG
`
`data and the like.
`
`The control data may also include
`
`software for downloading into the viewer's tuner for
`
`reprogramming the viewer's tuner as necessary.
`
`In a
`
`Page 001138
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`

`
`2164808
`
`W0 94/29811
`
`PCT/US94/06361
`
`-8-
`
`the control data from HEC 14 is
`preferred‘embodiment,
`inserted into the vertical§blanking interval of the selected
`
`cable television signal by daisy—chained scramblers 22, 24
`
`and 26 using known in-band techniques, although the control
`
`data from HEC 14 may also be modulated on an out-of-band
`carrier or an in-band audio carrier for transmission as
`
`described in related U.S. Patent Application Serial No.
`
`07/983,766, filed December 1,
`
`1992 and assigned to the
`
`present assignee,
`
`the contents of which are hereby
`
`incorporated by reference.
`
`Preferably,
`
`scramblers 22-26 are
`
`daisy—chained so that the scramblers may be addressed
`EPG data and text
`
`individually or globally. Similarly,
`
`channel data from ISP 16 are provided to the viewer's
`
`television tuner via an RS-485 output port of ISP 16.
`
`EPG
`
`data and text channel data are similarly inserted into the
`
`vertical blanking intervals of selected cable television
`
`signals by EPG scrambler 28 and text channel scramblers 30
`
`and 32,
`
`respectively, using, for example,
`
`the in—band
`
`vertical blanking interval insertion techniques described in
`
`the aforementioned patent application serial no.
`
`07/983, 766
`scramblers
`
`filed December 1, 1992.
`
`Of course,
`
`22-32 may insert the control data,
`
`if desired,
`and text channel
`
`EPG data,
`
`data into other portions of the video signals such as the
`
`horizontal blanking intervals or else replace the video
`
`entirely.
`
`Those skilled in the art will also appreciate that
`
`a number of scramblers may be provided in accordance with the
`
`volume of data received from HEC 14 and ISP 16. Typically,
`
`however,
`
`the number of scramblers depends on the number of
`
`premium channels for which scrambling is used.
`
`Preferably, EPG scrambler 28 and text channel
`
`scramblers 30 and 32 are identical to control data scramblers
`
`22-26 and are similarly daisy—chained for individual or
`scramblers 28-32
`
`global addressing. As shown in Figure 1,
`
`receive a single serial data channel which carries the
`
`combined EPG data and text data and display control
`
`transactions (to be described in more detail with respect to
`for all data streams in use. Each scrambler is
`
`Figure 2)
`
`Page 001139
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`

`
`wo 94129811
`
`2 1 5
`
`5 ()8
`
`PCT/US94/06361
`
`-9-
`
`also equipped with memory for storing a predetermined amount
`of this data in an internal memory so as to minimize the
`
`number of database accesses. Preferably, scramblers 28-32
`
`have internal memory sufficient to store a significant number
`
`5 of transactions.
`
`For example, scrambler 30 may have enough
`
`internal memory to score a day's sports scores for display on
`
`a sports text channel.
`
`The data received and stored in
`
`scramblers 28-32 is preferably in RS-485 format, and the
`
`protocol in a preferred embodiment is SDLC. All data
`transactions to scramblers 28-32 are sent on individual data
`
`10
`
`streams specifying the target scrambler (station addresses in
`
`SDLC protocol), and the control data is sent on a global data
`stream which is filtered in the scramblers 28-32 based on the
`
`address of the scrambler so that the data streams can be
`
`15 configured by a transaction from ISP 16.
`
`The individual EPG
`
`data and text data streams are preferably generic in the
`
`scramblers so that they can be allocated as desired.
`
`Preferably, scramblers 28-32 have baud rates of at least
`9600.
`
`20
`
`Preferably,
`
`the subscriber's tuner is a set top
`
`tuner 34 which comprises an EPG memory 36 for storing the EPG
`
`data from ISP 16.
`
`For example, EPG memory 36 may store one
`
`or two weeks of EPG data for selective access by the viewer
`
`via a menu of the set top tuner 34. This menu preferably
`
`25 allows the viewer to scroll through the EPG data stored in
`
`EPG memory 36 using the key pads of the viewer's television
`
`remote control device.
`
`Set
`
`top tuner 34 may also comprise a
`
`nonvolatile template memory 38 for storing the template in
`
`which the EPG data is to be inserted for display to the
`
`30 viewer on the viewer's television 40.
`
`In this manner, a
`
`video signal containing the template display data need not be
`
`continuously retransmitted to the set top tuner 34,
`
`thereby
`
`saving more bandwidth.
`
`Instead,
`
`the EPG data only needs to
`
`be updated every 30 minutes or when there is a program
`
`35 change. Of course, different set top tuners 34 may have a
`varied amounts of memory and processing capabilities for such
`
`Page 001140
`
`

`
`2164608
`
`W0 94/29811
`
`PCT/US94/06361
`
`-10-
`
`purposes in accordance with the acceptable memory costs
`
`during manufacture of the set top tuner 34.
`
`As shown in Figure 1, set top tuner 34 may also
`
`comprise a text data memory 42 for storing a page of text
`Thus,
`
`data for presentation to the screen.
`
`text data is displayed to the subscriber,
`
`while one page of
`the next page of
`
`text data may be loaded into the text data memory 42.
`
`As noted above,
`
`ISP 16 of the invention manages the
`
`flow of text data and EPG data from the data service provider
`
`to the viewer's set top tuner 34.
`
`ISP 16 manages this data
`
`by accepting data only from one or more authorized text data
`
`and/or EPG data sources, processing the text data and EPG
`
`data in its internal database manager, and formatting the
`
`processed data into a common data transaction format for
`
`output to the scramblers for transmission to the set top
`tuner 34. Provision of EPG data and text data to the
`
`subscribers is controlled by the head end controller 14 via
`
`the control link as will be described in more detail below.
`
`In a preferred embodiment,
`
`ISP 16 comprises an IBM
`
`PS2 model 7546 personal computer having a plurality of RS-232
`
`serial input ports for EPG data and/or text data inputs and
`
`at least one RS-485 HDLC serial link at its output of the
`
`type used by HEC 14.
`
`the control link
`As shown in Figure 1,
`The hardware and
`
`will be a single RS-232 serial port.
`
`software components of ISP 16 are then configured as
`
`illustrated in Figure 2.
`
`As shown in Figure 2,
`
`ISP 16 preferably comprises a
`
`plurality of RS-232 ports which provide a common interface
`for the EPG data and text channel data asynchronously
`18 and text channel suppliers
`
`provided by the EPG supplier(s)
`20.
`The EPG data and text channel data is transmitted to ISP
`
`16 via a satellite link
`
`(when the interface is operated in
`
`10
`
`15
`
`20
`
`25
`
`30
`
`simplex mode) or by modem (when the interface is operated in
`the data is transmitted at a
`half duplex mode). Preferably,
`35 baud rate of at least 1200.
`
`ISP 16 functions as a "gate keeper" which only
`allows access by authorized data sources. Accordingly, when
`
`Page 001141
`
`

`
`W0 94l298ll
`
`2164608
`
`PCTIUS94l06361
`
`_
`
`_
`
`ISP 16 receives a message from an EPG supplier 18 or a text
`it first checks the data for
`
`channel supplier 20,
`authorization.
`
`If that supplier is not authorized,
`
`the data
`
`is ignored.
`
`On the other hand,
`
`if the supplier is authorized
`
`to access ISP 16,
`
`ISP 16 performs the requested action and
`
`returns a command response message.
`
`If the communications
`
`link is simplex,
`
`ISP 16 is limited by authorization codes,
`
`the response is ignored. Hence, access to
`but as will be
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`described below,
`
`access is also limited by whether the data
`
`provider provides the EPG data or text data in the
`
`transmission protocol expected by ISP 16.
`
`In particular, messages sent between an EPG
`
`supplier 18 or a text channel supplier 20 and ISP 16 are
`a data
`
`preferably formatted to include a start of text byte,
`
`block of ASCII characters,
`checksum bytes and an ASCII
`This format is used in commands sent to ISP
`
`carriage return.
`
`16 from the data suppliers as well as in responses sent to
`
`the data suppliers. As known by those skilled in the art,
`
`the
`
`checksum verifies proper message transmission by comparing
`
`the checksum in the message with an internally computed
`checksum. Preferably,
`bytes in the message field beginning with the first character
`
`the checksum is a two byte CRC of all
`
`following the start of text character up to but not including
`the checksum field.
`The checksum is transmitted in the
`
`message as the hexadecimal ASCII representation (four bytes)
`
`of the CRC computation.
`
`The data blocks, on the other hand,
`
`are configured differently depending upon whether the input
`data is EPG data or text data.
`
`EPG data from the EPG supplier 18 is formatted in
`
`accordance with an EPG command set including, for example, a
`
`Define Program Command which is used to identify all data
`
`relating to a single program, a Define Category Command which
`
`is used to establish a category for identifying different
`
`types of programs, and a Delete Category Command which is
`
`used to delete an unused category to make room in the
`The EPG
`
`database of ISP 16 for new programming categories.
`
`data is formatted on a "per program" basis by these commands.
`
`Page 001142
`
`

`
`wo 94/29811 2
`
`1
`n
`4 8 0 Q
`
`PCTIUS94/06361
`
`An example of a presently preferred format for a Define
`
`_ 12 -
`
`Program Command is as follows:
`
`Define Program Comand
`
`Byte
`5 1-2
`
`Description
`Command Code
`
`3-4
`
`Service Provider
`
`O2
`
`- EPG Supplier No.
`
`1
`
`03 - EPG Supplier No.
`
`04 - EPG Supplier No.
`
`10 — System Manager
`
`20 — Local Origination
`
`5-7
`
`Type of Service
`001 - EPG
`
`(O01-O99 National Services)
`
`(100-199 System Manager Services)
`
`(200—299 Local Origination Services)
`(300—399 Other Services)
`
`10
`
`15
`
`8-13
`
`Authorization Code From Supplier
`
`14-19
`
`Starting Date (e.g., 112292 = 11/22/92)
`
`20 20-25
`
`Starting Time (e.g., 123045 = 12:30:45)
`
`26-29
`
`30-32
`
`33
`
`Program Identifier (e.g. WTBS)
`
`Duration (e.g., 135 = 1 hour and 35 minutes)
`
`MPAA Rating (O=NO Rating,
`
`l=G, 2=NR, 3=PG, 4=PG13,
`
`5=R, 6=X, 7=NC17)
`
`25
`
`34
`
`Critique Number of * given by movie critic)
`
`35-36
`
`37-38
`
`Category Identification
`
`Attribute Bit Map
`0-1 = Stereo
`
`30
`
`35
`
`1-1 = Black and White
`
`2-1 = Closed Captioned
`
`3-1 = Bilingual
`
`4-1 = Spanish
`
`39-40
`
`Traits Bit Map
`
`0-1 = Profanity
`
`1-1 = Nudity
`2-1 = Violence
`
`3-1 = Adult Situations
`
`Page 001143
`
`

`
`WO 94/259811
`
`2164608
`
`PCT/US94I06361
`
`_ 13 _
`
`4-1 = Adult Theme
`
`5-1 = Adult Language
`
`41-
`
`Title and Program Description blocks
`
`Delimiter characters are used for variable length
`
`5
`
`fields such as the title and program description blocks to
`
`For example, a NUL (O
`
`SOH (1 hexadecimal)
`
`identify the length of the field.
`hexadecimal)
`means the field is null,
`and ETX
`
`means the field is valid,
`
`(3 hexadecimal)
`
`means the
`
`end of the current record.
`
`10
`
`15
`
`20
`
`In a preferred embodiment, each program's record
`
`includes two lines of characters with up to 9 characters per
`
`line for a half hour program title block
`
`(the EPG display
`
`area is 9 characters by 2 lines for a half hour program),
`
`CWO
`
`lines of characters with up to 19 characters per line for a
`
`one or more hour title block (the EPG display area is 19
`
`characters by 2 lines for a 1 hour program), and three lines
`
`of characters with up to 40 characters per line for a program
`
`description describing the program corresponding to the
`
`current record. Those skilled in the art will appreciate
`
`that half hour shows need not have a one hour program title
`
`block but that shows having a duration of one hour or more
`
`should have a short and long title block since the EPG data
`
`is scrolled on the screen and does not always permit the
`
`display of an entire long title for a program at the edge of
`these
`the time frame of the EPG on the display. Of course,
`
`25
`
`blocks may have different sizes and may be filled by the
`
`appropriate delimiter if no text is available.
`
`Once data transmitted with a Define Program Command
`
`is stored in an EPG database of ISP 16,
`
`the EPG data is
`
`formatted into transactions for transmission to the set top
`This
`
`tuner 34 as will be described in more detail below.
`
`command may also be used to update a program definition since
`
`it will overwrite a corresponding entry in the EPG database
`
`of ISP 16.
`
`As noted above,
`
`the EPG data is preferably
`
`updated at least every 30 minutes on the half hour and also
`
`when changes are made to the data.
`
`30
`
`35
`
`Page 001144
`
`

`
`W0 94I29811
`
`2164808
`
`PCT/US94/06361
`
`-14-
`
`The Define Category Command also is formatted to
`
`have a command code,
`
`service provider, and type of service in
`
`bytes 1-7.
`the Define Category Command preferably
`However,
`has
`category identification data in bytes 8-9 and a category
`
`name having up to 21 bytes starting at byte 10. Once again,
`
`a delimiter is preferably used to mark the end of the field.
`
`In a preferred embodiment, up to 99 different categories may
`
`be defined using this command. Any categories beyond 99 will
`
`be ignored. Categories should thus be deleted to make room
`
`for new ones.
`
`The Delete Category Command is similarly
`
`formatted except that it is not necessary to specify the
`
`category name — the category ID is sufficient to specify a
`
`category to be deleted.
`
`ISP 16 may respond to such commands from the EPG
`
`supplier 18 by sending an appropriate response such as: no
`error
`
`(normal response), service provider not found (not
`
`authorized),
`
`type of service not found (not authorized),
`
`category ID not found, unrecognized command, checksum error,
`and the like.
`other EPG
`
`insufficient disk space,
`
`Of course,
`
`commands and command responses may be provided as desired.
`
`The above commands were merely described by way of example.
`
`However, it is important that any commands have a format
`
`known only to the authorized service providers in order to
`
`maintain system security.
`
`The text channel data, on the other hand, may
`
`originate from many different text channel suppliers 20 and
`
`may arrive at the ISP 16 via many different communications
`direct connect modem
`
`links such as satellite, dial up modem,
`
`or via direct connect to the system manager 12. Preferably,
`
`the text data is also supplied to the ISP 16 via an RS-232
`
`port identical to that used for receiving the EPG data and
`
`messages between the text channel supplier 20 and ISP 16 have
`
`the same general format and transmission characteristics as
`
`described above with respect to the EPG data except that the
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35 data blocks are formatted differently.
`
`in a preferred embodiment each text
`In particular,
`channel consists of one or more text screens, where each text
`
`Page 001145
`
`

`
`WO 94l298l1
`
`2154808.
`
`_
`
`_
`
`PCTIUS94/06361
`
`screen is comprised of 16 lines by either 24 or 45 characters
`
`per line depending upon the size of each character. Unlike
`
`the EPG data,
`
`the text data is not provided on a program
`
`the text data is provided for each line of
`basis. Rather,
`text on a text screen basis where one line of text is
`
`5
`
`transmitted in each text data block. Preferably,
`
`the text
`
`channel suppliers 20 provide the text data by defining text
`screens using a command formatted as follows:
`Define Text Screen
`
`10 Byte
`1-2
`
`Description
`Command Code
`
`3-4
`
`Service Provider
`
`02 - Text Supplier No.
`
`03 — Text Supplier No.
`
`04 - Text Supplier No.
`
`1
`
`2
`
`3
`
`10 — System Manager
`
`20 - Local Origination
`
`5-7
`
`Type of Service
`001 — EPG
`
`15
`
`20
`
`25
`
`8-13
`
`14-15
`
`16-17
`
`30
`
`18
`
`002 - Sports
`003 — Weather
`
`004-099 other Text Service
`
`(OO1—O99 National services)
`
`(100—199 System Manager Services)
`
`(200-299 Local Origination Services)
`
`(300-399 Other services)
`
`Authorization Code From Supplier
`
`Page #
`
`Line # (1-16)
`
`Justification
`
`O
`
`— Centered
`
`1 — Right
`2 - Left
`
`19-20
`
`Color
`
`35
`
`21
`
`Character Size
`
`0 - Normal
`
`(45 Characters per line)
`
`1 — Large (24 Characters per line)
`
`Page 001146
`
`

`
`2164608
`WO 94129811
`
`PCT/US94/06361
`
`_
`
`-
`
`22-??
`??
`
`Text 45 or 24 Bytes Max depending on Character Size
`SOH (01 Hex) End of Line Delimiter
`
`All bytes after byte 16 are repeated for each line
`
`of text until a complete page has been
`
`sent.
`
`The page number
`
`is then updated in bytes 14-15 and the
`
`16 for storage in the appropriate text
`
`next page sent to ISP
`database.
`As with the
`
`EPG data,
`
`the above-mentioned response
`
`codes may also be
`
`provided to the text channel supplier 20 which transmitted
`the text data to ISP 16.
`The structure of ISP 16 will now be
`
`described with respect to Figure 2.
`
`ISP 16 primarily comprises a plurality of databases
`
`and database managers. As shown in Figure 2,
`
`there are
`
`essentially two types of databases maintained in ISP 16 -
`The
`
`type for EPG data and one type for text channel data.
`
`one
`
`EPG database is designed to collect data from each EPG
`
`supplier and to sort each EPG program record by channel and
`
`time of day.
`
`A separate database is created for each text
`
`channel for collecting text data from the associated text
`
`channel supplier 20 and formatting that the received text
`
`data for transmission on individual text channels using the
`
`techniques to be described below.
`
`Each database that is
`
`created is identified by the service provider and type of
`
`service codes listed in the Define Program Command for use in
`
`the control link commands provided to ISP 16 from HEC 14.
`
`As shown in Figure 2, a received command is checked
`
`for its command code,
`
`the service provider,
`
`type of service
`
`and authorization code, as appropriate, by router and
`formatter 43.
`If the command is from an unauthorized data
`
`source,
`
`the subsequent data is ignored. However,
`router and
`
`if the
`
`received data is from an authorized supplier,
`
`10
`
`15
`
`20
`
`25
`
`30
`
`formatter 43 routes the data to the appropriate database
`within ISP 16.
`
`For example,
`
`if EPG data is received,
`
`routed via EPG database manager 44 to EPG database 46.
`if the received data is text data from a
`
`the other hand,
`
`it is
`On
`
`35
`
`weather service,
`
`the weather data is routed via weather
`
`database manager 48 to weather database 50. Similarly, if
`
`Page 001147
`
`

`
`W0 94I29811
`
`2164608
`
`PCT/US94/06361
`
`-17-
`
`the received data is text data from a sports service,
`
`the
`
`sports data is routed via sports database manager 52 to
`
`sports database 54.
`
`Those skilled in the art will appreciate
`
`that a single database manager may perform the function of
`
`the separate database managers as indicated by dotted line in
`Also,
`
`those skilled in the art will appreciate
`
`Figure 2.
`
`that the separate databases may be implemented on the hard
`
`disk of the storage means of ISP 16 as also indicated by
`
`dotted line in Figure 2.
`
`In a preferred embodiment, EPG database manager 44
`
`sorts the received EPG data by channel and time of day and
`
`stores the received EPG data in the appropriate location in
`
`EPG database 46 for later recall.
`
`EPG database manager 44
`
`may also perform garbage collection on the EPG database 46 as
`deleted.
`
`EPG database manager 44 may also call a
`
`records are
`
`10
`
`15
`
`data compression software routine such as the Huffman
`
`Compression Algorithm which, as known to those skilled in the
`
`art, maps more frequently used characters to fewer bits than
`
`20
`
`the usual eight bits used in normal ASCII, while giving the
`The number of
`
`less frequently used characters more bits.
`
`bits used for a character is based on its probability of
`
`appearing in the data stream. Huffman encoding is described
`
`in detail in an article entitled "Lossless Data Compression",
`
`gygg, March,
`
`1991, pp. 309-314.
`
`Such a routine is desired to
`
`maximize storage efficiency at EPG database 46.
`
`Similarly,
`
`each text database manager stores the text information in the
`
`associated text database and performs data compression.
`
`Router and formatter 43 and database managers 44,
`
`48 and 52 are all controlled by configurator 56, which is,
`
`in
`
`turn, responsive to control data from HEC 14. Configurator
`
`56 responds to control commands from HEC 14 to provide
`
`updated authorization information to router and formatter 43
`
`for comparison with the incoming data and for
`
`adding/subtracting database managers and databases and the
`
`like as EPG suppliers 18 and text channel suppliers 20 are
`
`added and subtracted from the system.
`
`25
`
`30
`
`35
`
`Page 001148
`
`

`
`WO 94129811
`
`2164608
`
`PCT/US94/06361
`
`-18-
`
`As noted above, access to ISP 16 is carefully
`
`controlled through the use of authorization codes.
`
`In
`
`addition,
`
`ISP 16 maintains control over the information
`
`services provided to the viewer by storing the EPG data and
`
`text data in a particular format in the appropriate database
`
`within ISP 16.
`
`For example,
`
`the EPG database may store the
`
`data in a particular binary tree format.
`
`Since the speed of
`
`the EPG database is not an issue in accordance with the
`
`invention (because the EPG database only needs to be able to
`
`read and write a number of records equal to the total number
`
`of channels in the cable system once every half an hour), a
`
`simple binary tree database has been used in a preferred
`Such an EPG database will be stored on a hard
`embodiment.
`
`disk drive of ISP 16.
`
`Preferably,
`
`the first 4 bytes stored
`
`on the hard disk drive will contain the file offset of the
`Each
`
`root node and the database records will follow.
`
`database record will contain,
`
`in addition to the required
`
`data, a left branch file offset and a right branch file
`offset.
`
`The left branch file offset points to the records
`
`with keys less than the current record, while the right
`
`branch file offset points to the records with keys greater
`
`than the current record.
`
`The database will use the program
`
`data and time and channel number as their key.
`
`For fastest
`
`access,
`
`those skilled in the art will appreciate that it is
`
`important to keep the database tree balanced.
`In a preferred embodiment,
`the EPG database records
`
`are formatted such that the left branch appears first,
`
`then
`
`the record key data and then the non—key
`the right branch,
`the EPG database key is a
`record data. As shown in Figure 3,
`
`combination of the date and time field and the channel number
`
`from the EPG data.
`
`Following these fields are the duration
`
`10
`
`15
`
`20
`
`25
`
`30
`
`field,
`
`the repeat field,
`
`the program rating field,
`
`the
`
`the attributes
`the critique field,
`program category field,
`the text data
`flag field,
`the program traits flag field,
`compressed flag and lastly the text data. Preferably,
`the
`text data field further consists of several optional
`
`35
`
`subfields with a delimiter between each field. As noted
`
`Page 001149
`
`

`
`“K)9UflWll
`
`PCT/US94/06361
`
`2164808
`
`-19-
`
`above,
`
`the subfields preferably include the short program
`
`title line 1,
`
`the short program title line 2,
`
`the long
`
`program title line 1,
`
`the long program title line 2, and
`
`three lines of program description.
`
`EPG database manager 44 accesses the EPG database
`
`46 through shared library routines such as add a record,
`In other
`and the like.
`
`delete a record, read a record,
`
`words,
`
`an application program does not access the EPG
`
`database 46 directly.
`
`In a preferred embodiment,
`
`the EPG
`
`database 46 also uses a semaphore to disallow more than one
`
`process thread (EPG database manager 44 and EPG transaction
`
`formatter 58)
`
`from changing at any given time. As the EPG
`
`database 46 is used, it is fragmented as records are added
`
`and deleted, and as a result, EPG database manager 44
`
`preferably further includes garbage collection routines for
`
`periodically performing the garbage collection function on
`
`the EPG database 46.
`
`The text databases are similarly
`
`configured except that garbage collection is not necessary.
`EPG transaction formatter 58 reads the database
`
`records of EPG database 46 and formats them into program-
`
`based transactions having a predetermined number of bytes
`which are transmitted to the EPG scrambler 28 for insertion
`
`into the vertical blanking interval of a video signal and
`
`transmission to the set top tuner 34. These transactions are
`
`then sent via a transaction arbitrator 64 to the EPG
`
`scrambler 28 shown in Figure 1 for insertion into the
`
`appropriate video channel. Similarly, weather transaction
`
`formatter 60 and sports transaction formatter 62 read the
`
`database records of weather database 50 and sports database
`
`54, respectively, and formats the text data into text screen-
`
`based transactions which may inserted into the vertical
`
`blanking interval of a Video signal.
`
`Preferably,
`
`at least
`
`one transaction is inserted into a vertical blanking interval
`It has been found that 22
`
`of each field of a video signal.
`
`bytes per transaction is a convenient transaction size to
`
`allow a transaction to fit into a vertical blanking interval
`of a field in this manner.
`In addition,
`the current time and
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`Page 001150
`
`

`
`2164608
`
`WO 94129811
`
`PCT/US94/06361
`
`_ 20 _
`
`date may be obtained from ISP system clock 63 to assure that
`
`the appropriate EPG programs are sent in the appropriate time
`slots.
`
`The transactions from transaction arbitrator 64 are
`
`output to a single RS-485 output port of ISP 16 which is
`
`connected to multiple scramblers of the type used to scramble
`
`The transactions are segmented into
`premium cable channels.
`EPG data and text data streams for transmission to the EPG
`
`10
`
`15
`
`20
`
`25
`
`30
`
`scrambler 28
`
`(if the transaction includes EPG data) or to the
`text channel scramblers 30 and 32
`
`(if the transaction
`EPG
`
`includes text data).
`
`In a preferred embodiment,
`
`transaction formatter 58 also tags the EPG transactions as
`
`Long Term or Short Term as they are transmitted to the EPG
`scrambler 28.
`
`EPG Short Term and Long Term data differ only
`
`in the timeliness of the information they provide to the set
`
`top tuner 34. Short Term data can be specified by HEC 14 via
`
`the control link to be anywhere from 1 to 255 hours of EPG
`data.
`The function of this Short Term data stream is to
`
`provide a quick refresh of the most
`
`immediate portion of the
`
`EPG data stored in EPG memory 36 of the set top tuner 34.
`
`Long Term data,
`EPG data.
`
`on the other hand, consists of the remaining
`
`The maximum time for the Long Term EPG data may
`
`also be specified by HEC 14 via the control link to be
`
`anywhere from 1 to 4096 hours, for example.
`
`The EPG transactions generated by EPG transaction
`formatter 58 are formatted into SDLC frames as noted above.
`
`A sample SDLC format for the EPG transaction data is shown in
`
`Figure 4.
`
`In Figure 4,
`
`the beginning flag delineates the
`
`beginning of the SDLC frame,
`
`the station address delineates
`
`the scrambler to be addressed,
`
`the control byte is a command
`
`code that defines what is to be processed,
`
`the information
`
`field contains the EPG data formatted as in Figure 3,
`frame check contains the CRC for all data between the
`
`the
`
`beginning and ending flags, and the ending flag delineates
`A transmission from EPG
`the end of the SDLC frame.
`
`35
`
`transaction formatter 58 will address a specific data stream
`
`and a response from the EPG scrambler 28 will identify its
`
`Page 001151
`
`

`
`WO 94/29811
`
`2164608
`
`PCTIUS94/06361
`
`-21-
`
`data stream in the station address location. As noted above,
`
`such transmissions may or may not require a response from the
`EPG scrambler 28.
`
`The EPG transactions typically include an Add EPG
`
`Block command including a byte specifying that the following
`
`data is from the EPG data stream, a control code byte
`
`specifying,
`
`for example, whether a reply from the scrambler
`
`is expected,
`
`two bytes setting forth the EPG data block
`
`number,
`
`a flag setting forth whether the EPG data is Short
`
`Term or Long Term data,
`
`the number of transactions which make
`
`up the EPG data block,
`
`and the actual transactions.
`
`EPG
`
`transaction formatter 58 may also generate a Delete EPG Block
`
`command which specifies that the data is to be deleted from
`
`the EPG data stream,
`
`the control code byte, and the EPG block
`
`number to be deleted. These two transaction type for Long
`
`Term and Short Term EPG data may be used together to form a
`
`block of EPG data for insertion into the vertical blanking
`As noted above,
`the EPG data
`interval of a video signal.
`
`block preferably defines all of the information for a single
`
`program at a specific time,
`
`such as short and long titles
`
`and three lines of program description.
`
`Figure 5 illustrates a flow chart for the software
`
`embodied in EPG transaction formatter 58.
`
`As shown,
`
`the
`
`software starts at step 500 and gets the system time and date
`
`from the ISP system clock 63 at step 502. An expired EPG
`
`data block is then deleted from the memory of the EPG
`
`scrambler 28 at step 504.
`
`An expired EPG data block is
`
`defined as a data block representing a program which has been
`
`completely aired prior to the current system time or a
`
`program which was aired before the time window used for the
`
`EPG. At step 506,
`
`current EPG data blocks having a time and
`
`date within the EPG time window are read from the EPG
`
`database 46.
`
`The current EPG data blocks are then formatted
`
`into Add EPG Block co