United States Patent (19)
`Keith
`
`IIIHIHIIIHIIII
`USOO528.5402A
`(11)
`Patent Number:
`5,285,402
`45
`Date of Patent:
`Feb. 8, 1994
`
`(54 MULTIPLYLESS DISCRETE COSINE
`TRANSFORM
`75 Inventor: Michael Keith, Holland, Pa.
`73 Assignee: Intel Corporation, Santa Clara, Calif.
`21 Appl. No.: 796,317
`22 Filed:
`Nov. 22, 1991
`51) int. C. ................................................ G06F 7/38
`52 U.S. Cl. .....................
`58) Field of Search ................................ 364/725,726
`(56)
`References Cited
`U.S. PATENT DOCUMENTS
`4,449,194 5/1984 Wilhelm .............................. 364/725
`4,791,598 12/1988 Liou et al. ........................... 364/725
`4,829,465 5/1989 Knauer et al. ..
`... 364/725
`5,054,103 10/1991 Yasuda et al. .................. 364/725 X
`FOREIGN PATENT DOCUMENTS
`0250152A2 12/1987 European Pat. Off. .
`OTHER PUBLICATIONS
`"The Multiply-Free Chen Transform-A Rational Ap
`proach to JPEG", Allen and Blonstein, Picture Coding
`Symposium, 1991, pp. 237-240.
`Primary Examiner-Tan V. Mai
`Attorney, Agent, or Firm-Carl L. Silverman; James E.
`Jacobson; William H. Murray
`
`ABSTRACT
`57
`A method is disclosed for performing a discrete cosine
`transform on a transform input value wherein the dis
`crete cosine transform has a plurality of predetermined
`transform coefficients. A number N1 of shift operations
`is determined independently of the transform input
`value in order to provide a set of N of shift operations.
`A number N2 of add operations is determined indepen
`dently of the transform input value in order to provide
`a set of N2 add operations. The transform input value is
`operated upon only by the N1 shift operations and the
`N2 add operations to provide a discrete cosine trans
`form output value without any multiplication. This
`method may be applied to both forward and inverse
`discrete cosine transforms. The transform coefficients
`are simplified coefficients which are provided by trun
`cating and modifying prior art transform coefficients.
`This simplification is adapted to provide coefficients
`which require fewer than a predetermined number of
`shift and add operations in order to determine an ap
`proximation of the product which would result from a
`multiplication by the coefficient. The simplification of
`the coefficients causes degradation of a video image
`transformed using the simplified coefficients. Therefore
`the simplification is constrained to cause an acceptable
`amount of image degradation.
`
`20 Claims, 5 Drawing Sheets
`
`52a.
`
`150
`
`56
`
`
`
`52
`
`154a
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1022, p. 1
`
`

`

`U.S. Patent
`
`Feb. 8, 1994
`
`Sheet 1 of 5
`
`5,285,402
`
`10
`
`
`
`
`
`
`
`-
`
`2 FORWARD
`g"
`
`17
`
`16
`
`
`
`
`
`
`
`
`
`
`
`14
`
`Y-4-
`
`INVERSE
`DCT
`
`AIG 7
`Arfor Aff
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1022, p. 2
`
`

`

`U.S. Patent
`
`Feb. 8, 1994
`
`Sheet 2 of 5
`
`5,285,402
`
`
`
`AIG, 2A
`Arior Aff
`
`
`
`40b 40c
`
`32
`
`A/G 2C
`Aprior Aff
`
`36a
`
`
`
`36
`
`
`
`F/G, 2D
`Arfor Aff
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1022, p. 3
`
`

`

`U.S. Patent
`
`Feb. 8, 1994
`
`Sheet 3 of 5
`
`5,285,402
`
`
`
`76
`
`X - RND UP p.
`Y - RND DNIY
`
`80
`
`OUT
`OFRANGE
`?
`
`Y
`
`84
`
`FOUND
`
`88
`
`A/G 3
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1022, p. 4
`
`

`

`U.S. Patent
`
`Feb. 8, 1994
`
`Sheet 4 of 5
`
`5,285,402
`
`
`
`
`
`SUPPRESS
`LEADING ZEROS
`
`
`
`
`
`124
`
`SUPPRESS
`RALING ZEROS
`
`
`
`REMAINING
`BITS 1
`?
`
`136
`
`SHIF CRITERA
`NOMET
`
`68
`
`
`
`AIG, 4.
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1022, p. 5
`
`

`

`U.S. Patent
`
`Feb. 8, 1994
`
`Sheet 5 of 5
`
`5,285,402
`
`
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1022, p. 6
`
`

`

`1.
`
`5,285,402
`
`MULTIPLYLESS DISCRETE COSINE
`TRANSFORM
`
`1. FIELD OF THE INVENTION
`This invention relates to the field of discrete cosine
`transforms and in particular to a discrete cosine trans
`form method having lower computational require
`nets.
`
`2
`-continued
`where
`
`C(k)
`
`1/sqrt(2) for k = 0
`= 1
`for k > 0
`
`and cosval(x,y) = cos(2x - 1)"T/16)
`
`with
`
`p(i,j) = -128 to +127
`f(u, v) = -1024 to -- 1023.
`
`O
`
`5
`
`35
`
`2. BACKGROUND ART
`The two-dimensional discrete cosine transform is a
`pair of mathematical equations that transforms one
`NXNarray of numbers to or from another NXNarray
`of numbers. The first array typically represents an
`NXN array of spatially determined pixel values which
`form the digital image. The second array is an array of
`discrete cosine transform coefficients which represent
`the image in the frequency domain. This method of
`20
`representing the image by the coefficients of its fre
`quency components is a special case of the discrete
`Fourier transform. The discrete Fourier transform is the
`discrete version of the classic mathematical Fourier
`transform wherein any periodic waveform may be ex
`25
`pressed as a sum of sine and cosine waves of different
`frequencies and amplitudes. The discrete cosine trans
`form, like the Fourier transform, is thus a transform
`which transforms a signal from the time domain into the
`frequency domain and vice versa.
`30
`It is well known in the art to use these discrete cosine
`transform coefficients for image compression. In combi
`nation with other techniques, such as color subsam
`pling, quantization, Huffman coding and run-length
`coding, the discrete cosine transform can compress a
`digital color image by a factor of approximately thirty
`to one with virtually no noticeable image degradation.
`Because of its usefulness in image compression, the
`discrete cosine transform is an integral part of several
`image compression standards used by international stan
`dards committees such as the International Standards
`Organization.
`There are two basic discrete cosine transform equa
`tions. The first basic equation is the forward discrete
`cosine transform which transforms the pixel values into
`45
`the discrete cosine transform coefficients. The second
`basic equation is the inverse discrete cosine transform
`which transforms the discrete cosine transform coeffici
`ents back into pixel values. Most applications of the
`discrete cosine transform for images use eight-by-eight
`50
`arrays wherein N therefore has a value of eight. Assum
`ing then that N has the value of eight when performing
`the transforms, where p(i,j) are the values of the pixel
`array and f(u,v) are the values of the discrete cosine
`transform coefficients, the equations of the discrete
`55
`cosine transforms are as follows.
`The forward discrete cosine transform may be ex
`pressed as:
`
`The forward and reverse discrete cosine transform
`operations of Equation (1) and Equation (2) may be
`represented by the diagram shown in prior art FIG. 1.
`Forward discrete cosine transform 12 of Equation (1)
`transforms eight-by-eight array 10 of pixel values in the
`spatial domain to an eight-by-eight array 16 of discrete
`cosine transform coefficients in the frequency domain.
`Inverse discrete cosine transform 14 performs the re
`verse transformation. Discrete cosine transform coeffi
`cient array 16 represents the frequency content of the
`p(i,j) function, separately, in both the horizontal and
`vertical directions. Since discrete cosine transform 12
`operates on two-dimensional array 10, it is referred to as
`two-dimensional discrete cosine transform 12. In the
`result of two-dimensional transform 12 the horizontal
`dimension of coefficient array 16 represents the hori
`Zontal frequency and the vertical dimension of coeffici
`ent array 16 represents the vertical frequency.
`In f(u,v) array 16 or frequency domain array 16, fre
`quencies increase with increasing value of the (u,v)
`indices. Discrete cosine transform coefficient 17 in the
`upper left corner of array 16 corresponds to zero fre
`quency in both horizontal and vertical directions, and is
`referred to as the DC term of frequency domain array
`16. From forward discrete cosine transform Equation
`(1), it can be seen that f(0,0) coefficient 17 is equal to the
`average of all sixty-four f(i,j) pixel values, multiplied by
`a scaling factor. It is well known in the art that f(0,0)
`coefficient 17 or DC term 17 has this characteristic. The
`other sixty-three (u,v) coefficients within discrete co
`sine transform coefficient array 16 represent amplitudes
`of cosine waves of increasing frequency and are there
`fore AC coefficients.
`Referring now to prior art FIGS. 2A-D, there are
`shown eight-by-eight spatial domain arrays 30, 32, 34,
`and 36 of pixels and their corresponding frequency
`domain discrete cosine transform coefficient arrays 38,
`40, 42 and 44. Darker squares in spatial domain arrays
`30, 32, 34, 36 represent darker pixels. It will be under
`stood that the relative darkness of squares in arrays 30,
`32, 34, 36,38, 40, 42, 44 is represented by the density of
`stippling. Darker squares in frequency domain arrays
`38, 40, 42, 44 represent smaller discrete cosine transform
`coefficients and lighter squares represent larger coeffi
`cients.
`The image represented by spatial domain array 30 is
`thus completely flat since all squares in array 30 are the
`same level of darkness. Therefore discrete cosine trans
`form array 38, corresponding to spatial domain array
`30, contains only a single DC term 38a. All other sixty
`three coefficients of discrete cosine transform array 38
`are Zero and are thus represented as black with the
`brightest density of stippling.
`The image represented by spatial domain array 32
`however, has a slowly varying horizontal gradient.
`Therefore, discrete cosine transform array 40 or fre
`
`7
`7
`fu, v) = (1/4)C(u)C(y) X X cosyai(iu)cosyal(iv)p(i,j)
`
`Equation (1)
`
`The inverse discrete cosine transform may be ex
`pressed as:
`
`Equation (2)
`7
`7
`X C(u)C(v)cosval(i, u)cosval(ifu, v)
`p(i,j) = (1/4) X.
`re
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1022, p. 7
`
`

`

`Equation (3)
`
`10
`
`30
`
`45
`
`50
`
`Thus straight forward calculation of the inverse dis
`crete cosine transform of Equation (2) requires sixty
`four floating-point multiplications per pixel. This is
`approximately five million multiplications for a modest
`size three-hundred twenty by two-hundred forty pixel
`image.
`However, there are methods known in the prior art to
`reduce this computational requirement by several or
`ders of magnitude. One method known in the prior art
`reduces the computation required to sixteen integer
`multiplications per pixel. Another prior art method,
`based upon further mathematical manipulation, can
`calculate the discrete cosine transforms 12, 14 using
`only two and three-quarters multiplications per pixel.
`However, even these methods still require too much
`computation to perform discrete cosine transforms 12,
`14 for many applications.
`These prior art methods must allow for the fact that
`the dynamic range of the fu,v) values is eight times the
`range of the p(i,j) values, it 1024 versus-128. This is
`required in order to preserve all the information in the
`p(i,j) spatial domain values when they are converted to
`the f(u,v) values of the frequency domain. Additionally,
`these prior art methods must allow for the fact that both
`the p(i,j) values of the spatial domain and f(u,v) values
`of the frequency domain are signed numbers. If forward
`discrete cosine transform 12 is used on eight-bit pixel
`values, for example, which have a numerical range of
`zero to two hundred fifty five, then one hundred twenty
`eight must subtracted from the pixel values to cause
`them to have the required range of negative one hun
`dred twenty eight to positive one hundred twenty
`seven. This subtraction must be performed prior to
`using forward discrete cosine transform 12. Similarly,
`after performing inverse discrete cosine transform 14
`one hundred twenty eight must be subtracted to return
`the pixel values to their proper range.
`Another known improvement reduces the number of
`multiplications to sixteen per pixel, as previously de
`scribed. This improvement was developed by determin
`ing that inverse discrete cosine transform Equation (2)
`may be rewritten as:
`
`5,285,402
`3
`4.
`quency domain 40, corresponding to spatial domain
`u,v). The K(i,j, u,v) constant may even include the () in
`array 32, contains not only DC term 40a but also con
`these constants. Thus Equation (2) becomes:
`tains a small number of low-frequency horizontal fre
`quency terms 40b,c. The high-frequency horizontal
`terms and all vertical frequency terms of discrete cosine
`transform array 40, however, are all zero.
`The image represented by spatial domain array 34
`contains sharp horizontal edge 34a, Sharp horizontal
`edge 34a causes all eight vertical frequency bands rep
`resented by squares 42a-h of discrete cosine transform
`coefficient array 42 to indicate energy. Because hori
`zontal edge 34a of spatial domain array 34 is encoun
`tered when tracing vertically through the image repre
`sented by array 34, and all eight cosine waves repre
`sented by squares 42a-h are needed to produce a sharp
`15
`edge after forward discrete cosine transform 12 is per
`formed. Thus all eight terms 42a-h of corresponding
`discrete cosine coefficient transform array 42 are non
`zero and are indicated as lighter than the remaining
`squares of array 42 with a lower density of stippling. All
`fifty six horizontal frequencies of corresponding dis
`crete cosine transform array 42 are zero and are repre
`sented as dark squares because the image of spatial do
`main array 34 is smooth in the horizontal direction.
`The image represented by spatial domain array 36
`25
`contains a single isolated pixel 36a. This produces en
`ergy in all sixty-four discrete cosine transform coeffici
`ents of corresponding discrete cosine coefficient trans
`form array 44. This energy is produced in all sixty-four
`cosine terms of frequency domain array 44 because
`isolated pixel 36a of spatial domain array 36 produces a
`sharp transition in both the horizontal and vertical di
`rections. Thus sixty-four cosine terms must be provided
`to produce a single-pixel two-dimensional impulse func
`tion as represented by pixel 36a of spatial domain array
`35
`36.
`Another important feature of discrete cosine trans
`forms 12, 14 is that they are reversible, information
`preserving, transformations. This means that exactly the
`same image information is present in spatial domain
`p(i,j) array 10 as in frequency domain f(u,v) array 16.
`The information in arrays representations 10, 16 is
`merely represented in different forms. Both array repre
`sentations 10, 16 contain exactly the same information,
`and they can be converted from one representation to
`the other by applying the appropriate discrete cosine
`transformation 12, 14.
`It is this reversible feature of discrete cosine trans
`forms 12, 14 which permits them to be very useful for
`image compression. Each eight-by-eight p(i,j) array,
`such as spatial domain arrays 30, 32, 34, and 36, contains
`values representing an eight-by-eight portion of an in
`age. For image compression arrays 30, 32, 34, and 36
`may each be transformed into corresponding eight-by
`eight f(u,v) arrays 38, 40, 42, and 44 in the frequency
`domain using forward discrete cosine transform 12 as
`set forth as Equation (1). Various compression algo
`rithms may then be applied to f(u,v) arrays 38, 40, 42,
`and 44. To reconstruct the original images represented
`by spatial domain arrays 30, 32, 34, and 36, the compres
`sion algorithm is reversed to yield f(u,v) arrays 38, 40,
`42, and 44. Inverse discrete cosine transform 14, set
`forth as Equation (2), is then applied to f(u,v) arrays 38,
`40, 42, and 44 to provide p(u,v) arrays 30, 32, 34, and 36.
`Referring to Equation (2), it can be seen that each
`p(i,j) is a result of a double summation. For a given i,j,u,
`and v, all the constants, C(u), C(v), cosval(i,u), and
`cosval(j,v), may be combined into one constant K(i,j-
`
`Equation (4)
`7
`p(i,j) = 1/2 i. C(u)cosval(i.u.) z o Cy)cosyaliy)f(u,v)
`
`e
`
`y
`
`55
`
`65
`
`Both two-dimensional inverse discrete cosine transform
`14 and forward discrete cosine transform 12 are separa
`ble transforms. Thus, two-dimensional inverse discrete
`cosine transform 14 can be separated into two one
`dimensional inverse discrete cosine transforms. Each of
`the one-dimensional transforms is being of the form:
`
`p(i) = (1/2) i. C(u)cosyai(iu)f(u)
`
`Equation (5)
`
`Equation (5) represents a one-dimensional discrete
`cosine transform between two eight-element arrays p(i)
`and f(u). The separability of two-dimensional discrete
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1022, p. 8
`
`

`

`5,285,402
`5
`6
`cosine transforms 12, 14 thus means that they can be
`puting the one-dimensional discrete cosine transform
`using Equation (1). For example, when computing each
`calculated as sixteen one-dimensional discrete cosine
`transforms. One-dimensional inverse discrete cosine
`p(i) value there is a multiply f(4) by the same constant
`transforms are first performed on each of the eight rows
`(M=4) all eight times in the fifth column of Table II.
`of f(u,v) matrix 16 to form a resulting intermediate array
`These multiplies differ only by their sign. Similarly, f(0),
`(not shown). One-dimensional discrete cosine trans
`set forth in the first column of Table II, is always multi
`forms are then performed on each of the eight columns
`plied by M=0 when performing this transform. Addi
`of the resulting intermediate matrix. The result of these
`tionally, f(2) is multiplied by only two different con
`operations is the same p(i,j) coefficient array 10 as com
`stants, either by M=2 or by M = 6.
`puted using inverse discrete cosine transform 14.
`Thus in this method all eight p(i) values are calcu
`According to Equation (5), there are sixty-four multi
`lated at the same time using one calculation. Only the
`plications in a one-dimensional discrete cosine transfer.
`minimum number of multiplications of f(u) values by
`Sixteen one-dimensional discrete cosine transforms are
`constants are performed and an overall savings are
`required for two-dimensional discrete cosine transforms
`achieved by reusing these intermediate results. Algo
`12, 14. Thus a total of sixteen times sixty-four multipli
`rithms of this type are called fast cosine transform algo
`cations ar required for two-dimensional discrete cosine
`rithms, and are analogous to the well-known fast fourier
`transform 12, 14 using this prior art method. Since there
`are sixty-four pixels this equals sixteen multiplications
`transform.
`per pixel. Thus the number of multiplications per pixel
`Further improvement may be obtained using a
`method requiring eleven multiplications instead of six
`is reduced by a factor of four in this prior
`Still further improvement in the number of multipli
`ty-four for a one-dimensional discrete cosine transform.
`cations required may be obtained by considering the
`Such a method is taught in Loeffler, Ligtenberg, and
`sixty four constants used by the one-dimensional dis
`Moschytz in "Practical Fast 1-D DCT Algorithms
`crete cosine transform as set forth in Equation (5). Ig
`With 11 Multiplications," IEEE Transactions, 1989. It
`noring the factor () in Equation (5), as well as the
`can be proven mathematically that eleven multiplica
`25
`values of C(u), consider only the cosval(i,u) values.
`tions is the minimum possible for a one-dimensional fast
`From the original equations:
`cosine transform as taught in the prior art. Using this
`improvement a two-dimensional discrete cosine trans
`form only requires 1116/64 = 2.75 multiplications per
`pixel.
`Thus, many improvements upon basic forward dis
`crete cosine transform 12 and inverse discrete cosine
`transform 14 are known in the prior art. However, in all
`of these prior art methods, in spite of the benefits of the
`improved discrete cosine transforms 12, 14 for image
`compression, many clock cycles are still required to
`perform the remaining multiplications. Calculations of
`prior art forward discrete cosine transform 12 and in
`verse discrete cosine transform 14 which eliminate some
`multiplications are still very time consuming because of
`these remaining multiplications. It will be understood
`that prior art improved discrete cosine transforms are
`still very expensive because on most processors a multi
`ply instruction is significantly more time consuming
`than an add operation or a shift operation. On proces
`sors that do not have a hardware multiplier, the differ
`ence in the number of cycles is very dramatic. This
`difference may be as much as a factor often or twenty.
`It will be understood by those skilled in the art that the
`computational time requirements of inverse discrete
`cosine transform 14 are very similar to the computa
`tional time requirements of forward discrete cosine
`transform 12.
`SUMMARY OF THE INVENTION
`A method is disclosed for performing a discrete co
`sine transform on a transform input value wherein the
`discrete cosine transform has a plurality of predeter
`mined transform coefficients. A number N1 of shift
`operations is determined only in accordance with the
`transform coefficients in order to provide a set of N1
`shift operations. A number N2 of add operations is de
`termined only in accordance with the transform coeffi
`cients to provide a set of N2 add operations. The trans
`form input value is operated upon only by the N1 shift
`operations and the N2 add operations to provide a dis
`crete cosine transform output value.
`
`Since M = (2i-1)u, the values in row i of Table I are
`45
`multiples (2i + 1). Each of these corresponds to the co
`sine of M*T/16. But the cosine function is periodic and
`symmetrical in various ways as well. Thus, the cosine of
`M*T/16, for any M, is equal to either the positive or
`negative cosine of MT/16 with M between zero and
`50
`seven. For example, cos(35'ar/16)=cos(3*n/16), since
`the cosine function repeats every thirty-two values of
`M. Thirty values of M corresponds to 2p(i). Thus, the
`array of Table I may be reduced to the cosines set forth
`in Table II.
`
`cos(2i + 1) unt/16)
`cos(Mn/16)
`
`re
`
`5
`5
`25
`35
`45
`55
`65
`75
`
`6
`8
`30
`42
`54
`66
`78
`90
`
`7
`21
`35
`49
`63
`77
`9
`105
`
`O
`
`15
`
`20
`
`30
`
`35
`
`55
`
`where M = (2i + 1)u.
`Referring now to Table I, the values of M for all
`sixty-four constants are set forth,
`TABLE
`3
`4.
`9
`12
`15
`20
`2.
`28
`27
`36
`33
`44
`39
`52
`45
`60
`
`O
`O
`O
`O
`O
`O
`0
`O
`
`2
`6
`10
`4
`8
`22
`26
`30
`
`3
`s
`7
`9
`
`3
`5
`
`O
`O
`O
`O
`O
`O
`O
`O
`
`3
`5
`7
`-7
`-5
`-3
`-l
`
`2
`6
`-6
`-2
`-2
`-6
`-6
`2
`
`TABLE I
`5
`3.
`4.
`-7
`- 4 -
`- 1
`- 4
`7
`-5
`4.
`3
`5
`4.
`-3
`- 4
`-7
`- 4
`1
`4.
`-5
`
`7
`-3
`
`7
`6
`-5
`-2
`3
`2
`-6 -
`-6
`2
`-2
`6
`
`-3
`5
`-7
`
`Within Table II, a negative sign before a value of M
`65
`indicates that a constant is -cos(Mar/16) rather than
`cos(M*T/16). From the contents of Table II, it can be
`seen that there is a great deal of redundancy when com
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1022, p. 9
`
`

`

`5
`
`10
`
`15
`
`20
`
`7
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 shows a schematic representation of prior art
`forward and inverse discrete cosine transforms applied
`to eight-by-eight arrays representative of spatial domain
`information and frequency domain information.
`FIGS. 2A-D show a schematic representation of
`prior art forward and inverse discrete cosine transforms
`applied to eight-by-eight arrays representative of spatial
`domain information and frequency domain information
`wherein the spatial domains are provided with varying
`intensity distributions.
`FIG. 3 shows a sample algorithm for providing the
`simplified discrete cosine transform coefficients of the
`present invention.
`FIG. 4 shows a more detailed block diagram repre
`sentation of a test performed in the algorithm of FIG. 3.
`FIG. 5 shows a discrete cosine transform device for
`performing the multiplyless inverse discrete cosine
`transform of the present invention.
`DETAILED DESCRIPTION OF THE
`INVENTION
`Referring now to FIG. 3, there is shown a flow chart
`representation of discrete cosine transform constant
`simplification method 50 of the present invention. In
`order to greatly decrease the amount of time necessary
`to perform discrete cosine transforms 12, 14, constant
`simplification method 50 provides coefficients which
`permit the discrete cosine transform system of the pres
`30
`ent invention to provide a one-dimensional fast cosine
`transform method that uses no multiplications at all.
`In order to provide simplified transform constants,
`discrete cosine transform constant simplification
`method 50 truncates the least significant bits of the
`constants of discrete cosine transforms 12, 14. This
`simplification results in a small loss in arithmetic accu
`racy. This loss in arithmetic accuracy is limited to an
`amount which produces acceptable image quality. In
`order to limit the loss of accuracy in this manner, the
`number of bits truncated is selected to be less than what
`would cause unacceptable image degradation.
`Selected remaining bits of the truncated constants are
`then modified by constant simplification method 50.
`After this modification, input values from frequency
`45
`domain array 16 are multiplied by the simplified con
`stants to provide the resulting product values of spatial
`domain array 10. However, the modification of the
`constants in the system of the present invention is
`adapted to permit the determination of these resulting
`product values by applying two or fewer shift opera
`tions, along with any required add operations, to the
`values of frequency domain array 16. Thus the product
`values resulting from multiplying the input values by
`the simplified constants, may be obtained using only
`55
`shift and add operations without any multiplication
`operations. It will therefore be understood that using
`the system of the present invention, inverse discrete
`cosine transform may be performed without any multi
`plications.
`This modification of the truncated constants by con
`stant simplification method 50 may result in a further
`decrease in arithmetic accuracy. However, the modifi
`cation of constant simplification method 50 is adapted
`to result in no noticeable degradation of image quality.
`Shift criteria limiting the number of shifts to a value
`other than two may be used depending on the amount of
`image degradation which may be tolerated in a particu
`
`5,285,402
`8
`lar application. A further consideration with respect to
`the number of shifts is the amount of hardware or soft
`ware which may be used to implement multiplyless
`discrete cosine transform 14 using constants provided
`by constant simplification method 50.
`In this manner, both discrete cosine transforms 12, 14
`may be performed with only shift operations and add
`operations. In particular, the new simplified constants
`provided by constant simplification method 50 of the
`present invention are adapted to perform reverse dis
`crete cosine transform 14. However the system of the
`present invention may be readily adapted to provide
`simplified constants for performing forward discrete
`cosine transform 12.
`Within the accuracy limitations required in an appli
`cation, the number of shift operations and add opera
`tions required to perform discrete cosine transforms 12,
`14 in the method of the present invention depends only
`upon the predetermined discrete cosine transform coef
`ficients themselves. In particular the number of shift and
`add operations required to perform discrete cosine
`transforms 12, 14 with these simplified constants is com
`pletely independent of any input values upon which
`discrete cosine transforms 12, 14 may be performed.
`Thus the shift and add operations of the system of the
`present invention may be hardwired when implemented
`in electronic circuitry or implemented as constants in
`arithmetic routines by computer software.
`It is possible to reduce the number of shift operations
`and add operations required to perform discrete cosine
`transforms 12, 14 in this manner without noticeable
`degradation in picture quality because the calculations
`performed by the simplified constants are performed
`while transforming either into or out of the frequency
`domain. Therefore if slight errors are made in perform
`ing the calculations of inverse discrete cosine trans
`forms 12, 14, the resulting visual errors are spread over
`all sixty-four pixels in any resulting eight-by-eight spa
`tial domain arrays 10 of pixel values. This prevents the
`resulting visual errors from being very noticeable. Be
`cause the information content of most common images
`is inherently low-frequency, these errors are made less
`noticeable by the fact that they tend to occur at higher
`frequencies.
`The eleven multiplication constants of a fast cosine
`transform algorithm are shown in Table III.
`TABLE III
`cos(3*n/16) + sin(3*T/16)
`sin(37/16) - cos(3r/16)
`cos(3*T/16)
`cos(T/16) -- sin(n/16)
`sin(ra6) - cos(TA16)
`cos(T/16)
`N2 (cos(6'7/16) + sin(6'7/16)
`W2 (sin(6'n/16) - cos(6'n/16)
`W2 (cos(6*n/16)
`2cos(4T/16)
`2'cos (47/16)
`
`25
`
`35
`
`50
`
`7.
`
`0.
`1.
`
`65
`
`Using discrete cosine transform constant simplification
`method 50 of the present invention, the values of Table
`III may be replaced with the simpler inverse discrete
`
`Unified Patents, LLC v. Elects. & Telecomm. Res. Inst., et al.
`
`Ex. 1022, p. 10
`
`

`

`.60
`-0.40
`0.0
`1.40
`-0.co
`1.00
`1.e0
`0.co
`0.80
`180
`80
`
`O
`
`35
`
`5,285,402
`10
`formed within test diamond 64. For example, when i has
`cosine transform constants shown in Table IV, ex
`pressed as fixed point sixteen bit hexadecimal values.
`the value one and X passes the shift criteria of test
`diamond 64 with a value 1.6, the first new constant is
`TABLE IV
`assigned the value 1.6 as shown in Table IV.
`After a value is assigned to new constanti the counter
`is incremented in block 100. A determination is then
`made in decision diamond 96 whether all the constants
`of the transform have been simplified by constant sim
`plification method 50 to provide the simplified new
`constants for performing discrete cosine transforms 12,
`14 according to the multiplyless method of the present
`invention. If all the constants of Table III have been
`processed, execution proceeds to terminal.92 and dis
`crete cosine transform constant simplification method
`50 is completed.
`If neither the value of X nor the value of Y meets the
`shift criteria as determined by test diamond 64, execu
`tion of discrete cosine transform constant simplification
`method 50 proceeds by way of false test line 68 to
`rounding block 76. In rounding block 76, the RNDUP
`and RNDDN routines are performed upon the values of
`X and Y, respectively. Routines RNDUP and RNDDN
`are adapted to return the next highest and the next
`lowest values of X and Y respectively. Thus, for exam
`ple, if X has the value 1.7 prior to execution of rounding
`block 76, X is assigned the value 1.8 during execution of
`rounding block 76. If Y has the value 1.6 before the
`execution of rounding block 76, Y is assigned the value
`1.5 during the execution of rounding block 76.
`As a further example, when i has the value four,
`constant i has the value 1.2 d as determined from Table
`III. Prior to execution of rounding block 76, when exe
`cution of constant simplification method 50 proceeds to
`rounding block 62, X is assigned the rounded up value
`1.3 by routine RNDUP when RNDUP operates upon
`constant i. In the same manner, Y is assigned the
`rounded down value 1.2 by the routine RNDDN in
`rounding block 62. The value of X, 1.3, may thus be
`represented by the binary string 0001.0011 and the
`value of Y may be represented by the binary string
`0001.0010. Neither of these binary strings passes the test
`criteria of test diamond 64 because the product resulting
`from multiplying X and Y by a multiplicand value can
`not be obtained using three or fewer shifts of the multi
`plicand value. Thus, execution proceeds by way of false
`test line 68 to rounding block 76, where routine
`RNDUP operates upon the value of X and assigns the
`value 1.4 to X. The routine RNDDN operates upon Y
`and assigns the value 1.1 to Y.
`A determination is then made in out-of-range decision
`diamond 80 whether the values of X or Y are out of
`range. The more times that rounding block 76 is exe
`cuted within constant simplification method 50, the less
`accuracy is obtained when performing discreet cosine
`transforms 12, 14 using the new constants determined
`by method 50. This occurs be