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-00167
`
`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-00167
`U.S. Patent No. 6,597,812 B1
`TABLE OF CONTENTS
`
`Page
`
`B. 
`
`B. 
`C. 
`
`I. 
`
`V. 
`
`MANDATORY NOTICES ............................................................................. 1 
`A. 
`Real Party-In-Interest ............................................................................ 1 
`B. 
`Related Matters ...................................................................................... 1 
`1. 
`Counsel And Service Information .............................................. 2 
`GROUNDS FOR STANDING PER SECTION 42.104(a) ............................. 3 
`II. 
`III.  CHALLENGE AND RELIEF REQUESTED................................................. 3 
`IV.  BACKGROUND AND STATE OF THE ART .............................................. 5 
`A. 
`Run Length Encoding Was Well-Known Before the Filing Date
`of the 812 Patent And Is Admitted Prior Art ........................................ 5 
`Dictionary Compression Was Well-Known Before The Filing
`Date Of The ’812 Patent And Is Admitted Prior Art ............................ 7 
`1. 
`LZ78 Dictionary Compression ................................................... 9 
`2. 
`LZW Dictionary Compression .................................................. 10 
`THE PRIOR ART .......................................................................................... 12 
`A.  O’Brien Combines Run Length
`Encoding And Dictionary Encoding ................................................... 12 
`1. 
`O’Brien Shows Run Length Encoding ..................................... 13 
`2. 
`O’Brien Shows Dictionary Encoding ....................................... 15 
`Nelson Provides Additional Details About Dictionary Encoding ...... 18 
`The Welch Patent Shows Compression
`Implemented In Either Hardware Or Software ................................... 20 
`The Heath Patent Shows Bit-Packing ................................................. 21 
`D. 
`VI.  OVERVIEW OF THE ’812 PATENT .......................................................... 23 
`A. 
`The ’812 Patent Combines Run
`Length Encoding And Dictionary Encoding ....................................... 24 
`Procedural History Of The ’812 Patent ............................................... 31 
`B. 
`VII.  STATEMENT OF THE PRECISE RELIEF REQUESTED ........................ 31 
`A. 
`Claims For Which Review Is Requested ............................................ 31 
`B. 
`Statutory Grounds For Challenge ........................................................ 31 
`
`
`
`i
`
`

`
`C. 
`D. 
`
`B. 
`
`C. 
`
`IPR2017-00167
`U.S. Patent No. 6,597,812 B1
`Level of Ordinary Skill In The Art ..................................................... 31 
`Claim Construction ............................................................................. 32 
`1. 
`Control Code Word ................................................................... 32 
`VIII.  THE CHALLENGED CLAIMS ARE NOT PATENTABLE ...................... 33 
`A.  Ground No. 1: Claims 1 And 28
`Are Obvious Over O’Brien In View Of Nelson.................................. 33 
`1.  Motivation To Combine ............................................................ 33 
`2. 
`Claim 1 Is Obvious Over O’Brien In View Of Nelson ............ 36 
`a) 
`O’Brien Discloses The Preamble ................................... 36 
`b) 
`O’Brien Discloses The “Detecting” Step ....................... 37 
`c) 
`O’Brien Discloses The First “Outputting” Step ............. 38 
`d) 
`O’Brien And Nelson Disclose The “Maintaining”
`Step ................................................................................. 40 
`O’Brien And Nelson Disclose The “Building” Step ...... 42 
`O’Brien And Nelson Disclose The “Searching” Step .... 43 
`O’Brien And Nelson Disclose
`The Second “Outputting” Step ....................................... 45 
`Independent Claim 28 Is Obvious
`Over O’Brien In View Of Nelson ............................................. 46 
`Ground No. 2: Claim Is 14 Obvious
`Over O’Brien In View Of Nelson And The Welch Patent ................. 50 
`1. 
`Claim 14 Is Obvious Over O’Brien
`In View Of Nelson And The Welch Patent .............................. 50 
`Ground No. 3: Claim 9 is Obvious Over O’Brien In View Of
`Nelson and Heath ................................................................................ 52 
`D.  Ground No. 4: Claim 22 is Obvious Over O’Brien In View Of
`Nelson, Welch and Heath .................................................................... 56 
`IX.  CONCLUSION .............................................................................................. 57 
`
`
`e) 
`f) 
`g) 
`
`3. 
`
`
`
`
`
`
`
`ii
`
`

`
`IPR2017-00167
`U.S. Patent No. 6,597,812 B1
`TABLE OF AUTHORITIES
`
` Page(s)
`
`Federal Cases
`In re Cuozzo Speed TechsLLC,
`793 F.3d 1268 (Fed. Cir. 2015), cert granted, 136 S.Ct. 890 (Jan 15,
`2016) ................................................................................................................... 32
`
`Federal Statutes
`
`5 U.S.C. § 102 .......................................................................................................... 32
`
`35 U.S.C. §§ 102(a), (b) and (e) ....................................................3, 4, 12, 18, 20, 21
`
`35 U.S.C. § 103 .............................................................................................. 3, 31, 32
`
`35 U.S.C. § 311 .................................................................................................... 1, 31
`
`Rules
`
`Fed. R. Evid. 803(16) ................................................................................................. 4
`
`Regulations
`
`37 C.F.R. § 42.15 ....................................................................................................... 1
`
`37 C.F.R. § 42.100 ..................................................................................................... 1
`
`37 C.F.R. § 42.100(b) .............................................................................................. 32
`
`
`
`
`
`
`
`iii
`
`

`
`IPR2017-00167
`U.S. Patent No. 6,597,812 B1
`
`LIST OF EXHIBITS
`Ex. 1001 U.S. Pat. No. 6,597,812, System and Method for Lossless Data
`Compression and Decompression, issued July 22, 2003 (“’812 patent”)
`
`Ex. 1002 U.S. Pat. No. 4,929,946, Adaptive Data Compression Apparatus
`Including Run Length Encoding for a Tape Drive System, issued May
`29, 1990 (“O’Brien”)
`
`Ex. 1003 Mark Nelson, The Data Compression Book, M&T Books, 1992
`(“Nelson”)
`
`Ex. 1004 U.S. Pat. No. 4,558,302, High Speed Data Compression and
`Decompression Apparatus and Method, issued December 10, 1985
`(“Welch patent”)
`
`Ex. 1005 Declaration of Prof. James Storer (“Storer Decl.” or “Storer
`Declaration”)
`
`Ex. 1006 A.H. Robinson and C. Cherry, “Results of a Prototype Television
`Bandwidth Compression Scheme,” Proceedings of the IEEE, 1967,
`55(3):356-64
`
`Ex. 1007 U.S. Pat. No. 3,560,639, Cascade Run Length Encoding Technique,
`issued February 2, 1971
`
`Ex. 1008 U.S. Pat. No. 4,626,829, Data Compression Using Run Length
`Encoding and Statistical Encoding, issued December 2, 1986
`
`Ex. 1009 U.S. Pat. No. 4,988,998, Data Compression System for Successively
`Applying at Least Two Data Compression Methods to an Input Data
`Stream, issued January 29, 1991
`
`Ex. 1010 U.S. Pat. No. 5,389,922, Compression Using Small Dictionaries with
`Applications to Network Packets, issued February 14, 1995
`
`Ex. 1011 U.S. Pat. No. 5,973,630, Data Compression for Use with a
`Communications Channel, issued October 26, 1999
`
`Ex. 1012
`
`J. Ziv and A. Lempel, “A Universal Algorithm for Sequential Data
`Compression,” IEEE Trans. Information Theory, Vol. 23, No. 3, May
`1977, pp. 337-43 (“LZ77”)
`
`
`
`iv
`
`

`
`Ex. 1013
`
`Ex. 1014
`
`Ex. 1015
`
`Ex. 1016
`
`IPR2017-00167
`U.S. Patent No. 6,597,812 B1
`J. Ziv and A. Lempel, “Compression of Individual Sequences via
`Variable-Rate Coding,” IEEE Trans. Information Theory, Vol. 24, No.
`5, Sept. 1978, pp. 530-36 (“LZ78”)
`
`T. Welch, “A Technique for High-Performance Data Compression,”
`IEEE Computer, Vol. 17, No. 6, June 1984, pp. 8-19 (“Welch article”)
`
`File History of U.S. Pat. No. 6,597,812, System and Method for
`Lossless Data Compression and Decompression, issued July 22, 2003
`
`Storer, Data Compression: Methods and Theory, Computer Science
`Press (1988) (“Storer 1988”)
`
`Ex. 1017 U.S. Patent No. 5,379,036 (“Storer ‘036”)
`
`Ex. 1018 U.S. Patent No. 4,876,541 (“Storer ‘541”)
`
`Ex. 1019 U.S. Patent No. 7,079,051 (“Storer ‘051”)
`
`Ex. 1020 Declaration of Dr. Scott Bennett (“Bennett Decl.”), as filed in IPR
`2016-00783
`
`Ex. 1021 Declaration of Charles D. Creusere (“Creusere Decl.”), as filed in IPR
`2016-00783
`
`Ex. 1022 Claim Construction Order, Realtime Data, LLC v. Oracle America,
`Inc., Civil Action No. 6:16-CV-88 at 33-37 (E.D. Tex. July 28, 2016)
`
`
`
`
`
`
`
`v
`
`

`
`IPR2017-00167
`U.S. Patent No. 6,597,812 B1
`Pursuant to 35 U.S.C. § 311 and 37 C.F.R. § 42.100, Oracle America, Inc.
`
`(“Petitioner”) respectfully requests inter partes review of claims 1, 9, 14, 22 and 28
`
`of U.S. Patent No. 6,597,812 B1 (“’812 patent”). The Director is hereby authorized
`
`to charge deposit account no. 02-4550 for the fee specified by 37 C.F.R. § 42.15,
`
`along with any additional fees required.
`
`As the petition in the instant case presents a challenge to some of the same
`
`claims challenged in IPR 2016-00783 and the Petitioner is a co-defendant with the
`
`IPR 2016-00783 Petitioners, this petition is accompanied by a motion for joinder.
`
`I. 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, and 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:
`
` 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;
`
`
`
`Page 1
`
`

`
`IPR2017-00167
`U.S. Patent No. 6,597,812 B1
` 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;
`
`The following co-pending IPRs would affect or could be affected by a
`
`decision in this proceeding: IPR 2017-00168, IPR 2016-00783.1
`
`Counsel And Service Information
`
`1.
`Lead Counsel: Monica Grewal (Registration No. 40,056)
`
`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). This petition is
`
`being filed with a motion requesting joinder to the ’783 petition.
`
`
`
`Page 2
`
`

`
`IPR2017-00167
`U.S. Patent No. 6,597,812 B1
`Back-up Counsel: Donald Steinberg (Registration No. 37,241)
`
`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.
`
`II. GROUNDS FOR STANDING PER SECTION 42.104(a)
`Petitioner certifies that the ’812 patent 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.
`
`III. CHALLENGE AND RELIEF REQUESTED
`Petitioner requests inter partes review of claims 1, 9, 14, 22, and 28
`
`(“challenged claims”) of the ’812 patent (Ex. 1001) and requests that the challenged
`
`claims be cancelled as unpatentable under 35 U.S.C. § 103.
`
`Petitioner relies on the following prior art as part of its Sec. 103 challenge
`
`combinations, as well other background prior art:
`
`1.
`
`U.S. Pat. No. 4,929,946, Adaptive Data Compression Apparatus
`
`Including Run Length Encoding for a Tape Drive System (“O’Brien,” Ex. 1002),
`
`which was issued May 29, 1990, and is prior art under 35 U.S.C. §§ 102(a) and (b).
`
`
`
`Page 3
`
`

`
`IPR2017-00167
`U.S. Patent No. 6,597,812 B1
`2. Mark Nelson, The Data Compression Book (“Nelson,” Ex. 1003),
`
`M&T Books, 1992, which is prior art under 35 U.S.C. §§ 102(a) and (b). The public
`
`availability of Nelson is demonstrated by its citation 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. 1016). See also Fed. R. Ev. 803(16)
`
`(Copyright page in Nelson is admissible to show the truth of the matters asserted.).)
`
`3.
`
`U.S. Pat. No. 4,558,302, High Speed Data Compression and
`
`Decompression Apparatus and Method (“Welch patent,” Ex. 1004), which issued
`
`December 10, 1985, and is prior art under 35 U.S.C. §§ 102(a) and (b).
`
`4.
`
`U.S. Pat. No. 5,973,630, Data Compression for Use with a
`
`Communications Channel (“Heath Patent,” Ex. 1011), which was filed March 1,
`
`1999 and issued October 26, 1999. The Heath patent 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).
`
`This Petition is supported by the Declaration of Dr. James Storer (“Storer
`
`Decl.” or “Storer Declaration,” Ex. 1005).
`
`Additional prior art cited throughout this Petition, including admitted prior
`
`art, is presented as evidence of the state of the art.
`
`
`
`Page 4
`
`

`
`IPR2017-00167
`U.S. Patent No. 6,597,812 B1
`IV. 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. Nonetheless, the ’812 patent claims the combination of these two
`
`techniques into a single compression algorithm. The claims were allowed on the
`
`first Office action. However, in view of the previously uncited art relied on in this
`
`Petition, the claims are unpatentable and should be cancelled.
`
`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.
`
`(Storer Decl. at ¶ 30; Ex. 1005.)
`
`
`
`Page 5
`
`

`
`IPR2017-00167
`U.S. Patent No. 6,597,812 B1
`
`
`While the basic concept of run length encoding is straightforward, there are
`
`several possible variations in its implementation. For example, many systems use 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.
`
`In some systems, multiple control codes are used with the specific control code
`
`selected providing information about the repetition count value. (Id. at ¶ 31.)
`
`Run-length encoding was well-known by the 1960’s, when it was used for
`
`television signals (see A.H. Robinson and C. Cherry, “Results of a Prototype
`
`Television Bandwidth Compression Scheme,” Proceedings of the IEEE, 1967,
`
`55(3):356-64; Ex. 1006) and facsimile transmissions (see U.S. Pat. No. 3,560,639,
`
`Cascade Run Length Encoding Technique, issued February 2, 1971; Ex. 1007). By
`
`the 1980’s, run length encoding was being paired with other encoding schemes.
`
`(See U.S. Pat. No. 4,626,829, Data Compression Using Run Length Encoding and
`
`Statistical Encoding, issued December 2, 1986; Ex. 1008). This trend continued into
`
`
`
`Page 6
`
`

`
`IPR2017-00167
`U.S. Patent No. 6,597,812 B1
`the late 1980’s and early 1990’s. (See, e.g., U.S. Pat. No. 4,988,998, Data
`
`Compression System for Successively Applying at Least Two Data Compression
`
`Methods to an Input Data Stream, issued January 29,1991; Ex. 1009; U.S. Pat. No.
`
`5,389,922, Compression Using Small Dictionaries with Applications to Network
`
`Packets, issued February 14, 1995; Ex. 1010; U.S. Pat. No. 5,973,630, Data
`
`Compression for Use with a Communications Channel, issued October 26, 1999;
`
`Ex. 1011.) (Storer Decl. at ¶ 32; Ex. 1005.)
`
`B. Dictionary Compression Was Well-Known Before The Filing Date
`Of The ’812 Patent And Is Admitted Prior Art
`
`Like run length encoding, dictionary encoding was known well before the
`
`filing date of the ’812 patent. In fact, the ’812 patent admits that dictionary
`
`compression was well known prior to the filing date of 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. (Storer Decl. at ¶ 33, Ex. 1005.) A data
`
`compression dictionary can be visualized as a table in which indices are mapped to
`
`“words” which can be characters, character strings, or other data blocks. The index
`
`can typically be represented by fewer bits than its corresponding word, so replacing
`
`the word with the index results in data compression. (Id.) During encoding, each
`
`time a word in the input stream is found in the dictionary, it is replaced with the
`
`index corresponding to that word. (Id.) For example, given the dictionary below,
`
`
`
`Page 7
`
`

`
`IPR2017-00167
`U.S. Patent No. 6,597,812 B1
`the string “dictionary data compression is well known” could be encoded as “3 2 1 is
`
`well 4”. (Id.)
`
`
`Dictionaries can be static, meaning that the words they contain are fixed
`
`before the encoding process starts, and do not change over the course of the
`
`encoding process. (Id. at ¶ 36). Alternatively, the dictionary can be adaptive,
`
`meaning that words from the input stream are added to the dictionary during the
`
`compression process. (Id.) Many modern adaptive dictionary encoders trace their
`
`roots to Lempel and Ziv’s groundbreaking papers in 1977 (“LZ77”) and 1978
`
`(“LZ78”). (J. Ziv and A. Lempel, “A Universal Algorithm for Sequential Data
`
`Compression,” IEEE Trans. Information Theory, Vol. 23, No. 3, May 1977, pp.
`
`337-43; Ex. 1012 and J. Ziv and A. Lempel, “Compression of Individual Sequences
`
`via Variable-Rate Coding,” IEEE Trans. Information Theory, Vol. 24, No. 5, Sept.
`
`1978, pp. 530-36; Ex. 1013.) (Storer Decl. at ¶ 36; Ex. 1005.)
`
`LZ77 and LZ78 both describe adaptive dictionary encoders. (Id.) In LZ77,
`
`dictionary indices point to character strings found in a “sliding window” dictionary
`
`of previously encoded data. LZ77 dictionary compression is not used in the prior art
`Page 8
`
`
`
`

`
`IPR2017-00167
`U.S. Patent No. 6,597,812 B1
`forming the basis for this petition and is not discussed further. In LZ78, indices are
`
`mapped to data blocks from the input stream to build the dictionary during the
`
`encoding process. (Id.) The prior art relied on in this Petition uses a variation of
`
`LZ78 encoding. Accordingly, LZ78 is explained in more detail below.
`
`LZ78 Dictionary Compression
`
`1.
`The signature feature of LZ78 is the algorithm used to build the dictionary as
`
`it encodes the input stream. (Id. at ¶ 37.) In the LZ78 algorithm the characters of the
`
`input stream are read one at a time. (Id.) 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.
`
`(Id.) The dictionary is then searched to see if the combined prefix string/last
`
`character is present in the dictionary. (Id.) 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. (Id.) 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. (Id.) 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. (Id.)
`
`
`
`Page 9
`
`

`
`IPR2017-00167
`U.S. Patent No. 6,597,812 B1
`
`
`A simple example of compression using this algorithm is set forth by Dr.
`
`Storer in his accompanying declaration. (Id. at ¶¶ 38-39.)
`
`LZW Dictionary Compression
`
`2.
`In 1984, Terry Welch described a particular variation of LZ78 that has
`
`become known as LZW, for Lempel-Ziv-Welch. (T. Welch, “A Technique for
`
`High-Performance Data Compression,” IEEE Computer, Vol. 17, No. 6, June 1984,
`
`pp. 8-19; Ex. 1014 (“Welch article”).) Welch provided the following pseudocode,
`
`below left, for his algorithm. (Id. at 15-16.) Based on this pseudocode, a flow chart,
`
`below right, can be created. (Storer Decl. at ¶ 40; Ex. 1005.)
`
`
`
`Page 10
`
`

`
`IPR2017-00167
`U.S. Patent No. 6,597,812 B1
`
`
`A step-by-step example of encoding a string using an LZW algorithm is set
`
`forth in the accompanying Storer Declaration. (Id. at ¶¶ 41-42.)
`
`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. (Id. at ¶ 43.) 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. (Id.) Also, according to LZW, when the
`
`
`
`Page 11
`
`

`
`IPR2017-00167
`U.S. Patent No. 6,597,812 B1
`combined prefix string/last character (ωK) is not found in the dictionary, the prefix
`
`string is set to be the last character (ω = K). (Id.)
`
`V. THE PRIOR ART
`This Petition relies on four pieces of prior art to challenge claims of the ’812
`
`patent, in addition to prior art and admissions showing the state of the art at the time
`
`of the ’812 patent’s filing date.
`
`A. O’Brien Combines Run Length
`Encoding And Dictionary Encoding
`
`The primary reference supporting the challenges in this Petition is U.S. Patent
`
`No. 4,929,946, Adaptive Data Compression Apparatus Including Run Length
`
`Encoding for a Tape Drive Apparatus, to John T. O’Brien, et al., (Ex. 1002,
`
`“O’Brien” or “O’Brien 946”). O’Brien issued May 29, 1990. As such, O’Brien is
`
`prior art under 35 U.S.C. §§ 102(a) and (b). O’Brien was not cited or considered by
`
`the Patent Office during the prosecution of the ’812 patent.
`
`As illustrated in O’Brien’s Fig. 3, below, O’Brien shows a compression
`
`system that combines a run length encoder 303 with a dictionary encoder 304.
`
`Although O’Brien uses the term “reference value encoder” or “string compression”
`
`instead of “dictionary encoder,” O’Brien’s description of this encoder bears the
`
`signature of an LZ78 dictionary encoder and additional LZW features, as explained
`
`below. (Storer Decl. at ¶ 47; Ex. 1005.)
`
`
`
`Page 12
`
`

`
`IPR2017-00167
`U.S. Patent No. 6,597,812 B1
`
`1. O’Brien Shows Run Length Encoding
`In O’Brien, run length encoding takes priority over string encoding.
`
`
`
`(O’Brien, 4:4-5; Ex. 1002.) Run length encoder 303 monitors three input bytes: the
`
`last byte currently being processed by the reference value encoder 304 and the next
`
`two bytes to be input. (Id. at 9:19-27.) If the three bytes are the same, a run is
`
`detected. (Id. at 9:29-34.) O’Brien does not use run length encoding for runs of only
`
`two bytes. If the three bytes are the same, the run length encoder 303 transmits a
`
`“run length detect signal” to the reference value encoder 304. (Id.) The reference
`
`value encoder 304 encodes the last byte it received, which it is currently processing
`
`and which starts the repeated characters of the run length sequence, inserts into the
`
`compressed data stream the “reference value” for the last byte (or reference value for
`
`the matched string that ends with the last byte), and transfers control to the run
`
`length encoder 303. (Id.) The run length encoder 303 continues to monitor input
`Page 13
`
`
`
`

`
`IPR2017-00167
`U.S. Patent No. 6,597,812 B1
`bytes, counting them to determine the length of the run length sequence. (Id. at
`
`9:34-41.) When the end of the run is reached, the run length encoder 303 encodes
`
`the length into a repeat code. (Id. at 9:41-45.) This repeat code is output to the
`
`reference value encoder 304, which represents the repeat code using an appropriate
`
`reference value and bits for the repeat count. (Id. ) The reference value encoder 304
`
`inserts the run length reference value and bits indicating the repeat count into the
`
`compressed data stream. (Id. at 9:45-47; see also Storer Decl. at ¶48; Ex. 1005.)
`
`O’Brien defines and uses several pre-defined run length reference values to
`
`encode run length sequences. (Id. at12:63-65.) “Each run length reference value
`
`defines a range of repeat counts.” (Id. at12:65-66.) This use of multiple, predefined
`
`ranges for repeat counts allows for repeat codes to be encoded using fewer bits on
`
`average, since short, common repeat counts are coded with fewer bits than long,
`
`uncommon repeat counts. (Id. at 12:66-69.) An exemplary table of run length
`
`reference values is set forth by O’Brien in Table A, below:
`
`
`
`
`
`Page 14
`
`

`
`IPR2017-00167
`U.S. Patent No. 6,597,812 B1
`(Id. at 13:3-17.) In this way, the compression of O’Brien encodes a run length
`
`sequence using: 1) the last character encoded by the reference value encoder 304
`
`before the run is encoded (which is the repeated character); 2) a reference value that
`
`tells the decoder that a run length has been encoded as well as the number of bits in a
`
`repeat count; and 3) the repeat count. (Storer Decl. at ¶ 49; Ex. 1005.)
`
`2. O’Brien Shows Dictionary Encoding
`In O’Brien, “[d]ata bytes that are not part of a run-length are encoded by
`
`reference value encoder 304 into a code value based on the lookup table stored in
`
`compression string table 306.” (O’Brien at 9:48-51; Ex. 1002.) As will be apparent
`
`from the explanation below, O’Brien’s reference value encoder 304 is an example of
`
`an LZW variation of the LZ78 dictionary encoder. (Storer Decl. at ¶ 50; Ex. 1005.)
`
`First, O’Brien initializes the dictionary with code words for all possible single
`
`characters. In particular, at the beginning of each data segment, the reference value
`
`encoder 304 is provided with two variables, END and BEGIN, which correspond to
`
`the largest and smallest individual character codes in the data segment. (O’Brien at
`
`10:19-25; Ex. 1002.) These variables define the range of reference values, or code
`
`words, which represent single characters and are known as “character reference
`
`values.” (Id. at 10:22-28.) Setting this range of character reference values and the
`
`associated single characters is analogous to the initialization of the LZW dictionary
`
`with all possible single characters. (Storer Decl. at ¶ 51; Ex. 1005.)
`
`
`
`Page 15
`
`

`
`IPR2017-00167
`U.S. Patent No. 6,597,812 B1
`In addition to initializing the dictionary with code words for all single
`
`characters, the dictionary in O’Brien is initialized to contain indices corresponding
`
`to the run length indicators. (O’Brien at 12:55-13:17; Ex. 1002.) As discussed
`
`above, these indices, or control codes, are listed in Table A. These control codes
`
`instruct the decoder that a run length sequence has been encoded. (Id. at 13:37-43;
`
`Storer Decl. at ¶ 52; Ex. 1005.)
`
`After the dictionary is initialized, the reference value encoder 304 of O’Brien
`
`implements the signature features of an LZ78 dictionary encoder. In particular,
`
`reference values above the character reference value range are used to encode strings
`
`of multiple bytes and are known as “string reference values.” (Id. at 10:28-31.)
`
`These string reference values are added to the dictionary by mapping them to new
`
`strings built from the input data. (Storer Decl. at ¶ 53; Ex. 1005.)
`
`In operation, the reference value encoder 304 combines the character or string
`
`represented by the previous reference value with the character indicated by next byte
`
`from the input stream. (O’Brien at 12:33-36; Ex. 1002.) The reference value
`
`encoder 304 then determines whether the “resultant string” is found in the string
`
`table 306. (Id. at 12:36-38.) If so, the previous reference value is updated to be the
`
`string reference value for the matched, resultant string found in the string table 306.
`
`Then, the next input byte is combined with the resultant string to produce a new
`
`string, and the string table 306 is searched again to see if the new string is present.
`
`
`
`Page 16
`
`

`
`IPR2017-00167
`U.S. Patent No. 6,597,812 B1
`(Id. at 12:38-43.) This process is repeated, adding to the string one character at a
`
`time, until a string is created that is not in the string table. (Id. at 12:43-44). When
`
`this occurs, the previous reference value (for the last string found in the string table
`
`306 or an individual character) is output, and the current string is added to the string
`
`table 306 and assigned the next available reference value. (Id. at 12:44-48.) The
`
`previous reference value is updated to be the reference value for the final character
`
`of the current string, which caused the current string not to be found in the string
`
`table 306. The entire process is then repeated using the next input byte. (Id. at
`
`12:48-50; see also Storer Decl. at ¶ 54; Ex. 1005).
`
`Although O’Brien does not include a flow chart, the flow chart below can be
`
`created from the written description of O’Brien’s reference value encoder 304.
`
`(Storer Decl. at ¶ 55 Ex. 1005.) As can be seen, O’Brien’s reference value encoder
`
`uses the signature LZ78 features of 1) reading the next input character; 2) adding the
`
`next input character to the current prefix string to build a new, combined string; 3)
`
`searching the dictionary to see if the new string is found; 4) if so, continuing by
`
`updating the prefix string, building the new string by adding one character at a time,
`
`and continuing to search the dictionary until the new string is not found; 5) when the
`
`new string is not found in the dictionary, outputting the reference value for the prefix
`
`string and adding the new string to the dictionary. (Id.) As in LZW, O’Brien’s
`
`encoder also includes features of initialization of code words (character reference
`
`
`
`Page 17
`
`

`
`IPR2017-00167
`U.S. Patent No. 6,597,812 B1
`values) for individual characters and setting the prefix string (referenced by last RV)
`
`to be the last input character when a combined string is not found in the string table.
`
`As such, it is a classic LZW dictionary encoder. (Id.)
`
`
`B. Nelson Provides Additional Details About Dictionary Encoding
`A secondary reference used for all challenges in this Petition is Mark Nelson,
`
`The Data Compression Book, M&T Books, 1992 (“Nelson,” Ex. 1003). Nelson was
`
`published in 1992 and is prior art un