?./ /:

W1- [_iA Concatenated Coded Modulation Scheme

For Error Control

( ADDITION II )

Technical Report

to

NASA

Goddard Space Flight Center

Greenbelt, Maryland 20771

Grant Number NAG 5-931

Shu Lin

Principal Investigator

Department of Electrical Engineering

University of Hawaii at Manoa

Honolulu, Hawaii 96822

( t AS _-CI_- 163(3 C6)

_CDU LA21(.I( _C I-_EF.E

LLJ.V .} 4.] [:

September 25, 1988

J CC_ChIthA_tE CCDED

CSCL 09B

N89-12268

tlncla_

GJ/ol 0174_39
A Concatenated Coded Modulation Scheme

For Error Control

Tadao Kasami

Osaka University

Toyonaka, Osaka 560, Japan

Shu Lin

University of Hawaii

Honolulu, Hawaii 96822

ABSTRACT

This paper presents a concatenated coded modulation scheme for error

control in data communications. The scheme is achieved by concatenating

a Reed-Solomon outer code and a bandwidth efficient block inner code for

M-ary PSK modulation. Error performance of the scheme is analyzed for an

AWGN channel. We show that extremely high reliability can be attained by

using a simple M-ary PSK modulation inner code and a relatively powerful

Reed-Solomon outer code. Furthermore, if an inner code of high effective rate

is used, the bandwidth expansion required by the scheme due to coding will

be greatly reduced. The proposed scheme is particularly effective for highspeed satellite communications for large file transfer where high reliability is

required.

This paper also presents a simple method for constructing block codes for

M-ary PSK modulation. Some short M-ary PSK codes with good minimum

squared Euclidean distance are constructed. These codes have trellis structure

and hence can be decoded with a soft-decision Viterbi decoding algorithm.

Furthermore, some of these codes are phase invariant under multiples of 45 °

rotation.
A CONCATENATED CODED MODULATION SCHEME

FOR ERROR CONTROL

1. Introduction

Recently a great deal of research effort has been expended in bandwidth efficient coded

modulation for achieving reliable communication on bandlimited channels [1-37]. This

new technique of coded modulation is achieved by coding onto an expanded set of channel

signals (relative to that needed for uncoded transmission). A properly designed coded

modulation can provide significant coding gain over an uncoded modulation system with

no or little bandwidth expansion. To achieve a 3 to 5 dB coding gain with a single modulation code, the decoding complexity is quite reasonable. However, to achieve coding gains

exceeding 5 dB with a single modulation (trellis or block) code, the decoding complexity

increases drastically, and the implementation of the decoder becomes very expensive and

unpractical (if not impossible). Then the question is, "how can we achieve coded modulation with reduced complexity?". An answer to this question is to use coded modulation

in conjunction with concatenated coding. In this combined coding/modulation scheme,

a good short modulation code is used as the inner code and a relatively powerful ReedSolomon (RS) code is used as the outer code. With properly chosen inner and outer codes,

this scheme not only can achieve large coding gain (or high reliability) with good bandwidth efficiency but also can be practically implemented. That is to say, this concatenated

coding/modulation scheme offers a way of achieving the best of three worlds.

In this paper, we present a coded modulation scheme with reduced complexity for error

control in data communications. This scheme is achieved by concatenating a RS outer code

and a bandwidth efficient block inner code for the M-ary PSK modulation. The outer code

is interleaved to enhance the overall system performance. We show that this concatenated

coded modulation scheme can achieve extremely high reliability (or large coding gain) with

a very simple M-ary PSK modulation inner code. Furthermore, if an inner code of high

effective rate is used, the overall bandwidth expansion of the scheme due to coding will be

greatly reduced. Suppose an inner code with effective rate equal to one is used. Then the

overall bandwidth expansion of the scheme is due to outer code coding. Generally, in a

concatenated coding scheme, the RS outer code is a high rate code. Hence the bandwidth

expansion required is small. Of course, if an inner code with effective rate greater than

2
one is used, the overall scheme may not need any bandwidth expansion at all [16,25]. The

proposed scheme is particularly effective for high-speed satellite communications for large

data file transfer where high reliability is required.

The presentation of this paper is organized as follows. In Section 2, we present a simple method for constructing block codes for M-dry PSK modulation with M = 2 _ which

are suitable for concatenated coding. Some short M-arT PSK modulation codes with good

minimum squared Euclidean distance are constructed. These codes have simple trellis

structure and can be decoded with a soft-decision Viterbi decoding algorithm. Furthermore, some of these codes are phase invariant under multiples of 45 ° rotation. In Section

3, the encoding and decoding of the proposed concatenated coded modulation scheme is

described. Error performance of the proposed scheme over an additive white Gaussian

noise (AWGN) channel is analyzed in Section 4. In Section 5, two specific concatenated

coded modulation schemes with the NASA standard (255,223) RS code over the Galois

field GF(2 s) as the outer code and 8-PSK modulation block codes as the inner codes are

presented; their error performance and coding gains over the uncoded QPSK are evaluated.

Conclusion is given in Section 6.

2. Bandwidth Efficient Block Codes for M-dry PSK Modulation

In this section, we present a simple method for constructing block codes for M-dry PSK

modulation with M = 2 t which are suitable for concatenated coding. Using this method,

some good short codes are constructed. These codes have simple trellis structure and can

be decoded with a soft-decision Viterbi decoding algorithm.

2.1 Code Construction

Consider the integer group, A = {0,1,2,... ,2 _ - 1}, under the modulo-2 t addition. Let

each element in A represent a point in a 2-dimensional 21-PSK modulation signal set.

Define a distance measure between two elements s and s' in A, denoted d(s, s'}, as follows:

d(s,s') _= 4sin 2 (2-'Tr(s- s'0).

It is clear that d(s, s') = d(s - s',0). Note that d(s, s') is simply the squared Euclidean

distance between two 2t-PSK signal points represented by s and s' respectively. For 1 <

i<l, letB_={0,T-1}. ThenA={bl+b_+..-+bt : b, EB, withl<i<l}. Letd,

be the minimum distance between elements in the set, B_ + B_+ 1 + ..- + B_, for 1 < i < I.
It is easy to see that _. = 4sin2(T-l-_r). Let A" denote the set of all n-tuples over

A. Define a squared Euclidean distance between two n-tuples, s = (sl,82,...,8,) and

s' = ('s 1,s2,,.., ' s.') , over A as follows:

t

d_")(..s')_ _ d(,;,,; ) (1)

whered(,,,,',) = 4sin2(2-'_(, -,')).

For 1 < i < l, let C_ be a block code of length n over B_ with minimum Hamming

distance 6i. From C1, C2,...,Cz, we construct a block code C with symbols from A as

follows:

C={vl +v2+...+v_ : v_ECi with l<i<l}.

i

Then Icl-- YI Ic, I where IXl denotesthe number of elements in set X. Let

i----I

DIe] _ min{d_"_(v,v') : v,v'_ c and _ # _'}. (2)

Then D[C] is the minimum squared Euclidean distance of C. It is possible to show [see

Appendix A] that

D[C] >_ min 5,d, = rain 45, sin2(2'-'-'r). (3)

The code C_ with symbols from B_ = {0,T-1} can be constructed from a binary code Cb_

of the same length and minimum Hamming distance 6_ by substituting T- _ for 1 in each

nonzero component of a code vector in Cbi. Denote Ci with T- 1Cb_. Then the following

direct-sum,

c = c_, + 2c_2+... + 2'-' c_, (4)

is a linear code over the additive group A. The code Cb_ is called a binary component code

of C. Suppose Cb_ is a binary (n, kb_) linear code. Then

!

The parameter k = _ kb_ is called the dimension of C. If each component of a code

i----1

vector v in C is mapped into a point in a 2-dimensional 2 t-PSK signal set, we obtain a

block coded 2 t-PSK modulation code. The effective rate of this code C is given by

I

1

RIC] = _ E k,, (5)

i=1

4
which is the number of information bits transmitted by C per dimension. The asymptotic

coding gain, denoted "_[C], of C over the uncoded QPSK is given by [2],

RIo].D[c] (6) -_[C]= 10log,0 2

As an example, let I = 3, M = 2 s /rid r_ = 8. Then A = {0,1,2,3,4,5,6,7},

B1 = {0,1},Ba = {0,2} and Bs = {0,4}. The minimum squared Euclidean distances of

A = B1 +B2 +Bs,Ba +B3, and B3 are d, = 0.586,d2 = 2 and d3 = 4 respectively. Choose

the binary component codes Cb,, Cb2 and Cb3 as follows: (1) Cb, is the binary (8,1) code

which consists of the all-zero and all--one vectors; (2) Cba is the binary (8,7) code with all

the even weight vectors; and (3) Cb3 is the (8,8) code which consists of all binary 8-tuples.

Clearly the minimum Hamming distances of Cbl, Cba and Cb3 are 8, 2, and 1 respectively.

Consequently, the code C = Cb, + 2Cb2 + 4Cba has minimum squared Euclidean distance

D[C] = 4, dimension k = 16 and effective rate R = 1. Mapping the code symbols of C into

points of the 8-PSK signal set as shown in Figure 1, we obtain a block code of length 8 for

the 8-PSK modulation. This simple code provides a 3 dB coding gain over the uncoded

QPSK modulation with no bandwidth expansion. Furthermore, the code has a trellis of 4

states and 8 sections as shown in Figure 2 (see Appendix B for the trellis construction),

and hence can be decoded easily by a soft-decision Viterbi decoding algorithm. This code

is in fact an analogue of one construction of Gosset lattice Es[6,17], and an analogous

4-state and 4-section trellis diagram for E8 appears in [Forney et al.[6]] (with two symbols

per branch). Another important feature of this 8-PSK modulation code is that it is phase

invariant under multiples of 45 ° rotation (by simple obserwation of its trellis diagram or

application of the necessary and sufficient condition for phase invariance given in [37J).

The modulation code construction method presented above is actually a multi-level

code construction approach which was first proposed by Imai and Hirakawa[1] and

Ginzburg [3], and later extended by others[ll,13,14,25-28,30-32,34,35 and 37]. Using the

above method, we have constructed a list of short block codes for QPSK, 8-PSK and 16-

PSK modulations given in Table 1. These codes have good minimum squared Euclidean

distances and provide 3 to 7.2 dB coding gains over the uncoded QPSK modulation. For

all the 8-PSK and 16-PSK codes, the coding gains are achieved without or with little

bandwidth expansion. All the codes in the table have trellis structure. A modulation code

C constructed by using the above proposed method has a trellis structure if its component

codes have trellis structure. A trellis diagram for C can be obtained by taking direct

product of trellis diagrams of its component codes[37]. The code constructions in the table
which use Reed-Muller codes as binary component codes are found to be analogues of

lattice constructions in Forney{18].

2.2 :Encoding and Decoding

Encoding of a 2_-PSK modulation code C of length n constructed based on the above

method can be done as follows. A message u of

i

k = E kbi

i=1

bits (called a segment} is divided into I subsegments, the i-th subsegment consists of kb+

bits. For 1 < i < l, the i-th subsegment is encoded into a code vector v_ in the binary

component code Cb+ of C. Then the sum

v=vl +2v2+"'+21-1v_

--

is the codeword in C for the message segment u. This codeword v is called a frame. The

components, sl, s2 ,..., s,,, of v are then mapped into points in a 2-dimensional 2 _-PSK

signal set and transmitted. Hence, each message segment of k bits is encoded into a

sequence of r_ 2_-PSK signals.

A soft-decision decoding algorithm for the above M-ary PSK codes can be devised

as follows. For any element s in the group A = {0,1,...,2' - 1}, let X(s) and Y(s) be

defined as

X(s) = cos(2'-i_rs), Y(s) = sin(2'-'_s). (7)

For any two elements, s and s', in A, we find that

d(s,,') = (X(s) - X(s')) 2 + (Y(s) - y( ,))2. (8)

For 1 < j < n, let ix,., Ys) be the normalized output of a coherent demodulator [37]

for the j-th symbol of a received frame. The received frame is then represented by

the following 2n-tuple: z = (xl,yl,x2, Y2,..., xn, y, ). For the received frame z and a

codeword v = (s_,s_,...,s,_) in C, let Iz, v] 2 be defined as follows:

n

i", l = - x(+;)) + (Y;- YCs;)) (9)

3"=1

6
Assume that the channel is an AWGN channel. When symbol 8 E {0,1,...,2 _ - 1) is

transmitted, the normolized output (z, y) of a coherent demodulator for 2:-ary PSK is

distributed with the following joint probability density function,

p(x,y)-- 2_.021 exp{-[(z- X(8))'_ (y- Y(8))'I/2o' }, (I0)

where cr2 = 1/2p, and p is the SNR per symbol [37]. Suppose every codeword of C is

transmitted with the same probability. Then we have the following decoding rule: For

a received frame z, choose a codeword v in C with minimum Iz, v] 2. The segment u

corresponding to v is then the decoded segment. This decoding rule achieves maximum

likelihood decoding for C over an AWGN channel. If C has a simple trellis structure with

moderate number of states, the decoding of C can be implemented easily with a Viterbi

decoding algorithm.

To analyze the error performance of a 2 _-PSK code C, we need to know its complete

weight distribution. Let v = (81,82,... ,so) be an n-tuple over the additive group A.

The weight composition of v, denoted comp(v), is a 2t-tuple,

t = (to,tl,...,t2__l),

where t_ is the number of components s_ in v equal to the symbol i in A. Let W(t) be the

-number of codewords v in C with comp(v) = t. Let T be the set,

T_ {(to,tl,...,t2,_l) : O<t, <n with 0_<i<21}.

Then, {W(t) : t E Y) is the detail weight distribution of C. W (t) can be enumerated from

the joint weight distribution [39] of the binary component codes, Cbl, Cb2,..., Cb_ of C.

Once the detail weight distribution of C is known, its error performance can be analyzed

and computed for an AWGN channel. The detail weight distributions of the codes listed

in Table 1 have been determined [25,26,37].

3. The Encoding and Decoding of the Proposed Concatenated

Coded Modulation Scheme

For the proposed concatenated coded modulation scheme, the inner code, denoted C1, is

a 2t-PSK code of length nl with binary component codes, Cbl, Cb_,..., Cbi, where Cb_ is

an (nl, kb_) binary linear code for 1 < i < l. The dimension of C1 is

l

kl -" E kbi.

i=1
The outer code of the scheme, denoted (5'2,is an (n2, k_) RS code with symbols from

the Galois fieldGF(2 b) and minimum (Hamming) distance d_ = n2 - k2 + 1. Each code

symbol of the outer code isrepresented by a binary b-tuple (called a b-bit byte) based

on a certain basis of GF(2b). We require that kl ----mb where rn isa positive integer.

The encoding of the proposed scheme is performed in two stages. First a message

of k2b bits is divided into k2 b-bit bytes. Each b-bit byte is regarded as a symbol in

GF(2_). These k2 bytes are encoded according to the outer code C2 to form an n2-byte

codeword in (5'2. This codeword is then temporarily stored in a buffer as a row in an array.

After m outer codewords have been formed, the buffer stores an m x n2 array, called a

segment-array as shown in Figure 3. Each row of a segment-array is called a section.

Each column of a segment-array consists of m b-bit bytes (or rnb bits), and is called a

segment. There are k2 data segments and n2 - k2 parity segments. At the second stage

of encoding, each segment of a segment-array isencoded according to the 2_-PSK inner

code Cz to form a sequence of nl 2I-PSK signals as described in the previous section.

This sequence of nl 2t-PSK signals iscalled a frame. The n2 frames corresponding to

the segments of a segment-array form a code block. A code block istransmitted column

by column (or frame by frame). In fact each frame istransmitted as soon as ithas been

formed. Note that the outer code isinteHeaved to a depth (or degree) of m.

The decoding for the proposed scheme also consists of two stages, the inner and outer

decodings. When a frame in a code block is received, it is decoded into a segment of m

bytes based on the soft-decision decoding algorithm as described in the previous section.

The decoded segment is then stored as a column of an array in a receiver buffer for the

second stage of decoding. After n2 frames of a received code block have been decoded, the

receiver buffer contains a m x n2 decoded segment-array. Each column of this decoded

segment-array may contain symbol (or byte) errors which are distributed among the m

sections (rows), at most one symbol error in each section. Now the second stage of decoding

begins. Each section of the decoded segment array is decoded based on the RS outer code

C'2. Suppose the RS outer code is designed to correct t2 or fewer symbol errors with

0 < t2 __ L(n2 - k2)/2J. If the syndrome of a section corresponds to an error pattern

of t2 or fewer symbol errors,error correction is performed. The values and locations of

symbol errors axe determined based on a certain algorithm. Ifmore than t2 symbol errors

are detected, the receiverstops the decoding process and declares an erasure (or raises a

flag)for the entire segment array. Ifallthe rn sections of a segment-array are successfully

8
decoded and the number of segments which contain corrected symbols is t2 or less, then the

k_ decoded data segments are accepted by the receiver and delivered to the user in proper

order. Otherwise, the receiver declares an erasure for the entire decoded segment-array.

When the receiver fails to decode a received block, 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.

4. Error Performance Analysis

In this section, we analyze the performance of the proposed concatenated coded modulation

scheme for an AWGN channel. We assume that all the codewords of the inner modulation

code are equally likely to be transmitted.

Let p(1} be the probability that a decoded segment is error-free and P_(_) be the

probability that a decoded segment is erroneous. Since the inner code C1 is linear over

(0, 1,...,2 _ - 1} under binary component-wise modulo-2 addition, we assume that the

all-zero codeword 0 is transmitted without loss of generality. For a received frame z, the

decoded segment is error-free if and only if

[z,v[ 2 :> [z,O[ 2 (11)

for every nonzero codeword v in C1 (the probability that [z, v[ 2 = [z, 8[ 2 is assumed to be

zero). It follows from (9) that the inequality of (11) can be put into the following form:

Y_I n 1

2 Z (X(sj)- 1)(z, - 1)+ YCsi)y s < Z (XCss) - 1)'

$'=1 $'----1

+ Y(si) 2 = d(")Cv, O), (12)

where z = (x:, y,, xa, y_,..., x,,,, y,,,) and v -- (sl, s,,..., s,,, ). For any codeword v in

C1, let Q(v) denote the set of (z_, Yl, z2, y2,..., z,:, y,,) which satisfies the inequality of

(12). Define the following set,

Q¢ _ ["1 Q(v). (13)

reck-{5}

Then it follows from (10) that

1 j( "" f exp{-(E "' Cxj- 1) _ +y_)/2a'}dx, dyl...dx,,,dy,,, (14) p(l)_

$'--1

9
where the integration is taken over the set Q_.

Let S be a subset of C1 - {6} such that

N = N Q(-). (15)

vECI-{O} v_8

Then S is called a representative set for Cl - (0}. To evaluate (14), it is desired to find a

small set S to represent Cl -{0} [25,26].

For a nonzero codeword v in C1, let P,(I)(v) denote the probability that a received

frame z satisfies the following condition:

Iz,vl=< I..,_1=. (16)

The inequality of (16) can be put into the following form:

nl

2 Z (X(sl)- 1)(xj. - 1) + Y(s,)yl > Ivl_ (17)

i=l

where I_1: _/d-(v,0). Since the random variable,

nl

2 _ (x(s,) - 1)(=,- 1)+ r(s,}_;

$'=1

is distributed with a Gaussian distribution of zero mean and variance 4a _ [vl 2 , we have

P._')(v)= 22v_-_}vlexp{

1 1

= _ erfc(2v_a )= _ erfc(Y-_) (18)

where

erfc(x) = _/_r ]+exp{-t2}dt

and p is the SNR per symbol [38].

Let (_, and _)(v) denote the complementary sets of Qc and Q(v) respectively. Then

it follows from (13) and (15) that

(_c = U (_(v), (19)

yES

10
where S is a representative set for CI - {0}. Consequently, we obtain the following upper

bound on P_),

P,?'=1- e2' < _ P_."(v). (20)

yES

Let A be the set of real numbers such that, for any d E A, there is a nonzero codeword

v in C1 with squared Euclidean distance d from the all-zero codeword 0. For a d E A and

a representative set S for C, - {8}, let Ad [S] be the number of codewords of C, in S with

squared Euclidean distance d from the all-zero codeword 0. Then it follows from (18) and

(20) that

e_V_<i- 2 B Ad[S] erfc(v/_/2). (21)

dE"

A_ [Ct - {0}] can be computed from the complete weight distribution of O1. If we can

choose a small representative set ,9 for C, - {0} [25,26], Ad[S] may be much smaller than

Ad [Ct - {0}] except for "dominate" d's close to the minimum squared Euclidean distance

D[C,] of 01.

Next we analyze the error performance of the overall concatenated coded modulation

scheme. Let Pc, Pc, and P. be the probabilities of a correct decoding, an erasure and an

incorrect decoding for an entire received code block respectively. Then

_-Pc--Po.+v., : _ [P,V'] '[_-P2_]°''. (22)

/=t_+l

Let _(2) denote an upper bound on P_(_), say the right-hand side of (2o). Then it follows

from (22) that

Pc _> 1- _ g.,,,(_(=*)) (23)

ks/

/=t_+l

where g,,,,,(x) = #(1- x)"'-' for 0 < z < i/r_z, and g.,,,(z) = (i/n_)'(1 -i/ha)"'-'

otherwise.

Let p_ (u) denote the probability that the error pattern induced by the inner code

decoding in a decoded segment is u. Let Q, denote the sum of the q largest numbers in

the following set:

{p.(u)' : u 6 [GF(2b)] " - {0} }. (24)

Then we can show that the probability of an incorrect decoding, Pc,, is upper bounded as

follows [see Appendix C for derivation]:

-- " °"""-"( z -°h ) B C)P(w,h,j), (25)

=,=d2 h=0 2"=w +h-t_

11
where d_ = n2 - k2 + 1, and

-- 1 - ) Qj+d,-,,. (26)

Let 15o and/5 denote the right-hand sides of (23) and (25) respectively. Then 15¢ is

a lower bound on Pc, and 15¢, is an upper bound on Pc,. The probability, 1 - ]5¢, is an

upper bound on the total probability of a decoding failure and a decoding error. Clearly,

1 - t5¢ serves as an upper bound on the probability that a received block will be rejected

(we will call this as the rejection rate). In the case where no block erasure is allowed, 1 - ]5¢

also serves as an upper bound on the probability of a decoding error. The performance

of the proposed concatenated coded modulation scheme is then measured by the pair of

probabilities,/5 and 1 -]5.

5. Two Specific Concatenated Coded Modulation Schemes

In this section, Two specific concatenated coded modulation schemes are considered, their

error performance and coding gains over the uncoded QPSK modulation system are computed. In both schemes, the NASA standard (255,223) RS code over GF(2 s) is used as

- the outer code and 8-PSK codes are used as the inner codes.

5.1 First Scheme

For the first specific concatenated coded modulation scheme, the inner code C_ is the 8-

PSK code of length 8 described in Section 2 (the 4-th code given in Table 1). This inner

code has dimension k_ = 16, effective rate R[C_] = 1 and minimum squared Euclidean

distance D[C1] = 4. Since kl = 16 and b = 8, the outer code is interleaved to a depth of

m = 2. The overall code rate of the scheme is R,_I -- (k2 In2 )-R[C, ] = (223/255).1 = 0.875

which is simply the outer code rate. The inner code provides a 3 dB (asymptotic) coding

gain over the uncoded QPSK modulation without bandwidth expansion. The bandwidth

expansion required by the overall scheme is due to the coding of the outer RS code. The

inner code C_ has a 4-state trellis structure as shown in Figure 2 and hence can be decoded

with a Viterbi decoder. Furthermore it is phase invariant under multiples of 45 ° rotation.

This property ensures rapid carrier-phase resynchronization.

The complete weight distribution of the inner code can be enumerated from the joint

weight distribution of its three binary component codes, Cb_, Cb_ and Cbs. For integers i,

12
j and h such that i is even, 0 __ j < i < 8 and 0 < h_< 8- i,

w((h,o,y,o,s - i- y,o))

-- w((o,h,o,y,o, s- i- h,o,i- y))

For other weight composition t = (to,tl,t2,ts,t4,ts,te,ts),W(t) = 0.

By choosing a representative set for CI - {0}, we find the following upper bound on

the probability of an incorrect decoding for the inner code,

Let _(_) denote the upper bound on P_(_}given by the right hand side expression of (28).

Then _(_) isused as a measure of the error performance of the inner code CI. The error

performance of the inner code and that of the uncoded QPSK versus SNR per symbol is

shown in Figure 4. Simulation result on P_(J)is also included. Note that the difference

between _(_) and the simulation result on P_) is very small for SNR > 8 dB/symbol

(or 5 dB/information bit). We also see that the simple 8-PSK inner code provides a

2.31 dB/symbol (real)coding gain over the uncoded QPSK modulation at 10-6 decoded

segment-error rate, and a 2.42 dB/symbo] coding gain at i0-o decoded segment-error

rate.

The RS outer code is a very powerful code which iscapable of correcting up to 16

symbol (or byte) errors. From (23) and (28),we can compute the probability 1- ]5c which

isan upper bound on the probability of a decoding failure.From (25) and (28),we can

compute the probability/_e,which isan upper bound on the probability Per of an incorrect

decoding of a received block.

We can also use the simulation result on p I_) denoted P(_) to compute the error _¢, • '

performance of the overall scheme. Let 1 - Pc,• denote the value computed from the

expression of (22) with P,(_)replaced by the simulation result P_(_). Then 1 - P_.• gives

the total probability of a decoding failureand a decoding error for the overall scheme

based on the simulation resultsof the inner code. Let/_e,.o denote the upper bound on

Per computed from the right-hand side expression of (25) with P_(_)and Q_.+a,-,, replaced

by the simulation results,P(_) and Qj'+d,-w.• respectively.Simulation result Q_'+d, _.•

on Q_.+_,_,, is obtained with a certain confidence level by using the following facts: (1)

13
the probability that the error pattern (an inner codeword) induced by the inner code

decoding in a decoded frame is v depends only on (to, tl + tT, t2 + t6, ts + ts, t4) where

(to,t_,t2,ts,t,,ts,ts,tT) is the weight composition of v; and (2) a decoded segment is

uniquely determined from a decoded frame. In the following, we will use 1 - 15c, 1 - Pc,,

and Per.° to measure the error performance of the overall scheme.

Using the outer code to correct up to 16 symbol errors (t2 = 16), the error performance

of the overall scheme is shown in Figures 5 to 8, where Figures 5 and 6 give the block-error

performance and Figures 7 and 8 give the bit-error performance. Figure 5 gives the upper

bound 1 - J5c and simulation result 1 - Pc,o on the total probability of a decoding failure

and a decoding error versus SNR/symbol, and Figure 6 gives the upper bound ]3er.0 on

the probability Per of a decoding error for the overall scheme versus SNR/symbol. From

Figures 5 to 6, we see that the first specific concatenated modulation scheme proposed in

this section provides extremely high reliability. For example, with SNR - 9 riB/symbol

(or 6.57 dB/information bit), the probability of a decoding error is upper bounded by

6.28 × 10 -2s and the rejection rate is upper bounded by 4.95 × 10-16 (using simulation

results of the inner code). We see that the rejection rate is extremely small and it does

not affect the system throughput. With SNR = 10 dB/symbol (or 7.57 dB/information

bit), the probability of a decoding error is less than 6.80 × 10-41! Practically, the scheme

achieves error-free communication. Figure 5 also shows the coding gain of the scheme

over the uncoded QPSK in terms of decoded block-error rate. For example, at decoded

block-error rates, 10 -_ and 10 -1°, the scheme achieves coding gains, 8 dB/symbol and

9 dB/symbol, over the uncoded QPSK Ca block of 2 × 223 bytes) respectively. These are

large coding gains.

For data filetransfer,the block-error-rates should be used as the measure of error

performance of the scheme. However, for the purpose of providing a basis for comparing

with other coding schemes, we follow the conventional practice to compute the decoded

bit-error-rate (BER) of the scheme. The bit-error performance of the scheme is shown

in Figures 7 and 8. Two types of decoded BERs are computed. The firsttype, denoted

Pbl, is computed based on the probability Per of an incorrect decoding of a code block

using the approximation, Pbl "- (d_/2n2). Pc,. This type of BER is a measure of bit-error

performance of the scheme when retransmission is allowed. The type--1 decoded BER of

the scheme versus SNR/symbol is shown in Figure 7. We see that the scheme achieves large

coding gain over the uncoded QPSK for Pbl __ 10 -1_- At Pbl= 10 -12, the coding gain is

14
9.8 dB/symbol (or 9.2 dB/information bit).The required SNR to achieve Pbl -- I0-_2 is

7.1 dB/symbol (or 4.6 dB/information bit).

The second type of decoded BER, denoted Pb2, iscomputed based on the total probability1 - P_ of a decoding failureand a decoding error of a code block using the appraximation, Pb2 = (d2/2r_)- (1 - P_). This type of BER isused as the measure of bit-error

performance of the scheme when retransmission is not allowed. Figure 8 gives the type2 decoded BER of the scheme versus SNR/symbol. We see that, at P_2 = 10-6 and

Pb2 = 10-_0, the coding gains of the scheme over the uncoded QPSK are 5.52 dB/symbol

(or4.94 dB/information bit) and 7.60 dB/symbol (or 7.02 riB/information bit) respectively.

The required SNR to achieve Pb_ = 10-e is8.04 dB/symbol (or 5.61 dB/information bit),

and the required SNR to achieve P_2 = 10-_0 is8.50 dB/symbol (or 6.07 riB/information

bit).

From Figure 2, we see that the 4-state trellisdiagram for the 8-PSK inner code

consists of two identicalparallel 2-state trellissub-diagrams without cross connections

between them. This structure suggests that the decoding of the inner code can be done

with two 2-state Viterbi decoders to process the two trellisub-diagrams in parallel.This

implementation not only simplify the decoding complexity but also speeds up the decoding

process. Since the inner code isvery short, a very high speed decoder can be implemented

without much cost.

5.2 Second Scheme

For the second specific concatenated coded modulation scheme, the inner code C_ is an 8-

PSK code of length 16, the 5-th code given in Table 1. This inner code C_ has dimension

kx = 36, effective rate R[CI] -- g/8 (greater than 1) and minimum squared Euclidean

distance D[C_] - 4. It provides a 3.52 dB (asymptotic) coding gain over the uncoded

QPSK modulation with less bandwidth (a bandwidth reduction). However, it has a 16-

state trellis diagram which makes the decoder more complicated to implement than the

4-state 8-PSK inner code used in the first specific scheme. Since k_ = 36 is not a multiple

of 8, the outer code is interleaved to a depth of m = 9. After the outer code encoding,

each column of the segment-array consists of 72 bits (or 9 bytes). Each column is divided

into 2 segments, 36 bits (or 4.5 bytes) each. Then each segment is encoded into a 16-

symbol codeword in the inner code C1. The overall code rate of this second specific

scheme is R_ss = (223/255)- (9/8) : 0.9838, and the overall scheme practically requires

15
no bandwidth expansion.

The complete weight distribution of the above inner code can also be enumerated from

the joint weight distribution of its binary component codes. By choosing a representative

set for C_ - {0_, we obtain the following upper bound on the probability of an incorrect

decoding for the inner code:

P_(_) <_ 248 erfc(v/p ) + 1920 erfc(V/2(2 - v/2)p ) + 30720 erfc( V/2(9 -24V_)p )

-t- 15360 erfc( V/2(8 -3v_)p_ _/_ 16384 erfc(21(2 - x/_)p )

Again let _(_) denote the upper bound on P_c given by the right hand side expression of

(29). The error performance of this 16--state 8-PSK inner code versus SNR per symbol

is shown in Figure 9, where the simulation result P_(cl). on P_?) and the error performance of the uncoded QPSK (4.5-byte segment) are included. We see that, at 10 -e

decoded segment-error rate, the 16-state 8-PSK inner code achieves a 2.26 dB/symbol

(2.77 dB/information bit) real coding gain over the uncoded QPSK with less bandwidth.

Again the (255, 223) RS outer code in the second specific concatenated coded modulation scheme is used to correct up to 16 symbol errors. The error performance of the

overall scheme is shown in Figures 10-13. From Figures 10 and 11, we see that, with SNR

-- 10 dB/symbol (or 7.06 dB/information bit), the probability of a decoding error of the

overall scheme is upper bounded by 6.91 × 10-4_ and the rejection rate is upper bounded by

2.08 x 10- _2 (using simulation results of the inner code). Figure 10 shows the coding gain

of the second scheme over the uncoded QPSK in terms of decoded block-error rate. For

example, at decoded block-error rates, 10-T and 10-_0, the second specific concatenated

coded modulation scheme achieves coding gains, 7 riB/symbol and 8 riB/symbol, over the

uncoded QPSK (a block of 9 × 223 bytes) respectively with very little overall bandwidth

expansion. Figures 12 and 13 give the bit-error performance of the second specific scheme.

At type-1 decoded BER, Pb_ = 10-sz, the coding gain over the uncoded QPSK is 15

dB/symbol. At type-2 decoded BERs, Pb2 = 10 -6 and Pb2 = 10 -_°, the coding gains of

the second specific concatenated coded modulation scheme over the uncoded QPSK are

4.05 dB/symbol (or 3.98 dB/information bit) and 6.26 dB/symbol (or 6.19 dB/information

bit) respectively.

16
From Figures 10-13, we see that the second specific concatenated coded modulation

scheme considered above also achieves extremely high reliability and large coding gain over

the uncoded QPSK modulation system. The 16-state trellis diagram of the inner code

consists of two identical parallel 8-state trellis sub-diagrams with no cross connections

between them, and hence the decoding of the inner code can be done with two 8-state

Viterbi decoders to process the two trellis sub--diagrams in parallel. Furthermore, the

inner code is also proved to be invariant under multiples of 45 ° phase shift[37].

Comparing the two specific concatenated coded modulation schemes, we find that the

second scheme achieves about 1 dB/symbol less coding gain (in terms of decoded blockerror rate) than the first scheme. However, the second scheme requires less bandwidth

expansion than the first scheme. Both schemes are suitable for high-speed satellite communications for large date file transfer where high reliability is required. Furthermore,

both schemes are very robust in correcting burst-errors. The first scheme is capable of

correcting any single burst of errors of length up to 241 bits, while the second scheme is

capable of correcting any single burst of errors of length up to 1081 bits!

6. Conclusion Remarks

In this paper, a concatenated coded modulation scheme for error control in data communications has been presented. This scheme is achieved by concatenating a RS (or

maximum-distance-separable) outer code and a bandwidth efficient block inner code for

the M-ary PSK modulation. Error performance of this scheme has been analyzed. A

simple method for constructing bandwidth efficient block codes for the M-ary PSK modulation has been devised. By two specific examples, we have shown that extremely high

reliability can be achieved by concatenating a good short 8-PSK modulation inner code

and a relatively powerful RS outer code, such as the NASA standard (255,223) RS code

over GF(2S). Since the inner code is short, a high speed decoder with a soft-decision

decoding algorithm can be implemented without much cost (or complexity). If a proper

high effective rate inner code is used, the bandwidth expansion required by the overall

scheme due to coding will be greatly reduced. The proposed scheme is actually devised to

achieve coded modulation with reduced complexity. It offers a way of obtaining the best

of three worlds, reliability, complexity and bandwidth e_ciency. The proposed scheme is

particularly suitable for high-speed satellite communications for large file transfer where

high reliability is required.

17
r

The inner code decoder can be implemented to perform both decoding and erasure

operations[40]. In this case, a decoded segment may contains symbol errors and an erased

segment creates m symbol erasures, one in each section. The RS outer code is then designed

to correct both symbol errors and erasures.

Of course, other types of modulation codes can be used as inner codes in the proposed

concatenated coded modulation scheme.

ACKNOWLEDGMENT

The authors would like to thank Dr. G.D. Forney, Jr for his most valuable comments

in the process of preparing this paper.

18
Appendix A

Proof of the Lower Bound on D[C] Given by (3)

Let v and v' he two different codewords in C. Then v and v' can be expressed as follows:

where

v=vl +vz+-"+vl, viEC_, (A-I)

# # I / #

v =v_+v2+...+v,, v,_C,, (A-2)

v, = (8,1,s,2,...,8,.), s,; _ B,,

# / U t a

v, = (s,l,s,2,...,8,.), 8,; e_B,,

with 1 < i < l and 1 < j _< n. Let h denote the first suffix such that

#

Then, since the minimum Hamming distance of Ch is 5h, there exists 6h suffices 1 ___Jl <

3"2 < "" < J6, <__n such that

e

say, _:sns., for l_<p_<Bh. (A-6)

For a nonempty subset B of the group A, let d[B] denote the minimum distance between

elements in B.

Sinces o --.. 8 o# for l<i<handl<j<n, we have that, for l<p<Sh, _ _

Since d(s,s') = d(s - s',O) and dn = d[Bh -k

for 1_< p _<5h,

!

if!

Bn+1 +'" + B,], it follows from (A-7) that,

i

n i I

Since d(")(v,v') = _ d( __, s,3., __, si3.) , we have that

3"=1 /----1 /----1

d(n ) (v, v') _> 5h dh >_ min 5, d,.

1<_,<_t

19
Appendix B

Trellis Diagram for the 8-PSK Code Described in Section 2

The 8-PSK code U described in Section 2 consists of three binary component codes Ubl,

Ub_ and Cb3 where (1) C_1 is the binary (8,1) code which consists of the all-zero and allone vectors; (2) Cb_ is the binary (8,7) code with all the even weight vectors; and {3) Css

is the (8,8) code which consists of all binary 8-tuples. Let u be a 16-bit message segment

to be encoded. Divide u into three sub-segments u_, u2 and u3 where u_ consists of only

one bit, u2 consists of seven bits and us consists of eight bits. Then ul, u2 and u3 are

encoded based on Cbl, Cb2 and Cbs respectively. Let

a = (a,, a3, a,, ao, aT, as),

b -- (bl, b_, b3, b4, bb, be, bT, bs),

C --- (Cl,C2,C3,C4,Cs,Ce,CT,Cs),

be their corresponding binary codewords. Note that a is either the all-zero vector or the

all-one vector. The codeword b has even weight.

For I < l < 8, the input to the signal selector of the overall encoder-modulator at

the/-th time unit is the triplet (at,bL,ct). If at = 0, then (bt,ct) selects a point from the

QPSK signal set shown in Figure lb. If at = 1, the (bt,ct) selects a point from the QPSK

signal set shown in Figure lc. Hence the system switches between two QPSK signal sets.

To construct the trellis diagram for C, we need to define the states of the overall encodermodulator. Let (b_, b2,..., bt) denote the/-bit prefix of codeword b. Let W(b_, b_,..., bt)

denote the Hamming weight of (bl,b2,...,b_). At the l-th time unit, the state of the

encoder-modulator depends on the bit at and the number W(b,,b2,...,bt). Define the

following states:

(1) A, represents the state that at = 0 and W(bl,b_,

(2) Ao represents the state that at = 0 and W(b_,b2,

(3) Be represents the state that at = 1 and W(b_,b2,

(4) Bo represents the state that at = 1 and W(b_,b2,

• .., bt) is even;

...,b,) is odd;

...,b,) is even; and

...,hi) is odd.

Assume that the encoder-modulator starts from the state A, at the time I = 0. Then

the trellis diagram for C can be constructed easily as shown in Figure 2. There are two

parallel branches (or transitions) between the transition of two states; they correspond to

c_ = 0 and ct = 1 respectively.

2O
The encoding of message u is equivalent to tracing a path in the trellis diagram. The

codeword corresponding to u is a sequence of QPSK signal points either from the set shown

in Figure lb or from the set shown in Figure lc.

21
Appendix C

Derivation of the Upper Bound on Pc, Given by (25)

Let us number the segments in a decoded segment-array (Fig.3) from 1 to r_. Let e I be

the f-th decoded segment, and _ = (el,e2,..., e_). Suppose that the segment-array is

decoded incorrectly by the outer code decoder. Then the segment-array is decoded into an

interleaved outer codeword and _7c+9, where vc is the actual transmitted interleaved outer

codeword and re is the nonzero interleaved codeword induced by the outer code decoding.

Let v I be the f-th segment of re. Define the following sets associated to re and _.

W(_')_{f : v t. :f:O}, (C-l)

: e:#0, v: ¢-o), (c-2)

and

JC_,9)_{f : e s =v I #0}. (C-3)

When a segment-array is decoded based on the outer code C2, only t2 or fewer error

segments are corrected. Hence, the following inequality holds:

IH(_,_)I + IW(_)I- IJ(_,_)l _< t_. (C- 4)

Let Co denote the interleaved outer code. For _ E Co, H _C {1,2,...,ha} and d _c

{1,2,...,n2} such that H is disjoint from W(ff),J C_ W(_) and IHI + Iw(_.)l - IJI < t2,

let Pc (re, H, J) be the probability of the occurrence of an error segment-array _ induced

by the inner code decoding for which H(_, re) = H and JC_, re) = J. Then

PoCre. .J): 1-[p.(v,) II (c-s)

SE J IEW (_,)- J

where w = IW(re)l,h = IHI and pc(u) denotes the probability that the error pattern

induced by the inner code decoding in a decoded segment is u.

Let W be a subset of {1,2,...,n2}-H such that W _DJ, da < IwI and ]Wl+h-j < t_.

Let Co (W) be defined as the following subset of codewords in Co:

Co{W) _-{ (va,v2,...,v_,)EC0 : v I #0 if and only if yEW }. (C-6)

For re E Co(W), W(re) = W. Let w denote IWI. Next we estimate

Pe(re, H,J}.

22
Sincet_ __ (d_ - 1)/2, we have that

d_>_2t,+ 1. (O- 7)

Since d2 _< to and h + to- j < t2, itfollows from (C - 7) that

j_> to-d_ _>0. (c-s)

Let J' be a subset of J such that

IJ'l---- to- d,2. (0-9)

For any a s e [GF(2b)] _ - {0} with f E J', consider two different codewords 9 =

i 0 t i

(vl,v2,...,v,_,) and 9' = (vl,v_,...,vn,) in Co(W) such that v/ = v s = a s for f E J'.

N t .

Since the number of nonzero segments of _ - v m at least d_, we have that

s

v # v s, for f E W - J'. (C - 10)

It follows from a well known inequality and (C - I0) that

IF[p.(",)

_E{ _EOo(W) : vt=a t .for

= FIp.(a,)

.feJ' _e{ #eoo(w)

II Z

.fEJ' _E{ 9EOo(W) : vyfa ! .for

<- II p.(a/)Oi+d,-.,

IEJ'

.fEJ' } .fEJ

Z II ,.(-,)

: v f-_a! .for .fEY' ) ]E J--J*

[p.(",)]'+"-"

y+d_-to

IEJ'} JEJ-J'

(C- 11)

where Q_ denotes the sum of the q greatest pe(u)qs in the set

{ pc(u)' : u E [GF(2b)] '' - {0}}.

Note that

p!11.o = _ p.(,).

Then it follows from (C - 11) that

Z II

_,eCo(W }.fes

p.(v,)< lZ_2)} "-''

Qj+ d_ - _ -

(C- 12)

[C- 13)

23

/
Hence we have that

Since Per is the sum of

that

n. 2 mln(f2,t:l--w }

z---- (:) h=O z

P.(¢, H,J) _<P(w,h,j). (C- 14)

Pe (9, H, J) taken over all possible W, H and J, we have

_Co(W)

( ) ()tU -n2 h- w _ j P(w,h,j). (C - 15)

jfw÷h-¢2

24
REFERENCES

1. H. Imai and S. Hirakawa, "A New Multilevel Coding Method Using Error Correcting

Codes," IEEE Trans. on Information Theory, Vol. IT-23, No. 2, March 1977.

2. G. Ungerboeck, "Channel Coding with Multilevel/Phase Signals," IEEE Trans. on

Information Theory, Vol. IT-28, pp. 55-67, January 1982.

3. V. V. Ginzhurg, "Multidimensional Signal for a Continuous Channel," ProbIemy

Peredachi Informatsii, Vol. 20, No. 1, pp. 28--46, 1984.

4. E. Biglieri, "High-level Modulation and Coding for Nonlinear Satellite Channels,"

IEEE Trans. on Communications, Vol. COM-32, pp. 616-626, May 1984.

5. S.G. Wilson, et.al., "Rate 3/4 Convolutional Coding of 16-PSK: Code Design and

Performance Study," IEEE Trans. on Communications, Vol. COM-32, pp. 1308-

1315, December 1984.

6. G.D. Forney, Jr., R.G. Gallager, C.R. Lang, F.M. Longstaff and S.U. Qurieschi, "Efficient Modulation for Band-Limited Channels, _ IEEE Journal of Select. Areas Communications, Vol. SAC-2, pp. 632-647, 1984.

7. L. F. Wei, "Rotationally Invariant Convolutional Channel Coding with Expanded

Signal Space - II: Nonlinear Codes," IEEE Journal of Select. Areas Communications,

Vol. SAC-2, pp. 672-686, 1984.

8. A.R. Calderbank and N.J.A. Sloane, "Four-Dimensional Modulation with an EightState Trellis Code," AT&T Tech. J., Vol. 64, pp. 1005-1018, 1985.

9. R. Padovani and J.K. Wolf, "Coded Phase/Frequency Modulation," IEEE Trans. on

Communications, Vol. COM-34, pp. 446-453, May 1986.

10. T. Fujino, et.al., "A 120 Mbit/s Coded 8-PSK Modem with Soft Decision Viterbi

Decorder," IEEE International Conference on Communications Conference Record,

Toronto, Canada, June 22-25, 1986.

11. S. I. Sayegh, "A Class of Optimum Block Codes in Signal Space," IEEE Trans. on

Communications, Vol. COM-34, No. 10, pp. 1043-1045, October 1986.

12. S. G. Wilson, "Rate 5/6 Trellis-Coded 8-PSK," IEEE Transactions on Communications, Vol. COM-34, pp. 1045-1049, October 1986.

25
13. R. M. Tanner, "Algebraic Construction of Large Euclidean Distance Combined CodLug/Modulation Systems," presented at IEEE International Symposium on Information Theory, October 6-9, 1986, Ann Arbor, Michigan, and also Technical Report

UCSC-CRL-87-7, June 5, 1987.

14. H.C.A. van Tilborg, "Block Codes for the 2_-PSK Channel, _ presented at the 1986

IEEE International Symposium on Information Theory, Ann Arbor, October 6-9,

1986.

15. G.D. Forney, Jr., "Construction, Analysis and Decoding of Codes and Lattices via

Partitions and Trellis, _ presented at the 1986 IEEE International Symposium on Information Theory, Ann Arbor, October 6-9, 1986.

16. R.H. Deng and D.J. Costello, Jr., "High Rate Concatenated Coding System with

Bandwidth Efficient Inner Codes, _ presented at the 1986 IEEE International Symposium on Information Theory, Ann Arbor, October 6-9, 1986 and also submitted to

IEEE Trans. on Communications, 1987.

17. G. D. Forney, Jr., "Coset Codes I: Geometry and Classification," to appear in IEEE

Trans. on Information Theory (submitted in 1986).

18. G. D. Forney, Jr., "Coset Codes II: Binary Lattices and Related Codes," to appear in

IEEE Trans. on Informa_tion Theory (submitted in 1986).

19. A.R. Calderbank and N.J.A. Sloane, "An Eight-Dimensional Trellis Code, _ Proc.

IEEE, Vol. 74, pp. 757-759, 1986.

20. G. Ungerboeck, "Trellis-Coded Modulation with Redundant Signal Sets, Pat I: Introduction," IEEE Communications Magzine, Vol. 25, No. 2, February 1987.

21. G. Ungerboeck, "Trellis-Coded Modulation with Redundant Signal Sets, Pat H: State

of the Art, _ IEEE Communications Magzine, Vol. 25, No. 2, February 1987.

22. A. R. Calderbank and N. J. A. Sloane, "New Trellis Codes Based on Lattices and

Cosets," IEEE Trans. on Information Theory, Vol. IT-33, No. 2, March 1987.

23. G. J. Pottie and D. P. Taylor, "An Approach to Ungerboeck Coding for Rectangular

Signal Sets," IEEE Trans. on Information Theory, Vol. IT-33, No. 2, March 1987.

24. L. F. Wei, "Trellis-Coded Modulation with Multidimensional Constellations, _ IEEE

Trans. on Information Theory, Vol. IT-33, No. 4, July 1987.

26
25. T. Kasam], T. Takata, T. l_jiwara and S. Lin, "Error Control Systems with Combined Block Coding and M-ary PSK Modulations," The Proceedings of the lO-th

Symposium on In£ormation Theory and Its Applications, Enoshhna Island, Japan,

Nov. 19-21, 1987.

26. T. Kasan_ and S. Lin, _Bandwidth Effcient Block Codes for M-ary PSK Modulation,"

Technical Report to NASA Goddard Space Flight Center, Greenbelt, MD. December

1987.

27. T. Kasami, T. Takata, T. Fujiwara and S. Lin, _Construction of Block Codes for 2_-

ary PSK and 2_-ary QASK Modulations," Papers of IEICE of Japan, Vol. IT87-126,

pp. 49-54, March 1988.

28. R.H. Deng, S.S. Pirtrobon, A. Lafanachere, G. Ungerboeck, and D.J. Costello, Jr.,

_Multi-Dimensional Trellis Coded Phase Modulation," submitted to IEEE Trans. on

Information Theory, 1988.

29. T. Kasami, T. Takata, T. Fujiwara and S. Lin, "Cascaded Error Control Systems

with Block COded M-ary PSK Inner Codes, _ presented at 1988 IEEE International

Symposium on Information Theory, Kobe, Japan, June 19-24, 1988.

30. G.J. Pottle, D.P. Taylor and A.R. Calderbank, _Multi-Level Channel Codes Based

on Partitioning," presented at 1988 IEEE International Symposium on Information

Theory, Kobe, Japan, June 19-24, 1988.

31. G.J. Pottie, D.P. Taylor, _A Comparison of Reduced Complexity Decoding Algorithms

for Trellis Codes," presented at 1988 IEEE International Symposium on Information

Theory, Kobe, Japan, June 19-24, 1988.

32. R.G.C. Williams and P.G. Farrell, _Combined Coding and Modulation with Reduced

Decoding Complexity," presented at 1988 IEEE International Symposium on Information Theory, Kobe, Japan, June 19-24, 1988.

33. M. Rouanne and Daniel J. Costello, Jr., "Construction of Good Trellis Codes," presented at 1988 IEEE International Symposium on Information Theory, Kobe, Japan,

June 19-24, 1988.

34. K. Yamaguchi and H. Imai, "Trellis-Coded Modulation Using Binary Convolutional

Codes-Towards High Reliability and Simple Implementation," presented at 1988 IEEE

International Symposium on Information Theory, Kobe, Japan, June 19-24, 1988.

27
35. A.R. Calderbank, "Multi-Level Trellis Coded for the Gaussian Channel and for Channels Subject to Impulse Noise," Abstracts o[ Papers, 1988 IEEE International Symposium on Information Theory, Kobe, Japan, June 19-24, 1988.

36. S. Lin and T. Kasami, T. Fujiwara and T. Takata, "Cascaded Coding Schemes for

Error Control in Space and Satellite Communications," Proceedings of 1988 International Forum on Information and its Applications, Tokyo, Japan, June 27-30, 1988

(invited paper).

37. T. Kasami, T. Takata, T. Fujiwara and S. Lin, "On Construction of Bandwidth Efficient Block Codes," submitted to IEEE Trans. on Information Theory, 1988.

38. J.C. Proakis, Digital Communications, Mc Graw-Hill, 1983.

39. F.J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, NorthHolland, 1977.

40. T. Kasami, T. Fujiwara, T. Takata and S. Lin, _A Cascaded Coding Scheme for Error

Control and Its Performance Analysis," IEEE Trans. on Information Theory, Vol.

IT-34, No. 2, May 1988.

28
Table 1 Some short QPSK, 8-PSK and 16--PSK codes (the reference system is the uncoded

C n dB

Nad_ _ry__

d_.U= eli _ _ _ Inwh_t

C1 10 8 13/16 5._ _ x 2 _ P_e Yes

16 16 1/2 Y.

Co 32 16 21/32 7.2 24x2 e _ . P_3 Yes

C4 8 4 1 3.0 2x2 P_- Pa Vs Yes

16 4 9/8 3.52 2a x 2 RM_I _6 _e Yes

c_ 24 4 _l_s 3.83 26 x2 _._ /:_ v_ Yes

Or 16 8 27/32 5.28 2 x 2_ x 2 _ _ P_e Yes

Cs 16<._<32 8 ,_:3 101oglo__12 2x24x2 .P_Ln a--R.'_S e.

Ce 32 8 63/64 5.9 24 x 24 x 2 P..A_I RMa, s _ Yes

16-PSK0=4)Clo 32 4 5/4 3.9 2 x 26 x 2 P_ R-_,2 _ V32 Yes

t I_v-a,-_nt,un(:lel-36[_/2/phaBeah_.

Notations:

(1) V'. : {0,1}";

(2) P. denotes the (n, n - 1) linear binary code which consists of all the even-weight

binary n-tuple;

(3) p i denotes the dual code of P_, which consists of the all-zero and all-one vectors;

(4) RM_,_ denotes the j-th order binary Reed-Muller code of length 2_;

(5) s - RM_,_ denotes a shortened version of RM_,_;

(6) ez-Golay denotes the (24,12) extended Golay code.

29
d 2 - 2 dl = 0.586

3

0

d3=4

6

Ca) 8-PSK signal set and squared Euclidean distances

between signal points

(OOl}

(OLO)

6 (o11)

o

(ooo)

3

(110)

5

$

( lOl )

1

(lOO)

7

(111)

(b) QPSK signal set forajz=0 and

signal mapping

Figure I

(c) QPSK signalset for a=l and

signal mapping

3o
31

o

i ,,,.,B

..=U0

S_I

oo

q_

,.c:

t-f

bO

f,.4

_o

.<
b-bit

byte

__L_

n2

• • •

J

v

1st

Section

m-byte

Segment

m-th

Section

1st

Segment

k2-th

Segment

n2 -th

Segment

Figure 3 A Segment-Array

32
I00.

Upper bound P_}

M

%.4

0

0

0

o/"q

IM

0

0

10 "1

Simulation P! _)

$¢T0

Uncoded QPSK (two-byte segment)

7.0 8.0 9.0 10.0 11.0 12.0 13.0 14.0 15.0

SNR per symbol (dB)

Figure 4 Error performance of the 4--state 8-PSK block code (the 4-th code in Table 1)

33
10 .2 ,

I

Q)

bO

0

oo,.q

•w."l

0

0

10 _q.

10 4 •

10"5.

10-6.

10 .7,

10 "8

10"9_

10"10

/I

9.0

Uncoded QPSK (2 x 223-byte block)

_ Pc,6

10"1_ ! • , , • , ' , • ! • , • , ' • , • I _' • ,

7.0 8.0 10.0 11.0 12.0 13.0 14.0 15.0 16.0 17.0 18.0 19.(

SNR per symbol (dB)

Figure 5 The total probability of a decoding failure and a decoding error for the concatenated

coded modulation scheme with the (255,223) RS outer code and the 4-state 8-PSK

block inner code (the 4-th code in Table 1)

34
10

10

Q

L

10

10

gl

•_ 10

0

•_ 10

0

,o 10

0

0

0

,_ 10

_, 10

0 i I I I I I I |

5.0 5.5 6.0 6.5 7.0 7.5 8.0 8.5 9.0

SNR per. mbol (dB)

Figure 6 The probability of a decoding error for the concatenated coded modulation scheme

with the (255,223) RS outer code and the 4--state 8-PSK block inner code (the 4-th

code in Table 1)

35
10 0

10 -1

10 -2

10 -o

10 -4

10 -5

10 -s

10"7

10 _

-9

-1(

I 10

10

10

10

10

I0

i0

I0

I0

I0

I0

I0

I0

I0

I0

5.0 6.0

!

Uncoded QPSK

7.0 8.0 9.0 10.0 11.0 12.0 13.0 14.0 15.0 16.0 17.0 18.0 19.0 20.0 21.0

SNR per sym_l (dB)

Figure T Type-1 bit-error performance of the concatenated coded modulation scheme with the

(255,223) RS outer code and the 4--state 8-PSK block inner code (the 4-th code in

Table 1)

38
Uncoded QPSK

10 "8,

Computation based on P(I)

I¢

Computation based on P! z)

IC_8

10

7.0 8.0 9.0 10.0 11.0 12.0 13.0 14.0 15.0 16.0 17.0

SNR per symbol (dB)

Figure 8 Type-2 bit-error performance of the concatenated coded modulation scheme with

(255,223) RS outer code and the 4-state 8-PSK block inner code (the 4-th code in

Table 1)

37
10

Upper bound _)

,.q

0

t_

0

;J

0

o_

0

o_q

.,_

0

10-2.

10 -3.

10 -4 ,

10 "5.

Simulation P! 1)

Uncoded QPSK (4.5--byte segment)

10 .7

7.0 8.0 9.0 10.0 11.0 12.0 13.0 14.0 15.0 16.0

SNR per symbol (dB)

Figure 9 Error performance of the 16--state 8--PSK block inner code (the 5-th code in Table 1)

38
I

Uncoded QPSK (9 × 233-byte block)

SNR per symbol (dB)

Figure 10 The total probability of a decoding failure and a decoding error for the concatenated

coded modulation scheme with the (255,223) ItS outer code and the 16-state 8-PSK

block inner code (the 5-th code in Table 1)

39
10 -2s.

0

bO

o

0

o

o

o

G;

-29 ...... 10 . , .... , ,

4.5 5.0 5.5 6.0

SNR per symbol (dB)

Figure 11 The probability of a decoding error for the concatenated coded modulation scheme

with the (255,223) RS outer code and the 16--state 8-PSK block inner code (the 5--th

code in Table 1)

40
*=I

m

"O

0

_=_

I

o

-o

Q;

10 0

10 -1

10 -2

10 -s

10 4

10 -5

10 -e

10 -7

10 -8

10 -o

10 -lc

10

10

10

10

10

10

10

Uncoded QPSK

10

10

10

10

10

5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

SNR per symbol (dB)

Figure 12 Type--Ibit--errorperformance ofthe concatenatedcoded modulation scheme with the

(255,223)RS outer code and the 16-state8-PSK block innercode (the5-th code in

Table 1)

41
10"1.

10.2

10-3 Uncoded QPSK

Computation based on p!,_1)

Computation based on P_)o

101(

7.0 8.0 9.0 10.0 11.0 12.0 13.0 14.0 15.0 16.0 17.0

SNRper symbol (dB)

Figure 13 Type-2 bit-error performance of the concatenated coded modulation scheme with the

(255,223) RS outer code and the 16-state 8-PSK block inner code (the 5-th code in

Table 1)

42