Efficient heuristic search algorithms for soft-decision decoding of linear block codes

Ching Cheng Shih, Christopher R. Wulff, Carlos R.P. Hartmann, Chilukuri K. Mohan

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


Efficient new algorithms are presented for maximum-likelihood and suboptimal soft-decision decoding algorithms for linear block codes. The first algorithm, MA*, improves the efficiency of the A* decoding algorithm [14], conducting heuristic search through a code tree while exploiting code-specific properties. The second algorithm, H*, reduces search space by successively estimating the cost of the minimum-cost codeword with a fixed value at each of the most reliable and linearly independent components of the received message. The third algorithm, Directed Search, finds the codeword closest to the received vector by exploring a continuous search space. The strengths of these three algorithms are combined in a hybrid algorithm, applied to the (128, 64), the (256, 131), and the (256, 139) binary-extended Bose-Chaudhuri-Hocquenghem (BCH) codes. Simulation results show that this hybrid algorithm can efficiently decode the (128, 64) code for any signal-to-noise ratio, with near-optimal performance. Previously, no practical decoder could have decoded this code with such a performance for all ranges of signal-to-noise ratio.

Original languageEnglish (US)
Pages (from-to)3023-3038
Number of pages16
JournalIEEE Transactions on Information Theory
Issue number7
StatePublished - 1998
Externally publishedYes


  • BCH code
  • Block codes
  • Code tree
  • Decoding
  • Graph-search
  • Linear codes
  • Soft-decision

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences


Dive into the research topics of 'Efficient heuristic search algorithms for soft-decision decoding of linear block codes'. Together they form a unique fingerprint.

Cite this