throbber
IN THE UNITED STATES PATENT AND TRADEMARK OFFICE
`
`James J. Fallon, et al.
`In re Patent of:
`8,880,862 Attorney Docket No.: 39521-0025IP1
`U.S. Patent No.:
`November 4, 2014
`Issue Date:
`Appl. Serial No.: 13/118,122
`Filing Date:
`May 27, 2011
`Title:
`SYSTEMS AND METHODS FOR ACCELERATED
`LOADING OF OPERATING SYSTEMS AND
`APPLICATION PROGRAMS
`
`DECLARATION OF DR. CHARLES J. NEUHAUSER
`
`1. My name is Dr. Charles J. Neuhauser. I understand that I am submitting a
`
`declaration in connection with an Inter Partes review (“IPR”) proceeding before
`
`the United States Patent and Trademark Office for U.S. Patent No. 8,880,862
`
`(“the ’862 Patent”).
`
`
`
`2.
`
`I have been retained on behalf of Apple Inc. to offer technical opinions with
`
`respect to the ’862 Patent and the prior art references cited in this IPR. My
`
`compensation is not based on the outcome of this matter.
`
`
`
`3.
`
`I am not a lawyer. However, counsel has advised me of legal concepts that are
`
`relevant to IPR proceedings and to the opinions that I offer in this declaration. I
`
`understand that, during IPR, claims of the subject patent are given a broadest
`
`reasonable interpretation. Counsel has advised me that the broadest reasonable
`
`
`
`1
`
`APPLE 1003
`
`

`
`
`
`interpretation must be consistent with the specification, and that claim language
`
`should be read in light of the specification and teachings in the underlying patent.
`
`
`
`4.
`
`I have reviewed the ’862 Patent, including the claims of the patent in view of the
`
`specification, and I have reviewed the ’862 Patent’s prosecution history. In
`
`addition, I have reviewed the following documents: U.S. Patent No. 5,860,083
`
`(“Sukegawa”), U.S. Patent No. 6,374,353 (“Settsu”), U.S. Patent No. 6,145,069
`
`(“Dye”), U.S. Patent No. 7,190,284 (“Dye ’284”), Burrows et al., “On-line Data
`
`Compression in a Log-structured File System” (1992) (“Burrows”), U.S. Patent
`
`No. 6,317,818 (“Zwiegincew”), Jeff Prosise, DOS 6 – The Ultimate Software
`
`Bundle?, PC Magazine, Apr. 13, 1993 (“Prosise”), John L. Hennessey & David
`
`A. Patterson, Computer Architecture a Quantitative Approach (1st ed. 1990)
`
`(“Hennessey”), Cache, Decoder, File, Program File, and Direct Memory Access,
`
`Microsoft Press Computer Dictionary (3d ed. 1997)(“MSFT Dictionary”), Tom
`
`Shanley & Don Anderson, PCI System Architecture, (4th ed. 1999) (“Shanley”),
`
`Jacob Ziv & Abraham Lempel, A Universal Algorithm for Sequential Data
`
`Compression, IT-23 No. 3 IEEE Transactions on Information Theory 337
`
`(1977)(“Ziv”), James A. Storer & Thomas G. Szymanski, Data Compression via
`
`Textual Substitution, 19 No. 4 Journal of the Association for Computing
`
`Machinery (1982)(“Storer”), Kyle Loudon, Mastering Algorithms with C (1999)
`
`
`
`2
`
`

`
`
`
`(“Loudon”), Michael Barr, Programming Embedded Systems in C and C++
`
`(1999)(“Barr”), and Tim O’Reilly, Troy Mott, and Walter Glenn, Windows 98 in
`
`a Nutshell (1999)(“O’Reilly”).
`
`
`
`5.
`
`I am an electrical engineer by training and profession with a specialization in the
`
`area of computer based systems. My educational and practical background also
`
`includes extensive experience in the field of computer science and engineering. I
`
`have been a practicing electrical engineer since 1968. In formulating my
`
`opinions, I have relied upon my training, knowledge, and experience in the
`
`relevant art. A copy of my curriculum vitae is provided as Appendix A to this
`
`Declaration (Ex. 1004) and provides a description of my professional experience,
`
`including my academic and employment history, publications, conference
`
`participation, and more.
`
`
`
`6.
`
`I have extensive educational and professional engineering experience. I was
`
`awarded a BSEE degree from the University of Notre Dame in 1968.
`
`Immediately after graduating from the University of Notre Dame, I was
`
`employed as a Technical Staff Member by Bell Telephone Laboratories (which
`
`has subsequently become Alcatel-Lucent).
`
`
`
`
`
`3
`
`

`
`
`
`7. During my time at Bell Telephone Laboratories, I worked on the specification,
`
`testing, and development of computer controlled data and telephone switching
`
`systems. During that time, I also received my MSEE from Northwestern
`
`University (1971) under a company sponsored program.
`
`
`
`8.
`
`I left Bell Telephone Laboratories in 1971 to pursue a Ph.D. in a joint CS/EE
`
`program at Johns Hopkins University. In 1980, I was awarded a doctorate based
`
`on my research in evaluating computer architectures using emulation techniques.
`
`
`
`9. While working on my Ph.D. research, I joined the Digital Systems Laboratory at
`
`Stanford University as a research associate in 1974. There, I worked on the
`
`development of emulation systems for architectural research. In 1974, I also
`
`began working on a part-time basis at Palyn Associates, Inc. to develop a range
`
`of commercial products based on this research.
`
`
`
`10. In 1980, I joined Palyn as a full-time member of the Technical Staff. I later
`
`became Director of Engineering at Palyn and, by 1985, I was the Vice President
`
`of Engineering. At Palyn, I was responsible for directing product development
`
`on behalf of our clients, which consisted of a range of international entities
`
`
`
`4
`
`

`
`involved in computer technology. I also directly consulted with clients regarding
`
`
`
`processor and peripheral design.
`
`
`
`11. In my consulting role at Palyn, I was responsible for the specification, design,
`
`testing, and debugging of a wide range of computer devices, including mini-
`
`computers, microprocessors, printers, and communication interfaces. This
`
`involved both hardware and software development.
`
`
`
`12. Since 1994, I have been an independent consultant focusing on technical analysis
`
`primarily in support of litigation or potential litigation. In this role I have
`
`analyzed many different types of computer based systems, including robotic
`
`manufacturing systems, television transmission and reception systems,
`
`microprocessors, main-frame systems, peripheral systems and networked
`
`systems. I also have led teams of engineers in the functional analysis of various
`
`types of systems, including robotic systems, networked processors, processor
`
`operation, and video production equipment.
`
`
`
`13. Other details concerning my background, including a list of my publications,
`
`professional service, and more, are set forth in my curriculum vitae. In forming
`
`the opinions expressed in this report, I have relied upon my education and my
`
`
`
`5
`
`

`
`
`
`nearly 50 years of professional experience in the fields of electrical and computer
`
`engineering and of computer science. This declaration is organized as follows:
`
`
`
`I. Overview
`
`A. One of Ordinary Skill
`
`B. The ’862 Patent
`
`C. Sukegawa
`
`D. Settsu
`
`E. Burrows
`
`F. Dye
`
`G. Zwiegincew
`
`H. Discussion of Prior Art and the Claims of the ’862 Patent
`
`II. Terminology
`
`III. Detailed Discussion
`
`IV. Legal Principles
`
`
`I. Overview
`A. One of Ordinary Skill
`14. It is my understanding that I must analyze and apply the prior art cited above
`
`from the perspective of a person having ordinary skill in the art as of February 3,
`
`
`
`6
`
`

`
`2000 (“one of ordinary skill”), which I understand to be the ’862 Patent’s earliest
`
`
`
`possible priority date.
`
`
`
`15. The ’862 Patent relates to accessing data in conventional computer systems.
`
`Figure 1 is an exemplary figure that illustrates the basic structure of one
`
`embodiment of the ’862 Patent’s system [’862 Patent, 4:36-37, 5:63-66]. This
`
`and other similar figures of the ’862 Patent show straightforward and well known
`
`structures related to conventional computer systems, such as the widely used
`
`personal computer. In my opinion, one of ordinary skill would be a person with a
`
`Bachelor’s Degree in electrical engineering, computer engineering, or a related
`
`area of study. In addition, this person would have between three and five years
`
`of practical experience in the design and implementation of computer systems,
`
`such as personal computers. Alternatively, a person with a Master’s Degree in
`
`the area of electrical engineering, computer engineering, or a related area of study
`
`and somewhat less practical experience would be similarly qualified.
`
`
`
`16. I am well aware of the qualifications of such a person because I have worked
`
`with, supervised, and hired engineers with similar capabilities. By the year 2000,
`
`I had been awarded a Ph.D. in CS/EE with a specialization in computer
`
`engineering and had over 30 years of practical experience. Thus, by February 3,
`
`
`
`7
`
`

`
`
`
`2000, I was at least as qualified as the person having ordinary skill in the art that I
`
`have identified above. Moreover, I understand the perspective of one of ordinary
`
`skill, which I have applied in my analysis.
`
`
`
`B. The ’862 Patent
`17. The claims of the ’862 Patent generally relate to systems and techniques that are
`
`described in the specification as accelerating, following a system boot, the
`
`loading of operating systems and application programs [’862 Patent, Abstract,
`
`1:20-26, 3:35-41].
`
`
`
`18. The ’862 Patent explains that following reset or power on of a host system, initial
`
`bus commands inevitably instruct a boot device controller to retrieve data from
`
`the boot device (such as a disk) for the operating system. [’862 Patent, 20:38-
`
`49]. The ’862 Patent recognizes that, because most boot devices are relatively
`
`slow compared to computer buses, this functionality results in a problem of slow
`
`boot of the host system [’862 Patent, 20:38-49].
`
`
`
`19. As a solution to this problem, the ’862 Patent describes “data storage controllers”
`
`that provide accelerated loading of operating systems and application programs
`
`[’862 Patent, 1:20-26]. Fig. 1 of the ’862 Patent illustrates an exemplary Data
`
`
`
`8
`
`

`
`
`
`Storage Controller 10 that is operatively connected to a Hard Disk 11 and to a
`
`Main or Expansion Computer Bus 16. [’862 Patent, 4:36-37, 5:63-6:53]. The
`
`Data Storage Controller 10 includes a Cache 13 for data storage/preloading, and a
`
`Data Compression Engine 12 for data compression/decompression [’862 Patent,
`
`5:63-6:53, 20:38-21:12].
`
`
`
`20. Data Storage Controller 10 handles information read and write requests from a
`
`host system attached to Main or Expansion Computer Bus 16, and provides
`
`information to the host system through Main or Expansion Computer Bus 16
`
`[’862 Patent, 6:54-57, 7:33-35]. To improve the read and write performance, the
`
`’862 Patent makes use of two techniques: data caching and data compression.
`
`Data Storage Controller 10 includes Cache 13, which buffers data being
`
`transferred to and from the Hard Disk 11. In the system of Fig. 1, the Hard Disk
`
`11 is a relatively slow data storage device when compared to the speed of the
`
`host system attached to Main or Expansion Bus 16. The Cache 13 provides
`
`intermediate storage which allows data previously read from Hard Disk 11 to be
`
`made available relatively quickly in response to read requests [’862 Patent, Fig.
`
`1, 7:11-21]. Similarly, on writes to the Hard Disk 11, the Cache 13 allows write
`
`requests to complete quickly from the perspective of the attached computer
`
`
`
`9
`
`

`
`
`
`system because the data can be written to Cache 13 and then later passed to the
`
`slower Hard Disk 11 [’862 Patent, Fig. 1, 7:44-58].
`
`
`
`21. The ’862 Patent also suggests that the effective performance of Hard Disk 11 can
`
`be improved through the use of data compression. Data on Hard Disk 11, for
`
`example, may be stored in compressed form. Doing this increases the effective
`
`storage capacity of the disk and may also lead to an improvement in the effective
`
`data transfer rate [’862 Patent, 1:20-26, 3:35-41, 3:60-63, 5:40-47, 8:45-58]. In
`
`Fig. 1, the Data Compression Engine 12 of Data Storage Controller 10 carries out
`
`compression and decompression [’862 Patent, 5:65-6:3, 7:11-21, 7:44-58,
`
`generally, 23:28-26:20].
`
`
`
`22. To further improve performance, the ’862 Patent suggests the use of information
`
`“preloading,” in which programs and data likely to be needed during system boot
`
`processes are loaded into Cache 13 in advance of their probable need. The ’862
`
`Patent suggests that by anticipating the need for boot data the Disk Storage
`
`Controller 10 can load such boot data from Hard Disk 11 while the central
`
`processing unit of the computer system attached to Bus 16 is in the process of
`
`initialization. Thus, once CPU initialization is complete, an access request for
`
`boot data only needs to reference the relatively fast Cache 13, rather than the
`
`
`
`10
`
`

`
`
`
`slower Hard Disk 11 [’862 Patent, 20:50-66, 21:3-6]. The ’862 Patent states that
`
`the preloading techniques can be used both with respect to operating system data,
`
`and with respect to application data that the user wants to have available directly
`
`after the boot process begins [’862 Patent, 20:58-61, 21:13-17].
`
`
`
`23. ’862 Patent Figs. 7a and 7b illustrate one approach to “preloading’ [’862 Patent,
`
`21:24-26].
`
`
`
`24. When the system is booted for the first time, the Data Storage Controller 10
`
`tracks disk blocks called for during the boot process, and retains that information
`
`in a list on Hard Disk 11 [’862 Patent, Fig. 7a, steps 70-74, 21:30-42]. During a
`
`subsequent power turn-on, this list is used by the Data Storage Controller 10 to
`
`preload the same data blocks into the Cache 13 while the computer system is
`
`initializing [’862 Patent, Fig. 7b, steps 75-78, 21:53-59]. Steps 82-85 of Fig. 7b
`
`illustrate how the list is updated, by excluding from the list preloaded data blocks
`
`that were not needed during the current boot process, and by including those data
`
`blocks that were used but were not preloaded [’862 Patent, Fig. 7b, steps 82-85,
`
`21:60-22:11].
`
`
`
`
`
`11
`
`

`
`25. Another claimed aspect of the ’862 Patent is the use of multiple encoders in a
`
`
`
`parallel configuration to both optimize the encoding process and to speed up that
`
`process. This is shown, for example, in ’862 Patent Fig. 9, where Encoder
`
`Module 125 contains a number of Encoders E1 to En. The ’862 Patent describes
`
`two approaches to using the encoders. In one approach, each encoder uses a
`
`different compression technique. Once encoding is complete (or after a
`
`designated period of time has elapsed) the compression factor for each encoder
`
`result is examined and the encoding scheme that produced the smallest result is
`
`used [’862 Patent, 24:1-6, 24:62-65, 25:15-22]. Encoders may also be structured
`
`to work in parallel using the same encoding techniques so that encoding takes
`
`place more quickly [’862 Patent, 24:25-29, 24:57-62].
`
`
`
`C. Sukegawa
`26. U.S. Patent 5,860,083 (“Sukegawa”) is titled “Data Storage System Having Flash
`
`Memory and Disk Drive.” The named inventor is Hiroshi Sukegawa. The patent
`
`was issued on January 12, 1999. It is my understanding that Sukegawa is prior
`
`art to the ’862 Patent.
`
`
`
`27. Sukegawa describes a disk based storage system that includes a flash memory
`
`system that functions as a cache memory [Sukegawa, Abstract, 1:5-8, 1:55-61,
`
`
`
`12
`
`

`
`
`
`7:46-50]. The use of cache memory as a front-end to disk storage was well-
`
`known to one of skill in 2000. Sukegawa recognized that the usefulness of a disk
`
`cache memory was reduced directly after system start up because, in the typical
`
`cache based on DRAM, the contents of the cache are lost during a system power-
`
`down. Thus, when the system is powered on, frequently used program code
`
`associated with the operating system and important application programs is lost
`
`and must be reloaded from the disk. This increases the time to boot the operating
`
`system or an application program that must be available directly after start up
`
`[Sukegawa, 1:39-49].
`
`
`
`28. To solve this problem, Sukegawa discloses a disk cache memory (flash memory
`
`unit 1) that is composed of non-volatile memory. Thus, frequently used
`
`operating system and application program code may be preloaded into this non-
`
`volatile memory and is available immediately after the system is powered-on
`
`[Sukegawa, 1:50-61, Fig. 1]. In the system of Sukegawa, the flash memory unit
`
`1 is divided into three areas: Permanent Storage Area 10A, High Speed Access
`
`Area 10B, and Non-Volatile Cache Area 10C. Area 10B, the High Speed Access
`
`Area, is used in Sukegawa as a program swap file storage area.
`
`
`
`
`
`13
`
`

`
`
`
`29. Permanent Storage Area 10A is used as a type of “explicit” cache memory, that
`
`is, its contents are established directly by the user [Sukegawa, 2:65-3:3, 5:10-14,
`
`Fig. 3, 4]. In contrast, Non-Volatile Cache Area 10C is managed as an “ordinary
`
`cache,” that is, its contents are based on actual usage and are not directly
`
`determined by the user [Sukegawa, 7:46-55, Fig. 5]. In both cases, the intention
`
`of the system is to maintain frequently used program code in the cache so that it
`
`is available directly at system power up [Sukegawa, 1:50-61, 2:65-3:3, 6:7-17,
`
`6:49-58, 9:23-24].
`
`
`
`30. Sukegawa Fig. 1 depicts the overall structure of the system.
`
`
`
`
`
`14
`
`

`
`
`
`31. Sukegawa’s Hard Disk Drive (HDD 2) holds operating system and application
`
`code. Host System 4 is a conventional computer system, similar to a personal
`
`computer, and includes a Central Processing Unit (CPU 22) [Sukegawa, Fig. 1, 2;
`
`4:1-11, 4:32-37]. Requests from Host System 4 for data are handled by the
`
`Cache System Controller 3, which manages the HDD 2 and flash memory unit 1
`
`[Sukegawa, 4:7-11, 4:25-30]. To do this, the Cache System Controller 3 makes
`
`use of the Management Information Table 3A, which stores information about
`
`the contents of the flash memory unit 1, particularly areas 10A and 10C
`
`[Sukegawa, 5:5-9, 5:43-46].
`
`
`
`32. Permanent Storage Area 10A is controlled directly by the user. To do this, the
`
`user makes use of a “data storage utility program” which allows them to specify
`
`which operating system and application control information is to be stored in area
`
`10A. Figs. 3 and 4 show how this is accomplished for application programs and
`
`operating system control information, respectively.
`
`
`
`33. One of ordinary skill would have understood that the term “control information”
`
`in Sukegawa refers to program code and data. Basically, the data storage utility
`
`program allows the user to specify which files or blocks of code are important
`
`enough that they should be permanently stored in flash memory unit 1 and are
`
`
`
`15
`
`

`
`
`
`thus available immediately upon start up. Steps S4-S7 of Sukegawa Fig. 3 show
`
`the use of the data storage utility program to transfer blocks of application
`
`program control information from the HDD 2 to the Permanent Storage Area 10A
`
`of flash memory unit 1 [Sukegawa, 5:29-40]. A similar process is used to move
`
`operating system control information from the HDD 2 to Permanent Storage Area
`
`10A. This is accomplished by steps S15-S19 of Fig. 4 [Sukegawa, 6:32-44].
`
`Once the Permanent Storage Area 10A has been preloaded with user selected
`
`application program or operating system code, this code is available immediately
`
`upon power up and initialization [Sukegawa, 6:7-17, 6:49-58].
`
`
`
`34. Non-Volatile Cache Area 10C functions as a conventional cache, and is not under
`
`the direct control of the user [Sukegawa, 7:46-55]. Fig. 5 provides an overview
`
`of cache operation for read requests to HDD 2 and, to one of ordinary skill,
`
`would have related the well-known operation of a cache. In response to a read
`
`request, step S21 of Fig. 5 determines if the requested information is currently in
`
`either cache area 10A or 10C (that is, it determines if the request “hit” the cache).
`
`If the request “hit” in the cache, then it is fulfilled directly from the cache at step
`
`S25 [Sukegawa, 7:28-49]. Otherwise, a check is made to determine whether the
`
`request is related to permanent data previously identified by the user or not (step
`
`S22). If the request is for data that should be stored permanently in the area 10A,
`
`
`
`16
`
`

`
`
`
`then the data read is placed in area 10A. Otherwise, the data is placed in area
`
`10C, the Non-Volatile Cache area [Sukegawa, 7:40-55].
`
`
`
`D. Settsu
`35. U.S. Patent 6,374,353 (“Settsu”) is titled “Information Processing Apparatus
`
`Method of Booting Information Processing Apparatus at a High Speed.” The
`
`named inventors are Atsuchi Settsu, Noriyuki Bab and Naoto Sugai. The patent
`
`was filed on March 3, 1999. It is my understanding that this patent is prior art to
`
`the ’862 Patent.
`
`
`
`36. Settsu describes a system for improving the boot performance of an operating
`
`system Settsu, 1:1-4]. Settsu Fig. 1 shows the basic arrangement of hardware and
`
`software for the system of Settsu, which forms the basis for other embodiments
`
`that represent variations on its basic concept.
`
`
`
`17
`
`

`
`
`
`37. In Settsu’s Fig. 1, ROM 1 holds a firmware module (6) that is executed when the
`
`system is powered up [Settsu, 8:8-13, 8:212-23]. Execution of this firmware
`
`starts the process of loading and initializing the main operating system. In Settsu,
`
`
`
`the operating system code to be loaded is divided into two parts: a Mini OS
`
`Module 7 and an OS Main Body Module 8, both of which are stored on a Boot
`
`Device 3, which in Settsu Fig. 1 is represented as a hard disk [Settsu, Fig. 1,
`
`1:51-62, 8:13-21, 10:25-29]. The Mini OS Module 7 contains basic operating
`
`system functions and a boot device driver that together allow the Mini OS
`
`Module 7 to load the OS Main Body Module 8. Settsu Fig. 4 shows the basic
`
`sequencing from power on until the main OS is operational. In this process, the
`
`F/W (Firmware) Code Module 6 loads and starts the execution of the Mini OS
`
`Module 7. In turn, the Mini OS Module 7 loads the OS Main Body Module 8
`
`
`
`18
`
`

`
`
`
`from the file system and initializes the operating system [Settsu, Fig. 4, generally
`
`at 9:4-10:24, especially at 9:4-11, 9:40-43, 10:32-36].
`
`
`
`38. What I have described directly above is termed the “First Embodiment” in Settsu,
`
`but it forms the basis for other embodiments. Settsu’s “Fourth Embodiment”
`
`relies on operations of the “First Embodiment” and, relevant to the ’608 Patent,
`
`adds compression/decompression [Settsu, Figs. 12-14; 13:49-15:4]. In the fourth
`
`embodiment, Settsu teaches the use of data compression with respect to the
`
`storage and accessing of operating system code. In this fourth embodiment
`
`operating systems are divided as described above between a Mini OS Module 7
`
`and a Main OS Body. The Main OS Body, however, is stored on the File System
`
`5 of the Boot Device 3 as compressed files. The Mini OS Module 7 is extended
`
`to include an OS Loading and Decompression Processing Module 50 [Settsu, Fig.
`
`13, item 50; 13:55-65, 14:6-12]. Settsu Fig. 14 depicts the process of loading the
`
`operating system, which includes at step ST182 the decompression of various OS
`
`functional modules [Settsu, Fig. 4, step 182; 14:13-17, 14:28-37]. Settsu
`
`describes that this approach reduces the overall time to load the operating system
`
`[Settsu, 14:64-15:5].
`
`
`
`E.
`
`Burrows
`
`
`
`19
`
`

`
`39. “Burrows” is a technical article titled “On-line Data Compression in a Log-
`
`
`
`structured File System,” with named authors Michael Burrows, Charles Jerian,
`
`Butler Lampson and Timothy Mann. This article appeared in the ASPLOS V
`
`Proceedings of the fifth international conference on Architectural Support for
`
`Programming Languages and Operating Systems (ASPLOS V). ASPLOS is an
`
`important technical conference that is widely attended. The copyright date of the
`
`proceedings is 1992, which is at least seven years in advance of the priority date
`
`of the ’862 Patent. It is my understanding that this article is prior art to the ’862
`
`Patent.
`
`
`
`40. Burrows discusses the application of well-known compression techniques to the
`
`storage of information in disk systems. One of ordinary skill in the art would
`
`have understood that this article is not simply a suggestion to use data
`
`compression techniques with respect to disk storage, but it also provides
`
`measured data demonstrating the effectiveness of such an approach [Burrows
`
`Section 6 – “Performance of Prototype, pp. 7-8]. The Burrows prototype system
`
`was based on the use of software compression. However, Burrows teaches that
`
`the software approach would be easily cast into hardware, thereby providing a
`
`significant performance increase [Burrows p. 2, ¶ 2; p. 6, ¶11].
`
`
`
`
`
`20
`
`

`
`
`
`41. The discussion in Burrows covers two issues: data compression and file structure.
`
`Burrows recognizes that storing data in compressed form on a disk requires
`
`special handling in the file system. Basically, when compressed data read from
`
`the file system is decompressed and then modified there is no guarantee that the
`
`re-compressed data will be smaller than the original compressed data. Thus, it
`
`may not fit in the original space on the disk [Burrows p. 2, ¶4-5]. Burrows solves
`
`this problem by using a specialized file structure.
`
`
`
`42. With respect to data compression, Burrows recognizes that data compression and
`
`the advantages of applying it to disk systems were well-known even in 1992
`
`[Burrows p. 2, ¶3]. Burrows suggests the use of several well-known data
`
`compression techniques and compares their effectiveness [Burrows p. 6, §4 –
`
`Compression Algorithms]. Burrows provides measurements that suggest a 50%
`
`reduction for operating system code and related applications [Burrows p. 6, Table
`
`2]. To test performance, Burrows implemented a prototype system that used
`
`software compression. Although measurements showed about a 6% loss in
`
`performance, the effect under actual usage was undetectable by the users
`
`[Burrows, pp. 7-8, §6 – Performance Prototype]. Burrows suggests that if the
`
`software compression were implemented in readily available 1992 hardware the
`
`performance issues would be resolved and the resulting system would have
`
`
`
`21
`
`

`
`
`
`improved storage capacity and transfer performance that was better than the
`
`unmodified system [Burrows, p. 7, §5.2 – Compression Hardware].
`
`
`
`F. Dye
`43. Dye claims priority to application “Ser. No. 09/239,659,” which issued as U.S.
`
`Patent No. 7,190,284 (“Dye ’284”). Counsel has advised me that because
`
`application Ser. No. 09/239,659 is “incorporated by reference in its entirety” into
`
`Dye, the disclosure of Dye ’284 is part of and fully included in Dye’s disclosure
`
`[Dye, 6:4-8].
`
`
`
`44. Dye describes a controller for a flash memory that makes use of compression and
`
`decompression technology to improve effective memory density and bandwidth
`
`[Dye, Abstract, 1:16-21, 2:42-47, 7:34-43, 8:6-12]. Flash memory is a type of
`
`non-volatile memory, that is, it retains data even when power is removed. Flash
`
`memory is very similar to a hard disk drive, except that it has a higher bandwidth
`
`and here is no mechanical action required to access data. Thus, there is no
`
`read/write access delay as there is with a hard disk. Because of their non-volatile
`
`capabilities flash memories have been used to implement “solid state disks”
`
`[Dye, 1:38-49]. Despite their obvious advantages over disk, flash memory based
`
`designs were in 2000 still relatively expensive on a per bit basis. Dye proposes
`
`
`
`22
`
`

`
`
`
`the use of data compression technology both to increase the effective size of a
`
`given flash memory, and to improve its bandwidth.
`
`
`
`45. Dye ’284 confirms that Dye’s controller also controls other memory devices,
`
`including hard disk drives [Dye ‘284, 11:54-12:22]. Dye ’284 explains, for
`
`example, that the controller can move “any data in the system” in normal or
`
`compressed format, can store data in any connected memory device in either a
`
`normal or compressed format, and can retrieve data for CPU usage in a normal or
`
`compressed format [Dye ‘284, 4:16-24, 11:28-37]. Dye ’284 further explains, for
`
`example, that where data is stored “in a compressed format, a CPU access of the
`
`data results in the data being decompressed and provided to the CPU,” thereby
`
`improving the data’s effective read access time [Dye ‘284, 12:19-22; Dye,
`
`Abstract, 7:34-43]. In these and other passages incorporated from Dye ’284, Dye
`
`describes benefits of using compression in several types of computer system
`
`memory devices, including hard disks and flash memory devices.
`
`
`
`46. Fig. 3 of Dye depicts the basic configuration of a system of Dye.
`
`
`
`23
`
`

`
`
`
`
`
`47. Flash Memory Array 100 is the non-volatile, permanent store for information.
`
`Information in the Flash Memory Array 100 is stored in compressed form;
`
`therefore, information to be stored in Flash Memory 100 must be compressed
`
`before storage. This is done by Compression Engine 260. Similarly, information
`
`read from Flash Memory Array 100 must be decompressed. This is done by
`
`Decompression Engine 280. A Bypass 240 allows for direct access to Flash
`
`Memory Array 100. Dye discloses that any of a number of lossless data
`
`compression methods may be used, including Huffman and Lempel-Ziv encoding
`
`[Dye, 18:20-35]
`
`
`
`48. To prevent the compression and decompression of data from impacting
`
`performance, the system of Dye includes specialized hardware to support these
`
`
`
`24
`
`

`
`
`
`activities [Dye, 4:44-49, 8:57-60]. In particular, Dye teaches the use of a parallel
`
`approach to compression and decompression. Briefly, one of the preferred
`
`embodiments of Dye discloses a parallel data compression approach to support
`
`Lempel-Ziv compression. In this particular embodiment, 16 encoders of the type
`
`shown in Dye Fig. 13 are used in parallel to produce encoded version of a four
`
`bytes of the Input Stream 610. This data is compared in parallel against 16 bytes
`
`of the current history table to determine the best encoding of the input data as
`
`shown in Dye Fig. 14 [Dye, Fig. 13, 14; 4:213-30, generally 18:43-26:57]. I will
`
`discuss the details of this parallel compression approach later with respect to
`
`claims 10, 17, and 24 of the ’862 Patent.
`
`
`
`49. The following discussion provides background on data compression and
`
`decompression, as used by Dye.
`
`
`
`50. Dye uses a variant of the Lempel-Ziv data compression technique and, LZSS.
`
`Details of Lempel-Ziv coding and its variant LZSS coding can be found in the
`
`original technical papers [Jacob Ziv & Abraham Lempel, A Universal Algorithm
`
`for Sequential Data Compression, IT-23 No. 3 IEEE Transactions on Information
`
`Theory 337 (1977)(“Ziv”)(see generally Section II. “The Compression
`
`Algorithm” at pp. 337-343); James A. Storer & Thomas G. Szymanski, Data
`
`
`
`25
`
`

`
`
`
`Compression via Textual Substitution, 19 No. 4 Journal of the Association for
`
`Computing Machinery (1982)(“Storer”)(see generally Section 2. “The Model and
`
`Basic Definitions” at 928-951)].
`
`
`
`51. Data compression was a widely known concept long before February 3, 2000.
`
`Basically, compression techniques attempt to reduce the size of a block of data by
`
`removing redundancies. A simple and familiar example is the use of acronyms
`
`and abbreviations in technical reports and the like. Instead of using a long-
`
`winded description, such as, “cathode ray tube” in a report, the author usually
`
`gives an abbreviation the first time the term is used. For example, the author
`
`might say “cathode ray tube (CRT).” Later the three letters CRT acronym can be
`
`used in place of the 17 character phrase “cathode ray tube.” Even if the reader is
`
`unfamiliar with the term they can simply go back to the first use of this term to
`
`find the full expression. This basic compression technique, i.e., using acronyms,
`
`is in a greatly simplified way the basis for Lempel-Ziv compression: “Basically,
`
`we employ the concept of encoding future segments of the source-output via
`
`maximum-length copying from a buffer containing the recent past output. The
`
`Transmitted codeword consists of the buffer address and the length of the copied
`
`segment” [Ziv, p. 337, ¶5].
`
`
`
`
`
`26
`
`

`
`
`
`52. Dye suggests several compression techniques, including Huffman coding,
`
`Lempel-Ziv compression, run length encoding and predictive encoding [Dye,
`
`18:20-35]. Of these, Lempel-Ziv-Storer-Szymanski (LZSS) compression forms
`
`the basis for Dye’s hardware based parallel compression technique [Dye, 18:44-
`
`49]. This technique is a variant of the basic Lempel-Ziv algorithm [Storer p. 928-
`
`929, §1: “Introduction”].
`
`
`
`53. Dye describes the parallel LZSS algorithm at 18:43

This document is available on Docket Alarm but you must sign up to view it.


Or .

Accessing this document will incur an additional charge of $.

After purchase, you can access this document again without charge.

Accept $ Charge
throbber

Still Working On It

This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.

Give it another minute or two to complete, and then try the refresh button.

throbber

A few More Minutes ... Still Working

It can take up to 5 minutes for us to download a document if the court servers are running slowly.

Thank you for your continued patience.

This document could not be displayed.

We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.

Your account does not support viewing this document.

You need a Paid Account to view this document. Click here to change your account type.

Your account does not support viewing this document.

Set your membership status to view this document.

With a Docket Alarm membership, you'll get a whole lot more, including:

  • Up-to-date information for this case.
  • Email alerts whenever there is an update.
  • Full text search for other cases.
  • Get email alerts whenever a new case matches your search.

Become a Member

One Moment Please

The filing “” is large (MB) and is being downloaded.

Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.

Your document is on its way!

If you do not receive the document in five minutes, contact support at support@docketalarm.com.

Sealed Document

We are unable to display this document, it may be under a court ordered seal.

If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.


Access Government Site

We are redirecting you
to a mobile optimized page.





Document Unreadable or Corrupt

Refresh this Document
Go to the Docket

We are unable to display this document.

Refresh this Document
Go to the Docket