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

Computation of distributions and their moments in the trellis


Institute of Telecommunications and Applied Information Theory, Ulm University, Albert-Einstein-Allee 43, 89083 Ulm, Germany, Germany


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].
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

Irene I. Bouw, Sabine Kampf. Syndrome decoding for Hermite codes with a Sugiyama-type algorithm. Advances in Mathematics of Communications, 2012, 6 (4) : 419-442. doi: 10.3934/amc.2012.6.419


Julia Lieb, Raquel Pinto. A decoding algorithm for 2D convolutional codes over the erasure channel. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021031


Thomas Hillen, Kevin J. Painter, Amanda C. Swan, Albert D. Murtha. Moments of von mises and fisher distributions and applications. Mathematical Biosciences & Engineering, 2017, 14 (3) : 673-694. doi: 10.3934/mbe.2017038


Zi Xu, Siwen Wang, Jinjin Huang. An efficient low complexity algorithm for box-constrained weighted maximin dispersion problem. Journal of Industrial and Management Optimization, 2021, 17 (2) : 971-979. doi: 10.3934/jimo.2020007


Ayache Benhadid, Fateh Merahi. Complexity analysis of an interior-point algorithm for linear optimization based on a new parametric kernel function with a double barrier term. Numerical Algebra, Control and Optimization, 2022  doi: 10.3934/naco.2022003


Xiaojun Zhou, Chunhua Yang, Weihua Gui. State transition algorithm. Journal of Industrial and Management Optimization, 2012, 8 (4) : 1039-1056. doi: 10.3934/jimo.2012.8.1039


Eliana Pepa Risma. A deferred acceptance algorithm with contracts. Journal of Dynamics and Games, 2015, 2 (3&4) : 289-302. doi: 10.3934/jdg.2015005


Jonathan Newton, William H. Sandholm. Stochastic dynamics and Edmonds' algorithm. Journal of Dynamics and Games, 2021  doi: 10.3934/jdg.2021029


François Béguin. Smale diffeomorphisms of surfaces: a classification algorithm. Discrete and Continuous Dynamical Systems, 2004, 11 (2&3) : 261-310. doi: 10.3934/dcds.2004.11.261


Ali Fuat Alkaya, Dindar Oz. An optimal algorithm for the obstacle neutralization problem. Journal of Industrial and Management Optimization, 2017, 13 (2) : 835-856. doi: 10.3934/jimo.2016049


Elena Beretta, Markus Grasmair, Monika Muszkieta, Otmar Scherzer. A variational algorithm for the detection of line segments. Inverse Problems and Imaging, 2014, 8 (2) : 389-408. doi: 10.3934/ipi.2014.8.389


Hadi Khatibzadeh, Vahid Mohebbi, Mohammad Hossein Alizadeh. On the cyclic pseudomonotonicity and the proximal point algorithm. Numerical Algebra, Control and Optimization, 2018, 8 (4) : 441-449. doi: 10.3934/naco.2018027


Siqi Li, Weiyi Qian. Analysis of complexity of primal-dual interior-point algorithms based on a new kernel function for linear optimization. Numerical Algebra, Control and Optimization, 2015, 5 (1) : 37-46. doi: 10.3934/naco.2015.5.37


J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control and Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008


Yuying Shi, Ying Gu, Li-Lian Wang, Xue-Cheng Tai. A fast edge detection algorithm using binary labels. Inverse Problems and Imaging, 2015, 9 (2) : 551-578. doi: 10.3934/ipi.2015.9.551


Simai He, Min Li, Shuzhong Zhang, Zhi-Quan Luo. A nonconvergent example for the iterative water-filling algorithm. Numerical Algebra, Control and Optimization, 2011, 1 (1) : 147-150. doi: 10.3934/naco.2011.1.147


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


Xiangyu Gao, Yong Sun. A new heuristic algorithm for laser antimissile strategy optimization. Journal of Industrial and Management Optimization, 2012, 8 (2) : 457-468. doi: 10.3934/jimo.2012.8.457


Fabián Crocce, Ernesto Mordecki. A non-iterative algorithm for generalized pig games. Journal of Dynamics and Games, 2018, 5 (4) : 331-341. doi: 10.3934/jdg.2018020


Brian D. O. Anderson, Shaoshuai Mou, A. Stephen Morse, Uwe Helmke. Decentralized gradient algorithm for solution of a linear equation. Numerical Algebra, Control and Optimization, 2016, 6 (3) : 319-328. doi: 10.3934/naco.2016014

2020 Impact Factor: 0.935


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

Other articles
by authors

[Back to Top]