Case 6:20-cv-01042-ADA Document 1-1 Filed 11/11/20 Page 1 of 13
`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