A Tree Search Approach for Maximum-Likelihood Decoding of Reed-Muller Codes

Seyyed Ali Hashemi, Nghia Doan, Warren J. Gross, John Cioffi, Andrea Goldsmith

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

A low-complexity tree search approach is presented that is equivalent to the maximum-likelihood (ML) decoding of Reed-Muller (RM) codes. The proposed approach generates a bit-flipping tree that is traversed to find the ML decoding result by performing successive-cancellation decoding after each node visit. A depth-first search (DFS) and a breadth-first search (BFS) scheme are developed and a log-likelihood-ratio-based bit-flipping metric is utilized to avoid redundant node visits in the tree. Several enhancements to the proposed algorithm are presented to further reduce the number of node visits. Simulation results confirm that the BFS scheme provides a lower average number of node visits than the existing tree search approach to decode RM codes.

Original languageEnglish (US)
Title of host publication2021 IEEE Globecom Workshops, GC Wkshps 2021 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
ISBN (Electronic)9781665423908
DOIs
StatePublished - 2021
Event2021 IEEE Globecom Workshops, GC Wkshps 2021 - Madrid, Spain
Duration: Dec 7 2021Dec 11 2021

Publication series

Name2021 IEEE Globecom Workshops, GC Wkshps 2021 - Proceedings

Conference

Conference2021 IEEE Globecom Workshops, GC Wkshps 2021
Country/TerritorySpain
CityMadrid
Period12/7/2112/11/21

All Science Journal Classification (ASJC) codes

  • Information Systems
  • Signal Processing
  • Software
  • Information Systems and Management
  • Artificial Intelligence
  • Computer Networks and Communications

Fingerprint

Dive into the research topics of 'A Tree Search Approach for Maximum-Likelihood Decoding of Reed-Muller Codes'. Together they form a unique fingerprint.

Cite this