Buletin Teknik Elektro dan Informatika
(Bulletin of Electrical Engineering and Informatics)
Vol. 2, No. 4, December 2013, pp. 293~298
ISSN: 2089-3191 293
Received July 9, 2013; Revised October 15, 2013; Accepted November 3, 2013
A New Block S-Random Interleaver for Shorter
Length Frames for Turbo Codes
Mohammad Salim*
1
, R.P. Yadav
2
, Kapil Narwal
3
, Aarti Sharma
4
Dept. of Electronics and Communication, MNIT, Jaipur (Rajasthan), India
*Corresponding author, e-mail: salimerjpr@yahoo.com
1
, rp_yadav@yahoo.com
2
,
krish1brilliant@gmail.com
3
, aarti2007@gmail.com
4
Abstract
In this paper, we have proposed a new design of interleaver based on S-random and block
interleaver. The characteristics of both block and S-random interleaver are used by this proposed
interleaver. There is a large influence of free distance in turbo codes due to interleaving as it lowers the
error floor. The free distance of turbo codes can be increased by designing interleaver with high spread. In
this case, the overall spreading factor is increased significantly for smaller length frames also. The
simulations results are compared with full S-random interleavers. The bit error rate performance of
proposed interleaver for Turbo codes is much better than full s-random interleaver at the cost of small
delay.
Keywords: turbo code, S-Random interleaver, spread property, parallel concatenated convolutional code
1. Introduction
Turbo codes [1] represent powerful error correcting codes so far. At low SNR, bit error
rate is affected by medium weight code words and at high SNR, error performance is influenced
by low weight code words. Due to low weight code words, a condition of low error floor is
introduced. These codes well performed at low SNR due to their sparse distance spectrum.
In order to lower the error floor, increase in free distance [2] is required. It can be done
either increasing interleaver size or interleaver design. Increasing interleaver size leads to
longer delays and more memory requirements. So interleaver is to be designed such that error
floor is reduced.
It is clearly discussed in literature that the interleaver size and structure affect the turbo
code error performance considerably. At low SNRs the interleaver size is the only important
factor, as the code performance is dominated by the interleaver gain. The effects induced by
changing the interleaver structure at low SNR region are not significant. However, both the
interleaver size and structure affect the turbo code minimum free distance and first several
distance spectral lines. At high SNRs turbo code performance is dominated by the several
distance spectral lines which are produced by low weight sequences. The interleaver structure
affects the mapping of low weight input sequences to the interleaver output.
Unlike convolutional codes [3], turbo codes have an error floor at high SNRs i.e., the bit
error rate drops very quickly at the beginning, but eventually levels off and becomes flat at high
SNRs. This is due to the asymptotic performance characterized by the minimum free distances
associated with the turbo codes are typically very small. The free distance of turbo code can be
increased by designing interleavers with high spreads.
S-Random interleaver [4] has a good distance spectrum property and produced
better results than previous interleavers. Some modifications are introduced in [5, 6] of S-
random interleaver for improvement in performance. But at the same time there are two major
drawbacks one is to find a good interleaver (with large spreading factor) for longer length
frames, that require more computation and second is the processing delay.
In this paper, we propose a new design of interleaver referred to as block S-random
interleaver. We evaluate the performance of Turbo codes with the proposed Block S-Random
Interleavers (BSRI) and compare it to those with full S-random interleavers.
ISSN: 2089-3191
Buletin TEI Vol. 2, No. 4, December 2013 : 293 298
294
This paper is organized as follows: In section II, several existing interleavers are briefly
explained. The definition of interleaver spread is defined in section III. Section IV describes the
algorithm for the proposed interleaver. Simulation results are compared for different designed
interleavers in section V.
2. Interleavers in Turbo Codes
The general structure used in turbo encoders is shown in Figure 1. Two component
codes are used to code the same input bits, but an interleaver is placed between the encoders.
Generally RSC codes are used as the component codes, but it is possible to achieve good
performance using a structure like that seen in Figure 1 with the aid of other component codes
called Parallel concatenated convolutional code [7]. The constituent encoders in a PCCC are
always recursive convolution encoders.
Figure 1. Parallel Concatenated Convolutional Code
Here m is input data stream and y
1
is first parity sequence after passing through
Recursive convolutional encoder 1. After interleaving input data passes through Recursive
convolutional encoder 2 and get second parity sequence y
2
. Among several conventional
interleavers we reviewed the two common interleavers as pseudo random and S- random
interleaver.
1) Pseudo-Random Interleaver
Let k denote an integer chosen from [0, N -1] and (k) denotes its position after
interleaving. For each k, a pseudo random interleaver randomly but uniquely chooses (k)
from [0, N-1].
2) S-Random Interleaver
S-random interleavers or spread interleavers are constructed by generating random
numbers from 1 to L based on an S- constraint where S is the minimum interleaving
distance.
The operation of the S-random interleaver is as follows. A randomly selected integer is
compared to the previously S1 selected integers. If the absolute differences between the
selected integer and any of the S1 previously selected Integers are greater or equal to
S2 then the randomly selected integer accepted otherwise it is rejected. An S- Random
interleaver is determined based on:
| Ii Ij | S1 (2)
| M (Ii) M (Ij) | S2 (3)
Where Ii denotes the original index and M(Ii) is the permuted index in the interleaved sequence.
When identical constituent codes are used, it is appropriate to choose S1=S2=S, where S
(N/2) [10].
The major issue associated with the conventional S-random interleaver is its lack of
flexibility since changing the number N requires another search of interleaver and the
generated interleavers with different length should be stored in memory separately.
Buletin TEI ISSN: 2089-3191
A New Block S-Random Interleaver for Shorter Length Frames for Turbo (Mohammad Salim)
295
3. Interleaver Spread
Figure 2 shows a definition of interleaver spread. Here, the indexes 1,2,.N form the
input vector of length N to be interleaved, and M is the vector after interleaving. The spread of
the interleaver is defined as:
S =
mn
,],=]
||H(i) - H(])| + |i - ]|] (1)
Pseudorandom interleavers permute the elements in a predefined random order. This
interleaver requires N indexes to be stored to implement an interleaver of length of N. There is
no restriction and thus may have poor distance properties, causing an error floor problem. To
improve the free distance of turbo code, spread-random or Semi-random (S-random)
interleavers can be used. In S-random interleaver, the permutation order is selected such that
any integer in the order is at least S number of positions away from the previous S integers in
the interleaver.
Input indexes
1 2 3 4 i j N
M(4) M(2) M(1) M(j) M(i) M(N)
Interleaved output
Figure 2. Spread of Interleaver
4. New Proposed Interleaver
In this section, we provide an algorithm for proposed interleaver referred to as Block S-
Random Interleaver (BSRI). The characteristics of both block and S-random interleaver are
used by this proposed interleaver. The detail algorithm and flowchart are stated as follows:
Step 1: Information sequence having length N is written row wise into a matrix [m, n] as
shown in Figure 4. Here m and n are rows and columns of block matrix.
Figure 3. Flowchart for Proposed Interleaver
ISSN: 2089-3191
Buletin TEI Vol. 2, No. 4, December 2013 : 293 298
296
Example: The length of information sequence is N = 16.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Figure 4: Information bits written row-wise
Step 2: First each rows of matrix are interleaved by fixed S-random interleavers
algorithm as shown in Figure 5. In this example spreading factor(S) N/2 and (N= 4), S
1.414, S = 1. S
C
= {2, 1, 4, 3}.
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
5 6 7 8
1 2 4 3
13 14 15 16
9 10 11 12
Figure 5. Interleave Each Row Using S-Random Method
Step 3: Then, each column of matrix is read one by one and interleaved sequence is
encoded by convolutional encoder. In this example, the interleaved sequence is as shown in
Figure 6.
5 1 13 9 6 2 14 10 7 4 15 11 8 3 16 12
Figure 6. Read Each Column
The spread of full S-random interleaver for frame having size N is:
S
SR
(N/2) (4)
In proposed interleaver, overall spread is dependent on size of row and spread between
each row.
The information sequence having frame size N is stored in block matrix of m rows and n
columns (N= N
R
N
C
). The overall spread of proposed interleaver is:
S
BSRI
= N
C
. S
R
(5)
S
BSRI
= N
C
. (N
R
/2)
(6)
Here S
BSRI
is overall spread and S
R
is spread between each rows calculated with
conventional S-random interleaver. The spread of new interleaver BSRI is N
C
times the spread
of original full S-random interleaver.
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Buletin TEI ISSN: 2089-3191
A New Block S-Random Interleaver for Shorter Length Frames for Turbo (Mohammad Salim)
297
Table 1. Spread for S-random and Proposed Interleaver (m=n)
Frame
size(N)
Full s-random int. BSRI (N= N
R
N
C
)
S
SR
(N/2) S
BSRI
= N
C
. S
R
16 2 4
64 5 16
256 11 32
1024 22 128
5. Simulation Results
We designed Turbo encoder using recursive systematic convolutional (RSC) encoders
having generator polynomial of G [1 15/13], constraint length is 4 and number of iterations is 5.
The overall code rate is after puncturing [8]. The frame size is taken 256.
Figure 7. Comparison of BER Performances in
Full S-random Interleaver and Proposed
Interleaver for AWGN Channel
Figure 8. Comparison of BER Performances in
Full S-random Interleaver and Proposed
Interleaver for Rican Channel
Figure 9. Comparison of BER Performances in Full S-random Interleaver and Proposed
Interleaver for Rayleigh Channel
ISSN: 2089-3191
Buletin TEI Vol. 2, No. 4, December 2013 : 293 298
298
There is comparison of Bit error rate performance in full s-random interleaver and
proposed interleaver for AWGN channel and fading channels. The performance of the proposed
interleaver is more than full s-random interleaver as shown in Figure 7, Figure 8 and Figure 9.
6. Conclusion
In this paper, we proposed a new interleaver that is based on both block and S-random
interleaver. In proposed interleaver, as the overall spread factor is N
C
times the spread factor
(S
SR
) in full S-random interleaver. This is another way to improve the free distance of turbo code
and hence it will improve Bit Error Rate performance of Turbo codes. The simulation results
show that for smaller frames (256) also, the BER performance of proposed interleaver is better
than full S-random interleaver. The error floor starts at BER 2.10
-4
as compared to 5.10
-4
for full
S-random i.e. BER is improved 2.5 times. On the other hand for a BER of 10
-4
, a coding gain of
0.875 dB is achieved by new interleaver as compared to the S-random interleaver for non-
fading AWGN channel. The similar improvements are evident for fading channel cases also.
References
[1] C. Berrou, A. Glavieux and P. Thitimasjshima. Near Shannon Limit Error-Correcting Coding and
Decoding: Turbo-Codes. Proceedings of the IEEE International Conference on Communications.
1993: 10641070.
[2] Garello R., et al. On the Error Floor and Free Distance of Turbo Codes, IEEE International Conference
on Communications Helsinki. Finland. 2001: 45-49.
[3] A. Viterbi. Error bounds for convolutional codes and an asymptotically optimum decoding algorithm.
IEEE Transactions on Information Theory. 1967; IT(13): 260269.
[4] C. Fragouli and R. D. Wesel. Semi random interleaver design criteria. Global telecommunication
Conference 99. Rio de Janeiro, Brazil. 1999.
[5] J. Yuan, B. Vucetic and W. Feng. Combined Turbo Codes and Interleaver Design. IEEE Trans.
Commun. 1999; 47(4): 484-487.
[6] M. Ferrari, F. Scalise and S. Bellini. Prunable S-random interleavers. Proc. IEEE (ICC'02). 2002; 3:
1711-1715.
[7] Jinhong Yuan, Wen Feng and Branka. Performance of Parallel and Serial Concatenated Codes on
Fading Channels. IEEE Transactions on communications. 2002; 50(10).
[8] Analysis of Various Puncturing Patterns and Code Rates: Turbo Code. International Journal of
Electronic Engineering Research. 2009; 1(2): 7988. ISSN 0975- 6450.
[9] H. R. Sadjadpour, N. J. A. Sloane, M. Salehi, and G. Nebe. Interleaver Design for Turbo Codes. 2000.
[10] D.Divasalar and F.Pollara. Turbo codes for PCS applications. Proc. Of ICC 95. Seatle, WA. 1995: 54-
59.
