TY - GEN

T1 - Reduction of computational complexity and sufficient stack size of the MLSDA by early elimination

AU - Shieh, Shin Lin

AU - Chen, Po-Ning

AU - Han, Yunghsiang S.

PY - 2007/12/1

Y1 - 2007/12/1

N2 - In this work, we revisited the priority-first sequential-search decoding algorithm proposed in [5]. By adopting a new metric other than the conventional Fano one, the sequential-search decoding in [5] guarantees the maximum-likelihood (ML) performance, and hence, was named the maximum-likelihood sequential decoding algorithm (MLSDA). In comparison with the other maximum-likelihood decoders, it was shown in [5] that the software computational complexity of the MLSDA is in general markedly smaller than that of the Viterbi algorithm. A common problem on sequential-type decoding is that at the signal-to-noise ratio (SNR) below the one corresponding to the cutoff rate, the average decoding complexity per information bit and the required stack size grow rapidly with the information length [7]. This problem somehow prohibits the practical use of sequential-type decoding on convolutional codes with long information sequence at low SNRs. In order to alleviate the problem in the MLSDA, we propose in this work to directly eliminate the top path whose end node is Δ-trellis-level prior to the farthest one among all nodes that have been expanded thus far by the sequential search, which we termed the early elimination. Simulations show that a level threshold Δ around three times of the code constraint length is sufficient to secure a near-ML performance. As a consequence of the small early-elimination threshold required, the proposed early-elimination modification not only can considerably reduce the needed stack size but also makes the average decoding computations per information bit irrelevant to the information length.

AB - In this work, we revisited the priority-first sequential-search decoding algorithm proposed in [5]. By adopting a new metric other than the conventional Fano one, the sequential-search decoding in [5] guarantees the maximum-likelihood (ML) performance, and hence, was named the maximum-likelihood sequential decoding algorithm (MLSDA). In comparison with the other maximum-likelihood decoders, it was shown in [5] that the software computational complexity of the MLSDA is in general markedly smaller than that of the Viterbi algorithm. A common problem on sequential-type decoding is that at the signal-to-noise ratio (SNR) below the one corresponding to the cutoff rate, the average decoding complexity per information bit and the required stack size grow rapidly with the information length [7]. This problem somehow prohibits the practical use of sequential-type decoding on convolutional codes with long information sequence at low SNRs. In order to alleviate the problem in the MLSDA, we propose in this work to directly eliminate the top path whose end node is Δ-trellis-level prior to the farthest one among all nodes that have been expanded thus far by the sequential search, which we termed the early elimination. Simulations show that a level threshold Δ around three times of the code constraint length is sufficient to secure a near-ML performance. As a consequence of the small early-elimination threshold required, the proposed early-elimination modification not only can considerably reduce the needed stack size but also makes the average decoding computations per information bit irrelevant to the information length.

UR - http://www.scopus.com/inward/record.url?scp=51649130166&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2007.4557462

DO - 10.1109/ISIT.2007.4557462

M3 - Conference contribution

AN - SCOPUS:51649130166

SN - 1424414296

SN - 9781424414291

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1671

EP - 1675

BT - Proceedings - 2007 IEEE International Symposium on Information Theory, ISIT 2007

T2 - 2007 IEEE International Symposium on Information Theory, ISIT 2007

Y2 - 24 June 2007 through 29 June 2007

ER -