UNITED STATES PATENT AND TRADEMARK OFFICE
`BEFORE THE PATENT TRIAL AND APPEAL BOARD
`
`In Re:
`
`U.S. Patent US 7,916,781
`
`: Attorney Docket No. 082944.0102
`
`Inventor: Hui Jin, et. al.
`
`Filed:
`
`June 30, 2008
`
`
`
`
`
`Claimed Priority: May 18, 2000
`
`Issued:
`
`March 29, 2011
`
`
`
`
`
`
`
`
`
`
`
`:
`
`:
`
`:
`
`: IPR No. Unassigned
`
`Assignee: California Institute of Technology
`
`Title:
`
`Serial Concatenation of Interleaved Convolutional Codes Forming
`Turbo-Like Codes
`
`Mail Stop PATENT BOARD
`Patent Trial and Appeal Board
`U.S. Patent and Trademark Office
`P.O. Box 1450
`Alexandria, Virginia 22313-1450
`
`Submitted Electronically via the Patent Review Processing System
`
`PETITION FOR INTER PARTES REVIEW OF CLAIMS 1, 2, 3, 4, 5, 6, 7, 13,
`14, 15, 16, and 19 OF U.S. PATENT NO. 7,916,781 UNDER 35 U.S.C. §§ 311-
`319 AND 37 C.F.R. §§ 42.100 ET SEQ.
`
`

`

`Petition for Inter Partes Review of U.S. Patent No. 7,916,781
`
`TABLE OF CONTENTS
`
`I. 
`
`II. 
`
`MANDATORY NOTICES, STANDING, AND FEES .................................. 1 
`
`OVERVIEW OF CHALLENGE AND RELIEF REQUESTED .................... 2 
`
`A.  Publications Relied Upon ........................................................................ 2 
`
`B.  Grounds For Challenge ............................................................................ 3 
`
`III.  OVERVIEW OF THE ’781 PATENT ............................................................ 4 
`
`A.  Summary of the Claimed Subject Matter ................................................ 4 
`
`B.  Prosecution History of the ’781 Patent .................................................... 5 
`
`IV.  SUMMARY OF PRIOR ART ......................................................................... 6 
`
`A.  State of the Art ......................................................................................... 6 
`
`B.  Summary of References Relied Upon ..................................................... 9 
`
`V. 
`
`CLAIM CONSTRUCTION .......................................................................... 11 
`
`A.  Level of Ordinary Skill in the Art .......................................................... 12 
`
`B. 
`
`"Codeword" ............................................................................................ 12 
`
`C.  “Summing” Terms ................................................................................. 12 
`
`VI.  A REASONABLE LIKELIHOOD EXISTS THAT THE CHALLENGED
`CLAIMS ARE UNPATENTABLE .............................................................. 13 
`
`A.  Ground 1: ‘781 Patent Claims 1 and 2 are Anticipated Under 35
`U.S.C. § 102 by Divsalar ....................................................................... 13 
`
`B.  Ground 2: ‘781 Patent Claims 1, 2, 3, 5, 6, 7, and 19 are Anticipated
`Under 35 U.S.C. § 102 by Ping ............................................................. 16 
`
`C.  Ground 3: ‘781 Patent Claim 4 is Obvious Under 35 U.S.C. § 103
`over Ping in view of the ’999 Patent ..................................................... 31 
`
`
`
`i
`
`

`

`Petition for Inter Partes Review of U.S. Patent No. 7,916,781
`
`D.  Ground 4: ‘781 Patent Claims 2, 3, 5, 6, 7, 13, 14, and 15 are
`Obvious Under 35 U.S.C. § 103 over Ping in view of the Luby ‘909
`Patent ...................................................................................................... 33 
`
`E.  Ground 5: ‘781 Claims 4 and 16 are Obvious Under 35 U.S.C. § 103
`over Ping in view of the Luby ‘909 Patent and in further view of
`the ’999 Patent ....................................................................................... 44 
`
`VII.  CONCLUSION .............................................................................................. 47 
`
`
`
`ii
`
`

`

`Petition for Inter Partes Review of U.S. Patent No. 7,916,781
`
`LIST OF EXHIBITS
`
`U.S. Patent No. 7,116,710 by Hui Jin, et. al. entitled “Serial
`Concatenation of Interleaved Convolutional Codes Forming Turbo-
`Like Codes.” (the “’710 Patent”)
`
`Prosecution History of the ’710 Patent
`
`U.S. Patent No. 7,421,032 by Hui Jin, et. al. entitled “Serial
`Concatenation of Interleaved Convolutional Codes Forming Turbo-
`Like Codes.” (the “’032 Patent”)
`
`Prosecution History of the ’032 Patent
`
`U.S. Patent No. 7,421,781 by Hui Jin, et. al. entitled “Serial
`Concatenation of Interleaved Convolutional Codes Forming Turbo-
`Like Codes.” (the “’781 Patent”)
`
`Prosecution History of the ’781 Patent
`
`U.S. Patent No. 8,284,833 by Hui Jin, et. al. entitled “Serial
`Concatenation of Interleaved Convolutional Codes Forming Turbo-
`Like Codes.” (the “’833 Patent”)
`
`Prosecution History of the ’833 Patent
`
`U.S. Provisional Application Ser. No. 60/205,095 by Hui Jin, et. al.
`(the “’095 Provisional Application”)
`
`Declaration of Henry D. Pfister, Ph.D.
`
`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-210, Sept. 1998
`(“Divsalar”) (published no later than April 30, 1999 at the
`University of Texas library)
`
` B.J. Frey and D.J.C. MacKay, “Irregular Turbocodes.” from the 37th
`Allerton Conference (“Frey”) (published no later than October 8, 1999
`at the website of D.J.C. MacKay)
`
`iii
`
`1001
`
`1002
`
`1003
`
`1004
`
`1005
`
`1006
`
`1007
`
`1008
`
`1009
`
`1010
`
`1011
`
`1012
`
`
`
`

`

`Petition for Inter Partes Review of U.S. Patent No. 7,916,781
`
`E.K. Hall and S.G. Wilson, “Stream-Oriented Turbo Codes.” 48th
`IEEE Vehicular Technology Conference, pp. 71-76, 1998 (“Hall”)
`(published no later than June 23, 1998 at the Library of Congress)
`
`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, Jan. 7th, 1999 (“Ping”) (published no later than
`April 22, 1999 at the Library of Congress)
`
`M. Luby, M. Mitzenmacher, A. Shokrollah, D. Spielman, “Analysis of
`Low Density Codes and Improved Designs Using Irregular Graphs.”
`STOC ’98 Proceedings of the Thirtieth Annual ACM symposium on
`Theory of Computing, pp. 249-258, 1998 (“Luby”) (published no
`later than July 30, 1998 at the University of Washington)
`
`U.S. Patent No. 6,081,909 by Michael Luby, et. al. entitled
`“Irregularly Graphed Encoding Technique.” (“the Luby ’909 Patent”)
`(filed November 6, 1997 and issued June 27, 2000)
`
`F. R. Kschischang and B. J. Frey, “Iterative decoding of compound
`codes by probability propagation in graphical models.” IEEE Journal
`on Selected Areas in Communications, 16, 219-230. 1998.
`(“Kschischang”) (published no later than Febuary 23, 1998 at the
`Library of Congress)
`
`U.S. Patent No. 7,089,477 by Michael Divsalar, et. al. entitled
`“Interleaved Serial Concatenation Forming Turbo-Like Codes .”
`(“the ’477 Patent”)
`
`RA.c code (including RA.c, and supporting files)
`
`J.L. Hennessy and D.A. Patterson, Computer organization and design:
`the hardware/software interface. 1994. (“Hennessy”) (published no
`later than November 8, 1994 at the Library of Congress)
`
`Complaint, California Institute of Technology v. Hughes
`Communications, Inc. et. al., No. 13-CV-07245 (CACD)
`
`Amended Complaint, California Institute of Technology v. Hughes
`Communications, Inc. et. al., No. 13-CV-07245 (CACD)
`
`iv
`
`1013
`
`1014
`
`1015
`
`1016
`
`1017
`
`1018
`
`1019
`
`1020
`
`1021
`
`1022
`
`
`
`

`

`Petition for Inter Partes Review of U.S. Patent No. 7,916,781
`
` 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-1454, Oct. 1999 (“MacKay”) (published no
`later than December 3, 1999 at the Library of Congress)
`
`Corrected Claim Construction Order (D.I. 105)
`
`Joint Claim Construction and Prehearing Statement (D.I. 60)
`
`Reporter’s Transcript of Claims Construction and Motion Hearing of
`July 9, 2014
`
`U.S. Patent No. 4,623,999 by Patricia Patterson, entitled “Look-up
`Table Encoder for Linear Block Codes .” (“the ’999 Patent”) (issued
`November 18, 1986)
`
`Luby, Mitzenmacher, Shokrollahi, Spielman, and Stemann, “Practical
`loss-resilient codes” in STOC '97 Proceedings of the twenty-ninth
`annual ACM symposium on Theory of Computing, 1997
`
`Richardson, Shokrollahi, and Urbanke, “Design of Provably Good
`Low-Density Parity Check Codes”
`
`Bond, Hui, and Schmidt, “Constructing Low-Density Parity-Check
`Codes with Circulant Matrices” ITW 1999, Metsovo, Greece (June
`27-July 1 1999).
`
`Viterbi and Viterbi, “New results on serial concatenated and
`accumulated-convolutional turbo code performance” in Annales Des
`Télécommunications 1999
`
`Benedetto, Divsalar, Montorsi, and Pollara, “Serial concatenation of
`interleaved codes: Performance analysis, design, and iterative
`decoding” in IEEE Transactions on Information Theory, Vol. 44 (3),
`1998
`
`McEliece, MacKay, and Cheng “Turbo Decoding as an Instance of
`Pearl’s “Belief Propagation” Algorithm”, as published to
`http://wol.ra.phy.cam.ac.uk/mackay/, under the filename
`“BPTD.ps.gz” by August 14, 1997
`
`v
`
`1023
`
`1024
`
`1025
`
`1026
`
`1027
`
`1028
`
`1029
`
`1030
`
`1031
`
`1032
`
`1033
`
`
`
`

`

`Petition for Inter Partes Review of U.S. Patent No. 7,916,781
`
`B.J. Frey and D.J.C. MacKay, slide presentation entitled “Irregular
`Turbocodes” presented at the 1999 Allerton Conference held
`September 22-24, 1999 (Published Sept 22-24, 1999)
`
`B.J. Frey, slide presentation entitled “Irregular Turbocodes” presented
`at the 2000 ISIT conference, on June 25, 2000 (Published June 25,
`2000)
`
`B.J. Frey, slide presentation entitled “Irregular Turbocodes” presented
`at the Second International Symposium on Turbocodes and Related
`Topics in Brest, France in September 2000 (Published June 25, 2000)
`
`D.J.C. MacKay, slide presentation entitled “Gallagher Codes-Recent”
`presented at the 1999 IMA Summer Program at the University of
`Minnesota in Minneapolis, Minnesota (Published Aug. 3-5, 1999)
`
`Wayback Machine capture of the May 7, 1999 contents of
`http://wol.ra.phy.cam.ac.uk/mackay/README.html
`
`D. J. C. MacKay, S. T. Wilson, and M. C. Davey, “Comparison of
`Constructions of Irregular Gallager Codes” as published to
`http://wol.ra.phy.cam.ac.uk/mackay/, under the filename “ldpc-
`irreg.ps.gz” on July 30, 1998 (Published July 30, 1998)
`
`Screen capture of last-modified time information of MacKay website
`content
`
`D. J. C. MacKay, “Gallager codes — Recent Results” as published to
`http://wol.ra.phy.cam.ac.uk/mackay/, under the filename
`“sparsecodes.ps.gz” by July 16, 1999 (Published July 16, 1999)
`
`D.J.C. Mackay, Abstract “Gallager Codes — Recent Results” as
`published to http://vol.ra.phy.com.ac.wh/mackay/ under file name
`“sparsecodes0.ps.gz by June 2, 1999
`
`D. J. C. MacKay, “Gallager codes — Recent Results.” Proceedings of
`the International Symposium on Communication Theory and
`Applications, Ambleside, 1999, ed. by M. D. B. Honary and P. Farrell.
`Research Studies Press, 1999 (the “Ambleside Presentation”).
`(published no later than July 16, 1999 at the website of D.J.C.
`MacKay)
`
`vi
`
`1034
`
`1035
`
`1036
`
`1037
`
`1038
`
`1039
`
`1040
`
`1041
`
`1042
`
`1043
`
`
`
`

`

`Petition for Inter Partes Review of U.S. Patent No. 7,916,781
`
`Portion of electronic log of D.J.C. MacKay dated July 16, 1999
`
`McEliese, et. al., slide presentation entitled “RA” presented at the
`Institute for Mathematics and its Applications conference on
`August 3, 1999.
`
`Screen capture of last modified dates of slides from
`https://www.ima.umn.edu/talks/workshops/aug2-
`13.99/mackay/mackay.html
`
`B.J. Frey and D.J.C. MacKay, “Irregular Turbocodes.” Proc. 37th
`Allerton Conf. on Comm., Control and Computing, Monticello,
`Illinois, Sep. 1999 (published no later than May 11, 2000 at the British
`Library Boston Spa)
`
`B.J.Frey and D.J.C. MacKay, “Irregular Turbocodes” ISIT 2000
`Conference, Sorrento, Italy June 25-30, 2000
`
`D.J.C. MacKay, R.J. McEliece, J-F.Cheng, “Turbo Decoding as an
`Instance of Pearl’s ‘Belief Propagation’ Algorithm” as appearing on
`the MacKay websites as of May 7, 1999
`
`D.J.C. MacKay, “Encyclopedia of Sparse Graph Codes” as it appeared
`on the MacKay websites as of May 7, 1999
`
`D.J.C. MacKay, “Low Density Parity Check Codes over GF(q)” as it
`appeared on the MacKay websites as of May 7, 1999
`
`D.J.C. MacKay, “Decoding Times of Irregular Gallager Codes” as it
`appeared on the MacKay websites as of May 7, 1999
`
`D.J.C. MacKay, “Good Error-Correcting Codes Based on Very Sparse
`Matrices” as it appeared on the MacKay websites as of May 7, 1999
`
`D.J.C. MacKay, “Decoding Times of Repeat-Accumulate Codes” as it
`appeared on the MacKay websites as of May 7, 1999
`
`B.J. Frey, D.J.C. MacKay, “Trellis-Constrained Codes” as it appeared
`on the MacKay websites as of May 7, 1999
`
`vii
`
`1044
`
`1045
`
`1046
`
`1047
`
`1048
`
`1049
`
`1050
`
`1051
`
`1052
`
`1053
`
`1054
`
`1055
`
`
`
`

`

`Petition for Inter Partes Review of U.S. Patent No. 7,916,781
`
`D.J.C. MacKay, “Turbo Codes are Low Density Parity Check Codes”
`as it appeared on the MacKay websites as of May 7, 1999
`
`H. D. Pfister and P. H. Siegel, “The serial concatenation of rate-1
`codes through uniform random interleavers.” Proc. 37th Allerton
`Conf. on Comm., Control and Computing, Monticello, Illinois, pp.
`260-269, Sep. 1999 (“Pfister”) (published no later than May 11, 2000
`at the British Library Boston Spa)
`
`R. J. McEliece, “Repeat-Accumulate Codes [A Class of Turbo-like
`Codes that we can analyse].” 1999 Summer Program: Codes, Systems,
`and Graphical Models, University of Minnesota, Institute for
`Mathematics and its Applications, Aug. 2-13, 1999 (the “IMA
`Presentation”).
`
`Declaration of Brendan J. Frey
`
`Declaration of David J.C. Mackay
`
`C. Berrou, A. Glavieux, and P. Thitimajshima, “Near Shannon Limit
`Error Correcting Coding and Decoding.” IEEE International
`Conference on Communications, ICC '93 Geneva. Technical Program,
`Conference Record, (1993)
`
`MacKay and Neal, “Near Shannon Limit Performance of Low Density
`Parity Check Codes.” Electronic Letters(August 29, 1996)
`
`S. Benedetto , G. Montorsi, “Unveiling Turbo Codes: Some Results
`on Parallel Concatenated Coding Schemes.” IEEE Transactions on
`Information Theory, vol. 42, no. 2 (March 1996)
`
`Declaration of Robin Fradenburgh Concerning the “Proceedings, 36th
`Allerton Conference on Communications, Control, and Computing”
`Reference
`
`Wayback Machine capture of the December 9, 2006 contents of
`http://wol.ra.phy.cam.ac.uk/mackay/SourceC.html
`
`1056
`
`1057
`
`1058
`
`1059
`
`1060
`
`1061
`
`1062
`
`1063
`
`1064
`
`1065
`
`1066
`
`E-mail from Paul Siegel to Henry D. Pfister
`
`
`
`viii
`
`

`

`Petition for Inter Partes Review of U.S. Patent No. 7,916,781
`
`I. MANDATORY NOTICES, STANDING, AND FEES
`
`Real Party in Interest: Hughes Network Systems, LLC and Hughes
`
`Communications, Inc. (“Petitioner” or “Hughes”) are the real parties in interest.
`
`Hughes is a provider of broadband satellite services. EchoStar Corporation is the
`
`parent of Hughes Satellite Systems Corporation, which is the parent of Hughes
`
`Communications, Inc.
`
`Related Matters: The ’781 Patent is currently involved in a pending lawsuit
`
`entitled California Institute of Technology v. Hughes Communications, Inc. et. al.,
`
`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.
`
`The complaint was filed on October 1, 2013 and was effectively served on
`
`November 12, 2013. Petitioner is contemporaneously filing petitions for Inter
`
`Partes review for the other patents identified above.
`
`Lead Counsel and Request for Authorization: Pursuant to 37 C.F.R.
`
`§§ 42.8(b)(3) and 42.10(a), Petitioner designates the following: Lead Counsel is
`
`Eliot D. Williams (Reg. No. 50,822) of Baker Botts L.L.P.; Back-up Counsel is G.
`
`Hopkins Guy (Reg. No. 35,886) of Baker Botts L.L.P.
`
`Service Information: Service information is as follows: Baker Botts L.L.P.,
`
`1001 Page Mill Rd., Palo Alto, CA 94304-1007 Tel. 650 739 7500; Fax 650-736-
`
`
`
`1
`
`

`

`Petition for Inter Partes Review of U.S. Patent No. 7,916,781
`
`7699.
`
`
`
`Petitioner
`
`consents
`
`to
`
`service
`
`by
`
`electronic mail
`
`at
`
`eliot.williams@bakerbotts.com and hop.guy@bakerbotts.com. A Power of
`
`Attorney is filed concurrently herewith under 37 C.F.R. § 42.10(b).
`
`Certification of Grounds for Standing: Petitioner certifies under 37 C.F.R.
`
`§ 42.104(a) that the ’781 Patent is available for inter partes review and that
`
`Petitioner is not barred or estopped from requesting inter partes review on the
`
`grounds set forth herein.
`
`Fees: The Office is authorized to charge the fee set forth in 37 C.F.R.
`
`§ 42.15(a) to Deposit Account No. 02-0384 as well as any additional fees that
`
`might be due in connection with this Petition.
`
`II. OVERVIEW OF CHALLENGE AND RELIEF REQUESTED
`
`Petitioner challenges claims 1, 2, 3, 4, 5, 6, 7, 13, 14, 15, 16, and 19 of U.S.
`
`Patent No. 7,916,781 by Hui Jin, et. al. (“the ’781 Patent”), titled “Serial
`
`Concatenation of Interleaved Convolutional Codes Forming Turbo-Like Codes.”
`
`See Ex. 1005.
`
`A. Publications Relied Upon
`
`Petitioner relies upon the following patents and publications:
`
`Exhibit 1011 - “Coding Theorems for "Turbo-like" Codes” by D. Divsalar,
`
`H. Jin, and R. J. McEliece (“Divsalar”), published at least by April 30, 1999 and
`
`available as prior art under 35 U.S.C. § 102(b); see also Ex. 1064.
`
`
`
`2
`
`

`

`Petition for Inter Partes Review of U.S. Patent No. 7,916,781
`
`Exhibit 1014 - “Low Density Parity Check Codes with Semi-random Parity
`
`Check Matrix” by L. Ping, W. K. Leung, N. Phamdo (“Ping”), published at least
`
`by April 22, 1999 and available as prior art under 35 U.S.C. § 102(b).
`
`Exhibit 1016 - U.S. Patent No. 6,081,909 entitled “Irregularly Graphed
`
`Encoding Technique” by M. Luby, et. al. (“the Luby ‘909 Patent”), filed on
`
`November 6, 1997 and issued on June 27, 2000. The Luby ‘909 Patent is
`
`available as prior art under 35 U.S.C. § 102(e).
`
`Exhibit 1027 - U.S. Patent No. 4,623,999 by Patricia Patterson, entitled
`
`“Look-up Table Encoder for Linear Block Codes ” (“the ’999 Patent”), issued on
`
`November 18, 1986 and available as prior art under 35 U.S.C. §102(b).
`
`With the exception of Divsalar, none of the above references was cited or
`
`considered during the prosecution of the challenged patent
`
`B. Grounds For Challenge
`
`Petitioner requests cancellation of the claims on the following grounds:
`
`1.
`
`2.
`
`3.
`
`4.
`
`Claims 1 and 2 are anticipated by Divsalar.
`
`Claims 1, 2, 3, 5, 6, 7, and 19 are anticipated by Ping.
`
`Claim 4 is obvious over Ping in view of the ’999 Patent.
`
`Claims 2, 3, 5, 6, 7, 13, 14, and 15 are obvious over Ping in view
`
`of the Luby ‘909 Patent.
`
`5.
`
`Claims 4 and 16 are obvious over Ping in view of the Luby ‘909
`
`
`
`3
`
`

`

`Petition for Inter Partes Review of U.S. Patent No. 7,916,781
`
`Patent and in further view of the ’999 Patent
`
`6.
`
`Claim 4 is obvious over Ping in view of the ’999 Patent and in
`
`further view of the Luby ‘909 Patent
`
`III. OVERVIEW OF THE ’781 PATENT
`
`A. Summary of the Claimed Subject Matter
`
`The ’781 Patent relates to regular and irregular repeat accumulate (“RA”)
`
`coding for transmission of communication signals. Claim 1 describes a two step
`
`process for encoding a signal comprising encoding of information bits into a
`
`codeword using a linear transform step and an accumulation step. Claim 4
`
`describes outputting the codeword as information bits followed by parity bits.
`
`Claim 7 describes transforming the information bits via a low density generator
`
`matrix transformation and a mod-2 or exclusive-OR summing of a subset of the
`
`information bits, where each subset of the information bits includes the same
`
`number of information bits.
`
`Claim 16 describes encoding a singal by generating a portion of a codeword
`
`by encoding information bits with an accumulation of mod-2 or exclusive-OR
`
`sums of bits in subsets of the information bits. The information bits appear in a
`
`variable, or irregular, number of subsets. The codeword is output as information
`
`bits followed by parity bits.
`
`Claim 19 describes encoding a singal by encoding information bits with an
`
`
`
`4
`
`

`

`Petition for Inter Partes Review of U.S. Patent No. 7,916,781
`
`accumulation of a mod-2 or exclusive-OR sums of bits in subsets of the
`
`information bits. The encoding generates a portion of a codeword. At least two
`
`of the information bits appear in three subsets of the information bits in an
`
`irregular configuration.
`
`B. Prosecution History of the ’781 Patent
`
`The application resulting the ’781 Patent was filed June 30, 2008 as a
`
`continuation of application No. 11/542,950, filed on Oct. 3, 2006, now U.S. Patent
`
`No. 7,421,032, which is a continuation of U.S. Application No. 09/861,102, filed
`
`on May 18, 2001, now U.S. Patent No. 7,116,710, and is also a continuation-in-
`
`part of U.S. Application No. 09/922,852, filed on Aug. 18, 2000, now Pat. No.
`
`7,089,477. U.S. Application No. 09/861,102 claims priority to U.S. Provisional
`
`Application Serial No. 60/205,095, filed on May 18, 2000. Ex. 1005.
`
`Prosecution History of Application Leading to the ’781 Patent
`
`The patent examiner initially allowed Claims 1-8, 10-12, and 22, but
`
`rejected claims 13-17 and 20 over U.S. Patent 5,181,207 to Chapman, et. al. Ex.
`
`1006 at 59-61. Furthermore, the patent examiner objected that claims 9, 21, and
`
`23 should be amended to clarify their unclear recitation of “irregular.” Id. at 60.
`
`In response, the applicants cancelled claim 21 and amended Claims 9 and 23 to
`
`clarify that “irregular” meant that information bits appeared “in a variable number
`
`of subsets.” Id. at 81-86. The applicants also added this limitation to rejected
`
`
`
`5
`
`

`

`Petition for Inter Partes Review of U.S. Patent No. 7,916,781
`
`claim 13. Id.. Claims 18 and 19 were amended to include limitations formerly
`
`pending in claim 13 and rewritten into independent form. Id. The applicants
`
`asserted that “It is believed that the meaning of the term ‘irregular’ in the claims
`
`is clear and is well known in the art of computer coding technology.” (emphasis
`
`added). The amended claims were allowed by the patent examiner. Id. at 86.
`
`IV. SUMMARY OF PRIOR ART
`
`A. State of the Art
`
`The ‘781 Patent relates to error detection and correction codes used in
`
`encoding information before transmission as a communication signal over a
`
`communication channel. Ex. 1010 at ¶¶ 34-40. In particular, the ‘781 patent is
`
`directed to repeat-accumulate (“RA”) and irregular RA coding techniques. Id. at ¶
`
`35. During transmission, information contained in communication signals may
`
`be affected by channel noise, leading to potential errors in the information when
`
`received at the receiver. Ex. 1010 at ¶¶ 16-23. Accordingly, various coding
`
`techniques were used in the art to generate parity bits, which are then combined
`
`with the information bits into a codeword that is sent in the communication signal.
`
`Id. The recipient of the codeword uses the parity bits to check the integrity of the
`
`information bits and perform subsequent remedial action, such as error correction,
`
`in order to recover the transmitted information. Id. at ¶¶ 22, 32.
`
`One prior art technique for generating parity information based on bipartite
`
`
`
`6
`
`

`

`Petition for Inter Partes Review of U.S. Patent No. 7,916,781
`
`graphs was known as low density parity check (“LDPC”) codes, which were first
`
`introduced by Robert G. Gallager in 1963 and later refined by David J.C. MacKay.
`
`Ex. 1010 at ¶ 25. Another technique, known as repeat/accumulate (“RA”)
`
`encoding, was published by two of the three inventors of the ‘781 Patent in
`
`September 1998, more than one year before the earliest priority claim of the ‘781
`
`Patent. Ex. 1010 at ¶ 32; Ex. 1011. Turbo codes were also known in the prior art.
`
`Ex. 1010 at ¶ 24. One paper, which Patent Owner has attached to and quoted
`
`from in its parallel district court complaint, published by authors that the Patent
`
`Owner has admitted are “experts” in the field, classified LDPC codes and RA
`
`codes (together with turbo codes) as members of the field of “random-like codes.”
`
`Ex. 1022 at ¶ 24 & at p. 88 (hereinafter, the “Roumy paper”).
`
`It was also known that making a coding technique “irregular,” wherein
`
`different message bits contribute to different numbers of parity bits, would
`
`improve performance of coding techniques. Ex. 1010 at ¶¶ 28-29, 33. For
`
`instance, by 1998 Michael Luby and others investigated whether codes based on
`
`regular graphs would “give rise to codes that are close to optimal” and concluded
`
`that “They do not.” Ex. 1028 at 9. Instead, Luby et al. showed that making
`
`codes irregular yields “much better performance than regular” codes. Ex. 1010.
`
`at ¶ 28; Ex. 1015 at 249; Ex. 1028 at 9. By mid-1999, a paper by Richardson,
`
`Shokrollahi & Urbanke was circulating within the academic community touting
`
`
`
`7
`
`

`

`Petition for Inter Partes Review of U.S. Patent No. 7,916,781
`
`new “results indicating the remarkable performance that can be achieved by
`
`properly chosen irregular codes” Ex. 1010 at ¶¶ 28-29; Ex. 1029 at 621.1 In
`
`August 1999, Dr. David MacKay presented a talk at the IMA academic conference
`
`on sparse graph codes, in the speaking slot directly before one of the named
`
`inventors of the ‘781 patent (McEliece). Ex. 1037 p. 3. In his slides presented
`
`at that talk, Dr. MacKay showed on one page a graph of a Gallager code, a Repeat-
`
`accumulate code, a turbo code, and a recursive convolutional code. Id. at 42. On
`
`the very next slide, the suggestion “make irregular” appears as the second bullet
`
`under the heading “Where to go from Regular Gallagher Codes.” Id. at 43. The
`
`immediate juxtaposition of these sparse graph codes, which includes a repeat-
`
`accumulate code, with a suggestion to “make irregular,” demonstrates that a person
`
`of ordinary skill in the art would recognize that irregularity would improve a
`
`repeat-accumulate code. Ex. 1010 at ¶ 150. The McEliece presentation, entitled,
`
`
`1 A 2001 version of this paper dated after the applicants’ provisional filing date
`
`was disclosed during prosecution. Applicants did not disclose that earlier 1999
`
`versions of this paper were published and well known within the relevant academic
`
`community more than 1 year before the applicant’s priority date. Ex. 1010 at ¶ 28.
`
`By April 5, 1999, the author (Richardson) circulated the paper via Internet link to
`
`colleagues within the academic community by e-mail. Id.
`
`
`
`8
`
`

`

`Petition for Inter Partes Review of U.S. Patent No. 7,916,781
`
`“Repeat Accumulate Codes [A Class of Turbo-Like Codes that we can analyse]”,
`
`at the same IMA conference discussed only repeat-accumulate and did not mention
`
`making them irregular. See Ex. 1045; Ex. 1060 at ¶ 39.
`
`Thus, the prior art provided clear motivation to modify encoding schemes
`
`using irregularity to improve performance. Ex. 1010 at ¶ 33. Indeed, the Roumy
`
`paper, which Patent Owner has featured prominently in its district court complaint,
`
`makes clear that this is exactly what happened -- explaining that this prior work
`
`actually motivated the inventors of the ‘781 Patent to modify the prior art regular
`
`RA codes by introducing irregularity: “The introduction of irregular LDPCs
`
`motivated other schemes such as irregular RA . . . and irregular turbo codes.”
`
`(emphasis supplied) Ex. 1022 at page 88 (Exhibit F therein).
`
`B. Summary of References Relied Upon
`
`The Luby ‘909 Patent (Ex. 1016)
`
`The Luby ‘909 Patent (Ex. 1010) is a patent corresponding to work by Luby,
`
`Mitzenmacher, Shokrollahi, Spielman, and Stemann that was academically
`
`published in a paper entitled “Practical loss-resilient codes.” This is generally
`
`credited as the first paper to introduce the idea of irregularizing the pre-existing
`
`low-density parity check codes. Ex. 1016 at ¶ 40; Luby et al. “Practical loss-
`
`resilient codes” Exhibit 1028 at 4 n.2 (“A good candidate for the code C is the low-
`
`density parity check…”)). In the Luby paper, the authors reported that they had
`
`
`
`9
`
`

`

`Petition for Inter Partes Review of U.S. Patent No. 7,916,781
`
`developed tools to analyze regular codes, and concluded “that they cannot yield
`
`codes that are close to optimal. Hence irregular graphs are a necessary
`
`component of our design.” Ex. 1028 at 2. In view of this, the Luby ‘909 Patent
`
`describes irregular codes and touts their benefits:
`
`irregular graphing of the edges is particularly beneficial for large numbers of
`data items. … For example, encoding based upon irregular graphing of the
`edges can be used very effectively in high bandwidth video transmissions
`Ex. 1016 at 11:42-47.
`
`Divsalar (Exhibit 1011)
`
`The Divsalar reference described a rate-1 “accumulate” convolutional
`
`encoder that was shown to produce useful codes that could be easily decoded.
`
`This type of code is known in the field as a “repeat-accumulate” or “RA” code.
`
`Ex. 1010 at ¶¶ 31-32.
`
`Ping (Exhibit 1014)
`
`The Ping reference discloses using a low-density generator matrix (LDGM)
`
`coder to perform low-density parity check coding. Ex. 1010 at ¶ 33. A very
`
`similar structure with linear-time encoding was also proposed in “Constructing
`
`Low-Density Parity-Check Codes with Circulant Matrices” by Bond, Hui, and
`
`Schmidt. Id. Combining these techniques with irregular LDPC codes naturally
`
`leads to codes that are expected to perform well and have low-complexity
`
`encoding. Id.
`
`
`
`10
`
`

`

`Petition for Inter Partes Review of U.S. Patent No. 7,916,781
`
`The ’999 Patent (Exhibit 1027)
`
`The ’999 Patent, which dates to 1986, describes how codewords can “be
`
`generated in a variety of ways,” including those where information bits are sent
`
`into a communication channel followed by parity bits “thus forming the complete
`
`codeword.” Ex. 1027 at 1:25-34. The ’999 Patent thus shows it was well-
`
`known in the art to transmit information and parity bits in a variety of ways over a
`
`communication channel. Ex. 1010 at ¶ 73.
`
`V. CLAIM CONSTRUCTION
`
`Claims 1, 2, 3, 4, 5, 6, 7, 13, 14, 15, 16, and 19 of the ’781 Patent are
`
`unpatentable when given their “broadest reasonable construction in light of the
`
`specification.” See 37 C.F.R. § 42.100(b). 2 Consistent with the broadest
`
`reasonable standard, claim terms “are generally given their ordinary and customary
`
`meaning,” as understood by “a person of ordinary skill in the art in question at the
`
`time of the invention.” Phillips v. AWH Corp., 415 F.3d 1303, 1312-13 (Fed. Cir.
`
`2005). The claim terms of the ’781 Patent should be given their plain and
`
`ordinary meaning under
`
`the “broadest reasonable construction” with
`
`the
`
`considerations discussed infra.
`
`2 Petitioner reserves the right to seek different claim constructions than those
`
`determined or sought in a different forum (e.g., District Court) that applies
`
`different standards of proof and analysis.
`
`
`
`11
`
`

`

`Petition for Inter Partes Review of U.S. Patent No. 7,916,781
`
`A. Level of Ordinary Skill in the Art
`
`A person of ordinary skill in the art would have a very high skill level, and
`
`would have a Ph.D. in electrical or computer engineering with emphasis in signal
`
`processing, communications, or coding, or a master’s degree in the above area with
`
`at least three years of work experience this field at the time of the alleged invention.
`
`Ex. 1010 at ¶ 44. The patent owner has accepted this level of skill in the Lawsuit.
`
`Ex. 1026 at 98.
`
`B. "Codeword"
`
`In the District Court Action, the court ruled that the construction of
`
`codeword is “a discrete encoded sequence of data elements.” Ex. 1024 at 46. A
`
`person of ordinary skill would understand that “codeword” would include at least
`
`the court’s construction.
`
` Id.
`
` The broadest reasonable interpretation of
`
`“codeword” would therefore include the court’s construction.
`
`C. “Summing” Terms
`
`The parties in the District Court case agreed that “summing of bits in a
`
`subset of the information bits” in claim 6 should be construed as “adding together
`
`two or more information bits from a subset of information bits.” Ex. 1025 at 1.
`
`The parties in the District Court case agreed that “sums of bits in subsets of the
`
`information bits” in claim 13 should be construed as “the result(s) of adding
`
`together two or more information bits from a subset of information bits.” Ex.
`
`
`
`12
`
`

`

`Petition for Inter Partes Revi