Computation of moments in the trellis

Axel Heim, Vladimir Sidorenko, Ulrich Sorger

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review


Decisions on sources with memory transmitted over independent channels can be taken by employing trellis calculations. In this paper, it is shown that for a certain class of functions their moments can be computed in the trellis, too. This is done by generalizing the forward/backward recursion known from the BCJR algorithm[1]. In analogy to the symbol probabilities, by introducing a constraint at a certain depth in the trellis we obtain symbol moments. These moments are required for an efficient implementation of the discriminated belief propagation algorithm in[2], and can furthermore be utilized to compute conditional entropies in the trellis. The moment computation algorithm has the same asymptotic complexity as the BCJR algorithm. It is applicable to any commutative semi-ring, thus also providing a generalization of the Viterbi algorithm[3].

Original languageEnglish
Title of host publicationProceedings - 2008 IEEE International Symposium on Information Theory, ISIT 2008
Number of pages5
Publication statusPublished - 2008
Externally publishedYes
Event2008 IEEE International Symposium on Information Theory, ISIT 2008 - Toronto, ON, Canada
Duration: 6 Jul 200811 Jul 2008

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8101


Conference2008 IEEE International Symposium on Information Theory, ISIT 2008
CityToronto, ON


Dive into the research topics of 'Computation of moments in the trellis'. Together they form a unique fingerprint.

Cite this