Stac v Microsoft
Barry Margolin
I heard on the news a few days ago that Stac, the developers of the Stacker
disk compression software for MS-DOS, is suing Microsoft over patent
infringement. They're apparently claiming that the compression facility
built into MS-DOS 6.0 incorporates their patented technology. Microsoft is
counter-suing, claiming that Stac is using MS's proprietary test software
(they apparently got access to it while the two companies were working
together).
Does anyone know any more details about this, such as the patent(s)
involved?
--
Barry Margolin
System Manager, Thinking Machines Corp.
bar...@think.com {uunet,harvard}!think!barmar
Albert Silverman
: I heard on the news a few days ago that Stac, the developers of the Stacker
: bar...@think.com {uunet,harvard}!think!barmar
There was a piece about this situation on Weekend Edition NPR today.
According to the information presented on the radio, Stacker is claiming
that Microsoft, with its "bully" power, is able to dominate the market by
including in its DOS program compression technology from one of Stacker's
competitors. In other words, simply by Microsoft purchasing a license to
use compression technology developed by one of Stacker's competitors and
then using this in its DOS program, Microsoft obviates the user's need
for a separate purchase of the Stacker program by one who is using MS DOS
with the compression technology included.
Note that this argument being made by Stacker does NOT claim that
Microsoft has infringed upon Stacker's patents. Therefore, the relevant
patents involved are irrelevant in this particular case. What Stacker
SHOULD be suing for, if it is predisposed to do so, is Microsoft's
overwhelming ability to dominate the market in the manner that is being
used when it licenses technology from one of Stacker's competitors.
Unfortunately, however, Stacker is muddying the waters with a claim of
"patent infringement" when this is NOT the issue of contest.
Albert Silverman
slv...@netcom.com
and not a mere Device
v. Microsoft was that Microsoft had been licensing Stacker for use with
MS-DOS. I thought that was the genesis of the intellectual property claim.
Of course, I was only listening with one ear and watching with one eye, so
I may very well be mistaken.
D.J.Schaeffer | The Todal looks like a blob of glup. It makes
go...@world.std.com | a sound like rabbits screaming and smells
^^^^^^^^^^^^^^^^^^^^^ of old, unopened rooms.
James Thurber, _The 13 Clocks_
Dave Ihnat
Albert Silverman <slv...@netcom.com> wrote:
>There was a piece about this situation on Weekend Edition NPR today.
>According to the information presented on the radio, Stacker is claiming
>that Microsoft, with its "bully" power, is able to dominate the market by
>including in its DOS program compression technology from one of Stacker's
>competitors. In other words, simply by Microsoft purchasing a license to
>use compression technology developed by one of Stacker's competitors and
>then using this in its DOS program, Microsoft obviates the user's need
>for a separate purchase of the Stacker program by one who is using MS DOS
>with the compression technology included.
Oh, Ghod. This had better not be real; or if it is, I hope it gets thrown so
far by the court that they'll have to file an environmental impact statement in
China. Scrape it down to the essentials, and what it reads as is "They're real
big; by including any new feature in their product, it will automatically
succeed and put anyone who sells something like that out of business, and
that's not fair." This would, in effect, mean that any large company with
a big market share could never substantially improve its product once it was
established!!
Now, note that most of what Microsoft has included in the MS-DOS 6.2 are
corrections to weaknesses or downright omissions of the program loader/file
manager (I still shudder when someone calls DOS an OS) that we've griped about
for years. Had Microsoft released a mature product or developed it as rapidly
as it *should* have, none of the memory managers, backup utilities, or disk
compression products would ever have been *necessary*, and very likely would
only have existed as power-user niche products.
This just has to have been misreported...but I'm afraid it isn't...
---
Dave Ihnat
ign...@homebru.chi.il.us (preferred return address)
ign...@chinet.chi.il.us
Barry Margolin
>There was a piece about this situation on Weekend Edition NPR today.
>According to the information presented on the radio, Stacker is claiming
>that Microsoft, with its "bully" power, is able to dominate the market by
>including in its DOS program compression technology from one of Stacker's
>competitors. In other words, simply by Microsoft purchasing a license to
>use compression technology developed by one of Stacker's competitors and
>then using this in its DOS program, Microsoft obviates the user's need
>for a separate purchase of the Stacker program by one who is using MS DOS
>with the compression technology included.
>
>Note that this argument being made by Stacker does NOT claim that
>Microsoft has infringed upon Stacker's patents. Therefore, the relevant
>patents involved are irrelevant in this particular case.
That may be what they're claiming on NPR, but the lawsuit is definitely
about patent infringement. Scott Alter sent me a copy of the complaint,
which I've included below. The patents are 5,016,009 DATA COMPRESSION
APPARATUS AND METHOD and 4,701,745 DATA COMPRESSION SYSTEM; their abstracts
are included at the end of the complaint.
BTW, the name of the company is "Stac", not "Stacker" -- Stacker is the
product.
Someone else posted that he thought that Microsoft licensed Stacker.
According to the complaint, Microsoft asked to license Stacker, but the two
companies were never able to agree to license terms, as Microsoft didn't
want to pay royalties. I think this is why Stac is complaining about
Microsoft's dominance in the market -- had they licensed Stacker to them,
they would have given up their potential market, and Microsoft wasn't going
to compensate them.
Here is the complaint:
IRELL & MANELLA Morgan Chu Wayne M. Barsky Mark A. Flagel Jeffrey L. Arrington
Steven S. Weiner 1800 Avenue of the Stars Los Angeles, California 90067-4276
Telephone: (310) 277-1010
SHEA & GOULD John Kidd Nicholas L. Coch 1251 Avenue of the Americas New York,
New York 10020 Telephone: (212) 827-3000
Attorneys for Plaintiff Stac Electronics
UNITED STATES DISTRICT COURT CENTRAL DISTRICT OF CALIFORNIA
STAC ELECTRONICS, a California corporation, Plaintiff, v. MICROSOFT
CORPORATION, a Delaware corporation, Defendant.
Civil No. COMPLAINT FOR PATENT INFRINGEMENT DEMAND FOR JURY TRIAL
Plaintiff Stac Electronics (''Stac'') demands a jury trial on all issues and
alleges as follows:
JURISDICTION AND VENUE
1. This is an action for patent infringement arising under the Patent
Act of the United States, 35 U.S.C. 271 and 281. This Court has subject
matter jurisdiction over the matters complained of under 28 U.S.C. 1338(a)
and 1331.
2. Venue is proper in this judicial district pursuant to 28 U.S.C.
1400(b) and 1391(c), as defendant Microsoft Corporation (''Microsoft'')
resides and has committed acts of patent infringement in this judicial
district.
THE PARTIES
3. Stac is a corporation organized and existing under the laws of the
State of California and has its principal place of business at 5993 Avenida
Encinas, Carlsbad, California 92008. Stac designs, develops, markets and
supports data compression/decompression products that increase the
effective capacity of computer-related storage devices and the transmission
rates of data communication systems. Stac is the leading supplier of high
performance data compression products for personal computers.
4. Microsoft is a corporation organized and existing under the laws of
the State of Delaware. Microsoft's principal place of business is located
at One Microsoft Way, Redmond, Washington 98052. Microsoft develops,
produces and markets, among other things, a broad range of software for
business and professional use, including operating systems, languages and
applications programs. Microsoft is the world's largest software company,
with reported revenues in excess of $2.7 billion in fiscal 1992, and some
12,000 employees in 27 countries. Microsoft produces and markets, among
other products, the MS-DOS operating system software for IBM and
IBM-compatible personal computers.
FACTUAL BACKGROUND
5. An operating system is a group of programs that, among other tasks,
translates user commands to the computer, schedules and implements the
execution of applications programs, allocates computer memory, and manages
the flow of information and communication among various components of the
computer system. Application programs ''attach'' to the underlying
operating system and, when called upon to do so by the operating system,
perform discrete functions such as word processing, graphics and
spreadsheet operations.
6. MS-DOS is currently installed on in excess of 100 million IBM and
IBM-compatible personal computers, and Microsoft ships more than 20 million
units of MS-DOS every year. Microsoft's MS-DOS is the predominant operating
system in the IBM and IBM-compatible personal computer market. MS-DOS is
marketed principally to original equipment manufacturers (OEMs) under
agreements their personal computers.
7. Stac is the manufacturer and publisher of a data compression utility
progrm known as STACKER, which attaches to DOS operating systems such as
MS-DOS, as well as other operating systems. Utility programs are a large
and diverse family of application programs that are designed to enhance
personal computer performance. The principal function of STACKER is to
compress data stored on the hard disk of IBM nad IBM-compatible personal
computers when the data is not being used, and later decompress such data
when it is to be used, thereby increasing the effective storage capacity of
the computer.
8. Although there are a number of software companies which offer data
compression programs, Stac is the acknowledged industry leader in
developing and marketing data compression technology, and STACKER is
currently the best-selling data compression program for use on the DOS
operating system. Stac's proprietary data compression technology, developed
over the course of five years and at substantial cost, is protected by a
number of patents, including U.S. Patent Nos. 5,016,009 (the "009" patent)
and 4,701,745 (the "745" patent) (collectively, the "patents in suit").
9. Stac's proprietary data compression technology is relied upon daily
by more than four million computer users worldwide. STACKER is the winner
of PC Magazine's Technical Excellence Award, Windows Magazine's WIN 100
Award, PC Magazine's Editor's Choice Award, PC Computing's Most Valuable
Product Award, Byte Magazine's Best of Comdex-Finalist Award, and National
Software Testing Lab's Recommendation (Five Stars), and is the recipient of
numerous additional industry accolades.
10. Largely as a result of the tremendous market acceptance of STACKER,
which utilizes Stac's proprietary data compression technology, Stac quickly
grew from a company with 25 employees and revenues of less than $1 million
in 1989 to a company with more than 200 employees and a market
capitalization in excess of $150 million today.
11. The personal computer software industry is characterized by rapid
technological change which requires software developers continually to
enhance existing products and develop new products. A critical factor in
the success of a new or enhanced product is getting the product to market
quickly in response to new user needs or technological advances, while at
the same time maintaining the integrity and quality of the product.
12. It was a well-known fact in the personal computer industry as early
as 1991 that Microsoft's MS-DOS 5.0 retail upgrade sales were rapidly
declining with each passing quarter. As Microsoft's flagship product --
with approximately $700 million in revenue per year attributable to MS-DOS
sales alone -- Microsoft was under intense market pressure to stimulate
MS-DOS sales with an improved version of the MS-DOS operating system.
13. Due in part to the overwhelming market success of STACKER, the
personal computer industry quickly recognized that an operating system
capable of incorporating a high-quality data compression utility such as
STACKER would be highly competitive. Indeed, the principal competitor of
Microsoft's MS-DOS -- Novell's DR-DOS operating system -- had already
incorporated a data compression utility in its operating system software.
14. Microsoft's Chairman and Chief Executive Officer, William H. Gates,
became personally interested in Stac's proprietary data compression
technology, and the possibility of using such technology in MS-DOS, in
1991, at approximately the same time that STACKER was receiving a number of
coveted industry awards for technical excellence and overall product
quality.
15. Mr. Gates met with Stac's President, Gary W. Clow, at the Fall
Comdex-91 ceremony in Las Vegas. During a discussion which preceded the
award ceremony, Mr. Gates said that Microsoft was considering including a
data compression capability in the next release of MS-DOS. Mr. Gates
further stated that Microsoft would not be developing this capability
internally, but rather would seek to obtain another company's data
compression technology for inclusion in MS-DOS. The Editor-in-Chief of PC
Magazine, Michael J. Miller -- whose magazine would later that evening
present its Technical Excellence Award to Stac -- told Mr. Gates before the
ceremony began that STACKER was a first-rate product. Mr. Gates asked Mr.
Clow to contact Microsoft after Mr. Clow returned to California, and Mr.
Clow agreed.
16. In late 1991, as a result of Mr. Gates' interest, Mr. Brad Chase --
who was then Microsoft's Group Product Manager and who today is Microsoft's
General Manager for MS-DOS -- and Mr. Clow began discussing the possibility
of Microsoft licensing Stac's proprietary data compression technology for
inclusion in future versions of the MS-DOS operating system.
17. During the ensuing months of negotiations, Microsoft proposed that
Stac grant to Microsoft a world-wide license to incorporate STACKER data
compression technology and know-how into future versions of its MS-DOS
operating system software. Microsoft steadfastly refused, however, to
offer to pay Stac any royalty for Stac's patented data compression
technology.
18. Mr. Chase made it clear during the negotiations that Microsoft was
considering including data compression capability in future versions of the
MS-DOS operating system, and that if it were unable to reach an agreement
with Stac, it would obtain this capability elsewhere, even though Microsoft
believed -- as it told Stac on numerous occasions -- that STACKER was the
best data compression product for the DOS market. When the subject of
incorporating data compression technology other than Stac's arose, Mr. Clow
reminded Mr. Chase and others that Stac owned patent rights to its data
compression technology and would enforce its patents against any
infringers. At least one draft agreement was provided to Microsoft that
included a specific reference to Stac's '009 patent.
19. Microsoft attempted to persuade Stac that its proposal to
incorporate
Stac's proprietary data compression technology -- or, for that matter, any
reliable data compression technology -- into the MS-DOS operating system
would, if implemented, have an immediate and adverse effect on the
viability of STACKER as an independently marketed product for the DOS
market. Indeed, at one point during the negotiations, Microsoft presented
Stac with a spreadsheet analysis purporting to detail the adverse impact on
sales of STACKER -- Stac's flagship product -- in the event Microsoft and
Stac failed to reach an agreement and Microsoft incorporated a different
data compression utility in future versions of the MS-DOS operating system.
20. In approximately April of 1992, Stac broke off further discussions
with Microsoft in light of Microsoft's failure to present a proposal that
offered reasonable compensation to Stac for Microsoft's use of Stac's
proprietary data compression technology.
21. In approximately June of 1992, Mr. Chase advised Mr. Clow that
Microsoft was obtaining data compression technology for use in MS-DOS, but
that Microsoft wanted to offer Stac one last chance to reach an agreement.
In the ensuing discussions, it again became clear that Microsoft had no
intention of paying any compensation to Stac in exchange for Stac's
proprietary data compression technology. Discussions between Stac and
Microsoft thereupon terminated for the second time.
22. Shortly thereafter, it became well known to the industry that a new
version of its DOS operating system, MS-DOS version 6.0 (''MS-DOS 6.0"),
would be released in the first six months of 1993 and that MS-DOS 6.0 would
include a data compression utility, which Microsoft was to later call
''DoubleSpace.''
23. Before a new program (or new version of an existing program) is made
available for retail distribution, the software developer will often
distribute preliminary copies of the new software (the ''beta software'')
to a large group of intended users (the ''beta sites"). The developer then
seeks comments from the beta sites on the beta software's performance,
thereby allowing it to identify and fix problems or ''bugs'' in the beta
software that might have slipped through the developer's quality control
procedures. Consistent with this practice, Microsoft commenced its MS-DOS
6.0 Beta Test Program in the second half of 1992.
24. On or about November 23, 1992, a telephone conference was held with
Mr. Clow and Mr. Whiting of Stac, and Microsoft's Mr. Chase. During that
conversation, Mr. Chase admitted that, during Microsoft's ''normal due
diligence process,'' Microsoft had concluded that the DoubleSpace data
compression utility of the MS-DOS 6.0 operating system software infringed
Stac's '009 patent, one of the two patents in suit. Mr. Chase requested
that Stac grant a license to Microsoft under Stac's '009 patent. After a
brief discussion, Mr. Clow requested that Microsoft make a specific
licensing proposal to Stac, and Mr. Chase agreed to do so. During this same
telephone conference, Mr. Chase promised, in response to Stac's request, to
make available to Stac a copy of the beta version of the MS-DOS 6.0
software.
25. Several weeks later, after not hearing back from Mr. Chase on a
licensing proposal for Stac's patent, and after not receiving the promised
beta version of MS-DOS 6.0, Mr. Clow wrote to Mr. Chase and again requested
a copy of the MS-DOS 6.0 software. Mr. Clow wrote to Mr. Chase and again
requested a copy of the MS-DOS 6.0 software. Mr. Clow explained that other
software developers had access to the beta versions of MS-DOS 6.0, which
was putting Stac at a competitive disadvantage. Mr. Clow also noted that
Stac was still awaiting a specific licensing proposal from Microsoft for
Stac's '009 patent.
26. Microsoft finally made the beta version of the MS-DOS 6.0 software
available to Stac in January of 1993. At or about the same time, with
respect to Microsoft's earlier admission regarding the infringement of
Stac's '009
patent, Mr. Chase advised Stac in writing: ''Don't worry about the patent
stuff. We are just going to keep with our changed code which does not
infringe.''
27. After receiving the beta version of MS-DOS 6.0, Stac engineers
determined that, whether or not the ''code'' had in fact been changed from
earlier versions, as represented by Mr. Chase, the DoubleSpace data
compression utility contained in the beta version of MS-DOS 6.0 infringes
upon Stac's '009 and '745
patents.
28. On or about January 15, 1993, Mr. Chase of Microsoft provided Mr.
Whiting and Mr. Clow of Stac with a preliminary press release for the
Microsoft Real-time Compression Interface (''MRCI''). MRCI defines a
compression standard for allowing vendors to design software and hardware
products that utilize or ''build'' upon the Double Space data compression
utility in the MS-DOS 6.0 operating system.
29. Microsoft's preliminary press release confirms that ''DoubleSpace,
the integrated data compression technology ... will be available with the
next major version of MS-DOS, MS-DOS 6.'' The preliminary press release
also reveals that, in an effort to have the compression technology in
MS-DOS 6.0 quickly adopted as an industry standard, Microsoft is now
offering to license - for free - the infringing DoubleSpace technology to
independent hardware and software vendors.
30. Mr. Chase sent Microsoft's preliminary press release to Mr. Whiting
and Mr. Clow for the stated purpose of having Stac approve the following
proposed quote for Microsoft's ultimate press release, drafted for Stac by
Microsoft:
"We're excited about MS-DOS 6 and DoubleSpace because they create a
large opportunity for boards, chips and add-on software to enhance the
compression services that MS-DOS 6 and DoubleSpace offer ..."
31. On information and belief, Microsoft is taking the calculated risk
of incorporating what it knows to be Stac's patented data compression
technology in its MS-DOS 6.0 operating system in order to stimulate sales
of its flagship product and respond to the intense market and financial
community pressure to remain competitive and demonstrate continued growth.
On information and belief, Microsoft is taking the calculated risk of
incorporating what it knows to be Stac's patented data compression
technology in its MS-DOS 6.0 operating system in order to stimulate sales
of its flagship product and respond to the intense market and financial
community pressure to remain competitive and demonstrate continued growth.
FIRST CAUSE OF ACTION FOR PATENT INFRINGEMENT
32. Stac repeats and realleges, as if set forth in full, paragraphs 1
through 31 of this Complaint.
33. On May 14, 1991, the '009 patent, entitled "Data Compression
Apparatus And Method," was granted to Stac. Since its issuance, Stac has
been, and continues to be, the owner of all right, title and interest in
and to the '009 patent. A copy of the '009 patent is attached as Exhibit
A, and incorporated herein by reference.
34. Defendant Microsoft is infringing the '009 patent, in this judicial
district and elsewhere, in connection with its activities pertaining to the
beta version of its MS-DOS 6.0 operating system software for IBM and
IBM-compatible personal computers, which embodies the inventions disclosed
and claimed in the '009 patent.
35. Unless enjoined by the Court, Microsoft will continue to infringe
Stac's '009 patent.
36. As a direct and proximate result of Microsoft's conduct, Stac has
suffered and will continue to suffer irreparable injury, for which it has
no adequate remedy at law. Stac has also been damaged, and, until an
injunction issues, will continue to be damaged in its business and
reputation in an amount yet to be determined. Moreover, the willful and
deliberate nature of Microsoft's infringement renders this an exceptional
case, and thus Stac is further entitled to treble damages, as well as its
actual attorneys' fees and litigation costs.
SECOND CAUSE OF ACTION FOR PATENT INFRINGEMENT
37. Stac repeats and realleges, as if set forth in full, paragraphs 1
through 31 of this Complaint.
38. On October 20, 1987, the '745 patent, entitled "Data Compression
System," was granted to Ferranti, plc ("Ferranti"). Ferranti subsequently
assigned all right, title and interest in and to the '745 patent to Stac,
which is now the owner of all right, title and interest in and to the '745
patent. A copy of the '745 patent is attached as Exhibit B, and
incorporated herein by reference.
39. Defendant Microsoft is infringing the '745 patent, within this
judicial district and elsewhere, in connection with its activities
pertaining to the beta version of the MS-DOS 6.0 operating system software,
which embodies the inventions disclosed and claimed in the '745 patent.
40. Unless enjoined by the Court, Microsoft will continue to infringe
Stac's '745 patent.
41. As a direct and proximate result of Microsoft's conduct, Stac has
suffered, and will continue to suffer, irreparable injury, for which it has
no adequate remedy at law. Stac has also been damaged and, until an
injunction issues, will continue to be damaged in its business and
reputation in an amount yet to be determined.
PRAYER FOR RELIEF
WHEREFORE, Stac prays for judgment against defendant Microsoft as
follows:
1. For a judicial determination and declaration that the '009
patent is valid and enforceable;
2. For a judicial determination and declaration that the '009
patent is infringed by the beta version of the MS-DOS 6.0 operating system
software, and such other Microsoft products as may infringe;
3. For a judicial determination and declaration that Microsoft's
infringement of either or both of the '009 and '745 patents is willful;
4. For a judicial determination and declaration that the '745 patent is
valid and enforceable;
5. For a judicial determination and declaration that the '745 patent is
infringed by the beta version of the MS-DOS 6.0 operating system software,
and such other products as may infringe;
6. For an order preliminary and permanently enjoining Microsoft, its
officers, directors, shareholders, agents, servants, employees and
attorneys, and all entities and individuals acting in concert with them or
on their behalf, from infringing the '009 and '745 patents;
7. For damages according to proof, trebled;
8. For Stac's attorneys' fees and litigation costs; and
9. For such other and further relief as the Court may deem just and
proper.
Dated: January 25, 1993
Respectfully submitted,
IRELL & MANELLA
Morgan Chu
Wayne M. Barsky
Mark A. Flagel
Jeffrey L. Arrington
Steven S. Weiner
SHEA & GOULD
John Kidd
Nicholas L. Coch
By: Morgan Chu
Attorneys for Plaintiff
Stac Electronics
DEMAND FOR JURY TRIAL
Stac demands a jury trial on all issues.
Dated: January 25, 1993
Respectfully submitted,
IRELL & MANELLA
Morgan Chu
Wayne M. Barsky
Mark A. Flagel
Jeffrey L. Arrington
Steven S. Weiner
SHEA & GOULD
John Kidd
Nicholas L. Coch
By: Morgan Chu
Attorneys for Plaintiff
Stac Electronics
UNITED STATES PATENT (19) (11) Patent Number: 5,016,009
Whiting et al. (45) Date of Patent: May 14, 1991
(54) DATA COMPRESSION APPARATUS AND METHOD
(75) Inventors: Douglas L. Whiting, South Pasadena;
Glen A. George; Glen E. Ivey, both of Pasadena,
all of Calif.
(73) Assignee: Stac, Inc., Pasadena, Calif.
(21) Appl. No.: 297,152
(22) Filed: Jan. 13, 1989
(51) Int. Cl. (5) H03M 7/40; H03L 7/00 (52) U.S. Cl. 341/67; 341/95;
341/106; 375/112; 370/102
(58) Field of Search 375/27, 112; 358/261.1;
364/715.02; 341/51, 67, 106, 95; 370/102
(56) References Cited
U.S. PATENT DOCUMENTS
3,976,844 8/1976 Betz
4,021,782 5/1977 Hoerning
4,054,951 10/1977 Jackson et al.
4,412,306 10/1983 Moll
4,464,650 8/1984 Eastman et al. 341/51
4,491,934 1/1985 Heinz
4,558,302 12/1985 Welch 341/51
4,612,532 9/1986 Bacon et al. 341/90 X
4,701,745 10/1987 Waterworth
4,814,746 3/1989 Miller et al.
4,876,541 10/1989 Storer 341/67 X
OTHER PUBLICATIONS
J. Cleary et al. "Data Compression Using Adaptive Coding and Partial String
Matching." IEEE Transactions on Communications, 32:396-403 (1984). M
Wells. "File Compression Using Variable Length Encodings," The Computer
Journal, 15:308-313 (1972).
Primary Examiner - A.D. Pellinan
Assistant Examiner - Sharon D. Logan
Attorney, Agent, or Firm - Irell & Manella
(57) ABSTRACT
An apparatus and method for converting an input data character stream into
a variable length encoded data stream in a data compression system. The
data compression system includes a history array means. The history array
means has a plurality of entries and each entry of the history array means
is for storing a portion of the input data stream. The method for
converting the input data character stream includes the following steps.
Performing a search in a history array means for the longest data string
which matches the input data string. If the matching data string is found
within the history buffer means, the next step includes encoding the
longest matching data string found by appending to the encoded data stream
a tag indicating the longest matching data string was found and a string
substitution code. If the matching data string is not found within the
history array means, the next step includes encoding the first character of
the input data string by appending to the encoded data stream a raw data
tag indicating that no matching data string was found and the first
character of the input data string. UNITED STATES PATENT (19) (11) Patent
Number: 4,701,745 Waterworth (45) Date of Patent: Oct. 20, 1987
(54) DATA COMPRESSION SYSTEM
(75) Inventor: John R. Waterworth, Cheadle, England
(73) Assignee: Ferranti, plc, Cheshire, England
(21) Appl. No.: 835,793
(22) Filed: Mar. 3, 1986
(30) Foreign Application Priority Data
Mar. 6, 1985 (GB) United Kingdom 8505790
(51) Int. Cl. (4) H03M 7/30
(52) U.S. Cl. 340/347 DD; 364/900
(58) Field of Search 340/347 DD; 235/310;
358/260, 261; 364/900
(56) References Cited
U.S. PATENT DOCUMENTS
4,054,951 10/1977 Jackson 364/900
Primary Examiner - Charles D. Miller
Attorney, Agent or Firm - Kerkam, Stowell, Kondracki & Clarke
(57) ABSTRACT
A data compression system includes an input store (1) for receiving and
storing a plurality of bytes of data from an outside source. Data
processing means for processing successive bytes of data from the input
store includes circuit means (21-25) operable to check whether a sequence
of bytes is identical with a sequence of bytes already processed, output
means (27) operable to apply to a transfer medium (12) each byte of data
not forming part of such an identical sequence, and an encoder (26)
responsive to the identification of such a sequence to apply to the
transfer means (12) an identification signal which identifies both the
location in the input store of the previous occurrence of the sequence of
bytes and the number of bytes in the sequence.
CONTACT: IRELL & MANELLA
Morgan Chu
Wayne M. Barsky
Mark A. Flagel
Jeffrey L. Arrington
Steven S. Weiner
1800 Avenue of the Stars
Los Angeles, California 90067-4276
Telephone: (310) 277-1010
or
SHEA & GOULD
John Kidd
Nicholas L. Coch
1251 Avenue of the Americas
New York, New York 10020
Telephone: (212) 827-3000