Computation of distributions and their moments in the trellis

Axel Heim; Vladimir Sidorenko; Uli Sorger

doi:10.3934/amc.2008.2.373

Article Contents

2008, Volume 2, Issue 4: 373-391. Doi: 10.3934/amc.2008.2.373

This issue Previous Article Zig-zag and replacement product graphs and LDPC codes Next Article Lee weight enumerators of self-dual codes and theta functions

Computation of distributions and their moments in the trellis

1.
Institute of Telecommunications and Applied Information Theory, Ulm University, Albert-Einstein-Allee 43, 89083 Ulm
2.
Computer Science and Communications Research Unit, University of Luxembourg, 6, rue Richard Coudenhove-Kalergi, L-1359 Luxembourg

Received: November 2007

Revised: June 2008

Published: November 2008

Abstract / Introduction Related Papers Cited by

Abstract

Consider a function whose set of vector arguments with known distribution is described by a trellis. For a certain class of functions, the distribution of the function values can be calculated in the trellis. The forward/backward recursion known from the BCJR algorithm [2] is generalized to compute the moments of these distributions. In analogy to the symbol probabilities, by introducing a constraint at a certain depth in the trellis we obtain symbol distributions and symbol moments, respectively. These moments are required for an efficient implementation of the discriminated belief propagation algorithm in [8], 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 actually providing a generalization of the Viterbi algorithm [10].

Keywords:

Mathematics Subject Classification: 94A15, 94B05.

Citation:

Article Metrics

HTML views() PDF downloads(138) Cited by(0)

Computation of distributions and their moments in the trellis

Abstract

Access History

Article Metrics

Access History

Other Articles By Authors

Catalog

Computation of distributions and their moments in the trellis

Abstract

Access History

SHARE

Article Metrics

Access History

Other Articles By Authors

Catalog

Export File

Citation

Format

Content