James A. STORER, Refac International, Ltd., Plaintiffs,
v.
HAYES MICROCOMPUTER PRODUCTS, INC. Zoom Telephonics, Inc. Defendants.
Civil Action No. 96-10602-WGY.
United States District Court, D. Massachusetts.
March 25, 1997.*499 Ronald J. Schultz, Kevin D. Conneely, Robins, Kaplan, Miller & Ciresi, Minneapolis, MN, John N. Love, Robins, Kaplan, Miller & Ciresi, Boston, MA, for James A. Storer, Refac Intern., Ltd.
Bruce E. Falby, Hill & Barlow, Boston, MA, Kirk W. Watkins, Sonya Y. Ragland, Parker, Johnson, Cook & Dunlevie, Atlanta, GA, for Hayes Microcomputer Products, Inc.,
*500 Thomas J. Sartory, David S. Weiss, Julie A. Frohlich, Goulston & Storrs, Marshall D. Stein, Cherwin & Glickman, Boston, MA, John F. Lynch, Arnold, White & Durkee, Houston, TX, Philip D. Segrest, Jr., Hartwell P. Morse, III, Daniel R. Cherry, Welsh & Katz, Ltd., Chicago, IL, for Defendant Zoom Telephonics, Inc.
Marshall D. Stein, Cherwin & Glickman, Boston, MA, John F. Lynch, Arnold, White & Durkee, Houston, TX, for Counter-Claimant Zoom Telephonics, Inc.
MEMORANDUM AND ORDER
YOUNG, District Judge.
James A. Storer and Refac International, Ltd. (collectively the "Plaintiffs") are the owners of United States Patent 4,876,541 (the "Storer Patent"). The Storer Patent describes a "data compression system," embodied in a computer program, that dynamically compresses and then decompresses streams of electronic data. The most widespread practical application of the invention is the speedy and efficient transmission of electronic data (in compressed form) from one computer to another via modem.
The Plaintiffs commenced this action alleging that computer modems manufactured and sold by Hayes Microcomputer Products, Inc. ("Hayes") and Zoom Telephonics, Inc. ("Zoom," collectively the "Defendants"), infringe upon one or more of the claims of the Storer Patent. Both Hayes and Zoom advertise that their modems compress and decompress data according to an international standard adopted after the Storer Patent issued, entitled Recommendation V.42 bis ("V.42 bis").[1] The Plaintiffs contend that all modems which follow the V.42 bis standard infringe upon the Storer Patent.
The Defendants now come before this Court having each filed a pre-discovery motion for summary judgment of non-infringement. For purposes of these motions: 1) the Defendants stipulate that their respective modems operate according to the exact specifications set forth in the V.42 bis standard, and 2) the Plaintiffs concede the absence of literal infringement, but assert that a genuine issue of material fact exists as to whether the accused modems infringe upon the Storer Patent under the doctrine of equivalents.
I. RELEVANT LEGAL STANDARDS
Summary judgment is appropriate where no genuine issue of material fact exists and the moving party is entitled to judgment as matter of law. Fed.R.Civ.P. 56; London v. Carson Pirie Scott & Co., 946 F.2d 1534, 1537 (Fed.Cir.1991). A "genuine" issue of fact is one that a reasonable jury, on the record before the court, could resolve in favor of the non-moving party. Anderson v. Liberty Lobby, Inc., 477 U.S. 242, 248, 106 S. Ct. 2505, 2510, 91 L. Ed. 2d 202 (1986). In making this determination, the court must view the evidence in the light most favorable to the non-moving party and draw all reasonable inferences in its favor. Eastman Kodak Co. v. Image Technical Servs., Inc., 504 U.S. 451, 456, 112 S. Ct. 2072, 2076, 119 L. Ed. 2d 265 (1992) (citing Anderson, 477 U.S. at 255, 106 S.Ct. at 2513).
Resolving a claim of patent infringement is a two-step process. The court must first determine the meaning and scope of the patent claims at issue, a question of law, before the factfinder may resolve whether the accused device infringes the patent claims as construed by the court, a question of fact. Markman v. Westview Instruments, Inc., ___ U.S. ___, ___ - ___, 116 S. Ct. 1384, 1393-96, 134 L. Ed. 2d 577 (1996). Although Markman involved literal infringement, the same analytical framework applies at least for now to claims brought under the doctrine of equivalents. See Warner-Jenkinson Co. v. Hilton Davis Chem. Co., ___ U.S. ___, ___, 117 S. Ct. 1040, 1053, 137 L. Ed. 2d 146 (1997) (declining to reach the issue of whether infringement under the doctrine of equivalents is a question for the *501 jury rather than the judge, but noting that "there is ample support in our prior cases" for the Federal Circuit's holding that it is question for the jury).
A. Claim Interpretation
"It is well-settled that, in interpreting an asserted [patent] claim, the court should look first to the intrinsic evidence of record, i.e., the patent itself, including the claims, the specification, and if in evidence, the prosecution history." Vitronics Corp. v. Conceptronic, Inc., 90 F.3d 1576, 1582 (Fed. Cir.1996) (citing Markman v. Westview Instruments, Inc., 52 F.3d 967, 979 [Fed.Cir. 1995]). The terms used in the patent to describe an invention are given their ordinary and customary meaning "unless another meaning is specified or evident from the patent history." Johansson v. Rose Displays, Ltd., 924 F. Supp. 328, 330 (D.Mass. 1996) (citing Transmatic Inc. v. Gulton Indus., 53 F.3d 1270, 1277 [Fed. Cir.1995]; Carroll Touch, Inc. v. Electro Mechanical Sys., Inc., 15 F.3d 1573, 1577 [Fed.Cir. 1993]). A court may look to extrinsic evidence to aid its interpretation of a patent claim only if the intrinsic evidence is ambiguous. Vitronics, 90 F.3d at 1583.
B. Infringement Under the Doctrine of Equivalents
In its recent opinion in Warner-Jenkinson Co. v. Hilton Davis Chem. Co., ___ U.S. ____, 117 S. Ct. 1040, 137 L. Ed. 2d 146 (1997), the Supreme Court attempted to clarify the applicable standard for claims of infringement under the doctrine of equivalents. Historically, courts have applied a "triple identity" test, see id. at ____, 117 S.Ct. at 1054, which looks to whether the accused device "performs substantially the same overall function or work, in substantially the same way, to produce substantially the same overall result as the claimed invention." Dolly, Inc. v. Spalding & Evenflo Cos., 16 F.3d 394, 397 (Fed.Cir.1994) (citing Graver Tank & Mfg. Co. v. Linde Air Prods. Co., 339 U.S. 605, 608, 70 S. Ct. 854, 856, 94 L. Ed. 1097 [1950]). In Hilton Davis Chem. Co. v. Warner-Jenkinson Co., 62 F.3d 1512 (Fed.Cir. 1995), however, the Federal Circuit held that "evaluation of function, way, and result does not necessarily end the inquiry," id. at 1518, and announced the circular and somewhat amorphous standard that "infringement under the doctrine of equivalents requires proof of insubstantial differences between the claimed and accused products or processes," id. at 1521-22, from the vantage point of a person of ordinary skill in the relevant art, id. at 1519.
The Supreme Court, in reversing the Federal Circuit, held that the "particular linguistic framework used is less important than whether the test is probative of the essential inquiry: Does the accused product or process contain elements identical or equivalent to each claimed element of the patented invention?" Warner-Jenkinson, ___ U.S. at ____, 117 S.Ct. at 1054, (emphasis added). In applying this standard, the Supreme Court cautioned, it is important to maintain the focus on the individual elements of the claim, rather than the invention as a whole. Id. at ____, 117 S.Ct. at 1049.
A focus on individual elements and a special vigilance against allowing the concept of equivalence to eliminate completely any such elements should reduce considerably the imprecision of whatever language is used. An analysis of the role played by each element in the context of the specific patent claim will thus inform the inquiry as to whether the substitute element matches the function, way, and result of the claimed element, or whether the substitute element plays a role substantially different from the claimed element.
Id. at ____, 117 S.Ct. at 1054.
II. FACTUAL BACKGROUND
Data compression is the process of reducing the size of the representation of a string of electronic data in order to permit it to be transmitted or stored more efficiently and later to be reconstructed without error. In the context of data communications (e.g., transmissions between modems), data compression saves time and money by reducing the amount of data that needs to be transmitted in order to convey the same amount of information.
A modem is a telecommunications device that permits one computer to transmit data, via a (transmitting) modem and a telephone line, to another computer equipped with a *502 (receiving) modem. Many modems have the capability of compressing data by using shorthand codes to represent longer strings of the data input stream. The transmitting modem (the encoder) sends only the shorthand codes, and the receiving modem (the decoder) then decompresses the data by translating the codes back into their original form (the output stream).
A. Dynamic Dictionary Method of Data Compression
The Storer Patent and the V.42 bis standard both use a "dynamic" or "adaptive" dictionary method of data compression. Under this general approach, which was well-established in the prior art at the time the Storer Patent was awarded,[2] the transmitting and receiving modems maintain their own internal dictionaries, with each dictionary entry consisting of a string of data and the corresponding shorthand code. The dictionaries are initialized to contain codes only for each single character of the input alphabet (e.g., the letters of the alphabet, the digits from 0 to 9, and other single-character symbols).[3] The modems then build up their dictionaries in real time as the data is transmitted. Because the dictionaries are constructed on the fly, they do not waste space on shorthand codes for characters that are not actually transmitted.
To illustrate how this process operates, suppose that the input data stream consists of the characters "THE-DOG-CHASED-THE CAT." Starting with the first character of the data input stream, the transmitting modem determines the longest string in its dictionary that matches the incoming input; this is known as the "current match."[4] Because the dictionaries initially contain codes only for individual characters, the first three current matches will be "T", "H", and "E," and accordingly, the transmitting modem will send three separate codes for these characters. Both the transmitting and the receiving modems, however, noting the occurrence of the codes for T, H, and E one after another, might update their respective dictionaries to include a shorthand code for the three-character string "THE." Thus, when the transmitting modem reaches the second "T" in the input data stream, the current match will be "THE," and the transmitting modem will transmit only the single shorthand code.
In order for this dynamic dictionary approach to data compression to yield an accurate result, it is essential that both the transmitting and receiving modems make the same updates to their respective dictionaries. It is not necessary, however, for the modems to keep each other advised of their updating activities. Instead, each modem performs its updates in accordance with a predetermined rule, known as an "update heuristic"[5] and assumes that the other modem is doing the same.[6]
*503 During the course of a long data transmission, the dictionary may become full. In that event, a predetermined "deletion method"[7] is used to create room. Once again, it is essential that both the transmitting and the receiving modems use the same deletion method.
B. The Present Dispute
The Storer Patent discloses a dynamic dictionary data compression system that utilizes, inter alia, novel update and deletion heuristics. Of the fifty-five claims in the Storer Patent, Claims 1, 18, 19, 35, and 55 are independent. Claim 18 describes the novel deletion method, while the other independent claims each recite the novel update heuristic as one of the claim limitations.[8]
All of the remaining claims are dependent, either directly or through an intervening claim, on one of the independent claims. A dependent claim incorporates by reference all of the limitations of the claim to which it refers. 35 U.S.C. § 112. Thus, if V.42 bis modems do not infringe upon any of the independent claims, as matter of law, they do not infringe on any claims in the patent. Wolverine World Wide, Inc. v. Nike, Inc., 38 F.3d 1192, 1199 (Fed.Cir.1994). Accordingly, the Defendants have concentrated their efforts on demonstrating non-infringement of the five independent claims.
To establish infringement under the doctrine of equivalents, every claim element must be present in the accused device, either exactly or by an equivalent. Warner-Jenkinson, ___ U.S. at ____, 117 S.Ct. at 1054; see also Intellicall, Inc. v. Phonometrics, Inc., 952 F.2d 1384, 1389 (Fed.Cir.1992). Although the independent Storer Patent claims each contain a myriad of other claim elements, the Defendants' respective motions for summary judgment of non-infringement are based exclusively on the alleged dissimilarity between the update and deletion techniques described in the V.42 bis Recommendation and those set forth in the Storer Patent. Accordingly, as to Claims 1-17 and 19-55, the motions for summary judgment must be denied unless the Court determines that no reasonable jury could conclude that the V.42 bis update heuristic and the novel update algorithm claimed in the Storer Patent constitute equivalents. Similarly, as to Claim 18, the motions for summary judgment must be denied unless the Court determines that no reasonable jury could conclude that the V.42 bis deletion method and the deletion method claimed in the Storer Patent constitute equivalents.
III. THE UPDATE HEURISTIC (Claims 1-7, 19-55)
A. Introduction
The Storer Patent describes a novel update heuristic that adds N new entries to the dynamic dictionary for each current match, where N equals the number of characters in the current match. The new entries consist of the prior match concatenated (added to) all of the non-empty prefixes of the current match.[9] For example, if the current match is "DOG" (N = 3) and the prior match is "A," the following three entries would be added to the dictionary: "AD," "ADO," and "ADOG." The parties agree that persons of ordinary skill in the art now commonly refer to this *504 update algorithm as the "All Prefixes" (AP) heuristic.[10]
It is undisputed that the V.42 bis standard does not use the exact update method claimed in the Storer Patent. The Plaintiffs acknowledge that V.42 bis does not utilize the AP heuristic, and that V.42 bis modems add only one dictionary entry for each current match, regardless of the number of characters in the current match (for any value of N). Nevertheless, the Plaintiffs contend that 1) V.42 bis uses a "First Character" (FC) update heuristic, and 2) persons of ordinary skill in the art consider FC an equivalent to the AP update means described in the Storer Patent.[11] The Defendants respond that 1) in fact, V.42 bis uses a "Next Character" (NC) update heuristic, and 2) regardless of whether V.42 bis uses FC or NC, neither is equivalent to the AP heuristic used in the Storer Patent.
B. Illustration of the Relevant Update Heuristics
Recognizing the esoteric nature of the technology at issue, the Court begins its analysis of these update heuristics through the following example (hereinafter the "Parcells Example"). Assume that 1) in the middle of the data transmission, a modem using the dynamic dictionary method of data compression encounters the data stream "PARCELLS;" 2) in addition to the letters of the input alphabet, the modem's dictionary already contains the entries "AR," "ARC," and "LL," which were added earlier in the data stream; 3) the characters immediately preceding and following "PARCELLS" in the data stream are blank spaces; and 4) like most systems that use the dynamic dictionary method of data compression, the modem takes the longest string already in the dictionary that matches the incoming input as the "current match."[12]
1. All Prefixes (AP) Heuristic
The parties agree that AP is the heuristic described in the Storer Patent. It concatenates (adds) the previous match with all of the non-empty prefixes of the current match. Note that, as expressly required by the Storer Patent, the AP heuristic adds N new dictionary entries for each current match, where N equals the number of characters in the current match.
CURRENT MATCH ENTRIES ADDED TO DICTIONARY
1) P _P
2) ARC PA; PAR; PARC[13]
3) E ARCE
4) LL EL; ELL
5) S LLS
*505 2. First Character (FC) Heuristic
The Plaintiffs contend that the V.42 bis standard uses the FC heuristic. FC concatenates (adds) the previous match with the first character of the current match.
CURRENT MATCH ENTRIES ADDED TO DICTIONARY
CURRENT MATCH ENTRIES ADDED TO DICTIONARY
1) P P
2) ARC PA
3) E ARCE
4) LL EL
5) S LLS
To a certain extent, FC is a subset of the AP heuristic: when the current match is one character (when N =i), the same entries will be added to the dictionary under both AP and FC. When the current match is greater than one ("N > 1"), however, AP adds multiple entries to the dictionary, while FC adds only one entry. As a result, the dictionary grows more rapidly under AP than FC, and as the data stream progresses, a modem using AP will likely begin to draw different current matches than a modem using FC. For example, for the second current match, AP adds "PA," "PAR," and "PARC" to the dictionary, while FC adds only "PA." If the string "PARCELLS" happens to recur later in the data stream, for a modem using AP, the next current match would be "PARC;" in contrast, for a modem using FC, the next current match would be "PA."
3. Next Character (NC) Heuristic
According to the Defendants, the V.42 bis standard does not use the FC heuristic, but rather uses the NC heuristic. NC concatenates (adds) the current match with the next character from the uncompressed input.
CURRENT MATCH ENTRIES ADDED TO DICTIONARY
1) P PA
2) ARC ARCE
3) E EL
4) LL LLS
5) S S_
FC and NC yield nearly identical results; essentially, NC adds the same entries as FC, but does so one step earlier. Unlike all of the other update heuristics discussed in this example, however, NC lacks the "processed components property" because it uses data that has not yet been processed as a basis for forming new dictionary entries. As a result, the receiving modem must work by adding strings one step later than they were added by the transmitting modem. Although generally not a problem, for certain data strings, this one-step time lag can result in a decoding glitch. See Declaration of Dr. James A. Storer ("Storer Decl.") ¶ 16.[14]
*506 4. Current Match (CM) Heuristic
CM is the prior art heuristic developed by Mark N. Wegman and Victor S. Miller. See supra note 2. It concatenates (adds) the previous match with the current match.
CURRENT MATCH ENTRIES ADDED TO DICTIONARY
1) P P
2) ARC PARC
3) E ARCE
4) LL ELL
5) S LLS
CM lacks what the Plaintiffs refer to as the "all prefixes property" because it does not ensure that if an entry is in the dictionary, so are all of its prefixes. For example, for the second current match, CM adds "PARC" to the dictionary, but does not add the prefixes "PA" and "PAR."
C. The V.42 Bis Update Heuristic
The Defendants contend that the plain language of the V.42 bis Recommendation unambiguously describes an NC update heuristic. See Recommendation V.42 bis § 6.4 (stating that "the next character shall be read and appended to the string"). The Plaintiffs concede that Section 6.4 is phrased in the language of the NC heuristic, but assert that other provisions in the V.42 bis Recommendation add important elements to the update procedure which make it identical to the FC heuristic. Most importantly, in determining the current match, Section 6.3(b) forbids the use of the dictionary entry that was added in the preceding step.[15] This modification effectively eliminates the decoding glitch which plagues the NC heuristic and gives the V.42 bis update heuristic the "processed components property" which NC lacks. See Storer Decl. ¶ 17; Second Declaration of Dr. James A. Storer ("Second Storer Decl.") ¶ 3. Since FC and NC are nearly identical except that NC adds entries to the dictionary one step earlier than FC, the Plaintiffs assert that the one-step delay in the use of the new dictionary entry mandated by Section 6.3(b) means that V.42 bis effectively operates according to an FC heuristic. Furthermore, as the Plaintiffs noted during oral argument, Appendix II in the V.42 bis Recommendation contains an example of how the V.42 bis update algorithm operates which is consistent with the proper results under FC but not under NC.[16]
For the foregoing reasons, this Court holds that the Defendants have failed to demonstrate that there is no genuine issue of material fact as to whether V.42 bis modems use an FC or NC update heuristic. Accordingly, for purposes of these summary judgment motions only, the Court adopts the nonmovant Plaintiffs' contention that V.42 bis uses FC.
D. Prior Art Limitation on Range of Permissible Equivalents
Hayes argues that, even assuming V.42 bis uses the FC update heuristic, it is unnecessary for this Court to reach the question of whether FC and AP constitute equivalents because 1) FC is prior art to the Storer Patent, and 2) the Storer Patent claims must be construed, if possible, to avoid reaching the prior art in order to preserve their validity. Reply Brief of Defendant Hayes ("Hayes Reply Brief") at 5 (citing ACS Hosp. Sys., Inc. v. Montefiore Hosp., 732 F.2d 1572, 1577 [Fed.Cir.1994]).[17]
As to the first prong of Hayes' argument, this Court holds that FC does constitute prior art to the Storer Patent. Storer's 1985 *507 article, see supra note 2, which the Plaintiffs concede is prior art, describes the algorithm of "concatenat[ing] the last match with the first character of the current match" as one of "two simple heuristics for forming new dictionary entries for which [] significant experimental research has been performed." Storer, Textual Substitution Techniques for Data Compression at 122-23. This Court rejects the Plaintiffs' assertion that the Storer article only addresses the theoretical underpinnings of FC. Indeed, it is difficult to see how the description of the FC heuristic in the Storer article is not enabling as it is the same description that both parties presently use for FC. See, e.g., Storer Decl. ¶ 13; Rebuttal Affidavit of Alan Clark ("Clark Rebuttal Aff.") ¶ 8 at 7. Furthermore, the Storer Patent itself describes the 1985 Storer Article as developing a "practical technique" for data compression. Storer Patent Col. 2, Line 48.
Hayes is also correct that prior art restricts the application of the doctrine of equivalents. Wilson Sporting Goods Co. v. David Geoffrey & Assocs., 904 F.2d 677, 683 (Fed.Cir.), cert. denied, 498 U.S. 992, 111 S. Ct. 537, 112 L. Ed. 2d 547 (1990). The reason for this limitation, however, "is not because we construe claims narrowly if necessary to sustain their validity." Id. at 684 (emphasis added). As the Wilson court noted, "[t]he doctrine of equivalents, by definition, involves going beyond any permissible interpretation of the claim language," and "[t]o say that the doctrine of equivalents extends or enlarges the claims is a contradiction in terms." Id. This Court therefore rejects Hayes' contention that if the Court were to deem V.42 bis modems equivalent to the devices claimed in the Storer Patent, it would enlarge the Storer Patent claims to the point where they would be rendered invalid.
Contrary to Hayes' assertion, the actual purpose of the prior art limitation on the scope of permissible equivalents is to "prevent the patentee from `obtain[ing], under the doctrine of equivalents, coverage which (the patentee) could not lawfully have obtained from the [Patent and Trademark Office] by literal claims.'" Conroy v. Reebok Int'l, Ltd., 14 F.3d 1570, 1577 (Fed.Cir.1994) (quoting Wilson, 904 F.2d at 684). The relevant question therefore "is not whether each [claim] element existed in the prior art, but whether the prior art made obvious the invention as a whole for which patentability is claimed." Grain Processing Corp. v. American-Maize Prods. Co., 840 F.2d 902, 907 (Fed.Cir.1988) (citing Lindemann Maschinenfabrik GMBH v. American Hoist & Derrick Co., 730 F.2d 1452, 1462 [Fed.Cir.1984)). (emphasis added). Although the update heuristic is the only claim limitation involved in the present dispute, it is not the only limitation within Claims 1-17 and 19-55. Looking to the patent as a whole, "[i]t is conceivable that any one of [the claim) limitations, alone or in combination with the other limitations, may have been sufficient to confer patentability." Bradshaw v. Igloo Prods. Corp., No. 96-1199, 1996 WL 663310, at *4 (Fed.Cir. 1996) (unpublished disposition). Thus, the "mere existence of [FC] in the prior art [does not) automatically preclude[] [the Plaintiffs] from asserting a scope of equivalency sufficient to encompass the corresponding element in [V.42 bis]." Conroy, 14 F.3d at 1577 (emphasis added).[18]
E. Application of the Doctrine of Equivalents
Drawing all reasonable inferences in favor of the Plaintiffs, see Eastman Kodak, 504 U.S. at 456, 112 S.Ct. at 2076, this Court assumes, for purposes of these motions, that V.42 bis uses the FC update heuristic, and that a modem using the FC update heuristic *508 does not fall outside the range of permissible equivalents to the claimed invention. Accordingly, this Court must now consider whether a reasonable jury could conclude that the FC update heuristic is "equivalent" to the AP update heuristic described in Claims 1-17 and 19-55 of the Storer Patent. See Warner-Jenkinson, ___ U.S. at ____, 117 S.Ct. at 1054. Because the Plaintiffs have focused their infringement argument on the evidence in the record regarding function, way, and result, the Court uses that framework to aid its analysis.
1. Function
It is undisputed that the claimed "update means" in the Storer Patent (AP) and the update method described in the V.42 bis standard (FC) perform substantially the same function: to identify and add new strings of characters to the dynamic dictionary structure.
2. Way
The Storer Patent claims and V.42 bis do not perform this update function in substantially the same way, however. First, for every current match of length N, AP adds N new entries to the dynamic dictionary, while FC always adds one entry, regardless of the length of the current match. Thus, whenever N > 1, the Storer Patent adds multiple entries to the dictionary, while V.42 bis does not.[19] Second, the Storer apparatus uses all of the characters in the current match to construct the new dictionary entries, while V.42 bis uses only the first character of the current match.
The Plaintiffs acknowledge these differences between AP and FC, but nevertheless contend that "[t]here is substantial similarity between the way the two relevant update heuristics work to satisfy infringement under the doctrine of equivalents." Plaintiffs' Memorandum in Opposition to Defendants' Motions for Summary Judgment of Non-Infringement ("Plaintiffs' Brief") at 11. In particular, the Plaintiffs point to four categories of similarities which the Court will now address in turn.
First, the Plaintiffs assert that every dictionary entry added by V.42 bis will also always be added by the Storer apparatus. Plaintiffs' Brief at 11. As Zoom points out, however, the Plaintiffs do not dispute that the converse is not true not every dictionary entry added by the Storer update means will be added to a V.42 bis modem's dictionary. Defendant Zoom's Reply Concerning in Motion for Summary Judgment of Non-Infringement ("Zoom Reply Brief") at 2. It is well settled that "[i]t is the limitations and functions of the invention described in the claims, not the elements or functions of the accused device, which establish the reference point for the doctrine of equivalents analysis." Insta-Foam Prods., Inc. v. Universal Foam Sys., Inc., 906 F.2d 698, 702 (Fed.Cir.1990).[20]
Second, the Plaintiffs state that although a finding of infringement cannot be based solely on the fact that the Storer Patent and V.42 bis add identical dictionary entries when N = i, the "Defendants' admission that the two methods are identical some of the time supports the conclusion that the two are substantially similar all of the time." Plaintiffs' Brief at 12. (citing Bell Communications *509 Research, Inc. v. Vitalink Communications Corp., 55 F.3d 615, 622-23 [Fed.Cir. 1995]; Pall Corp. v. Micron Separations, Inc., 792 F. Supp. 1298, 1319 [D.Mass.1992], aff'd in rel. part, 66 F.3d 1211 [Fed.Cir.1995], cert. denied, ___ U.S. ____, 117 S. Ct. 1243, 137 L. Ed. 2d 326 [1997]). This argument is also without merit.[21] Although the Bell Communications court did hold that "an accused product that sometimes, but not always, embodies a claimed method nonetheless infringes," 55 F.3d at 622-23, in this case, nothing in the record suggests that V.42 bis modems ever use the AP update means described in the Storer Patent. Furthermore, in Pall, this Court stated only that "an infringer cannot take refuge in the fact that he has a sloppy product." 792 F.Supp. at 1319. FC is not a sloppy or imperfect version of the AP, but rather a different approach to data compression. See infra pp. 510-511.
Third, the Plaintiffs point out that both the Storer Patent and the V.42 bis standard store their respective dictionary entries in a tree data structure known as a "trie," and that both prescribe an upper limit on the length of strings that may be added to the dynamic dictionary (the "maxmatch" feature). Plaintiffs' Brief at 11. While these similarities indicate that some of the other limitations described in the Storer Patent are also present in V.42 bis modems, they do not change the fact that FC and AP (and hence V.42 bis and Storer) add new entries to the dictionary in a substantially different way. To establish infringement of a patent claim, every claim element must be present in the accused device, either exactly or by an equivalent. Warner-Jenkinson, ___ U.S. at ____, 117 S.Ct. at 1054; Intellicall, 952 F.2d at 1389.
Finally, the Plaintiffs contend that AP and FC operate in a substantially similar manner because both have what Storer describes as the "processed components" property[22] and the "all prefixes" property. Plaintiffs' Brief at 11-12. While the Plaintiffs are indeed correct that, under both AP and FC, if an entry is in the dictionary, so are all of its prefixes, the term "all prefixes" property is somewhat misleading. Only the AP heuristic adds new entries to the dictionary by concatenating the prior match to all of the prefixes of the current match. FC, by contrast, concatenates the prior match only to the first character of the current match. As a result, under AP, if an entry is in the dictionary, it is more likely that some of its suffixes will also be in the dictionary than under FC.[23] This difference is not insubstantial; if the longer data string (containing the suffix) repeats in the data stream, the modem using AP will be able to compress the entire string, while the modem using FC will not. See infra note 25.
3. Result
Because AP adds multiple dictionary entries whenever N > 1, the Storer dictionary *510 grows at a faster rate than the V.42 bis dictionary. See Plaintiffs' Brief at 12 ("In effect, V.42 bis creates a subset of updated dictionary entries to those added by Storer's [AP] heuristic.") (emphasis added); Wornell Decl. at Tables 1-2.[24] Furthermore, given that both the Storer Patent and V.42 bis use dictionaries of finite size, the Storer dictionary will become full more rapidly than the V.42 bis dictionary. See Expert Declaration of Clark D. Thomborson ("Thomborson Decl.") ¶ 46.
The Plaintiffs respond that even though AP causes the dictionary to grow more rapidly, AP and FC result in "similar amounts of compression" because: 1) FC adds the first set of strings added by AP for each current match; and 2) for N > 1, the additional strings added by AP will be added by FC at a later step if they turn out to occur often in the text. Thomborson Decl. ¶ 22. Maybe so. But the fact that FC adds these entries later than AP (i.e., not until the next time the string arises in the input stream) is not an insubstantial difference. First, because the Storer dictionary at least until it fills up and has to begin deleting entries contains every dictionary entry in the V.42 bis dictionary, plus additional (and longer) entries, it is likely that, as the input stream continues, the Storer apparatus will begin to obtain longer current matches than V.42 bis.[25] Second, because AP adds long strings quickly, whether they are repeated or not, the Storer dictionary will become full more rapidly than V.42 bis. Even though both the Storer apparatus and V.42 bis have procedures to clear space in the dictionary once it becomes full, the fact that it will generally be necessary to use the deletion means more often under the Storer apparatus is not insignificant; deletion processing takes time, and there is also a risk that the strings being deleted will recur later in the text (thereby impairing the compression ratio). Declaration of Victor S. Miller ("Miller Decl.") ¶ 50.[26] As stated by the Chief Technical Officer and Vice President of Hayes, Alan Clark:
If long strings repeat frequently, the Storer system is optimal. If long strings repeat infrequently, V.42bis will operate faster with a more compact dictionary ... [Therefore], [t]he [AP and FC] algorithms *511 approach optimal compression from opposite ends of the spectrum: V.42 bis adds a single string of minimal additional length with each match, while Storer adds every possible string from the latest two matches.
Clark Rebuttal Aff. ¶ 8 at 11 (emphasis omitted). Thus, by design, the AP and FC heuristics yield substantially different results.[27]
4. Conclusion
Although AP and FC perform substantially the same function, AP and FC perform this function in substantially different ways and achieve substantially different results. Accordingly, this Court holds that no reasonable jury could conclude that AP and FC constitute equivalents, see Warner-Jenkinson, ___ U.S. at ____, 117 S.Ct. at 1054, and hereby GRANTS the Defendants' respective motions for summary judgment as to Claims 1-17 and 19-55 of the Storer Patent.
IV. THE DELETION METHOD (Claim 18)
A. Background: The Trie Data Structure and Leaf Nodes
A data structure is a way to organize data in computer memory which allows for faster and more efficient manipulation of the data for a specific problem. Both the Storer Patent and V.42 bis organize their respective dynamic dictionaries in a tree-like data structure known as a "trie." There is exactly one trie for every letter of the input alphabet. Although somewhat counter intuitive, at the top of each trie rests a "root node." A root node is the single character of the input alphabet from which the rest of the tree stems down. Root nodes are never deleted.
As the dictionary grows, offspring branch off from these root nodes. For example, if the dynamic dictionary contains the entries "PA," "PAR," "PARC," "PE," and "PEN," they will be stored in the trie data structure as follows:
"P" constitutes the root node of this trie. In contrast, "PARC" and "PEN" constitute "leaf nodes." As the diagram illustrates, a leaf node has no offspring (i.e., no further suffixes). All of the remaining nodes ("PA," "PE," and "PAR") are internal nodes each one has both a parent and a child.
The distinction between leaf nodes and internal nodes takes on particular importance in the context of deletion heuristics. As discussed above, once the dynamic dictionary becomes full, it is necessary for the modem to delete existing entries to clear space for *512 new ones. In order for the dictionary to maintain the "all prefixes" property (i.e., if an entry is in the dictionary, so are all of its prefixes),[28] it is imperative that only leaf nodes are selected for deletion. If the modem were to delete an internal node such as "PAR," while leaving the leaf node "PARC" in the dictionary, the dictionary would lose its all prefixes property. Maintaining the all prefixes property is desirable because shorter strings are more likely to recur in the input stream than longer strings.
As a final background matter, the Court notes that once a leaf node is deleted, its parent internal node becomes a leaf node. In other words, if "PARC" is deleted, "PAR" is transformed into a leaf node because it no longer has any suffixes in the dictionary.
B. The Storer Patent
Claim 18 of the Storer Patent describes, inter alia, a novel deletion algorithm for deleting those dictionary entries which are "approximately least frequently matched."[29] Under the claimed deletion method, all entries in the dictionary that are longer than two characters in length (i.e., everything except the "root" nodes) are organized in a linear queue (i.e., a line), with strings entering on the right of the queue and exiting (going out to be deleted) on the left. See Storer Patent Col. 18, Lines 15-16.[30] In this respect, the Storer deletion method closely resembles the prior art "Least-Recently Used" (LRU) Algorithm. The Storer Patent discloses certain modifications to LRU, however, which guarantee that internal nodes never make it to the left of the queue for deletion. By ensuring that only leaf nodes are deleted, the Storer deletion algorithm, referred to in the patent specification as the "Modified Least Recently Used Queue Heuristic" ("MLRUH"), allows the dictionary to maintain the all prefixes property. Storer Patent, Col. 16, Lines 57-59.[31]
The precise modifications that the Storer Patent makes to LRU are extraordinarily complex, but the crux is that: 1) new dictionary entries enter on the right of the queue; 2) whenever an entry already in the dictionary is matched, that entry, along with all of its prefixes move toward the right of the queue (and thus further away from deletion); 3) whenever new entries enter the queue or move within the queue as required under (1) and (2), they are placed in a "reverse order arrangement" such that the prefixes for every string in the dictionary are positioned closer to the right of the queue (and thus farther away from deletion) than any suffixes of that string which happen to be in the dictionary.[32] By constantly reordering the *513 dictionary entries within the queue, the Storer apparatus ensures that only the least frequently used leaf nodes are deleted.
C. Claim Interpretation
Hayes contends that: 1) the phrase "reverse order arrangement" in Claim 18 must be construed to mean that, at every current match, the newly created dictionary entries must be placed in a reverse order arrangement, and 2) because V.42 bis modems never add more than one dictionary entry for any current match, there are no entries to place in reverse order, and thus, as matter of law, V.42 bis modems are not covered by Claim 18. See Hayes Reply Brief at 12.
Looking solely at the language of Claim 18, the meaning of the phrase "reverse order arrangement" is indeed ambiguous. In interpreting a patent claim, however, this Court must look not only to the language of the claim itself, but also the specification and patent history. See, e.g., Vitronics, 90 F.3d at 1582. The specification defines "reverse order arrangement" as "strings [that] are arranged so that the ancestors of any given descendant node are positioned closer to the front [right] of the queue than the given node." Storer Patent, Col. 17, Lines 25-27. The specification further indicates that this "reverse order arrangement" applies not only to new strings that are added to the dictionary, but also to those strings which are already in the dictionary and show up in the input data stream as the current match. See id. Col. 17, Lines 22-37.
As explained above, under the Storer deletion algorithm, whenever an entry already in the dictionary comes up as the current match, that entry, along with all of its prefixes must be moved toward the right of the queue. The Parcells Example illustrates that FC, like AP, will sometimes yield current matches longer than three characters; the third current match using the FC heuristic is "ARCE." If the modem were to apply the Storer deletion algorithm, "ARC" and "AR" would be moved toward the right of the queue (away from deletion) in the reverse order arrangement described in Claim 18 with "AR" being placed farthest to the right. Thus, Hayes' contention that the reverse order arrangement described in Claim 18 of the Storer Patent has no possible applicability to modems using the FC update heuristic is simply incorrect.
The Court further notes that, in construing a patent, each claim is considered an independent invention. Leeds & Catlin Co. v. Victor Talking Machine Co., 213 U.S. 301, 319, 29 S. Ct. 495, 501, 53 L. Ed. 805 (1909). Unlike all of the other independent claims in the Storer Patent, which speak of an update means for adding N new entries to the dictionary by concatenating the last current match with all of the non-empty prefixes of the current match (the AP heuristic), Claim 18 carefully recites the update means limitation in more general terms: "update means ... for concatenating the last matched string with the currently matched string." As AP and FC both concatenate the last matched string to the currently matched string in some fashion, a modem which uses either of these two update heuristics satisfies the update means element as to Claim 18.
D. Application of the Doctrine of Equivalents
It is undisputed that the V.42 bis standard does not use the exact deletion method claimed in the Storer Patent. According to the Defendants, V.42 bis uses a rotating pointer or clock system that operates as follows: 1) new dictionary entries are placed in the next available open space (which the clock points to); and 2) once the dictionary fills up, the clock just points to the next entry in sequence and deletes it, provided *514 that it is a leaf node. If it is an internal node, the pointer just skips on by. See Brief in Support of Hayes' Motion for Summary Judgment ("Hayes Brief") at 34; Zoom Brief at 14-15. The Defendants contend that because this rotating clock system does not require the modem to arrange (and constantly re-arrange) the dictionary entries in any particular order, it uses far less processing time for dictionary deletion than the Storer apparatus.
The Plaintiffs acknowledge that V.42 bis does not arrange its dictionary entries in a linear queue, but argue that V.42 bis uses an approximate least recently used deletion strategy which is substantially equivalent to the Storer deletion means. According to the Plaintiffs, 1) the rotating clock used by V.42 bis is commonly referred to as a circular queue data structure, and 2) persons of ordinary skill in the art regard the differences between a circular queue and a linear queue as insubstantial. Second Storer Decl. ¶ 11-12. Storer states that despite the Defendants' attempts to portray the cycling function of the pointer as some random strategy, in fact it operates just as systematically as the linear queue described in the Storer Patent. Id. In essence, the Plaintiffs argue, the differences between a circular and linear queue are no more substantial than the differences between physically standing in line (at a bus stop) or taking a numbered ticket and standing anywhere (at a deli or government agency). Plaintiffs' Brief at 14.
The Defendants respond that the Plaintiffs misunderstand how the rotating pointer deletion system operates. According to Alan Clark, Chief Technical Officer and Vice President of Hayes, new dictionary entries are added sequentially, but are not reordered when they come up as a current match; in other words, V.42 bis modems do not do anything equivalent to moving recently used entries to the right of the queue. Clark Rebuttal Aff. ¶ 8 at 14-17. It is true, Clark concedes, that like the Storer apparatus, V.42 bis will never delete internal nodes. But because V.42 bis does not do anything to reorder recently used entries, Clark asserts, it will delete leaf nodes without regard to how recently they have been used. Id. at 17. In other words, the Defendants contend that the Storer apparatus will always delete the least recently used leaf node, while V.42 bis will delete any leaf node selected by the pointer without regard to how recently it has been used.
The Plaintiffs' expert, however, asserts that V.42 bis does in fact move recently used entries backward in the deletion order, thus assuring that like the Storer apparatus, V.42 bis deletes only the least recently used leaf node. Thomborson Decl. ¶ 27. The text of the V.42 bis Recommendation does not resolve the issue. Section § 6.1(c) ambiguously provides for "the deletion of infrequently used strings in order that storage capacity may be reused." The Plaintiffs contend that the term "infrequently used" contradicts Clark's assertion that V.42 bis deletes leaf nodes without regard to how frequently they have been used. Thomborson Decl. ¶ 47. The Defendants counter that "infrequently used" means only that V.42 bis will not delete internal nodes because internal nodes tend to be more frequently used than their longer leaf counterparts, and does not suggest that V.42 bis will delete only the least frequently used leaf node. Clark Rebuttal Aff. ¶ 8 at 22; Miller Decl. ¶ 50. In light of this genuine dispute of material fact as to whether V.42 bis deletes leaf nodes without regard to how recently they have been used, the Court hereby DENIES the Defendants' motions for summary judgment as to Claim 18.
IV. CONCLUSION
For the foregoing reasons, the Defendants' motions for summary judgment of non-infringement are GRANTED as to Claims 1-17 and 19-55 of the Storer Patent, and DENIED as to Claim 18.
SO ORDERED.
NOTES
[1] The Storer Patent was awarded on October 24, 1989. The V.42 bis standard was approved by the International Telegraph and Telephone Consultative Committee (the permanent organ of the International Telecommunication Union) on January 31, 1990. The final draft of the V.42 bis standard, however, was completed in September of 1989 before the Storer Patent was awarded. Affidavit of Alan Clark ("Clark Aff.") at 15-16.
[2] See, e.g., Jacob Ziv & Abraham Lempel, Compression of Individual Sequences Via Variable-Rate Coding, in IEEE Transactions on Information Theory, Vol. IT-24, No. 5 (1978); James A. Storer, Textual Substitution Techniques for Data Compression, in NATO ASI Series, Vol. F12, Combinational Algorithms on Words, at 111 (A. Apostolico & Z. Galil eds., 1985); Victor S. Miller & Mark N. Wegman, Variations on a Theme by Ziv and Lempel, in NATO ASI Series, Vol. F12, Combinational Algorithms on Words, supra, at 131; United States Patent 4,558,302 (1985) (entitled "High Speed Data Compression and Decompression Apparatus and Method") (hereinafter the "Welch Patent"); United States Patent 4,814,716 (1989) (entitled "Data Compression Method") (hereinafter "Miller-Wegman Patent").
[3] The manner in which the dictionary is initialized is referred to as the "initialization method."
[4] The process the modem uses to determine what constitutes the current match is known as the "match method."
[5] An "update heuristic" may also be referred to as an "update algorithm," an "update method," or an "update means."
[6] Zoom suggests the following quarterback signal-calling analogy: At the line of scrimmage, the quarterback (the transmitting modem), does not call out detailed instructions, but rather a shorthand code known as an "audible." The wide receiver (the receiving modem) hears the audible and knows that it is shorthand for a longer instruction. If both the quarterback and wide receiver have memorized the same playbook (dictionary), the message gets across correctly in shorthand form. See Zoom's Memorandum in Support of its Motion for Summary Judgment ("Zoom Brief") at 8; Declaration of Dr. Gregory Wornell ("Wornell Decl.") ¶ 14.
This analogy, however, is only partially accurate. In football, the quarterback and wide receiver learn the audibles before the game (from a playbook) or during the game (by talking to each other or the coach). Under the dynamic dictionary method of data compression, the quarterback and wide receiver learn the audibles during the game, but without directly communicating with each other about what those audibles will be. Instead, the quarterback and wide receiver agree before the game on the method (known as an update heuristic) that they will use to learn the audibles, such that as the game progresses, they can begin to communicate in this shorthand form.
[7] A "deletion method" may also be referred to as a "deletion heuristic," a "deletion algorithm," or a "deletion means."
[8] Claims 1 and 55 describe the update heuristic in the context of a general discussion of the data compression system. Claim 19 recites the update heuristic in the context of dynamic compression by the transmitting modem (encoder), while Claim 35 recites the update heuristic in the context of dynamic decompression by the receiving modem (decoder).
[9] Independent claims 1, 19, 35, and 55 of the Storer Patent use nearly identical language to describe the update heuristic. Claim 1 provides, in relevant part:
first update means for adding N new strings of data characters to said first dictionary means for each current match, wherein N equals the number of characters in said current match, said N new strings comprising the last current match concatenated with each non-empty prefix of said current match.
[10] The Storer Patent specification uses the abbreviation PAPH, which stands for Pure All Prefixes Heuristic.
Furthermore, some of the dependent claims in the Storer Patent describe a more complex variation of this update heuristic entitled MAPH (Modified All Prefixes Heuristic), which limits the number of dictionary entries that can start with the same first letter. MAPH, however, is irrelevant for purposes of the present motions.
[11] In contrast, the Plaintiffs concede that NC is not equivalent to AP. Plaintiffs' Surreply Brief on Defendants' Motions for Summary Judgment of Non-Infringement ("Plaintiffs' Surreply Brief") at 3.
[12] In other words, if the incoming data stream is "THE" and both "TH" and "THE" are already in the dictionary, the current match would be "THE" rather than "TH." This match method, referred to by persons of ordinary skill in the art as "greedy parsing" or "greedy matching," was well-established in the prior art at the time of the Storer Patent and is used by both Storer and V.42 bis modems.
It is important to note that two modems can use the same match method and different update heuristics. The match method pertains to how the modem determines the current match; the update heuristic determines what (and how many) new strings are added to the dictionary with each current match.
[13] Remember, the AP heuristic adds the prior match to each of the sequential groupings of characters of the current match. So here, adding the prior match "P" to all of the prefixes of the current match "ARC" yields the entries "PA," "PAR," and "PARC." See supra pp. 503-504.
[14] For example, suppose a system using the NC heuristic encounters the data string "aWaWa," and the string "aW" is already in the dictionary. The transmitting modem will match aw, add awa as a new dictionary entry, and then on the very next step (before the receiving modem has had a chance to add awa to its dictionary), match awa. Storer Decl. ¶ 16. Although the receiving modem is able to deduce what has transpired, the complication of the decoding glitch is a disadvantage of NC as compared to AP and FC. Id.
[15] In other words, although Section 6.4 states that unprocessed input shall be used to form new dictionary entries, Section 6.3(b) provides that these new entries cannot be used until after the input has been processed.
[16] Specifically, at the motion hearing, the Plaintiffs' counsel presented an example on the blackboard indicating that V.42 bis would parse a string consisting of four consecutive a's as a/a/aa, as opposed to a/a/a/a. According to the Plaintiffs, this result is consistent with FC but not NC.
[17] Zoom does not raise this prior art argument.
[18] To determine whether a modem using an FC update heuristic falls outside the permissible range of equivalents, the proper inquiry is: Would Claims 1-17 and 19-55 of the Storer Patent have been patentable if they had literally included the prior art FC update heuristic instead of the novel AP algorithm? See Wilson, 904 F.2d at 684 (stating to simplify the analysis, "it may be helpful to conceptualize the [prior art] limitation on the scope of equivalents by visualizing a hypothetical patent claim, sufficient in scope to literally cover the accused product," and then determine whether this hypothetical claim would have been patentable over the prior art). In light of the analysis set forth below, it is unnecessary the Court to reach this complex issue.
[19] It is possible to create a special data input stream that would result in nothing but single character current matches (N = i), but any such data stream would necessarily be a short one, because it would not take long for every possible two character combination to be added to the dictionary; after that, two character matches would begin to occur. For most real world data streams, such as the example presented in the Storer Patent specification at Figure 8, it does not take long before two character matches begin to occur.
[20] Furthermore, a simple example demonstrates the patent absurdity of the Plaintiffs' argument. When a person wishes to shut off a television, she generally has two options. Option A is to simply press the off button on the remote control. Option B is to get up, walk across the room, go up to the television, and press the off button on the television set. Just as the single dictionary entry added by V.42 bis will always be added under the Storer apparatus, the single step performed in Option A (pressing the button) will also always be performed under Option B. Nevertheless, it is clear that Option A and Option B do not shut off the television in substantially the same way.
[21] Once again, the television example illustrates the flaws in the Plaintiffs' argument. Suppose the person who wishes to shut off the television is sitting on the floor right in front of the television. In that instance, whether she uses Option A (the remote control) or Option B (manually pressing the button on the TV), the procedure will be nearly identical (simply pressing a button). Despite the similarities between Option A and Option B in this limited circumstance, it remains clear that the two options operate in a substantially different way.
[22] As discussed in the Parcells Example, the Plaintiffs are correct that AP, FC, and CM all share the "processed components" property in that, unlike NC, they never rely on any uncompressed input to form new dictionary entries.
[23] For example, in the Parcells Example, at the second current match, AP adds "PA," "PAR," and "PARC," while FC adds only "PA." Thus, at that point in time, the Storer dictionary contains two more suffixes of "PA" than the V.42 bis dictionary.
To a certain extent, AP combines FC and CM by using the innovation of adding multiple dictionary entries. FC and CM both add only one entry for each current match. FC builds that entry by using only the first character of the current match; CM uses all of the characters of the current match. As a result, CM adds longer strings into its dictionary than FC, but fails to ensure that the shorter strings (which are most likely to recur) are added. For instance, in the Parcells Example, at the second current match, CM adds "PARC," but does not add "PA" or "PAR." Thus, AP represented an innovation over the prior art because it effectively combined the best attributes of FC and CM, adding both the shorter and the longer strings into the dictionary for every current match.
[24] Wornell uses the example given in Figure 8 of the Storer Patent ("THE CAT AT THE CAR ATE THE RAT") to illustrate that the dictionary grows more rapidly under AP even for a relatively short data input stream. Here, AP generated 28 new dictionary entries while the V.42 bis update means generated 20 new entries. Wornell Decl. ¶ 39.
It should be noted that Wornell's table is actually based on the assumption that V.42 bis uses the NC heuristic, an assumption which this Court must reject for purposes of these motions. Nevertheless, Wornell's analysis would have yielded essentially the same results had he assumed that FC applies. As illustrated by the Parcells Example, NC and FC generate the dictionary entries, except that NC generates the entries one step ahead of FC.
[25] For example, in the Parcells Example, for the second current match, AP adds "PA," "PAR," and "PARC" to the dictionary, while FC adds only "PA." The next time the modem encounters "PAR," under AP, the current match will be "PAR," and the shorthand code will be transmitted. Under FC, in contrast, the current match will be "PA," and the prior current match plus P will be added to the dictionary. "PA" then becomes the prior match, and when "R" is the current match, "PAR" will be added to the dictionary. The shorthand code for "PAR," however, will not be sent until the next time (i.e., the third time) that the V.42 bis modem encounters the stream "PAR."
[26] In fact, Hayes contends that, for this very reason, although the Storer apparatus yields more compression early on, once the Storer dictionary becomes full, V.42 bis actually achieves better compression ratios. Whether Hayes is correct is a disputed question of fact that cannot be resolved on this motion for summary judgment.
This Court further notes that the rate of compression is not the only relevant criterion for measuring which update heuristic yields "better" results from a practical standpoint. As a general matter, data compression saves time by reducing the amount of data that needs to be transmitted to convey the same information. But the law of diminishing marginal returns suggests that the modem should reach a point after which the cost (i.e., the time the modem spends adding and deleting entries to its dictionary) of achieving the extra character or two of compression outweighs the benefit. Unfortunately, it is uncertain where this point of diminishing marginal returns lies (particularly as it most likely varies with the content of the data input stream).
Despite this uncertainty as to which update means is more effective, in the view of this Court, there exists no genuine issue of material fact but that AP and FC take very different approaches to data compression.
[27] As further evidence that the differences between the claimed Storer apparatus and V.42 bis are substantial, Zoom asserts that because of differences in the way dictionary entries are added under the two systems, for most real-world data streams, a modem built in accordance with the specifications set forth in the Storer Patent would not be able successfully to transmit data to a V.42 bis modem, or vice versa. Zoom Brief at 16; Wornell Decl. ¶¶ 42-43. The Plaintiffs counter that the question of whether Storer modems can "talk" to V.42 bis modems is irrelevant for purposes of determining infringement under the doctrine of equivalents. After all, the Plaintiffs argue, when two different football teams employ audibles to call plays at the line of scrimmage, they use different specific code words (so that the players from the other team cannot intercept the message), but there is no doubt that the two teams are doing virtually the same thing (using a shorthand code to call plays).
The Plaintiffs are correct that as a general matter, the mere fact that the two modems cannot communicate does not prove anything about the substantiality of the differences concerning how they operate. For example, even if the Storer Patent and the V.42 bis modems used the same exact update heuristics, the modems could not successfully transmit data to each other if the two systems assigned different shorthand codes to the same dictionary entries (i.e., used different audibles). In this case, however, the proffered reason why the modems cannot talk to each other is not that they assign different shorthand codes to the same dictionary entries, but rather that they use entirely different methods to add entries to their dictionaries (i.e., they use a different technique to learn the plays, and in fact, learn a different number of plays). See supra note 6. Nevertheless, as the inability of the modems to communicate is relevant only to the extent that the Court knows why they cannot communicate, Zoom's argument adds nothing to the Court's analysis.
[28] Dictionaries which use the AP, FC, or NC update heuristics all share this "all prefixes" property. Under AP, however, if an entry is in the dictionary, it is more likely that some of its suffixes will also be in the dictionary than under FC or NC. See supra pp. 509-510.
[29] Claim 18 of the Storer Patent provides, in relevant part:
deletion means for deleting said plurality of strings of characters in said dictionary means in said encoder module and in said dictionary means in said decoder module those strings with which strings of characters from said input stream are approximately least frequently matched by arranging said plurality of strings in said dictionary means in said encoder and decoder modules in a reverse order arrangement with the currently matched strings appearing after said concatenation of the last matched string and the currently matched string.
[30] It is actually more common to refer to the ends of the queue as front and back. Indeed, the Storer Patent states that strings enter at the front of the queue and exit at the back. Storer Patent Col. 16, Lines 66 Col. 17, Line 4. Nevertheless, Storer and Plaintiffs' expert Thomborson use the opposite terminology in their submissions to this Court. See Thomborson Decl. ¶ 36; Storer Decl. ¶ 66. Thus, to avoid confusion, the Court refers to strings as entering on the right of the queue and exiting on the left.
[31] Some prior art structures that used the LRU method were also able to maintain the all prefixes property, but only by using reference counts to determine when a node becomes a leaf node, and therefore eligible to enter the queue for deletion. See Storer Decl. ¶ 66 (referring to the prior art Miller-Wegman Patent). The Storer Patent, in contrast, does not employ reference counts; internal nodes are permitted to enter the queue, but are reordered within the queue in a manner that ensures they are never deleted.
[32] For example, if "PARC," "PAR," and "PA" are in the dictionary, they will always be arranged in that order, with "PA" farthest to the right, and thus farthest from deletion. As new entries and current matches enter the queue on the right, "PARC," "PAR" and "PA" will shift toward the left of the queue. But, if "PAR" were to recur in the data stream, "PAR" and "PA" move back to the right of the queue. In contrast, if neither "PA," "PAR," or "PARC" recurs in the input stream, the three entries will keep moving to the left of the queue. As the leaf node "PARC" is farthest to the left, it would be the first of the group to be deleted. With "PARC" no longer in the dictionary, "PAR" would then constitute a leaf node, and become the next candidate for deletion. By constantly reorganizing the entries within the queue, the Storer apparatus deletes only the least recently used leaf nodes.
For a more detailed example, see Figure 9 in the Storer Patent and the accompanying explanation in the specification at Cols. 16-19.