&/e c 

vu- &/ 

Vyf 7 

A CASCADED CODING SCHEME FOR ERROR CONTROL 

AND ITS PERFORMANCE ANALYSIS 

;NASA-CR- 179936) 

FOR EEiRCE CCNTECL AND ITS FEGEChllANCE 

ANALYSIS (Texas BEM ULlV-) 55 F CSCL 098 

A CASCADEC CCCING SCHEflE 

Technical Report I11 

to 

NASA 

Goddard Space Flight Center 

Greenbelt, Maryland 

~a7- I 40 to 

Unclas 

G3/6l 43492 

. 

I 

Grant Number NAG 5-778 

Shu Lin 

Principle Investigator 

Department of Electrical Engineering 

Texas A&M University 

College Station, Texas 77843 

November 28,1986 
S 

-4 C‘.L\SCADED C‘ODINC SCHEME FOR ERROR C’ONTROL 

AXD IT’S PERFORR;IXN(’E AN.\LYSIS 

Shu Lin 

Department of E.E. 

College Station, Texas 77843 

Texas A & M Lyniversity 

Tadao Kasami 

Osaka Universitv 

Faculty of Engineering Science 

Toyonaka. Osaka. Japan 560 

ABSTRACT 

In this paper, we investigate a coding scheme for error coiidrol in data comniunication 

,stems. The scheme is obtained by cascading two error-correct,ing codes, called tile inner 

and outer codes. The error performance of the scheme is analyzed for a binary symmetric 

channel with bit-error rate e < 1/2. We show that, if t.he inner and outer codes are chosen 

properly, extreniely high reliability can be attained even for a high channel bit-error rabe. 

Various specific example schemes with inner codes ranging from high rat.es t,o very low 

Fates and Reed-Solomon codes as outer codes are considered, and their error probabilities 

i 

are evaluated. They all provide extremely high reliability even for very high bit-error rates, 

say 10-I to lo-’. Several example schemes are being considered by NASA for satellitme 

a.nd spacecraft. down-link error control. 

* This research is supported by NASA Grants No. NAG 5-407 and No. NAG 5-778, 

arid by the Ministry of Education. Japan, Grant No (C) 61.5.50243 

1 
1. Introduction 

In this paper we present and analyze a coding scheme for error control 

for a binary symmetric channel with bit-error rate E. < 112. The scheme is 

achieved by cascading two linear block codes, called the inner and outer 

codes. The inner code, denoted C1, is a binary (nl ,kl > code with minimum 

distance dl. It is designed to correct tl or fewer errors and simultaneously 

detect X1 (A1 - > tl> or fewer errors where tl+A1+l - < dl [l-51. The outer code, 

denoted C2, is an (n2,k2) code with symbols from the Galois Field GF(2') and 

minimum distance d2. If each code symbol of the outer code is represented by 

a binary R-tuple based on a certain basis of GF(2'1, then the outer code 

becomes an (n2R,k2R) linear binary code. For the proposed coding scheme, we 

assume that the following conditions hold: 

kl = mlR , (1 > 

and 

n2 = mlm2 ' (2) 

where ml and m2 are two positive integers. 

The encoding is performed in two stages as shown in Figures 1 and 2. 

First a message of k2E binary information digits is divided into k2 bytes of 

R information bits each. Each E-bit byte (or binary R-tuple) is regarded as 

a symbol in CF(2'). These k2 bytes are encoded according to the outer code C2 

to form an n2-byte (n2% bits) codeword in C2. At the second stage of 

encoding, the n2-byte codeword at the output of the outer code encoder is 

' divided into m2 segments of ml bytes (or mill bits) each. Each ml-byte segment 

is then encoded according to the inner code C, to form an nl-bit codeword. 

This nl-bit codeword in C1 is called a frame. Thus, corresponding to a 

message of k2g bitsat the input of the outer code encoder, the output of the 

inner code encoder is a sequence of m2 frames of n1 bits each. This sequence 

-2- 
of m2 frames is called a block. The entire encoding operation results in a 

binary (m2nl,k211) linear code C which is called a cascaded code. If ml=l 

(i.e., each segment consists of a single Il-bit byte), the cascaded code C 

becomes a concatenated code C61. A concatenated code with varying binary 

linear block inner code can be regarded as a cascaded code with n2=ml and 

m2=1. Therefore there exist cascaded codes which asymptotically meet the 

Varshamov-Gilbert bound for all rates L71. 

The decoding for the proposed scheme also consists of two stages as 

shown in Figures 1 and 3. The first stage is the inner code decoding. 

Depending on the number of errors in a received frame, the inner code decoder 

performs one of the three following operations: error-correction, erasure and 

leave-it-alone (LIA) operations. When a frame in a block is received, its 

syndrome is computed based on the inner code C1. If the syndrome corresponds 

to an error pattern e of tl or fewer errors, error correction is performed by 

adding e' to the received frame. The nl-kl parity bits are removed from the 

decoded frame, and the decoded ml-byte segment is stored in a receiver buffer 

for the second stage of decoding. A successfully decoded segment is called a 

decoded segment with no mark. Note that a decoded segment is error-free, if 

the number of transmission errors in a received frame is tl or less. If the 

number of transmission errors in a received frame is more than X1, the errors 

may result in a syndrome which corresponds to a correctable error pattern 

with tl or fewer errors. In this case, the decoding will be successful, but 

the decoded frame (or segment) contains undetected errors. If an 

uncorrectable error pattern is detected in a received frame, the inner code 

decoder will perform one of the following two operations (See section 2.2): 

1. Erasure Operation -- The erroneous segment is erased. We will call 

-3- 

~- -- 
such a segment an erased segment. Note that this operation creates 

ml symbol erasures. 

2. Leave-it-alone (LIA) Operation -- The erroneous segment is stored in 

the receiver buffer with a - mark. Note that a marked segment may 

contain error-free symbols, 

Whether the erasure operation or the LIA-operation is performed depends on 

the degree of error contamination in the erroneous segment. Since the outer 

code C2 has a fixed minimum distance, it is desired to devise a strategy to 

choose between these two operations so that the minimum distance of the outer 

code is used most effectively in correcting symbol erasures and errors. A 

simple strategy may by devised based on the concepts of correcting symbol 

erasures and errors C2-53. For a code to be able to correct e or fewer symbol 

erasures and t or fewer symbol errors, its minimum distance d is at least 

e+2t+l. This implies that, to correct one symbol erasure, one unit of the 

minimum distance of the code is needed. However, to correct a symbol error, 

two units of the minimum distance of the code are needed. In the proposed 

scheme, when an erasure operation is performed, ml symbol erasures are 

created. To correct these ml symbol erasures, ml units of the minimum 

distance of the outer code are needed. When a LIA-operation is performed, the 

marked segment contains one to ml symbol errors. As a result, 2 to 2ml units 

of the minimum distance of the outer code are required to correct these 

symbol errors. It is clear that, to minimize the consumption of minimum 

distance of the outer code, we would perform the LIA-operation when the 

number of symbol errors in an erroneous segment is less than Lm1/2J+1, and 

perform the erasure operation when the number of symbol errors in an 

erroneous segment is greater than Lml /2J. Hence we may use the following 

-4- 
strategy to choose between the erasure operation and the LIA-operation: If 

the probability that an erroneous segment contains more than Lm1/2J symbol 

errors is relatively small compared to the probability that the erroneous 

segment contains Lm1/2J or less symbol errors, the LIA-operation is 

performed. Otherwise, the erasure operation is performed. The joint 

probability distribution that a received frame is decoded successfully (or 

detected to contain an uncorrectable error pattern) and the corresponding 

segment contains w symbol errors is derived in Section 2.1 (or 2.2). 

The inner code decoding described above consists of three operations: the 

error correction, the erasure and the LIA operations. An inner code decoding 

which performs only the error-correction and erasure operations is called an 

erasure-only inner decoding. On the other hand, an inner code decoding which 

performs only the error-correction and LIA operations is called a LIAonly inner decoding. In this paper we mainly consider the erasure-only inner 

decoding and the LIA-only inner decoding. Which of these two decodings gives 

better performance will be discussed in Section 2.2. A combined erasure-and- 

- 

LIA inner decoding is discussed in Section 5. 

As soon as m2 frames in a received block have been processed, the second 

stage of decoding begins and the outer code decoder starts to decode the m2 

segments which are stored in the buffer. Symbol errors are contained in the 

segments with or without marks. Each erased segment results in ml symbol 

erasures. The outer code C2 and its decoder are designed to correct the 

combinations of symbol erasures and symbol errors. Maximum-distance-separable 

codes with symbol from CF(2') are most effective in correcting symbol 

erasures and errors. 

Now we describe outer code decoding process. Let i and h be the numbers 

of erased segments and marked segments respectively. The outer code decoder 

-5- 
declares an erasure (or raises a flag) for the entire block of m2 segments if 

either of the following two events occurs: 

(i> The number i is greater than a Certain pre-designed threshold 

T,, with Tes 1. (d2-1 )/m, . 

The number h is greater than a certain pre-designed threshold 

Tell(i) with Tell(i) - < (d2-l-mli)/2 for a given i. 

(ii) 

If none of the above two events occurs, the outer code decoder starts the 

error-correction operation on the m2 decoded segments. The ml i symbol 

erasures and the symbol errors in the marked or unmarked segments are 

corrected based on the outer code C2. Let t,(i) be the error-correction 

threshold for a given i where 

Tell(i) 5 t,(i> 5 (d2-l-mli)/2 . (3) 

If the syndrome of m2 decoded segments in the buffer corresponds to an error 

pattern of m,i erasures and t2(i) or fewer symbol errors, error-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. If more than 

t,(i> symbol errors are detected, then the outer code decoder again declares 

an erasure (or raises a flag) for the entire block of m2 decoded segments. 

When a received block is detected in errors and can not be successfully 

decoded, the block is erased from the receiver buffer and a retransmission 

for that block is requested. However, if retransmission is either not 

possible or not practical and no block is allowed to be discarded, then the 

erroneous block with all the parity symbols removed is accepted by the user 

with alarm. An important feature of the proposed scheme is that the decoding 

information of the inner code decoder is passed to the outer code decoder. 

-6- 
This makes the outer code decoding more efficient. 

In the rest of this paper, the error performance of the proposed 

cascaded coding scheme is analyzed. Interleaving the outer code is 

considered. We show that, if the inner and outer codes are chosen properly, 

extremely high reliability can be attained even for high bit-error rate, say 

~=10-~. Various specific example schemes with inner codes ranging from high 

rates to very low rates and Reed-Solomon codes as outer codes are considered, 

and their error probabilities are evaluated. They all provide extremely high 

reliability. Several of these specific schemes are being considered by NASACSFC for satellite and spacecraft down-link error control [SI. 

2. Probabilities of Correct Decoding, Incorrect Decoding and Decoding 

Failure for a Frame 

In this section, we analyze the inner code decoding. We assume that 

the channel is a binary symmetric channel with bit-error rate E - < 112. Let 

P(l) be the probability that a decoded segment is error-free. A decoded 

segment is error-free if and only if the corresponding received frame 

contains tl or fewer errors. Thus 

C 

Let Pi:) be the probability of an incorrect decoding for a frame. This 

is actually the probability of an error pattern of A1+l or more errors whose 

syndrome corresponds to a correctable error pattern of tl or fewer errors. 

Let Pes (l) be the probability of a frame erasure, and let PLk' be the 

probability that a LIA operation is performed on a frame. Let Pi;) be the 

-7- 
probability that a decoded segment with or without a mark contains errors. 

Then 

(5) 

and 

ic + 'et (6) 

Note that Pc (l) + Pi:) is the probability that a received frame is decoded 

successfully (correctly or incorrectly), and PA:) + Pi;) represents the 

probability of a decoding failure. 

Let Ai1) and BI') be the numbers of codewords of weight i in the inner 

code C1 and its dual code Ct respectively. Let Wtjn) denote the number of 

binary n-tuples with weight j which are at a Hamming distance s from a given 

binary n-tuple with weight i. The generating function for Wy,L(n) C91 is 

It was proved by MacWilliams C91 that 

where rl=nl-kl is the number of parity-check bits of the inner code, and 

PS(*, e) is a Krawtchouk polynomial [4,p.129] whose generating function is 

-8- 
Equations (8) and (9) are useful for computing PA1) + Pic (1) if a formula for 

A\’) or ,I1) is known, or min(kl,rl) is small enough (say less than 30) to be 

feasible to compute AI1) or BI1) by generating all the codewords in C1 or C1. L 

Hereafter, .we mainly consider the LIA-only inner decoding and the 

erasure-only inner decoding (A combined inner decoding is discussed in 

section 5). For the LIA-only inner decoding, the LIA-operation is performed 

whenever an uncorrectable error pattern in the received frame is detected. In 

this case, the frame erasure probability Pi:) is lfzerolf. For the erasure-only 

inner decoding, it is obvious that Pi:) = 0. 

If Peg (1 1 (or Pes (l)) is known, then PLb) (or Peg (l)) and Pi:) can be computed 

from (4) to (6) and (8) (or (9)). 

2.1. Detail Error Probabilities for a Decoded Segment with no Mark 

A successfully decoded segment may contain errors. For 0 -- < w < m,, let 

Pe,w (1) be the joint probability that a segment is successfully decoded and the 

number of symbol (or byte) errors in the decoded segment is w. It is clear 

that 

and 

To obtain the probability of a correct block decoding, we need to know P (1 1 - e,w 

for 0 < w < ml. In this section we will derive a formula for Pe,w (1) . -- 

- For a binary nl-tuple v, we divide the first kl=mlL bits into ml R-bit 

bytes. For 1 < h < ml, let ih be the weight of the h-th R-bit byte of v’. Let 

iml+l be the weight of the last rl=nl-kl bits. Then the (m,+l)-tuple, (il, 

-- 

-9- 

~ 
i2, ..e, iml+l), is called the weight structure of 7. 

Suppose that a frame u is transmitted and an error pattern e' with weight 

) occurs. The probability of occurrence of e' is structure (j,, j,, 0.0 ' jrnl+l 

h= 1 

Suppose that there is a codeword v' in C1 which is at a distance tl or less 

from e'. Since the minimum distance of C1 is assumed to be greater than 2tl, 

such a codeword v' in C1 is uniquely determined. Then the inner decoder 

assumes that the frame c+s was sent, and the error pattern e'+; occured. The 

decoded segment is the first kl-bit of u'+v'. If v' is a nonzero codeword, the 

decoding is incorrect, and the first kl-bit of v' represent the errors 

introduced by the inner code decoder. If there is no such codeword v' in C1, 

then the inner code decoder performs either the LIA-operation or the erasureoperation. Conversely, for a codeword v' in C1 whose weight structure is 

(11 , i2, ** , iml+l 1, there are 

error patterns e's with weight structure (j,, j,, e**, jml+l such that the 

weight structure of v+e is (sl, s,, 0.0, sml+l 1. Let ~(1) 11 ,i2s**e,im1+1 be the 

number of codewords in C, with weight structure (il, i, a**, iml+l). For 0 - < 

w - < ml, let 

I, = {(il, i2, e**, iml+l) : 0 - < ih - < R for 1 -- < h < ml, 0 F iml+l 5 rl, 

and exactly w components of (il, i2, -e*, i 1 are nonzero.) . ml 

(1 4) 

Then, P,','? is given below: 

-1 0- 
where 

ml +1 

and E Sh tl 1 . h= 1 (16) 

The formula given by (15) is useful if either (1) the dimension of C1, is 

small enough (say kl < 30) to be feasible to compute the detail weight 

distribution, {Ai1) 1, by generating all the codewords in 

C1, or (2) the dimension of Ct , rl, is small enough to be feasible to 

compute the detail weight distribution of C1 and the number of element in 1, 

is small enough to be feasible to enumerate all the elements in 1, and 

compute IA!~) } by using the generalized MacWilliams’ Identity 

MI. 

kl, 

1, 29**’*im1+1 

I 

1 ’i2””im1+1 

Next we will express the probability P,‘,’i in terms of the detail weight 

distribution of the dual code Ct of C1. Let H be a subset of {l,2,***,ml}. 

Let P,(l)(H) be the probability that for hcH, the h-th R-bit byte of a decoded 

segment is error-free. Let R be the complement of H in {1,2,**-,m1+1}. Define 

the following set: 

I(H) = {(il, i2, 0.0 , iml+l 1: ih = 0 for heH, 0 - - < ih < 2 for h&k{ml+l}, 

and 0 i iml+l - < rll. (17) 

Then, we have that 

-1 1- 
Define 

(l-J1 [ ml rI (d(1-E)) jh 3 

h= 1 (18) 

It follows from (10) and (19) that 

L Let Bi (1). 

(il ,i2, -**,iml+l 1. Then we have Lemma 1. 

be the number of codewords in C1 with weight stmcture 1'12, ***,iml+l 

Lemma 1: 

where IHI denotes the number of elements in H. 

Proof: See Appendix A. 

-1 2- 

AA 
For 0 -- < s < ml, let us be the sum of PL1)(H) where H is taken over all the 

subsets of {1,2,***,m,} with s elements. Define 

Then it follows from (22) and (23) that 

-rl R 9. R rl 

us = 2 c z .'. z c 

il=O i2=0 

In the sum us, error patterns with ml-s-l or less symbol (or byte) errors in 

a decoded segment are counted more than once. In fact, 

Using the principle of inclusion and exclusion [lo], we have that 

For 0 -- < j < ml, define 

Then it follows from (24) to (27) that we have 

-1 3- 
Theorem 1: 

AA 

It is feasible to obtain detail weight distribution {B;' I. 1 1,129 ,im, +1 

by generating all the codewords in C;' for relatively small rl, say less Lhan 

30. Note that the number of terms to be added in the right-hand side of (23) 

is (:' ) , and therefore the number of terms to be added or subtracted in the 

right-hand side of (27) is at most 2m1. For small ml, Tj(il,i2,-*-,iml+l;~) 

can be easily computed and added for each codeword generated. If the dual 

code of C1 contains the all-one vector, then Pi!: can be computed by 

generating every codeword in the even-weight subcode and using 

instead of Tj(11,i2,**-,im1+1 ;E). From (11) and (281, Pi:) can be computed. 

2.2. Detailed Error Probability for a Marked Segment 

In this section we will evaluate the probability of symbol errors in a 

marked segment. Let Pea,w ('I be the joint probability that a segment is marked 

and the number of erroneous symbols in the marked segment is w. Then 

-1 4- 
In the following, we consider the LIA-only inner decoding. Define 

J, = {(jl,j2,***,jm,+1) : 0 L jh L 9. for 1 -- < h < m1 , 0 jml+l rl , 

and there are exactly w nonzero components in (jl,j2,***,j 

(30) 

Then it follows from the definition of Pea,w that 

where St is defined by (16). The first term of (31) represents the 

probability that there are exactly w erroneous symbols (or bytes) in the 

first ml bytes of a received frame, and the second term is the probability 

that the syndrome of these symbol errors corresponds to an error pattern of 

t, or fewer errors. Define 

1 

where the summation is taken over all the subsets of {1,2,***,m11 with 

exactly w elements. Then ('I can be expressed in terms of the detail weight 

distribution of the dual code of C,. 

-1 5- 
Theorem 2: 

" B(1).' (1-263) 

-rl a. 

il ,i2, -0- 

-2 z z z 

Proof: See Appendix B. AA 

An important question is which provides better performance, "the LIAonly inner decoding,11 or "the erasure-only inner decoding ?I1 LIA-only inner 

decoding may be reasonable only if 

If 

where Pea,w (1 1 is computed under the assumption that the inner code decoding is 

a LIA-only inner decoding, then a LIA-only inner decoding provides better 

performance than the erasure-only inner decoding. 

3. The Probability of a Correct Block Decoding 

In this section, we will evaluate the probability that a block of m2 

segments will be decoded correctly by the outer code decoder. Let Pe(j,m,h) 

denote the probability that there are h segments with marks and j symbol 

-1 6- 
errors in a set of Consisting of m decoded segments with or without marks. It 

follows from the definition of Pe(j,m,h) that 

From (34) to (371, Pe(j,m,h) can be computed readily. 

The probability that, after the inner code decoding of a block of 

frames, there exist i erased segments, h marked segments and j symbol errors 

in the marked and unmarked (or decoded) segments is 

(i m2 Pe(j,m2-i,h) . (38) 

Therefore, the probability of correct decoding of a block, denoted Pc, is 

given by 

Let Pes and Per denote the probabilities of a block erasure and an 

’ incorrect decoding respectively. Then 

‘c + Pes + Per =1 . (40) 

It follows from definitions that the following equality and bound hold: 

-1 7- 
TeR( i) n2-m1 i 

z Pe(j,m2-i,h) + Per = Te~ z (i '2 1 [Pes (1)Ii 

i=O h=O j=t2( i)+l 'e, 

The right-hand side of Eq.(41) provides an upper bound on the probability of 

a block erasure (or decoding failure), and the right-hand side of (42) gives 

an upper bound on the probability of an incorrect block decoding. 

To the authors' knowledge, no feasible procedure for computing Per or 

has been derived except for the special case where the outer code is a 'es 

binary code (11=1) and used only for error detection and nl-k1+n2-k2 is small, 

say less than 25 [ll]. If the outer code is used for both error correction 

and detection, detailed information on the weight distribution of outer 

codewords with specified bit patterns is required in general. 

4. Interleaving 

In this section, we investigate how interleaving affects the error 

performance of the cascaded scheme. Suppose that the outer code C2 is 

interleaved in such a way.that each symbol (or R-bit byte) in a segment is 

from a different outer code codeword as shown in Figure 4. Hence the 

-1 a- 
interleaving depth (or degree) is ml. Each symbol-column (an n2x!L submatrix) 

in the first ml columns of the code array is called a section. Note that a 

section is simply a codeword in the outer code C2. The klk2 bits in the first 

k2 rows and kl columns are used as information bits. The code array consists 

of n2 frames and is transmitted row by row. As for the decoding, after n2 

received frames have been decoded by the inner code decoder, the n2 decoded 

segments are arranged into an array as shown in Figure 5 which is called a 

decoded segment-array. Note that an erased segment creates one symbol erasure 

in each section. A decoded segment with or without mark may contain symbol 

errors which are distributed among the ml sections of a decoded segmentarray, at most one symbol error in each section. Therefore, each section in a 

decoded segment-array may contain symbol erasures and errors. Now each 

section is decoded based on the outer code C2. Note that buffers are needed 

to store code arrays at both transmitter and receiver. 

For 1 < u < ml, let pe(u) be the probability that the u-th symbol of a 

decoded segment with no mark is erroneous. If the inner code C1 is quasicyclic by every s-bit shift where s divides II, then pe(u) is independent of 

u. It follows from the definition that 

-- 

where Pe (1 1 ({uj) is given by (18) or (22). Hence pe(u) can be computed from 

either (8) and (18) or (9) and (22). 

Let peI1(u) be the probability that the u-th symbol of a marked segment 

is erroneous. For simplicity, the LIA-only inner decoding is considered. 

Define 

) : 0 < jh < II for 1 -- < h < mls jufO J(u) = I (jl,j2,---,dml+l - - 

and 0 jml+l rl 1 . (44) 

Modifying the derivation of (31) or (331, we have that 

-1 9- 
II II rl A(1 p,,(u) = 1 - (1-EIR - E *** z z il ,i2,*** 

and 

(46) 

[See Appendix C for the derivation of (4613. 

Since the 

every segment 

Per(u) denote 

- 

outer code is interleaved by a depth of ml, the u-th symbol of 

is from the u-th section for 1 -- < u < ml. Let Pc(u>, Pes(u> and 

the probabilities of a correct decoding, an erasure and an 

- - 

incorrect decoding for the u-th section respectively. Then formulas or bounds 

- - I 

for P,(u), Pes(u) and Per(u) can be derived from those for Pc, Pes and Per by 

the following replacement: m,i + i , m2 + n2 and 

-20- 
The restrictions on thresholds Tes, Tell(i) and t2(i) can be relaxed as 

follows : 

Tes d2-1 , Tell(i) 5 (d2-1-i)/2 and t2(i> - < (d2-1-i)/2 . 

Let Pc be the probability of a correct decoding for all interleaved ml 

sections. Let Per and Pes be the probability that an incorrect decoding 

occurs for at least one of the interleaved ml sections and that of a block 

erasure, respectively. Then 

- 

per < max mlPer(u) , - 1 <u<ml -- 

(47) 

and 

Let Per+Pes denote the right-hand side of (48). 

Next we present a formula for Pc and another upper bound on Per. For 

simplicity, we only consider the erasure-only inner decoding in which t2(i> 

is independent of i and is denoted t2. 

(1 1 denote the 9 aml ), let Pe,al, Saml 

probability that a segment is not erased and the u-th symbol of the decoding 

segment is error-free if and only if au=O in the inner code decoding. A 

computing procedure for is shown in Appendix D. For a positive 

integer n and integers jh with 1 - < h - < ml such that 0 - < jh - < n, let 

petjl ,j2,***,jml (n) be defined by 

For a binary ml-tuple (a,, a2, **e 

(1 1 

',,a1 , ***,am, 

Then Pc (= l-Per-Pes) is given by 

-21 - 
It is feasible to compute P, for small ml, t2 and relatively small min{kl, 

"1 -kl I. 

For 1 -- < u < ml and a in GF(2'1, let pe(u,a) be the probability that a 

segment is not erased and the u-th error symbol of the decoded segment is a. 

A procedure for computing pe(u,a) is stated in Appendix E. Then we have that 

In Appendix F, the following upper bound on Per is derived. 

n2-i n2-i min{ t2,n2-i-w) 

h=O 

where 

where Y is a primitive element of GF(2'). 

Let Per be defined as follows: 

(1 ) For the case where the outer code is not interleaved, 

right-hand side of (421, and 

Per denotes the 

(2) for the case where the outer code is interleaved by a depth ml , Per 

denotes the right-hand side of (47), if an erasure-only inner decoding 

-22- 
is used and t,(i> is independent of i, 

right-hand side of (52). 

and otherwise, Per denotes the 

It follows from (421, (47) and (52) that 

Per LPer 

- 

For most cases of the example schemes considered in the next section, the 

right-hand side of (52) is considerably tighter than that of (47). 

5. Example Schemes 

In the following we consider various specific example schemes using 

cascaded coding for error control. In these example schemes, the inner codes 

range from high rates to very low rates, and the outer codes are Reed-Solomon 

(RS) (or a shortened RS) codes with symbols from CF(2'). The outer code is 

either interleaved or not interleaved. The inner codes with their parameters 

and generator polynomials are listed in descending order of the rates in 

Table 1. The first three inner code, C1(l) to C1(3) are shortened distance-4 

Hamming codes. The next three codes, Cl(4) to C1(6) are obtained by 

shortening the even subcodes of primitive BCH codes of length 63. The forth 

and fifth codes, Cl(4) and c1(5), can be decoded with a table look-up 

decoding. The sixth code C1(6) is majority-logic decodable in two steps [l], 

and its decoder can be implemented easily. C1(7) is a quadruple-error 

correcting Goppa code [12]. The eighth code is an extended primitive BCH 

code. In fact, is is also a Reed-Muller code and is majority-logic decodable. 

Cl(9) is the extended (24,12) Golay code which is widely used for satellite 

and deep space communications. C1 (101, C1 (12) and C1 (1 3) are low-rate 

biorthgonal codes (or f irst-order Reed-Muller codes). C1 (1 1 is a quadrupleerror correcting one-step majority-logic decodable code [I]. 

-23- 
For various combinations of code parameters and bit-error rates, the sum 

of the probability of a block erasure (decoding failure) and that of a 

decoding error, Pes+Per [given by (41 ) or (5011, and upper bound Fer [defined 

in the previous section] on the probability of a decoding error are given in 

Tables 2 to 5 and Figures 6 and 7. The degree of interleaving, denoted Id, is 

either 1 or ml. Thresholds, TeI1 and t2, which are independent of the number 

of erased segments are considered here. The parameter, mlTes/Id+2t2+1, is 

used as a measure of the complexity of the outer code. 

Symbol llE1l (or l1Lv1) shown in Tables 2 to 5 indicates that an erasureonly inner decoding (or a LIA-only inner decoding) is used. For a comparison, 

we also consider a combined erasure and LIA inner decoding where the LIAoperat ion is performed whenever an uncorrectable error pattern whose weight 

is even (or odd) is detected in a received frame for odd (or even) t,. In 

Table 2 symbol 'lE-Lfl indicates that the combined inner decoding is used. For 

the combined inner decoding, formulas for Peg, (1 1 and peQ(u) are given 

in our NASA Technical Report C81. In Table 2, the computation results for the 

combined inner decoding are given only for the cases where either d2 or 

ml Te,/Id+2t2+1 is smaller than that for either the erasure-only inner 

decoding or the LIA-only innel* decoding. 

Example schemes shown in Table 2 are obtained as follows: Given the 

inner code C,(i) with 1 < i 7, n2=252 or 255, Id'l or m1 and the type of 

inner code decoding, the values of t2, Tes and TeQ are chosen to minimize 

mlTes/Id+2t2+1 under the condition that 

- 

pes + per (or peS+per) < IO-1 

for bit-error rate E = 

satisfy the following condition 

and then the minimum value of d2 is chosen to 

Per < 10-l0 

-24- 
for E = Only the example schemes with rates greater than 0.6 and d2 < 

33 are listed in Table 2. In the column of Pes+Per, an entry marked ft*ff is 

given by the upper bound of (48). 

- 

In Tables 3 to 5, Pes+Per and Perare shown for cascaded coding schemes 

in which the inner code is C,(i) with 1 < i < 13, the outer code is an 

interleaved RS code with a depth of ml, and an erasure-only inner decoding is 

used. Parameters Tes and t2 are chosen to minimize the values of Pes+Per for 

a certain bit-error rate E under the restriction that Per < lo-'' for every 

bit-error rate E listed in the Tables. 

-- 

- 

In Table 3 the outer code is the NASA standard (255,223) RS code over 

GF(2 and the rates are greater than 0.6. For comparison, the case with no 

inner code is shown in the first row. In Table 4 the rates are less than 0.6 

and greater than 0.4, and example schemes with lower rates are given in 

Table 5. 

8 

In Figure 6 (or 71, the curves of Pes+Per (or Fer) vs. E are shown for 

five representative example schemes listed in Tables 3 to 5. 

6. Conclusion 

In this paper, we have investigated a cascaded coding scheme for error 

control. An important feature of the scheme is that the decoding information 

of the inner code decoder is passed to the outer code decoder. This makes the 

outer code decoding more effective. Error performance of the scheme is 

analyzed. If the inner and outer codes are chosen properly, e x t r e m e l y h i g h 

reliability can be achieved even for a high channel bit-error rate. Many 

example schemes are being evaluated. Some high-rate example schemes are being 

considered by NASA for satellite down-link error control, and some low-rate 

-25- 
example schemes are being considered for spacecraft down-link error control. 

A major advantage of the proposed cascaded coding scheme, especially 

with interleaving, is its robustness against unpredictable bursts. 

This paper presents first serious effort in analyzing the error 

performance of a cascaded coding scheme which includes concatenated coding as 

a special case. 

ACKNOWLEDGMENT 

The authors wish to thank the anonymous reviewers of this paper for 

their constructive comments and suggestions, which were helpful in improving 

its quality. 

-26- 
REFERENCES 

1. S. Lin and D.J. Costello, Jr., Error Control Coding: Fundamentals and 

Applications, Prentice-Hall, New Jersey, 1983. 

2. E.R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, New York, 1968. 

3. W.W. Peterson and E.J. Weldon, Jr., Error-Correcting Codes, Second 

Edition, The MIT Press, Cambridge, Mass., 1972. 

4. F.J. MacWilliams and N.J.A. Sloane, Theory of Error-Correcting Codes, 

North Holland, Amsterdam, 1977. 

5. R.E. Blahut, Theory and Practice of Error Control Codes, Addison Wesley, 

Reading, Mass., 1983. 

6. G.D. Forney, Jr., Concatenated Codes, The MIT Press, Cambridge, Mass., 

1966. 

7. E.L. Blokh and V.V. Zyablov, IIExistence of Linear Concatenated Binary 

Codes with optimal correcting properties,I1 Probl. Peredach. Inform., 

vo1.9, PP.3-10, 1973. 

8. T. Kasami and S. Lin, "A Cascaded Coding Scheme for Error Control,11 

NASA-GSFC Technical Report, December 10, 1985. 
3. J. MacWilliams, "A Theorem on the Distribution of Weights in a 

Systematic Code," Bell System Technical Journal, 

VO1.42, pp. 79-94, 1963- 

10. J. Riordan, An Introduction to Combinatorial Analysis, 

John-Wiley and Sons Inc., New York, 1958. 

11. T. Kasami, T. Fujiwara and S. Lin, "A Concatenated Coding Scheme for 

Error Control," IEEE Trans. on Communications, Vol. COM-34, No. 5, 

pp. 481-488, 1986. 

12. V. D. Goppa, "A New Class of Linear Error-Correcting Codes," Problems of 

Information Transmission, Vol. 6, No. 3, pp.207-212, 1970. 

-28- 
APPENDIX A 

Proof of Lemma 1 

Let IHI = u. It follows from (7) that 

m1 +1 m1 +1 

"1- hi1 ih E ih 

(l+XY) 

ml +1 m1 +1 

nl-tu- E ih ih 

(A-1 h=l (x+y)h=l . (l+XY) 

The set of codewords in C1 whose weight in the h-th 2-bit byte is zero for 

every h in H is a linear (nl ,kl-tu) subcode of C1. Let C1 (HI denote the 

linear (nl-2u,k,-Ru) code obtained from the above subcode by deleting the u 

zero R-bit bytes for the u positions in H. Let AI1)(H) denote the number of 

codewords of weight i in C1(H). Then 

-29- 
where 

ml +l 

h= 1 

C ih=i 1. 

The right-hand side of (A-1) can be rewritten as 

(A-2) 

(A-3) 

Let Bil)(H) be the number of codewords of weight i in the dual code of C1(H). 

Then, by MacWilliams' identity [41, (A-3) can be rewritten as 

n1 -tu n1 -Ru-i n1 -Ru-i 

2-r1(l+XY)Ru Z Bll)(H)(l+X) (1-X)i (l+Y) (1-Y)i . i=O 

(A-4 1 

It follows from (211, (A-1) and (A-4) that 

n1 -tu n1 -Ru-i "1 

=2 -rl z B!~)(H)(~+X) (t-X)i Z Qs(i,nl-Jlu,Ru,X)Ys . (A-5) 

s=o i=O 

Taking the terms on both sides of (A-5) for which the degree of Y is tl or 

-30- 
less and substituting "1" for Y, we have that 

R R '*1 

z il , i2, z *" z r, A(1) 

( it , i2, , iml + €1 (H) 9 'ml +I j =O jml =O jml +1 =O 

m, +1 

Substituting d(1-E) for X and multiplying the left-hand side of (A-6) by 

(l-~)~', we obtain the right-hand side of (18). Therefore we have that 

Since a generator matrix of the dual code of C1(H) can be obtained from a 

parity-check matrix of C1 by deleting all columns corresponding to the h-th 

R-bit positions for hsH, the following relation holds. 

where 

0 5iml+, 5 rl, and Z ih = i 1 . hsH 

Then, expression (22) of Lemma 1 follows from (A-7) and (A-8). 
APPENDIX B 

Proof of Theorem 2 

Let F(X1 ,X2,***,Xm1+1 ,Y> be defined as follows: 

It follows from (7) and generalized MacWilliams' identity [4,p.l471 that 

Let H be a subset of {l,2,-**,mll and FH,t (X1,X2,-*.,X, +l,Y) be the sum of 

the terms of F(X,,X2,***,~m1+l,Y) for which the degree of xh is nonzero for 

heH and is zero for h~Il,2,*.*,m~l-H, and the degree of Y is tl or less. 

1 1 

-32- 
R'ih tl ml+l 

[ z pS( z ih,nl)yS 3 II [ (1+xh) (l-xh)ih - 1 ] s=O h=l hEH 

Let F,,+ (x, ,X2,"' rXml+l,Y) be defined as the sum of 

FH,tl(xl *x2*"'~xm1+1 ,Y) over all the subsets, H's, of {l,2,-**,ml} with 

exactly w elements. Then the second term of (31) is equal to 

It follows from (B-3), the definition of R, given by (32) and the following 

that (B-4) is equal to 
~~ ____- 

APPENDIX C 

Derivation of (46) 

Let Fu(X1 ,X2,-**,Xm1+1 ,Y) be the sum of terms of F(X,,X2, ""xml+l ,Y) 

defined in Appendix B for which the degree of Xu is nonzero and the degree of 

Y is tl or less. Using (10) and (B-21, we have that 

-- I 

h+u 

Il-i '1 -iml + 1 iml +I 

[(l+X) U(1-XliU - 11 (l+X) (1-X) . . 

The second term of (45) is equal to 

- (l-~)~' FU(c/(l-~) ,~/(l-€),o**,€/(l-€),l) 

Then (46) follows from (B-5). 

-34- 
APPENDIX D 

A formula for computing Pe,al,a2 (1 1 

,**-,am, 

Let H be a subset of {l, 2, **., ml}. For small m,, say less than 11, 

{Pe(H) : HS 11, 2, **e, ml 1 1 can be found as shown in section 2.1. Then it 

follows from the principle of inclusion and exclusion [lo] that 

where W = { i I ai = 1, 1 -- < i < ml) and H’ = 11, 2, *e* , ml 1-H. 

-35- 
APPENDIX E 

A procedure for computing p,(u,a) 

For 1 < u < ml, 0 < i < nl-R and u E: GF(2'1, let Ail)(u,a) (or 

Bjl)(u,a)) be the number of codewords in C1 (or the dual code of C,) whose uth symbol is a and whose binary weight excluding the u-th symbol is i. Let af 

be the f-th bit of the binary representation of a, and let la1 be the weight 

of the binary reprensentation of a. It follows from the definition of pe(u,a) 

that 

-. - - - 

For relatively small kl, say less than 25, 

a in GF(2') can be found by generating 2 

{Ail)(u,a)l 0 -- < i < nl-Rl for an 

codewords of C1. 

k1 -R 

A procedure for computing pe(u,a) which is more convenient for kl > nlkl will be derived below. By the generalized MacWilliams' identity [4, 

p.1471, we have that 

-(nl -k, nl'R 

B(l)(u,B)Pi(h,nl-a) II a P (Bf,l> . f=l Of 

Ail)(u,a) = 2 

h=O E BcGF(2 ' Rh ) 

( E-2 

By [4,p.151], we have that 

and 

-36- 
n1 -R-i n1 -1-h nl -2-h n1 -R 

i=O 

E Pi (h,nl -R) (1 +XY) (X+Y)l = (1+X) (1-XIh (1+Y) (1-Y)h 

It follows from (71, (E-21, (E-3) and (E-4) that 

-(nl -kl 1 n, -R 

=2 ZE Bil )(u,B) h=O fl~GF(2~) 

where 

(l+XY)m-h(X+Y>h(l+Y> n-i(l-Y)i = n+m Z Q;(i,n,h,m,X)Ys , 

s-0 

Taking the term on both sides of (E-5) for which the degree of Y is t, or 

less substituting d(1-c) for X and 1 for Y and multiplying the both sides by 

(1 -E)"~, we obtain the following formula from (E-1 ): 

-37- 
L 

If C1 is a shortened cyclic code, min{lJnl-kl~ columns of a generating 

matrix corresponding to the u-th symbol position are linearly independent, 

and for a symbol B, {BA')(u,B) I 0 -- < h < nl-ll} can be found by generating 

min{n,-k, -k,O} 2 codewords of the dual code of C1. 

-38- 
Appendix F 

Derivation of (52) 

At first an upper bound on Per(u) will be derived. Let us number the 

segment in a decoded segment-array (Fig. 5) from 1 to n2. Suppose that the 

number of erased segments after the inner code decoding is Tes or less. Let 

E, be the set of the erased segment numbers. For f 1 E,, let ef be the error 

symbol at the u-th symbol position of the f-th decoded segment, and let e = 

(e,, e2, ***, e 1. Note that ef is the symbol error at the f-th symbol 

position of the u-th section of a decoded segment-array. Suppose that the uth section of a segment-array is decoded incorrectly by the outer code 

decoder. Then the u-th section is decoded into an outer codeword vc + 7, 

where Vc is the actual transmitted outer codeword and 3 is the nonzero outer 

codeword induced by the outer code decoding. Let vf be the f-th symbol of 5. 

Define the following sets associated to 3 and e. 

"2 

W(v) = A { f I Vf * 0, f L E, 1, 

H(e,v) A = { f I ef t 0, vf = 0, f L E, 1, 

and 

( F-3 1 J(Z,?) A = { f I ef = vf 0, f L E, 1. 

When a section is decoded based on the outer code C2, only t2 or fewer 

symbol errors and Tes or fewer erasures are corrected. Hence, the following 

inequality holds: 
For given 1 -- < u < ml, E,G{ 1,2, ***, n21, 7 E C2, HC- 1,2, *** , n21 

and Jr{ 1,2, ***, n21 such that H is disjoint from E, and W(v'), JSW(v) and 

[HI + [ w(?)I - I JI t2, let Pe(u,E,,v,H,J) be the probability of the 

occurrence of an error pattern e induced by the inner code decoding for 

which H(e,?)=H and J(e,v)=J. Then 

where i=lE,l, w=lW(v>I and h=lHI (see Figure 8). 

Let W be a subset of {1,2,***,n21-E,-H such that WZJ, d2-i < IWl and 

Let C2(E,,W) be defined as the following subset of codewords 

- 

IWl+h-j - < t2. 

in C2: 

vffO if f E W and only if f E WUE,}. (F-6) 

Since i - < Te, and t2 - < (d2-1-TeS)/2, we have that 

d2>i+2t2+1. - 

-40- 

(F-7) 
Since d2 < w+i and h+w-j < t2, it follows from (F-7) that - - 

j > i+w-d2 > 0 . - - ( F-8 1 

Let J' be a subset of J such that 

For any af E CF(2')-{01 with f E J', consider two different codewords 7 

and v' - = (vi, v$, 0.0, vA2) in C2(E,,W) such that vf = 

9 'n2 = (v,, v2, 0.. 

-- vi = af for f E J'. Since the weight of v-v' is at least d2, we have that 

Vf * vi , for f E EsUW - J'. (F-10) 

It follows from a well known inequality and (F-10) that 

(F-11 ) 

-41 - 

~ 
It follows from (51) and (F-11) that 

i+w-d2 2'-2 j +d2-i-w 

z n Pe(U,Vf) 5 CPe(u)1 z CP~(U,Y')I . (F-12) 

kC2(Es,W) fEJ q= 0 

Thus it follows from (53) that 

- 

Since Per(u) is the sum of Z Pe(u,Es,v,H,J) taken over all possible 

vcC2(Es,W) e E,, W, H and J, we have that 

(F-14) 

Per is bounded above by the expression obtained from the right-hand side of 

(F-14) by replacing P(u,i,w,h,j) with Z P(u,i,w,h,j). ml 

up 1 

-42- 
4 

Outer Code Inner Code 

Encoder Encoder 

("2 9 k2 1 ("1 'kl) 

I Outer Code . Inner Code .( Decoder Decoder 

i 

Figure 1 A cascaded coding system 
k211-bit (or k2-byte) Message 

Block 

n2-byte 

n, -bit n1 -bit n1 -bit 

Frame-1 Frame-2 

..e 

codeword in C2 

1 ~~ 

ml -byte 

I segment-1 I segment-2 1 I segmnt-m2 

Figure 2 Encoding Operation 
segment-1 segment-2 e.. segment-m2 

Figure 3 Decoding operation 

Frame-1 Frame-2 ..e Frame-m2 
G- ml-byte segment .-> 

"2 I 

t- %-bit 4 

byte 

? 

rnl -th 

+ 

1 st 

Section Sect ion 

* 1st 

Frame 

k th a- 2- 

Frame 

n2-th 

Frame 

Figure 4 An interleaved code block 
"2 I 

- ¶.-bit- ~ 

byte 

t t 

1 st m, -th 

Sect ion Section 

1 st Decoded 

* segment 

k2-th Decoded 

6 

s egmen t 

+n2-th Decoded 

segment 

Figure 5 A decoded segment-array 
I 

13-1 

I 

CL a IO-* 

+ 

10-4 

no inner code and 

and 

223) 

and 

223) 

RS 

RS 

code II' 

code 

i 

C (13) and 

(63,311 RS code 

1 

C1(9) and 

(63,421 RS code 

\ 

10-3 10-2 10-I 

BIT ERROR RATE E 

Figure 6 The sum of probabilities of a block erasure and 

a decoding error. 
L 

aJ 

ILL 

& 

0 

e 

& 

LLJ 

W 

LL 

0 

). 

I- 

-I 

n 

U 

U 

p3 

cc 

M 

0 

Q 

no inner code 

n 

and 

223) 

and 

RS 

I 

(255,223) RS 

code 

code 

I 

code 

1 (63,42) RS code 

BIT ERROR RATE E: 

10-1 

Figure 7 Upper bounds on the probability-of decoding error 

for cascaded codes. 
4 n2-i unerased segments 

decoded by the inner code decoder 't 

n2-i-w-h 

h segments s egme n t s 

i erased whose u-th whose u-th 

nonzero symbols t- of outer codeword v 

segments 

I 

t, - 

j segments whose error symbol 

at the u-th symbol position 

is identical with the u-th 

symbol of codeword v 

\ 

symbol is 

error-free 

:;:E:;: symbol is 

erroneous 

I 

1 

I 

, - 

Figure 8 Illustration for Equation (F-5) 
Table 1 Inner Codes 

shortened 

shortened 

shortened 

Hamming code 

Hamming code 

Hamming code 

shortened 

BCH code 

c, (9) 

(55,481 0.873 8 6 4 1 

(56,481 0.857 8 6 4 1 

(30,241 0.800 8 3 4 1 

(61,481 0.787 8 6 6 2 

I 

extended 

BCH code 

Rate 

inner code Inner codes (nl ,kl> of the R m1 dl tl 

(32,161 0.500 8 2 4 3 

biorthogonal code 

I (53,401 0.755 8 5 6 2 BCH code 

shortened 

( 8, 4) 0.500 4 1 41 

shortened 1 (59,401 0.678 8 5 8 3 BCH code 

Goppa code 1 (64,401 0.625 8 5 9 4 

extended 1 (24,121 0.500 6 2 8 3 Golay code 

shortened 

Type 0 (51,241 0.471 8 310 4 

DTI code 

biorthogonal code I (16, 5) 0.313 5 1 83 

biorthogonal (32, 6) 0.188 6 1 16 7 

code 

~~ ~ ~~~ 

Generator polynomial 

(1 +X) (1 +x+x71 

The generator polynomials are given only for shortened cyclic codes, and 

6 is the minimum polynomial of ai with a as a root of 1+X+X . 
0) 

&mu 

ou 0 

cu ro3 

a ou c, U +ma 

n 

N 

Q) 

4 

P 

(d 

fa 

-0 

8 

L 

a 

S 

H 

E" 

N 

d 

0) 

c, 

fa 

0) 

fJ 

\ 

W 

U 'H 

N 

U 

N 

S 

a 

c, 

a 

a 

............... 

e.-mmt - c ma -a -=r m- 

* * * * o*o - om m 

............... 

c ba c N -N mJ m- -ma N 

............... 

Nbm-m=rcb=rmNNwNc 

** * * 

........ ... ooooooodddddooo 
L 

0 

k 

M 

c 

P 

4 

8 

8 

G-l 

0 

x 

c, 

d 

d 

d 

(d 

0 

L 

a 

a, 

n 

n 

5 

C 

0 

r4 

-0 

0 

s 

m 

k 

P 

3 

U 

C 

(d 

a3 e c .- e e- -e e- (v .- a 

lo 0'; 07 I II I1 7 ww ww ow ww ww && x om om wcu ow Inm Inm 

w rm-e Q\.P m e T c u ?? ?< 82 ?? '9? ?? 

- 

cu 

ww 

om 

rm 

0'; 

?? 

IO m 

mcu =r(v I1 II 

ww ww mIn Incu 

27 O!? 

ma m.- 

il I I I I I I 4 

mcu I In 

0 rIn a3In 

I t-- W 

.- 

x &A 

?5 

a 

IG ba3 2 

L 

Q, 

L L 

Q, Q, 

L L L 

0, Q, 

r4L r4L rnL mL VlL VlL 

Q,Q, Q,Q, Q,al Q,Q, ala 

* a + @a 

a la a la La12 a la e la a la 

a a a + + + + 

n n n n n 

m In W W v e cu 

W 

u- u- u- u- co 

W 

cu 0 c cu 

cu cu cu cu TFFFFF 2 0 0 

cu 

w w w w W w 2 

\ 

W 

U e W m IO In W 

m m m m m m m m m m m m cu 

U 

I I I I I I 

1 I I I 

N m m m m m m cu (v 

cu cu (v cu cu cu 

cu In In Ln Ln In 

In Ln 

cu In In In In 

cu (v cu cu 

C 

Y cu cu cu cu 

In 

cu 

0 

IO 

0 

Q 

a3 

0 

'9 '9 5: 8 

? ? 

In 1 t- IO 

0 0 

Q, 

c, 

0 0 

0: (d ? p1 
=r rnb 

II 

ww 

a3\o 

coco 

T.9 

-m Inm 

-a3 -m 

II II 

ww ww =r=r 00 

lnm \o(u 

9". .. - 

L 

a, 

QL 

a + 

aa,laa, 

L L 

a, a, 

QL QL a,@ a,@ 

a a + + 

a 10. a la 

cu 

lo 

e 

X 

In 

w 

n 

- 

cu 

I 

0 

X 

=r 

Y 

w 

e 

a, 

& 

(If 

L 

b 

L 

L 

a, 

I 

& 

d 

rn 

N 

I 

0 

X 

m 

I 

w 

c 

- 

N 

I 

0 

X 

(u 

I 

w 

c 

b 

L 

L 

w 

M 

C 

U 

a, 

L 

0 

d 

8 

n 

5 

rl 

d 

r!2 

B 

M 

r: 

d 

0 

a, 

Ll 

0 

01 

a, 

d 

& 

d 

rl 

d 

(If 

D 

0 

L 

a 

n 

n 

=r 

a, 

4 

D 

3 

cu 

I 

0 

c 

X 

I 

W 

e 

L 

a, 

QL 

9)Q, 

a + 

a. in 

n 

VLa, 

n 23 

N 

& m 

KJ 

w 

J 

\ 

w 

U 

H 

N 

U 

(u 

Y 

(u 

E: 

In 

In cu I3 I3 

a, 

c, 

CrJ 

0: 
4 

aww 

om 

-3 

07 

9T 

(u 

ww 

cntcnm 

77 

??' 

n 

W 

cn 

un 

0 

c 

W 

u7- 

0 

7. 

W 

(u 

W 

- W I- m 

I 

0 

X 

m 

I1 

w 

c 

oco 

-W 

9'4 

m Ln 

NI1 

ww 

t-tmco 

?? 

7. 

I 

0 

X 

N 

II 

w 

c 

c 

I 

0 

e 

X 

II 

w 

7 

7 

I 

0 

X 

0 

I 

w 

c 

v! 

- 

c 

I 

0 

X 

N 

c 

B 

w 

cc 

I1 

ww 

coo 

cntY? 

c, 

Q) --i 

(d 

L 

5 

L 

Q) 

I 

3 

4 

n 

m .. 

II 

ww 

=aam 

?? 

=r -N 

II 

ww t-a 

-(u 

eI 

.'. 

Ln* 

(u* 

I* w* o* 

Ln* 

?*, 

f L 

a 4 + 

mL mL 

Q)Q) Q)Q) 

a In. a In. 

f 

a + 

a la 

mL 

Q)Q) 

G4 

0 

m 

a 4 

h 

e 

N 

I 

v 

un 

m 

7 

W 

u3 

d 

(u Io N I (u 

& (u 

pc 

D 

2 Ln 

N 

W 

e 

m 

m 

G' 

m 

N 

cn 

0 

d 

Ln 

W 

U 

w 

(u 

U 

(u - Ln 

Y 

N 

c I