(12; United States Patent
`Barton et al.
`
`(10) Patent N0.:
`(45) Date of Patent:
`
`US 6,233,389 B1
`May 15, 2001
`
`USUU6233389B1
`
`('54) MULTIMEDIA TIME WARPING SYSTEM
`
`OTHER PUBLICKFIONS
`
`_/\STARTl_" DVDirector'”“ Beta Testing Program.
`
`Primrrry Exmm'rrei‘—Thai Tran
`(74) Atmmey, Agent, or H1"rtr—Michael A. Glenn; Kirk
`Wong
`
`(57)
`
`ABSTRACT
`
`A multimedia time warping system. The invention allows
`the user to store selected television broadcast programs
`while the user is simultaneously watching or reviewing
`another program. A preferred embodiment of the invention
`accepts television (TV)
`input streams in a multitude of
`forms, for example, National Television Standards Commit-
`tee (NTSC) or PAL broadcast, and digital forms such as
`Digital Satellite System (DSS), Digital Broadcast Services
`{DB8}, or Advanced Television Standards Committee
`(ATSC). The TV streams are converted to an Moving
`Pictures Experts Group (MPEG) formatted stream for inter-
`nal transfer and manipulation and are parsed and separated
`it into video and audio components. The components are
`stored in temporary buffers. Events are recorded that indi-
`cate the type of component that has been found, where it is
`located, and when it occurred. The program logic is notified
`that an event has occurred and the data is extracted from the
`
`bu[Ters. The parser and event bulTer decouple the CPU from
`having to parse the MPEG stream and from the real time
`nature of the data streams which allows for slower CPU and
`bus speeds and translate to lower system costs. The video
`and audio components are stored on a storage device and
`when the program is requested for display, the video and
`audio components are extracted from the storage device and
`reassembled into an MPEG stream which is sent
`to a
`decoder. The decoder converts the MPEG stream into TV
`
`output signals and delivers the TV output signals to a TV
`receiver. User control commands are accepted and sent
`through the system. These commands alfect the flow of said
`MPEG stream and allow the user to view stored programs
`with at least the following functions: reverse, fast forward,
`play, pause, index, fastfslow reverse play, and fast,=’slow play.
`
`(75)
`
`Inventors: James M. Barton, hos Uatos;
`Roderick James Melnnis, Milpitas;
`Alan S. Moskowitz, San Francisco;
`Andrew Martin Goodman, Menlo
`Park; Cliing Tong Chow, Fremont;
`Jean Swey Kao, Cupertino, all of (TA
`(US)
`
`(73) Assignee: TiV0, Ine., Alviso, CA (US)
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09,r’126,tIF/'1
`
`(22
`
`Filed:
`
`Jul. 30, 1998
`
`(51)
`
`Int. CL? ..................................................... .. H04N 5792
`
`('52) U.S. Cl. . .............................................. .. 386746; 380768
`
`(58) Field of Search .................................. .. 38671, 33, 45,
`386746, 111-112, 125-126, 68; 369760;
`36677, 33; 34877, 10, 571, 714, 722, 725;
`H04N 5776, 5792, 9779, 5714
`
`(56)
`
`References Cited
`U.S. I-’ATl;‘NT I)()CUMl_’.NTS
`
`2.-“I991 Cooper ............................... .. 3587149
`1.-“I982 Cooper
`.... .. 3537149
`571987 Cooper
`.. 358,-‘I45
`4.-" 1993 Cooper . . . . . . ..
`. . . . .. 3587149
`12.-"1994 Logan et al.
`.... .. 3437571
`8.71995 Lynch et al.
`358,-‘335
`..
`8,.'l996 Cooper et al.
`3487513
`11.-“I996 Cooper ............................... .. 3437512
`
`
`
`Re. 33,535
`4,313,135
`4,665,431
`5,202,761
`5,371,551
`5,438,423
`5,550,594
`5,572,261
`
`(List continued on next page.)
`FOREIGN PATENT DOCUMENTS
`
`0726574
`
`871996 (F?) .......................... .. G113,-'27,-T134
`
`61 Claims, 12 Drawing Sheets
`
`101'
`
`
`
`Input
`streams
`
`I06
`
`SAMSUNG 1004
`
`1
`
`SAMSUNG 1004
`
`

`
`US 6,233,389 B1
`Page 2
`
`5,787,225 *
`5,920,842
`539373138 at
`
`"H1998 Ilonjo ................................. .. 386E111
`7';‘]999 Cooper el al.
`. T-‘U4.«’5fT3
`
`gfrlggg Fukuda cl 3'‘ _m____m___m___m 386E112
`
`* cited by cxamincr
`
`U.S. P/\'l‘I_-‘.N'l‘ I)()CUML".N'l'S
`
`............................... .. 348K461
`10.31997 COOP-Cl‘
`12fl99?' Kim ct al.
`1/1998 Isaka .................................. .. 386E125
`
`
`
`5,675,338
`5,696,868
`5,706,388
`
`2
`
`

`
`U.S. Patent
`
`May 15, 2001
`
`Sheet 1 of 12
`
`US 6,233,389 B1
`
`Input
`st reams
`
`p
`
`MPEG
`st reams
`
`3
`
`

`
`U.S. Patent
`
`May 15, 2001
`
`Sheet 2 of 12
`
`US 6,233,389 B1
`
`201
`
`Input
`
`input
`Module
`
`Input
`
`Input
`M0dU'9
`
`202
`
`203
`
`204
`
`0t
`
`1
`
`Output
`Moduie
`
`0t
`
`1
`
`Output
`Module
`
`206
`
`397
`
`208
`
`209
`
`205
`
`Media
`Switch
`
`FIG.2
`
`4
`
`

`
`U.S. Patent
`
`May 15, 2001
`
`Sheet 3 of 12
`
`US 6,233,389 B1
`
`308
`
`302
`
`305
`306
`
`307
`
`5
`
`

`
`U.S. Patent
`
`May 15, 2001
`
`Sheet 4 of 12
`
`US 6,233,389 B1
`
`401
`
`Parser
`
`406
`
`407
`
`402
`
`pointer
`next pointer
`
`408-
`
`409
`
`pointer
`next pointer
`
`403
`
`pointer
`next pointer
`
`404
`
`pointer
`next pointer
`405}
`
`FIG. 4
`
`410
`
`video buffer
`
`411
`
`audio buffer
`
`4f2
`
`private data buffer
`
`413
`
`event buffer
`
`502 --
`
`503
`
`address
`
`type
`
`504
`
`time stamp
`
`FIG.5
`
`6
`
`

`
`U.S. Patent
`
`May 15, 2001
`
`Sheet 5 of 12
`
`US 6,233,389 B1
`
`Circu1c1r
`
`Segment
`Buffers
`
`
`
`603'
`
`Medic: Switch
`
`
`
`
`
`A Logi col
`Segment
`
`
`
`
`Length
`
`Type : 1-FRAME
`
`Timestomp 1‘ 096453
`
`604
`
`
`
`H.
`
`Translated t
`Logical
`Segments
`
`‘#303
`
`6'05
`
`\\\
`
`\‘
`
`I.
`I
`
`,5
`.1‘
`
`I
`
`/I’
`
`7
`
`

`
`U.S. Patent
`
`May 15, 2001
`
`Sheet 6 of 12
`
`US 6,233,389 B1
`
`5
`
`
`audio
`video
`on-screen
`
`display
`
`1710.7
`
`8
`
`

`
`U S Patent
`
`May 15 2001
`
`Sheet 7 of 12
`
`US 6,233,339 31
`
`Trans forms
`
`hard disk
`
`FIG. 8
`
`9
`
`

`
`U S Patent
`
`May 15 2001
`
`Sheet 8 of 12
`
`US 6,233,339 B1
`
`912
`
`
`
`
`
`Tmk Clip
`Cache
`
`10
`
`Source
`
`904
`
`
`
`
`
`.906
`
`
`903
`9‘?
`Tmk Core
`905
`_Tmk_
`999
`9”
`_Tmk_
`lTmk_
`.
`Prpelme releaselimptyauf
`Prpehne
`Pipeline
`
`Tmk Sgurce * _ Tmk Sink
`c1llocEmptyBuf nextFuHBuf
`
`
`
`
`99:‘:
`‘W5
`Medic: Switch
`
`
`
`
`
`
`Ve Ia
`decoder
`
`
`
`
`
`
`
`10
`
`

`
`U.S. Patent
`
`May 15, 2001
`
`Sheet 9 of 12
`
`US 6,233,389 B1
`
`1002\
`
`TmkC I ipCc3che
`
`11
`
`

`
`U.S. Patent
`
`May 15, 2001
`
`Sheet 10 of 12
`
`US 6,233,389 B1
`
`FIG. 71
`
`12
`
`12
`
`

`
`U.S. Patent
`
`May 15, 2001
`
`Sheet 11 of 12
`
`US 6,233,389 B1
`
`NTSC Field Sequence
`
`Picture {
`
`Region
`
`VBI Line 21 (FCC Mandated)
`
`If Even field, Line 21
`Contains Extended Data
`Services (EDS) data (e.g.,
`Time of day, V—chip)
`
`/1202
`
`N
`
`'t'
`P
`tE t
`ex my OS‘
`‘on
`
`
`
`Next Unpcl rsed
`Character
`
`Recognizer state machine
`
`
`
`Separate into
`words
`
`Word2 Stc1teB ____..
`Word3 StateC
`
`i205
`
`
`
`
`
`
`
`Words added to 0 special
`segment
`in the fixed-size
`PES buffer.
`
`FIG. 72
`
`13
`
`“-120?
`
`Trigger
`Action
`
`
`
`
`
`
`
`Start capture ,
`Stop capture,
`Phrase seen ,
`
`Etc.
`
`13
`
`

`
`U.S. Patent
`
`May 15, 2001
`
`Sheet 12 of 12
`
`US 6,233,389 B1
`
`FIG. 13
`
`14
`
`14
`
`

`
`US 6,233,389 B1
`
`1
`MULTIMEDIA TIME WARPING SYSTEM
`
`BACKGROUND OF THE INVENTION
`
`1. Technical Field
`
`The invention relates to the time shifting of television
`broadcast signals. More particularly, the invention relates to
`the real
`time capture, storage, and display of television
`broadcast signals.
`2. Description of the Prior Art
`The Video Cassette Recorder (VCR) has changed the
`lives of television (TV) viewers throughout the world. The
`VCR has offered viewers the flexibility to time—shift TV
`programs to match their lifestyles.
`The viewer stores TV programs onto magnetic tape using
`the VCR. The VCR gives the viewer the ability to play,
`rewind, fast forward and pause the stored program material.
`These functions enable the viewer to pause the program
`playback whenever he desires,
`fast
`forward through
`unwanted program material or commercials, and to replay
`favorite scenes. Ilowever, a VCR cannot both capture and
`play back information at the same time.
`One approach to solving this problem is to use several
`VCRs. For example,
`if two video tape recorders are
`available,
`it might be possible to Ping-Pong between the
`two. In this case, the fll'Sl recorder is started at the beginning
`of the program of interest. If the viewer wishes to rewind the
`broadcast, the second recorder begins recording, while the
`first recorder is halted, rewound to the appropriate place, and
`playback initiated. However, at
`least a third video tape
`recorder is required if the viewer wishes to fast forward to
`some point in time after the initial rewind was requested. In
`this case, the third recorder starts recording the broadcast
`stream while the second is halted and rewound to the
`
`appropriate position. Continuing this exercise, one can
`quickly see that
`the equipment becomes unwieldy,
`unreliable, expensive, and hard to operate, while never
`supporting all desired functions. In addition, tapes are of
`finite length, and may potentially end at inconvenient times,
`drastically lowering the value of the solution.
`The use ofdigital computer systems to solve this problem
`has been suggested. US. Pat. No. 5,371,551 issued to Logan
`et al., on Dec. 6, 1994, teaches a method for concurrent
`video recording and playback. It presents a microprocessor
`controlled broadcast and playback device. Said device com-
`presses and stores video data onto a hard disk. Ilowever, this
`approach is diificult
`to implement because the processor
`requirements for keeping up with the high video rates makes
`the device expensive and problematic. The microprocessor
`must be extremely fast to keep up with the incoming and
`outgoing video data.
`It would be advantageous to provide a multimedia time
`warping system that gives the user the ability to simulta-
`neously record and play back TV broadcast programs. It
`would further be advantageous to provide a multimedia time
`warping system that utilises an approach that decouples the
`microprocessor from the high video data rates,
`thereby
`reducing the microprocessor and system requirements which
`are at a premium.
`
`SUMMARY OF THE INVENTION
`
`The invention provides a multimedia time warping sys-
`tem. The invention utilizes an easily manipulated, low cost
`multimedia storage and display system that allows the user
`to view a television broadcast program with the option of
`instantly reviewing previous scenes within the program. In
`
`‘ll!
`
`15
`
`2U
`
`25
`
`40
`
`45
`
`60
`
`65
`
`2
`addition, the invention allows the user to store selected
`television broadcast programs while the user is simulta-
`neously watching or reviewing another program.
`A preferred embodiment of the invention accepts televi-
`sion ('I'V)
`input streams in a multitude of forms,
`for
`example, analog forms such as National Television Stan-
`dards Committee (NTSC) or PAL broadcast, and digital
`forms such as Digital Satellite System (DSS), Digital Broad-
`cast Services (DBS), or Advanced Television Standards
`Committee (ATSC). Analog TV streams are converted to an
`Moving Pictures Experts Group (MPl_’.(}) formatted stream
`for internal transfer and manipulation, while pre—formatted
`MPEG streams are extracted from the digital TV signal and
`presented in a similar format to encoded analog streams.
`The invention parses the resulting MPI.".G stream and
`separates it
`into its video and audio components. It
`then
`stores the components into temporary butfers. Events are
`recorded that indicate the type of component that has been
`found, where it
`is located, and when it occurred. The
`program logic is notified that an event has occurred and the
`data is extracted from the buffers.
`
`The parser and event buffer decouple the CPU from
`having to parse the MPEG stream and from the real time
`nature of the data streams. This decoupling allows for slower
`CPU and bus speeds which translate to lower system costs.
`The video and audio components are stored on a storage
`device. When the program is requested for display, the video
`and audio components are extracted from the storage device
`and reassembled into an MP}.-EU stream. The MPEG stream
`is sent to a decoder. The decoder converts the MPEG stream
`into TV output signals and delivers the TV output signals to
`a TV receiver.
`
`User control commands are accepted and sent through the
`system. These commands affect
`the How of said MPl_’.(}
`stream and allow the user to view stored programs with at
`least the following functions: reverse, fast forward, play,
`pause, index, fastfslow reverse play, and fastfslow play.
`Other aspects and advantages of the invention will
`become apparent from the following detailed description in
`combination with the accompanying drawings, illustrating,
`by way of example, the principles of the invention.
`BRIL".I" IHLSCRIPTION ()[7 'l'IIl'_". DR/\W'INGS
`
`l"'I(}. I is a block schematic diagram of a high level view
`of a preferred embodiment of the invention according to the
`invention;
`FIG. 2 is a block schematic diagram of a preferred
`embodiment of the invention using multiple input and output
`rnodules according to the invention;
`FIG. 3 is a schematic diagram of an Moving Pictures
`Experts Group (MPEG) data stream and its video and audio
`components according to the invention;
`FIG. 4 is a block schematic diagram of a parser and four
`direct memory access (DMA) input engines contained in the
`Media Switch according to the invention;
`FIG. 5 is a schematic diagram of the components of a
`packetized elementary stream (PES) bu ifer according to the
`invention;
`FIG. 6 is a schematic diagram of the construction of a I-’I_".S
`buffer from the parsed components in the Media Switch
`output circular buffers;
`FIG. 7 is a block schematic diagram of the Media Switch
`and the various components that
`it communicates with
`according to the invention;
`FIG. 8 is a block schematic diagram of a high level view
`of the program logic according to the invention;
`
`15
`
`15
`
`

`
`US 6,233,389 B1
`
`3
`FIG. 9 is a block schematic diagram of a class hierarchy
`of the program logic according to the invention;
`FIG. 10 is a block schematic diagram of a preferred
`embodiment of the clip cache component of the ir1vention
`according to the invention;
`l"I(i. 11 is a block schematic diagram of a preferred
`embodiment of the invention that emulates a broadcast
`
`studio video mixer according to the invention;
`FIG. 12 is a block schematic diagram of a closed caption
`parser according to the invention; and
`FIG. 13 is a block schematic diagram of a high level view
`of a preferred embodiment of the invention utilizing a VCR
`as an integral component of the invention according to the
`invention.
`
`|)Ij'|"AII.l£D I)t£SCRIP’I‘I()N 01‘ TIIIE.
`INVENTION
`
`The invention is embodied in a multimedia time warping
`system. A system according to the invention provides a
`multimedia storage and display system that allows the user
`to view a television broadcast program with the option of
`instantly reviewing previous scenes within the program. The
`invention additionally provides the user with the ability to
`store selected television broadcast programs while simulta-
`neously watching or reviewing another program and to view
`stored programs with at
`least
`the following functions:
`reverse, fast forward, play, pause, index, faslfslow reverse
`play, and fastfslow play.
`Referring to FIG. 1, a preferred embodiment of the
`invention has an Input Section 101, Media Switch 102, and
`an Output Section 103. The Input Section 101 takes televi-
`sion (TV)
`input streams in a multitude of forms,
`for
`example, National Television Standards Committee (NTSC)
`or PAL broadcast, and digital forms such as Digital Satellite
`System (DSS), Digital Broadcast Services (DBS), or
`Advanced Television Standards Committee (ATSC). DBS,
`DSS and /\TS(f are based on standards called Moving
`Pictures Experts Group 2 (MPEG2) and MPEG2 Transport.
`MPEG2 Transport is a standard for formatting the digital
`data stream from the TV source transmitter so that a TV
`
`receiver can disassemble the input stream to find programs
`in the multiplexed signal. The Input Section 101 produces
`MPEG streams. An MPEG2 transport multiplex supports
`multiple programs in the same broadcast channel, with
`multiple video and audio feeds and private data. The Input
`Section 101 tunes the channel
`to a particular program,
`extracts a specific MP].-lG program out of it, and feeds it to
`the rest of the system. Analog TV signals are encoded into
`a similar MPEG format using separate video and audio
`encoders, such that the remainder of the system is unaware
`of how the signal was obtained. Information may be modu-
`lated into the Vertical Blanking Interval (VB!) of the analog
`TV signal in a number of standard ways; for example, the
`North American Broadcast Teletext Standard (NABTS) may
`be used to modulate information onto lines 10 through 20 of
`an NTSC signal, while the FCC mandates the use of line 21
`for Closed Caption (CC) and Extended Data Services
`(EDS). Such signals are decoded by the input section and
`passed to the other sections as if they were delivered via an
`Ml-‘liG2 private data channel.
`The Media Switch 102 mediates between a microproces-
`sor CPU 106, hard disk or storage device 105, and memory
`104. Input streams are converted to an MPEG stream and
`sent to the Media Switch 102. The Media Switch 102 butfers
`the MPEG stream into memory. It then perfonns two opera-
`tions if the user is watching real time TV: the stream is sent
`
`‘IE!
`
`15
`
`2U
`
`25
`
`40
`
`45
`
`60
`
`65
`
`4
`
`to the Output Section 103 and it is written simultaneously to
`the hard disk or storage device 105.
`The Output Section 103 takes MPEG streams as input and
`produces an analog TV signal according to the NTSC, PAL,
`or other required TV standards. The Output Section 103
`contains an MPEG decoder, On-Screen Display {()SI))
`generator, analog TV encoder and audio logic. The OSD
`generator allows the program logic to supply images which
`will be overlayed on top of the resulting analog TV signal.
`Additionally, the Output Section can modulate information
`supplied by the program logic onto the VIII of the output
`signal in a number of standard formats, including NABTS,
`CC and EDS.
`
`With respect to FIG. 2, the invention easily expands to
`accommodate multiple Input Sections (tuners) 201, 202,
`203, 204, each can be tuned to different types of input.
`Multiple Output Modules (decoders) 206, 207, 203, 209 are
`added as well. Special effects such as picture in a picture can
`be implemented with multiple decoders. The Media Switch
`205 records one program while the user is watching another.
`This means that a stream can be extracted off the disk while
`another stream is being stored onto the disk.
`Referring to FIG. 3, the incoming MPEG stream 301 has
`interleaved video 302, 305, 306 and audio 303, 304, 30’?
`segments. These elements must be separated and recom-
`bined to create separate video 308 and audio 309 streams or
`bulfers. This is necessary because separate decoders are used
`to convert MPEG elements back into audio or video analog
`components. Such separate delivery requires that
`time
`sequence inforrnation be generated so that the decoders may
`be properly synchronized for accurate playback of the
`signal.
`The Media Switch enables the program logic to associate
`proper time sequence information with each segment, pos-
`sibly embedding it directly into the stream. The time
`sequence information for each segment
`is called a
`time
`stamp. These time stamps are monotonically increasing and
`start at zero each time the system boots up. This allows the
`invention to find any particular spot in any particular video
`segment. For example,
`if the system needs to read five
`seconds into an incoming contiguous video stream that is
`being cached, the system simply has to start reading forward
`into the stream and look for the appropriate time stamp.
`A binary search can be performed on a stored file to index
`into a stream.
`I.-'.ach stream is stored as a sequence of
`fixed-size segments enabling fast binary searches because of
`the uniform time stamping. If the user wants to start in the
`middle of the program, the system performs a binary search
`of the stored segments until it finds the appropriate spot,
`obtaining the desired results with a minimal amount of
`information. If the signal were instead stored as an Ml-’L".(l
`stream, it would be necessary to linearly parse the stream
`from the beginning to find the desired location.
`With respect to FIG. 4, the Media Switch contains four
`input Direct Memory
`(DMA) engines 402, 403, 4-04,
`405 each DM/-\ engine has an associated buffer 4-10, 4-11,
`412, 4-13. Conceptually, each DMA engine has a pointer 4-06,
`a limit for that pointer 407, a next pointer 408, and a limit
`for the next pointer 409. Each DMA engine is dedicated to
`a particular type of information, for example, video 4-02,
`audio 403, and parsed events 405. The buffers 4-I0, 4-11, 4-12,
`413 are circular and collect the specific information. The
`DMA engine increments the pointer 406 ir1to the associated
`bufler until it reaches the limit 407 and then loads the next
`pointer 408 and limit 409. Setting the pointer 406 and next
`pointer 408 to the same value, along with the corresponding
`
`16
`
`16
`
`

`
`US 6,233,389 B1
`
`5
`limit value creates a circular buffer. The next pointer 408 can
`be set to a different address to provide vector DMA.
`The input stream flows through a parser 401. The parser
`401 parses the stream looking for MPEG distinguished
`evenLs indicating the start of video, audio or private data
`segments. For example, when the parser 401 finds a video
`event, it directs the stream to the video DMA engine 402.
`The parser 401 buffers up data and DMAs it into the video
`buffer 410 through the video DMA engine 402. At the same
`time,
`the parser 401 directs an event to the event DM/-\
`engine 405 which generates an event into the event bulTer
`413. When the parser 401 sees an audio event, it redirects the
`byte stream to the audio DMA engine 403 and generates an
`event into the event buffer 413. Similarly, when the parser
`401 sees a private data event, it directs the byte stream to the
`private data DMA engine 4-04 and directs an event to the
`event butfer 413. The Media Switch notifies the program
`logic via an interrupt mechanism when events are placed in
`the event buffer.
`
`Referring to FIGS. 4 and 5, the event buffer 413 is filled
`by the parser 401 with events. Each event 501 in the event
`buffer has an offset 502, event type 503, and time stamp field
`504. The parser 401 provides the type and otfset of each
`event as it is placed into the buffer. For example, when an
`audio event occurs, the event type field is set to an audio
`event and the olfset indicates the location in the audio buffer
`411. The program logic knows where the audio butfer 411
`starts and adds the otfset to find the event in the stream. The
`
`address otfset 502 tells the program logic where the next
`event occurred, but not where it ended. The previoLLs event
`is cached so the end ofthe current event can be found as well
`as the length of the segment.
`With respect to FIGS. 5 and 6, the program logic reads
`accumulated events in the event buffer 602 when it
`is
`interrupted by the Media Switch 601. From these events the
`program logic generates a sequence of logical segments 603
`which correspond to the parsed MPEG sements 615. The
`program logic converts the otfset 502 into the actual address
`610 of each segment, and records the event length 609 using
`the last cached event.
`If the stream was produced by
`encoding an analog signal, it will not contain Program Time
`Stamp (PTS) values, which are used by the decoders to
`properly present the resulting output. Thus, the program
`logic uses the generated time stamp 504- to calculate a
`simulated PTS for each segment and places that into the
`logical segment time stamp 607. In the case of a digital TV
`stream, PTS values are already encoded in the stream. The
`program loge extracts this information and places it in the
`logical segment time stamp 607.
`The program logic continues collecting logical segments
`603 until it reaches the fixed buflier size. When this occurs,
`the program logic generates a new butfer, called a Pack-
`etized Elementary Stream (PES) 605 bufier containing these
`logical segments 603 in order, plus ancillary control infor-
`mation. Each logical segment poinLs 604 directly to the
`circular buffer, e.g., the video butTer 613, filled by the Media
`Switch 601. This new butfer is then passed to other logic
`components, which may further process the stream hi the
`buflier in some way, such as presenting it for decoding of
`writing it to the storage media. Thus, the MPl_’.G data is not
`copied from one location in memory to another by the
`processor. This results in a more cost etfective design since
`lower memory bandwidth and processor bandwidth is
`required.
`A unique feature of the MP1.-I} stream transformation into
`PES bulTers is that the data associated with logical segments
`
`‘IE!
`
`15
`
`2E]
`
`25
`
`40
`
`45
`
`60
`
`65
`
`6
`need not be present in the butler itself, as. presented above.
`When a PBS buffer is written to storage,
`these logical
`segments are written to the storage medium in the logical
`order in which they appear. This has the efiect of gathering
`components of the stream, whether they be in the video,
`audio or private data circular buffers, into a single linear
`buffer of stream data on the storage medium. The buffer is
`read back from the storage medium with a single transfer
`from the storage media, and the logical segment information
`is updated to correspond with the actual locations in the
`bulfer 606. Iligher level program logic is unaware of this
`transformation, since it handles only the logical segments,
`thus stream data is easily managed without requiring that the
`data ever be copied between locations in DRAM by the
`CPU.
`
`/\ unique aspect ol‘ the Media Switch is the ability to
`handle high data rates effectively and inexpensively.
`It
`performs the functions of taking video and audio data ir1,
`sending video and audio data out, sending video and audio
`data to disk, and extracting video and audio data from the
`disk on a low cost platfonrt. Generally, the Media Switch
`runs asynchronously and autonomously with the micropro-
`cessor CPU, using its DMA capabilities to move large
`quantities of infonrtation with minimal intervention by the
`CPU.
`
`Referring to I-"IO. 7, the input side of the Media Switch
`701 is connected to an MPEG encoder 703. There are also
`
`circuits specific to MPEG audio 704 and vertical blanking
`interval (VBI) data 702 feeding into the Media Switch 701.
`If a digital TV signal is being processed instead, the MPEG
`encoder 703 is replaced with an MPEG2 Transport
`Demultiplexor, and the MPEG audio encoder 704 and VBI
`decoder 702 are deleted. The demultiplexor multiplexes the
`extracted audio, video and private data channel streams
`through the video input Media Switch port.
`The parser 705 parses the input data stream from the
`MPEG encoder 703, audio encoder 704 and VB] decoder
`702, or from the transport demultiplexor in the ease of a
`digital TV stream. The parser 705 detects the beginning of
`all of the important events in a video or audio stream, the
`start of all ol‘ the frames, the start of sequence headers«—all
`of the pieces of information that the program logic needs to
`know about in order to both properly play back and perform
`special effects on the stream, e.g. fast forward, reverse, play,
`pause, fast.r‘slow play, indexing, and fastfslow reverse play.
`The parser 705 places tags 707 into the l5"II-‘O 706 when
`it identifies video or audio segments, or is given private data.
`The DMA 709 controls when these tags are taken out. The
`tags 707 and the DMA addresses of the segments are placed
`into the event queue 708. The frame type information,
`whether it is a start of a video I-frame, video I3-frame, video
`P—frame, video PES, audio PES, a sequence header, an audio
`frame, or private data packet, is placed into the event queue
`708 along with the otfset in the related circular buffer where
`the piece of information was placed. The program logic
`operating in the CPU 713 examines events in the circular
`buffer after it is transferred to the DRAM 714.
`The Media Switch 701 has a data bus 711 that connects to
`the CPU 713 and DRAM 714. An address bus 712 is also
`shared between the Media Switch 701, CPU 713, and
`DRAM 714. A hard disk or storage device 710 is connected
`to one of the ports of the Media Switch 701. The Media
`Switch 701 outputs streams to an MPEG video decoder 715
`and a separate audio decoder 717. The audio decoder 717
`signals contain audio cues generated by the system in
`response to the user's commands on a remote control or
`
`17
`
`17
`
`

`
`US 6,233,389 B1
`
`7
`other internal events. The decoded audio output from the
`MPEG decoder is digitally mixed 718 with the separate
`audio signal. The resulting signals contain video, audio, and
`on—screen displays and are sent to the TV 716.
`The Media Switch 701 takes in 8-bit data and sends it to
`the disk, while at the same time extracts another stream of
`data off of the disk and sends it to the MI’l£(} decoder 715.
`All of the DMA engines described above can be working at
`the same time. The Media Switch 701 can be implemented
`in hardware using a liield Programmable Gate Array
`(FPGA), ASIC, or discrete logic.
`Rather than having to parse through an immense data
`stream looking for the start of where each frame would be,
`the program logic only has to look at
`the circular event
`buffer in DRAM 714 and it can tell where the start of each
`
`frame is and the frame type. This approach saves a large
`amount of CPU power, keeping the real time requirements
`of the CPU 713 small. The CPU 713 does not have to be very
`fast at any point in time. The Media Switch 701 gives the
`CPU 713 as much time as possible to complete tasks. The
`parsing mechanism 705 and event queue 708 decouple the
`CPU 713 from parsing the audio, video, and buffers and the
`real time nature of the streams, which allows for lower costs.
`It also allows the use of a bus structure in a CPU environ-
`ment that operates at a much lower clock rate with much
`cheaper memory than would be required otherwise.
`The CPU 713 has the ability to queue up one DMA
`transfer and can set up the next DMAtransfer at its leisure.
`This gives the CPU 713 large time intervals within which it
`can service the DM/\ controller 709. The CPU 713 may
`respond to a DMA interrupt within a larger time window
`because of the large latency allowed. MPEG streams,
`whether extracted from an MPEG2 Transport or encoded
`from an analog TV signal, are typically encoded using a
`technique called Variable Bit Rate encoding (VBR). This
`technique varies the amount of data required to represent a
`sequence of images by the amount of movement between
`those images. This technique can greatly reduce the required
`bandwidth for a signal, however sequences with rapid move-
`ment (such as a basketball game) may be encoded with much
`greater bandwidth requirements. For example, the llughes
`DirecTV satellite system encodes signals with anywhere
`from 1 to 10 Mbfs of required bandwidth, varying from
`frame to frame. It would be diflicult for any computer system
`to keep up with such rapidly varying data rates without this
`S1fl.lC[Ll]'C.
`
`With respect to FIG. 8, the program logic within the CPU
`has three conceptual components: sources 801, transforms
`802, and sinks 803. The sources 801 produce buifcrs of data.
`Transforms 802 process bufTers of data and sinks 803
`consume bulTers of data. A transform is responsible for
`allocating and queuing the buifers of data on which it will
`operate. Bulfers are allocated as if “empty” to sources of
`data, which give them back “full”. The bulTers are then
`queued and given to sinks as “full”, and the sink will return
`the buffer “empty”.
`A source 801 accepts data from encoders, e.g., a digital
`satellite receiver. It acquires buffers for this data from the
`downstream transform, packages the data into a buffer, then
`pushes the buffer down the pipeline as described above. The
`source object 301 does not know anything about the rest of
`the system. The sink 803 consumes bu ffers, taking a buffer
`from the upstream transform, sending the data to the
`decoder, and then releasing the buiTer for reuse.
`There are two types of transforms 802 used: spatial and
`temporal. Spatial transforms are transforms that perfonn, for
`
`‘ll!
`
`15
`
`2U
`
`25
`
`40
`
`45
`
`60
`
`65
`
`8
`
`example, an image convolution or compression!
`decompression on the buifered data that is passing through.
`Temporal transforms are used when there is no time relation
`that is expressible between buffers going in and buffers
`coming out of a system. Such a transform writes the buffer
`to a file 804 on the storage medium. The buffer is pulled out
`at
`a
`later time, sent down the pipeline, and properly
`sequenced within the stream.
`Referring to FIG. 9, a C++ class. hierarchy derivation of
`the program logic is shown. The TiVo Media Kernel (Tmk)
`904, 908, 913 mediates with the operating system kernel.
`The kernel provides operations such as: memory allocation,
`synchroni'/.ation, and threading. The TmkCore 904, 908, 913
`structures memory taken from the media kernel as an object.
`It provides operators, new and delete, for constructing and
`deconstructing the object. Each object (source 901, trans-
`form 902, and sink 903) is multi-threaded by definition and
`can run in parallel.
`The TmkPipeline class 905, 909, 914 is respon