`571.272.7822
`
`IPR2015-00059; Paper 18
`Entered: April 27, 2015
`
`UNITED STATES PATENT AND TRADEMARK OFFICE
`_______________
`BEFORE THE PATENT TRIAL AND APPEAL BOARD
`_______________
`HUGHES NETWORK SYSTEMS, LLC and
`HUGHES COMMUNICATIONS, INC.,
`Petitioner,
`
`v.
`
`CALIFORNIA INSTITUTE OF TECHNOLOGY,
`Patent Owner.
`_______________
`
`Case IPR2015-00059
`Patent 7,916,781 B2
`_______________
`
`Before KALYAN K. DESHPANDE, GLENN J. PERRY, and
`TREVOR M. JEFFERSON, Administrative Patent Judges.
`
`PERRY, Administrative Patent Judge.
`
`DECISION
`Institution of Inter Partes Review
`37 C.F.R. § 42.108
`
`Apple 1214
`
`
`
`IPR2015-00059
`Patent 7,916,781 B2
`
`INTRODUCTION
`
`A. Background
`Hughes Network Systems, LLC and Hughes Communications, Inc.1
`(collectively “Petitioner”) filed a Petition requesting an inter partes review
`of claims 1–7, 13–16, and 19 of U.S. Patent No. 7,916,781 B2 (Ex. 1005,
`“the ’781 patent”). Paper 4 (“Pet.”)2. California Institute of Technology
`(“Patent Owner”) timely filed a Preliminary Response. Paper 13 (“Prelim.
`Resp.”). We have authority to determine whether to institute an inter partes
`review under 35 U.S.C. § 314; 37 C.F.R. § 42.4(a). Upon consideration of
`the Petition and the Preliminary Response, we determine that Petitioner has
`established a reasonable likelihood of prevailing as to claims 1 and 2 as
`challenged in the Petition. Accordingly, we institute an inter partes review
`of claims 1 and 2 of the ’781 patent.
`
`B. Related Proceedings
`Petitioner states that the ’781 Patent (Ex. 1005) is involved in a
`pending lawsuit titled California Institute of Technology v. Hughes
`Communications, Inc., No. 13-CV-07245 (CACD) (“the Lawsuit”). See Ex.
`1015. The Lawsuit includes the following patents: (i) U.S. Patent No.
`7,116,710; (ii) U.S. Patent No. 7,421,032; (iii) U.S. Patent No. 7,916,781;
`and (iv) U.S. Patent No. 8,284,833.
`
`
`1 EchoStar Corporation is named in the Petition as the parent of Hughes
`Satellite Systems Corporation, which is the parent of Hughes
`Communications, Inc. Pet. 1. Both EchoStar Corporation and Hughes
`Satellite Systems Corporation are real parties in interest. The record is still
`being developed as to whether Dish is an unnamed real party in interest.
`2 “Pet.” refers to the corrected petition filed October 30, 2014 (Paper 4).
`
`2
`
`
`
`IPR2015-00059
`Patent 7,916,781 B2
`Petitioner filed additional Petitions for Inter Partes review challenging
`other patents of the patent family. Pet. 1.
`
`THE ’781 PATENT
`
`A. Background and Context
`We understand that error correcting codes are used to communicate
`information across a noisy communication channel. They enable the
`recovery of a transmitted message that may have become distorted by
`channel noise. To prepare a message for transmission, it is parsed into
`groups of message bits that are “encoded” into “codewords” by adding
`redundant information to them.3 The codewords are transmitted over the
`communication channel and are received at another location, where the
`codewords are “decoded” into the original message. No single coding
`scheme is optimal for all communication channels. Also, there are design
`tradeoffs between the use of complex codes, which permit better error
`correction, and less complex codes, which are easier to decode. This has led
`to the development of many different encoding/decoding schemes. The ’781
`patent describes one such scheme.
`
`B. The ’781 Patent Invention
`The ’781 patent describes the serial concatenation of interleaved
`convolutional codes forming turbo-like codes. Ex. 1005, Title. It explains
`some of the prior art with reference to its Figure 1, reproduced below.
`
`
`3 For example, a message bits “10011” may be encoded into a codeword
`“100111” by adding a “parity” bit “1” to the original message.
`
`3
`
`
`
`IPR2015-00059
`Patent 7,916,781 B2
`
`Figure 1 is a schematic diagram of a prior “turbo code” system. Ex. 1005,
`2:20–21. The ’781 patent specification describes Figure 1 as follows:
`
`A block of k information bits is input directly to a first coder
`102. A k bit interleaver 106 also receives the k bits and
`interleaves them prior to applying them to a second coder 104.
`The second coder produces an output that has more bits than its
`input, that is, it is a coder with rate that is less than 1. The
`coders 102, 104 are typically recursive convolutional coders.
`Three different items are sent over the channel 150: the original
`k bits, first encoded bits 110, and second encoded bits 112. At
`the decoding end, two decoders are used: a first constituent
`decoder 160 and a second constituent decoder 162. Each
`receives both the original k bits, and one of the encoded
`portions 110, 112. Each decoder sends likelihood estimates of
`the decoded bits to the other decoders. The estimates are used to
`decode the uncoded information bits as corrupted by the noisy
`channel.
`Ex. 1005, 1:44–60.
`A coder 200, according to a first embodiment of the invention, is
`described with respect to Figure 2, reproduced below.
`
`4
`
`
`
`IPR2015-00059
`Patent 7,916,781 B2
`
`Figure 2 of the ’781 patent is a schematic diagram of coder 200.
`
`The coder 200 may include an outer coder 202, an interleaver
`204, and inner coder 206. . . . The outer coder 202 receives the
`uncoded data [that] may be partitioned into blocks of fixed size,
`[e.g.] k bits. The outer coder may be an (n,k) binary linear
`block coder, where n>k. The coder accepts as input a block u
`of k data bits and produces an output block v of n data bits. The
`mathematical relationship between u and v is v=T0u, where T0
`is an nxk matrix, and the rate4 of the coder is k/n.
`
`The rate of the coder may be irregular, that is, the value of T0 is
`not constant, and may differ for sub-blocks of bits in the data
`block. In an embodiment, the outer coder 202 is a repeater that
`repeats the k bits in a block a number of times q to produce a
`block with n bits, where n=qk. Since the repeater has an
`irregular output, different bits in the block may be repeated a
`different number of times. For example, a fraction of the bits in
`the block may be repeated two times, a fraction of bits may be
`repeated three times, and the remainder of bits may be repeated
`four times. These fractions define a degree sequence or degree
`profile, of the code.
`
`The inner coder 206 may be a linear rate-1 coder, which means
`that the n-bit output block x can be written as x=TIw, where TI
`is a nonsingular nxn matrix. The inner coder 210 can have a
`
`
`4 The “rate” of an encoder refers to the ratio of the number of input bits to
`the number of resulting encoded output bits related to those input bits.
`
`5
`
`
`
`IPR2015-00059
`Patent 7,916,781 B2
`rate that is close to 1, e.g., within 50%, more preferably 10%
`and perhaps even more preferably within 1% of 1.
`
`Ex. 1005, 2:40–3:2. Codes characterized by a regular repeat of message bits
`into a resulting codeword are referred to as “regular repeat,” whereas codes
`characterized by irregular repeat of message bits into a resulting codeword
`are referred to as “irregular repeat.” The second (“inner”) encoder 206
`performs an “accumulate” function. Thus, the two step encoding process
`illustrated in Figure 2, including a first encoding (“outer encoding”)
`followed by a second encoding (“inner encoding”), results in either a
`“regular repeat accumulate” (“RRA”) code or an “irregular repeat
`accumulate” (“IRA”) code, depending upon whether the repetition in the
`first encoding is regular or irregular.
`Figure 4 of the ’781 patent is reproduced below.
`
`Figure 4 shows an alternative embodiment in which the first encoding is
`carried out by a low density generator matrix. Low density generator matrix
`(LDGM)5 codes are a special class of low density parity check codes that
`allow for less encoding and decoding complexity. LDGM codes are
`
`5 We understand that a “generator” matrix (typically referred to by “G”) is
`used to create (generate) codewords. A parity check matrix (typically
`referred to by “H”) is used to decode a received message.
`
`6
`
`
`
`IPR2015-00059
`Patent 7,916,781 B2
`systematic linear codes generated by a “sparse” generator matrix. No
`interleaver (as in the Figure 2 embodiment) is required in the Figure 4
`arrangement because the LDGM provides scrambling otherwise provided by
`the interleaver in the Figure 2 embodiment.
`
`C. Illustrative Claim
`All of the claims of the ’781 patent are directed to methods of coding.
`Among the challenged claims, claims 1, 13, and 19 are independent. Claim
`13 and its dependent claims are directed to encoding methods that produce
`irregular repeat accumulate codes. Claim 1, which does not require
`irregularity, is illustrative and is reproduced below.
`
`1. A method of encoding a signal, comprising:
`
`[a] receiving a block of data in the signal to be encoded, the
`block of data including information bits;
`
`[b] performing a first encoding operation on at least some of the
`information bits, the first encoding operation being a linear
`transform operation that generates L transformed bits; and
`
`[c] performing a second encoding operation using the L
`transformed bits as an input, the second encoding operation
`including an accumulation operation in which the L
`transformed bits generated by the first encoding operation are
`accumulated,
`
`[d] said second encoding operation producing at least a portion
`of a codeword, wherein L is two or more.
`
`(bracketed claim limitation references added)
`
`7
`
`
`
`IPR2015-00059
`Patent 7,916,781 B2
`ALLEGED GROUNDS OF UNPATENTABILITY
`
`Petitioner contends that the challenged claims are unpatentable on the
`following specific grounds.6
`
`Reference(s)
`
`Basis
`
`Claim(s) challenged
`
`Divsalar7
`
`35 U.S.C. § 102
`
`1–2
`
`Ping8
`
`35 U.S.C. § 102
`
`1–3, 5–7, and 19
`
`Ping and Patterson9
`
`35 U.S.C. § 103
`
`4
`
`Ping and Luby10
`
`35 U.S.C. § 103
`
`2, 3, 5–7, and 13-15
`
`Ping, Luby, and
`Patterson
`
`35 U.S.C. § 103
`
`4 and 16
`
`ANALYSIS OF CLAIM CHALLENGES
`
`A. Claim Construction
`Claim constructions presented in this Decision are preliminary in that
`they are based on the record developed thus far, prior to Patent Owner’s
`
`6 Petitioner supports its challenge with Declaration of Henry D. Pfister,
`Ph.D. (Ex. 1010) (“Pfister Decl.”). See infra.
`7 Dariush Divsalar, et al., Coding Theorems for “Turbo-Like” Codes, 1998
`THIRTY-SIXTH ANNUAL ALLERTON CONFERENCE ON COMMUNICATION,
`CONTROL, AND COMPUTING201–209 (Ex. 1011, “Divsalar”).
`8 Li Ping et al., Low Density Parity Check Codes with Semi-Random Parity
`Check Matrix, 35 IEEE ELECTRONICS LETTERS, 38–39 (1999) (Ex. 1014,
`“Ping”).
`9 Patterson, U.S. Patent No. 4,623,999, application filed June 4, 1984 (Ex.
`1027, “Patterson”).
`10 Luby et al., U.S. Patent 6,081,909, application filed November 6, 1997
`(Ex. 1016, “Luby”).
`
`8
`
`
`
`IPR2015-00059
`Patent 7,916,781 B2
`formal response. Constructions may change as the record more fully
`develops.
`In an inter partes review, claim terms of an unexpired patent are given
`their broadest reasonable construction in light of the specification of the
`patent in which they appear. See 37 C.F.R. § 42.100(b); Office Patent Trial
`Practice Guide, 77 Fed. Reg. 48,756, 48,766 (Aug. 14, 2012). Under the
`broadest reasonable construction standard, claim terms are given their
`ordinary and customary meaning, as would be understood by one of ordinary
`skill in the art in the context of the entire disclosure. See In re Translogic
`Tech., Inc., 504 F.3d 1249, 1257 (Fed. Cir. 2007). Any special definition for
`a claim term must be set forth with reasonable clarity, deliberateness, and
`precision. In re Paulsen, 30 F.3d 1475, 1480 (Fed. Cir. 1994).
`
`1. “linear transformation”(claim 1)
`Petitioner states that Divsalar demonstrates linear transformation
`within its broadest reasonable construction, but does not construe the term.
`Patent Owner asserts that Petitioner did not construe the term, but does not
`offer its own construction. We construe the term in order to apply the
`references.
`The term “linear transformation” is used in the context of a linear
`transformation between two vector spaces. For purposes of this decision, we
`adopt a linear algebra definition11 as follows:
`A linear transformation is one that obeys the laws of linear algebra
`including distributive and associative properties, e.g. the transform of
`vectors a+b is equal to the transform of a + the transform of b. The
`
`
`11 This definition is explained by “Wolfram MathWorld” at
`http://mathworld.wolfram.com/lineartransformation.html.
`
`9
`
`
`
`IPR2015-00059
`Patent 7,916,781 B2
`transform of x (a scalar) times a vector y is equivalent to x times the
`transform of vector y.
`2. additional claim terms
`
`For purposes of this decision, we find it unnecessary to construe
`additional claim terms.
`
`B. Divsalar (Ex. 1011)
`
`1. Divsalar as a Publication
`The cover page of the Divsalar document is reproduced below.
`
`The cover page includes a photograph of the “Allerton House” in which the
`Allerton Conference is held. It also includes the date range of the
`conference and indicates sponsorship information.
`Petitioner states that Divsalar was “published no later than April 30,
`
`10
`
`
`
`IPR2015-00059
`Patent 7,916,781 B2
`1999 at the University of Texas library.” In support, Petitioner proffers the
`declaration testimony of the University of Texas librarian (Ex. 1064),
`including an acquisition record pasted into an email. According to Dr.
`Pfister, Petitioner’s declarant, the Allerton Conference is generally regarded
`as one of the main conferences in the field of information theory and
`communications. Ex. 1010 ¶ 29.
`Patent Owner argues that Petitioner has not established that Divsalar
`is a publication within the meaning of 35 U.S.C. § 311(b). Patent Owner
`states that Divsalar is “undated” (Prelim. Resp. 19) and that the library
`acquisition record does not state that the paper was actually shelved or
`otherwise displayed and accessible to those of “ordinary skill.” Id. at 22.
`According to the Divsalar cover page, it was presented at the Allerton
`Conference held Sept 23–25, 1998. Ex. 1011, 1. The acquisition record of
`the University of Texas indicating acquisition in April 1999 lends credence
`to the actual presentation and publication of the paper at the September 1998
`Allerton Conference. See attachment to Declaration of Robin Fradenburgh,
`Ex. 1064. Given Dr. Pfister’s testimony that the Allerton Conference is the
`premier conference for information theorists, we find sufficient evidence to
`establish Divsalar as having been presented and published as required by 35
`U.S.C. § 311(b).
`We note that Divsalar is listed as being of record among the
`“References Cited” in the ’781 patent itself. It was not of record in the
`prosecution of its grandparent application (issued as the ’710 patent).
`Accordingly, we are persuaded by Petitioner and the supporting
`evidence that Divsalar is prior art for the purposes of this Decision. Patent
`Owner may rebut Petitioner’s explanation and supporting evidence with
`evidence that Divsalar was not presented and published as part of the
`
`11
`
`
`
`IPR2015-00059
`Patent 7,916,781 B2
`Allerton Conference.
`
`
`
`2. Challenge to Claims 1 and 2 based on Divsalar
`Divsalar describes a rate-1 accumulate convolutional encoder known
`as a “repeat-accumulator” or “RA” code. Ex. 1010 at para. 31–32.
`Petitioner relies on Divsalar’s Figure 3, reproduced below.
`
`Figure 3 of Divsalar describes an encoder for a (qN, N) repeat and
`accumulate code. Ex. 1011, 7. The numbers above the input-output lines
`indicate the length of the corresponding block, and those below the lines
`indicate the weight of the block. Id.
`Petitioner argues that Divsalar’s “rate 1/q repetition” followed by a
`permutation constitutes a linear transform operation as required by claim 1.
`Pet. 14. Patent Owner disagrees, arguing that Petitioner has not
`demonstrated why this is so. Prelim. Resp. 23–27. Patent owner draws a
`distinction between the’781 patent being directed to “irregular” repeat codes
`and Divsalar being directed to “regular” repeat codes. Patent Owner
`correctly points out that Divsalar does not disclose an encoding operation
`utilizing irregular repetition. Prelim. Resp. 26. Patent Owner argues that the
`specification explains how irregular coding can be achieved. Pet. 26. Patent
`Owner points to a passage of the ’781 patent specification including the
`statement that “'[t]he outer coder may be an (n,k) binary linear block coder,'”
`and describes the relationship between the input and output data in
`
`12
`
`
`
`IPR2015-00059
`Patent 7,916,781 B2
`mathematical terms. Pet. 24 (citing Ex. 1005, 2:47–53). We agree with
`Patent Owner that the specification explains how irregular coding is
`achieved.
`However, we do not read claim 1 as being limited to irregular repeat
`coding. Claim 1 requires “performing a first encoding operation on at least
`some of the information bits, the first encoding operation being a linear
`transform operation that generates L transformed bits.” The first encoding
`can be on “at least some” of the information bits. Thus, it could also be on
`all of the information bits. Also, according to the claim, the first encoding
`operation must produce “L” transformed bits. There is no explanation in the
`claim as to the relationship of “L” to the incoming block of bits being
`transformed. All the reader of claim 1 is told, at the end of the claim, is that
`L is 2 or more. Thus, claim 1 could produce a regular repeat code by
`repeating all of the information bits to generate L (more than 2) transformed
`bits. If claim 1 is limited to producing irregular codes, it has not yet been
`made clear to us what language so limits the claim.
`If claim 1 were limited to “irregular” codes, Patent Owner’s position
`would have more merit. However, claim 1 embraces more than just
`“irregular” repeat codes. It includes first and second encoding operations
`that may produce “regular” and “irregular” repeat codes. Thus, on this
`record, Patent Owner’s argument does not appear to be commensurate in
`scope with the actual language of claim 1.
`Claim 2 depends from claim 1 and further requires that a codeword
`resulting from the claim 1 encoding process includes parity bits. Divsalar
`adds parity bits by outputting more bits than are input. See Divsalar’s Figure
`3 showing a first encoding having a rate less than 1. Nothing in claim 2
`limits it to producing irregular repeat codewords.
`
`13
`
`
`
`IPR2015-00059
`Patent 7,916,781 B2
`For the above-stated reasons we conclude that on this record
`Petitioner has demonstrated it is reasonably likely to prevail in challenging
`claims 1 and 2 as anticipated by Divsalar.
`
`C. Challenges based on Ping (Ex. 1014)
`
`1. What Ping describes
`Ping generally relates to low density parity check (LDPC) codes that
`have been known since 1962. See Ex. 1014, 7 n.1. It was known to
`randomly generate matrix elements using a process referred to as “Gaussian
`elimination.” Ex. 1014, 6.12 Ping describes generating LDPC using a semi-
`random parity check matrix. Ex. 1014, Title. Some of the matrix elements
`are determined randomly and some of the matrix elements are deterministic.
`Id. at 6. Ping states that a fully random matrix is best, but leads to codes that
`are not practical to decode. Id. Ping’s theorizes that by only semi-
`randomizing the parity check matrix, one can achieve a code scheme that is
`almost as good as that which can be obtained by a fully randomized matrix
`and at considerable less encoding complexity. Id. Ping randomly selects a
`portion of the coding matrix and determines the rest of the matrix by
`formula, thus deterministically rather than randomly. Id.
`
`2. Anticipation Challenges based on Ping
`Claim 1 does not require an irregular repeat (the only independent
`claim requiring irregular repeat is claim 13). Petitioner reads the challenged
`claims on Ping at Pet. 16–31. This portion of the Petition is supported by
`the Pfister Report (Ex. 1010¶¶ 49–60.
`
`
`12 We refer to exhibit page numbers rather than pages number of the
`cumulative publication in which the article is positioned.
`
`14
`
`
`
`IPR2015-00059
`Patent 7,916,781 B2
`According to Petitioner, Ping discloses a low-density generator matrix
`with an accumulate encoder. Pet. 17 (citing Ex. 1010 ¶ 51).
`With regard to the claim 1 “first encoding,” Petitioner provides a
`lengthy quote from Ping at page 6 of Exhibit 1014. Pet. 18–19. Petitioner
`then asserts that Ping’s encoding procedure, reproduced above, is a low-
`density generator matrix (LDGM) encoding combined with an accumulate
`encoder. Pet. 19 (citing Ex. 1010 ¶ 55). Petitioner states that equation (4) of
`Ping (Ex. 1010, 56) performs an accumulation to determine parity bits.
`Petitioner further states that the summation term used to calculate each
`parity bit is a linear transform operation. Id. Petitioner relies on the
`assertion that one of ordinary skill would recognize that the (n-k) term
`(allegedly corresponding to the claimed “L” bits) would be two or more.
`Pet. 21 (citing Ex. 1010 ¶ 59). Petitioner’s argued mathematical equivalence
`further relies upon a person of ordinary sill recognizing that “any reasonable
`configuration of the encoder of Ping would use (n-k) much greater than two.
`Pet. 21 (citing Ex. 1010 ¶ 59).
`Patent Owner argues that Petitioner has not carried its burden. First,
`according to Patent Owner, Ping improperly equates Ping’s LDPC codes
`with the ’781 use (Fig. 4) of a low density generator matrix (LDGM) in
`order to imply that Ping meets limitations [b] and [c] of claim 1. Prelim.
`Resp. 28. Patent Owner argues that Petitioner and Dr. Pfister jump to the
`unexplained conclusory statement that the LDGM code definition is given
`by “basic coding theory” without any explanation as to why this is so. Id. at
`29.
`
`Although Patent Owner does not offer an alternative analysis. We
`nonetheless do not find helpful Petitioner’s unexplained conclusory remarks
`regarding Ping’s equivalency to claim 1. Absent sufficient explanation and
`
`15
`
`
`
`IPR2015-00059
`Patent 7,916,781 B2
`evidence, we are not persuaded by Petitioner that Ping’s LDPC codes meets
`limitation [b] and [c] of claim 1. Accordingly, we are not persuaded that
`there is a reasonable likelihood that Petitioner will prevail with respect to
`claim 1.
`
`3. Obviousness Challenges based on Ping, Patterson , and
`Luby
`The additional references (Patterson and Luby) do not overcome the
`flaws identified above with respect to Ping. Luby is relied upon for its
`description of irregularizing known codes. Pet. 9–10. Patterson is relied
`upon for its description of codewords comprising information bits followed
`by parity bits. Pet. 10–11.
`Petitioner does not explain why one of ordinary skill would have
`made the assumptions referred to above with respect to the anticipation
`challenges based on Ping. Luby and Patterson do not overcome this. We
`therefore conclude that Petitioner is not reasonably likely to succeed in its
`obviousness challenges based upon Ping and additional references.
`
`SUMMARY
`For the foregoing reasons, we determine that the information
`
`presented in the Petition establishes a reasonable likelihood that Petitioner
`would prevail on at least one alleged ground of unpatentability with respect
`to claims 1 and 2 of the ’781 patent. The Board has not made a final
`determination on the patentability of any challenged claims.
`
`
`ORDER
`
` For the reasons given, it is
`ORDERED that inter partes review of the ’781 patent is hereby
`instituted as to all the challenged claims as follows: claims 1 and 2 as
`anticipated by Divsalar;
`
`16
`
`
`
`IPR2015-00059
`Patent 7,916,781 B2
`FURTHER ORDERED that no ground other than those specifically
`granted above is authorized for the inter partes review; and
`FURTHER ORDERED that pursuant to 35 U.S.C. § 314(c) and
`37 C.F.R. § 42.4, notice is hereby given of the institution of a trial on the
`grounds of unpatentability authorized above; the trial commences on the
`entry date of this Decision.
`
`PETITIONER:
`Eliot D. Williams
`G. Hopkins Guy
`Baker Botts, LLP
`eliot.williams@bakerbotts.com
`hop.guy@bakerbotts.com
`
`PATENT OWNER:
`Michael T. Rosato
`Matthew A. Argenti
`Wilson Sonsini Goodrich & Rosati
`mrosato@wsgr.com
`margenti@wsgr.com
`
`17