Early-elimination modification for priority-first search decoding

Shin Lin Shieh*, Po-Ning Chen, Yunghsiang S. Han, Ting Yi Wu

*Corresponding author for this work

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

In order to release the growing demand for computational complexity with respect to increasing information sequence length in the priority-first search decoding algorithm, a path elimination modification is proposed and also analyzed in this work. Specifically, we propose to directly eliminate all paths whose end nodes are -level prior to the farthest node among those that have been visited thus far by the priority-first search. Following the argument on random coding, we then analyze the path elimination window that results in a larger exponent for additional decoding error caused by path elimination than the exponent of the maximum-likelihood error performance, and hence guarantees exponentially negligible performance degradation. Our analytical results indicate that under additive white Gaussian noise (AWGN) channels, the path elimination window required for exponentially negligible performance degradation is just three times the code constraint length for rate one-half convolutional codes. It can be further reduced to 1.7-fold of the code constraint length when rate one-third convolutional codes are considered instead. Simulation results confirm these analytical window sizes. As a consequence, the priority-first search decoding algorithm can considerably reduce its computation burden and memory consumption by directly eliminating a large number of paths with nearly no performance degradation. This makes the priority-first search decoding algorithm with path elimination suitable for applications that demand low-complexity software implementation with near optimal performance.

Original languageEnglish
Article number5610972
Pages (from-to)3459-3469
Number of pages11
JournalIEEE Transactions on Communications
Volume58
Issue number12
DOIs
StatePublished - 1 Dec 2010

Keywords

  • Priority-first search decoding
  • maximum-likelihood
  • random coding
  • soft-decision

Fingerprint Dive into the research topics of 'Early-elimination modification for priority-first search decoding'. Together they form a unique fingerprint.

  • Cite this