`
`Ulllted States Patent
`
`
`Stearns et al.
`
`
`
`[19]
`
`
`
`[11] Patent Number:
`
`
`
`
`
`
`[45] Date of Patent:
`
`5,774,676
`
`
`*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_ T], Mi]pi[aS,be[h of
`Cahf.
`
`
`
`
`[
`
`.
`.
`
`
`
`
`
`A551gT1ee3 S3: I11C01‘P01‘3ted> Santa Clara, Ca11f~
`[73]
`.
`.
`*
`
`
`
`
`
`
`
`
`
`] Nedeei
`The term of due peter” Shall not extend
`
`
`
`
`
`
`
`beyond the explraden date of Pat‘ No‘
`5,774,676.
`
`
`
`
`
`
`
`
`[21] Appl' No‘: 5383887
`
`
`
`
`[22]
`Filed.
`()et_ 3, 1995
`
`[51]
`Int. Cl.5 .................................................... .. G06F 17/00
`
`
`
`
`
`[52]
`"""""""" " 395/200377
`_
`
`
`
`
`
`
`
`
`
`
`
`[58] Fleld of Search .......................... .. 364/514 R, 514 A,
`
`
`
`
`
`
`364/71502; 395/200~77> 412> 439; 382/233>
`246> 234
`
`
`
`
`
`[56]
`
`
`
`
`
`
`5,212,742
`
`5,335,321
`5’379’356
`5,394,534
`5,493,339
`
`5,557,538
`
`5,642,139
`
`
`
`
`_
`
`References Clted
`
`
`
`
`
`Us. PATENT DOCUMENTS
`
`..................... .. 382/233
`5/1993 Normille et al.
`
`
`
`
`
`........................ .. 395/162
`8/1994 Harney et al.
`
`
`1/1995 Purcelletal‘
`382/233
`
`
`
`
`2/1995 Kulakowski et al.
`395/425
`. . . .. 348/461
`2/1996 Birch et al.
`. . . . . . . . .
`
`
`
`
`
`9/1996 Retter et al.
`. 364/514 R
`
`
`
`
`
`6/1997 Eglit et al.
`382/233
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FOREIGN PATENT DOCUMENTS
`9/1992 European Pat. Off.
`.
`0 503 956
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Foley, P.:. “The MPACT Media Processor Redefines the
`
`
`
`
`
`
`
`Multimedia PC”,
`IEEE Comput. Soc. Press, USA, pp.
`311-318, XP000577494, proceedings of Compcon ’96.
`
`
`
`
`
`
`
`
`
`
`
`
`
`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 Examiner—Ellis B. Ramirez
`
`
`
`
`
`
`
`
`Attorney, Agent, or Firm—SkjerVen, Morrill, MacPherson,
`
`
`
`
`
`Franklin & Friel LLP; Norman R. Klivans
`
`
`
`ABSTRACT
`[57]
`
`
`MPEG compressed data is decompressed in a computer
`
`
`
`
`
`
`
`
`
`
`
`System by Sharing Computational decompression tasks
`
`
`
`
`
`
`
`the
`between the computer system host microprocessor,
`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 deeempreeeee The remainder ef the
`
`
`
`
`
`
`
`decom ression (lower data la ers)
`erformed b
`the
`is
`
`
`
`
`
`
`
`t d
`MPEGPd d.
`d5/’
`th
`P h.
`15’
`t
`e lea e process“ an 0r
`e g”? leg aeee era 0“
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`26 Claims, 14 Drawing Sheets
`
`
`
`
`
`
`
`
`Microfiche Appendix Included
`(1 Microfiche, 51 Pages)
`
`
`
`
`
`
`
`
`
`System
`
`Memory
`
`36
`
`
`
`C54
`
`
`
`30
`
`
`
`
`
`
`
`
`
` Micro
`
`Processor
`
`
`
`
`
`
`I4
`
`2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Graphics Acc.
`
`
`MPEG Acc.
`
`
`
`
`
`
`
`1
`
`Peripheral Bus
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Lower ioyer
`
`decompression
`
`3
`3
`
`
`
`UPPGT '°Y9_I
`d6C0mPie33'°”
`
`
`
`
`
`
`Page 1 of 24
`
`Samsung Exhibit 1007
`
`Samsung Exhibit 1007
`
`Page 1 of 24
`
`

`

`
`
`U.S. Patent
`
`
`
`Jun. 30, 1998
`
`
`
`
`
`Sheet 1 of 14
`
`5,774,676
`
`
`
`
`
`
`White/ Green Book Layer
`
`
`
`MPEG System Layer
`
`r“d"*i
`
`
`
`
`Video Layer
`Audio Layer
`
`Sequence
`
`
`Group of Pictures
`
`Picture
`
`Slice
`MacroBiock
`
`
`
`
`
`1 P
`
`
`
`
`
`
`
`
`
`36
`
`
`
`FIG.
`
`Frame
`
`
`Buffer
`
`
`38:
`
`
`
`
`
`
`
`
`3
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 2
`
`Peripheral Bus -
`
`E
`
`
`
`
`
`Chip Set
`
`
`
`
`
`34
`
`
`
`Upper layer
`decompression
`
`Micro
`
`
`
`
`
`30
`
`
`
`
`
`rivate
`
`
`Memory
`
`
`
`
`
`
`
`
`
`
`
`
`
`Lower layer
`
`
`
`
`decompression
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`f
`
`
`
`E
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Page 2 of 24
`
`Page 2 of 24
`
`

`

`
`
`U.S. Patent
`
`
`
`Jun. 30, 1998
`
`
`
`
`Sheet 2 of 14
`
`5,774,676
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Peripheral Bus
`
`
`3
`
`42
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`layer
`Lower
`
`
`decompression
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`.
`
`
`
`
`
`
`
`
`
`Micro
`Processor
`
`
`
`Upper 10)/er
`
`
`decompression
`
`
`
`
`
`
`
`I
`
`
`
`
`
`
`.
`
`. n
`
`
`__ _ _ _
`
`
`
`
`
`Sound
`System
`
`
`
`. ,
`
`- -
`
`l
`
`
`
`52
`
`
`\
`
`CD—ROM
`
`
`
`Page 3 of 24
`
`Upper layer
`Lower layer
`
`
`
`
`
`
`3
`decompression
`decompression
`
`
`FIG. 4
`
` 50
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Micro
`
`
`Processor
`
`
`
`
`
`
`
`
`
`Graphics Acc.
`
`
`
`
`
`MPEG Ace.
`
`
`
`
`408
`
`ll
`l
`Peripheral Bus
`
`
`
`
`Y
`
`42
`
`
`
`Page 3 of 24
`
`

`

`
`
`U.S. Patent
`
`
`
`Jun. 30, 1998
`
`
`
`
`Sheet 3 of 14
`
`5,774,676
`
`
`
`
`
`
`
`
`
`DE
`
`
`mas
`
`
`
`
`
`
`co_m$aEo$o
`
`
`
`225:
`
`
`
`Fr25En.
`
`
`
`Nm
`
`
`
`
`
`
`
`co_mmoaEo8Q
`
`
`mace:
`
`
`
`
`
`cosoucozoim
`
`
`
`
`.382
`
`
`25
`
`eém
`
`
`
`Page 4 of 24
`
`Page 4 of 24
`
`
`
`
`
`

`

`
`
`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
`
`l
`3
`
`
`display
`
`
`IO frame
`
`-
`3
`
`.
`
`r
`
`
`display
`
`B1 frame
`1
`
`
`l
`
`
`
`
`display
`
`82 frame
`-
`
`
`
`l
`
`
`display
`
`
`P3 frame
`
`l
`
`
`
`
`decode
`decode
`decode
`
`
`
`
`
`
`IO_frame{ L P3 framefil
`I
`3. B1 fram_e_l
`
`
`
`V
`3
`l
`
`'
`
`_B.l_f
`B2
`P6
`Program
`Program
`t Program
`
`
`
`
`
`
`
`l
`decode
`decode
`
`
`
`
`l 82 frame‘ FP6 frame_{
`
`
`S
`
`fig
`Program
`
`
`
`
`
`
`decode
`
`
`B4 framey
`
`
`:
`
`if
`Program
`
`
`_
`Drsplay
`
`
`
`
`VDE
`
`E
`
`*
`
`*
`
`Host
`
`
`
`
`(Software)
`Driller
`
`
`W
`
`
`
`
`
`P‘)
`I Program
`
`
`Start
`
`Frame
`
`
`Start
`
`Frame
`
`
`Start
`
`Frame
`
`
`Start
`
`Frame
`
`
`Start
`
`Frame
`
`
`Start
`
`Frame
`
`
`1
`
`_
`Display
`
`
`
`1
`
`
`
`W5
`
`
`decode
`
`
`10 frarr_1_e_{
`
`
`
`
`I display
`
`
`10 frame
`
`-l
`
`V
`
`
`
`no display
`
`
`Bl frame
`
`
`
`display
`display
`
`
`
`
`P3 frame
`B2 frame
`
`
`y—-—~~l —-——l
`
`
`
`decode
`
`
`P3 frame_,
`
`
`
`r
`
`
`
`decode
`
`
`
`
`81 frame/
`
`
`
`decode
`
`
`
`
`
`
`decode
`
`
`B2 frame‘ F P6 frame_.
`
`
`
`
`
`decode
`
`
`B4 frome_{
`
`
`
`abandon
`
`
`
`
`frame
`
`B1
`
`Host
`
`
`/Software)
`l D’lV9F
`
`
`
`
`
`Program
`
`
`
`Program
`
`
`
`Program
`
`
`
`
`Program
`
`
`
`
`Program
`
`
`
`
`FIG. 7
`
`Page 5 of 24
`
`Page 5 of 24
`
`

`

`
`U.S. Patent
`
`
`
`
`
`
`Jun. 30, 1998
`
`
`Sheet 5 of 14
`
`5,774,676
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Muster Controller
`
`82
`
`
`
`
`FIG. 8
`
`Snwflmwwmw
`
`
`
`
`
`
`Awmmmmmm“HmuMW
`
`
`
`
`
`
`swmwwwmm
`
`
`
`
`19W%_,w..mwW
`
`
`
`
`
`
`
`36
`
`zmmwmwww
`
`
`
`
`
`48
`
`
`
`Oooafilun/_..JA.A._.D
`
`42086
`
`
`
`
`
`
`
`35
`
`Page 6 of 24
`
`
`
`
`
`emmmmwmw
`
`
`
`
`
`
`7wwmmnww
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 9
`
`Page 6 of 24
`
`
`

`

`
`
`U.S. Patent
`
`
`
`Jun. 30, 1998
`
`
`
`
`Sheet 6 of 14
`
`5,774,676
`
`
`
`/
`
`/”*’\
`ENE
`
`(B
`‘
`O
`
`l
`
`B
`1
`
`\
`
`B
`7
`
`P
`8
`
`,4’ \ / \_/ \\_4/ \ / L// \\4’ \ \/
`____,__.M._,-
`__,v..__///
`\\.M.
`,...._._..?//
`\_.._.... 4
`
`
`FIG. 10
`
`
`
`1 begin
`
`
`
`
`
`end 2
`
`
`3 begin
`
`
`
`
`end 1
`
`
`2 begin
`
`end 3
`
`
`
`
`4 begin
`
`
`
`*1
`
`-4
`
`-
`
`end 4E begin
`
`
`
`
`
`
`
`6 begin
`
`end 7
`
`7
`
`8
`
`
`W
`8
`
`
`
`9 begin
`
`
`
`G 6
`
`
`an
`7 be In
`end 9 i 10 begin
`
`
`
`97
`
`
`
`
`end 5
`
`
`
`.1
`__J
`
`end 10 .
`
`
`
`
`FIG.
`
`11
`
`
`
`tu
`
`F
`
`;
`
`Page 7 of 24
`
`Page 7 of 24
`
`

`

`
`
`U.S. Patent
`
`
`
`Jun. 30, 1998
`
`
`
`
`Sheet 7 of 14
`
`5,774,676
`
`
`
`
`DATA_|N
`
`
`
`
`
`
`
`Page 8 of 24
`
`Page 8 of 24
`
`

`

`
`
`U.S. Patent
`
`
`
`Jun. 30, 1998
`
`
`
`
`Sheet 8 of 14
`
`5,774,676
`
`
`
`
`
`FORWARD REF. FRAME
`
`
`
`
`
`BACKWARD REF. FRAME
`
`
`
`
` HORIZ. INTERP.
`
`
`
`
`
`
`HORIZ.
`
`
`
`INTERP.
`
`
`
`HBA
`
`
`
`122A
`
`
`
`
`
`
`VERRCAL INTERP.
`
`
`
`
`
` VERTICAL INTERP.
`
`
`
`
`
`POST PROC SSING
`E
`
`
`
`
`
`124
`
`
`WR_DATA
`
`
`
`
`FIG. 13A
`
`
`
`
`DATAJN
`
`
`HORIZ.
`
`INTERP.
`
`
`
`118
`
`
`
`178
`
`
`
`
`
`
`
`VERTICAL INTERP.
`
`
`
`122
`
`
`
`
`
`POST PROCESSING
`
`124
`
`
`
`mm MEMORY
`
`
`
`180
`
`
`
`
`
`WR_DATA
`
`FIG. 13B
`
`
`
`Page 9 of 24
`
`Page 9 of 24
`
`

`

`
`U.S. Patent
`
`
`
`
`
`
`Jun. 30, 1998
`
`Sheet 9 of 14
`
`
`5,774,676
`
`
`
`
`
`MPEG Driver
`
`
`
`
`VDE_|nit
`MPG_lnit
`
`
`
`
`
`
`Allocate system memory buffers.
`initialize drivers.
`
`
`
`
`
`
`
`VDE_Open
`
`
`
`Initialize painters and variables.
`
`
`
`
`
`
`MPG_Open
`
`
`
`
`Open MPEG file, prepare
`
`
`
`
`to read and parse.
`
`
`
`
`
`
`
`
`
`
`
`
`
`VDE_AddPacket
`
`
`
`
`
`
`
`
`
`
`
`
`Parse video packet data into
`Send Video packets to VDE driver.
`
`
`
`
`
`
`
`
`
`
`
`
`
`Header buffer and Picture buffer.
`Send Audio packets to ADE driver.
`
` Read MPEG file data during initialization.
`
`
`
`
`
`
`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
`
`
`
`
`
`terminate decode.
`Close MPEG file,
`
`
`VDE_Ciose
`
`
`
`Make sure VDE is stopped.
`
`
`
`
`
`
`MPG_Exit
`
`Deinitialize drivers.
`
`
`
`
`VDE_Exit
`
`
`
`Free system memory buffers.
`
`
`
`End
`
`
`
`
`FIG. 14A
`
`
`
`Page 10 of 24
`
`Page 10 of 24
`
`

`

`
`
`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.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Initialize variables for new MPEG file.
`
`
`
`
`
`Prepare to receive video packets.
`
`
`
`
`
`
`
`
`FIG. MB
`
`
`
`Page 11 of 24
`
`Page 11 of 24
`
`

`

`
`
`U.S. Patent
`
`
`
`Jun. 30, 1998
`
`
`
`
`Sheet 11 of 14
`
`5,774,676
`
`
`
`
`VDE__AddPacket
`
`
`
`Extract video PTS,
`
`
`
`if any.
`
`
`
`
`
`
`
`
`
`
`
`
`into Raw
`Copy rest of video packet
`
`
`
`
`
`to any
`buffer temporarily, appending it
`
`
`
`
`
`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.
`
`
`
`
`
`Copy into Picture 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.
`
`
`
`
`
`
`if End of Sequence found,
`
`
`
`
`mark end of video sequence.
`
`
`
`
`
`
`FIG. 140
`
`
`
`Page 12 of 24
`
`Page 12 of 24
`
`

`

`
`
`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.
`
`
`
`
`
`
`
`
`
`
`
`
`
`buffers with picture data.
`
` Fill VDE Input Ping and Pong
`
`
`
`Get from Picture buffer.
`
`
`
`
`
`
`
`
`
`Get from Header buffer.
`
`
`
`
`
`
`
`
`
`
`Program CP2 with Sequence information:
`
`
`
`
`image size, quantization matrices.
`
`
`
`
`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:
`
`
`
`
`
`
`
`Get from Header buffer.
`
`
`
`
`
`
`
`VPTS, Picture Offset, Picture Type, etc.
`
`
`
`
`
`
`
`
`FIG. 14D
`
`
`
`Page 13 of 24
`
`Page 13 of 24
`
`

`

`
`
`U.S. Patent
`
`
`
`Jun. 30, 1998
`
`
`
`
`Sheet 13 of 14
`
`5,774,676
`
`
`
`
`
`
`
`and start of decoding of picture PNH.
`
`
`
`
`
`
`indicates start
`Called when SCR=VPTS.
`
`
`
`
`
`
`
`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 buffet
`
`
`
`
`
`
`
`
`
`if next entry is Group Header, reset
`
`
`
`
`
`
`some counters to start the next group.
`
`
`
`
`
`
`Get from Header buffer.
`
`
`
`_L_.__
` Get from Header buffer.
`
`
`
`
`
`
`
`
`
`
`If next entry is Picture Header, program
`
`
`
`
`
`CP2 for next picture PN+2:
`
`
`
`
`
`VPTS, Picture Offset, Picture Type, etc.
`
`
`
`
`
`
`
`
`
`
`
`
`Send finished picture PN_1 from system
`
`
`
`
`
`
`memory buffer to 868 pixel formatter.
`
`
`
`
`
`
`
`
`
`
`FIG. 14E
`
`
`
`Page 14 of 24
`
`Page 14 of 24
`
`

`

`
`
`U.S. Patent
`
`
`
`
`Jun. 30, 1998
`
`
`Sheet 14 of 14
`
`5,774,676
`
`
`
`
`
`
`CV_lRQ Handler
`
`
`
`
`
`
`
`
`
`
`Called when CP2 detects that one of
`
`
`
`
`
`
`
`the VDE lnput Ping or Pong buffer
`
`
`
`
`has been consumed.
`
`
`
`
`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.
`
`
`
`
`
`Page 15 of 24
`
`
`FIG. 14F
`
`
`
`Page 15 of 24
`
`

`

`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 Jul. 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
`
`
`
`
`
`
`60
`
`
`
`65
`
`
`
`Page 16 of 24
`
`10
`
`
`
`15
`
`
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`5,774,676
`
`
`
`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
`
`
`
`
`
`
`frame
`including a microprocessor, graphics accelerator,
`
`
`
`
`
`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
`
`

`

`
`
`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
`
`
`
`
`
`
`
`
`
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`
`
`
`
`
`
`
`
`
`
`60
`
`65
`
`
`
`Page 17 of 24
`
`5,774,676
`
`10
`
`
`
`15
`
`
`
`
`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
`
`
`
`
`
`
`
`
`
`
`
`Page 17 of 24
`
`

`

`5,774,676
`
`5
`
`10
`
`
`
`15
`
`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
`
`
`
`
`
`
`
`
`
`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.
`
`
`
`
`
`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
`
`
`
`
`
`
`
`
`
`
`
`comput