United States Patent 1191
`Kato
`
`US005392037A
`[11] Patent Number:
`[45] Date of Patent:
`
`5,392,037
`Feb. 21, 1995
`
`[54] METHOD AND APPARATUS FOR
`ENCODING AND DECODING
`[75] Inventor:
`Shiro Kato, Osaka, Japan
`[73] Assignee: Matsushita Electric Industrial (10.,
`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
`Feb. 21, 1992 [JP]
`
`Japan . . . . .
`. . . .. 3-302847
`Japan .................................. .. 4-34659
`
`[51] Int. Cl.6 .......................................... .. H03M 13/00
`[52] U.S. Cl. ...................................... .. 341/67; 341/94;
`341/76
`[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
`ated. An estimation error which is equal to a difference
`between the estimate and the input data is calculated.
`The estimation error is classi?ed, 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 de?ning a range of the category.
`The category index and the remainder are encoded into
`corresponding codes which are outputted. In a decod
`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
`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
`mate.
`
`26 Claims, 6 Drawing Sheets
`
`101
`i
`
`_
`01
`1
`
`11162
`
`‘1112
`PREDICT
`
`10:2 51
`-
`
`H104
`1CLASSIFY
`
`REMAIN
`CALC
`OUILMIN
`105
`
`conv
`
`1.111111 ENCODE
`1107
`_
`E1 |- ---------------- --—|
`\;
`_
`0E1
`:
`SUB
`-
`;
`;
`ENCODE
`;
`l
`{110
`E
`E
`1
`5
`i
`a
`i108
`5J1:
`i
`:
`: c_
`
`_111
`C_J1 3
`11192
`“PX
`SUB
`ENCODE
`
`. Pi
`
`L _________________ --_1 1
`
`Apple Inc. Exhibit 1003 Page 1
`
`

`
`US. Patent
`
`Feb. 21, 1995
`
`Sheet 1 of 6
`
`5,392,037
`
`FIG. 7(a)
`
`E.
`
`I06
`7
`REMAIN
`cALc
`OUi.Mi''\__
`105\
`#104
`‘ASSIFY
`I CL
`
`conv
`
`101
`a‘
`
`01
`5
`
`_
`£102 10?( $1
`'
`
`PREDICT
`
`Pi
`
`MAIN IJECODE
`1,113
`Fun‘ ----------- "(g-{"1-
`=
`TIP-‘H
`=
`5
`sue
`?
`5
`DECODE
`E
`H9
`"
`112?
`-
`i
`1 ,BUFFER
`C51
`;
`:
`MEMORY
`;
`c1;
`;
`Ch ‘120
`5
`:
`sue
`g
`g
`- DECODE (J
`5
`1:
`_L':J___J
`
`l_ _____________________ ..__!
`
`MAIN ENCODE
`1101
`
`SUB
`ENcouE
`1110
`
`1 ---------------- --—|
`CE1
`:
`s
`;
`;
`E
`:
`5
`,1"
`5108
`1092 (mg
`SUB’ LMPX :
`ENCODE
`; C_
`
`-
`;
`%
`:
`5
`.5
`‘J1:
`:
`
`i_ _________________ --_1 1
`
`‘
`
`-
`
`SYNTHESIS CKT
`E16 126
`-
`
`QUOTIENT CALC
`
`Apple Inc. Exhibit 1003 Page 2
`
`

`
`U.S. Patent
`
`Feb. 21, 1995
`
`Sheet 2 of 6
`
`5,392,037
`
`lqi’
`OUOTIENT
`
`CALC
`
`Sx
`
`j
`
`203
`
`,
`
`PREDICT
`
`FIG. 5
`
`1 PREDICT CKT
`
`_______ __
`
`-
`
`505
`
`OUANTIZE
`
`CONTROL SIGNAL
`
`Apple Inc. Exhibit 1003 Page 3
`
`

`
`US. Patent
`
`Feb. 21, 1995
`
`Sheet 3 of 6
`
`5,392,037
`
`F/G. 3(a)
`
`PREDICT CKT
`
`Pi, P'i
`
`CONTROL SIGNAL
`
`FIG. 3/17)
`
`Ei
`
`QUOTIENT CALC
`203
`F """"""""""""" "I """ m!
`
`OUj
`
`i
`
`‘ nouuo -—§—-+ Ni
`
`SXj
`
`230s
`
`< Pi, P'i
`
`L ____ “3.01 _________________ __ ___---_i
`couméi SIGNAL
`
`Apple Inc. Exhibit 1003 Page 4
`
`

`
`US. Patent
`
`Feb. 21, 1995
`
`Sheet 4 of6
`
`5,392,037
`
`FIG. 4 (a)
`
`4m
`
`H402
`
`V
`
`.
`
`DDi(h)
`
`404 Di
`
`mi 4444514 5
`H403
`'
`
`405
`
`544641105
`
`?ci
`r ‘408 409
`
`/
`AC'(k)
`cci
`/
`1 - QUANTIZE 5
`ENCODE W
`1
`Bi(k)
`
`442
`\ i
`“E005 K OUANTIZE
`Ci~ ‘411 01
`
`DE-
`
`410
`
`4
`
`-
`~DT1 Dc"
`r’ 1
`
`441
`~
`
`DELAY
`
`419
`
`420
`
`‘k
`DE
`, k BLOCKING
`41a
`DDi'(h)
`V‘
`
`446
`»’
`o >—— INVERSE
`HGT
`
`1
`
`4
`56-; SEPARATE
`A1~M413
`(415
`BE
`DECODE B’QUANTIZE
`
`AC'i(k)
`
`Apple Inc. Exhibit 1003 Page 5
`
`

`
`U.S. Patent
`
`Feb. 21, 1995
`
`Sheet 5 of 5
`
`5,392,037
`
`628 £630F "' '1
`
`Apple Inc. Exhibit 1003 Page 6
`
`

`
`U.S. Patent
`
`la2b.eF
`
`5991
`
`Sheet 6 of 6
`
`Nat
`
`
`
`zommamacs<._.<o
`
`
`
`E.u.zo_Eo._ozomm9533%5mzo_Eo._5%.S53
`
`az:_m3"5zo:H_m_oaz:_~_3Hazo_Sm_~_a
`
`.5?QQEQQDI
`
`uz_E<5
`
`
`
`zoama3.5«:3Ham.
`
`_.
`
`
`
`zmao¢AIl.|...|||.|Il|IIlIII
`
`<#_<..uzzaz8zo_B#_a
`
`U8%;
`
`lH!
`
`Apple Inc. Exhibit 1003 Page 7
`
`

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

`
`l0
`
`15
`
`20
`
`25
`
`5,392,037
`4
`3
`ing Coded DC data into a quantized DC coef?cient;
`USE DIGITAL VTR”, IEEE Trans. CE-35, No. 3,
`dequantizing the quantized AC coef?cients into AC
`Aug. 1989, pp 450457).
`coef?cients; dequantizing the quantized DC coef?cient
`SUMMARY OF THE INVENTION
`into a DC coefficient; subjecting the AC coef?cients
`and the DC coef?cient to inverse transform and thereby
`It is a ?rst object of this invention to provide an im
`proved method of ef?cient encoding.
`generating ?rst decoded data in a block in accordance
`with the AC coef?cients and the DC coef?cient; and
`It is a second object of this invention to provide an
`improved method of decoding.
`rearranging the ?rst 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
`improved apparatus for ef?cient encoding.
`sponding to a data arrangement of input data to be
`encoded in an encoding side; wherein the Coded-DC
`It is a fourth object of this invention to provide an
`improved apparatus for decoding.
`data decoding step comprises the sub steps of decoding
`A ?rst aspect of this invention provides a method of
`the Coded DC data into a category index and a remain
`ef?cient encoding which comprises the steps of generat
`der, generating an estimate in accordance with decoded
`quantized data, generating a divisor in accordance with
`ing an estimate of input data; calculating an estimation
`the category index, generating an offset in accord;race
`error which is equal to a difference between the esti
`with the divisor and the estimate, the offset being equal
`mate and the input data; classifying the estimation error
`to the divisor multiplied by an integer, adding the offset
`and generating a category index indicative of a category
`corresponding to the estimation error; dividing the
`and the remainder and thereby generating new quan
`tized data in accordance with the offset and the remain
`input data by a divisor and generating a remainder of a
`der; wherein the estimate-generating step comprises the
`result of the dividing, the divisor being equal to a given
`sub step of, in the presence of a control signal, generat
`value which is greater than a difference between an
`ing the estimate by a prediction process which differs
`upper limit value and a lower limit value de?ning a
`range of the category; and encoding the category index
`from a prediction process in an encoding side, and
`wherein the offset-generating step comprises the sub
`and the remainder into corresponding codes and out
`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‘
`decoded data in an error-free block adjoining the block
`input data into a category index and a remainder; gener
`being currently decoded.
`ating an estimate from previous output data; generating
`A ?fth aspect of this invention provides a method of
`a divisor in accordance with the category index; gener
`ef?cient encoding which comprises the steps of encod
`ating an offset in accordance with the divisor and the
`ing input data into a variable-length code, and arranging
`estimate, the offset being equal to the divisor multiplied
`by an integer; and adding the offset and the remainder
`the variable-length code into a data store region of a
`given capacity and outputting the variable-length code,
`and thereby generating new output data in accordance
`the improvement comprising the steps of encoding the
`with the offset and the remainder; wherein the estimate
`input data into variable-length code words each having
`generating step comprises the sub step of, in the pres
`a first portion and a second portion, wherein the ?rst
`ence of a control signal, generating the estimate by a
`prediction process which di?'ers from a prediction pro
`portion includes a bit pattern which can determine a
`cess in an encoding side, and wherein the offset-generat
`code length of the related word, and wherein the sec
`ing step comprises the sub step of, in the presence of the
`ond portion is equal to a part of the related word except
`the ?rst portion; collecting the ?rst portions into a
`control signal, generating the offset so as to increase a
`group and arranging the group of the ?rst portions into
`correlation between output data and the estimate.
`the data store region; and collecting the second portions
`A third aspect of this invention provides a method of
`ef?cient encoding which comprises the steps of collect
`into a group and arranging the group of the second
`45
`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 coef?cient and AC coeffi
`for ef?cient 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
`an estimation error which is equal to a difference be
`DC data; quantizing the AC coef?cients; and encoding
`tween the estimate and the input data; means for classi
`results of quantizing the AC coef?cients 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
`divisor and generating a remainder of a result of the
`ating an estimation error which is equal to a difference
`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
`remainder into corresponding codes and outputting the
`corresponding to the estimation error, dividing the data
`D by the divisor and generating a remainder of a result
`codes.
`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
`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 coef?cients; decod
`dance with the divisor and the estimate, the offset being
`
`40
`
`35
`
`55
`
`65
`
`Apple Inc. Exhibit 1003 Page 9
`
`

`
`6
`being currently decoded and decoded data in an error
`free block adjoining the block being currently decoded.
`A tenth aspect of this invention provides an apparatus
`for ef?cient encoding which comprises means for en
`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 ?rst portion and a second
`portion, wherein the ?rst 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 ?rst portion; means for collect
`ing the ?rst portions into a group and arranging the
`group of the ?rst 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
`FIG. 1(a) is a block diagram of an ef?cient encoding
`apparatus which uses an e?icient encoding method
`according to a ?rst embodiment of this invention.
`FIG. 1(b) is a block diagram of a decoding apparatus
`which uses a decoding method according to the ?rst
`embodiment of this invention.
`FIG. 2 is a block diagram of a decoding apparatus
`which uses a decoding method according to the second
`embodiment of this invention.
`FIG. 3(a) is a block diagram of the prediction circuit
`of FIG. 2.
`FIG. 3(b) is a block diagram of the quotient data
`calculation circuit of FIG. 2.
`FIG. 4(a) is a block diagram of an efficient encoding
`apparatus which uses an efficient encoding method
`according to a third embodiment of this invention.
`FIG. 4(b) is a block diagram of a decoding apparatus
`which uses a decoding method according to the third
`embodiment of this invention.
`FIG. 5 is a block diagram of a prediction circuit in
`one of the decoding circuits in FIG. 4(b).
`_ FIG. 6(a) is a block diagram of a transmitter using an
`efficient encoding method according to a fourth em
`bodiment of this invention.
`FIG. 6(b) is a block diagram of a receiver using a
`decoding method according to the fourth embodiment
`of this invention.
`FIG. 7 is a diagram showing an example of the ar
`rangement of variable-length code words in a data store
`region in the fourth embodiment of this invention.
`FIG. 8 is a diagram showing an example of the ar
`rangement of variable-length code words in a data store
`region according to a prior-art design.
`
`20
`
`5,392,037
`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
`ing 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-generating means
`comprises means for, in the presence of the control
`signal, generating the offset so as to increase a correla
`tion between output data and the estimate.
`An eighth aspect of this invention provides an appa
`ratus for e?icient 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
`given transform and thereby generating a DC coeffici
`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
`encoding results of quantizing the AC coef?cients into
`Coded AC data; wherein the data-D encoding means
`comprises means for generating an estimate of the data
`D, means for generating an estimation error which is
`equal to a difference between the data D and the esti
`mate means for classifying the estimation error and
`generating a category index indicative of a category
`corresponding to the estimation error, means for deter
`mining a divisor in accordance with the category corre
`sponding to the estimation error, means for dividing the
`data D by the divisor and generating a remainder of a
`result of the dividing, and means for encoding the cate
`gory index and the remainder and thereby generating
`the Coded DC data in accordance with the category
`index and the remainder.
`A ninth aspect of this invention provides an apparatus
`for decoding which comprises means for decoding
`Coded AC data into quantized AC coe?icients; means
`for decoding Coded DC data into a quantized DC coef
`?cient; means for dequantizing the quantized AC coef?
`cients into AC coef?cients; means for dequantizing the
`quantized DC coef?cient into a DC coef?cient; means
`for subjecting the AC coefficients and the DC coeffici
`ent to inverse transform and thereby generating ?rst
`45
`decoded data in a block in accordance with the AC
`coefficients and the DC coef?cient; and means for rear
`ranging the ?rst decoded data in a block into second
`decoded data which has a data arrangement corre
`sponding to a data arrangement of input data to be
`encoded in an encoding side; wherein the Coded-DC
`data decoding means comprises means for decoding the
`Coded DC data into a category index and a reminder,
`means for generating an estimate in accordance with
`decoded quantized data, means for generating a divisor
`in accordance with the category index, means for gen
`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
`mainder and thereby generating new quantized data in
`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
`generating means comprises means for, in the presence
`of the control signal, generating the offset so as to in
`crease a correlation between decoded data in a block
`
`10
`
`15
`
`25
`
`35
`
`55
`
`65
`
`DESCRIPTION OF THE FIRST PREFERRED
`EMBODIMENT
`According to a ?rst 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.
`
`Apple Inc. Exhibit 1003 Page 10
`
`

`
`5,392,037
`7
`8
`input data Di is previously subjected to code conversion
`2. The estimation error Si is classi?ed in accordance
`into a corresponding unsigned integer.
`with the value thereof by referring to a given classi?ca
`tion table. Speci?cally, a decision is made regarding
`Next, a description will be given of a decoding
`which of rages (categories) the estimation error Si is
`method according to the ?rst embodiment of this inven
`present in. The category index (the category number) Ji
`tion. As described previously, in the ef?cient encoding
`denoting the range or the category where the estima
`method of the ?rst embodiment of this invention, the
`tion error Si is present is determined. When the upper
`category index Ji and the remainder data Ei are en
`limit value and the lower limit value of the estimation
`coded and are then transmitted. As understood from the
`error range corresponding to the category index Ji are
`equation (3), the data Di can be recovered in accor
`represented by SXi and SNi respectively, the following
`dance with the divisor data Oui, the remainder data Bi,
`relation is satis?ed.
`and the quotient data Ni. The category index Ji and the
`divisor data Oui correspond to each other in a one-t0
`one manner. Thus, a table of the conversion from cate
`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
`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
`nate the term of the estimation error Si, and the follow
`ing relation is obtained.
`
`SNiéSiéSXi
`
`(1)
`
`Furthermore, a calculation is given of divisor data OUi
`15
`which corresponds to the category index Ji in a one-to
`one manner, and which satis?es the following relation,
`
`OUi>SXi~SNi
`
`(2)
`
`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
`?ed.
`
`Di=Ni-OUi+Ei
`
`25
`
`(3)
`
`Pi+Sni§Di§Pi+SXi
`
`(4)
`
`'
`where Ni denotes the quotient.
`4. The category index Ji and the remainder data Ei
`are encoded.
`An example of the classi?cation table used in the
`above-mentioned processing step 1 is shown in the fol
`lowing.
`
`The relation (4) and the equation (3) are combined to
`eliminate the term of the data Di, and the following
`relation is obtained.
`
`(Pi+SNi—E0/0Ui§M§(Pi+SM—El)/0l?
`
`(5)
`
`The estimate Pi is calculated from the previously-recov
`ered data Dk, where “k” denotes an integer smaller
`than the integer “i”. Each of values SXi and SNi corre
`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
`index Ji by referring to the data conversion table. Since
`the quotient data Ni denotes an integer and the differ
`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
`data Ni which satis?es the relation (5) could be uniquely
`determined. Accordingly, the quotient data Ni is deter
`mined by calculating the smallest integer which satis?es
`the following left-hand portion of the relation (5).
`
`35
`
`45
`
`50
`
`(Pi+SM'—Ei)/OUi§M
`
`(6)
`
`TABLE 1
`
`CATEGORY
`INDEX
`Ji
`
`ESTIMATION
`ERROR
`RANGE QSN ~ S3!
`SNi
`SXi
`
`REMAIND
`ER DATA
`DIVISOR WORD
`DATA LENGTH
`OUi
`Mi
`
`— 8
`—7
`—6
`—5
`—4
`—3
`—2
`——l
`0
`l
`2
`3
`4
`5
`6
`7
`8
`
`— 255
`— 127
`—63
`—3l
`— l5
`—7
`— 3
`—l
`0
`l
`2
`4
`8
`l6
`32
`64
`128
`
`— 128
`—64
`—32
`— l6
`— 8
`—4
`—2
`— l _
`0
`l
`3
`7
`l5
`3 1
`63
`127
`255
`
`128
`64
`32
`1
`8
`4
`2
`l
`l
`l
`2
`4
`8
`l6
`32
`64
`128
`
`7
`6
`5
`4
`3
`2
`l
`0
`0
`0
`l
`2
`3
`4
`5
`6
`7
`
`55
`
`Table 1 shows the category indexes Ji, the correspond
`ing estimation error ranges (SNi-SXi), the correspond
`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 ?rst 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
`ger, the ef?cient encoding method of the ?rst embodi
`ment of this invention is carried out provided that the
`
`65
`
`The quotient data Ni may also be determined by calcu
`lating the greatest integer which satis?es the following
`right-hand portion of the relation (5).
`
`Ni§(Pi+SXi—Ei)/OUi
`
`(7)
`
`In this way, the quotient data Ni can be calculated by
`using either of the relations (5), (6), and (7). Since the
`calculation of the quotient data Ni which uses the rela
`tion (7) allows omitting the ?gures below the decimal
`point from the result of the division in the right-hand
`side of the relation (7), this calculation can be easily
`carried out.
`The determined quotient data Ni is substituted for the
`corresponding term of the equation (3), and therefore
`the data Di is obtained. In other words, the data Di is
`recovered by the decoding process.
`
`Apple Inc. Exhibit 1003 Page 11
`
`

`
`5
`
`15
`
`25
`
`30
`
`35
`
`45
`
`0Ui=2Mi=SXi-NI+1
`
`(8)
`
`5,392,037
`9
`10
`In summary, the decoding method of the ?rst em
`data CH. The sub encoding circuit 110 encodes the
`bodiment of this invention executes a sequence of pro
`remainder data Ei into coded data CEi. The multiplex
`cessing steps 1-5 as follows.
`ing circuit 111 combines the coded data CJi and the
`1. The transmitted codes (data) are decoded into the
`coded data CEi into the multiplexed coded data Ci.
`category index Ji and the remainder data Bi.
`The efficient encoding apparatus of FIG. 1(a) oper
`2. The estimate Pi is calculated from the previously
`ates as follows. The input data Di is fed via the input
`recovered data Dk, where “k” denotes an integer
`terminal 101 to the prediction circuit 102, the subtrac
`smaller than the integer “i”