Document Type




Embargo Period



block codes, soft-decision, decoding, code tree, graph-search, BCH code




Computer Sciences


This paper deals with maximum-likelihood soft-decision decoding as well as suboptimal soft-decision decoding of linear block codes. In this paper we present a novel and efficient hybrid decoding algorithm for (n, k) linear block codes. This algorithm consists of three new decoding algorithms: M A*, H*, and Directed Search. It hybridizes these three algorithms to take advantage of their strengths and make the decoding more efficient. The first algorithm, M A*, is a modified Algorithm A* that conducts a heuristic search through a code tree of the transmitted code when the decoding problem is transformed into a problem of graph-search through a code tree. M A* takes into consideration more properties of the code and is considerably more efficient than the original A* algorithm presented by Han, Hartmann, and Chen. The second algorithm, H*, is a new decoding algorithm that determines the value of every component of a minimum-cost codeword by estimating the cost of the minimum-cost codeword, which has a fixed value at one of the k most reliable, linearly independent bit positions when the decoding problem is transformed into a minimum-cost problem among all codewords of the transmitted code. The suboptimal version of this algorithm can be incorporated with other decoding algorithms to reduce the search space during the decoding process. The third algorithm, Directed Search, is a novel heuristic approach designed to enhance the performance of soft-decision decoding by searching in continuous space. This approach explores the search space between a given vector and the received vector and finds the closest codeword to the received vector in the space explored. Simulation results for this hybrid algorithm are presented for the (128, 64), the (256, 131 ), and the (256, 139) binary-extended BCH codes. This hybrid algorithm can efficiently decode the (128, 64) code for any signal-to-noise ratio and has near-optimal to optimal performance. Previously, no practical decoder could have decoded this code with such a performance for all ranges of signal-to-noise ratio.

Additional Information

School of Computer and Information Science, Syracuse University, SU-CIS-96-03

Authors later published: Ching-Cheng Shih, Wulff, C. R., Hartmann, C. R. P., & Mohan, C. K. (1998). Efficient heuristic search algorithms for soft-decision decoding of linear block codes. IEEE Transactions on Information Theory, 44(7), 3023-3038. Institute of Electrical and Electronics Engineers. doi:10.1109/18.737530





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.