Filed on behalf of Oracle America, Inc.
`By: Monica Grewal, Reg. No. 40,056 (Lead Counsel)
`Donald Steinberg, Reg. No. 37,241 (Back-up Counsel)
`Wilmer Cutler Pickering Hale and Dorr LLP
`60 State Street
`Boston, MA 02109
`Phone: (617) 526-6223
`Email: Monica.Grewal@wilmerhale.com
`
` Don.Steinberg@wilmerhale.com
`
`UNITED STATES PATENT AND TRADEMARK OFFICE
`
`____________________________________________
`
`BEFORE THE PATENT TRIAL AND APPEAL BOARD
`
`____________________________________________
`
`ORACLE AMERICA, INC.
`
`Petitioner
`
`v.
`
`REALTIME DATA LLC
`
`Patent Owner of
`
`U.S. Patent No. 6,597,812 to Fallon
`
`IPR Trial No. IPR2017-00168
`
`PETITION FOR INTER PARTES REVIEW OF
`CLAIMS 1, 9, 14, 22, 28
`U.S. PATENT NO. 6,597,812
`UNDER 35 U.S.C. § 312 AND 37 C.F.R. § 42.104
`
`

`
`IPR2017-00168: Petition
`U.S. Patent No. 6,597,812, Claims 1, 9, 14, 22, 28
`TABLE OF CONTENTS
`
`INTRODUCTION ........................................................................................... 1 
`I. 
`II.  MANDATORY NOTICES ............................................................................. 2 
`A. 
`Real Party In Interest ............................................................................. 2 
`B. 
`Related Matters ...................................................................................... 2 
`C. 
`Counsel .................................................................................................. 4 
`D. 
`Service Information ............................................................................... 4 
`III.  LEVEL OF ORDINARY SKILL .................................................................... 4 
`IV.  CERTIFICATION OF GROUNDS FOR STANDING .................................. 5 
`V.  OVERVIEW OF CHALLENGE AND RELIEF REQUESTED .................... 5 
`A. 
`Prior Art ................................................................................................. 5 
`B. 
`Grounds of Challenge ............................................................................ 6 
`VI.  LEGAL PRINCIPLES ..................................................................................... 6 
`VII.  BACKGROUND AND STATE OF THE ART .............................................. 7 
`A. 
`Run Length Encoding Was Well-Known Before the Filing Date
`of the ’812 Patent And Is Admitted Prior Art ....................................... 7 
`Dictionary Compression Was Well-Known Before The Filing
`Date Of The ’812 Patent And Is Admitted Prior Art ............................ 8 
`1. 
`LZ78 Dictionary Compression ................................................. 11 
`2. 
`LZW Dictionary Compression .................................................. 12 
`VIII.  OVERVIEW OF THE ’812 PATENT .......................................................... 15 
`A. 
`Priority ................................................................................................. 15 
`B. 
`Brief Description ................................................................................. 15 
`C. 
`Prosecution History of the ’812 patent ................................................ 22 
`IX.  CLAIM CONSTRUCTION .......................................................................... 22 
`1. 
`Control Code Word ................................................................... 23 
`PRIOR ART REFERENCES ........................................................................ 24 
`A. 
`Seroussi ............................................................................................... 24 
`B. 
`Heath .................................................................................................... 31 
`C. 
`Nelson .................................................................................................. 34 
`
`X. 
`
`B. 
`
`
`
`i
`
`

`
`IPR2017-00168: Petition
`U.S. Patent No. 6,597,812, Claims 1, 9, 14, 22, 28
`XI.  THE CHALLENGED CLAIMS ARE NOT PATENTABLE ...................... 35 
`XII. 
`IDENTIFICATION OF HOW CLAIMS 1, 9, 14, 22, 28 ARE
`UNPATENTABLE ........................................................................................ 35 
`A.  Ground 1: Claims 1, 9, 14, and 22 are Obvious in View of
`Seroussi and Heath .............................................................................. 35 
`1.  Motivation to Combine Seroussi and Heath ............................. 35 
`2. 
`Independent Claim 1 is Obvious in View of Seroussi and
`Heath. ........................................................................................ 36 
`i.
`The preamble of Claim 1 is disclosed in Seroussi. ......... 37 
` 
`ii.
`Limitation A of Claim 1 is obvious in view of
` 
`Seroussi and Heath. ........................................................ 38 
`iii.
`Limitation B of Claim 1 is disclosed in Seroussi. .......... 42 
` 
`iv.
`Limitation C of Claim 1 is disclosed in Seroussi. .......... 46 
` 
`v.
`Limitation D of Claim 1 is disclosed in Seroussi. .......... 50 
` 
`vi.
`Limitation E of Claim 1 is disclosed in Seroussi. .......... 51 
` 
`  Limitation F of Claim 1 is disclosed in Seroussi. ........... 51 vii.
`
`Dependent Claim 9 is Obvious in View Seroussi and
`Heath. ........................................................................................ 52 
`Independent Claim 14 is Obvious in View of Seroussi
`and Heath. ................................................................................. 55 
`i.
`The preamble of Claim 14 is disclosed in Seroussi. ....... 56 
` 
`ii.
`Limitation A of Claim 14 is obvious in view of
` 
`Seroussi and Heath. ........................................................ 57 
`iii.
`Limitation B of Claim 14 is disclosed in Seroussi. ........ 57 
` 
`iv.
`Limitation C of Claim 14 is disclosed in Seroussi. ........ 57 
` 
`v.
`Limitation D of Claim 14 is disclosed in Seroussi. ........ 57 
` 
`vi.
`Limitation E of Claim 14 is disclosed in Seroussi. ........ 58 
` 
`  Limitation F of Claim 14 is disclosed in Seroussi. ......... 58 vii.
`
`Dependent Claim 22 is Obvious in View of Seroussi and
`Heath. ........................................................................................ 58 
`Ground 2: Claim 28 is Anticipated by Seroussi .................................. 59 
`1. 
`Independent Claim 28 is Disclosed in Seroussi. ....................... 59 
`
`3. 
`
`4. 
`
`5. 
`
`B. 
`
`
`
`ii
`
`

`
`C. 
`
`IPR2017-00168: Petition
`U.S. Patent No. 6,597,812, Claims 1, 9, 14, 22, 28
`i.
`The preamble of Claim 28 is disclosed in Seroussi. ....... 59 
` 
`ii.
`Limitation A of Claim 28 is disclosed in Seroussi. ........ 60 
` 
`iii.
`Limitation B of Claim 28 is disclosed in Seroussi. ........ 63 
` 
`Limitation C of Claim 28 is disclosed in Seroussi. ........ 67 
`iv.
` 
`Ground 3: Claim 28 is Obvious in view of Seroussi and Nelson ....... 70 
`1.  Motivation to Combine Seroussi and Nelson ........................... 70 
`2. 
`Independent Claim 28 is Obvious in view of Seroussi and
`Nelson ....................................................................................... 71 
`i.
`The preamble of Claim 28 is disclosed in Seroussi. ....... 71 
` 
`ii.
`Limitation A of Claim 28 is obvious in view of
` 
`Seroussi and Nelson. ....................................................... 71 
`Limitation B of Claim 28 is disclosed in Seroussi. ........ 73 
`iii.
` 
`Limitation C of Claim 28 is disclosed in Seroussi. ........ 74 
`iv.
` 
`XIII.  Conclusion ..................................................................................................... 75 
`
`
`
`
`
`iii
`
`

`
`IPR2017-00168: Petition
`U.S. Patent No. 6,597,812, Claims 1, 9, 14, 22, 28
`TABLE OF AUTHORITIES
`
` Page(s)
`
`Federal Cases
`KSR Int’l Co. v. Teleflex, Inc.,
`550 U.S. 398 (2007) ........................................................................................ 7, 55
`
`Cuozzo Speed Techs., LLC,
`136 S. Ct. 2131 (2016) .................................................................................. 22-23
`
`Federal Statutes
`
`35 U.S.C. § 102 .................................................................................................... 6, 23
`
`35 U.S.C. § 102(a), (b), and (e) ............................................................................. 5, 6
`
`35 U.S.C. § 103 .................................................................................................... 6, 23
`
`35 U.S.C. § 103(a) ..................................................................................................... 6
`
`35 U.S.C. § 314(a) ..................................................................................................... 6
`
`Regulations
`
`37 C.F.R § 42.22(a)(1) ............................................................................................... 5
`
`37 C.F.R. § 42.100(b) .............................................................................................. 22
`
`37 C.F.R. § 42.104(a) ................................................................................................. 5
`
`37 C.F.R. § 42.104(b)(1)-(2) ...................................................................................... 5
`
`37 C.F.R. § 42.104(b)(4)-(5) ...................................................................................... 5
`
`Other Authorities
`
`Leahy-Smith America Invents Act, Pub. L. No. 112-29, 125 Stat. 284
`(2011) .................................................................................................................... 6
`
`
`
`iv
`
`

`
`IPR2017-00168: Petition
`U.S. Patent No. 6,597,812, Claims 1, 9, 14, 22, 28
`I.
`INTRODUCTION
`
`U.S. Patent No. 6,597,812 (“the ’812 patent”, Ex. 1101) is generally directed
`
`to systems and methods for data compression and decompression using a
`
`combination of run-length encoding and dictionary encoding.
`
`A patent that was not before the Patent Office during prosecution of the ’812
`
`patent, however, U.S. Patent No. 5,389,922 to Seroussi (“Seroussi”, Ex. 1103),
`
`teaches the implementation of a combination of run-length and dictionary encoding
`
`to compress and decompress data in methods and systems. Seroussi expressly
`
`discloses every limitation of claims 1, 9, 14, 22, and 28 of the ’812 patent except
`
`arguably “detecting if the input data comprises a run-length sequence of data
`
`blocks,” “bit-packing encoded run-length sequences and code words that are
`
`output,” and “control code words.” For example, Seroussi teaches outputting code
`
`words indicative of a run-length sequence when a run in an input data stream is
`
`detected, and outputting code words indicative of a dictionary entry for characters
`
`in the input data stream that are not part of a run.
`
`U.S. Patent No. 5,973,630 to Heath (“Heath”, Ex. 1104) and Mark Nelson,
`
`The Data Compression Book, M&T Books, 1992 (“Nelson”, Ex. 1105), references
`
`that also were not discussed by the Patent Office during prosecution of the ’812
`
`patent, disclose the run-length detection, the bit-packing limitation, and control
`
`code words. Because Nelson is a textbook describing common compression
`
`
`
`1
`
`

`
`IPR2017-00168: Petition
`U.S. Patent No. 6,597,812, Claims 1, 9, 14, 22, 28
`techniques, including the compression methods described in Seroussi, and because
`
`Heath discloses similar systems and methods as Seroussi, including systems and
`
`methods that use similar dictionary compression methods (e.g., Lempel-Ziv Welch
`
`“LZW”), and improve the same dictionary compression by adding run-length
`
`compression, it would have been obvious to combine the teachings of Seroussi
`
`with the teachings of Nelson or Heath. Accordingly, Seroussi alone and in
`
`combination with Heath or Nelson renders claims 1, 9, 14, 22, and 28
`
`unpatentable.
`
`As the petition in the instant case presents a challenge to some of the same
`
`claims challenged in IPR 2016-00783 and is being filed by Oracle America, Inc.,
`
`which is a co-defendant with the IPR 2016-00783 petitioners, this petition is
`
`accompanied by a motion for joinder.
`
`II. MANDATORY NOTICES
`A. Real Party In Interest
`Oracle America, Inc. (“Petitioner”) is the sole real party-in-interest.
`
`Petitioner submits this Petition for Inter Partes Review (“Petition”) for review of
`
`claims 1, 9, 14, 22, 28 of U.S. Patent No. 6,597,812.
`
`B. Related Matters
`The following co-pending litigation matters would affect or could be
`
`affected by a decision in this proceeding:
`
`
`
`2
`
`

`
`IPR2017-00168: Petition
`U.S. Patent No. 6,597,812, Claims 1, 9, 14, 22, 28
` Realtime Data LLC v. Actian Corporation et al., E.D. Tex. Case No.
`
`6:2015-cv-00463, filed on May 8, 2015;
`
` Realtime Data LLC v. BMC Software, Inc., E.D. Tex. Case No. 6:15-
`
`cv-00464, filed on May 8, 2015;
`
` Realtime Data LLC v. Oracle America, Inc., Hewlett-Packard Co. and
`
`HP Enterprise Services, LLC, E.D. Tex. Case No. 6:2015-cv-00467,
`
`filed on May 8, 2015;
`
` Realtime Data LLC v. SAP America, Inc. et al., E.D. Tex. Case No.
`
`6:2015-cv-00469, filed on May 8, 2015;
`
` Realtime Data LLC v. Teradata Corporation et al., E.D. Tex. Case
`
`No. 6:2015-cv-00470, filed on May 8, 2015;
`
` Realtime Data LLC v. Oracle America, Inc., E.D. Tex. Case No. 6:16-
`
`cv-00088, filed on February 26, 2016;
`
` Realtime Data LLC v. Teradata Corporation, et al., N.D. Cal. Case
`
`No. 3:16-cv-01836, filed on April 8, 2016;
`
` Realtime Data LLC v. Teradata Operations, Inc., C.D. Cal. Case No.
`
`2:16-cv-02743, filed on April 21, 2016;
`
`
`
`3
`
`

`
`IPR2017-00168: Petition
`U.S. Patent No. 6,597,812, Claims 1, 9, 14, 22, 28
`The following co-pending IPRs would affect or could be affected by a
`
`decision in this proceeding: IPR 2017-00167, IPR 2016-00783.1
`
`C. Counsel
`Lead Counsel: Monica Grewal (Registration No. 40,056)
`
`Back-up Counsel: Donald Steinberg (Registration No. 37,241)
`
`Service Information
`
`D.
`Email: Monica.Grewal@wilmerhale.com; Don.Steinberg@wilmerhale.com
`
`Post and hand delivery address: Wilmer Cutler Pickering Hale and Dorr LLP,
`
`60 State Street, Boston, MA 02109 Telephone: (617) 526-6223
`
`Facsimile: (617) 526-5000. Petitioner consents to electronic service.
`
`III. LEVEL OF ORDINARY SKILL
`A person of ordinary skill in the relevant field is a hypothetical person to
`
`whom an expert in the relevant field could assign a routine task with reasonable
`
`confidence that the task would be successfully carried out. The level of skill in the
`
`art is evidenced by prior art references. The prior art discussed herein
`
`demonstrates that a person of ordinary skill in the field, at the time the ’812 patent
`
`was effectively filed, had an undergraduate degree in computer science and two
`
`years’ industry experience or a graduate degree in the field of data compression.
`
`
`1 The Board issued a Decision to institute the ’783 petition on October 5, 2016.
`
`See Decision on Institution, IPR 2016-00783, Paper 18 (Oct. 5, 2016).
`
`
`
`4
`
`

`
`IPR2017-00168: Petition
`U.S. Patent No. 6,597,812, Claims 1, 9, 14, 22, 28
`IV. CERTIFICATION OF GROUNDS FOR STANDING
`Petitioner certifies pursuant to Rule 42.104(a) that the patent for which
`
`review is sought is available for inter partes review and that Petitioner is not
`
`barred or estopped from requesting an inter partes review challenging the patent
`
`claims on the grounds identified in this Petition.
`
`V. OVERVIEW OF CHALLENGE AND RELIEF REQUESTED
`Pursuant to Rules 42.22(a)(1) and 42.104(b)(1)-(2), Petitioner challenges
`
`claims 1, 9, 14, 22, and 28 of the ’812 patent (Ex. 1101) and requests that they be
`
`cancelled.
`
`Prior Art
`
`A.
`Petitioner relies upon the following prior art:
`
`1.
`
`U.S. Patent No. 5,389,922 to Seroussi (“Seroussi,” Ex. 1103), which
`
`was filed on April 13, 1993, and issued on February 14, 1995, is prior art under 35
`
`U.S.C. § 102(b).
`
`2.
`
`U.S. Patent No. 5,973,630 to Heath (“Heath,” Ex. 1104), which was
`
`filed on March 1, 1999, and issued on October 26, 1999. Heath claims priority to
`
`and is a divisional application of U.S. Application No. 08/982,864, filed December
`
`2, 1997. As such, Heath is prior art under 35 U.S.C. § 102(e).
`
`3. Mark Nelson, The Data Compression Book, M&T Books 1992
`
`(“Nelson,” Ex. 1105), was published in 1992 and is prior art under 35 U.S.C.
`
`§§ 102(a) and (b). The public availability of Nelson is demonstrated by its citation
`
`
`
`5
`
`

`
`IPR2017-00168: Petition
`U.S. Patent No. 6,597,812, Claims 1, 9, 14, 22, 28
`in many patents prior to the filing date of the ’812 patent (see, e.g., U.S. Pat. Nos.
`
`5,408,542; 5,745,392; 5,798,718; 5,867,114; 5,870,036; 5,839,100 and WO
`
`1997013164 A1) and by the attached Declaration of Dr. Scott Bennett (Ex. 1119).
`
`See also Fed. R. Ev. 803(16) (Copyright page in Nelson is admissible to show the
`
`truth of the matters asserted.).)
`
`B. Grounds of Challenge
`Petitioner requests cancellation of claims 1, 9, 14, 22, and 28 (the
`
`“challenged claims”) of the ’812 patent as unpatentable under 35 U.S.C. §102 and
`
`§103.
`
`This Petition, supported by the declaration of Dr. James Storer (“Storer
`
`Declaration” or “Storer Decl.,” Ex. 1102), demonstrates a reasonable likelihood
`
`that Petitioner will prevail with respect to the challenged claims and that they are
`
`unpatentable for the reasons cited in this Petition. See 35 U.S.C. § 314(a).
`
`VI. LEGAL PRINCIPLES
`The challenged claims were filed prior to the effective date of the Leahy-
`
`Smith America Invents Act, Pub. L. No. 112-29, 125 Stat. 284 (2011) and
`
`therefore should be analyzed for patentability under pre-AIA 35 U.S.C. §§ 102 and
`
`103. A claim is invalid if it is “not novel” or would have been “obvious.” See 35
`
`U.S.C. §§ 102, 103(a). The key inquiry to determine obviousness is whether an
`
`“improvement is more than the predictable use of prior art elements according to
`
`
`
`6
`
`

`
`IPR2017-00168: Petition
`U.S. Patent No. 6,597,812, Claims 1, 9, 14, 22, 28
`their established functions.” KSR Int’l Co. v. Teleflex, Inc., 550 U.S. 398, 415,
`
`417, 420-21 (2007).
`
`VII. BACKGROUND AND STATE OF THE ART
`The ’812 patent relates to two data compression techniques—run length
`
`encoding and dictionary encoding. The background of the ’812 patent admits that
`
`both of these encoding techniques were well known prior to the filing date of the
`
`’812 patent.
`
`A. Run Length Encoding Was Well-Known Before the Filing Date of
`the ’812 Patent And Is Admitted Prior Art
`
`The ’812 patent notes that run length encoding was well known prior to the
`
`filing date of the ’812 patent. ’812 patent at 2:59-66. In a simple example of run
`
`length encoding, a “run” of repeated characters is identified and replaced with an
`
`identifier for the repeated character and a count of the number of times it is
`
`repeated. As shown below, run length encoding allows the string
`
`AAABBBCCCBBBBCCCCCAAAA to be represented as 3A3B3C4B5C4A. See
`
`Storer Decl. at ¶ 35; Ex. 1102.
`
`
`
`7
`
`

`
`IPR2017-00168: Petition
`U.S. Patent No. 6,597,812, Claims 1, 9, 14, 22, 28
`
`
`While the basic concept of run length encoding is straightforward, there are
`
`several possible variations in its implementation (e.g., using a control code (also
`
`called an escape sequence or code) to identify run length sequences of inputs
`
`(characters, bytes, or blocks) that have been run length encoded or using multiple
`
`control codes are used with the specific control code selected providing
`
`information about the repetition count value). See id. at ¶ 36.
`
`Run-length encoding was well-known by the 1960’s, when it was used for
`
`television signals (see Robinson; Ex. 1106) and facsimile transmissions (see U.S.
`
`Pat. No. 3,560,639; Ex. 1107). By the 1980’s, run length encoding was being
`
`paired with other encoding schemes. See U.S. Pat. No. 4,626,829; Ex. 1108. This
`
`trend continued into the late 1980’s and early 1990’s. See, e.g., U.S. Pat. No.
`
`4,988,998; Ex. 1109; Seroussi; Ex. 1003; Heath; Ex. 1004. See Storer Decl. at ¶
`
`37; Ex. 1102.
`
`B. Dictionary Compression Was Well-Known Before The Filing Date
`Of The ’812 Patent And Is Admitted Prior Art
`
`
`
`8
`
`

`
`IPR2017-00168: Petition
`U.S. Patent No. 6,597,812, Claims 1, 9, 14, 22, 28
`Like run length encoding, dictionary encoding was known well before the
`
`filing date of the ’812 patent and is admitted prior art in the ’812 patent. ’812
`
`patent at 2:59-66. In dictionary encoding, a “dictionary” maps data blocks (such as
`
`characters and character strings) to indices. A data compression dictionary can be
`
`visualized as a table in which indices are mapped to strings of data which can be
`
`characters, character strings, or other data blocks. For example, given the
`
`dictionary below, the string “dictionary data compression is well known” could be
`
`encoded as “3 2 1 is well 4”. See id. at ¶ 38.
`
`
`A dictionary index can typically be represented by fewer bits than its
`
`corresponding string of data, so replacing the string of data with the index results
`
`in data compression. During encoding, each time a string of data in the input
`
`stream is found in the dictionary, it is replaced with the index corresponding to that
`
`string of data. See id. at ¶ 39.
`
`For decompression, a decoder uses the same dictionary to reverse the
`
`compression process. The decoder looks up indices in a compressed data stream
`
`
`
`9
`
`

`
`IPR2017-00168: Petition
`U.S. Patent No. 6,597,812, Claims 1, 9, 14, 22, 28
`and replaces them with the corresponding “words” from the dictionary. See id. at ¶
`
`40.
`
`Dictionaries are often visualized as tables, in which each entry associates an
`
`index with the corresponding character, string, word, etc. represented by that
`
`index, but dictionaries can be implemented in a variety of ways. The defining
`
`characteristic of a dictionary used for encoding is the mapping of index values to
`
`data blocks and data block strings. See id. at ¶ 41.
`
`Dictionaries can be static, meaning that the strings of data they contain are
`
`fixed before the encoding process starts, and do not change over the course of the
`
`encoding process. Alternatively, the dictionary can be adaptive, meaning that
`
`strings of data from the input stream are added to the dictionary during the
`
`compression process. Many adaptive dictionary encoders trace their roots to
`
`Lempel and Ziv’s groundbreaking papers in 1977 (“LZ77”) and 1978 (“LZ78”).
`
`See Ziv Universal Algorithm; Ex. 1112; Ziv Variable-Rate Coding; Ex. 1113; see
`
`also Storer Decl. at ¶ 42; Ex. 1102.
`
`LZ77 and LZ78 both describe adaptive dictionary encoders. In LZ77,
`
`dictionary indices point to character strings found in a “sliding window” dictionary
`
`composed of the most recent previously encoded data. In LZ78, indices are
`
`mapped to data blocks from the input stream to build the dictionary during the
`
`encoding process. The prior art relied on in this Petition uses a variation of LZ78
`
`
`
`10
`
`

`
`IPR2017-00168: Petition
`U.S. Patent No. 6,597,812, Claims 1, 9, 14, 22, 28
`encoding—namely, LZW encoding. Accordingly, LZ78 is explained in more
`
`detail below. See Storer Decl. at ¶ 42; Ex. 1102.
`
`LZ78 Dictionary Compression
`
`1.
`The signature feature of LZ78 is the algorithm used to build the dictionary as
`
`it encodes the input stream. The LZ78 algorithm starts with a dictionary initialized
`
`to contain only the “null” value, which is typically mapped to the “0” index. In the
`
`LZ78 algorithm, the characters of the input stream are read one at a time. As it is
`
`read, each character is combined with a prefix string (which is empty in the case of
`
`the first character or a new character after a string has been encoded) by adding it
`
`to the end of the prefix string. The dictionary is then searched to see if the
`
`combined prefix string/last character is present in the dictionary. If so, then the
`
`combined prefix string/last character is set to be the new prefix string and the
`
`process repeats by reading the next character in the input stream. If the combined
`
`prefix string/last character is not in the dictionary, then the index for the prefix
`
`string is output followed by the last character, the combined prefix string/last
`
`character is then added to the dictionary, and the prefix string is set to empty.
`
`Following this, the next character in the input stream is read and the process
`
`repeats. This sequence of steps, shown in the flow chart below, is the signature of
`
`an LZ78 encoding algorithm.
`
`
`
`11
`
`

`
`IPR2017-00168: Petition
`U.S. Patent No. 6,597,812, Claims 1, 9, 14, 22, 28
`
`
`
`A simple example of compression using this algorithm is set forth by Dr.
`
`Storer in his accompanying declaration. See id. at ¶¶ 43-45.
`
`LZW Dictionary Compression
`
`2.
`In 1984, Terry Welch described a particular variation of LZ78 that has
`
`become known as LZW, for Lempel-Ziv-Welch. Welch article; Ex. 1114. Welch
`
`provided the following algorithm:
`
`
`
`
`
`12
`
`

`
`IPR2017-00168: Petition
`U.S. Patent No. 6,597,812, Claims 1, 9, 14, 22, 28
`
`Id. at 15-16; see also Storer Decl. at ¶ 46; Ex. 1102.
`
`Based on this algorithm (which is reformatted below on the left), a flow
`
`chart, below right, can be created. See Storer Decl. at ¶ 47.
`
`
`
`A step-by-step example of encoding a string using an LZW algorithm is set
`
`forth in the accompanying Storer Declaration. Id. at ¶¶ 48-49.
`
`
`
`13
`
`
`
`

`
`IPR2017-00168: Petition
`U.S. Patent No. 6,597,812, Claims 1, 9, 14, 22, 28
`The LZW algorithm incorporates the signature features of LZ78, but
`
`precedes them with initializing the dictionary to contain every possible single
`
`character value mapped to a different dictionary index. Typically, there are 256
`
`single-character strings (that is, every possible single-character value for an 8-bit
`
`character) that are mapped to indices 0-255. Because of this, it is no longer
`
`necessary to output single characters, since an index corresponding to each single
`
`character is in the initial dictionary. Also, according to LZW, when the combined
`
`prefix string/last character (ωK) is not found in the dictionary, the prefix string is
`
`set to be the last character (ω = K). See id. at ¶¶ 50-51.
`
`One of ordinary skill in the art at the time of the filing of the ’812 patent
`
`would be very familiar with the LZW algorithm as presented in the 1984 Welch
`
`Article and provided as the well-known UNIX compress utility available starting in
`
`the late 1980s (and still present on UNIX systems today), and would have
`
`recognized the dictionary compression presented as part of the flow chart of
`
`the’812 patent Figure 2 as the LZW algorithm. In the accompanying Storer
`
`Declaration, a chart is provided showing 7 steps of LZW compression as described
`
`in Seroussi on the left-hand side of the chart and the corresponding steps of the
`
`dictionary algorithm that is presented in the ’812 patent shown in the right-hand
`
`side of the chart. See Seroussi at 6:32-6:53; Ex. 1103; ’812 patent at 8:3 – 9:19,
`
`FIG. 2. As shown and described in the chart in the accompanying Storer
`
`
`
`14
`
`

`
`IPR2017-00168: Petition
`U.S. Patent No. 6,597,812, Claims 1, 9, 14, 22, 28
`declaration, the ’812 patent describes the same dictionary compression algorithm
`
`as detailed in Seroussi, which is the same algorithm described in the 1984 Welch
`
`article—which became known as the LZW algorithm. See Storer Decl. at ¶¶ 52-
`
`53; Ex. 1102.
`
`VIII. OVERVIEW OF THE ’812 PATENT
`A.
`Priority
`The ’812 patent, titled “System and method for lossless data compression
`
`and decompression,” was filed on May 26, 2000 and claims priority to U.S.
`
`Provisional Application No. 60/136,561, filed on May 28, 1999.
`
`Brief Description
`
`B.
`The ’812 patent is directed to systems and methods for providing lossless
`
`data compression and decompression using run-length encoding/decoding and
`
`dictionary encoding/decoding. ’812 patent at Abstract; Ex. 1101. A block diagram
`
`of an encoder implementing this combination is illustrated in Figure 1 of the ’812
`
`patent, with the run length encoder identified as box 13 and the dictionary encoder
`
`identified as box 14. See Storer Decl. at ¶ 55; Ex. 1102.
`
`
`
`15
`
`

`
`IPR2017-00168: Petition
`U.S. Patent No. 6,597,812, Claims 1, 9, 14, 22, 28
`
`
`The algorithm described in the ’812 patent first checks for a run length.
`
`’812 patent at 5:30-37; Ex. 1101. If one is detected, the run length is encoded and
`
`output. Id. The encoded run length sequence includes a control code from the
`
`dictionary so that the decoder will know that the associated codes should be
`
`decoded as a run length. Id. The specific run length encoding described in the
`
`‘812 patent is, as output, the run length indicator control code, followed by the
`
`code for the character in the run, followed by the number of times the character is
`
`repeated. Id. at 6:25-31; see also Storer Decl. at ¶ 56; Ex. 1102.
`
`If a run-length is not detected, the ’812 patent begins a dictionary encoding
`
`process as illustrated in FIG. 2B below. FIG. 2A is also provided for
`
`completeness. As can be seen, this algorithm contains the signature features of
`
`
`
`16
`
`

`
`IPR2017-00168: Petition
`U.S. Patent No. 6,597,812, Claims 1, 9, 14, 22, 28
`LZ78 and LZW. In fact, as described earlier, the dictionary portion of this
`
`combined run-length and dictionary algorithm is the LZW algorithm. See Storer
`
`Decl. at ¶ 57; Ex. 1102.
`
`
`
`17
`
`

`
`IPR2017-00168: Petition
`U.S. Patent No. 6,597,812, Claims 1, 9, 14, 22, 28
`
`
`
`
`
`18
`
`

`
`IPR2017-00168: Petition
`U.S. Patent No. 6,597,812, Claims 1, 9, 14, 22, 28
`
`
`As shown in Figure 2A, before beginning the process of checking for a run
`
`length sequence, the encoder reads the next character and stores it at C. See ’812
`
`patent, Fig. 2A at box 211; Ex. 1101. For dictionary encoding, this value C is
`
`
`
`19
`
`

`
`IPR2017-00168: Petition
`U.S. Patent No. 6,597,812, Claims 1, 9, 14, 22, 28
`combined with the current prefix string, called the “working character string”
`
`Pstring, to create Pstring+C, at box 210. Id. at 8:50-53. Next, the encoder
`
`searches the dictionary to see if it contains Pstring+C. Id. at 8:53-61 (see box
`
`211). If it does, the encoder stores the dictionary code word for Pstring+C in
`
`Mcode (Mcode is a data structure for temporarily storing the code word for
`
`Pstring+C (id. at 5:61-64)) and sets Pstring to be equal to Pstring+C, at boxes 213
`
`and 214. Id. at 9:1-5. To determine if a longer match can be found in the
`
`dictionary, the encoder then reads the next input character (at box 203 of Figure
`
`2A), if there is one, and repeats the process. Id. at 9:5-10; see also Storer Decl. at ¶
`
`58; Ex. 1102.
`
`If the longest match between the prefix string (working character string
`
`Pstring), and the dictionary has already been found, the new string Pstring+C will
`
`not be in the dictionary. ’812 patent at 9:1-10; Ex. 1101. Therefore, as shown in
`
`box 215, the encoder outputs the code for Pstring (found in Mcode). Id. at 9:17-
`
`22. At boxes 216-218, Pstring+C, the longest matching string plus the next
`
`character, is added to the dictionary, unless it is already full. Id. at 9:26-35; see
`
`also Storer Decl. at ¶ 59; Ex. 1102.
`
`Once the new entry has been added to the dictionary, the encoder is ready to
`
`continue searching for run lengths and string matches. To do this, the encoder sets
`
`the current prefix string (the working string, Pstring) equal to C (at box 223),
`
`
`
`20
`
`

`
`IPR2017-00168: Petition
`U.S. Patent No. 6,597,812, Claims 1, 9, 14, 22, 28
`searches the dictionary for the new code word value for the new Pstring, which is
`
`equal to C (at box 224), and stores the dictionary code word for the new Pstring in
`
`Mcode (at box 225). ’812 patent at 9:50-61; Ex. 1101. It is assured that there will
`
`always be a dictionary code word for the new Pstring because Pstring has just
`
`been set equal to C, a single character, and the dictionary is initialized to contain
`
`code words for all single characters. Id. at 8:61-67; see also Storer Decl. at ¶ 60;
`
`Ex. 1102.
`
`Starting at box 202 (shown in Figure 2A) and continuing through boxes 203,
`
`204, 210, and so on, the encoder repeats the process of adding to the character
`
`string, one character at a time to update Pstring+C, until the character string
`
`Pstring+C is no longer found in the dictionary or a run length sequence is
`
`encountered. The process is repeated so long as there are remaining input
`
`characters. ’812 patent at 9:62-65; Ex. 1101. When there are no more input
`
`characters (e.g., “No” at box 202), the encoder outputs the dictionary code word
`
`for the last Pstring (at box 226) and outputs the end of stream control word (at box
`
`227), and the algorithm terminates. Id. at 9:65-10:3; see also Storer Decl. at ¶ 61;
`
`Ex. 1102.
`
`The ’812 patent also describes that a dictionary is initialized to include three
`
`control codes as well a