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
`
`DECLARATION OF PROFESSOR JAMES A. STORER, Ph.D.
`
`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
`
`ORACLE 1 102
`
`

`
`IPR2017—00168: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`TABLE OF CONTENTS
`
`II-‘-I
`
`BACKGROUND AND QUALIFICATIONS ............................................... ..1
`
`MATERIALS REVIEWED .......................................................................... ..4
`
`III.
`
`THE RELEVANT LEGAL STANDARDS .................................................. ..6
`
`A.
`
`B.
`
`C.
`
`Claim Construction ............................................................................. ..6
`
`Anticipation ......................................................................................... ..6
`
`Obviousness ......................................................................................... ..8
`
`IV.
`
`BACKGROUND AND STATE OF THE ART .......................................... ..11
`
`A.
`
`B.
`
`Run Length Encoding Was Well—Known Before the Filing Date
`of the ’8l2 Patent And ls Admitted Prior Art ................................... .. 11
`
`Dictionary Compression Was Well—Known Before The Filing
`Date Of The ’8 12 Patent And Is Admitted Prior Art ........................ .. 13
`
`1.
`
`2.
`
`LZ78 Dictionary Compression ............................................... .. 15
`
`LZW Dictionary Compression ................................................ .. 18
`
`OVERVIEW OF THE ’812 PATENT ........................................................ ..26
`
`A.
`
`B.
`
`C.
`
`Priority ............................................................................................... ..26
`
`Brief Description ............................................................................... ..26
`
`Prosecution History of the ’812 patent .............................................. ..32
`
`VI.
`
`CLAIM CONSTRUCTION ........................................................................ ..32
`
`1.
`
`Control Code Word ................................................................. ..33
`
`VII.
`
`PRIOR ART REFERENCES ...................................................................... ..33
`
`A.
`
`B.
`
`C.
`
`Seroussi ............................................................................................. ..33
`
`Heath .................................................................................................. ..41
`
`Nelson ................................................................................................ ..43
`
`VIII.
`
`THE CHALLENGED CLAIMS ARE NOT PATENTABLE .................... ..45
`
`IX.
`
`IDENTIFICATION OF HOW CLAIMS 1, 9, 14, 22, 28 ARE
`UNPATENTABLE ...................................................................................... ..45
`
`A.
`
`Ground 1: Claims 1, 9, 14, and 22 are Obvious in View of
`Seroussi and Heath ............................................................................ ..45
`
`1.
`
`Motivation to Combine Seroussi and Heath ........................... ..45
`
`

`
`1PR2017—00l68: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`2.
`
`Independent Claim 1 is Obvious in View of Seroussi and
`Heath. ...................................................................................... ..46
`
`i.
`
`ii.
`
`iii.
`
`iv.
`
`v.
`
`vi.
`
`The preamble of Claim 1 is disclosed in Seroussi ........ ..47
`
`Limitation A of Claim 1 is obvious in View of
`
`Seroussi and Heath. ...................................................... ..48
`
`Limitation B of Claim 1 is disclosed in Seroussi. ........ ..52
`
`Limitation C of Claim 1 is disclosed in Seroussi. ........ ..56
`
`Limitation D of Claim 1 is disclosed in Seroussi. ........ ..59
`
`Limitation E of Claim 1 is disclosed in Seroussi. ........ ..60
`
`vii.
`
`Limitation F of Claim 1 is disclosed in Seroussi .......... ..60
`
`3.
`
`4.
`
`Dependent Claim 9 Obvious in View Seroussi and Heath. ......61
`
`Independent Claim 14 is Obvious in View of Seroussi
`and Heath. ............................................................................... ..64
`
`i.
`
`ii.
`
`iii.
`
`iv.
`
`V.
`
`vi.
`
`The preamble of Claim 14 is disclosed in Seroussi ...... ..65
`
`Limitation A of Claim 14 is obvious in view of
`
`Seroussi and Heath. ...................................................... ..66
`
`Limitation B of Claim 14 is disclosed in Seroussi. ...... _.66
`
`Limitation C of Claim 14 is disclosed in Seroussi. ...... _-66
`
`Limitation D of Claim 14 is disclosed in Seroussi ....... _.66
`
`Limitation E of Claim 14 is disclosed in Seroussi. ...... ..67
`
`vii.
`
`Limitation F of Claim 14 is disclosed in Seroussi ........ ..67
`
`5.
`
`Dependent Claim 22 is Obvious in View of Seroussi and
`Heath. ...................................................................................... ..67
`
`B.
`
`Ground 2: Claim 28 is Anticipated by Seroussi ................................ ..68
`
`1.
`
`Independent Claim 28 is Disclosed in Seroussi. ..................... ..68
`
`i.
`
`ii.
`
`iii.
`
`iv.
`
`The preamble of Claim 28 is disclosed in Seroussi ...... ..68
`
`Limitation A of Claim 28 is disclosed in Seroussi ....... ..69
`
`Limitation B of Claim 28 is disclosed in Seroussi. ...... .-73
`
`Limitation C of Claim 28 is disclosed in Seroussi _______ _.78
`
`C.
`
`Ground 3: Claim 28 is Obvious in view of Seroussi and Nelson ..... ..80
`
`1.
`
`Motivation to Combine Seroussi and Nelson ......................... ..80
`
`

`
`lPR2017—00l68: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`2.
`
`Independent Claim 28 is Obvious in view of Seroussi and
`Nelson ..................................................................................... .. 81
`
`i.
`
`ii.
`
`iii.
`
`iv.
`
`The preamble of Claim 28 is disclosed in Seroussi ...... ..82
`
`Limitation A of Claim 28 is obvious in view of
`
`Seroussi and Nelson ...................................................... ..82
`
`Limitation B of Claim 28 is disclosed in Seroussi. ...... .-84
`
`Limitation C of Claim 28 is disclosed in Seroussi. ...... ..84
`
`X.
`
`Conclusion ................................................................................................... ..85
`
`iii
`
`

`
`lPR20 1 7-00 1 68: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`1, Prof. James A. Storer, Ph-D., declare as follows:
`
`I.
`
`BACKGROUND AND QUALIFICATIONS
`
`1.
`
`My name is James Storer.
`
`I am a Professor at Brandeis University in
`
`the Computer Science Department.
`
`I am an expert in the field of computer
`
`algorithms, including data communications and intemet related computing, data
`
`compression, data and image retrieval, storage and processing of large data sets,
`
`and image/video processing.
`
`1 have studied, researched, and practiced in the field
`
`of computer science for more than 35 years, and have taught Computer Science at
`
`Brandeis since 1981.
`
`2.
`
`I received my Doctor of Philosophy (Ph.D.) degree in the field of
`
`Computer Science from Princeton University in 1979.
`
`I received my Masters of
`
`Arts (M.A.) degree in Computer Science from Princeton University and my
`
`Bachelor of Arts (BA) degree in Mathematics and Computer Science from
`
`Cornell University.
`
`3.
`
`After receiving my Ph.D. degree, I worked in industry as a researcher
`
`at AT&T Bell Laboratories from 1979 to 1981 before joining the faculty of
`
`Brandeis University.
`
`4.
`
`I have been involved in computer science research since 1976. My
`
`research has been funded by a variety of governmental agencies, including the
`
`National Science Foundation (NSF), National Aeronautics and Space
`
`1
`
`

`
`IPR20 1 7-00 1 68: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14,22,28
`
`Administration (NASA), and Defense Advanced Research Projects Agency
`
`(DARPA).
`
`In addition, I have received government Small Business Innovation
`
`Research (SBIR) funding, as well as numerous industrial grants.
`
`5.
`
`I regularly teach courses in software and hardware technology for data
`
`compression and communications (including text, images, video, and audio) at
`
`both the undergraduate and graduate level, and in my capacity as co—chair of the
`
`Annual Data Compression Conference, I regularly referee academic papers in these
`
`areas.
`
`In addition, much of my consulting activity has been in the areas of
`
`software and hardware for consumer electronic devices, including cell
`
`phones/PDAs (including cellular technology), smartphones, digital cameras, digital
`
`video and audio recorders, and personal computers (“PCS”), as well as devices for
`
`communications over the Internet.
`
`6.
`
`I am the author of two books: An Introduction to Data Structures and
`
`Algorithms and Data (.‘ompresst'on.' Methods and Theory (Ex. 1115). Both books
`
`have been used as references for undergraduate level computer science courses in
`
`universities.
`
`I am the editor or co—editor of four other books, including
`
`Hyperspectral Data C()mpre.s'.sir)rt and Image and Text Compres.s't'ort.
`
`7.
`
`I have three issued U.S. patents that relate to computer software and
`
`hardware (two for which I am sole inventor and one for which I am co—inventor).
`
`

`
`IPR20 1 7-00 1 68: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`These are submitted herewith as Exhibits 1116-1118.
`
`I am the author or co-author
`
`of well over 100 articles and conference papers.
`
`8.
`
`In 1991, I founded the Annual Institute of Electrical and Electronics
`
`Engineers (IEEE) Data Compression Conference (DCC), the first major
`
`international conference devoted entirely to data compression, and have served as
`
`the conference chair since then.
`
`9.
`
`I routinely serve as referee for papers submitted to journals such as,
`
`for example, JACM, SICOMP, Theoretical CS, Computer Journal, J. Algorithms,
`
`Signal Processing, JPDC, Acta Informatica, Algorithmicia, IPL, IPM, Theoretical
`
`CS, J. Algorithms, Networks, IEEE J. Robotics & Automation, IEEE Trans.
`
`Information Theory, IEEE Trans. Computers, IEEE Trans. Image Processing,
`
`Proceedings of the IEEE, IBM J. of R&D, and J. Computer and System Sciences.
`
`10.
`
`I have served as guest editor for a number of professional journals,
`
`including Proceedings of the IEEE, Journal of Visual Communication and Image
`
`Representation, and Information Processing and Management.
`
`I have served as a
`
`program committee member for various conferences, including IEEE Data
`
`Compression Conference, IEEE International Symposium on Information Theory,
`
`Combinatorial Pattern Matching (CPM), International Conference on String
`
`Processing and Information Retrieval (SPIRE), Conference on Information and
`
`Knowledge Management (CIKM), Conference on Information Theory and
`
`

`
`lPR2017—00168: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`Statistical Learning (ITSL), Sequences and Combinatorial Algorithms on Words,
`
`Dartmouth Institute for Advanced Graduate Studies Symposium (DAGS),
`
`International Conference on Language and Automata Theory and Applications
`
`(LATA), DIMACS Workshop on Data Compression in Networks and
`
`Applications, Conference on Combinatorial Algorithms on Words.
`
`11. A copy of my latest curriculum vitae (C.V.) is attached as Appendix
`
`12. My compensation is in no way contingent on the results of these or
`
`any other proceedings relating to the above-captioned patent.
`
`II. MATERIALS REVIEWED
`
`13.
`
`I have carefully reviewed U.S. Patent No. 6,597,812 patent (the ‘”812
`
`patent”).
`
`14.
`
`For convenience, a list of the information that I considered in arriving
`
`at my opinions is attached as Appendix B.
`
`I understand that the prior art relied on
`
`in this petition includes:
`
`I U.S. Patent No. 5,389,922 to Seroussi (“Seroussi,” Ex. 1103).
`
`Seroussi was filed on April 13, 1993, and issued on February 14,
`
`1995.
`
`I have been informed that Seroussi qualifies as prior art.
`
`0 U.S. Patent No. 5,973,630 to Heath (“Heath,” Ex. 1104). Heath was
`
`filed on March 1, 1999, and issued on October 26, 1999.
`
`I understand
`
`

`
`IPR20l7-00168: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`that Heath claims priority to and is a divisional application of U.S.
`
`Application No. 08/982,864, filed December 2, 1997.
`
`I have been
`
`informed that Heath is prior art.‘
`
`I Mark Nelson, The Data C()mpre.s'.s'z'(m Book, lVl&T Books 1992
`
`(“Nelson,” Ex. 1 105). Nelson was published in 1992.
`
`I have been
`
`informed that Nelson is prior art under 35 U.S.C. §§ 102(a) and (b).
`
`15.
`
`Furthermore, I have reviewed the Declaration of Charles D. Creusere
`
`in Support of SAP America, Inc., et al.’s Petition for z'm‘erparte.s' review of claims
`
`1-4, 8, 14-17, 21 and 28 ofthe ’812 patent (“Creusere Decl.,” Ex. llll ). See SAP
`
`America Inc, et al. v. Realtime Dam LL(‘ d/b/a IX(), Case No. IPR20l6—00783,
`
`Paper No. 1, Ex. 1105 (PTAB April 1, 2016).
`
`I agree with Dr. Creusere’s
`
`statements in the Creusere Decl. and have included relevant portions below.
`
`16.
`
`Based on my review of these materials, I believe that the relevant field
`
`for purposes of the ’812 patent is systems and methods of data compression and
`
`decompression.
`
`' I have been informed that U.S. Patent No. 5,973,630, which was not cited, claims
`
`priority to U.S. Patent No. 5,955,976, which was cited, and was briefly noted by
`
`the Examiner in a first action allowance to “disclose methods for using run-length
`
`encoding and dictionary.” See ’8l2 File History at 98-99; Ex. 1110.
`
`

`
`IPR20 1 7-00 1 68: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14,22,28
`
`17.
`
`As described in Section I above, I have extensive experience in
`
`computer science and data compression and decompression. Based on my
`
`experience, I have a good understanding of the relevant field in the relevant
`
`timeframe (which is discussed in Section IV below).
`
`III. THE RELEVANT LEGAL STANDARDS
`
`18.
`
`I am not an attorney. For the purposes of this declaration, I have been
`
`informed about certain aspects of the law that are relevant to my opinions. My
`
`understanding of the law is as follows:
`
`A.
`
`Claim Construction
`
`19.
`
`I have been informed that claim construction is a matter of law and
`
`that the final claim construction will ultimately be determined by the Board. For
`
`the purposes of my invalidity analysis in this proceeding and with respect to the
`
`prior art, I have applied the broadest reasonable construction of the claim terms as
`
`they would be understood by one skilled in the relevant art.
`
`20.
`
`I have been informed and understand that a claim in inter parres
`
`review is given the “broadest reasonable construction in light of the specification.”
`
`37 C.F.R. § 42.l00(b).
`
`I have also been informed and understand that any claim
`
`term that lacks a definition in the specification is therefore also given a broad
`
`interpretation.
`
`B.
`
`Anticipation
`
`

`
`1PR2017—00l68: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`21.
`
`I have been informed and understand that a patent claim is invalid as
`
`“anticipated” if each element of that claim is present either explicitly or inherently
`
`in a single prior art reference.
`
`22.
`
`I have been informed that, under the principle of inherency, a prior art
`
`reference may anticipate a claimed invention even if the reference does not
`
`expressly disclose every limitation of the later invention, so long as any limitation
`
`not expressly disclosed is necessarily present in the reference. I have also been
`
`informed that to be an inherent disclosure, the limitation must necessarily be
`
`contained in the prior art reference and the mere fact that the method or system
`
`described in the reference might possibly (or sometimes) practice or contain a
`
`claimed limitation is insufficient to establish that the reference inherently teaches
`
`the limitation.
`
`23.
`
`I have been informed that material not explicitly contained in a single,
`
`prior art document may still be considered for purposes of anticipation if that
`
`material is incorporated by reference into the prior art document.
`
`24.
`
`I have also been informed and understand that a prior art reference is
`
`considered enabling when the reference permits a person having ordinary skill in
`
`the field of technology of the patent to make and use the disclosed technology
`
`without having to conduct undue experimentation. However, some amount of
`
`experimentation to make and use the invention is allowable.
`
`

`
`lPR20 1 7-00 1 68: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`C.
`
`Obviousness
`
`25.
`
`It is my opinion that a person of ordinary skill in the art at the time the
`
`’8 1 2 patent was effectively filed, is a person who has an undergraduate degree in
`
`computer science and two years’ industry experience or a graduate degree in the
`
`field of data compression.
`
`26.
`
`Based on my experience, I have an understanding of the capabilities
`
`of a person of ordinary skill in the relevant field.
`
`I have supervised and directed
`
`many such persons over the course of my career. Further, I had at least those
`
`capabilities myself at the time the patent was filed.
`
`27.
`
`The analysis set forth herein evaluates obviousness and priority issues
`
`consistent with the foregoing principles and through the eyes of one of ordinary
`
`skill in the art at the time of filing (which is discussed in Sections V.A and IX
`
`below).
`
`28.
`
`I have been informed and understand that a patent claim can be
`
`considered to have been obvious to a person of ordinary skill in the art at the time
`
`the application was filed. This means that, even if all of the requirements of a
`
`claim are not found in a single prior art reference, the claim is not patentable if the
`
`differences between the subject matter in the prior art and the subject matter in the
`
`claim would have been obvious to a person of ordinary skill in the art at the time
`
`the application was filed.
`
`

`
`lPR20 1 7-00 1 68: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14,22,28
`
`29.
`
`I have been informed and understand that a determination of whether
`
`a claim would have been obvious should be based upon several factors, including,
`
`among others:
`
`0
`
`the level of ordinary skill in the art at the time the application was
`
`filed;
`
`0
`
`the scope and content of the prior art;
`
`0 what differences, if any, existed between the claimed invention and
`
`the prior art.
`
`30.
`
`I have been informed and understand that the teachings of two or
`
`more references may be combined in the same way as disclosed in the claims, if
`
`such a combination would have been obvious to one having ordinary skill in the
`
`art. In determining whether a combination based on either a single reference or
`
`multiple references would have been obvious, it is appropriate to consider, among
`
`other factors:
`
`0 whether the teachings of the prior art references disclose known
`
`concepts combined in familiar ways, and when combined, would yield
`
`predictable results;
`
`0 whether a person of ordinary skill in the art could implement a
`
`predictable variation, and would see the benefit of doing so;
`
`

`
`lPR20 1 7-00 1 68: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1,9,14,22,28
`
`0 whether the claimed elements represent one of a limited number of
`
`known design choices, and would have a reasonable expectation of
`
`success by those skilled in the art;
`
`I whether a person of ordinary skill would have recognized a reason to
`
`combine known elements in the manner described in the claim;
`
`0 whether there is some teaching or suggestion in the prior art to make
`
`the modification or combination of elements claimed in the patent;
`
`and
`
`0 whether the innovation applies a known technique that had been used
`
`to improve a similar device or method in a similar way.
`
`31.
`
`I understand that one of ordinary skill in the art has ordinary
`
`creativity, and is not an automaton.
`
`32.
`
`I understand that in considering obviousness, it is important not to
`
`determine obviousness using the benefit of hindsight derived from the patent being
`
`considered.
`
`33.
`
`Given this standard, the Board should conclude, based on the
`
`information in this petition, that the challenged claims are merely a predictable
`
`combination of old elements that are used according to their established functions.
`
`10
`
`

`
`1PR2017—00l68: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`IV. BACKGROUND AND STATE OF THE ART
`
`34.
`
`The ’812 patent relates to two data compression techniques—run
`
`length encoding and dictionary encoding. The background of the ’8l2 patent
`
`admits that both of these encoding techniques were well known prior to the filing
`
`date ofthe ’8l2 patent.
`
`’812 patent at 2259-322; Ex. 1101.
`
`A.
`
`Run Length Encoding Was Well-Known Before the Filing Date of
`the ’812 Patent And Is Admitted Prior Art
`
`35.
`
`The ’812 patent notes that run length encoding was well known prior
`
`to the filing date of the ’812 patent.
`
`’8 12 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 3A3B3 C4B5C4A.
`
`|nitia|String
`S
`|dentifyRunS
`
`c
`Encfide
`
`Output
`
`AAABBBCCCBBBBCCCCCAAAA
`
`AAABBBCCCBBBBCCCCCAAAA
`
`LHLH
`3A
`3B
`
`*—4i:H—"—H
`5C
`4A
`
`3C
`
`3A3B3C4B5C4A
`
`Illustration of Run length Encoding
`
`36. While the basic concept of run length encoding is straightforward,
`
`there are several possible Variations in its implementation. For example, many
`
`1]
`
`

`
`IPR2017—00168: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`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-
`
`37.
`
`Run length encoding was well-known by the 1960’s, when it was used
`
`for television signals (see AH. Robinson and C. Cherry, “Results of a Prototype
`
`Television Bandwidth Compression Scheme,” Proceedings ofthe IEEE, 1967,
`
`55(3):356-64; Ex. 1106) and facsimile transmissions (see Centanni, U.S. Pat. No.
`
`3,560,639, (.‘ascade Run Length Encoding Technique, issued February 2, 1971; Ex.
`
`1107). By the 1980’s, run length encoding was being paired with other encoding
`
`schemes. (See Hauck, U.S. Pat. No. 4,626,829, Data Compression Using Run
`
`Length Encoding and Siaiisiical Encoding, issued December 2, 1986; Ex. 1108.)
`
`This trend continued into the late 1980’s and early 1990’s. See, eg. , O’Brien,
`
`U.S. Pat. No. 4,988,998, Data (_.‘ompre.s'.s'ion ifijistemfor Succes.s'ive1y Applying at
`
`Iieasi Yiw) 1)ai'a Compression Methods to an Input Data Stream, issued January
`
`29,1991; Ex. 1109; Seroussi, U.S. Pat. No. 5,389,922, (_.‘ompression Using Small
`
`Dictionaries with Applications to Network Packets’, issued February 14, 1995; Ex.
`
`1 103; Heath, U.S. Pat. No. 5,973,630, Data Compression_for Use with a
`
`(.‘oninninicati0n.s' Channel, issued October 26, 1999; Ex. 1104. Run length
`
`encoding is frequently used in combination with Huffman coding and is part of
`
`12
`
`

`
`IPR20 1 7-00 1 68: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14,22,28
`
`major industry specifications and standards adopted in the l980’s and l990’s, such
`
`as TIFF and JPEG.
`
`B.
`
`Dictionary Compression Was Well-Known Before The Filing Date
`Of The ’812 Patent And Is Admitted Prior Art
`
`38.
`
`Like run length encoding, dictionary encoding was known well before
`
`the filing date of the ’8l2 patent.
`
`In fact, the ’8l2 patent admits that dictionary
`
`compression was well known prior to the filing date of the ’8l2 patent. ’8l2
`
`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 I is well 4”.
`
`Index
`
`String
`
`1
`
`2
`
`3
`
`4
`
`"compression"
`
`"data"
`
`"dictionary"
`
`"known"
`
`Dictionary
`
`39.
`
`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
`
`13
`
`

`
`IPR2017—0O168: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`stream is found in the dictionary, it is replaced with the index corresponding to that
`
`string of data.
`
`40.
`
`For decompression, a decoder uses the same dictionary to reverse the
`
`compression process. The decoder looks up indices in a compressed data stream
`
`and replaces them with the corresponding “words” from the dictionary.
`
`41.
`
`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.
`
`42.
`
`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. Altemately, 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”). 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. 1112; and J. Ziv and A. Lempel, “Compression of Individual
`
`Sequences via Variab1e—Rate Coding,” IEEE Trans. Information Theory, Vol. 24,
`
`14
`
`

`
`1PR2017—00168: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14,22,28
`
`No. 5, Sept. 1978, pp. 530-36; Ex. 1113. 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. LZ77 dictionary compression is not used in the prior art discussed below 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. The prior art relied on
`
`below uses a variation of LZ78 encoding—namely, LZW encoding. Accordingly,
`
`LZ78 is explained in more detail below.
`
`1.
`
`LZ78 Dictionary Compression
`
`43.
`
`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
`
`15
`
`

`
`IPR20l7—00l68: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`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.
`
`,"'
`
`Start
`
`")
`
`There Anothe\'r"'—~... Y
`
`Input Character?
`
`No
`
`Read Next Input
`Character, |(
`
`
`
`
`Output
`Codeforw
`
`
`
`End
`
`.)
`
`Add K to {.0 to
`Create w|(
`
`Y
`
`ES
`
`.."'
`
`,
`
`ls u:K in
`_
`Dictionary?
`
`"
`
`._
`
`
`
`
`No
`
`Output Code for in
`followed by K
`
`
`
`
`Set w=emptv
`Dictionary
`
`
`Add wK to
`
`Exemplary Flow Chart For L278
`
`44.
`
`A simple example of this algorithm compressing the string “A B A B
`
`B B A B B A B B B” follows. Before the algorithm starts, the dictionary is
`
`emptied by initializing it so that the “null” value, i.e., no match, is mapped to the
`
`16
`
`

`
`IPR2017—0Ol68: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14,22,28
`
`“0” index. The first character “A” is read and set to be the combined prefix
`
`string/last character. The character “A” is not in the dictionary, so a “0” index
`
`followed by an “A” is output. Then “A” is added to the dictionary and mapped to
`
`the “I” index, and the prefix string is set to empty. The next character “B” is read
`
`and becomes a new combined prefix string/last character. This new combined
`
`string is compared to the dictionary. Again, there is no match, so a “0” index
`
`followed by a “B” is output. Then, “B” is added to the dictionary and mapped to
`
`index “2,” and the prefix string is set to empty. The next character “A” is read and
`
`becomes part of the new prefix string/last character. This time “A” is found in the
`
`dictionary (mapped to index “1”), so the next character “B” is added to the
`
`combined string, and “AB” is compared to the dictionary. There is no match, so
`
`index
`
`661)‘)
`
`(the index for the prefix string, which was “A”), is output followed by a
`
`“B.” Then “AB” is added to the dictionary and mapped to the “3” index, and the
`
`prefix string is set to empty. This process is repeated until the end of the input
`
`stream is reached. For the example above, the outputs (0 A 0 B l B 2 B 3 B 5 B)
`
`and the resulting dictionary are summarized in the tables below.
`
`17
`
`

`
`IPR2017—00l68: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`String
`Index
`Encoded String
`Index Character
`
`moA “A” m
`
`0
`
`1
`
`2
`
`3
`
`5
`
`"B"
`
`"AB"
`
`"BB"
`
`"A38"
`
`"ABBB"
`
`B
`
`3
`
`3
`
`8
`
`B
`
`Output
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`"A"
`
`"B"
`
`"AB"
`
`"BB"
`
`"A33"
`
`"ABBB"
`
`Dictionary
`
`45.
`
`This example results in an output of 12 values—6 indices and 6
`
`characters—in place of the original 13 characters. This is not a significant
`
`reduction, assuming an index is represented with a code word having the same
`
`number of bits as a character. However, as the compression process continues and
`
`the dictionary grows, the LZ78 algorithm can produce substantial compression
`
`since more strings, and longer strings, are found in the dictionary.
`
`2.
`
`LZW Dictionary Compression
`
`46.
`
`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. l1l4 (“Welch article”). Welch provided the following
`
`algorithm:
`
`Initialize table to contain single—_chara_cIer strings.
`Read first input characier—-preiix string ti)
`
`18
`
`

`
`IPR20l7-00168: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`Step:
`
`Fiead next input character K
`it no such K (input exhausted): code (0.!) —-output; EXIT
`it wK exists in string table: 0.3K-ail repeat Step.
`eise 1...-K not in string table: cede ltd) —-output:
`wK—-string table;
`K--wj repeat Step.
`
`Id. at, pp. 15-16.
`
`47.
`
`Based on this algorithm (which is reformatted below on the left), a
`
`flow chart, below right, can be created.
`
`Dictionary
`
`Initialize
`
`Read First Input
`Character and Store in
`
`
`
`
`
`
`Prefix String to
`
`
`
`2/ \
`
`»._\-
`
`xxx
`_.//i
`,2 Is There Another‘\ V
`Input Character?
`
`95
`
`Read Next Input
`Character, K
`
`I
`
`
`
`Initialize table to contain
`
`single-character strings.
`
`Read first input character
`
`—> prefix string to
`
`Step: Read next input character K
`
`If no such K (input exhausted):
`
`code(cu) —> output; EXIT
`
`if aiK exists in string table:
`
`wk’ -> to; repeat Step
`
`else wk’ not in string table:
`
`code (to) -v output;
`
`cuK —> string table;
`
`it’ —> to; repeat Step.
`
`No
`,. :13. _ .
`Output
`Code for in
`
`_
`
`7
`
`End
`
`_
`
`}
`
`
`
`
`Add it to to to
`
`Create unit’.
`
`/
`,/Is am in
`
`\~\
`
`Setto.-.r.ui( Yes
`
`NO
`I
`I Otitput Code
`