`
`3
`
`1 David C. Marcus (SBN 158704)
`david.marcus@wilmerhale.com
`James M. Dowd (SBN 259578)
`james.dowd@wilmerhale.com
`Matthew J. Hawkinson (SBN 248216)
`4 matthew.hawkinson@wilmerhale.com
`Aaron Thompson (SBN 272391)
`5 aaron.thompson@wilmerhale.com
`WILMER CUTLER PICKERING
`6 HALE AND DORR LLP
`350 South Grand Avenue, Suite 2100
`Los Angeles, CA 90071
`8 Telephone: (213) 443-5300
`Facsimile:
`(213) 443-5400
`
`7
`
`9
`
`11
`
`William F. Lee (pro hac vice)
`10 william.lee@wilmerhale.com
`WILMER CUTLER PICKERING
`HALE AND DORR LLP
`12 60 State Street
`Boston, MA 02109
`13 Telephone: (61 7) 526-6000
`Facsimile:
`(617) 526-5000
`
`14
`
`15
`
`Attorneys for Defendants and Counterclaim-Plain tiffs
`Hughes Communications Inc.
`16 Hughes Network Systems LLC
`DISH Network Corporation,
`17 DISH Network LLC, and
`dishNET Satellite Broadband LLC
`
`18
`
`Additional Counsel Listed on Signature Page
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`B.FREY
`EXHIBIT
`2
`3/10/2015
`JAN IS JENNINGS
`CSR. CLR. CCRR
`
`Expert Report of Dr. Brendan Frey
`Case No. 2: l 3-cv-07245 -MRP-JEM
`
`Hughes, Exh. 1068, p. 1
`
`
`
`2
`
`3
`
`UNITED STATES DISTRICT COURT
`CENTRAL DISTRICT OF CALIFORNIA
`
`Case No. 2:13-cv-07245 -MRP-JEM
`
`EXPERT REPORT OF DR.
`BRENDAN FREY REGARDING
`INVALIDITY OF PATENTS-IN(cid:173)
`SUIT
`
`THE CALIFORNIA INSTITUTE OF
`4 TECHNOLOGY,
`
`5
`
`6
`
`7
`
`Plaintiff and Counter-Defendant,
`
`vs .
`
`HUGHES COMMUNICATIONS INC.,
`8 HUGHES NETWORK SYSTEMS LLC,
`9 DISH NETWORK CORPORATION,
`DISH NETWORK LLC, and DISHNET
`1 O SATELLITE BROADBAND LLC,
`
`Defendants and Counter-Plaintiffs.
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`-2-
`
`Expert Report of Dr. Brendan Frey
`Case No. 2: l 3-cv-07245-MRP-JEM
`
`Hughes, Exh. 1068, p. 2
`
`
`
`1
`
`2
`
`3
`
`4
`
`I.
`
`1.
`
`EXPERT REPORT OF DR. BRENDAN FREY
`REGARDING INVALIDITY OF PATENTS-IN-SUIT
`
`SUMMARY OF REPORT
`
`I have been retained as an expert in this case by counsel for Defendants and
`
`5 Counter-Plaintiffs Hughes Communications Inc., Hughes Network Systems LLC,
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`21
`
`22
`
`23
`
`24
`
`19
`20 4 ·
`preceding paragraph (the "asserted claims") are valid. In my opinion, all of the
`
`DISH Network Corporation, DISH Network LLC, and dishNET Satellite
`
`Broadband LLC (collectively, "Defendants"). I expect to testify at trial about the
`
`matters set forth in this report, if asked about these matters by the Court or by the
`
`parties' attorneys.
`
`I understand that the Plaintiff and Counter-Defendant in this proceeding, the
`
`2.
`California Institute of Technology ("Plaintiff' or "Caltech") has asserted against
`
`Defendants the fo llowing four patents:
`
`• U.S . Patent No. 7,116,710 (the "' 710 patent");
`
`• U.S. Patent No. 7,421 ,032 (the '"032 patent");
`
`• U.S . Patent No. 7,916,781 (the '"781 patent"); and
`
`• U.S. Patent No. 8,284,833 (the '"833 patent").
`I further understand that Plaintiff has asserted the following claims:
`
`3.
`
`• claims 1, 4, 6, 15, 20, and 22 of the '710 patent;
`
`• claims 1, 18, 19, and 22 of the '032 patent;
`
`• claims 16 and 19 of the '781 patent; and
`• claims 1, 2, 4, and 8 of the '833 patent.
`I have been asked for my expert opinion on whether the claims listed in the
`
`asserted claims are invalid for the reasons stated below.
`
`5.
`
`I have also been asked for my opinion on whether various documents,
`
`including an email from an inventor dated March 7, 2000, demonstrate conception
`
`-1-
`
`Expert Report of Dr. Brendan Frey
`Case No. 2: I 3-cv-07245-MRP-JEM
`
`Hughes, Exh. 1068, p. 3
`
`
`
`of the claimed invention. In my opinion, these documents do not demonstrate
`
`2
`
`conception for the reasons stated below.
`
`3 6.
`
`I have also been asked for my opinion regarding whether three references
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`(two by Luby et al. and one by Richardson et al.) were material to the claimed
`
`invention. In my opinion, as explained below, these three references, none of
`
`which were before the patent office during prosecution of the asserted patents,
`
`were material to the claimed invention.
`
`BACKGROUND
`
`A. Qualifications and Experience
`
`7.
`
`I received a B.Sc. with Honors in Electrical Engineering from the University
`
`of Calgary in 1990, a M.Sc. in Electrical and Computer Engineering from the
`
`University of Manitoba in 1993, and a Ph.D. in Electrical and Computer
`
`Engineering from the University of Toronto in 1997. Since July 2001, I have been
`
`at the University of Toronto, where I am a Professor of Electrical and Computer
`
`Engineering and Computer Science.
`
`8.
`
`During my career I have conducted research in the areas of graphical models
`
`error-correcting coding, machine learning, genome biology and computer vision. I
`
`have authored more than 200 publications and am named as an inventor on nine
`
`patents issued by the U.S. Patent and Trademark Office.
`
`9.
`
`I have received a number of honors and awards for the research I have
`
`conducted. In 2008, I was named a Fellow of the Institute for Electrical and
`
`Electronic Engineers (IEEE), an honor given to a person with an "extraordinary
`
`record or accomplishments" in the field of electrical engineering. In 2009, I was
`
`named a Fellow of the American Association for the Advancement of Science
`
`(AAAS), an honor that recognizes "efforts on behalf of the advancement of science
`
`or its applications which are scientifically or socially distinguished."
`
`-2-
`
`Expert Report of Dr. Brendan Frey
`Case No. 2: l 3-cv-07245-MRP-JEM
`
`Hughes, Exh. 1068, p. 4
`
`
`
`1 10.
`
`In 2009, I was awarded a Steacie Fellowship for my work on the theory and
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`implementation of artificial and natural mechanisms for inferring patterns from
`
`data. The Steacie Fellowship is awarded by the Natural Sciences and Engineering
`
`Research Council of Canada (NSERC) to "outstanding and highly promising
`
`scientists and engineers" who are facu lty members of Canadian universities. In
`
`2011 , I received the NSERC's John C. Polanyi Award, in recognition of my
`
`research on inferring genetic codes embedded in DNA that direct activities within
`
`cells.
`
`8 11.
`
`Throughout my career I have received funding from various governmental
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`agencies to support my research, including the Natural Sciences and Engineering
`
`Research Council of Canada, the Canadian Institutes of Health Research, and the
`
`Canadian Institute for Advanced Research.
`
`12. A copy of my curriculum vi tee is attached to this report as Exhibit A.
`
`B. Understanding of the Law
`
`13.
`
`I am not an attorney. For the purposes of this report, I have been informed
`
`about certain aspects of the law that are relevant to my analysis and opinions. My
`
`understanding of the law is as follows:
`
`i)
`
`Invalidity in General
`
`14. A patent is presumed valid, and a challenger to the validity of a patent must
`
`show invalidity of the patent by clear and convincing evidence. Clear and
`
`convincing evidence is evidence that makes a fact highly probable.
`
`ii)
`
`Anticipation
`
`15. A patent claim is invalid if it is "anticipated" by prior art. For the claim to
`
`be invalid because it is anticipated, all of its requirements must have existed in a
`
`single device or method that predates the claimed invention, or must have been
`
`described in a single publication or patent that predates the claimed invention.
`-3-
`
`Expert Report of Dr. Brendan Frey
`Case No. 2: l 3-cv-07245-MRP-JEM
`
`Hughes, Exh. 1068, p. 5
`
`
`
`1 16. The description in a written reference does not have to be in the same words
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`as the claim, but all of the requirements of the claim must be there, either stated or
`
`necessarily implied, so that someone of ordinary skill in the art, looking at that one
`
`reference would be able to make and use the claimed invention.
`
`17. A patent claim is also anticipated if there is clear and convincing proof that,
`
`more than one year before the filing date of the patent, the claimed invention was:
`
`in public use or on sale in the United States; patented anywhere in the world; or
`
`described in a printed publication anywhere in the world. This is called a statutory
`
`bar.
`
`iii) Obviousness
`
`10 18. A patent claim is invalid if the claimed invention would have been obvious
`
`11
`
`to a person of ordinary skill in the art at the time the application was filed. This
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`means that even if all of the requirements of a claim cannot be found in a single
`
`prior art reference that would anticipate the claim or constitute a statutory bar to
`
`that claim, the claim is invalid if it would have been obvious to a person of
`
`ordinary skill who knew about the prior art.
`
`19. The determination of whether a claim is obvious should be based upon
`
`several factors, including:
`
`•
`
`the level of ordinary skill in the art that someone would have had at the time
`the claimed invention was made;
`
`•
`
`the scope and content of the prior art;
`• what difference, if any, existed between the claimed invention and the prior
`art.
`In considering the question of obviousness, it is also appropriate to consider
`
`20.
`
`any secondary considerations of obviousness or non-obviousness that may be
`
`shown. These include:
`
`• commercial success of a product due to the merits of the claimed invention;
`-4-
`
`Expert Rep01i of Dr. Brendan Frey
`Case No. 2: l 3-cv-07245-MRP-J EM
`
`Hughes, Exh. 1068, p. 6
`
`
`
`• a long felt need for the solution provided by the claimed invention;
`
`• unsuccessful attempts by others to find the solution provided by the claimed
`invention;
`
`• copying of the claimed invention by others;
`
`• unexpected and superior results from the claimed invention;
`
`• acceptance by others of the claimed invention as shown by praise from
`others in the field or from the licensing of the claimed invention; and
`
`•
`
`independent invention of the claimed invention by others before or at about
`the same time as the named inventor thought of it.
`
`21.
`
`A patent claim composed of several elements is not proved obvious merely
`
`by demonstrating that each of its elements was independently known in the prior
`
`art. In evaluating whether such a claim would have been obvious, it is relevant to
`
`consider if there would have been a reason that would have prompted a person of
`
`ordinary skill in the field to combine the elements or concepts from the prior art in
`
`the same way as in the claimed invention. For example, market forces or other
`
`design incentives may be what produced a change, rather than true inventiveness .
`
`It is also appropriate to consider:
`
`• whether the change was merely the predictable result of using prior art
`elements according to their known functions, or whether it was the result of
`true inventiveness;
`
`• whether there is some teaching or suggestion in the prior art to make the
`modification or combination of elements claimed in the patent;
`
`• whether the innovation applies a known technique that had been used to
`improve a similar device or method in a similar way; or
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`• whether the claimed invention would have been obvious to try, meaning that
`the claimed innovation was one of a relatively small number of possible
`approaches to the problem with a reasonable expectation of success by those
`of ordinary skill in the art.
`In considering obviousness, it is important to be careful not to determine
`
`22 22.
`
`obviousness using the benefit of hindsight; many true inventions might seem
`
`obvious after the fact.
`
`23
`
`24
`
`-5-
`
`Expert Report of Dr. Brendan Frey
`Case No. 2: l 3-cv-07245-MRP-JEM
`
`Hughes, Exh. 1068, p. 7
`
`
`
`1 23. A single reference can alone render a patent claim obvious, if any
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`differences between that reference and the claims would have been obvious to a
`
`person of ordinary skill in the art at the time of the alleged invention - that is, if the
`
`person of ordinary skill could readily adapt the reference to meet the claims of the
`
`patent, by applying known concepts to achieve expected results in the adaptation of
`
`the reference.
`
`iv)
`
`The "Written Description" Requirement
`
`24. A patent claim is invalid if the patent specification does not contain a written
`
`description of the invention to which the claim is directed. To satisfy the written
`
`description requirement, a patent specification must describe the claimed invention
`
`in sufficient detail that one of ordinary skill in the art can reasonably conclude that
`
`the inventor had possession of the claimed invention.
`
`12 25. An applicant shows possession of the claimed invention by describing the
`
`claimed invention with all of its limitations using such descriptive means as words,
`
`structures, figures, diagrams, and formulas that fully set forth the claimed
`
`invention. A description that merely renders the invention obvious does not satisfy
`
`the written description requirement.
`
`v)
`
`Inequitable Conduct and Materiality
`
`26.
`
`I have been informed that during prosecution, inventors have a duty to
`
`disclose to the Patent Office all information known to the inventors that is material
`
`to the patentability of the claims being examined.
`
`27.
`
`Information is deemed to be material to patentability when it is not
`
`cumulative to information already before the Patent Office, and when: (1) it
`
`establishes, by itself or in combination with other information, that a claim was
`
`unpatentable; or (2) it refutes, or is inconsistent with, a position the applicant takes
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`-6-
`
`Expert Report of Dr. Brendan Frey
`Case No. 2: l 3-cv-07245-MRP-JEM
`
`Hughes, Exh. 1068, p. 8
`
`
`
`1
`
`in (a) opposing an argument ofunpatentability relied on by the Patent Office, or (b)
`
`2 asserting an argument of patentability.
`
`3
`
`C. Materials Reviewed
`
`4 28. Among the materials I have reviewed in forming my opinions are:
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`• The '710, '032, '781 , and ' 833 patents;
`
`• The prosecution histories of the ' 710, '032, '781, and '833 patents;
`
`• The prior art of record that was available to the patent examiner;
`
`• The prior art references discussed herein;
`
`• Claim Construction Order dated August 6, 2014 (Dkt. No. 105);
`
`• Declaration of Stephen B. Wicker, dated Oct. 6, 2014 (Dkt. No. 130-10);
`
`• Transcript of the October 14, 2014 deposition of Stephen B . Wicker;
`
`•
`
`•
`
`•
`
`•
`
`•
`
`•
`
`IPR Petition No. IPR2015 -00067 and accompanying exhibits, including the
`declaration of Henry D. Pfister;
`
`IPR Petition No. IPR2015-00068 and accompanying exhibits, including the
`declaration of Henry D. Pfister;
`
`IPR Petition No. IPR2015-00060 and accompanying exhibits, including the
`declaration of Henry D. Pfister;
`
`IPR Petition No. IPR2015 -00059 and accompanying exhibits, including the
`declaration of Henry D. Pfister;
`IPR Petition No. IPR2015 -00061 and accompanying exhibits, including the
`declaration of Henry D. Pfister;
`IPR Petition No. IPR2015 -00081 and accompanying exhibits, including the
`declaration of Henry D . Pfister;
`
`• Transcript of the December 11 , 2014 deposition of inventor Aamod
`Khandekar;
`• Transcript of the January 7, 2015 deposition of inventor Hui Jin;
`
`• Transcript of the Jan 15, 2015 deposition of Dariush Divsalar;
`
`• Laboratory Notebook of Robert McEliece (CALTECH000004472-603);
`
`• Caltech's Supplemental Responses to Defendants' First Set of
`Interrogatories, Nos. 3-5, Jan. 11, 2015 ;
`
`-7-
`
`Expert Report of Dr. Brendan Frey
`Case No. 2: l 3-cv-07245-MRP-JEM
`
`Hughes, Exh. 1068, p. 9
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`• Caltech's Second Supplemental Responses to Interrogatories 1-5 and
`Caltech' s First Supplemental Responses to Interrogatories 6-11;
`
`• Email from Brendan Frey to Dariush Divsalar dated Dec. 8, 1999
`(CAL TECH00002402 l );
`
`• Khandekar, Aamod ("Capacity Achieving Codes on the Binary Erasure
`Channel") (CALTECH00000732 l-7349).
`
`• Khandekar, Aamod, "Graph-based Codes and Iterative Decoding," thesis
`dated June 10, 2002.
`
`• McEliece Email dated March 7, 2000 (CALTECH000008667)
`
`• Luby, M. et al., "Practical Loss-Resilient Codes," STOC '97 (1997)
`
`• Luby, M. et al., "Analysis of Low Density Codes and Improved Designs
`Using Irregular Graphs," STOC '98, p. 249-259 (1998)
`
`10
`
`• Richardson, T. et al. "Design of provably good low-density parity check
`codes," IEEE Transactions on Jriformation Theory (1999) (preprint)
`
`11
`
`29.
`
`Level of Ordinary Skill in the Art
`
`12 30.
`
`In my opinion, based on the materials and information I have reviewed, and
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`on my extensive experience working with people in the technical areas relevant to
`
`the patents-in-suit (i.e. in the field of code design), a person of ordinary skill in the
`
`art is a person with a Ph.D. in electrical or computer engineering with emphasis in
`
`signal processing, communications, or coding, or a master's degree in the above
`
`area with at least three years of work experience this field at the time of the alleged
`invention. 1 I understand that Caltech has agreed with this definition of the level of
`ordinary skill in this case. 23
`
`1 I was asked to use a similar qualification for a "person of ordinary skill in the art" for purposes
`of a declaration that I understand was filed in connection with petitions for Inter Partes Review
`of the asserted patents. See Declaration of Brendan Frey dated October 14, 2014, at ~2.
`2 Reporter's Transcript of Claim Construction and Motion Hearing of July 9, 2014, Ex. 1026, at
`98.
`3 This is also consistent with testimony given by, e.g., Dr. Dariush Divsalar, an author of one of
`the prior art references discussed in this report (see Divsalar Dep. at 55-56).
`-8-
`
`Expett Report of Dr. Brendan Frey
`Case No. 2: 13-cv-07245-MRP-JEM
`
`Hughes, Exh. 1068, p. 10
`
`
`
`1
`
`D. Claim Constructions Used in This Report
`
`2 31.
`
`I understand that the parties have agreed on the following claim
`
`3
`
`constructions:
`
`Claim Term
`"irregularly"
`('710 and '032 patents)
`"interleaving" I "interleaver" I
`"scramble"
`(' 710 patent)
`
`"sums of bits in subsets of the
`information bits" I "summing of bits
`in a subset of the information bits" I
`"adding additional subsets of
`information bits"
`('781 patent)
`
`"wherein two or more memory
`locations of the first set of memory
`locations are read by the permutation
`module different times from one
`another"
`('833 patent)
`
`Agreed-Upon Construction
`
`"a different number of times"
`
`"changing the order of data elements" I
`"module that changes the order of data
`elements"
`
`"the result(s) of adding together two or
`more information bits from a subset of
`information bits" I "adding together two or
`more information bits from a subset of
`information bits"
`
`"where two or more memory locations of
`the first set of memory locations are read
`by the permutation module a different
`number of times from one another"
`
`"permutation module"
`('833 patent)
`
`"a module that changes the order of data
`elements"
`
`32.
`
`I further understand that the Court in this case has issued a claim
`
`construction order construing certain disputed claim terms as follows:
`
`Claim Term
`"transmitting" I "transmission"
`('032 patent)
`
`Court' Construction
`"sending over a channel"
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`-9-
`
`Expert Report of Dr. Brendan Frey
`Case No. 2: 13-cv-07245-MRP-J EM
`
`Hughes, Exh. 1068, p. 11
`
`
`
`"codeword"
`('781 patent)
`
`"repeat"
`('710 and '032 patents)
`"combine" I "combining"
`('833 patent)
`
`Equation in claim 1 of the '032 patent
`('032 patent)
`
`Tanner Graph term in claims 11 and
`18 of '032 patent
`('032 patent)
`
`"a discrete encoded sequence of data
`elements"
`plain meaning4
`
`"perform logical operations on"
`
`"the parity bit Xj is the sum of (a) the parity
`bit Xj-J and (b) the sum of a number, 'a,' of
`randomly chosen irregular repeats of the
`message bits"
`
`"a graph representing an IRA code as a set
`of parity checks where every message bit is
`repeated, at least two different subsets of
`message bits are repeated a different
`number of times, and check nodes,
`randomly connected to the repeated
`message bits, enforce constraints that
`determine the parity bits"
`
`33.
`
`For the purposes of this report, I have used the constructions given in the
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`two tables above. For all other claim terms, I have used the plain and ordinary
`
`15 meaning the term would have to one of ordinary skill in the art.
`
`16
`
`II. OVERVIEW OF THE TECHNOLOGY
`
`17 34.
`
`The four patents-in-suit, which share a common specification, relate to the
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`field of error-correcting codes. Below I provide a brief introduction to channel
`
`coding and error-correcting codes, and highlight a few of the developments in the
`
`field that are relevant to the asserted patents. Also, attached as Appendix A is a
`
`mathematical description of some properties of error-correcting codes.
`
`4 The Claim Construction Order dated August 6, 2014 expounded on the plain meaning of
`"repeat." For example, the order said the "plain meaning of 'repeat' requires the creation of new
`bits corresponding to or reflecting the value of the original bits. In other words, repeating a bit
`with the value 0 will produce another bit with the value 0. The Court will refer to this concept as
`duplication" (Claim Construction Order dated August 6, 2014, p. I 0).
`-10-
`
`Expert Report of Dr. Brendan Frey
`Case No. 2: 13-cv-07245-MRP-JEM
`
`Hughes, Exh. 1068, p. 12
`
`
`
`
`
`
`
`1
`
`the decoder converts instances of " 111 " into " l " and instances of "000" into "O" to
`
`2 produce the decoded bits "l 0 l ," which match the original information bits.
`
`3 43 .
`
`Suppose a bit is flipped during transmission, changing "000" to "010." The
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`decoder will be able to detect that there was a transmission error, because "010" is
`
`not a valid "repeat-three" codeword. Using a "majority vote" rule, the decoder can
`
`infer that the original information bit was a 0, correcting the transmission error.
`
`Thus, due to the redundancy incorporated into the codeword, no information was
`
`lost due to the transmission error.
`
`44. Error-correcting codes may be either systematic or non-systematic. In a
`
`systematic code, both the parity bits and the original information bits are included
`
`in the codeword. In a non-systematic code, the encoded data only includes the
`
`parity bits.
`
`45 .
`
`Systematic and non-systematic codes had been known in the art for decades
`
`prior to May 18, 2000, the claimed priority date of the patents-in-suit (see, e.g.,
`
`Wicker Dep . at 77 : 15-20; see also, e.g., Divsalar Dep. at pp. 66-67).
`
`B. Coding Rate
`
`46. Many error-correcting codes encode information bits in groups, or blocks of
`
`fixed length n. An encoder receives an k-bit block of information bits as input, and
`
`produces a corresponding n-bit codeword. The ratio ki n is called the rate of the
`
`code. Because the codeword generally includes redundant information, n is
`
`generally greater than k, and the rate kin of an error-correcting code is generally
`
`20
`
`less than one.
`
`21
`
`C. Performance of Error-Correcting Codes
`
`22 4 7.
`
`The effectiveness of an error-correcting code may be measured using a
`
`23 variety of metrics.
`
`24
`
`-13-
`
`Expert Report of Dr. Brendan Frey
`Case No. 2: l 3-cv-07245-MRP-JEM
`
`Hughes, Exh. 1068, p. 15
`
`
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`48. One tool used to assess the performance of a code is its bit-error rate (BER).
`
`The BER is defined as the number of corrupted information bits divided by the
`
`total number of information bits during a particular time interval. For example, if a
`
`decoder outputs 1000 bits in a given time period, and 10 of those bits are corrupted
`
`(i.e., they differ from the information bits originally received by the encoder), then
`
`the BER of the code during that time period is (10 bit errors) I (1000 total bits) =
`0.01or1 %.5
`
`49.
`
`The BER of a coded transmission depends on the amount of noise that is
`
`present in the communication channel, the strength of the transmitted signal (i.e.,
`
`the power that is used to transmit the modulated waveform), and the performance
`
`of the error-correcting code. An increase in noise tends to increase the error rate
`
`and an increase in signal strength tends to decrease the error rate. The ratio of the
`
`signal strength to the noise, called the "signal-to-noise ratio," is often used to
`
`characterize the channel over which the encoded signal is transmitted. The signal(cid:173)
`
`to-noise ratio can be expressed mathematically as Eb/N0, in which Eb is the amount
`of energy used to transmit each bit of the signal, and N0 is the density of the noise
`on the channel. 6 The BER of an error-correcting code is often measured for
`
`multiple values of Eb/N 0 to determine how the code performs under various
`
`channel conditions.
`
`50.
`
`Error-correcting codes may also be assessed based on their computational
`
`complexity. The complexity of a code is a rough estimate of how many
`
`calculations are required for the encoder to generate the encoded parity bits and
`
`how many calculations are required for the decoder to reconstruct the information
`
`5 Note that as used herein, BER refers to the information BER, which measures the percentage of
`bits that remain incorrect after decoding. This is not to be confused with the transmission BER,
`which measures the percentage of bits that are incorrect when they are received by the decoder.
`6 More precisely, Eb/N0 is the normalized signal-to-noise ratio. It is a dimensionless quantity that
`does not depend on the particular units used to measure the strength of the signal and the
`quantity of noise on the channel.
`
`-14-
`
`Expert Report of Dr. Brendan Frey
`Case No. 2: l 3-cv-07245-MRP-JEM
`
`Hughes, Exh. 1068, p. 16
`
`
`
`1 bits from the parity bits. If a code is too complex, it may be impractical to build
`
`encoders/decoders that are fast enough to use it.
`
`D. LDPC Codes, Convolutional Codes, Turbocodes, and Repeat-
`Accumulate codes
`
`51.
`
`In 1963, Robert Gallager described a set of error correcting codes called
`
`Low Density Parity Check ("LDPC") codes. Gallager described how LDPC codes
`
`provide one method of generating parity bits from information bits using a matrix
`
`populated with mostly Os and relatively few 1 s, and he described how decoding
`
`could be performed using an iterative "message passing" decoding algorithm, as
`described below. 7
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`11
`
`9
`1 o 52. Gallager' s work was largely ignored over the following decades, as
`researchers continued to discover other algorithms for calculating parity bits. These
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`algorithms included, for example, convolutional encoding (see below) with Viterbi
`
`decoding and cyclic code encoding with bounded distance decoding. In many
`
`cases these new codes could be decoded using low-complexity decoding
`
`algorithms.
`
`53.
`
`In 1993, researchers discovered "turbocodes,'' a class of error-correcting
`
`codes capable of transmitting information at a rate close to the Shannon Limit - the
`
`maximum rate at which information can be transmitted over a channel.
`
`Turbocodes make use of "convolutional codes'', which were described in the
`
`1960's and were widely used in telephone modems in the 1980's and 1990's. A
`
`convolutional code is a type of error-correcting code that generates parity bits by
`
`processing the information bits in order. The convolutional code contains a
`
`"memory bank" in the form of a short sequence of bits, e.g., 4 bits. When an
`
`information bit dk is processed, the memory bits si, s2, s 3, s4 are combined with the
`
`information bit to produce a new memory bit and the remaining memory bits are
`
`7 Gallager, R., Low-Density Parity-Check Codes (Monograph, M.I.T. Press, 1963).
`-15 -
`
`Expert Report of Dr. Brendan Frey
`Case No. 2: I 3-cv-07245-MRP-JEM
`
`Hughes, Exh. 1068, p. 17
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`"shifted", so that the last memory bit is discarded. For example, the new memory
`
`bit St , could be computed by s 1' = dk + s 1 + s 2 + s 3 + s 4 modulo 2, and the other
`
`memory bits would be s 2' = s 1, s 3' = s 2, and s4 ' = s 3. What does "modulo 2" mean?
`If the sum of the bits is even, then the sum modulo 2 is zero, whereas if the sum of
`
`the bits is odd, then the sum modulo 2 is one. Note that s 4 has been discarded.
`
`When an information bit is being processed, a parity bit is also generated. The
`
`parity bit Yk is a combination of the new memory bit and the entire set of current
`memory bits, for example, Yk = s 1' + s 4 modulo 2. The combinations used to
`determine the new memory bit and the parity bit need not include all of the bits,
`
`e.g., the above example uses all bits to compute the new memory bit, but only s 1'
`and s4 when computing the parity bit. If a particular bit is used in a combination,
`
`we say there is a "tap" connected to that bit. In the example, the parity bit is
`
`connected by a tap to St' and another tap to s 4. The set of taps for the memory bit
`
`and the set of taps for the parity bit are fixed when processing information bits and
`
`they completely characterize the convolutional code. In a "systematic"
`
`convolutional code, the information bits are also transmitted across the channel, in
`
`addition to the parity bits. Some parity bits and/or some information bits may be
`
`punctured so as to adjust the rate of the convolutional code (the number of
`
`information bits processed divided by the number of bits transmitted). If the new
`
`memory bit doesn't have any taps to any memory bits, the code is called "non(cid:173)
`
`recursive" and otherwise it is called "recursive", alluding to the fact that the new
`
`memory bit depends on the bits in the old memory. Using the above example, the
`
`figure below shows how a recursive convolutional code is depicted, where a circle
`
`with a plus inside indicates summation modulo 2 and a box with a T inside
`indicates a memory location (figure modified from 8
`
`).
`
`8 Claude Berrou et al., Near Shannon Limit Error-Correcting Coding and Decoding: Turbo
`Codes , 2 IEEE International Conference on Communications, ICC '93 Geneva. Technical
`-16-
`
`Expert Report of Dr. Brendan Frey
`Case No. 2: l 3-cv-07245-MRP-JEM
`
`Hughes, Exh. 1068, p. 18
`
`
`
`
`
`
`
`In 1995 and 1996, researchers began to explore "concatenated"
`1 58.
`convolutional codes. 11 While turbocodes use two convolutional coders connected
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`in parallel, concatenated convolutional codes use two convolutional coders
`
`connected in series: the information bits are encoded by a first encoder, the output
`
`of the first encoder is interleaved, and the interleaved sequence is encoded by a
`
`second convolutional code. In such codes, the first and second encoders are often
`
`called the "outer coder" and the "inner coder," respectively.
`
`59.
`In 1998, researchers developed "repeat-accumulate," or "RA codes" by
`simplifying the principles underlying turbocodes . 12 In RA codes, the information
`
`bits are first passed to a repeater that repeats (i.e., duplicates) the information bits
`
`and outputs a stream ofrepeated bits (the encoder described above in the context of
`
`the "repeat three" coding scheme is one example of a repeater). The repeated bits
`
`are then passed through an interleaver, which scrambles their order, and then to an
`
`accumulator, where they are "accumulated" to form the parity bits, which are
`
`transmitted across the channel.
`
`60.
`
`The accumulation operation is a running sum process whereby each input bit
`
`is added to the previous input bits to produce a sequence of running sums, each of
`
`which represents the sum of all input bits yet received. More formally, if an
`
`accumulator receives a sequence of input bits i 1, i 2, i3, . . . in. it will produce output
`bits oi, 02, o3, . .. oY/J such that: 13
`
`11 Benedetto, S. et al., S