UNITED STATES PATENT AND TRADEMARK OFFICE
`BEFORE THE PATENT TRIAL AND APPEAL BOARD
`
`In Re:
`
`U.S. Patent US 7,421,032
`
`: Attorney Docket No. 082944.0102
`
`Inventor: Hui Jin, et. al.
`
`Filed:
`
`Oct. 3, 2006
`
`
`
`
`
`Claimed Priority: May 18, 2000
`
`Issued:
`
`Sep. 2, 2008
`
`
`
`
`
`
`
`
`
`
`
`:
`
`:
`
`:
`
`: IPR No. 2015-00060
`
`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
`
`CORRECTED PETITION FOR INTER PARTES REVIEW OF CLAIMS 1, 8,
`10, 18, 19, and 22 OF U.S. PATENT NO. 7,421,032 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,421,032
`
`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 ’032 PATENT ............................................................ 4 
`
`A.  Summary of the Claimed Subject Matter ................................................ 4 
`
`B.  Prosecution History of the ’032 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.  Claim 1 - The Generating Step .............................................................. 12 
`
`C.  Claim 18 Tanner Graph ......................................................................... 13 
`
`D.  “Transmission” ...................................................................................... 14 
`
`E. 
`
`“Data Stream” ........................................................................................ 15 
`
`VI.  A REASONABLE LIKELIHOOD EXISTS THAT THE CHALLENGED
`CLAIMS ARE UNPATENTABLE .............................................................. 15 
`
`A.  Ground 1: The ‘032 Patent Claim 1 is Obvious Under 35 U.S.C.
`§ 103 over Frey in view of Divsalar...................................................... 16 
`
`B.  Ground 2: The ‘032 Patent Claims 1, 8, and 10 are Obvious Under
`35 U.S.C. § 103 over Frey in view of Divsalar and in further view of
`the Luby ‘909 Patent .............................................................................. 23 
`
`
`
`i
`
`

`
`Petition for Inter Partes Review of U.S. Patent No. 7,421,032
`
`C.  Ground 3: The ‘032 Patent Claim 1, 8 and 10 are Obvious Under 35
`U.S.C. § 103 over Frey in view of Divsalar and in further view of
`the Luby ‘909 Patent and Hall ............................................................... 28 
`
`D.  Ground 4: The ‘032 Patent Claims 18, 19, and 22 are Obvious Under
`35 U.S.C. § 103 Over Frey in View of Divsalar and in Further View
`of Kschischang ....................................................................................... 29 
`
`E.  Ground 5: The ‘032 Patent Claims 18, 19, and 22 are Obvious Under
`35 U.S.C. § 103 Over Frey in View of Divsalar and Kschischang
`and in Further View of Hall ................................................................... 41 
`
`F.  Ground 6: The ‘032 Patent Claims 1 and 8 are Obvious Under 35
`U.S.C. § 103 over Divsalar in view of the Luby ‘909 Patent ............... 42 
`
`G.  Ground 7: The ‘032 Patent Claims 18 and 22 are Obvious Under 35
`U.S.C. § 103 Over Divsalar in view of the Luby ‘909 Patent and in
`Further View of Kschischang ................................................................ 49 
`
`H.  Ground 8: The ‘032 Patent Claim 10 is Obvious Under 35 U.S.C.
`§ 103 over Divsalar in view of the Luby ‘909 Patent and in further
`view of Ping ........................................................................................... 53 
`
`I.  Ground 9: The ‘032 Patent Claim 19 is Obvious Under 35 U.S.C.
`§ 103 over Divsalar in view of the Luby ‘909 Patent and
`Kschischang and in further view of Ping ............................................... 55 
`
`VII.  CONCLUSION .............................................................................................. 56 
`
`
`
`ii
`
`

`
`Petition for Inter Partes Review of U.S. Patent No. 7,421,032
`
`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,916,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,421,032
`
`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,421,032
`
` 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,421,032
`
`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,421,032
`
`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,421,032
`
`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,421,032
`
`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 ’032 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,421,032
`
`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 ’032 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, 8, 10, 18, 19, and 22 of U.S. Patent No.
`
`7,421,032 by Hui Jin, et. al. (“the ’032 Patent”), titled “Serial Concatenation of
`
`Interleaved Convolutional Codes Forming Turbo-Like Codes.” See Ex. 1003.
`
`A.
`
`Publications Relied Upon
`
`Petitioner relies upon the following patents and publications:
`
`Exhibit 1012 - “Irregular Turbocodes” by B.J. Frey and D.J.C. MacKay
`
`(“Frey”), published at least by October 8, 1999 and available as prior art under 35
`
`U.S.C. § 102(a); see also Ex. 1060 at ¶¶ 40-49.
`
`Exhibit 1011 - “Coding Theorems for "Turbo-like" Codes” by D. Divsalar,
`
`
`
`2
`
`

`
`Petition for Inter Partes Review of U.S. Patent No. 7,421,032
`
`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.
`
`Exhibit 1017 - “Iterative decoding of compound codes by probability
`
`propagation in graphical models” by F. R. Kschischang and B. J. Frey,
`
`(“Kschischang”) published at least by February 23, 1998 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 1013 - “Stream-Oriented Turbo Codes” by E.K. Hall and S.G.
`
`Wilson (“Hall”), published at least by June 23, 1998 and available as prior art
`
`under 35 U.S.C. § 102(a).
`
`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).
`
`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:
`
`
`
`3
`
`

`
`Petition for Inter Partes Review of U.S. Patent No. 7,421,032
`
`1.
`
`2.
`
`Claim 1 is obvious over Frey in view of Divsalar.
`
`Claims 1, 8 and 10 are obvious over Frey in view of Divsalar and
`
`in further view of the Luby ‘909 Patent.
`
`3.
`
`Claims 1, 8, and 10 are obvious over Frey in view of Divsalar and
`
`in further view of Hall.
`
`4.
`
`Claims 18, 19, and 22 are obvious over Frey in view of Divsalar
`
`and in further view of Kschischang.
`
`5.
`
`Claims 18, 19, and 22 are obvious over Frey in view of Divsalar
`
`and in further view of Kschischang and in further view of Hall.
`
`6.
`
`Claims 1 and 8 are obvious over Divsalar in view of the Luby ‘909
`
`Patent.
`
`7.
`
`Claims 18 and 22 are obvious over Divsalar in view of the Luby
`
`‘909 Patent and in further view of Kschischang.
`
`8.
`
`Claim 10 is obvious over Divsalar in view of the Luby ‘909 Patent
`
`and in further view of Ping.
`
`9.
`
`Claim 19 is obvious over Divsalar in view of the Luby ‘909 and in
`
`further view of Kschischang and in further view of Ping.
`
`III. OVERVIEW OF THE ’032 PATENT
`
`A.
`
`Summary of the Claimed Subject Matter
`
`The ’032 Patent relates to irregular repeat accumulate (“RA”) coding for
`
`
`
`4
`
`

`
`Petition for Inter Partes Review of U.S. Patent No. 7,421,032
`
`transmission of communication signals. Claim 1 describes generating a sequence
`
`of parity bits for a sequence of message bits according to a specified formula.
`
`The formula requires irregular repeats of the message bits. Claim 8 describes
`
`transmitting the parity bits while Claim 10 describes transmitting the parity bits as
`
`part of a systematic code. Claim 18 describes a message passing decoder
`
`configured to receive data that includes parity bits. The decoder decodes data that
`
`has been encoded according to a graphical model (called a Tanner graph). Claim
`
`19 describes decoding the received data including the message bits. Claim 22
`
`describes that the decoder is a belief propagation decoder.
`
`B.
`
`Prosecution History of the ’032 Patent
`
`The application resulting in the ’032 Patent was filed on October 3, 2006 as
`
`a continuation of U.S. Application No. 09/861,102, filed on May 18, 2001, now
`
`U.S. Patent No. 7,116,710, which claimed priority to U.S. Provisional Application
`
`Serial No. 60/205,095, filed on May 18, 2000. Ex. 1003.
`
`The application resulting in the ’032 Patent was also filed as a continuation-
`
`in-part of U.S. Application No. 09/922,852, filed on Aug. 18, 2000, now Pat. No.
`
`7,089,477. The patent examiner initially allowed pending claims 1-17 and
`
`rejected the others. Ex. 1004 at 46. Applicants thereafter amended claim 18 to
`
`include the limitation of the otherwise allowed claim 20. Id. at 77-84. On
`
`February 25, 2008, the patent examiner issued a notice of allowance. Ex. 1004 at
`
`
`
`5
`
`

`
`Petition for Inter Partes Review of U.S. Patent No. 7,421,032
`
`93. Applicants later amended to claim priority to U.S. Patent Application
`
`09/922,852 as a continuation-in-part, rather than a continuation. Id. at 103.
`
`IV. SUMMARY OF PRIOR ART
`
`A.
`
`State of the Art
`
`The ’032 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 ‘032 patent is
`
`directed to irregular repeat-accumulate (“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, 33.
`
`One prior art technique for generating parity information 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
`
`
`
`6
`
`

`
`Petition for Inter Partes Review of U.S. Patent No. 7,421,032
`
`by two of the three inventors of the ‘032 Patent in September 1998, more than one
`
`year before the earliest priority claim of the ‘032 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
`
`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
`
`1 A 2001 version of this paper dated after the applicants’ provisional filing date
`
`
`
`7
`
`

`
`Petition for Inter Partes Review of U.S. Patent No. 7,421,032
`
`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 ‘032 Patent (McEliece). Ex. 1037 at 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 ¶ 156. The McEliece presentation,
`
`entitled, “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.
`
`
`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,421,032
`
`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 ‘032 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
`
`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
`
`
`
`9
`
`

`
`Petition for Inter Partes Review of U.S. Patent No. 7,421,032
`
`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.
`
`Frey (Exhibit 1012)
`
`The Frey reference built upon the work of Luby by applying irregular
`
`coding techniques to prior art turbocodes. Ex. 1010 at ¶ 29. The Frey reference
`
`describes this as “tweaking the regular turbocode originally introduced by Berrou
`
`et al” Ex. 1012 at 7. This reference also shows graphically that repeat-accumulate
`
`codes are simply examples of the more general turbocode. Id. at pp. 3-4 (Figs. 1 &
`
`2).
`
`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.
`
`Kschischang (Exhibit 1017)
`
`The Kschischang reference describes graphical models, including Tanner
`
`graphs, for decoding a variety of coding systems including low-density parity-
`
`check codes. Ex. 1017 at 1, 7; Ex. 1010 at ¶ 98.
`
`10
`
`
`
`

`
`Petition for Inter Partes Review of U.S. Patent No. 7,421,032
`
`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.
`
`Hall (Exhibit 1013)
`
`The Hall reference describes a streaming-oriented turbocode, showing how
`
`to use prior art coding and decoding principles which were traditionally “block
`
`coding” approaches in a streaming paradigm “without explicit block boundaries.”
`
`Ex. 1010 at ¶¶ 59-60; Ex. 1013 at 71.
`
`V. CLAIM CONSTRUCTION
`
`Claims 1, 8, 10, 18, 19, and 22 of the ’032 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 ’032 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 by the Board or sought herein 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,421,032
`
`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