An upper bound on moments of sequential decoding effort
- 1 January 1969
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 15 (1) , 140-149
- https://doi.org/10.1109/tit.1969.1054264
Abstract
In this paper we derive an infinite tree code ensemble upper bound on the\nuth(\nu \leq 1)moments of the computational effort connected with sequential decoding governed by the Fano \footnote[1]{algorithm}. It is shown that the\nuth 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\nu. 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].Keywords
This publication has 5 references indexed in Scilit:
- A lower bound to the distribution of computation for sequential decodingIEEE Transactions on Information Theory, 1967
- The distribution of the sequential decoding computation timeIEEE Transactions on Information Theory, 1966
- Sequential Decoding - The Computation Problem*Bell System Technical Journal, 1966
- THE COMPUTATION PROBLEM WITH SEQUENTIAL DECODINGPublished by Defense Technical Information Center (DTIC) ,1965
- A heuristic discussion of probabilistic decodingIEEE Transactions on Information Theory, 1963