throbber
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”

This document is available on Docket Alarm but you must sign up to view it.


Or .

Accessing this document will incur an additional charge of $.

After purchase, you can access this document again without charge.

Accept $ Charge
throbber

Still Working On It

This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.

Give it another minute or two to complete, and then try the refresh button.

throbber

A few More Minutes ... Still Working

It can take up to 5 minutes for us to download a document if the court servers are running slowly.

Thank you for your continued patience.

This document could not be displayed.

We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.

Your account does not support viewing this document.

You need a Paid Account to view this document. Click here to change your account type.

Your account does not support viewing this document.

Set your membership status to view this document.

With a Docket Alarm membership, you'll get a whole lot more, including:

  • Up-to-date information for this case.
  • Email alerts whenever there is an update.
  • Full text search for other cases.
  • Get email alerts whenever a new case matches your search.

Become a Member

One Moment Please

The filing “” is large (MB) and is being downloaded.

Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.

Your document is on its way!

If you do not receive the document in five minutes, contact support at support@docketalarm.com.

Sealed Document

We are unable to display this document, it may be under a court ordered seal.

If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.


Access Government Site

We are redirecting you
to a mobile optimized page.





Document Unreadable or Corrupt

Refresh this Document
Go to the Docket

We are unable to display this document.

Refresh this Document
Go to the Docket