RELIABILITY AND THROUGHPUT ANALYSIS OF A

CONCATENATED CODING SCHEME*

Robert H. Deng

Dept. of Elec. & Comp. Engr.

111. Inst. of Tech.

Chicago, IL 60616

Daniel J. Costello, Jr.

Dept. of Elec. Engr.

University of Notre Dame

Notre Dame, IN 46556

ABSTRACT

In this paper, the performance of a concatenated coding scheme for error

control in ARQ systems is analyzed for^both random-noise and burst-noise channels. In particular, the probability of undetected error and the system

throughput are calculated. In this scheme, the inner code is used for both

error correction and error detection, and the outer code is used for error detection only. Interleaving/deinterleaving is assumed within the outer code.

A retransmission is requested if either the inner code or the outer code detects the presence of errors. Various coding examples are considered. The

results show that concatenated coding can provide extremely high system reliability (i.e., low probability of undetected error) and high system throughput.

CSCL 17B Uflcias

G3/32 05151

kThis -research was supported by NASA Grants NAG5-234 and NAG5-557.
RELIABILITY AND THROUGHPUT ANALYSIS OF A

CONCATENATED CODING SCHEME

1. INTRODUCTION

In a companion paper [1], the probability of undetected error of a

specific concatenated coding scheme on a memoryless binary symmetric channel

(MBSC) was calculated. Two linear block .codes, denoted by Cf and C^, are used

in the concatenated code. The inner code Cf, called the frame code, is an

(n,k) binary block code with minimum distance df. The frame code is designed

to correct t or fewer errors and to simultaneously detect X(X > t) or fewer

errors, where t + X + 1 < df [2]. The outer code is an (n^, ky,) binary block

code with

% -Ink- , (1)

where m, a positive integer, is the number of frames. The outer code is

designed for error detection only.

No interleaving/deinterleaving within the concatenated coding scheme was

assumed in [1]. In this paper, we modify the coding scheme of [1] by assuming

interleaving/deinterleaving within an outer code word. In addition, we extend

the analysis to include burst-noise channels.

The encoding of the concatenated code is achieved in two stages (see Fig.

1). A message of k^ bits is first encoded into a codeword of n^ bits in the

outer code Cj,. Then this codeword is interleaved to depth m. After interleaving, the n^-bit block is divided into m k-bit words for encoding by the

frame code Cf. Each n-bit code word is called a frame. The two dimensional

block fromat is depicted in Fig. 2.

Decoding consists of error correction and error detection on each frame

and error detection on the m decoded k-bit segments. When a frame is received,

It is first decoded based on the frame code Cf. The n-k parity bits are then

removed from the decoded frame. 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 the received frame, the errors

will be either detected or undetected. If the errors are detected, the decoder stops decoding immediately and requests a retransmission of the entire

block. On the other hand, if the errors in a frame are undetected, the decoded segment will be stored in a buffer and the decoder begins to decode the

next frame. After the m frames of a block have been decoded, the m k-bit decoded segments are then deinterleaved. Error detection Is then performed on

these deinterleaved segments based on the outer code C^,. If no errors are detected, the m decoded segments are assumed to be error-free, and are accepted

by the receiver. If the presence of errors is detected, the m decoded segments are discarded and the receiver requests a retransmission of the entire

block.

The error control scheme described above is actually a combination of

forward-error-correction (FEC) and automatic-repeat-request (ARQ). In this

paper, we analyze the performance of this error control scheme. Specifically,

the system reliability and the system throughput are calculated. The system

reliability is measured in terms of the probability of undetected error after

decoding.

First, by assuming the inner channel to be an MBSC with a bit error rate

(BER) e, we look at the outer channel created by the combination of the interleaver, the frame code, and the inner channel. Then we develop precise expressions for both the probability of undetected error and the system throughput. Various coding examples are considered, and one case studied in [1] is

included for comparison. Our results indicate that concatenated coding can

provide high throughputs and extremely low undetected error probabilities at

moderate values of e, and for the example considered in [1] the probability of
undetected error is slightly lower with interleaving than without interleaving. In addition, interleaving simplifies the performance analysis compared

to the analysis without interleaving, which requires a detailed knowledge of

the algebraic structure of both the inner code and the outer code. This

allows us to easily compare the performance of several different coding

examples.

Finally, the analysis is extended to a Gilbert type burst-noise channel

[3-5]. The burst-noise channel contains two states. Each state represents an

MBSC with BER GJ, j = 1,2, and ^2 » £!• The probabilities of undetected

error on burst-noise channels, as expected, degrade compared with those on

MBSCs with the same average BER, while the system throughputs remain almost

the same. For moderate values of average BER, low probabilities of undetected

error are still achievable.

2. SYSTEM PERFORMANCE ON AN MBSC

The Outer Channel Model. Let Pc(

f

)(e) denote the probability of correct

decoding for the frame code. Suppose that a bounded-distance decoding algorithm is employed. Bounded-distance decoding corrects all received n-bit

frames with t or fewer errors. When an n-bit frame with more than t errors is

detected, no attempt is made to correct the errors. Since there are (n) distinct ways in which i errors may occur among n bits,

t

Pc(

f

)(e) = Z (n) eJ(l-e)n-J (2)

j=0 J

for bounded-distance decoding.

For a code word v in the frame code Cf, let w(v) denote the Hamming

weight of v. If a decoded frame contains an undetectable error pattern, this

error pattern must be a nonzero codeword in Cf. Let eQ be an undetectable

error pattern after decoding. The probability Pf(w,e) that a decoded frame
contains a nonzero error pattern e^ after decoding is given by [1,6-8]

t min(t-i,n-w)

Pf(w,e) - z I (w)(n-w)ew-i+j(1_e)n-w+i-j ^ (3)

i=0 j=0 i J

where w = w(eo), and e is the BER of the inner channel. If e « — , then

Pf(w,e) « (

(f)

Let Pud (e) denote the probability of undetected error for the frame code.

(f)

Let {Aw , df < w < n> be the weight distribution of Cf. It follows from (3)

and (4) that

(f)

 n (f)

Pud (e) = Z AW Pf(w,e) , (5)

w=df

and "- —

(f) (f)

pud (£

) " Adf

 pf(dfie)

(f) &f 1 (^)

- AH (t ) edf-t(l-e)n"

df+t , f or e « - .

f n

Now consider any one of the m frames. If the decoded frame contains

undetected errors, the BER ea after decoding is given by

1

 n (f)

ea - - Ew Aw Pf(w,e) . (7)

n

 w=df

For e « - ,

n

1

ea *-clfAd Pf(df,e) (8)

n f

is a good approximation to ea. Let E be defined as the event that a frame

contains undetected errors. Let ea/g denote the BER embedded in a decoded

frame conditioned on the occurrence of event E. It follows from (7) that

For e « — , substituting (6) and (8) into (9) yields

n
1/n dfA#)Pf(dfte) df

ea/E » - — — t --- . (10)

Ad(f)pf(df,e) n

Now define S to be a random variable such that when h of the m frames

contain undetected errors, and the remaining m-h frames are decoded correctly,

S = h, h = 0, l,2,...,m. It follows from (2) and (5) that

m (f) , (f)

Pr{S = h} = (h)[Pud (e)lh[Pc (e)]m~

h . (11)

(O (f)

Note that (11) is not a binomial distribution because PU(j (e) + Pc (c) < 1,

i.e.; some received frames with more than t errors are detected by the frame

code.

After deinterleaving of the m decoded segments (with the n-k parity bits

removed from each frame), the BER embedded in the n^-bit block, conditioned on

S = h, is given by

e0<

h) = ea/E ' ~ » h = 0,1,2 ..... m. (12)

m

We call the channel specified by (11) and (12) the outer channel, and it is

depicted in Fig. 3. Note that eo(0) = 0. This channel can be viewed as a

block interference (BI) channel, as described in [9]. Aft, h= 0,1, 2, ...,m, is

called the htn component channel of the BI channel. Each block of n^, bits (n^,

is the length of the outer code) is transmitted over one of the nri-1 component

channels. The random variable S determined which component channel is used to

transmit a given n^-bit block.

(b)

The Probability of Undetected Error and the System Throughput. Let

djj < i < nj,} be the weight distribution of the outer code, where dj, is the

(b)

minimum distance of C^. Let PU{J (e) be the probability of undetected error

for the outer code C]j. If the n^-bit block is transmitted over the

component channel A^ of -the outer channel, it follows from (12) that
(b)

 nb (b) . n,-i

Pud (e0<

h)) - S A! (e0(h))i(l - e0(h)) b . (13)

i=db

Let PU(j(e) be the average probability of undetected error of the concatenated

code. From (11) and (13) we obtain

m

 (b)

Pud(e) - S Pr{S = h}Pud (e0(h»

h=0

m

 * (f) u (O

- Z {(h)[Pud (e>]h[Pc (e)r-h

h=l

nb (b) . n.-i

• S Ai (e0(h))i(l-e0(h)) b } , (14)

i=db

where Pc (e) and Pud (e) are geven by X-2J_. and (5), respectively.

The system throughput is defined as the ratio of the average number of

information bits successfully accepted by the receiver per unit time to the

total number of bits that can be transmitted per unit time [2]. It is determined by the retransmission strategy, which may be one of the three basic

types: stop-and-wait, go-back-N, or selective-repeat. All three basic ARQ

schemes achieve the same reliability; however, they have different throughputs. Suppose that selective-repeat ARQ is used as the retransmission strategy. The specific manner in which the receiver signals to the transmitter for

a retransmission will not be considered. It will be assumed, however, that

this backword signal is error free, and that repeat retransmissions of a block

are possible. Then the throughput of the concatenated coding system is [2]

n .£ . ]3i . (Pud(e) + Pc(e)), (15)

n nb

where Pc(e) is the probability of accepting a correct block. Note that a

transmitted block will be received correctly if and only if all m frames are

decoded correctly. Therefore,
(f)

 C n .

Pc(e) - [Pc (e)]ra = [ I (j)eJ(l - e)n-J]m . (16)

For the usual situation where Pud(e) « Pc(e), it follows from (15) and (16)

that

t

n « £ . £h .[ z (.) ej(i - e)

n

~J]m . (17)

n nb j=Q

It can easily be seen that n increases monotonically as t increases; but for

small e, n is only a weakly increasing function of t.

In order to find the relationship between t and Pud(e), we see from (14)

that

Pud(e) - m • Pud (e) • [Pc*

nb (b) , "~n.-l i

• { Z A± (e0(l))i(l - e0(l))

 b

 } , for e « - . (18)

i=db

 n

Using (6), (10), and (12), Pud(e) can be further approximated as

d, d,-t n-d,+t (f) .

Pud(e) = K • (tf) e f (1 - e)

 f

 • [Pc (e)]"1'

1

 ,

for e « - , (19)

n

where

A (f)

 nb (b) d, . d, n,-i

K = m • Ad • { I AJ, ( ?£- )i(l - ^- ) "> }

f i=dv, m.n m.n

is a constant which is independent of t. Let Q(t) denote the right hand side

of (19). Then

• - » n , for e « - . (20)

Q(t) (t+1) e n

That is, for e « — , when t increases by 1, Pud(s), the probability of unden

tected error, will increase by approximately e~*. Thus Pud(e) is a strongly

increasing function of t. For this reason, a large value of t is not desirable in such a system.
Coding Examples. In this subsection we present some concatenated code

examples whose purpose is to give a feeling for actual system performance.

Recall that the concatenated coding scheme described above is used in ARQ systems, and that the major advantage of ARQ is that it requires simple decoding

while achieving high system reliability and throughput. Therefore, only codes

which require simple decoding are chosen as examples.

Example 1. This concatenated code example has been proposed for a NASA

telecommand system, and was also considered in [1]. The frame code Cf is a

distance-4 Hamming code with generator polynomial

g(x) = (x+l)(x6+x+l) - x7 + x6 + x2 + 1 , (21)

where- x° + x + 1 is a primitive polynomial of degree 6. The natural length of

^,^_

this code is 63. This code is used for single error correction (t=l), and is

also used to detect all error patterns of weight two and some higher odd

weight error patterns. The outer code is a distance-4 shortened Hamming code

with generator polynomial

g(x) = (x+l)(x15 + x14 + x13 + x12 + x4 + x3 + x2 + x + 1)

= x16 + x12 + x5 + 1 , (22)

where x*5 + x14 + x13 + x12 + x4 + x3 + x2 + x + 1 is a primitive polynomial

of degree 15. This code is the X.25 standard for packet-switched data networks [10]. The natural length of this code is 215 -1 = 32,767. In this example, a shortened code of maximum length 3,584 bits is considered. This code

is used for error detection only. We assume that the number of information

bytes (IB) in a frame is between 3 and 7, that is, the inner code can also be

shortened.

To obtain a precise result for Pud(£)>

 a computer program was written to

help determine the reliability of the proposed concatenated coding scheme. We

found that if only one frame contains a weight 4 undetected error pattern,
then this error pattern can always be detected by the outer code. Thus (14)

can be modified as follows:

ra _(f ) (f ) .

 nb (b) _ . _ n -i

PudCO - (i)Pud (e>[Pc CO]TM-1 • I At (eo(l))1(l-eo(D)

 b

i=db

m

 m (f) , (f) .

+ S {(h)[Pud (OJh[Pc (E)]m-

h

h=2

n

b (b) . n.-l

• Z Ai (e0(h))i(l - e 0 (h)) & } , (23)

i=db

where

_(f)

 n (f)

Pud (e> » Z AW Pf(w,e) , (24.1)

w=df+l

and ^

n

 "~"(f)

_ (1/n) E wAw Pf (w,e )

e n (l) • w=df+l _ . 1 . (24.2)

Pud

Results for the probability of undetected error PU(j(e), based on (23),

and the system throughput n> are plotted in Fig. 4 for m = 64, IB = 7, and for

m = 24, IB = 4, respectively, where we have used the method in [11] to obtain

(b)

 nb (b) . iL-1

Pud (e0(

h

» -Z

 Ai (eoW^Cl - £0(h

))^ •

i=db

Comparing the results here with those obtained in [1], we see that

interleaving slightly improves the system reliability. For example, for m =

64, IB = 7, and e = 10~5, Pud(s) = 6.7 x 10~22 with interleaving, while 8.05 x

IQ-22 < pud(e) < 8.78 x 10~19 without interleaving [1].

The example described above can be altered by allowing the frame code to

do error detection only (i.e., t = 0) . In this case, PU(j(e) and n are shown

in Fig. 5.

Example 2. The same frame code and outer code are employed as in Example

1. However, the inner channel is assumed to be an AWGN channel with BPSK

10
modulation and the frame code is decoded by using the Viterbi decoding

algorithm with repeat request and infinite demodulator output quantization

[12]. Let u, a positive real number, be the retransmission metric threshold

(f)

of the algorithm [12] . Let PU(J , P<j , and ea denote the probability of

undetected error, the probability of detected error, and the BER after

decoding, respectively, for the frame code. Then [12]

QC df + u ) exp( l d£)T(x) |x = exp(_ l } , (25)

Q( df - u. ) exp( Si df)T(X)|x . exp(_ &. ) , (26)

V

OT7 f OT7 ^---.T? ^T/VV ^ Y — 1 "M j _i_ / "N \ / ^*N- JN^^V-^-*^ / i ^N /O7\

Jdf + u^ _tt) exp( J^d£) —— |x. exp(-/) . (27)

NO TM No

 No d x ao

where i 2

Q(X) = -±- f» e~z /2dz , (28)

— Jx

n

 ,

T(X) - E A£ X1 , (29)

l-df

i , (30)

3Y i=df

is the channel symbol signal energy-to-noise power density ratio, and

B£ is the total number of nonzero information bits in all codewords of

weight i. From (25) and (26) we see that the probability of correct decoding

for the frame code is

! - P . for ,«'« ,«>. (31)

The probability of undetected error of the concatenated code, PU(j» and the

system throughput, n, can be computed by using (25) - (31) in (23) and (15).

In (23), e0(h), h = 2,3 ..... tn, is given by (9) and (12), and

11
V

" ^TJ TJ

—H- ) exp( -^ df)(

NO

 No i-df+l

(32)

exp( * df )(

N0 i=df+1

' (33)

Both PU(J and ri are shown in Fig. 6 for u = 4, where EN/NO and e are related by

the equation

e = QC^/^L ) . (34)

The influence of the value of u on the system performance is obvious.

(f)

For larger values of u, from (25), (26>,^jind (31), the probabilities Pucj and

(f)

Pc become smaller, and consequently the probability of undetected error and

the system throughput are lower.

Example 3. The outer code is again a shortened distance-4 Hamming code

with generator polynomial given by (22). The frame code is an (n,n-l)

single-parity-check code. The frame code has a minimum distance of 2, and is

used for error detection only. The frame code can detect all odd weight error

patterns. The weight distribution of the frame code can be calculated from

A2i - (21 > + <2i-l> ' i = 1,2,3,..., , (35.1)

Aj - 0 for all odd j , (35.2)

n

where (^) = 0 for k < 0 and k > n, and x denotes the integer part of x.

Because the outer code can detect three or fewer errors, if only one

frame contains a weight 3 or less undetected error pattern, then this error

pattern can always be detected by the outer code. Hence, (23) is used to

compute the probability of undetected error, where

n

Pud(e) = Z A2j eJ(l - e)n- (36)

j=2

12
is the probability of undetected error when the undetected error pattern has

weight greater than 3, and

n

~2

F0(l) - j=2

 n

 . 1 . (37)

" Ff^ TM

Pud (£) '

Fig. 7 shows the probability of undetected error PU(j(e) and the system

throughput n for this example.

From Figures 4-7, we observe that the performance of a particular

scheme depends strongly upon the channel noise conditions. Therefore, we

canno-t say that a particular one of the above schemes is "best". However, we

can draw several conclusions which will be discussed below.

From Figures 4 and 5, we can see the tradeoffs between the probability

of undetected error and the system throughput obtained by varying the number

of correctable errors t in the frame code. Smaller values of t always result

in a lower probability of undetected error, and, therefore, a higher system

reliability. But as the channel BER gets higher, the system throughput degrades rapidly for small t. The system throughput is less affected by t if

the channel BER is small.

Figure 6 shows the advantages of a Viterbi decoded (soft decision) frame

code over an algebraically decoded (hard decision) frame code. The Viterbi

decoding algorithm makes the system much more flexible in trading between system reliability and throughput by simply changing the value of u. Varying u

can be viewed as a generalized method of "varying t" for algebraic decoding of

the frame code. From comparing Figures 4-7, we see that lower inner code rates

provide higher system reliabilities but lower system throughputs. We conclude

that, at moderately lower BER's, the concatenated coding scheme is capable of

achieving high system throughputs and extremely low undetected error probabilities.

13
3. SYSTEM PERFORMANCE ON A BURST-NOISE-CHANNEL

Channels with memory often occur in practice. Errors on these channels

tend to occur in bursts, and hence they are called burst-noise-channels. In

this section we extend the performance analysis of the concatenated coding

scheme to burst-noise-channels.

The Inner Channel Model. The generalized Gilbert type channel [3-5], as

shown in Fig. 8, is used as our inner channel model. There are two states in

the model. Each state represents a BSC. State 1 is the "quiet" state, where

the BER is e^. State 2 is the "noisy" state, where the BER is ££, and £2 ^

ej_. The transition probabilities between states are P^ = Pr{l-»-2} and P£ =

Pr{2-»-l} (see Fig. 8). The probabilities.^ remaining in states 1 and 2 are

q^ = I-PI and q2 = l-P2i respectively. To simply the model's treatment, we assume that one transition time in the model corresponds to the transmission of

one frame of length n bits, i.e., the noisy bursts last for a multiple of the

transmission time of a frame. This is a reasonable assumption for channels

where burst lengths are usually long compared to the transition time of one

frame. The average burst length is then [3]

IT = — frames, (38)

?2

or

 - - 1

H = Ln = — n bits, (39)

^2

the average BER is

e" » —-— (P2ei + Pl£2> » (40)

Pl+P2

and the steady state probability of being in the noisy state is

Pn = ^L • (41)

e2~el

Four parameters govern the model. They can be chosen to be L, e, Pn, and the

high-to-low BER ratio £2/el*

14
(f) (f)

The Outer Channel Model. Let Pc (M), Pud ( £j ) »

 e aj» anc* e ai/E» J=

denote the probability of correct decoding for the frame code, the probability

of undetected error for the frame code, the BER in a decoded frame, and the

BER embedded in the decoded frame conditioned on the decoded frame containing

undetected errors, respectively, when the frame is transmitted in state j.

(In the following, we will always use the subscript j, j=l,2, to denote that a

(f) (f)

frame is transmitted in state j.) Then Pc (ej)> ?ud (ej)»

 eaj» anc* eai/E are

given by (2), (5), (7), and (9), respectively, with e replaced by e-j, j=l,2.

Now define EJJ n 0 < Jl < h < m, to be an event such that h of the m

decoded frames contain undetected errors (the other m-h decoded frames are

error free) and 9, of the h frames containing undetected errors are transmitted

in state 2 of the inner channel. Let Pr{% h^ ^e

 fc^e probability that event

E^ h occurs. Then, after de inter leaving of the ra segments (with the n-k

parity bits removed from each decoded frame), the BER embedded in the nj,-bit

block, conditioned on the occurrence of event E£ ^, is given by

0 < i < h < m . (42)

We call the channel specified by (42) and the probability distribution

Pr{E£ }j} the outer channel (see Fig. 9).

The Probability of Undetected Error and the System Throughput . If the

n^-bit block is transmitted over the component channel A£ ^ of the outer

channel, the probability of undetected error of the outer code is

(b)

 nb (b) , n,-i

Pud («o<*i,h» " * Ai (eoffl.h))1^ -eoO^.h))13 • (43)

i=db

Based on the above outer channel model, the average probability of undetected

error of the concatenated code can be expressed as

m h (b)

Pud = X Z P{E1>h> Pud (e

h=0 1=0

15
For large m, the computation of (44) is very complex and time consuming.

To reduce the computational work to a manageable load, we seek an approximation to (44). Define

It follows from (42) that

1 A

and equality holds when ei and £2 are equal, i.e., when the inner channel is

(b) 1

an MBSC. Assuming that Pud (e) is an increasing function of e , 0 < e < — , we

obtain from (44) and (46)

*

 h (b)

Pud < E E Pr {E. h> Pud (e0(h))

h=0 l=Q \_

m

 (b)

 h

• E Pud (e0(h» E Pr{E£>h}

h=0 fc=0

m

 (b)

= E Pud (e0(h)) fj(h) , (47)

h=0

where

A h

S(h) - E Pr{E£ h} , 0 < h < m . (48)

1=0

is the probability that h of the m decoded frames contain undetected errors

(and the remaining m-h decoded frames are error free).

S(h) can be readily computed by a recursive method. To find g(h), we

model the decoded frame status as a Markov chain. In state j, j=l,2, the

(f)

decoded frame contains an undetected error with probability Pud (e j) and is

(f)

error free with probability Pc Ce-j)« Define G(h,m) = Pr{h of the m decoded

frames contain undetected errors/the inner channel starts in state 1} and

B(h,m) = Pr{h of the m decoded frames contain undetected errors/the inner channel starts in state 2}. By applying a similar argument as in [5], we obtain

16
g(h) - -2 — G(h,ra) + - - B(h,m) , 0 < h < m . (49.1)

Pl+P2

 P1+P2

G(h,m) and 8(h,m) can be found recursively from

(f) (f)

G(h,m) = G(h,m-l) qiPc (GI) + B(h,m-

(f)

G(h-l,m-l)qiPud (n) + BCh-l.m-DPiPud (EI) , (49.2)

(f)

B(h,m) = B(h,m-l)q2Pc (e2) + G(h,ra-l)P2Pc (e2)

B(h-l,m-l)q2Pud

)(e2) + G(h-l,m-l)P2Pud)

(e2) , (49.3)

where

G(O.l)

2) , (49.4)

and G(h,m) = B(h,m) = 0 when h < 0 or h > m.

Note that if eai/£ « ea2/E»

 t*ie uPPer

 bound of (47) is very close to

(44). Fortunately, this is usually the case for 0 < ei <£2 < — , especially

for small EI and e2, for then eai/E " ea2/E

 a

To evaluate the system throughput, again assume that selective-repeat ARQ

is used. In order to simplify the problem, we assume that retransmissions do

not depend on the previous inner channel state. This is a reasonable assumption if the channel round-trip delay is large. Then the system throughput is

given by (15), where Pc, the probability of correct decoding, can be found

from

Pc =-^ — G(m) +-^ - B(m) , (50.1)

and where /f ) tf \

G(m) = G(m-l) qiPc (£l) + B(m-l)PiPc (EI), (50.2)

(f) (f)

B(m) - B(m-l) q2Pc (e2) + G(m-l)P2Pc (e2) , (50.3)

17
(f) (f) = Pc (ei) , B(l) = Pc (e2) - (50.4)

Coding Examples on a Burst-Noise-Channel. For the inner channel, we

choose Pn = 0.1, L = 5, and £2/el

 = ^ an<* 1000 for our example's.

Example 4. The same frame and outer codes are used as in Example 1. The

probability of undetected error, PU(j) and 'the system throughput, n, are

plotted in Figures 10. a and 10. b for t = 1, and in Figures 11. a and 11. b for

t = 0, respectively.

Example 5. The same coding scheme is used as in Example 3. PU(j and n

are shown in Figures 12. a and 12. b.

The performance of the concatenated coding scheme on burst-noise-channels

depends greatly on the channel parameters^ especially on the high-to-low BER

ratio, e2/ei- As shown in Figures 10.a-12.b, for a given average BER e, with

the other parameters fixed, as the e2/ei ratio becomes large, the system performance becomes poor. Our results indicate that on a burst-noise-channel,

for a given average BER, the system reliability degrades significantly, while

the system throughput remains about the same, compared with the same coding

scheme on an MBSC. For moderate values of average BER, high system reliability and throughput are still achievable.

4. CONCLUSIONS

In this paper, the performance of a concatenated coding scheme for error

control in data communications is analyzed. By developing a block interference channel model for the outer channel, both the undetected error probability and the system throughput of the concatenated coding scheme were calculated for burst-noise channels as well as random-noise channels. The performance of several specific coding examples was compared. Results indicate that

high throughputs and extremely low undetected error probabilities are achievable using this scheme.

18
5. REFERENCES

[1] T Kasaml, T. Fujiwara, and S. Lin, "A Concatenated Coding Scheme for

Error Control", submitted to IEEE Trans, on Communications.

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

Applications, Prentice-Hall, NJ, 1983.

[3] L. R. Lugand and D. J. Costello, Jr., "A Comparison of Three Hybrid ARQ

Schemes Using Convolutional Codes on, a Non-Stationary Channel,"

GLOBECOM'82 Conf. Rec., C8.4, Miami, FL, Nov. 29-Dec. 2, 1982.

[4] E. N. Gilbert, "Capacity of a Burst-Noise Channel", Bell Syst. Tech. J.,

39, pp. 1253-1265, Sept. 1960.

[5] E. 0. Elliott, "Estimates of Error Rates for Codes on Burst-Noise

Channels", Bell Syst. Tech. J., 42, pp. 1977-1997, Sept. 1963.

[6] E. R. Berlekamp, Algebric Coding Theory, McGraw-Hill, NY, 1968.

[7] ' J. MacWilliams, "A Theorem on the Distribution of Weights in a

Systematic Code", Bell Syst. Tech.'J., 42, pp. 79-94, 1963.

[8] Z. McHuntoon and A. M. Michelson, "On the Computation of the Probability

of Post-Decoding Error Events for Block Codes", IEEE Trans. Inform.

Theory, IT-23, pp. 399-403, May 1977.

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

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

[10] CCITT Recommendation X.25, "Interface Between Data Terminal Equipment

for Terminals Operating in Packet Mode on Public Data Networks", Plenary

Assembly, Doc. No. 7, Geneva, Switzerland, 1980.

[11] T. Fujiwara, T. Kasami, A. Kitai, and S. Lin, "On the Probability of .

Undetected Error for Shortened Cyclic Hamming Code", IEEE Trans. Commun.,

COM-33, pp. 570-574, June 1985.

[12] H. Yamamoto and K. Itoh, "Viterbi Decoding Algorithm for Convolutional

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

540-547, Sept. 1980.

19
Outer Code

Encoder

(n

b'V

Interleaver

Depth m

Inner Code

Encoder

(n,k)

Channel

Outer Code

Decoder

Deinterleaver

Inner Code

Decoder

Figure 1 A concatenated coding system
m

n

k ..

Frame

Figure 2

Frame Parity

— check bits

Block format of a concatenated code word
l-e0(m)

m

" Figure 3 The outer channel resulting from decoding the inner

code on an MBSC. ^""—
10

 iJ -

10

10

-25

10

-30

10

-2

10

-3 10

e

-4

10

-5

- .9

- .8

- .7

- .6

- .5

- .4

- .3

- .2

- .1

10

-6

Figure 4 Performance of the concatenated code

of Example 1 (t=l).
r

.Pud

10

10

10

10

-3d

10

Figure 5 Performance of the concatenated code

of Example 1 (t=0).
Pud

10

10 10

-6

Figure 6 Performance of the concatenated code of

Example 2 with u=4.
10

-5

Pud

ICT10 \-

ICT15 L

io-20 h

10

-25 _

10

-30

10

Figure 7 Performance of the concatenated code

of Example 3.
Figure 8 The burst-noise inner channel.
uI

SB"

Go0) •aooMa)

wUrH

,e«v <

•rl

0) 00PI

•rl

IDOaOJo

owouI

OwuIow. uI

o<o<

t>0 c

•H

4-1

0)

rH C <U C C rt C rG CO O O 0) CO M -H <u o s f O 4JCO <U !-i ^3 3 H •& 00 •H
Pud

10

-5

10

-10

10

-15 -

10

-20 .

10

-25

10

-30

_n 1.0

10

Figure 10.a Performance of the concatenated code of

Example 4 with Pn=0.1, L=5, e /e,=10, t=l.
.Pud n i.o

10

 XJ

-

10

10 *

10

-30

10

-6

Figure 10.b Performance of the concatenated code

of Example 4 with P =0.1, L=5, e2/e =1000, t=l.
-Pud

n i.o

- .1

10

-6

Figure 11.a Performance of the concatenated code of

Example 4 with Pn=0.1, L=5, e2/e =10, t=0.
-Pud

10

10

1Q

10 10 10

-6

Figure 11.b Performance of the concatenated code of

Example 4 with P =0.1, L=5, e.Jt =1000, t=0.
10

-5

10

-10

10

-15

10

-20 U

10

-25 fc10

-30

10

Figure 12. a Performance of the concatenated code of

Example 5 with P =0.1, L=5, e^e^lO.
1.0

10 10

-6

Figure 12.b Performance of the concatenated code of

Example 5 with Pn=0.1, L=5, e2/e =1000.