Some Results Concerning Design And Decoding Of Turbo-codes

To appear in Problemy Pereda hi Informatsii, vol. 37, no. 3, 2001.

D. V. Truha hev, M. Lentmaier, and K. Sh. Zigangirov

Some Results Con erning Design and

1

De oding of Turbo{Codes .

The following problems related to the onstru tion and analysis of turbo{ odes are

onsidered: the asymptoti behavior of the interleavers (permutors), the asymptoti behavior of the minimum distan e, and also some examples of the pra ti al appli ation of the developed methods to on rete turbo{ odes. x1

Introdu tion

Turbo{ odes, also alled parallel on atenated odes, were introdu ed by a group of fren h authors in 1993 [1℄. They an be onsidered as a parti ular ase of low{density parity{

he k odes [2℄. The main advantage of these odes is that they an be de oded iteratively. While the omplexity of iterative de oding is onsiderably lower than the omplexity of maximum likelihood de oding (ML), the reliability is signi antly higher than for ML de odable odes with the same omplexity. There exist two dierent approa hes to the analysis of low{density odes. In the rst approa h random ensembles of odes are onsidered and ode hara teristi s averaged over the whole ensemble are estimated. This approa h is produ tive for the analysis of general

hara teristi s of the odes (for example minimum distan e, spe trum) and maximum likelihood de oding. The se ond approa h is to analyze spe ially hosen odes. The existen e of these odes in the ensemble is being proved using spe ial onstru tive methods. From our point of view this way is preferable for the analysis of iterative de oding of odes. The two approa hes were introdu ed in the work of Gallager [2℄ and developed, parti ularly, in the papers of Zyablov and Pinsker [3℄, Margulis [4℄,[5℄,[6℄, Tanner [7℄, Benedetto and Montorsi [8℄ and other re ently published works. 1 This

work was supported in part by Swedish Resear h Coun il for Engineering S ien es (Grant 98{216).

1

In this arti le we adhere to the se ond approa h and analyze the asymptoti properties of iterative de oding of binary turbo{ odes. The de oding omprises the iterative al ulation of the a posteriori probabilities of information symbols. The \ orre t" al ulation of these a posteriori probabilities puts some onstraints to the stru ture of the turbo{en oder, parti ularly to the onstru tion of the permutor (interleaver)2. The main results of this work are a proof of the existen e of a permutor, providing \ orre t" al ulation of the a posteriori probabilities of the symbols and a proof of the existen e of turbo{ odes with a minimum distan e growing logarithmi ally with the length of the ode. Binary turbo{ odes with omponent en oders having memory equal to one are studied more in detail. Although these odes have worse hara teristi s than turbo{ odes with

omponent en oders with greater memory their stru ture allows a simple mathemati al analysis. The authors are going to arry out the analysis of more ompli ated turbo{ odes in a dierent arti le [9℄ using the results of this paper. The ideas of the proof of the existen e of asymptoti ally \good" permutors were used for the pra ti al onstru tion of permutors with relatively short length. In the nal part of the arti le we will demonstrate that turbo{ odes with spe ially onstru ted permutors perform signi antly better than turbo{ odes with randomly hosen permutors. x2

Des ription of Blo k Turbo{Codes

A lassi al example of a rate 1=3 turbo{en oder is onsidered in Example 3 of the paper [10℄. The en oder uses systemati re ursive onvolutional (7; 5) en oders as omponent en oders and a standard interleaver onsisting of two tables as a permutor. In this paper we onsider a lass of rate 1=3 binary turbo{en oders ontaining the turbo{en oder des ribed above 2 The

term\interleaver" is usually used in the te hni al literature to des ribe a devi e onsisting of a

table whi h is lled olumnwise by input symbols and read rowwise. We will denote by \permutor" a general devi e that hanges the order of the symbols in the input information sequen e. The lass of these devi es ontains usual interleavers as parti ular ase. Before, we used the term \s rambler" but sin e this term determines other devi es in ommuni ation theory and ryptography we de ided to hange it, following the advi e of J. Massey.

2

as a parti ular ase. The generalization is that any systemati re ursive rate 1=2 memory m

onvolutional en oders an serve as omponent en oders and spe ial permutors are used instead of the standard interleaver. The onstru tion of these permutors is dis ussed in the following two paragraphs. Mathemati ally, a blo k permutor an be de ned as a square permutation matrix  of size N  N , having a single one in ea h row and in ea h olumn and zeros in the other positions. The task of the permutor is to hange the order of the symbols in the input information sequen e of length N : if a binary ve tor u = u0; u1; : : : ; u 1 enters the permutor then the ve tor u = u; u = u00; u01; : : : ; u0 1 appears at it's output. The binary sequen es u and u enter two parallel binary omponent en oders whi h are systemati re ursive rate 1=2 memory m

onvolutional en oders. The output of the rst en oder is the binary ode sequen e v = (v0(1) ; v1(1) ; : : : ; v(1) 1 ), the output of the se ond the binary sequen e v = (v0(2) ; v1(2) ; : : : ; v(2) 1 ). The sequen es u, v and v are transmitted over the hannel. Two ways to terminate the transmission an be onsidered. The rst is to add \tails" of m

symbols to the sequen es u and u . These symbols bring the en oders to the starting state, whi h usually is the zero state. Additionally to u, v and v these tails and the

orresponding ode symbols are then transmitted over the hannel. This auses a de rease of the transmission rate, but sin e usually N  m

the de rease is not signi ant. The se ond way is to use a \tail{biting" method. In this ase the starting states of the en oders are hosen su h that the input sequen es u and u bring the en oders to these starting states. For memory m

> 1 omponent en oders a ne essary and suÆ ient ondition for the possibility to onstru t a \tail{biting" ode is that the polynomial 1+ D and the feedba k polynomial of the en oders are relatively prime [11℄. In this ase the transmission rate of the

orresponding turbo{ ode is 1=3 (bits/ hannel symbol). For memory m

= 1 omponent en oders a ne essary and suÆ ient ondition to build a tail{biting ode is that the input information sequen e of ea h omponent en oder has even Hamming weight. This an be N

0

0

N

0

(1)

(2)

N

(1)

N

0

(1)

(2)

0

N

3

(2)

a hieved, for example, by adding a parity{ he k symbol to the input information sequen e. Later on we will assume that input sequen es of memory one en oders onsist of N 1 information and one parity{ he k symbol. The transmission rate is equal to (1 1=N )=3. In this paper we will follow the se ond way and onsider tail{biting turbo{ odes. We investigate the appli ation of these odes to the transmission over the binary symmetri hannel (BSC) and the additive white Gaussian noise (AWGN) hannel. Let r = (r0; r1; : : : ; r 1), r(1) = (r0(1), r1(1) , : : : , r(1) 1 ), and r(2) = (r0(2) , r1(2) , : : : , r(2) 1) denote the re eived information sequen e, the parity{ he k sequen e of the rst en oder and the parity{ he k sequen e of the se ond en oder, respe tively. In order to des ribe the de oding pro edure we introdu e the Lee metri on the set N = f0; 1; : : : ; N 1g of indi es of symbols u : dL(i; j ) = min(ji j j; N ji j j), i; j 2 N . The de oder operates in the following way. First, using the sequen es r and r(1) it

al ulates the a posteriori probabilities (APP) of the symbols from the information sequen e u. This is done by a symbolwise APP omponent de oder that is based on a forward ba kward algorithm, known as the BCJR algorithm [12℄. We have onsidered a modi ation of the BCJR algorithm, operating on a sliding window of size 2
+ 1. In this ase, for the al ulation of the a posteriori probability for symbol u , the rst omponent de oder operates with r ; r(1) , the 2
re eived symbols of the sequen e r whi h are losest (here and further on we onsider the Lee metri ) to r and the 2
re eived symbols of the sequen e r(1) , losest to r(1) . In the se ond de oding iteration the se ond omponent de oder operates again on a sliding window of size 2
+ 1. It al ulates the a posteriori probability of the symbol u0 0 = u from the permuted information sequen e u0, making now use of the newly al ulated a posteriori probabilities of the 2
symbols losest to u0 0 , symbol r(2)0 , the 2
symbols of the sequen e r(2) losest to r(2)0 and symbol r . Here n0 denotes the index of the symbol u in the sequen e u0. The additional information from the previous step is not used about the symbol u0 0 itself, in order to obtain independent new a posteriori probabilities. In the third iteration again the rst omponent de oder is used to al ulate the a posN

N

N

n

n

n

n

n

n

n

n

n

n

n

n

n

4

n

teriori probabilities of the symbols from the information sequen e u, using the a posteriori probabilities al ulated in the previous iteration and, as before, the 2
symbols of the re eived sequen e r(1) , losest to r(1) . The following iterations, up to I 1, are arried out analogously. In the last iteration, I , the omponent en oder uses both the 2
symbols of the sequen e u, losest to u and the 2
symbols of the sequen e u0 , losest to u0 0 and makes a hard de ision about the symbol u . The BCJR algorithm minimizes the bit error probability Pb of onvolutional odes and is optimal in this sense. It an be shown, that if
! 1 the performan e of the modi ed BCJR de oder, operating on a window of size 2
+1 approa hes the performan e of the standard BCJR de oder. Unfortunately, the BCJR algorithm an not be analyzed analyti ally and should be investigated numeri ally by Monte{Carlo methods. For the purpose of analysis we introdu ed a suboptimal APP de oding algorithm for onvolutional

odes, alled \max{path" algorithm. It al ulates the probability of the most probable path in the
{trun ated trellis orresponding to u = 0 and the probability of the most probable path in the
{trun ated trellis orresponding to u = 1. The ratio of these two probabilities is an approximation of the likelihood ratio for the symbol u , al ulated by BCJR algorithm. To des ribe the de oding of symbol u it is onvenient to introdu e a tree{like graph,
{graph (Figure 1), analogous to the one onsidered in [13℄. Ea h node within an even level of the tree represents one of the information symbols and ea h node within an odd level is asso iated with one of the omponent odes, de ning the relationship between the information symbols onne ted to this node. We will all the set of nodes in the even levels of the tree \(u ;
){ lan". The root node u (zero level), orresponding to the symbol we started to build the tree from, we denote by \ lan head". From this node arise two edges leading to the two nodes asso iated with the rst and the se ond omponent ode. These two nodes of the rst level we will all the lan head's \families" or \marriages" of the rst and se ond type, respe tively. Ea h of these two nodes is onne ted to the 2
nodes of the se ond level that represent the 2
n

n

n

n

n

n

n

n

n

n

5

information symbols losest to the lan head u in the rst and the se ond omponent ode, respe tively. These nodes of the se ond level we will all \ hildren" or \dire t des endants" of the lan head. Ea h dire t des endant of the lan head has one family, i.e. ea h node of the se ond level is onne ted with one node in the third level, orresponding to the other omponent

ode that ontains this des endant. If one parti ular symbol belongs to a family of the rst type as a des endant then it is the head of a family of the se ond type and vi e versa. It has 2
hildren in the fourth level. They are des endants of the lan head u in the se ond generation and so on. We will refer to the set of nodes in the 2lth level as lth generation. A (u ;
){ lan is alled \nondegenerated" up to the lth generation if all the symbol nodes in the tree up to the lth generation are dierent. We all a lan degenerated in the lth generation, if it is nondegenerated up to the (l 1)th generation and there exist two nodes in the lth and kth (for some k  l) generation asso iated with the same information symbol. A ode is alled \(l0 ;
){nondegenerated", if the lans of all ode symbols are nondegenerated up to the l0th generation. We will mark all symbol nodes in the tree by zeros and ones depending on the value of the information symbols orresponding to the nodes. To simplify referen es we will, a

ording to [13℄, all nodes marked by one \male nodes" and nodes marked by zero \female nodes". By agreement, the surname (family name) an be inherited by male individuals only. If the head of a family is a man and all his des endants are women, then we talk about \bran h extin tion". If there are no inheritors in the lth generation, l 2 f1; 2; : : : ; l0 g, we will talk about \family name extin tion". An upper bound on the nondegeneration level l0 of a ode is presented by the next simple theorem. n

n

n

Theorem 1 For any (l0 ;
){nondegenerated turbo{ ode with permutor size N the nondegeneration level l0 satis es

l0 <

log2 N=2 log2 (2
) 6

:

(1)

Let us onsider the nontrivial ase N > 2
. Then there are exa tly 2


hildren in ea h family. Let us onsider one arbitrary lan. Sin e the lan head has 2


hildren in ea h of it's two families, the rst generation ontains 4
symbols. Analogously, the se ond generation ontains 2(2
)2 symbols and so on. The l0 th generation ontains 2(2
) 0 symbols. For an (l0;
){nondegenerated ode, all symbols in the lan up to the l0 th generation are dierent and we have Proof:

l

N

1+2

l0 X k

=1

(2
)

k

> 2(2
)l0 :

(2)

Taking the logarithm on both sides of (2), we get (1). The theorem is proved. A more interesting and nontrivial problem is to nd a lower bound for l0 . The next paragraph is devoted to a onstru tive proof of the existen e of permutors for whi h the nondegeneration level is a logarithmi fun tion of N . The proof is based on the investigation of y les in the permutation matrix. x3

Constru tion of the Permutation Matrix

The permutor  = jj jj; i; j = 0; : : : ; N 1, de nes a permutation of indi es of the input sequen e u. Let us introdu e a fun tion (i) = j labeling the index of the symbol u 2 u in the sequen e u = u, i.e.  ( ) = 1. i;j

i

0

i; i

= i1, i2 , j2 , j3, i3 , i4 , : : :, j , j1 , are dierent and j = (i ); k = 1; : : : ; l,

De nition 1 For any even l we all the sequen e 

0  i ; j  N 1, k = 1; : : : ; l, su h that all i a y le of length l in the permutor matrix . k

k

k

Consider a sequen e of distan es (in Lee metri ): dL (i3 ; i4 ), : : :, d = dL(j ; j1 ). l

l

k

d1

k

= dL(i1 ; i2), d2 = dL(j2 ; j3), d3 =

l

De nition 2 Assume 9k1 ; k2 2 f1; : : : ; lg su h that 1  dk1 ; dk2  2
, and that 1  dk 


, 8k 2 f1; : : : ; lg n fk1; k2g. Then  is alled a rst type
{ y le of length l.

De nition 3 Assume 9k1 2 f1; : : : ; lg su h that 2
< dk1  3
, and that 8k 2 f1; : : : ; lg n fk1g. Then  is alled a se ond type
{ y le of length l.

7

1  d 
, k

The following lemma, analogously to Lemma C.1 [2℄ for homogeneous blo k low-density

odes, des ribes the relation between y les in the matrix  and the nondegeneration level l0 of the ode. Lemma 1 If the permutation matrix  does not ontain rst type
{ y les of length less

than 2l0 + 1 and does not ontain se ond type


{ y les of length less than l0

orresponding turbo{ ode is (l0 ;
){nondegenerated.

then the

The proof of the lemma is given in Appendix A. De nition 4 For any given even l we all the sequen e  = i1 , i2 , j2 , j3 , i3 , i4 , : : : il 1 , il , j1 (symbol jl is not present), where 0  ik  N 1, k = 1; : : : ; l, 0  jk  N 1, k = 1; : : : ; l

1, su h that all i

k

are dierent and jk = (ik ); k = 1; : : : ; l

of length l in the permutor matrix .

1, a half{ y le

Consider a sequen e d1 = dL(i1; i2 ), d2 = dL(j2; j3 ), d3 = dL(i3; i4 ), ..., d 1 = dL(i l

De nition 5 Assume 9k1 ; k2 1  dk 
, 8k 2 f1; : : : ; l

l

1 ; il ).

2 f1; : : : ; l 1g, su h that 1  dk1 ; dk2  2
, and that 1g n fk1; k2g. Then the sequen e  is alled a rst type


{half{ y le of length l. The positions (i ; j ); k = 1; : : : ; l 1 of the matrix  are alled verti es and position (i ; j1 ) is alled the free vertex of this
{half{ y le. k

k

l

A se ond type
{half{ y le is de ned analogously. Let us des ribe a method to onstru t a permutation matrix  without rst type
{

y les of length less than 2l0 + 1 and se ond type
{ y les of length less than l0 . We will

all these
{ y les \prohibited y les". Analogously, we will all rst type
{half{ y les of length less than 2l0 +1 and se ond type
{half{ y les of length less than l0 \prohibited half{ y les". In the beginning the matrix  ontains the symbol A in all it's positions. The symbol A denotes positions that are a

epted in the sense that is possible to pla e a 1 without forming a prohibited y le. We demand also that a position marked by A is not a free vertex of a prohibited half{ y le. 8

First we sele t some position in the rst row of the matrix ontaining A and hange it to 1. We pla e a 0 in front of ea h symbol in the matrix that is in the same row or

olumn as that 1. Then we hange A to U in the positions of the matrix that be ame una

eptable. We ontinue with the se ond row of the matrix hanging one of the symbols A (but not 0A) to 1, pla ing a 0 in front of ea h symbol in the matrix that is in the same row or olumn as that 1, and hanging A to U when ne essary. We repeat this pro edure until we pla ed a 1 in ea h row of the matrix. If at some point in this pro ess a row is en ountered, say the kth, in whi h no position ontains an A without an a

ompanying 0, we do a spe ial \emergen y pro edure". Let be a olumn in whi h the kth row ontains a U ( = U ). Find a row i0 < k su h that  0 = 0A,  ( 0) = 0A. Let 0 = (i0). For this row i0 we hange  0 to 1,  0 to 1,  0 0 to 0A, and hange the symbols A, 0A, U and 0U in the whole matrix a

ording to the new set of 1's. k

k; k

i ; k

k; i

k; i

i ; k

i

i ; i

Lemma 2 For any l0 , satisfying the inequality

16l03(2
)2 0  N l

(3)

;

it is possible to perform the emergen y pro edure without forming prohibited y les.

The proof of Lemma 2 is given in Appendix B. Theorem 2 There exists an (l0 ;
){nondegenerated turbo{ ode with permutor size N , su h that

1 (log N 3 log (log N ) 4) 1 2 2 2 log2(2
) 2 Proof: Let us hoose a positive integer l0 , su h that l0 

:

(4)

4 + 3 log2 l0 + 2l0 log2 (2
)  log2 N < 4 + 3 log2(l0 + 1) + 2(l0 + 1) log2 (2
) : (5) A

ording to Lemma 2 there exists an (l0;
){nondegenerated ode for this l0. Let us further assume, that Theorem 2 is wrong and for ea h (l0;
){nondegenerated ode the inequality 1 (log N 3 log (log N ) 4) l0 + 1 < (6) 2 2 2 log (2
) 2 2

9

is satis ed. Combining (5) and (6) we get log2 N 3 log2(l0 + 1) 4 < log2 N 3 log2 (log2 N ) 4 2 log2(2
) 2 log2(2
) and onsequently log2(l0 + 1) > log2 (log2 N ) :

;

(7) (8)

The last inequality is in ontradi tion with (6). This proves the theorem. In the next paragraph we will analyze (l0 ;
){nondegenerated turbo{ odes with memory one omponent en oders, alled in short \memory one turbo{ odes". x4

Analysis of Memory One Turbo{Codes

Consider an (l0;
){nondegenerated memory one turbo{ ode with identi al systemati onvolutional omponent en oders whose generator matri es, in polynomial form, are equal to (1 1=(1 + D)). The a tive olumn distan e a [14℄ of this ode is equal to the row distan e and is given by the formula a = a = 2 + j . Let us study the asymptoti minimum distan e behavior of the ode if N ! 1. Assume N  4 and hoose
= b(log2 N )=2 , where b
denotes the integer part of a number. Consider an arbitrary nonzero binary information sequen e u at the input of the en oder, and an arbitrary nonzero symbol u(0) out of the sequen e u. Let us onstru t an (u(0);
){

lan for this symbol. It will be nondegenerated up to the l0th generation a

ording to the

hoi e of the turbo{ ode. First we onsider the ase where family name extin tion does not o

ur up to the l0 th generation. Then there is at least one one in ea h generation of the lan. If the onsidered re ursive systemati en oder is in the zero state an in oming one produ es at least one parity{ he k symbol. This implies that the weight of the orresponding ode sequen e, w(0) , is bounded from below by the inequality 4 log2 N 5 (9) w(0)  2l0  log2 (log2 N ) log2(log2 N ) ;

j

j

r j

10

whi h follows from (4). Inequality (9) implies log2 N w(0)  (10) log2 (log2 N ) 9 : Consider now the ase when family name extin tion o

urs in the lth generation, where l  l0 . Then there exists a nonzero symbol in the (l 1)th generation su h that all it's des endants are zeros. This symbol, when entering the omponent en oder, produ es a burst of nonzero ode symbols having weight at least
+ 1 a

ording to the formula for the olumn distan e of the ode. Hen e, in this ase the following inequality is satis ed   log N log N 2 (0) > 2 : (11) w 2+
=2+ 2 2 It follows from (10) and (11) that for N  4 there exists a memory one turbo{ ode whose minimum distan e is bounded from below by the inequality log2 N (12) dmin  log2(log2 N ) 9 : We will now prove that for any memory one turbo{ ode with permutor size N the inequality dmin  6 log2 N + 4 (13) is satis ed. Choose
= 2. It follows from Theorem 1 that the nondegeneration level of a turbo{

ode with permutor size N satis es l0  log2 N

1

(14)

:

Sin e the turbo{ ode is not (l0 + 1; 2){nondegenerated there exists a rst type
{ y le of length l  2l0 + 2 or a se ond type
{ y le of length l  l0 in the permutor matrix . Assume  = i1 ; i2; j2 ; j3; i3; i4 ; : : : ; j ; j1 is this y le and the orresponding distan es (in Lee metri ) are fd1 = dL(i1 ; i2), d2 = dL(j2 ; j3), d3 = dL(i3 ; i4), : : :, d = dL(j ; j1 )g. Consider an information sequen e u, su h that u = 1; k = 1 : : : l, and all other symbols are zeros. The ones in the permuted sequen e u = u will be pla ed in the l

l

ik

0

11

l

positions j1; j2 ; : : : ; j . It follows from the formula for the a tive olumn distan e, that the weight of the ode sequen e is l

w (u) 

l X k

=1

(d + 2)

l=

k

l X k

The onstraints in the de nition of a
{ y le imply

=1

dk + l :

(15)

w(u)  (l + 2)
+ l :

(16)

Using
= 2, and l  2l0 + 2, where l0 is bounded from above by (14), we get w(u)  3l + 4  3(2l0 + 2) + 4 = 6l0 + 10  6(log2 N

1) + 10 = 6 log2 N + 4 : (17)

We have shown that for any memory one turbo ode there exists a ode word whose weight is bounded from above by (13). It follows from (13) that the minimum distan e of a memory one turbo{ ode is bounded from above by a logarithmi fun tion of N . Inequality (12) implies the existen e of a turbo{

ode whose minimum distan e also grows almost logarithmi allywith N . The se ond bound will be strengthened in the next paragraph. Let us onsider transmission with an (l0;
){nondegenerated memory one turbo{ ode over the BSC with rossover probability p. We will study iterative de oding with I iterations (I equals to l0) of an arbitrary symbol u ; n = 0; 1; : : : ; N 1, of the information sequen e u. To simplify the analysis we onsider the ase when the de ision u^ is made using the set of des endants from only one marriage of u in the (u ;
){ lan. This in reases the bound for the de oding error probability. Let us denote by V (u ) the set of des endants of the head of the (u ;
){ lan up to the l0th generation and ode symbols

orresponding to them. The set of orresponding re eived symbols we will designate by R(u ). The set V (u ) we will all odeword. Codewords having u = 0 we will denote by V0(u ) and odewords with u = 1 by V1(u ). Let P (R(u )jV (u )) be the onditional probability to re eive the word R(u ) onditioned that the word V (u ) was sent. It an be shown that if the de oder uses the \max{path" algorithm in ea h iteration step then iterative de oding with I = l0 iterations is equivalent to the determination of two maxima: n

n

n

n

n

n

n

n

n

n

n

n

n

n

n

n

12

P (0) =

max P (R(u )jV0(u )) and P (1) = Vmax P (R(u )jV1 (u )). If P (0) > P (1) then 1( ) the de ision is u^ = 0, if P (0) < P (1) then the de ision is u^ = 0, if P (0) = P (1) then the de ision is arbitrary. In the analysis we will assume that the de ision is erroneous in this latter ase, whi h in reases the bound on the error probability. The onsidered algorithm is an analog of maximum likelihood de oding in the l0 {trun ated
{graph. Let us estimate the probability of erroneous de ision about symbol u . Without loss of generality we assume that the all{zero sequen e u = 0 is transmitted. In order to nd an upper bound on the bit error probability Pb = P (^u = 1) we onsider the sets V~1(u ) of the des endants of the symbol u = 1 being inheritors of the family name and the orresponding ode symbols. In this onsideration we will take into a

ount only one dire t des endant (if it exists) of a male symbol u 2 V~1(u ), namely, either the des endant losest to the symbol   ~ u from the left or the des endant losest to the symbol u from the right. Let w V1 (u ) be the Hamming weight of the set V~1 (u ). The union bound gives the inequality X (18) D (V~1 ( )) ; Pb = P (^u = 1) < V0 (u )

n

n

n

n

un

n

n

n

n

n

n

n

m

n

m

m

n

n

w

n

un

V~1 (u ) n

p

where D = 2 p(1 p) is the Bhatta haryya parameter and the summation is taken over all possible sets V~1 (u ). Let us show that 1 a D2+
+ a D ; (19) Pb < 2 1 a where a = 12 2 . Assume I = l0 = 1. If family name extin tion o

urs in the rst generation of the set V~1(u ), all dire t des endants of u are zero symbols. There exist two ombinations V~1 (u ), both of weight 2+
, whi h an ause a de oding error. An upper bound on the probability of error, aused by ea h of the ombinations is equal to D2+
. If family name extin tion does not happen in the rst generation then an error is aused by one of the ombinations of information symbols like fu
= 0; : : : ; u 1 = 0; u = 1; u +1 = 0; : : : u + 1 = 0; u + = 1; u + +1 = 0; : : : ; u +
= 0g or fu
= 0; : : : ; u 1 = 0; u = 1; u +1 = 0; : : : ; u 1 = 0; u = 1; u +1 = 0; : : : ; u +
= 0g, where 0 < j 
. Probabilities of errors,

aused by these ombinations are upperbounded by D2+ . Summing D2+ over all j  1 n

I

I

D D

n

n

n

n

n j

n j

n

n

n

n

n

n

n

n

n j

n j

n j

n

j

13

j

n j

and adding an upper bound for the ase of family name extin tion we get for I = 1 2D2 D + 2D2+
: Pb < (20) 1 D In the general ase we use analogous arguments. Consider all odewords V~1 (u ), where family name extin tion o

urs in the lth generation, l 2 f1; 2; : : : ; l0g. The probability of error, aused by at least one su h a odeword, is upperbounded by   1 2 D2 2 1 D D2+
= 2a 1D2+
: (21) The summation over all l; 1  l  l0 = I; gives an upper bound on the probability of error, aused by at least one of the odewords where family name extin tion o

urs, whi h is equal to the rst term in (19), namely (22) 2 11 aa D2+
: The probability of error, aused by at least one of the odewords V~1 (u ), where family name extin tion does not happen up to the I th generation, is upperbounded by   2 D2 (23) D 1 D = Da ; whi h is equal to the se ond term in (19). The rst part of (19), and onsequently Pb , onverges to zero when
! 1 and I ! 1, if a < 1 or, equivalently, D < 1=2, whi h is the same as if p 2 3 = 0:067 : p < p0 = (24) 4 In the paper [13℄ the iterative limit p0 for the BSC was de ned as the supremum of

hannel rossover probabilities su h that the de oding bit error probability Pb onverges to zero at least exponentially with the number of iterations if the number of de oding iterations tends to in nity. The value p0 , found in (24), is a lower bound for p0. The ase of transmission over the AWGN hannel an be analyzed analogously. In   this ase the Bhatta haryya parameter D = exp R b0 , where R = 1=3 and Eb=N0 is the signal{to{noise ratio per bit. D < 1=2 is a suÆ ient ondition for the exponential n

l

l

I

n

I

I

E N

14

onvergen e of the bit error probability to zero with the number of iterations I . Thus the signal{to{noise ratio in the hannel should ex eed 



Eb = 3 ln2 = 2:08 N0 0

(3:18 dB)

:

(25)

The value (Eb=N0 )0 is an upper bound on the iterative limit (Eb =N0)0 for the signal{ to{noise ratio in the AWGN hannel. Results of the al ulation of the iterative de oding bit error probability Pb as a fun tion of the number of iterations I = l0 , using Monte{Carlo methods, are presented in Figure 2. The ase of transmission with memory one turbo{ odes over the AWGN hannel is onsidered. It is easy to see that the theoreti al bound on the iterative limit is in good agreement with the numeri al al ulations. Moreover, the slope of the urves orresponds to the theoreti al estimation:   d(log10 Pb ) 1 2 D2 ; D< :  log (26) 10 dI 1 D 2 The lower bound on the minimum distan e of memory one turbo{ odes obtained in this paragraph will be strengthened and generalized to arbitrary turbo{ odes in the next paragraph. Moreover, the onstru tive algorithm for the analysis of the asymptoti properties of a permutor, studied in x 3, will be modi ed to a synthesis algorithm for \good" permutors for turbo{ odes. x5

Constru tive Generation of Permutors for Turbo{ Codes

Consider a modi ation of the method for permutor onstru tion, des ribed in x 3, in order to obtain turbo{ odes whose minimum distan e is proportional to the logarithm of the ode length N . Consider a y le  = i1; i2 ; j2; j3 ; i3; i4 ; : : : ; j ; j1 and the sequen e of distan es d1 = dL (i1 ; i2 ), d2 = dL (j2 ; j3 ), d3 = dL (i3 ; i4 ), : : :, d = dL (j ; j1 ). l

l

15

l

De nition 6 The summary distan e dsum of the y le  is dsum =

l X i

=1

(27)

di :

The summary distan e of a half{ y le an be de ned analogously. Lemma 3 There exists a permutor matrix  of size N N , su h that the summary distan e of any of it's y les satis es the inequality

log2 N 1 : (28) log2 3 Proof: For any xed dsum, a matrix without y les with summary distan e less than dsum

an be built using a modi ation of the onstru tive pro edure, des ribed in x 3. The dieren e is that y les and half{ y les with summary distan e less than dsum will be

onsidered as prohibited. Let us estimate nr(dsum), the maximal number of symbols in a row of the matrix , that an be marked by U (or 0U ). Consider an arbitrary row k. Let us ount the number of positions (k; ) in the row su h that pla ing a 1 in this position will reate a

y le  = fi1 = k; i2; j2 ; j3; : : : ; j ; j1 = g of length l with summary distan e Æ. Sin e Æ = dL (i1 ; i2 )+ dL(j2 ; j3 )+ : : : + dL(j ; j1 ), the number of su h positions does not ex eed the number of dierent representations of the positive integer Æ as a sum of l ordered positive integers multiplied by 2 , i.e. 11
2 . The fa tor 2 appears be ause when building a y le we an l times hoose between two dierent dire tions to move. Analogous al ulations

an be done for half{ y les. Then the total number of positions, ausing prohibited y les and half{ y les with summary distan e Æ, does not ex eed  X Æ 1 2 = 2
3 1: (29) l 1 =1 We prohibit all y les and half{ y les with summary distan e Æ < dsum and therefore dsum 

k

l

k

l

l

Æ l

l

l

Æ

l

Æ

l

nr (dsum)  2

dsum X Æ

=1

1

3 1 = 3 sum Æ

d

1

1:

(30)

An analogous bound an be derived for n (dsum), the maximal number of symbols in a

olumn of the matrix , that an be marked by U (or 0U ). 16

For xed N hoose some dsum, satisfying 2
3 sum 1  N < 2
3 sum d

d

(31)

:

It follows from 2 max(n (dsum); nr(dsum)) = 2
3 sum 1 2 < N (see Appendix B), that the emergen y pro edure an always be performed and it is possible to onstru t a matrix , whi h does not ontain y les with summary distan e less than dsum. From the right hand side of (31) we get (28). The lemma is proved. Consider now a turbo{ ode with permutor matrix , satisfying the ondition of Lemma 3 with omponent odes whose a tive olumn distan e satis es the inequality d

a j  (j + 1); j  0 ;

(32)

where is some positive onstant. This ondition is satis ed for all re ursive systemati

onvolutional en oders. Theorem 3 For any positive integer N there exists a turbo{ ode with information sequen e length N whose minimum distan e satis es

dmin  (log2 N

1)

(33)

;

where the onstant  depends only on the type of the omponent en oders.

Assume the a tive olumn distan e of the omponent odes satis es inequality (32). Consider an arbitrary nonzero information sequen e u. For this sequen e it is always possible to nd a y le  = i1 , i2 , j2 , j3, : : :, j , j1 , su h that u = 1; k = 1; : : : ; l, and the

omponent en oders do not visit the zero state within the intervals between the positions i1 and i2 , j2 and j3 , : : :, j and j1 . The summary distan e of this y le is lowerbounded by inequality (28). Making use of (32) we nd that the weight of the ode sequen e v is lowerbounded by

w (v )  (34) 2 log 3 (log2 N 1) ;

Proof:

l

l

2

whi h implies (33). The theorem is proved.

17

ik

The existen e of turbo{ odes whose minimum distan e grows logarithmi ally with the

ode length follows from (33). In ombination with the paper [15℄, whi h proves that the minimum distan e of turbo{ odes annot grow faster than logarithmi ally with the ode length, Theorem 3 determines the minimum distan e behavior of optimal turbo{ odes with respe t to their ode length. In the proof of Lemma 3 a onstru tive method was used to analyze permutors, for whi h the summary distan es of all y les satisfy (28). A modi ation of this method was used in order to onstru t turbo{ odes with lengths N = 500; 1000 and 2000 with memory m = 2 re ursive systemati onvolutional omponent en oders. Simulation results for transmission with these odes and odes with uniform interleavers of orresponding lengths over the AWGN hannel are given in Figure 3. It is easy to see that the bit error probability for turbo{ odes with spe ially hosen permutors is at least ten times smaller than the bit error probability for turbo{ odes with uniform interleavers of orresponding length at a signal{to{noise ratio of 2 dB. Appendix A. Proof of Lemma 1.

Let us assume, that Lemma 1 is wrong and the turbo{ ode orresponding to the y le{ free permutor , appearing in the ondition of the lemma, is degenerated in the lth generation, l  l0 . This implies that there exists an (u 0 ;
){ lan that is degenerated in the lth generation, i.e. some symbol u from the lth generation of the lan appears one more time either as the head of the lan or as a des endant in the kth generation, k  l. We will he k all possible on gurations of the lan and show that the matrix  in all ases

ontains at least one of the y les, listed in the ondition of the lemma. Case 1: The symbol u oin ides with it's an estor in the kth generation, k < l, (Figure 4 (a)). Let us denote the symbols along the path from u down to the symbol u by u ; u +1 ; : : : ; u 1 ; u = u . Let f ; f 2 f1; 2g, be the type of the family (the number of the en oder) of the symbol u ; r = k; : : : ; l 1 (the head of the family), and j = (i ); r = k; : : : ; l. Sin e the (u 0 ;
){ lan is nondegenerated up to the (l 1)th i

il

il

ik

il

ik

ik

il

il

ik

r

r

ir

r

r

i

18

generation, all the indi es i ; i +1; : : : ; i 1 are dierent. It follows from the stru ture of the ode that f 6= f +1 for any r. Consider now two sub ases. Case 1.1: f = 1; f 1 = 2. Then dL (i ; i +1 ) 
, dL (j +1 ; j +2 ) 
, : : :, dL (j 1 ; j ) 
. Sin e i = i , the sequen e i ; i +1; j +1; j +2, : : : ; j 1; j is a rst type
{ y le of length l k  l0 . (The ase f = 2; f 1 = 1 an be onsidered analogously.) Case 1.2: f = 1; f 1 = 1. Then dL (i ; i +1 ) 
, dL (j +1 ; j +2 ) 
, : : :, dL (j 2 ; j 1 ) 
, dL(i 1 ; i ) 
. Sin e i = i we have dL(i ; i +1) 
, dL(i ; i 1) 
) dL(i +1; i 1)  2
. This implies that the sequen e i 1 ; i +1, j +1; j +2, i +2; : : : ; j 1 is a rst type
{ y le of length l k 1  l0 1. (The ase f = 2; f 1 = 2 an be onsidered analogously.) Case 2: There exists a symbol that is a des endant of the lan head in the lth generation from one marriage and a des endant of the lan head in the kth generation from another marriage, k  l, and this symbol is not a des endant of itself (Figure 4 (b)), i.e. u = u 0 . Let us denote by u 0 ; u 1 ; : : : ; u 1 ; u the symbols along the path from the lan head u 0 down to u and by u 0 ; u 01 ; : : : ; u 0 1 ; u 0 the symbols along the path from u 0 down to u 0 . Let f be the type of the family of symbol u ; r = 0; : : : ; l 1 (the head of the family), f 0 be the type of the family of u 0 ; q = 1; : : : ; k 1, and j = (i ); r = 0; : : : ; l, j 0 = (i0 ); q = 1; : : : ; k. All the indi es i0 ; i1 ; : : : ; i 1 ,i01 ; : : : ; i0 1 ; i0 are dierent sin e the (u 0 ;
){ lan is nondegenerated up to the (l 1)th generation. This ase an also be divided into two sub ases. Case 2.1: f 1 = 1; f 0 1 = 2. Then dL (i ; i 1 ) 
, dL (j 1 ; j 2 ) 
, : : : ; dL (i1 ; i0 ) 
, dL(j0 ; j10 ) 
; dL(i01; i02 ) 
, : : : ; dL(j 0 1, j 0 ) 
. Sin e i = i0 , the sequen e i ; i 1 ; j 1 , : : : ; i0 , : : : ; i0 1 , j 0 1 , j is a rst type
{ y le of length l + k  2l0 . (The ase f 1 = 2; f 0 1 = 1 an be onsidered analogously.) Case 2.2: f 1 = 1; f 0 1 = 1. Then dL (i ; i 1 ) 
, dL (j 1 ; j 2 ) 
, : : : ; dL (i1 ; i0 ) 
, dL(j0 ; j10 ) 
; dL(i01 ; i02) 
; : : : ; dL(i0 1; i0 ) 
. Sin e i = i0 , we have dL(i0 ; i0 1) 
; dL(i0 ; i 1) 
) dL(i0 1; i 1)  2
. This implies that the sequen e i0 1 ; i 1; j 1, : : : , i0 , : : : , j 0 2 , j 0 1 is a rst type
{ y le of length l + k 1  2l0 2 (sin e k < l in this ase). (The ase f 1 = 2; f 0 1 = 2 an be onsidered analogously.) k

r

l

k

k

k

k

k

l

l

r

k

l

k

k

k

k

k

k

l

k

l

l

k

l

l

l

l

l

k

l

l

k

k

k

k

l

k

k

k

k

k

k

k

l

k

l

l

l

il

i

il

i

il

i

i

il

ik

i

i

ik

r

ik

ir

iq

q

q

ik

r

l

q

k

r

k

i

l

l

k

l

k

l

l

l

k

l

l

l

l

k

k

l

k

k

l

l

k

k

k

l

k

k

l

k

l

l

l

k

k

k

k

l

l

k

19

k

l

l

There exists a symbol whi h is a des endant of some symbol u from the marriage fe in the lth and kth generation of the lan, 0  n < k  l, su h that it is not a des endant of itself and it does not oin ide with des endants of the lan head from another marriage up to the lth generation. (Figure 4 ( )). Let f denote the type of the family of symbol u ; r = n + 1; : : : ; l 1 (the head of the family), f 0 denote the type of the family of u 0 ; q = n + 1; : : : ; k 1 and j = (i ); r = n + 1; : : : ; l, j 0 = (i0 ); q = n + 1; : : : ; k. All the indi es i +1 ; i +2; : : : ; i 1,i0 +1; : : : ; i0 1; i0 are dierent sin e the (u 0 ;
){ lan is nondegenerated up to the (l 1)th generation. This ase an be divided into four sub ases. Case 3.1: k = n + 1; f 1 = 1; fe = 2. Then dL (i ; i 1 ) 
, dL (j 1 ; j 2 ) 
, : : :, dL (i +2 ; i +1 ) 
and dL (j +1 ; j 0 +1 )  2
, sin e u +1 and u 0 +1 belong to one family fe = 2. It follows from k = n +1; i0 = i that the sequen e i ; i 1 ; j 1 ; : : : ; j +1 ; j is a rst type
{ y le of length l n  l0. (The ase k = n + 1; f 1 = 2; fe = 1 an be onsidered analogously.) Case 3.2: k = n + 1; f 1 = 1; fe = 1. Then dL (i ; i 1 ) 
, dL (j 1 ; j 2 ) 
, : : :, dL (j +1 ; j +2 ) 
and dL (i +1 ; i0 +1 )  2
, sin e u +1 and u 0 +1 belong to one family fe = 1. It follows from i = i0 +1 that dL(i +1 ; i0 +1)  2
, dL(i 1 ; i ) 
) dL(i +1; i 1)  3
. This implies that the sequen e i +1; i 1; j 1 ; : : : ; j +2 ; j +1 is either a rst or a se ond type
{ y le of length l n 1  l0 1. (The ase k = n +1; f 1 = 2; fe = 2 an be onsidered analogously.) Case 3.3: k > n + 1; f 1 = 1; f 0 1 = 2. Then dL (i ; i 1 ) 
, dL (j 1 ; j 2 ) 
, : : : ; dL (i0 2 ; i0 1 ) 
, dL (j 0 1 ; j 0 ) 
. If fe = 2 then dL (j +1 ; j 0 +1 )  2
, otherwise dL (i +1 ; i0 +1 )  2
. It follows from i0 = i that the sequen e i ; i 1 ; j 1 ; : : : ; i0 2 , i0 1 , j 0 1 , j is a rst type
{ y le of length l + k 2n 1  2l0 2 (The ase k > n +1; f 1 = 2; f 0 1 = 1 an be onsidered analogously.) Case 3.4: k > n + 1; f 1 = 1; f 0 1 = 1. Then dL (i ; i 1 ) 
, dL (j 1 ; j 2 ) 
, : : : ; dL (j 0 2 ; j 0 1 ) 
, dL (i0 1 ; i0 ) 
. If fe = 2 then dL (j +1 ; j 0 +1 )  2
otherwise dL (i +1 ; i0 +1 )  2
. It follows from i0 = i that dL (i 1 ; i0 ) 
, dL (i0 ; i0 1) 
) dL (i0 1 ; i 1 )  2
. This implies that the sequen e i0 1 ; i 1 ; j 1 ; : : : ; i0 2; j 0 2 ; j 0 1 is a Case 3:

in

r

ir

q

iq

r

n

n

r

l

n

q

k

i

k

l

n

l

n

n

q

l

l

in

n

in

l

k

l

l

l

l

n

l

l

l

n

n

l

n

l

l

l

in

n

n

n

n

in

l

n

l

l

l

n

l

n

l

l

l

n

l

l

k

n

k

l

k

k

n

k

n

l

k

l

n

l

l

l

k

k

l

k

l

k

l

k

n

n

k

l

k

l

k

k

l

l

n

k

k

l

l

k

20

n

k

l

k

l

l

k

k

k

k

rst type
{ y le of length l + k 2n 2  2l0 2. (The ase k > n +1; f 1 = 2; f 0 1 = 2

an be onsidered analogously.) We onsidered all possible ases of degeneration of a lan. All of them result in the existen e of either a rst type
{ y le of length less than 2l0 + 1 or a se ond type
{

y le of length less than l0 . This implies that the onstraints, imposed by Lemma 1 to the permutation matrix , are suÆ ient for (l0;
){nondegeneration of the orresponding turbo{ ode. Lemma 1 is proved. l

k

Appendix B. Proof of Lemma 2.

We have to prove that making both  0 = 1 and  0 = 1 simultaneously will not

reate a prohibited
{ y le and also prove that if inequality (3) is satis ed, we always an nd su h an i0 that  0 = 0A,  ( 0) = 0A. The rst statement we will prove by ontradi tion. Let us assume that setting  0 and  0 to 1 and  0 0 to 0A reates a prohibited
{ y le. This
{ y le should ontain both points, (i0; ) and (k; 0 ), as verti es, sin e the 0A's formerly in these positions indi ated that no prohibited
{ y les existed through either point alone. Let this
{ y le be  = fi1 = k; i2; j2 ; j3 : : : ; i = i0 ; : : : ; i ; j ; j1 = 0 g. Case 1: n is even. Then the sequen e  = fi1 = k; i2 ; j2 ; j3 : : : ; i = i0 ; 0 g was a
{half{ y le of length n  l with free vertex (k; 0 ) before the emergen y pro edure. This
{half{ y le was prohibited. If it was a rst type
{half{ y le then it was prohibited sin e n  l  2l0 . If it was a se ond type
{half{ y le then  was a se ond type
{ y le. This leads to the onstraint n  l  l0 1, whi h is satis ed only if  was a prohibited
{ y le. This ontradi ts the fa t that the free vertex of the
{half{ y le  was marked by 0A. Case 2: n is odd. Then the sequen e i = i0 ; i +1 ; j +1 ; : : : ; j ; 0 formed a prohibited
{ y le before the emergen y pro edure. This is in ontradi tion with the way of

onstru tion of the matrix. We proved that the emergen y pro edure does not reate prohibited
{ y les. i ; k

i ; k

k; i

k; i

i ; k

k; i

i ; i

k

i

n

l

l

i

0

n

i

i

0

0

n

21

n

n

l

i

Let us show that if (3) is satis ed, it is always possible to perform the emergen y pro edure. We denote by nr(l0 ;
) the maximal number of symbols in a row of the matrix marked by U or 0U and by n (l0 ;
) the maximal number of symbols in a olumn of the matrix marked by U or 0U . We will show that if N  2 max(nr(l0 ;
); n (l0;
)), it is always possible to nd an i0 su h that  0 = 0A,  ( 0) = 0A. Consider a row of the matrix (say the kth) where we annot nd symbols A. If N  2 max(nr(l0;
), n (l0;
)) then at least one{half of the symbols in the row are symbols 0A. Assume that some symbol at position (k; j ) is marked by 0A. This means that there is a 1 at position ( 1(j ); j ) in the j th olumn. If the symbol at position ( 1(j ); ) is 0A then we have found i0 =  1(j ). Assume that for all j su h that  = 0A the symbol  1 ( ) 6= 0A. Then the fra tion of symbols 0A in the th olumn is less than one{half (the symbol at position (k; ) is U ). This fa t is in ontradi tion with our assumption N  2 max(nr (l0 ;
); n (l0 ;
)), whi h implies that we an nd an i0 su h that  0 = 0A,  ( 0 ) = 0A . Let us now estimate nr(l0;
). Consider an arbitrary row k. We will ount the maximal number of positions (k; ) in this row su h in whi h a 1 would reate a
{ y le  = fi1 = k; i2; j2 ; j3; : : : ; i ; j ; j1 = g, where dL(i1 ; i2) 
, dL(j2 ; j3) 
, dL(i3; i4 ) 
, ...,dL (j ; j1 ) 
. What is the number of possibilities to reate su h a
{ y le? If i1 = k is xed then i2

an take at most 2
dierent values be ause dL(i1 ; i2) 
. j2 = (i2) is xed if i2 is xed. For xed j2 the index j3 an be hosen by at most 2
dierent ways sin e dL(j2 ; j3) 
and so on. Finally we dedu e that there are at most (2
) ways to reate su h a
{ y le and onsequently there are at most (2
) positions (k; ) in the kth row whi h an be a vertex of this y le. The distan es between some verti es in a rst type
{ y le an be greater than
. It follows from the de nition of a rst type
{ y le that there exist at most (2
) (1 + l + (l 1)l=2) positions in a row whi h an be a vertex of a rst type
{ y le of length l. Analogously, there are at most l(2
) positions in a row whi h an be a vertex of a se ond i ; k

k; i

k

k;j



k

j ; k

k

i ; k

k; i

k

l

l

k

l

l

l

k

l

l

22

type
{ y le of length l, at most (2
)( 1) (1 + l 1 + (l 2)(l 1)=2) positions whi h

an be a free vertex of a rst type
{half{ y le of length l and at most (l 1)(2
)( 1) positions in a row whi h an be a free vertex of a se ond type
{half{ y le of length l. Taking into a

ount all prohibited
{ y les and
{half{ y les we get the following bound for nr(l0;
): l

l

nr (l0 ;
) 

2l0  X l

=1



 0 1 X 1) (2
) + l(2
) + 2 (2
) + l(2
)  l

l

l (l

l

l

l

l



=1

 2l0(2
)2l0 1 + l0 + l0(l02 1) + l0(l0 1)(2
)2l0  8l03(2
)2l0 :

(35)

The same bound is valid for n (l0 ;
). As it was shown, the emergen y pro edure an be performed if N  2 max(nr(l0 ;
); n (l0;
)). If we substitute the bound (35) in this inequality we see that a permutor matrix without prohibited y les an be onstru ted for any N satisfying (3). The lemma is proved.

23

Referen es

[1℄

Berrou C., Glavieux A., Thitimajshima P., Near Shannon Limit Error Corre ting Cod-

ing and De oding: Turbo{Codes. // Pro eedings IEEE Int. Conf. on Communi ations, Geneva, Switzerland, 1993, p. 1064{1070.

[2℄

Gallager R. G.,

[3℄

Zyablov V. V., Pinsker M. S.,

[4℄

Margulis G. A., Expli it Constru tions of Graphs Without Short Cy les and Low Den-

[5℄

husetts, 1963.

Low{Density Parity{Che k Codes. M.I.T. Press, Cambridge, Massa-

Estimation of the Error{Corre tion Complexity of Gallager Low{Density Codes. // Probl. Pereda h. Inform. 1975. V. 11, N. 1, P. 23{36.

sity Codes. // Combinatori a, 2(1):71{78, 1982.

Margulis G. A., Some Expli it Constru tions of Low{Density odes. // Pro . III Inter-

national Seminar on Information Theory \Convolutional odes; ommuni ation with many users". So hy 1987. P. 120{123.

[6℄

Margulis G. A., Expli it Group{Theoreti Constru tions of Combinatorial S hemes and

[7℄

Tanner R. M.,

A Re ursive Approa h to Low Complexity Codes. // IEEE Trans. Inform. Theory. 1981. V. 27, N. 9, P. 533{547.

[8℄

Benedetto S., Montorsi G.,

Unveiling Turbo Codes: Some Results on Parallel Con atenated Coding S hemes. // IEEE Trans. on Inform. Theory, 1996, V. IT{42, 2, P. 409{428.

[9℄

Lentmaier M., Truha hev D. V., Zigangirov K. Sh.,

their Appli ation to the Design of Expanders and Con entrators. // Probl. Pereda h. Inform. 1988. V. 24. N. 1. P. 51{60.

On the Theory of Low{Density Convolutional Codes II. // submitted to Probl. Pereda h. Inform.

[10℄ Engdahl K., Zigangirov K. Sh., On the Theory of Low{Density Convolutional Codes I. // Probl. Pereda h. Inform. 1999. V. 35. N. 4. P. 12{27. 24

[11℄ Stahl P., Anderson J., Johannesson R., A Note on Tailbiting and Systemati Feedba k En oders. // submitted to IEEE Trans. on Inform. Theory. [12℄

Bahl L., Co ke J.,Jelinek F., Raviv J.,

Optimal De oding of Linear Codes for Minimizing Symbol Error Rate. // IEEE Trans. Inform. Theory, 1974, V.20, 1, p. 284{287.

[13℄

Zigangirov K. Sh., Lentmaier M., Mathemati al Analysis of an Iterative Algorithm for

Low{Density Code De oding. // Probl. Pereda h. Inform. 2000. V. 36. N. 4. P. 35{46.

[14℄ Johannesson R., Zigangirov K. Sh., Fundamentals of Convolutional Coding. Pis ataway, N.J., IEEE Press, 1999. [15℄

Breiling M., A Logarithmi Upper Bound on the Minimum Distan e of Turbo Codes.

// submitted to IEEE Trans. on Inform. Theory .

25

Figure Captions

Fig. 1:

Tree{like representation of turbo{ odes.

The asymptoti de oding bit error probability Pb of memory one turbo{ odes over the AWGN hannel as a fun tion of the number of iterations I . Signal{to{noise ratios per bit are Eb=N0 = 2:9; 3:0; 3:1; 3:2 (dB) (from top to bottom).

Fig. 2:

Simulated de oding bit error probability Pb of turbo{ odes with (7; 5) omponent odes over the AWGN hannel as a fun tion of signal{to{noise ratio per bit Eb =N0 . Curves for odes with onstru ted permutors are solid, urves for odes with random permutors are dashed. The lengths of the information sequen es are N = 500; 1000; 2000 (from top to bottom). (These results were obtained in ollaboration with Ola Wintzell.)

Fig. 3:

Fig. 4:

The three possible ases of degeneration of a lan.

26

g repla ements

un

2


Figure 1:

27

−1

10

−2

10

−3

Pb

10

g repla ements

−4

10

−5

10

−6

10

0

10

20

30

40

50

I

Figure 2:

28

60

70

80

90

100

−1

10

−2

10

−3

Pb

10

−4

10

−5

10

−6

10

g repla ements −7

10

0

0.2

0.4

0.6

0.8

1

Eb =N0

Figure 3:

29

1.2

1.4

1.6

1.8

2

ui

ui0

k

fk ui +1 fk+1 ui +2 k

...

f1

...

k

ui

l

1

fl 1 ui = ui l

(a)

0

f0

ui1

ui 1 fl 1 ui = ui0 l

fe ui01 f10 ui02

...

ui2

ui

n

ui0

1

k

fk0 1 ui0

l

k

f0

k

k

...

ui

ui0 +1 fn0 +1 ui0 +2 n

+1

fn+1 n

...

+2

ui 1 fl 1 ui = ui0

Figure 4:

30

1

fk0 1 ui0 k

k

( )

(b)

ui0

k

l

l

n