An upper bound on moments of sequential decoding effort
F. Jelinek · IEEE Transactions on Information Theory · 1969
In this paper we derive an infinite tree code ensemble upper bound on the uth( u \leq 1)moments of the computational effort connected with sequential decoding governed by the Fano \footnote[1]{algorithm}. It is shown that the uth moment of the effort per decoded branch is hounded by a constant, provided the transmission rateR_{0}satisfies inequality (2), This result, although often conjectured, has previously been shown to hold only for positive integral values of u. For a wide class of discrete memoryless channels (that includes all symmetric channels), our bounds agree qualitatively with the lower bounds of Jacobs and Berlekamp [8].