`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