Analysis of decoding complexity using the Berry-Esseen theorem

Abstract

This work presents a novel technique to analyze the computational efforts of an ordering-free variant of the generalized Dijkstras's algorithm (GDA) and the maximum-likelihood sequential decoding algorithm (MLSDA) based on the Berry-Esseen theorem. Different from the theoretical bounds determined by the conventional central limit theorem argument, which often holds only for sufficiently large blocklength, the new bounds are valid for any blocklength.