# Parameter Estimation of Turbo Code Encoder

Authors: Mehdi Teimouri; Ahmadreza Hedayat
Journal: Advances in Electrical Engineering
 (2014)

---

## Abstract

The problem of reconstruction of a channel code consists of finding out its design parameters solely based on its output. This paper investigates the problem of reconstruction of parallel turbo codes. Reconstruction of a turbo code has been addressed in the literature assuming that some of the parameters of the turbo encoder, such as the number of input and output bits of the constituent encoders and puncturing pattern, are known. However in practical noncooperative situations, these parameters are unknown and should be estimated before applying reconstruction process. Considering such practical situations, this paper proposes a novel method to estimate the above-mentioned code parameters. The proposed algorithm increases the efficiency of the reconstruction process significantly by judiciously reducing the size of search space based on an analysis of the observed channel code output. Moreover, simulation results show that the proposed algorithm is highly robust against channel errors when it is fed with noisy observations.


---

## Body

## 1. Introduction

Channel code reconstruction problem is usually considered in noncooperative communication scenarios, where finding the structure and parameters of the channel code is a major goal of the receiver [1–14]. Since turbo codes are introduced in many standards and applications [15–22], blind reconstruction of turbo codes in practical noncooperative situations is a well motivated problem. This problem has been investigated in [1–4, 8, 11], where some of the code parameters are assumed to be known to the receiver, such as the number of input and output bits of each constituent convolutional code and the structure of puncturing matrix. Having the above parameters, the receiver becomes capable of separating the received coded stream into three sets [3]: systematic bits, parity bits of the first convolutional encoder, and parity bits of the second convolutional encoder. Now the turbo code reconstruction problem converts into three simpler reconstruction problems: two convolutional code reconstruction problems and one interleaver reconstruction problem.However, in most practical noncooperative situations, the parameters of turbo code are unknown and thus should be estimated before applying reconstruction process or to test each possible set of parameters which is highly time consuming. To the best of the authors’ knowledge, no algorithm has yet been proposed for estimating these parameters, and this paper is the first to propose a novel method to estimate above-mentioned parameters before applying the turbo code reconstruction process. The proposed method reduces the search space of the reconstruction process significantly compared to [3] and makes the reconstruction process faster and more efficient. The proposed method is first formulated for noiseless streams and then it is adjusted for noisy observations.The rest of the paper is organised as follows. In Section2, system model is described. The method for estimating the turbo code parameters is proposed in Section 3 and experimental results are presented in Section 4. Finally, the paper is concluded in Section 5.


## 2. System Model

We consider the system model of turbo code reconstruction as shown in Figure1. In this model, input bits and their interleaved version are fed to the first and second convolutional encoders, respectively. The first encoder is an (n1,k1,m1) convolutional code, where n1 is the number of output bits, k1 is the number of input bits, and m1 is the memory length of the longest shift register of the encoder. Since convolutional codes used for parallel turbo codes are systematic [15], k1 bits out of n1 output bits are systematic bits, and the remaining n1-k1 bits are parity bits. With such configuration, the value of any n1-k1 parity bits is a function of recent k1 systematic output bits and at most k1×m1 values of shift registers content. In the system model of Figure 1, the second convolutional code is also assumed to be an (n2, k2, m2) convolutional code, but unlike the first convolutional encoder, its systematic bits are removed and only the remaining n2-k2 parity bits are used.Figure 1
System model of turbo code reconstruction.Since parallel turbo codes have the same number of input bits per constituent convolutional code [15], we assume k1 and k2 are equal and denote both by k. Assume the length of input frames is N; then N is a multiple of k. Using this assumption, at each time step, k bits out of N input bits and k bits out of the interleaver are fed to the first and second convolutional encoders, respectively. These input bits result in n1+n2-k output bits; thus we can say that N/k sets of input bits form an output frame with length L=N/k×(n1+n2-k).As shown in Figure1, a puncturing pattern can also be applied to the output frames to form smaller frame lengths and higher code rates. We use an (n1+n2-k)×p matrix P=[qi,j] to represent puncturing pattern where p is the puncturing period. Every row ofP corresponds to one output bit; that is, the first row corresponds to the first systematic bit, the second row corresponds to the second systematic bit (or the first parity bit of the first convolutional encoder), and so on. Note that qi,j∈0,1, where 0 implies that the corresponding bit is punctured. If n0 elements out of (n1+n2-k)×p ofP take the value of 1, then the output frame length is L=(N×n0)/(k×p). Note that we have implicitly assumed that N is a multiple of k×p, since the input frame needs to be a multiple of the puncturing period. Since the turbo codes employed in many applications such as CDMA 2000 [16] and WCDMA [17] are systematic parallel turbo codes, in this paper we consider systematic parallel turbo codes. The term “systematic” is used for a turbo code when none of its systematic bits are punctured. In systematic turbo codes all the elements of the first k rows ofP take the value of 1. Other elements ofP can be either 0 or 1; however, it should be noted that none of the rows can be an all zeros vector.All the previous works that address the turbo code reconstruction problem implicitly assume that the received coded stream is partitioned into three sets: systematic bits, parity bits of the first convolutional encoder, and parity bits of the second convolutional encoder. However, it should be noted that in order to do such partitioning we need to know the number of output bits of both encoders (i.e.,n1 and n2) and the puncturing pattern (i.e.,P). But, in most practical noncooperative situations, these parameters are unknown and thus should be estimated before applying reconstruction process or to test each possible set of parameters which is highly time consuming. In this paper, a novel method is proposed to estimate the above-mentioned parameters before applying the turbo code reconstruction process. The proposed method reduces the search space of the reconstruction process significantly and makes the reconstruction process faster and more efficient.


## 3. Proposed Method

Assume that the number of elements with the value of 1 in puncturing matrixP(n1+n2-k)×p is equal to n0. Using the same arguments as those detailed in [5], if the input data to the turbo encoder behaves as random data, we can say that the number of linearly independent blocks of received coded stream with length n0×i, assuming i to be a positive integer, is at most equal to (p×k+p×k)×i+m0, where nonnegative integer m0 takes at most the value of m1+m2. This can be easily seen by noting that each block, out of i blocks with length n0, is generated by linear combination of p×k+p×k information bits and m1+m2 initial memory bits. When the Hamming weight in the last n2-k rows ofP is smaller than p×k, the value of the second p×k should be interchanged with this Hamming weight. Let us denote the minimum value between p×k and the Hamming weight in the last n2-k rows ofP by p2. Thus, we can say that the number of linearly independent blocks of received coded stream with length n0×i is at most equal to (p×k+p2)×i+m0. When p2<p×k we can say that p2 parity bits of the second convolutional encoder in each puncturing period act like random independent data, so it can be concluded that in this case m0 can take at most the value of m1. Since only the values of i that results in ((p×k+p2)×i+m0)/(n0×i)<1 are acceptable, we have
(1)i≥m0n0-p0+1,
where p0=p×k+p2 and x denotes the largest integer less than or equal to x.Starting from the first bit we partition the received bit stream into blocks with lengthn and consider these blocks as the rows of a matrix named Zn with size a×n. Choosing the value of a is arbitrary, but it should be selected in order to be much bigger than n. Now, if we define function R(n) for the received bit stream in the domain of positive integer as follows:
(2)Rn=RankZnn,
where Rank(Zn) denotes the rank of matrix Zn, according to the aforementioned discussion in the beginning of this section, it is obvious that this function should have local minimum points at n=n0×i, where i is given by (1). Moreover, the function values at these local minimum points are given as follows:
(3)Ri×n0=p0×i+m0n0×i;i≥m0n0-p0+1.
By obtaining local minimum points and function values at these points for function R(n) it is possible to estimate the values of m0, p0, and n0 parameters of turbo code, which can facilitate the turbo code reconstruction process.If in the construction process ofZn (whilst n=n0×i) we eliminate the first α  bits of bit stream (α∈{0,1,2,…,n0-1}), the obtained matrix denoted by Zn,α can help us to estimate the puncturing matrix. In fact, if the value of α  is chosen such that the first considered bit in construction of Zn,α is a systematic bit in the first row ofP, it is obvious that Rank(Zn,α)=Rank(Zn). On the other hand, if the value of α  is chosen such that the first considered bit in construction of Zn,α is a systematic bit in other rows ofP or a parity bit of the first convolutional code, we expect that Rank(Zn,α)>Rank(Zn). As a matter of fact, in such situations degree of freedom is increased which results in larger rank values. Finally, if the value of α  is chosen such that the first considered bit in construction of Zn,α is a parity bit of the second convolutional code, we expect that in (at most) p positions the equality Rank(Zn,α)=Rank(Zn) holds, whereas, in the remaining positions, if any, the inequality Rank(Zn,α)>Rank(Zn) holds.Thus, we can define puncturing signature as a vector with lengthn0 in the following way. For any α∈{0,1,2,…,n0-1}, if Rank(Zn0×i,α)>Rank(Zn0×i) the corresponding element in puncturing signature is set to 1; otherwise it is set to 0. Note that, by knowing the values of k, n1, n2, and p, construction of puncturing matrixP from puncturing signature is not unique, but definitely, the search space size for puncturing matrix is intensely reduced. Numerical results for implying this fact will be provided in the following section.According to the above analysis, we are ready to present the proposed method for estimation of the number of input and output bits of both encoders (i.e.,k, n1, and n2) and the puncturing pattern (i.e.,P).(1)
PlotR(n) versus n for n=nmin⁡, nmin⁡+1,…,nmax⁡ (nmin⁡ and nmax⁡ are two arbitrary integers). Denote the set of the points at which the local minimums occur by {n^j} and the set of the function local minimum values by {Rj}, where j=1,2,3,…,jmax⁡. Define the set of {k^j} such that k^j=Rj×n^j for any j.(2)
Estimate the value ofn0 as follows: n0=mode({n^j+1-n^j;j=1,2,…,jmax⁡-1}), where modeX denotes the most frequent value in set X.(3)
Estimate the value ofp0 as follows: p0=mode({k^j+1-k^j;j=1,2,…,jmax⁡-1}).(4)
Estimate the value ofm0 as follows: m0=mode({k^j-(n^j/n0)×p0;j=1,2,…,jmax⁡}).(5)
Plot functionR(n^jmax⁡,α)=Rank(Zn^jmax⁡,α)/n^jmax⁡ versus α for α=0,1,…,n0-1, and then obtain the puncturing signature as stated before.(6)
Using the estimated values ofn0, p0, and puncturing signature we can consider feasible values of k, n1, and n2 to construct all possible puncturing matrices. Then, since the construction process of the turbo code can be called with any sets of these possible parameters, somewhere we expect that one of these calls successfully results in a turbo code structure. Estimated value of m0 can as well help to make the size of the search space for constituent convolutional codes smaller.Note that, compared to the current methods which should blindly pass any possible set of parameters to the turbo code construction process, the proposed method here tries to reduce the size of such large search space. Numerical results for comparison reasons are provided in the following section.In formulation of the proposed method for estimation of turbo code parameters it is assumed that the observed turbo coded stream is noiseless. In such situation, the rows of matrixZn form a linear space denoted by Γ. Similarly, the rows of matrix Zn,α form a linear space denoted by Γα. So, if the received data is noisy it is obvious that we can use the proposed algorithm on noiseless rows of Zn and Zn,α, and yet the same turbo code parameters as the noiseless case will be obtained. However, we should choose the number of the rows of Zn and Zn,α large enough in order that the number of the noiseless rows of these matrices becomes much bigger than n.In order to find the noiseless rows ofZn, first we apply Valembois’ algorithm [7] on (noisy) rows of Zn to find some words in the dual space of Γ. Now, any rows of Zn that is orthogonal to all obtained words in the dual space of Γ can be considered as a noiseless row. A similar method can be used to find noiseless rows of Zn,α.Numerical and simulation results provided in the next section show that this algorithm is quite efficient in space search size reduction, and moreover it is also robust when it is fed with noisy and erroneous input.


## 4. Experimental Results

For obtaining experimental results we consider three different turbo code structures. The characteristics of these codes are given in Table1. The first code is the code applied in WCDMA standard and the two others are introduced in CDMA 2000 standard. In this table,G1(D) andG2(D) denote polynomial representation of generator matrix of the first and the second convolutional codes, respectively.Table 1
The structure of the simulated turbo code.
Constituent convolutional codesG1(D)=G2(D)=G(D)
Puncturing matrix
Overall code rate
Turbo codeA
G
(
D
)
=
[
1
,
1
+
D
+
D
3
1
+
D
2
+
D
3
]
P
=
[
1
1
1
]
1/3
Turbo codeB
G
(
D
)
=
[
1
,
1
+
D
+
D
3
1
+
D
2
+
D
3
,
1
+
D
+
D
2
+
D
3
1
+
D
2
+
D
3
]
P
=
[
1
1
1
1
1
]
1/5
Turbo codeC
G
(
D
)
=
[
1
,
1
+
D
+
D
3
1
+
D
2
+
D
3
,
1
+
D
+
D
2
+
D
3
1
+
D
2
+
D
3
]
P
=
[
1
1
1
1
1
0
0
1
1
1
]
1/4For comparison reasons, we set the first dimension of matrixZn to 3×n and set the value of nmin⁡ and nmax⁡ to 21 and 60, respectively. In Figure 2, function R(n) for turbo codeB is plotted. For this code the set of the points at which the local minimums occur is {n^j}=25,30,35,…,55. According to this set and as we expected, the distance between the consecutive points at which the local minimums occur is equal to n0=5. For some turbo codes, more than one set of local minimums can be observed. For example, function R(n) for turbo codeC is shown in Figure 3. As it is apparent from this figure, two distinguishable sets of local minimum points are {n^j}=24,32,40,48,56 and {n^j}=28,36,44,52. In such cases, the set with smallest local minimum values should be used to estimate turbo code parameters. The other local minimum set(s) in this case are formed due to the special structure of the constituent convolutional encoders and the puncturing pattern. For example, for codeC, when the values of n are selected from the set {8×3+4, 8×4+4, 8×5+4,…}, linearly independent blocks of received coded stream would be less than n; however, the relative number of these linearly independent blocks, that is, R(n), is higher compared to the situation in which the values of n are selected from the right set which is {8×3, 8×4, 8×5, …}.Figure 2
Plot ofR(n) for turbo codeB.Figure 3
Plot ofR(n) for turbo codeC.In Table2, estimated parameters of turbo codes defined in Table 1 for the case of noiseless coded stream are given. As we can see, the given values for parameters n0, p0, and m0 match the expected value. The last column of Table 2 represents the number of the potential sets of k,n1,n2,P which can be considered according to the estimated values for n0 and p0. For turbo codesA andB, the only potential sets of k,n1,n2,P are those given in Table 1. But for turbo codeC the number of the potential sets of k,n1,n2,P is equal to 56. Note that this value is much smaller compared to the number of the potential sets in blind reconstruction. For example, if the reconstruction process operates blindly in the case in which the values of k, n1, n2, and p are assumed to be at most equal to 2, 3, 3, and 5, respectively, all possible puncturing matrices having these properties should be considered and the only constraint is that the number of 1 s in the examined puncturing matrices should be a factor of the output frames length which is assumed to be equal to 1200 in this case. It can be seen that in this case the search space size is equal to 461794 which is much larger than 56.Table 2
Estimated parameters of turbo codes defined in Table1 for noiseless case.
n
0
p
0
m
0
Puncturing signature
Number of potential sets of{k,n1,n2,P}
Turbo codeA
3
2
3
[
0,1
,
0
]
1
Turbo codeB
5
2
6
[
0,1
,
1,0
,
1
]
1
Turbo codeC
8
4
5
[
0,1
,
1,0
,
0,1
,
0,1
]
56To evaluate the capability of the proposed method against channel noise, we consider that the turbo coded stream is first modulated by a binary phase shift keying (BPSK) modulator and then passed through an additive white Gaussian noise (AWGN) channel. Also, we defineEb/N0 as the ratio of energy per transmitted bit (Eb) to the spectral noise density (N0). In Table 3, success probability for turbo code parameter estimation is given under the assumption of different Eb/N0 values, considering the turbo codes defined in Table 1. The number of tests for each turbo code and SNR pair is set to 1000. As it is apparent from this table, when the value of Eb/N0 is more than 5 dB, the probability of success is near 1, but for Eb/N0 values around 3 dB the probability of success reaches 0.Table 3
Probability of success in parameters estimation of turbo codes defined in Table1 for noisy channel.
E
b
/
N
0 (dB)
5.2
4.2
3.7
3.2
Turbo codeA
≈1
0.91
0.42
0.05
Turbo codeB
≈1
0.52
0.05
≈0
Turbo codeC
≈1
0.65
0.07
≈0Since turbo codes are supposed to perform in noisy channels, the low noise assumption for code reconstruction may seem too optimistic. However, it should be noted that in practical noncooperative situations, recognition of a communication system is usually done in higher values of signal to noise ratio compared to cooperative situations. In fact, in order to achieve such signal quality, we have no choice other than using ultra low noise receivers. Finally, it should be noted that the channel code reconstruction process is done once based on many observations of the channel code outputs and decision on which of the estimated code parameters to be picked as the true code parameters can be easily made based on the multiplicity and inferred confidence of the estimated sets.


## 5. Conclusion

A novel method is proposed in this paper to estimate the parameters of turbo codes. These parameters are the number of input and output bits of both constituent convolutional encoders and the puncturing pattern while assuming that the target turbo code is systematic. It is assumed that receiver is only aware of the turbo coded bit stream. Numerical results confirm that the proposed method significantly reduces the size of the search space for reconstruction process of the turbo code. Moreover, simulation results indicate that when the proposed algorithm is fed with erroneous channel observations, the outcome is highly reliable as long as theEb/N0 value is more than 5 dB, demonstrating robustness of the proposed algorithm.



---

*Source: 282108-2014-09-18.xml*