11~ Ill~ 111111111~ 1~111~ 111111~I~111~ II
`
`US005680482A
`[HJ Patent Number:
`[45J Date of Patent:
`
`5,680,482
`Oct. 21, 1997
`
`OTHER PUBLICATIONS
`
`Dr. Richard Baker, "Standards Dominate Videoconferencing
`Implementations", Computer Design, Dec. 1994, pp. 66-70 .
`Stephen Ohr, "Digital Video Spearheads TV and Videocon(cid:173)
`ferencing Applications'', Computer Design, Dec. 1994, pp.
`59-64.
`Lawrence A. Rowe, et al., "MPEG Video in Software:
`Representation, Transmission, and Playback'', High Speed
`Networking and Multimedia Computing, Syrup. on Blee.
`Imaging Sci. & Tech., San Jose, CA, Feb., 1994, pp. 1-11.
`Peng H. Ang, et al., "Video Compression Makes Big Gains",
`IEEE Spectrum, Oct 1991, pp. 16-19.
`Andy C. Hung, et al, "A Comparison of Fast Inverse
`Discrete Cosine Transform Algorithms", Multimedia Sys(cid:173)
`tems, ©1994, pp. 204-217.
`Pl 180/D 1, "Draft Standard Specification for the Implemen(cid:173)
`tations of 8x8 Inverse Discrete Cosine Transform", May 29,
`1990,pp. 1-9.
`ISO/lEC 11172-1, "Information Technology-Coding of
`Moving Pictures and Associated Audio for Digital Storage
`Media at up to about 1,5Mbit/s"-Part1: Systems, Aug. 1,
`1993, pp. i-vi, 1-53 ..
`
`(List continued on next page.)
`
`Primary Examiner-Leo Boudreau
`Assistant Examiner-Monica S. Davis
`Attorney, Agen~ or Finn-Skjerven, Morrill, MacPherson,
`Franklin & Friel; Ken J. Koestner
`
`[57]
`
`ABSTRACT
`
`A video decompression system utilizes multiple independent
`input buffers so that input/output operations and processing
`take place concurrently, nearly continuously and at a rate
`that is substantially equal to a selected maximum access rate
`of the storage device. Consequently, the data rate of the
`video decompression system is optimized with respect to the
`rate of data accessing. The video decompression system
`adaptively sets input buffer parameters as a function, for
`example, of processor capabilities, bitstream characteristics,
`drive latency and access time, and file YO overhead.
`
`15 Claims, 7 Drawing Sheets
`
`United States Patent [19]
`Liu et al.
`
`[54] METHOD AND APPARATUS FOR
`IMPROVED VIDEO DECOMPRESSION BY
`ADAYfIVE SELECTION OF VIDEO INPUT
`. BUFFER PARAMETERS
`
`[75]
`
`Inventors: Yi Liu; Michael R. Tucker; Geoffrey
`S. Strongin, all of Austin, Tex.
`
`[73] Assignee: Advanced Micro Devices, Inc.,
`Sunnyvale, Calif.
`
`[21] Appl. No.: 443,206
`
`[22] Filed:
`
`May 17, 1995
`
`Int. CL 6
`•••••••••••••••••••••••••••••••• G06K 9130; H04N 7/12
`[51]
`[52] U.S. Cl •.......................... 382/233; 382/235; 382/232;
`348/426
`[58] Field of Search ..................................... 382/233, 236,
`382/303, 304, 235; 348/402, 426; 358/427,
`433
`
`[56]
`
`References Cited
`
`5,144,424
`5;2.27,878
`5;2.47,363
`5;2.89,577
`5,315,670
`5,347,308
`5,353,062
`5,357;2.82
`5,371,547
`5,371,611
`5,386;2.32
`5,450,599
`5,452,104
`5,481,364
`5,489,944
`5,502,493
`5,510,840
`5,523,847
`5,543,846
`5,559,557
`
`U.S. PATENT DOCUMENTS
`
`9/1992 Savatier .................................. 358/133
`7 /1993 Puri et al. ......................•........ 358/136
`9/1993 Sun et al .•••••....•.•.•....••••....••.•.. 358/167
`2/1994 Gonzales et al ...••.••...•••••...••.•• 395/163
`5/1994 Shapiro ..................................... 382/56
`9/1994 Wai ......................................... 348/394
`10/1994 Maeda ...........................•......... 348/412
`10/1994 Lee ........••.......................•........ 348/403
`12/1994 Siracusa et al. ........................ 348/426
`12/1994 Kato et al ............................... 358/456
`1/1995 Golin et al ....•.••.....••••...••••.•.... 348/396
`911995 Horvath et al .•....•.••....•••....••••• 395/800
`9/1995 Lee ................................•......... 358/433
`1/1996 Ito . ............................. .......... 3581261.1
`2/1996 Jo ............................................ 348/405
`3/1996 Meyer ..................................... 348/426
`4/1996 Yonemitsu et al .....•••....••••....•• 348/402
`6119% Feig et al .••.•.....••••....••••....••• 3581261.3
`8/1996 Yagasaki .......................•......... 348/415
`9/1996 Kato ..•..................................... 348/405
`
`-70
`
`Video
`Storage
`Device
`
`w
`0 62
`
`Input
`Butter
`
`\
`60
`
`Input
`Butter
`
`Input
`Buffer
`
`I
`64
`
`66
`
`Oerompression
`Processing
`Pathway
`
`>- 72
`
`Apple Inc. v. Parthenon
`Ex. 1008 / Page 1 of 17
`
`Petitioners HTC Corp. & HTC America, Inc. - Ex. 1008, p. 1
`
`

`
`5,680,482
`Page 2
`
`OTHER PUBLICATIONS
`
`ISO/IEC 11172-2, "Information Technology-Coding of
`Moving Pictures and Associated Audio for Digital Storage
`Media at up to about 1,5 Mbit/s"-Part 1: Video, Aug. 1,
`1993, pp. i-ix, 1-112.
`
`ISO/IEC 11172-3, "Information Technology-Coding of
`Moving Pictures and Associated Audio for Digital Storage
`Media at up to about 1,5 Mbit/s"-Part 1: Audio, Aug. 1,
`1993, pp. i-vi, 1-150.
`Kevin L. Gong, et al., "Parallel MPEG-1 Video Encoding",
`Report, University of California, Berkeley, Computer Sci(cid:173)
`ence Division, 1994, pp. 1-14.
`
`Ex. 1008 / Page 2 of 17
`
`Petitioners HTC Corp. & HTC America, Inc. - Ex. 1008, p. 2
`
`

`
`U.S. Patent
`
`Oct. 21, 1997
`
`Sheet 1of7
`
`5,680,482
`
`352 Pixels
`
`-
`-
`
`44 Blocks
`
`~
`
`I
`
`'
`
`en
`~
`(.)
`0
`cc
`0
`C")
`
`''
`
`FIG. 1
`(PRIOR ART)
`
`Ex. 1008 / Page 3 of 17
`
`Petitioners HTC Corp. & HTC America, Inc. - Ex. 1008, p. 3
`
`

`
`(12
`
`(10
`
`Input
`Buffer
`20
`
`VLC
`Inverse
`f--+. Decode ~ z/z & quant. f-+
`22
`24
`
`Inverse
`OCT
`26
`(14
`
`.
`-
`
`Previous
`Picture Store
`30
`L
`
`Memory
`33
`
`I
`
`Future
`Picture Store
`32
`
`-
`
`p
`
`Forward
`MC
`34
`
`Backward
`MC
`38
`
`FIG. 2
`
`-"'
`
`- Adder
`...
`16
`
`~ v
`
`-
`...
`
`Display
`18
`
`~ •
`00 •
`
`~ ~ a
`
`0 p.
`
`N
`""""'
`"'
`
`""""' ~
`
`~
`~
`~
`N
`~
`
`-...)
`
`Ol
`
`'9 "" QC
`
`'9
`
`Q
`~
`QC
`N.
`
`Ex. 1008 / Page 4 of 17
`
`Petitioners HTC Corp. & HTC America, Inc. - Ex. 1008, p. 4
`
`

`
`U.S. Patent
`
`Oct. 21, 1997
`
`Sheet 3 of 7
`
`5,680,482
`
`Start
`
`' '
`VLC
`Decode
`50
`
`, w
`
`Inverse Zig Zag
`52
`
`, r
`
`Inverse OCT
`54
`
`, r
`
`Motion
`Compensation
`56
`
`, Ir
`
`End
`
`FIG. 3
`
`Ex. 1008 / Page 5 of 17
`
`Petitioners HTC Corp. & HTC America, Inc. - Ex. 1008, p. 5
`
`

`
`U.S. Patent
`
`Oct. 21, 1997
`
`Sheet 4 of 7
`
`5,680,482
`
`-70
`
`Video
`Storage
`Device
`
`Input
`Buffer
`
`Input
`Buffer
`
`Input
`Buffer
`
`Input
`Buffer
`
`\
`60
`
`\
`62
`
`\
`64
`
`, r
`
`66
`
`Decompression
`Processing
`Pathway
`
`r--- 72
`
`FIG. 4
`
`Ex. 1008 / Page 6 of 17
`
`Petitioners HTC Corp. & HTC America, Inc. - Ex. 1008, p. 6
`
`

`
`100
`
`1110
`
`105
`
`(
`
`I
`I
`[]iQJ
`.. I IT!QJ PROCESSOR
`[]iQJ ,-----44--_J
`[}iQJ COPROCESSOR
`
`115
`
`145
`
`'• ...,1 MEMORY
`CONTROLLER
`
`179 \ J
`FLOPPY
`DRIVE
`
`135
`
`GRAPHICS
`CONTROLLER
`
`sc~~~us C l - -1 -1-5~--o-·· I
`
`160
`
`BUS
`INTERFACE
`CONTROLLER
`
`180
`
`DISK
`CONTROLLER
`
`DISPLAY
`
`190
`
`PARALLEL 1/0
`CONTROLLER
`
`E
`X
`P
`A B
`N U
`s s
`
`FIG. 5
`
`d • rJ.l • ;p
`~
`
`0
`?-
`N
`"""'
`"'
`"""' ~
`
`"'-I
`
`g
`"' ~
`
`~
`
`"'-I
`
`Ot
`Q\
`
`00 = 'l;.
`
`00
`N
`
`Ex. 1008 / Page 7 of 17
`
`Petitioners HTC Corp. & HTC America, Inc. - Ex. 1008, p. 7
`
`

`
`U.S. Patent
`
`Oct. 21, 1997
`
`Sheet 6 of 7
`
`r
`
`r
`
`Jl
`
`5,680,482
`20z_ (
`)
`IFS 210
`-
`-~-}-------1--------}--
`220 r-
`~
`rNETWORK
`VFAT
`CDFS
`FS
`I
`222
`224
`226
`I
`...
`'-
`••
`--- ---------------------
`, .
`. '
`I
`108 230
`
`-,
`
`I
`I
`I
`
`·I _,
`
`,
`
`,.
`
`j .
`
`1'
`
`DISK
`TYPE
`TSO
`, ,
`
`j ~
`
`VSD
`
`'~
`1~
`
`PORT
`DRIVER
`
`j .
`
`,,
`
`ADAPTER
`
`I.
`
`1
`
`~
`
`....
`
`,
`
`j
`
`VTD 240
`, .
`CD TYPE
`TSD
`242
`,,
`
`j l
`
`"
`SCSllZER
`244
`
`~
`
`••
`SCSI
`MANAGER
`246
`
`MINI PORT
`DRIVER
`248
`
`~
`
`l
`
`SCSI
`ADAPTER
`250
`
`FIG. 6
`
`, Ir
`
`T
`
`.....
`
`MAPPER
`
`MINI PORT
`DRIVER
`248
`
`.._
`
`,
`
`ADAPTER
`
`Ex. 1008 / Page 8 of 17
`
`Petitioners HTC Corp. & HTC America, Inc. - Ex. 1008, p. 8
`
`

`
`......
`
`/
`
`t
`OPTIMIZE FOR
`DRIVE LATENCY,
`ACCESS TIME, BW
`350
`
`'\
`
`~
`
`\.
`
`~
`
`/
`
`•
`
`'
`OPTIMIZE FOR
`BITSTREAM
`CHARACTERISTICS
`310
`
`~
`
`'
`
`'
`
`~
`
`'
`
`\._
`
`•
`,--··-
`ACCUMULATE
`PICTURE
`TYPE DATA
`312
`
`/
`
`\..
`
`r
`
`..
`
`CLASSIFY
`AVERAGE
`PICTURE TYPE
`314
`
`•
`CONFIGURE
`BUFFER BY
`PICTURE TYPE
`316
`
`OPTIMIZE FOR
`FILE 1/0
`OVERHEAD
`330
`
`•
`MONITOR
`FILE 1/0
`OVERHEAD
`332
`
`•
`CLASSIFY
`110 OVERHEAD
`PERFORMANCE
`334
`
`r
`
`CONFIGURE
`BUFFER BY 1/0
`PERFORMANCE
`336
`
`/
`
`\.
`
`r
`
`/
`
`'-
`
`/
`
`'-
`
`""'
`
`'
`
`)
`
`"'\
`
`/
`
`\._
`
`r
`
`/
`
`•
`
`OPTIMIZE FOR
`PROCESSING
`POWER
`370
`
`*
`EVALUATE
`PROCESSOR
`372
`
`.....
`
`~
`
`""
`
`1
`SELECT
`PROCESSOR(cid:173)
`DEPENDENT
`BUFFER PARAM
`374
`
`.......
`
`)
`
`•
`
`FIG. 7
`
`~ • 00
`
`•
`
`~ = ..... a
`
`0
`
`~ .
`
`N
`~
`"'
`~
`
`~
`
`00.
`t:r'
`('!) a
`a,
`
`~
`
`~
`
`tit °' 00 = ~
`
`00
`~
`
`'
`
`-
`
`*
`, - - - -
`MONITOR VIDEO
`STORAGE DEVICE,
`PERFORMANCE
`352
`
`*
`,--
`-...,
`CLASSIFY VIDEO
`STORAGE DEVICE,
`PERFORMANCE
`354
`
`\.
`
`~
`
`\_
`
`*
`"'
`/
`CONFIGURE BUFFER
`BY VIDEO
`STORAGE DEVICE
`PERFORMANCE 356
`
`Ex. 1008 / Page 9 of 17
`
`Petitioners HTC Corp. & HTC America, Inc. - Ex. 1008, p. 9
`
`

`
`5,680,482
`
`1
`METHOD AND APPARATUS FOR
`IMPROVED VIDEO DECOMPRESSION BY
`ADAPTIVE SELECTION OF VIDEO INPUT
`BUFFER PARAMETERS
`
`FIELD OF THE INVENTION
`
`The present invention relates to decompression of video
`information and, more particularly, to improved perfor(cid:173)
`mance of video decompression by adaptive selection of
`input buffer characteristics.
`BACKGROUND OF THE INVENTION
`
`2
`picture), forward predicted pictures (P picture) and
`bi-predicted pictures (B picture).
`An I picture is encoded as a single image having no
`reference to any past or future picture. Each block of an I
`5 picture is encoded independently. Accordingly, when decod(cid:173)
`ing an I picture, no motion processing is necessary.
`However, for the reasons discussed below, it is necessary to
`store and access I pictures for use in decoding other types of
`pictures.
`10 AP picture is encoded relative to a past reference picture.
`A reference picture is a P or I picture. The past reference
`picture is the closest preceding reference picture. Each
`macroblock in a P picture can be encoded either as an I
`Video information requires a large amount of storage
`macroblock or as a P macroblock. A P macroblock is stored
`space, therefore video information is generally compressed
`before it is stored. Accordingly, to display compressed video 15 as a translated 16xl6 area of a past reference picture plus an
`error term. To specify the location of the P macroblock, a
`information which is stored, for example, on a compact disk
`read only memory (CD ROM), the compressed video infor-
`motion vector (i.e., an indication of the relative position of
`mation is decompressed to furnish decompressed video
`the macroblock in the current picture to the position of the
`translated area in the past reference picture) is also encoded.
`information. The decompressed video information is then
`communicated in a bit stream to a display. The bit stream of 20 When decoding a P macroblock, the 16xl6 area from the
`reference picture is offset according to a motion vector. The
`video information is generally stored in a plurality of
`memory storage locations corresponding to pixel locations
`decoding function accordingly includes motion
`on a display. The stored video information is generally
`compensation, which is performed on a macroblock, in
`referred to as a bit map. The video information representing
`combination with error (IDCT) terms, which are defined on
`a single screen of information on a display is called a picture. 25 a block by block basis.
`A goal of many video systems is to quickly and efficiently
`A B picture is encoded relative to the past reference
`decode compressed video information to enable a motion
`picture and a future reference picture. The future reference
`picture is the closest proceeding reference picture.
`video capability.
`Standardization of recording media, devices and various 30 Accordingly, the decoding of a B picture is similar to that of
`aspects of data handling, such as video compression, is
`an· P picture with the exception that a B picture motion
`highly desirable for continued growth of this technology and
`vector may refer to areas in the future of the reference
`its applications. One compression standard which has
`picture. For macroblocks that use both past and future
`reference pictures, the two 16x16 areas are averaged. The
`attained wide spread use for compressing and decompress-
`ing video information is the moving pictures expert group 35 macroblocks from the reference pictures are offset according
`(MPEG) standard for video encoding and decoding. The
`to motion vectors.
`MPEG standard is defined in International Standard ISO/
`Pictures are coded using a discrete cosine transform
`IEC 11172-1, "Information Technology-Coding of moving
`(DCT) coding scheme which transforms pixels (or error
`pictures and associated audio for digital storage media at up
`terms) into a set of coefficients corresponding to amplitudes
`to about 1.5 Mbit/s'', Parts 1, 2 and 3, First edition 1993- 40 of specific cosine basis functions. The discrete cosine trans-
`08-01 which is hereby incorporated by reference in its
`form is applied to image compression to decorrelate picture
`entirety.
`data prior to quantization. The DCT coefficients are further
`Pictures within the MPEG standard are divided into
`coded using variable length coding. Variable length coding
`(VLC) is a statistical coding technique that assigns code-
`16x16 pixel macroblocks. Each macroblock includes six
`8x8 blocks: four luminance (Y) blocks, one chrominance red 45 words to values to be encoded. Values of high frequency of
`(Cr) block and one chrominance blue (Cb) block. The
`occurrence are assigned short codewords, and those of
`luminance blocks correspond to sets of 8x8 pixels on a
`infrequent occurrence are assigned long codewords. On the
`display and control the brightness of respective pixels. The
`average, the more frequent shorter codewords dominate so
`chrominance blocks to a large extent control the colors for
`that the code string is shorter than the original data.
`sets of four pixels. For each set of four pixels on the display, 50
`For a video system to provide a motion video capability,
`there is a single Cr characteristic and a single Cb charac-
`compressed video information must be quickly and effi-
`teristic.
`ciently. decoded. One aspect of the decoding process is
`For example, referring to FIG. 1, labeled prior art, a
`inverse discrete cosine transformation (IDCT). A second
`picture presented by a typical display includes 240 lines of
`aspect is a motion compensation operation. Both the IDCT
`video information in which each line has 352 pixels. 55 operation and the motion compensation operation are com-
`Accordingly, a picture includes 240x352=84,480 pixel loca-
`putationally intensive operations. Over a wide range of
`tions. Under the MPEG standard, this picture of video
`processor capabilities and image characteristics, a condition
`includes 44 by 30 luminance blocks or 1320 blocks of
`sometimes arises in which the picture decoding operation
`luminance video information. Additionally, because each
`overburdens a video system. Under this condition, video
`macroblock of information also includes two corresponding 60 frames are commonly dropped or a lag in motion video
`chrominance blocks, each picture of video information also
`results.
`includes 330 Cr blocks and 330 Cb blocks. Accordingly,
`The above described scheme using I, P, and B frames and
`each picture of video information requires 126,720 pixels or
`motion vectors is often referred to as motion compensation.
`a total of 1,013,760 bits of bit mapped storage space for
`The pixel error terms are coded via the discrete cosine
`65 transform (DCT), quantization, and variable-length coding
`presentation on a display.
`There are three types of pictures of video information
`(VLC). Performing an inverse discrete cosine transform
`function (IDCT) is one of the most computationally inten-
`which are defined by the MPEG standard, intra-pictures (I
`
`Ex. 1008 / Page 10 of 17
`
`Petitioners HTC Corp. & HTC America, Inc. - Ex. 1008, p. 10
`
`

`
`5,680,482
`
`3
`sive operations in many common video decompression
`methods and which requires extensive processor resources.
`Furthermore, such an operation must be performed to
`decode every block in the compressed video information.
`The IDCT function severely burdens the system processor 5
`when implemented in a general pmpose processor system
`since this operation requires many additions and multipli(cid:173)
`cations for each term of the 64-term block.
`Systems unable to keep up with the computational
`demands of such a decompression burden frequently drop
`entire frames to resynchronize with a real time clock signal
`also encoded in the video stream. Otherwise, video signals
`would become out of synchronization with audio signals,
`and/or the video playback would "slow down" compared to
`the "real" speed otherwise intended. This is sometimes 15
`observable as a momentary freeze of the picture in the video
`playback, followed by sudden discontinuities or jerkiness in
`the picture.
`Handling the computational demands of decompression is
`only part of the task of a video display system. In addition,
`the system must gain access to the compressed data before
`the data can be processed for decompression. Data is read
`from a video storage device, typically a CD ROM device. A
`CD ROM is a slow device having single, double and
`quadruple speeds of 150, 300 and 600 KB/s, respectively,
`which are substantially slower than the processing speed of
`the system. Generally, a computer system does not utilize its
`processing capabilities to perform input/output operations
`on a bit-by-bit basis. Instead the processor of a computer
`system initiates an input/output operation and special input/
`output circuits perform data transfer operations. However,
`data is typically read into an input buffer and data from the
`input buffer is then decompressed. Reading of data from a
`video storage device into the input buffer and processing of
`data in the input buffer cannot be performed at the same time
`if only a single buffer is used to store the data bitstream read
`from a video storage device file. When only a single input
`buffer is used, data is read into the input buffer while video
`data decoding is blocked. After all bits in the buffer have
`been read, the decoder decompresses the video data. In this
`manner, input buffer is alternately filled then utilized for
`processing. Serial reading and processing operations slow
`down overall video data decoding.
`What is needed is a video decompression system that
`reads and processes data concurrently.
`
`SUMMARY OF THE INVENTION
`In accordance with the present invention, a video decom(cid:173)
`pression system utilizes multiple independent input buffers
`so that input/output operations and processing take place
`concurrently, nearly continuously and at a rate that is sub(cid:173)
`stantially equal to a selected maximum access rate of the
`storage device. Consequently, the data rate of the video
`decompression system is optimized with respect to the rate
`of data accessing.
`In accordance with one embodiment of the present
`invention, a method of reading compressed video data from
`a video data storage device in a video processing system
`includes the steps of allocating a plurality of input data
`buffers, transferring compressed video data from the video
`data storage device to a first input data buffer of the plurality
`of input data buffers and decompressing compressed video
`data from a second input data buffer of the plurality of input
`data buffers concurrently with the data transferring step.
`In accordance with a second embodiment of the present
`invention, a method of decompressing video data using a
`
`4
`computer system includes the steps of defining a plurality of
`input data buffers and operating the computer system using
`a foreground processing and a background processing. The
`background processing includes the steps of assigning a read
`input data buffer from the plurality of input data buffers,
`reading compressed video data from a video data storage
`device into the read input data buffer and reassigning the
`read input data buffer to a process input data buffer when the
`read input data buffer is full. The foreground processing
`10 includes the step of decompressing compressed video data
`from a process input data buffer concurrently with the
`reading step.
`Other embodiments of the present invention are similar to
`the first and second embodiments and also include the steps
`of selecting a number N of input data buffers for allocation
`by the allocating step and selecting a buffer length L of input
`data buffers for allocation by the allocating step. Some of
`these embodiments include the steps of determining a mea(cid:173)
`sure of processing performance of the computer and select-
`20 ing the number N and the buffer length L of input data
`buffers which are dependent on the measure of processing
`performance. Some of these embodiments also include the
`steps of determining a measure of the character of the
`bitstream the compressed video data and selecting the num-
`25 ber N and the buffer length L of input data buffers which are
`dependent on the measure of bitstream character. Some of
`these embodiments further include the steps of determining
`a measure of latency, access time and bandwidth of the video
`data storage device and selecting the number N and the
`30 buffer length L of input data buffers which are dependent on
`the measure of latency, access time and bandwidth. Some of
`these embodiments also include the steps of determining a
`measure of file input/output overhead for accessing data
`from the video data storage device and selecting the number
`35 N and the buffer length L of input data buffers which are
`dependent on the measure of file input/output overhead.
`Usage of adaptively controlled input buffering as
`described above has several advantages. One advantage is
`that the data decompression operation becomes more effi-
`40 cient with the data accessing operation taking place concur(cid:173)
`rently with the data processing operation, thereby increasing
`the overall data handling rate of the system. Another advan(cid:173)
`tage is that decoding processing becomes substantially asyn(cid:173)
`chronous with respect to data reading so that the rates of data
`45 transfer and processing become generally independent.
`Independence of the data transfer and processing operations
`is advantageous in a system which performs tasks other than
`data handling so that data is available without delay when
`the system returns to a task utilizing data handling. It is
`50 advantageous that the processor in the video decompression
`system executes generally independently of the data transfer
`operation. When data is available for decoding, the proces(cid:173)
`sor may decode the data but may also perform other tasks
`which occasionally have a higher priority. When the pro-
`55 cessor does perform these other tasks, data continues to fill
`the input buffers so that delays due to unavailable data are
`avoided when the processor returns to the decoding task.
`The above and other objects, features, and advantages of
`the present invention will become apparent from the fol(cid:173)
`lowing detailed description and drawings.
`
`60
`
`BRIEF DESCRIPTION OF THE DRAWJNGS
`FIG. 1, labeled prior art, shows an arrangement of blocks
`65 of pixels on a display screen.
`FIG. 2 shows a block diagram of a decoder video system
`in accordance with the present invention.
`
`Ex. 1008 / Page 11 of 17
`
`Petitioners HTC Corp. & HTC America, Inc. - Ex. 1008, p. 11
`
`

`
`5,680,482
`
`5
`FIG. 3 shows a flow chart of the decoding of video
`information which is encoded using the MPEG standard.
`FIG. 4 is a block diagram which illustrates an allocation
`of input data buffers in accordance with the disclosed
`method.
`FIG. 5 is a block diagram of a computer on which the
`disclosed method can be implemented.
`FIG. 6 is a block diagram of a filesystem architecture
`within which the disclosed method can be implemented.
`FIG. 7 illustrates a flow chart of a routine for adaptively
`setting the number of buffers allocated for decoding and the
`length of the data buffers.
`
`DEfAILED DESCRIPTION
`
`Referring to FIG. 2, a system for decompressing video
`information is shown. Video system 10 includes input
`stream decoding portion 12 incorporating an inverse discrete
`cosine transformation, motion decoding portion 14, adder 16
`and display device 18. Input stream decoding portion 12
`receives a stream of compressed video information and
`provides blocks of statically decompressed video informa(cid:173)
`tion to adder 16. Motion decoding portion 14 receives
`motion information and provides motion compensation
`information to adder 16. Adder 16 receives the statically
`decompressed video information and the motion compen(cid:173)
`sation information and provides decompressed video infor(cid:173)
`mation to display 18.
`Input stream decoding portion 12 includes input buffer 20,
`variable length coding (VLC) decoder 22, inverse zig-zag
`and quantizer circuit 24 and inverse digital cosine transform
`circuit 26. Motion decoding portion 14 includes previous
`picture store circuit 30, future picture store circuit 32,
`memory 33, forward motion compensation circuit 34 and
`backward motion compensation circuit 38. Display device
`18 includes a picture buffer (not shown) which allows
`information provided by adder 16 to be rasterized prior to
`display by display device 18.
`Input stream decoding portion 12 provides statically
`decompressed video signals to adder 16 on a block-by-block
`basis. Additionally, forward motion compensation circuit 34
`and backward motion compensation circuit 38 of motion
`decoding portion 14 provide motion compensation signals to
`adder 16 on a macroblock by macroblock basis. Adder 16 45
`provides a decompressed video signal to display 18 on a
`picture by picture basis. The decompressed video signal is
`also provided as a previous picture signal to previous picture
`store circuit 30 and future picture store circuit 32 (in the case
`of an I or P picture).
`Referring to FIGS. 2 and 3, in operation, input buffer 20
`receives a compressed video signal in the form of a bitstream
`from a video signal source such as a CD ROM (not shown);
`the compressed video signal is provided as a stream of
`compressed video information. Input buffer 20 buffers this 55
`compressed video signal to compensate for variations in the
`speed which the signal is provided by the video source.
`Multiple input buffers 20 are allocated in the video system
`10 so that video bitstream data is read from the video signal
`source into one buffer while another buffer is used to process 60
`the compressed video signal bitstream. Referring to FIG. 4,
`an example of an allocation of video input buffers is shown
`which includes four allocated input buffers 60, 62, 64 and
`66. Under one typical condition, the input buffer 60 is
`currently filled from a video storage device 70 while video 65
`bitstream data in input buffer 64 is processed by a decom(cid:173)
`pression processing pathway 72. In this example, the video
`
`6
`storage device 70 transfers data to the input buffers in the
`order of buffers 60, 62, 64, 66 and recycling to buffer 60 and
`the decompression processing pathway 72 also processes
`video bitstream data in the order of input buffers 60, 62, 64,
`5 66 and recycling to buffer 60. In this example, transferring
`data to the input buffers is one buffer ahead of the processing
`of input data with input buffer 62 being filled and awaiting
`processing and input buffer 66 being processed and awaiting
`filling. The number of input buffers under various conditions
`10 and circumstances is greater or lesser than the four buffers
`shown in this example. The minimum number of input
`buffers is two. The number of input buffers and the length of
`the buffers is set adaptively as a function, for example, of
`processor capabilities, available system memory, bitstream
`15 characteristics, drive latency and access time, and file J/O
`overhead.
`Referring again to FIGS. 2 and 3, the input bitstream is
`accumulated in the input buffer 20 until the bitstream data is
`to be utilized. This buffered compressed video signal is
`20 provided to VLC decoder 22 which decodes the variable
`length coded portion of the compressed signal at VLC
`decoding step 50 to provided a variable length decoded
`signal.
`The variable length decoded signal is provided to inverse
`25 zig-zag and quantizer circuit 24 which, at inverse zig-zag
`and quantization step 52, decodes the variable length coded
`signal to provide a zig-zag decoded signal. Inverse zig-zag
`and quantizer circuit 24 produces actual DCT coefficients
`using a preset quantization step size. When a signal is
`30 encoded, data is run-length encoded in zig-zag ordering
`across an image so that compression is optimized. In
`general, most of the energy in an image is concentrated at the
`low frequency coefficients, which are conventionally written
`in the upper left comer of the transformed matrix, Therefore,
`35 image data which has been converted to a frequency repre(cid:173)
`sentation typically has larger coefficients at lower spatial
`frequencies, clustered at the upper left corner of a frequency
`image block. Coefficients typically decrease along rays
`extending from the zero-frequency, or DC, term to higher
`40 spatial frequency terms. A block of data is compressed by
`discrete cosine transform (DCT) coefficient quantization.
`Most of the information in a block is contained in the lower
`frequency coefficients. Quantization serves to remove small
`coefficients-coefficients that are smaller than a quantiza(cid:173)
`tion step. Higher frequency coefficients have a larger quan(cid:173)
`tization step. Zig-zag ordering is used to reorder the quan-
`tized discrete cosine transform (DCT) block of coefficients
`so that non-zero coefficients are transmitted first, thereby
`increasing transmission efficiency. The inverse zig-zag and
`50 quantization step 52 compensates for the fact that, while a
`compressed video signal is compressed in a zig-zag run
`length code fashion, the zig-zag decoded signal is provided
`to inverse DCT circuit 26 as sequential blocks of video
`information. Accordingly, this zig-zag decoded signal pro(cid:173)
`vides blocks which are in a suitable order for raster scanning
`across display 18.
`When a signal is encoded, an image block is first trans-
`formed from the spatial domain to the frequency domain
`using the Discrete Cosine Transform (DCT), which sepa(cid:173)
`rates the signal into independent frequency bands. Most of
`the frequency information is in the upper left comer of the
`resulting block. The zig-zag decoded signal is applied to
`inverse DCT circuit 26 to convert the frequency domain
`image into the spatial domain. The inverse DCT circuit 26,
`at inverse DCT step 54, performs an inverse digital cosine
`transform on the zig-zag decoded video signal on a block-
`by-block basis to provide a decompressed video signal. This
`
`Ex. 1008 / Page 12 of 17
`
`Petitioners HTC Corp. & HTC America, Inc. - Ex. 1008, p. 12
`
`

`
`5,680,482
`
`7
`decompressed video signal corresponds to either error tenns
`for P or B-coded macroblocks or pixels for I-coded mac(cid:173)
`roblocks.
`The decompressed signal is provided to adder 16 which,
`if the signal does not include any motion information (i.e., 5
`I pictures) provides this signal to display 18. However, for
`video signals which include motion information (i.e., B
`pictures and P pictures), adder 16 uses the forward motion
`compensation and backward motion compensation outputs
`from motion decode portion 19 to generate the video infor- 10
`mation which is provided to display 18 at motion compen(cid:173)
`sation step 56. More specifically, forward motion vectors are
`used to locate information in previous picture store circuit
`30 and backward motion vectors are used to locate infor(cid:173)
`mation in future picture store circuit 32 and this information
`is added to the output provided by inverse DCT circuit 26. 15
`VLC decoder 22 decodes a sequence of pictures in the
`following manner. VLC decoder 22 first decodes the header
`of a first picture, called picture 0, and determines that it is an
`I-picture. VLC decoder 22 produces quantized coefficients
`corresponding to the quantized DCT coefficients. These are 20
`assembled for each 8 by 8 block of pixels in the image by
`inverse zig-zag scanning. VLC decoder 22 decodes the
`header of the next picture, picture 3, and determines that it
`is a P-picture. For each inter-coded macroblock, the VLC
`decoder 22