||||||||||||l||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
`
`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 .
`2720077
`l’au
`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
`IPR2 of U.S. Pat. No. 8,612,515
`IPR2 of US. Pat. No. 8,612,515
`
`

`

`US. Patent
`
`Apr. 9, 2002
`
`Sheet 1 0f 10
`
`US 6,370,193 B1
`
`FIG.1(Pri0r Art)
`
`MP
`BIT STREAM
`
`10
`
`__.._...-.
`
`BIngTREflI
`DE DER
`
` 16
`
`
`
`
`MEMORY
`
`
`MPEG VIDEO
`
`
`MANN; EMENT
`MEMORY
`RES'I‘ORER
`
`
`PROC ESSOR
`
`VIDEO
`OUTPUT
`PROCESSOR
`
`18
`
`FIG.2
`
`20
`
`
`MPEG
`
`‘
`MPFJG
`BIT STREAM ‘—'” Bfléfi?
`
`
`
`MEMORY
`
`
` MPEG VIDEO
`IMAGEMENT
`RESTORER
`
`
`
` COILIPRESSOR
`PROCESSOR
`
`
`AND RESTORER
`
`
`
`
`I.“ I DEO
`TO TV
`OUTPUT
`
`
`PROCESSOR
`
`
`28
`
`0002
`0002
`
`

`

`US. Patent
`
`Apr. 9, 2002
`
`Sheet 2 0f 10
`
`US 6,370,193 B1
`
`FIG.3A
`
`
`
`STORE lhl.Dn‘1.---.DZ.DI
`
`[N REGISTER R1
`
`STORE LEADING DATA Dn IN REGISTER R2
`
`100
`
`102
`
`
`
`
`
`
`
`
`
`OBTAIN DIFFERENCE VALUESEAn-ll
`BETWEEN ADJACENT DATA
`
`STORHATIHN REGISTER R2
`AND STORE "0" IN Xn-l
`
`DECREASE n BY "1"
`
`IN REGISTER R2
`STORE DATMDn-l)
`AND STORE "1" IN Xn-I
`
`
`
`
`
`STORE "1" IN X0
`
`116
`
`0003
`0003
`
`

`

`US. Patent
`
`Apr. 9, 2002
`
`Sheet 3 of 10
`
`US 6,370,193 B1
`
`FIG.BB
`
`118
`
`[5 THE NUEIBEROF
`
`
`BITS OF DATA. STORED IN REGISTER
`
`R2 SMLLER THAN
`
`
`(01 XnJ-n ?
`
`
`RESPEXIIIVEILY DIVIDE DMZ-X
`
`
`S'IURED IN REGISTERRI BY 2 AND
`STORE DIVIDEDDATA IN REGISTERRZ
`
`
`IS THE NUMBER OF
`
`BITS OF DATA STDRED 1N
`
`
`122
`REGISIERRZ EQUAL '10
`
`
`(m X n}-n ‘?
`
`
`
`
`MKE THE NUIIIBER 0F BITS
`SIDED-TIE: gill”; ?
`
`IN‘IU (an)-n BY ADDING
`
`REPLACETHE VALUE STORED IN
`
`Xo WITH "0" DL'AMY BIT 1N REGISTERRZ
`
` OUTPIH‘ DATA S'IURED IN
`
`
`RFfiISTERRZ AS A UNIT
`
`130
`
`END
`
`0004
`0004
`
`

`

`US. Patent
`
`Apr. 9, 2002
`
`Sheet 4 0f 10
`
`US 6,370,193 B1
`
`FIG.4A
`
`
`
`I m bits I
`
`an bits
`
`|
`
`R2 “HI-—
`m bits
`0: bits l—E—bitis
`
`(mxn‘)'n bits
`
`1
`
`x mu
`
`1 bit
`
`r1 bits
`
`FIG.4B
`
`R1 “M—
`l m bits i
`\
`
`an bit
`
`R2
`
`(m~1) bits
`
`i
`
`(an)-nbits
`
`I
`
`1 bit
`
`I
`
`(n3 bits
`
`0005
`0005
`
`

`

`US. Patent
`
`Apr. 9, 2002
`
`Sheet 5 0f 10
`
`US 6,370,193 B1
`
`READ OUT WE‘RESSEDDATA FROM
`MEMORY AS A UNIT AND STORE
`READ OUT DATA [N REGISIERRZ
`
`
`
`
`LSBXo 0F
`
` a 1.. ?
`CGAPRESSEDDATA
`=
`
`
`
` INSERT "0" 0R "1" IN
`EACH LSB 0F RESPFIJTIVE
`
`(III‘IJ'BITDATA AND STORE
`ORIGINAL mvBIT DATA
`
`IN RHSISTER R1
`
`
`212
`
`STORE In'BIT DATA IN
`
`RESTORE DATA TU m-BIT DATA BY
`ADDING DIFFERENCEVALUES TU
`RES'IUREDDATA BASED ON LEADING
`DATA AND STORE RESTORED
`DATA IN REEISTER R1
`
`REIGISTERRI AS IT IS
`
`
`
`215
`
`Y
`
`OUTPUT VALUE STORED IN
`REBISIER R1
`
`0006
`0006
`
`

`

`US. Patent
`
`Apr. 9, 2002
`
`Sheet 6 0f 10
`
`US 6,370,193 B1
`
`FIG.6A
`
`SIDRE 8 DATA 0F 8 BITS IN
`REGISTER RI
`
`
`
`300
`
`
`
`31012;: Lammc um 03
`IN REGISTERRPJ
`
`302
`
`OBTA IN D I FFERENCE VALUES ( Ian-1)
`BETWEEN ADJACENT DATA
`
`
`
`
`3mm: DIFFERENCEVALli-ES
`(An'lIIN REGISTERAND STORE
`"0" IN Xn-l
`
`310
`
`STORE 8~BIT DATA (Du-1)
`IN REGISTERRZ AND
`
`STORE "1" I” “‘1
`
`SIURE "1"
`
`IN X0
`
`316
`
`0007
`0007
`
`

`

`US. Patent
`
`Apr. 9, 2002
`
`Sheet 7 of 10
`
`US 6,370,193 B1
`
`FIG.6B
`
`
`IS THE NUMBER OF
`
`BITS OF DATA STORED IN RFfiIS'I‘ER
`
`R2 SILILLLERTHM
`
`
`55 BITS ?
`
`
`
`
`
`lIES’Efi'TIIflY DIVIDE DATA
`STORED IN REGISTERRl BY 2 AND
`STORE DIVIDED DATA IN REEISTERR2
`
`IS THE NUMBEROF
`
`BITS OF DATA STORED IN
`322
`
`
`REGISTERRZ EQUAL
`
`
`TU 56 '?
`
`IS "II-IE VALUE
`MAKE "II-1E NUMBER OF BITS
`
`
`
`STORED IN X0 "1" ?
`INTO 56 BITS BY ADDINCI
`DUE” BIT IN REGISTER R2
`
`
`328
`
`
`Xe Fr'ITH 'O"
` OUTPUT DATA S'IURED IN
`330
`
`REPLIICE THE VALUE SIURED IN
`
`REGISI‘ERRZ AS A UNIT
`
`0008
`0008
`
`

`

`US. Patent
`
`Apr. 9, 2002
`
`Sheet 8 of 10
`
`US 6,370,193 B1
`
`I 8bits I
`
`FIG.7A
`
`64 bits
`
`56 bits
`
`1
`
`m
`
`X
`
`m
`
`I
`
`8bits
`
`4bits1
`
`i 8
`
`bits
`
`;
`‘lbit
`flflflflflflfll
`
`8bits
`
`FIG.7B
`
`64 bits
`
`56 bits
`
`R2
`
`X
`
`flllflflflll
`
`0009
`0009
`
`

`

`US. Patent
`
`Apr. 9, 2002
`
`Sheet 9 0f 10
`
`US 6,370,193 B1
`
`FIG.7C
`
`64 bits
`
`60 bits
`
`Bbits
`
`Bbits
`
`4bit‘
`
`[22—1
`
`
`242
`7 n 100
`217
`200
`3
`123
`
`7bits
`
`56 bits
`
`x
`
`I
`
`7 hits
`
`llbifl
`fill-”fl
`
`0010
`0010
`
`

`

`US. Patent
`
`Apr. 9, 2002
`
`Sheet 10 0f 10
`
`US 6,370,193 B1
`
`F1G.8
`
`
`
`READ DUI CDHPRESSEDDATA
`
`FROM MEMORY AS A WORD UNIT
`
`
`AND SIDRE READOUT DATA
`IN REGISTER R2
`
`
`400
`
`STORE LEADING DATA DB
`IN REEIS’IERRI
`
`LSBXo 0F
`
`COIfl’REEEDgATA
`
`
`402
`
`
`406
`
`INSERT “0" OR "1" IN
`EACH LSB 0F RESPMIVE
`~."'-BI'I‘ DATA AND STORE
`m-BIT RESIURED DATA
`IN REGISTERRI
`
`412
`
`SIDRE B-BIT DATA IN
`REGISTERRl AS IT IS
`
`RESTORE DATA TU B-BIT DATA
`BY ADDING DIFFERENCEVALUES TO
`RESIUREDDATA BASED ON
`LEADING DATA AND STORE RESTORE!)
`DATA IN REGISTERRI
`
`
`
`0011
`0011
`
`

`

`US 6,370,193 B1
`
`1
`MI’EG DATA COMPRESSION AND
`DECOMPRESSION USING ADJACENT DATA
`VAMJIC DIFFERENCING
`
`FIELD OF THE INVENTION
`
`This invention relates to MPEG multimedia data, and
`more preferably to compression and decompression of
`MPEU data.
`
`BACKGROUND OF THE INVENTION
`
`ll]
`
`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-
`
`15
`
`pressed may be restored or decompressed using an MPEG-1 *
`or MPEG-2 decoder. More specifically, 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.
`
`an
`
`In one specific example, if the number of horizontal pixels
`are 720 and 480 respectively,
`the numerical value for
`discrimination between blacki’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 ol'data to be stored may
`become 720x480x3x8x2 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 ot‘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 MI’EG 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 int'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
`MPEU system decoder 01' FIG. I will now be described.
`Specifically, the memory management processor 12 stores
`the MPEG-compressed video data separated by and output
`from the MPEG bitstream decoder 11] in a compressed video
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`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
`l6 restores the
`MPEG-compressed video data. The memory management
`processor 12 stores the video data restored by the Mt’EG
`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 andtor decrease the perfor-
`mance of the system that processes MPEG data.
`SUMMARY OF TIIE 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 compresv
`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 it‘ the dilIerence value is less than a predetermined
`range, compression may be provided for MPEG data.
`More specifically. according to the present invention, a
`series of data values of MPEG video data is separated from
`an MPEG bitstream. Dill‘erence values are obtained between
`succeeding adjacent data values of the MPEG video data.
`For each data value, the data value is stored if the dilference
`exceeds a predetermined range, and the difference 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. 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. Go the other
`hand, if the data values and ditlerence values that were
`stored are less than the predetermined sixe,dummy bits may
`be added to the data, so that the data that was stored equals
`the predetermined size. A mode flag 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 MI’EG video
`data from an MPEG bitstream to obtain mxn bits of MPEG
`video data. The mxn bits of MPEG video data are com-
`pressed into (mxn)—n bits using adjacent value difiereneing
`and data value dividing. The (mxn)—n bits of compressed
`MPEG video data is stored.
`
`Preferably, the (mxn)—n bits of compressed MPEG video
`data include rt l-bit conversion flags to indicate whether the
`
`0012
`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, it” needed, to increase the size of the compressed
`video data to (mxn)—n bits. Finally, the (mxn)—n bits of
`compressed MPEG video data also preferably include a .1 -bit
`mode flag, to indicate whether dilIerence values or divided
`values are stored.
`
`'Ihe compressed MPEG data may be dccompressed 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 flag that is
`associated with the data value indicates that the difference is
`
`stored. Adjacent data value adding is preferably performed
`only if the mode flag has a first value to indicate that
`differencing was used in compression. If the mode flag 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. (mxn)-n bits of compressed MPEG video
`data are decompressed into a series of [1 data values of m bits
`each ofdecompresscd MPEG video data using adjacent data
`value adding and data value multiplying. The (mxn)—n bits
`of compressed MPEG video data include n 1—bit conversion
`flags to indicate whether the data value or adjacent data
`value adding is used to decompress each of the n data values.
`The (mxn)—n bits of compressed MPEG video data also
`preferably include a plurality of dummy bits that increase
`the sin: of the compressed MPEG video data to (mxn)-n
`bits, if needed. A 1—bit mode flag 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) andtor com—
`puter program products.
`
`BRIE!T 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 flowchart 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 ofFIGS. 3A
`and SB.
`
`flowchart explaining video data restoring
`FIG. 5 is a
`according to the present invention.
`FIGS. 6A and 6B are a flowchart explaining data corn—
`preSsion aceording to an embodiment of the present inven-
`tion.
`
`l-‘IGS. 7A to 7D are views explaining data compression
`utilizing data compression of FIGS. 6A and 68.
`FIG. 8 is a flowchart explaining video data restoring
`according to the present invention.
`
`DETAILED DESCRIPTION 01“ 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,
`
`5
`
`It]
`
`15
`
`*
`
`3o
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`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
`compressiontdeoornpression 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
`F IG. 2, a system decoder according to the present invention
`includes an Mt’EG 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 MPEC-
`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 rcstorer 26. The
`MPEG video restorer 26 restores (decompresses) the com-
`pressed video data and outputs the restored video data to the
`compressor and rcstorer 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 restorcr 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 3|]. 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, 68 and 8 which are flowchart illustrations. It will be
`understood that each block of the flowchart illustrations, and
`combinations of blocks in the flowchart illustrations. can be
`implemented by computer program instructions. 'l‘hcse 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 specified in the
`flowchart 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 specified in the flow-
`chart block or blocks.
`
`0013
`0013
`
`

`

`US 6,370,193 B1
`
`5
`Accordingly, blocks of the flowchart illustrations support
`combinations of means for performing the specified
`functions, combinations of steps for performing the speci-
`fied functions and program instruction means for performing
`the specified functions. It will also be understood that each
`block of the flowr:hart
`illustrations, and combinations of
`blocks in the flowchart illustrations, can be implemented by
`special purpose hardware-based computer systems which
`perform the specifier]
`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 flowchart 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 SB when the compressed data
`is less than (mxn)—n bits, and FIG. 4B is a View explaining
`video data compression when the compressed data exceeds
`(mxn)-n bits.
`. D2, D. output
`.
`The n data values of to bits D,,, D,,_I .
`from the MPEG video restorer 26 are stored in a register R1
`(Block 100). The register R1 can store therein mxn-bit data.
`The data I)N 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 (mxn)—n-bit data. Thereafter, a data
`dilIerence value A,,_,
`is obtained by subtracting adjacent
`data D“_J from leading data D" based on the leading data D”
`of the restored data (Block 104}. The adjacent data ditIer—
`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 satisfies the condition of -p<A"_l<q [Block 106).
`Here, the values of p and q are preferably determined for the
`effective data compression. Aspecitic example will be given
`below.
`
`If the obtained data difference value a,,_, satisfies the
`condition of —p<A"_1<q, it is stored in the register R2 as
`shown in FIG. 4A, and “U” is stored in an X”_l 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 X,“] to X] of the X region store therein the
`conversion flag bits, which represent whether or not
`the
`stored data DWI, D,,_2, .
`.
`. , D1 have been compressed. If the
`conversion flag bit is I", 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 significant bit
`(LSB) XIl stores therein a conversion mode flag bit. If the
`conversion mode flag 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 dilIerence value AH does not satisfy
`the condition of —p<A“_1<q as a result of determination at
`Block 106, the data D”_, is stored in the register R2, and “1"
`is stored in the position of X"_, (Block 110). After the
`operation of Block 108 or 110 is performed, the value of rt
`is decreased by I {Block 112). It is determined if n is " I",
`and if not, Blocks 104 to 112 are repeatedly performed
`(Block 114). If it is determiner! that n is “l”, a “I" is stored
`in the position of X0 to represent that
`the data has been
`converted by DPCM (Block 116).
`Thereafter, it is determined whether or not the bit number
`ofthe data stored in the register R2 is smaller than (mxn)—n
`bits (Block 118). Ifso, it is determined whether or not the hit
`number of the data stored in the register R2 is equal
`to
`
`in
`
`15
`
`*
`
`an
`
`35
`
`4t]
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`the data stored in the
`(mxn)—n bits (Block 120). If so,
`register R2 is maintained as is. That is, the register R2 stores
`the n converted data, conversion flags, and conversion mode
`flag, preferably in that order. If the bit number of the data
`stored in the register R2 is less than (mxn)—n bits, the bit
`number of the data is expanded to (mxn}-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 flags, and conversion mode flag
`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 (mxn)—n hits at Block
`118. the respective data stored in the register R1 are div idcd
`by 2, respectively, and the divider] data are stored in the
`register R2 as shown in FIG. 43 (Block 124). It is deter—
`mined whether the value stored in the X0 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 Rl by 2, respectively. If the value stored in the X,J
`position is “l
`it is replaced by “0" (Block 128). If the value
`stored in the X0 position, which is the conversion mode flag
`data, is "(1", 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 X0 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 flowchart 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 43.
`First, the compressed data are read out from the memory
`24in FIG. 2 as a unit, and the read—out data are stored in the
`register 112 (Block 200). The leading data DJ, is stored in the
`register R1 {Block 202). Thereafter, it is checked whether or
`not the value of the LSB X,J 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 R] (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 X,,_.
`is “0“
`(Block 208). If the value of X,,_, 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—hit data are stored in the register R1 (Block 210).
`Otherwise, if the value of )(,,_I is not “0", the m-bit data are
`stored in the register RI as is (Block 212). Thereafter, it is
`checked whether or not the value of n—l
`is “1” after the
`
`operations of Blocks 210 or 212 are performed (Block 214).
`If the value of n—l is not "1", the operation of Block 208 is
`performed. If the value of n—I is "I". 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 flowchart explaining a specific
`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 ofS bits restored by the MPEG video
`restorer 26 are stored in the register R1 (Block 300}. The
`leading data D,I (128) stored in the register R] as shown in
`FIG. 7A is stored in the register R2 (Block 302). A data
`dilIerence value AM 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
`0014
`
`

`

`US 6,370,193 B1
`
`7
`Next, it is determined whether the data dilference value is
`within a predetermined range, i.e., whether the data ditIer—
`ence value satisfies the condition of —9<6,,_ .<8 (Block 306).
`Since the obtained data difference value of 3 satisfies the
`condition of —9<A,,_,<8. it is stored in the register R2, and
`“0" is stored in the X, (MSB) position of the X region of the
`register R2 (Block 308). If the obtained data dilference value
`AMI does not satisfy the condition of —9<A"_1<8 as a result
`of determination at Block 306, the 8-bit data 125 is stored in
`the register R2, and “ l " is stored in the X7 position of the X
`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 ifn is "t", 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. TA,
`73, and 7C. If it is determined that n is “1”. a “1” is stored
`in the XD 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
`hit number of the data stored in the register R2 exceeds 56
`bits.
`'l'hereal‘ter,
`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 hits 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 hit number of
`the data is equal to 56 bits, the data stored in the register R2
`is maintained as is as shown in FIG. TB.
`If it is determined that the bit number of the data stored
`in the register R2 is not smaller than 56 hits as a result of
`determination at Block 318. for example, it‘ the hit number
`of the data becomes GU bits as illustrated as the register R2—l
`in FIG. 7C. the respective data stored in the register Rl 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 XE,
`position of the X region of the register R2 is "1" (Block
`326). If the value stored in the 1QJ position is “1",
`it is
`replaced by “0" (Block 328}. Specifically, data 121 is
`obtained by dividing the last data 242 in FIG. 7C by 2, and
`this divided data is represented as "1111001". Since the
`value stored in the KO position is “l" . it is replaced by “0“,
`and then in the X0 position of the X region of the register R2
`“1111000" is stored. After Blocks. 320, 322, or 328 is
`performed, or if it is determined that the value stored in the
`X0 position of the X region of the register R2 is not "1” at
`Block 326, the data stored in the register F2 are output as a
`unit (Block 330).
`FIG. 8 is a flowchart explaining an example of restoring
`(decompressing) 8 data values of 8 bits each, that may be
`performed by an embodiment of the compressor and restorer
`in FIG. 2.
`
`First, the compressed data are read out from the memory
`24 in FIG. 2 as a word unit. and the read-out data are stored
`in the register R2 (Block 400). The leading data D3 is stored
`in the register R1 (Block 402). "thereafter.
`it is checked
`whether or not the value 01" the LSB