`Case 6:20-cv-01042—ADA Document 1-1 Filed 11/11/20 Page 1 of 13

`

`6:20-cv-1042

`

`6:20-cv-1042

`

`EXHIBIT A

`

`EXHIBIT A

`

`

`

`Case 6:20-cv-01042-ADA Document 1-1 Filed 11/11/20 Page 2 of 13

`case 6120'CV'01042'ADA ”will“lillillllflilliflllfillifilllfililIiiillfiliiflfllfifllllllllll

`

`

`US007ll6710Bl

`

`

`

`

`

`

`

`

`

`United States Patent

`(12)

`US 7,116,710 B1

`(10) Patent No.:

`

`

`

`

`

`

`

`

`(45) Date of Patent:

`Oct. 3, 2006

`Jin et al.

`

`

`

`

`

`

`(54) SERIAL CONCATENATION 0F

`

`

`INTERLEAVED CONVOLUTIONAL CODES

`FORMING TURBO-LIKE CODES

`

`

`

`

`

`

`

`

`

`Inventors: Hui Jin, Glen Gardner, NJ (US);

`

`

`

`Aamod Khandekar, Pasadena, CA

`.

`_

`

`

`

`(Us): RObert J- McEllece, Pasadena:

`

`

`CA (US)

`

`

`

`(75)

`

`

`

`

`

`

`5,881,093 A

`

`6,014,411 A *

`6,023,783 A

`

`6,031,874 A

`

`

`

`2,824,112 2

`

`’

`’

`

`6,396,423 B1 *

`

`

`6,437,714 B1*

`

`

`2001/0025358 A1

`

`

`

`

`

`

`3/1999 Wang et a1.

`

`

`

`1/2000 Wang ......................... 375/259

`2/2000 Divsalar et a1.

`

`

`

`2/2000 Chennakeshu et a1.

`

`

`

`$3888 @155

`

`ang

`

`

`

`

`5/2002 Laumen et a1.

`............... 341/95

`

`

`

`

`8/2002 Kim et a1.

`.................... 341/81

`

`

`

`

`9/2001 Eidson et a1.

`

`

`

`

`

`

`

`

`

`

`

`

`

`(73) Assignee: Califiornia Institute of Technology,

`

`Pasa ena, CA

`S

`(U )

`

`

`

`

`

`

`

`

`

`Subject to any disclaimer, the term of this

`( * ) Notice:

`’

`’

`

`

`

`pJatSerét 1155:);b63nb1ed7305 :djuswd under 35

`

`

`

`

`'

`ays.

`'

`'

`y

`

`

`

`

`

`

`

`

`

`

`

`OTHER PUBLICATIONS

`Wiberg et a1., “Codes and Iteratie Decoding on General Graphs”,

`

`

`

`

`

`

`

`

`

`

`

`

`

`1:995 13? :yinpgtsriuunélfn Iglgorlrgtg); T111613}? .Sep' $89? $306:

`3.11

`ppen X

`e 0

`CC

`a rices 0

`an

`lZe

`.

`C

`

`

`

`

`

`

`

`

`

`

`

`

`LDPC Codes,” Digital Video Broadcasting (DVB) User guidelines

`

`

`

`

`

`

`

`

`for the second generation system for Broadcasting,

`Interactive

`

`

`

`

`

`

`

`

`Services, News Gathering and other broadband satellite applications

`

`

`

`

`

`

`

`(DVB—s2) ETSI TR 102 376 v1.1.1. (2005-02) Technical Report.

`

`

`pp. 64.

`

`

`

`

`

`

`

`Benedetto et a1., “Bandwidth efficient parallel concatenated coding

`

`

`

`

`

`

`

`schemes,” Electronics Letters 3l(24):2067-2069 (Nov. 23, 1995).

`

`

`

`

`

`

`

`Benedetto et a1., “Soft-output decoding algorithms in iterative

`

`

`

`

`

`

`

`

`decoding of turbo codes,” The Telecommunications and Data

`

`

`

`

`

`

`

`

`Acquisition (TDA) Progress Report 42-124 for NASA and Califor-

`

`

`

`

`

`

`

`

`nia Institute of Technology Jet Propulsion Laboratory, Joseph H.

`

`

`

`

`

`

`

`Yuen, Ed., pp. 63-87 (Feb. 15, 1996).

`(Continued)

`

`

`

`

`Primary ExamineriDac V. Ha

`

`

`

`

`

`

`

`(74) Attorney, Agent, or FirmiFish & Richardson P.C.

`

`

`ABSTRACT

`(57)

`

`

`

`

`

`

`

`

`

`

`

`

`

`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.

`

`

`

`

`33 Claims, 5 Drawing Sheets

`

`

`

`.

`

`

`

`(21) APP1~ N°~~ 09/861,102

`.

`

`

`

`

`May 183 2001

`Flled:

`

`

`_

`_

`

`

`

`

`RBIated U-S- Application Data

`.

`.

`.

`.

`

`

`

`

`

`PrOVISlonal appl1catlon NO' 60/205’095’ filed on May

`

`

`18’ 2000'

`

`n .

`.

`I t Cl

`

`

`

`(2006.01)

`H04B 1/66

`

`

`

`

`

`

`.............3.7.53.41325124501,..337451/21632;3771549276552;

`(52) US. Cl.

`

`

`

`

`

`’375/259

`(58) Field of Classification search

`’

`

`

`

`

`

`

`

`375/262, 265, 285, 296, 341, 346, 348; 714/746,

`

`

`

`

`

`

`

`714/752, 755, 756, 786, 792, 794, 795, 796;

`

`

`

`

`.

`.

`341/51’ 52’ 56, 102’ 103

`

`

`

`

`

`

`

`See appl1cat1on file for complete search h1story.

`

`

`References Cited

`US. PATENT DOCUMENTS

`

`

`2/1995 Rhines et a1.

`

`

`

`5/1998 Seshadri et a1.

`

`

`

`

`

`

`(22)

`

`

`

`

`

`(60)

`

`(51)

`

`

`

`(56)

`

`

`

`5,392,299 A

`

`5,751,739 A *

`

`

`

`

`

`

`

`............ 714/746

`

`

`

`

`OUTER

`

`

`

`”

`V

`

`

`

`202

`

`

`

`204

`

`

`

`206

`

`

`

`

`200 \‘

`

`

`

`

`k U k

`

`

`

`U

`

`

`

`Case 6:20-cv-01042-ADA Document 1-1 Filed 11/11/20 Page 3 of 13

`Case 6:20-cv-01042-ADA Document 1-1 Filed 11/11/20 Page 3 of 13

`

`

`

`US 7,116,710 B1

`

`

`Page 2

`

`OTHER PUBLICATIONS

`

`

`

`

`

`

`Benedetto et a1., “Serial Concatenation of Interleaved Codes:

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`Performace Analysis, Design, and Iterative Decoding,” The Tele-

`

`

`

`

`

`

`

`communications and Data Acquisition (TDA) Progress Report

`

`

`

`

`

`

`

`

`

`42-126 for NASA and California Institute of Technology Jet Pro-

`

`

`

`

`

`

`

`

`

`

`pulsion Laboratory, Jospeh H. Yuen, Ed., pp. 1-26 (Aug. 15, 1996).

`

`

`

`

`

`

`Benedetto et a1., “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., “Parallel Concatenated Trellis Coded Modulation,”

`

`

`

`

`

`

`

`

`

`

`

`

`

`ICC ’96, IEEE, pp. 974-978, (Jun. 1996).

`

`

`

`

`

`

`

`

`

`Benedetto, S. et a1., “A Soft-Input Soft-Output APP Module for

`

`

`

`

`

`

`Iterative Decoding of Concatenated Codes,” IEEE Communications

`

`

`

`

`Letters 1(1):22-24 (Jan. 1997).

`

`

`

`

`

`

`

`Benedetto et a1., “Serial Concatenation of interleaved codes: per-

`

`

`

`

`

`

`

`formance 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., “Serial Concatenated Trellis Coded Modulation

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`with Iterative Decoding,” Proceedings from IEEE 1997 Interna-

`

`

`

`

`

`

`

`tional Symposium on Information Theory (ISIT), Ulm, Germany, p.

`8, Jun. 29-Ju1. 4, 1997.

`

`

`

`

`

`

`

`

`

`

`Benedetto et a1., “Design of Serially Concatenated Interleaved

`

`

`

`

`

`

`

`

`Codes,” ICC 97, Montreal, Canada, pp. 710-714, (Jun. 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-S2)

`

`

`

`

`

`

`

`

`

`ETSI TR 102 376 V1.1.1. (Feb. 2005) Technical Report, pp. 1-104

`

`

`

`(Feb. 15, 2005).

`

`

`

`

`

`

`

`

`Divsalar et a1., “Coding Theorems for ‘Turbo-Like’ Codes,” Pro-

`

`

`

`

`

`

`

`ceedings of the 36th Annual Allerton Conference on Communica-

`

`

`

`

`

`

`

`

`

`tion, Control, and Computing, Sep. 23-25 1998, Allerton House,

`

`

`

`

`

`Monticello, Illinois, pp. 201-210 (1998).

`

`

`

`

`

`

`

`

`

`Divsalar, D. et a1., “Multiple Turbo Codes for Deep-Space Com-

`

`

`

`

`

`

`munications,” The Telecommunications and Data Acquisition

`

`

`

`

`

`

`

`* cited by examiner

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`(TDA) Progress Report 42-121 for NASA and California Institute of

`

`

`

`

`

`

`

`

`

`Technology Jet Propulsion Laboratory, Jospeh H. Yuen, Ed., pp.

`

`

`

`60-77 (May 15, 1995).

`

`

`

`

`

`

`

`Divsalar, D. et a1., “On the Design of Turbo Codes,” The Telecom-

`

`

`

`

`

`

`

`munications and Data Acquisition (TDA) Progress Report 42-123

`

`

`

`

`

`

`

`for NASA and California Institute of Technology Jet Propulsion

`

`

`

`

`

`

`

`

`

`Laboratory, Jospeh H. Yuen, Ed., pp. 99-131 (Nov. 15, 1995).

`

`

`

`

`

`

`

`

`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, p. 35.

`

`

`

`

`

`

`

`

`Divsalar, D. et a1., “Turbo Codes for PCS Applications,” ICC 95,

`

`

`

`

`

`

`IEEE, Seattle, WA, pp. 54-59 (Jun. 1995).

`

`

`

`

`

`

`

`Divsalar, D. et a1., “Multiple Turbo Codes,” MILCOM 95, San

`

`

`

`

`

`Diego, CA pp. 279-285 (Nov. 5-6, 1995).

`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., “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).

`

`

`

`

`

`

`

`Jin et a1., “Irregular Repeat - Accumulate Codes,” 2nd International

`

`

`

`

`

`

`

`Symposium on Turbo Codes & Related Topics, Sep. 4-7, 2000,

`

`

`

`

`

`

`Brest, France, 25 slides, (presented on Sep. 4, 2000).

`

`

`

`

`

`

`Jin et a1., “Irregular Repeat-Accumulate 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, “Eflicient encoding of low-density

`

`

`

`

`

`

`

`

`

`parity check codes,” IEEE Trans. Inform. Theory 47: 638-656 (Feb.

`

`2001).

`

`

`

`Case 6:20-cv-01042-ADA Document 1-1 Filed 11/11/20 Page 4 of 13

`Case 6:20-cv-01042-ADA Document 1-1 Filed 11/11/20 Page 4 of 13

`

`

`U.S. Patent

`

`

`

`

`Oct. 3, 2006

`

`

`

`

`

`Sheet 1 of 5

`

`

`

`US 7,116,710 B1

`

`

`

`N L

`

`LJ

`{:1

`

`ooL

`

`LJ

`

`FIG.1 (PriorArt)

`

`a:

`

`

`

`

`

`

`

`

`

`Case 6:20-cv-01042-ADA Document 1-1 Filed 11/11/20 Page 5 of 13

`Case 6:20-cv-01042-ADA Document 1-1 Filed 11/11/20 Page 5 of 13

`

`

`U.S. Patent

`

`

`

`

`Oct. 3, 2006

`

`

`

`

`Sheet 2 of 5

`

`

`

`US 7,116,710 B1

`

`

`

`

`

`

`

`

`V

`

`CD

`

`I

`

`0O<

`

`:

`

`

`

`

`N

`

`Q'J

`I

`

`x

`

`

`

`

`1

`

`

`2(

`

`DD_

`

`x

`

`

`

`

`

`

`

`Case 6:20-cv-01042-ADA Document 1-1 Filed 11/11/20 Page 6 of 13

`Case 6:20-cv-01042-ADA Document 1-1 Filed 11/11/20 Page 6 of 13

`

`

`U.S. Patent

`

`

`

`

`Oct. 3, 2006

`

`

`

`

`Sheet 3 of 5

`

`

`

`US 7,116,710 B1

`

`

`

`Variable Node

`

`

`Fraction of nodes

`

`degree i

`

`

`

`

`Check Node

`

`degree a

`

`

`

`f/

`

`2 9K E E 0

`

`:

`

`

`

`f2

`

`f3

`

`

`

`

`

`

`3:

`

`

`

`

`E 8 <

`

`2:

`

`0:

`

`

`FIG. 3

`

`

`

`Case 6:20-cv-01042-ADA Document 1-1 Filed 11/11/20 Page 7 of 13

`Case 6:20-cv-01042-ADA Document 1-1 Filed 11/11/20 Page 7 of 13

`

`

`U.S. Patent

`

`

`

`

`Oct. 3, 2006

`

`

`

`

`Sheet 4 of 5

`

`

`

`US 7,116,710 B1

`

`

`

`

`FIG. 5A

`

`304

`

`

`

`

`

`

`

`

`FIG. 53

`

`

`

`Case 6:20-cv-01042-ADA Document 1-1 Filed 11/11/20 Page 8 of 13

`Case 6:20-cv-01042-ADA Document 1-1 Filed 11/11/20 Page 8 of 13

`

`

`U.S. Patent

`

`

`

`

`Oct. 3, 2006

`

`

`

`

`Sheet 5 of 5

`

`

`

`US 7,116,710 B1

`

`

`

`

`

`

`

`Case 6:20-cv-01042-ADA Document 1-1 Filed 11/11/20 Page 9 of 13

`Case 6:20-cv-01042-ADA Document 1-1 Filed 11/11/20 Page 9 of 13

`

`

`

`US 7,116,710 B1

`

`

`1

`SERIAL CONCATENATION OF

`

`

`INTERLEAVED CONVOLUTIONAL CODES

`

`

`FORMING TURBO-LIKE CODES

`

`

`

`

`

`

`CROSS-REFERENCE TO RELATED

`

`APPLICATIONS

`

`

`

`

`

`

`

`

`

`

`

`This application claims priority to US. Provisional Appli-

`

`

`

`

`

`

`

`

`cation Ser. No. 60/205,095, filed on May 18, 2000, and to

`

`

`

`

`

`

`

`

`

`US. application Ser. No. 09/922,852, filed on Aug. 18, 2000

`

`

`

`

`

`

`and entitled Interleaved Serial Concatenation Forming

`Turbo-Like Codes.

`

`

`GOVERNMENT LICENSE RIGHTS

`

`

`

`

`

`

`

`

`

`

`

`

`

`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

`

`

`

`

`

`

`

`

`

`provided for by the terms of Grant No. CCR-9804793

`

`

`

`

`

`awarded by the National Science Foundation.

`BACKGROUND

`

`

`

`10

`

`

`

`15

`

`

`

`20

`

`

`

`

`

`

`

`

`

`Properties of a 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 106471070, (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

`

`

`

`

`

`

`

`sufficient structure to allow practical encoding and decoding

`

`

`

`

`

`

`

`

`algorithms. 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

`40

`k bit interleaver 106 also receives the k bits and interleaves

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`them prior to applying them to a second coder 104. The

`

`

`

`

`

`

`

`

`

`second coder produces an output that has more bits than its

`

`

`

`

`

`

`

`

`

`

`

`

`input, that is, it is a coder with rate that is less than 1. The

`

`

`

`

`

`

`coders 102, 104 are typically recursive convolutional coders.

`Three different items are sent over the channel 150: the

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`original k bits, first encoded bits 110, and second encoded

`

`

`

`

`

`

`

`

`

`bits 112. At the decoding end, two decoders are used: a first

`constituent decoder 160 and a second constituent decoder

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`162. Each receives both the original k bits, and one of the

`

`

`

`

`

`

`

`

`encoded portions 110, 112. Each decoder sends likelihood

`estimates of the decoded bits to the other decoders. The

`

`

`

`

`

`

`

`

`

`

`estimates are used to decode the uncoded information bits as

`

`

`

`

`

`

`

`

`

`

`

`

`corrupted by the noisy channel.

`SUMMARY

`

`25

`

`30

`

`35

`

`45

`

`50

`

`55

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`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 appor-

`

`

`

`

`

`

`

`

`

`tioned into two or more sub-blocks, and bits in different

`

`

`

`

`

`

`

`sub-blocks are repeated a different number of times accord-

`

`

`

`

`

`

`

`

`

`ing to a selected degree profile. The outer coder may include

`

`

`

`

`

`

`

`

`a repeater with a variable rate and an interleaver. Alterna-

`

`

`

`

`

`

`

`

`tively, the outer coder may be a low-density generator matrix

`

`

`(LDGM) coder.

`

`60

`

`

`

`65

`

`

`

`2

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`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 represen-

`tation 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

`

`

`

`accumulate (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 embodi-

`

`

`

`

`

`

`

`

`

`ment. 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 redun-

`

`

`

`

`

`

`

`

`

`

`dancy into the stream of data to protect the data from loss

`

`

`

`

`

`

`

`

`due to transmission errors. The encoded data may then be

`

`

`

`

`

`

`

`

`decoded at a destination in linear time at rates that may

`

`

`

`

`approach the channel 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 dilfer 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 frac-

`

`

`

`

`

`

`

`

`tions 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)

`

`

`

`

`

`

`

`

`partial sums of its inputs. The accumulator may be a

`

`

`

`Case 6:20-cv-01042-ADA Document 1-1 Filed 11/11/20 Page 10 of 13

`Case 6:20-cv-01042-ADA Document 1-1 Filed 11/11/20 Page 10 of 13

`

`

`3

`truncated rate-1 recursive convolutional coder with the

`

`

`

`

`

`

`

`

`

`

`

`

`

`transfer function 1/(1+D). Such an accumulator may be

`

`

`

`

`

`

`

`

`considered a block coder whose input block [x1, .

`.

`, xn] and

`.

`

`

`

`

`

`

`

`

`

`

`

`output block [y1,

`, yn] are related by the formula

`.

`.

`.

`

`Y1:X1

`

`

`

`US 7,116,710 B1

`

`4

`

`

`

`

`

`

`

`

`

`

`

`to each of the check nodes 304 is zero. To see this, set x0:0.

`

`

`

`

`

`

`Then if the values of the bits on the ra edges coming out the

`

`

`

`

`

`

`

`

`

`

`

`permutation box are (v1,

`.

`.

`, vm),

`then we have the

`.

`recursive formula

`

`

`

`

`

`

`

`

`

`5

`

`10

`

`

`

`A

`

`z:1

`Xj = Xj71+ Z mum;

`

`Y2:x1”x2

`

`

`

`Y3 :x1Wx2®x3

`

`

`

`

`

`yn:xlfix2®x3® .

`

`.

`

`. 63x".

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`where “63” denotes mod-2, or exclusive-OR C(OR), addi-

`

`

`

`

`

`

`

`

`tion. An advantage of this system is that only mod-2 addition

`

`

`

`

`

`

`

`

`is necessary for the accumulator. The accumulator may be 15

`

`

`

`

`

`

`

`

`

`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 20

`

`

`

`

`

`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 25

`

`

`

`

`

`

`

`

`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

`

`

`

`

`

`

`

`

`

`

`

`

`.

`.

`f}; a), where fiEO, Zifi:1 and “a” is a positive 30

`.

`(f1,

`,

`

`

`

`

`

`

`

`

`

`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:(k2iifi)/a check nodes 3 5

`

`

`

`

`

`

`

`

`

`304 connected between the information nodes and the parity

`nodes. Each information node 302 is connected to a number

`

`

`

`

`

`

`

`of check nodes 304. The fraction of information nodes

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`connected to exactly i check nodes is fl. For example, in the

`

`

`

`

`

`

`

`

`

`Tanner graph 300, each of the f2 information nodes are 40

`

`

`

`

`

`

`connected to two check nodes, corresponding to a repeat of

`

`

`

`

`

`

`

`q:2, and each of the f3 information nodes are connected to

`

`

`

`

`

`three check nodes, corresponding to q:3.

`

`

`

`

`

`

`

`

`Each check node 304 is connected to exactly “a” infor-

`

`

`

`

`

`

`

`mation nodes 302. In FIG. 3, a:3. These connections can be 45

`

`

`

`

`

`

`

`made in many ways, as indicated by the arbitrary permuta-

`

`

`

`

`

`

`

`

`tion of the ra edges joining information nodes 302 and check

`

`

`

`

`

`

`

`nodes 304 in permutation block 310. These connections

`

`

`

`

`

`

`correspond 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 55

`the coder 400 is a serial concatenation of the LDGM code

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`and the accumulator code. The interleaver 204 in FIG. 2 may

`

`

`

`

`

`

`

`

`be excluded due to the randomness already present in the

`structure of the LDGM code.

`

`

`

`

`

`

`

`

`

`

`

`If the permutation performed in permutation block 310 is 60

`

`

`

`

`

`

`

`

`

`fixed, the Tanner graph represents a binary linear block code

`

`

`

`

`

`

`

`

`.

`with k information bits (ul, .

`. ,uk) andr parity bits (x1, .

`.

`.

`,

`

`

`

`

`

`

`

`x,), as follows. Each of the information bits is associated

`

`

`

`

`

`

`

`

`with one of the information nodes 302, and each of the parity

`

`

`

`

`

`

`

`

`

`bits is associated with one of the parity nodes 306. The value 65

`

`

`

`

`

`

`

`

`of a parity bit is determined uniquely by the condition that

`the mod-2 sum of the values of the variable nodes connected

`

`

`

`

`

`

`

`

`50

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`.

`.

`, r. This is in effect the encoding algorithm.

`for j:1, 2,

`.

`

`

`

`

`

`

`

`

`Two types of IRA codes are represented in FIG. 3, a

`

`

`

`

`

`

`

`nonsystematic version and a systematic version. The non-

`

`

`

`

`

`

`

`

`systematic version is an (r,k) code, in which the codeword

`

`

`

`

`

`

`corresponding to the information bits (ul, .

`, uk) is (x1, .

`.

`.

`,

`.

`.

`

`

`

`

`

`

`

`

`x,). The systematic version is a (k+r, k) code, in which the

`

`

`

`

`

`

`

`

`

`.

`codeword is (ul, .

`.

`, uk; x1,

`.

`.

`, x,).

`.

`

`

`

`

`

`

`The rate of the nonsystematic code is

`

`a

`R __

`

`

`nsys Zif;

`

`

`

`

`

`

`

`The rate of the systematic code is

`

`a

`

`

`Rsys =

`

`

`a+Zifi

`

`

`

`

`

`

`

`

`

`For example, regular repeat and accumulate (RA) codes

`

`

`

`

`

`

`

`

`can be considered nonsystematic IRA codes with a:1 and

`

`

`

`

`

`

`

`

`exactly one fl equal to 1, say f(1:1, and the rest zero, in which

`

`

`

`case Rwy: simplifies to R:1/q.

`

`

`

`

`

`

`

`

`The IRA code may be represented using an alternate

`

`

`

`

`

`

`

`

`

`notation. Let Al. be the fraction of edges between the infor-

`

`

`

`

`

`

`

`

`

`

`mation 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 corresponding node fractions. Define 2t(x):2i}tixi'l and

`

`

`

`

`

`

`

`

`p(x):2ipl.xi'l

`to be the generating functions of these

`

`

`

`

`

`

`

`

`sequences. The pair (2», p) is called a degree distribution. For

`L(X):ZifiXZ-,

`

`

`

`L(x):jom(z)dz/jol>t(z)dz

`

`

`

`

`

`

`

`The rate of the systematic IRA code given by the degree

`

`

`distribution is given by

`

`

`

`ij/j 71

`

`

`Rate: 1+ J

`

`

`./

`ZAj/J'

`

`

`

`

`

`

`

`

`

`“Belief propagation” on the Tanner Graph realization may

`

`

`

`

`

`

`

`

`

`be used to decode IRA codes. Roughly speaking, the belief

`

`

`

`Case 6:20-cv-01042-ADA Document 1-1 Filed 11/11/20 Page 11 of 13

`Case 6:20-cv-01042-ADA Document 1-1 Filed 11/11/20 Page 11 of 13

`

`

`

`US 7,116,710 B1

`

`

`6

`

`

`

`

`

`

`conditional probabilities relating all possible outputs to

`

`

`

`

`

`

`

`

`possible inputs. Thus, for the BSC yE{0, 1},

`

`

`

`if y = 0

`

`

`ify=1

`

`

`p

`

`log

`

`1 _

`

`

`

`

`p

`

`—log

`

`

`

`"10(14):

`

`

`10

`

`

`

`15

`

`

`

`20

`

`25

`

`

`

`30

`

`

`

`and

`

`

`

`

`

`

`

`

`In the AWGN, the discrete-time input symbols X take

`

`

`

`

`

`

`

`

`their values in a finite alphabet while channel output sym-

`

`

`

`

`

`

`

`

`

`bols Y 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 7E5 and 1 to the symbol with

`

`

`

`

`

`amplitude —\/Es, output yER, then

`m0(u)fily«/E_S/NO

`

`

`

`

`

`

`

`

`where NO/2 is the noise power spectral density.

`

`

`

`

`

`

`

`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.

`

`

`

`

`5

`

`

`

`

`

`

`

`propagation decoding technique allows the messages passed

`

`

`

`

`

`

`

`

`on an edge to represent posterior densities on the bit asso-

`

`

`

`

`

`

`

`

`ciated with the variable node. A probability density on a bit

`

`

`

`

`

`

`

`

`is a pair of non-negative real numbers p(O), p(1) satisfying

`

`

`

`

`

`

`

`p(0)+p(1):1, where p(O) denotes the probability of the bit

`

`

`

`

`

`

`

`

`being 0, p(1) the probability of it being 1. Such a pair can be

`

`

`

`

`

`

`

`represented by its log likelihood ratio, m:log(p(0)/p(1)).

`

`

`

`

`

`

`

`The outgoing 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 of u except

`

`

`

`

`

`

`

`

`v. If u is a variable message node, this outgoing message is

`

`W¢v

`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

`

`

`

`tanhmw —> 14)

`2

`

`

`=

`

`waev

`I I

`

`

`2

`

`m(u —> v)

`

`

`

`tank

`

`

`

`

`

`

`

`

`

`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 informa-

`

`

`

`

`

`

`

`

`

`tion. If the channel is memoryless, i.e., each channel output

`

`

`

`

`

`

`

`

`

`only relies on its input, and y is the output of the channel

`

`

`

`

`

`

`

`code bit u,

`then m0(i):log(p(u:0|y)/p(u:1|y)). After this

`

`

`

`

`

`

`

`

`initialization,

`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 messages. Decoding is terminated after a fixed

`

`

`

`

`

`

`

`

`number of iterations 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 diifers

`

`

`

`

`

`

`

`

`

`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 1

`

`

`

`

`

`

`

`

`

`is transmitted, the receiver can receive either 1 or E. Thus,

`

`

`

`

`

`for the BEC, yE{0, E, 1}, and

`

`35

`

`40

`

`45

`

`50

`

`55

`

`"1004) =

`

`

`+00

`0

`

`—oo

`

`

`

`

`

`ify=0

`

`ifyzE

`

`ify=1

`

`

`

`

`

`

`

`

`

`

`

`

`

`In the BSC, there are two possible inputs (0,1) and two

`

`

`

`

`

`

`

`

`possible outputs (0, 1). The BSC is characterized by a set of

`

`60

`

`

`

`65

`

`

`

`

`

`

`

`

`

`

`

`

`

`a

`

`

`

`A2

`

`A3

`

`A5

`

`A6

`

`A10

`

`A11

`

`A12

`

`A13

`

`A14

`

`A16

`

`A27

`

`A28

`

`Rate

`

`oGA

`

`0*

`

`(Eb/N0) * (dB)

`

`S.L. (dB)

`

`

`

`

`

`TABLE 1

`

`

`2

`

`

`0.139025

`

`0.2221555

`

`0.638820

`

`

`

`

`

`3

`

`

`0.078194

`0.128085

`0.160813

`0.036178

`

`

`

`

`

`

`0.108828

`0.487902

`

`

`

`

`

`

`0.333364

`1.1840

`

`1.1981

`

`0.190

`

`—0.4953

`

`

`

`

`

`0.333223

`1.2415

`1.2607

`—0.250

`

`—0.4958

`

`

`

`

`

`

`4

`

`

`0.054485

`0.104315

`

`

`

`

`0.126755

`

`0.229816

`

`0.016484

`

`

`

`

`

`

`0.450302

`0.017842

`0.333218

`1.2615

`1.2780

`—0.371

`

`—0.4958

`

`

`

`

`

`

`

`

`

`

`

`

`

`

`Table 1 shows degree profiles yielding codes of rate

`

`

`

`

`

`

`

`approximately 1/3 for the AWGN channel and with a:2, 3, 4.

`

`

`

`

`

`

`

`For each sequence,

`the Gaussian approximation noise

`

`

`

`

`

`

`

`threshold, the actual sum-product decoding threshold and

`

`

`

`

`

`

`

`

`the corresponding energy per bit (Eb)-noise power (N0) ratio

`

`

`

`

`

`

`

`

`

`in dB are given. Also listed is the Shannon limit (S.L.).

`

`

`

`

`

`

`

`As the parameter “a” is

`increased,

`the performance

`

`

`

`

`

`

`

`

`

`improves. For example, for a:4, the best code found has an

`

`

`

`

`

`

`iterative decoding threshold of Eb/NO:—0.371 dB, which is

`

`

`

`

`

`

`only 0.12 dB above the Shannon limit.

`

`

`

`

`

`

`

`The accumulator component of the coder may be replaced

`

`

`

`

`

`

`

`by a “double accumulator” 600 as shown in FIG