Annual Status Report

submitted to

NASA

Goddard Space Flight Center

Greenbelt, Maryland

Error Control Techniques for Satellite and Space Communications

Grant Number NAG5-557

June 1, 1985-May 31, 1987

Principal Investigator:

Daniel J. Costello, Jr.

Department of Electrical and Computer Engineering

University of Notre Dame

Notre Dame, IN 46556

'^

July, 1986

{NASA-CR- 177224) ERBOB

P OB SATELLITE AND SPACE

Annual Status Beport, \

1S87 (Notre Dame Univ.)

CCNIECL TECHNIQUES

CCMMUNICATION S

Jun. .1585 - 31. May

76 p HC A09/MF A01

CSCL 17B G3/32

N86-27517

Onclas

43306
Summary of Results

In this report, we analyze the performance of several high rate

convolutional inner code/RS outer code concatenated coding systems for

possible use in NASA's high speed digital satellite communication systems.

Three types of inner codes are considered:

1) Rate (n-l)/n, n>3, punctured convolutional codes which produce a

total effective information rate between 0.5 and 1 bits per unit

bandwidth. Punctured codes are decoded using the same decoding

trellis as NASA's standard rate 1/2 inner codes. However some parity

bits are deleted, resulting in a higher effective rate. This causes

some trellis branches to contain two bits (one information and one

parity), while other branches contain only one information bit, and

may cause problems in properly synchronizing the decoder.

2) High rate majority-logic decodable convolutional codes. These codes

also produce an effective information rate between 0.5 and 1 bits per

unit bandwidth, and the decoders are simple and capable of high speed

operation. However, performance falls far short of what can be

achieved with Viterbi decoding.

3) Bandwidth efficient trellis codes using MPSK modulation which achieve

effective information rates greater than 1 bit per unit bandwidth.

These codes can make use of soft decision Viterbi decoding to achieve

significant coding gains on bandlimited channels.

Two decoding schemes are considered. Scheme 1 is a concatenated coding

system without side information. The received sequence is first decoded by

the inner decoder using the conventional Viterbi algorithm. The outputs of

the inner decoder are then grouped into bytes, deinterleaved, and decoded by
an outer errors-only RS decoder. Our results indicate that coding gains from

5 to 8 dB can be achieved at decoded BER's of 10~6 to 10~9 with little or no

bandwidth expansion. For example, with a 64-state punctured inner code and an

overall code rate of 0.75, coding gains of 7.75 dB @ 10~9 and 5.05 dB @ 10"6

are achievable. With a 4-state bandwidth efficient inner code, 8-PSK

modulation, and an overall code rate of 1.0, coding gains of 7.15 dB @ 10~9,

and 5.05 dB @ 10"^ are achievable. This 4-state decoder is capable of high

speed operation.

Scheme 2 is a concatenated coding system with side information. The

received sequence is first decoded by the inner decoder with a modified

Viterbi algorithm. In this modified algorithm, "path metric" comparisons are

used to estimate the entire information sequence and "branch metric"

comparisons are used to provide side information on the estimated sequence.

This is done by erasing the estimated bits that are probably in error. The

outputs of the inner decoder are then grouped into bytes, deinterleaved, and

decoded by an outer errors-and-erasures RS decoder. If the erasure-correcting

capability of the outer code is exceeded, the block is erased. Our results

indicate that extremely low undetected bit error rates (BER's) can be achieved

with only moderate erasure probabilities at signal-to-noise ratios near 5dB

and with little or no bandwidth expansion. For example, undetected BER's as

low as 10~1^, with an erasure rate no more than 10"^, can be achieved with a

64-state punctured inner code with overall code rate 0.765 at an E D /N0 of 5.35

dB or with a 16-state bandwidth efficient inner code, 8-PSK modulation, and an

overall code rate 0.9 at an E^/Ng of 5.45 dB. The 16-state decoder would be a

factor of 4 faster than the 64-state decoder.
HIGH RATE CONCATENATED CODING SYSTEMS

Robert H. Deng

Daniel J. Costello, Jr.

Dept. of Elec. & Comp. Engr.

Univ. of Notre Dame

Notre Dame, IN 46556

Abstract

In this paper, we consider high rate concatenated coding systems with

trellis inner codes and Reed-Solomon (RS) outer codes for application in

satellite communication systems. Two types of inner codes are studied.

1) High rate punctured binary convolutional codes which result in overall

effective information rates between 1/2 and 1 bit per channel use;

2) Bandwidth efficient signal space trellis codes which can achieve

•

overall effective information rates greater than 1 bit per channel use.

Channel capacity calculations with and without side information are

carried out for the concatenated coding system. It is shown that, for

moderate values of constraint length, optimal performance is obtained by

choosing the inner code rate near inner channel cutoff rate.

Two concatenated coding schemes are investigated. In Scheme I, the inner

code is decoded with the Viterbi algorithm and the outer RS code performs

error-correction only (decoding without side information). In scheme II, the

inner code is decoded with a modified Viterbi algorithm which produces

reliability information along with the decoded output. In this algorithm,

path metrics are used to estimate the entire information sequence, while

branch metrics are used to provide the reliability information on the decoded

sequence. This information is used to erase unreliable bits in the decoded

1
output. An errors-and-erasures RS decoder is then used for the router code.

These two schemes are proposed for use on NASA satellite channels. Our

results indicate that high system reliability can be achieved with little or

no bandwidth expansion.
1. Introduction

Concatenated coding has long been used as a practical means of achieving

reliable communication over satellite channels [1,2,3]. One such system

consists of Viterbi decoding of an (n,l,m) convolutional inner code

concatenated with an outer Reed-Solomon (RS) code. The overall effective

information transmission rate of this system is less than 1/n, n _>_ 2, bits per

channel use [2,3], This system achieves increased power efficiency for

decreased bandwidth efficiency. With the ever-increasing demand for satellite

communication services, both available channel bandwidth and transmitter power

must be conserved. Thus, the search for bandwidth and power-efficient

modulation/coding systems has recently become a very active research area.

In this paper, we present a trellis code/RS code concatenated coding

system for use in high speed satellite communication systems. Two types of

trellis codes are considered:

1) High rate punctured binary convolutional codes with code rates

(n-l)/n, n >_ 3 [4,5].

2) Bandwidth efficient signal space trellis codes with effective code

rates of 1 or greater [6,7,8,9].

The advantage of using punctured codes is that decoding is simplified,

especially if the decoder must be capable of decoding rate 1/n and rate k/n

codes. With rate (n-l)/n, n >_ 3, punctured codes as inner codes, an overall

effective information rate greater than 1/2 but less 1 bit per channel use can

be achieved. The goal of using bandwidth efficient signal space trellis codes

as inner codes is to achieve overall effective information rates around 1 bit

per channel use. As we will see in the following sections, such a system can

provide a rather large coding gain at bit error rates (BER's) of 10~6 " 1Q~9

with no bandwidth expansion.
Fig. 1 shows the encoding-decoding block diagram of the concatenated

coding system. Encoding is performed in two stages. An information sequence

of Kb bits is divided into K bytes of b bits each, and each b-bit byte is

regarded as a symbol in GF(2^). These K bytes are used as the input to the RS

encoder. The output of this encoder is an N-byte codeword which is

byte-interleaved and then serially encoded by the trellis encoder. Decoding

is accomplished in the .reverse order. The output of the maximum-liklihood

(Viterbi) trellis decoder contains bursty errors. The main purpose of the

inner code is to shape the distribution of the errors on the inner channel,

rather than to correct errors, particularly when the inner code rate is around

the cutoff rate of the inner channel. When an RS outer code is used, this

shaping compresses the random errors on the inner channel into symbol errors

corresponding to the symbol size used by the outer code [10]. The use of

bandwidth efficient signal space trellis codes as inner codes has one

important feature: because of the bandwidth efficient property of the code, it

compensates for the bandwidth expansion introduced by the outer RS code, so

that the overall system suffers no bandwidth expansion.

The organization of the paper is as follows. In section II, the outer

channel is modeled as a block interference (81) channel [11]. We then

calculate the channel capacity of the outer channel both with and without side

information. This calculation shows that:

1) Concatenated code performance (in terms of outer channel capacity) is.

optimized at a certain inner code rate, denoted by RI°PC. The value of Ri°Pt

depends on the inner code constraint length, it increases as the constraint

length increases, and it approaches the inner channel capacity as the

constraint length goes to infinity. For moderate constraint lengths, Ri°Pt is

close to the inner channel cutoff rate.
2) For a given inner code constraint length, there exists a limit on"the

inner code rate, denoted by Rimax, beyond which coding becomes useless (the

outer channel capacity goes to zero).

3) As the inner code rate increases from RIOP

C to Rimax, system

performance (outer channel capacity) degrades rapidly. This helps explain the

steep BER curves of concatenated codes.

In sections III - V we study two concatenated coding schemes. Scheme I,

a Viterbi decoded trellis inner code/RS outer code system, where the Viterbi

decoder outputs (without side information) are provided to the outer decoder,

is studied in section III. A modified Viterbi decoding algorithm for trellis

codes with output reliability information is presented in section IV. Scheme

II, a concatenated coding system with side information available to the outer

decoder, is then studied in section V. In the modified algorithm, path

metrics are used to estimate the entire information sequence, and branch

..metrics are used to provide reliability information on the decoded sequence.

This is done by erasing a certain number of bits on the survivor of a

comparison between the two most likely paths whose metrics are within some

preset threshold of each other. Finally, in section VI, we summarize our

results and draw some conclusions which are useful in the design of

concatenated coding systems.
IT. Channel Capacity Calculations --------- . - - ---- - ----- ----------- - ------- - -

We assume the inner channel to be a discrete memory less channel (DMC).

After decoding the inner code, however, the outer channel (the channel seen by

the outer decoder) is no longer a memoryless channel. It has been transformed

into a nonunifortn or time varying channel by the inner decoder. In this

section, we will consider the outer channel formed by the byte interleaver,

inner encoder, inner channel, inner decoder, and byte deinter leaver, as shown

in Fig. 1. We assume that an (n,k,m) convolutional code is used as the inner

code. We first show that this outer channel can be model as a BI channel

[11]. It has been argued that channel capacity is the best measure of system

performance, whereas cutoff rate is an inverse measure of decoding delay [11].

This observation is further supported by noting (from (3.7) and (4.17) in [11])

that channel capacity is additive while cutoff rate is not for BI channels

with side information. Therefore, to assess concatenated code performance,

we will calculate the channel capacity of the outer channel.

It has been shown that [12], for any DMC, there exists an (n,k,m)

time-varying convolutional code for which the probability of an event error of

length j + m branches with maximum-likelihood decoding is upper bounded by

for 0 _< RI < GI, 0 £ p _< 1, j = 1,2,..., (1)

where R^= k/n is the inner code rate, C\ is the inner channel capacity, and

y x
- ---- Since in -a j + m-branch- error -event the last m k^bit information tuples

must be correct for the incorrect path to remerge with the correct path, the

a

A

error burst is confined to the first m(j) = jk bits of the error event. When

a code with symbols over GF(2^),b _>. 2, is used as the outer code, a j+m-branch

A

error event can cause up to t(j) = fm(j)/bl + 1 symbol errors, where [xl

denotes the integer greater than or equal to x. Hence, the symbol error

probability in the outer channel can be upper bounded by

Z

Pj

Z ( ~ + 2)

j-J

 b

for 0 £ RI < GI, 0 _< p _< 1, (3)

A

where J, 1<J<°°, is arbitrary and v = mk is the encoding constraint length*.

Let the second term on the right hand side of (3) be denoted by Q(^, p).

Then

{£ — 2kP^ J~l >2-k( j-DEQ^, p)/Ri

j=J

 b

+ Z 2-2kp(j-l)o-k(j-l)E (q,p)/R }

j=J * u _ i

= (2k-l)P2-(v+k)E0(q^,p)/R1 { Ji J jzj-l+2 Z zJ-1}, (4)

b j=J j-J

where z » 2kP2~kEo\l'p^

R

l-

 To obtain a closed form expression for

*Por simplicity, we assume that each encoder shift register

has full length m.
p), note that

j-J 1-z

and by taking the derivative of both sides we obtain

d « . d ZJ ZJ

— ( S ,3) =r (f— =77-7-2

dz j=j dz 1-z (1-z) 1-z

After some manipulation, (4) can now be rewritten as

0 IC.T Wz*"l k w

Q(_a,p) = (2k-l) {( — +2)- + - ~ }, Oj< p E0(^,P)/R1 <. 1,

b 1-z b (i-z)2

(5)

where w =

Substituting (5) into (3) and minimizing Ps(^., p) over a^ and p, we obtain the

following closed form expression for the symbol error probability:

min i I

q j-i

0

 R < Ci. (6)

Due to the interleaving, symbol errors in the outer channel are

statistically independent, and hence the outer channel is equivalent to a BI

channel with two memoryless BSC's, as shown in Fig. 2. Channel AQ is a noise-
"less BSC, and"~b~i~/2t~ assuming "the worst case, is a useless BSC with "crossover

probability 1/2. A sequence of b consecutive bits is sent over AQ with

probability Pr{Ao) = 1 - P8 and over Aj/2 with probability Pr{Ai/2} = Ps.

The outer channel capacity with and without side information is given by

[11]

C2 = 1 - Ps (7)

and

C2 = (1-p) - - {H(p) + p Iog2 (l-2-b)}, (8)

b

A

respectively, where p = Ps(l-2~b) and H(p) is the binary entropy function.

Then the overall channel capacity of the concatenated coding system is

C = C2 • RI (with side information) (9)

and

C = C2 ' RI. (without side information) (10)

Note that the capacity without side information approaches the capacity

with side information as b increases, but the rate of convergence is slow

(o(l/b) convergence). Also, from (6) we see that Pg is a decreasing function

of b; therefore, both C and C increase as b increases.

To obtain some numerical results, assume the inner channel is a BSC with

crossover probability e =0.1. Fig. 3 shows the overall channel capacity of

the concatenated coding system, normalized by the inner channel capacity GI,

for k=3 and b=8, with v as a parameter. For fixed v, there is an optimum

value of RI/CI that maximizes the overall capacity. We denote the corresponding inner code rate by Rjopt (R^opt). Note that the optimum inner code rate

does not occur at the value of RI which presents the best (least noisy)
channel.-to the. outer, decoder. .Instead, .there is-a local, .maximum for .each—

value of v that drifts towards the higher rates as v increases. This is

reasonable since the system performance should improve for increasing

contraint length. For moderate values of v, RjOptCRiOpt) is close to the

inner channel cutoff rate. In addition, for a fixed v, there is a limit on

R]_, denoted by Rjmax (Rimax), beyond which the overall capacity goes to zero

(for v=3, 1*imax=0.60Ci and Rimax=0.58Ci). Therefore, the inner code rate is

constrained between 0 and Ilimax(Rimax). In fact, in a concatenated coding

system, the inner code rate often lies between Rj^P^Riopt) and Rjmax

(j^max). The rapid increase in overall capacity as Rj goes from Rimax(Rimax)

to ^°Pt(Ri°Pt) corresponds to the sharp decrease in BER with increasing

i

signal power (and hence C}) in well designed concatenated coding systems.

III. Coding Scheme I - Without Side Information

A concatenated coding system is depicted in Fig. 1. Decoding is

accomplished in the reverse order of encoding. The inner decoder uses the

Viterbi algorithm. The outputs of the inner decoder (without side

information) are grouped into b-bit symbols. Because the lengths of the

bursts of output errors made by the Viterbi decoder are widely distributed,

b-bit symbol deinterleaving is used so that errors in the individual

RS-symbols of one block (N symbols) are independent; otherwise, a very long

block code would be required to operate the system efficiently.

Let the minimum distance of the (N,K) RS code be d2. When an N-symbol

block is received by the outer decoder, it performs errors - only decoding.

id2~l i

That is, if the N-symbol block contains t2 = H or fewer errors, the errors

10
are corrected; otherwise, decoding fails. t2 is called the er ror-corr ec t ing

capability of the (N,K) RS code [13]. The decoded bit error rate at the

output of outer decoder can be closely approximated by

Pb = — z * (p )i (i-p )N-i (11)

2N

 1

where Ps is the symbol error probability into the outer decoder.

In this section, we give several examples of the Scheme I concatenated

coding system. For each example, we use RS codes with symbols over GF(2^)

and N=255. The symbol error probability Ps is obtained by computer simulation

on an AWGN channel unless otherwise noted, and (11) is used to estimate the

final decoded BER.

A. Examples with inner punctured codes

Example 3.1:

The best punctured rate RI = 3/4, 5/6, and 7/8 codes that are formed from

the basic (2,1,6) convolutional code [5] are used as inner codes. Decoding is

by the Viterbi algorithm with 3-bit quantization. The decoded BER Pfc vs.

EJ,/NQ is shown in Figs. 4.1 - 4.3 for 3 different RS code minimum distances.

Fig. 4.4 shows the E^/No required to achieve- decoded BERs of 10~6 and 10~9 as

a function of the overall code rate R. Note that, for the given decoded BERs

and a given R, lower inner code rates gives better performance. From Fig.

4.4, we see that the best performance is obtained at R = 0.65 for RI = 3/4,

and at R = 0.73 for RI = 5/6 and 7/8. These curves indicate the existence of

an optimum outer code rate, i.e., the outer code rate which minimizes the

required EI,/NO to achieve a given decoded BER for a fixed inner code rate.

11
Fig. 4.5 shows system performance for the case RI = 3/4, R = 0.656, and d2 =

33 vs. RI/ROI- As RI/RQI goes to 1 (the channel becomes noisier), system

performance degrades rapidly. This corresponds to the rapid decrease in overall capacity with increasing Rj illustrated in Fig. 3.

B. Examples with inner bandwidth efficient trellis codes

The goal of using bandwidth efficient trellis codes as inner codes is to

achieve a moderate coding gain with no bandwidth expansion. Currently, QPSK

is the prevalent modulation scheme in use for digital satellite communications. To improve power efficiency, error-correcting codes have been

employed. Because extra bits must be added to'the information sequence to

perform the error correction, the modulator must operate at a higher rate,

thus requiring a larger bandwidth. On the other hand, if bandwidth is limited

and the modulator must operate at the same rate as in the uncoded case, the

information transmission rate is lowered. To improve power efficiency and

maintain a high rate of information transmission without bandwidth expansion,

coded modulation, or bandwidth efficient coding, in which trellis codes are

combined with an expanded set of modulation signals (typically 8-PSK or

16-PSK), provides an exciting alternative.

In our concatenated coding system, bandwidth efficient inner trellis

codes have two functions:

1) To compensate for the bandwidth expansion introduced by the outer RS

code;

2) To compress the random errors on the inner channel into symbol errors

which can be corrected by byte-error-correcting codes, such as RS codes.

This concatenated coding scheme performs well on channels which are both power

and bandwidth limited, as shown in the following examples.

12
Example 3.2

Periodically time-varying trellis codes (PTVTC) of rate RI = (2P + i)/3P,

P > 2, 1 < i < P, are used as inner codes with 8-PSK modulation [7]. These

codes are especially designed for high data rate channels with low decoding

complexity. This PTVTC/8-PSK system has an effective information rate

(1) 3 (2P + i)

Reff s — RI = > 1 bits/channel use, so it is possible to

achieve an overall effective information rate Reff equal to 1 bit/channel use

or greater. Moreover, because of the periodic property of the code, its

trellis structure is the same as the trellis structure of a lower-rate code,

and as a result the complexity of the decoder is reduced significantly [7].

The PTVTC's are decoded by the Viterbi algorithm assuming no demodulator

output quantization. Figs. 5.1 - 5.3 show the decoded BER Pb vs. Eb/No for

concatenated codes with 4-state inner codes and 3 different RS outer codes;

Figs. 5.4 - 5.6 give similar results for 16-state inner codes. In Figs. 5.7 -

5.8 we show the required Eb/NQ to achieve decoded BERs 10"^ and 10~9 for

4-state and 16-state inner codes, respectively.

Note that at high effective code rates, e.g., Reff - 1 bit/channel use,

7

we still get large coding gains. For example, with a 16-state, R\ = ~ PTVTC,

the coding gain equals 3.92 dB at Pb = 10~6 and 6.18 dB at PJ, = 10~9. Even

7

for a 4-state, RI = — PTVTC, coding gains of 3.68 dB and 5.98 dB at Pb = 10~&

and Pb = 10~9, respectively, can be obtained. Only a small increment in

coding gain is achieved as the number of trellis states increases. As the

number of states goes from 4 to 16, only about 0.2 dB more gain is obtained.

This appears to be a characteristic of coded modulation in general [6]. We

will see this more clearly when we derive the asymptotic coding gain.

13
Example 3.3

Ungerboeck's 16-state, rate RI = 2/3 convolutional code with 8-PSK

modulation is used as the inner code. This code has an effective information

<!> rate Reff =. 1 bit/channel use. Therefore, the overall effective information

rate, Reff» °f the concatenated coding system is less than 1. Again, the

inner code is decoded by the Viterbi algorithm without demodulator output

quantization. The final decoded bit error probability P^ is shown in Fig. 6.1

for 2 different RS outer codes. Fig. 6.2 shows the required E^/NO to achieve

4

Pj, = 10~6 and 10~9. At Pfc = 10~6 and 10~9, coding gains of 4.96 dB and

7.25 dB can be obtained with only 12.5% bandwidth expansion.

Example 3.4

In this example, two kinds of trellis codes are used as inner codes.

The first kind uses 8-PSK modulation twice per trellis interval (forming a

64-ary set), and this set is then coded with a RI = 5/6 trellis code [8J.

Viewed more generally, code symbols are mapped onto a four-dimensional signal

set (8PSK x 8PSK) with 5 information bits for every two 8-PSK signals. Thus

(1) 5

the effective information rate is Reff =— = 1.25 bits/channel use. The

4

second kind uses rate R^ = 3/4 convolutional codes with 16-PSK modulation

(D 3 [9]. The effective information rate is Rpff = — =1.5 bits/channel use. ert

 4

This code is more bandwidth efficient than the RI = 5/6, 8-PSK code, but it is

less power efficient.

Let df, Es, and A be the normalized minimum Euclidean free distance, the

energy per modulation symbol, and the number of nonzero information bits in

the set of error events at distance df from the correct path, respectively.

Then at high signal-to-noise ratios, the bit error probability at the Viterbi

14
decoder output is approximated by

. A ^ |df2(5/2)EbR2 ,

 A

 nf |<*f2l .25EbR2

);

 =

 ~ QUl - - J = ~~ QW - J. (12.1)

 5 ^ 2N0 5 TM NO ^

n

e = ~ Q

5 1 2N0

for RI = 5/6 and 8-PSK,

and

A d fE

3

R

2 , A ^df(3E b ) R2 , A f df1. 5 EbR2 ,

e s ~ QU - J = - QU/- - - ) = - QU - - - ) (12.2)

3 1 2N0

 J 31 2N0 3 1 N0

for RI = 3/4 and 16-PSK,

where R2 is the outer RS code rate. The RS-symbol (over GF(2*5)) error probability at the output of the Viterbi decoder is bounded by

P3 <_ be. (13)

The final decoded bit error probability Pfc, obtained from (12.1), (12.2),

(13), and (11), is shown in Figs. 7.1 - 7.4, where we have chosen the outer RS

code rate R2 such that the overall effective information rate Reff

 = 1 bit/

channel use. Tables 1.1 and 1.2 list the coding gains at Pfc = 10"^ and 10~9

for the RI = 5/6, 8-PSK and R^ = 3/4, 16-PSK inner codes, respectively. In

both cases, the relatively poor performance of the 8-state and 16-state codes

compared to the 4-state codes is due to a large number of minimum free

distance paths.

Example 3.5

In this example, we use high-rate self orthogonal convolutional codes

with majority- logic decoding as inner codes. These codes have the advantage

of an extremely simple and fast inner decoder. Assuming the inner channel to

be a BSC with crossover probability p, the BER of the inner decoder output for

a self-orthogonal (n,k,m) convolutional code is bounded by

15
i °E /nE\ i , »°E ~ *•

_<- E ( )P (1-P) , (14)

k

 i=tMT+l

 i7

where

P - Q( ) , (15)

for BPSK or QPSK modulation on an AWGN channel, n^ is the effective constraint

length and tj^L is the majority-logic error correcting capability of the code

[13]. Using (14), (15), (13), and (11), the final decoded HER is shown in

Figs. 8.1 and 8.2 for rate RI = 3/4 and 4/5 self-orthogonal inner convolutional codes, respectively. Three different values of t^L are considered

in each case. Although these codes have implementation advantages, their

performance is clearly much worse than the punctured codes with Viterbi

decoding.

C. Asymptotic concatenated coding gain

Having studied the performance of concatenated coding systems for small

and medium values of ED/NQ, it is interesting to look at how the systems

perform at large values of E^/NQ - the asymptotic coding gain. This approach

also gives us some insight into concatenated coding system design.

We will use BPSK or QPSK as our reference system in the coding gain calculation. When uncoded BPSK or QPSK is used on an AWGN channel with coherent

demodulation, the demodulator output BER is given by

/2Eh 1 EK

p, _ Q(J—- ) = — e ~^t/^0 large _ (16)

1N0

 J

 ~ 2 ° NO

16
1) Asymptotic coding gain with punctured inner code3.

Let A be the number of nonzero information bits on all weight df paths

for an (n,k,ra) convolutional code. If BPSK or QPSK modulation is used, the

free Euclidean distance df normalized by Es, the symbol energy at the modulator output, is related to the free Hamming distance df(H) by

df2 = 4df(H), for BPSK, (17.1)

df2 = 2df(H), for QPSK. (17.2)

At high signal-to-noise ratios with either BPSK or QPSK modulation, an

asymptotically tight expression for the bit error probability at the output

of a Viterbi decoder without demodulator output quantization is*

A r dfRE s ^ A ,2df(H)REb

_A df(H)REb

= 2k e

~

 N0 , (18)

where R = R].R2, R!

 = k/n is the inner convolutional code rate, and R2 = K/N

is the outer (N,K) RS code rate with symbols over GF(2b). From (18), (13),

and (11), the final decoded bit error probability Pfo of the concatenated

coding system can be approximated by

N \ P

 c:

tz+i/

 s

d2 . „ . t Ab ,

t2+1

 df(H)REb(t2+]J ^ Q9)

t2+lj Ps '2 - N ^2+1; 2k ' e NO

For QPSK modulation, Eg = 2E& since there are 2 bits transmitted per symbol.

17
Comparing (16) to (19), we see that for a fixed Eb/NQ, the (negative) exponent

with concatenated coding is larger by a factor of df(H)R(t2+l) than the

exponent without coding. Since the exponential terra dominates the error

probability expressions for large E^/NQ, we define the asymptotic coding gain

as

A

= 10 logio df(H)R(t2*l). (without demodulator output quantization)

(20.1)

If hard quantized demodulator outputs are used at the input of the Viterbi

decoder, it can be shown that

df(H)R(t2+l)

Y - 10 login • (with demodulator output quantization)

2 (20.2)

For RS codes, N - K = 2t2 and

N-K 2t2

= 1-R2 = —- . (21)

N N

Substituting (21) into (20.1) and (20.2), the asymptotic coding gain can be

rewritten as

/N(1-R2) \

Y = 10 Iog10 df(H)RiR2( :+ l)

/N(1-R2). \

= 10 logjQ df(H)RI + 10 logio

 R2\ + I) » (without quantization)

\

 2 /

d2(H)R! /N(1-R2) \

Y = 10 logio +10 logio

 R2l +l)> (with quantization)

2 \ 2 /

(22.1)

and

N(1-R2)

+1J, {.with quantization;

(22.2)

where the first term is due to the inner convolutional code and the second

terra depends on the RS outer code. This implies that, for very large E^/NO,

the inner and the outer codes in a concatenated coding system can be designed

18
independently of each other.

Taking derivatives of Y with respect to R2, the maximum coding gain is

achieved at R2 = — + — for a fixed inner code, and

Y =10 logio df(H)Ri + 10 logio — ( — + 1 + ~ ) (without quantization)

max 2\4 N/ (23.1)

and

df(H)Rj 1 / N 1 \

Y =10 logio ~~* + 10 logio — I — + 1 + — I . (with quantization)

max 2 2 \ 4 N / f-j-i o)

Fig. 9 shows the asymptotic coding gain without demodulator output quantization, where we use Rj = (n-l)/n, n > 3, punctured convolutional codes formed

from the (2,1,6) convolutional code as inner codes and an RS code with N = 255

and symbols over GF(2°) as the outer code. Note that, at high overall code

rates, higher inner code rates outperform lower inner code rates, which is in

contrast to the case when EJJ/NQ is small. The important fact is that system

performance is very sensitive when the outer code rate R2 is high. A small

increase in R2 results in a large system performance degradation. This is

also true for small values of E^/NO, as shown in Figures 4.1 - 4.3.

2) Asymptotic coding gain with bandwidth efficient inner codes

Bandwidth efficient codes have been proposed and extensively investigated

for high data rate transmission over voiceband telephone channels and

band-limited satellite channels with power constraints. Although most of the

previous studies on coded modulation for satellite channels have been focused

on constant carrier envelope signaling formats such as 8-PSK and 16-PSK

modulation, applications of coded amplitude modulation to high speed satellite

communication have also been investigated. However, since constant envelope

19
signals mitigate the non-linear effects of TWT amplifiers and have relatively

simple high speed modem implementations, coded MPSK modulation is the

preferred modulation scheme for satellite channels. Hence, in the following

asymptotic coding gain derivation, we assume that the code is formed from a

rate RI = k/n convolutional code in combination with 2^-ary PSK modulation,

L > 2.

Let-£3. .be the symbol energy at the modulator output, df be the Euclidean

distance normalized by Eg, and A be the number of nonzero information bits in

the set of paths at distance df from the correct path. Then

Eg = R2RiLEb, (24)

and the bit error probability at the output of a Viterbi decoder without

demodulator output quantization is

e = AQ(

gA df2R2RlLEb (25)

2 4N0

where RjL is the average number of information bits in each modulator output

symbol. Using (25) and following a similar procedure as in the punctured

inner code case, we can show that the asymptotic coding gain is given by

df

2LRiR2(t2 + 1)

Y = 10 Iog10

9 (1) / •> df

 2ReffR

2(c2 * D df

 Reff(c2 * D

= 10 Iog10 ; = 10 logio ; , (26)

where

L

Reff = — RI bits/channel use (27)

20
is the effective inner code information rate, and

(1)

Reff = Reff R2 bits/channel use (28)

is the overall effective information rate of the concatenated coding system.

If an RS code of length N is used as the outer code, by substituting (21)

into (26) it follows that

df2Reff Y = 10 logio —:—

df2Reff /N(1-R2) \ , x

= 10 logio ~ + 10 logio

 R2 I — +1) » <29>

and for a fixed inner code, the maximum coding gain is

t (1)

- 10 io

 df Reff + l/£ + +-\ • -1 + 1

0810 2 * 10 1081° 2 \4 + l + NJ ' Wlth R2

 ~ 2 + N '(3())

Note that in (29) the first term denotes the coding gain due to the bandwidth

efficient inner code and the second term represents the coding gain

contributed by the outer code; therefore, for very large Eb/NQ, the inner and

outer codes can be designed independently in a concatenated coding system.

Fig. 10 shows the asymptotic concatenated coding gain Y for Example 3.2, Fig.

11 shows Y for Example 3.3, Fig. 12.1 shows Y for Example 3.4 when RI = 5/6

coded 8 PSK is used as the inner code, and Fig. 12.2 shows Y for Example 3.4

when RI= 3/4 coded 16PSK is used as the inner code.

Before finishing this section, we can draw a number of conclusions from

the above discussion:

(1)

1) For a given overall Reff» there exists an Reff which optimizes system

(1)

performance; or conversely, for a given Reff, there exists an optimum

value of Reff.

2) System performance is very sensitive to R2 at very low and very high

values of R2.

21
3) For small or moderate values of Efe/NQ, and for a fixed Reff, a lower

(1)

Reff is preferred as long as the outer code rate R2 is not too high.

4) Because df increases slowly as the number of trellis states increases,

choosing inner codes with a small number of trellis states increases the

data transmission rate (by reducing the number of decoder computations)

with only a slight sacrifice in system performance.

IV. A Modified Viterbi Algorithm

In section II, we have shown that the overall channel capacity of a

concatenated coding system with side information is an upper bound on the

capacity without side information. The difference between the two capacities

is significant, especially on noisy channels, when the inner code rate is in

the region from Ri°Pt to Rimax. We also pointed out in section II that in a

concatenated coding system [R^Pt, Rimax] is the practically interesting

region for the inner code rate RI . Therefore, it is advantageous if the inner

decoder can provide some kind of reliability information (side information)

about its estimated output which will aid the outer decoder. In scheme I,

discussed in section III, the inner code is decoded by the Viterbi algorithm

and the output of the decoder is a sequence of "hard decisioned" binary

digits, i.e., no side information is associated with the output. To provide

side information, it becomes necessary to modify the conventional Viterbi

algorithm so that soft decisioned outputs are made available to the outer

decoder.

Several ideas have been proposed to provide some kind of side information

with the convolutional decoder outputs. Zeoli [14] proposed a concatenated

coding system that employs a long constraint length (m = 31) convolutional

code obtained by annexing a tail to a (3,1,7) convolutional code. The

22
longer code is then decoded by the same Viterbi decoder as the short code,

with the exception that the information sequence along the best path to each

state is treated as correct and used to "cancel" the effect of the longer tail

from the encoded sequence. The tail provides excellent error-detection

capability once the decoder starts to make mistakes. But the algorithm is

subject to very serious error propagation and the decoder has to be reset

frequently.

Another method of providing reliability information with the decoder

output is to compute the a posteriori probability of each decoded symbol from

the decoder being correct [3]. However, the a posteriori probability must be

computed for each branch using a recursive method and real numbers must also

be stored. This computation process slows down the decoder, so it is not

suitable for high speed systems.

A third alternative is to use the "Viterbi decoding algorithm for

convolutional codes with repeat request" [15] to extract reliability information from the inner decoder. When all the path metrics at some level of the

trellis are below a predetermined threshold, the received sequence up to that

level is erased (instead of being retransmitted). But this approach has two

major drawbacks: 1) when a long received sequence is erased, this erasure

information cannot be used by the outer decoder because the number of erasures

may exceed the erasure correction capability of the outer code; 2) with high

probability, most of the symbols in the received sequence can be decoded

correctly and hence should not be erased.

In the following, we propose a decoding technique based on the Viterbi

algorithm. It erases only the information symbols that are "probably in

error", and this erasure procedure does not affect the decoder's selection of

the most likely path. Therefore, the decoder is still maximum-likelihood.

23
Furthermore, the algorithm is very simple to implement and capable of high

speed operation.

As the name suggests, an (n,k,m) trellis code is best described in terms

of its trellis diagram. In the decoding of trellis codes by the Viterbi

algorithm, a first-event error is made at an arbitrary level j if the, correct

path is eliminated for the first time at level j in favor of the incorrect

path. This is illustrated in Fig. 13. The incorrect path must be some path

that had previously diverged from the correct path. For the example shown in

Fig. 13, let

Vj = (...,Vj_3, Vj_2, Vj_i, Vj)

and

v'j = (..., v'j-a.v'j^, v'j-i, v'j)

represent the correct path and the incorrect path, respectively, where V^

(V i) is the symbol on the ith branch of the correct (incorrect) path, and let

!j = (V'j_3, v'j-2, V'j-i, V'j)

represent the 4-branch first-event error at level j. Also let

Uj = (..., Uj_3, Uj-2, Uj_i, Uj)

and

U.'j = (..., u'j-3, u'j-2, u'j-i, U'j)

represent the information sequences associated with paths V; and \f ;,

respectively, where U^ (U ^) is a binary k-tuple, and let

lj = (U'j-3, U'j_2, D'J-I. U*j)

represent the 4-branch information sequence corresponding to the 4-branch

first-event error Ej at level j. Denote a branch metric by X(Vi) and a path

metric by *(V_j). From Fig. 13 we observe that Ij is unreliable and should be

erased. This observation motivates us to propose the following decoding

algorithm.

24
Algorithm 1:

For each state at level j, select the path V; = (..., V ]-t+i,

i i i

V ;_£+2»'--i V j-1, V ;) (where i is chosen as the expected error event

length) that has the largest metric X(V j) and the path Vj = (..., Vj_£+j,

Vj_£+2t.••, Vj_i, Vj) that has the next largest metric X(Vj). Because

\£ j has the largest metric, V^ j survives at that state. Moreover, if

X(V_'j) > X(Vj) -i- T (T > 0), (31)

decoding continues as in the conventional Viterbi algorithm. On the other

hand, if

X(v'j) < X(Vj) + T, (32)

then ^j = (U j-i+i, U ;_£+2,..., U j-l» U ;) on the surviving path is

erased and decoding continues.

Note that if T = 0, the algorithm reduces to the conventional Viterbi

algorithm. As an illustration of the algorithm, in Fig. 13, for some state at

level j, suppose that X(V :) > X(Vj), so the incorrect path V_ j survives. If

XCv'j) < A(Vj) + T, (33)

then ^j = (U j_3, U j_2, U j_j, U j) is erased. Note that (33) is equivalent

to

\(v'j_3)+ X(v'j_2)+ X(v'j_i)+ X(v'j)< X(Vj_3)+ X(Vj_2)+ X(Vj_i)+ X(Vj)+ T.(34)

Eq. (34) implies that, if the metrics of the two 4-branch sequences are

"close" in terras of the threshold T, the corresponding information sequence I.;

is not reliable, and therefore a tag should be attached to it which indicates

its degree of reliability. The simplest way of doing this is to erase it.

From (34) we see that this erasure decision is made on the most recent i

branches for a A-branch error event, and hence it is a "local" estimate. On

the other hand, the path estimate is a "global" estimate. From this point of

view, we see that Algorithm 1 is constructed based on the following ideas.

25
1) By letting the path with the largest path metric survive, we are

choosing the maximum-likelihood estimate.

2) By performing a "branch comparison" over the most recent £ branches,

we provide some reliability information on the maximum-likelihood path.

Because the reliability is estimated over only I branches, the

reliability estimates are suboptimum. However, in feedback decoding of convolutional codes, decisions are made over only one constraint length. Hence

we can say that the reliability estimates have a certain degree of precision.

Ideally, the number of erased k-triples, £., should equal the length of the

error event. Practically, however, choosing £ equal to the average error

event length should be sufficient.

Algorithm 1 can be applied to any trellis code. If, however, the trellis

is generated by a finite-state machine, the algorithm can be improved. Let m

and k denote the memory order of the finite-state machine and the number of

input bits to the finite-state machine. Then trellis codes can be divided

into two cases .of practical interest:

1) If all k input bits are shifted into memory, there can be no parallel

transitions in the trellis. Since the last km information bits

associated with an error event of length £ branches must be correct for

the incorrect path to remerge with the correct path, decoding errors are

confined to the first t-m branches.

2) If fewer than k bits are shifted into memory and the remaining bits

are uncoded, there are parallel transitions between any two connected

states in the trellis, and all the information bits associated with an

error event may be in error.

26
In the case where parallel transitions are possible, we must use

algorithm 1. However, in decoding trellis codes without parallel transitions,

a modified algorithm can be used.

Algorithm 2.

For each state at level j (j=m+l,m+2,...) , select the path

_V j = (..., V j_£_+i, V j-£+2>--.,v j) (where I is chosen as the expected

error event length) that has the largest metric A(V_ j) and the path

V; = (..., Vj_£+j, Vj_£+2»•••»vj) that has the next largest metric X(Vj).

Because V^ j has the largest metric, V^ ; survives at that state. Then if

XOv'j) > A(Vj) •»- T ( T > 0), (35)

decoding continues as in the conventional Viterbi algorithm. On the other

hand, if

XCV*j) < A(Vj) + T, (36)

then the information symbols U j-i+i, U j_j+2,...,

 u j-m on the surviving path

are erased and decoding continues.

In both algorithms, smaller values of T result in lower erasure rates but

higher error rates, and larger values of T result in higher erasure rates but

lower error rates.

V. Coding Scheme II - With Side Information

The encoding process is the same as in Scheme I. Decoding is done in two

steps. First, the inner trellis code is decoded by the modified Viterbi

algorithm presented in the last section. The outputs of the inner decoder

consist of binary digits as well as erased bits, and they are grouped into

b-bit bytes, deinterleaved, and sent to the outer decoder. Bytes which

contain any erased bits are considered as erasures by the outer decoder.

27
Let i be the number of erased symbols in an RS outer codeword of length

N. The outer decoder declares an erasure (or raises a flag) for the entire

block of N bytes if i is greater than the erasure-correction threshold Tes,

where

Tes < <d2 ~ 1) (37)

and d2 is the minimum distance of the outer (N,K) RS code. If i is less than

Tes> the outer decoder starts errors-and-erasures decoding on the N-symbol

block, and the i symbol erasures along with the symbol errors are corrected

based on the outer code. Let t(i) be the error-correction threshold for a

given i, where

(38)

If the syndrome of the N-byte block corresponds to an error pattern of i

erasures and t(i) or fewer symbol errors, errors-and-erasures correction is

performed. The values of the erased symbols, and the values and the locations

of symbol errors, are determined based on a certain algorithm. However, if

more than t(i) symbol errors are detected, then the outer decoder again

declares an erasure (or raises a flag) for the entire N-symbol block.

Let Pg and Pe be the RS-symbol error probability and RS-symbol erasure

probability at the input of the outer decoder, respectively. The probability

of correct decoding of a block is given by

Tes /N\ . t(i)/N-i

c

 = E pe

L z 1

i=0 V i / j=o V j

p

s

j (1

 ~

 ps -

where Tes and t(i) are defined in (37) and (38). Let Pfce and P|,i denote the

probabilities of a block erasure and an incorrect decoding, respectively.

Then

PC * pbe

 + Pbi = 1, (40)

28
and

?bi = 1 - PC

Tes /N

i=0

N-i\ . N-i-j

Si(l-Pe-Pg)

N

+ E

/N\ .

MP.XI-:P)N-1 . (41)

The probability of incorrect decoding of a block is not easy to determine.

But it can be upper bounded by [16]

T N— i eg — i / N— i\

?bi < Z HPe1 ^ I PsKl-Ps-Pe)^1-^

i=0 V1/ j=d2-i-t(i)V J 7

(42)

and the final decoded BER of the concatenated coding system is approximated by

Pb = -^ Pbi- (43)

In the following we consider several examples for Scheme II. The outer

code is again an RS code of length N = 255. Inner trellis codes are decoded

by the modified Viterbi algorithm in section IV. We use B to denote the

number of erased branches in the modified Viterbi algorithm. The RS-symbol

error probability Ps and the RS-symbol erasure probability Pe at the input to

the outer decoder are determined by computer simulation. In decoding the

outer code, thresholds Tes and t, which are independent of the number of

erased symbols in an N-symbol block, are assumed, and (41) and (42) are

modified as

29
and

Tes /N\ . N-i /N-i\

Pbe + Pbi = E UjPe1 £ I j

i=0

 X ' j=min(t(i),t)+lV

N /N\

i=Teg-t-l

Tes /N\ . N-i /N-:

Pbil MijPei Z I j

i=0 j=d2-i-min(t(i),t)

where Tes < d2~l and t <|(d2-l)/2]. Usually, the probability of a block

erasure Pbe is much larger than the probability of block decoding error

Therefore, Pfce

 + Pbi is a tight bound on Pbe- *n the examples below we

compute the sum of the probability of a block erasure and of a block decoding

error, P^e

 + pbi» and the final decoded BER Pfo.

A. Examples with Punctured Inner Codes

Example 5.1:

The inner codes are the same as in Example 3.1. In decoding the inner

code, we use Algorithm 2. BPSK or QPSK modulation over an AWGN channel with

three bit uniform quantization is assumed. The bit metric is given by

m(l/l) = log p(l/l), I = 0,1,2,...,7, (46)

when I is received and 1 is transmitted. In the computer simulation, we use

nonnegative bit metrics by letting

m(l/l) = log p(l/l) - log p(0/l), I = 0,1,...7, (47.1)

and by symmetry,

m(l/0) = m((7-l)/l) , I =0,1,...,7. (47.2)

30
The branch erasure threshold T in Algorithm 2 is chosen to be

T = T'm(0/0), (48)

where T1 is a normalized threshold. Figs. 14.1 - 14.3 show the probabilities

P|j and P],e + P|,i as a function of t.

B. Examples with Bandwidth Efficient Inner Codes

In decoding the bandwidth efficient code we use Euclidean distance as the

decoding metric. The erasure threshold in the modified Viterbi algorithm is

chosen to be

T = (T'dfEb/N0)

2

, (49)

where df is the Euclidean free distance of the code normalized by the signal

energy at the demodulator output, and T1 is a normalized threshold.

Example 5.2:

As in Example 3.2, the PTVTCs of RI = (2P + i)/3P, P > 2 and

1 < i < P, with 8PSK modulation are used as inner codes. Only 16-state codes

are considered. Because of the parallel transitions in the trellis, algorithm

1 is used. PJ, and Pjje + ?bi» with RI = 7/9, 5/6, 8/9, are shown as functions

of t in Figs. 15.1, 15.2, and 15.3, respectively.

Example 5.3;

As in Example 3.3, Ungerboeck's RI = 2/3 coded 8PSK with 16 trellis

states is used as the inner code. Because there are no parallel transitions

in the code trellis, we use algorithm 2 in decoding the inner code. Pjj and

pbe + **bi are shown in Fig. 16 as a function of t.

From the above examples, we see that for a given E^/NO, the decoded BER

of Scheme II is significantly lower than that of Scheme I. Scheme II provides

us with flexibility in the system design. Tradeoffs between the decoded BER

31
and the probability of block erasure can be obtained by varying the error

correction threshold t of the outer code. Smaller values of t always result

in lower decoded BER's, but a higher probability of block erasure. In

practice, given a specified system performance, the values of t can be chosen

accordingly.

VI. Summary and Conclusions

In this paper we considered high rate concatenated coding systems with

trellis inner codes and RS outer codes for application to satellite communication systems. Specifically, we considered high rate punctured binary convolutional inner codes, which result in overall effective information rates

between 1/2 bit and 1 bit per channel use, and bandwidth efficient signal

space inner codes which can achieve overall effective information rates

greater than 1 bit per channel use.

The outer channel in the concatenated coding system was modeled as a BI

channel, from which we were able to calculate the overall channel capacities

with and without side information. These calculations revealed that for

finite total encoder memory order, optimum system performance is achieved at

an inner code rate RI°PC, and as the inner code rate increases beyond R^opt,

system performance degrades sharply. We also showed that system performance

in terras of channel capacity improves when side information is available.

Two types of concatenated coding systems were studied. Scheme I operates

without side information, while Scheme II uses side information. The

performance of Scheme I was studied by computer simulations, formula

calculations, and by asymptotic coding gain derivations. Results indicated

that rather large coding gains could be obtained with little or no bandwidth

expansion. In studying the performance of Scheme II, we first proposed a

32
modified Viterbi algorithm for decoding trellis codes. Side information was

provided to the outer decoder in the form of symbol erasures. The outer RS

code was then decoded by an errors-and-erasures decoder. A significant

improvement in decoded BER was obtained for Scheme II. For systems where

block erasures are allowed, Scheme II is highly recommended.

33
References

[1] G. D. Forney, Jr., Concatenated Codes, Cambridge, MA: MIT Press, 1966.

[2] J. P. Odenwalder, "Optimal Decoding of Convolutional Codes," Ph.D.

thesis, University of California, Los Angeles, 1970.

[3] L. N. Lee, "Concatenated Coding Systems Employing a Unit-Memory

Convolutional Code and a Byte-Oriented Decoding Algorithm," IEEE Trans.

Common., COM-25, pp. 1064-1074, October 1977.

[4] G. C. Clark, J. B. Cain, and J. M. Geist, "Punctured Convolutional Codes

of Rate (n-l)/n and Simplified Maximum Likelihood Decoding," IEEE Trans.

on Inform. Theory, IT-25, pp. 97-100, January 1979.

[5] Y. Yasuda, K. Kashiki, and Y. Hirata, "High-Rate Punctured Convolutional

Codes for Soft Decision Viterbi Decoding," IEEE Trans, on Commun., COM-32

pp. 315-319, March 1984.

[6] G. Ungerboeck, "Channel Coding with Multilevel/Phase Signals," IEEE

Trans, on Inform. Theory, IT-28, pp. 55-67, January 1982.

[7] F. Heramati and R.J. F. Fang," Low Complexity Coding Methods for High Data

Rate Channels", Comsat Laboratories Technical Note, Feb. 7, 1984.

[8] S. G. Wilson, "Rate 5/6 Trellis-Coded 8PSK", submitted to IEEE Trans, on

Commun..

[9] S. G. Wilson, H. A. Sleeper, II, P. J. Schottler, and M. T. Lyons,

"Rate 3/4 Convolutional Coding of 16-PSK: Code Design and Performance

Study," IEEE Trans on Commun., COM-32, December 1984.

[10] M. A. Herro, D. J. Costello, Jr., and L. Hu, "Capacity and Cutoff Rate

Calculations for a Concatenated Coding System," submitted to IEEE

Trans. Inform. Theory, July 1985.

34
[11] R. J. McEliece and W. E. Stark, "Channels with Block Interference,"

IEEE Trans. Inform. Theory, IT-30, pp. 44-53, January 1984.

[12] A. J. Viterbi and J. K. Omura, Principles of Digital Communication and

Coding, New York, NY: McGraw-Hill, 1979.

[13] S. Lin and D. J. Costello, Jr., Error Control Coding; Fundamentals and

Applications, Englewood Cliffs, NJ: Prentice-Hall, 1983.

[14] G. W. Zeoli, "Coupled Decoding of Block-Convolutional Concatenated

Codes," IEEE Trans, on Commun.. COM-21, pp. 219-226, March 1973.

[15] H. Yaraamoto and K. Itoh, "Viterbi Decoding Algorithm for Convolutional

s

Codes with Repeat Request," IEEE Trans. Inform. Theory, IT-26, pp.

540-546, Sept. 1980.

[16] T. Kasarai, S. Lin, and T. Takata, "A Cascaded Coding Scheme for Error

Control," submitted to IEEE Trans. Inform. Theory, Jan. 1986.

35
r "T

Outer RS Code

(N,K)

Outer

Channel

Outer RS Code

Decoder

1

1

1

1

Inner T

Code E

(n,k

J

Inner

i

Inner 1

Code E

rellis

ncoder

,m)

Channel

rellis

ecoder

| ; 1

Fig..l A concatenated coding system
•0 0

1/2

Pr{A.} = 1 - P 0 s

Pr{An } = P 1 s

Fig. 2 Outer channel model
c/cl,c/cl.

with side information

—. — —_ without side information

0 .1 .2 .3

Fig. 3 Capacity for k=3 , b=8 , e = 0.1.
3.4 3.5 3.6 3.7 3.8 3.9 4.0 4.1 4.2 4.3 —

Fig.. 4.1 Performance of Example 3.1. Csimulation) with

R, = 3/4 punctured convolutional code as innder code.
10

-3

10

-5

10

-6

10

-7

10

-8

10

-9

4.2 4.3 4.4 4.5 4.6 4.7 4.8 4.9 5.0

Fig. 4.2 Performance of Example 3.1 (simulation) with

R- =5/6 punctured convolutional code as inner code.
10

-3

10

-4

10

-5

10

-6

10

-7

10

-8

10

-9

= 0.848

4.9 5.0 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 — dB

N

0

Fig. 4.3 Performance of Example 3.1 (simulation) with

RI = 7/8 punctured convolutional code as inner code.
dB

12.55

Uncoded BPSK or OPSK

3.0

Fig. 4.4 E./N required to achieve P, = 10~ and 10~ vs. overall

code rate for Example 3.1 with 64-state punctured

convolutional code as inner code (simulation);
logio

 pb

' ' ' 1 1 1 1 1

0.9 0.91 0.920.930.94-0.950.960.970.980.991 01

Fig. 4.5 Code performance of Example 3.1 with

RX = 3/4, d2 = 33, R = 0.656 vs. R^/B
p

10

b

-3

10

-4

10

-5

10

-6

10'

-7

10

-8

10"

R

u d

eff

= 1.05

= 27

5.8 5.9 6.0 6.1 6.2 6.3 6.4 6.5 6.6 °

Fig. 5.1 Performance of Example 3.2 (simulation) with

4-state, rate E^ = 7/9 PTVTC as inner code.
10

b

-3

10

-4

10

-5

10

-6

10

-7

10

-8

10

-9

eff

d2 = 52

6.5 6.6 6.7 6.8 6.9 7.0 7.1 7.2 7.3 °

E

b

N7dB

Fig. 5.2 Performance of Example 3.2 (simulation) with

4-state, rate Rj = 5/6 PTVTC as inner code.
10

-3

10

-4

10

-5

10

-6

10

-7

10

-8

10

-9

7.2 7.3 7.4 7.5 7.6 7.7 7.8 7.9 8.0

Fig. 5.3 Performance of Example 3.2 (simulation) with

4-state, rate R- = 8/9 PTVTC as inner code.
10

-3

10

-4

10

-5

10

-6

10

-7

io-8

10

-9

5.7 5.8 5.9 6.0 6.1 6.2 6.3 6.4 6.5

Fig. 5.4 Performance of Example 3.2 (simulation) with

16-state, rate R, =7/9 PTVTC as inner code.
10

-3

10

,-4

10

-5

10

-6

10

-7

10

-8

10

-9

Reff - °'95

d2 = 62

6.5 6.6 6.7 6.8 6.9 7.0 7.1 7.2

Fig. 5.5 Performance of Example 3.2 (simulation) with

16-state, rate R, = 5/6 PTVTC as inner code.
10

-3

10

-4

10

10

-6

10'

-7

10

-8

10

-9

7.3 7.4 7.5 7.6 7.7 7.8 7.9 8.0 8.1 ftFig. 5.6 Performance of Example 3.2 (simulation) with

16-state, R = 8/9 PTVTC code as inner code.
12.55

10.05

Uncoded BPSK or QPSK

at 10

-9

.80 .85 .90 .95 1.0 1.05 Reff

Fig. 5.7 E^/Un required to achieve PL = 10~ and 10~ vs. R b u b

for Example 3.2 with 4-state PTVTCs as inner codes

(simulation) .

,,

err
12.55

10.5

Uncoded BPSK or QPSK

I

.80 .85 .90 0.95 1.0 1.05 Reff

Fig. 5.8 Eb/NQ required to achieve Pfa = 10~ and 10

 9 vs. Rgff

for Example 3.2 with 16-state PTVTCs as inner codes (simulation).
10

-9

4.7 4.8 4.9 5.0 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8

N,

dB

Fig. 6.1 Code performance of Example 3.3 (simulation)

with Ungerboeck's 16-state R, = 2/3 coded

8PSK as inner code.
0

12.55

10.05

6.0

5.0

uncoded BPSK or QPSK

5.5 -

0.7 0.8 0.9 1.0

eff

Fig. 6.2 E /NQ required to achieve Pfo = 10

 6 and 10~9

vs. the .overall-effective information rate R ,.,. for

Example 3.3 with Ungerboeck's 16-state RI = 2/3 coded

8PSK as inner code (simulation).
10

-3

10

-4

10

-5

10

-6

10

-7

10

-8

10

-9

= 3/4 coded 16 PSK

R, = 5/6 coded 8 PSK

Reff = *• d2 - 52

6.8 7.0 7.2 7.4 7.6 7.8 8.0 8.2 8.4 -~ dB

N

0

Fig. 7.1 Code performance of Example 3.4 (formula calculation)

with 2-state inner codes.
10

-3

10

-4

10

-5

10

-6

10

-7

10

-8

10

-9

= 3/4 coded 16 PSK

Reff = X> d2 = 86

= 5/6 coded 8 PSK

4.4 4.6 4.8 5.0 5.2 5.4 5.6 5.8 6.0 6.2 6.4 6.6 6.8 _b dB

N

0

Fig. 7.2 Code performance of Example 3.4 (formula calculation)

with 4-state inner codes.
10

-3

10

-4

10

-5

10

-6

10

-7

10

-8

10

-9

R = 3/4 coded

16PSK, R

d2 = 86

err

R-L = 5/6 coded

8PSK, Reff = 1,

d2 = 52

5.5 5.7 5.9 6.1 6.3 6.5 6.7 6.9 7.1 — dB

N

0

Fig. 7.3 Code performance of Example 3.4 (formula

calculation) with 8-state inner codes.
10

-3

10

-4

10

-5

10

-6

10

-7

10

-8

10

-9

d2 = 86

R., = 3/4 coded

16PSK, R ff = 1,

= 5/6 coded 8PSK,

R

 " **

 d

 =

 52

5.5 5.7 5.9 6.1 6.3 6.5 6.7 6.9 7.1 dB

Fig. 7.4 Code performance of Example 3.4 (formula

calculation) with 16-state inner codes.
Table 1. Coding gain over QPSK of Example 3.4

with R, = 5/6 coded 8PSK as inner code.

# of inner

code states

2

4

8

16

# of inner

code states

2

4

8

16

Reff, bits per

channel use

1

1

1

1

Table 2. Coding

with RI = 3/4

Reff, bits per

channel use

1

1

1

1

Coding gain at 10~6 Coding gain at 10~9

(Eb/N0)dB, 10-6 (Eb/N0)dB, 1Q-9

2.85

5.07

3.65

4.15

gain over QPSK

coded 16PSK as

Coding gain

(Eb/N0)dB:

2.05

3.60

3.22

3.22

5.08

7.13

6.28

6.35

of Example 3.4

inner code.

at 10"6 Coding gain

, 10-6 (Eb/N0)dB

4.18

5.77

5.45

5.47

at 10-9

,10-9
10

-3

10

-4

10

-5

10

-6

10

-7

10

-8

10

-9

R = 0.656

5.0 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 6.0 6.1 -p

 dB

Fig. 8.1 Code performance of Example 3.5 (formula calculation)

with Rn = 3/4 self-orthogonal convolutional codes

as inner codes.
10

-3

10

-4

10

-5

10

-6

10

-7

10

-8

10

-9

5.0 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 6.0 6.1 b ._

Fig. 8.2 Code performance of Example 3.5 (formula calculation)

with R = 4/5 self-orthogonal convolutional codes as

inner codes.
0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 R

Fig. 9 Asympototic concatenated coding gain without

demodulator output quantization and with

RI = (n-l)/n punctured codes formed from

(.2,1,6) convolutional code and RS code of

length N = 255.
Y dB

19

18

17

16

15

14

13

12

11

10

S = 16, R = 7/9

S = 16,

= 5/6

S: # of trellis states

0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 1.1 1.2 1.3 Reff

Fig. 10 Asymptotic concatenated coding gain of Example 3.2 with

PTVTCs as inner codes and N = 255 RS codes.
S: // of trellis states

0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 Reff

Fig. 11 Asymptotic concatenated coding gain of Example 3.3

with Ungerboeck's R = 2/3 coded 8PSK as inner

codes and N = 255 RS outer codes.
Y dB

20

19

18

17

16

15

14

13 -

12 -

11 .

10 .

9 .

0.3 0.4 0.5 0.6 0.7 0.8 0.9 1.0 1.1 1.2 Reff

Fig. 12.1 Asymptotic concatenated coding gain of Example 3.4

with RI = 5/6 coded 8PSK as inner code and N = 255

RS outer codes.
7 •

.5 .6 .7 .8 .9 1.0 1.1 1.2 1.3 1.4 Reff

Fig. 12,2 Asymptotic concatenated coding gain of Example 3.4

with R. = 3/4 coded 16PSK as inner code and N = 255

RS outer codes.
incorrect path V'

Fig. 13. A 4-branch first event error at level j in

decoding a trellis code.
10-3

be bi

Fig. 14.1 Code performance of Example 5.1 (simulation) with

R, = 3/4 punctured inner convolutional code, and B=4,

T'=0.1, T =5, d2=33, R=0.656. (1) Eb/NQ=3.68 dB

(Pb=7.9xlO-7 in scheme 1); (2) Eb/NQ=3.88 dB (Pfa =

2.7xlO~ in scheme 1).
'b 10

'

8

icf9 u

ID'10 I

10

-11

10

-12

10

-13

10

-14

10

-15

10'

-16

10

Fig. 14-2 Code performance of Example 5.1 (simulation) with

R..=5/6 punctured inner convolutional code and B=4,

T'=0.2, T =5, d =33, R=0.729. (1) /Nrt=4.56 dB

es z LI u

(Pb=6.5xlO~6 in scheme .1); (.2) Eb/NQ=4.73

(Pb=4.2xlO~ in scheme 1).

dB
10

10

10

10 ^ -

10

-16

-2

,„-! P, +P, . 10 be bi

Fig. 14.3 Code performance of Example 5.1 (simulation) with

R =7/8 punctured inner convolutional code and B=4,

T'=0.2, Tes=6, d2=33. R=0.765. (1) Eb/NQ=5.20 dB

(Pb=2.2xlO~6 in scheme 1); (2) Eb/NQ=5.35 dB (Pfa =

1.3xlO~ in scheme 1).
10

-3

10

-9

10

-10

10

-11

10

-12

10

-13

10

-14

10

-15

10

-16

O P, +P, . be bi

10

10

11 t

Fig. 15.1 Code performance of Example 5.2 (simulation) with

16-state R, =7/9 PTVTC 8PSK as inner code and B=7,

T'=0.2, Tes=10, d2=37, Reff=L CD Eb/NQ=6.1 dB

(P =2.5xlO~6 in scheme 1); (2) Eb/NQ=6.34 dB (Pfa

8.5x10 in scheme 1).
10

-10

10

-11

10

-12

10

-13

10

-14

10

-15

10

-16

10

-17 -6

u

be

Fig. 15.2 Code performance of Example 5.2 (simulation) with

16-state R,=5/6 PTVTC 8PSK as inner code and B=5,

T'=0.1, Tes=8, d2=52, Reff=l. CD Eb/NQ=6.53 dB

(P =4.2x10-7 in scheme 1); (2) E,/Nn=6.77 dB

D

o

(P =1.9x10 in scheme 1).
O p +p

be bi "1

10

10

10

-15

10

-16 -5

18 20 22 24 26 t

Fig. 15.3 Code performance of Example 5.2 (simulation) with

16-state R^S/9 PTVTC 8PSK as inner code and B=8,

T'=0.1, T^=9, d2=64, Reff=l. (1) Eb/N0=7.48 dB

(P=4.3xKT6 in scheme 1); (2) E/N=7.68 dB

(P =5.8x10 in scheme 1).

b Q
10

-9

10

-10

10

-11

10

-12

10

-13

10

-14

10

-15

10

-16

Fig. 16 Code performance of Example 5.3 (simulation) with

16-state R =2/3 coded 8PSK inner code, and B=4,

T'=0.3, Tes=10, d2=26, Reff=0.9. (1) Eb/NQ=5.07 dB

(Pb=l.llxlO~6 in scheme 1); (2) Eb/NQ=5.45 dB

(P =5.3xlO~ in scheme 1).