Title

Genetic Algorithms for Soft Decision Decoding of Linear Block Codes

Author(s)/Creator(s)

Harpal Maini, Syracuse UniversityFollow
Kishan Mehrotra, Syracuse UniversityFollow
Chilukuri K. Mohan, Syracuse UniversityFollow
Sanjay Ranka, Syracuse University

Document Type

Report

Date

11-23-1993

Keywords

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

Language

English

Disciplines

Computer Sciences

Description/Abstract

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 http://dx.doi.org/10.1162/evco.1994.2.2.145

Recommended Citation

Maini, Harpal; Mehrotra, Kishan; Mohan, Chilukuri K.; and Ranka, Sanjay, "Genetic Algorithms for Soft Decision Decoding of Linear Block Codes" (1993). Electrical Engineering and Computer Science - Technical Reports. 161.
https://surface.syr.edu/eecs_techreports/161

Source

local