Contact:
Marcus Greferath
School of Math. Sciences
University College Dublin
Belfield, Dublin 4, Ireland
Phone:
+353-1-716-2588 (UCD)
+353-85-153-0951 (mobile)

Joachim Rosenthal
Institut of Mathematics
University of Zurich
Winterthurerstrasse 190
8057 Zurich, Switzerland
Phone:
+41-44-63 55884 (office)

ITW 2010 Dublin
IEEE Information Theory Workshop
Dublin, August 30 - September 3, 2010

Graphical models and decoding

Tue 31 Aug, 16.20-18.00, Room 1

Contributed session

Heide Gluesing-Luerssen and Elizabeth Weaver Tail-biting products trellises, the BCJR-construction and their duals

Abstract: We consider the constructions of tail-biting trellises for linear codes introduced by Koetter/Vardy and Nori/Shankar. We will show that each one-to-one product trellis can be merged to a BCJR-trellis defined in a slightly stronger sense than in [Nori/Shankar] and that each trellis that originates from the characteristic matrix defined in [Koetter/Vardy] is a BCJR-trellis. Furthermore, BCJR-trellises are always nonmergeable. Finally, we will consider a certain duality conjecture of [Koetter/Vardy] and show that it holds true for minimal trellises. Tue 31 Aug, 16.20-16.40, Room 1

Ali Al-Bashabsheh and Yongyi Mao Valiant Transform of Forney Graphs

Abstract: In his recent work, Valiant presented a powerful family of new algorithms, which he calls holographic algorithms. The mathematical foundation of holographic algorithms is what is known as Holant Theorem. Synthesizing from Valiant's work, in this paper, we introduce the notion of Valiant transform for normal graphs. Exploiting this synthesis, we establish a more general version of Holant Theorem, which allows an alternative interpretation of the duality results on normal graphs. Tue 31 Aug, 16.40-17.00, Room 1

M. Borges-Quintana, M. A. Borges-Trenard, I. Máarquez-Corbella, and E. Martínez-Moro An Algebraic View to Gradient Descent Decoding

Abstract: There are two gradient descent decoding procedures for binary codes proposed independently by Liebler and by Ashikhmin and Barg. Liebler mentions that both algorithms have the same philosophy but in fact they are rather different. The purpose of this communication is to show that both algorithms can be seen as two ways of understanding the reduction process algebraic monoid structure related to the code. The main tool used for showing this is the Gröbner representation of the monoid associated to the linear code. Tue 31 Aug, 17.00-17.20, Room 1

Sabine Kampf and Martin Bossert The Euclidean Algorithm for Generalized Minimum Distance Decoding of Reed-Solomon Codes

Abstract: This paper presents a method to merge Generalized Minimum Distance decoding of Reed-Solomon codes with the extended Euclidean algorithm. By merge, we mean that the steps performed in Generalized Minimum Distance decoding are similar to those of the extended Euclidean algorithm. The resulting algorithm has a complexity of O(n2). Tue 31 Aug, 17.20-17.40, Room 1

Emmanuel Abbe and Rethnakaran Pulikkoonattu Universal A Posteriori Metrics Game

Abstract: Over binary input channels, the uniform distribution is a universal prior, in the sense that it maximizes the worst case mutual information of all binary input channels and achieves at least 94.2 % of the capacity. In this paper, we address a similar question. We look for the best collection of finitely many a posteriori metrics, to maximize the worst case mismatched mutual information achieved by decoding with these metrics (instead of an optimal decoder such as the Maximum Likelihood (ML) tuned to the true channel). It is shown that for binary input and output channels, two metrics suffice to actually achieve the same performance as an optimal decoder. In particular, this implies that there exist a decoder which is generalized linear and achieves at least 94.2 % of the compound capacity on any compound set, without knowledge of the underlying set. Tue 31 Aug, 17.40-18.00, Room 1

Back to previous page

Return to conference mainpage

SPONSORS