This project aims to develop new efficient maximum-likelihood soft-decision decoding algorithms for linear block codes and convolutional codes. The approach used here is to convert the decoding problem into a search problem through a graph which is a trellis for an equivalent code of the transmitted code. Algorithm A*, which is widely used in Artificial Intelligence search problems, is used to search through this graph. This search is guided by an evaluation function f defined to take advantage of the information provided by the received vector and the inherent properties of the transmitted code. This function f is used to drastically reduce the search space and to make the decoding efforts of these decoding algorithms adaptable to the noise level. Preliminary results indicate a possible breakthrough in the decoding of linear block codes. Successful application to convolutional codes should make possible the use of maximum-likelihood soft-decision decoders for large constraint length convolutional codes in practical communications systems.
