Parallel Genetic Algorithm Decoder Based on Multi-Criteria Method for Low Density Parity Check Codes

Hasna Chaibi

doi:10.15866/irecos.v10i8.7241

Parallel Genetic Algorithm Decoder Based on Multi-Criteria Method for Low Density Parity Check Codes

Hasna Chaibi^(1*)

^(*) Corresponding author

Authors' affiliations

DOI: https://doi.org/10.15866/irecos.v10i8.7241

Abstract

Genetic algorithms are successfully used for decoding some classes of error correcting codes, and to give very good performances when solving large optimization problems. This article proposes a decoder based on parallel Genetic Algorithms (PGAD) for Decoding Low Density Parity Check (LDPC) codes. The proposed algorithm gives large gains over the Sum-Product decoder, which proves its efficiency; the best performances are obtained for Ring Crossover (RC) as a type of crossover and the tournament as a type of selection. Furthermore, the performances of the new decoder are improved using Multi-criteria method, this new optimized version called (PGAWS).Simulation results show that our proposed PGAD exceeds the sum-product performance by a gain of 1.5 dB at BER = 10-4, and the PGAWS exceeds the sum-product performance by 2.5 dB.

Keywords

Parallel Genetic Algorithms Decoder; Fitness Function; Sum-Product Decoder; LDPC Codes; Multi-Criteria Method; Weighted Sum Method; Error Correcting Codes

Full Text:

PDF

References

http://spectrum.ieee.org/consumer-electronics/standards/

R. G. Gallager, Low-Density Parity-Check Codes. The MIT Press, Sep. 1963.
http://dx.doi.org/10.1109/tit.1964.1053651

T. K. Moon, Error Correcting Coding: Mathematical Methods and Algorithms. New York: Wiley, 2005.
http://dx.doi.org/10.1002/0471739219

T. Richardson, A. Shokrollahi and R. Urbanke, “Design of capacity approaching irregular Low-Density Parity-Check codes,” IEEE Trans. Inform.Theory, 47,619-637, 2001.
http://dx.doi.org/10.1109/18.910578

T. Richardson, and R. Urbanke, “The capacity of Low-Density Parity-Check codes under message-passing decoding,” IEEE Trans. Inform. Theory, 47,599-618, 2001.
http://dx.doi.org/10.1109/18.910577

D.J.C. MacKay, “Good error-correcting codes based on very sparse matrices” IEEE Trans. Inform. Theory, 45,399-431, (1999).
http://dx.doi.org/10.1109/18.748992

D.J.C MacKay, and R.M. Neal, “Near Shannon Limit Performance of Low-Density Parity-check Codes” IEE Elect. Lett., 33, 457-458, (1997).
http://dx.doi.org/10.1049/el:19970362

H. Wymeersch, H. Steendam et M. Moeneclaey, "Log-domain decoding of LDPC codes over GF(q)",IEEE Communications Society, vol. 45(2), pp. 399-431,2004.
http://dx.doi.org/10.1109/icc.2004.1312606

H. Berbia, F. Elbouanani, R. Romadi, M. Belkasmi, “Metaheuristic Algorithms for Decoding Binary Linear Codes”, World Academy of Science, Engineering and Technology Vol:5 2011-04-29.

R. Murphy “A Generic Parallel Genetic Algorithm”, Thesis submitted to The University of Dublin for the degree of M.Sc. in High Performance Computing, Department of Mathematics University of Dublin, Trinity College, October 2003.

C. Pettey, M. Leuze, J. Grefenstette, "A parallel genetic algorithm," In Proceedings of the Second International Conference on Genetic Algorithms, pp. 155-161, , Los Altos, CA, 1987.

D. E. Goldberg, "Sizing populations for serial and parallel genetic algorithms," in Proceedings of the Third International Conference on Genetic Algorithms, pp. 70-79, San Mateo, CA, 1989.

H. Mühlenbein, "Parallel genetic algorithms, population genetics and combinatorial optimization," Proceedings of the Third International Conference on Genetic Algorithms, pp. 416-421, San Mateo, CA, 1989.

E. C.Paz, "A Survey of Parallel Genetic Algorithms," Calculateurs Paralleles, Reseaux et Systems Repartis, v10, pp. 141-171, 1998.

S. Tongchim, “Coarse-Grained Parallel Genetic Algorithm for Solving the Timetable Problem”, Proc. of the 3 rd Annual Nat.Symp.on Computational Science and Engineering. Bangkok, Thailand, 1999

J. Vahidi, S. Saeed MirpourMarzuni , S. Farzai, “Comparing performance of parallel grouping genetic algorithm with serial grouping genetic algorithm for clustering problems” in International Journal of Mechatronics, Electrical and Computer Technology, Vol. 5(15) Apr. 2015, PP. 2198-2206

Y. Kaya, M. Uyar, and R. Tekin, “A Novel Crossover Operator for Genetic Algorithms: Ring Crossover,” presented at CoRR, 2011.

J.C. Vansnick, “Measurement theory and decision aid”, in Banae Costa (ed.), Readings in Multiple Criteria Decision Aid, Springer-Verlog, Berlin, 81-100.
http://dx.doi.org/10.1007/978-3-642-75935-2_5

I.Y Kim, O.L Weck, “adaptive Weighted Sum Method for Multiobjective Optimization.” A/AA, 2004-4322, 2009.
http://dx.doi.org/10.2514/6.2004-4322

I. Das, and J. E., Dennis, “A closer look at drawbacks of minimizing weighted sums of objectives for Pareto set generation in multicriteria optimization problems,” Structural Optimization, Vol. 14, 1997, pp. 63-69. 15.
http://dx.doi.org/10.1007/bf01197559

Sahraeian, R., Zamani, B., Akbari, A., Ayatollahi, A., Eigenspace-based MLLR adaptation using MCE, (2010) International Review on Computers and Software (IRECOS), 5 (6), pp. 628-634.

Refbacks

There are currently no refbacks.

Username
Password
Remember me