Majority Voting Procedure Allowing Soft Decision Decoding of Linear Block Codes on Binary Channels

Saïd Nouh, Achraf El Khatabi, Mostafa Belkasmi

SIME Lab, National School of Computer Science and Systems Analysis (ENSIAS), Mohammed V Souissi University, Rabat, Morocco.

DOI: 10.4236/ijcns.2012.59066                

Abstract

In this paper we present an efficient algorithm to decode linear block codes on binary channels. The main idea consists in using a vote procedure in order to elaborate artificial reliabilities of the binary received word and to present the obtained real vector r as inputs of a SIHO decoder (Soft In/Hard Out). The goal of the latter is to try to find the closest codeword to r in terms of the Euclidean distance. A comparison of the proposed algorithm over the AWGN channel with the Majority logic decoder, Berlekamp-Massey, Bit Flipping, Hartman-Rudolf algorithms and others show that it is more efficient in terms of performance. The complexity of the proposed decoder depends on the weight of the error to decode, on the code structure and also on the used SIHO decoder.

Keywords

Error Correcting Codes; Genetic Algorithms; HIHO Decoder; SIHO Decoder; Vote Procedure

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	G. C. Clarck and J. B. Cain, “Error-Correction Coding for Digital Communication,” Plenum, New York, 1981.
[2]	S. Nouh and M. Belkasmi “Genetic Algorithms for Finding the Weight Enumerator of Binary Linear Block Codes,” International Journal of Applied Research on Information Technology and Computing, Vol. 2, No. 3, 2011, pp. 80-93.
[3]	D. Chase, “A Class of Algorithms for Decoding Block Codes with Channel Measurement Information,” IEEE Transactions on Information Theory, Vol. 18, No. 1, 1972, pp. 170-181. doi:10.1109/TIT.1972.1054746
[4]	J. L. Massey, “Shift-Register Synthesis and BCH Decoding,” IEEE Transaction on Information Theory, Vol. 15, No. 1, 1969, pp. 122-127.
[5]	E. R. Berlekamp, “Algebraic Coding Theory,” Aegean Park Press, Walnut Creek, 1984.
[6]	F. J. MacWilliams, “Permutation Decoding of Systematic Codes,” The Bell System Technical Journal, Vol. 63, No. 1, 1964, pp. 485-505.
[7]	S. Nouh, M. Askali and M. Belkasmi, “Efficient Genetic Algorithms for Helping the Permutation Decoding Algorithm,” International Conference on Intelligent Systems, Mohammedia, 16-17 May 2012.
[8]	R. G. Gallager, “Low-Density Parity-Check Codes,” IRE Transactions on Information. Theory, Vol. 8, No. 1, 1962, pp. 21-28. doi:10.1109/TIT.1962.1057683
[9]	R. H. Morelos-Zaragoza, “The Art of Error Correcting Coding,” 2nd Edition, John Wiley & Sons, Hoboken, 2006.
[10]	Azouaoui, I. Chana and M. Belkasmi “Efficient Information Set Decoding Based on Genetic Algorithms,” International Journal of Communications, Network and System Sciences, Vol. 5, No. 7, 2012, pp. 423-429.
[11]	R. Sujan, et al., “Adaptive ‘Soft’ Sliding Block Decoding of Convolutional Code Using the Artificial Neural Net-Work,” Transactions on Emerging Telecommunications Technologies, 2012.
[12]	M. Sayed, “Coset Decomposition Method for Decoding Linear Codes,” International Journal of Algebra, Vol. 5, No. 28, 2011, pp. 1395-1404.
[13]	M. Kerner and O. Amrani, “Iterative Decoding Using Optimum Soft Input—Hard Output Module,” IEEE Transactions on Communications, Vol. 57, No. 7, 2009, pp. 1881-1885. doi:10.1109/TCOMM.2009.07.070167
[14]	B. Cristea, “Viterbi Algorithm for Iterative Decoding of Parallel Concatenated Convolutional Codes,” Proceedings of 18th European Signal Processing Conference, Aalborg, 23-27 August 2010.
[15]	C. R. P. Hartmann and L. D. Rudolph, “An Optimum Symbol-by-Symbol Decoding Rule for Linear Codes,” IEEE Transactions on Information Theory, Vol. 22, No. 5, 2009, pp. 514-517.
[16]	D. E. Goldberg, “Genetic Algorithms in Search, Optimization and Machine Learning,” Addison Wesley, Reading, 1989.
[17]	J. McCall, “Genetic Algorithms for Modelling and Optimizationm” Journal of Computational and Applied Mathematics, Vol. 184, No. 1, 2005, pp. 205-222. doi:10.1016/j.cam.2004.07.034
[18]	H. Maini, K. Mehrotra, C. Mohan and S. Ranka, “Soft Decision Decoding of Linear Block Codes Using Genetic Algorithms,” IEEE International Symposium on Information Theory, Trondheim, 27 June-1 July 1994.
[19]	M. P. C. Fossorier and S. Lin, “Soft Decision Decoding of Linear Block Codes Based on Ordered Statistics,” IEEE Transactions on Information Theory, Vol. 41, No. 5, 1995, pp. 1379-1396. doi:10.1109/18.412683
[20]	J. S. Yedidia, J. Chen and M. Fossorier, “Generating Code Representations Suitable for Belief Propagation Decoding,” Tech. Report TR-2002-40, Mitsubishi Electric Re- search Laboratories, Broadway, 2002.
[21]	J. S. Yedidia, J. Chen and M. Fossorier, “Representing Codes for Belief Propagation Decoding,” Proceedings of IEEE International Symposium on Information Theory, Yokohama, 29 June-4 July 2003, p. 176.
[22]	A. Azouaoui, M. Askali and M. Belkasmi, “A Genetic Algorithm to Search of Good Double-Circulant Codes,” IEEE International Conference on Multimedia Computing and Systems Proceeding, Ouarzazate, 7-9 April 2011, pp. 829-833.
[23]	J. L. Massey, “Threshold Decoding,” M.I.T. Press, Cambridge, 1963.