IN THE UNITED STATES PATENT AND TRADEMARK OFFICE
`
`––––––––––
`
`BEFORE THE PATENT TRIAL AND APPEAL BOARD
`
`––––––––––
`
`Unified Patents Inc.
`Petitioner,
`
`v.
`
`GE Video Compression, LLC,
`Patent Owner.
`
`––––––––––
`
`Case No. IPR2019-00726
`
`U.S. 6,943,710
`
`––––––––––
`
`PETITION FOR INTER PARTES REVIEW
`
`OF U.S. PATENT NO. 6,943,710
`
`

`

`IPR2019-00726 Petition
`U.S. Patent No. 6,943,710
`
`TABLE OF CONTENTS
`
`I.
`
`II.
`III.
`IV.
`
`V.
`
`VI.
`
`2.
`
`C.
`D.
`
`Introduction ...................................................................................................... 1
`Introduction to BAC .............................................................................. 1
`A.
`Probability Modeling ............................................................................. 2
`B.
`1.
`Static and Adaptive Statistical Probability Modeling ...................... 2
`Table-Based Probability Modeling .................................................. 4
`2.
`BAC Tutorial ......................................................................................... 5
`The Challenged Claims are Obvious ...................................................13
`1.
`The ’710 Patent Admits that Replacing Multiplication
`Operations with Table Lookups was Known .................................14
`Printz Teaches the Only Allegedly Novel Feature of the
`Challenged Claims—a Quantization Index ...................................15
`Grounds for Standing .....................................................................................16
`Identification of ChallengeS ..........................................................................16
`U.S. 6,943,710 ...............................................................................................17
`Summary .............................................................................................17
`A.
`Level of Ordinary Skill in the Art .......................................................23
`B.
`Claim Construction..............................................................................23
`C.
`1.
`“interval division table” (claims 25, 33, and 60-63) ......................23
`Prior Art .........................................................................................................24
`Overview of Howard (EX1004) ..........................................................24
`A.
`Overview of Printz (EX1005) .............................................................28
`B.
`Overview of Kimura (EX1006)...........................................................31
`C.
`Challenged Claims .........................................................................................34
`Ground 1: Claims 25, 33, and 60-63 are Obvious Over Howard in
`A.
`view of Printz ......................................................................................34
`1.
`Motivation to Combine Howard with Printz .................................34
`Independent Claim 25 ....................................................................42
`2.
`Independent Claims 60 and 62 .......................................................58
`3.
`
`- i -
`
`

`

`IPR2019-00726 Petition
`U.S. Patent No. 6,943,710
`
`B.
`
`4.
`Independent Claim 33 ....................................................................59
`5.
`Independent Claims 61 and 63 .......................................................60
`Ground 2: Claims 25, 33, and 60-63 are Obvious Over Kimura in
`view of Printz ......................................................................................61
`1.
`Motivation to Combine Kimura with Printz ..................................61
`Independent Claim 25 ....................................................................65
`2.
`Independent Claims 60 and 62 .......................................................76
`3.
`Independent Claim 33 ....................................................................77
`4.
`Independent Claims 61 and 63 .......................................................78
`5.
`Conclusion .....................................................................................................78
`Mandatory Notices and Fees .........................................................................79
`
`VII.
`VIII.
`
`- ii -
`
`

`

`IPR2019-00726 Petition
`U.S. Patent No. 6,943,710
`
`EXHIBIT LIST
`
`Exhibit No.
`
`Description
`
`1001
`1002
`1003
`1004
`
`1005
`1006
`1007
`
`1008
`
`1009
`
`1010
`
`1011
`
`1012
`
`1013
`
`1014
`1015
`1016
`1017
`
`1018
`
`U.S. Patent No. 6,943,710 to Marpe et al. (“the ’710 Patent”)
`Prosecution File History for the ’710 Patent
`Declaration of Dr. Immanuel Freedman
`Howard, “Design and analysis of fast text compression based on
`quasi-arithmetic coding,” Journal of Information Processing and
`Management, 30(6), 777–790 (1994) (“Howard”)
`U.S. Patent No. 5,592,162 to Printz et al. (“Printz”)
`U.S. Patent No. 6,351,569 to Kimura et al. (“Kimura”)
`Howard, “Practical Implementations of Arithmetic Coding,”
`Image and Text Compression,” J.A. Storer, ed., Kluwer
`Academic Publishers, Norwell, MA, 85-112 (1992) (“Howard
`2”)
`for Data Compression,”
`“Arithmetic Coding
`Howard,
`Proceedings of the IEEE (July 1994) (“Howard 3”)
`Marpe, “Fast Adaptive Binary Arithmetic Coding (M Coder),”
`http://iphome.hhi.de/marpe/mcoder.htm
`(accessed Nov. 12,
`2018).
`Moffat, “Arithmetic Coding Revisited,” ACM Transactions on
`Information Systems, Vol. 16, No. 3 (July 1998), Pages 256-294.
`Duttweiler, Probability Estimation in Arithmetic Adaptive-
`Huffman Entropy Coders
`Excerpts from Microsoft Computer Dictionary, Fourth Edition,
`Microsoft Press (1999).
`Langdon, Jr., “An Introduction to Arithmetic Coding,” IBM J.
`Res. Develop, Vol. 28, No. 2 (March 1984)
`Nelson, Data Compression Book, 2nd Ed. (1996).
`Westwater, Real-Time Video Compression Techniques
`Declaration of Jacob Munford
`Rissanen, “A Multiplication Free Multialphabet Arithmetic
`Code,” IEE Transactions on Communications, Vol. 37, No. 2
`(Feb. 1989)
`Pennebaker, “An Overview of the Basic Principles of the Q-
`Coder Adaptive Binary Arithmetic Coder,” IBM J. Res.
`Develop., Vol. 32, No. 6 (Nov. 1988).
`
`- iii -
`
`

`

`IPR2019-00726 Petition
`U.S. Patent No. 6,943,710
`
`Exhibit No.
`
`Description
`
`1019
`1020
`1021
`1022
`
`University of Michigan Library MARC Record
`Petitioner’s Voluntary Interrogatory Responses
`ITU-T Recommendation H.264 (May 2003)
`WorldCat Record for the Journal Information Processing and
`Management
`
`- iv -
`
`

`

`IPR2019-00726 Petition
`U.S. Patent No. 6,943,710
`
`I.
`
`INTRODUCTION
`Petitioner Unified Patents Inc. (“Petitioner” or “Unified”) requests inter
`
`partes review of Claims 25, 33, and 60-63 (the “Challenged Claims”) of U.S.
`
`Patent 6,943,710 (EX1001). The ’710 Patent purports to claim a “new”
`
`implementation of the half-century-old “binary arithmetic coding” (“BAC”)
`
`algorithm using an implementation of “Table-Aided Interval Separation.” EX1001
`
`at 1:17-26, 1:54-60. But the implementation claimed by the ’710 Patent was well-
`
`known before the priority date of the ’710 Patent.
`
`A.
`
`Introduction to BAC
`
`BAC is one type of digital data compression algorithm. EX1003 ¶¶70-72.
`
`BAC is known as a “lossless entropy” coder, which is a category of digital data
`
`compression coding that “minimize[s] space in the representation of random
`
`sequences of symbols . . . based upon the probability [of] the symbol,” while
`
`enabling full-fidelity reproduction of the input at the decoder. EX1015, 81;
`
`EX1003 ¶73. Entropy coders, such as BAC, are therefore often applied as the final
`
`stage compression process in higher-order lossy compression techniques, such as
`
`the popular H.263, H.264/MPEG-4-AVC (H.264) and High Efficiency Video
`
`Coding (HEVC/H.265) standards for video compression. EX1003 ¶73.
`
`BAC uses a probability model to replace the entire stream of input
`
`characters with a single output number within a numerical interval (e.g., the
`
`1
`
`

`

`IPR2019-00726 Petition
`U.S. Patent No. 6,943,710
`
`interval between 0 and 1, or [0, 1)1). EX1014, 81; EX1003 ¶74. BAC is generally
`
`regarded as providing better compression than other entropy coders, with the
`
`disadvantage of requiring a larger amount of processing to perform. EX1003 ¶74;
`
`EX1014, 96.
`
`B.
`
`Probability Modeling
`
`An accurate probability model is of central importance to all entropy coding
`
`schemes because it informs the selection of the output code. EX1003 ¶¶75-77;
`
`EX1014, 15, 19. The amount of compression an encoder can provide is directly
`
`dependent on the probability model. EX1003 ¶¶76-77; EX1014, 15.
`
`1.
`
`Static and Adaptive Statistical Probability Modeling
`
`To ensure the accuracy of the probability model, most entropy coders use a
`
`“statistical” probability model, which tracks the probability of a symbol based on
`
`what symbols appeared previously in the input stream. EX1014, 17. The simplest
`
`forms of statistical probability modelling use a static table of probabilities that is
`
`created by performing a first pass on the input data before the coding phase.
`
`EX1003 ¶78; EX1014, 19. For example, a static table could be pre-computed on
`
`the input string “BAB” by tallying up the number of occurrences of each symbol
`
`and dividing by the total number of symbol occurrences to determine the symbol
`
`1 Intervals will be expressed for convenience using the [x, y) notation to express an
`
`interval from and including x up to, but not including, y.
`
`2
`
`

`

`IPR2019-00726 Petition
`U.S. Patent No. 6,943,710
`
`probabilities. EX1003 ¶78; EX1014, 19. In this example, the symbol “B” has a
`
`probability of 2/3, and the symbol A has a probability of 1/3. EX1003 ¶78;
`
`EX1014. 19. However, in addition to the extra pass on the input data set, the
`
`“static” approach requires that the probability model be passed with the coded data
`
`for use in decoding, which represents considerable overhead that usually eliminates
`
`any gains achieved by the compression. EX1003 ¶78; EX1014. 19.
`
`Thus, statistical modeling research before the priority date of the ’710 Patent
`
`was focused on adaptive models that continually update the statistics in the
`
`probability model as new characters are read in and coded or decoded and
`
`therefore do not require a first pass of the input data. EX1014, 19-20; EX1003 ¶79.
`
`For example, the “scaled frequency” method is one adaptive method that
`
`recalculates the symbol probability in the same manner as the “static” approach
`
`discussed above as each symbol is input to the coder and without requiring a first
`
`pass on the input data. EX1003 ¶79; EX1001, 10:10-28.
`
`For example, to calculate the probability model for the input string “BAB”,
`
`the probability model might be initialized so that the symbol “A” is favored (i.e.,
`
`2/3 for “A” and 1/3 for “B”). EX1003 ¶80. After the first “B” in the “BAB” string
`
`is input and coded, the probability model is recalculated to account for the input
`
`“B” by summing the total occurrences of B (now 2, since our model was initialized
`
`to 1 for “B” and 2 for “A”) and dividing that number by the new total number of
`
`3
`
`

`

`IPR2019-00726 Petition
`U.S. Patent No. 6,943,710
`
`both symbol occurrences (i.e., 2 for “A” and 2 for “B” = 4). EX1003 ¶80. In the
`
`second coding iteration (just before coding the “A” in “BAB”) the probability
`
`model is updated so that the probability of A is 1/2 and the probability of B is also
`
`1/2. EX1003 ¶80. This process repeats after the next input A so that the probability
`
`of A is 3/5 and the probability of B is 2/5, and so on. EX1003 ¶80. This is the same
`
`implementation as the prior art method described in the ’710 Patent. EX1001,
`
`10:10-28 (discussing implementation of prior art Duttweiler (EX1011, 5));
`
`EX1003 ¶81.
`
`2.
`
`Table-Based Probability Modeling
`
`Researchers next realized that “significant implementation advantage[s]” can
`
`be obtained if the scaled frequency method becomes “table driven,” or
`
`implemented in a state table where the “current state augmented by the current
`
`observation [, or input symbol,] indexes to a table” that “provides both the next
`
`state and its associated probability estimate.” EX1011, 8; EX1001, 10:42-67
`
`(discussing prior art Duttweiler (EX1011)); EX1001, 3:10-11 (discussing prior art
`
`Howard (EX1007)); EX1003 ¶82. One example of such a table driven probability
`
`model is shown below:
`
`4
`
`

`

`IPR2019-00726 Petition
`U.S. Patent No. 6,943,710
`
`See EX1004, Table 5 (prior art table-based probability model and basis for
`
`example above). The probabilities at states 1-3 correspond to the scaled frequency
`
`example above. EX1003 ¶82. For example, after encoding the first “B” in the
`
`string “BAB” at state 1, the table indicates that the “Next State if B Input” is 2,
`
`which provides probabilities of 1/2 for both “A” and “B”. EX1003 ¶82. This is the
`
`same probability calculated after the first coding iteration in the adaptive example
`
`above. EX1003 ¶82.
`
`C.
`
`BAC Tutorial
`
`BAC leverages the concept of probability modeling. EX1003 ¶83. At a high
`
`level, BAC recursively divides a current interval according to the probability
`
`assigned by the model. EX1003 ¶83. This process is called “interval division.”
`
`EX1003 ¶83. Interval division is performed for each input character until the entire
`
`string of input characters is represented with a single output number within a final
`
`interval. EX1014, 81; EX1003 ¶83. For example, using BAC with an initial
`
`interval of [0, 1), it is possible to encode the binary string “BAB” with a binary
`
`output code .11001 (about 4/5) that falls within a final interval [23/30, 5/6) such
`
`5
`
`

`

`IPR2019-00726 Petition
`U.S. Patent No. 6,943,710
`
`that the decoder can perfectly recreate the input string using the same model.
`
`EX1003 ¶83. Data compression is therefore achieved because the single output
`
`number can usually be represented in fewer bits than the input bit stream. EX1003
`
`¶83.
`
`BAC involves two basic steps: (A) subdivision of the current interval into
`
`two subintervals, or partial intervals, based on the probability model and selecting
`
`the partial interval corresponding to the input character (“Interval Division”), and
`
`(B) determining the next current interval by updating the “code point” and “range”
`
`to reflect the selected partial interval and advancing the probability state based on
`
`the input event (“Code Point Update”). EX1003 ¶84. These steps are repeated
`
`until the last input character is encoded to obtain a final interval. The compressed
`
`output is then taken as a number within that final interval.
`
`An example is helpful in explaining the steps of BAC.2 Here, the binary
`
`string “BAB” is encoded within the initial interval [0, 1). At initialization, both the
`
`encoder and decoder are provided with a probability model, such as the adaptive
`
`table driven model shown below:
`
`2 This entire example including the interval images reproduced below, is adapted
`
`from Ex. 1008, 4.
`
`6
`
`

`

`IPR2019-00726 Petition
`U.S. Patent No. 6,943,710
`
`The current interval can be thought of as a range on a number line that is
`
`divided according to the probability that a given symbol will be input. EX1003
`
`¶86. When performing interval division, BAC aims to transpose the probability
`
`distribution given by the model onto that number line. EX1003 ¶86. The divided
`
`interval corresponding to the input symbol, or “event”, is selected and set as the
`
`new current interval for the next iteration. EX1003 ¶86.
`
`This BAC example starts with an initial interval [0, 1). At the first step of
`
`encoding, the current interval is equal to the initial interval [0, 1) and the
`
`probability state is set to 1:
`
`Interval Division [1] – To begin, the initial current interval is subdivided
`
`into partial intervals according to the respective probability of each symbol at
`
`probability state 1 in the table above – 2/3 for “A” and 1/3 for “B”. EX1003 ¶88.
`
`The Interval Division operation is illustrated graphically below with the “A” partial
`
`interval to the left (2/3) and the “B” partial interval to the right (1/3):
`
`7
`
`

`

`IPR2019-00726 Petition
`U.S. Patent No. 6,943,710
`
` To perform Interval Division, the range of the current interval is multiplied
`
`by the relative probabilities. EX1003 ¶89. In our example, this operation is initially
`
`trivial because the initial range is 1, resulting in partial intervals that match the
`
`probabilities (1 x 2/3 for “A” and 1 x 1/3 for “B”). EX1003 ¶89.
`
`It may seem counterintuitive, but Interval Division actually requires one or
`
`more multiplication operations at each
`
`iteration,
`
`depending on
`
`the
`
`implementation. EX1003 ¶90.
`
`A partial interval is selected based on the next input character in the string.
`
`In the example encoding the string “BAB”, the first input character is “B.” EX1003
`
`¶91. The right branch is therefore selected because that corresponds to the “B”
`
`partial interval. EX1003 ¶91.
`
`8
`
`

`

`IPR2019-00726 Petition
`U.S. Patent No. 6,943,710
`
`Code Point Update [1] – Next, the current interval is updated by updating
`
`the “code point,” or the left most point of the current interval, to the left most point
`
`of the selected partial interval. EX1003 ¶92. Here, the code point is updated from 0
`
`to 2/3. EX1003 ¶92. For computer implementations of BAC, it is useful to
`
`represent the current interval [2/3, 1) with two numbers: the current code point
`
`(2/3) and the range (1/3). EX1003 ¶92. Thus, the new current interval is [2/3, 1).
`
`EX1003 ¶92.
`
`Finally, the probability model is updated to the next state based on the “B”
`
`input event, which is state 2. EX1003 ¶93.
`
`Interval Division [2] – Next, the new current interval is subdivided
`
`according to the probabilities at state 2 – 1/2 for “A” and 1/2 for “B”. EX1003 ¶94.
`
`The range of the current interval (1/3) is multiplied by these probabilities to
`
`achieve to equal subdivisions of 1/6 for both “A” and “B”. EX1003 ¶94.
`
`9
`
`

`

`IPR2019-00726 Petition
`U.S. Patent No. 6,943,710
`
`The partial interval is selected according to the next input character in the
`
`string “BAB”, which in this example is “A.” Therefore, the left branch is selected
`
`as corresponding to the “A” partial interval.
`
`Code Point Update [2] – The code point remains at 2/3, but the range is
`
`updated to 1/6 according to the corresponding subdivision for “A”. EX1003 ¶96.
`
`The current interval is therefore [2/3, 5/6).
`
`The probability state is also updated according to the input event, which in
`
`this case was “A”. EX1003 ¶97. Accordingly, the probability state is set to 3.
`
`EX1003 ¶97.
`
`Interval Division [3] – To encode the final character in our input string “B,”
`
`we subdivide the current interval according to the probabilities in state 3 of the
`
`table – 3/5 for “A” and 2/5 for “B”. The range of the current interval (1/6) is
`
`multiplied by these probabilities to achieve subdivisions of 3/30 for “A” and 2/30
`
`10
`
`

`

`IPR2019-00726 Petition
`U.S. Patent No. 6,943,710
`
`for “B”. The partial interval is selected based on the final “B” input character in the
`
`input string “BAB”, which requires selection of the right branch.
`
`Code Point Update [3] – The current code point (2/3, or 20/30) is shifted
`
`right by 3/30 to 23/30. The range is updated to 2/30. And the current, and now
`
`final, interval is updated to [23/30, 25/30), or [23/30, 5/6).
`
`The binary input string “BAB” can therefore be represented with any
`
`convenient number in the interval of [23/30, 5/6), such as 24/30, which reduces to
`
`4/5.
`
`11
`
`

`

`IPR2019-00726 Petition
`U.S. Patent No. 6,943,710
`
`Decoding – To decode the string, the same Interval Division and Code Point
`
`Update operations are performed again starting from the output (4/5). EX1003
`
`¶101. The decoder is equipped with the probability table and initial interval [0, 1).
`
`The initial interval is subdivided according to the probabilities for the first
`
`character in the probability table at state 1 – 2/3 for “A” and “1/3” for B, again
`
`requiring at least one multiplication to perform this Interval Division step.
`
`EX1003 ¶101. The number 4/5 falls within the right branch, so “B” is output as the
`
`first character, which matches against the first character in our input string “BAB”.
`
`EX1003 ¶101.
`
`The code point is updated to 2/3, the range is 1/3, and the current interval is
`
`[2/3, 1/3). EX1003 ¶102. The probability state is advanced in accordance with the
`
`“B” event to state 2. EX1003 ¶102. The Interval Division and Code Point Update
`
`processes are repeated in the decoding process in the same manner until the
`
`original string is decoded.
`
`12
`
`

`

`IPR2019-00726 Petition
`U.S. Patent No. 6,943,710
`
`It was well-known that, in order to improve performance of this BAC, an
`
`initial interval of [1, 65,536) could be used rather than [0, 1) because the use of the
`
`latter would require using floating point arithmetic to represent the fractions while
`
`the use of the former could use simple integer arithmetic. See EX1001, 2:42 (citing
`
`to prior art Witten, Neal, Cleary implementation); EX1003 ¶103. In such
`
`implementations, “rescaling” or “interval expansion” processes were run to ensure
`
`that the interval could be divided using integer arithmetic. EX1001, 2:39-42;
`
`EX1003 ¶103.
`
`D.
`
`The Challenged Claims are Obvious
`
`The Challenged Claims are directed exclusively to the Interval Division
`
`process discussed above. EX1003 ¶¶111-116. The ’710 Patent confirms that all
`
`BAC coders rely on the process of Interval Division, and that “[t]he main
`
`disadvantage of [prior art BAC implementations] now lies in the fact that the
`
`calculation of the interval width [] requires a multiplication for every symbol to be
`
`coded. Generally, multiplication operations, in particular when they are realized in
`
`hardware, are cost- and time-intensive.” EX1001, 2:43-48,3 2:65-3:11, 3:20, 2:22-
`
`42.
`
`3 Throughout the petition, emphasis has been added to quoted language unless
`
`otherwise specified.
`
`13
`
`

`

`IPR2019-00726 Petition
`U.S. Patent No. 6,943,710
`
`1.
`
`The ’710 Patent Admits that Replacing Multiplication
`Operations with Table Lookups was Known
`
`The ’710 Patent purports to solve this problem by replacing these
`
`multiplication operations with a table lookup to determine the interval width.
`
`EX1003 ¶110; EX1001, 3:24-44. The table-based implementations described in the
`
`’710 Patent “do not require multiplication [and therefore] allow a probability
`
`estimation without calculation effort.” EX1003 ¶110; EX1001, 3:19-20. The
`
`Challenged Claims obviate performance of these expensive multiplication
`
`operations merely “by accessing an interval division table using [a] quantization
`
`index and [a] probability index” to perform Interval Division. EX1001, cls. 25, 33.
`
`However, accessing an interval division table with indices to perform
`
`Interval Division was well-known before the ’710 Patent. EX1001, 2:43-46, 2:65-
`
`3:11. The ’710 Patent admits numerous prior art implementations in which “any
`
`arithmetic operations are replaced by table accesses” to an “interval division
`
`table.” EX1001, 2:65-3:11 (“Background” section citing prior art interval division
`
`tables of EX1007 and EX1018). The ’710 Patent also admits that using a
`
`“probability index” to an interval division table was also well known in the prior
`
`art. EX1001, 3:9-11 (“Background” section admitting that “[a]dditionally, the
`
`probability estimation us[es] a table in the form of a finite state machine” and
`
`citing to a table-aided prior art BAC coder of EX1007). Further, the first named
`
`14
`
`

`

`IPR2019-00726 Petition
`U.S. Patent No. 6,943,710
`
`inventor of the ’710 Patent admitted that the patented implementation “can be
`
`considered as a generalization of the [admitted prior art] Q coder,” going so far as
`
`to call the two coders “conceptually equivalent.” EX1009, 3; EX1001, 2:65-3:2
`
`(discussing the “Q-Coder used in the JPEG standard” as prior art); EX1009
`
`(website published by Detlev Marpe explaining the coder claimed by the ’710
`
`Patent with admissions of “equivalence”).
`
`2.
`
`Printz Teaches the Only Allegedly Novel Feature of the
`Challenged Claims—a Quantization Index
`
`The only element of the Challenged Claims that the ’710 Patent does not
`
`admit as in the prior art is the concept of “mapping the current interval width to a
`
`quantization index,” which is simply an approximation of the current interval
`
`width used to access a table that replaces the Interval Division process of BAC.4
`
`EX1003 ¶110; EX1001, 11:4-5, 11:14-16, cls. 25, 33. But Printz (EX1005) is
`
`directed to this precise concept: “In the process according to the invention
`
`selection takes place of a set of r values A={A[0], A[1], . . . , A[r-1]} and the
`
`interval width is maintained as an index Wi in said set,” and the index Wi is used
`
`to “perform[] a single table lookup of f’’ [that] replaces” Interval Division.
`
`EX1005, 6:56-7:11.
`
`4 In fact, the entire concept of the only alleged novel feature of the ’710 Patent is
`
`described in less than two columns of disclosure. Ex. 1001 at Cols. 11-12.
`
`15
`
`

`

`IPR2019-00726 Petition
`U.S. Patent No. 6,943,710
`
`The combination of Howard (EX1004) in view of Printz (EX1005) would
`
`have rendered the ’710 Patent obvious. See infra § VI.A.1. Howard teaches a BAC
`
`coder that uses coding tables with “internal states corresponding to expandable
`
`subintervals.” EX1004, 15, Table 3. Howard teaches “selecting a new state [in the
`
`coding
`
`table] based on
`
`the current event and event probabilities” with
`
`“probabilities (indicated by probability index numbers).” EX1004, 15, Table 5.
`
`Kimura (EX1006) similarly teaches a BAC coder implementing an interval
`
`division table indexed by a probability index, and, in combination with Printz
`
`would have also rendered the Challenged Claims obvious. See infra § VI.B.1.
`
`Indeed, the first named inventor essentially agreed by admitting that the coder of
`
`the ’710 Patent is “conceptually equivalent” to the coder described by Kimura. See
`
`EX1009.
`
`II.
`
`GROUNDS FOR STANDING
`Petitioner certifies that the ’710 Patent is eligible for inter partes review.
`
`Petitioner further certifies that they are not barred or estopped from requesting this
`
`inter partes review.
`
`III.
`
`IDENTIFICATION OF CHALLENGES
`Petitioner requests inter partes review on the following grounds:
`
`16
`
`

`

`IPR2019-00726 Petition
`U.S. Patent No. 6,943,710
`
`Ground
`No.
`
`1
`
`2
`
`References
`
`Statutory Basis
`
`Claims Challenged
`
`Printz (EX1005)
`Howard (EX1004)
`Printz (EX1005)
`Kimura (EX1006)
`
`Obviousness (§103)
`
`25, 33, 60-63
`
`Obviousness (§103)
`
`25, 33, 60-63
`
`IV.
`
`U.S. 6,943,710
`
`A.
`
`Summary
`
`The application that led to the ’710 Patent was filed December 4, 20035 as
`
`U.S. Application 10/727,801 and claims priority
`
`to PCT Application
`
`PCT/EP03/04654, which was filed on May 2, 2003, and Danish Application 102
`
`20 962, which was filed on May 2, 2002.
`
`The ’710 Patent is directed to “arithmetically encoding and decoding binary
`
`states . . . which may in particular be used in digital data compression.” EX1001,
`
`1:18-22. The ’710 Patent describes its purportedly novel features in the context of
`
`the admitted prior art6 implementation of Moffat, which it summarizes in Fig. 1.
`
`EX1001, 2:22-42, Fig. 1 (discussing and citing to Moffat (EX1010)).
`
`5 The pre-AIA 35 U.S.C. §102 statutory framework applies to the ’710 Patent.
`
`6 The ’710 Patent expressly cites to 17 prior art references, including publications
`
`supporting its description of the Moffat coder in its “Description of the Related
`
`17
`
`

`

`IPR2019-00726 Petition
`U.S. Patent No. 6,943,710
`
`In explaining the BAC prior art, the ’710 Patent refers to the “LPS” (least
`
`probable symbol) and “MPS” (most probable symbol). EX1001, 2:30-32. The LPS
`
`refers to the input character with the lowest probability of occurring according to
`
`the probability model. The MPS refers to the input character with the highest
`
`probability of occurring. For example, in the probability table from the tutorial
`
`supra (reproduced below), at the first position the LPS is “B” because it has a
`
`lower probability than “A” (2/3).
`
`The ’710 Patent states that the Moffat implementation has the “main
`
`disadvantage . . . that the calculation of the interval width RLPS requires a
`
`multiplication for every symbol to be coded.” EX1001, 2:44-46. The multiplication
`
`operation shown in step 2 of Fig. 1 is identical to the Interval Division step
`
`discussed in the example above.
`
`Art” section, and each of these references should be treated as admitted prior art.
`
`See Ex. 1001 at 2:20-3:11 (citing e.g., Exs. 1007, 1010, 1017, 1018); see In re
`
`Nomiya, 509 F.2d 566, 571, 184 USPQ 607, 611 (CCPA 1975).
`
`18
`
`

`

`IPR2019-00726 Petition
`U.S. Patent No. 6,943,710
`
`The RLPS (range of the least probable symbol) and RMPS (range of the most
`
`probable symbol) refer to the subdivided ranges of the current interval based on
`
`this multiplication of the current interval by each of the symbol probabilities.
`
`The ’710 Patent proposes a “modified scheme for a table-aided arithmetic
`
`coding” that “eliminate[s] the mentioned disadvantages and in particular (a) do[es]
`
`not require a multiplication, (b) allow[s] a probability estimation without
`
`calculation effort and (c) simultaneously guarantee[s] a maximum coding
`
`efficiency over a wide range of typically occurring symbol probabilities.” EX1001,
`
`3:18-23, 11:2-3. To achieve this, the ’710 Patent follows the prior art
`
`implementation but replaces the Interval Division process of Fig. 1 with two steps
`
`– (1) mapping the current interval to a “quantized” or approximated value and (2)
`
`19
`
`

`

`IPR2019-00726 Petition
`U.S. Patent No. 6,943,710
`
`accessing a table to perform the interval division for the least probable symbol
`
`(RLPS). Id., 11:1-26.
`
`Interval Quantization - The ’710 Patent states that “the given interval
`
`width R is mapped to a quantized value Q using a tabulated mapping Qtab” that
`
`has “a relatively coarse quantization to K=2 . . . 8 representative values.” EX1001,
`
`11:4-11. Qtab contains a set of “quantized,” “representative,” or approximated
`
`values of the current interval width R. Id. “[N]o explicit determination of [the
`
`approximated interval width] Q is performed; rather, only an index q_index is
`
`transferred to Q.” Id., 11:12-14. The ’710 Patent describes embodiments where
`
`Qtab contains “relatively coarse” approximations of just 2, 4, 6, or even 8
`
`“representative values” of the current interval width. Id., 11:10-11.
`
`20
`
`

`

`IPR2019-00726 Petition
`U.S. Patent No. 6,943,710
`
`For example, assume Qtab contains a set of K=2 quantized values of an
`
`initial interval width [0, 1). EX1003 ¶112. In this example, Qtab might contain the
`
`following values:
`
`Index
`0
`1
`
`Width
`3/4
`1
`
`Interval quantization “maps” the current interval to a quantized interval width.
`
`EX1003 ¶112. Using the example from the tutorial above, at the first coding
`
`iteration interval quantization maps the current interval (current interval = [0, 1)) to
`
`q_index = Qtab[1] because the interval width 1 is the best representative value of
`
`the current interval width. EX1003 ¶112.
`
`Interval Division - The ’710 Patent discloses that the q_index is “used
`
`together with the index p_state for a characterization of the current probability
`
`state for the determination of the interval width RLPS” by retrieving “the
`
`corresponding entry of the table Rtab.” EX1001, 11:14-17. The index “p_state” is
`
`maintained in a “probability estimation” table that contains probability “states” that
`
`reference the probability of the current symbol to be coded. EX1001, 10:42-67.
`
`Each probability state contains an identification of the least probable symbol (the
`
`LPS, i.e., a “0” or “1”), an estimated probability that the current symbol is
`
`equivalent to the LPS (the PLPS), and transition “rules” that “indicate which new
`
`state is to be used for the next symbol to be coded based on the currently coded
`
`21
`
`

`

`IPR2019-00726 Petition
`U.S. Patent No. 6,943,710
`
`symbol” (e.g., “Next_State_LPS”, “Next_State_MPS”). EX1001, 10:50-52, 10:63-
`
`65, 11:29-30.
`
`Rtab contains precomputed “product values R x PLPS, that correspond to all
`
`K quantized values of R,” which are stored or “entered as integer values” with
`
`limited accuracy. EX1001, 11:18-26. The values of Rtab provide “integer”
`
`approximations of RLPS from Moffat’s implementation. Compare EX1001, Fig. 1,
`
`step (2) with EX1001, Fig. 2, step (3). The indices q_index and p_state address a
`
`specific RLPS entry in Rtab.
`
`The table below illustrates how q_index and p_state values might index a
`
`table Rtab. EX1003 ¶115.
`
`According to the ’710 Patent, execution of the remaining codin