Analysis of Sequential Decoding Complexity Using the Berry-Esseen Inequality

Simple item page
dc.creatorChen, Po-Ning
dc.creatorHan, Yunghsiang S.
dc.creatorHartmann, Carlos R. P.
dc.creatorWu, Hong-Bin
dc.date2007-01-05
dc.date2007-08-19
dc.date.accessioned2026-07-07T08:24:09Z
dc.date.available2026-07-07T08:24:09Z
dc.descriptionhis study presents a novel technique to estimate the computational complexity of sequential decoding using the Berry-Esseen theorem. Unlike the theoretical bounds determined by the conventional central limit theorem argument, which often holds only for sufficiently large codeword length, the new bound obtained from the Berry-Esseen theorem is valid for any blocklength. The accuracy of the new bound is then examined for two sequential decoding algorithms, an ordering-free variant of the generalized Dijkstra's algorithm (GDA)(or simplified GDA) and the maximum-likelihood sequential decoding algorithm (MLSDA). Empirically investigating codes of small blocklength reveals that the theoretical upper bound for the simplified GDA almost matches the simulation results as the signal-to-noise ratio (SNR) per information bit ($γ_b$) is greater than or equal to 8 dB. However, the theoretical bound may become markedly higher than the simulated average complexity when $γ_b$ is small. For the MLSDA, the theoretical upper bound is quite close to the simulation results for both high SNR ($γ_b\geq 6$ dB) and low SNR ($γ_b\leq 2$ dB). Even for moderate SNR, the simulation results and the theoretical bound differ by at most \makeblue{0.8} on a $\log_{10}$ scale.
dc.descriptionSubmitted to the IEEE Trans. on Information Theory, 30 pages, 9 figures
dc.identifierhttps://arxiv.org/abs/cs/0701026
dc.identifierhttp://arxiv.org/abs/cs/0701026
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/136246
dc.subjectInformation Theory
dc.titleAnalysis of Sequential Decoding Complexity Using the Berry-Esseen Inequality
dc.typetext

Files

Collections

arXiv