I|||||||||||ll|||||||||||||||||l|||||||||||||||||||||||||||||||||||||||||||
`
`US[J(]6?-7019331
`
`(12) United States Patent
`Lee
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 6,370,193 B1
`Apr. 9, 2002
`
`(54) Ml’l<Z(} DATA C()MI’RESSI()N AN!)
`DECOMPRESSION USING ADJACENT DATA
`VALUE DIFFERENCING
`
`5,973,742 A "‘
`(i,tlB__205 A "
`6,028,635 A "
`6,038,345 A "‘
`
`l[I,tl999 Gardyne et al.
`
`2;’2itU(J
`l’au
`2,I'2UU(l Owen et al.
`.
`
`3;"2ltUlJ Osava ct al.
`
`348.5416
`34874-(J5
`34874-{J3
`382232
`
`(75)
`
`Inventor: Yong-Wnon Lee, Kyungki-do (KR)
`
`‘ cited by examiner
`
`Pririiarjv I:'xnminer—Chris Kelley
`Ass'.r‘st‘artI Exnn:im2r—Tung V0
`(74) Attorriey, Agurtt, or Firm—Myers Bigel Sibley &
`Sajovec
`(57)
`
`ABSTRACT
`
`MPEU data is compressed by obtaining dil;Terent:e values
`between succeeding adjacent data values of MPEG video
`data and store the difference value if the dillerenee value is
`
`less than a predetermined range. By storing the difference
`values rather than the data values it‘ the ditference value is
`less than a predetermined range, compression may be pro-
`vided for MPEG data. More specifically, a series of data
`values of MPEG video data is separated from an MPEG
`hitstream. Difference values are obtained between succeed-
`ing adjacent data values of the MPEG video data. For each
`data value, the data value is stored II‘ the ditference exceeds
`a predetermined range, anti the dilIerence value is stored if
`the difference value is less than the predetermined range. A
`conversion [lag is also stored for each data value, to indicate
`whether the data value or the difference value is stored. After
`the data value or difference value is stored for each data
`value, a determination is made if the data values and
`dilTerent.'e values that were stored exceed a predetermined
`sin.-. Each data value is divided by 2. and the divided data
`values are stored if the data values and difference values that
`were stored exceed the predetermined size. On the other
`hand,
`it‘ the data values and dilIerenee values that were
`stored are less than the predetermined size, dummy bits may
`be added to the data, so that the data that was stored equals
`the predetermined size. A mode flag maybe used to indicate
`whether difference values or divided values are stored.
`
`49 Claims, .10 l)ru\-ving Sheets
`
`20
`
`(73) Assignce: Salttsung Isllectrnnies C0., Ltd. {KR}
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent
`is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) App}. No.: 09,r’03l,212
`
`(2.,
`
`Filed:
`
`Feb. 26, 1998
`
`(30)
`
`Foreign Application Priority Data
`
`Feb. 26, I997
`
`(KR)
`
`97-5916
`
`H043 use
`Int. C1.‘
`(51)
`375724045
`(52) U.S.C].
`34s;3s4.1, 390.1,
`(53) Field or Search
`34sr342.1, 401, 402.1—405.1, 405.1, 416.1.
`420.1, 423.1, 420.1; 3647578; 3827232;
`3757240, 240.01, 240.02, 240.03, 240.09,
`240.1, 240.11, 240.12, 340.13, 240:4;
`I-I048 1,366
`
`(56)
`
`References Cited
`U.S. I-"Al'l:]N'I' DOCUMl_-INTS
`
`6,-“I993 Honjt)
`523,949 A "'
`2,-‘I998 Mnhini
`5,715,176 A *
`3,-‘I998 Keesman
`5.729.293 A “
`471998 Kandltlr ct al.
`5.7«-’t2_.3-’-l7 A *
`ll;"l998 Slrcatcr
`5,831,677 A "
`Ilr'l9‘J8 Park
`3,832,il37 A *
`3.338.597 A * 1171998 Pat: et al.
`5,844,608 A "‘ 1271998 Yt: et al.
`5,847,762 A " 1231998 Candlield et al.
`5,959,690 A "
`971999 Toebes, VIII et al.
`
`..
`
`
`
`358.3426
`36¢-l,t'5l4 R
`348r'4f]1
`343.-"-’-$26
`.3-487415
`37'5.s’24'l.l
`.. 304.-'7l5.U2
`343.-"390
`343.3415
`348.3576
`
`
`MPEG
`BIT STREAM ':"' B” 5“‘E’”“
`DECODER
`
`
`ltlI-‘E13
`
` “PEG VIDEO
`
`RESWRER
`
`COMPRESSOR
`PAD RESTDRER
`
`llEll0RY
`
`MA.-‘l!tGElIlENT
`
`PROCESSOR
`
`
`
`
`TO TV
`
`
`
`V l DEO
`0U'l‘PL'T
`PROCFSSOR
`
`
`28
`
`0001
`0001
`
`Apple/Twitter
`Apple/Twitter
`Ex. 1022
`Ex. 1022
`IPR1 of U.S. Pat. No. 7,765,482
`IPR1 of U.S. Pat. No. 7,765,482
`
`

`
`U.S. Patent
`
`Apr. 9, 2002
`
`Sheet 1 0f 10
`
`US 6,370,193 B1
`
`PIG.l(Pri0r Art)
`
`10
`
`MPEG ——> B I TMISTREAM
`B I T STREAM
`DECODER
`
`16
`I"
`
`12
`1"
`
`\
`
`14
`/~/
`
`MPEG VIDEO _ _ m?ggggm :
`RESTORER
`PROCESSOR
`
`M
`
`MEMORY
`
`I
`
`V I DEO
`OUTPUT —-——> TO TV
`PROCESSOR
`»,
`18
`
`PIG.2
`
`MPEG
`MPEG
`BIT STREAM _—’ BIDEC%%%%AM
`
`26
`
`22
`
`24
`
`MPEG V I DEO
`RESTORER
`
`MEMORY
`MANAGEMENT
`> COMPRESSOR 4 : PROCESSOR
`AND RESTORER
`x,
`30
`
`VIDEO
`OUTPUT —» TO TV
`PROCESSOR
`
`V
`
`MEMORY
`
`0002
`
`

`
`U.S. Patent
`
`Apr. 9, 2002
`
`Sheet 2 0f 10
`
`US 6,370,193 B1
`
`FIG.3A
`
`I
`
`START
`
`I
`
`I
`STORE Dn,Dn—l, ,D2,D1 IN REGISTER R1
`
`100
`
`STORE LEADING DATA Dn IN REGISTER R2
`
`OBTAIN DIFFERENCE VALUES(An-l)
`BETWEEN ADJACENT DATA
`
`104
`
`STORE(An—1)IN REGISTER R2
`AND STORE "O" IN Xn-l
`
`I
`
`DECREASE n BY "1"
`
`STORE “1" IN X0
`
`116
`
`110
`r’
`I
`STORE DATA(Dn-1) IN REGISTER R2
`AND STORE "1'' IN Xn—1
`
`0003
`
`

`
`U.S. Patent
`
`Apr. 9, 2002
`
`Sheet 3 0f 10
`
`US 6,370,193 B1
`
`FIG.3B
`
`IS THE NUMBER OF
`BITS OF DATA S'IURED IN REGISTER
`R2 SMALLER THAN
`(m Xn)-n ?
`
`122
`‘~'\
`
`I
`
`MAKE 110; NUMBER OF BITS
`INTO (mXrO-n BY ADDING
`DUMMY BIT IN REGISTERRZ
`
`IS THE NUMBER OF
`BITS OF DATA STORED IN
`REGISTERRZ EQUAL T0
`(m Xn)—n ‘?
`
`Y
`
`OUTPUT DATA STORED IN
`REGISTERRZ AS A UNIT
`
`‘
`
`124
`/\/
`
`RESPHITIVEILY DIVIDE DATA
`STORED IN REGISTERRI BY 2 AND
`STORE DIVIDED DATA IN REGISTERRZ
`
`15 THE VALUE
`SmRED IN X0 "1.. 7
`
`REPLACE THE VALUE STORED IN
`X0 WITH "0"
`
`0004
`
`

`
`U.S. Patent
`
`Apr. 9, 2002
`
`Sheet 4 0f 10
`
`US 6,370,193 B1
`
`FIG.4A
`
`R1—
`m bits
`
`m><n bits
`
`R2_
`
`m bits
`
`m bits glbits
`
`(m><n‘)-n bits
`
`1
`
`X =
`
`1 bit
`
`n bits
`
`FIG.4B
`
`R1_
`
`
`
`(m-1) bitsi
`
`(m><n)-n bits
`
`1
`
`0005
`
`0005
`
`

`
`U.S. Patent
`
`Apr. 9, 2002
`
`Sheet 5 0f 10
`
`US 6,370,193 B1
`
`FIG.5
`
`START
`
`I
`READ OUT COMPRESSEDDATA FROM
`MEMORY AS A UNIT AND STORE w 200
`READ OUT DATA IN REGISTERRZ
`
`sIDRE LEADING DATA Dn
`IN REGISTER R1
`
`\1‘ 202
`
`204
`
`LSB X0 OF
`COMPRESSED DATA
`= "1" ?
`
`210
`\.\
`
`Y E
`
`REsIDRE DATA ID m—BIT DATA BY
`ADDING DIFFERENCE VALUES 'IO
`RESTORED DATA BASED ON LEADING
`DATA AND STORE RESTORED
`DATA IN REGISTER R1
`
`I
`
`214
`
`VALUE OF
`
`N
`
`216
`
`Y i
`
`OUTPUT VALUE STORED IN
`REGISTER R1
`
`END
`
`206
`/"
`I
`INSERT "0“ 0R “1" IN
`EACH LSB OF RESPECTIVE
`(m-1)-BITDATA AND STORE
`ORIGINAL m-BIT DATA
`IN REGISTER R1
`
`212
`
`I
`"\
`sIDRE m~EIT DATA IN
`REGISTERRI AS IT IS
`
`0006
`
`

`
`U.S. Patent
`
`Apr. 9, 2002
`
`Sheet 6 0f 10
`
`US 6,370,193 B1
`
`EIG.6A
`
`START
`
`I
`STORE 8 DATA OF 8 BITS IN
`REGISTERRl
`
`I
`STORE LEADING DATA D8
`IN REGISTERRZ
`
`0 300
`
`w 302
`
`I
`OBTAIN DIFFERENCE VALUES ( An-l)
`BETWEEN ADJACENT DATA
`
`w 304
`
`STORE DIFFERENCEVALUES
`(An-1) IN REGISTER AND STORE
`"O" IN Xn-1
`
`V
`
`DECREASEn BY "1"
`
`314
`
`310
`/‘I
`
`I
`STORE 8-BIT DATA (Dn-l)
`IN REGISTERRZ AND
`STORE "1" IN Xn-l
`
`N o
`
`Y
`
`STORE "1" IN X0
`
`w 316
`
`0007
`
`

`
`U.S. Patent
`
`Apr. 9, 2002
`
`Sheet 7 0f 10
`
`US 6,370,193 B1
`
`FIG.6B
`
`IS THE NUMBER OF
`BITS OF DATA STORED IN REGISTER
`R2 SMALLER THAN
`56 BITS ?
`
`322
`\'\
`MAKE THE NUMBER OF BITS
`INTO 56 BITS BY ADDING
`DUMMY BIT IN REGISTERRZ
`
`IS THE NUMBER OF
`BITS OF DATA STORED IN
`REGISTERRZ EQUAL
`TO 56 ?
`Y
`
`I
`OUTPUT DATA STORED IN
`REGISTERRZ AS A UNIT
`
`END
`
`324
`,4
`RESJECIIVHX DIVIDE DATA
`STORED IN REGISTERRl BY 2 AND
`STORE DIVIDED DATA IN REGISTERRZ
`
`IS THE VALUE
`STORED IN X0 "1" ?
`
`328
`
`REPLACE THE VALUE STORED IN
`X0 WITH "0"
`
`0008
`
`

`
`U.S. Patent
`
`Apr. 9, 2002
`
`Sheet 8 0f 10
`
`US 6,370,193 B1
`
`FIG.7A
`
`64 bits
`
`125
`
`120
`
`124
`
`130
`
`135
`
`133
`
`140
`
`‘
`
`Sbits
`~—>1
`128
`
`R1
`
`‘
`
`Sbits
`
`4bit3
`
`56 bits
`
`_
`
`R2
`
`128
`
`3
`
`5
`
`—4
`
`-6
`
`—5
`
`2
`
`-7
`
`‘
`
`lbit
`
`Sbits
`
`‘
`
`X
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`0
`
`1
`
`l
`8bits
`‘—>i
`128
`
`R1
`
`64 bits
`
`125
`
`200
`
`217
`
`210
`
`208
`
`212
`
`140
`
`8bits
`
`11bit?
`
`56 bits
`
`R2
`
`128
`
`3
`
`200
`
`217
`
`7
`
`2
`
`-4
`
`140
`
`‘
`
`_
`
`Sbits
`
`0009
`
`

`
`U.S. Patent
`
`Apr. 9, 2002
`
`Sheet 9 0f 10
`
`US 6,370,193 B1
`
`I
`
`?bits ‘
`
`64 bits
`
`R1
`
`128
`
`125
`
`200
`
`217
`
`210
`
`208
`
`100
`
`242
`
`8bits ‘40m
`
`I
`
`Rz-l
`
`12a
`
`3
`
`200
`
`217
`
`7
`
`2
`
`100
`
`242
`
`“1:55,?”
`
`60 bits
`
`_
`
`7bits
`
`56 bits
`
`R2
`
`64
`
`62
`
`100
`
`10B
`
`105
`
`104
`
`50
`
`120
`
`7 bits
`
`I
`
`i
`11ml
`
`0010
`
`

`
`U.S. Patent
`
`Apr. 9, 2002
`
`Sheet 10 0f 10
`
`US 6,370,193
`
`FIG.8
`
`START
`
`I
`
`READ OUT COMPRESSEDDATA
`FROM MEMORY AS A WORD UNIT
`AND STORE READOUT DATA w 400
`IN REGISTERRZ
`
`I
`STORE LEADING DATA 08
`IN REGISTER R1
`
`d‘ 402
`
`404
`
`Y
`
`410
`[\I
`
`RESTORE DATA TO 8-BIT DATA
`BY ADDING DIFFERENCEVALUES 'IO
`RESTORED DATA BASED ON
`LEADING DATA AND STORE RESTORED
`DATA IN REGISTER R1
`
`I
`
`414
`
`VALUE OF
`n-1 = "1" ?
`
`N
`
`416
`
`Y A
`
`OUTPUT VALUE STORED IN
`REGISTER R1
`
`END
`
`f“
`I
`INSERT "0" 0R "1" IN
`EACH [.55 OF RESPECTIVE
`7-BIT DATA AND STORE
`m-BIT RESTORED DATA
`IN REGISTERRI
`
`412
`I
`"\
`STORE 8-BIT DATA IN
`REGISTERRI AS IT IS
`
`0011
`
`

`
`US 6,370,193 B1
`
`1
`MPEG DATA COMPRESSION AND
`DECOMPRESSION USING ADJACENT DATA
`VALUE DIFFERENCING
`
`FIELD OF THE INVENTION
`
`This invention relates to MPEG multimedia data, and
`more preferably to compression and decompression of
`MPEG data.
`
`BACKGROUND OF THE INVENTION
`
`Multimedia data including audio, still video and motion
`video data is being Widely used in video games, internet
`related applications and other data processing related appli
`cations. As is Well knoWn to those having skill in the art,
`multimedia applications often require large quantities of
`video and audio data. In order to store and process large
`quantities of data, international standards for coding audio
`and video data have been prepared by the Moving Picture
`Expert Group (MPEG). Examples of MPEG standards are
`MPEG-1 and MPEG-2 standards. MPEG standards are
`Widely used With multimedia data and need not be described
`further herein.
`MPEG-1 or MPEG-2 standard data that has been com
`pressed may be restored or decompressed using an MPEG-1
`or MPEG-2 decoder. More speci?cally, MPEG data may
`include intra picture data, predictive picture data and bidi
`rectionally predictive picture data. Moreover, each picture
`generally includes a luminance signal and a chrominance
`signal. Accordingly, notWithstanding the existence of MPEG
`compression and decompression, large siZe memories may
`still be needed to store multimedia data.
`In one speci?c example, if the number of horiZontal pixels
`are 720 and 480 respectively, the numerical value for
`discrimination betWeen black/White and color signal is 2,
`and the number of bits per pixel is 8, in order to store all of
`the intra picture, predictive picture and bidirectionally pre
`dictive picture data, the total amount of data to be stored may
`become 720x480><3><8><2 or 15.2 Mbits. Accordingly, 15.2
`Mbits of data may need to be stored in a memory to process
`the three pictures.
`FIG. 1 is a block diagram of a conventional MPEG system
`decoder. Referring to FIG. 1, a conventional MPEG system
`decoder includes an MPEG bitstream decoder 10, a memory
`management processor 12, a memory 14, an MPEG video
`restorer 16 (decompressor), and a video output processor 18.
`The video output processor 18 provides video data to a
`display, such as a TV. It Will be understood that the block
`diagram of FIG. 1 illustrates only blocks for processing
`video data.
`The MPEG bitstream decoder 10 receives an MPEG
`bitstream and separates the bitstream into video data, audio
`data, and system data. The memory 14 stores therein com
`pressed video and audio data, and restored video and audio
`data. The MPEG video restorer 16 restores the compressed
`video data output from the memory 14 and provides the
`restored video data to the memory 14. The memory man
`agement processor 12 controls the generation of addresses
`for storing or reading data in/out of the memory 14. The
`video output processor 18 outputs the restored video data
`from the memory 14 to a video display.
`A data processing method performed by a conventional
`MPEG system decoder of FIG. 1 Will noW be described.
`Speci?cally, the memory management processor 12 stores
`the MPEG-compressed video data separated by and output
`from the MPEG bitstream decoder 10 in a compressed video
`
`10
`
`15
`
`25
`
`35
`
`45
`
`55
`
`65
`
`2
`data storage region of the memory 14. The memory man
`agement processor 12 then outputs the MPEG-compressed
`video data stored in the memory 14 to the MPEG video
`restorer 16. The MPEG video restorer 16 restores the
`MPEG-compressed video data. The memory management
`processor 12 stores the video data restored by the MPEG
`video restorer 16 in a restored video data storage region of
`the memory 14. The memory management processor 12
`outputs the restored data stored in the memory 14 to the
`video output processor 18.
`As described above, according to a conventional data
`processing method performed by a conventional MPEG
`system decoder, the video data restored by the MPEG video
`restorer 16 is stored in the memory 14 as is. Unfortunately,
`the storing of video data in the memory 14 may require an
`excessive amount of storage capacity. The large storage
`capacity may increase the cost and/or decrease the perfor
`mance of the system that processes MPEG data.
`
`SUMMARY OF THE INVENTION
`
`It is therefore an object of the present invention to provide
`improved storage of MPEG data.
`It is another object of the invention to provide compres
`sion of MPEG data to alloW reduction in the storage space
`that need be used by the data.
`These and other objects are provided, according to the
`present invention, by methods, systems or apparatus and
`computer program products that compress MPEG data by
`obtaining difference values betWeen succeeding adjacent
`data values of MPEG video data and store the difference
`value if the difference value is less than a predetermined
`range. By storing the difference values rather than the data
`values if the difference value is less than a predetermined
`range, compression may be provided for MPEG data.
`More speci?cally, according to the present invention, a
`series of data values of MPEG video data is separated from
`an MPEG bitstream. Difference values are obtained betWeen
`succeeding adjacent data values of the MPEG video data.
`For each data value, the data value is stored if the difference
`exceeds a predetermined range, and the difference value is
`stored if the difference value is less than the predetermined
`range. A conversion ?ag is also stored for each data value,
`to indicate Whether the data value or the difference value is
`stored. As an example, the predetermined range may be
`betWeen —9 and 8.
`According to another aspect of the present invention, after
`the data value or difference value is stored for each data
`value, a determination is made if the data values and
`difference values that Were stored exceed a predetermined
`siZe. Each data value is divided by 2, and the divided data
`values are stored if the data values and difference values that
`Were stored exceed the predetermined siZe. On the other
`hand, if the data values and difference values that Were
`stored are less than the predetermined siZe, dummy bits may
`be added to the data, so that the data that Was stored equals
`the predetermined siZe. A mode ?ag may be used to indicate
`Whether difference values or divided values are stored.
`Accordingly, MPEG data may be compressed by separat
`ing a series of n data values of m bits each of MPEG video
`data from an MPEG bitstream to obtain m><n bits of MPEG
`video data. The m><n bits of MPEG video data are com
`pressed into (m><n)—n bits using adjacent value differencing
`and data value dividing. The (m><n)—n bits of compressed
`MPEG video data is stored.
`Preferably, the (m><n)—n bits of compressed MPEG video
`data include n 1-bit conversion ?ags to indicate Whether the
`
`0012
`
`

`
`US 6,370,193 B1
`
`3
`data value or the difference value is stored for each of the n
`data values. A plurality of dummy bits are also preferably
`included, if needed, to increase the siZe of the compressed
`video data to (m><n)—n bits. Finally, the (m><n)—n bits of
`compressed MPEG video data also preferably include a 1-bit
`mode ?ag, to indicate Whether difference values or divided
`values are stored.
`The compressed MPEG data may be decompressed or
`restored by adding a compressed data value to an immedi
`ately preceding decompressed data value to obtain an asso
`ciated decompressed data value if the conversion ?ag that is
`associated With the data value indicates that the difference is
`stored. Adjacent data value adding is preferably performed
`only if the mode ?ag has a ?rst value to indicate that
`differencing Was used in compression. If the mode ?ag has
`a second value, indicating that dividing Was used to
`compress, then each compressed data value is multiplied by
`2 to decompress the data.
`Accordingly, (m><n)—n bits of compressed MPEG video
`data are decompressed into a series of n data values of m bits
`each of decompressed MPEG video data using adjacent data
`value adding and data value multiplying. The (m><n)—n bits
`of compressed MPEG video data include n 1-bit conversion
`?ags to indicate Whether the data value or adjacent data
`value adding is used to decompress each of the n data values.
`The (m><n)—n bits of compressed MPEG video data also
`preferably include a plurality of dummy bits that increase
`the siZe of the compressed MPEG video data to (m><n)—n
`bits, if needed. A 1-bit mode ?ag is also preferably included
`to indicate Whether difference values or divided values are
`stored.
`Accordingly, the storage capacity of a memory that stores
`MPEG video data may be reduced by compressing the
`restored data using differencing and division and then
`decompressing the stored data as needed. As Will be appre
`ciated by those of skill in the art, the present invention may
`be embodied as methods, apparatus (systems) and/or com
`puter program products.
`
`10
`
`15
`
`35
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a block diagram of a conventional MPEG system
`decoder.
`FIG. 2 is a block diagram of an MPEG system decoder
`according to the present invention.
`FIGS. 3A and 3B are a ?oWchart of video data compres
`sion according to the present invention.
`FIGS. 4A and 4B are vieWs explaining video data com
`pression utiliZing difference values and division of FIGS. 3A
`and 3B.
`FIG. 5 is a ?oWchart explaining video data restoring
`according to the present invention.
`FIGS. 6A and 6B are a ?oWchart explaining data com
`pression according to an embodiment of the present inven
`tion.
`FIGS. 7A to 7D are vieWs explaining data compression
`utiliZing data compression of FIGS. 6A and 6B.
`FIG. 8 is a ?oWchart explaining video data restoring
`according to the present invention.
`
`45
`
`55
`
`DETAILED DESCRIPTION OF PREFERRED
`EMBODIMENTS
`
`The present invention noW Will be described more fully
`hereinafter With reference to the accompanying draWings, in
`Which preferred embodiments of the invention are shown.
`
`65
`
`4
`This invention may, hoWever, be embodied in many different
`forms and should not be construed as limited to the embodi
`ments set forth herein; rather, these embodiments are pro
`vided so that this disclosure Will be thorough and complete,
`and Will fully convey the scope of the invention to those
`skilled in the art. Like numbers refer to like elements
`throughout.
`As Will also be appreciated by one of skill in the art, the
`present invention may be embodied as methods, MPEG
`compression/decompression systems (apparatus), or com
`puter program products. Accordingly, the present invention
`may take the form of an entirely hardWare embodiment, an
`entirely softWare embodiment or an embodiment combining
`softWare and hardWare aspects. Furthermore, the present
`invention may take the form of a computer program product
`on a computer-readable storage medium having computer
`readable program code means embodied in the medium. Any
`suitable computer readable medium may be utiliZed includ
`ing hard disks, CD-ROMs, optical storage devices, or mag
`netic storage devices.
`FIG. 2 is a block diagram illustrating an MPEG system
`decoder according to the present invention. Referring to
`FIG. 2, a system decoder according to the present invention
`includes an MPEG bitstream decoder 20, a memory man
`agement processor 22, a memory 24, an MPEG video
`restorer 26, a video output processor 28, and a compressor
`and restorer 30.
`The memory management processor 22 stores the MPEG
`compressed video data separated by the MPEG bitstream
`decoder 20 in the memory 24. The memory management
`processor 22 then outputs the compressed video data stored
`in the memory 24 to the MPEG video restorer 26. The
`MPEG video restorer 26 restores (decompresses) the com
`pressed video data and outputs the restored video data to the
`compressor and restorer 30. The compressor and restorer 30
`compresses the restored video data by adjacent data value
`differencing or division, and outputs the compressed video
`data to the memory management processor 22. The memory
`management processor 22 stores the video data output from
`the compressor and restorer 30 in a restored data storage
`region of the memory 24. The memory management pro
`cessor 22 outputs the video data stored in the restored data
`storage region of the memory 24 to the compressor and
`restorer 30. The compressor and restorer 30 restores
`(decompresses) the video data from the memory 24, and
`outputs the restored video data to the video output processor
`28. The video output processor 28 outputs the restored video
`data to a display such as a television.
`Operations for various aspects of one embodiment of the
`present invention are illustrated in detail in FIGS. 3A, 3B, 5,
`6A, 6B and 8 Which are ?oWchart illustrations. It Will be
`understood that each block of the ?oWchart illustrations, and
`combinations of blocks in the ?oWchart illustrations, can be
`implemented by computer program instructions. These com
`puter program instructions may be provided to a processor
`or other programmable data processing apparatus to produce
`a machine, such that the instructions Which execute on the
`processor or other programmable data processing apparatus
`create means for implementing the functions speci?ed in the
`?oWchart block or blocks. These computer program instruc
`tions may also be stored in a computer-readable memory that
`can direct a processor or other programmable data process
`ing apparatus to function in a particular manner, such that
`the instructions stored in the computer-readable memory
`produce an article of manufacture including instruction
`means Which implement the functions speci?ed in the ?oW
`chart block or blocks.
`
`0013
`
`

`
`US 6,370,193 B1
`
`5
`Accordingly, blocks of the ?owchart illustrations support
`combinations of means for performing the speci?ed
`functions, combinations of steps for performing the speci
`?ed functions and program instruction means for performing
`the speci?ed functions. It Will also be understood that each
`block of the ?oWchart illustrations, and combinations of
`blocks in the ?oWchart illustrations, can be implemented by
`special purpose hardWare-based computer systems Which
`perform the speci?ed functions or steps such as Was
`described in FIG. 2, or by combinations of special purpose
`hardWare and computer instructions.
`FIGS. 3A and 3B are a ?oWchart explaining video data
`compression that can be performed by the compressor and
`restorer in FIG. 2. FIG. 4A is a vieW explaining video data
`compression of FIGS. 3A and 3B When the compressed data
`is less than (m><n)—n bits, and FIG. 4B is a vieW explaining
`video data compression When the compressed data exceeds
`(m><n)—n bits.
`. D2, D1 output
`.
`The n data values of m bits Dn, Dn_1 .
`from the MPEG video restorer 26 are stored in a register R1
`(Block 100). The register R1 can store therein m><n-bit data.
`The data Dn stored in the register R1 is then stored in a
`register R2 as shoWn in FIG. 4A (Block 102). The register
`R2 can store therein (m><n)—n-bit data. Thereafter, a data
`difference value An_1 is obtained by subtracting adjacent
`data Dn_1 from leading data Dn based on the leading data D”
`of the restored data (Block 104). The adjacent data differ
`encing (subtracting) operation is also referred to herein as
`Differential Pulse-Code Modulation (DPCM).
`Next, it is determined Whether the data difference value is
`Within a predetermined range, i.e., Whether the data differ
`ence value satis?es the condition of —p<An_1<q (Block 106).
`Here, the values of p and q are preferably determined for the
`effective data compression. Aspeci?c example Will be given
`beloW.
`If the obtained data difference value An_1 satis?es the
`condition of —p<An_1<q, it is stored in the register R2 as
`shoWn in FIG. 4A, and “0” is stored in an Xn_1 position of
`an X region of the register R2 as shoWn in FIG. 4A in order
`to represent that the data is compressed information (Block
`108). The X region of the register R2 can store n-bit data.
`The positions Xn_1 to X1 of the X region store therein the
`conversion ?ag bits, Which represent Whether or not the
`stored data Dn_1, Dn_2, .
`.
`. , D1 have been compressed. If the
`conversion ?ag bit is “1”, it indicates that the stored data has
`been compressed, While if it is “0”, it indicates that the
`stored data has not been compressed. The least signi?cant bit
`(LSB) XO stores therein a conversion mode ?ag bit. If the
`conversion mode ?ag bit is “1”, it indicates that the data has
`been compressed by DPCM (differencing), While if it is “0”,
`it means that the data has been compressed by division as
`described beloW.
`If the obtained data difference value An_1 does not satisfy
`the condition of —p<An_1<q as a result of determination at
`Block 106, the data Dn_1 is stored in the register R2, and “1”
`is stored in the position of Xn_1 (Block 110). After the
`operation of Block 108 or 110 is performed, the value of n
`is decreased by 1 (Block 112). It is determined if n is “1”,
`and if not, Blocks 104 to 112 are repeatedly performed
`(Block 114). If it is determined that n is “1”, a “1” is stored
`in the position of XO to represent that the data has been
`converted by DPCM (Block 116).
`Thereafter, it is determined Whether or not the bit number
`of the data stored in the register R2 is smaller than (m><n)—n
`bits (Block 118). If so, it is determined Whether or not the bit
`number of the data stored in the register R2 is equal to
`
`10
`
`15
`
`25
`
`35
`
`45
`
`55
`
`65
`
`6
`(m><n)—n bits (Block 120). If so, the data stored in the
`register R2 is maintained as is. That is, the register R2 stores
`the n converted data, conversion ?ags, and conversion mode
`?ag, preferably in that order. If the bit number of the data
`stored in the register R2 is less than (m><n)—n bits, the bit
`number of the data is expanded to (m><n)—n by adding one
`or more dummy bits to the data in the register R2 (Block
`122). Thus, the data is composed of the n compressed data,
`dummy bits, conversion ?ags, and conversion mode ?ag
`stored in the register R2, preferably in that order.
`If it is determined that the bit number of the data stored
`in the register R2 is not smaller than (m><n)—n bits at Block
`118, the respective data stored in the register R1 are divided
`by 2, respectively, and the divided data are stored in the
`register R2 as shoWn in FIG. 4B (Block 124). It is deter
`mined Whether the value stored in the XO position of the X
`region of the register R2 is “1” (Block 126). As shoWn in
`FIG. 4B, in the X region respective data of n bits are stored,
`Which are produced by dividing the n bit data stored in the
`register R1 by 2, respectively. If the value stored in the XO
`position is “1”, it is replaced by “0” (Block 128). If the value
`stored in the XO position, Which is the conversion mode ?ag
`data, is “0”, it indicates that the data has been compressed by
`division. After the Blocks 120, 122, or 128 are performed, or
`if it is determined that the value stored in the XO position of
`the X region of the register R2 is not “1” at Block 126, the
`data stored in the register R2 are output as a unit (Block
`130).
`FIG. 5 illustrates a ?oWchart explaining video data restor
`ing (decompression) that can be performed by the compres
`sor and restorer in FIG. 2. The video data restoring Will be
`explained With reference to FIGS. 4A and 4B.
`First, the compressed data are read out from the memory
`24 in FIG. 2 as a unit, and the read-out data are stored in the
`register R2 (Block 200). The leading data D” is stored in the
`register R1 (Block 202). Thereafter, it is checked Whether or
`not the value of the LSB X0 is “1” (Block 204). If the LSB
`is not “1” as a result of checking at Block 204, “0” or “1”
`is added to the LSB of the respective (m—1)-bit data, and the
`resultant m-bit data are stored in the register R1 (Block 206).
`OtherWise, if the LSB is “1” as a result of checking at Block
`204, it is checked Whether or not the value of Xn_1 is “0”
`(Block 208). If the value of Xn_1 is “0”, the data are restored
`to the m-bit data by adding the difference values to the
`restored data based on the leading data, and the restored
`m-bit data are stored in the register R1 (Block 210).
`OtherWise, if the value of Xn_1 is not “0”, the m-bit data are
`stored in the register R1 as is (Block 212). Thereafter, it is
`checked Whether or not the value of n—1 is “1” after the
`operations of Blocks 210 or 212 are performed (Block 214).
`If the value of n—1 is not “1”, the operation of Block 208 is
`performed. If the value of n—1 is “1”, or after the operation
`of Block 206 is performed, the value stored in the register R1
`is output (Block 216).
`FIGS. 6A and 6B are a ?oWchart explaining a speci?c
`example of compressing 8 data values of 8 bits each, that can
`be performed by one embodiment of the compressor and
`restorer in FIG. 2. The data compressing Will be explained
`With reference to FIGS. 7A, 7B, and 7C.
`The 8 data values of 8 bits restored by the MPEG video
`restorer 26 are stored in the register R1 (Block 300). The
`leading data D” (128) stored in the register R1 as shoWn in
`FIG. 7A is stored in the register R2 (Block 302). A data
`difference value An_1 is obtained by subtracting the adjacent
`data from the leading data 128 based on the leading data
`(Block 304). As a result, the data difference value of 3 is
`obtained.
`
`0014
`
`

`
`US 6,370,193 B1
`
`15
`
`7
`Next, it is determined Whether the data difference value is
`Within a predetermined range, i.e., Whether the data differ
`ence value satis?es the condition of —9<An_1<8 (Block 306).
`Since the obtained data difference value of 3 satis?es the
`condition of —9<An_1<8, it is stored in the register R2, and
`“0” is stored in the X7 (MSB) position of the X region of the
`register R2 (Block 308). If the obtained data difference value
`An_1 does not satisfy the condition of —9<An_1<8 as a result
`of determination at Block 306, the 8-bit data 125 is stored in
`the register R2, and “1” is stored in the X7 position of the X
`10
`region (Block 310). After Blocks 308 or 310 are performed,
`the value of n is decreased by 1 (Block 312). That is, the
`value of n becomes 7. It is then determined if n is “1”, after
`Block 312 is performed (Block 314). Since the value of n is
`not 1, the Block 304 is performed. By performing the above
`process, the registers are occupied as shoWn in FIGS. 7A,
`7B, and 7C. If it is determined that n is “1”, a “1” is stored
`in the XO position of the X region (Block 316).
`Thereafter, it is determined Whether or not the bit number
`of the data stored in the register R2 is smaller than 56 bits
`(Block 318). FIGS. 7A and 7B illustrate the case that the bit
`number of the data stored in the register R2 is equal to and
`smaller than 56 bits, and FIG. 7C illustrates the case that the
`bit number of the data stored in the register R2 exceeds 56
`bits. Thereafter, it is determined Whether or not the bit
`number of the data stored in the register R2 is equal to 56
`bits (Block 320). If not, 56 bits of data are produced by
`adding dummy bits in empty (blank) regions of the register
`R2 as shoWn in FIG. 7A (Block 322). If the bit number of
`the data is equal to 56 bits, the data stored in the register R2
`is maintained as is as shoWn in FIG. 7B.
`If it is determined that the bit number of the data stored
`in the register R2 is not smaller than 56 bits as a result of
`determination at Block 318, for example, if the bit number
`of the data becomes 60 bits as illustrated as the register R2-1
`in FIG. 7C, the respective data stored in the register R1 are
`divided by 2, respectively, and the respective divided data
`are stored in the register R2 (Block 324). Though the
`registers R2-1 and R2 are illustrated differently, they have
`the same structure.
`Then, it is determined Whether the value stored in the XO
`position of the X region of the register R2 is “1” (Block
`326). If the value stored in the XO position is “1”, it is
`replaced by “0” (B