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

`

`Case 6:20-cv-01042-ADA Document 1-3 Filed 11/11/20 Page 2 of 13
`Case 6120'CV'01042'ADA D"c“ml‘lllllllllll||fllllllllll'llllfilllfilllIllllllll’llllllilll'llll||||||||
`
`USOO7916781B2
`
`
`
`
`
`
`
`
`US 7,916,781 B2
`(10) Patent No.:
`(12) Unlted States Patent
`
`
`
`
`
`
`
`
`Jin et al.
`(45) Date of Patent:
`Mar. 29, 2011
`
`
`
`
`
`(56)
`
`
`
`
`References Cited
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`U.S. PATENT DOCUMENTS
`
`
`
`...................... 714/755
`5181207 A *
`1/1993 Ch
`
`
`
`
`
`
`
`
`
`5:392:299 A
`2/1995 Rhifigé: 31.
`
`
`
`
`5,530,707 A
`6/1996 Lin
`
`
`
`5,751,739 A
`5/1998 Seshadri et a1.
`
`
`
`5,802,115 A
`9/1998 Meyer
`
`
`
`
`335121!,2? :
`igggg gang et 3L
`ang
`5
`a
`
`
`
`6,023,783 A
`2/2000 Divsalar et al.
`
`
`
`2:83:33 2
`$3888 gfiilsmakesm et 31'
`
`
`
`6,044,116 A
`3/2000 Wang
`
`
`
`
`6,094,739 A
`7/2000 Miller et al.
`
`
`
`
`6,195,396 B1 *
`2/2001 Fang et al.
`.................... 375/261
`
`
`
`
`
`6,396,423 B1
`5/2002 Laumen et 31.
`6,437,714 B1
`8/2002 Kim et 31.
`
`
`
`
`
`
`6,732,328 B1 *
`5/2004 McEwen et al.
`.............. 714/795
`
`
`
`
`
`
`
`
`
`6,859,906 B2
`2/2005 Hammonsetal.
`
`
`
`
`
`
`7,089,477 B1
`8/2006 .Dlvsalar et al.
`
`(Continued)
`OTHER PUBLICATIONS
`
`
`tSft-O tAPPMdlf
`B dtt,S.,tl.,“ASft-I
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`utpu
`0 u e or
`e a
`ene e 0
`npu
`0
`0
`
`
`
`
`
`
`Iterative Decoding ofConcatenated Codes, IEEE Commumcatzons
`
`
`
`
`Letters’ 1(1):22-24, Jan' 1997'
`(Continued)
`
`
`Primary Examiner i Dac V Ha
`
`
`
`
`
`
`(74) Attorney, Agent, or Firm 7 Perkins Coie LLP
`
`
`
`
`(54) SERIAL CONCATENATION OF
`INTERLEAVED CONVOLUTIONAL CODES
`
`
`FORMING TURBO-LIKE CODES
`
`
`
`
`
`
`(75)
`
`
`
`
`
`
`
`
`
`
`Inventors: Hui Jin, Glen Gardner, NJ (US); Aamod
`
`
`
`Khandekar, Pasadena, CA (US);
`
`
`
`
`Robert J. McEliece, Pasadena, CA (US)
`
`
`
`
`
`(73) Assignee: California Institute of Technology,
`
`
`Pasadena’ CA (Us)
`
`
`
`
`
`
`Subject. to any disclaimer, the term ofthis
`
`
`
`
`patent is extended or adjusted under 35
`
`
`
`
`U.S.C. 154(b) by 424 days.
`
`
`( * ) Notice:
`
`
`
`
`
`
`
`
`(21) App], No.: 12/165,606
`.
`~
`
`
`Ffled‘
`
`
`
`
`(22)
`(65)
`
`
`
`
`Jun' 30’ 2008
`
`
`Prior Publication Data
`
`
`
`
`US 2008/0294964 A1
`NOV. 27, 2008
`
`
`
`
`
`
`
`
`
`Related US. Application Data
`.
`.
`.
`.
`
`
`
`
`
`
`(63) Cont1nuation of applicatlon No. 11/542,950, filed on
`
`
`
`
`
`
`
`Oct. 3, 2006, now Pat. No. 7,421,032, which is a
`
`
`
`
`
`continuation of application No. 09/861,102, filed on
`
`
`
`
`
`
`
`May 18, 2001, now Pat. No. 7,116,710, which is a
`
`
`
`
`
`continuation-in-part of application No. 09/922,852,
`
`
`
`
`
`
`
`filed on Aug. 18, 2000, now Pat. No. 7,089,477.
`
`
`
`
`
`
`(60) Provisional application No. 60/205,095, filed on May
`
`
`18, 2000.
`
`Int Cl
`
`
`
`(2006.01)
`H04B 1/66
`
`
`
`
`
`
`
`,,,,,,,, 375/240; 375/285; 375/296; 714/801;
`(52) US, Cl,
`714/804
`
`
`
`
`
`(58) Field of Classification Search .................. 375/240
`
`
`
`
`
`
`375/240-24, 254, 285, 295, 296, 260; 714/755,
`
`
`
`
`714/758, 800, 801, 804, 805
`
`
`
`
`
`
`
`See application file for complete search history.
`
`
`
`
`
`
`
`
`
`
`
`(51)
`
`
`200\
`
`
`
`
`
`
`
`
`
`
`
`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.
`
`
`
`
`22 Claims, 5 Drawing Sheets
`
`
`
`k 2
`
`02
`
`
`
`204
`
`
`
`206
`
`
`
`

`

`Case 6:20-cv-01042-ADA Document 1-3 Filed 11/11/20 Page 3 of 13
`Case 6:20-cv-01042-ADA Document 1-3 Filed 11/11/20 Page 3 of 13
`
`
`
`US 7,916,781 B2
`Page 2
`
`
`U.S. PATENT DOCUMENTS
`
`
`9/2001 Eidson et a1.
`2001/0025358 A1
`
`
`
`
`
`
`OTHER PUBLICATIONS
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Benedetto, S., et al., “A Soft-Input Soft-Output Maximum A Poste-
`
`
`
`
`
`
`
`
`riori (MAP) Module to Decode Parallel and Serial Concatenated
`
`
`
`
`
`
`
`Codes,” The Telecommunications and Data Acquisition Progress
`
`
`
`
`
`
`
`Report (TDA PR 42—127), pp. 1-20, Nov. 1996.
`
`
`
`
`
`
`Benedetto, S., et al., “Bandwidth efficient parallel concatenated cod-
`
`
`
`
`
`
`
`
`ing schemes,” Electronics Letters, 31(24):2067-2069, Nov. 1995.
`
`
`
`
`
`
`Benedetto, S., et a1., “Design of Serially Concatenated Interleaved
`
`
`
`
`
`
`
`Codes,” ICC 97, vol. 2, pp. 710-714, Jun. 1997.
`Benedetto, S., et a1., “Parallel Concatenated Trellis Coded Modula-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`tion,” ICC 96, vol. 2, pp. 974-978, Jun. 1996.
`Benedetto, S., et a1., “Serial Concatenated Trellis Coded Modulation
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`with Iterative Decoding,” Proceedings 1997 IEEE International
`
`
`
`
`
`
`
`Symposium on Information Theory (ISIT), Ulm, Germany, p. 8, Jun.
`29-Ju1. 4, 1997.
`
`
`Benedetto, S., et al., “Serial Concatenation of Interleaved Codes:
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Performace Analysis, Design, and Iterative Decoding,” The Telecom—
`
`
`
`
`
`
`
`
`munications andDataAcquisition Progress Report (TDA PR 42126),
`
`
`
`
`pp. 1-26, Aug. 1996.
`Benedetto, S., et a1., “Serial concatenation of interleaved codes:
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`performance analysis, design, and iterative decoding,” Proceedings
`
`
`
`
`
`
`
`1997 IEEE International Symposium on Information Theory (ISIT),
`
`
`
`
`
`
`Ulm, Germany, p. 106, Jun. 29-Ju1. 4, 1997.
`
`
`
`
`
`
`
`Benedetto, S., et al., “Soft-Output Decoding Algorithms in Iterative
`
`
`
`
`
`
`
`Decoding of Turbo Codes,” The Telecommunications and Data
`
`
`
`
`
`
`
`
`
`Acquisition Progress Report (TDA PR 42—124), pp. 63-87, Feb. 1996.
`
`
`
`
`
`
`
`
`
`Berrou, C., et a1., “Near Shannon Limit Error%orrecting Coding
`
`
`
`
`
`
`
`
`
`
`and Decoding: Turbo Codes,” ICC 93, vol. 2, pp. 1064-1070, May
`1993.
`
`
`
`
`
`
`
`
`
`
`Digital Video Broadcasting (DVB)7User 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 Technical Report, pp. 1-104 (p. 64), Feb.
`2005.
`
`
`
`
`
`
`
`
`
`Divsalar, D., et al., “Coding Theorems for ‘Turbo-Like’ Codes,”
`
`
`
`
`
`
`
`Proceedings ofthe 3 6th AnnualAllerton Conference on Communica—
`
`
`
`
`
`
`
`
`
`tion, Control, and Computing, Monticello, Illinois, pp. 201-210, Sep.
`1998.
`
`
`Divsalar, D., et a1., “Effective free distance ofturbo codes,” Electron—
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ics Letters, 32(5):445-446, Feb. 1996.
`
`
`
`
`
`
`
`
`Divsalar, D., et al ., “Hybrid Concatenated Codes and Iterative Decod-
`
`
`
`
`
`
`
`ing,” Proceedings I997IEEE International Symposium on Informa—
`
`
`
`
`
`
`
`
`
`tion Theory (ISIT), Ulm, Germany, p. 10, Jun. 29-Jul. 4, 1997.
`
`
`
`
`
`
`
`
`Divsalar, D., et a1., “Low-Rate Turbo Codes for Deep-Space Com-
`
`
`
`
`
`
`munications,” Proceedings 1995 IEEE International Symposium on
`
`
`
`
`
`
`
`
`
`Information Theory (ISIT), Whistler, BC, Canada, p. 35, Sep. 1995.
`
`
`
`
`
`
`
`
`Divsalar, D., et a1., “Multiple Turbo Codes for Deep-Space Commu-
`
`
`
`
`
`
`
`nications,” The Telecommunications and Data Acquisition Progress
`
`
`
`
`
`
`
`Report (TDA PR 42—121), pp. 66-77, May 1995.
`
`
`
`
`
`
`
`
`
`Divsalar, D., et a1., “Multiple Turbo Codes,”MILCOM ’95, vol. 1,pp.
`279-285, Nov. 1995.
`
`
`
`
`
`
`
`
`
`
`
`
`Divsalar, D., et al., “On the Design of Turbo Codes,” The Telecom—
`
`
`
`
`
`
`
`
`munications and Data Acquisition Progress Report
`(TDA PR
`
`
`
`
`
`42—123), pp. 99-121, Nov. 1995.
`Divsalar, D., et a1., “Serial Turbo Trellis Coded Modulation with
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Rate-1 Inner Code,” Proceedings 2000 IEEE International Sympo—
`
`
`
`
`
`
`
`
`sium on Information Theory (ISIT), Sorrento, Italy, pp. 194, Jun.
`2000.
`
`
`
`
`
`
`
`
`
`Divsalar, D., et a1., “Turbo Codes for PCS Applications,” IEEE ICC
`
`
`
`
`
`
`
`
`
`’95, Seattle, WA, USA, vol. 1, pp. 54-59, Jun. 1995.
`
`
`
`
`
`
`
`Jin, H., et a1., “Irregular RepeatiAccumulate Codes,” 2nd Interna—
`
`
`
`
`
`
`
`
`tional Symposium on Turbo Codes, Brest, France, 25 pages, Sep.
`2000.
`
`77 2nd
`
`
`
`
`
`
`
`Interna—
`Jin, H., et al., “Irregular RepeatiAccumulate Codes,
`
`
`
`
`
`
`
`
`
`
`tional Symposium on Turbo Codes &Related Topics, Brest, France, p.
`
`
`
`1-8, Sep. 2000.
`
`
`
`
`
`
`Richardson, T.J., et a1., “Design of Capacity-Approaching Irregular
`
`
`
`
`
`Low-Density Parity-Check Codes,” IEEE Transactions on Informa—
`
`
`
`
`
`tion Theory, 47(2):619-637, Feb. 2001.
`
`
`
`
`
`
`Richardson, T.J., et a1., “Efficient Encoding of Low-Density Parity-
`
`
`
`
`
`
`Check Codes,” IEEE Transactions
`on Information Theory,
`
`
`
`47(2):638-656, Feb. 2001.
`
`
`
`
`
`
`
`
`
`Wiberg, N., et a1., “Codes and Iterative Decoding on General
`
`
`
`
`
`
`Graphs,” Proceedings 1995 IEEE International Symposium on Infor—
`
`
`
`
`
`
`
`
`
`mation Theory (ISIT), Whistler, BC, Canada, p. 468, Sep. 1995.
`
`
`
`
`
`
`
`
`Aji, S.M., et al., “The Generalized Distributive Law,” IEEE Trans—
`
`
`
`
`
`
`actions on Information Theory, 46(2):325-343, Mar. 2000.
`
`
`
`
`
`
`Tanner, R.M., “A Recursive Approach to Low Complexity Codes,”
`
`
`
`
`
`
`IEEE Transactions on Information Theory, 27(5):533-547, Sep.
`1981.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`* cited by examiner
`
`
`
`

`

`Case 6:20-cv-01042-ADA Document 1-3 Filed 11/11/20 Page 4 of 13
`Case 6:20-cv-01042-ADA Document 1-3 Filed 11/11/20 Page 4 of 13
`
`
`US. Patent
`
`
`
`
`Mar. 29, 2011
`
`
`
`
`
`Sheet 1 015
`
`
`
`US 7,916,781 B2
`
`
`
`FIG.1 (PriorArt)
`
`
`
`

`

`Case 6:20-cv-01042-ADA Document 1-3 Filed 11/11/20 Page 5 of 13
`Case 6:20-cv-01042-ADA Document 1-3 Filed 11/11/20 Page 5 of 13
`
`
`US. Patent
`
`
`
`
`Mar. 29, 2011
`
`
`
`
`Sheet 2 of5
`
`
`
`US 7,916,781 B2
`
`
`
`
`
`
`
`(.3
`
`O<
`
`N
`
`
`
`QS
`
`IT.
`
`
`
`
`Vl-
`
`
`
`c5
`II
`
`:
`
`x
`
`
`
`|
`
`
`E(
`
`DD_
`
`x
`
`

`

`Case 6:20-cv-01042-ADA Document 1-3 Filed 11/11/20 Page 6 of 13
`Case 6:20-cv-01042-ADA Document 1-3 Filed 11/11/20 Page 6 of 13
`
`
`US. Patent
`
`
`
`
`Mar. 29, 2011
`
`
`
`
`Sheet 3 of5
`
`
`
`US 7,916,781 B2
`
`
`
`Variable Node
`
`
`Fraction of nodes
`
`degree;
`
`
`
`
`Check Node
`
`degree a
`
`
`
`2 E
`
`
`
`3
`
`E
`
`g
`0:
`
`E
`
`----rO<
`
`{U 1,
`‘.
`
`
`
`:
`i
`E
`
`"-21:04:
`302
`
`
`
`
`
`I,
`
`
`
`302
`o———;l-
`
`.'
`1|
`
`
`\\
`
`
`
`-
`.
`
`‘.
`:
`
`----fi
`
`
`
`\f/
`S
`/:‘\E
`m
`
`
`
`E
`=
`
`
`
`i
`.‘u
`
`
`
`FIG. 3
`
`
`
`1‘2
`
`
`
`f3
`
`
`a"
`
`

`

`Case 6:20-cv-01042-ADA Document 1-3 Filed 11/11/20 Page 7 of 13
`Case 6:20-cv-01042-ADA Document 1-3 Filed 11/11/20 Page 7 of 13
`
`
`US. Patent
`
`
`
`
`Mar. 29, 2011
`
`
`
`
`Sheet 4 of5
`
`
`
`US 7,916,781 B2
`
`
`
`
`FIG. 5A
`
`
`
`304
`
`
`
`
`
`304
`
`
`
`

`

`Case 6:20-cv-01042-ADA Document 1-3 Filed 11/11/20 Page 8 of 13
`Case 6:20-cv-01042-ADA Document 1-3 Filed 11/11/20 Page 8 of 13
`
`
`U.S. Patent
`
`
`
`
`Mar. 29, 2011
`
`
`
`
`Sheet 5 of 5
`
`
`
`US 7,916,781 B2
`
`
`
`
`
`

`

`Case 6:20-cv-01042-ADA Document 1-3 Filed 11/11/20 Page 9 of 13
`Case 6:20-cv-01042-ADA Document 1-3 Filed 11/11/20 Page 9 of 13
`
`
`
`US 7,916,781 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. 11/542,950, filed Oct. 3, 2006 now US. Pat. No. 7,421,
`
`
`
`
`
`
`
`032, which is a continuation of US. application Ser. No.
`
`
`
`
`
`
`
`
`
`09/861,102, filedMay 18, 2001,nowU.S. Pat. No. 7,1 16,710,
`
`
`
`
`
`
`
`
`which claims the priority ofUS. Provisional Application Ser.
`
`
`
`
`
`
`
`No. 60/205,095, filed May 18, 2000, and is a continuation-
`
`
`
`
`
`
`
`
`in-part ofU.S. application Ser. No. 09/922,852, filedAug. 18,
`
`
`
`
`
`
`
`
`
`2000, now US. Pat. No. 7,089,477. The disclosure of the
`
`
`
`
`
`
`
`
`prior applications are considered part of (and are incorporated
`
`
`
`
`
`
`
`by reference in) the disclosure of this application.
`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 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
`
`10
`
`
`
`15
`
`
`
`20
`
`25
`
`
`
`30
`
`
`
`35
`
`
`
`40
`
`
`
`45
`
`
`
`50
`
`
`
`55
`
`
`
`60
`
`
`
`65
`
`
`
`
`2
`
`
`
`
`
`
`
`
`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
`
`
`
`
`
`
`
`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
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`Case 6:20-cv-01042-ADA Document 1-3 Filed 11/11/20 Page 10 of 13
`Case 6:20-cv-01042-ADA Document 1-3 Filed 11/11/20 Page 10 of 13
`
`
`
`
`3
`
`
`
`
`
`
`
`
`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 truncated
`rate-1 recursive convolutional coder with the transfer func-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`tion 1/(1 +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 35177269953
`
`
`
`US 7,916,781 B2
`
`4
`
`
`
`
`
`
`
`
`
`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
`
`
`
`
`
`
`
`
`
`fixed, the Tanner graph represents a binary linear block code
`
`
`
`
`
`
`
`
`
`
`
`.
`with k information bits (ul,
`.
`, uk) and r parity bits
`.
`
`
`
`
`
`
`
`
`
`
`
`.
`.
`.
`, x,), as follows. Each of the information bits is
`(x1,
`
`
`
`
`
`
`
`
`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
`
`R
`
`£71
`Xj = Xj71+ 2 W121)“;
`
`10
`
`
`
`15
`
`
`
`20
`
`. 6936,,
`yn:xl@x2@x3@. .
`
`
`
`
`
`
`
`
`
`
`
`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, Zifi:1 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
`
`
`
`
`
`
`connected to three check nodes, corresponding to q:3.
`
`
`
`
`
`
`
`
`Each check node 304 is connected to exactly “a” informa-
`
`
`
`
`
`
`
`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
`coder 400 is a serial concatenation ofthe LDGM code and the
`
`
`
`
`
`
`
`25
`
`
`
`30
`
`
`
`35
`
`
`
`40
`
`
`
`45
`
`
`
`50
`
`
`
`55
`
`
`
`60
`
`
`
`65
`
`
`
`.
`
`.
`
`.
`
`
`
`
`
`
`
`
`
`
`
`
`, vm), then we have the recursive formula for j:
`(V1,
`.
`
`
`
`
`
`
`
`.
`, r. This is in effect the encoding algorithm.
`1, 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-
`
`
`
`
`
`
`
`wordis(u1, .. .,uk;x1, .. .,x4.
`
`
`
`
`The rate of the nonsystematic code is
`
`
`
`
`
`
`
`a
`
`Rn 5y: —
`
`1
`Eff;
`
`
`
`
`
`The rate of the systematic code is
`
`a
`
`
`Rsys =
`
`a+zmi
`
`
`
`
`
`
`
`
`
`
`
`
`
`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 fq:1, and the rest zero, in which
`
`
`
`VlSyS
`simplifies to R:1/q.
`case R
`
`
`
`
`
`
`
`
`
`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):
`
`Zipixi'l to be
`
`
`
`
`
`
`
`
`
`
`
`the generating functions ofthese sequences. The pair (2», p) is
`
`
`
`
`
`
`called a degree distribution. For L(x):2ifixi,
`
`

`

`Case 6:20-cv-01042-ADA Document 1-3 Filed 11/11/20 Page 11 of 13
`Case 6:20-cv-01042-ADA Document 1-3 Filed 11/11/20 Page 11 of 13
`
`
`
`US 7,916,781 B2
`
`
`6
`
`
`
`
`
`
`
`
`
`An erasure E output means that the receiver does not know
`
`
`
`
`
`
`
`how to demodulate the output. Similarly, when 1 is transmit-
`
`
`
`
`
`
`
`
`
`
`ted, the receiver can receive either 1 or E. Thus, for the BEC,
`
`
`ye{0, E, 1}, and
`
`
`
`
`
`"10(14):
`
`
`+00 if y=0
`
`
`if y=E
`0
`
`
`if y=1
`—oo
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`In the BSC, there are two possible inputs (0,1) and two
`
`
`
`
`
`
`
`
`possible outputs (0, 1). The BSC is characterized by a set of
`
`
`
`
`
`
`
`conditional probabilities relating all possible outputs to pos-
`
`
`
`
`
`
`
`
`sible inputs. Thus, for the BSC ye{0, 1},
`
`
`log
`
`
`p
`m0(14) =
`
`1-p
`—log
`
`p
`
`if
`
`
`
`:0
`
`
`
`y
`
`if y = 1
`
`
`
`
`
`
`
`
`
`
`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 V3 and 1 to the symbol with amplitude 4/3,
`
`
`
`output yeR, then
`
`mowHyVEflvo
`
`
`
`
`
`
`
`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.
`
`10
`
`
`
`15
`
`
`
`20
`
`25
`
`
`
`30
`
`
`
`35
`
`
`
`40
`
`
`
`
`5
`
`
`
`
`
`
`The rate of the systematic IRA code given by the
`
`
`
`1
`o
`o
`L(x)=f/I(t)dt/f/I(t)dt
`
`ZPj/j 71
`
`Rate 2 1+
`
`
`
`./
`Aj/J'
`
`
`j Z
`
`
`
`
`degree distribution is given by
`
`
`
`
`
`
`“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(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 repre-
`
`
`
`
`
`
`
`sented by its log likelihood ratio, m:log(p(0)/p(1)). 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
`
`watv
`m(u a v) = 2mm a 14) + ”1004)
`
`
`
`
`
`
`
`
`
`where m0(u) is the log-likelihood message associated with u.
`
`
`
`
`
`
`If u is a check node, the corresponding formula is
`
`
`m(u a v)
`m(w a 14)
`
`
`WV
`
`
`
`2
`2
`— 1—1 tanh
`
`
`tanh
`
`
`
`
`
`
`
`
`
`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
`
`
`
`
`
`
`
`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:1|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) = Z wm(w a 14).
`
`
`
`
`
`
`
`
`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 canreceive either 0 or an erasure E.
`
`50
`
`
`
`55
`
`
`
`60
`
`
`
`65
`
`
`
`45
`
`
`
`a
`
`
`
`TABLE 1
`
`
`2
`
`
`0.139025
`
`0.2221555
`
`
`
`0.638820
`
`
`
`
`
`0.333364
`1.1840
`
`1.1981
`
`0.190
`
`—0.4953
`
`
`
`3
`
`
`0.078194
`0.128085
`0.160813
`0.036178
`
`
`
`
`
`
`
`
`
`
`
`0.108828
`0.487902
`
`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
`
`
`
`
`
`
`A2
`
`A3
`
`A5
`
`A6
`
`A10
`
`A11
`
`A12
`
`A13
`
`A14
`
`A16
`
`A27
`
`A28
`
`Rate
`
`oGA
`
`0*
`
`(Eb/N0) * (dB)
`
`S.L. (dB)
`
`
`
`
`
`
`
`
`
`
`
`
`
`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 thresh-
`
`
`
`
`
`
`
`
`
`old, the actual sum-product decoding thres