Document Type





genetic algorithms, soft-decision decoding, uniform crossover, Walsh polynomials




Computer Sciences


Soft-decision decoding is an NP-hard problem of great interest to developers of communication systems. We show that this problem is equivalent to the problem of optimizing Walsh polynomials. We present genetic algorithms for soft-decision decoding of binary linear block codes and compare the performance with various other decoding algorithms. Simulation results show that our algorithms achieve bit-error-probabilities as low as 0.00183 for a [104, 52] code with a low signal-to-noise ratio of 2.5 dB, exploring only 30,000 codewords, whereas the search space contains 4.5 x 1015 codewords. We define a new crossover operator that exploits domain-specific information and compare it with uniform and two point crossover. We also give a schema theorem for our genetic algorithm, showing that high reliability, low order codewords are the building blocks for the evolutionary process.

Additional Information

School of Computer and Information Science, Syracuse University, SU-CIS-93-25

Authors later published: Harpal Maini, Kishan Mehrotra, Chilukuri Mohan, and Sanjay Ranka. 1994. Genetic algorithms for soft-decision decoding of linear block codes. Evol. Comput. 2, 2 (June 1994), 145-164. DOI=10.1162/evco.1994.2.2.145





To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.