`david.marcus@wilmerhale.com
`James M. Dowd (SBN 259578)
`james.dowd@wilmerhale.com
`Matthew J. Hawkinson (SBN 248216)
`matthew.hawkinson@wilmerhale.com
`Aaron Thompson (SBN 272391)
`aaron.thompson@wilmerhale.com
`WILMER CUTLER PICKERING
`HALE AND DORR LLP
`350 South Grand Avenue, Suite 2100
`Los Angeles, CA 90071
`Telephone: (213) 443-5300
`Facsimile:
`(213) 443-5400
`
`William F. Lee (pro hac vice)
`william.lee@wilmerhale.com
`WILMER CUTLER PICKERING
`HALE AND DORR LLP
`60 State Street
`Boston, MA 02109
`Telephone: (617) 526-6000
`Facsimile:
`(617) 526-5000
`
`Attorneys for Defendants and Counterclaim-Plaintiffs
`Hughes Communications Inc.
`Hughes Network Systems LLC
`DISH Network Corporation,
`DISH Network LLC, and
`dishNET Satellite Broadband LLC
`
`Additional Counsel Listed on Signature Page
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`Apple 1017
`
`Expert Report of Dr. Brendan Frey
`Case No. 2:13-cv-07245-MRP-JEM
`
`1
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`UNITED STATES DISTRICT COURT
`CENTRAL DISTRICT OF CALIFORNIA
`
`THE CALIFORNIA INSTITUTE OF
`TECHNOLOGY,
`
`Plaintiff and Counter-Defendant,
`
`vs.
`
` Case No. 2:13-cv-07245-MRP-JEM
`
`EXPERT REPORT OF DR.
`BRENDAN FREY REGARDING
`INVALIDITY OF PATENTS-IN-
`SUIT
`
`HUGHES COMMUNICATIONS INC.,
`HUGHES NETWORK SYSTEMS LLC,
`DISH NETWORK CORPORATION,
`DISH NETWORK LLC, and DISHNET
`SATELLITE BROADBAND LLC,
`
`
`
`Defendants and Counter-Plaintiffs.
`
`-2-
`
`Expert Report of Dr. Brendan Frey
`Case No. 2:13-cv-07245-MRP-JEM
`
`2
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`EXPERT REPORT OF DR. BRENDAN FREY
`REGARDING INVALIDITY OF PATENTS-IN-SUIT
`
`SUMMARY OF REPORT
`
`I.
`I have been retained as an expert in this case by counsel for Defendants and
`1.
`Counter-Plaintiffs Hughes Communications Inc., Hughes Network Systems LLC,
`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 following four patents:
`
`(cid:120) U.S. Patent No. 7,116,710 (the “’710 patent”);
`(cid:120) U.S. Patent No. 7,421,032 (the “’032 patent”);
`(cid:120) U.S. Patent No. 7,916,781 (the “’781 patent”); and
`(cid:120) U.S. Patent No. 8,284,833 (the “’833 patent”).
`I further understand that Plaintiff has asserted the following claims:
`
`3.
`
`(cid:120) claims 1, 4, 6, 15, 20, and 22 of the ’710 patent;
`(cid:120) claims 1, 18, 19, and 22 of the ’032 patent;
`(cid:120) claims 16 and 19 of the ’781 patent; and
`(cid:120) 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
`4.
`preceding paragraph (the “asserted claims”) are valid. In my opinion, all of the
`asserted claims are invalid for the reasons stated below.
`
`I have also been asked for my opinion on whether various documents,
`5.
`including an email from an inventor dated March 7, 2000, demonstrate conception
`
`-1-
`
`Expert Report of Dr. Brendan Frey
`Case No. 2:13-cv-07245-MRP-JEM
`
`3
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`of the claimed invention. In my opinion, these documents do not demonstrate
`conception for the reasons stated below.
`
`I have also been asked for my opinion regarding whether three references
`6.
`(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
`I received a B.Sc. with Honors in Electrical Engineering from the University
`7.
`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.
`
`During my career I have conducted research in the areas of graphical models,
`8.
`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.
`
`I have received a number of honors and awards for the research I have
`9.
`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:13-cv-07245-MRP-JEM
`
`4
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`In 2009, I was awarded a Steacie Fellowship for my work on the theory and
`10.
`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 faculty 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.
`
`Throughout my career I have received funding from various governmental
`11.
`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 vitæ is attached to this report as Exhibit A.
`
`B. Understanding of the Law
`I am not an attorney. For the purposes of this report, I have been informed
`13.
`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:13-cv-07245-MRP-JEM
`
`5
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`The description in a written reference does not have to be in the same words
`16.
`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
`
`18. A patent claim is invalid if the claimed invention would have been obvious
`to a person of ordinary skill in the art at the time the application was filed. This
`means that even if all of the requirements of a claim 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.
`
`The determination of whether a claim is obvious should be based upon
`19.
`several factors, including:
`
`(cid:120) the level of ordinary skill in the art that someone would have had at the time
`the claimed invention was made;
`(cid:120) the scope and content of the prior art;
`(cid:120) 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:
`
`(cid:120) commercial success of a product due to the merits of the claimed invention;
`-4-
`
`Expert Report of Dr. Brendan Frey
`Case No. 2:13-cv-07245-MRP-JEM
`
`6
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`(cid:120) a long felt need for the solution provided by the claimed invention;
`(cid:120) unsuccessful attempts by others to find the solution provided by the claimed
`invention;
`(cid:120) copying of the claimed invention by others;
`(cid:120) unexpected and superior results from the claimed invention;
`(cid:120) 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
`(cid:120) 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:
`
`(cid:120) 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;
`(cid:120) whether there is some teaching or suggestion in the prior art to make the
`modification or combination of elements claimed in the patent;
`(cid:120) whether the innovation applies a known technique that had been used to
`improve a similar device or method in a similar way; or
`(cid:120) 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.
`obviousness using the benefit of hindsight; many true inventions might seem
`obvious after the fact.
`
`-5-
`
`Expert Report of Dr. Brendan Frey
`Case No. 2:13-cv-07245-MRP-JEM
`
`7
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`23. A single reference can alone render a patent claim obvious, if any
`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.
`
`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
`
`I have been informed that during prosecution, inventors have a duty to
`26.
`disclose to the Patent Office all information known to the inventors that is material
`to the patentability of the claims being examined.
`
`Information is deemed to be material to patentability when it is not
`27.
`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
`
`-6-
`
`Expert Report of Dr. Brendan Frey
`Case No. 2:13-cv-07245-MRP-JEM
`
`8
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`in (a) opposing an argument of unpatentability relied on by the Patent Office, or (b)
`asserting an argument of patentability.
`
`C. Materials Reviewed
`28. Among the materials I have reviewed in forming my opinions are:
`
`(cid:120) The ’710, ’032, ’781, and ’833 patents;
`(cid:120) The prosecution histories of the ’710, ’032, ’781, and ’833 patents;
`(cid:120) The prior art of record that was available to the patent examiner;
`(cid:120) The prior art references discussed herein;
`(cid:120) Claim Construction Order dated August 6, 2014 (Dkt. No. 105);
`(cid:120) Declaration of Stephen B. Wicker, dated Oct. 6, 2014 (Dkt. No. 130-10);
`(cid:120) Transcript of the October 14, 2014 deposition of Stephen B. Wicker;
`(cid:120) IPR Petition No. IPR2015-00067 and accompanying exhibits, including the
`declaration of Henry D. Pfister;
`(cid:120) IPR Petition No. IPR2015-00068 and accompanying exhibits, including the
`declaration of Henry D. Pfister;
`(cid:120) IPR Petition No. IPR2015-00060 and accompanying exhibits, including the
`declaration of Henry D. Pfister;
`(cid:120) IPR Petition No. IPR2015-00059 and accompanying exhibits, including the
`declaration of Henry D. Pfister;
`(cid:120) IPR Petition No. IPR2015-00061 and accompanying exhibits, including the
`declaration of Henry D. Pfister;
`(cid:120) IPR Petition No. IPR2015-00081 and accompanying exhibits, including the
`declaration of Henry D. Pfister;
`(cid:120) Transcript of the December 11, 2014 deposition of inventor Aamod
`Khandekar;
`(cid:120) Transcript of the January 7, 2015 deposition of inventor Hui Jin;
`(cid:120) Transcript of the Jan 15, 2015 deposition of Dariush Divsalar;
`(cid:120) Laboratory Notebook of Robert McEliece (CALTECH000004472-603);
`(cid:120) 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:13-cv-07245-MRP-JEM
`
`9
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`(cid:120) Caltech’s Second Supplemental Responses to Interrogatories 1-5 and
`Caltech’s First Supplemental Responses to Interrogatories 6-11;
`(cid:120) Email from Brendan Frey to Dariush Divsalar dated Dec. 8, 1999
`(CALTECH000024021);
`(cid:120) Khandekar, Aamod (“Capacity Achieving Codes on the Binary Erasure
`Channel”) (CALTECH000007321-7349).
`(cid:120) Khandekar, Aamod, “Graph-based Codes and Iterative Decoding,” thesis
`dated June 10, 2002.
`(cid:120) McEliece Email dated March 7, 2000 (CALTECH000008667)
`(cid:120) Luby, M. et al., “Practical Loss-Resilient Codes,” STOC ’97 (1997)
`(cid:120) Luby, M. et al., “Analysis of Low Density Codes and Improved Designs
`Using Irregular Graphs,” STOC ’98, p. 249-259 (1998)
`(cid:120) Richardson, T. et al. “Design of provably good low-density parity check
`codes,” IEEE Transactions on Information Theory (1999) (preprint)
`Level of Ordinary Skill in the Art
`
`29.
`
`In my opinion, based on the materials and information I have reviewed, and
`30.
`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-
`
`Expert Report of Dr. Brendan Frey
`Case No. 2:13-cv-07245-MRP-JEM
`
`10
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`D. Claim Constructions Used in This Report
`I understand that the parties have agreed on the following claim
`31.
`constructions:
`
`Claim Term
`“irregularly”
`(’710 and ’032 patents)
`“interleaving” / “interleaver” /
`“scramble”
`(’710 patent)
`“sums of bits in subsets of the
`information bits” / “summing of bits
`in a subset of the information bits” /
`“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)
`“permutation module”
`(’833 patent)
`
`Agreed-Upon Construction
`“a different number of times”
`
`“changing the order of data elements” /
`“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” / “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”
`
`“a module that changes the order of data
`elements”
`
`I further understand that the Court in this case has issued a claim
`32.
`construction order construing certain disputed claim terms as follows:
`
`Claim Term
`“transmitting” / “transmission”
`(’032 patent)
`
`Court’s Construction
`“sending over a channel”
`
`-9-
`
`Expert Report of Dr. Brendan Frey
`Case No. 2:13-cv-07245-MRP-JEM
`
`11
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`“codeword”
`(’781 patent)
`“repeat”
` (’710 and ’032 patents)
`“combine” / “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-1 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”
`
`For the purposes of this report, I have used the constructions given in the
`33.
`two tables above. For all other claim terms, I have used the plain and ordinary
`meaning the term would have to one of ordinary skill in the art.
`
`II. OVERVIEW OF THE TECHNOLOGY
`
`The four patents-in-suit, which share a common specification, relate to the
`34.
`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. 10).
`-10-
`
`Expert Report of Dr. Brendan Frey
`Case No. 2:13-cv-07245-MRP-JEM
`
`12
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`A. Error-Correcting Codes in General
`35. Most computing devices and other digital electronics use bits to represent
`information. A bit is a binary unit of information that may have one of two values:
`1 or 0. Any type of information, including, e.g., text, music, images and video
`information, can be represented digitally as a collection of bits.
`
`36. When transmitting binary information over an analog communication
`channel, the data bits representing the information to be communicated (also called
`“information bits” or “source bits”) are converted into an analog signal that can be
`transmitted over the channel. This process is called modulation. The transmitted
`signal is then received by a receiving device and converted back into binary form.
`This process, in which a received analog waveform is converted into bits, is called
`demodulation. The steps of modulation and demodulation are shown in the figure
`below:
`
`Modulation, Transmission, and Demodulation
`
`Transmission over physical channels is never 100% reliable. The
`37.
`transmitted signal can be corrupted during transmission by “noise” caused by, e.g.,
`obstacles obstructing the signal path, interference from other signals, or
`electrical/magnetic disturbances. Noise can cause bits to “flip” during
`transmission: for example, because of noise, a bit that was transmitted as a 1 can be
`corrupted during transmission and demodulated as 0, and vice versa.
`
`-11-
`
`Expert Report of Dr. Brendan Frey
`Case No. 2:13-cv-07245-MRP-JEM
`
`13
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`Error-correcting codes were developed to combat such transmission errors.
`38.
`Using the bits representing the information to be communicated (called
`“information bits”, “data bits” or “source bits”) an error-correcting code generates
`“parity bits” that allow the receiver to verify that the bits were transmitted correctly,
`and to correct transmission errors that may have occurred.
`
`39. Bits are encoded by an encoder, which receives a sequence of information
`bits as input, generates parity bits based on the information bits according to a
`particular encoding algorithm, and outputs a sequence of encoded bits (or data
`elements) called a codeword. The codeword produced by the encoder is then
`modulated and transmitted as an analog signal.
`
`40. At the receiver the signal is received, demodulated and passed to the decoder,
`which uses a decoding algorithm to recover the original codeword and the original
`information bits.
`
`Encoding and Decoding
`
`Error-correcting codes work by adding redundant information to the original
`41.
`message. Due to redundancy, the information represented by a given information
`bit is spread across multiple bits of the codeword. Thus, even if one of those bits is
`flipped during transmission, the original information bit can still be recovered from
`the others.
`
`42. As a simple example, consider an encoding scheme, which I will call
`“repeat-three,” that outputs three copies of each information bit. In this scheme,
`the information bits “1 0 1” would be encoded as “111 000 111.” Upon receipt,
`-12-
`
`Expert Report of Dr. Brendan Frey
`Case No. 2:13-cv-07245-MRP-JEM
`
`14
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`the decoder converts instances of “111” into “1” and instances of “000” into “0” to
`produce the decoded bits “1 0 1,” which match the original information bits.
`
`Suppose a bit is flipped during transmission, changing “000” to “010.” The
`43.
`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.
`
`Error-correcting codes may be either systematic or non-systematic. In a
`44.
`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.
`
`Systematic and non-systematic codes had been known in the art for decades
`45.
`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 k/n is called the rate of the
`code. Because the codeword generally includes redundant information, n is
`generally greater than k, and the rate k/n of an error-correcting code is generally
`less than one.
`
`C. Performance of Error-Correcting Codes
`The effectiveness of an error-correcting code may be measured using a
`47.
`variety of metrics.
`
`-13-
`
`Expert Report of Dr. Brendan Frey
`Case No. 2:13-cv-07245-MRP-JEM
`
`15
`
`
`
`1
`
`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) / (1000 total bits) =
`0.01 or 1%.5
`
`The BER of a coded transmission depends on the amount of noise that is
`49.
`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-
`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/N0 to determine how the code performs under various
`channel conditions.
`
`Error-correcting codes may also be assessed based on their computational
`50.
`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:13-cv-07245-MRP-JEM
`
`16
`
`
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`20
`
`21
`
`22
`
`23
`
`24
`
`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
`
`In 1963, Robert Gallager described a set of error correcting codes called
`51.
`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 0s and relatively few 1s, and he described how decoding
`could be performed using an iterative “message passing” decoding algorithm, as
`described below.7
`
`52. Gallager’s work was largely ignored over the following decades, as
`researchers continued to discover other algorithms for calculating parity bits. These
`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.
`
`In 1993, researchers discovered “turbocodes,” a class of error-correcting
`53.
`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 s1, s2, s3, 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:13-cv-07245-MRP-JEM
`
`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
`’ could be computed by s1
`’ = dk + s1 + s2 + s3 + s4 modulo 2, and the other
`bit s1
`’ = s1, s3
`’ = s2, and s4
`’ = s3. What does “modulo 2” mean?
`memory bits would be s2
`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 s4 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
`’ + s4 modulo 2. The combinations used to
`memory bits, for example, yk = s1
`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 s1
`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 b