`
`APPLICATION FOR
`
`UNITED STATES PATENT
`
`IN THE NAME OF
`
`Dariush Divsalar
`
`Fabrizio Pollara
`
`of
`
`Jet Prepulsion Laboratory
`California Institute of Technology
`
`FOR
`
`HYBRID CONCATENATED CODES
`AND ITERATIVE DECODING
`
`
`
`
`
`“1:13"‘'1':1Z11:;.131{'3113.1$111
`
`1t.
`
`it?iii‘iaES'TIF?
`
`Scott Harris & John Land
`RD
`FISH & RICHA SON
`4225 Executive Square, Suite 1400
`La Jolla, CA 92037
`(619) 678-5070 voice
`19
`- 0
`fax
`) 678 S 99
`(6
`
`,5.
`__
`E 2
`A E
`A E kg? 25'
`Date ofDeposit:
`I hereby cenify under 37 CFR 1.1m tthis ca” upondence is being deposited
`with the United States Postal Service as xprm Mail Post OITIce To
`Addressee w
`Ificicnt postage on the flu:
`ridiculed above and is addressed
`to the Con
`nergfl‘altnluml
`rnd
`irks, Washington. DC 2023].
`'
`
`
`Christa
`er llnime
`
`DOCKET NO.
`
`06816/043001
`
`EXPRESS MAIL NO. EM122760575US
`
`ERICSSON EXHIBIT 1002
`
`

`

`
`
`-1-
`
`
`
`HYBRID CONCATENATED CODES AND ITERATIVE DECODING
`
`ORIGIN OF INVENTION
`
`The invention described herein was made in the performance 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 ofthe Invention
`
`This invention relates to error correcting codes.
`
`2.
`
`Description ofRelated Art
`
`10
`
`15
`
`20
`
`Turbo codes are binary error-correcting codes built fi'om the parallel concatenation of two
`
`recursive systematic convolutional 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 US. Patent Nos. 5,446,747 and 5,406,570.
`
`The reference and patents to Berrou describe a basic turbo code encbder architecture of
`
`the type shown in the block diagram in FIGURE 1. As described in Berrou '747, FIGURE
`
`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 (1. The codes implemented in coding
`modules 11 and 13 may be identical or different.
`
`
`
`

`

`
`
`-2-
`
`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. A codeword 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 YI 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 “necessary 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
`desiredin certain environments, including low-power, constrained-bandwidth uses, such
`as deep space communications and personal communication devices, and high-noise
`environments.
`
` 1O
`
`15
`
`
`
`

`

`
`
`3!till!E33$3427.5:It]?
`
`SUMMARY OF THE INVENTION
`
`improved turbo code apparatuses and
`The present invention encompasses several
`methods. In a first class ofturbo 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. A parallel 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
`
`subsequent encoders. Each of the encoders outputs a turbo code element. In addition, the
`original data source dis 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 interleaver 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 ofthe turbo code engoder 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.
`
`10
`
`15
`
`20
`
`25
`
`
`
`

`

`
`
`
`
`-4-
`
`The invention also encompasses a novel method of terminating 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
`
`FIGURE 1 is a block diagram of a prior art turbo code encoder.
`
` 10
`
`FIGURE 2 is a block diagram of a general model of a turbo code encoder having three
`codes.
`
`FIGURE 3 is a matrix of a weight-4 sequence.
`
`FIGURE 4 is a block diagram of an input trellis termination method for turbo code
`
`encoders in accordance with the present invention.
`
`\.
`
`15
`
`FIGURE 5 is a block diagram of a turbo encoder showing output only of encoded parity
`elements.
`
`FIGURE 6A is a block diagram of a third embodiment of the present invention, showing
`output of multiple encoded elements derived from multiple input data sources, the use of
`
`multiple interleavers on at least one data source, and an optional multilevel trellis-coded
`modulator.
`
`20
`
`FIGURE 6B is a block diagram of a variation of the coder shown in FIGURE 6A,
`showing a self-concatenating code.
`
`
`
`

`

`
`
`-5-
`
`FIGURE 6B2 is a block diagram showing a variation of a self-concatenated code, where
`
`the encoder has at least one input data line d, and d is sent to the modulator.
`
`FIGURE 6C is a block diagram of a fourth embodiment ofthe present invention, showing
`
`output of multiple encoded elements derived from multiple input data sources, the use of
`
`multiple interleavers on at least one data source, and an optional multilevel trellis-coded
`modulator.
`
`FIGURE 7A is a block diagram of a serial encoder in accordance with the present
`invention.
`
`10
`
`FIGURE 7B is a block diagram of a parallel-serial encoder in accordance with the present
`invention.
`
`FIGURE 7C is a block diagram of a serial-parallel hybrid encoder in accordance with the
`present invention.
`
`FIGURE 8 is a diagram showing the performance of various turbo codes.
`
`15
`
`FIGURE 9 is a block diagram of a first rate 1/2 turbo coder in accordance with the present
`'\.
`invention.
`
`FIGURE 10 is a block diagram of a second rate 1/2 turbo coder in accordance with the
`
`present invention.
`
`FIGURE 11 is a block diagram of a rate 1/3 turbo coder in accordance with the present
`invention.
`
`20
`
`FIGURE 12 is a block diagram of a rate 1/4 turbo coder in accordance with the present
`invention.
`
`
`
`

`

`
`
`-6-
`
`
`
`FIGURE 13 is a diagram showing the performance of various rate 1/4 turbo codes.
`
`FIGURE 14 is a diagram showing the performance of various turbo codes with short
`block sizes.
`
`FIGURE 15 is a diagram showing the performance of various three code turbo codes.
`
`5
`
`FIGURE 16 is a block diagram of a prior art decoder structure.
`
`FIGURE 17 is a block diagram of a parallel decoder structure in accordance with the
`present invention.
`
`FIGURE 18 is a block diagram of a channel model.
`
`FIGURE 19 is a signal flow graph for extrinsic information in a decoder.
`
`10
`
`FIGURE 20A is a block diagram of a single parallel block decoder in accordance with the
`present invention.
`
`FIGURE 20B is a block diagram showing a multiple turbo code decoder fona three code
`system, using three blocks similar to the decoder in FIGURE 20A.
`
`FIGURE 20C is a block diagram showing a multiple turbo code decoder for a three code
`
`15
`
`system, using three blocks similar to the decoder in FIGURE 20A, and having a
`switchable serial decoder mode.
`
`FIGURE 20D is a block diagram showing a decoder corresponding to the self-concatenat-
`ing coder of FIGURE 6B.
`
`

`

`-7.
`
`FIGURE 20D2 is a block diagram showing a decoder corresponding to the self-concaten-
`ated coder of FIGURE 6B2.
`
`FIGURE 20E is a block diagram showing a decoder corresponding to the serial coder of
`FIGURE 7A.
`
`FIGURE 20E2 shows a block diagram of an original and a modified MAP algorithm.
`
`FIGURE 20F is a block diagram showing a decoder corresponding to the serial coder of
`FIGURE 7B.
`
`FIGURE 20G is a block diagram showing a decoder corresponding to the hybrid
`
`concatenated code (serial-parallel, type II) of FIGURE 7C.
`
`FIGURE 21 is a block diagram of a 16 QAM turbo trellis-coded modulation coder in
`
`accordance with the present invention.
`
`FIGURE 22 is a diagram showing the BER performance of the coder shown in FIGURE
`21.
`
`FIGURE 23 is a block diagram of an 8 PSK turbo trellis-coded modulation}! coder in
`
`accordance with the present invention.
`
`FIGURE 24 is a diagram showing the BER performance of the coder shown in FIGURE
`23.
`
`FIGURE 25 is a block diagram of a 64 QAM turbo trellis—coded modulation coder in
`
`accordance with the present invention.
`
`
`
`10
`
`15
`
`

`

`
`
`.3-
`
`FIGURE 26 is a diagram showing the BER performance of the coder shown in FIGURE
`25.
`
`FIGURE 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
`modulator.
`
`FIGURE 28 is a block diagram showing a general decoder for the TCM encoded output
`of, for example, FIGURES 21, 23, and 25.
`
`Like reference numbers and designations in the various drawings indicate like elements.
`
` I”:5:=3:
`
`sf“-
`i=5T
`
`

`

`"ll“.9-
`i5.
`:1
`I11.
`
`till#1:.iiiFiil
`
`w...“
`
`"'Hill
`1.]"''3-
`
`r
`
`mill
`15.31:“-
`[1"
`
`-9-
`
`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:
`
`C=EJND +1
`
`(1)
`
`where n is the processing gain and Eb/Na is the required signal-to-noise ratio to achieve
`a desired bit error rate (BER) performance (Eb: energy received per useful bit; No:
`monolateral spectral density of noise). For a specified BER, a smaller required E/N,
`implies a larger capacity or cell size. Unfortunately, to reduce E,/N0, 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.511. However, iftwo
`(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.811 (with l92-bits and 256-bits interleavers, which correspond to
`9.6 Kbps and 13 Kbps with roughly 20ms frames). Higher capacity can be obtained with
`
`

`

`
`
`-10-
`
`larger interleavers. 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 fimctions 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).
`
`As another example, the invention may be implemented in computer programs executing
`on programmable computers 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 programs
`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 computer 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 computer.
`
` 10
`
`15
`
`20
`
`25
`
`

`

`
`
`Turbo Code Encoders
`
`Following is a discussion of several general considerations in designing turbo code
`encoders and decoders in accordance with the present invention. 'Since these consider-
`ations pertain to the novel designs described below as well as prior art designs in some
`cases, a simple 3-code encoder, as shown in FIGURE 2, will be used as an initial
`example.
`
`
`
`10
`
`15
`
`20
`
`25
`
`General Structure ofan Encoder
`
`In FIGURE 2, the turbo code encoder contains three recursive binary convolutional
`
`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 = (ul,
`, u”) of
`length N is applied to the component Encoder 1 through interleaver n1 (normally set to the
`identify fimction), which outputs a sequence 11,. The component Encoder 1 produces two
`output sequences, x1, and X”, (the subscript 1' stands for “information” bits, while the
`subscript p stands for “parity” bits). The component Encoder 2 operates on a reordered
`sequence ofinformation bits, u2, produced by an interleaver (also known as a permuter),
`11:2, of length N, and outputs the sequence X». The component Encoder 3 operates on a
`reordered sequence ofinformation bits, us, produced by an interleaver, 7g, of length N, and
`outputs the sequence X». Similarly, subsequent component encoders operate on a
`reordered sequence of information bits, uj , produced by interleaver 7cj
`, and output the
`sequence ij.
`
`In the preferred embodiment, each interleaver is a pseudo-random block scrambler
`defined by a permutation ofN 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 x1,-
`and xJ-p as received sequences y,. 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
`
`
`
`

`

`-12-
`
`been corrupted by noise. In the present invention, the encoder does not need to transmit
`the original data sequence. If one or more encoder outputs, including possibly x“, is
`punctured (not transmitted) based on a predetermined pattern, the punctured positions will
`be filled with erasures at the receiver.
`
`FIGURE 2 shows an example where a rate r = l/n = 1/4 code is generated by three
`component codes with M, = M) = M3 = M = 2, producing the outputs:
`x“ = u
`
`X”, = u ' gl/g.
`
`xzp = “2 'gA/ga
`
`Xsp = u3 'gI/ga
`
`(1:1 is assumed to be an identity, i. e., no permutation), where the generator polynomials
`g0 and g, have octal representation (7)96“, and (5)06“, respectively. Note that various code
`rates can be obtained by proper puncturing of xlp, xzp, x3,” and even X], if a decoder in
`accordance with the present invention is used (see below).
`
`Design ofPreferred Constituent Encoders
`
`characteristics over the region of interest).
`
`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 published 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 g, is a
`primitive polynomial. This suggestion, used in the report cited above to obtain “good”
`rate ]/2 constituent codes, will be used in this article to obtain “good” rate 1/3, 2/3, 3/4,
`and 4/5 constituent codes. By “good” codes, we mean codes with a maximum effective
`free distance dzf, that is, those codes that maximize the minimum output weight for
`weight-2 input sequences (because this weight tends to dominate the performance
`
`

`

`
`
`
`
`-13-
`
`Maximizing the weight of output codewords corresponding to weight-2 data sequences
`gives the best BER performance 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:
`
`Pb = i Q 2r_b(f (115a)
`
`(2)
`
`is the minimum parity-weight (weight due to parity checks only) of the
`where (13.5
`codewords at the output of thejth constituent code due to weight-2 data sequences, and
`[i is a constant independent of N. Define d],2 = “i5 + 2 as the minimum output weight
`including parity and information bits, ifthejth constituent code transmits the information
`(systematic) bits. Usually one constituent code transmits the information bits (i=1), and
`the information bits of other codes are punctured. Definedef= 8:1 dj’; + 2 as the
`effective free distance of the turbo code and l/N‘Tl as the “interleaver’s gain.” We have
`the following bound ondjs for any constituent code: for any r = b/(b+1) recursive
`systematic convolutional encoder with generator matrix:
`
`111(1))
`
`how)
`
`
`h2(D)
`
`G = [W h0(D)
`
`(3)
`
`
`MD)
`
`h()(D)
`
` 10
`
`15
`
`where IN is the identity matrix, deg[h,.(D) s m, h,(D) at h0(d), i= 1,2,...,b, and h0(D) is
`a primitive polynomial of degree m, the following upper bound holds:
`
`
`
`

`

`
`
`J+2
`
`(4)
`
`‘
`
`5
`
`10
`
`A corollary of this is that, for any r=b/n recursive systematic convolutional code with b
`
`inputs, b systematic outputs, and n-b parity output bits using a primitive feedback
`generator, we have:
`
`dfsioibgz—MJQM—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 l/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 1, where d2 =45 + 2. The
`'
`minimum-weight codewords corresponding to weight-3 data sequences are denoted by
`(1;, d,,,,,, is the minimum distance ofthe code, and k = m + 1 in all the tables. By “best” we
`mean only codes with a large d2 for a given m that result in a maximum eflective 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.
`
` :3fl
`LIB.
`g
`Mi
`ii";
`
`‘3'
`
`
`
`5 ‘
`
`3
`I}?
`:2
`3:?
`iii.
`
`

`

`-15-
`
`Table 1. Best rate 2/3 constituent codes.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`h0=13
`h,=15
`
`ho=13
`h,=15
`
`
`
`
`h0=23
`
`h,=35
`
`h2=33
`
`h0=23
`h,=35
`h2=27
`
`
`h2=21
`
`ho=23
`
`h,=35
`
`1O
`
`15
`
`

`

`-16-
`
`B. Best Punctured Rate 1/2 Constituent Codes
`
`A rate 2/3 constituent code can be derived by puncturing the parity bit of a rate 1/2
`recursive systematic convolutional code using, for example, a pattern P = [10]. A
`puncturing pattern P has zeros where parity bits are removed.
`
`Consider a rate 1/2 recursive systematic convolutional code (1 ,g,(D)/(g0(D)). For an input
`u(D), the parity output can be obtained as:
`
`D =
`J“ )
`
`“(0ng (D)
`giro)
`
`(6)
`
`We would like to puncture the output x(D) using, for example, the puncturing pattern
`P[10] (decimation by 2) and obtain the generator polynomials ho(D), h,(D), and hz(D) for
`the equivalent rate 2/3 code:
`
`G =
`
`
`h,(D)
`
`how)
`
`
`hzw)
`
`h0(D)
`
`(7)
`
`We note that any polynomialflD) = 2 (1,0 ’, a, E GF(2), can be written as: f(D) =f,(D2)
`+ Df2(D2), where f,(D2) corresponds to the even power terms of f(D), and Df2(D2)
`corresponds to the odd power terms off(D). Now, if we use this approach and apply it to
`u(D), gl(D), and go(D), then we can rewrite the equation for x(D) as:
`
`(“1(1) 2) +Du2(D 2))(g1 [(0 2)+D812(D 2)?
` xl(D 2) +Dx2 D2):
`801(1) 2) +Dg02(D 2)
`
`(3)
`
`
`
` E -
`
`__‘-
`4’?
`i=4:
`
`, '
`
`"e—E
`
`10
`
`

`

`-17-
`
`where xl(D) and x2(D) correspond to the punctured output x(D) using puncturing patterns
`
`P[l 0] and P[01], respectively. If we multiply both sides of the above equation by (go,(Dz)
`
`+ Dgoz(D2) and equate the even and the odd power terms, we obtain two equations in two
`
`unknowns, namely xl(D) and xz(D). For example, solving for xl(D), we obtain:
`
`
`MD) +
`MD)
`_
`MD) — 141(0) ho(D)
`u2(D) ho(D)
`
`5
`
`where h0(D) = g0(D) and:
`
`h1(D) =g11(D)g01(D) + Dg12(D)g02(D)
`
`h2(0) =812(D)g01(D) + Dg1.(D)goz(D)
`
`(9)
`
`(10)
`
`(11)
`
`From the second equation above, it is clear that th = 0. A similar method can be used to
`
`show that for P[01] we get hm = 0. These imply that the conditions that hio=l and hm=l
`
`will be violated. Thus, we have the following theorem: if the parity puncturing pattern is
`
`10
`
`P = [10] or P = [01], then it is impossible to achieve the upper bound on d2 =djf; + 2 for
`rate 2/3 codes derived by puncturing rate 1/2 codes.
`
`The best rate 1/2 constituent codes with puncturing pattern P = [10] that achieve the
`
`largest d1 are given in Table 4.
`
` 5:_==.
`t:E1:531i175i=3;i"'
`
`m a
`
`
`
`

`

`
`
`.18-
`
`Table 4. Best rate 1/2 punctured constituent codes.
`
`
`
`
`
`
`
`
`
`
`C.
`
`Best Rate I/n Constituent Codes
`
`As known in the art, for rate I/n codes, the upper bound for b=l reduces to:
`
`c155 s (n—1)(2""1+2)
`
`(12)
`
`Based on this condition, we have obtained the best rate 1/3 and 1/4 codes without parity
`repetition, as shown in Tables 5 and 6, where a?2 =a}; + 2 represents the minimum output
`weight given by weight-2 data sequences. The best nonpunctured rate 1/2 constituent
`codes have been reported by S. Benedetto er al., supra.
`
`"1v
`
`fiflfiflflmmfififlfififlflh
`
`10
`
`15
`
`Table 5. Best rate 1/3 constituent codes.
`
`Code generator
`
`
`
`
`
`
`
`
`
`
`

`

`
`
`.19-
`
`Table 6. Best rate 1/4 constituent codes.
`
`
`Code generator
`
`
`
`
`
`
`
`
`
`
`
`10
`
`15
`
`20
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`General Interleaver Design Considerations
`
`In order to estimate the performance of a code, it is necessary to have information about
`
`its minimum distance, weight distribution, or actual code geometry, depending on the
`
`accuracy required for the bounds or approximations. The challenge is in finding the
`
`pairing of codewords from each individual encoder, induced by a particular set of
`
`interleavers. We have found that it is best to avoid joining low-weight codewords from
`
`one encoder with low-weight words fi'om the other encoders. In the example of FIGURE
`
`2, the component codes have minimum distances 5, 2, and 2. This will produce a worst-
`
`case minimum distance of 9 for the overall code. Note that this would be unavoidable if
`
`the encoders were not recursive since, in this case, the minimum weight word for all three
`
`encoders is generated by the input sequence 11 = (00. . .0000100. ..000) with a single “1”,
`
`which will appear again in the other encoders, for any choice of interleavers. This
`
`motivates the use of recursive encoders, where the key ingredient is the recursiveness and
`
`not the fact that the encoders are systematic. For this example; the input sequence u =
`
`(00...00100100...000) generates a low-weight codeword with weight 6 for the first
`
`encoder. If the interleavers do not “break” this input pattern, the resulting codeword’s
`
`weight will be 14. In general, weight-2 sequences with 2+3r zeros separating the 1’s
`
`would result in a total weight of 14 + 6t if there were no permutations. By contrast, if the
`
`number of zeros between the ones is not of this form,
`
`the encoded output
`
`is
`
`
`
`
`
`

`

`nonterminating until the end of the block, and its encoded weight is very large unless the
`sequence occurs near the end of the block.
`
`With permutations before the second and third encoders, a weight-2 sequence with its 1’s
`separated by 2 + 3!, zeros will be permuted into two other weight-2 sequences with 1’s
`separated by 2 + 3t, zeros, where i= 2, 3, and where each I, is defined as a multiple of 1/3.
`If any I, is not an integer, the corresponding encoded output will have a high weight
`because then the convolutional code output is nonterrninating (until the end ofthe block).
`Ifall t,’s are integers, the total encoded weight will be 14 + 22,1, 1,. Thus, one of the
`considerations in designing the interleaver is to avoid integer triplets (1,, 1,, 1,) that are
`simultaneously small in all three components. In fact, it would be nice to design an
`interleaver to guarantee that the smallest value oni, I, (for integer r,) grows with the
`block size N.
`
`For comparison, consider the same encoder structure in FIGURE 2, except with the roles
`of g, and g, reversed. Now the minimum distances of the three component codes are 5,
`3, and 3, producing an overall minimum distance of 11 for the total code without any
`permutations. This is apparently a better code, but it turns out to be inferior as a turbo
`code. This paradox is explained by again considering the critical weight-2 data sequences.
`For this code, weight-2 sequences with l + 2!, zeros separating the two 1’s produce self-
`terminating output and, hence, low-weight encoded words. In the turbo encoder, such
`sequences will be permuted to have separations l + 2t,, where i = 2, 3, for the second and
`third encoders, but each I, is now defined as a multiple of 1/2. Now the total encoded
`
`weight for integer triplets (1,, (2, 5) is 11 + 2 21, t,. Notice that this weight grows only
`half as fast with2?_, t, as the previously calculated weight for the original code. If
`,1,
`t, can be made to grow with block size by the proper choice of an interleaver, then
`clearly it is important to choose component codes that cause the overall weight to grow
`as fast as possible with the individual separations 1,. This consideration outweighs the
`criterion of selecting component codes that would produce the highest minimum distance
`if unpermuted.
`
`10
`
`15
`
`20
`
`25
`
` In:
`
`a,
`
`,
`
`1“:
`a
`
`r.’atu
`
`I5“
`ii.
`
`

`

`
`
`-21-
`
`
`
`There are also many weight-n, n = 3, 4, 5,
`
`.. ., data sequences that produce self-
`
`terminating output and, hence, low encoded weight. However, as argued below, these
`
`sequences are much more likely to be broken up by random interleavers than the weight-2
`
`sequences and are, therefore, likely to produce nonterrninating output from at least one
`
`of the encoders. Thus, turbo code structures that would have low minimum distances if
`
`unpermuted can still perform well if the low-weight codewords of the component codes
`
`are produced by input sequences with weight higher than two.
`
`10
`
`15
`
`20
`
`25
`
`We briefly examine the issue of whether one or more random interleavers can avoid
`
`matching small separations between the 1’s of a weight-2 data sequence with equally
`
`small separations between the 1’s of its permuted version(s). Consider for example a
`
`particular weight-2 data sequence (...001001000...) which corresponds to a low weight
`
`codeword in each of the encoders of FIGURE 2. If we randomly select an. interleaver of
`
`size N, the probability that this sequence will be permuted into another sequence of the
`
`same form is roughly 2/N (assuming thatN is large, and ignoring minor edge effects). The
`
`probability that such an unfortunate pairing happens for at least one possible position of
`
`the original sequence within the block size of N, is approximately 1 - (l - 2/N)” 5* l -
`e‘z. This implies that the minimum distance of a two-code turbo code constructed with a
`
`random permutation is not likely to be much higher than the encoded weight of such an
`
`unpermuted weight-2 data sequence, e.g., 14 for the code in FIGURE 2. (For the worst
`
`case permutations, the d ofthe code is still 9, but these permutations are highly unlikely
`
`if chosen randomly). By contrast, if we use three codes and two different interleavers, the
`
`probability that the particular sequence above will be reproduced by both interleavers is
`
`only (2/N)2. Now the probability of finding such an unfortunate data sequence somewhere
`
`within the block of size N is roughly 1 — [l - (2/N)2]"' = 4/N. Thus it is probable that a
`
`three-code turbo code using two random interleavers will see an increase in its minimum
`
`distance beyond the encoded weight of an unpermuted weight-2 data sequence. This
`
`argument can be extended to account for other weight-2 data sequences which may also
`
`produce low weight codewords, e.g. , (...00100(000)'1000. . .), for the code in FIGURE 2.
`
`

`

`
`
`
`
`-22-
`
`For comparison, consider a weight-3 data sequence such as (... 0011100. ), which for
`our example corresponds to the minimum distance ofthe code (using no permutations).
`The probability that this sequence is reproduced with one random interleaver1s roughly
`6/N2, and the probability that some sequence of that form15 paired with another of the
`same form is l - (1 — 6/N2)” ~ 6N. Thus, for large block sizes, bad weight-3 data
`sequences have a small probability of being matched with bad weight-3 permuted data
`sequences, even in a two-code system.
`
`For a turbo code using q codes and q-l random interleavers, this probability is even
`smaller,
`1 - [l - (6/N)‘i"]N = 6/N (WA/2)“. This implies that the minimum distance
`codeword of the turbo code in FIGURE 2 is more likely to result from a weight-2 data
`sequence ofthe form (. . .001001000. . .) than from the weight-3 sequence (...0011100...)
`that produces the minimum distance in the unperrnuted version ofthe same code. Higher
`weight sequences have an even smaller probability of reproducing themselves after being
`passed through a random interleaver.
`
`For a turbo code using q codes and q—l interleavers, the probability that a weight-n data
`sequence will be reproduced somewhere within the block by all q— 1 permutations is of
`the form 1 - [l — (B/N"")""]”, where B is a number that depends on the weight-n data
`sequence but does not increase with block size N. For large N, this probability is
`proportional to (UN )"4'""’ , which falls offrapidly with N, when n and q are greater than
`two. Furthermore, the symmetry of this expression