throbber
Case 6:20-cv-01042-ADA Document 1-2 Filed 11/11/20 Page 1 of 15
`Case 6:20-cv-01042—ADA Document 1-2 Filed 11/11/20 Page 1 of 15
`
`6:20-cv-1042
`
`6:20-cv- 1042
`
`EXHIBIT B
`
`EXHIBIT B
`
`

`

`Case 6:20-cv-01042-ADA Document 1-2 Filed 11/11/20 Page 2 of 15
`Case 612°‘CV'01042'ADA D(“”1111llllfllllfllllllllll'lllll’llllfillllllllllllllllllllll'llll||||||||
`
`
`US007421032B2
`
`
`
`
`
`
`
`
`
`(12) United States Patent
`US 7,421,032 B2
`(10) Patent N0.:
`
`
`
`
`
`
`
`Jin et al.
`
`(45) Date of Patent: Sep. 2, 2008
`
`
`
`
`
`
`(54) SERIAL CONCATENATION 0F
`INTERLEAVED CONVOLUTIONAL CODES
`
`
`FORMING TURBO-LIKE CODES
`
`
`
`
`
`
`(56)
`
`
`
`
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`
`
`
`
`
`(73) Assignee:
`
`
`
`(75)
`
`
`
`(*)
`
`
`
`(21)
`
`(22)
`
`(65)
`
`
`
`
`
`(63)
`
`
`
`(60)
`
`(51)
`
`(52)
`
`(58)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Inventors: Hui Jin, Glen Gardner, NJ (US); Aamod
`
`
`
`Khandekar, Pasadena, CA (US);
`
`
`
`Robert J. McEliece, Pasadena, CA (US)
`
`
`
`Callifornia Institute of Technology,
`
`
`Pasadena, CA (US)
`
`
`
`
`
`
`Subject to any disclaimer, the term of this
`
`
`
`
`patent is extended or adjusted under 35
`
`
`
`U.S.C. 154(b) by 0 days.
`
`Notice:
`
`
`
`
`Appl. No.:
`
`
`
`11/542,950
`
`
`
`Filed:
`
`
`
`
`
`Oct. 3, 2006
`Prior Publication Data
`
`
`
`
`
`US 2007/0025450 A1
`Feb. 1, 2007
`
`
`
`
`
`
`
`
`Related US. Application Data
`
`
`
`
`
`Continuation of application No. 09/861,102, filed on
`
`
`
`
`
`
`
`
`May 18, 2001, now Pat. No. 7,116,710, and a continu-
`
`
`
`
`
`ation-in—part of application No. 09/922,852, filed on
`
`
`
`
`
`
`
`Aug. 18, 2000, now Pat. No. 7,089,477.
`
`
`
`
`
`Provisional application No. 60/205,095, filed on May
`
`
`18, 2000.
`Int. Cl.
`
`
`
`
`(2006.01)
`H04L 5/12
`
`
`
`
`
`....................... 375/262; 375/265; 375/348;
`US. Cl.
`
`
`
`
`714/755; 714/786; 714/792; 341/52; 341/102
`
`
`
`
`Field of Classification Search ................. 375/259,
`
`
`
`
`
`
`375/262, 265, 285, 296, 341, 346, 348; 714/746,
`
`
`
`
`
`
`
`714/752, 755, 756, 786, 792, 7947796; 341/51,
`
`
`
`341/52,56,102,103
`
`
`
`
`
`
`
`See application file for complete search history.
`
`
`
`
`
`
`
`
`
`
`
`
`
`5,392,299 A
`
`5,530,707 A *
`
`5,751,739 A
`
`
`5,802,115 A *
`
`5,881,093 A
`
`6,014,411 A
`6,023,783 A
`
`6,031,874 A
`
`6,032,284 A
`
`
`6,044,116 A
`6,094,739 A *
`
`
`
`
`
`
`2/1995 Rhines et a1.
`
`
`
`6/1996 Lin ............................ 714/792
`
`
`
`5/1998 Seshadri et a1.
`
`
`
`
`
`
`9/1998 Meyer ........................ 375/341
`
`
`3/1999 Wang et a1.
`
`
`1/2000 Wang
`2/2000 Divsalar et a1.
`
`
`
`2/2000 Chennakeshu et a1.
`
`
`2/2000 Bliss
`
`
`
`
`
`3/2000 Wang
`7/2000 Miller et a1.
`
`
`
`
`
`................ 714/792
`
`
`
`
`
`(Continued)
`OTHER PUBLICATIONS
`
`
`
`
`
`
`
`
`
`Appendix A.l “Structure of Parity Check Matrices of Standardized
`
`
`
`
`
`
`
`LDPC Codes,” Digital Video Broadcasting (DVB) User guidelines
`
`
`
`
`
`
`
`
`for the second generation system for Broadcasting, Interactive Ser-
`
`
`
`
`
`
`
`vices, News Gathering and other broadband satellite applications
`
`
`
`
`
`
`
`(DVB-S2) ETSI TR 102 376 V1.1.1. (Feb. 2005) Technical Report,
`
`
`pp. 64.
`
`
`
`
`
`
`
`
`
`(Continued)
`
`
`
`Primary ExamineriDac V. Ha
`
`
`
`
`
`(74) Attorney, Agent, or FirmiFish & Richardson PC.
`
`
`
`(57)
`
`ABSTRACT
`
`
`
`A serial concatenated coder includes an outer coder and an
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`inner coder. The outer coder irregularly repeats bits in a data
`
`
`
`
`
`
`
`
`block according to a degree profile and scrambles the
`
`
`
`
`
`
`
`
`
`repeated bits. The scrambled and repeated bits are input to an
`
`
`
`
`
`
`
`
`inner coder, which has a rate substantially close to one.
`
`
`
`
`23 Claims, 5 Drawing Sheets
`
`
`
`Check Node
`
`
`degree a
`
`
`
`Variable Node
`
`
`Fraction of nodes
`
`
`
`degree i \ )
`. | l
`
`
`
`
`
`
`
`
`2““Si
`
`f2
`
`f3
`
`Q
`
`
`
`
`
` V1
`6%
`
`
`
`
` egg
`
`
`
`
`
`~———*
`
`2:)
`302
`
`
`302
`r‘x
`o 1 l ,2
`
`
`
`
`
`
`1 \
`
`
`)...
`
`
`
`E———»_
`
`
`
`
`
`
`
`
`
`$3
`
`
`
`
` $9
`
`RANDOMPEHMUTATION
`
`
`
`
`

`

`Case 6:20-cv-01042-ADA Document 1-2 Filed 11/11/20 Page 3 of 15
`Case 6:20-cv-01042-ADA Document 1-2 Filed 11/11/20 Page 3 of 15
`
`
`
`US 7,421,032 B2
`
`
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`
`5/2002 Laumen et a1.
`6,396,423 B1
`
`
`
`
`8/2002 Kim et a1.
`6,437,714 B1
`
`
`
`
`
`
`2/2005 Hammons et a1.
`6,859,906 B2*
`
`
`
`9/2001 Eidson et a1.
`2001/0025358 A1
`
`
`
`
`
`
`OTHER PUBLICATIONS
`
`
`
`
`
`
`
`
`
`
`
`
`........... 714/786
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Benedetto et al., “A Soft-Input Soft-Output Maximum A Posteriori
`
`
`
`
`
`
`
`
`(MAP) Module to Decode Parallel and Serial Concatenated Codes,”
`
`
`
`
`
`
`
`The Telecommunications and Data Acquisition (TDA) Progress
`
`
`
`
`
`
`
`Report 42-127 for NASA and California Institute of Technology Jet
`
`
`
`
`
`
`
`
`
`
`Propulsion Laboratory, Jospeh H. Yuen, Ed., pp. 1-20 (Nov. 15,
`
`1996).
`
`
`
`
`
`
`Benedetto et a1., “Bandwidth efficient parallel concatenated coding
`
`
`
`
`
`
`
`
`schemes,” Electronics Letters 31(24): 2067-2069 (Nov. 23, 1995).
`
`
`
`
`
`
`Benedetto et a1., “Design of Serially Concatenated Interleaved
`
`
`
`
`
`
`
`
`Codes,” ICC 97, Montreal, Canada, pp. 710-714, ( Jun. 1997).
`Benedetto et a1., “Parallel Concatenated Trellis Coded Modulation,”
`
`
`
`
`
`
`
`
`
`
`
`
`ICC ’96, IEEE, pp. 974-978, (Jun. 1996).
`Benedetto et a1., “Serial Concatenated Trellis Coded Modulation
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`With Iterative Decoding,” Proceedings from the IEEE 1997 Interna-
`
`
`
`
`
`
`
`tional Symposium on Information Theory (ISIT), Ulm, Germany, p.
`8, Jun. 29-Ju1. 4, 1997.
`
`
`
`
`Benedetto et a1., “Serial Concatenation of Interleaved Codes: Perfor-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`mance Analysis, Design, and Iterative Decoding,” The Telecommu-
`
`
`
`
`
`
`
`
`
`nications and Data Acquisition (TDA) Progress Report 42-126 for
`
`
`
`
`
`
`NASA and California Institute of Technology Jet Propulsion Labo-
`
`
`
`
`
`
`
`
`
`ratory, Jospeh H.Yuen, Ed., pp. 1-26 (Aug. 15, 1996).
`
`
`
`
`
`
`Benedetto et a1., “Serial Concatenation of interleaved codes: perfor-
`
`
`
`
`
`
`
`mance analysis, design, and iterative decoding,” Proceedings from
`
`
`
`
`
`
`the IEEE 1997 International Symposium on Information Theory
`
`
`
`
`
`
`
`(ISIT), Ulm, Germany, p. 106, Jun. 29-Ju1. 4, 1997.
`
`
`
`
`
`
`
`Benedetto et a1., “Soft-output decoding algorithms in iterative decod-
`
`
`
`
`
`
`
`
`ing of turbo codes,” The Telecommunications and Data Acquisition
`
`
`
`
`
`
`
`(TDA) Progress Report 42-124 for NASA and California Institute of
`
`
`
`
`
`
`
`
`
`Technology Jet Propulsion Laboratory, Jospeh H. Yuen, Ed., pp.
`
`
`
`
`63-87 (Feb. 15, 1996).
`
`
`
`
`
`
`
`
`
`Benedetto, S. et al., “A Soft-Input Soft-Output APP Module for
`
`
`
`
`
`
`Iterative Decoding of Concatenated Codes,” IEEE Communications
`
`
`
`
`
`Letters 1(1): 22-24 (Jan. 1997).
`
`
`
`
`
`
`
`Berrou et a1., “Near Shannon Limit Error-Correcting Coding and
`
`
`
`
`
`
`Decoding: Turbo Codes,” ICC pp. 1064-1070 (1993).
`
`
`
`
`
`
`
`
`
`Digital Video Broadcasting (DVB) User guidelines for the second
`
`
`
`
`
`
`
`generation system for Broadcasting, Interactive Services, News
`
`
`
`
`
`
`
`
`Gathering and other broadband satellite applications (DVB-SZ) ET SI
`
`
`
`
`
`
`
`
`
`
`TR 102 376V1.1.1. (Feb. 2005) Technical Report, pp. 1-104 (Feb. 15,
`
`2005).
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Divsalar et a1., “Coding Theorems for ‘Turbo-Like’ Codes,” Proceed-
`
`
`
`
`
`
`ings of the 36th Annual Allerton Conference on Communication,
`
`
`
`
`
`
`
`Control, and Computing, Sep. 23-25, 1998, Allerton House,
`
`
`
`
`
`Monticello, Illinois, pp. 201-210 (1998).
`Divsalar et a1., “Effective free distance of turbo codes,” Electronics
`
`
`
`
`
`
`
`
`
`
`
`
`
`Letters 32(5): 445-446 (Feb. 29, 1996).
`
`
`
`
`
`
`
`
`Divsalar, D. et a1., “Hybrid Concatenated Codes and Iterative Decod-
`
`
`
`
`
`
`
`
`ing,” Proceedings from the IEEE 1997 International Symposium on
`
`
`
`
`
`
`
`
`Information Theory (ISIT), Ulm, Germany, p. 10 (Jun. 29-Ju1. 4,
`
`1997).
`
`
`
`
`
`
`
`
`Divsalar, D. et a1., “Low-rate turbo codes for Deep Space Commu-
`
`
`
`
`
`
`
`nications,” Proceedings from the 1995 IEEE International Sympo-
`
`
`
`
`
`
`
`sium on Information Theory, Sep. 17-22, 1995, Whistler, British
`
`
`
`
`Columbia, Canada, pp. 35.
`
`
`
`
`
`
`Divsalar, D. et a1., “Multiple Turbo Codes for Deep-Space Commu-
`
`
`
`
`
`
`nications,” The Telecommunications and Data Acquisition (TDA)
`
`
`
`
`
`
`
`Progress Report 42-121 for NASA and California Institute of Tech-
`
`
`
`
`
`
`
`
`nology Jet Propulsion Laboratory, Jospeh H. Yuen, Ed., pp. 60-77
`
`
`(May 15, 1995).
`
`
`
`
`
`
`
`Divsalar, D. et a1., “Multiple Turbo Codes,” MILCOM 95, San Diego,
`
`
`
`
`
`CA pp. 279-285 (Nov. 5-6, 1995).
`
`
`
`
`
`
`
`Divsalar, D. et a1., “On the Design of Turbo Codes,” The Telecom-
`
`
`
`
`
`
`
`
`munications and DataAcquisition (TDA) Progress Report 42-123 for
`
`
`
`
`
`NASA and California Institute of Technology Jet Propulsion Labo-
`
`
`
`
`
`
`
`
`
`ratory, Jospeh H.Yuen, Ed., pp. 99-131 (Nov. 15, 1995).
`Divsalar, D. et al., “Serial Turbo Trellis Coded Modulation with
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Rate-1 Inner Code,” Proceedings from the IEEE 2000 International
`
`
`
`
`
`
`
`Symposium on Information Theory (ISIT), Italy, pp. 1-14 (Jun.
`
`2000).
`
`
`
`
`
`
`
`
`
`Divsalar, D. et a1., “Turbo Codes for PCS Applications,” ICC 95,
`
`
`
`
`
`
`IEEE, Seattle, WA, pp. 54-59 (Jun. 1995).
`
`
`
`
`
`
`Jin et a1., “Irregular RepeatiAccumulate Codes,” 2nd International
`
`
`
`
`
`
`
`
`Symposium on Turbo Codes & Related Topics, Sep. 4-7, 2000, Brest,
`
`
`
`
`
`France, 25 slides, (presented on Sep. 4, 2000).
`
`
`
`
`
`
`Jin et al., “Irregular RepeatiAccumulate Codes,” 2nd International
`
`
`
`
`
`
`
`
`Symposium on Turbo Codes & Related Topics, Sep. 4-7, 2000, Brest,
`
`
`
`
`France, pp. 1-8 (2000).
`
`
`
`
`
`
`Richardson et a1., “Design of capacity approaching irregular low
`
`
`
`
`
`
`
`
`density parity check codes,” IEEE Trans. Inform. Theory 47: 619-637
`
`
`(Feb. 2001).
`
`
`
`
`
`Richardson, T. and R. Urbanke, “Efficient encoding of low-density
`
`
`
`
`
`
`
`
`
`parity check codes,” IEEE Trans. Inform. Theory 47: 638-656 (Feb.
`
`2001).
`
`
`
`
`
`
`
`Wilberg, et al., “Codes and Iteratie Decoding on General Graphs”,
`
`
`
`
`
`
`
`
`1995 Intl. Symposium on Information Theory, Sep. 1995, p. 468.
`
`
`
`* cited by examiner
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`Case 6:20-cv-01042-ADA Document 1-2 Filed 11/11/20 Page 4 of 15
`Case 6:20-cv-01042-ADA Document 1-2 Filed 11/11/20 Page 4 of 15
`
`
`US. Patent
`
`
`
`
`Sep. 2, 2008
`
`
`
`
`
`Sheet 1 0f5
`
`
`
`US 7,421,032 B2
`
`
`
`FIG.1 (PriorArt)
`
`
`
`

`

`Case 6:20-cv-01042-ADA Document 1-2 Filed 11/11/20 Page 5 of 15
`Case 6:20-cv-01042-ADA Document 1-2 Filed 11/11/20 Page 5 of 15
`
`
`US. Patent
`
`
`
`
`Sep. 2, 2008
`
`
`
`
`Sheet 2 0f5
`
`
`
`US 7,421,032 B2
`
`
`
`C.)
`C.)
`<(
`
`c
`
`
`
`
`
`
`w-
`
`as
`
`IT.
`
`
`N
`
`
`
`as
`t
`
`x
`
`
`
`
`l
`
`
`2(
`
`DD_
`
`x
`
`
`
`
`

`

`Case 6:20-cv-01042-ADA Document 1-2 Filed 11/11/20 Page 6 of 15
`Case 6:20-cv-01042-ADA Document 1-2 Filed 11/11/20 Page 6 of 15
`
`
`US. Patent
`
`
`
`
`Sep. 2, 2008
`
`
`
`
`Sheet 3 0f5
`
`
`
`US 7,421,032 B2
`
`
`
`Variable Node
`Fraction of nodes
`degree i
`
`
`
`
`Check Node
`degree a
`
`
`
`""K
`
`/:-.\
`
`m
`
`..__2
`
`‘
`
`E
`
`E
`1‘“
`
`=
`,
`
`
`FIG. 3
`
`.‘U 1,
`E
`:
`
`‘1
`E
`
`302
`
`2 E
`
`E
`302
`:
`o——-il-
`E
`‘
`.'
`0:
`'.
`.
`E.“
`,i
`-
`1
`"-4021, 2
`

`
`f?
`
`f3
`
`0'
`
`

`

`Case 6:20-cv-01042-ADA Document 1-2 Filed 11/11/20 Page 7 of 15
`Case 6:20-cv-01042-ADA Document 1-2 Filed 11/11/20 Page 7 of 15
`
`
`US. Patent
`
`
`
`
`Sep. 2, 2008
`
`
`
`
`Sheet 4 0f5
`
`
`
`US 7,421,032 B2
`
`
`
`
`FIG. 5A
`
`304
`
`
`
`
`
`
`
`
`FIG. 53
`
`

`

`Case 6:20-cv-01042-ADA Document 1-2 Filed 11/11/20 Page 8 of 15
`Case 6:20-cv-01042-ADA Document 1-2 Filed 11/11/20 Page 8 of 15
`
`
`U.S. Patent
`
`
`
`
`Sep. 2, 2008
`
`
`
`
`Sheet 5 of 5
`
`
`
`US 7,421,032 B2
`
`
`
`
`
`

`

`Case 6:20-cv-01042-ADA Document 1-2 Filed 11/11/20 Page 9 of 15
`Case 6:20-cv-01042-ADA Document 1-2 Filed 11/11/20 Page 9 of 15
`
`
`
`US 7,421,032 B2
`
`
`1
`SERIAL CONCATENATION OF
`
`
`INTERLEAVED CONVOLUTIONAL CODES
`
`
`FORMING TURBO-LIKE CODES
`
`
`
`
`
`
`CROSS-REFERENCE TO RELATED
`
`APPLICATIONS
`
`
`
`
`
`
`
`
`
`
`This application is a continuation of US. application Ser.
`
`
`
`
`
`
`
`
`
`
`No. 09/861,102, filed May 18, 2001, now US. Pat.No. 7,116,
`
`
`
`
`
`
`
`
`710, which claims the priority ofUS. provisional application
`
`
`
`
`
`
`
`
`Ser. No. 60/205,095, filed May 18, 2000, and is a continua-
`
`
`
`
`
`
`
`tion-in-part of US. application Ser. No. 09/922,852, filed
`
`
`
`
`
`
`
`
`Aug. 18, 2000, now US. Pat. No. 7,089,477.
`GOVERNMENT LICENSE RIGHTS
`
`
`
`
`
`10
`
`
`
`15
`
`
`
`
`
`
`
`
`
`
`
`The US. Government has a paid-up license in this inven-
`
`
`
`
`
`
`
`
`
`tion and the right in limited circumstances to require the
`
`
`
`
`
`
`
`
`patent owner to license others on reasonable terms as pro-
`
`
`
`
`
`
`
`vided for by the terms of Grant No. CCR-9804793 awarded
`
`
`
`
`by the National Science Foundation.
`BACKGROUND
`
`
`
`
`
`
`
`
`
`
`
`Properties ofa channel affect the amount of data that can be
`
`
`
`
`
`
`
`
`handled by the channel. The so-called “Shannon limit”
`defines the theoretical limit of the amount of data that a
`
`
`
`
`
`
`
`
`
`
`
`
`channel can carry.
`
`
`
`
`
`
`
`
`Different techniques have been used to increase the data
`
`
`
`
`
`
`
`
`rate that can be handled by a channel. “Near Shannon Limit
`
`
`
`
`
`
`Error-Correcting Coding and Decoding: Turbo Codes,” by
`
`
`
`
`
`
`
`Berrou et al. ICC, pp 1064-1070, (1993), described a new
`
`
`
`
`
`
`
`
`“turbo code” technique that has revolutionized the field of
`
`
`
`
`
`
`
`
`error correcting codes. Turbo codes have sufficient random-
`ness to allow reliable communication over the channel at a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`high data rate near capacity. However, they still retain suffi-
`
`
`
`
`
`
`
`
`cient structure to allow practical encoding and decoding algo-
`
`
`
`
`
`
`
`
`
`rithms. Still, the technique for encoding and decoding turbo
`
`
`
`
`codes can be relatively complex.
`A standard turbo coder 100 is shown in FIG. 1. 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 kbits, 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 esti-
`
`
`
`
`
`
`
`
`mates are used to decode the uncoded information bits as
`
`
`
`
`
`
`
`
`
`
`
`
`
`corrupted by the noisy channel.
`
`SUMMARY
`
`
`
`
`
`
`
`
`
`A coding system according to an embodiment is config-
`
`
`
`
`
`
`
`
`
`ured to receive a portion of a signal to be encoded, for
`
`
`
`
`
`
`
`
`example, a data block including a fixed number of bits. The
`
`
`
`
`
`
`
`
`coding system includes an outer coder, which repeats and
`
`
`
`
`
`
`
`
`
`scrambles bits in the data block. The data block is apportioned
`
`
`
`
`
`
`
`
`into two or more sub-blocks, and bits in different sub-blocks
`
`
`
`
`
`
`are repeated a different number of times according to a
`
`
`
`
`
`
`
`
`selected degree profile. The outer coder may include a
`
`20
`
`25
`
`
`
`30
`
`
`
`35
`
`
`
`40
`
`
`
`45
`
`
`
`50
`
`
`
`55
`
`
`
`60
`
`
`
`65
`
`
`
`2
`
`
`
`
`
`
`
`
`
`
`
`repeater with a variable rate and an interleaver. Alternatively,
`
`
`
`
`
`
`the outer coder may be a low-density generator matrix
`
`
`(LDGM) coder.
`
`
`
`
`
`
`
`
`
`The repeated and scrambled bits are input to an inner coder
`
`
`
`
`
`
`
`
`
`
`that has a rate substantially close to one. The inner coder may
`
`
`
`
`
`
`
`include one or more accumulators that perform recursive
`
`
`
`
`
`
`
`
`modulo two addition operations on the input bit stream.
`
`
`
`
`
`
`
`
`
`The encoded data output from the inner coder may be
`transmitted on a channel and decoded in linear time at a
`
`
`
`
`
`
`
`
`
`
`
`
`
`destination using iterative decoding techniques. The decod-
`
`
`
`
`
`
`
`ing techniques may be based on a Tanner graph representation
`of the code.
`
`
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 1 is a schematic diagram of a prior “turbo code”
`
`system.
`
`
`
`
`
`FIG. 2 is a schematic diagram of a coder according to an
`embodiment.
`
`
`
`
`
`
`
`
`FIG. 3 is a Tanner graph for an irregular repeat and accu-
`
`
`
`mulate (IRA) coder.
`
`
`
`
`
`FIG. 4 is a schematic diagram of an IRA coder according to
`an embodiment.
`
`
`
`
`
`
`
`
`FIG. 5A illustrates a message from a variable node to a
`
`
`
`
`
`
`check node on the Tanner graph of FIG. 3.
`
`
`
`
`
`
`
`FIG. 5B illustrates a message from a check node to a
`
`
`
`
`
`
`variable node on the Tanner graph of FIG. 3.
`
`
`
`
`
`FIG. 6 is a schematic diagram of a coder according to an
`alternate embodiment.
`
`
`
`
`
`
`
`FIG. 7 is a schematic diagram of a coder according to
`another alternate embodiment.
`
`
`
`
`
`
`DETAILED DESCRIPTION
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 2 illustrates a coder 200 according to an embodiment.
`
`
`
`
`
`
`
`
`
`The coder 200 may include an outer coder 202, an interleaver
`
`
`
`
`
`
`
`
`
`
`204, and inner coder 206. The coder may be used to format
`
`
`
`
`
`
`
`blocks of data for transmission, introducing redundancy into
`
`
`
`
`
`
`
`
`
`
`the stream of data to protect the data from loss due to trans-
`
`
`
`
`
`
`
`
`mission errors. The encoded data may then be decoded at a
`
`
`
`
`
`
`
`
`
`destination in linear time at rates that may approach the chan-
`
`
`nel capacity.
`The outer coder 202 receives the uncoded data. The data
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`may be partitioned into blocks of fixed size, say 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 11 data bits. The mathematical
`
`
`
`
`
`relationship between u and v is v:TOu, where T0 is an n><k
`
`
`
`
`
`
`matrix, and the rate 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 11 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:T,w,
`
`
`
`
`
`
`
`
`where T,is a nonsingular n><n matrix. The inner coder 210 can
`
`
`
`
`
`
`
`
`have a rate that is close to 1, e.g., within 50%, more preferably
`
`
`
`
`
`
`
`10% and perhaps even more preferably within 1% of 1.
`
`
`
`
`
`
`In an embodiment, the inner coder 206 is an accumulator,
`
`
`
`
`
`
`
`
`which produces outputs that are the modulo two (mod-2)
`
`
`
`
`
`
`
`
`
`

`

`Case 6:20-cv-01042-ADA Document 1-2 Filed 11/11/20 Page 10 of 15
`Case 6:20-cv-01042-ADA Document 1-2 Filed 11/11/20 Page 10 of 15
`
`
`
`US 7,421,032 B2
`
`
`3
`
`
`
`
`
`
`
`partial sums of its inputs. The accumulator may be a truncated
`rate-l recursive convolutional coder with the transfer func-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`tion l/(l +D). Such an accumulator may be considered a block
`
`
`
`
`
`
`
`
`
`
`coder whose input block [x1,
`.
`,xn] and output block
`.
`.
`
`
`
`
`.
`. ,yn] are related by the formula
`[y1, .
`Y1:X1
`
`
`y2:x177x2
`
`
`
`y3:x1"x2®x3
`
`
`
`
`
`yn:xl@x2@x3@. .
`
`
`. flax".
`
`
`
`
`
`
`
`
`
`
`
`where “69” denotes mod-2, or exclusive-OR (XOR), addition.
`
`
`
`
`
`
`
`
`An advantage of this system is that only mod-2 addition is
`
`
`
`
`
`
`
`necessary for the accumulator. The accumulator may be
`
`
`
`
`
`
`
`
`
`embodied using only XOR gates, which may simplify the
`
`design.
`
`
`
`
`
`
`
`
`
`
`The bits output from the outer coder 202 are scrambled
`
`
`
`
`
`
`
`
`
`
`before they are input to the inner coder 206. This scrambling
`
`
`
`
`
`
`
`may be performed by the interleaver 204, which performs a
`
`
`
`
`
`pseudo-random permutation of an input block v, yielding an
`
`
`
`
`
`
`output block w having the same length as V.
`
`
`
`
`
`
`The serial concatenation of the interleaved irregular repeat
`
`
`
`
`
`
`
`
`code and the accumulate code produces an irregular repeat
`
`
`
`
`
`
`
`
`
`and accumulate (IRA) code. An IRA code is a linear code, and
`
`
`
`
`
`
`
`
`as such, may be represented as a set of parity checks. The set
`
`
`
`
`
`
`
`of parity checks may be represented in a bipartite graph,
`
`
`
`
`
`
`
`
`called the Tanner graph, of the code. FIG. 3 shows a Tanner
`
`
`
`
`
`
`
`
`
`graph 300 of an IRA code with parameters (f1,
`.
`.
`, f}; a),
`.
`
`
`
`
`
`
`
`
`
`where 13:0, Eiffl and “a” is a positive integer. The Tanner
`
`
`
`
`
`
`
`
`
`graph includes two kinds of nodes: variable nodes (open
`
`
`
`
`
`
`
`
`
`circles) and check nodes (filled circles). There are k variable
`
`
`
`
`
`
`
`
`
`nodes 302 on the left, called information nodes. There are r
`
`
`
`
`
`
`
`
`
`variable nodes 306 on the right, called parity nodes. There are
`
`
`
`
`
`
`
`r:(kZl.ifl.)/a check nodes 304 connected between the informa-
`
`
`
`
`
`
`
`
`
`tion nodes and the parity nodes. Each information node 3 02 is
`connected to a number of check nodes 304. The fraction of
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`information nodes connected to exactly i check nodes is fi.
`
`
`
`
`
`
`
`
`For example, in the Tanner graph 300, each of the f2 informa-
`
`
`
`
`
`
`
`
`tion nodes are connected to two check nodes, corresponding
`
`
`
`
`
`
`
`to a repeat of q:2, and each of the f3 information nodes are
`
`
`
`
`
`
`cc a,
`connected to three check nodes, corresponding to q:3.
`
`
`
`
`
`
`
`
`
`Each check node 304 is connected to exactly a informa- 50
`
`
`
`
`
`
`
`tion nodes 302. In FIG. 3, a:3. These connections can be
`
`
`
`
`
`
`made in many ways, as indicated by the arbitrary permutation
`
`
`
`
`
`
`
`
`
`of the ra edges joining information nodes 302 and check
`
`
`
`
`
`
`
`
`nodes 304 in permutation block 310. These connections cor-
`
`
`
`
`
`
`
`respond to the scrambling performed by the interleaver 204.
`
`
`
`
`
`
`
`
`In an alternate embodiment, the outer coder 202 may be a
`
`
`
`
`
`
`
`low-density generator matrix (LDGM) coder that performs
`
`
`
`
`
`
`
`
`an irregular repeat of the k bits in the block, as shown in FIG.
`
`
`
`
`
`
`
`
`4. As the name implies, an LDGM code has a sparse (low-
`
`
`
`
`
`
`
`
`density) generator matrix. The IRA code produced by the 60
`coder 400 is a serial concatenation ofthe LDGM code and the
`
`
`
`
`
`
`
`
`
`
`
`
`
`accumulator code. The interleaver 204 in FIG. 2 may be
`
`
`
`
`
`
`
`
`excluded due to the randomness already present in the struc-
`ture of the LDGM code.
`
`
`
`
`
`
`
`
`
`
`
`If the permutation performed in permutation block 310 is 65
`
`
`
`
`
`
`
`
`
`fixed, the Tanner graph represents a binary linear block code
`
`
`
`
`
`
`
`
`
`
`
`with k information bits (ul,
`.
`, uk) and r parity bits
`.
`.
`
`
`
`55
`
`
`
`
`
`
`
`5
`
`10
`
`
`
`15
`
`
`
`20
`
`25
`
`
`
`30
`
`
`
`35
`
`
`
`40
`
`
`
`45
`
`
`
`4
`
`
`
`
`
`
`
`
`
`
`
`
`
`.
`.
`(x1,
`,x,), as follows. Each of the information bits is
`.
`
`
`
`
`
`
`
`
`associated with one ofthe information nodes 302, and each of
`
`
`
`
`
`
`
`
`
`
`the parity bits is associated with one of the parity nodes 306.
`
`
`
`
`
`
`
`
`The value of a parity bit is determined uniquely by the con-
`dition that the mod-2 sum of the values of the variable nodes
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`connected to each of the check nodes 304 is zero. To see this,
`
`
`
`
`
`
`
`
`set x0:0. Then if the values ofthe bits on the ra edges coming
`
`
`
`
`
`
`
`
`
`out the permutation box are (v1, .
`, vm), then we have the
`.
`.
`recursive formula
`
`
`
`i
`
`z:1
`xj =Xj71+2 mg)“;
`
`
`
`
`
`
`
`
`.
`.
`, r. This is in effect the encoding algorithm.
`forj:l, 2, .
`
`
`
`
`
`
`
`
`Two types of IRA codes are represented in FIG. 3, a non-
`
`
`
`
`
`
`
`systematic version and a systematic version. The nonsystem-
`
`
`
`
`
`
`
`
`
`atic version is an (r,k) code, in which the codeword corre-
`
`
`
`
`
`
`
`
`sponding to the information bits (ul, .
`.
`. ,uk) is (x1, .
`.
`. ,x,).
`
`
`
`
`
`
`
`
`The systematic version is a (k+r, k) code, in which the code-
`
`
`
`
`word is (ul, .
`. ,uk; x1, .
`.
`.
`, x,).
`.
`
`
`
`
`The rate of the nonsystematic code is
`
`Rnsys —
`
`
`a
`
`
`i
`
`
`
`
`
`
`
`The rate of the systematic code is
`
`a
`
`
`Rsys =
`
`a+Zifi
`i
`
`
`
`
`
`
`
`
`
`
`
`
`
`For example, regular repeat and accumulate (RA) codes
`
`
`
`
`
`
`
`can be considered nonsystematic IRA codes with a:l and
`
`
`
`
`
`
`
`
`
`exactly one fl. equal to 1, say fq:l, and the rest zero, in which
`
`
`
`case Rwy: simplifies to R:l/q.
`
`
`
`
`
`
`
`
`The IRA code may be represented using an alternate nota-
`
`
`
`
`
`
`
`
`
`tion. Let Al. be the fraction of edges between the information
`
`
`
`
`
`
`
`
`
`
`nodes 302 and the check nodes 304 that are adjacent to an
`
`
`
`
`
`
`information node of degree i, and let pl. be the fraction of such
`
`
`
`
`
`
`
`
`
`
`edges that are adjacent to a check node of degree i+2 (i.e., one
`
`
`
`
`
`
`
`that is adjacent to i information nodes). These edge fractions
`
`
`
`
`
`
`
`
`
`
`may be used to represent the IRA code rather than the corre-
`
`
`
`
`
`
`sponding node fractions. Define }t(x):2i}tixi'l and p(x):2ipi
`
`
`
`
`
`
`
`xi"l to be the generating functions of these sequences. The
`
`
`
`
`
`
`
`
`pair (2», p) is called a degree distribution. For L(x):2ifl.xl.,
`
`
`
`x
`1
`o
`o
`L(x) = f Mndt/f MIMI
`
`

`

`Case 6:20-cv-01042-ADA Document 1-2 Filed 11/11/20 Page 11 of 15
`Case 6:20-cv-01042-ADA Document 1-2 Filed 11/11/20 Page 11 of 15
`
`
`5
`
`
`
`
`
`
`
`The rate of the systematic IRA code given by the degree
`
`
`distribution is given by
`
`
`
`
`
`US 7,421,032 B2
`
`
`6
`
`
`
`
`
`
`
`relies on its input, and y is the output of the channel code bit
`
`
`
`
`
`
`u, then m0(u):log(p(u:0|y)/p(u:l |y)). After this initializa-
`
`
`
`
`
`
`
`
`
`tion, the decoding process may run in a fully parallel and local
`
`
`
`
`
`
`
`manner. In each iteration, every variable/check node receives
`
`
`
`
`
`
`
`
`messages from its neighbors, and sends back updated mes-
`
`
`
`
`
`
`
`sages. Decoding is terminated after a fixed number of itera-
`
`
`
`
`
`
`
`
`
`tions or detecting that all the constraints are satisfied. Upon
`
`
`
`
`
`
`
`termination, the decoder outputs a decoded sequence based
`
`
`
`
`on the messages m(u):2wm(w—>u).
`
`
`
`
`
`
`Thus, on various channels, iterative decoding only differs
`
`
`
`
`
`
`
`
`in the initial messages m0(u). For example, consider three
`
`
`
`
`
`memoryless channel models: a binary erasure channel
`
`
`
`
`
`
`(BEC); a binary symmetric channel (BSC); and an additive
`
`
`
`
`
`white Gaussian noise (AGWN) channel.
`
`
`
`
`
`
`
`
`
`
`
`In the BEC, there are two inputs and three outputs. When 0
`
`
`
`
`
`
`
`
`
`is transmitted, the receiver can receive either 0 or an erasure E.
`
`
`
`
`
`
`
`
`
`
`An erasure E output means that the receiver does not know
`
`
`
`
`
`
`
`
`how to demodulate the output. Similarly, when l is transmit-
`
`
`
`
`
`
`
`
`
`
`
`ted, the receiver can receive either 1 or E. Thus, for the BEC,
`
`
`y e {0, E, l}, and
`
`
`
`
`
`
`"10(14):
`
`
`+00 ify=0
`
`
`ifyzE
`0
`
`
`ify=l
`—oo
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`In the BSC, there are two possible inputs (0,1) and two
`
`
`
`
`
`
`
`
`possible outputs (0, l). The BSC is characterized by a set of
`
`
`
`
`
`
`
`conditional probabilities relating all possible outputs to pos-
`
`
`
`
`
`
`
`sible inputs. Thus, for the BSC y e {0, l},
`
`
`log
`
`"1004) =
`
`—log
`
`
`ify=O
`
`
`if y = l
`
`
`and
`
`
`
`
`
`
`
`
`
`In the AWGN, the discrete-time input symbols X take their
`
`
`
`
`
`
`
`values in a finite alphabet while channel output symbole can
`
`
`
`
`
`
`
`
`
`take any values along the real line. There is assumed to be no
`distortion or other effects other than the addition of white
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Gaussian noise. In an AWGN with a Binary Phase Shift
`
`
`
`
`
`
`
`
`Keying (BPSK) signaling which maps 0 to the symbol with
`
`
`
`
`
`
`
`
`amplitude E and l to the symbol with amplitude fifg,
`
`
`output y e R, then
`
`m0(u)fily\/E/NO
`
`
`
`
`
`
`
`where NO/2 is the noise power spectral density.
`
`
`
`
`
`
`
`
`
`
`
`“Belief propagation” on the Tanner Graph realization may
`
`
`
`
`
`
`
`
`
`be used to decode IRA codes. Roughly speaking, the belief
`
`
`
`
`
`
`
`propagation decoding technique allows the messages passed
`
`
`
`
`
`
`
`
`on an edge to represent posterior densities on the bit associ-
`
`
`
`
`
`
`
`ated with the variable node. A probability density on a bit is a
`
`
`
`
`
`
`
`
`pair of non-negative real numbers p(0), p(l) satisfying p(0)+
`
`
`
`
`
`
`
`
`p(l):l, where p(O) denotes the probability of the bit being 0,
`
`
`
`
`
`
`
`
`p(1) the probability of it being 1. Such a pair can be repre-
`
`
`
`
`
`
`
`sented by its log likelihood ratio, m:log(p(0)/p(l)). The out-
`
`
`
`
`
`
`
`going message from a variable node u to a check node v
`
`
`
`
`
`
`
`represents information about u, and a message from a check
`
`
`
`
`
`
`node u to a variable node v represents information about u, as
`
`
`
`
`
`shown in FIGS. 5A and 5B, respectively.
`
`
`
`
`
`
`
`The outgoing message from a node u to a node v depends
`
`
`
`
`
`
`
`on the incoming messages from all neighbors w ofu except v.
`
`
`
`
`
`
`
`If u is a variable message node, this outgoing message is
`
`waev
`m(u —> v) = Z m(w —> 14) +m0(u)
`
`
`
`
`
`
`
`
`where m0(u) is the log-likelihood message associated with
`
`
`
`
`
`
`u. If u is a check node, the corresponding formula is
`
`tanh
`
`
`m(u —> v)
`2
`
`
`
`
`tanhm(w —> 14)
`2
`
`
`=
`
`waev
`I I
`
`
`10
`
`
`
`15
`
`
`
`20
`
`25
`
`
`
`30
`
`
`
`35
`
`
`
`40
`
`
`
`45
`
`
`
`50
`
`
`
`55
`
`
`
`60
`
`
`
`
`
`
`
`
`
`
`
`Before decoding, the messages m(w—>u) and m(uev) are
`
`
`
`
`
`
`
`initialized to be zero, and m0(u) is initialized to be the log-
`likelihood ratio based on the channel received information. If
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the channel is memoryless, i.e., each channel output only
`
`65
`
`
`
`

`

`Case 6:20-cv-01042-ADA Document 1-2 Filed 11/11/20 Page 12 of 15
`Case 6:20-cv-01042-ADA Document 1-2 Filed 11/11/20 Page 12 of 15
`
`
`
`US 7,421,032 B2
`
`
`7
`
`
`
`
`
`
`
`The selection of a degree profile for use in a particular
`
`
`
`
`
`
`transmission channel is a design parameter, which may be
`
`
`
`
`
`
`
`affected by various attributes of the channel. The criteria for
`
`
`
`
`
`
`
`
`selecting a particular degree profile may include, for example,
`
`
`
`
`
`
`
`
`
`
`
`the type of channel and the data rate on the channel. For
`
`
`
`
`
`
`
`
`
`example, Table 1 shows degree profiles that have been found
`
`
`
`
`
`
`
`
`to produce good results for an AWGN channel model.
`
`a
`
`A2
`
`A3
`
`A5
`
`A6
`
`MO
`
`211
`
`A12
`
`213
`
`M4
`
`M6
`
`A27
`
`A28
`
`Rate
`
`OGA
`
`0*
`
`(1311010) * (dB)
`
`S.L. (dB)
`
`
`
`
`
`TABLE 1
`
`
`2
`
`
`0.139025
`
`0.2221555
`
`
`
`0.638820
`
`
`
`3
`
`
`0.078194
`
`0.128085
`
`0.160813
`
`0.0

This document is available on Docket Alarm but you must sign up to view it.


Or .

Accessing this document will incur an additional charge of $.

After purchase, you can access this document again without charge.

Accept $ Charge
throbber

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.

throbber

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.

Become a Member

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

We are redirecting you
to a mobile optimized page.





Document Unreadable or Corrupt

Refresh this Document
Go to the Docket

We are unable to display this document.

Refresh this Document
Go to the Docket