An upper bound on moments of sequential decoding effort

In this paper we derive an infinite tree code ensemble upper bound on the th moments of the computational effort connected with sequential decoding governed by the Fano footnote[1]{algorithm}. It is shown that the th moment of the effort per decoded branch is hounded by a constant, provided the transmission rate satisfies inequality (2), This result, although often conjectured, has previously been shown to hold only for positive integral values of . 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].