Celebratio Mathematica — Berlekamp

Complete Bibliography

Works connected to I. M. Jacobs

Filter the Bibliography List

year	title	people

			clear

E. Berlekamp and I. M. Jacobs: “A lower bound to the distribution of computation for sequential decoding,” IEEE Trans. Inform. Theory 13 : 2 (April 1967), pp. 167–174. A Russian translation was published in Nekotoryye Voprosy Teorii Kodirovaniya (1970). article

In sequential decoding, the number of computations which the decoder must perform to decode the received digits is a random variable. In this paper, we derive a Paretian lower bound to the distribution of this random variable. We show that \[ P[C > L]L^{-\rho} ,\] where \( C \) is the number of computations which the sequential decoder must perform to decode a block of \( \Lambda \) transmitted bits, and is a parameter which depends on the channel and the rate of the code. Our bound is valid for all sequential decoding schemes and all discrete memoryless channels. In Section II we give an example of a special channel for which a Paretian bound can be easily derived. In Sections III and IV we treat the general channel. In Section V we relate this bound to the memory buffer requirements of real-time sequential decoders. In Section VI, we show that this bound implies that certain moments of the distribution of the computation per digit are infinite, and we determine lower bounds to the rates above which these moments diverge. In most cases, our bounds coincide with previously known upper bounds to rates above which the moments converge. We conclude that the performance of systems using sequential decoding is limited by the computational and buffer capabilities of the decoder, not by the probability of making a decoding error. We further note that our bound applies only to sequential decoding, and that, in certain special cases (Section II), algebraic decoding methods prove superior.

E. Berlekamp and I. M. Jacobs: “A lower bound to the distribution of computation for sequential decoding,” pp. 230–248 in Nekotoryye voprosy teorii kodirovaniya [Some problems of coding theory]. Edited by E. L. Bloch and M. S. Pinsker. Mir (Moscow), 1970. Russian translation of an article published in IEEE Trans. Inform. Theory 13:2 (1970). Zbl 0221.94011 incollection

E. L. Bloch	Related
Mark Shlemovich Pinsker	Related
I. M. Jacobs	Related