[191
`United States Patent
`6,023,783
`[11] Patent Number:
`[45] Date of Patent: Feb. 8, 2000
`Divsalar et al.
`
`
`
`U8006023783A
`
`54] HYBRID CONCATENATED CODES AND
`ITERATIVE DECODING
`
`75]
`
`Inventors: Dariush Divsalar, Pacific Palisades;
`Fabrizio Pollara, La Canada, both of
`Calif.
`
`Benedetto, S., et al., “Bandwidth efficient parallel concat-
`enated coding schemes”, Electronics Letters, vol. 31, No.
`24, pp. 2067—2069, Nov. 23, 1995.
`
`Divsalar, D., et al., “Turbo Codes for PCS Applications”,
`IEEE ICC ’95, Seattle, WA, pp. 54—59, Jun. 1995.
`
`73] Assignee: California Institute of Technology,
`Pasadena, Calif.
`
`Divsalar, D., et al., “Multiple Turbo Codes”, MILCOM ’95,
`San Diego, CA, pp. 279—285, Nov. 5—6, 1995.
`
`
`
`21] Appl. No.2 08/857,021
`
`22]
`
`Filed:
`
`May 15, 1997
`
`51]
`
`Int. Cl.7 ........................ H03M 13/12; 1103M 13/22;
`H04L 25/49
`.......................... 714/792; 375/262; 375/264;
`52] US. Cl.
`375/265; 714/755; 714/757; 714/794; 714/795
`58] Field of Search .................................. 371/37.4, 37.6,
`371/37.06, 43.2, 43.4, 43.6, 43.7; 375/264,
`265, 262, 341
`
`56]
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`5,233,629
`5,446,747
`5,721,745
`5,729,560
`5,734,962
`
`8/1993 Paik et al.
`................................. 375/39
`
`8/1995 Berrou
`.. 371/45
`2/1998 Hladik et al.
`.. 371/43
`
`.
`371/43.1
`3/1998 Hagenauer et al.
`.......................... 455/121
`3/1998 Hladik et al.
`
`OTHER PUBLICATIONS
`
`Divsalar, D., et al. “Multiple Turbo Codes for Deep—Space
`Communications”, The Telecommunications and Data
`Acquisition Progress Report 42—121 for NASA and Califor-
`nia Institute of Technology Jet Propulsion Laboratory,
`Joseph H. Yuen, ed., pp. 60—77, May 15, 1995.
`Divsalar, D., et al. “On the Design of Turbo Codes”, The
`Telecommunications and Data Acquisition Progress Report
`42—123 for NASA and California Institute of Technology Jet
`Propulsion Laboratory, Joseph H. Yuen, ed., pp. 99—121,
`Nov. 15, 1995.
`Divsalar, D., et al., “Low—Rate Turbo Codes for Deep Space
`Communications”, Proceedings from the 1995 IEEE Inter-
`national Symposium on Information Theory, Whistler, Brit-
`ish Columbia, Canada, p. 35, Sep. 17—22, 1995.
`
`d
`
`(List continued on next page.)
`
`Primary Examiner—Stephen M. Baker
`Attorney, Agent, or Firm—Fish & Richardson, PC.
`
`[57]
`
`ABSTRACT
`
`Several improved turbo code apparatuses and methods. The
`invention encompasses several classes: (1) A data source is
`applied to two or more encoders with an interleaver between
`the source and each of the second and subsequent encoders.
`Each encoder outputs a code element which may be trans—
`mitted or stored. A parallel decoder provides the ability to
`decode the code elements to derive the original source
`information d without use of a received data signal corre-
`sponding to d. The output may be coupled to a multilevel
`trellis-coded modulator (TCM).
`(2) A data source d is
`applied to two or more encoders with an interleaver between
`the source and each of the second and subsequent encoders.
`Each of the encoders outputs a code element. In addition, the
`original data source d is output from the encoder. All of the
`output elements are coupled to a TCM. (3) At least two data
`sources are applied to two or more encoders with an inter-
`leaver between each source and each of the second and
`
`subsequent encoders. The output may be coupled to a TCM.
`(4) At least two data sources are applied to two or more
`encoders with at least two interleavers between each source
`
`and each of the second and subsequent encoders. (5) At least
`one data source is applied to one or more serially linked
`encoders through at least one interleaver. The output may be
`coupled to a TCM. The invention includes a novel way of
`terminating a turbo coder.
`
`74 Claims, 30 Drawing Sheets
`
`
`
`ERICSSON EXHIBIT 1001
`
`

`

`6,023,783
`Page 2
`
`OTHER PUBLICATIONS
`
`Benedetto, S., et al. “Soft—Output Decoding Algorithms in
`Iterative Decoding of Turbo Codes”, The Telecommunica-
`tions and Data Acquisition Progress Report 42—724 for
`NASA and California Institute of Technology Jet Propulsion
`Laboratory, Joseph H. Yuen, ed., pp. 63—87, Feb. 15, 1996.
`Divsalar, D., et al., “Effective free distance of turbo codes”,
`Electronic Letters, vol. 32, No. 5, pp. 445446, Feb. 29,
`1996.
`Benedetto, S., et al. “Serial Concatenation of Interleaved
`Codes: Performance Analysis, Design, and Iterative Decod-
`ing”, The Telecommunications
`and Data Acquisition
`Progress Report 42—126 for NASA and California Institute
`of Technology Jet Propulsion Laboratory, Joseph H. Yuen,
`ed., pp. 1—26, Aug. 15, 996.
`Benedetto, S., et al. “A Soft—Input Soft—Output Maximum A
`Posteriori (MAP) Module to Decode Parallel and Serial
`Concatcnatcd Codes”, The Telecommunications and Data
`Acquisition Progress Report 42—127 for NASA and Califor-
`nia Institute of Technology Jet Propulsion Laboratory,
`Joseph H. Yuen, ed., pp. 1420, Nov. 15, 1996.
`Benedetto, S., et al., “Parallel Concatenated Trellis Coded
`Modulation”, ICC ’96, pp. 974—978, Jun. 1996.
`Benedetto, S., et al., “A Soft—Input Soft—Output APP Mod—
`ule for Iterative Decoding of Concatenated Codes”, IEEE
`Communication Letters, vol. 1, No. 1, pp. 22—24, Jan. 1997.
`Divsalar, D., et al., “Hybrid Concatenated Codes and Itera-
`tive Decoding”, Proceedings from the IEEE 1997 Interna-
`tional Symposium on Information Theory, Ulm, Germany, p.
`10, Jun. 29—Jul. 4, 1997.
`Benedetto, S., et al., “Serial Concatenation of interleaved
`codes: performance analysis, design, and iterative decod-
`ing”, Proceedings from the IEEE 1997 International Sym-
`posium on Information Thcory, Ulm, Germany, p. 106, Jun.
`29—Jul. 4, 1997.
`
`Benedetto, S., et al., “Serial Concatenated Trellis Coded
`Modulation with Iterative Decoding”, Proceedings from the
`IEEE 1997 International Symposium on Information
`Theory, Ulm, Germany, p. 8, Jun. 29—Jul. 4, 1997.
`Benedetto, S., et al., “Design of Serially Concatenated
`Interleaved Codes”,
`ICC ’97, Montreal, Canada, pp.
`7104714, Jun. 1997.
`Hagenauer et al., “A Viterbi Algorithm with Soft—Decision
`Outputs and its Applications”, GLOBECOM ’89, pp.
`47.1.1—47.1.7, Nov. 1989.
`Berrou et al., “Near Shannon Limit Error—Correcting Cod-
`ing and Decoding: TurboiCodes”, ICC ’93, pp. 106441070,
`May 1993.
`Le Goff et al., “Turbo—Codes and High Spectral Efficiency
`Modulation”, ICC ’94, pp. 645—649, May 1994.
`Hagenauer et al., “Decoding “Turbo”—C0des with the Soft
`Output Viterbi Algorithm (SOVA)”, 1994 International
`Symposium on Information Theory, p. 164, Jul. 1994.
`Anderson, “‘Turbo’ Coding for Deep Space Applications”,
`1995 International Symposium on Information Theory, p.
`36, Sep. 1995.
`Siala et al., “An Iterative Decoding Scheme for Serially
`Concatenated Convolutional Codes”, 1995 International
`Symposium on Information Theory, p. 473, Sep. 1995.
`Fazel et al., “Combined Multilevel TurboiCode with SPSK
`Modulation”, GLOBECOM ’95, pp. 649—652, Nov. 1995.
`Thitimaj shima, “Recursive Systematic Convolutional Codes
`and Application to Parallel Concatenation”, GLOBECOM
`’95, pp. 2267—2272, Nov. 1995.
`Hagenauer et al., “Iterative Decoding of Binary Block and
`Convolutional Codes”, IEEE Trans. on Information Theory,
`vol. 42, No. 2, Mar. 1996, pp. 429—445, Mar. 1996.
`Lcc, “Convolutional Coding: Fundamcntals and Applica-
`tions”, Artech House, 1997, p. 38, Oct. 1997.
`
`

`

`US. Patent
`
`Feb. 8, 2000
`
`Sheet 1 0f 30
`
`6,023,783
`
`SYSTEMATIC
`
`
`
`
`FIRST
`
`
`CODING
`
`
`12
`
` TEMPORAL
`INTERLEA VING
`
`
`SECOND
`
`SYSTEMATIC
`
`CODING
`
`FIG. 1
`
`(Prior Art)
`
`u
`
`
`
`X1i
`
`x1p
`
`xgp
`
`X3p
`
`

`

`US. Patent
`
`Feb. 8, 2000
`
`Sheet 2 0f 30
`
`6,023,783
`
`WHITE
`
`—»
`
`00
`
`0
`
`
`
`0
`
`.3:
`
`000.
`
`0
`
`00
`
`:e
`
`1:D
`
`
`
`

`

`US. Patent
`
`Feb. 8, 2000
`
`Sheet 3 0f 30
`
`6,023,783
`
`
`
`FIG. 5
`
`
`
`

`

`US. Patent
`
`Feb. 8, 2000
`
`Sheet 4 0f 30
`
`6,023,783
`
`
`
`Not
`
`Transmitted
`
`To
`
`Modulator
`
`FIG. BB
`
`Modulator
`
`To
`
`Multiplexer
`
`FIG. 632
`
`

`

`US. Patent
`
`Feb. 8, 2000
`
`Sheet 5 0f 30
`
`6,023,783
`
`
`
`FIG. 60
`
`
`
`

`

`US. Patent
`
`Feb. 8, 2000
`
`Sheet 6 0f 30
`
`6,023,783
`
`
`
`Channel
`
`To
`
`To
`
`Channel
`
`

`

`US. Patent
`
`Feb. 8, 2000
`
`Sheet 7 0f 30
`
`6,023,783
`
`100
`
`Code 0
`Rate = 1/3
`m = 11
`
`Code A
`Rate = 7/2
`= 12m
`
`Code E
`Rate = 1/15
`m = 12
`
`10-7
`
`10.2
`
`103
`
`BER
`
`0
`70-10 -0.8 -0.6 -0.4 -0.2 0.0 0.2 0.4 0.6 0.0 1.0
`
`Eb/No, dB
`
`FIG. 8
`
`

`

`US. Patent
`
`Feb.8,2000
`
`Sheet8 0f30
`
`6,023,783
`
`
`
`Input Data
`
`Differential Encoder
`
`16, 384-bit
`Interleaver
`
`FIG. 10
`
`
`
`
`

`

`US. Patent
`
`Feb. 8, 2000
`
`Sheet 9 0f 30
`
`6,023,783
`
`Input Data
`
`Input Data
`
`
`
`
`

`

`US. Patent
`
`Feb. 8,2000
`
`Sheet 10 0f 30
`
`6,023,783
`
`104
`
`RATE=1/4
`
`m=20
`
`N = 16384,
`
`

`

`US. Patent
`
`Feb. 8,2000
`
`Sheet 11 0130
`
`6,023,783
`
`107
`
`r= 1/4
`
`In =20
`
`Three K=3 Codes
`Random Inter/eaver,
`
`Two K=5 Codes
`Random lnter/eaver,
`N = 192
`
`BER
`
`10'4
`
`lnter/eaver, N =256
`
`Convolutiona/ Code
`(Reference)
`
`Three K=4 Codes
`
`11-Random
`and (a,=2,ac=4)
`Interleaver, N=256
`
`Two K=5 Codes
`(ar=2:ac =4)
`
`-5
`
`70
`
`0
`
`0.2 0.4 0.6 0.8 1.0
`
`1.2
`
`1.4
`
`1.6
`
`1.8 2.0
`
`Eb/Na, dB
`
`FIG. 14
`
`

`

`US. Patent
`
`Feb. 8,2000
`
`Sheet 12 0f 30
`
`6,023,783
`
`10"
`
`10‘2
`
`BER
`
`10'3
`
`N =4096
`
`Code Rate = 1/4
`
`K= 15, r= 1/4
`Galileo Code
`
`/
`
`Three K=3 Codes
`.
`m=20
`
`/
`
` /
`
`10'5
`-0.2
`
`-0.1
`
`0.0
`
`0.1
`
`0.2
`
`0.3
`
`0.4
`
`0.5
`
`Eb/No, dB
`
`FIG. 15
`
`10-4 Three K=4 Codes
`m=30
`
`/
`
`Three K=4 Codes
`m=20
`
`

`

`US. Patent
`
`Feb. 8,2000
`
`Sheet 13 0f 30
`
`6,023,783
`
`FIG. 16
`
`(Prior Art)
`
`«at
`
`cm» ow cap
`\1
`
`\I
`
`\1WWW».
`
`®’ ®"@"@
`
`(c)ParaI/e/
`
`Time
`
`FIG. 17
`
`

`

`US. Patent
`
`Feb. 8,2000
`
`Sheet 14 0f 30
`
`6,023,783
`
` y1,-=p(2u-1)+n1,-
`
`y1p=p(2x7p-1)+n1p
`
`
`
`FIG. 20A
`
`

`

`US. Patent
`
`Feb. 8,2000
`
`Sheet 15 0f 30
`
`6,023,783
`
`
`_
`I9“I“'
`
` [3(m)- MM1
`
`l-le I.3' Map3 a._' L~3(m+1)
`I-L-e..IorSova3IE3Ii.
`
`
`Decoded
`
`II_-
`
`Lk
`
`
`
`Bits
`
`FIG. 208
`
`

`

`US. Patent
`
`Feb. 8,2000
`
`Sheet 16 0f 30
`
`6,023,783
`
`
`
`FIG. 200
`
`

`

`US. Patent
`
`Feb. 8,2000
`
`Sheet 17 0f 30
`
`6,023,783
`
`
`
`Observation
`
`Received
`
`From Encoder 0
`
`
`
`FIG. 200
`
`

`

`US. Patent
`
`Feb. 8,2000
`
`Sheet 18 0f 30
`
`6,023,783
`
`Received Observation
`From Channel for d
`
`
`DMUX
`
`
`Received Observation
`
`
`
`Decoded
`
`BITS
`
`From Channel for p
`
`
`
`Observation
`
`Received
`
`From Encoder 7
`
`
`
`FIG. 20E 1
`
`

`

`US. Patent
`
`Feb. 8,2000
`
`Sheet 19 0f 30
`
`6,023,783
`
`.
`Coded
`Input B’t \ / Output
`
`W Bits
`d/u,p
`
`State 8,- at
`time k—i
`o
`
`State 8/- at
`time k—1
`0 Original
`
`Treatas @ Coded
`Em M’A/ Bits
`
`Output
`
`Input Bits
`
`d,u,p/u,p
`
`FIG. 2052
`
`Modified
`
`extrinsic,
`information for u
`
`Decoded
`
`from encoder 2
`
`Y1 Observation received
`from encoder 1
`
`Y2 Observation received
`
`FIG. 20F
`
`extrinsic
`information for p
`
`

`

`US. Patent
`
`Feb. 8,2000
`
`Sheet 20 0f 30
`
`6,023,783
`
`for q2
`
`Modulator
`
`
`
`
` Inter/ea ver Deinter/ea ver
`From
`
`
`
`Modulator
`
`for q,
`
`FIG. 206
`
`

`

`US. Patent
`
`Feb. 8,2000
`
`Sheet 21 0f 30
`
`6,023,783
`
`I!
`
`FIG.21/:
`
`
`
`

`

`US. Patent
`
`Feb.8,2000
`
`Sheet22 0f30
`
`6,023,783
`
`6
`
`6
`
`9Ial
`
`a-ru-a-ru-a-ru-a-ru-a
`.Illi.m
`
`Ill:
`
`q
`
`EN.3
`
`

`

`US. Patent
`
`Feb. 8,2000
`
`Sheet 23 0f 30
`
`6,023,783
`
`
`
`10'5
`2.5
`
`2.6
`
`2.7
`
`2.8
`
`2.9
`
`3.0
`
`3.1
`
`3.2
`
`Eb/NO, dB
`
`FIG. 22
`
`

`

`US. Patent
`
`Feb. 8,2000
`
`Sheet 24 0f 30
`
`6,023,783
`
`8PSK
`
`8PSK
`
`FIG23A
`
`H"_
`
`
`
`

`

`US. Patent
`
`Feb.8,2000
`
`Sheet25 0f30
`
`6,023,783
`
`MamGt
`
`

`

`US. Patent
`
`Feb. 8,2000
`
`Sheet 26 0f 30
`
`6,023,783
`
`10‘?
`
`10'3
`
`E 10‘4
`
`10‘5
`
`10-6
`33
`
`
`
`.
`37
`
`38
`
`a4
`
`35
`
`a6
`
`BIT SNB, dB
`
`FIG. 24
`
`BER
`
`Eb/No, dB
`
`FIG. 26
`
`

`

`US. Patent
`
`Feb. 8,2000
`
`Sheet 27 0f 30
`
`6,023,783
`
`6
`
`w.
`
`to 0AM
`
`FIG.25A
`
`
`
`

`

`US. Patent
`
`Feb.8,2000
`
`Sheet28 0f30
`
`6,023,783
`
`9
`
`aI...1?
`
`I'llm
`
`GI.
`
`lea
`
`mam6E
`
`

`

`US. Patent
`
`Feb. 8,2000
`
`Sheet 29 0f 30
`
`6,023,783
`
`
`
`FIG. 27
`
`

`

`US. Patent
`
`Feb. 8,2000
`
`Sheet 30 0f 30
`
`6,023,783
`
`i [
`
`.
`
`-101
`
`Reliability
`Calculation
`
`‘
`
`Calculation
`
`5
`
`;
`
`m Bit ”
`
`SVmbO’
`
`Reliability
`
`1:
`
`-7
`
`0 ;
`
`i
`
`FIG. 28
`
`

`

`6,023,783
`
`1
`HYBRID CONCATENATED CODES AND
`ITERATIVE DECODING
`
`ORIGIN OF INVENTION
`
`The invention described herein was made in the perfor-
`mance of work under a NASA contract, and is subject to the
`provisions of Public Law 96—517 (35 USC 202) in which the
`Contractor has elected to retain title.
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`
`This invention relates to error correcting codes.
`2. Description of Related Art
`Turbo codes are binary error—correcting codes built from
`the parallel concatenation of two recursive systematic con-
`volutional codes and using a feedback decoder. Recently
`introduced be Berrou, et al. (“Near Shannon limit error—
`correcting coding and decoding: Turbo-codes", ICC’93,
`Conf Rec. pp. 1064—1070, Geneva, May 1993), the basics of
`such codes are described further in U.S. Pat. Nos. 5,446,747
`and 5,406,570.
`The reference and patents to Berrou describe a basic turbo
`code encoder architecture of the type shown in the block
`diagram in FIG. 1. As described in Berrou ’747, FIG. 1
`shows a block diagram of a coder in an example where two
`distinct codes are used in parallel. Each source data element
`d to be coded is coupled to a first systematic coding module
`11 and, through a temporal interleaving module 12, to a
`second systematic coding module 13. The coding modules
`11 and 13 may be of any known systematic type, such as
`convolutional coders, that take into account at least one of
`the preceding source data elements in order to code the
`source data element d. The codes implemented in coding
`modules 11 and 13 may be identical or different.
`The input information bits d feed the first coding module
`11 and, after being scrambled by the interleaving module 12,
`enter the second coding module 13. Acodeword of a parallel
`concatenated code consists of the information input bits to
`the first encoder followed by the parity check bits of both
`encoders.
`
`Under this architecture, there are at least two coded data
`elements Y1 and Y2, coming from distinct coders 11 and 13,
`associated with each source data element d. A data element
`X, equal to the source data element d, is also transmitted.
`This characteristic was described in Berrou ’747 as “neces-
`
`sary for the making of the decoding modules”.
`The transmitted coded data elements and source data
`element become received data elements at a decoder. The
`
`task of the decoder is to re-construct the original data source
`d bit stream from the received data elements, which may
`have been corrupted by noise.
`Thus, an important aspect of prior art turbo code encoders
`is that they transmit a data element X equal to input source
`data element d.
`
`The present invention results from observation that the
`prior art fails to achieve a simpler architecture for the
`encoder, and fails to provide as robust encoding as is
`required or desired in certain environments, including low-
`power, constrained-bandwidth uses, such as deep space
`communications and personal communication devices, and
`high-noise environments.
`SUMMARY OF THE INVENTION
`
`improved
`invention encompasses several
`The present
`turbo code apparatuses and methods. In a first class of turbo
`
`10
`
`15
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`code encoders, a data source d is applied to two or more
`encoders with an interleaver between the data source and
`
`each of the second and subsequent encoders. Each of the
`encoders outputs a turbo code element which may be
`transmitted or stored. Aparallel decoder provides the ability
`to decode the turbo code elements to derive the original
`source information d without use of a received data signal
`corresponding to d. The output of the turbo code encoder
`optionally may be coupled to a multilevel
`trellis-coded
`modulator that provides excellent performance.
`In a second class of turbo code encoders, a data source d
`is applied to two or more encoders with an interleaver
`between the data source and each of the second and subse-
`quent encoders. Each of the encoders outputs a turbo code
`element. In addition, the original data source d is output
`from the encoder. All of the output elements are coupled to
`a multilevel trellis-coded modulator.
`
`In a third class of turbo code encoders, at least two data
`sources are applied to two or more encoders with an inter-
`lcavcr between each data source and each of the second and
`
`subsequent encoders. Each of the encoders outputs a plu-
`rality of turbo code elements which may be transmitted or
`stored. The output of the turbo code encoder optionally may
`be coupled to a multilevel trellis-coded modulator.
`In a fourth class of turbo code encoders, at least two data
`sources are applied to two or more encoders with at least two
`interleavers between each data source and each of the
`second and subsequent encoders. Each of the encoders
`outputs a plurality of turbo code elements which may be
`transmitted or stored. The output of the turbo code encoder
`optionally may be coupled to a multilevel
`trellis-coded
`modulator.
`
`In a fifth class of turbo code encoders, at least one data
`source is applied to one or more serially linked encoders
`through at least one interleaver.
`The invention also encompasses a novel method of ter-
`minating or resetting a turbo coder, and a general parallel
`decoder structure.
`
`The details of the preferred embodiments of the present
`invention are set forth in the accompanying drawings and
`the description below. Once the details of the invention are
`known, numerous additional innovations and changes will
`become obvious to one skilled in the art.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a block diagram of a prior art turbo code encoder.
`FIG. 2 is a block diagram of a general model of a turbo
`code encoder having three codes.
`FIG. 3 is a matrix of a weight-4 sequence.
`FIG. 4 is a block diagram of an input trellis termination
`method for turbo code encoders in accordance with the
`present invention.
`FIG. 5 is a block diagram of a turbo cncodcr showing
`output only of encoded parity elements.
`FIG. 6A is a block diagram of a third embodiment of the
`present invention, showing output of multiple encoded ele-
`ments derived from multiple input data sources, the use of
`multiple interleavers on at least one data source, and an
`optional multilevel trellis-coded modulator.
`FIG. 6B is a block diagram of a variation of the coder
`shown in FIG. 6A, showing a self—concatenating code.
`FIG. 6B2 is a block diagram showing a variation of a
`self-concatenated code, where the encoder has at least one
`input data line (1, and d is sent to the modulator.
`
`

`

`6,023,783
`
`3
`FIG. 6C is a block diagram of a fourth embodiment of the
`present invention, showing output of multiple encoded ele—
`ments derived from multiple input data sources, the use of
`multiple interleavers on at least one data source, and an
`optional multilevel trellis-coded modulator.
`FIG. 7A is a block diagram of a serial encoder in
`accordance with the present invention.
`FIG. 7B is a block diagram of a parallel-serial encoder in
`accordance with the present invention.
`FIG. 7C is a block diagram of a serial-parallel hybrid
`encoder in accordance with the present invention.
`FIG. 8 is a diagram showing the performance of various
`turbo codes.
`
`FIG. 9 is a block diagram of a first rate 1/2 turbo coder in
`accordance with the present invention.
`FIG. 10 is a block diagram of a second rate 1/2 turbo coder
`in accordance with the present invention.
`FIG. 11 is a block diagram of a rate 1/3 turbo coder in
`accordance with the present invention.
`FIG. 12 is a block diagram of a rate M: turbo coder in
`accordance with the present invention.
`FIG. 13 is a diagram showing the performance of various
`rate 1%: turbo codes.
`
`FIG. 14 is a diagram showing the performance of various
`turbo codes with short block sizes.
`
`FIG. 15 is a diagram showing the performance of various
`three code turbo codes.
`
`FIG. 16 is a block diagram of a prior art decoder structure.
`FIG. 17 is a block diagram of a parallel decoder structure
`in accordance with the present invention.
`FIG. 18 is a block diagram of a channel model.
`FIG. 19 is a signal flow graph for extrinsic information in
`a decoder.
`
`FIG. 20A is a block diagram of a single parallel block
`decoder in accordance with the present invention.
`FIG. 20B is a block diagram showing a multiple turbo
`code decoder for a three code system, using three blocks
`similar to the decoder in FIG. 20A.
`
`FIG. 20C is a block diagram showing a multiple turbo
`code decoder for a three code system, using three blocks
`similar to the decoder in FIG. 20A, and having a switchable
`serial decoder mode.
`
`FIG. 20D is a block diagram showing a decoder corre-
`sponding to the self—concatenating coder of FIG. 6B.
`FIG. 20D2 is a block diagram showing a decoder corre-
`sponding to the self-concatenated coder of FIG. 6B2.
`FIG. 20E is a block diagram showing a decoder corre-
`sponding to the serial coder of FIG. 7A.
`FIG. 20E2 shows a block diagram of an original and a
`modified MAP algorithm.
`FIG. 20F is a block diagram showing a decoder corre-
`sponding to the serial coder of FIG. 7B.
`FIG. 20G is a block diagram showing a decoder corre-
`sponding to the hybrid concatenated code (serial-parallel,
`type II) of FIG. 7C.
`FIG. 21 is a block diagram of a 16 QAM turbo trellis-
`coded modulation coder in accordance with the present
`invention.
`
`10
`
`15
`
`30
`
`35
`
`4O
`
`45
`
`50
`
`55
`
`60
`
`FIG. 22 is a diagram showing the BER performance of the
`coder shown in FIG. 21.
`
`65
`
`FIG. 23 is a block diagram of an 8 PSK turbo trellis-coded
`modulation coder in accordance with the present invention.
`
`4
`FIG. 24 is a diagram showing the BER performance of the
`coder shown in FIG. 23.
`
`FIG. 25 is a block diagram of a 64 QAM turbo trellis-
`coded modulation coder in accordance with the present
`invention.
`
`FIG. 26 is a diagram showing the BER performance of the
`coder shown in FIG. 25.
`
`FIG. 27 is a block diagram of general embodiment of the
`present invention, showing output of the source data element
`and encoded elements to a multilevel trellis-coded modula-
`tor.
`
`FIG. 28 is a block diagram showing a general decoder for
`the TCM encoded output of, for example, FIGS. 21, 23, and
`25.
`
`Like reference numbers and designations in the various
`drawings indicate like elements.
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`Throughout this description, the preferred embodiment
`and examples shown should be considered as exemplars,
`rather than as limitations on the present invention.
`Overview
`Turbo codes are believed to be able to achieve near
`Shannon-limit error correction performance with relatively
`simple component codes and large interleavers. The present
`invention encompasses several novel designs for turbo code
`encoders and a corresponding decoder that is suitable for
`error correction in high noise or constrained—bandwidth, low
`power uses, such as personal communications systems
`(PCS) applications, where lower rate codes can be used.
`For example,
`in multiple-access schemes like CDMA
`(Code Division Multiple Access), the capacity (maximum
`number of users per cell) can be expressed as:
`
`’7
`
`(1)
`
`where n is the processinggain and Eb/NO is the required
`signal-to-noise ratio to achieve a desired bit error rate (BER)
`performance (Eh: energy received per useful bit; N0: mono-
`lateral spectral density of noise). For a specified BER, a
`smaller required Eb/No implies a larger capacity or cell size.
`Unfortunately, to reduce Eb/NO, it is necessary to use very
`complex codes (e.g., large constraint length convolutional
`codes). However, the present invention includes turbo codes
`that are suitable for CDMA and PCS applications and which
`can achieve superior performance with limited complexity.
`For example,
`if a (7,
`1/2) convolutional code is used at
`BER=10'3, the capacity is C=0.5n. However, if two (5, 1/3)
`punctured convolutional codes or three (4, 1/3) punctured
`codes are used in a turbo encoder structure in accordance
`
`with the present invention, the capacity can be increased to
`C=0.8n (with 192-bits and 256-bits interleavers, which
`correspond to 9.6 Kbps and 13 Kbps with roughly 20ms
`frames). IIigher capacity can be obtained with larger inter-
`leavers. Note that low rate codes can be used for CDMA
`since an integer number of chips per coded symbol are used
`and bandwidth is defined mainly by chip rate.
`Implementation
`The invention may be implemented in hardware or
`software, or a combination of both.
`In the preferred
`embodiment, the functions of a turbo coder and decoder
`designed in conformance with the principals set forth herein
`are implemented as one or more integrated circuits using a
`suitable processing technology (e.g., CMOS).
`
`

`

`6,023,783
`
`5
`As another example, the invention may be implemented
`in computer programs executing on programmable comput—
`ers each comprising a processor, a data storage system
`(including volatile and non-volatile memory and/or storage
`elements), at least one input device, and at least one output
`device. Program code is applied to input data to perform the
`functions described herein and generate output information.
`The output information is applied to one or more output
`devices, in known fashion.
`Each such program may be implemented in a high level
`procedural or object oriented programming language to
`communicate with a computer system. However, the pro-
`grams can be implemented in assembly or machine
`language, if desired. In any case, the language may be a
`compiled or interpreted language.
`Each such computer program is preferably stored on a
`storage media or device (e.g., ROM or magnetic disk)
`readable by a general or special purpose programmable
`computer, for configuring and operating the computer when
`the storage media or device is read by the computer to
`perform the procedures described herein. The inventive
`system may also be considered to be implemented as a
`computer-readable storage medium, configured with a com-
`puter program, where the storage medium so configured
`causes a computer to operate in a specific and predefined
`manner to perform the functions described herein. An
`example of one such type of computer is a personal com-
`puter.
`Turbo Code Encoders
`Following is a discussion of several general consider-
`ations in designing turbo code encoders and decoders in
`accordance with the present invention. Since these consid-
`erations pertain to the novel designs described below as well
`as prior art designs in some cases, a simple 3-code encoder,
`as shown in FIG. 2, will be used as an initial example.
`General Structure of an Encoder
`In FIG. 2, the turbo code encoder contains three recursive
`binary convolutional encoders, with M1, M2 and M3
`memory cells (comprised of the delay gates D shown in each
`encoder)
`respectively.
`In general,
`the three component
`encoders may not be identical and may not have identical
`code rates. The information bit sequence u=(u1, .
`.
`. uN) of
`length N is applied to the component Encoder 1 through
`interleaver 31:1 (normally set to the identify function), which
`outputs a sequence 111. The component Encoder 1 produces
`two output sequences, xii and xlp (the subscript i stands for
`“information” bits, while the subscript p stands for “parity”
`bits). The component Encoder 2 operates on a reordered
`sequence of information bits, u2, produced by an interleaver
`(also known as a permuter), 312, of length N, and outputs the
`sequence xzp. The component Encoder 3 operates on a
`reordered sequence of information bits, u3, produced by an
`interleaver, 313, of length AT, and outputs the sequence x3p.
`Similarly, subsequent component encoders operate on a
`reordered sequence of information bits, uj, produced by
`interleaver 313., and output the sequence X”:-
`In the preferred embodiment, each interleaver is a pseudo-
`random block scrambler defined by a permutation of N
`elements with no repetitions. That is, a complete block is
`read into an interleaver and read out in a specified (fixed)
`random order.
`
`In general, a decoder (discussed more fully below)
`receives the transmitted sequences xli and xjp, as received
`sequences yj. As noted above, the task of the decoder is to
`re-construct the original data source d bit stream from the
`received data elements, which may have been corrupted by
`noise. In the present invention, the encoder does not need to
`
`6
`transmit the original data sequence. If one or more encoder
`outputs,
`including possibly xli,
`is punctured (not
`transmitted) based on a predetermined pattern, the punctured
`positions will be filled with erasures at the receiver.
`
`FIG. 2 shows an example where a rate r=1/n=% code is
`generated by three component codes with M1=M2=M3=M=
`2, producing the outputs:
`
`10
`
`15
`
`xli=u
`
`X1p=u~gb/ga
`X2p=u2~g1/ga
`X3p=u3 ~gL/ga
`
`n1 is assumed to be an identity, i.e., no permutation), where
`the generator polynomials ga and gb have octal representa-
`tion (7)0le and (5)0le, respectively. Note that various code
`rates can be obtained by proper puncturing of xlp, xzp, x3p,
`and even xh. if a decoder in accordance with the present
`invention is used (see below).
`
`Design of Preferred Constituent Encoders
`
`A design for constituent convolutional codes, which are
`not necessarily optimum convolutional codes, was originally
`reported in S. Benedetto and G. Montorsi, “Design of
`Parallel Concatenated Convolutional Codes” (to be pub-
`lished in IEEE Transactions on Communications, 1996) for
`rate l/n codes. We extend those results to rate b/n codes. It
`has been suggested (without proof) that good random codes
`are obtained if ga is a primitive polynomial. This suggestion,
`used in the report cited above to obtain “good” rate 1/2
`constituent codes, will be used in this article to obtain
`“good" rate 1/3, 2/3, 3A1, and 4/5 constituent codes. By “good"
`codes, we mean codes with a maximum effective free
`distance def, that is, those codes that maximize the minimum
`output weight for weight-2 input sequences (because this
`weight tends to dominate the performance characteristics
`over the region of interest).
`
`Maximizing the weight of output codewords correspond-
`ing to weight—2 data sequences gives the best BER perfor—
`mance for a moderate bit signal-to-noise ratio (SNR) as the
`random interleaver size N gets large. In this region, the
`dominant term in the expression for bit error probability of
`a turbo code with q constituent encoders is:
`
`
`,3
`Eb
`q
`Pb 2 Mil Q 2r—0[1§1df2 + 2]
`
`(2)
`
`where dP132 is the minimum parity-weight (weight due to
`parity checks only) of the codewords at the output of the jth
`constituent code due to weight-2 data sequences, and [3 is a
`constant independent of N. Define dj)2=dp132+2 as the mini-
`mum output weight including parity and information bits, if
`the jth constituent code transmits the information
`(systematic) bits. Usually one constituent code transmits the
`information bits (j=1), and the information bits of other
`codes are punctured. Define def=2qj=1dpjg+2 as the effective
`free distance of the turbo code and 1/Nq'1 as the “interleav—
`er’s gain.” We have the following bound on de2 for any
`constituent code: for any r=b/(b+1) recursive systematic
`convolutional encoder with generator matrix:
`
`30
`
`35
`
`4O
`
`45
`
`50
`
`55
`
`60
`
`65
`
`

`

`G =
`
`1be
`
`
`Ill (D)
`ho (D)
`
`hz (D)
`ho (D)
`
`
`hb(D)
`ho(D)
`
`6,023,783
`
`(3)
`
`8
`
`TABLE 3
`
`Best rate 4/5 constituent codes.
`
`k
`
`4
`
`5
`
`10
`
`Code generator
`
`d2
`
`d3
`
`dmin
`
`h4 = 7
`h3 = 11
`17
`h2
`15
`h1
`13
`hD
`h4 = 5
`h3 = 11
`h2 — 17
`h1 — 15
`13
`hD
`hD—23 h1=35 h2=33 h3=37 h4=31
`h0=23 h1=35 h2
`21 h3=37 h4=31
`hD
`23
`h1
`35
`h2
`21
`h3 = 37
`h4 = 31
`
`4
`4
`5
`5
`5
`
`3
`3
`4
`4
`4
`
`3
`3
`4
`4
`4
`
`where beb is the identity matrix, deg[hi(D)§m, hi(D)¢h0(d),
`i=1,2, .
`.
`. ,b, and hO(D) is a primitive polynomial of degree
`m, the following upper bound holds:
`
`2m71
`[15’s — +2
`b
`
`15
`
`(4)
`
`A corollary of this is that, for any r=b/n recursive sys-
`tematic convolutional code with b inputs, b systematic
`outputs, and n-b parity output bits using a primitive feedback
`generator, we have:
`
`p
`(125
`
`_
`7m,1
`[Kl +2(n —b)
`
`(5)
`
`There is an advantage to using b>1, since the bound in the
`above equation for rate b/bn codes is larger than the bound
`for rate 1/n codes. Examples of codes that meet the upper
`bound for b/bn codes are set forth below.
`A. Best Rate b/b+1 Constituent Codes
`We obtained the best rate 2/3 codes as shown in Table l,
`where d2=dpf)2+2. The minimum-weight codewords corre-
`sponding to weight—3 data sequences are denoted by d3, dmm
`is the minimum distance of the code, and k=m+1 in all the
`tables. By “best” we mean only codes with a large d2 for a
`given In that result in a maximum effective free distance. We
`obtained the best rate 3/4 codes as shown in Table 2 and the
`best rate 4/5 codes as shown in Table 3.
`
`TABLE 1
`
`Best rate 213 constituent codes.
`
`Code generator
`
`h0 = 7
`h0=13
`hn=23
`h0=23
`h0 = 45
`
`h1 = 3
`h1=15
`h1 =35
`h1=35
`h1 = 43
`
`h2 = 5
`h2=17
`h7=27
`h2=33
`h2 = 61
`
`d7
`
`4
`5
`8
`8
`12
`
`d3
`
`3
`4
`5
`5
`6
`
`dw-n
`
`3
`4
`5
`5
`6
`
`TABLE 2
`
`Best rate 314 constituent codes.
`
`Code generator
`
`d2
`
`d3
`
`dmin
`
`h0=7
`h0=7
`h0=7
`hn=13
`hU—23
`h0=23
`h0—23
`hD
`23
`
`h1=5
`h1=5
`h1=5
`h1=15
`h1=35
`h1=35
`h1=35
`h1 = 27
`
`h3=1
`h2=3
`h3=4
`h2=3
`h3=2
`h2=3
`h7=17 h3=11
`h2=33 h3=25
`h<=27 h3=31
`h2=37 h3=21
`h2 = 37 h3 = 21
`
`3
`3
`3
`4
`5
`5
`5
`5
`
`3
`3
`3
`4
`4
`4
`4
`4
`
`k
`
`3
`4
`5
`
`6
`
`k
`
`3
`
`4
`5
`
`30
`
`35
`
`4O
`
`45
`
`50
`
`55
`
`60
`
`65
`
`B. Best Punctured Rate 1/2 Constituent Codes
`A rate 2/3 constituent code can be derived by puncturing
`th