Document Type




Embargo Period







Computer Sciences


In this report we present a class of efficient maximum-likelihood soft-decision decoding algorithms for linear block 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 uses a priority-first search strategy, is employed 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 this decoding algorithm adaptable to the noise level. For example, simulation results for the (128,64) binary extended BCH code indicate that for most real channels the proposed decoding algorithm is at least fifteen orders of magnitude more efficient in time and in space than that proposed by Wolf. Simulation results for the (104, 52) binary extended quadratic residue code are also given. These simulation results indicate that the use of Algorithm A* for decoding has resulted not only in an efficient soft-decision decoding algorithm for hitherto intractable linear block codes, but an algorithm which is in fact optimal as well.

Additional Information

School of Computer and Information Science, Syracuse University, SU-CIS-92-10





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.