XII Reunión de Trabajo en Procesamiento de la Información y Control, 16 al 18 de octubre de 2007

Non-linear systematic Turbo Codes over GF(4)

D. M. Petruzzi, M. C. Liberatori, J. C. Bonadero and J. Castiñeira Moreira

Laboratorio de Comunicaciones, Facultad de Ingeniería, UNMdP, Mar del Plata, Argentina.

casti@[Link]

machines that constitute the turbo code are known to

Abstract— In this paper we use non-linear Finite have to be Infinite Impulse Response (IIR) FSSMs to
State Sequential Machines (FSSMs) designed over provide the turbo code with a good BER performance.
the Finite Field GF(4) as constituent encoders of In this paper we show that one of the most relevant
non-linear systematic turbo codes. These FSSMs characteristics of a FSSM as constituent encoder of a
have the property of showing a non-zero output for turbo code is the randomness of its output. This
the all-zero input case. The state transitions conclusion is obtained by studying 63 cases of FSSMs
structure and the randomness of the corresponding that are defined over GF ( 4 ) .
output of the responses to the all-zero input are These FSSMs are in general non-linear, and they are
studied for different initial state conditions. A constructed as proposed in (Petruzzi et. al., 2006). The
relationship is found between these two topology of these FSSMs includes a polynomial defined
characteristics and the BER performance or, also over GF ( 4 ) . Coefficients of this polynomial
equivalently, the form of the corresponding EXIT determine the main characteristics of these FSSMs and
chart. It is found that FSSMs with responses of the also their performances as constituent encoders of a
form of long closed cycles, and good randomness turbo code.
properties of the corresponding output, are the best FSSMs designed over the binary field with good
options as constituent encoders of non-linear random properties were presented in (Frey, 1993).
systematic turbo codes designed over GF(4). A These random properties were defined by Frey in his
coefficient called the random behaviour coefficient is paper. He determined that under certain conditions, a
defined, to provide a quantitative measure of the given FSSM can show what is called a Quasi-Chaotic
behaviour of these FSSMs as constituent encoders of (QC) behaviour. This QC behaviour is measured by
a systematic turbo code. determining how close to the ideal white noise
behaviour, is the behaviour of the output of the FSSM.
Keywords— Coding, Communications. A coefficient called the delta function coefficient ηδ is
defined in (Petruzzi et. al., 2006) to provide a
I. INTRODUCTION quantitative measure of this behaviour.
Finite State Sequential Machines (FSSMs) are usually The polynomial g ( x ) that is part of the encoder and
utilized as constituent encoders of turbo codes, as it has the decoder of the proposed scheme is in general of the
been proposed in the original paper of Berrou, Glavieux, form:
and Tithisjmashima (Berrou et. al., 1993). The original g (x ) = a0 + a1 x + ... + a m x m (1)
turbo coding scheme utilised FSSMs operating over the
binary field, also known as the Galois Field GF ( 2 ) . where m is an integer, and a i ∈ GF ( q ) , i = 0 ,1,..., m .
In this paper we analyse the performance of FSSMs
designed over the Galois Field GF ( 4 ) , as constituent Fig. 1 shows the proposed FSSM operating as an
encoders of a turbo code. We put our attention on the encoder, and the corresponding decoder.
main properties and characteristics of these FSSMs and This FSSM differs from the one proposed by Frey in
their relationship with the Bit Error Rate (BER) two aspects: On one side it operates over the field
performance of the corresponding turbo code. GF ( q ) (In this paper GF ( 4 ) ), and on the other side it
Turbo codes over GF ( 4 ) have BER performances replaces the shift-circulant operator (Frey, 1993) by the
that are equal to those of the equivalent versions over polynomial g ( x ) . In a previous work of the authors it
the binary field GF ( 2 ) . There are however much more is found that the proposed FSSMs show the best QC
study cases of FSSMs over GF ( 4 ) than over GF ( 2 ) , behaviour for certain set of coefficients of the
thus allowing us to analyse a rich number of polynomial g ( x ) . In this paper we show that FSSMs
possibilities to obtain a relationship between the state with the best QC behaviour are also the best options as
transitions structure of these FSSMs and their behaviour constituent encoders of a turbo code. Thus, the
as constituent encoders of a turbo code. randomness of the output of the FSSM is related to the
As it is well known the data interleaver of a turbo BER performance of the corresponding turbo code.
code has to be a random interleaver to provide the
scheme with the best BER performance. FSSMs
 XII Reunión de Trabajo en Procesamiento de la Información y Control, 16 al 18 de octubre de 2007
Since we operate over GF ( 4 ) , and due to the We will consider all the possible systematic turbo
inclusion of the polynomial g ( x ) , the number of codes defined over GF ( 4 ) , with s = 2 memory units,
possible FSSMs highly increases with respect to FSSMs and with encryption polynomials of the form
defined over GF ( 2 ) . This increased number of study g ( x ) = a 0 + a 1 x + a 2 x 2 , that is, with m = 2 . The
cases allows us to do a suitable analysis of the systematic turbo code is always constructed using the
relationship between the behaviour of the proposed same FSSM in both constituent encoders. Thus, a given
FSSMs, and the BER performance of the turbo code systematic turbo code scheme defined over GF ( 4 ) , and
constructed using that FSSM. This is the aim of this
with m = 2 , will be denoted as a (a0 a1 a 2 )
paper.
The proposed FSSMs operate as constituent encoders systematic turbo code, a notation that describes the
of a turbo code. A ½-rate systematic non-linear turbo coefficients of the encryption polynomial g ( x ) . Thus,
code defined over GF ( 4 ) is seen in Fig. 2. The rate of for each systematic turbo code,
the code is obtained by a proper use of puncturing g 1 ( x ) = g 2 ( x ) = g( x ) = a 0 + a1 x + a 2 x 2 (2)
(Output selector block) of the outputs of the FSSMs.
FSSMs with good QC behaviour contribute as
constituent encoders of a turbo code to accelerate the II. STRUCTURE OF THE STATE
slope of the waterfall region of the BER performance TRANSITIONS OF FSSMS OVER GF ( 4 )
curve of the code. We provide in this paper an analysis
of this behaviour, by using the classic BER performance
FSSMs with the best QC properties are those for
analysis, and the Extrinsic Information Transfer (EXIT)
chart analysis (Ten Brink, S., 2001; Ashikhmin et. al., which g( x ) = a0 + a1 x , and for particular values of
2002; Castiñeira Moreira and Farrell, 2006). coefficients (a0 a1 ) . The optimum FSSMs show
responses of the form of what is called a limit cycle,
η(n)
which runs all the states of the machine, excepting the
u(n) e(n) r(n) y(n) equilibrium point state. In the particular case of FSSMs
operating over GF ( 4 ) , and with s = 2 memory units,
d(n) D D δ(n) the maximum length of this limit cycle is Lmax = 15
(Petruzzi et. al., 2006).
ed(n) rd(n)
For each FSSM we have analysed the response for the
16 possible initial state conditions. The response of the
g(x) g(x)
edgfd(n) rdgfd(n) FSSM under analysis can be classified into different
edgf(n) rdgf(n) groups. FSSMs can run a cycle, that is, a sequence of
D
states that start and end at the same state. This cycle can
D
be run from any of the sates of the machine, or either be
ENCODER DECODER reached after a given transient response. Since this
Fig. 1. FSSM operating as an encoder, and the difference in the behaviour of the FSSM is relevant to
corresponding decoder, defined over a Galois Field its performance as a constituent encoder of a systematic
GF ( 4 ) . turbo code, we want to differentiate these two types of
u1(n) Polar and 1 c (n) cycles. A cycle that includes always a given set of states
and is run starting from any of these states, will be
u1(n) e1(n) binary
format for
referred to as a closed cycle. The number of states that
Output u1(l) and the cycle runs is the length of the cycle, and it will be
d1(n) D Selector e(l) denoted as LC . Another definition of a closed cycle is
e2(n)
ed1(n) e(n) c2 (n) that it is a cycle that starts and ends at the initial state.
When the cycle is reached after a sequence of states
g1(x) d2(n) D that do not form the cycle, showing a transient response
edgf1(n) ed2(n) before entering into the cycle, the response will be
referred to as a cycle with transients, and the number of
D g2(x)
edgfd1(n) states of the cycle, (excluding the number of states of
edgf2(n) the transient), is the length of the cycle, and it will be
Interleaver denoted as LT . FSSMs will be classified by the form
D
edgfd2(n) of their state transitions structures, evaluated over all the
initial state conditions. There is a relationship between
Fig. 2. A systematic non-linear systematic turbo code the state transitions structure of the FSSM, and the BER
over GF ( 4 ) . performance, or equivalently, the form of the
corresponding EXIT chart.
 XII Reunión de Trabajo en Procesamiento de la Información y Control, 16 al 18 de octubre de 2007
III. THE RAMDOM BEHAVIOUR turbo codes that use these FSSMs as constituent
COEFFICIENT encoders are those with the best BER performance.
They are also FSSMs with the maximum values of the
The random behaviour of the output of the response to
random behaviour coefficient ∆R . In each group we can
the all-zero input of the FSSM, and the form of the state
transitions structure are both interesting characteristics also identify three different sub groups classified
of these FSSMs, related to their performance as basically by the form of the state transitions structure,
constituent encoders of a systematic turbo code. A for different initial state conditions.
distinctive characteristic of a given state transitions Table I describes some of the FSSMs found for the
structure is the presence of closed cycles. The longer are different groups, detailing the number of closed cycles,
these closed cycles, the better is the BER performance cycles with transients, responses without cycles and
of the corresponding turbo code. stationary responses for each FSSM, and the value of
FSSMs with many responses of the form of cycles the corresponding random behaviour coefficient ∆R ,
with transients, or responses without cycles, perform evaluated using (3):
worse than those with long closed cycles. We define in Sub group A.1: FSSMs with 15 closed cycles of
this paper a coefficient that take into account not only length: LC = Lmax = 15 .
the value of the delta function coefficient ηδ for each Sub group A.2: FSSMs with 12 closed cycles of
response, but also the number and length of closed length 6, 3 closed cycles of length 3, and 1 stationary
cycles of the corresponding FSSM. response. All these FSSMs have 15 closed cycles, and
The random behaviour coefficient for the FSSM is one stationary response. Closed cycles are shorter than
defined as: in the case of sub group A.1, of lengths 6 and 3, and the
qs random behaviour coefficient ∆R is slightly smaller
1
∆R =
q s Lc _ max
∑L
i =1
C ( i )ηδ ( i ) (3) than for FSSMs of sub group A.1.
Sub group A.3: FSSMs with 15 closed cycles of
length 3, and one stationary response.
where LC ( i ) is the length of the closed cycle present at Systematic Turbo codes constructed using FSSMs of
the response for the initial condition i , ηδ ( i ) is the group A have good or very good BER performances.
delta function coefficient measured for the all-zero input Group B:
case, and for the initial condition i , and Lc _ max is the FSSMs of group B have as a characteristic in common
that not all the non-stationary responses are closed
maximum length of a closed cycle verified for the cycles. Some responses are of the form of cycles with
corresponding FSSM, and evaluated over all the transients, and responses without cycles and/or
responses. If the response has cycles with transients, or stationary responses are also present. The random
responses without cycles for the initial condition i , behaviour coefficient for FSSMs of this group is always
then LC ( i ) = 1 . This coefficient measures the random less than ∆R < 0.3 .
behaviour of the FSSM with more accuracy than by
using simply mean or peak values of the delta function V. BER PERFORMANCE
coefficient ηδ evaluated over all the responses. FSSMs described in section IV are utilized as
constituent encoders of systematic ½ rate convolutional
IV. CLASSIFICATION OF FSSMS IN TERMS turbo codes. These schemes are described in Fig. 2, and
OF THEIR STATE TRANSITIONS make use of puncturing, and a random interleaver of
STRUCTURES length LINT = 10000 . The interleaver used in each case
There are essentially two groups of FSSMs, which is the same for all these schemes. They are iteratively
will be called groups A and B. These two groups differ decoded using the LOG-MAP BCJR algorithm (Bahl et.
not only in the length of the cycle but also in the type of al., 1974), with 8 iterations. Some slight modifications
cycle of the response for each initial condition. In each were implemented in his algorithm to take into account
group, there are also sub groups, which are classified by operations over GF ( 4 ) . All other parameters of the
their differences in the state transitions structure: systematic turbo code remain the same for all these
Group A: schemes. This analysis is developed for the waterfall
FSSMs of this group are those that provide the region of the BER performance.
corresponding systematic turbo code with the best BER BER performances of several schemes are shown in
performance, among all the 63 cases under study. The Fig. 3. It can be seen that schemes of group A.1 perform
main characteristic of FSSMs of this group is that 15 very well and close to an equivalent scheme operating
responses for different initial conditions are always over the binary field, GF ( 2 ) , considered as a reference
closed cycles, in some cases of the maximum length, in
for comparison proposes. Systematic turbo codes
some other cases of considerable long length, and there
constructed using FSSMs of sub group A.1, and some of
is always only one stationary response, that is, for a
sub group A.2, can be considered as the best among all
certain initial condition, the FSSM stays at a given state,
that are under study.
generating also a constant value output. Systematic
 XII Reunión de Trabajo en Procesamiento de la Información y Control, 16 al 18 de octubre de 2007

Table I. Classification of FSSMs in terms of their state transitions structures

Scheme ∆R LC=15 LC=6 LT=6 LC=4 LT=4 LC=3 LT=3 LC=2 No Stationary
cycles responses
Group A
Sub group A.1
(1 α2 0 ) 0.7289 15 1

(α 2
α 0) 0.7386 15 1

(α 2
α2 0 ) 0.7260 15 1
Sub group A.2
(α 0 α ) 0.5058 12 3 1

(α 0 α2 ) 0.3861 12 3 1

(α 2
0 1) 0.4527 12 3 1
Sub group A.3
(0 1 0 ) 0.3789 15 1
(1 1 0) 0.4245 15 1

(α 2
1 0 ) 0.4074 15 1
Group B
Sub group B.1
(1 α 1) 0.2494 6 6 2 2

(1 α 2
1 ) 0.1404 6 6 2 2

(1 α2 α2 ) 0.2482 6 6 2 2
Sub group B.2
(1 1 α) 0.1762 4 12

(1 1 α 2
) 0.1335 4 12

(α 2
1 1) 0.2148 4 12
Sub group B.3
(0 α α2 ) 0.2161 6 6 2 2

(α α α) 0.2977 6 6 2 2

(α 2
α2 α2 ) 0.2600 6 6 2 2
Sub group B.4
(0 1 1) 0.2361 2 12 2
(0 1 α) 0.2688 2 12 2

(0 1 α2 ) 0.3325 2 12 2

quantitatively indicated by the value of the defined

VI. EXIT CHART ANALYSIS
random behaviour coefficient ∆R . The EXIT chart
The EXIT chart (Ten Brink, 2001) is an especially analysis of a systematic turbo code designed over
good tool for the analysis of the waterfall region, and
also illustrates the behaviour of the code in the other
GF ( 4 ) using FSSMs with coefficients α 2 α 0 ( )
two regions of the BER performance curve of a and (α 0 α ) are shown in Fig. 4.
systematic turbo code. This Extrinsic Information The “bottleneck” region of the EXIT chart is given at
Transfer function is defined as: around Eb / N 0 ≈ 0.7 dB for the α 2 α 0 ( )
systematic turbo code with a FSSM of sub group A.1,
I E = Tr ( I A , E b / N 0 ) (4)
whereas this is given at around E b / N 0 ≈ 0.9 dB for
Some relationship is found between the EXIT chart the (α 0 α ) systematic turbo code with a FSSM of
appearance and the structure of the state transitions and sub group A.2. The BER performance of the
randomness of the output for the all-zero input case, ( )
α 2 α 0 systematic turbo code is better than that of
 XII Reunión de Trabajo en Procesamiento de la Información y Control, 16 al 18 de octubre de 2007

the (α 0 α) turbo code, in the region of

Eb / N0 ≈ 0.7 dB to Eb / N0 ≈ 1.2dB , and this is in 1
agreement with the above EXIT chart analysis. 0.9
However, the BER performance of the (α 0 α ) 0.8 A1
systematic code is better than that of the α 2 α 0 ( ) 0.7
systematic turbo code, in the region of around 0.6
Eb / N0 ≈ 1.2dB to Eb / N0 ≈ 1.5 dB . IE
0 0.5
10
0.4
-1
10 0.3 Exit Chart from
0.2 0.7 dB
-2 to 1.9 dB
10 0.1

0 0.2 0.4 0.6 0.8 1

Pb 10-3 IA
(a)
-4
10 1
0.9
-5
10 0.8 A2
-6 0.7
10
-1 -0.5 0 0.5 1 1.5 2 2.5 0.6
IE
Eb/No [dB] 0.5
(α α α) Turbo code 0.4
* * (1 α 1) Turbo code 0.3 Exit Chart from
+ + (0 1 α) Turbo code 0.2 0.7 dB
(0 1 0) Turbo code to 1.9 dB
(α 0 1) Turbo code 0.1

x x (α α 0) Turbo code 0 0.2 0.4 0.6 0.8 1

IA
(α 2
α 0 2
)
Turbo code (b)
Classic best known binary turbo code Fig. 4. EXIT charts for the systematic turbo codes
(1 0 α ) Turbo code (
using a FSSM with coefficients: (a) α 2 α 0 ; (b) )
(α 0 α ) Turbo code
(α 0 α ) .
Fig. 3. BER performances of some systematic turbo 1
code schemes constructed using FSSMs defined over
GF ( 4 ) . 0.9
0.8 A2
Fig. 5 shows the EXIT chart of the α 0 1 (
0.7
2
)
systematic turbo code, sub group A.2. This EXIT chart 0.6
is quite similar to that of the (α 0 α ) systematic IE
0.5
turbo code of the same sub group A.2. However,
separation between curves is very small for the EXIT 0.4
chart of the α 2
( )
0 1 systematic turbo code. This 0.3 Exit Chart from:
means that the number of iterations required for a good 0.2 0.9 dB
BER performance is quite large. step 0.2 dB, to:
0.1 1.9 dB
The presence of anticipated intersecting points is an
indication of a poorer BER performance with respect to 0 0.2 0.4 0.6 0.8 1
schemes for which these anticipated points are not IA
present in the EXIT chart, and it indicates that iterative
decoding is not efficient at those values of E b / N 0 . Fig. 5. EXIT chart of the α 2 0 1 systematic ( )
turbo code.
 XII Reunión de Trabajo en Procesamiento de la Información y Control, 16 al 18 de octubre de 2007

Fig. 6 shows the EXIT chart of the (α α α ) randomness of the output for the all-zero input. These
systematic turbo code. By comparing EXIT charts of two main groups are called groups A and B.
Figs. 5 and 6, we can say that the behaviour of the EXIT EXIT chart analysis for systematic turbo codes
( )
chart of the α 2 0 1 systematic turbo code shows a
constructed using FSSMs of group A shows a strong
relationship between the form of this EXIT chart
form which have only one anticipated intersecting point, (classified by the number of anticipated intersecting
and a suitable “bottleneck” shape region, whereas the points that this chart presents), and the state transitions
(α α α ) systematic turbo code, displays many structure of the FSSM used to construct the
anticipated intersecting points, and a rather missing corresponding systematic turbo code. On the contrary,
“bottleneck” shape region. FSSMs of group B have responses that mix closed
cycles with cycles with transients, and also responses
1 without cycles. There are also stationary responses in
some cases. The main difference with respect to group
0.9 A is that not all the non-stationary responses of these
0.8 B3 FSSMs are closed cycles.
0.7 This means that it is important for these FSSMs to
have all their non-stationary responses for the all-zero
0.6 input of the form of closed cycles, and also that the
IE
0.5 length of these closed cycles has to be long enough.
Finally, the strong correspondence between the state
0.4
transitions structure and the value of the random
0.3 Exit Chart from: behaviour coefficient of the FSSM, and the form of the
0.7 dB EXIT chart of the corresponding systematic turbo code,
0.2
step 0.2 dB, to: verified in group A, is not completely given in group B.
0.1 1.9 dB
VIII. REFERENCES
0 0.2 0.4 0.6 0.8 1
IA Ashikhmin, A., Kramer, G. and Ten Brink, S.,
Fig. 6. EXIT chart for the (α α α ) systematic turbo “Extrinsic information transfer functions: A model
code (FSSM of sub group B.3). and two properties,“ Proc. conf. Information
Sciences and systems, Princeton, NJ, Mar 20-22,
The presence of anticipated intersecting points 2002, pp. 742-747.
indicates that iterative decoding does not make sense at
those values of E b / N 0 , confirming that the Bahl, L., Cocke, J., Jelinek, F. and J. Raviv, “Optimal
decoding of linear codes for minimising symbol
corresponding BER performances are the poorest error rate,” IEEE Transactions on Information
among all the evaluated cases in Fig. 3. The best Theory, vol. IT–20, pp. 284–287, Mar. 1974.
systematic turbo codes are constructed using FSSMs
whose state transitions structures are characterised by Berrou, C., Glavieux, A. and Thitimajshima, P., “Near
responses to the all-zero input case that are all closed Shannon limit error-correcting coding and
cycles, like those FSSMs that belong to the group A. decoding: turbo codes,” Proc.1993 IEEE
We can also say that the best systematic turbo codes are International Conference on Communications,
those for which the random behaviour coefficient is Geneva, Switzerland, pp.1064-1070, May 1993.
larger than ∆R > 0.4 . Castiñeira Moreira, J. and Patrick G. Farrell, Essentials
VII. CONCLUSIONS of Error-Control Coding, John Wiley and Sons,
July 2006.
Systematic turbo codes can be designed using FSSMs
Frey, D. R., “Chaotic digital encoding: an approach to
that operate over the Galois Field GF ( 4 ) . The selected
secure communication” IEEE Trans. Circuits and
topology present 63 different systematic turbo coding Systems-II, analog and Digital Signal Processing,
schemes that were studied in terms of their BER vol. 40, pp. 660-666, October 1993.
performance, and equivalently of their EXIT chart
representation. FSSMs are classified by their state Petruzzi, D. M., J. Castiñeira Moreira y Damian G.
transitions structures. These are the structures of the Levin, "Quasi-Chaotic coding over GF(q)", IEEE
sequences of states that the corresponding FSSM runs as Transactions on Communications, Vol. 54, No 3,
a response to the all-zero input, for different initial state pp. 462-468, March 2006.
conditions. On the other hand these FSSMs are also Ten Brink, S., “Convergence behaviour of iteratively
characterised by the level of randomness that the decoded parallel concatenated codes,” IEEE Trans.
corresponding output shows, for the all-zero input. On Comm., vol. 49, pp. 1727-1737, October 2001.
FSSMs can be classified into two main groups,
depending on the state transitions structure, and on the