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]

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
[2]

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
[3]

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
[4]

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
[5]

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
[6]

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

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
[8]

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

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
[10]

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
[11]

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
[12]

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
[13]

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
[14]

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
[15]

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
[16]

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
[17]

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
[18]

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
[19]

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
[20]

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

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy