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
`
`REALTIME DATA LLC d/b/a IXO
`
`Patent Owner
`
`U.S. Patent No. 6,597,812 B1
`
`IPR Trial No. IPR2017-00167
`
`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 1005
`
`

`
`IPR2017—00l67: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`TABLE OF CONTENTS
`
`BACKGROUND AND QUALIFICATIONS .............................................. .. 4
`
`MATERIALS CONSIDERED ..................................................................... .. 7
`
`III.
`
`THE RELEVANT LEGAL STANDARDS ................................................. .. 8
`
`A.
`
`B.
`
`Claim Construction ............................................................................ .. 8
`
`Obviousness ....................................................................................... .. 8
`
`IV.
`
`BACKGROUND AND STATE OF THE ART ......................................... .. 12
`
`A.
`
`B.
`
`Run Length Encoding Was Well-Known Before the Filing Date of the
`’8l2 Patent And Is Admitted Prior Art ............................................ .. 12
`
`Dictionary Compression Was Well—Known Before The Filing Date Of
`The ’812 Patent And Is Admitted Prior Art ..................................... .. 14
`
`1.
`2.
`
`LZ78 Dictionary Compression .............................................. .. 16
`LZW Dictionary Compression ............................................... .. 20
`
`THE PRIOR ART ....................................................................................... .. 26
`
`A.
`
`O’Brien Combines Run Length Encoding And Dictionary Encoding27
`
`1.
`2.
`
`O’Brien Shows Run Length Encoding .................................. .. 27
`O’Brien Shows Dictionary Encoding .................................... .. 29
`
`B.
`C.
`
`Nelson Provides Additional Details About Dictionary Encoding .... .. 33
`The Welch Patent Shows Compression Implemented In Both
`Hardware And Software ................................................................... .. 36
`
`D.
`
`The Heath Patent Shows Bit-Packing .............................................. .. 36
`
`VI.
`
`OVERVIEW OF THE ’812 patent ............................................................. .. 38
`
`A.
`
`B.
`C.
`
`The ’8 12 patent Combines Run Length Encoding and Dictionary
`Encoding .......................................................................................... .. 38
`Run Length Encoding in the ’8l2 patent ......................................... .. 39
`Dictionary Encoding In The ’812 patent .......................................... .. 42
`
`VII.
`
`CLAIM CONSTRUCTION ....................................................................... .. 46
`
`A.
`
`Control Code Word .......................................................................... .. 47
`
`Page 2 of T2
`
`

`
`IPR2017—00167: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`VIII. EACH CHALLENGED CLAIM IS OBVIOUS OVER O’BRIEN IN VIEW
`
`OF NELSON, WELCH, AND/OR HEATH .............................................. .. 47
`
`A.
`
`Ground No. 1: Claims 1 And 28 Are Obvious Over O’Brien In View
`
`Of Nelson ......................................................................................... .. 47
`
`1.
`
`2.
`
`Motivation To Combine ......................................................... .. 48
`
`Claim 1 Is Obvious Over O’Brien In View Of Nelson .......... .. 50
`
`a.
`
`b.
`c.
`d.
`e.
`f.
`g.
`
`O’Brien Discloses The Preamble ................................ .. 51
`
`O’Brien Discloses The “Detecting” Step .................... .. 51
`O’Brien Discloses The First “Outputting” Step .......... .. 53
`O’Brien And Nelson Disclose The “Maintaining” Step 55
`O’Brien And Nelson Disclose The “Building” Step 57
`O’Brien And Nelson Disclose The “Searching” Step 57
`O’Brien And Nelson Disclose The Second “Outputting”
`Step .............................................................................. .. 59
`
`3.
`
`Claim 28 Is Obvious Over O’Brien In View Of Nelson ........ .. 60
`
`B.
`
`Ground No. 2: Claim 14 Is Obvious Over O’Brien In View Of Nelson
`
`And The Welch Patent ..................................................................... .. 64
`
`1.
`
`Claim 14 Is Obvious Over O’Brien in View of Nelson and the
`
`Welch Patent .......................................................................... .. 64
`
`C.
`
`Ground No. 3: Claim 9 is Obvious Over O’Brien In View Of Nelson
`
`and Heath ......................................................................................... .. 66
`
`D.
`
`Ground No. 4: Claim 22 is Obvious Over O’Brien In View Of Nelson,
`
`Welch and Heath .............................................................................. .. 70
`
`IX.
`
`Conclusion .................................................................................................. .. 71
`
`Page 3 of 72
`
`

`
`IPR2017—00167: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`1, Prof. James 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.
`
`I 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 (B.A.) 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
`
`Page 4 of 72
`
`

`
`IPR2017—00l67: 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 Compression: Methods and Theory (Ex. 1016). 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 Compression and Image and Text Compression.
`
`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).
`
`Page 5 of T2
`
`

`
`IPR2017—00l67: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`These are submitted herewith as Exhibits 1017-1019.
`
`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, Aeta Inforrnatica, 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
`
`Page 6 of T2
`
`

`
`IPR2017—00l67: 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.
`
`1 1.
`
`A copy of my latest curriculum vitae (C.V.) is attached as
`
`Appendix A.
`
`12. My compensation is in no way contingent on the results of this case or
`
`any other proceedings relating to the asserted patents.
`
`II. MATERIALS CONSIDERED
`
`13.
`
`I have carefully reviewed U.S. Patent No. 6,597,812 patent (the “’812
`
`patent,” EX. 1001).
`
`14.
`
`For convenience, a list of the information that I considered in arriving
`
`at my opinions is attached as Appendix B.
`
`15.
`
`Furthermore, I have reviewed the Declaration of Charles D. Creusere
`
`in Support of SAP America, Inc., et al.’s Petition for interpartes review of claims
`
`1-4, 8, 14-17, 21 and 28 of the ’812 patent (“Creusere Decl.,” Ex. 1021). See SAP
`
`America Inc., et al. v. Realtime Data LLC d/b/a IX0, Case No. IPR2016-00783,
`
`Paper No. 1, Ex. 1005 (PTAB April 1, 2016).
`
`I agree with Dr. Creusere’s
`
`statements in the Creusere Decl. and have included relevant portions below.
`
`Page 7 of 72
`
`

`
`IPR2017—00l67: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`III. THE RELEVANT LEGAL STANDARDS
`
`16.
`
`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
`
`17.
`
`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.
`
`18.
`
`I have been informed and understand that a claim in inter partes
`
`review is given the “broadest reasonable construction in light of the specification.”
`
`37 C.F.R. § 42.100(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.
`
`Obviousness
`
`19.
`
`It is my opinion that a person of ordinary skill in the art at the time the
`
`’8l2 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.
`
`Page 8 of T2
`
`

`
`IPR20l7—00l67: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`20.
`
`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.
`
`21.
`
`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 VI and VIII
`
`below).
`
`22.
`
`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.
`
`23.
`
`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:
`
`Page 9 of T2
`
`

`
`IPR20l7—00l67: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`0
`
`the level of ordinary skill in the art at the time the application was
`
`filed;
`
`I
`
`the scope and content of the prior art;
`
`I what differences, if any, existed between the claimed invention and
`
`the prior art.
`
`24.
`
`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
`
`£111.
`
`25.
`
`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;
`
`Page 10 of T2
`
`

`
`IPR2017—00167: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`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;
`
`whether a person of ordinary skill would have recognized a reason to
`
`combine known elements in the manner described in the claim;
`
`whether there is some teaching or suggestion in the prior art to make
`
`the modification or combination of elements claimed in the patent;
`
`and
`
`whether the innovation applies a known technique that had been used
`
`to improve a similar device or method in a similar way.
`
`26.
`
`I understand that one of ordinary skill in the art has ordinary
`
`creativity, and is not an automaton.
`
`27.
`
`I understand that in considering obviousness, it is important not to
`
`determine obviousness using the benefit of hindsight derived from the patent being
`
`considered.
`
`28. 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.
`
`Page 11 of T2
`
`

`
`IPR2017—00l67: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`IV. BACKGROUND AND STATE OF THE ART
`
`29.
`
`The ’812 patent (Ex. l0O1)1 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. This
`
`combination, as claimed in the ’812 patent, is shown in the prior art discussed
`
`below.
`
`A.
`
`Run Length Encoding Was Well-Known Before the Filing Date of
`the ’812 Patent And Is Admitted Prior Art
`
`30.
`
`The ‘S12 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; Ex. 1001.) 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 3A3B3C4B5 C4A.
`
`1 All Exhibit numbers in this Declaration refer to the Exhibits attached to the
`
`accompanying Petition for Inter Partes Review.
`
`Page 12 of T2
`
`

`
`IPR2017—00I67: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`|nitia|String
`G
`MHmWRwB
`G
`
`Encode
`0
`Output
`
`AAABBBCCCBBBBCCCCCAAAA
`
`AAABBBCCCBBBBCCCCCAAAA
`HJLHLH
`‘—x—’H—’
`
`3A
`
`3B
`
`3C
`
`5C
`
`4A
`
`ii
`
`3A3B3C4B5C4A
`
`31. 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.
`
`32.
`
`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 ofthe 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
`
`Page 13 of 72
`
`

`
`IPR2017—00l67: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`trend continued into 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; BX. 101].) Run length encoding is frequently used in combination with
`
`Huffinan coding and is part of major industry specifications and standards adopted
`
`in the 1980’s and 1990’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
`
`33.
`
`Like run length encoding, dictionary encoding was known well before
`
`the filing date of the ’812 patent. In fact, the ’8l2 patent admits that dictionary
`
`compression was well known prior to the filing date of the ’812 patent.
`
`’812
`
`patent at 2159-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 “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. During encoding, each time a word in the
`
`Page 14 of T2
`
`

`
`IPR20l7-00167: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`input stream is found in the dictionary, it is replaced with the index corresponding
`
`to that Word. For example, given the dictionary below, the string “dictionary data
`
`compression is well known” could be encoded as “3 2 1 is well 4”.
`
`Index
`
`String
`
`1
`
`2
`
`3
`
`4
`
`“compression”
`
`"data"
`
`“dictiona ry”
`
`“known”
`
`Dictionary
`
`34.
`
`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.
`
`35. Dictionaries are ofien 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.
`
`36. 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. Alternately, the dictionary can be adaptive, meaning that words
`
`from the input stream are added to the dictionary during the compression process.
`
`Page 15 of 72
`
`

`
`IPR2017—00167: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`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.) 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 discussed below uses a
`
`variation of LZ78 encoding. Accordingly, LZ78 is explained in more detail below.
`
`1.
`
`LZ78 Dictionary Compression
`
`37.
`
`The signature feature of LZ78 is the algorithm used to build the
`
`dictionary as it encodes the input stream. 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
`
`Page 16 of T2
`
`

`
`IPR2017—00l67: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`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.
`
`Page 17 of 72
`
`

`
`IPR2017-00167: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`Start
`
`)
`
`-' Is There Another“ _
`
`
`
`I Set uJ~'-‘empty
`
`3 Read Next Input
`Character, K
`‘
`
`
`
`Add K to nu to
`Create m|(
`
`Y _.
`
`65
`
`-
`
`"
`
`1
`
`ls :.uKin '‘
`
`.
`
`ND
`
`] l
`
`.
`
`No
`.1!
`
`Output
`_Code for no
`I
`
`I_
`
`End
`
`=
`
`SETILIJ UK
`
`
`
`Output Code for LU
`
`followed by K
`
`Add wk to
`
`Dictionary
`
`I
`
`Exemplary Flow Chart For L278
`
`38.
`
`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
`
`“0” index. The first character “A” is read and set to be the combined prefix
`
`striiig/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 “1” index, and the prefix string is set to empty. The next character “B” is read
`
`Page 18 of 72
`
`

`
`IPR2017-00167: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`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 “O” 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 “1” (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 1 B 2 B 3 B 5 B)
`
`and the resulting dictionary are summarized in the tables below.
`
`Index Character Encodcd String
`0
`A
`"A"
`
`Index
`U
`
`0
`
`1
`
`2
`
`3
`
`5
`
`"B"
`
`"AB"
`
`"BB"
`
`“ABE”
`
`“A338”
`
`B
`
`B
`
`8
`
`B
`
`B
`
`OMDUT
`
`1
`
`2
`
`3
`
`1!
`
`5
`
`6
`
`String
`Null
`
`‘A’
`
`"B"
`
`"AB"
`
`"BB"
`
`“A88”
`
`"A668"
`
`Dictionary
`
`39.
`
`This example results in an output of 12 va1ues—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
`
`Page 19 of 72
`
`

`
`IPR2017—00167: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`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
`
`40.
`
`In 1984, Terry Welch described a particular Variation of LZ78 that has
`
`become known as LZW, for Lernpel-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 pp. 15-16.) Based on this
`
`pseudocode, a flow chart, below right, can be created.
`
`Page 20 of T2
`
`

`
`IPR2017-00167: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`._
`
`start
`I
`lnllulixe
`
`:—;—J°""'°"""
`
`ch.:::.:°:L'Zf:,t..,
`Prefix String w
`
`Initialize table to contain
`
`single-character strings.
`
`Read first input character
`
`—- prefix string (:1
`
`Step: Read next input character A‘
`
`If no such K (input exhausted):
`
`code(m) - output, EXIT
`
`If mK exists in string table:
`
`(UK —~ to; repeat Step
`
`else wk’ not in string table:
`
`code ((1)) —- output;
`
`mix’ —+ string table;
`’
`A —- cu: repeat Step.
`
`,-,.',,,,,,,,,,,,,-,-._
`:‘\1[\9v.a‘t Character?
`\\'\
`No
`.
`C
`Output
`_CI:Ide for in
`
`:
`i
`
`.
`
`End
`
`'1
`
`I
`1'"
`Stead Ne-rt Input
`fhararlat I
`
`Add it to w to
`Create uni
`
`
`
`!
`.
`
`Se!w=I.uIZ
`
`f'fes—.
`
`I:
`K n.
`. w '
`~.\|3Itt-omrv?
`\_‘r
`No
`V
`Outptfl Cod-e
`f°”’
`Add I.I.l—';_1O
`'
`S“w___K
`4' Jlointana
`
`LZW Pseudocode
`
`LZW Flow Chart
`
`41. An explanation of how the LZW algorithm would encode the string
`
`“A B A B B B A B B A B B B” (the same string used in the example for LZ78
`
`above) follows. Before the algorithm starts, the dictionary is initialized to map
`
`each possible single character to a different dictionary index, or code word. In this
`
`example, there are two possible single characters, “A” and “B,” and they can be
`
`mapped to code words “0” and “1,” respectively. After the dictionary is initialized,
`
`the first character “A” is read and stored as the prefix string. Because the
`
`Page 21 of 72
`
`

`
`IPR2017—00l67: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`dictionary has been initialized to contain code words for all possible single
`
`characters, “A” is in the dictionary, mapped to code word “0.” The next character
`
`“B” is read and added to the end of the prefix string “A” to create a combined
`
`string (“AB”). This combined string is compared to entries in the dictionary.
`
`There is no match, since the dictionary contains only single characters at this time.
`
`So, the index for the prefix string (a “0” index mapped to “A”) is output, and the
`
`combined string “AB” is added to the dictionary, mapped to index “2.” The prefix
`
`string is set to be the character “B” (last character of the combined string “AB”),
`
`and a new next character “A” is read. Again, the next character is combined with
`
`the prefix string to create a combined string (“BA”), and the dictionary is searched
`
`for the combined string. It is not found, so the index for the prefix string (a “1” for
`
`“B”) is output. The combined string “BA” is added to the dictionary, mapped to
`
`index “3.” The prefix string is updated to be the current character “A” (last
`
`character of the combined string “BA”), and a new next character “B” is read and
`
`added to the prefix string to create a combined string “AB.” The dictionary is
`
`searched for “AB” and it is found, mapped to index “2.” As a result, the combined
`
`string “AB” becomes the new prefix string. The next character, another “B,” is
`
`read and added to the prefix string to create a combined string “ABB”. The
`
`dictionary is searched, but this combined string is not found. As a result, the index
`
`of the current prefix string (a “2” for “AB”) is output, and “ABB” is added to the
`
`Page 22 of T2
`
`

`
`IPR2017—00167: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`dictionary, mapped to index “4.” The current character “B” (last character of the
`
`combined string) becomes the prefix string. The next character, another “B,” is
`
`read and added to the prefix string to create a combined string “BB.” The
`
`dictionary is searched, but “BB” is not found. As a result, the index for the current
`
`prefix string (a “1” for “B”) is output, and the combined string “BB” is added to
`
`the dictionary, mapped to index “5.” The prefix string is set to be the current
`
`character “B” (last character of the combined string), and the next character “A” is
`
`read and added to the prefix string to create a new combined string “BA.” The
`
`dictionary is searched and this combined string is found, mapped to index “3.”
`
`The combined string “BA” becomes the prefix string, and the next character “B” is
`
`read and added to the prefix string to create a new combined string “BAB.” This
`
`string is not found in the dictionary. Accordingly, the index for the current input
`
`string (a “3” for “BA”) is output, and “BAB” is added to the dictionary, mapped to
`
`index “6.” The prefix string is set to be the current character “B” (last character of
`
`the combined string), and the next character “B” is read and added to the prefix
`
`string to create a combined string “BB.” The dictionary is searched and the
`
`combined string “BB” is found, mapped to index “5.” The combined string “BB”
`
`becomes the new prefix string. The next character “A” is read and added to the
`
`prefix string to create a new combined string “BBA.” This combined string is not
`
`present in the dictionary, so the index for the prefix string is output (a “S” for
`
`Page 23 of T2
`
`

`
`IPR2017—00167: Storer Declaration
`
`U.S. Patent No. 6,597,812, Claims 1, 9,14, 22, 28
`
`“BB”), and “BBA” is added to the dictionary, mapped to index “7.” The prefix
`
`string is set to be the current character “A” (last character of the combined string),
`
`and the next character “B” is read and added to the prefix string to create a
`
`combined string “AB.” The dictionary is searched and the combined string “AB”
`
`is found, mapped to index “2.” The combined string “AB” becomes the new prefix
`
`string. The next character “B” is read and added to the prefix string to create a
`