David C. Marcus (SBN 158704)
`david.marcus@wi1me1'hale.com
`James M. Dowd (SEN 259578)
`jarnes.dowd@wilme1'hale.com
`Matthew J. Hawkinson (SBN 248216)
`matthew.hawkinson@wilmerhalecom
`Aaron Thompson (SBN 272391)
`aaron.tl1ornpson@wilmerha1e.com
`WILMER CUTLER PICKERING
`
`1-[ALE AND DORR LLP
`
`350 South Grand Avenue, Suite 2100
`
`Los Angeles, CA 90071
`Telephone:
`(213) 443-5300
`Facsimile:
`(213)443-5400
`
`1
`
`I\.)
`
`\OOO--JO\
`
`William F. Lee (pro hac vice)
`william.lee@wi1merha1e.com
`WILMER CUTLER PICKERING
`
`HALE AND DORR LLP
`
`60 State Street
`
`Boston, MA 02109
`
`Telephone:
`Facsimile:
`
`(617) 526-6000
`(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
`
`Apple 1115
`Apple 1115
`
`Expert Report of Dr. Brendan Frey
`Case No. 2: I 3-cv—0?245—MRP-J EM
`
`

`
`[J
`
`UNITED STATES DISTRICT COURT
`
`CENTRAL DISTRICT OF CALIFORNIA
`
`THE CALIFORNIA INSTITUTE OF
`
`Case No. 2 : I 3-cv-07245 -MRP—J EM
`
`TECHNOLOGY,
`
`Plaintiff and Counter-Defendant,
`
`BRENDAN FREY REGARDING
`
`INVALIDITY OF PATENTS-IN-
`
`VS.
`
`SUIT
`
`EXPERT REPORT OF DR.
`
`HUGHES COMMUNICATIONS INC-.,
`
`HUGHES NETWORK SYSTEMS LLC,
`
`DISH NETWORK CORPORATION,
`
`DISH NETWORK LLC, and DISHNET
`
`SATELLITE BROADBAND LLC,
`
`Defendants and Counter—Plainti1°fs.
`
`Expert Report of Dr. Brendan Frey
`Case No. 2:13-cv-07245-MRP—JEM
`
`

`
`EXPERT REPORT OF DR. BRENDAN FREY
`
`REGARDING INVALIDITY OF PATENTS-lN—SUIT
`
`|'~..J
`
`I.
`
`1.
`
`SUMMARY OF REPORT
`
`I have been retained as an expert in this case by counsel for Defendants and
`
`Counter-Plaintiffs Hughes Communications 1nc., 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.
`
`2.
`
`I understand that the Plaintiff and Counter-Defendant in this proceeding, the
`
`California Institute of Technology ( “Plaintiff” or “‘Caltech”) has asserted against
`
`Defendants the following four patents:
`
`I U.S. Patent No. 7,1 16,710 (the “‘71O patent”);
`
`I U.S. Patent No. 7,421,032 (the “"032 patent”);
`
`I U.S. Patent No. 7,916,781 (the ‘"781 patent"); and
`
`I U.S. Patent No. 8,284,833 (the “833 patent“).
`
`3.
`
`I further understand that Plaintiff has asserted the following claims:
`
`I
`
`I
`
`I
`
`I
`
`claims 1, 4, 6, 15, 20, and 22 ofthe ’710 patent;
`
`claims 1, 18, 19, and 22 ofthe ’032 patent‘,
`
`claims 16 and 19 ofthe ’78l patent; and
`
`claims 1, 2, 4, and 8 ofthe ’833 patent.
`
`4.
`
`I have been asked for my expert opinion on whether the claims listed in the
`
`preceding paragraph (the “asserted claims”) are valid.
`
`In my opinion, all of 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:13-cv-07?.45—MRP-JEM
`
`

`
`I"-J
`
`Lu
`
`C3\OGO*-JG\
`
`of the claimed invention.
`
`In my opinion, these documents do not demonstrate
`
`conception for the reasons stated below.
`
`6.
`
`I have also been asked for my opinion regarding whether three references
`
`("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 1 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 2003, 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.”
`
`-’7_
`
`Expert Report of Dr. Brendan Frey
`Case No. 2:13-cv-0'z'245—MRP-JEM
`
`

`
`1
`
`la}
`
`10.
`
`In 2009, l was awarded a Steacie Fellowship for my work on the theory and
`
`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
`
`201 1, 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.
`
`1 1.
`
`Throughout my careerl have received funding from various governmental
`
`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 czm'icuZz.:nz vitae is attached to this report as Exhibit A.
`
`B. Understanding ofthe Law
`
`I3.
`
`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: I 3~cv-07245-MRP-JEM
`
`

`
`1
`
`Ex.)
`
`Lu.)
`
`16.
`
`The description in a written reference does not have to be in the same words
`
`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.
`
`19.
`
`The determination of whether a claim is obvious should be based upon
`
`several factors, including:
`
`0
`
`the level of ordinary skill in the art that someone would have had at the time
`the claimed invention was made;
`
`I
`
`the scope and content of the prior art;
`
`I what difference, if any, existed between the claimed invention and the prior
`art.
`
`20.
`
`In considering the question of obviousness, it is also appropriate to consider
`
`any secondary considerations of obviousness or non—obviousness that may be.
`
`shown. These include:
`
`0 commercial success of a product due to the merits of the claimed invention;
`
`-4-
`
`Expert Report of Dr. Brendan Frey
`Case No. 2: l 3—cv-07245-M RP—J EM
`
`

`
`I"-J
`
`LI)
`
`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.
`
`.
`
`a_.
`71
`
`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:
`
`I 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
`
`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.
`
`22.
`
`In considering obviousness, it is important to be careful not. to determine
`
`obviousness using the benefit of hindsight; many true inventions might seem
`
`obvious after the fact.
`
`_ 5-
`
`Expert Report 01' Dr. Brendan Frey
`Case No. 2: I 3-cv—07245-MRP-J EM
`
`

`
`Ix)
`
`O0‘-.lCJ\
`
`23.
`
`A single reference can alone render a patent clain1 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)
`
`Ineguitable Conduct and Materialiy
`
`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
`
`Expert Report of Dr. Brendan Frey
`Case No. 2:13-cv-0?245~MRP-JEM
`
`

`
`1
`
`Ix.)
`
`in (a) opposing an argument of unpatentability relied on by the Patent Office, or (b)
`
`asserting an argument of patentability.
`
`C. Materials Reviewed
`
`4
`
`28.
`
`Among the materials I have reviewed in forming my opinions are:
`
`The ’710, ‘O32, ’78l, and ‘S33 patents;
`
`The prosecution histories ofthe ‘710, ’032, 781, and ‘S33 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;
`
`[PR Petition No. lPR20l5-00068 and accompanying exhibits, including the
`declaration of Henry D. Pfister;
`
`IPR Petition No. IPR20l 5—00O60 and accompanying exhibits, including the
`declaration of Henry D. Pfister;
`
`IPR Petition No. lPR2015—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;
`
`[PR Petition No. lPR2015—0008l and accompanying exhibits, including the
`declaration of Henry D. Pfister;
`
`Transcript of the December 1 1, 2014 deposition of inventor Aamod
`Khandekar;
`
`Transcript of the January 7, 2015 deposition of inventor Hui J in;
`
`Transcript of the Jan 15, 2015 deposition of Dariush Divsalar;
`
`Laboratory Notebook of Robert McEliece (CALTECH0000O4472-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: 1 3-cv-07245-MRP-JEM
`
`

`
`0 Caltech’s Second Supplemental Responses to lnterrogatories 1-5 and
`Caltech's First Supplemental Responses to Interrogatories 6-] 1;
`
`0 Email from Brendan Frey to Dariush Divsalar dated Dec. 8, I999
`(CALTECH00O024021)f,
`
`la.)
`
`DJ
`
`0 Khandekar, Aamod (“Capacity Achieving Codes on the Binary Erasure
`Channel”) (C ALTEC I-100000732 ] -7349).
`
`I Khandekar, Aamod, “Graph-based Codes and Iterative Decoding,” thesis
`dated June 10, 2002.
`
`I McEliece Email dated March 7, 2000 (CALTECH000008667)
`
`I Luby, M. et al., “Practical Loss—Resilient Codes,” STOC '97 (1997)
`
`I Luby, M. et al., “Analysis of Low Density Codes and Improved Designs
`Using Irregular Graphs,” STOC ’98, p. 249-259 (1998)
`
`in Richardson, T. et al. “Design of provably good low—density parity check
`codes,” IEEE Tmn.sacr:'0r1s on Irgformafion Theory (1999) (preprint)
`
`29.
`
`Level ofOrdina1y Skill in the Art
`
`30.
`
`In my opinion, based on the materials and information I have reviewed, and
`
`on my extensive experience working with people in the technical areas relevant to
`
`the patents-in-suit (17. 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.‘
`
`I understand that Caltech has agreed with this definition of the level of
`
`ordinary skill in this case.”
`
`l was asked to use a similar qualification for a “person of ordinary skill in the art" for purposes
`'
`ofa declaration that I understand was filed in connection with petitions For Inter Pcrrre.s- RE"l’f€lrI»‘
`ofthe asserted patents. See Declaration of Brendan Frey dated October 14. 20l4, at '[[2.
`3 Reporter's Transcript ofClaim Construction and Motion Hearing ol"July 9. 2014, Ex. I026, at
`98.
`3 This is also consistent with testimony given by, e.g.. Dr. Dariush Divsalar, an author olione of
`the prior art references discussed in this report (see Divsalar Dep. at 55-56).
`-3-
`
`Expert Report of Dr. Brendan Frey
`Case No. 2: l 3—cv»07245-M RP-JEM
`
`

`
`l
`
`D. Claim Constructions Used in This Report
`
`31.
`
`I understand that the parties have agreed on the following claim
`
`constructions:
`
`
`Claim Term Agreed-Upon Construction
`
`
`“irregularly”
`“a different number of times"
`(710 and ‘032 patents)
`
`
`“interleaving” / “interleaver” /
`“scramble”
`
`
`
`
`
`“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”
`
`
`
`
`
`
`
`C710 patent)
`
`“sums of bits in subsets of the
`
`information bits” I “summing of bits
`in a subset of the information bits”!
`
`“adding additional subsets of
`information bits”
`
`(‘78l 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”
`(‘S33 patent)
`
`
`
`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
`
`Court’s Construction
`
`“transmitting” / “transmission”
`(’032 patent)
`
`“sending over a channel”
`
`Expert Report of Dr. Brendan Frey
`Case No. 2: l3—cv—0’?245-MRP~.lEM
`
`

`
`“codeword"
`
`(781 patent)
`
`“repeat”
`(710 and “O32 patents)
`
`
`
`“combine” / "“combining"
`(‘S33 patent)
`
`Equation in claim 1 of the ‘O32 patent
`(_’032 patent)
`
`Tanner Graph term in claims 11 and
`18 of ‘032 patent
`(“O32 patent)
`
`“a discrete encoded sequence of data
`elements”
`
`plain meaning4
`
`“perform logical operations on"
`
`“the parity bit x, is the sum of (a) the parity
`bit X,--1 and (b) the sum ofa number, ‘a,’ of
`randomly chosen irregular repeats of the
`message hits”
`
`“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 at 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
`
`two tables above. For all other claim terms, [ have used the plain and ordinary
`
`meaning the term would have to one of ordinary skill in the art.
`
`II.
`
`OVERVIEW OF THE TECHNOLOGY
`
`34.
`
`The four patents-in-suit, which share a common specification, relate to the
`
`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' 1'e'quires the creation of new
`bits corresponding to or reflecting the value ofthe 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: l 3—cv-07245-MRP-JEM
`
`

`
`I
`
`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
`
`Demorlulation
`
`(bits:
`
`1
`
`.M
`
`__"|_.i|'l|'i.|ii|~!'/ialiii/f-_,
`
`in
`
`_.l',__I"i|’l|IiJ.‘!l M ”
`“
`
`T
`
`11oooo1o
`T
`
`Digital
`I information
`{bits}
`
`in ft: rm at-ia :1
`
`Modulation, Transmission, and Demodulation
`
`37.
`
`Transmission over physical channels is never 100% reliable. The
`
`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: I 3-cv—07245~M RP-JEM
`
`

`
`38.
`
`Error—correcting codes were developed to combat such transmission errors.
`
`l\.)
`
`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 occur1'ed.
`
`C.‘.D\DOO‘--..10\
`
`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.
`
`
`
`T
`
`Information bits
`
`codeword
`
`information bits
`
`Encoding and Decoding
`
`4|.
`
`Error-correcting codes work by adding redundant information to the original
`
`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 O 1” would be encoded as “1 11 000 I 11." Upon receipt,
`
`-19-
`
`Expert Report of Dr. Brendan Frey
`Case No. 2: I 3-cv—07245-MRP-JEM
`
`

`
`the decoder converts instances of “1 1 1"‘ into “1” and instances of “000“ into “0" to
`
`Ix.)
`
`produce the decoded bits “I 0 1.” which match the original information bits.
`
`43.
`
`Suppose a bit is flipped during transmission, changing “000” to “O10?” The
`
`decoder will be able to detect that there was a transmission error, because “0l0" 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 sysremaric or non—sysremari'c.
`
`In a
`
`systematic code, both the parity bits and the original information bits are included
`
`in the codeword.
`
`In a non—systen‘1atic 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 :1. An encoder receives an k—bit block of information bits as input, and
`
`produces a corresponding n-bit codeword. The ratio Ii!/IT is called the rate of the
`
`code. Because the codeword generally includes redundant information, I? is
`
`generally greater than k, and the rate k/rz of an error-correcting code is generally
`
`less than one.
`
`C.
`
`Performance of Error-Correcting Codes
`
`47.
`
`The effectiveness of an error-correcting code may be measured using a
`
`variety of metrics.
`
`_ ] 3-
`
`Expert Report of Dr. Brendan Frey
`Case No. 2: l3—cv—07245-MRP-JEM
`
`

`
`48.
`
`One tool used to assess the performance of a code is its bit-error rate (BER).
`
`In.)
`
`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
`
`(t'.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%?‘
`
`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 (t'.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 E;, is the amount
`
`of energy used to transmit each bit of the signal, and N0 is the density of the noise
`
`on the channelfi The BER of an error—correcting code is often measured for
`
`multiple Values of E),/N0 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 frgfbrmzirtrin BER, which measures the percentage of
`bits that remain incorrect after decoding. This is not to be confused with the trartsmf.s'.s'forr BER,
`which measures the percentage ofbits that are incorrect when they are received by the decoder.
`l’ More precisely, Eg,x'Ng is the nrmntrfized signal-to-noise ratio.
`It is a dimensionless. quantity that
`does not depend on the particular units used to measure the strength ofthe signal and the
`quantity of noise on the channel.
`
`-14-
`
`Expert Report of Dr. Brendan Frey
`Case No. 3: l 3-cv-07245-MRP—JEM
`
`

`
`bits from the parity bits. If a code is too complex, it may be impractical to build
`
`Ix.)
`
`encoders/decoders that are fast enough to use it.
`
`10
`
`ll
`
`13
`
`I4
`
`15
`
`D. LDPC Codes, Convolutional Codes, Turbocodes, and Repeat-
`Accumulate codes
`
`51.
`
`In 1963, Robert Gallager described a set of error correctin g 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 05 and relatively few Is, and he described how decoding
`
`could be performed using an iterative “message passing” decoding algorithm, as
`
`described below?
`
`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 lcw—complexity decoding
`
`algorithms.
`
`53.
`
`In 1993, researchers discovered “turbococles," 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
`
`l960’s a11d were widely used in telephone modems in the 1980's and l990’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 51,. is processed, the memory bits 3., S3, S3, S4 are combined with the
`
`information bit to produce a new memory bit and the remaining memory bits are
`
`7 Gallager, R._. Low-De:—m‘t_1-'Parf.ty—Check ('.'oa'e.s- (Monograph. M.I.T. Press. 1963).
`-15-
`
`Expert Report ol'Dr. Brendan Frey
`Case No. 2:13-cv-0'/'245—MRP-JEM
`
`

`
`“shifted”, so that the last memory bit is discarded. For example, the new memory
`
`l\J
`
`bit S]. could be computed by sin '—' all + s. + 32 + 5;, + 54 modulo 2, and the other
`
`memory bits would be 32‘ = s., 53,- = 32, and 34‘ = 33. 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
`
`10
`
`11
`
`l3
`
`I4
`
`15
`
`16
`
`the bits is odd, then the sum modulo 2 is one. Note that 3.», has been discarded.
`
`When an information bit is being processed, a parity bit is also generated. The
`
`parity bit y,, is a combination of the new memory bit and the entire set of current
`
`memory bits, for example, y;, = sf + 3.; 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 all
`
`and 34 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 51' and another tap to S.-... 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 hits, the code is called “non-
`
`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 .S'hcmr.-rm Limf! Error-CorrecIr‘ng Coding and Decridfng.‘ Turfao
`C‘m:.'ie.s', 2 IEEE International Conference on Cornmunicatiolts, ICC ’93 Geneva. Technical
`-1 6..
`
`Expert Report of Dr. Brendan Frey
`Case No. 2:13-cv-07245-MRP—.lEM
`
`

`
`Ix.)
`
`54.
`
`Convolutional codes are usually decoded using the “Viterbi algorithm” or
`
`the “BCI R algorithm". These algorithms can be viewed as iterative “message
`
`passing" decoding algorithms, if we represent the convolutional code using a
`
`“Tanner graph" or a “factor graph”, as described below.
`
`55.
`
`The main drawback of convolutional codes is that they only produce local
`
`redundancy in the output stream. They do not perform well when the channel
`
`introduces errors that are nearby. Turbocodes overcome this deficiency by
`
`encoding the input bits twice. The input bits are fed to a convolutional encoder in
`
`their normal order, and they ar