United States Patent c191
`Kato
`
`I lllll llllllll Ill lllll lllll lllll lllll lllll lllll lllll lllll llllll Ill lllll llll
`US005392037A
`5,392,037
`[11] Patent Number:
`[45] Date of Patent:
`Feb. 21, 1995
`
`[54] METHOD AND APPARATUS FOR
`ENCODING AND DECODING
`[75]
`Inventor: Shiro Kato, Osaka, Japan
`[73] Assignee: Matsushita Electric Industrial Co.,
`Ltd., Osaka, Japan
`[21] Appl. No.: 885,940
`[22] Filed:
`May 20, 1992
`[30]
`Foreign Application Priority Data
`May 21, 1991 [JP]
`Japan .................................. 3-116008
`Aug. 31, 1991 [JP]
`Japan .................................. 3-302847
`Feb. 21, 1992 [JP]
`Japan .................................... 4-34659
`
`Int. Cl.6 ............................................ H03M 13/00
`[51]
`[52] U.S. Cl •........................................ 341/67; 341/94;
`341176
`[58] Field of Search ............... 341/94, 76, 67; 375/26,
`375/27, 34
`
`[56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`5,034,965 7/1991 Kato .
`
`OTHER PUBLICATIONS
`"Draft (Revision 6) of the JPEG algorithm", JPEG--
`8-46, Jun. 23, 1990.
`"An Experimental Study for a Home-Use Digiral
`VTR" by C. Yamamitsu, et al. IEEE Trans. CE-35 No.
`3, Aug. 1989, pp. 450-457.
`Primary Examiner-Sharon D. Logan
`
`Attorney, Agent, or Firm-Lowe, Price, LeBlanc &
`Becker
`ABSTRACT
`[57]
`In an encoding side, an estimate of input data is gener(cid:173)
`ated. An estimation error which is equal to a difference
`between the estimate and the input data is calculated.
`The estimation error is classified, thereby generating a
`category index indicative of a category corresponding
`to the estimation error. The input data is divided by a
`divisor, and a remainder of a result of the dividing is
`generated. The divisor is equal to a given value which is
`greater than a difference between an upper limit value
`and a lower limit value defining a range of the category.
`The category index and the remainder are encoded into
`corresponding codes which are outputted. In a decod(cid:173)
`ing side, input data is decoded into a category index and
`a remainder. An estimate is generated from previous
`output data. A divisor is generated in accordance with
`the category index. An offset is generated in accordance
`with the divisor and the estimate. The offset is equal to
`the divisor multiplied by an integer. The offset and the
`remainder are added, and thereby new output data is
`generated in accordance with the offset and the remain(cid:173)
`der. In the presence of a control signal, the estimate is
`generated by a prediction process which differs front a
`prediction process in an encoding side. In the presence
`of the control signal, the offset is generated so as to
`increase a correlation between output data and the esti(cid:173)
`mate.
`
`26 Claims, 6 Drawing Sheets
`
`MAIN ENCODE
`107
`_10_s..___Ei r _____ J_ _______ cii---,
`Di
`101
`n-.----'---------.... CALC
`REMAIN
`SUB
`.......... __.... ENCODE
`OUi,Mi
`105
`
`110
`
`102 103 Si
`
`104
`
`CONV
`
`109
`
`PREDICT
`
`Ji
`SUB
`CLASSIFY 1 - - -....... - -... ENCODE
`t_ ___________________ _J
`
`108
`
`Ci
`
`Page 1 of 27
`
`

`
`U.S. Patent
`
`Feb. 21, 1995
`
`Sheet 1of6
`
`5,392,037
`
`101
`
`Di
`
`FIG. 1(a)
`
`MAIN ENCODE
`Ei r----_J_1_0_1~- -- -------,
`106
`CEi
`SUB
`REMAIN
`CALC
`ENCODE
`
`I
`I
`I
`I
`I
`
`110
`
`OUi,Mi
`105
`
`102 103 Si
`..-----'--- +
`PREDICT
`
`CONV
`
`109
`104
`--""--
`Ji
`SUB
`CLASSIFY 1--.--..~-..... ENCODE
`L. ___________________ _J
`
`108
`
`Ci
`
`FIG. 1(b)
`MAIN DECODE
`r ____ f __________________ -,
`113
`-------. 121
`Mi
`SUB
`DECODE
`
`SYNTHESIS CKT
`116 126
`r1--, D.
`
`1
`
`I
`I
`
`111
`
`Ei
`
`OUi,Mi
`
`119
`
`112
`
`BUFFER
`MEMORY
`
`CEi
`
`CJi 120
`SUB
`·DECODE
`
`I
`q• I
`LJ
`Jl:
`:
`L_ _______________________ _J
`I
`I
`
`I
`I
`
`L-
`114 r-- ----- -.,
`
`. - - - . . - -
`
`-
`
`CONV
`
`I
`I
`
`.__,..._._..,. i.--......-t PREDICT
`:
`122
`:
`Sxj L._) _______ .J
`
`115
`QUOTIENT CALC
`
`Pi
`
`Page 2 of 27
`
`

`
`U.S. Patent
`
`Feb. 21, 1995
`
`Sheet 2 of 6
`
`5,392,037
`
`FIG. 2
`
`MAIN DECODE
`r ____ 11_1_3 _______________ 1
`SYNTHESIS CKT
`116
`126
`r L_ -..,
`121
`:
`I Di
`Ei
`:
`SUB
`I
`DECODE 1----'----+----~
`OUi.Mi
`
`:
`:
`!
`I
`
`I
`
`u•
`Ml
`
`119
`
`CEi
`
`112 :
`: BUFFER
`C. : MEMORY
`CJi 120
`SUB
`:
`CONV
`!
`DECODE
`:Ji! - - -
`:
`LJ
`L--------------_________ .J
`Sxj
`
`l :
`I
`
`1
`
`114
`
`I
`
`I
`
`117
`
`125
`
`I
`L ____ .J
`I
`
`I
`
`Ni
`
`202
`
`PREDICT
`
`QUOTIENT
`CALC
`
`203
`201
`
`FIG. 5
`PREDICT CKT
`r-----------------1--------------------------------,
`504
`505
`503
`502
`+
`QUANTIZE
`AVERAGE
`DELAY
`:+:
`
`DDi '(q)
`
`L ______________ ----------------------------------_J
`
`CONTROL SIGNAL
`
`Page 3 of 27
`
`

`
`U.S. Patent
`
`Feb. 21, 1995
`
`Sheet 3 of 6
`
`5,392,037
`
`FIG. 3(a)
`PREDICT CKT
`202
`,------------------l------------------,
`P'i=Di-H
`Pi=Di-I
`,-------,
`
`: SW U4-.... , ---t DELAY
`DELAY
`Pi, P'i ..--·~
`:
`302
`301
`I L ==~r===--3_0_3 _____________ ----____ _J
`CONTROL SIGNAL
`
`I
`I
`
`I
`I
`
`FIG. 3(b)
`OUj
`QUOTIENT CALC
`Ei
`203
`,----- --------- ____________ j _______ -,
`
`307
`
`- - -N i
`
`308
`
`SXj >----..:+14-.._-------+-----< Pi, P' i
`304
`l_ __________________________________ _J
`
`CONTROL SIGNAL
`
`Page 4 of 27
`
`

`
`U.S. Patent
`
`Feb. 21, 1995
`
`Sheet 4 of 6
`
`5,392,037
`
`FIG. 4(a)
`
`404 Di
`
`405
`
`Bi (k)
`
`FIG. 4(b)
`
`DTi
`
`DCi'
`
`417
`
`DELAY
`
`419
`
`420
`
`DE(cid:173)
`BLOCKI NG
`
`418 DOi' {h)
`
`V'
`
`Page 5 of 27
`
`

`
`U.S. Patent
`
`Feb. 21, 1995
`
`Sheet 5 of 6
`
`5,392,037
`
`FIG. 6(a)
`
`CONTROL
`
`l-602
`ENCODE
`CKT
`
`I
`
`I
`
`I
`
`L. ____ ...J~615
`616
`
`COUNT
`
`:
`•----
`
`I
`I
`I
`
`n
`
`FIG. 6(b)
`.....---- · - - - - - - - - - - ------. ,,.__, 622 DECODE
`CKT
`CONTROL
`
`,- 608
`
`I
`
`LI
`l2
`
`601
`
`621
`
`I
`
`I
`
`I
`
`L. ____ J\.533 :
`634: I
`
`COUNT
`
`I
`I
`I
`
`I
`
`625
`
`635
`
`SIDE
`INFO
`SEPARATE
`620 L_ _ _!:=:=.=~--- - - - - - - ·---
`
`r-------•-.. 636
`63,,
`---vi.Vi' - (cid:173)
`........... ___..ROM
`
`623
`~ ........... --...624
`ERROR
`CONCEAL
`
`Page 6 of 27
`
`

`
`.....,)
`CH
`0
`~ ...
`CH
`...
`(II
`
`Q\
`~
`Q\
`
`a
`00 go
`
`~ UI
`..
`~ ......
`~
`~
`
`"'C a ;
`•
`~ • 00
`
`f"'I'-
`
`AREA
`OPEN
`
`WORDS Ci
`DIRECTION OF WRITING ,
`
`.. ~
`
`i
`
`I en
`
`__
`I ---
`
`EENDING
`OGE
`
`DATA STORE REGION
`
`--
`I ---
`I Ci
`PRIOR ART
`
`FIG. 8
`
`(2
`
`I (1 I
`i
`EDGE
`STARTING
`
`WORD SECOND PORTIONS R i
`DIRECTION OF WRITING
`
`)
`
`AREA
`OPEN
`
`WORD FIRST PORTIONS Pi
`DIRECTION OF WRITING
`
`~
`
`!ml
`~
`EDGE
`ENDING
`
`I -~~ I Pi 1-~~ I Pn ~•Rn I ~~~E[~~~ I R2
`
`DATA STORE REGION
`
`FIG. 7
`
`I P1 I P2
`
`~
`EDGE
`STARTING
`
`Page 7 of 27
`
`

`
`1
`
`5,392,037
`
`MEI'HOD AND APPARATUS FOR ENCODING
`AND DECODING
`
`2
`lower bits is determined by the category index. The
`lower bits of .the estimation error are outputted subse(cid:173)
`quently to the category-index Huffman code. In this
`way, the estimation error is divided into higher-bit in-
`5 formation and lower-bit information, and each of the
`BACKGROUND OF THE INVENTION
`higher-bit information and the lower-bit information is
`1. Field of the Invention
`encoded. If L lower bits of an estimation error (a pre-
`This invention relates to a method of efficient encod-
`diction error) are directly cut and taken out, duplicated
`ing which can reduce the total number of bits of re-
`code words occur in a positive side and a negative side
`corded or transmitted data. This invention also relates
`to a method ofrelated decoding. In addition, this inven- 10 respectively. Accordingly, in cases where an estimation
`error is negative, "l" is subtracted from the estimation
`tion relates to apparatus for efficient encoding and de-
`coding.
`error and then L lower bits of the result of the subtrac-
`2. Description of the Prior Art
`tion are cut and taken out.
`Highly-efficient encoding is of various types, and
`According to a variable-length encoding procedure
`some of encoding is based on the combination of two of 15 such as a Huffman encoding procedure, short code
`words are assigned to data having high probabilities of
`the types. Systems for efficiently encoding image data
`and audio data are being standardized. The standardiza-
`occurrence while long code words are assigned to data
`tion of a system for efficiently encoding still image data
`having small probabilities of occurrence, so that the
`is advanced by JPEG, a lower branch of International
`total number of bits of generated code words can be
`Standardization Organization (ISO), and is now nearly 20 reduced in time average. The variable-length encoding
`is highly efficient, and is reversible.
`completed.
`A description will now be given of a prior-art JPEG
`In image data and audio data, adjacent data are
`efficient encoding of the DCT (discrete cosine trans-
`closely correlated so that an estimation error is close to
`form) type which is disclosed in "Draft (Version 6) of
`"O" at a high probability. Thus, advanced highly-effi-
`25 cient encoding is enabled by assigning short code words
`the JPEG algorithm", JPEG-8-R6, Jun. 24, 1990.
`to identification numbers (category indexes) for catego-
`Input data is digital image data, that is, a sampled and
`quantized image signal. A frame represented by the
`ries corresponding to estimation errors having small
`image data is divided into blocks each having 8 by 8
`absolute values.
`pixels (8 pixels in a horizontal direction, and 8 pixels in
`Such predictive encoding (one of highly-efficient
`a vertical direction), and the image data is rearranged 30
`into sets of data which correspond to the blocks respec-
`encoding) has a problem as follows. A decoding side
`tively. This process is referred to as "blocking". The
`recovers decoded values through processes including a
`image data in each block is subjected to 8-degree dis-
`process of integrating or accumulating the estimation-
`error data outputted from an encoding side. Thus, if an
`crete cosine transform (referred to as DCT hereinafter),
`generating a set of DCT coefficients corresponding to 35 error occurs in the signal transmitted from the encoding
`the image data. A set of DCT coefficients has one DC
`side to the decoding side due to noise or others, the
`coefficient and 63 AC coefficients. Each DCT coeffici-
`affection by the error is accumulated and remains in the
`ent is quantized with a given quantization step size Q. In
`decoding side for a long time so that the propagation of
`other words, each DCT coefficient is divided by Q, and
`the error is caused.
`the result of the division is rounded. The resultant quan- 40 U.S. Pat. No. 5,034,965 discloses highly-efficient en-
`coding in which data processing is executed block by
`tized AC coefficients are two-dimensionally encoded
`into a Huffman code. The resultant quantized DC coef-
`block. In general, a large-scale circuit is required to
`ficient is predictively encoded.
`implement such block-by-block data processing.
`The predictive encoding of a quantized DC coeffici-
`Variable-length encoding such as Huffman encoding
`ent will be described hereinafter. A quantized DC coef- 45 is inherently efficient. In general variable-length encod-
`ing, input data is encoded into variable-length code
`ficient is represented by data Di (i= 1, 2, 3, ... , and "i"
`denotes an order number of data which is equal to an
`words, and the data store region in a transmission for-
`order number of a related block). In the predictive
`mat is stuffed with a bit sequence composed of the code
`encoding, an estimate (a prediction value) Pi is calcu-
`words before data transmission is executed. FIG. 8
`lated from input data Dk which is previously encoded, 50 shows an example of the arrangement of variable-length
`code words in the data store region in a prior-art trans-
`and an estimation error (a prediction error) Si equal to
`the difference between the data Di and the estimate Pi
`mission format. As shown in FIG. 8, "n" variable-code
`is calculated and then the estimation error Si is encoded.
`words Ci (i= 1, 2, 3, ... , n) are sequentially arranged in
`Here, the letter "k" denotes an integer smaller than the
`the data store region, and there is no open space be-
`integer "i". This prediction is of the 0-th order type and 55 tween adjacent code words. In addition, the first code
`Cl extends from the starting edge of the data store
`is executed on the basis of a previous value, and the
`region, and the last code word Cn is spaced from the
`immediately-preceding input data is used as the esti-
`ending edge of the data store region by an open area.
`mate.
`The encoding of an estimation error (a prediction
`According to such variable-length encoding and re-
`error) Si will be described hereinafter. One of preset 60 lated decoding, if an error occurs in the transmission of
`categories identified by different numbers (category
`code words from an encoding side to a decoding side,
`indexes) is selected in accordance with the value of an
`the lengths of code words following the error can not
`estimation error Si, and the identification number (the
`be detected and also the boundaries between the code
`category index) corresponding to the selected category
`words following the error can not be detected. Thus, in
`is encoded into a Huffman code. The category index 65 the presence of an error, the code words following the
`error can not be accurately decoded. This problem is
`corresponds to the information represented by higher
`bits of the estimation error. Lower bits of the estimation
`referred to as error propagation (see C. Y amamitsu, et
`error are cut and taken out. The number L of these
`al, "AN EXPERIMENTAL STUDY FOR A HOME-
`
`Page 8 of 27
`
`

`
`5,392,037
`
`3
`USE DIGITAL VTR", IEEE Trans. CE-35, No. 3,
`Aug. 1989, pp 450-457).
`
`4
`ing Coded DC data into a quantized DC coefficient;
`dequantizing the quantized AC coefficients into AC
`coefficients; dequantizing the quantized DC coefficient
`SUMMARY OF THE INVENTION
`into a DC coefficient; subjecting the AC coefficients
`It is a first object of this invention to provide an im- 5 and the DC coefficient to inverse transform and thereby
`generating first decoded data in a block in accordance
`proved method of efficient encoding.
`It is a second object of this invention to provide an
`with the AC coefficients and the DC coefficient; and
`improved method of decoding.
`rearranging the first decoded data in a block into second
`It is a third object of this invention to provide an
`decoded data which has a data arrangement corre-
`10 sponding to a data arrangement of input data to be
`improved apparatus for efficient encoding.
`It is a fourth object of this invention to provide an
`encoded in an encoding side; wherein the Coded-DC-
`data decoding step comprises the sub steps of decoding
`improved apparatus for decoding.
`A first aspect of this invention provides a method of
`the Coded DC data into a category index and a remain-
`efficient encoding which comprises the steps of generat-
`der, generating an estimate in accordance with decoded
`ing an estimate of input data; calculating an estimation 15 quantized data, generating a divisor in accordance with
`error which is equal to a difference between the esti-
`the category index, generating an offset in accord;race
`mate and the input data; classifying the estimation error
`with the divisor and the estimate, the offset being equal
`and generating a category index indicative of a category
`to the divisor multiplied by an integer, adding the offset
`corresponding to the estimation error; dividing the
`and the remainder and thereby generating new quan-
`input data by a divisor and generating a remainder of a 20 tized data in accordance with the offset and the remain-
`der; wherein the estimate-generating step comprises the
`result of the dividing, the divisor being equal to a given
`value which is greater than a difference between an
`sub step of, in the presence of a control signal, generat-
`upper limit value and a lower limit value defining a
`ing the estimate by a prediction process which differs
`range of the category; and encoding the category index
`from a prediction process in an encoding side, and
`and the remainder into corresponding codes and out- 25 wherein the offset-generating step comprises the sub
`putting the codes.
`step of, in the presence of the control signal, generating
`A second aspect of this invention provides a method
`the offset so as to increase a correlation between de-
`of decoding which comprises the steps of decoding
`coded data in a block being currently decoded and·
`input data into a category index and a remainder; gener-
`decoded data in an error-free block adjoining the block
`ating an estimate from previous output data; generating 30 being currently decoded.
`A fifth aspect of this invention provides a method of
`a divisor in accordance with the category index; gener-
`ating an offset in accordance with the divisor and the
`efficient encoding which comprises the steps of encod-
`estimate, the offset being equal to the divisor multiplied
`ing input data into a variable-length code, and arranging
`by an integer; and adding the offset and the remainder
`the variable-length code into a data store region of a
`and thereby generating new output data in accordance 35 given capacity and outputting the variable-length code,
`the improvement comprising the steps of encoding the
`with the offset and the remainder; wherein the estimate-
`generating step comprises the sub step of, in the pres-
`input data into variable-length code words each having
`ence of a control signal, generating the estimate by a
`a first portion and a second portion, wherein the first
`prediction process which differs from a prediction pro-
`portion includes a bit pattern which can determine a
`cess in an encoding side, and wherein the offset-generat- 40 code length of the related word, and wherein the see-
`ing step comprises the sub step of, in the presence of the
`ond portion is equal to a part of the related word except
`control signal, generating the offset so as to increase a
`the first portion; collecting the first portions into a
`correlation between output data and the estimate.
`group and arranging the group of the first portions into
`A third aspect of this invention provides a method of
`the data store region; and collecting the second portions
`efficient encoding which comprises the steps of collect- 45 into a group and arranging the group of the second
`portions into the data store region.
`ing a given number of bits of input data into a block;
`subjecting the input data in a block to given transform
`A sixth aspect of this invention provides an apparatus
`and thereby generating a DC coefficient and AC coeffi-
`for efficient encoding which comprises means for gen-
`cients from the input data in a block; quantizing the DC
`erating an estimate of input data; means for calculating
`coefficient into data D; encoding the data D into Coded 50 an estimation error which is equal to a difference be-
`DC data; quantizing the AC coefficients; and encoding
`tween the estimate and the input data; means for classi-
`results of quantizing the AC coefficients into Coded AC
`fying the estimation error and generating a category
`data: wherein the data-D encoding step comprises the
`index indicative of a category corresponding to the
`sub steps of generating an estimate of the data D, gener-
`estimation error; means for dividing the input data by a
`ating an estimation error which is equal to a difference 55 divisor and generating a remainder of a result of the
`dividing, the divisor being equal to a given value which
`between the data D and the estimate, classifying the
`estimation error and generating a category index indica-
`is greater than a difference between an upper limit value
`tive of a category corresponding to the estimation error,
`and a lower limit value defining a range of the category;
`determining a divisor in accordance with the category
`and means for encoding the category index and the
`corresponding to the estimation error, dividing the data 60 remainder into corresponding codes and outputting the
`codes.
`D by the divisor and generating a remainder of a result
`of the dividing, and encoding the category index and
`A seventh aspect of this invention provides an appa-
`the remainder and thereby generating the Coded DC
`ratus for decoding which comprises means for decoding
`data in accordance with the category index and the
`input data into a category index and a remainder; means
`65 for generating an estimate from previous output data;
`remainder.
`A fourth aspect of this invention provides a method
`means for generating a divisor in accordance with the
`of decoding which comprises the steps of decoding
`category index; means for generating an offset in accor-
`Coded AC data into quantized AC coefficients; decod-
`dance with the divisor and the estimate, the offset being
`
`Page 9 of 27
`
`

`
`6
`being currently decoded and decoded data in an error(cid:173)
`free block adjoining the block being currently decoded.
`A tenth aspect of this invention provides an apparatus
`for efficient encoding which comprises means for en(cid:173)
`coding input data into a variable-length code, and
`means for arranging the variable-length code into a data
`store region of a given capacity and outputting the
`variable-length code, the improvement comprising
`means for encoding the input data into variable-length
`code words each having a first portion and a second
`portion, wherein the first portion includes a bit pattern
`which can determine a code length of the related word,
`and wherein the second portion is equal to a part of the
`related word except the first portion; means for collect(cid:173)
`ing the first portions into a group and arranging the
`group of the first portions into the data store region; and
`means for collecting the second portions into a group
`and arranging the group of the second portions into the
`data store region.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`5
`equal to the divisor multiplied by an integer; and means
`for adding the offset and the remainder and thereby
`generating new output data in accordance with the
`offset and the remainder; wherein the estimate-generat(cid:173)
`ing means comprises means for, in the presence of a 5
`control signal, generating the estimate by a prediction
`process which differs from a prediction process in an
`encoding side, and wherein the offset-generating means
`comprises means for, in the presence of the control
`signal, generating the offset so as to increase a correla- 10
`tion between output data and the estimate.
`An eighth aspect of this invention provides an appa(cid:173)
`ratus for efficient encoding which comprises means for
`collecting a given number of bits of input data into a
`block; means for subjecting the input data in a block to 15
`given transform and thereby generating a DC coeffici(cid:173)
`ent and AC coefficients from the input data in a block;
`means for quantizing the DC coefficient into data D;
`means for encoding the data D into Coded DC data;
`means for quantizing the AC coefficients; and means for 20
`encoding results of quantizing the AC coefficients into
`FIG. l(a) is a block diagram of an efficient encoding
`Coded AC data; wherein the data-D encoding means
`apparatus which uses an efficient encoding method
`comprises means for generating an estimate of the data
`according to a first embodiment of this invention.
`FIG. l(b) is a block diagram of a decoding apparatus
`D, means for generating an estimation error which is 25
`equal to a difference between the data D and the esti-
`which uses a decoding method according to the first
`mate means for classifym· g the estimation error and
`embodiment of this invention.
`FIG. 2 is a block diagram of a decoding apparatus
`generating a category index indicative of a category
`which uses a decoding method according to the second
`corresponding to the estimation error, means for deter-
`mining a divisor in accordance with the category corre- 30 embodiment of this invention.
`FIG. 3(a) is a block diagram of the prediction circuit
`sponding to the estimation error, means for dividing the
`data D by the divisor and generating a remainder of a
`of FIG. 2.
`result of the dividing, and means for encoding the cate-
`FIG. 3(b) is a block diagram of the quotient data
`gory index and the remainder and thereby generating
`calculation circuit of FIG. 2.
`the Coded DC data in accordance with the category 35
`FIG. 4(a) is a block diagram of an efficient encoding
`index and the remainder.
`apparatus which uses an efficient encoding method
`A ninth aspect of this invention provides an apparatus
`according to a third embodiment of this invention.
`FIG. 4(b) is a block diagram of a decoding apparatus
`for decoding which comprises means for decoding
`Coded AC data into quantized AC coefficients; means
`which uses a decoding method according to the third
`for decoding Coded DC data into a quantized DC coef- 40 embodiment of this invention.
`FIG. 5 is a block diagram of a prediction circuit in
`ficient; means for dequantizing the quantized AC coeffi-
`cients into AC coefficients; means for dequantizing the
`one of the decoding circuits in FIG. 4(b).
`quantized DC coefficient into a DC coefficient; means
`FIG. 6(a) is a block diagram of a transmitter using an
`for subjecting the AC coefficients and the DC coeffici-
`efficient encoding method according to a fourth em-
`ent to inverse transform and thereby generating first 45 bodiment of this invention.
`FIG. 6(b) is a block diagram of a receiver using a
`decoded data in a block in accordance with the AC
`coefficients and the DC coefficient; and means for rear-
`decoding method according to the fourth embodiment
`ranging the first decoded data in a block into second
`of this invention.
`FIG. 7 is a diagram showing an example of the ar-
`decoded data which has a data arrangement corre-
`sponding to a data arrangement of input data to be 50 rangement of variable-length code words in a data store
`encoded in an encoding side; wherein the Coded-DC-
`region in the fourth embodiment of this invention.
`FIG. 8 is a diagram showing an example of the ar-
`data decoding means comprises means for decoding the
`Coded DC data into a category index and a reminder,
`rangement of variable-length code words in a data store
`means for generating an estimate in accordance with
`region according to a prior-art design.
`decoded quantized data, means for generating a divisor 55
`in accordance with the category index, means for gen(cid:173)
`erating an offset in accordance with the divisor and the
`estimate, the offset being equal to the divisor multiplied
`by an integer, means for adding the offset and the re(cid:173)
`mainder and thereby generating new quantized data in 60
`accordance with the offset and the remainder; wherein
`the estimate-generating means comprises means for, in
`the presence of a control signal, generating the estimate
`by a prediction process which differs from a prediction
`process in an encoding side, and wherein the offset- 65
`generating means comprises means for, in the presence
`of the control signal, generating the offset so as to in(cid:173)
`crease a correlation between decoded data in a block
`
`5,392,037
`
`DESCRIPTION OF THE FIRST PREFERRED
`EMBODIMENT
`According to a first embodiment of this invention, a
`method of efficient encoding executes a sequence of
`processing steps 1-4 as follows.
`1. An estimate (a prediction value) Pi for actual input
`data Di (an unsigned integer) is obtained. The estimate
`Pi is subtracted from the actual input data Di, thereby
`calculating an estimation error (a prediction error) Si. It
`should be noted that Di denotes an i-th input data. In the
`following description, reference characters with the
`adscript "i" denote data corresponding to the input data
`Di.
`
`Page 10 of 27
`
`

`
`5,392,037
`
`7
`2. The estimation error Si is classified in accordance
`with the value thereof by referring to a given classifica(cid:173)
`tion table. Specifically, a decision is made regarding
`which of rages (categories) the estimation error Si is
`present in. The category index (the category number) Ji 5
`denoting the range or the category where the estima(cid:173)
`tion error Si is present is determined. When the upper
`limit value and the lower limit value of the estimation
`error range corresponding to the category index Ji are
`represented by SXi and SNi respectively, the following 10
`relation is satisfied.
`
`SNi;;;si;;;SXi
`
`(!)
`
`Furthermore, a calculation is given of divisor data OUi 15
`which corresponds to the category index Ji in a one-to(cid:173)
`one manner, and which satisfies the following relation,
`
`8
`input data Di is previously subjected to code conversion
`into a corresponding unsigned integer.
`Next, a description will be given of a decoding
`method according to the first embodiment of this inven(cid:173)
`tion. As described previously, in the efficient encoding
`method of the first embodiment of this invention, the
`category index Ji and the remainder data Ei are en(cid:173)
`coded and are then transmitted. As understood from the
`equation (3), the data Di can be recovered in accor(cid:173)
`dance with the divisor data Oui, the remainder data Ei,
`and the quotient data Ni. The category index Ji and the
`divisor data Oui correspond to each other in a one-to(cid:173)
`one manner. Thus, a table of the conversion from cate(cid:173)
`gory indexes to divisor data is previously prepared, and
`the divisor data Oui is calculated from the transmitted
`category index Ji by referring to the data conversion
`table. The remainder data Ei is transmitted. Accord(cid:173)
`ingly, the data Di is obtained provided that the quotient
`data Ni is calculated.
`The quotient data Ni is calculated as follows. The
`relation (1) and the equation (3) are combined to elimi(cid:173)
`nate the term of the estimation error Si, and the follow(cid:173)
`ing relation is obtained.
`
`OIB>m-~
`
`~
`20
`
`3. The input data Di is divided by the divisor data
`OUi, and the remainder Ei is calculated according to
`modulo operation. Thus, the following equation is satis(cid:173)
`fied.
`
`Di=Ni-OUi+Ei
`
`(3)
`
`where Ni denotes the quotient.
`4. The category index Ji and the remainder data Ei
`are encoded.
`An example of the classification table used in the
`above-mentioned processing step 1 is shown in the fol(cid:173)
`lowing.
`
`TABLE 1
`
`ESTIMATION
`ERROR
`RANGE ~SN - S2Q
`SNi
`SXi
`-255
`-128
`-64
`-127
`-63
`-32
`-31
`-16
`-15
`-8
`-7
`-4
`-3
`-2
`-1
`-1.
`0
`0
`1
`1
`3
`2
`4
`7
`8
`15
`16
`31
`32
`63
`64
`127
`128
`255
`
`CATEGORY
`INDEX
`Ji
`-8
`-7
`-6
`-5
`-4
`-3
`-2
`-1
`0
`1
`2
`3
`4
`5
`6
`7
`8
`
`REMAIND-
`ERDATA
`DIVISOR WORD
`DATA
`LENGTH
`OUi
`Mi
`
`128
`64
`32
`1
`8
`4
`2
`1
`1
`1
`2
`4
`8
`16
`32
`64
`128
`
`7
`6
`5
`4
`3
`2
`1
`0
`0
`0
`1
`2
`3
`4
`5
`6
`7
`
`The relation (4) and the equation (3) are combined to
`eliminate the term of the data Di, and the following
`relation is obtained.
`
`(4)
`
`25
`
`30
`
`(Pi+SNi-E1)/0Ui;aNi;a(Pi+SXi-E1)/0Ui
`
`(5)
`
`The estimate Pi is calculated from the previously-recov(cid:173)
`ered data Dk, where "k" denotes an integer smaller
`35 than the integer "i". Each of values SXi and SNi corre(cid:173)
`sponds to a category index Ji in a one-to-one manner.
`Thus, a table of the conversion from category indexes
`to data SXi and SNi is previously prepared, and the
`values SXi and SNi are calculated from the category
`40 index Ji by referring to the data conversion table. Since
`the quotient data Ni denotes an integer and the differ(cid:173)
`ence "(SXi-SNi)/OUi" between the left-hand term
`and the right-hand term of the relation (5) is smaller
`than 1 as understood from the relation (2), the quotient
`45 data Ni which satisfies the relation (5) could be uniquely
`determined. Accordingly, the quotient data Ni is deter(cid:173)
`mined by calculating the smallest integer which satisfies
`the following left-hand portion of the relation (5).
`
`50
`
`(Pi+SNi-Ez)!OUi;aN;
`
`(6)
`
`55
`
`Table 1 shows the category indexes Ji, the correspond(cid:173)
`ing estimation error ranges (SNi-SXi), the correspond(cid:173)
`ing divisor data OUt, and the word lengths Mi of the
`remainder data Ei.
`As is made clear from the above description, in the 60
`efficient encoding method of the first embodiment of
`this invention, the category index which is higher-bit
`information of the estimation error is encoded and also
`the remainder data which is lower-bit information of the
`input data is encoded before they are transmitted.
`In cases where input data Di represents a signed inte(cid:173)
`ger, the efficient encoding method of the first embodi(cid:173)
`ment of this invention is carried out provided that the
`
`65
`
`The quotient data Ni may also be determined by calcu(cid:173)
`lating the greatest integer which satisfies the following
`right-hand portion of the relation (5).
`
`N