`
`oO
`
`
`
`David C. Marcus (SBN 158704)
`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 CommunicationsInc.
`Hughes Network Systems LLC
`DISH Network Corporation,
`DISH Network LLC, and
`dishNETSatellite Broadband LLC
`
`Additional Counsel Listed on Signature Page
`
`Case No. 2:13-cv-07245-MRP-JEM
`
`Expert Report of Dr. Brendan Frey
`
`Apple 1015
`Apple 1015
`
`
`
`bo
`
`UNITED STATES DISTRICT COURT
`CENTRAL DISTRICT OF CALIFORNIA
`
`THE CALIFORNIA INSTITUTE OF
`TECHNOLOGY,
`
`Plaintiff and Counter-Defendant,
`
`vs.
`
`HUGHES COMMUNICATIONS INC.,
`HUGHES NETWORK SYSTEMS LLC,
`DISH NETWORK CORPORATION,
`DISH NETWORK LLC, and DISHNET
`SATELLITE BROADBANDLLC,
`
`Defendants and Counter-Plaintiffs.
`
`
`
`Case No. 2:13-cv-07245-MRP-JEM
`
`EXPERT REPORTOF DR.
`BRENDAN FREY REGARDING
`INVALIDITY OF PATENTS-IN-
`SUIT
`
`
`
`
`
`
`
`Expert Report of Dr. Brendan Frey
`Case No. 2:]3-cv-07245-MRP-JEM
`
`
`
`i)
`
`
`
`EXPERT REPORT OF DR. BRENDAN FREY
`REGARDING INVALIDITY OF PATENTS-IN-SUIT
`
`I.
`
`l.
`
`SUMMARY OF REPORT
`
`| have been retained as an expert in this case by counsel for Defendants and
`
`Counter-Plaintiffs Hughes Communications Inc., Hughes Network Systems LLC,
`
`DISH Network Corporation, DISH Network LLC, and dishNETSatellite
`
`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-Defendantin this proceeding, the
`
`California Institute of Technology (“Plaintiff’ or “Caltech”) has asserted against
`
`Defendants the following four patents:
`
`e U.S. Patent No. 7,116,710 (the “’710 patent’);
`
`e U.S. Patent No. 7,421,032 (the “’032 patent”);
`
`e U.S. Patent No. 7,916,781 (the “781 patent”); and
`
`e U.S. Patent No. 8,284,833 (the “’833 patent”).
`
`3.
`
`[ further understand that Plaintiff has asserted the following claims:
`
`e
`
`e
`
`e
`
`e
`
`=
`
`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 ofthe °833 patent.
`I have been asked for my expert opinion on whetherthe claimslisted in the
`
`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,
`
`including an email from an inventor dated March 7, 2000, demonstrate conception
`
`=jic
`
`Expert Report of Dr, Brendan Frey
`Case No. 2:13-cv-07245-MRP-JEM
`
`
`
`bh
`
`uo
`
`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 Lubyet al. and one by Richardsonet 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.
`
`[ 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 | am a Professor of Electrical and Computer
`
`Engineering and Computer Science.
`
`8.
`
`During my career | have conducted research in the areas of graphical models
`
`error-correcting coding, machine learning, genome biology and computer vision.[
`
`have authored more than 200 publications and am namedas an inventoron 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, | was
`
`named a Fellow of the American Association for the Advancement of Science
`
`(AAAS), an honorthat recognizes “efforts on behalf of the advancement ofscience
`
`or its applications which are scientifically or socially distinguished.”
`
`xP
`
`Expert Report of Dr. Brendan Frey
`Case No. 2:13-cv-07245-MRP-JEM
`
`
`
`10.
`
`In 2009, I was awarded a Steacie Fellowship for my work on the theory and
`
`bt
`
`implementationofartificial and natural mechanismsfor 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, 1 received the NSERC’s John C. Polanyi Award, in recognition of my
`
`research on inferring genetic codes embedded in DNAthat 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
`
`CanadianInstitute for Advanced Research.
`
`12.
`
`A copy of my curriculumvite is attached to this report as Exhibit A.
`
`B. Understanding of the Law
`
`13.
`
`Tam notanattorney. For the purposesofthis report, | 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
`
`A patent claim is invalid if it is “anticipated” by prior art. For the claim to
`15.
`be invalid becauseit 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.
`33.
`
`Expert Report of Dr. Brendan Frey
`Case No. 2:13-cv-07245-MRP-JEM
`
`
`
`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 someoneofordinary skill in the art, looking at that one
`
`ho
`
`ad
`
`reference would be able to make and use the claimed invention.
`
`A patent claim is also anticipated if there is clear and convincing proofthat,
`17.
`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
`
`A patent claim is invalid if the claimed invention would have been obvious
`18.
`to a person ofordinary skill in the art at the time the application was filed. This
`meansthat evenif all of the requirements of a claim cannot be foundin a single
`
`prior art reference that would anticipate the claim orconstitute a statutory bar to
`that claim, the claim is invalid if it would have been obviousto a person of
`
`ordinary skill who knew aboutthe prior art.
`
`19.
`
`The determination of whether a claim ts obvious should be based upon
`
`several factors, including:
`
`«
`
`the level of ordinary skill in the art that someone would have hadat the time
`the claimed invention was made;
`
`the scope and contentofthe prior art;
`e
`e whatdifference, if any, existed between the claimed invention and the prior
`art.
`
`20.
`
`Inconsidering the question of obviousness,it is also appropriate to consider
`
`any secondary considerations of obviousness or non-obviousness that may be
`
`shown. These include:
`
`toUo
`
`e 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
`
`
`
`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 superiorresults from the claimed invention;
`acceptance by others of the claimed invention as shownby praise from
`others in the field or from the licensing of the claimed invention; and
`
`eels
`21
`
`independentinvention of the claimed invention by others before or at about
`the same time as the named inventor thought ofit.
`A patent claim composedofseveral elements is not proved obvious merely
`by demonstrating that each of its elements was independently knowninthe 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 thepriorart in
`
`the same wayas 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:
`
`e whether the change was merely the predictable result of using prior art
`elements according to their known functions, or whetherit was the result of
`true inventiveness;
`
`whetherthere 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 obviousto try, meaning that
`the claimed innovation was oneof a relatively small numberofpossible
`approachesto 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
`
`oD.
`
`obviousness using the benefit of hindsight; many true inventions might seem
`
`obvious after the fact.
`
`BBs
`
`Expert Report of Dr. Brendan Frey
`Case No. 2:13-ev-07245-MRP-JEM
`
`
`
`23. Asingle reference can alone rendera patent claim obvious,if any
`
`differences between that reference and the claims would have been obvious to a
`
`to
`
`person of ordinary skill in the art at the time ofthe alleged invention — thatts, 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
`
`A patent claim is invalid if the patent specification does not contain a written
`24.
`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.
`
`An applicant showspossession of the claimed invention by describing the
`25,
`claimed invention with all ofits limitations using such descriptive means as words,
`
`structures, figures, diagrams, and formulasthat fully set forth the claimed
`invention. A description that merely renders the invention obvious does notsatisfy
`
`the written description requirement.
`
`v)
`
`Inequitable Conduct and Materiality
`
`26.
`
`Ihave been informed that during prosecution, inventors have a duty to
`
`disclose to the Patent Office all information knownto the inventors that is material
`
`to the patentability of the claims being examined.
`
`27.
`
`Information is deemed to be material to patentability whenit 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
`
`-6-
`
`Expert Report of Dr. Brendan Frey
`Case No. 2:13-cv-07245-MRP-JEM
`
`
`
`in (a) opposing an argument of unpatentability relied on by the Patent Office, or (b)
`
`asserting an argumentofpatentability.
`
`b2
`
`C. Materials Reviewed
`
`28.
`
`Among the materials I have reviewed in forming my opinionsare:
`
`e The *710, °032, *781, and °833 patents;
`
`e The prosecutionhistories of the °710, °032, °781, and °833 patents;
`e
`Theprior art of record that was available to the patent examiner;
`e
`Theprior art references discussed herein;
`e Claim Construction Order dated August 6, 2014 (Dkt. No. 105):
`
`e
`
`e
`
`«
`
`e Declaration of Stephen B. Wicker, dated Oct. 6, 2014 (Dkt. No. 130-10);
`e Transcript of the October 14, 2014 deposition of Stephen B. Wicker;
`e
`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. [PR2015-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;
`e Transcript of the December 11, 2014 deposition of inventor Aamod
`Khandekar:;
`
`e
`
`e
`
`e
`
`‘Transcript of the January 7, 2015 deposition of inventor Hui Jin;
`
`e Transcript of the Jan 15,2015 deposition of Dariush Divsalar;
`e Laboratory Notebook of Robert McEliece (CALTECH000004472-603):
`e Caltech’s Supplemental Responses to Defendants’ First Set of
`Interrogatories, Nos. 3-5, Jan. 11, 2015;
`
`ae
`
`Expert Report of Dr. Brendan Frey
`Case No. 2:13-cv-07245-MRP-JEM
`
`
`
`soCo—loOwa-adi)
`
`29.
`
`30.
`
`e Caltech’s Second Supplemental Responsesto Interrogatories 1-5 and
`Caltech’s First Supplemental Responsesto Interrogatories 6-11;
`
`e Email from Brendan Frey to Dariush Divsalar dated Dec. 8, 1999
`(CALTECH000024021):
`
`e Khandekar, Aamod (“Capacity Achieving Codes on the Binary Erasure
`Channel”) (CALTECH000007321-7349).
`
`e Khandekar, Aamod, “Graph-based Codesand Iterative Decoding,”thesis
`dated June 10, 2002.
`
`e McEliece Email dated March 7, 2000 (CALTECH000008667)
`
`e Luby, M. et al., “Practical Loss-Resilient Codes,” STOC '97 (1997)
`
`e Luby, M. et al., “Analysis of Low Density Codes and Improved Designs
`Using Irregular Graphs,” STOC 98, p. 249-259 (1998)
`e Richardson, T.et al. “Design of provably good low-density parity check
`codes,” JEEE Transactions on Information Theory (1999) (preprint)
`Level of Ordinary Skill in the Art
`
`In myopinion, 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(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 experiencethis field at the time of the alleged
`invention.’
`| understand that Caltech has agreed withthis definition of the level of
`ordinary skill in this case.”*
`
`| was asked to use a similar qualification for a “person ofordinary skill in the art” for purposes
`'
`of a declaration that I understand wasfiled in connection with petitions for /nter Partes Review
`of the asserted patents. See Declaration of Brendan Frey dated October 14, 2014, at §[2.
`Reporter’s Transcript of Claim Construction and Motion Hearing of July 9, 2014, Ex. 1026,at
`98.
`> This is also consistent with testimony given by, e.g., Dr. Dariush Divsalar, an author ofone of
`the priorart 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
`
`
`
`D. Claim Constructions Used in This Report
`
`31.
`
`1 understand that the parties have agreed on the following claim
`
`constructions:
`
`
`
` Claim Term
`Agreed-Upon Construction
`
` “irregularly”
`
`“a different numberof times”
`
`(°710 and °032 patents)
`
` “changing the order of data elements”/
`
`
`“interleaving” / “interleaver” /
`“module that changes the order of data
`“scramble”
`
`
`elements”
`(°710 patent)
`
`
`
`
`
`
`“the result(s) of adding together two or
`“sums of bits in subsets of the
`more information bits from a subset of
`informationbits” / “summingofbits
`
`
`
`
`information bits” / “adding together two or
`in a subsetof the information bits” /
`
`
`more information bits from a subset of
`“adding additional subsets of
`
`
`information bits”
`information bits”
`
`
`
`(°781 patent)
`
` “where two or more memory locations of
`
`
`the first set of memory locations are read
`
`
`
`by the permutation module a different
`
`
`numberof times from one another”
`
`
`
`
`
`
` “a module that changes the order of data
`
`“permutation module”
`
`elements”
`(°833 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)
`
`32.
`
`| further understand that the Court in this case has issued a claim
`
`construction order construing certain disputed claim termsas follows:
`
`
`
`Claim Term
`
`Court’s Construction
`
`“sending over a channel”
`“transmitting” / “transmission”
`(°032 patent)
`
`Expert Report of Dr. Brendan Prey
`Case No, 2:13-cv-07245-MRP-JEM
`
`
`
`
`
`
`
`“a discrete encoded sequenceofdata
`“codeword”
`elements”
`(°781 patent)
`plain meaning’
`“repeat”
`(°710 and °032 patents)
`“combine”/ “combining”
`“perform logical operations on”
`(*833 patent)
`Equation in claim 1 of the ’032 patent
`(°032 patent)
`
`|“the parity bit x; is the sum of(a) the parity
`bit x;.; and (b) the sum of a number,‘a,’ of
`randomly chosen irregular repeats of the
`message bits”
`
`Tanner Graph term in claims 11 and
`18 of °032 patent
`(°032 patent)
`
`_|“a graph representing an IRA code asa set
`of parity checks where every messagebit is
`repeated, at least two different subsets of
`messagebits are repeated a different
`numberof times, and check nodes,
`randomly connected to the repeated
`messagebits, enforce constraints that
`determine the parity bits”
`
`33.
`
`For the purposesofthis report, I have used the constructions givenin 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 theart.
`
`Il.
`
`OVERVIEW OF THE TECHNOLOGY
`
`The four patents-in-suit, which share a commonspecification, 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 developmentsin 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.
`
`* The Claim Construction Order dated August 6, 2014 expounded onthe plain meaning of
`“repeat.” For example, the order said the “plain meaning of ‘repeat’ requires the creation of new
`bits correspondingto or reflecting the value ofthe originalbits.
`In other words, repeating a bit
`with the value 0 will produce anotherbit with the value 0, The Court will refer to this conceptas
`duplication” (Claim Construction Order dated August6, 2014, p. 10).
`«iQ:
`
`Expert Report of Dr, Brendan Frey
`Case No. 2:13-cv-07245-MRP-JEM
`
`
`
`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 representeddigitally as a collection ofbits.
`
`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 shownin the figure
`
`below:
`
`Modulation
`»
`Transmission
`11000010 ee 3s Alie ANN
`|
`Transmitter
`|
`
`AALS
`
`allt
`
`aia
`
`(bits)
`
`Demodulation
`eee 11000010
`|
`
`Digital
`Information
`
`Receiver
`
`Digital
`Information
`(bits)
`
`Analag
`Signal
`(waves)
`
`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 causebits 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.
`
`FF.
`
`Expert Report of Dr. Brendan Frey
`Case No. 2:13-cv-07245-MRP-JEM
`
`
`
`Nm
`
`OonsOf
`=6
`
`38.
`
`Error-correcting codes were developed to combat such transmissionerrors.
`
`Usingthe 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 encodedbits (or data
`elements) called a codeword. The codeword produced by the encoderis then
`
`modulated and transmitted as an analogsignal.
`
`40.
`
`At the receiver the signal is received, demodulated and passed to the decoder
`
`which uses a decoding algorithm to recoverthe original codeword andthe original
`
`information bits.
`
`>. Transmission
`
`
`
`ii
`
`00101010010
`
`11000010
`
`Information bits Encoding and Decoding
`
`Informatian bits
`
`Codeword
`
`Codeward
`
`41.
`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 informationbit canstill be recovered from
`
`the others.
`
`42. Asasimple 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.” Uponreceipt,
`
`1s
`
`Expert Report of Dr. Brendan Frey
`Case No. 2:13-cv-07245-MRP-JEM
`
`
`
`sooo~~onWw+odbo
`
`the decoder converts instances of “1117 into “1” and instances of “000”tnto “0” to
`
`produce the decodedbits “1 0 1,” which matchthe original informationbits.
`
`43.
`
`Supposea bit is flipped during transmission, changing “O00” to “010.” The
`
`decoderwill 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 transmissionerror.
`
`44.
`
`Error-correcting codes may be either systematic or non-systematic. Ina
`
`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 knownin the art for decades
`
`prior to May 18, 2000, the claimed priority date of the patents-in-suit (see, ¢.g.,
`Wicker Dep.at 77:15-20; see also, e.g., Divsalar Dep. at pp. 66-67).
`
`B. Coding Rate
`
`46.
`
`Manyerror-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 m-bit codeword. The ratio k/n is called the rate ofthe
`
`code. Because the codeword generally includes redundant information, 77 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
`
`47.
`
`The effectiveness of an error-correcting code may be measured using a
`
`variety of metrics.
`
`aT:
`
`Expert Report of Dr. Brendan Frey
`Case No. 2:13-cv-07245-MRP-JEM
`
`
`
`sOoo~oNWwa>we)i)_
`
`48.
`
`Onetool used to assess the performance of a codeis its bil-error rate (BER).
`
`The BERis defined as the numberof 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 ofthe code during that time periodis (10 bit errors) / (1000 total bits) =
`0.01 or 1%
`
`49.
`
`The BER of a coded transmission depends on the amountofnoise thatis
`
`present in the communication channel, the strength of the transmitted signal (i.e.,
`the powerthat is used to transmit the modulated waveform), and the performance
`
`of the error-correcting code. An increase in noise tends to increase the errorrate
`
`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 encodedsignalis transmitted. The signal-
`
`to-noise ratio can be expressed mathematically as E,/No, in which &;is the amount
`
`of energy used to transmit eachbit of the signal, and Nois the density of the noise
`on the channel.° The BERofan error-correcting code is often measured for
`
`multiple values of £;/No 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 manycalculations are required for the decoder to reconstruct the information
`
`> Note that as used herein, BER refers to the information BER, which measuresthe percentage of
`bits that remain incorrect after decoding. This is not to be confused with the ¢ransmission BER,
`which measures the percentageofbits that are incorrect when they are received by the decoder.
`° Moreprecisely, E;/Ng is the normalized signal-to-noiseratio.
`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.
`
`-|4-
`
`Expert Report of Dr. Brendan Frey
`Case No. 2:]3-cv-07245-MRP-JEM
`
`
`
`bits from the parity bits. If a code is too complex, it may be impractical to build
`
`encoders/decoders that are fast enoughto useit.
`
`MN
`
`D. LDPC Codes, Convolutional Codes, Turbocodes, and Repeat-
`Accumulate codes
`
`51.
`
`In 1963, Robert Gallager described a set of error correcting codescalled
`
`Low Density Parity Check (“LDPC”) codes. Gallager described how LDPCcodes
`
`provide one method of generating parity bits from informationbits using a matrix
`populated with mostly Os and relatively few 1s, and he described how decoding
`
`could be performed using an iterative “message passing” decoding algorithm, as
`described below.’
`
`52. Gallager’s work waslargely 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.
`
`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 makeuse of “convolutional codes’, which were described in the
`
`1960’s and were widely used in telephone modemsin the 1980’s and 1990’s. A
`
`convolutional codeis 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 sequenceof bits, e.g., 4 bits. When an
`
`information bit ad, is processed, the memory bits 5), 52, 53, S4 are combined with the
`
`informationbit to produce a new memorybit and the remaining memory bits are
`
`7 Gallager, R., Low-Density Parity-Check Codes (Monograph, M.1.T. Press, 1963).
`-15-
`
`Expert Report of Dr, Brendan Frey
`Case No, 2:13-cv-07245-MRP-JEM
`
`
`
`NM
`
`“shifted”, so that the last memory bit is discarded. For example, the new memory
`bit Sy) could be computed by Sy, = dy + 8; + 89 + 53+ 84 modulo 2, and the other
`memory bits would be 5) =S|, 83 =5>, and 54 = 83. What does “modulo 2” mean?
`If the sum ofthe bits is even, then the sum modulo 2 is zero, whereasif the sum of
`
`the bits is odd, then the sum modulo 2 is one. Note that s4 has been discarded.
`
`Whenan 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, yy, = s; +4 modulo 2. The combinations used to
`determine the new memory bit and the parity bit need not includeall of the bits,
`e.g., the above example usesall bits to compute the new memory bit, but only s)
`and sy when computing the parity bit. If a particular bit is used in a combination,
`wesay there is a “tap” connectedto that bit. In the example, the parity bit is
`connected by a tap tos, and anothertap to sy. 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 informationbits are also transmitted across the channel, in
`
`addition to the parity bits. Some parity bits and/or some information bits may be
`
`punctured soas to adjust the rate of the convolutional code (the number of
`information bits processed divided by the numberof bits transmitted). If the new
`
`memory bit doesn’t have any taps to any memory bits, the code is called “non-
`
`recursive” and otherwiseit is called “recursive”, alluding to the fact that the new
`
`memory bit dependsonthe bits in the old memory. Using the above example,the
`figure below shows howa 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 5
`
`* Claude Berrou etal., Near Shannon Limit Error-Correcting Coding and Decoding: Turbo
`Codes, 2 IEEE International Conference on Communications, [CC *93 Geneva. Technical
`+16.
`
`Expert Report of Dr. Brendan Frey
`Case No. 2:13-cv-07245-MRP-JEM
`
`
`
`I
`
`54.
`
`Convolutional codes are usually decoded using the “Viterbi algorithm”or
`
`the “BCJR algorithm”. These algorithms can be viewedasiterative “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 codesis that they only produce local
`
`redundancy in the output stream. They do not perform well when the channel
`
`introduces errors that are nearby. Turbocodes overcomethis deficiency by
`
`encodingthe input bits twice. The inputbits are fed to a convolutional encoder in
`
`their normal order, and they are also reordered by an interleaver and the reordered
`
`bits are encoded by a second convolutional encoder. Using a turbocode, a small
`
`numberoferrors will not result in loss of information unless the errors happen to
`
`fall close togetherin both the original data stream and in the permuted data stream,
`
`whichis unlikely.
`
`56.
`
`A standard turbocoder encodes a sequenceof information bits using two
`
`convolutional coders, The information bits are passed to the first conv