Document Type
Report
Date
7-1996
Keywords
block codes, soft-decision, decoding, code tree, graph-search, BCH code
Language
English
Disciplines
Computer Sciences
Description/Abstract
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.
Recommended Citation
Shih, Ching-Cheng; Wulff, C. R.; Hartmann, Carlos R.P.; and Mohan, Chilukuri K., "Efficient Heuristic Search Algorithms for Soft-Decision Decoding of Linear Block Codes" (1996). Electrical Engineering and Computer Science - Technical Reports. 147.
https://surface.syr.edu/eecs_techreports/147
Source
local
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