Ulllted States Patent
`
`19
`
`11
`
`Patent Number:
`
`5 774 676
`9
`9
`
`Stearns et al.
`
`[45] Date of Patent:
`
`*Jun. 30, 1998
`
`US005774676A
`
`[54] METHOD AND APPARATUS FOR
`DECOMPRESSION OF MPEG COMPRESSED
`DATA IN A COMPUTER SYSTEM
`
`95 32578
`
`11/1995 WIPO .
`
`OTHER PUBLICATIONS
`
`[75]
`
`Inventors; Charles C_ Stearns, San Jose;
`Stephanie w_ Ti, Mi1pitaS’b0th of
`Cahf.
`
`Foley, P.:. “The MPACT Media Processor Redefines the
`Multimedia PC”,
`IEEE Comput. Soc. Press, USA, pp.
`311-318, XP000577494, proceedings of Compcon ’96.
`
`[73]
`*
`
`[
`
`.
`.
`A551gT1993 S3: I11C01‘P01‘3ted> Santa Clara, Ca11f~
`.
`.
`] Nedeei
`The term of due peter” Shall not extend
`beyond the explranen date of Pat‘ No‘
`5,774,676.
`
`[21] Appl' No‘: 5383887
`[22]
`Filed:
`Oct 3, 1995
`
`Gruger, K., et al.: MPEG-1 Low Cost Encoder Solution,
`Proceedings of the SPIE—The International Society for
`Optical Engineering, 1995, USA, pp. 41-51, XP000577418,
`Advanced Image and Video Communications and Storage
`Technologies, Amsterdam, Netherlands, 20-23 Mar. 1995.
`
`Primary Exami/1er—Ellis B. Ramirez
`Attorney, Agent, or Firm—SkjerVen, Morrill, MacPherson,
`Franklin & Fr1el LLP; Norman R. Khvans
`
`Int. Cl.5
`[51]
`[52] U.S. Cl.
`[5 l
`
`G06F 17/00
`[57]
`ABSTRACT
` MPEG compressed data is decompressed in a computer
`. .. . . . . . . . . . .
`. . . . . . . . . . . . .. 395/200.77
`Field of Search .......................... .. 364/514 R, 514 A,
`system by sharing Computational decompression tasks
`364/71502; 395/200~77> 412> 439; 382/233>
`between the computer system host microprocessor,
`the
`246> 234
`graphics accelerator, and a dedicated MPEG processor in
`order to make best use of resources in the computer system.
`Thus the dedicated MPEG processor is of minimum capa-
`bility and hence advantageously minimum cost. The host
`microprocessor is used to decompress the MPEG upper data
`layers. The more powerful the host microprocessor, the more
`upper data layers it decompresses The remainder of the
`decom ression (lower data la ers)
`is
`erformed b
`the
`Mpmpd d.
`t d
`d5/’
`th
`P h.
`15’
`t
`e 1“ e Processor an 0‘
`e g”? 1“ “Ce era 0“
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`5,212,742
`533353321
`5’379’356
`5,394,534
`5,493,339
`5,557,538
`5,642,139
`
`5/1993 Normille et al.
`8/1994 Hamey et al‘
`1/1995 Purcelletal‘
`2/1995 Kulakowski et al.
`2/1996 Birch et al.
`. . . . . . . . .
`9/1996 Retter et al.
`6/1997 Eglit et al.
`
`..................... .. 382/233
`395/162
`382/233
`395/425
`. . . .. 348/461
`. 364/514 R
`............................ .. 382/233
`
`FOREIGN PATENT DOCUMENTS
`0 503 956
`9/1992 European Pat. Off.
`.
`
`26 Claims, 14 Drawing Sheets
`
`Microfiche Appendix Included
`(1 Microfiche, 51 Pages)
`
`
`
`1
`Peripheral Bus Y
`42
`
`
`
`
`
`
`Lower ioyer
`decompression
`
`3
`'
`
`UPPGT '9)?’
`d600mPie33'°”
`
`
`Page 1 of 24
`
`Samsung Exhibit 1007
`Petitioners HTC & LG - Exhibit 1007, p. 1
`
`
`
`
`
`Graphics Acc.
`
`System
`Memory
`
`35
`
`MPEG Acc.
`
`
`
`C54
`
`30
`
` Micro
`Processor
`
`Petitioners HTC & LG - Exhibit 1007, p. 1
`
`

`
`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 1 of 14
`
`5,774,676
`
`White/ Green Book Layer
`
`MPEG System Layer
`
`r“d"‘i
`
`Audio Layer
`
`Video Layer
`Sequence
`Group of Pictures
`Picture
`Slice
`MacroBlock
`
`1 F
`
`FIG.
`
`rame
`Buffer
`
`38:
`
`Lower layer
`
`decompression
`
`f
`
`3
`
`36
`
`Peripheral Bus -
`
`Chip Set
`
`Micro
`
`34
`
`30
`
`Upper layer
`decompression
`
`FIG. 2
`
`Page 2 of 24
`
`Petitioners HTC & LG - Exhibit 1007, p. 2
`
`Petitioners HTC & LG - Exhibit 1007, p. 2
`
`

`
`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 2 of 14
`
`5,774,676
`
`Peripheral Bus
`
`3
`42
`
`Micro
`Processor
`
`layer
`Lower
`decompression
`
`3
`
`'0)/el
`UPP€F
`d9C0mP“3'5'3'0”
`
` 50
`
`
`, ,
`
`408
`
`ll
`l
`Peripheral Bus
`
`Micro
`
`Processor
`
`Y
`42
`
`Graphics Acc.
`
`MPEG Ace.
`
`
`
`.
`
`. n
`
`__ _ _ _
`
`Sound
`System
`
`l
`
`52
`\
`
`Upper loyer
`Lower layer
`-
`decompression
`decompression
`
`
`- -
`
`CD—ROM
`
`
`FIG. 4
`
`Page 3 of 24
`
`Petitioners HTC & LG - Exhibit 1007, p. 3
`
`Petitioners HTC & LG - Exhibit 1007, p. 3
`
`

`
`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 3 of 14
`
`5,774,676
`
`82>
`
`co_mmoaEo8Q
`
`gs;
`
`:o:oN_co._;o§m
`
`2_.6o_2
`
`222
`
`co_m$aEo$o
`
`2:8:
`
`0%
`
`mas
`
`.382
`
`25
`
`eém
`
`r.»
`
`25En.
`
`NV
`
`Page 4 of 24
`
`Petitioners HTC & LG - Exhibit 1007, p. 4
`
`Petitioners HTC & LG - Exhibit 1007, p. 4
`
`
`
`
`
`

`
`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 4 of 14
`
`5,774,676
`
`Start
`Frame
`
`Start
`Frame
`
`Start
`Frame
`
`Start
`Frame
`
`Start
`Frame
`
`Start
`Frame
`
`L
`
`_
`Drsplay
`
`Host
`
`(Software)
`DW9’
`
`"
`
`P
`I Program
`
`1
`
`i
`3
`
`1
`
`B1
`
`_._r
`Program
`
`frame
`
`‘
`
`B2
`
`___1
`Program
`
`P6
`
`t Program
`
`B4
`
`.__1
`Program
`
`B5
`
`Program
`
`dlsploy
`IO frame
`P
`-
`1
`
`r
`
`display
`B1 frame
`
`display
`B2 frame
`-
`
`1
`
`drsplay
`P3 frame
`1
`
`1
`
`I-\
`
`decode
`P6 frame_{
`
`decode
`B4 frame
`
`11
`
`11
`
`decode
`[ B2 frame 1
`
`Start
`Frame
`
`Start
`Frame
`
`Start
`Frame
`
`Start
`Frame
`
`Start
`Frame
`
`Start
`Frame
`
`_
`Display
`
`1
`
`
`1
`
`I display
`10 frame
`-t
`
`V
`
`no display
`B1 frame
`
`display
`display
`P3 frame
`B2 frame
`‘—---Wt :--t
`
`W5
`
`decode
`10 frarr_1_e_{
`
`decode
`P3 frame_,
`
`decode
`r B1 frame
`
`decode
`decode
`B2 frame‘ HP6 frame‘
`
`decode
`B4 frame_{
`
`abandon
`
`B1
`
`frame
`
`Host
`
`/Software)
`L WV”
`
`Program
`
`Program
`
`Program
`
`Program
`
`Program
`
`FIG. 7
`
`Page 5 of 24
`
`Petitioners HTC & LG - Exhibit 1007, p. 5
`
`Petitioners HTC & LG - Exhibit 1007, p. 5
`
`

`
`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 5 of 14
`
`5,774,676
`
`Muster Controller
`
`52
`
`IVICK £3
`
`emnmmwmm
`
`22
`
`79
`
`445556
`
`142592
`
`7w.umm_A/www
`
`24
`
`82
`
`3704013
`455666
`
`3Hma.n_umW.wmw
`
`74287
`4127034
`
`49
`
`4+mmmmmmw“wM“mw
`
`.4nl.1l
`
`46
`
`51960
`23345
`
`57
`
`swmwwwmm
`
`12
`
`56
`
`104455
`005116
`
`58
`
`1711?.
`
`E?
`
`zmmwuwww
`
`28337
`11233
`
`48
`
`19W%.,m..mwW
`
`8 1
`
`1
`
`19
`
`22
`
`34
`
`36
`
`084623445
`42086
`
`39mmm._.nu
`
`35
`
`Page 6 of 24
`
`Petitioners HTC & LG - Exhibit 1007, p. 6
`
`Petitioners HTC & LG - Exhibit 1007, p. 6
`
`
`

`
`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 6 of 14
`
`
`
`/\ /x./\\{\ x//
`
`FIG. 10
`
`
`
`6 begin
`
`-t
`
`end 7r8
`
`8
`
`9 begin
`
`H
`
`r
`%
`’
`
`l_.
`
`end 4
`
`5 begin
`
`end 5
`
`.
`end 6] 7 begin
`end 9 i 10 begin
`
`i
`
`__J
`
`end 10 .
`
`FIG.
`
`11
`
`Page 7 of 24
`
`Petitioners HTC & LG - Exhibit 1007, p. 7
`
`Petitioners HTC & LG - Exhibit 1007, p. 7
`
`

`
`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 7 of 14
`
`5,774,676
`
`DATA_|N
`
`Page 8 of 24
`
`Petitioners HTC & LG - Exhibit 1007, p. 8
`
`Petitioners HTC & LG - Exhibit 1007, p. 8
`
`

`
`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 8 of 14
`
`5,774,676
`
`FORWARD REF. FRAME
`
`BACKWARD REF. FRAME
`
`
`
`POST
`
`P
`
`ROC SSING
`E
`
`124
`
`WR_DATA
`
`FIG. 13A
`
`DATAJN
`
`HORIZ.
`
`INTERP.
`
`118
`
`178
`
`IDCT MEMORY
`
`180
`
`VERTICAL INTERP.
`
`122
`
`POST PROCESSING
`
`124
`
`WR_DATA
`
`FIG. 13B
`
`Page 9 of 24
`
`Petitioners HTC & LG - Exhibit 1007, p. 9
`
`
`
` HORIZ. INTERP.
`
`HORIZ.
`
`INTERP.
`
` VERTICAL INTERP.
`
`VERRCAL INTERP.
`
`HBA
`
`122A
`
`Petitioners HTC & LG - Exhibit 1007, p. 9
`
`

`
`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 9 of 14
`
`5,774,676
`
`MPEG Driver
`
`
`
`VDE_|nit
`Allocate system memory buffers.
`
`MPG_lnit
`
`initialize drivers.
`
`
`
`
`
`
`
`
`VDE_Open
`
`Initialize painters and variables.
`
`
`
`MPG_Open
`Open MPEG file, prepare
`to read and parse.
`
`
`
`
`
` Read MPEG file data during initialization.
`
`
`VDE_AddPacket
`Parse video packet data into
`Send Video packets to VDE driver.
`
`
`Header buffer and Picture buffer.
`Send Audio packets to ADE driver.
`
`
`
`MPG_Decode
`Start audio and video
`
`decode and playback.
`
`
`
`VDE_Decode
`Program CP2 to start VDE decoding.
`
`
`
`7
`
`Read MPEG file data as needed to keep
`audio buffers filled. Send any video
`packets encountered to VDE driver.
`
`VDE_AddPacket
`Parse video packet data into
`Header buffer and Picture buffer.
`
`MPG_Close
`Close MPEG file,
`terminate decode.
`
`VDE_Ciose
`Make sure VDE is stopped.
`
`MPG_Exit
`Deinitialize drivers.
`
`VDE_Exit
`Free system memory buffers.
`
`End
`
`FIG. 14A
`
`Page 10 of 24
`
`Petitioners HTC & LG - Exhibit 1007, p. 10
`
`Petitioners HTC & LG - Exhibit 1007, p. 10
`
`

`
`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 10 of 14
`
`5,774,676
`
`VDE_lnit
`
`
`
`Allocate system memory buffers.
`
`
`
`.
`
`Raw Buffer
`
`is used to hold raw video packet
`data until
`it can be parsed.
`
`Header Buffer
`
`
` {
`
`is used to hold parameters extracted from
`Sequence, Group. and Picture headers.
`Used to program CP2 registers.
`
`
`
`
`
`Picture Buffer
`to be
`is used to hold picture layer data,
`copied later into CP2 private memory.
`
`
`
`
`
`Target Buffers
`transfer
`are two buffers where CP2 will
`decompressed frames using PCI bus master.
`
`
`
`FIG. 14B
`
`
`
`
`
`Initialize variables for new MPEG file.
`Prepare to receive video packets.
`
`
`
`Page 11 of 24
`
`Petitioners HTC & LG - Exhibit 1007, p. 11
`
`
`
`Petitioners HTC & LG - Exhibit 1007, p. 11
`
`

`
`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 11 of 14
`
`5,774,676
`
`VDE__AddPacket
`
`Extract video PTS,
`
`if any.
`
`
`
`Copy rest of video packet into Raw
`buffer temporarily, appending it
`to any
`leftover data from previous packet.
`
`
`
`
`
`
`Parse packet data in Raw buffer.
`
`if Sequence header found, extract
`image size, quantizer matrices, etc.
`
`Copy into Header buffer.
`
`If Group header found,
`extract
`time code, etc.
`
`Copy into Header buffer.
`
`Copy into Header buffer.
`
`
`
`If Picture header found, extract
`temporal reference, picture type, etc.
`Calcuiate PTS if none was given.
`
`
`
`Locate end of picture,
`and pad with picture end code.
`
`Copy into Picture buffer.
`
`if End of Sequence found,
`mark end of video sequence.
`
`Copy into Header buffer.
`
`FIG. 140
`
`Page 12 of 24
`
`Petitioners HTC & LG - Exhibit 1007, p. 12
`
`Petitioners HTC & LG - Exhibit 1007, p. 12
`
`

`
`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 12 of 14
`
`5,774,676
`
`VDE,Decode
`
`
`
`Program CP2 to partition private memory:
`VDE Input buffers Ping and Pong,
`I5 VDE Reference Frame buffers.
`
`
`
`Get from Picture buffer.
`
`Fill VDE Input Ping and Pong
`buffers with picture data.
`
`Program CP2 with Sequence information:
`image size, quantization matrices.
`
`Get from Header buffer.
`
`
`
`
`i
`
`Initialize STC to a reasonable value.
`
`
`
`Program CP2 to decode first picture:
`VPTS, Picture Offset, Picture Type, etc.
`
`Get from Header buffer.
`
`
`
`
`
`
`Program CP2 to decode second picture:
`
`VPTS, Picture Offset, Picture Type, etc.
`
`
`Get from Header buffer.
`
`
`
`FIG. MD
`
`Page 13 of 24
`
`Petitioners HTC & LG - Exhibit 1007, p. 13
`
`Petitioners HTC & LG - Exhibit 1007, p. 13
`
`

`
`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 13 of 14
`
`5,774,676
`
`and start of decoding of picture PNH.
`
`Called when SCR=VPTS.
`indicates start
`of PCi master transfer of picture PN.
`
`Check next entry in Header buffer.
`if next entry is End of Sequence, stop.
`
`Get from Header buffer.
`
`If next entry is Sequence Header, program
`CP2 with new quantization matrices.
`
`get from Header buffe,_
`
`if next entry is Group Header, reset
`some counters to start the next group.
`
`Get from Header buffer.
`
`_L_.
`
`If next entry is Picture Header, program
`CP2 for next picture PN+2:
`
`VPTS, Picture Offset, Picture Type, etc.
`
` Get from Header buffer.
`
`
`
`
`Send finished picture PN_1 from system
`memory buffer to 868 pixel formatter.
`
`FIG. ME
`
`Page 14 of 24
`
`Petitioners HTC & LG - Exhibit 1007, p. 14
`
`Petitioners HTC & LG - Exhibit 1007, p. 14
`
`

`
`U.S. Patent
`
`Jun. 30, 1998
`
`Sheet 14 of 14
`
`5,774,676
`
`
`
`
`
`
`Called when CP2 detects that one of
`the VDE lnput Ping or Pong buffer
`has been consumed.
`
`CV_lRQ Handler
`
`Get from Picture buffer.
`
`
`
`
`
`block of picture data.
`
`Fill Ping or Pong buffer with next
`
`End
`
`
`
`Make sure VDE and timers are stopped.
`
`
`
`
`
`
`
`
`Free system memory buffers
`allocated by VDE_lnit.
`
`
`
`FIG. 14F
`
`Page 15 of 24
`
`Petitioners HTC & LG - Exhibit 1007, p. 15
`
`Petitioners HTC & LG - Exhibit 1007, p. 15
`
`

`
`5,774,676
`
`1
`METHOD AND APPARATUS FOR
`DECOMPRESSION OF MPEG COMPRESSED
`DATA IN A COMPUTER SYSTEM
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`This application is related to copending and commonly
`owned U.S. patent applications Ser. No. 08/489,488, filed
`Jun. 12, 1995, entitled “Decompression of MPEG Com-
`pressed Data in a Computer System”, Charles C. Stearns,
`Ser. No. 08/490,322, filed Jun. 12, 1995, entitled “Video
`Decoder Engine”, Soma Bhattacharjee et al., Ser. No.
`08/489,489, filed Jun. 12, 1995, entitled “Audio Decoder
`Engine,” Charlene S. Ku et al., and Ser. No. 08/508,636,
`filed Jill. 28, 1995, entitled “Frame Reconstruction For
`Video Data Compression”, Stephanie W. Ti et al., all incor-
`porated by reference.
`
`MICROFICHE APPENDIX
`
`Amicrofiche appendix including 1 fiche and a total of 51
`frames is a part of this disclosure.
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`
`This invention relates to data decompression, and specifi-
`cally to decompression of MPEG compressed data in a
`computer system.
`2. Description of Prior Art
`The well-known MPEG (Motion Picture Experts Group)
`data standard defines two compression/decompression
`processes, called conventionally MPEG 1 and MPEG 2. For
`purposes of this disclosure, MPEG 1 and MPEG 2 are
`similar. The MPEG 1 standard is described in the ISO
`
`publication No. ISO/IEC 11172: 1993(E), “Coding for mov-
`ing pictures and associated audio .
`.
`. ”, and the MPEG 2
`standard is defined in the ISO publication No. ISO/IEC
`13818-2, both incorporated by reference herein in their
`entirety. The MPEG standard defines the format of com-
`pressed audio and video data especially adapted for e.g.,
`motion pictures or other live video. MPEG compression is
`also suitable for other types of data including still pictures,
`text, etc. The MPEG standard in brief (the above-mentioned
`publications are more complete) defines the data format
`structure shown in FIG. 1 for CD-ROM content. The top
`required layer is the MPEG system layer having underneath
`it, in parallel, the video layer and audio layer. The MPEG
`system layer contains control data describing the video and
`audio layers.
`Above (wrapped around) the MPEG system layer is
`another (optional) layer called the White book (“video CD”)
`or the Green book (“CDI”) that includes more information
`about the particular program (movie). For instance, the book
`layer could include Karaoke type information, high resolu-
`tion still
`images, or other data about how the program
`content should appear on the screen. The video layer
`includes sequence (video), picture (frame), slice (horizontal
`portions of a frame), macroblock (64 pixels by 64 pixels)
`and block (8 pixels by 8 pixels) layers, the format of each of
`which is described in detail by the MPEG standard.
`There are commercially available integrated circuits
`(chips) for MPEG decompression. Examples are those sold
`by C-Cube Microsystems and called the CL-450 and
`CL-480 products. In these products the MPEG audio and
`visual decompression (of all layers) is accomplished com-
`pletely in dedicated circuitry in an internally programmable
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`microcontroller. The book layer and entire MPEG system
`layer parsed to the last pixel of the compressed data are
`decompressed using the C-Cube Microsystems products.
`Thus these chips accomplish the entire decompression on
`their own, because these chips are intended for use in
`consumer type devices (not computers). Thus these chips
`include a system memory, a CD-ROM controller and any
`necessary processing power to perform complete MPEG
`decompression.
`Similar products are commercially available from a vari-
`ety of companies. While these products perform the decom-
`pression task fully in a functional manner, they are relatively
`expensive due to their inclusion of the large number of
`functions dedicated to MPEG decompression. Thus their
`commercial success has been limited by high cost.
`SUMMARY
`
`It has been recognized by the present inventors that in a
`computer (i.e., personal computer or workstation)
`environment, that already available elements are capable of
`performing a large portion of the MPEG decompression
`task. Thus in this environment use of a dedicated fully
`functional MPEG decompression integrated circuit is not
`necessary, and instead a substantial portion of the decom-
`pression can be off-loaded onto other conventional computer
`system elements. Thus only a relatively small portion of the
`actual data decompression must be performed by dedicated
`circuitry, if any. In accordance with the invention, the MPEG
`decompression task is allocated amongst various already
`existing elements of a typical computer system and if
`necessary, depending on the capabilities of these other
`elements, an additional relatively small (hence inexpensive)
`dedicated MPEG decompression circuit is provided.
`Thus advantageously in accordance with the present
`invention the MPEG (compressed using layers) content of
`data is decompressed in a computer system typically already
`including a microprocessor, graphics accelerator,
`frame
`buffer, peripheral bus and system memory. A shared com-
`putational approach between the microprocessor (host
`processor), graphics accelerator and a dedicated device
`makes best use of the computer system existing resources.
`This is a significant advantage over the prior art where the
`MPEG decompression is performed entirely by a dedicated
`processor. Thus in accordance with the invention by parti-
`tioning of the decompression process amongst the major
`available elements in a personal computer, decompression is
`provided inexpensively.
`Further, in accordance with the present invention frame
`reconstruction is carried out by logic circuitry including
`three main elements which are a horizontal interpolation
`element, a vertical interpolation element, and a post pro-
`cessing element. The horizontal interpolation element inter-
`polates two adjacent (horizontally adjacent) pixels in one
`particular MPEG block of pixels. That is, this is a digital
`averaging filter. The output of the horizontal interpolation
`element is then provided to the vertical interpolation element
`which similarly interpolates (averages) two pixels which are
`vertically adjacent in that same MPEG block. (In another
`embodiment, the vertical interpolation is before the hori-
`zontal interpolation.) In the post-processing element (which
`is a selector) the vertically and horizontally interpolated data
`is processed in conjunction with externally provided IDCT
`MPEG decompressed data to generate the final output data.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 shows conventional content layering for MPEG
`compression.
`
`Page 16 of 24
`
`Petitioners HTC & LG - Exhibit 1007, p. 16
`
`Petitioners HTC & LG - Exhibit 1007, p. 16
`
`

`
`5,774,676
`
`3
`FIG. 2 shows one embodiment of the invention with
`
`partitioning of decompression including a dedicated MPEG
`processor with associated private memory, in a computer.
`FIG. 3 shows a second embodiment of the invention also
`
`with a dedicated MPEG processor in a computer.
`FIG. 4 shows a third embodiment of the invention with
`
`partitioning of MPEG compression in a computer system
`using a high performance graphics accelerator.
`FIG. 5 shows a block diagram of a chip including MPEG
`video and audio decompression in accordance with the
`invention.
`
`FIG. 6 shows host processor/VDE partitioning of video
`decompression.
`FIG. 7 shows graceful degradation of video decompres-
`sion by abandoning frames.
`FIG. 8 shows in a block diagram three stage pipelining in
`the VDE.
`
`FIG. 9 shows a transparent IZZ process.
`FIG. 10 shows a group of pictures in display order in
`accordance with MPEG compression for frame reconstruc-
`tion.
`
`FIG. 11 shows an arrangement of slices in a picture in
`accordance with MPEG compression.
`FIG. 12 shows a frame reconstruction circuit in accor-
`
`dance with the present invention.
`FIGS. 13A and 13B show respectively parallel and serial
`processing in a frame reconstruction circuit as used for
`reconstruction of a B-type frame in accordance with the
`present invention.
`FIGS. 14A to 14F show a flowchart for a computer
`program for performing higher level video decompression in
`a host processor.
`Identical reference numbers in different figures refer to
`similar or identical structures.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`
`As well known, each element in a computer system (e.g.,
`personal computer or workstation) has particular strength
`and weaknesses. For instance,
`the microprocessor (host
`processor) is typically the single most capable and expensive
`circuit in a computer system. It is intended to execute a
`single instruction stream with control flow and conditional
`branching in minimum time. Due to its internal arithmetic
`units, the microprocessor has high capability for data pars-
`ing and data dependent program execution. However, the
`microprocessor is less capable at transferring large quanti-
`ties of data, especially data originating from peripheral
`elements of the computer.
`The core logic chip set of a computer interfaces the
`microprocessor to the peripherals, manages the memory
`subsystem, arbitrates usage and maintains coherency.
`However, it has no computational capabilities of its own.
`The graphics subsystem manages and generates the data
`which is local to the frame buffer for storing video and
`graphics data. The graphics subsystem has a capability to
`transfer large amounts of data but
`is not optimized for
`control flow conditional branching operation.
`The present inventors have recognized that in MPEG
`compressed content (video data) having the various layers,
`each layer has certain characteristics requiring particular
`hardware (circuit) properties to parse that level of informa-
`tion. For example, it has been determined that in the book
`and system layers of MPEG, which are the top most layers
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`4
`in the video data stream, the information resembles a pro-
`gram data/code data stream and in fact may contain execut-
`able code (software). The information at that level is thus
`like a program code stream containing control
`flow
`information, variable assignments and data structures.
`Hence it has been recognized that the microprocessor is
`suited for parsing such information. (The term “parsing”
`herein indicates the steps necessary to decompress data each
`layer of the type defined by the MPEG standard.)
`The video layer, under the system layer,
`includes the
`compressed video content. There are as described above an
`additional six layers under the video layer as shown in FIG.
`1. These layers are the sequence layer, group of pictures
`layer, picture layer, slice layer, macroblock layer, and block
`layer. All but
`the macroblock and block layers contain
`additional control and variable information similar to the
`
`type of information in the system layer. Thus again the
`microprocessor is best suited for parsing the information
`down to but not including the macroblock layer.
`Within the macroblock and block layers are compressed
`pixel data that requires, according to MPEG decompression,
`steps including 1) variable length decoding (VLD), 2)
`inverse zig-zagging (IZZ), 3) inverse quantization (IQ), 4)
`inverse discrete cosine transformation (IDCT), and 5)
`motion vector compensation (MVC),
`in that order. The
`VLD, IZZ, IQ, and especially IDCT are computationally
`intensive operations, and suitable for a peripheral processor
`or the microprocessor capabilities, assuming adequate pro-
`cessing capability being available in the microprocessor.
`However, in some cases depending on the microprocessor
`capabilities, the microprocessor itself may be insufficient in
`power or completely utilized already for parsing the upper
`layers.
`The remaining task for video decompression is motion
`vector compensation (MVC) also referred to as frame recon-
`struction
`MVC requires retrieving large quantities of
`data from previously decompressed frames to reconstruct
`new frames. This process requires transferring large
`amounts of video data and hence is suited for the graphics
`accelerator conventionally present in a computer system. An
`example of such a graphics accelerator is the Trident
`TVP9512, or S3 Inc. Trio 64V.
`The audio stream layer under the system layer includes
`the compressed audio content. Audio decompression
`requires 1) variable length decoding, 2) windowing, and 3)
`filtering. Since audio sampling rates are lower than pixel
`(video) sampling rates, computational power and data band-
`width requirements for audio decompression are relatively
`low. Therefore, a microprocessor may be capable of accom-
`plishing this task completely, assuming it has sufficient
`computational power available.
`Thus in accordance with the invention the MPEG decom-
`
`pression process is partitioned between the various hardware
`components in a computer system according to the compu-
`tational and data bandwidth requirements of the MPEG
`decompression. Thus the system partitioning depends on the
`processing power of the microprocessor.
`Therefore, while the present invention is applicable to
`computers including various microprocessors of the types
`now commercially and to be available,
`the following
`description is of a computer systems having a particular
`class of microprocessor (the 486DX2 class microprocessors
`commercially available from e.g., Intel and Advanced Micro
`Devices.) Thus this description is illustrative and the prin-
`ciples disclosed herein are applicable to other types of
`computer systems including other microprocessors of all
`
`Page 17 of 24
`
`Petitioners HTC & LG - Exhibit 1007, p. 17
`
`Petitioners HTC & LG - Exhibit 1007, p. 17
`
`

`
`5,774,676
`
`5
`types. As a general rule, it has been found empirically that
`no more than 30% of the microprocessor’s computing
`capability should be used for MPEG decompression in order
`to preserve the remaining portion for other tasks. It has to be
`understood that this rule of thumb subjective and somewhat
`arbitrary; it is not to be is construed as limiting.
`Moreover, the actual steps of MPEG decompression and
`apparatus to perform same are well known; see e.g. U.S. Pat.
`No. 5,196,946 issued Mar. 23, 1993 to Balkanski et al.; U.S.
`Pat. No. 5,379,356 issued Jan. 3, 1995 to Purcell et al., and
`European Patent Application publication 93304152-7, pub-
`lished Jan. 12, 1993, applicant C-Cube Microsystems, Inc.
`Therefore one skilled in the art will understand how to
`
`5
`
`10
`
`implement these well-known functions, which may be car-
`ried out in a variety of ways, all of which are contemplated
`in accordance with the invention.
`
`15
`
`In accordance with the first embodiment of the present
`invention shown in FIG. 2, microprocessor 30 (the host
`processor) has been found only to have computational power
`sufficient to decompress the MPEG book layer and system
`layer. Also, in this computer system the graphics accelerator
`40 e.g.,
`the Trio 64V chip from S3 Inc. has insufficient
`computing power to accomplish the motion vector compen-
`sation (MVC) decompression. Therefore, a dedicated pro-
`cessor called the MPEG accelerator 46 is provided to
`perform the remainder of the MPEG decompression tasks. It
`is to be understood that the MPEG accelerator 46 may be
`any suitable processor or dedicated logic circuit adapted for
`performing the required functions. The private memory 44 is
`e.g. one half megabyte of random access memory used to
`accomplish the MVC and is distinct from the frame buffer in
`the FIG. 1 embodiment.
`
`The other elements shown herein including the system
`memory 36, chip set 34, sound system 50, CD-ROM player
`52, and the peripheral bus 42, are conventional. In one
`version of the FIG. 2 embodiment as shown by the dotted
`line connecting MPEG accelerator 46 to PCI (peripheral)
`bus 42, the MPEG accelerator 46 is connected to PCI bus 42
`for video and audio decompression and typically would be
`a chip on an add-in card. The type of microprocessor 30,
`how the sound system 50 and other elements are connected,
`and the particular interconnection between the MPEG accel-
`erator 46 and the peripheral bus 42 are not critical to the
`present
`invention. Further,
`the particular partitioning
`described herein is not critical to the present invention but is
`intended to be illustrative.
`
`In a second version of the FIG. 2 embodiment, MPEG
`accelerator connects (see dotted lines) directly to graphics
`accelerator 40 for video decompression and to sound system
`50 for audio decompression, not via peripheral bus 42. This
`version would be typical where MPEG accelerator 46 is
`located on the motherboard of the computer.
`In FIG. 2, the lower layer MPEG decompression includes
`the functions performed by the private memory 44 and the
`MPEG accelerator 46. The upper layer decompression is that
`performed by microprocessor 30.
`It is to be understood that typically the source of the
`MPEG program material is a CD-ROM to be played on
`CD-ROM player 52. However, this is not limiting and the
`program material may be provided from other means such as
`an external source.
`
`Asecond embodiment is shown in FIG. 3. Again, here the
`486 class microprocessor 30 has sufficient computational
`power only to decompress the book layer and the system
`layer. In this embodiment a more capable graphics accel-
`erator 40A has the capability to perform the MPEG decom-
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`
`pression motion vector compensation (MVC). Therefore,
`the memory requirement for accomplishing MVC, which
`was accomplished by the private memory 44 in FIG. 2, here
`takes place either in the frame buffer 38 or the system
`memory 36. Therefore, in this case the lower layer decom-
`pression includes the functions performed by the graphics
`accelerator 40A, unlike the case with FIG. 2.
`The FIG. 3 embodiment, like that of FIG. 12, has two
`versions as shown by the dotted lines. In the first version,
`MPEG accelerator 46 communicates via peripheral bus 42.
`In the second version, MPEG accelerator 46 is directly
`connected to sound system 50 for audio decompression and
`to graphics accelerator 40A for video decompression.
`A third embodiment is shown in FIG. 4. In this case the
`MPEG accelerator functionality is included in a yet more
`powerful graphics accelerator 40B (a graphics controller).
`As in the embodiment of FIG. 3,
`the memory storage
`requirements for motion vector compensation (MVC) are
`satisfied by the off-screen memory in the frame buffer 38 or
`a non-cacheable portion of the system memory 36. The
`decompression of the audio layer is performed by either the
`sound system 50,
`the graphics accelerator 40A, or the
`microprocessor 30.
`Also, in accordance with the invention there may be a
`partitioning of the audio decompression between the micro-
`processor 30 and a dedicated audio decompression processor
`which may be part of the MPEG accelerator. Asystem of this
`type for audio decompression is disclosed in the above
`mentioned U.S. patent application Ser. No. 08/489,489, filed
`Jun. 12, 1995, entitled “Audio Decoder Engine”, Charlene
`Ku et al.
`Thus in accordance with the invention the MPEG decom-
`pression process is partitioned between various elements of
`a computer system. The more powerful
`the host
`microprocessor, the more upper layer decompression tasks it
`handles. The remainder of the decompression tasks are
`off-loaded to a dedicated MPEG accelerator (processor)
`circuit, or to a graphics accelerator already conventionally
`present in a computer system on a layer-by-layer basis. Thus
`the need for dedicated circuitry for MPEG decompression is
`minimized in accordance with the capabilities of the other
`elements of the computer system, hence reducing total
`computer system cost and making MPEG decompression
`more widely available even in low cost computer systems.
`The various elements of FIGS. 2, 3, and 4 are
`conventional, as is their interconnection, except for the
`MPEG accelerator and the decompression software in the
`microprocessor.
`The following describes a system as shown in present
`FIG. 2 for video decompression. This particular embodiment
`of the invention is illustrative and is for MPEG 1 decom-
`
`pression. The two chief elements disclosed herein are (1) the
`software driver (program) executed by the microprocessor
`which performs the upper layer video decompression, and
`(2) the MPEG accelerator circuit which is a dedicated digital
`signal processor for video decompression.
`FIG. 5 shows a high level block diagram of a chip which
`includes the MPEG accelerator 46 of for instance FIG. 2.
`
`This chip provides both video and audio decompression. The
`video decompression is of the type disclosed herein and the
`audio decompression is of the type disclosed in the above-
`referenced copending and commonly owned patent applica-
`tion. The chip includes a video decompression module 60
`which includes a video decompression engine (VDE), an
`audio decompression module which includes an audio
`decompression engine 64, and a synchronization module 62
`
`Page 18 of 24
`
`Petitioners HTC & LG - Exhibit 1007, p. 18
`
`Petitioners HTC & LG - Exhibit 1007, p. 18
`
`

`
`5,774,676
`
`7
`for synchronizing the video and audio in their decompressed
`forms. The VDE is a hardwired (circuitry) engine. Also
`provided is an audio display module 66 which provides the
`function of sending decompressed digital audio data to an
`external DAC.
`
`An arbiter 68 arbitrates amongst the various modules for
`purposes of private memory access. Also provided is a
`conventional memory controller 70 which interfaces with
`the private memory 44 of FIG. 2. Also provided is a
`peripheral master and slave bus interface 72 int