General Disclaimer

One or more of the Following Statements may affect this Document

This document has been reproduced from the best copy furnished by the 

organizational source. It is being released in the interest of making available as 

much information as possible.

This document may contain data, which exceeds the sheet parameters. It was 

furnished in this condition by the organizational source and is the best copy 

available.

This document may contain tone-on-tone or color graphs, charts and/or pictures, 

which have been reproduced in black and white.

This document is paginated as submitted by the original source.

Portions of this document are not fully legible due to the historical nature of some 

of the material. However, it is the best reproduction available from the original 

submission.

Produced by the NASA Center for Aerospace Information (CASI)
- 

r

.— I _%1

PERFORMANCE ANALYSIS OF A

CONCATENATED CODING SCHEME FOR ERROR CONTROL

ocS 1^8^

RECEIVED

NASA Sn F RC111r 9 per.

- ^Z50

Technical Report

to

NASA

Godda-d Space Flight Center

G.<enbelt, Maryland

(NASA-CH-175345) PERMANENCE ANALYSIS OF A N84-15422

CONCATENATED CODING SCHENE FOR ERROR CCNTROL

(Illinois Inst. of Tech.) 15 P

HC A 02/4F A01 'SCL 17B Gnclas

G3/32 15205

Grant Number NAG 5-234

P

Principal Investigators

Daniel J. Costello, Jr. Shu Lin

Department of Electrical Engineering Department of Electrical Engineering Illinois Institute of Technology University of Hawaii at Manoa

Chicago, Illinois 60616 2540 Dole Street

Honolulu, Hawaii 96822

September 6, 1983
PERFORMANCE ANALYSIS OF A

CONCATENATED CODING SCHEME FOR ERROR CONTROL

Tadao Kasami Shu Lin

Osaka University University of Hawaii at Manoa

Toyonaka, Japan Honolulu, Hawaii 96822

ABSTRACT

In this paper, a concatenated coding scheme for error control in data

communications is analyzed. In this scheme, the inner code is used for both

error correction and detection, however the outer code is used only for error

detecticn. A retransmission is requested if the outer code detects the presence

of errors after the inner code decoding. Probability of undetected error is

derived and bounded. A particular example, proposed for NASA Planetary Program,

is analyzed.

*This project is supported by NASA Grant No. NAG 5-234.
1. Introduction

Consider a concatenated coding scheme for error control for a binary symmetric channel with bit-error-rate E<1/2 as shown in Figure 1. Two linear block

codes, C and Cb , are used. The inner code CV, called frame code, is an (n,k)

code with minimum distance d f . The frame code is designed to correct t or fewer

errors and simultaneously detect a(a>t) or fewer errors where t+a+l<d f . The outer

code Cb is an (nb ,k b ) code with

n b = mk .

The outer code is designed for error detection only.

The encoding is done in two stages. A message of k b bits is first encoded

into a codeword of n bits in the outer code C b . Then the n-bit word is divided

into m k bit segments. Each k bit segment is encoded into an n bit word in the

frame code C f . This n-bit word is called a frame. Tnus, corresponding to each

k b-bit message at the input of the outer code encoder, the output of the frame

coda encoder is a sequence of m frames. This sequence of m frames is called a

bl ock. A two dimensional block format is depicted in Figure 2.

The decoding consists of error correction in frames and error detection in

m decoded k-bit segments. When a frame in a block is received, it is decoded

based on the frame code C f . The n-k parity bits are then removed from the

decoded frame, the k-bit decoded segment is stored in a buffer. If there are

t or fewer transmission errors in a received frame, the errors will be corrected

and the decoded segment is error free. If there are more than t errors in a

received frame, the decoded segment contains undetected errors. After m frames

of a block have been decoded, the buffer contains m k-bit decoded segments.

Then error detection is performed on these m decoded segments based on the outer

code Cb . If no error is detected, the m decoded segments are assumed to be error

free and are accepted (with the n b -k b parity bits removed) by the receiver. If

-2-
aR'GINAL PAGE IS

.

OF PppR 

Q11ALITV

the presence of errors is detected, the m decoded segments are discarded and

the receiver requests a retransmission of the rejected block. Retransmission

and decoding process continues until a transmitted block is successfully

received. Note that a successfully received block may be either error free or

contains undetectable errors.

The error control scheme described above is actually a combination of

forward-error-correction (FEC) and automatic-repeat-request (ARQ), called a

hybrid ARQ scheme [1]. The retransmission strategy determines the system

throughput, it may be one of the three basic modes namely, stop-and-wait, goback-N or selective-repeat. In this report, we are only concerne ,: with the

reliabiliLy of the proposed error control scheme. The reliability is measured

in terms of the probability of undetected error after decoding.

An example scheme, proposed for NASA Planetary Program, is analyzed.

2. Probability of Undetected Error for the Frame Code

For a codeword v in the frame code C f , let w(—v), w (1) C—v) and 

w(2) 

(7) denote

the weight of v, the weight of information-part of v and the weight of paritypart of v respectively. Clearly w(v)=w(')(v)+w(2)(—v). If a decoded frame contains an undetectable error pattern, this error pattern must be a nonzero codeword in Cf . Let e0 be a nonzero error pattern after decoding. Since e 0 is in

Cf , we have

and

w(1)(—e 0 ) + w(2) (0 ) ? d f

(1)

w(1)(e0) > 1 (2)

The probability P f (—e0 ,c) that a decoded frame contains a nonzero error vector

e 0 after decoding is given by [2],

t min(t-i,n-w) w n-w w-i+d )n-w+i 

P f(O . e ) = I I (i)(j )e (1-e d (3)

i=0 J--%i

-3-
UNIGMAL PAGE 19

where w=w(—e0 ) . OF POOR QUALITY

Let P (d) (E) denote the probability of undetected error for the frame code.

Let ( A (w

f) , 0<w<n} be the weight distribution of C f where Awf) denotes the number

of codewords in C with weight w. Then, it follows from (3) that

P(f)(E) -

A(f)

min(t^i, n-w)(u)(n-w)Ew-i+j(1-E)n-w+i-j

(4 )

ud

W=0 

w 

i=0 j=0 j

Hence, if we know the weight distribution of the frame code, we can compute

Pud ) (E) from (4).

Let Q t(w,E) denote the right-hand side of (3). For w<n-1-j,

(w+l)(n-w-1) W+l-i+j (

)n-w-1+i-j

i j

1-E

_ w+l n-w E < w+l E (5)

(w)(n-w)Ew-,+j (1-E)n-w+i-j w+1-i n-w 1-E — ,w+1-t 1 -E

i j

Since w>2t+1, we have that

w+1 2t+2 (6)

W+ -t - t+2

It follows from (5) and (6) that, for E < t+2

— Tt+T

Q t (w+ l,E) < Q t (W,E) . (7)

For 1<i<k, let

W(i) = minfw (—v): vEC f and w (l) ()=i} (8)

Then we see readily that

W(i) > max(d f ,i) (9)

If C is an even-weight code and i is odd, then

W(i) > max(d,i+l) . (10)

It follows from (3), (7) and (9) that, for 0<E<(t+2)/(3t+4),

Pf(_eo.E) < Qt(W(w(1)(e0)),E) < Q t ( ma x( d f , w(1) (p)), c ) (11)

-4-
For E«1/n, we can see from (3) and (11) that OF POOR QUALITY

( ^f)E d-t

(1-E)

n-d

f+t for w (1) ^O )<d (12)

P f^O .E) < \

w(1)^O)

t

Ew(1)(_e0)-t(1-E)n-w(1)(e0)+t, otherwise . (13)

3. Probability of Undetected Error for the OutEr Code

Recall that a codeword in the outer code C b consists of m k-bit segments.

At the receiver, error detection is performed on every m decoded segments based

on Cb . Let Pb (_e, E) denote 0e probability that the decoded word contains an

undetectable error pattern a (a nonzero codeword in C b ). For a nonzero codeword

v in Cb , we define the weight configuration of v as the sequence of nonzero

weights of component segments of v, arranged in ascending order. For an undetectable error pattern a with weight configuration (il,i2,...)ih), it follows from

(11) that

h

P b (.E) ^ H Qt ( W ( i R ).E)L 1 - P^d)(E)]m-h (14)

R=1

It follows from (12), (13) and (14) that the power of E in the right-hand side

of (14) is

h

W(i^) - th .

k=1

Suppose that the frame code C is an even-weight code. For any positive

integer i, define W'(i) as follows:

W'(i) = d if i< d f;

w (i) = i if i > d and 1 is even;

W'(i) = i+1 , otherwise .

For an error pattern a of weight configuration (il,i21...'1h), definE the order

t_

O E D) of a as follows:

(15)

(16)

' h

O E D) _ W' (i^) - th .

- R=1

1

-5-

(17)

J
ORIGINAL PA„' ES

OF POOR QUALITY

If 0C(—e)>w(_e), we say that a has a good weight configuration and a is a good

jerror pattern. On the other hand, if OE(_e)<w(_e), a is said to be a bad error

pattern.

Let p(b) (c) be the probability of undetected error for the outer code ud

Cb . In order to obtain a good evaluation of P

u

d ) (E), we need to estimate the

proportion of bcd error patterns and that of good error patterns to the error

patterns of the same weight for several low weights. Unless the former is negligibly smaller than the latter, the error correction of the frame code does not

make sense.

For 1<j1<j2<...<jh<' consider the set of codewords in C b where nonzero

bits are confined in j 1 -th segment, j 2 -ch segment,..., and the j h -th segment.

This set of codewords forms a subcode of Cb , called a (j l' j 2' " ''jh)-subcode .i

of Cb . If Cb is a cyclic or shortened cyclic code, all (j1,j2,...,jh)-subcodes

of C for a given h with the same j2 j 1' j 3 -j 2'" ''jh-jh-1 are equivalent codes

and are called h-segment (j 2 -j 1' j 3 -3 2'" ''jh-3h-1) subcodes of Cb.

Consider a (j 1 ,j 2 ,...,j h )-subcode of Cb . Let i 1 ,i 2 ,..., and i h be a set of

..

integers for which O<i Q<n with I<z<h. Let A 

j1,j2,. i1,i2,. ,3h

'ih denote the number of

codewords in the (j i1 j 2 ,...,j h )-subcode whos_ weight in the j th segment is

i Z for 1<Z<h. If we know segment-weight distributions for all h-segment subcodes of C b , we can obtain an upper bound on P(d ) ( E) from (14). If E «1/nb , a

small h is sufficient to attain a good Evaluation of P (b) W. This will be

ud

illustrated by an exampie in the next section.

4. Examples

Consider the concatenated coding scheme proposed for the NASA planetary command system in which both the inner (frame) code and outer code are shortened

i

Hamming codes. The frame code C f is a distance-4 Haoming code with generator

polynomial,

-6-
ON161"NAL TV

g (X ) _ (X+ 1) (X6 +X+1) = X 7

+X6 +X2

+1 OF POOR QUALITY

where X6+X+1 is a primitive polynomial of degree 6. The maximum length of this

code is 63. This code is used for single error correction. The code is capable

of detecting all the error patterns of double and odd number errors. The outer

code is also a distance-4 shortened Hamming code with generator polynomial,

g

(X) = (X+1)(X15+X14*X13+X12+X4+X3+X2+X+1)

= X16+X12+X5+1

where X15+X 14+X 13 +X 12

+X4 +X3 +X2

+X+1 is a primitive polynomial of degree 1.`. This

code is the X.25 standard for packet-switched data networks. The natural length

of this code is 2 15 -1 = 32,767. But maximum length n being considered is 2,048

bits. The 16 parity bits of this code is used for error detection only.

To evaluate P (b) (E), we need to know the weight configurations and orders ud

cf error patterns for Cb . The weight configurations and orders of errors patterns

of weights 4, 6 and 8 are listed in Table 1. The order of an error pattern e,

0 (e), is at least

W(e) - L w ( ) /4 j . (18)

which occurs for the weight configuration

(4,4,...,4,a+(—e)-4Lw(—e)/4j+4)

where Lxj denotes the integer no greater than x.

Suppose that n>7 and

E <_

 1/2n . (19)

Then (1-E) n >1/2 and (1- E) /E>13. Note that

Q (W,E) 1/w = E w(1-E n+1 1/w 

1 +

E + nn=w ( E ^2 1

/W1 (20)

E c W(1- EW 1-E'

which decreases mcnotonically as w increases for 4<w<n. Hence

-7-

- - 
I

_ UNIGiNAL. PAGE IS

Q1(w',E)1/w' < QI(w.c)1/w OF POOR QUALITY (21)

for 4<w<w'<n. It is easy to check that

QI(4,c) < Q I ( 4 .c)

1/2

 < Q I ( 4 ,c)

1/3

 < Q 1 ( 6 ,c) 1/6

(22)

It follows from (14), (21) and (22) that

Q1(4, c) w

1

(4,E) w (—e)/4 , if w (—e) is a mult 4 ple of 4

Pb(e.c)

` Q 1 (4,E) Lw (e)/4J-1Q1(6,E), otherwise (23)

Let

e ! Q 1 (4,c) 1/4

(24)

Then, 4t follows from (20) that

E < 1.5 E3/4 (26)

.let {A( b) } be the weight distri',ution of the outer code C b . Suppose that

A4 and Al of the one-segment subcode of C b are known besides {A^ b) }. Then it

follows from (14), (21) to (24) and Table I that

P^d ) (E) < m A4 

^ + ( A 4b )- m A4): + m A6Q1(6,E)

Lnb/4 J

+ ( A(.b) -m A 1 1^ + A(b i

6 6'

i12

4i

l(nb-2) /4J

(b) —4i-4

+ 1

A4i+2 

E Q I (6, E ) (27)

i=2

where m is the number of segments per block (see Figure 2) and 2<m<52.

Let A" i be the number of codewords of weight i in two-segment (1j) subcode of C for 1<j<m. If A4, A6, A8 and A

i

'^ with 1<j<m and 4<i<8 are known,

then p(b) (c) can be bounded as follows:

ud

-8-
' m

Pud)(E) < m A4 E 4 + (m-j)4'j - 2A4)^ (A

i J=2

+ [A4)b - mA4 - 

m

T (m- j )( A4' j

 - 2A1) c

J-2

ORIGINAL PAGE IS OF POOR QUALITY

m

• m A6Q1 ( 6,e) + I (m-j)(A6' j 

- 2A6)E

j-2

• [A6b))- m A6 - Z -m (m- - 2A6)]^12

j=2

m

• m A8 Q 1 ( 'J 8 ,E) + j 2I(m - j )(A8JE_ - 2A

+ [A(b)-m A8 - ^(M-j)(A8'J - 2A1 E12

j=2

L( nb- 2 )/ 4 .l Lnb/4j

4i+2 E Q1(6,E)i-3 4i '

If Ai'j2i for 2<j<m and 4<il+i2<8 are also known, a better bound on P

2 ud

can be obtained,

p(b)(E) < 

a4 b

+ (a l 3 + a 3 1 + a2,2

)e8 + Al E12

+ a 6Q 1 (6,e) + (a2 4 + a 4

2 + a33)e8

+ (a1,5 + a5'1) 'EQ1(6,E) + T6(b)12

+ a (8,c) + (a1,7 + a

7,l

)-4 Q1(8,E)

+ (a2,6 + a

6,2 + a 3,5 + a5,3)E: 4 Q1 ( 6,c) + a4'4 -E$

+'A e A(b) —4i-4 (b)—di

8 4i+2 Q1(6.c) + 1 A41 E

i=2 i=3

'Where

a =m Ai1

m

l,j a i1J2 = j=2 (m-j) Ai1J2 (30)

-A b) = A

(

b)-a. i

it+i2=i ail'i2

( -9-

low

(28)

(29)
ORIGINAL PAGE IS

OF POOR QUALITY

The weights Ai, Ai'j and A1

;

1

1 1 2 can be computed from those of the dual code of

Cb by the IacWilliams' identities [3].

If finer weight structure of C and C is known, further improvement on

bounding Pud ) (c) can be made. Let A(f,b) denote the number of codewords v in

C such that w (1) (v) = i, w (2) (—v)=j and the vector consisting of the first k

bits of v and n b -k zeros is a codeword in one-segment subcode of C b . Better

bounds on P ( d ) (E) can be obtained by replacing m A4 E , m A6 Q 1 (6,E) and

1 n-k n-k 1 n-k

M A8 Q 1 (8,E) by m I A4

(fb) 

Q 1 ( 4+j ,E) . m

A(fb 

) Q i (6+j,E, and m 1 A

(fb) 

Q1(8+J,E)

j = 0 j=0 j . 0 '

respectively in (21), (28) and (29).

For moderate code length n, it may be feasible to compute Ai f^ b)

Evaluation based on (27) for E = 10-5 is given in Table 2. Evaluation of F (d ) (E) based

on (28) or (29) will be made in the next report.

REFERENCES

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

Applications, Prentice-Hall, New Jersey, 198

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

Holland, Amsterdam, 1977.

3. J. MacWilliams, "A Theorem on the Distribution of Weights in a Systematic

Code," Bell System Technical Journal, Vol. 42, pp. 79-94, 1963.

-1C-
weight weight configuration GE(e)

4 4 3 "bad"

1, 3 6 "good"

2, 2 6 "good"

:, 2 9 "good"

12 "good"

6 6 5 "bad"

1, 5 8 "good"

2, 4 6

3, 3 6

1, 1, 4 9 "good"

1, 2, 3 9 "good"

2, 2, 2 9 "good"

1, 1, 1, 3 12 "good"

1, :, 2, 2 12 "good"

8 8 7 "bad"

1, 7 10 "good"

2, 6 8

5 8

4, 4 6 "bad"

1, 1, 6 11 "good"

1, 2, 5 11 "Ooo(-

1, 3, 4 9 "good"

2, 2, 4 9 "good"

2, 3, 3 9 "good"

others > 12 "good"

i

Table 1

OHI(, M'A.. PAGE 19

OF POOR QL'ALIT

-11-
ORMINAL PAGE IS

Table 2 OF POOR QUALITY

E - 10-5

nb Pud)(£) nb Pud) (E)

160 .6809 x 10 -11 1120 .9067 x 10_8

192 .1411 x 1G-10 1152 .no/ x 10-7

224 .2086 x 10 -10 1184 .1115 x 10-7

256 .3013 x 10 -10 1216 .1231 x 10-7

288 .4802 x 10-10 1248 .1356 x 10-7

320 .7277 x 10-10 1780 .1489 x 10-7.

352 .1058 x 10 -9 1312 .1632 a 10-7

384 .1489 x 10' 1344 .1734 x 10-7

416 .2038 x 10- '1 376 .1945 x 10-7

448 I .2722 x 10 -9 1408 .2117 x 10-7

480 .3561 x 10 -9 I 1440 .2299 x 10-7

512 .4576 x 10-9 1472 .24 _ x 10-7

544 .5789 x 10 -9 1504 .2696 x 10-7

576 .7222 x 10 -9 1536 .2912 x 10-7

608 .8899 x 10

-9

1568 .3139 x. 10-7

640 .1084 x 10-8 1600 .3379 x 10-7

672 .1307 x 10 -8 1632 .3631 x 10-7

704 .1563 x 10 -8 1664 .3896 x 10-7

736 .1853 x 10 -8 1696 .4174 x 10-7

768 .21¢0 x 10 -8 1728 .4467 x 107

800 .2547 x 10

-8 1760 .4773 x 10-7

832 .2957 x 10 -8 1792 .5093 x 10-7

864 .3413 x 10

-8 1824 .5428 x 10-7

896 .3917 x 10 -8 1856 .5778 x 10-7

928 .4473 x 10 -8 1888 .6144 x 10-7

960 .5084 x 10 -8 1920 .6525 x 10-7

992 .5/53 x 10 -8 1952 .6923 x 10-'

102 v. .6482 x 10 -8 1984 .7337 x 10-7

1056 .7275 x 10 -8 -016 9 .7768 x 10-7

1088 .8136 x 10-8 2048 .3216 x 10-7

-12- 
Figure 1 A concatenated coding system
m

Frame

i

r

)I.

ORIG

OF PO00R QUALITY

Frame ParityCheck Bits

Figure 2 Black format

f^

A