`
`USUUG370193131
`
`(72) United States Patent
`US 6,370,193 B1
`(10) Patent N0.:
`Lee
`
`(45) Date of Patent: Apr. 9, 2002
`
`(54) MPH } DATA COMPRESSION AN!)
`DECOMPRESSION USING ADJACENT DATA
`VALUE DIFFERENCING
`
`5,973,742 A * 1071999 Gardyne et a].
`(7,023,295 A .
`272mm Fan
`6,028,635 A a 272er Owen etal .
`6,038,345 A 7
`37277077
`()sava ct al
`
`
`
`34874177
`34374775
`3487403
`. 3827232
`
`(75)
`
`Inventor: Yong-Wnon Lee, Kyungki-do (KR)
`
`‘ cited by examiner
`
`(7'3) Assigncc: Sal‘nsungI Electronics (30., [.td. {KR}
`
`( * ) Notice:
`
`Subject to any disclaimer, the term of this
`patent
`is extended or adjusted under 35
`USU. 154(b) by 0 days.
`
`(21) App}. No.: 097031212
`
`(22)
`
`Filed:
`
`Feb. 26, 1998
`
`(30)
`
`Foreign Application Priority Data
`
`Feb. 26, [997
`
`(KR)
`
`92—5916
`
`H0415 1766
`Int. Cl.7
`(51)
`"3757240. 15
`(52) U.S. C].
`348.384 1,390.1,
`.
`(58) Field of Search
`348.842.1"401, 402.1—405.1, 406.1, 416.1
`420.1, 423.1, 426.1-, 3647578; 3827232;
`3757240, 240.01. 240.02, 240.03, 240.09,
`240. l, 2401], 240.12, 240.13, 240.}4;
`1-1041} 17’66
`
`(56)
`
`References Cited
`U.S. PAI‘ENT DOCUMENTS
`
`67'1993 Honjo
`358.3426
`523,949 A "'
`271998 Mohini
`.. 364514 R
`5,215,126 A *
`
`371998 Keesman
`.. 3487'401
`5.?29293 A “
`3437’426
`471098 Kandltlr ct al.
`5342.34? A *
`
`.3487'415
`5,831.67? A " “”998 Slrcatcr
`
`
`3757247
`3,832,037 A * “71998 Park
`. 304771532
`5.338.597 A * 1171998 Fan et al.
`
`..
`5344.608 A * 127'1998 Yt: cl a1
`3437390
`5341262 A * 12.11993 Candficld ei al.
`3437415
`
`971999 Toebes, VIII et al.
`5,959,690 A "
`348.3526
`
`Primary Examiner—Chris Kelley
`Assistant Exmm'ner—Tung V0
`(74) Attorney, Agent, or Firm—Myers Bige] Sibley &
`Sajovec
`(5?)
`
`ABSTRACT
`
`MPEU data is compressed by obtaining difference values
`between succeeding adjacent data values of MI’EG 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 [1‘ lhe dill'erence value is
`less than a predetermined range, compression may be pro—
`vided for MPEG data. More specifically, a series of data
`values of MPEG7 video data is separated from an MI’EG
`bitstrcam. Difi'crcnce values are obtained between succeed—
`ing adjacent data values of the MPEG video data. For each
`data value, the data value is stored il‘ lhe ditl'erence exceeds
`a predetermined range, and the dilIerence value is stored if
`the difference value is less than the predetermined range. A
`conversion flag 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
`dill'erence values that were stored exceed a predetermined
`sire. 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. 0n the other
`hand.
`it‘ the data values and dilIerence 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 Drawing Sheets
`
`20
`
`
`MPEG
`BIT STREMI _—"" BIT STREM:
`DECODER
`
`
`MPEL-
`
`MEMORY
` HPEG VIDEO
`
`
`iLiNAGEMENT
`
`
`
`PROCESSOR
`
`mm“
`COMPRESSOR
`AND RESTORER
`
`
`
`
`
`V 1 DEC!
`TO TV
`OUTPUT
`
`
`PROCESSOR
`
`
`28
`
`0001
`0001
`
`Apple/Twitter
`Apple/Twitter
`Ex. 1022
`Ex. 1022
`IPR3 of U.S. Pat. No. 7,765,482
`IPR3 of US. 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
`
`
`
`US. Patent
`
`Apr. 9, 2002
`
`Sheet 4 0f 10
`
`US 6,370,193 B1
`
`FIG.4A
`
`R1 ------—
`m bitsi
`
`m><n bits
`
`R2 -----—
`
`m bits
`
`m bits g—bits
`
`(an‘)-n bits
`
`1
`
`X mu
`
`1 bit
`
`n bits
`
`FIG.4B
`
`m ------—
`
`
`
`(m-l) bitsi
`
`(an)-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” (Block 328). Speci?cally, data 121 is
`obtained by dividing the l