`Apple v. California Institute of Technology
`
`UNITED STATES PATENT AND TRADEMARK OFFICE
`
`BEFORE THE PATENT TRIAL AND APPEAL BOARD
`
`APPLE INC.,
`Petitioner,
`
`v.
`
`CALIFORNIA INSTITUTE OF TECHNOLOGY,
`Patent Owner.
`_________________________________________
`
`Case IPR2017-00701
`Patent 7,421,032
`_________________________________________
`
`DECLARATION OF BRENDAN FREY, PH.D.
`REGARDING U.S. PATENT NO. 7,421,032
`CLAIMS 1, 4-10
`
`Apple v. Caltech
`IPR2017-00701
`Apple 1165
`
`
`
`U.S. Patent No. 7,421,032
`Apple v. California Institute of Technology
`TABLE OF CONTENTS
`
`I.(cid:1)
`
`BACKGROUND .......................................................................................... 1(cid:1)
`
`II.(cid:1)
`
`LEGAL PRINCIPLES .................................................................................. 6(cid:1)
`
`III.(cid:1) THE CHALLENGED CLAIMS ARE OBVIOUS ........................................ 8(cid:1)
`
`A.(cid:1)
`
`B.(cid:1)
`
`Ping in view of MacKay, Divsalar, and Luby97 .................................. 8(cid:1)
`
`Secondary Considerations of Non-Obviousness ................................ 37(cid:1)
`
`IV.(cid:1) AVAILABILITY FOR CROSS-EXAMINATION ..................................... 40(cid:1)
`
`V.(cid:1)
`
`RIGHT TO SUPPLEMENT ....................................................................... 40(cid:1)
`
`VI.(cid:1)
`
`JURAT ....................................................................................................... 41(cid:1)
`
`
`
`U.S. Patent No. 7,421,032
`Apple v. California Institute of Technology
`
`
`
`I, Brendan Frey, Ph.D., declare as follows:
`
`1. My name is Brendan Frey.
`
`I.
`
`BACKGROUND
`
`2.
`
`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.
`
`3.
`
`Since July 2001, I have been at the University of Toronto, where I am a
`
`Professor of Electrical and Computer Engineering and Computer Science.
`
`4.
`
`During my career I have conducted research in the areas of graphical
`
`models, error-correcting coding, machine learning, genome biology, medicine and
`
`computer vision. In 2015, I co-founded Deep Genomics Inc., a startup located in
`
`Toronto that is using artificial intelligence to find new medicines. Since then I have
`
`acted as its Chief Executive Officer. Deep Genomics has received over $17M in
`
`venture capital funding, mostly from Silicon Valley investors. Deep Genomics has
`
`recruited scientists and engineers from top universities, including MIT, Stanford, the
`
`University of California, San Diego, and the University of Toronto, and from
`
`competing biotech and software companies, including Amazon, Autodesk, Calico,
`
`
`
`1
`
`
`
`U.S. Patent No. 7,421,032
`Apple v. California Institute of Technology
`and Human Longevity. In 2017, I co-founded the Vector Institute for Artificial
`
`Intelligence. The Vector Institute is internationally regarded as one of, if not the, top
`
`artificial intelligence research institutes in the world. It has over $200M in funding
`
`and its current and newly hired professors have chosen faculty positions at the
`
`Vector Institute in preference to faculty offers from leading universities, including
`
`Stanford and MIT, and to senior researcher offers from leading industrial labs,
`
`including DeepMind, Google, Facebook, Microsoft and OpenAI.
`
`5.
`
`I have received a number of honors and awards for the research I have
`
`conducted. In 2008, I was named a Fellow of the Institute for Electrical and
`
`Electronic Engineers (IEEE), an honor given to a person with an “extraordinary
`
`record or accomplishments” in the field of electrical engineering. In 2009, I was
`
`named a Fellow of the American Association for the Advancement of Science
`
`(AAAS), an honor that recognizes “efforts on behalf of the advancement of science
`
`or its applications which are scientifically or socially distinguished.” In 2009, I 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 2011, I received the
`
`
`
`2
`
`
`
`U.S. Patent No. 7,421,032
`Apple v. California Institute of Technology
`NSERC’s John C. Polanyi Award, in recognition of my research on inferring genetic
`
`codes embedded in DNA that direct activities within cells. In 2015, I was elected as
`
`a Fellow of the Royal Society of Canada, with the following citation: “Professor
`
`Frey has contributed to the emergence of new fields of research in machine learning
`
`and genome biology. He was one of the first researchers to successfully train a deep
`
`neural network, and he was a pioneer in inventing message passing algorithms,
`
`which are now widely used. He co-developed the long-sought-after ‘splicing code’
`
`for determining how genes are expressed and introduced a new approach to
`
`understanding the genetics of disease.”
`
`6.
`
`Throughout my career I 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.
`
`7.
`
`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.
`
`8.
`
`9.
`
`A copy of my curriculum vitae is included as Exhibit 1166.
`
`I have reviewed the specification and claims of U.S. Patent No.
`
`7,421,032 (the “’032 patent”; Ex. 1101). I have been informed that the ’032 patent
`
`
`
`3
`
`
`
`U.S. Patent No. 7,421,032
`Apple v. California Institute of Technology
`claims priority to a provisional application filed on May 18, 2000, and to U.S.
`
`application Ser. No. 09/922,852, filed on Aug. 18, 2000.
`
`10.
`
`I have also reviewed the following references, all of which I understand
`
`to be prior art to the ’032 patent:
`
`(cid:120) L. Ping, W. K. Leung, N. Phamdo, “Low Density Parity Check
`Codes with Semi-random Parity Check Matrix.” Electron. Letters,
`Vol. 35, No. 1, pp. 38-39, January 7, 1999 (“Ping”; Ex. 1103.)
`
`(cid:120) D. J. C. MacKay, S. T. Wilson, and M. C. Davey, “Comparison of
`constructions of irregular Gallager codes,” IEEE Trans. Commun.,
`Vol. 47, No. 10, pp. 1449-54, October 1999 (“MacKay”; Ex. 1102.)
`
`(cid:120) D. Divsalar, H. Jin, and R. J. McEliece, “Coding theorems for
`‘turbo-like’ codes,” Proc. 36th Allerton Conf. on Comm., Control
`and Computing, Allerton, Illinois, pp. 201-10, March 1999
`(“Divsalar”; Ex. 1117.)
`
`(cid:120) Luby, M. et al., “Practical Loss-Resilient Codes,” STOC ‘97, pp.
`150-159, published in 1997 (“Luby97”; Ex. 1108)
`
`11.
`
`I have also reviewed the following filings in this inter partes review:
`
`(cid:120) Petition for Inter Partes Review of U.S. Pat. No. 7,421,032 (Paper 3)
`(“Petition” or “Pet.”)
`
`(cid:120) Patent Owner’s Preliminary Response (Paper 13) (“POPR”)
`
`(cid:120) Institution Decision (Paper 14)
`
`(cid:120) Patent Owner’s Response (Paper 32) (“POR”)
`
`(cid:120) Declaration of Professor James Davis, Ph.D. (Ex. 1104)
`
`(cid:120) Transcript of the Deposition of Dr. Michael Mitzenmacher
`(Ex. 2038) and associated exhibits (Exs. 1144-1149)
`4
`
`
`
`
`
`U.S. Patent No. 7,421,032
`Apple v. California Institute of Technology
`(cid:120) California Institute of Technology v. Hughes Communications Inc.,
`No. 2:13-cv-07245, 2015 WL 11089495 (C.D. Cal. May 5, 2015)
`(Ex. 1167)
`
`(cid:120) Transcript of the Deposition of Dr. Dariush Divsalar (Ex. 2039) and
`associated exhibits (Exs. 1157-1161)
`
`(cid:120) Declaration of Dr. Michael Mitzenmacher (Ex. 2004)
`
`(cid:120) DVB-S2 User Guidelines (Ex. 2009)
`
`(cid:120) Declaration of Dr. Hui Jin (Ex. 2020)
`
`(cid:120) Declaration of Dr. Dariush Divsalar (Ex. 2031)
`
`(cid:120) Curriculum Vitae of Dr. Dariush Divsalar (Ex. 2032)
`
`12.
`
`I am being compensated at my normal consulting rate of $950 per hour
`
`for my work.
`
`13. My compensation is not dependent on and in no way affects the
`
`substance of my statements in this Declaration.
`
`14.
`
`I have no financial interest in Petitioner. I similarly have no financial
`
`interest in the ’032 patent.
`
`15.
`
`I have reviewed the Petition and the declaration of Dr. Davis and agree
`
`with their explanation of why the instituted claims are invalid. I have also reviewed
`
`the institution decision and agree with the Board’s reasoning regarding the instituted
`
`claims. I have also read Caltech’s POPR, its POR and the declaration of Caltech’s
`
`
`
`5
`
`
`
`U.S. Patent No. 7,421,032
`Apple v. California Institute of Technology
`expert, Dr. Mitzenmacher, and disagree with their challenges to the invalidity of the
`
`instituted claims.
`
`16.
`
`I understand that after submitting his declaration in this case, Dr. Davis
`
`relocated to Europe pursuant to a Fulbright Global Scholar Award. I further
`
`understand that he is unavailable to work on the Reply due to these professional
`
`obligations. As explained below, in my opinion the challenged claims are invalid.
`
`II. LEGAL PRINCIPLES
`
`17.
`
`I have been informed that a claim is invalid as anticipated under
`
`Pre-AIA 35 U.S.C. § 102(a) if “the invention was known or used by others in this
`
`country, or patented or described in a printed publication in this or a foreign country,
`
`before the invention thereof by the applicant for patent.” I have also been informed
`
`that a claim is invalid as anticipated under Pre-AIA 35 U.S.C. § 102(b) if “the
`
`invention was patented or described in a printed publication in this or a foreign
`
`country or in public use or on sale in this country, more than one year prior to the
`
`date of the application for patent in the United States.” Further I have been informed
`
`that a claim is invalid as anticipated under Pre-AIA 35 U.S.C. § 102(e) if “the
`
`invention was described in . . . an application for patent, published under section
`
`122(b), by another filed in the United States before the invention by the applicant for
`
`patent . . . .” It is my understanding that for a claim to be anticipated, all of the
`
`
`
`6
`
`
`
`U.S. Patent No. 7,421,032
`Apple v. California Institute of Technology
`limitations must be present in a single prior art reference, either expressly or
`
`inherently.
`
`18.
`
`I have been informed that a claim is invalid as obvious under Pre-AIA
`
`35 U.S.C. § 103(a):
`
`if the differences between the subject matter sought to be patented and
`
`the prior art are such that the subject matter as a whole would have been
`
`obvious at the time the invention was made to a person having ordinary
`
`skill in the art to which [the] subject matter pertains.
`
`19.
`
`I understand that a claimed invention would have been obvious, and
`
`therefore not patentable, if the subject matter claimed would have been considered
`
`obvious to a person of ordinary skill in the art at the time that the invention was made.
`
`I understand that when there are known elements that perform in known ways and
`
`produce predictable results, the combination of those elements is probably obvious.
`
`Further, I understand that when there is a predictable variation and a person would
`
`see the benefit of making that variation, implementing that predictable variation is
`
`probably not patentable. I have also been informed that obviousness does not
`
`require absolute predictability of success, but that what does matter is whether the
`
`prior art gives direction as to what parameters are critical and which of many
`
`possible choices may be successful.
`
`
`
`7
`
`
`
`U.S. Patent No. 7,421,032
`Apple v. California Institute of Technology
`III. THE CHALLENGED CLAIMS ARE OBVIOUS
`
`A.
`
`20.
`
`Ping in view of MacKay, Divsalar, and Luby97
`
`I disagree with Caltech’s proposition that MacKay’s uneven column
`
`weights could be limited to columns in Ping corresponding to parity bits. POR at
`
`18-21. As an initial matter, MacKay standing alone discloses uneven weights for
`
`columns corresponding to information bits as required by the asserted claims.
`
`Moreover, a person of ordinary skill in the art (“POSA”) would have been motivated
`
`to apply MacKay’s uneven column weights to Ping’s Hd matrix. Therefore, the
`
`combination of Ping in view of MacKay meets those claim limitations.
`
`21. MacKay discloses profiles that correspond to parity check matrices. In
`
`MacKay’s profile 93y (reproduced below), some columns have weight nine and
`
`others have weight three.
`
`
`
`
`
`8
`
`
`
`U.S. Patent No. 7,421,032
`Apple v. California Institute of Technology
`Ex. 1102 at 1450. These weights can be calculated by summing the circled numbers
`
`in the profile. Empty areas of these profiles correspond to portions of a parity check
`
`matrix that contain all zeroes. For example, the far-right column contains two fours
`
`and a one. The weight of that column is the sum of those numbers, i.e., nine. All the
`
`other columns in profile 93y have weight three (i.e., all the other columns contain
`
`either three ones or a two and a one).
`
`22. Like profile 93y, MacKay’s profile 193y (reproduced below) also has
`
`weights of either nine or three.
`
`
`
`Id. at 1453. In profile 193y, the diagonal line in the right portion of the matrix
`
`represents a “one.” Therefore, most columns in that right portion contain a two and
`
`a one, via the diagonal, and sum to three. The one remaining column in the right
`
`portion contains only a three. In the left portion of the matrix, one column contains
`
`two fours and a one and thus has weight nine. The remaining columns have weight
`
`
`
`9
`
`
`
`U.S. Patent No. 7,421,032
`Apple v. California Institute of Technology
`three. In an actual parity check matrix corresponding to either of profiles 93y and
`
`193y, 1/12 of the columns would have weight nine and the others would have weight
`
`three.
`
`23. MacKay’s Figure 5 explains its encoding procedure.
`
`Id. at 1452. The matrix shown at the top of Figure 5 is a generalized form of the
`
`profiles shown in MacKay’s Figure 6. MacKay’s Figure 5 explains that the first K
`
`columns, all of which are to the left of the diagonal, correspond to information bits.
`
`Therefore, in MacKay’s profile 193y, some of the columns corresponding to
`
`
`
`
`
`10
`
`
`
`U.S. Patent No. 7,421,032
`Apple v. California Institute of Technology
`information bits have weight nine and the other columns corresponding to
`
`information bits have weight three. In other words, in profile 193y some
`
`information bits appear in nine subsets and others appear in three subsets.
`
`MacKay’s Figures 5 and 6 thus clearly teach that “information bits appear in a
`
`variable number of subsets.” Using those weightings in Ping – as further detailed
`
`below – results in information bits appearing in variable numbers of subsets (i.e.,
`
`either nine or three) as claimed.
`
`24. A POSA would have been motivated to use MacKay’s uneven column
`
`weights in Ping to obtain improved performance. As discussed by Dr. Davis, Ex.
`
`1104, ¶¶103-111, and detailed more fully below, this motivation would have come
`
`from several sources. First, MacKay teaches that codes with parity check matrices
`
`with uneven column weights can outperform their regular counterparts. Ex. 1102 at
`
`1449 (“The low-density parity check codes whose performance is closest to the
`
`Shannon limit are ‘Gallager Codes’ based on irregular graphs.” (emphasis added)).
`
`A POSA would therefore be motivated to use MacKay’s uneven column weights to
`
`improve the performance of Ping. Second, the codes described in the two references
`
`are naturally combinable. The encoding matrix disclosed in MacKay’s Figure 5 and
`
`Ping’s H matrix are of a similar structure. This is further demonstrated below with
`
`reference to the Tanner Graph representations of the codes. These similarities would
`
`
`
`11
`
`
`
`U.S. Patent No. 7,421,032
`Apple v. California Institute of Technology
`have motivated a POSA to add MacKay’s uneven column weights to Ping. Also, as
`
`I demonstrate below through coding simulations of Ping’s code and Ping’s code
`
`with MacKay’s uneven column weights, it would have been straightforward for a
`
`POSA to apply MacKay’s uneven column weights to Ping’s Hd matrix. Particularly
`
`in view of MacKay’s statement that “[t]he low-density parity check codes whose
`
`performance is closest to the Shannon limit are ‘Gallager Codes’ based on irregular
`
`graphs,” a POSA would have been encouraged to quickly test MacKay’s uneven
`
`column weights in Ping. Id. at 1449 (emphasis added).
`
`25. Caltech argues that in MacKay, the uneven column weightings could
`
`all correspond to parity bits, such that all columns corresponding to information bits
`
`had the same weight. POR at 18-21. This argument is incorrect for the reasons
`
`above. But, even if that were true, the combination of Ping in view of MacKay
`
`would disclose uneven weights for columns corresponding to information bits.
`
`Ping clearly teaches that all columns in its Hd matrix represent information bits. The
`
`weight of a column of the Hd matrix, i.e., the number of ones appearing in that
`
`column, equals the number of subsets in which the information bit appears.
`
`26. A POSA would have been motivated to use MacKay’s uneven column
`
`weights in Ping’s Hd matrix (or outer coder) to improve the performance of Ping’s
`
`code for the reasons Dr. Davis identified, Ex. 1104, ¶¶103-111, and as noted above
`
`
`
`12
`
`
`
`U.S. Patent No. 7,421,032
`Apple v. California Institute of Technology
`and discussed more fully below. Doing so would necessarily result in “information
`
`bits [appearing] in a variable number of subsets,” even if all of MacKay’s uneven
`
`column weights corresponded to parity bits, because using MacKay’s uneven
`
`column weights in Ping’s Hd matrix would result in some information bits appearing
`
`in more subsets than others as claimed.
`
`27.
`
`In other words, applying MacKay’s fundamental teaching – that use of
`
`parity check matrices with uneven column weights can outperform codes with
`
`evenly weighted parity check matrices – to Ping’s Hd matrix causes information bits
`
`to “appear in a variable number of subsets.”
`
`28.
`
`I disagree with Caltech’s position that Ping’s Hd matrix is not a
`
`low-density generator matrix. A POSA would understand that the Hd matrix meets
`
`the definition of a generator matrix. Ping discloses two stages of encoding. In the
`
`first stage, summations are computed where each summation equals a row of Hd
`
`times the vector of information bits, or, in other words, the vector of Ping’s
`
`summations equals Hd times the vector of input bits. Hd therefore meets the
`
`definition of a generator matrix. Furthermore, the vast majority of entries of Hd are
`
`zeroes. Thus, Hd is also low density. It is a low-density generator matrix.
`
`29. Caltech argues that it would not have been obvious for a POSA to
`
`modify Ping to be a non-systematic code. POR at 22. I disagree. Systematic and
`
`
`
`13
`
`
`
`U.S. Patent No. 7,421,032
`Apple v. California Institute of Technology
`non-systematic codes were both well-known long before the ’032 patent. On the
`
`encode side, making a code non-systematic simply involves not transmitting the
`
`information bits. On the decode side, it would be obvious to a POSA how to modify
`
`the decoder to take into account the fact that the information bits were not sent.
`
`Decoders operate by iteratively combining messages that represent intermediate
`
`calculations with numerical values that represent evidence derived from the channel
`
`output pertaining to the values of transmitted bits. The latter are usually stored in the
`
`form of log-likelihood ratios and they are combined with messages using addition.
`
`If an information bit is not transmitted, as in the non-systematic case, there is no
`
`evidence at the channel output pertaining to either of its values, so the corresponding
`
`log-likelihood ratio is zero. To take this into account, the decoder is modified so that
`
`when messages are combined using addition, the log-likelihood ratio corresponding
`
`to a systematic bit is not included in the addition. This has the same effect as adding
`
`zero. For some decoders, the numerical values that represent evidence derived from
`
`the channel output pertaining to the values of transmitted bits may be stored in the
`
`form of likelihood ratios, instead of log-likelihood ratios, and they are combined
`
`with messages using multiplication. In these cases, the decoder is modified so that
`
`when messages are combined using multiplication, the likelihood ratio
`
`corresponding to a systematic bit is not included in the multiplication. This has the
`
`
`
`14
`
`
`
`U.S. Patent No. 7,421,032
`Apple v. California Institute of Technology
`same effect as multiplying by one. These modifications would have been known
`
`and obvious to a POSA. Thus, implementing a combination of Ping, MacKay,
`
`Divsalar, and Luby97 non-systematic would have been obvious.
`
`30.
`
`I disagree with Caltech’s position that a POSA would not have been
`
`motivated to apply MacKay’s irregularity to Ping because Ping is already irregular.
`
`POR at 24-26. Caltech presumes that a POSA would compare MacKay’s irregular
`
`matrices to Ping’s complete H matrix. This is a false comparison. The proper
`
`comparison is between MacKay’s irregular matrices and Ping’s Hd matrix (in which
`
`all columns have the same weight). Ping’s H matrix is a combination of two
`
`sub-matrices, Hd and Hp, such that H = [Hp, Hd]. Ex. 1103 at 38. Hp can have only
`
`a single form: an accumulator. An accumulator can be implemented simply and
`
`cheaply. A POSA would not have been motivated to modify Hp because, as even
`
`Caltech notes, it has only a single form, and because doing so would have
`
`complicated a simple encoder. POR at 25 (“Hd has a specific structure that guides
`
`its construction, but is not limited to a single form like Hp” (emphasis added).)
`
`Therefore, a POSA who wanted to obtain the benefit of MacKay’s irregularity in
`
`Ping would have incorporated MacKay’s uneven column weights into (regular) Hd.
`
`Doing so would have been simple, and a POSA would have been motivated to do so
`
`
`
`15
`
`
`
`U.S. Patent No. 7,421,032
`Apple v. California Institute of Technology
`to obtain the benefit of MacKay’s irregularity (which MacKay itself instructs will
`
`improve code performance) in Ping.
`
`31. Caltech argued that a POSA would not have been motivated to use
`
`MacKay’s irregularity in Ping because Ping is even more irregular than MacKay. Id.
`
`at 26. I disagree. Caltech bases its position on a scenario that is not disclosed in
`
`Ping. Id. Specifically, Caltech presents an example in which t=9. In that case, half
`
`the columns in the parity check matrix would have weight 9. In the other half, all but
`
`one would have weight 2 and the one remaining column would have weight 1. Id.
`
`The non-zero differences in column weights for this matrix are either 7 or 8 (i.e., 9
`
`minus 2 or 9 minus 1). In his computation of “variance,” Caltech’s expert Dr.
`
`Mitzenmacher used only this example matrix with t=9. Ex. 2038 at 330:10-18,
`
`331:14-21.
`
`32. But, Ping does not disclose a matrix with t=9. Instead, Ping discloses a
`
`matrix with t=4. Ex. 1103 at 39. In this matrix, half of Ping’s columns have weight
`
`4 and, in the other half, all but one of the columns have weight 2 and the one
`
`remaining column has weight 1. In this example, the non-zero differences in column
`
`weights are either 2 or 3 (i.e., 4 minus 2 or 4 minus 1). In MacKay’s matrices, where
`
`the weights are either 9 or 3, the non-zero difference between column weights is 6
`
`(i.e., 9-3). Thus, the difference in column weights in MacKay’s matrix (6) is twice
`
`
`
`16
`
`
`
`U.S. Patent No. 7,421,032
`Apple v. California Institute of Technology
`as large as any difference in Ping’s explicitly disclosed example and is three times as
`
`large as the most common difference. In other words, Ping is not more irregular than
`
`MacKay. Nothing about Ping’s code would have dissuaded a POSA from wanting
`
`to use MacKay’s uneven column weights in Ping.
`
`33. Also, a POSA would not have considered Ping’s code to be irregular.
`
`Accumulators were well known prior to discussion of “irregularity” in the coding
`
`community and POSAs did not, and do not, consider accumulators to be irregular.
`
`Moreover, Ping’s Hd matrix is quite regular as even Dr. Mitzenmacher concedes. Ex.
`
`2004 ¶62. A POSA applying MacKay’s teaching to Ping’s code would thus
`
`naturally apply MacKay’s irregular column weights to Ping’s Hd matrix, and doing
`
`so would cause information bits to “appear in a variable number of subsets.” That is
`
`the same as some information bits contributing to more parity bits than others.
`
`When combined with Divsalar, that results in irregular repetition of information bits
`
`exactly as claimed in the ’032 patent for the reasons demonstrated above.
`
`34. Parity check matrices and Tanner graphs are different ways of
`
`representing the same codes, and both representations were understood by POSAs in
`
`
`
`17
`
`
`
`U.S. Patent No. 7,421,032
`Apple v. California Institute of Technology
`1999.1 Ping and MacKay both describe their codes in terms of parity check matrices.
`
`The drawings below show Tanner graphs corresponding to Ping’s code and a code
`
`described in MacKay’s profile 93y.
`
`
`
`
`
`Ex. 1148
`
`Ex. 1149
`
`
`
`1 I disagree with Dr. Divsalar’s suggestion that Tanner graphs were innovative at the
`
`time of the claimed invention. Ex. 2031, ¶15. Tanner graphs were a standard
`
`technique for representing codes. In fact, I used such graphs in my own paper (Ex.
`
`1110) to represent the irregular code I later suggested applying to the Divsalar
`
`reference.
`
`
`
`18
`
`
`
`U.S. Patent No. 7,421,032
`Apple v. California Institute of Technology
`35. As shown, both Ping’s code and MacKay’s code connect message
`
`nodes (open circles on the left) to check nodes (grey circles on the right) via a
`
`random permutation. Ping’s coder includes the extra step shown at the right side of
`
`the Tanner graph, which corresponds to Ping’s accumulating Hp matrix, or outer
`
`coder. The left sides of the Tanner graphs are similar, i.e., they both include
`
`message nodes and a random permutation. The difference is that Ping’s message
`
`nodes all have degree four (i.e., four edges intersect each node), while MacKay’s
`
`message nodes have different degrees (i.e., some nodes have degree three and others
`
`have degree nine). It would have been obvious for a POSA to use MacKay’s
`
`irregular degree profile in Ping by making the degree of Ping’s d nodes irregular.
`
`Making the degree of the d nodes in Ping’s Tanner graph uneven corresponds
`
`exactly to making the column weights of Hd uneven. As shown by the above Tanner
`
`graphs, Ping’s and MacKay’s codes are similar and it would have been easy for a
`
`POSA to use MacKay’s irregularity, or uneven column weights, in Ping.
`
`36. Caltech has also argued that Ping’s Hd matrix does not correspond to an
`
`outer code and that Ping’s encoding is not performed in two steps. POR at 33-35. I
`
`disagree. A POSA would have understood Ping to disclose two stages of encoding,
`
`an outer coder followed by an inner coder. Indeed, Ping says so explicitly by stating
`
`that its H matrix is a combination of two sub-matrices, Hd and Hp, such that H = [Hp,
`
`
`
`19
`
`
`
`U.S. Patent No. 7,421,032
`Apple v. California Institute of Technology
`Hd]. Ex. 1103 at 38. Equation 4 from Ping is shown below and clearly shows that
`
`parity bit pi is the summation modulo 2 (XOR) of two components, the first being
`
`the previous parity bit pi-1 and the second being a summation modulo 2 of a subset of
`
`information bits. A POSA would naturally interpret this equation as having two
`
`coding steps, the first being an outer code that determines the summation of a subset
`
`of information bits modulo 2, and the second being an inner code that determines the
`
`parity bit as the XOR of the previous parity bit and an output from the outer code.
`
`
`
`The equation above from Ping stands in contrast to an equation written in a way so
`
`that there are less clearly two separate components. I have written the equation in
`
`such a way below:
`
`pi = hi1 d1 + hi2 d2 + pi-1 + hi3 d3 + …
`
`Here, the component pi-1 is mixed in with the others. However, even in this case,
`
`upon examining the equation, a POSA would quickly see that there are two different
`
`forms, one containing a p and the other containing h’s and d’s. A POSA would think
`
`to group these into two components and implement the determination of pi using two
`
`codes, an outer code and an inner code. So, even in the case of an equation that less
`
`
`
`20
`
`
`
`U.S. Patent No. 7,421,032
`Apple v. California Institute of Technology
`directly shows an outer code and an inner code, it would still have been obvious to a
`
`POSA to implement Ping with an outer code and an inner code.
`
`37. Furthermore, in Ex. 1103 at 38, Ping’s two-step encoding, as modified
`
`to use Divsalar’s repetition and MacKay’s irregularity, is shown in the below block
`
`diagram.
`
`
`
`Exhibit 1172
`
`
`
`38. As shown, a repeater repeats incoming information bits irregularly and
`
`stores the irregularly repeated bits in a shift-register. For example, bit i1 is shown as
`
`having been repeated three times and bit i2 is shown as having been repeated nine
`
`times. Other information bits are also repeated, e.g., such that each information bit
`
`is repeated either three or nine times. Once the information bits have all been
`
`repeated, XOR gates combine them to produce new combined bits, which are stored
`
`
`
`21
`
`
`
`U.S. Patent No. 7,421,032
`Apple v. California Institute of Technology
`in registers shown highlighted yellow, pink and purple. In this example, each such
`
`bit equals the sum of two repeated information bits. This matches Ping’s example of
`
`a rate 1/3 code, in which each new bit is the sum of exactly two information bits.
`
`(Petition at 56.) The ones in each row of Hd determine which information bits are
`
`summed to produce a particular bit, e.g., with the top row of Hd corresponding to the
`
`XOR gate that feeds the yellow register and the last row of Hd corresponding to the
`
`XOR gate that feeds the purple register. If a row of Hd had more than two ones, such
`
`that more than two bits were summed to produce a new combined bit, the
`
`corresponding XOR gate would be generalized to a multi-bit mod-2 adder.
`
`39.
`
`In Exhibit 1172, each bit of the shift-register drives only a single gate,
`
`which would have been an obvious choice both due to the ease of implementing
`
`repeating with Divsalar’s repeater and to avoid having any of the shift register
`
`outputs driving more inputs than it was capable of driving. Once the new combined
`
`bits have been produced, they are shifted into the inner coder, which is an
`
`accumulator, and which produces the final output parity bits. The recursive nature
`
`
`
`22
`
`
`
`U.S. Patent No. 7,421,032
`Apple v. California Institute of Technology
`of Ping’s equations would have encouraged a POSA to implement Ping as an outer
`
`coder followed by an inner coder as shown in Exhibit 1172.2
`
`
`
`2 Exhibit 1171 (discussed in Petitioner’s Reply for IPR2017-297, where it is
`
`identified as Exhibit 1048) depicts another way to incorporate MacKay’s
`
`irregularity in Ping. The implementations shown in Exhibit 1171 and Exhibit 1172
`
`both would have been obvious. The implementation shown in Exhibit 1171 can be
`
`flexibly programmed to implement all possible versions of Hd. The implementation
`
`shown in Exhibit 1172 implements only one specific version of Hd, i.e., because the
`
`combinations used to form the outer coder parity bits are hard-wired into
`
`connections between XOR gates and the shift register. The Exhibit 1172
`
`implementation is therefore less flexible, but is also simpler. A POSA would have
`
`found either implementation obvious and would have selected one or the other, or
`
`some other obvious variant, suitable for an application, e.g., selecting the
`
`implementation shown in Exhibit 1171 for a system in which it was important for the
`
`encoder to be capable of encoding according to several different versi