American Institute of Mathematical Sciences

Advanced
November  2008, 2(4): 373-391. doi: 10.3934/amc.2008.2.373

Computation of distributions and their moments in the trellis

Axel Heim 1, , Vladimir Sidorenko 1, and  Uli Sorger 2,

1. 

Institute of Telecommunications and Applied Information Theory, Ulm University, Albert-Einstein-Allee 43, 89083 Ulm, Germany, Germany
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

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: Trellis algorithms, decoding, moments, distributions, complexity, Viterbi algorithm, BCJR algorithm.
Mathematics Subject Classification: 94A15, 94B05.
Citation: Axel Heim, Vladimir Sidorenko, Uli Sorger. Computation of distributions and their moments in the trellis. Advances in Mathematics of Communications, 2008, 2 (4) : 373-391. doi: 10.3934/amc.2008.2.373
[1]

Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005
[2]

Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017
[3]

Cheng Peng, Zhaohui Tang, Weihua Gui, Qing Chen, Jing He. A bidirectional weighted boundary distance algorithm for time series similarity computation based on optimized sliding window size. Journal of Industrial & Management Optimization, 2021, 17 (1) : 205-220. doi: 10.3934/jimo.2019107
[4]

Jie Li, Xiangdong Ye, Tao Yu. Mean equicontinuity, complexity and applications. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 359-393. doi: 10.3934/dcds.2020167

2019 Impact Factor: 0.734

Tools

Metrics

  • PDF downloads (83)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences