Early-elimination modification for priority-first search decoding

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

研究成果: Conference article同行評審


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. ?c 2010 IEEE.

頁(從 - 到)3436-3447
期刊IEEE Workshop on Local and Metropolitan Area Networks
出版狀態Published - 1 1月 1993
事件6th IEEE Workshop on Local and Metropolitan Area Networks, LANMAN 1993 - San Diego, United States
持續時間: 14 10月 199616 10月 1996


深入研究「Early-elimination modification for priority-first search decoding」主題。共同形成了獨特的指紋。