`
`
`
`
`
`
`
`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-00219
`Patent No. 7,116,710
`_____________________________
`
`
`DECLARATION OF DR. R. MICHAEL TANNER
`
`
`
`CALTECH - EXHIBIT 2001
`Apple Inc. v. California Institute of Technology
`IPR2017-00219
`
`
`
`I, Robert Michael Tanner, declare as follows:
`
`I.
`
`QUALIFICATIONS
`
`1.
`
`I am Chief Academic Counsel at the Association of Public and Land-
`
`grant Universities (APLU), in which position I have served since my retirement in
`
`2015. I had previously served as APLU’s Vice President for Academic Affairs and
`
`Chief Academic Officer since 2011.
`
`2.
`
`Prior to my work at APLU, I taught as a professor of Computer
`
`Science and Electrical Engineering at the University of Illinois at Chicago and at
`
`the University of California, Santa Cruz. I also served in Vice Chancellor positions
`
`at both institutions, as well as other administrative roles. I have also been a visiting
`
`professor at institutions including the California Institute of Technology
`
`(“Caltech”), the Massachusetts Institute of Technology, and Stanford University,
`
`and I worked in the 1980’s as a consultant to companies in the disk and
`
`telecommunication industry.
`
`3.
`
`In 1981, I authored a paper titled “A Recursive Approach to Low
`
`Complexity Codes,” in which I proposed a new method of graphically representing
`
`the constraint equations governing the codeword elements in sparse check matrix
`
`codes. This graphical representation, called a “Tanner graph,” is named after me.
`
`My contributions to the field of coding have led me to be recognized as the founder
`
`of the subfield “codes on graphs.”
`
`1
`
`
`
`4. My professional research interests have concentrated on topics
`
`involving information and communication theory, and on the theory of algorithms
`
`and computational complexity. Significant areas on which I have focused have
`
`included: a) development of highly efficient error-correcting codes that are
`
`amenable to decoding with ultra-concurrent iterative algorithms; and b) the
`
`theoretical and algorithmic reconciliation of block and convolutional codes.
`
`5.
`
`I received a Ph.D. in Electrical Engineering with Specialization in
`
`Information Theory from Stanford in 1971. I also hold a Master’s Degree from
`
`Stanford in Electrical Engineering and a Bachelor’s Degree from Stanford in
`
`Electrical Engineering, which I received in 1967 and 1966, respectively.
`
`6.
`
`A copy of my Curriculum Vitae, provided as Exhibit 2002, contains
`
`further details on my education, experience, publications, patents, and other
`
`qualifications to render an expert opinion in this matter.
`
`II.
`
`SCOPE OF WORK
`
`7.
`
`I was asked by counsel for Caltech in the case IPR2017-00219 to
`
`review U.S. Patent No. 7,116,710 (“the ’710 patent”) and related applications,
`
`including Provisional Application No. 60/205,095 (“the ’095 provisional
`
`application”). I receive $400 per hour for my services. No part of my compensation
`
`is dependent on my opinions or on the outcome of this proceeding.
`
`2
`
`
`
`8.
`
`I was also asked by counsel for Caltech to review the papers
`
`“Analysis of Low Density Codes and Improved Designs Using Irregular Graphs,”
`
`authored by Michael G. Luby et al. (“Luby,” Ex. 1204) and “Coding Theorems for
`
`‘Turbo-Like’ Codes” by Dariush Divsalar et al (“Divsalar,” Ex. 1203).
`
`9.
`
`I was further asked to provide my understanding of whether an
`
`irregular graph as discussed in Luby indicates that the underlying code includes
`
`irregular repetition of data elements.
`
`10. Luby discloses decoding, but does not describe encoding. Luby does
`
`not disclose encoding involving repetition of information bits, much less encoding
`
`with irregular repetition as in the ’710 patent claims. Divsalar discloses a coding
`
`scheme with regular repetition. As described in further detail below, a regular
`
`repeat-accumulate code as disclosed by Divsalar can be represented by an irregular
`
`graph, as defined by Luby, without any changes to the underlying code.
`
`III. OVERVIEW OF IRREGULAR CODES IN LUBY AND IN THE ’710 PATENT
`
`11. The ’710 patent discloses a serially-concatenated interleaved
`
`convolutional code with an outer code and an inner code. (Ex. 1201, Title,
`
`Abstract.) The outer code irregularly repeats bits in a data block, which are then
`
`scrambled by a permuter. (Id. at Abstract, 1:58-67.)
`
`12. The specification of the ’710 patent explains that the outer coder may
`
`be irregular, meaning that it could be a repeater that repeats the bits in a block a
`
`3
`
`
`
`particular number of times, and repeats bits in another block a different number of
`
`times. (See id. at 2:48-58.)
`
`13. The scrambled, or interleaved, bits are then subjected to a second
`
`encoding, which includes one or more accumulators that perform modulo two
`
`addition. (Id. at 2:1-5, 2:65-3:17.)
`
`14. Modulo two addition is an exclusive-or operation, often called XOR,
`
`and denoted with the symbol ⊕. The modulo-two addition of two bits is shown
`
`below:
`
`
`
`A
`0
`0
`1
`1
`
`B
`0
`1
`0
`1
`
`A⊕B
`0
`1
`1
`0
`
`15. As indicated above, the modulo-two addition of a value with itself is
`
`0.
`
`16. The ’710 patent defines an accumulator as a block whose input block
`
`[x1, x2, … , xn] and output block [y1, . . . , yn] are related by the following
`
`formula:
`
`y1 = x1
`
`y2 = x1⊕x2
`
`y3 = x1⊕x2⊕x3
`
`4
`
`
`
`17. This relationship can be simplified as follows:
`
`. . .
`
`y1 = x1
`
`y2 = y1⊕ x2
`
`y3 = y2⊕ x3
`
`. . .
`
`18. A code may be represented as a set of parity checks, which may in
`
`turn be represented in a bipartite graph known as a Tanner graph, which I
`
`introduced as a graphical representation of the constraint equations governing
`
`codeword elements in sparse check matrix codes, including low density parity
`
`check (“LDPC”) codes.
`
`19. A Tanner graph contains multiple sets of nodes, with message nodes
`
`shown as open circles and check nodes shown as filled circles. In a Tanner graph
`
`of a repeat-accumulate code, such as the one from the ’095 provisional application
`
`shown in Section IV below, open circles on the left side represent information
`
`nodes, or information bits, filled circles near the middle represent check nodes, and
`
`open circles on the far right represent parity nodes, or parity bits. Each check node
`
`represents a constraint on the information and parity nodes to which it is
`
`connected, such that the modulo-two addition of the bit values of the information
`
`and parity nodes connected to a particular check node must equal zero.
`
`5
`
`
`
`20. The Luby reference discusses bipartite graphs which contain only two
`
`sets of nodes. Nodes on the left are referred to as “message” nodes, while nodes on
`
`the right are referred to as “check” nodes. Based on my understanding of Luby,
`
`Luby’s reference to “message” nodes is not the same thing as the “information”
`
`nodes I discussed above. For instance, Luby discusses a rate 1/2 code with 16,000
`
`message bits and 8,000 check bits. (Ex. 1204 at 256.) Because the code rate is 1/2,
`
`the 16,000 message bits include 8,000 information bits and 8,000 parity bits. Thus,
`
`Luby’s “message” nodes represent both information bits and parity bits. An
`
`irregular bipartite graph, as Luby describes it, does not distinguish irregularity
`
`between information node edges and parity node edges from irregularity within the
`
`group of information node edges. (See id. at 250, 253 (defining irregularity as
`
`having varying degrees of message nodes)).
`
`21. The five authors of the Luby reference also filed U.S. Patent No.
`
`6,081,909 (“the Luby ’909 patent”). The Luby ’909 patent defines irregular
`
`graphing in the same manner described above, except check nodes are not shown
`
`and redundant parity node values are described as an explicit XOR sum of
`
`connected values. (See, e.g., Ex. 2003, Fig. 17, col. 5:45-47 (“Fig. 17 depicts an
`
`irregular graph of the edges between node layers….”), 17:61-18:15.)
`
`22.
`
`In a Tanner graph representing a code with irregular repetition, the
`
`information nodes will have variable degrees—i.e., not all information nodes will
`
`6
`
`
`
`have the same number of edges connected to them. As I discuss below, the
`
`“irregularity” in an irregular graph as Luby describes it does not necessarily
`
`represent irregular repetition in a code.
`
`IV. TANNER GRAPH REPRESENTATION OF DIVSALAR’S RA CODES SHOWS
`LUBY’S “IRREGULARITY”
`
`23. As an example, a Tanner graph for a regular repeat and accumulate
`
`code is shown below. I understand that this graph was presented in the ’095
`
`provisional application. This is a depiction of the same RA code shown at page 39
`
`of the Petition, which was taken from Dr. Khandekar’s thesis. The open circles on
`
`the left represent information nodes and each open circle on the right is a parity
`
`node with a value determined by a step in the accumulation process. The filled
`
`circles in the middle are check nodes representing constraint equations between the
`
`information and parity nodes. The constraint equations of the check nodes cause
`
`each of the parity nodes to have a value equal to the modulo-two addition of the
`
`value of the open circle immediately above the parity node (considered zero when
`
`no such open circle exists) and the information node connected to the filled circle
`
`immediately above and to the left of the parity node.
`
`7
`
`
`
`RA Code from ’095 Provisional Application, page 6
`
`
`
`24.
`
`In this graph, each information node on the left has three edges
`
`connected to it. Each of the open circle parity nodes on the right side of the graph
`
`has only two edges connected to it, which is a different number of edges than the
`
`information nodes on the left have. Differences between the number of information
`
`node edges and the number of parity node edges is not the same thing as irregular
`
`repetition. Rather, the uniform number of edges connected to the information
`
`nodes shows that the code has regular repetition.
`
`25. The Tanner graph shown above may also be redrawn so that all of the
`
`open circles—i.e., the information nodes and the parity nodes—are shown together
`
`on the left side of the graph, while all of the filled circles representing check nodes
`
`are shown on the right side. Such a graph would depict a bipartite graph with only
`
`two sets of nodes. Looking at the Tanner graph above, the parity nodes can be
`
`8
`
`
`
`shown on the left side of the graph with the information nodes, yet still retain their
`
`respective connections with the check nodes. In this case, the parity nodes will
`
`have a different number of edges than the information nodes. Although the
`
`representation would be redrawn to show an irregular graph, the underlying code
`
`with regular repetition does not change, and the graph does not represent an
`
`irregular repetition code. Without an explicit distinction between information and
`
`parity nodes, it would be impossible to determine from the graph itself whether the
`
`code corresponds to a code that uses irregular repetition of information bits in the
`
`sense of the ’710 patent.
`
`26. The Tanner graph shown above corresponds to a regular repeat-
`
`accumulate code as disclosed by Divsalar. Figure 3 of Divsalar shows a regular
`
`repeat-accumulate code in which a set of information bits is repeated q times,
`
`permuted, and then accumulated. (Ex. 1203 at 5). Divsalar also discloses that q
`
`should be at least 3, because “an RA code can have word error probability
`
`interleaving gain only if q ≥ 3.” (Id. at 6). For example, Divsalar discloses the
`
`cases of q = 3 and q = 4. (Id. at 9).
`
`27. The Tanner graph of a repeat-accumulate code with q-fold repetition
`
`has information bits with degree q and parity bits of degree 2 (with the final parity
`
`bit having degree 1). The Tanner graph from page 6 of the ’095 Provisional
`
`Application is one example, with q = 3 for a pair of information bits. The general
`
`9
`
`
`
`structure of a regular repeat-accumulate code with q-fold repetition includes
`
`information nodes with degree q and parity nodes with degree 2 or 1. Because each
`
`information node has degree q (with q ≥ 3) and each parity node has degree 2 or 1,
`
`every RA code is an “irregular” code, as Luby defines the term.
`
`28. The Tanner graph above can also be remapped in order to show the
`
`direct relationship between the information nodes on the left and the parity nodes
`
`on the right, producing an irregular graph. This can be done by labeling the
`
`information nodes ‘A’ and ‘B,’ respectively, and writing out the modulo-two
`
`addition of the accumulator step as follows, as I have done below:
`
`
`
`Tanner graph of RA Code showing modulo-two addition of information bits
`that generate parity bits
`
`
`
`
`
`10
`
`
`
`
` The first parity node value is simply the value of the information
`
`29.
`
`node ‘B.’ The second parity node value is the modulo-two sum of the values of the
`
`information node ‘A’ and the first parity node, which we know from the previous
`
`step is ‘B.’ The third parity node value is the modulo-two sum of the information
`
`node ‘B’ value and that of the second parity node, ‘A’⊕’B’, which is
`
`‘B’⊕(‘A’⊕‘B’) = ‘B’⊕‘B’⊕‘A’ = ‘0’⊕‘A’ = ‘A’. The remaining parity nodes
`
`values can be calculated in a similar manner.
`
`30. Because each parity node represents a modulo-two addition of the
`
`values of some subset of the information nodes, edges can be drawn to directly
`
`connect each parity bit with the information bits included in that parity bit sum, as
`
`I have shown below:
`
`11
`
`
`
`Example graph of an RA code remapped according to modulo-2 addition of
`information bits
`
`
`
`
`In the remapped graph above, information node ‘A’ now has four
`
`31.
`
`edges, while information node ‘B’ has only three edges. Because the information
`
`nodes have varying degrees, the graph is irregular. But the underlying code, which
`
`did not involve irregular repetition of information bits, has not changed. Thus, an
`
`irregular bipartite graph as discussed in Luby does not necessarily represent a code
`
`with irregular repetition, as recited in the claims of the ’710 patent.
`
`V. CONCLUDING STATEMENTS
`
`32.
`
`In signing this declaration, I understand that the declaration will be
`
`files as evidence in a contested case before the Patent Trial and Appeal Board of
`
`the United States Patent and Trademark Office. I acknowledge that I may be
`
`12
`
`
`
`subject to cross-examination in this case and that cross-examination will take place
`
`within the United States. If cross-examination is required of me, I will appear for
`
`cross-examination within the United States during the time allotted for cross-
`
`examination.
`
`33.
`
`I declare that all statements made herein of my knowledge are true,
`
`and that all statements made on information and belief are believed to be true, and
`
`that these statements were made with the knowledge that willful false statements
`
`and the like so made are punishable by fine or imprisonment, or both, under
`
`Section 1001 of Title 18 of the United States Code.
`
`
`
`Dated: March 31, 2017
`
`
`
`
`
`By: / R. Michael Tanner /
`
`R. Michael Tanner, Ph.D.
`
`13
`
`
Accessing this document will incur an additional charge of $.
After purchase, you can access this document again without charge.
Accept $ Charge
Still Working On It
This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.
Give it another minute or two to complete, and then try the refresh button.
A few More Minutes ... Still Working
It can take up to 5 minutes for us to download a document if the court servers are running slowly.
Thank you for your continued patience.
This document could not be displayed.
We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.
Your account does not support viewing this document.
You need a Paid Account to view this document. Click here to change your account type.
Your account does not support viewing this document.
Set your membership
status to view this document.
With a Docket Alarm membership, you'll
get a whole lot more, including:
- Up-to-date information for this case.
- Email alerts whenever there is an update.
- Full text search for other cases.
- Get email alerts whenever a new case matches your search.
One Moment Please
The filing “” is large (MB) and is being downloaded.
Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.
Your document is on its way!
If you do not receive the document in five minutes, contact support at support@docketalarm.com.
Sealed Document
We are unable to display this document, it may be under a court ordered seal.
If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.
Access Government Site
