# Reduced Complexity Iterative Decoding of 3D-Product Block Codes Based on Genetic Algorithms

Authors: Abdeslam Ahmadi; Faissal El Bouanani; Hussain Ben-Azza; Youssef Benghabrit
Journal: Journal of Electrical and Computer Engineering
 (2012)

---

## Abstract

Two iterative decoding algorithms of 3D-product block codes (3D-PBC) based on genetic algorithms (GAs) are presented. The first algorithm uses the Chase-Pyndiah SISO, and the second one uses the list-based SISO decoding algorithm (LBDA) based on order-i reprocessing. We applied these algorithms over AWGN channel to symmetric 3D-PBC constructed from BCH codes. The simulation results show that the first algorithm outperforms the Chase-Pyndiah one and is only 1.38 dB away from the Shannon capacity limit at BER of 10−5 for BCH (31, 21, 5)3 and 1.4 dB for BCH (16, 11, 4)3. The simulations of the LBDA-based GA on the BCH (16, 11, 4)3 show that its performances outperform the first algorithm and is about 1.33 dB from the Shannon limit. Furthermore, these algorithms can be applied to any arbitrary 3D binary product block codes, without the need of a hard-in hard-out decoder. We show also that the two proposed decoders are less complex than both Chase-Pyndiah algorithm for codes with large correction capacity and LBDA for large i parameter. Those features make the decoders based on genetic algorithms efficient and attractive.


---

## Body

## 1. Introduction

Among the proposed codes in the history of error correcting, there are those who have performance very close to the Shannon limit, like Turbo codes [1] and LDPC codes [2]. Nevertheless, the remarkable reduction of BER is performed at the expense of their decoders complexity. The current challenge for researchers in this field is to find a compromise between performance and decoding complexity. Thus, several optimization works of decoding algorithms have emerged, in particular, those associated to product codes. These codes were first introduced in 1954 by Elias [3]. In 1981 and 1983, an iterative decoding method hard-in hard-out (HIHO) of these codes has been described, respectively by Tanner [4] and Lin and Costello [5]. In 1994, a soft-in soft-out (SISO) iterative decoding of the product block codes (PBC) was proposed by Pyndiah et al. [6], using the Chase algorithm as the elementary decoder [7]. This algorithm does not work alone, but together with another decoder HIHO which is not always easy to find for some codes, like quadratic residue (QR). Later, in 2004, an enhanced SISO iterative decoding algorithm of PBC, based on order reprocessing decoding, was developed by Martin et al. [8].Recently, the researchers in the field of channel coding were inspired from artificial intelligence techniques to develop very good decoders for linear block codes. We quote from the first works in this sense, the decoding of linear block codes using algorithm A* [9], genetic algorithms [10], and neural networks [11].We were interested in this work in decoders based on genetic algorithms (GAD) [10] applied to the 3D-product block code (3D-PBC). It was shown in [12], that these decoders applied to BCH codes outperform the Chase-2 algorithm and present a lower complexity for BCH codes with large block lengths. We note that their performances can be improved further by optimizing some parameters such as the population size and the number of generations.In this paper, which is the continuation of the work [13], we introduce and study two iterative decoding algorithms of an arbitrary 3D binary product block code based on GAD. The extrinsic information is computed in the first proposed algorithm according to the Chase-Pyndiah formulas [6] and is computed in the second one according to the list-based SISO decoding algorithm (LBDA) [8]. A comparison at the level of complexity of the proposed algorithms versus Chase-Pyndiah and LBDA algorithms was made.This paper is organized as follows. Section2 defines the 3D-PBC code. Then, we explain in Section 3, the elementary decoding based on GAD. The presentation and complexity study of our iterative decoding algorithms using genetic algorithms IGAD, will be given in Section 4. Section 5 illustrates, through simulations, the IGAD performances and the effect of some parameters on these performances. It also presents a comparison of performances between the two proposed algorithms. Finally, Section 6 presents the conclusion and indicates how the performances of our decoders can be improved further.


## 2. 3D-Product Block Code (3D-PBC)

The product codes (or iterative codes) are a particular case of serial concatenated codes. They allow to construct codes of great length by concatenating two or more arbitrary block codes with short lengths. In our case, we considered twosymmetric  3D-PBC, (16, 11, 4)3 and (31, 21, 5)3, which consists of three identical codes BCH each one.LetC(1)(n1,k1,d1), C(2)(n2,k2,d2), and C(3)(n3,k3,d3), three linear block codes. We encode an information block, using 3D-PBC=C(1)⊗C(2)⊗C(3) given in the Figure 1, by(1)
filling a cube ofk2 rows, k1 columns and k3 as the depth by k1×k2×k3 information bits;(2)
coding thek2×k3 rows (the cube contains k3 lateral plans which are composed from k2 rows each one) using code C(1). The check bits are placed at the right, and we obtain a new cube with k2×k3×n1 bits;(3)
coding then1×k3 columns of the cube obtained in the previous step using code C(2). This means that the check bits will be also encoded (the previous cube contains n1 transverse plans which are composed from k3 columns each one). The check bits are placed at the bottom of the cube obtained in step 2, and we get a new cube with n1×k3×n2 bits;(4)
Coding, finally the obtained cube in step 3 from the front to the behind, that is, coding then1×n2 columns, using code C(3) (the previous cube consists of n2 horizontal plans which contains n1 columns). The check bits are placed at the behind. So, the last cube which has n1×n2×n3 bits is the codeword.Figure 1
The 3D-product block code.We can show by similar reasoning in [14] that the parameters of the 3D-PBC are(i)
length:n=n1×n2×n3;(ii)
dimension:k=k1×k2×k3:(iii)
minimum Hamming distance;d=d1×d2×d3.(iv)
rate:R=R1×R2×R3=k1/n1×k2/n2×k3/n3.This shows one of the best advantages of product block codes: building very long block codes with large minimum Hamming distance by concatenating short codes with small minimum Hamming distance.


## 3. Elementary Decoding of Linear Codes

LetR=(R1,…,Rn) be the received sequence at the decoder input of a binary linear block code C(n,k,d) with a generator matrix G.


### 3.1. Hard-Input Soft-Output Decoder

Step 1
Sort the elements of received vectorR in descending order of magnitude. This will put reliable elements in the first ranks, since using an AWGN channel. Then, the vector is permuted such that its first k coordinates are linearly independent. We obtain a vector R′=π(R)=(R1′,…,Rn′) such that |R1′|≥|R2′|≥···≥|Rn′|. Let G′ be the permutation of G by π, that is, G′=π(G).Step 2
Quantize the firstk bits of R′ to obtain vector r and randomly generate (Ni-1) information vectors of k bits each one. This vectors form with vector r the initial population of Ni individuals (I1,…,INi).Step 3
Encode individuals of the current population, usingG′ to obtain codewords: Ci=G′·Ii(1≤i≤Ni). Then, compute individuals fitness, defined as Euclidian distance between Ci and R′. Sort individuals in ascending order of fitness.Step 4
Place the firstNe individuals (Ne: elite number ≤Ni) to the next population, which will be completed by offsprings generated using reproduction operators: selection of two best individuals as parents (a,b) using the following linear ranking:
(1)Wi=Wmax⁡-2(i-1)(Wmax⁡-1)Ni-1,∀i∈{1,…,Ni},
where Wi is the ith individual weight, and Wmax weight is assigned to the fittest (nearest) individual.
Reproduce the(Ne+1) remaining individuals of the next population by crossover and mutation operations. Let pc, pm and Rand be respectively, probabilities of crossover and mutation, and a uniformly random value between 0 and 1, generated at each time.
ifRand<pc,  thenforall∈{Ne+1,…,Ni},j∈{1,…,k}:(2)Iij={ajifRand<(1-aj+ajbj)+aj-bj1+e-4Rj′/N0bjelse,
and then,
(3)Iij=1-IijifRand<pm,else(4)Ii={aifRand<0.5belse,end ifRepeat steps 3 and 4 forNg generations.Step 5
The first (fittest) individualD′ of the last generation is the nearest to R′. So, the decided codeword is D=π-1(D′).


### 3.2. Soft-Input Soft-Output Decoder

In this section, we present the SO_GAD decoders (soft-output GAD) used as the elementary decoder in our iterative decoding algorithms.LetD denote the GAD decision of the input sequence R and w the extrinsic information.LetH(j) be the competitor codeword of D corresponding to the jth bit defined by (5)‖H(j)-R‖=min⁡2≤p≤Ni⁡{‖Q(p)-R‖,Qj(p)≠Dj},
where Q(p)is the pth codeword of the last generation, Qj(p) and Dj are the jth bits of Q(p),D and, ∥.∥ is the Euclidean distance.Algorithm 1.
(w,D)=SO_GAD(k,n,R,pc,pm,Ni,Ng,β). Algorithm SO_GAD accepts as input k,n,pc,pm,Ni,Ng, the coefficient β. This coefficient is optimized according to the chosen code and SNR to enhance the algorithm performance.
Forj=1  ton  do
if  H(j)  exists, then(6)wj=D̃j[‖H(j)-R‖-‖D-R‖4]=D̃j∑p=1,p≠jHp(j)≠DpnRPD̃p,
else(7)wj=βD̃j,
where D̃j=2Dj-1.
end if
End forAlgorithm 2.
(w,D)=SO_GAD(k,n,R,pc,pm,Ni,Ng,Ns). Let Ns be the LBDA parameter (Ns≤k)  enhancing the decoding performances [8]. The algorithm SO_GAD accepts as input k,n,pc,pm,Ni,Ng, and Ns. This parameter is usually chosen to be ⌈2k/3⌉ or k.
Forj=1  to  k-Ns  do(8)wj=D̃j|Γ|∑l=k-Ns+1,l∈ΓnD̃lwlif∑l=k-Ns+1,l∈ΓnD̃lwl≥0,wj=D̃jmin⁡l∈Γ{D̃lwl>0}otherwise,
where Γ denotes the set of positions j where H(j) exists.
End for
Forj=k-Ns+1  ton   do
if  H(j)  exists, then(9)wj=[12D̃j∑l=1n(D̃l-H̃l(j))Rl]-Rj,
else(10)wj=D̃j|Γ|∑l=k-Ns+1,l∈ΓnD̃lwlif∑l=k-Ns+1,l∈ΓnD̃lwl≥0,wj=D̃jmin⁡l∈Γ{D̃lwl>0}otherwise,
where Γ denotes the set of positions j where H(j) exists.
end if
End for.


#### 3.2.1. Decoding

The SO_GAD algorithm uses GAD for decoding the input sequenceR. The decision codeword D is the top of the Ngth generation sorted in ascending order of fitness, and the competitor codeword H(j) corresponding to the jth bit of D, if it exists, is the first member of the last generation which have the different jth bit Hj(j)(Hj(j)≠Dj).


#### 3.2.2. Extrinsic Information

The decision codewordD and the associated competitor codewords (H(j))1≤j≤n are used to calculate the extrinsic information from the formulas (6) and (7) for the first algorithm and (8) and (9) in the case of the second one.


## 3.1. Hard-Input Soft-Output Decoder

Step 1
Sort the elements of received vectorR in descending order of magnitude. This will put reliable elements in the first ranks, since using an AWGN channel. Then, the vector is permuted such that its first k coordinates are linearly independent. We obtain a vector R′=π(R)=(R1′,…,Rn′) such that |R1′|≥|R2′|≥···≥|Rn′|. Let G′ be the permutation of G by π, that is, G′=π(G).Step 2
Quantize the firstk bits of R′ to obtain vector r and randomly generate (Ni-1) information vectors of k bits each one. This vectors form with vector r the initial population of Ni individuals (I1,…,INi).Step 3
Encode individuals of the current population, usingG′ to obtain codewords: Ci=G′·Ii(1≤i≤Ni). Then, compute individuals fitness, defined as Euclidian distance between Ci and R′. Sort individuals in ascending order of fitness.Step 4
Place the firstNe individuals (Ne: elite number ≤Ni) to the next population, which will be completed by offsprings generated using reproduction operators: selection of two best individuals as parents (a,b) using the following linear ranking:
(1)Wi=Wmax⁡-2(i-1)(Wmax⁡-1)Ni-1,∀i∈{1,…,Ni},
where Wi is the ith individual weight, and Wmax weight is assigned to the fittest (nearest) individual.
Reproduce the(Ne+1) remaining individuals of the next population by crossover and mutation operations. Let pc, pm and Rand be respectively, probabilities of crossover and mutation, and a uniformly random value between 0 and 1, generated at each time.
ifRand<pc,  thenforall∈{Ne+1,…,Ni},j∈{1,…,k}:(2)Iij={ajifRand<(1-aj+ajbj)+aj-bj1+e-4Rj′/N0bjelse,
and then,
(3)Iij=1-IijifRand<pm,else(4)Ii={aifRand<0.5belse,end ifRepeat steps 3 and 4 forNg generations.Step 5
The first (fittest) individualD′ of the last generation is the nearest to R′. So, the decided codeword is D=π-1(D′).


## 3.2. Soft-Input Soft-Output Decoder

In this section, we present the SO_GAD decoders (soft-output GAD) used as the elementary decoder in our iterative decoding algorithms.LetD denote the GAD decision of the input sequence R and w the extrinsic information.LetH(j) be the competitor codeword of D corresponding to the jth bit defined by (5)‖H(j)-R‖=min⁡2≤p≤Ni⁡{‖Q(p)-R‖,Qj(p)≠Dj},
where Q(p)is the pth codeword of the last generation, Qj(p) and Dj are the jth bits of Q(p),D and, ∥.∥ is the Euclidean distance.Algorithm 1.
(w,D)=SO_GAD(k,n,R,pc,pm,Ni,Ng,β). Algorithm SO_GAD accepts as input k,n,pc,pm,Ni,Ng, the coefficient β. This coefficient is optimized according to the chosen code and SNR to enhance the algorithm performance.
Forj=1  ton  do
if  H(j)  exists, then(6)wj=D̃j[‖H(j)-R‖-‖D-R‖4]=D̃j∑p=1,p≠jHp(j)≠DpnRPD̃p,
else(7)wj=βD̃j,
where D̃j=2Dj-1.
end if
End forAlgorithm 2.
(w,D)=SO_GAD(k,n,R,pc,pm,Ni,Ng,Ns). Let Ns be the LBDA parameter (Ns≤k)  enhancing the decoding performances [8]. The algorithm SO_GAD accepts as input k,n,pc,pm,Ni,Ng, and Ns. This parameter is usually chosen to be ⌈2k/3⌉ or k.
Forj=1  to  k-Ns  do(8)wj=D̃j|Γ|∑l=k-Ns+1,l∈ΓnD̃lwlif∑l=k-Ns+1,l∈ΓnD̃lwl≥0,wj=D̃jmin⁡l∈Γ{D̃lwl>0}otherwise,
where Γ denotes the set of positions j where H(j) exists.
End for
Forj=k-Ns+1  ton   do
if  H(j)  exists, then(9)wj=[12D̃j∑l=1n(D̃l-H̃l(j))Rl]-Rj,
else(10)wj=D̃j|Γ|∑l=k-Ns+1,l∈ΓnD̃lwlif∑l=k-Ns+1,l∈ΓnD̃lwl≥0,wj=D̃jmin⁡l∈Γ{D̃lwl>0}otherwise,
where Γ denotes the set of positions j where H(j) exists.
end if
End for.


### 3.2.1. Decoding

The SO_GAD algorithm uses GAD for decoding the input sequenceR. The decision codeword D is the top of the Ngth generation sorted in ascending order of fitness, and the competitor codeword H(j) corresponding to the jth bit of D, if it exists, is the first member of the last generation which have the different jth bit Hj(j)(Hj(j)≠Dj).


### 3.2.2. Extrinsic Information

The decision codewordD and the associated competitor codewords (H(j))1≤j≤n are used to calculate the extrinsic information from the formulas (6) and (7) for the first algorithm and (8) and (9) in the case of the second one.


## 3.2.1. Decoding

The SO_GAD algorithm uses GAD for decoding the input sequenceR. The decision codeword D is the top of the Ngth generation sorted in ascending order of fitness, and the competitor codeword H(j) corresponding to the jth bit of D, if it exists, is the first member of the last generation which have the different jth bit Hj(j)(Hj(j)≠Dj).


## 3.2.2. Extrinsic Information

The decision codewordD and the associated competitor codewords (H(j))1≤j≤n are used to calculate the extrinsic information from the formulas (6) and (7) for the first algorithm and (8) and (9) in the case of the second one.


## 4. Iterative Decoding Algorithm and Complexity

In this section, we describe the iterative decoding algorithm of PBC based on GAD (IGAD), then we show that IGAD has a polynomial time complexity.Let{C(i)(ni,ki,di)}1≤i≤3 denotes three binary linear block codes of length ni, dimension ki, minimum Hamming distance di, and generator matrix G(i).


### 4.1. Iterative Decoding Algorithm

Let(Rijk)1≤i≤n2,1≤j≤n1,1≤k≤n3 be the received codeword. Figures 2 and 3 show the iterative decoding schemes of PBC based on GAD for the proposed algorithms. The following is an outline of IGADs.Figure 2
The(⌊θ/3⌋+1)th iteration of IGAD1.Figure 3
The(⌊θ/3⌋+1)th iteration of IGAD2.Algorithm 3.
IGAD(k1,
k2,
k3,n1,
n2,
n3,R,
pc,
pm,
Ni,
Ng,
Nit,
α,{Ns|β}).
Algorithm IGAD accepts as inputk1,  k2,  k3,  n1,  n2,  n3,R,  pc,  pm,  Ni,  Ng, the iterations number Nit, the coefficients (α(θ))0≤θ<3Nit. In the case of the first algorithm, we use the coefficients (β(θ))0≤θ<3Nit, and in the second, we use the Ns parameter. The α and β coefficients are optimized by simulation step by step for each code. For the second algorithm, we chooseα  to be 0.5.Step 1
Extrinsic informationinitialization
θ=0, Iteration=1.
Letwijk(θ) is the extrinsic information given to θth elementary decoder by the other decoder:(11)wijk(0)=0,1≤i≤n2,1≤j≤n1,1≤k≤n3.Step 2
Row, column, and depth decoding:
While(It≤Nit)  doStep 2.1.
Decoding with SO_GAD thejth columnand estimating the extrinsic informationwijk(θ+1), using (6) and (7), of each vectors.j. at the input of the elementary decoder:
(12)sijk(θ)=Rijk+α(θ)wijk(θ)1≤i≤n2,1≤k≤n3.Step 2.2.  and 2.3.
Repeat step 2.1 for decoding the rows and depths and estimating the extrinsic information. LetD(θ+3) and w(θ+3) be respectively the cubes decision and extrinsic information at the output of the depth elementary decoder.Step 3
Iteration=Iteration+1;  θ=θ+1.End While.Select thedecided codewordD(3Nit)  at theNitth iteration.Stopping Criterion for the Second Algorithm.Since the GAD decoder decides always a codeword, our second decoder does not need to use the NCB (nonconvergent block) decoder proposed in [8]. So, its complexity will be reduced.


### 4.2. Complexity Analysis

In this section, we present and compare the expressions of time complexities of the studied decoders.


#### 4.2.1. IGADs Time Complexity

If we do not take into consideration the calculating step of the extrinsic information, the two algorithms have the same time complexity. The GAD algorithm for a linear block codeC(n,k) has polynomial time complexity O(f(k,n,Ni,Ng)), where the function f is given by [12](13)f(k,n,Ni,Ng)=k2n+NiNg(kn+log⁡⁡Ni).Time Complexity of IGAD1
(i)
Time complexity of extrinsic information computing: For each decision (row, column, or depth) at the last generation of each iteration, the worst-case time complexity of competitors search isO([Ni-1]n).From (6), the time complexity of extrinsic information calculating in the worst-case (if the competitor exists) at the last generation of each iteration is O(n2). So the total time complexity of extrinsic information computing is O(comp1(Ni,n)), where(14)comp1(Ni,n)=Nin+n2,(ii)
total time complexity:At any iteration of IGAD1, the first elementary decoder has a time complexity ofO(k2k3f(k1,n1,Ni,Ng)), the second decoder has a complexity of O(n1k3f(k2,n2,Ni,Ng)), and the third decoder has a time complexity of O(n1n2f(k3,n3,Ni,Ng)), so the total complexity is polynomial:(15)O(Nit[k2k3g(k1,n1,Ni,Ng)+n1k3g(k2,n2,Ni,Ng)+n1n2g(k3,n3,Ni,Ng)]),
where(16)g(k,n,Ni,Ng)=f(k,n,Ni,Ng)+comp1(Ni,n).
For the symmetric 3D-PBCn1=n2=n3=n and k1=k2=k3=k, then the IGAD1 time complexity becomes(17)O(Nit[k2+n2+kn][k2n+NiNg(kn+log⁡⁡Ni)+nNi+n2]).Time Complexity of IGAD2
(i)
Time complexity of extrinsic information computing: The maximal number of competitors of each decision is|Γ|max=n. So, at the last generation of each iteration, the worst-case time complexity of the first step given by (8) is O((k-Ns)max(2n+1,2(n+Ns-k)+3))=O(n(k-Ns)).From (9), the worst-case time complexity of competitors search is is O([Ni-1](n-k+Ns)).From (9) and (10), the time complexity in the worst-case of the second step of extrinsic information calculating is(18)O((n-k+Ns)max⁡(2n+3,2(n+Ns-k)+3,2n+1))=O(n(n-k+Ns)).So the total time complexity of extrinsic information computing isO(comp2(Ni,n,Ns,k)), where(19)comp2(Ni,n,Ns,k)=Ni(n-k+Ns)+n2,(ii)
total time complexity:The total complexity in this case is given from (16):(20)g(k,n,Ni,Ng)=f(k,n,Ni,Ng)+comp2(Ni,n,Ns,k).
For the symmetric 3D-PBCn1=n2=n3=n and k1=k2=k3=k, then the IGAD2 time complexity becomes(21)O(k2Nit[k2+n2+kn]×[k2n+NiNg(kn+log⁡Ni)+Ni(n-k+Ns)+n2]).
It is clear from (17) and (21) that IGAD2 is less complex than IGAD1, and their complexities are equal if Ns=k.


#### 4.2.2. Chase-Pyndiah and LBDA Algorithms Time Complexities

We show that this algorithm has an exponential time complexity. LetC(n,k,d) be a BCH code, and let M be the test patterns number used in both Chase and OSD-i (ordered statistic decoding) algorithms. The complexity of each algorithm is O(Mn2log2n).The Euclidian distance computing of each codeword has a computational complexity ofO(n). So, the total time complexity of decoding and computing fitness of the M test patterns is O(Mn2log2n).At any given decoding iteration of the Chase-Pyndiah algorithm, the sorting step of theM fitness has a time complexity of O(Mlog2M) and the the worst-case time complexity of competitors search is O([M-1]n). Thus, the total time complexity of the Chase-Pyndiah algorithm is(22)O(Nit[k2k3F(n1,k1,t1)+k3n1F(n2,k2,t2)+n1n2F(n3,k3,t3)]),
where (23)F(n,k,t)=M[n2log⁡2⁡n+log⁡2⁡M].Thus, in the case ofn1=n2=n3=n, k1=k2=k3=k, and, the exponential time complexity of the two algorithms is(24)O(NitM[n2+k2+kn][log⁡2M+n2log⁡2n]).Note that in the case of Chase-2 algorithm,M=2t,  where   t=⌊(d-1)/2⌋.From (17) and (24), it is shown that IGAD1 and IGAD2 are less complex than the two Chase-Pyndiah and LBDA algorithms for codes with large correction capacity t or for large i parameter or also with great length and low rate.


## 4.1. Iterative Decoding Algorithm

Let(Rijk)1≤i≤n2,1≤j≤n1,1≤k≤n3 be the received codeword. Figures 2 and 3 show the iterative decoding schemes of PBC based on GAD for the proposed algorithms. The following is an outline of IGADs.Figure 2
The(⌊θ/3⌋+1)th iteration of IGAD1.Figure 3
The(⌊θ/3⌋+1)th iteration of IGAD2.Algorithm 3.
IGAD(k1,
k2,
k3,n1,
n2,
n3,R,
pc,
pm,
Ni,
Ng,
Nit,
α,{Ns|β}).
Algorithm IGAD accepts as inputk1,  k2,  k3,  n1,  n2,  n3,R,  pc,  pm,  Ni,  Ng, the iterations number Nit, the coefficients (α(θ))0≤θ<3Nit. In the case of the first algorithm, we use the coefficients (β(θ))0≤θ<3Nit, and in the second, we use the Ns parameter. The α and β coefficients are optimized by simulation step by step for each code. For the second algorithm, we chooseα  to be 0.5.Step 1
Extrinsic informationinitialization
θ=0, Iteration=1.
Letwijk(θ) is the extrinsic information given to θth elementary decoder by the other decoder:(11)wijk(0)=0,1≤i≤n2,1≤j≤n1,1≤k≤n3.Step 2
Row, column, and depth decoding:
While(It≤Nit)  doStep 2.1.
Decoding with SO_GAD thejth columnand estimating the extrinsic informationwijk(θ+1), using (6) and (7), of each vectors.j. at the input of the elementary decoder:
(12)sijk(θ)=Rijk+α(θ)wijk(θ)1≤i≤n2,1≤k≤n3.Step 2.2.  and 2.3.
Repeat step 2.1 for decoding the rows and depths and estimating the extrinsic information. LetD(θ+3) and w(θ+3) be respectively the cubes decision and extrinsic information at the output of the depth elementary decoder.Step 3
Iteration=Iteration+1;  θ=θ+1.End While.Select thedecided codewordD(3Nit)  at theNitth iteration.Stopping Criterion for the Second Algorithm.Since the GAD decoder decides always a codeword, our second decoder does not need to use the NCB (nonconvergent block) decoder proposed in [8]. So, its complexity will be reduced.


## 4.2. Complexity Analysis

In this section, we present and compare the expressions of time complexities of the studied decoders.


### 4.2.1. IGADs Time Complexity

If we do not take into consideration the calculating step of the extrinsic information, the two algorithms have the same time complexity. The GAD algorithm for a linear block codeC(n,k) has polynomial time complexity O(f(k,n,Ni,Ng)), where the function f is given by [12](13)f(k,n,Ni,Ng)=k2n+NiNg(kn+log⁡⁡Ni).Time Complexity of IGAD1
(i)
Time complexity of extrinsic information computing: For each decision (row, column, or depth) at the last generation of each iteration, the worst-case time complexity of competitors search isO([Ni-1]n).From (6), the time complexity of extrinsic information calculating in the worst-case (if the competitor exists) at the last generation of each iteration is O(n2). So the total time complexity of extrinsic information computing is O(comp1(Ni,n)), where(14)comp1(Ni,n)=Nin+n2,(ii)
total time complexity:At any iteration of IGAD1, the first elementary decoder has a time complexity ofO(k2k3f(k1,n1,Ni,Ng)), the second decoder has a complexity of O(n1k3f(k2,n2,Ni,Ng)), and the third decoder has a time complexity of O(n1n2f(k3,n3,Ni,Ng)), so the total complexity is polynomial:(15)O(Nit[k2k3g(k1,n1,Ni,Ng)+n1k3g(k2,n2,Ni,Ng)+n1n2g(k3,n3,Ni,Ng)]),
where(16)g(k,n,Ni,Ng)=f(k,n,Ni,Ng)+comp1(Ni,n).
For the symmetric 3D-PBCn1=n2=n3=n and k1=k2=k3=k, then the IGAD1 time complexity becomes(17)O(Nit[k2+n2+kn][k2n+NiNg(kn+log⁡⁡Ni)+nNi+n2]).Time Complexity of IGAD2
(i)
Time complexity of extrinsic information computing: The maximal number of competitors of each decision is|Γ|max=n. So, at the last generation of each iteration, the worst-case time complexity of the first step given by (8) is O((k-Ns)max(2n+1,2(n+Ns-k)+3))=O(n(k-Ns)).From (9), the worst-case time complexity of competitors search is is O([Ni-1](n-k+Ns)).From (9) and (10), the time complexity in the worst-case of the second step of extrinsic information calculating is(18)O((n-k+Ns)max⁡(2n+3,2(n+Ns-k)+3,2n+1))=O(n(n-k+Ns)).So the total time complexity of extrinsic information computing isO(comp2(Ni,n,Ns,k)), where(19)comp2(Ni,n,Ns,k)=Ni(n-k+Ns)+n2,(ii)
total time complexity:The total complexity in this case is given from (16):(20)g(k,n,Ni,Ng)=f(k,n,Ni,Ng)+comp2(Ni,n,Ns,k).
For the symmetric 3D-PBCn1=n2=n3=n and k1=k2=k3=k, then the IGAD2 time complexity becomes(21)O(k2Nit[k2+n2+kn]×[k2n+NiNg(kn+log⁡Ni)+Ni(n-k+Ns)+n2]).
It is clear from (17) and (21) that IGAD2 is less complex than IGAD1, and their complexities are equal if Ns=k.


### 4.2.2. Chase-Pyndiah and LBDA Algorithms Time Complexities

We show that this algorithm has an exponential time complexity. LetC(n,k,d) be a BCH code, and let M be the test patterns number used in both Chase and OSD-i (ordered statistic decoding) algorithms. The complexity of each algorithm is O(Mn2log2n).The Euclidian distance computing of each codeword has a computational complexity ofO(n). So, the total time complexity of decoding and computing fitness of the M test patterns is O(Mn2log2n).At any given decoding iteration of the Chase-Pyndiah algorithm, the sorting step of theM fitness has a time complexity of O(Mlog2M) and the the worst-case time complexity of competitors search is O([M-1]n). Thus, the total time complexity of the Chase-Pyndiah algorithm is(22)O(Nit[k2k3F(n1,k1,t1)+k3n1F(n2,k2,t2)+n1n2F(n3,k3,t3)]),
where (23)F(n,k,t)=M[n2log⁡2⁡n+log⁡2⁡M].Thus, in the case ofn1=n2=n3=n, k1=k2=k3=k, and, the exponential time complexity of the two algorithms is(24)O(NitM[n2+k2+kn][log⁡2M+n2log⁡2n]).Note that in the case of Chase-2 algorithm,M=2t,  where   t=⌊(d-1)/2⌋.From (17) and (24), it is shown that IGAD1 and IGAD2 are less complex than the two Chase-Pyndiah and LBDA algorithms for codes with large correction capacity t or for large i parameter or also with great length and low rate.


## 4.2.1. IGADs Time Complexity

If we do not take into consideration the calculating step of the extrinsic information, the two algorithms have the same time complexity. The GAD algorithm for a linear block codeC(n,k) has polynomial time complexity O(f(k,n,Ni,Ng)), where the function f is given by [12](13)f(k,n,Ni,Ng)=k2n+NiNg(kn+log⁡⁡Ni).Time Complexity of IGAD1
(i)
Time complexity of extrinsic information computing: For each decision (row, column, or depth) at the last generation of each iteration, the worst-case time complexity of competitors search isO([Ni-1]n).From (6), the time complexity of extrinsic information calculating in the worst-case (if the competitor exists) at the last generation of each iteration is O(n2). So the total time complexity of extrinsic information computing is O(comp1(Ni,n)), where(14)comp1(Ni,n)=Nin+n2,(ii)
total time complexity:At any iteration of IGAD1, the first elementary decoder has a time complexity ofO(k2k3f(k1,n1,Ni,Ng)), the second decoder has a complexity of O(n1k3f(k2,n2,Ni,Ng)), and the third decoder has a time complexity of O(n1n2f(k3,n3,Ni,Ng)), so the total complexity is polynomial:(15)O(Nit[k2k3g(k1,n1,Ni,Ng)+n1k3g(k2,n2,Ni,Ng)+n1n2g(k3,n3,Ni,Ng)]),
where(16)g(k,n,Ni,Ng)=f(k,n,Ni,Ng)+comp1(Ni,n).
For the symmetric 3D-PBCn1=n2=n3=n and k1=k2=k3=k, then the IGAD1 time complexity becomes(17)O(Nit[k2+n2+kn][k2n+NiNg(kn+log⁡⁡Ni)+nNi+n2]).Time Complexity of IGAD2
(i)
Time complexity of extrinsic information computing: The maximal number of competitors of each decision is|Γ|max=n. So, at the last generation of each iteration, the worst-case time complexity of the first step given by (8) is O((k-Ns)max(2n+1,2(n+Ns-k)+3))=O(n(k-Ns)).From (9), the worst-case time complexity of competitors search is is O([Ni-1](n-k+Ns)).From (9) and (10), the time complexity in the worst-case of the second step of extrinsic information calculating is(18)O((n-k+Ns)max⁡(2n+3,2(n+Ns-k)+3,2n+1))=O(n(n-k+Ns)).So the total time complexity of extrinsic information computing isO(comp2(Ni,n,Ns,k)), where(19)comp2(Ni,n,Ns,k)=Ni(n-k+Ns)+n2,(ii)
total time complexity:The total complexity in this case is given from (16):(20)g(k,n,Ni,Ng)=f(k,n,Ni,Ng)+comp2(Ni,n,Ns,k).
For the symmetric 3D-PBCn1=n2=n3=n and k1=k2=k3=k, then the IGAD2 time complexity becomes(21)O(k2Nit[k2+n2+kn]×[k2n+NiNg(kn+log⁡Ni)+Ni(n-k+Ns)+n2]).
It is clear from (17) and (21) that IGAD2 is less complex than IGAD1, and their complexities are equal if Ns=k.


## 4.2.2. Chase-Pyndiah and LBDA Algorithms Time Complexities

We show that this algorithm has an exponential time complexity. LetC(n,k,d) be a BCH code, and let M be the test patterns number used in both Chase and OSD-i (ordered statistic decoding) algorithms. The complexity of each algorithm is O(Mn2log2n).The Euclidian distance computing of each codeword has a computational complexity ofO(n). So, the total time complexity of decoding and computing fitness of the M test patterns is O(Mn2log2n).At any given decoding iteration of the Chase-Pyndiah algorithm, the sorting step of theM fitness has a time complexity of O(Mlog2M) and the the worst-case time complexity of competitors search is O([M-1]n). Thus, the total time complexity of the Chase-Pyndiah algorithm is(22)O(Nit[k2k3F(n1,k1,t1)+k3n1F(n2,k2,t2)+n1n2F(n3,k3,t3)]),
where (23)F(n,k,t)=M[n2log⁡2⁡n+log⁡2⁡M].Thus, in the case ofn1=n2=n3=n, k1=k2=k3=k, and, the exponential time complexity of the two algorithms is(24)O(NitM[n2+k2+kn][log⁡2M+n2log⁡2n]).Note that in the case of Chase-2 algorithm,M=2t,  where   t=⌊(d-1)/2⌋.From (17) and (24), it is shown that IGAD1 and IGAD2 are less complex than the two Chase-Pyndiah and LBDA algorithms for codes with large correction capacity t or for large i parameter or also with great length and low rate.


## 5. Simulation Results

The figures in this section plot the bit error rate (BER) versus the energy per bit to noise power spectral density ratioEb/N0 for the symmetric 3D-PBC (16, 11, 4)3 and (31, 21, 5)3. The simulation parameters used in IGADs are given in Table 1.Table 1
Simulation default parameters.
Ne1Nit12 for(16,11)3 and 15 for (31,21)3ChannelAWGNModulationBPSKMin. number of transmitted frames100Min. of erroneous frames30


### 5.1. IGAD1 Performances

#### 5.1.1. Scaling Factors Optimization for IGAD1

As the iterations number increases, the extrinsic information gradually becomes more reliable. To take the effect into account, the scaling factorsα are used to reduce the turbo decoder input impact. It has shown that these factors depend on the code and GAD. So, they are optimized step by step for each code. The optimized values α and β for our algorithm are shown in Table 2. However, as the scaling factors α and β are gradually increased or decreased from the optimal values, the decoding performance of IGAD1 decoder decreases. Figure 4 shows the gain with the optimized values of α, for (16, 11, 4)3, compared to the values taken randomly. The values of genetic parameters used are Ng=18,Ni=35,pc=0.97 and pm=0.03.Table 2
Optimized values ofα and β for IGAD1.
Optimized valuesα(θ)(31,21,5)3(0,1,2,3,5,7,9,10,11,15,16,17,19,19,19,15,15,15,19,19,19,17,17,17)·10-2α(θ)=0.2,24≤θ≤44(16,11,4)3Optimizedα(0,6,20,30,30,20,30,23,20,50,20,50,20,30,30,20,33,30,30,30,40,40,40,30,40,30,35,40,40,40,40,32,40,23,30,40)·10-2(16,11,4)3 nonoptimized  α0,0.1,0.01,0.1,0.1,0.02,0.1,0.1,0.03,0.1,0.1,0.05,0.1,0.1,0.07,0.1,0.1,0.09α(θ)=0.1,18≤θ≤35Optimized valuesβ(θ)All codes(0,20,40,60,80)·10-2β(θ)=1,forallθ,θ≥5Figure 4
Effect scaling factor of (16, 11, 4)3 for 12th iterations on IGAD1.


#### 5.1.2. Effect of Evaluated Codewords Number

Generally, increasing the number of evaluated codewordsNiNg, the probability to find the codeword closest to the input sequence becomes high. This makes it possible to improve the BER performances. The effect of increasing the number of evaluated codewords on the BER improvement for code (16, 11, 4)3 at the 12th iteration is presented in Figures 5 and 6. The values Ng=18 and Ni=60 can be the optimal values in a large range Eb/N0. The other genetic parameters for the first optimization are Ni=35,  pc=0.97,  and pm=0.03; Ng=18,  pc=0.97,  and pm=0.03 for the second.Figure 5
Effect of the generation number for (16, 11, 4)3 at 12th iteration on IGAD1.Figure 6
Effect of the population size for (16, 11, 4)3 at 12th iteration on IGAD1.


#### 5.1.3. Cross-Over Rate Effect

Since the cross-over rate is one of the important features of a genetic algorithm, an optimization of this probability is necessary. Figure7 shows the optimized value pc=0.97 for (16, 11, 4)3   3D-PBC which improves the BER at a rather high SNR and at 12th iteration. This value closing to 1 means that IGAD1 requires a broad exploration and efficient exploitation, but increases somewhat the algorithm complexity. Indeed, when pc is close to 0, the crossover operation will occur rarely. For this simulation, we fixed the other parameters as follows: Ng=18,  Ni=60, and pm=0.03.Figure 7
Effect of the crossover probability for (16, 11, 4)3 at 12th iteration on IGAD1.


#### 5.1.4. Mutation Rate Effect

The effect of mutation rate on IGAD1 forBCH (16, 11, 4)3   3D-PBC is depicted in Figure 8. it is shown that pm=0.05 is the optimal value for BER at a high SNR and at 12th iteration. One reason of this value close to 0 may be the stability of members in vicinity of optima for low mutation rates. The fixed values are Ng=18,  Ni=60, and pc=0.97.Figure 8
Effect of the mutation rate for (16, 11, 4)3  3D-PBC at 12th iteration on IGAD1.


#### 5.1.5. Code Rate Effect

The Figure9 shows the improvement/degradation of the BER performance of IGAD1 at the 12th and 15ths, iteration respectively, with decreasing/increasing the code dimension or code rate. The rate 0.31 of (31, 21, 4)3 is less than that of (16, 11, 4)3 which equals to 0.32. This explains the better performances for the first 3D-PBC code in the range Eb/N0≥2.5 dB. In this simulation, we adopted the optimal values previously found: Ng=18,  Ni=60,  pc=0.97,  and pm=0.03.Figure 9
IGAD1 performances forBCH  (16, 11, 4)3 and BCH  (31, 21, 4)3  3D-PBC PBC at 12th iteration.


#### 5.1.6. Comparison between IGAD1 and IGAD2

As the iteration number increases, the IGADs performances improve approximately in this paper in the wholeEb/N0 range for all 3D-PBC studied. The performances of the IGAD decoders is depicted in Figure 10 for BCH (16, 11, 4)3   3D-PBC. These performances can be improved by increasing the total number of members as shown in Figure 6. The IGAD1 and IGAD2 performances are respectively about 1.4 dB and 1.33 dB away from the Shannon capacity limit, which is 0.97 dB for this code. We used the following optimized parameters: Ng=18,  Ni=60,  pc=0.97, and pm=0.05.Figure 10
BER of IGAD1 and IGAD2 of (16, 11, 4)3 for 12 iteration (Ns=8).


## 5.1. IGAD1 Performances

### 5.1.1. Scaling Factors Optimization for IGAD1

As the iterations number increases, the extrinsic information gradually becomes more reliable. To take the effect into account, the scaling factorsα are used to reduce the turbo decoder input impact. It has shown that these factors depend on the code and GAD. So, they are optimized step by step for each code. The optimized values α and β for our algorithm are shown in Table 2. However, as the scaling factors α and β are gradually increased or decreased from the optimal values, the decoding performance of IGAD1 decoder decreases. Figure 4 shows the gain with the optimized values of α, for (16, 11, 4)3, compared to the values taken randomly. The values of genetic parameters used are Ng=18,Ni=35,pc=0.97 and pm=0.03.Table 2
Optimized values ofα and β for IGAD1.
Optimized valuesα(θ)(31,21,5)3(0,1,2,3,5,7,9,10,11,15,16,17,19,19,19,15,15,15,19,19,19,17,17,17)·10-2α(θ)=0.2,24≤θ≤44(16,11,4)3Optimizedα(0,6,20,30,30,20,30,23,20,50,20,50,20,30,30,20,33,30,30,30,40,40,40,30,40,30,35,40,40,40,40,32,40,23,30,40)·10-2(16,11,4)3 nonoptimized  α0,0.1,0.01,0.1,0.1,0.02,0.1,0.1,0.03,0.1,0.1,0.05,0.1,0.1,0.07,0.1,0.1,0.09α(θ)=0.1,18≤θ≤35Optimized valuesβ(θ)All codes(0,20,40,60,80)·10-2β(θ)=1,forallθ,θ≥5Figure 4
Effect scaling factor of (16, 11, 4)3 for 12th iterations on IGAD1.


### 5.1.2. Effect of Evaluated Codewords Number

Generally, increasing the number of evaluated codewordsNiNg, the probability to find the codeword closest to the input sequence becomes high. This makes it possible to improve the BER performances. The effect of increasing the number of evaluated codewords on the BER improvement for code (16, 11, 4)3 at the 12th iteration is presented in Figures 5 and 6. The values Ng=18 and Ni=60 can be the optimal values in a large range Eb/N0. The other genetic parameters for the first optimization are Ni=35,  pc=0.97,  and pm=0.03; Ng=18,  pc=0.97,  and pm=0.03 for the second.Figure 5
Effect of the generation number for (16, 11, 4)3 at 12th iteration on IGAD1.Figure 6
Effect of the population size for (16, 11, 4)3 at 12th iteration on IGAD1.


### 5.1.3. Cross-Over Rate Effect

Since the cross-over rate is one of the important features of a genetic algorithm, an optimization of this probability is necessary. Figure7 shows the optimized value pc=0.97 for (16, 11, 4)3   3D-PBC which improves the BER at a rather high SNR and at 12th iteration. This value closing to 1 means that IGAD1 requires a broad exploration and efficient exploitation, but increases somewhat the algorithm complexity. Indeed, when pc is close to 0, the crossover operation will occur rarely. For this simulation, we fixed the other parameters as follows: Ng=18,  Ni=60, and pm=0.03.Figure 7
Effect of the crossover probability for (16, 11, 4)3 at 12th iteration on IGAD1.


### 5.1.4. Mutation Rate Effect

The effect of mutation rate on IGAD1 forBCH (16, 11, 4)3   3D-PBC is depicted in Figure 8. it is shown that pm=0.05 is the optimal value for BER at a high SNR and at 12th iteration. One reason of this value close to 0 may be the stability of members in vicinity of optima for low mutation rates. The fixed values are Ng=18,  Ni=60, and pc=0.97.Figure 8
Effect of the mutation rate for (16, 11, 4)3  3D-PBC at 12th iteration on IGAD1.


### 5.1.5. Code Rate Effect

The Figure9 shows the improvement/degradation of the BER performance of IGAD1 at the 12th and 15ths, iteration respectively, with decreasing/increasing the code dimension or code rate. The rate 0.31 of (31, 21, 4)3 is less than that of (16, 11, 4)3 which equals to 0.32. This explains the better performances for the first 3D-PBC code in the range Eb/N0≥2.5 dB. In this simulation, we adopted the optimal values previously found: Ng=18,  Ni=60,  pc=0.97,  and pm=0.03.Figure 9
IGAD1 performances forBCH  (16, 11, 4)3 and BCH  (31, 21, 4)3  3D-PBC PBC at 12th iteration.


### 5.1.6. Comparison between IGAD1 and IGAD2

As the iteration number increases, the IGADs performances improve approximately in this paper in the wholeEb/N0 range for all 3D-PBC studied. The performances of the IGAD decoders is depicted in Figure 10 for BCH (16, 11, 4)3   3D-PBC. These performances can be improved by increasing the total number of members as shown in Figure 6. The IGAD1 and IGAD2 performances are respectively about 1.4 dB and 1.33 dB away from the Shannon capacity limit, which is 0.97 dB for this code. We used the following optimized parameters: Ng=18,  Ni=60,  pc=0.97, and pm=0.05.Figure 10
BER of IGAD1 and IGAD2 of (16, 11, 4)3 for 12 iteration (Ns=8).


## 5.1.1. Scaling Factors Optimization for IGAD1

As the iterations number increases, the extrinsic information gradually becomes more reliable. To take the effect into account, the scaling factorsα are used to reduce the turbo decoder input impact. It has shown that these factors depend on the code and GAD. So, they are optimized step by step for each code. The optimized values α and β for our algorithm are shown in Table 2. However, as the scaling factors α and β are gradually increased or decreased from the optimal values, the decoding performance of IGAD1 decoder decreases. Figure 4 shows the gain with the optimized values of α, for (16, 11, 4)3, compared to the values taken randomly. The values of genetic parameters used are Ng=18,Ni=35,pc=0.97 and pm=0.03.Table 2
Optimized values ofα and β for IGAD1.
Optimized valuesα(θ)(31,21,5)3(0,1,2,3,5,7,9,10,11,15,16,17,19,19,19,15,15,15,19,19,19,17,17,17)·10-2α(θ)=0.2,24≤θ≤44(16,11,4)3Optimizedα(0,6,20,30,30,20,30,23,20,50,20,50,20,30,30,20,33,30,30,30,40,40,40,30,40,30,35,40,40,40,40,32,40,23,30,40)·10-2(16,11,4)3 nonoptimized  α0,0.1,0.01,0.1,0.1,0.02,0.1,0.1,0.03,0.1,0.1,0.05,0.1,0.1,0.07,0.1,0.1,0.09α(θ)=0.1,18≤θ≤35Optimized valuesβ(θ)All codes(0,20,40,60,80)·10-2β(θ)=1,forallθ,θ≥5Figure 4
Effect scaling factor of (16, 11, 4)3 for 12th iterations on IGAD1.


## 5.1.2. Effect of Evaluated Codewords Number

Generally, increasing the number of evaluated codewordsNiNg, the probability to find the codeword closest to the input sequence becomes high. This makes it possible to improve the BER performances. The effect of increasing the number of evaluated codewords on the BER improvement for code (16, 11, 4)3 at the 12th iteration is presented in Figures 5 and 6. The values Ng=18 and Ni=60 can be the optimal values in a large range Eb/N0. The other genetic parameters for the first optimization are Ni=35,  pc=0.97,  and pm=0.03; Ng=18,  pc=0.97,  and pm=0.03 for the second.Figure 5
Effect of the generation number for (16, 11, 4)3 at 12th iteration on IGAD1.Figure 6
Effect of the population size for (16, 11, 4)3 at 12th iteration on IGAD1.


## 5.1.3. Cross-Over Rate Effect

Since the cross-over rate is one of the important features of a genetic algorithm, an optimization of this probability is necessary. Figure7 shows the optimized value pc=0.97 for (16, 11, 4)3   3D-PBC which improves the BER at a rather high SNR and at 12th iteration. This value closing to 1 means that IGAD1 requires a broad exploration and efficient exploitation, but increases somewhat the algorithm complexity. Indeed, when pc is close to 0, the crossover operation will occur rarely. For this simulation, we fixed the other parameters as follows: Ng=18,  Ni=60, and pm=0.03.Figure 7
Effect of the crossover probability for (16, 11, 4)3 at 12th iteration on IGAD1.


## 5.1.4. Mutation Rate Effect

The effect of mutation rate on IGAD1 forBCH (16, 11, 4)3   3D-PBC is depicted in Figure 8. it is shown that pm=0.05 is the optimal value for BER at a high SNR and at 12th iteration. One reason of this value close to 0 may be the stability of members in vicinity of optima for low mutation rates. The fixed values are Ng=18,  Ni=60, and pc=0.97.Figure 8
Effect of the mutation rate for (16, 11, 4)3  3D-PBC at 12th iteration on IGAD1.


## 5.1.5. Code Rate Effect

The Figure9 shows the improvement/degradation of the BER performance of IGAD1 at the 12th and 15ths, iteration respectively, with decreasing/increasing the code dimension or code rate. The rate 0.31 of (31, 21, 4)3 is less than that of (16, 11, 4)3 which equals to 0.32. This explains the better performances for the first 3D-PBC code in the range Eb/N0≥2.5 dB. In this simulation, we adopted the optimal values previously found: Ng=18,  Ni=60,  pc=0.97,  and pm=0.03.Figure 9
IGAD1 performances forBCH  (16, 11, 4)3 and BCH  (31, 21, 4)3  3D-PBC PBC at 12th iteration.


## 5.1.6. Comparison between IGAD1 and IGAD2

As the iteration number increases, the IGADs performances improve approximately in this paper in the wholeEb/N0 range for all 3D-PBC studied. The performances of the IGAD decoders is depicted in Figure 10 for BCH (16, 11, 4)3   3D-PBC. These performances can be improved by increasing the total number of members as shown in Figure 6. The IGAD1 and IGAD2 performances are respectively about 1.4 dB and 1.33 dB away from the Shannon capacity limit, which is 0.97 dB for this code. We used the following optimized parameters: Ng=18,  Ni=60,  pc=0.97, and pm=0.05.Figure 10
BER of IGAD1 and IGAD2 of (16, 11, 4)3 for 12 iteration (Ns=8).


## 6. Conclusion

In this paper, we have presented two iterative decoding algorithms which can be applied to any arbitrary 3D-product block codes based on a genetic algorithm, without the need of a hard-in hard-out decoder. Our theoretical results show that these algorithms reduce the decoding complexity, for codes with a low rate and large correction capacityt or large i parameter used in LBDA algorithm. Furthermore, the performances of these algorithms can be improved by using asymmetric 3D-PBC codes and also, by tuning some parameters like the selection method, the crossover/mutation rates, the population size, the number of generations, and the iterations number. These algorithms can be applied again on multipath fading channels in both CDMA systems and systems without spread-spectrum. Those features open broad prospects for decoders based on artificial intelligence.



---

*Source: 609650-2012-04-29.xml*